Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

System Design HLD-19.12

Design Google Drive / Dropbox

Design file sync: content-defined chunks and dedupe, block storage, a metadata journal with cursors, change notifications and conflict copies.

Advanced 22 min Last reviewed

The problem

You save a file on your laptop and, a few seconds later, it appears on your phone. You edit a 200 MB presentation, change one slide, and the sync finishes almost instantly. You edit the same document on a plane and on your desktop, and when the laptop lands neither version is lost. A file sync service makes many devices behave like one folder.

The hard parts are not storing files; object storage does that. They are moving as few bytes as possible (only what changed, never what the server already has), telling every device what changed without them asking constantly, and handling concurrent edits honestly when two devices change the same file while apart.

Requirements

Functional

  • Upload, download, rename, move and delete files and folders; sync them across a user's devices.
  • Keep version history; restore old versions.
  • Share folders with other users.
  • Work offline and sync on reconnect, never silently losing an edit.

Non-functional

  • Scale: 50 million users storing 5 GB each on average; 10 million daily active users with 2 devices each.
  • Durability: files must never be lost or corrupted (a replicated object store holds the bytes).
  • Sync latency: changes appear on other online devices within seconds.
  • Efficiency: small edits to big files transfer little data.

Out of scope

  • Real-time co-editing inside documents (a later case study), full-text search of contents, and previews.

