System Design (HLD)Google Drive / Dropbox

Designing Cloud File Storage Systems

LevelAdvanced

Duration90 mins

TopicGoogle Drive / Dropbox

2 / 6

File Synchronization

The Heart of Cloud Storage

File synchronization is the defining feature that separates cloud storage from simple file hosting. It's the invisible magic that ensures your files appear consistently across your laptop, phone, tablet, and web browser—regardless of where you last edited them.

Synchronization is fundamentally a distributed systems problem. Each device acts as a replica, and changes must propagate bidirectionally while maintaining consistency. This page explores the protocols, algorithms, and architectures that make reliable synchronization possible at scale.

The core challenge can be summarized as: How do we keep N replicas consistent when any of them can be modified at any time, potentially while offline, with varying network conditions, and without user intervention?

Learning Objectives

By the end of this page, you'll understand: (1) How sync protocols detect and propagate changes, (2) Client-server vs peer-to-peer sync models, (3) Delta synchronization for bandwidth efficiency, (4) State machine design for sync clients, and (5) Handling network partitions and offline operation.

Synchronization Models

There are fundamentally two approaches to file synchronization, each with distinct trade-offs. Understanding both is essential because production systems often use hybrid approaches.

Client-Server Model

•Central server is the source of truth
•Clients sync up (push) and sync down (pull) from server
•Server coordinates all conflict resolution
•Pros: Simple conflict handling, easy auditing, clear consistency model
•Cons: Server is single point of failure, higher latency for device-to-device sync
•Examples: Dropbox, Google Drive, OneDrive

Peer-to-Peer Model

•No central authority—all peers are equal
•Devices sync directly with each other when possible
•Conflict resolution is distributed (CRDTs or similar)
•Pros: Works offline, low latency LAN sync, no server dependency
•Cons: Complex conflict resolution, harder auditing, eventual consistency only
•Examples: Syncthing, Resilio Sync

Hybrid Approach (Most Common):

Production cloud storage systems typically use a server-centric model with peer-to-peer optimizations:

The cloud server remains the authoritative source of truth
Clients can sync directly on the same LAN for speed (Dropbox LAN Sync)
The server still records all changes for consistency and recovery

This hybrid approach provides the consistency guarantees of client-server while optimizing for the common case where users work from a single location with multiple devices on the same network.

Interview Insight

In interviews, start with the client-server model since it's simpler and what major products use. Mention P2P optimizations as an enhancement. If asked about fully decentralized systems, discuss the trade-off: you gain offline capability and remove the server bottleneck, but conflict resolution becomes significantly more complex.

Change Detection

Before syncing changes, we must first detect that changes occurred. This seemingly simple task is surprisingly complex because the sync client must monitor the local file system continuously without consuming excessive resources.

Change Detection Strategies

•Polling/Scanning — Periodically scan the entire file tree, comparing file attributes (size, mtime) against a local database. Simple but CPU-intensive for large folders. Typical polling intervals: 5-60 seconds.
•File System Events — Use OS-provided file system watching APIs: inotify (Linux), FSEvents (macOS), ReadDirectoryChangesW (Windows). Near-instant detection, low CPU usage, but each OS has different APIs and quirks.
•Hybrid Approach — Use file system events for immediate detection, with periodic full scans as a safety net. Events can be lost if the buffer overflows or during heavy activity.

File System Event APIs by Platform
Platform	API	Characteristics	Limitations
Linux	inotify	Per-file watches, event-based	Limited watch count (~8K default), no recursive watching
macOS	FSEvents	Per-directory, batched events	Latency (~1s default), can miss rapid changes
Windows	ReadDirectoryChangesW	Recursive capable, immediate	Buffer overflow on burst, handle limits
Cross-platform	libfsevent / watchman	Unified API	Added dependency, may not cover all cases

Determining What Changed:

Once we detect a file modification, we need to determine the type of change:

Change Types:
├── CREATE — New file added
├── MODIFY — Existing file content changed
├── DELETE — File removed
├── RENAME — File moved or renamed
└── ATTRIBUTE — Permissions or metadata changed

The Rename Detection Problem:

File system events typically report renames as separate DELETE + CREATE events. Detecting that these are actually a rename (rather than deleting one file and creating a different one) requires correlation:

Inode-based (Unix): If CREATE has same inode as recent DELETE, it's a rename
Content-hash based: If CREATE has same hash as recent DELETE, likely a rename
Timing-based: DELETE and CREATE within short window, same size, probably rename

