Designing Cloud File Storage Systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// Server revision-based conflict detection
interface FileVersion {
    path: string;
    revision: number;      // Server-assigned, monotonically increasing
    contentHash: string;   // SHA-256 of file content
    parentRevision: number; // The revision this was based on
}
 
class ConflictDetector {
    // Called when client attempts to upload
    detectConflict(
        serverVersion: FileVersion,
        clientUpload: { parentRevision: number; contentHash: string }
    ): 'no_conflict' | 'conflict' | 'no_change' {
        
        // Client is up-to-date in sync with server
        if (clientUpload.parentRevision === serverVersion.revision) {
            if (clientUpload.contentHash === serverVersion.contentHash) {
                return 'no_change';  // Same content, no upload needed
            }
            return 'no_conflict';    // Normal upload proceeds
        }
        
        // Client's parent doesn't match server's current revision
        // Server has been modified since client's last sync
        if (clientUpload.parentRevision < serverVersion.revision) {
            // But content is same? No real conflict
            if (clientUpload.contentHash === serverVersion.contentHash) {
                return 'no_change';
            }
            return 'conflict';  // True conflict: different content
        }
        
        // Client claims newer parent than server knows?
        // This shouldn't happen - indicates client bug
        throw new Error('Invalid state: client revision ahead of server');
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

// Simplified three-way merge algorithm
type MergeResult = 
    | { status: 'success'; content: string[] }
    | { status: 'conflict'; conflicts: ConflictRegion[] };
 
interface ConflictRegion {
    lineStart: number;
    localContent: string[];
    remoteContent: string[];
}
 
function threeWayMerge(
    base: string[],
    local: string[],
    remote: string[]
): MergeResult {
    // Compute differences
    const localDiff = computeDiff(base, local);   // What local changed
    const remoteDiff = computeDiff(base, remote); // What remote changed
    
    const result: string[] = [];
    const conflicts: ConflictRegion[] = [];
    
    let baseIdx = 0, localIdx = 0, remoteIdx = 0;
    
    while (baseIdx < base.length || localIdx < local.length || remoteIdx < remote.length) {
        const localChanged = localDiff.hasChange(baseIdx);
        const remoteChanged = remoteDiff.hasChange(baseIdx);
        
        if (!localChanged && !remoteChanged) {
            // Neither changed - keep base
            result.push(base[baseIdx]);
            baseIdx++; localIdx++; remoteIdx++;
        } 
        else if (localChanged && !remoteChanged) {
            // Only local changed - use local
            const change = localDiff.getChange(baseIdx);
            result.push(...change.newLines);
            baseIdx += change.baseLines;
            localIdx += change.newLines.length;
            remoteIdx += change.baseLines;
        }
        else if (!localChanged && remoteChanged) {
            // Only remote changed - use remote  
            const change = remoteDiff.getChange(baseIdx);
            result.push(...change.newLines);
            baseIdx += change.baseLines;
            localIdx += change.baseLines;
            remoteIdx += change.newLines.length;
        }
        else {
            // BOTH changed - check if same change
            const localChange = localDiff.getChange(baseIdx);
            const remoteChange = remoteDiff.getChange(baseIdx);
            
            if (arraysEqual(localChange.newLines, remoteChange.newLines)) {
                // Same change - no conflict
                result.push(...localChange.newLines);
            } else {
                // Different changes - TRUE CONFLICT
                conflicts.push({
                    lineStart: result.length,
                    localContent: localChange.newLines,
                    remoteContent: remoteChange.newLines,
                });
                // Add conflict markers
                result.push('<<<<<<< LOCAL');
                result.push(...localChange.newLines);
                result.push('=======');
                result.push(...remoteChange.newLines);
                result.push('>>>>>>> REMOTE');
            }
            baseIdx += Math.max(localChange.baseLines, remoteChange.baseLines);
            localIdx += localChange.newLines.length;
            remoteIdx += remoteChange.newLines.length;
        }
    }
    
    return conflicts.length > 0 
        ? { status: 'conflict', conflicts }
        : { status: 'success', content: result };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

// Edge case handlers for file system conflicts
class EdgeCaseHandler {
    
    // Delete vs Edit: User A deletes, User B edits
    handleDeleteVsEdit(
        deleteOp: DeleteOperation,
        editOp: EditOperation
    ): Resolution {
        // Never lose edits - restore file with new edits
        return {
            action: 'restore_and_apply',
            steps: [
                { op: 'create', path: editOp.path, content: editOp.newContent },
                { 
                    op: 'notify', 
                    user: deleteOp.userId,
                    message: `${editOp.userEmail} edited ${editOp.path} ` +
                                `which you deleted. File has been restored.`
                }
            ]
        };
    }
    
    // Rename to same name by different users
    handleRenameNameConflict(
        rename1: RenameOperation,
        rename2: RenameOperation
    ): Resolution {
        // Both trying to rename to 'report.docx'
        // First one wins, second gets deduplicated name
        const winner = rename1.timestamp < rename2.timestamp ? rename1 : rename2;
        const loser = winner === rename1 ? rename2 : rename1;
        
        return {
            action: 'deduplicate',
            steps: [
                { op: 'rename', from: winner.oldPath, to: winner.newPath },
                { 
                    op: 'rename', 
                    from: loser.oldPath, 
                    to: this.deduplicateName(loser.newPath)  // 'report (1).docx'
                }
            ]
        };
    }
    
    // Folder move creating cycle
    handleMoveCycle(
        moveA: MoveOperation,  // X into Y
        moveB: MoveOperation   // Y into X
    ): Resolution {
        // Detect cycle: if we apply both, neither can be root
        // Resolution: Apply first, reject second with explanation
        const first = moveA.timestamp < moveB.timestamp ? moveA : moveB;
        const second = first === moveA ? moveB : moveA;
        
        return {
            action: 'partial_apply',
            steps: [
                { op: 'move', operation: first },
                { 
                    op: 'reject', 
                    operation: second,
                    reason: 'Would create folder cycle'
                },
                {
                    op: 'notify',
                    user: second.userId,
                    message: `Could not move ${second.sourcePath} - would create ` +
                            `circular structure.`
                }
            ]
        };
    }
    
    // Cross-platform case sensitivity
    handleCaseSensitivityConflict(
        file1: string,  // 'README.md' (created on Linux)
        file2: string   // 'readme.md' (created on Windows)
    ): Resolution {
        // These are same file on Windows/macOS, different on Linux
        // Auto-rename one to avoid conflict on case-insensitive systems
        return {
            action: 'auto_rename',
            steps: [
                { 
                    op: 'rename',
                    from: file2,
                    to: this.addSuffix(file2, '-1'),  // 'readme-1.md'
                    platform: 'case_insensitive'
                },
                {
                    op: 'notify',
                    broadcast: true,
                    message: `Renamed '${file2}' to avoid conflict with '${file1}' ` +
                        `on case-insensitive systems.`
                }
            ]
        };
    }
}