Estimates

  • Storage: 50M x 5 GB = 250 PB of logical data. Deduplication (identical chunks stored once) and compression bring the physical size down, and the object store's replication or erasure coding brings it back up.
  • Changes: if each daily user changes 10 files a day, that is 100 million commits a day, about 1,160 per second on average, more at peaks. Each commit is a small metadata write; the bytes go to block storage separately.
  • Connections: 10M users x 2 devices = 20 million devices online during the day, each holding a long-poll or WebSocket connection to learn about changes ( Real-time: polling, long polling, SSE and WebSockets ).
  • Metadata: at 2,000 files per user, 100 billion file rows of a few hundred bytes each, so tens of TB. It must be partitioned, and the natural key is the namespace (a user's root folder or a shared folder), because a sync always reads one namespace ( Partitioning and sharding ).

API

POST /v1/blocks/check        { hashes: [...] }         -> { missing: [...] }
PUT  /v1/blocks/{hash}       <bytes>                    # verified against the hash
POST /v1/files/commit        { namespace, path, parent_version, blocks: [...] }
                              -> 200 { version }  or  409 { conflict, latest_version }
GET  /v1/changes?namespace=..&cursor=..  -> { entries: [...], cursor, has_more }
GET  /v1/changes/wait?cursor=..          # long poll: returns when something changed
GET  /v1/blocks/{hash}       -> <bytes>

A file is uploaded as a list of block hashes. The client asks which blocks the server lacks, uploads only those, then commits the new version with the version it started from.

Data model

  • Blocks (object storage, Object storage, block storage and file systems ): hash -> bytes, immutable, content-addressed. A block's id is the SHA-256 of its content, so the same bytes always get the same id, and the server can verify every upload.
  • Block index (database): hash -> location, size, refcount for dedupe and garbage collection.
  • File versions (database, partitioned by namespace): namespace, file_id, version, path, size, block_list, parent_version, device, modified_at.
  • Journal (database, partitioned by namespace): an append-only list namespace, seq -> file_id, version. A device's cursor is the last seq it has seen; syncing means reading the journal after the cursor.

High-level design

File sync: upload, commit and notify paths Upload path: the desktop client watches files, splits a changed file into chunks, asks the block service which hashes are missing and uploads only those to block storage. Commit path: the client commits the new block list to the metadata service with its parent version; the metadata service checks the version, writes the file version and appends to the namespace journal. Notify path: the notification service wakes the user's other devices, which read journal entries after their cursor from the metadata service and download the blocks they lack. missing? new blocks commit version + journal changed wake up changes after 811 missing blocks Laptop client watch, chunk, hash Block service check + upload Block storage hash -> bytes Metadata service versions, journal Metadata DB by namespace Notification service long polls Phone client cursor 811 Figure 1. Bytes and metadata take separate roads. Blocks go to content-addressed storage; a small commit records which blocks make up the new version and appends it to the journal that other devices follow.
  1. Upload path The client notices a changed file, splits it into chunks and hashes each one. It asks the block service which hashes are missing and uploads only those. Blocks are verified against their hash and stored once.
  2. Commit path The client commits the file's new block list with the version it was based on. If that is still the latest version, the metadata service writes the new version and appends an entry to the namespace's journal, then tells the notification service.
  3. Notify path Other devices hold a long poll. When the namespace changes, the phone wakes, reads journal entries after its cursor, and downloads only the blocks it does not have locally.

Deep dives

Deep dive 1: Chunking and deduplication

Splitting files into chunks gives three wins: only changed chunks are uploaded, identical chunks are stored once (across versions, files and possibly users), and a failed upload resumes at the last chunk.

How you split matters. With fixed-size chunks, inserting a few bytes near the start of a file shifts every later byte, so every chunk boundary moves and every chunk looks new. Content-defined chunking cuts where a rolling hash of the last few bytes matches a pattern, so boundaries move with the content:

chunks.pyruns with python3 (standard library)
# Why sync clients use content-defined chunks: insert 12 bytes near the
# start of a 256 KB file and count how many chunks must be uploaded again.
import hashlib, random

rnd = random.Random(7)
old = bytes(rnd.getrandbits(8) for _ in range(256 * 1024))
new = old[:1000] + b"hello, world" + old[1000:]
GEAR = [random.Random(i).getrandbits(32) for i in range(256)]

def fixed_chunks(data, size=8192):
    return [data[i:i + size] for i in range(0, len(data), size)]

def cdc_chunks(data, mask=(1 << 13) - 1, lo=2048, hi=32768):
    # cut where a hash of the last 32 bytes ends in 13 zero bits
    chunks, start, h = [], 0, 0
    for i, b in enumerate(data):
        h = ((h << 1) + GEAR[b]) & 0xFFFFFFFF
        n = i - start + 1
        if (n >= lo and (h & mask) == 0) or n >= hi:
            chunks.append(data[start:i + 1])
            start, h = i + 1, 0
    if start < len(data):
        chunks.append(data[start:])
    return chunks

def ids(chunks):
    return [hashlib.sha256(c).hexdigest()[:12] for c in chunks]

METHODS = (("fixed 8 KB", fixed_chunks), ("content-defined", cdc_chunks))
for name, split in METHODS:
    before, after = set(ids(split(old))), ids(split(new))
    changed = [c for c in after if c not in before]
    avg = len(new) / len(after) / 1024
    print(f"{name:16} {len(after):3} chunks (avg {avg:4.1f} KB), "
          f"{len(changed):2} new to upload")

Output

fixed 8 KB        33 chunks (avg  7.8 KB), 33 new to upload
content-defined   22 chunks (avg 11.6 KB),  1 new to upload

Twelve bytes inserted at offset 1,000 made all 33 fixed chunks new, so the whole 256 KB file would be uploaded again. With content-defined chunks only the one chunk containing the edit changed; the cut points after it found the same content and fell in the same places. Real systems use larger chunks than this demo (a few MB), because every chunk costs a row of metadata and a request, and the trade-off is metadata size against how much a small edit re-uploads. Compressed formats such as video often change throughout, so chunking helps them less.

Deep dive 2: The sync protocol

Each namespace has a journal: an ordered list of changes. A device remembers its cursor, the last journal entry it applied, so syncing is "give me everything after 811". Here is a full round trip as the laptop edits a file and the phone picks it up:

Sync round trip: laptop edits, phone follows The laptop asks which of its nine block hashes are missing, uploads the one missing block, and commits the new block list with parent version 3, getting version 4. The metadata service appends journal entry 812 and tells the notification service, which completes the phone's long poll. The phone lists changes after cursor 811, receives version 4's block list and downloads the one block it lacks. Laptop Block store Metadata versions + journal Notify Phone which of h1..h9 are missing? missing: h7 PUT h7 commit(parent=v3, h1..h9) ok: v4, journal seq 812 namespace changed long poll returns changes after 811? file v4: h1..h9, cursor 812 GET h7 Figure 2. Only one block crosses the network in each direction, and the phone learns about the change from a long poll instead of asking every few seconds.
  1. which of h1..h9 are missing? After an edit, the laptop rechunks the file and sends its nine block hashes.
  2. missing: h7 Eight blocks are already stored, from the previous version. Only h7 is new.
  3. PUT h7 The laptop uploads the single new block. The store checks that its SHA-256 matches h7.
  4. commit(parent=v3, h1..h9) The laptop commits the new block list, saying it was based on version 3.
  5. ok: v4, journal seq 812 Version 3 is still the latest, so the commit succeeds as version 4 and is appended to the journal.
  6. namespace changed The metadata service tells the notification service that this namespace has new entries.
  7. long poll returns The phone's waiting request completes: something changed.
  8. changes after 811? The phone reads the journal after its cursor.
  9. file v4: h1..h9, cursor 812 It gets the new block list and advances its cursor to 812.
  10. GET h7 It already has h1..h6 and h8..h9 locally, so it downloads only h7 and rebuilds the file.

The journal makes sync robust: a phone that was off for a week just reads more entries, and a lost notification only delays sync until the next poll, because the cursor, not the notification, is the source of truth.

Deep dive 3: Conflicts

The commit carries parent_version, which is optimistic concurrency control: nothing is locked while you edit, and a write succeeds only if nobody else wrote in between. If the laptop and the phone both edit version 3 offline, the first to reconnect commits version 4. The second commit says "parent 3" while the latest is 4, so the server answers 409.

The service cannot know how to merge two edits of an arbitrary file (a spreadsheet, a photo), so it does not try. The losing client saves its version as a conflicted copy next to the original, named with the device and date, and both versions are kept. It is a little ugly, but nothing is silently lost, which is the one property a sync service must never give up. Edits to different files never conflict, because versions are tracked per file.

Deletes and renames are journal entries too, and deleted files are kept as versions for a retention period so they can be restored.

Deep dive 4: Storage and garbage collection

Blocks are immutable and shared, so deleting a file cannot delete its blocks directly: another version or another file may use them. The block index keeps a reference count, or a periodic mark-and-sweep job finds blocks no live version references and removes them after a grace period. Popular shared files and recently used blocks can be cached, while old versions can move to colder, cheaper storage tiers.

Try it

What does the sync client have to send for each change?

Show answers
  • Copy a 2 GB video you already synced into another folder: Metadata only. Every block hash is already stored, so the commit just lists existing blocks.
  • Change one paragraph in a 50 MB document: Some new blocks. Content-defined chunks keep most boundaries; only the chunks around the edit are new.
  • Rename a folder of 300 photos: Metadata only. Paths are metadata; no block content changes.
  • Laptop and phone both edit notes.txt offline; the phone syncs first: Conflicted copy. The laptop's commit names parent version 3, but the latest is now 4, so its version is kept as a conflicted copy.
  • Laptop and phone each edit a different file in the same folder offline: Some new blocks. Versions are tracked per file, so both commits succeed and each uploads its own new blocks.
  • Append 1 MB to the end of a log file: Some new blocks. The earlier chunks are unchanged; only the last chunk and the appended data are new.

Try this:

  1. Sort all six, then Check.
  2. Run the chunking sample in your head with 4 MB fixed chunks and a 1-byte insert at the start of a 1 GB file. How much is uploaded?
  3. Why is it safe for a client to miss a notification?

Bottlenecks and failure modes

FailureImpactMitigation
Huge namespace (a company-wide shared folder)One partition hot, long journalsSplit large namespaces; paginate change lists
Notification lost or device asleepDevice does not syncCursor-based journal; next poll catches up
Upload interruptedPartial fileBlocks uploaded first, commit last; resume missing blocks
Corrupted blockWrong file contentsVerify SHA-256 on upload and download
Concurrent offline editsLost workParent version check; conflicted copies
Deleted blocks still referencedData lossReference counts or mark-and-sweep with a grace period

Trade-offs we made

OptionWins whenLoses when
Content-defined chunks (chosen) Inserts and small edits upload a few chunks More CPU on the client; variable chunk sizes
Fixed-size chunks Simple and fast to compute One insert near the start re-uploads the whole file
Conflicted copies (chosen) Never loses an edit; works for any file type Users must merge by hand
Last writer wins No extra files Silently discards one device's edits
Cross-user deduplication Less storage for common files Reveals whether a file exists elsewhere; harder with per-user encryption

Extensions

  • Shared folders and permissions: a shared namespace mounted into several users' trees.
  • LAN sync: devices on the same network fetch blocks from each other instead of the cloud.
  • Selective sync and on-demand files that download only when opened.
  • Delta compression within changed chunks for further savings.

In the wild

Where you will see this: consumer and business file sync services, photo backup apps, and version control systems, which also store content-addressed blobs and history. Backup tools use content-defined chunking for the same reason this design does: unchanged data is never sent twice.

Check yourself

  1. Why are blocks identified by the hash of their content?

    Show answer

    B. Identical content gets the same id, enabling dedupe and integrity checks Content addressing lets the server say which blocks it already has and verify every upload.

  2. A few bytes are inserted near the start of a large file. Why do content-defined chunks re-upload less than fixed chunks?

    Show answer

    B. Their boundaries depend on content, so they move with it instead of shifting Fixed boundaries shift and every chunk changes; content-defined boundaries reappear in the same content.

  3. The phone missed a notification while offline. What happens when it reconnects?

    Show answer

    B. It reads the journal after its cursor and catches up The cursor and journal are the source of truth; notifications only say 'look now'.

  4. Two devices commit edits to the same file, both with parent version 3. What does the server do?

    Show answer

    B. Accepts the first as version 4 and rejects the second, which becomes a conflicted copy Optimistic concurrency detects the conflict; keeping a copy guarantees no edit is lost.

Recap

  • Split files into content-defined chunks named by their hash; upload only blocks the server lacks.
  • Bytes go to immutable block storage; a small commit records each version's block list.
  • Each namespace has a journal; devices sync by reading entries after their cursor, woken by long polls.
  • Commits carry the parent version; concurrent edits produce a conflicted copy, never a silent overwrite.
  • Shared blocks need reference counting or mark-and-sweep before deletion.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up