Correctly detecting renames is important because syncing a rename is much cheaper than re-uploading the entire file.

The Sync Folder Size Problem

Users with millions of files can exhaust watch limits. Dropbox faced this when users synced entire drives. Solutions include: (1) Raising system limits via configuration, (2) Falling back to polling for large folders, (3) Implementing smart watch management that prioritizes active folders. There's no perfect solution—it's a fundamental OS limitation.

Sync Protocol Design

The sync protocol defines how clients and servers communicate changes. A well-designed protocol minimizes round trips, handles failures gracefully, and provides clear consistency guarantees.

Server State Model:

The server maintains a global, ordered log of all changes (similar to a database transaction log):

Journal/Changelog:
┌─────────┬────────────────┬───────────┬─────────────────┐
│ cursor  │ path           │ operation │ metadata        │
├─────────┼────────────────┼───────────┼─────────────────┤
│ 1001    │ /work/doc.txt  │ CREATE    │ {size, hash...} │
│ 1002    │ /work/doc.txt  │ MODIFY    │ {size, hash...} │
│ 1003    │ /photos/a.jpg  │ DELETE    │ {}              │
│ 1004    │ /work/doc.txt  │ RENAME    │ {to: /doc.txt}  │
└─────────┴────────────────┴───────────┴─────────────────┘

Each entry has a monotonically increasing cursor. Clients track their last-synced cursor and request all changes since then.

Core Sync Operations

•list_folder(path) — Returns current state of a folder. Used for initial sync and recovery.
•list_folder_continue(cursor) — Returns changes since cursor. The primary sync mechanism.
•get_metadata(path) — Returns current metadata for a specific file. Used for conflict checks.
•upload(path, content, parent_rev) — Uploads new content. parent_rev enables conflict detection.
•download(path, rev) — Downloads specific revision of file content.
•commit_batch(operations) — Atomically applies multiple operations. Enables folder moves.

Long Polling for Real-Time Updates:

Clients don't continuously poll for changes. Instead, they use long polling:

Client Flow:
1. Call list_folder_longpoll(cursor, timeout=90s)
2. Server holds connection until:
   a. Changes occur → return immediately
   b. Timeout expires → return "no changes"
3. If changes indicated, call list_folder_continue(cursor)
4. Apply changes locally, update cursor
5. Repeat from step 1

Long polling reduces server load dramatically compared to frequent polling while maintaining near-real-time sync (typically <5 second latency).

Converting Mermaid diagram...

WebSocket vs Long Polling

WebSockets provide true real-time bidirectional communication but add operational complexity (connection state, reconnection logic, load balancer configuration). Long polling achieves nearly the same latency (<5 seconds) with simpler infrastructure. Most cloud storage services use long polling. WebSockets are typically reserved for real-time collaborative editing.

Delta Synchronization

Delta synchronization is a critical optimization: instead of re-uploading or re-downloading entire files when they change, we transfer only the changed portions. This dramatically reduces bandwidth usage and sync time, especially for large files.

The Problem:

Consider a 100 MB presentation file where you add one slide (1 MB of changes). Without delta sync, you upload 100 MB. With delta sync, you upload ~1 MB. This is a 100x improvement in sync speed and bandwidth usage.

Content-Defined Chunking (CDC):

The key to delta sync is breaking files into chunks where chunk boundaries are determined by content, not fixed positions. This means if you insert 10 bytes at the start of a file, only the first chunk changes—subsequent chunks remain identical and don't need re-upload.

How CDC Works:

Slide a rolling hash window over file content
When hash matches a pattern (e.g., last N bits are zero), mark a chunk boundary
Hash each chunk with a strong hash (SHA-256)
Store/upload chunks by their hash (content-addressed storage)

Example: File with CDC at average 4MB chunk size

Original File:               [Chunk A][Chunk B][Chunk C][Chunk D]
Hash values:                    abc123   def456   ghi789   jkl012

After inserting 10KB at start:
                             [Chunk A'][Chunk B][Chunk C][Chunk D]
Hash values:                    xyz999   def456   ghi789   jkl012
                                  ↑
                            Only this chunk is different

Rolling Hash Algorithms

•Rabin Fingerprinting — The classic choice, mathematically elegant. Provides uniform chunk size distribution. Used by rsync and many backup systems.
•Gear Hash / FastCDC — Optimized for speed, using lookup tables instead of polynomial arithmetic. 2-3x faster than Rabin with similar distribution. Used by Dropbox.
•Buzhash — Cyclic polynomial rolling hash. Good performance, easy to implement. Used by various backup tools.

Chunk Size Trade-offs
Avg Chunk Size	Upload Granularity	Metadata Overhead	Best For
256 KB	Fine-grained, minimal re-upload	High (millions of chunks)	Frequently edited documents
1 MB	Balanced approach	Moderate	General purpose
4 MB	Coarse-grained	Low	Large media files, archival
Adaptive	Varies by file type	Optimized	Production systems

Upload Flow with Delta Sync:

1. Client detects file modification
2. Re-chunk the file using CDC
3. Hash each chunk
4. Query server: "Which of these chunks do you already have?"
5. Server returns list of missing chunks
6. Client uploads only missing chunks
7. Client sends manifest: "File X = [chunk_A, chunk_B, chunk_C]"
8. Server reconstructs file from chunks

This flow also enables cross-user deduplication: if two users upload the same file, the chunks are stored only once. Dropbox reportedly achieves 50%+ storage savings through deduplication.

Deduplication Privacy Concerns

Cross-user deduplication can leak information. If uploading chunk X is instant (server already has it), an attacker could infer that another user has the same content. Mitigations include: (1) always simulating upload time, (2) per-user encryption (breaks dedup), or (3) convergent encryption (same plaintext → same ciphertext, enables dedup). Each has trade-offs.

Client State Machine

The sync client maintains a sophisticated state machine to track every file's synchronization status. Understanding this state machine is crucial for implementing reliable sync behavior.

Converting Mermaid diagram...

File States Explained:

State	Icon	Meaning
Synced	✓ Green checkmark	File is identical locally and on server
LocalChange	↑ Blue arrow	Local modifications pending upload
Uploading	↑ Animated	Upload in progress
RemoteChange	↓ Blue arrow	Server has newer version, download pending
Downloading	↓ Animated	Download in progress
Conflict	⟷ Red icon	Both local and remote changes exist
Error	⚠ Yellow warning	Sync failed (permissions, disk full, etc.)

State Transitions in Detail

•Synced → LocalChange: File system watcher detects local modification. Client records the change in a local journal. The change is queued for upload.
•LocalChange → Uploading: Upload worker picks up the file. Client computes content hash and chunks, initiates upload to server.
•Uploading → Synced: Server confirms upload. Client updates local database with new revision. File is now synced.
•Synced → RemoteChange: Long-poll returns changes from server. Client records remote change, queues download.
•RemoteChange → Downloading: Download worker fetches new content. Content is downloaded to a temp file first.
•Downloading → Synced: Download complete, verified by hash. Temp file atomically replaces original. Database updated.
•Any → Conflict: Simultaneous local and remote changes detected. Both versions preserved. User notification triggered.

sync_state.ts
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
// Simplified sync state machine implementation
interface FileState {
    path: string;
    localVersion: number;    // Local modification counter
    remoteVersion: number;   // Server's revision number
    state: 'synced' | 'local_change' | 'uploading' | 
           'remote_change' | 'downloading' | 'conflict';
    localHash?: string;      // Hash of local content
    remoteHash?: string;     // Hash of server content
    error?: string;
}
 
class SyncStateMachine {
    private states: Map<string, FileState> = new Map();
    
    // Called when file system watcher detects local change
    onLocalChange(path: string, newHash: string): void {
        const state = this.getState(path);
        
        if (state.state === 'synced' || state.state === 'local_change') {
            state.state = 'local_change';
            state.localVersion++;
            state.localHash = newHash;
            this.queueUpload(path);
        } else if (state.state === 'remote_change' || state.state === 'downloading') {
            // Local change while remote change pending → conflict
            state.state = 'conflict';
            this.notifyConflict(path);
        }
    }
    
    // Called when server reports remote change
    onRemoteChange(path: string, newRevision: number, newHash: string): void {
        const state = this.getState(path);
        
        if (state.state === 'synced') {
            state.state = 'remote_change';
            state.remoteVersion = newRevision;
            state.remoteHash = newHash;
            this.queueDownload(path);
        } else if (state.state === 'local_change' || state.state === 'uploading') {
            // Remote change while local change pending → conflict
            state.state = 'conflict';
            this.notifyConflict(path);
        }
    }
    
    // Called when upload completes successfully
    onUploadSuccess(path: string, newRevision: number): void {
        const state = this.getState(path);
        state.state = 'synced';
        state.remoteVersion = newRevision;
        state.remoteHash = state.localHash;
    }
    
    // Called when upload fails
    onUploadError(path: string, error: string): void {
        const state = this.getState(path);
        if (error === 'CONFLICT') {
            state.state = 'conflict';
            this.notifyConflict(path);
        } else {
            // Transient error, retry
            state.state = 'local_change';
            this.scheduleRetry(path);
        }
    }
}

Crash Recovery

The state machine must be durable. If the sync client crashes mid-upload, it must resume correctly after restart. This requires persisting state to disk (SQLite is common) and using atomic operations. Never update state before the operation completes; always assume crash can happen at any moment.

Handling Offline Operation

Users expect to work on files even without internet connectivity, with changes syncing automatically when connectivity returns. This requires the sync client to be a fully functional offline replica with sophisticated reconnection logic.

Offline Capability Requirements

•Local State Persistence — The complete file system state (metadata, not content) is cached locally in a database. Users can browse their files even offline.
•Selective File Caching — Users mark files/folders for offline access. These files are pre-downloaded and kept current. Storage limits apply.
•Change Journaling — All local changes are recorded in a persistent journal. This journal survives restarts and is replayed on reconnection.
•Conflict Accumulation — Multiple offline sessions may create multiple conflicting versions. All must be preserved and presented for resolution.
•Graceful Degradation — The UI clearly indicates offline status. Operations that require connectivity (sharing, getting links) are disabled with explanation.

Reconnection Flow:

1. Connectivity Detected
   └─> Check current server cursor
   
2. If server cursor > local cursor:
   └─> Fetch all remote changes since local cursor
   └─> For each remote change:
       ├─> If no local change to same file: apply remote
       └─> If local change exists: mark conflict
   
3. Replay local journal:
   └─> For each local change:
       ├─> If file not conflicted: upload
       └─> If conflicted: create conflict copy, upload
   
4. Resolve conflicts:
   └─> Present conflicts to user
   └─> User chooses: keep local, keep remote, or keep both
   
5. Update cursors, clear journal, back to normal sync

Offline Scenarios and Handling
Scenario	Detection	Resolution
Edit same file on two offline devices	Both have local changes with same parent revision	Create conflict copies, user picks winner
Delete file on one device, edit on another	Remote DELETE vs local MODIFY	Keep both: restore file and apply edits
Rename to same name on two devices	Two files claiming same path	Auto-rename second file (e.g., 'file (1).txt')
Edit file, then delete on same device	Local journal: MODIFY then DELETE	Only send DELETE to server (MODIFY overridden)
Create folder, delete parent folder on other device	Child's parent no longer exists remotely	Recreate parent or move orphans to root

The Extended Offline Problem

If a device is offline for weeks, the server's change journal may have rolled past the client's cursor (journals have limited retention). In this case, the client must do a full tree comparison (expensive) rather than incremental sync. Production systems typically retain journals for 30-90 days for this reason.

Sync Optimizations

Production sync clients employ numerous optimizations to minimize sync time, reduce bandwidth usage, and provide responsive user experience. Here are the key techniques:

Bandwidth Optimizations

•Chunk Deduplication — Before uploading, query server for existing chunks. Skip chunks already present. Typically saves 30-60% bandwidth.
•Compression — Compress chunks before upload (gzip, zstd). Particularly effective for text and documents. Disabled for already-compressed formats (JPEG, MP4).
•Transfer Scheduling — Deprioritize sync during user activity. Sync in background at lower priority. Pause during video calls or metered connections.
•Bandwidth Throttling — User-configurable upload/download limits. Auto-detect metered connections and reduce speed.

Latency Optimizations

•LAN Sync — Detect other devices on same LAN, sync directly without round-trip to cloud. Sub-second sync for local files.
•Streaming Sync — Start syncing immediately on change, don't wait for file to finish writing. Particularly valuable for large files being created.
•Predictive Pre-fetch — Pre-download files user is likely to need (recently accessed, about to present). ML models can predict access patterns.
•Parallel Transfers — Multiple concurrent uploads/downloads (typically 4-8). Saturate available bandwidth.

Resource Optimizations

•Batched Updates — Coalesce rapid changes (e.g., IDE auto-save) into single sync operations. Reduces API calls and server load.
•Prioritized Queue — Sync user's current working folder first. Deprioritize untouched folders. Age-based priority decay.
•Lazy Hashing — Defer hash computation until needed. Use file attributes (size, mtime) for quick-change detection, hash only when uploading.
•Memory-Mapped Chunking — Use mmap for large files to avoid loading entire file into memory during chunking.

The Dropbox LAN Sync Innovation

Dropbox's LAN sync broadcasts on UDP port 17500, allowing devices to discover each other and sync directly. This was a critical feature for offices where 50 employees might sync a 100MB presentation—without LAN sync, the office internet got hammered 50 times. With it, one upload to cloud, 49 fast LAN transfers.

Summary: File Synchronization Mastery

File synchronization is the invisible backbone of cloud storage systems. Let's consolidate the key concepts covered:

Key Takeaways

•Client-server is the dominant model — Central server provides consistency guarantees and simplifies conflict resolution. P2P optimizations (LAN sync) enhance performance without sacrificing correctness.
•Change detection uses file system events — Platform-specific APIs (inotify, FSEvents) enable near-instant detection with minimal CPU usage. Periodic scanning provides a safety net.
•The sync protocol is cursor-based — Clients track their position in the server's change log. Long polling provides real-time updates without constant polling overhead.
•Delta sync is essential at scale — Content-defined chunking (CDC) with rolling hashes enables efficient incremental sync. Only changed chunks are transferred.
•The client is a sophisticated state machine — Each file progresses through states (synced → local_change → uploading → synced). Crash recovery requires persistent state.
•Offline operation requires change journaling — Local changes are recorded and replayed on reconnection. Extended offline periods may require full resync.

What's Next:

With synchronization understood, the next critical challenge is Conflict Resolution—what happens when the same file is modified on multiple devices simultaneously. We'll explore detection algorithms, resolution strategies, and the trade-offs between automatic and manual resolution.

Page Complete

You now understand the core mechanisms of file synchronization: change detection, sync protocols, delta sync, and state machine design. These concepts form the foundation for any reliable cloud storage system. Next, we tackle the thorniest problem in distributed file systems: conflict resolution.

2 / 6

Loading learning content...

System Design (HLD)Google Drive / Dropbox

Designing Cloud File Storage Systems

LevelAdvanced

Duration90 mins

TopicGoogle Drive / Dropbox

2 / 6

File Synchronization

The Heart of Cloud Storage

Learning Objectives

Synchronization Models

There are fundamentally two approaches to file synchronization, each with distinct trade-offs. Understanding both is essential because production systems often use hybrid approaches.

Client-Server Model

•Central server is the source of truth
•Clients sync up (push) and sync down (pull) from server
•Server coordinates all conflict resolution
•Pros: Simple conflict handling, easy auditing, clear consistency model
•Cons: Server is single point of failure, higher latency for device-to-device sync
•Examples: Dropbox, Google Drive, OneDrive

Peer-to-Peer Model

•No central authority—all peers are equal
•Devices sync directly with each other when possible
•Conflict resolution is distributed (CRDTs or similar)
•Pros: Works offline, low latency LAN sync, no server dependency
•Cons: Complex conflict resolution, harder auditing, eventual consistency only
•Examples: Syncthing, Resilio Sync

Hybrid Approach (Most Common):

Production cloud storage systems typically use a server-centric model with peer-to-peer optimizations:

The cloud server remains the authoritative source of truth
Clients can sync directly on the same LAN for speed (Dropbox LAN Sync)
The server still records all changes for consistency and recovery

This hybrid approach provides the consistency guarantees of client-server while optimizing for the common case where users work from a single location with multiple devices on the same network.

Interview Insight

Change Detection

Change Detection Strategies

•Polling/Scanning — Periodically scan the entire file tree, comparing file attributes (size, mtime) against a local database. Simple but CPU-intensive for large folders. Typical polling intervals: 5-60 seconds.
•File System Events — Use OS-provided file system watching APIs: inotify (Linux), FSEvents (macOS), ReadDirectoryChangesW (Windows). Near-instant detection, low CPU usage, but each OS has different APIs and quirks.
•Hybrid Approach — Use file system events for immediate detection, with periodic full scans as a safety net. Events can be lost if the buffer overflows or during heavy activity.

File System Event APIs by Platform
Platform	API	Characteristics	Limitations
Linux	inotify	Per-file watches, event-based	Limited watch count (~8K default), no recursive watching
macOS	FSEvents	Per-directory, batched events	Latency (~1s default), can miss rapid changes
Windows	ReadDirectoryChangesW	Recursive capable, immediate	Buffer overflow on burst, handle limits
Cross-platform	libfsevent / watchman	Unified API	Added dependency, may not cover all cases

Determining What Changed:

Once we detect a file modification, we need to determine the type of change:

Change Types:
├── CREATE — New file added
├── MODIFY — Existing file content changed
├── DELETE — File removed
├── RENAME — File moved or renamed
└── ATTRIBUTE — Permissions or metadata changed

The Rename Detection Problem:

Inode-based (Unix): If CREATE has same inode as recent DELETE, it's a rename
Content-hash based: If CREATE has same hash as recent DELETE, likely a rename
Timing-based: DELETE and CREATE within short window, same size, probably rename

Correctly detecting renames is important because syncing a rename is much cheaper than re-uploading the entire file.

The Sync Folder Size Problem

Sync Protocol Design

The sync protocol defines how clients and servers communicate changes. A well-designed protocol minimizes round trips, handles failures gracefully, and provides clear consistency guarantees.

Server State Model:

The server maintains a global, ordered log of all changes (similar to a database transaction log):

Journal/Changelog:
┌─────────┬────────────────┬───────────┬─────────────────┐
│ cursor  │ path           │ operation │ metadata        │
├─────────┼────────────────┼───────────┼─────────────────┤
│ 1001    │ /work/doc.txt  │ CREATE    │ {size, hash...} │
│ 1002    │ /work/doc.txt  │ MODIFY    │ {size, hash...} │
│ 1003    │ /photos/a.jpg  │ DELETE    │ {}              │
│ 1004    │ /work/doc.txt  │ RENAME    │ {to: /doc.txt}  │
└─────────┴────────────────┴───────────┴─────────────────┘

Each entry has a monotonically increasing cursor. Clients track their last-synced cursor and request all changes since then.

Core Sync Operations

•list_folder(path) — Returns current state of a folder. Used for initial sync and recovery.
•list_folder_continue(cursor) — Returns changes since cursor. The primary sync mechanism.
•get_metadata(path) — Returns current metadata for a specific file. Used for conflict checks.
•upload(path, content, parent_rev) — Uploads new content. parent_rev enables conflict detection.
•download(path, rev) — Downloads specific revision of file content.
•commit_batch(operations) — Atomically applies multiple operations. Enables folder moves.

Long Polling for Real-Time Updates:

Clients don't continuously poll for changes. Instead, they use long polling:

Client Flow:
1. Call list_folder_longpoll(cursor, timeout=90s)
2. Server holds connection until:
   a. Changes occur → return immediately
   b. Timeout expires → return "no changes"
3. If changes indicated, call list_folder_continue(cursor)
4. Apply changes locally, update cursor
5. Repeat from step 1

Long polling reduces server load dramatically compared to frequent polling while maintaining near-real-time sync (typically <5 second latency).

Converting Mermaid diagram...

WebSocket vs Long Polling

Delta Synchronization

The Problem:

Content-Defined Chunking (CDC):

How CDC Works:

Slide a rolling hash window over file content
When hash matches a pattern (e.g., last N bits are zero), mark a chunk boundary
Hash each chunk with a strong hash (SHA-256)
Store/upload chunks by their hash (content-addressed storage)

Example: File with CDC at average 4MB chunk size

Original File:               [Chunk A][Chunk B][Chunk C][Chunk D]
Hash values:                    abc123   def456   ghi789   jkl012

After inserting 10KB at start:
                             [Chunk A'][Chunk B][Chunk C][Chunk D]
Hash values:                    xyz999   def456   ghi789   jkl012
                                  ↑
                            Only this chunk is different

Rolling Hash Algorithms

•Rabin Fingerprinting — The classic choice, mathematically elegant. Provides uniform chunk size distribution. Used by rsync and many backup systems.
•Gear Hash / FastCDC — Optimized for speed, using lookup tables instead of polynomial arithmetic. 2-3x faster than Rabin with similar distribution. Used by Dropbox.
•Buzhash — Cyclic polynomial rolling hash. Good performance, easy to implement. Used by various backup tools.

Chunk Size Trade-offs
Avg Chunk Size	Upload Granularity	Metadata Overhead	Best For
256 KB	Fine-grained, minimal re-upload	High (millions of chunks)	Frequently edited documents
1 MB	Balanced approach	Moderate	General purpose
4 MB	Coarse-grained	Low	Large media files, archival
Adaptive	Varies by file type	Optimized	Production systems

Upload Flow with Delta Sync:

1. Client detects file modification
2. Re-chunk the file using CDC
3. Hash each chunk
4. Query server: "Which of these chunks do you already have?"
5. Server returns list of missing chunks
6. Client uploads only missing chunks
7. Client sends manifest: "File X = [chunk_A, chunk_B, chunk_C]"
8. Server reconstructs file from chunks

This flow also enables cross-user deduplication: if two users upload the same file, the chunks are stored only once. Dropbox reportedly achieves 50%+ storage savings through deduplication.

Deduplication Privacy Concerns

Client State Machine

The sync client maintains a sophisticated state machine to track every file's synchronization status. Understanding this state machine is crucial for implementing reliable sync behavior.

Converting Mermaid diagram...

File States Explained:

State	Icon	Meaning
Synced	✓ Green checkmark	File is identical locally and on server
LocalChange	↑ Blue arrow	Local modifications pending upload
Uploading	↑ Animated	Upload in progress
RemoteChange	↓ Blue arrow	Server has newer version, download pending
Downloading	↓ Animated	Download in progress
Conflict	⟷ Red icon	Both local and remote changes exist
Error	⚠ Yellow warning	Sync failed (permissions, disk full, etc.)

State Transitions in Detail

•Synced → LocalChange: File system watcher detects local modification. Client records the change in a local journal. The change is queued for upload.
•LocalChange → Uploading: Upload worker picks up the file. Client computes content hash and chunks, initiates upload to server.
•Uploading → Synced: Server confirms upload. Client updates local database with new revision. File is now synced.
•Synced → RemoteChange: Long-poll returns changes from server. Client records remote change, queues download.
•RemoteChange → Downloading: Download worker fetches new content. Content is downloaded to a temp file first.
•Downloading → Synced: Download complete, verified by hash. Temp file atomically replaces original. Database updated.
•Any → Conflict: Simultaneous local and remote changes detected. Both versions preserved. User notification triggered.

sync_state.ts
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
// Simplified sync state machine implementation
interface FileState {
    path: string;
    localVersion: number;    // Local modification counter
    remoteVersion: number;   // Server's revision number
    state: 'synced' | 'local_change' | 'uploading' | 
           'remote_change' | 'downloading' | 'conflict';
    localHash?: string;      // Hash of local content
    remoteHash?: string;     // Hash of server content
    error?: string;
}
 
class SyncStateMachine {
    private states: Map<string, FileState> = new Map();
    
    // Called when file system watcher detects local change
    onLocalChange(path: string, newHash: string): void {
        const state = this.getState(path);
        
        if (state.state === 'synced' || state.state === 'local_change') {
            state.state = 'local_change';
            state.localVersion++;
            state.localHash = newHash;
            this.queueUpload(path);
        } else if (state.state === 'remote_change' || state.state === 'downloading') {
            // Local change while remote change pending → conflict
            state.state = 'conflict';
            this.notifyConflict(path);
        }
    }
    
    // Called when server reports remote change
    onRemoteChange(path: string, newRevision: number, newHash: string): void {
        const state = this.getState(path);
        
        if (state.state === 'synced') {
            state.state = 'remote_change';
            state.remoteVersion = newRevision;
            state.remoteHash = newHash;
            this.queueDownload(path);
        } else if (state.state === 'local_change' || state.state === 'uploading') {
            // Remote change while local change pending → conflict
            state.state = 'conflict';
            this.notifyConflict(path);
        }
    }
    
    // Called when upload completes successfully
    onUploadSuccess(path: string, newRevision: number): void {
        const state = this.getState(path);
        state.state = 'synced';
        state.remoteVersion = newRevision;
        state.remoteHash = state.localHash;
    }
    
    // Called when upload fails
    onUploadError(path: string, error: string): void {
        const state = this.getState(path);
        if (error === 'CONFLICT') {
            state.state = 'conflict';
            this.notifyConflict(path);
        } else {
            // Transient error, retry
            state.state = 'local_change';
            this.scheduleRetry(path);
        }
    }
}

Crash Recovery

Handling Offline Operation

Offline Capability Requirements

•Local State Persistence — The complete file system state (metadata, not content) is cached locally in a database. Users can browse their files even offline.
•Selective File Caching — Users mark files/folders for offline access. These files are pre-downloaded and kept current. Storage limits apply.
•Change Journaling — All local changes are recorded in a persistent journal. This journal survives restarts and is replayed on reconnection.
•Conflict Accumulation — Multiple offline sessions may create multiple conflicting versions. All must be preserved and presented for resolution.
•Graceful Degradation — The UI clearly indicates offline status. Operations that require connectivity (sharing, getting links) are disabled with explanation.

Reconnection Flow:

1. Connectivity Detected
   └─> Check current server cursor
   
2. If server cursor > local cursor:
   └─> Fetch all remote changes since local cursor
   └─> For each remote change:
       ├─> If no local change to same file: apply remote
       └─> If local change exists: mark conflict
   
3. Replay local journal:
   └─> For each local change:
       ├─> If file not conflicted: upload
       └─> If conflicted: create conflict copy, upload
   
4. Resolve conflicts:
   └─> Present conflicts to user
   └─> User chooses: keep local, keep remote, or keep both
   
5. Update cursors, clear journal, back to normal sync

Offline Scenarios and Handling
Scenario	Detection	Resolution
Edit same file on two offline devices	Both have local changes with same parent revision	Create conflict copies, user picks winner
Delete file on one device, edit on another	Remote DELETE vs local MODIFY	Keep both: restore file and apply edits
Rename to same name on two devices	Two files claiming same path	Auto-rename second file (e.g., 'file (1).txt')
Edit file, then delete on same device	Local journal: MODIFY then DELETE	Only send DELETE to server (MODIFY overridden)
Create folder, delete parent folder on other device	Child's parent no longer exists remotely	Recreate parent or move orphans to root

The Extended Offline Problem

Sync Optimizations

Production sync clients employ numerous optimizations to minimize sync time, reduce bandwidth usage, and provide responsive user experience. Here are the key techniques:

Bandwidth Optimizations

•Chunk Deduplication — Before uploading, query server for existing chunks. Skip chunks already present. Typically saves 30-60% bandwidth.
•Compression — Compress chunks before upload (gzip, zstd). Particularly effective for text and documents. Disabled for already-compressed formats (JPEG, MP4).
•Transfer Scheduling — Deprioritize sync during user activity. Sync in background at lower priority. Pause during video calls or metered connections.
•Bandwidth Throttling — User-configurable upload/download limits. Auto-detect metered connections and reduce speed.

Latency Optimizations

•LAN Sync — Detect other devices on same LAN, sync directly without round-trip to cloud. Sub-second sync for local files.
•Streaming Sync — Start syncing immediately on change, don't wait for file to finish writing. Particularly valuable for large files being created.
•Predictive Pre-fetch — Pre-download files user is likely to need (recently accessed, about to present). ML models can predict access patterns.
•Parallel Transfers — Multiple concurrent uploads/downloads (typically 4-8). Saturate available bandwidth.

Resource Optimizations

•Batched Updates — Coalesce rapid changes (e.g., IDE auto-save) into single sync operations. Reduces API calls and server load.
•Prioritized Queue — Sync user's current working folder first. Deprioritize untouched folders. Age-based priority decay.
•Lazy Hashing — Defer hash computation until needed. Use file attributes (size, mtime) for quick-change detection, hash only when uploading.
•Memory-Mapped Chunking — Use mmap for large files to avoid loading entire file into memory during chunking.

The Dropbox LAN Sync Innovation

Summary: File Synchronization Mastery

File synchronization is the invisible backbone of cloud storage systems. Let's consolidate the key concepts covered:

Key Takeaways

•Client-server is the dominant model — Central server provides consistency guarantees and simplifies conflict resolution. P2P optimizations (LAN sync) enhance performance without sacrificing correctness.
•Change detection uses file system events — Platform-specific APIs (inotify, FSEvents) enable near-instant detection with minimal CPU usage. Periodic scanning provides a safety net.
•The sync protocol is cursor-based — Clients track their position in the server's change log. Long polling provides real-time updates without constant polling overhead.
•Delta sync is essential at scale — Content-defined chunking (CDC) with rolling hashes enables efficient incremental sync. Only changed chunks are transferred.
•The client is a sophisticated state machine — Each file progresses through states (synced → local_change → uploading → synced). Crash recovery requires persistent state.
•Offline operation requires change journaling — Local changes are recorded and replayed on reconnection. Extended offline periods may require full resync.

What's Next:

Page Complete

2 / 6