02. File Sync — Low-Level Design¶

~22 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)

The HLD named the two rails. This file opens the four pieces that carry the design's weight — content chunking with block-level dedup, the metadata service and its cursor, the sync and conflict-resolution engine, and the content-addressed blob store — and pins down the schemas, the chunking math on the scenario's numbers, and the concurrency corners where sync actually breaks.

Data models¶

Metadata is partitioned by namespace_id. A namespace is one user's root folder or one shared folder; every file, version, and cursor for that namespace lives on one shard, which is what makes ordering a single-row transaction.

-- One row per namespace: the serialization point for all its commits.
CREATE TABLE namespace (
    namespace_id   BIGINT PRIMARY KEY,
    head_cursor    BIGINT NOT NULL DEFAULT 0,   -- monotonic; every commit advances it
    kind           SMALLINT NOT NULL            -- 0 = user root, 1 = shared folder
);

-- One row per file/dir path currently present in a namespace.
CREATE TABLE file (
    file_id        BIGINT PRIMARY KEY,
    namespace_id   BIGINT NOT NULL,
    path           TEXT   NOT NULL,             -- '/videos/demo.mp4'
    current_version BIGINT NOT NULL,            -- FK -> file_version.version_id
    is_dir         BOOLEAN NOT NULL DEFAULT FALSE,
    UNIQUE (namespace_id, path)                 -- one live file per path
);

-- Append-only version history. Never updated in place -> free versioning + undo.
CREATE TABLE file_version (
    version_id     BIGINT PRIMARY KEY,
    file_id        BIGINT NOT NULL,
    namespace_id   BIGINT NOT NULL,
    blocklist      JSON   NOT NULL,             -- ordered ["<sha256>", ...]
    size_bytes     BIGINT NOT NULL,
    mtime          TIMESTAMP NOT NULL,
    author_device  BIGINT NOT NULL,
    commit_cursor  BIGINT NOT NULL,             -- the head_cursor value at commit
    is_conflict    BOOLEAN NOT NULL DEFAULT FALSE
);
CREATE INDEX idx_ns_cursor ON file_version (namespace_id, commit_cursor);  -- delta pulls

-- Global block index (not sharded by namespace; sharded by hash prefix).
CREATE TABLE block (
    block_hash     CHAR(64) PRIMARY KEY,        -- SHA-256 of the 4 MB block
    size_bytes     INT    NOT NULL,             -- <= 4 MB (last block is short)
    refcount       BIGINT NOT NULL,             -- how many versions point here
    location       TEXT   NOT NULL              -- blob-store placement handle
);

The choices that matter. First, file_version is append-only and carries the ordered blocklist — a file version is its recipe of block hashes, so "what changed between two versions" is a list diff and versioning is free (old versions are simply older rows). Second, commit_cursor and namespace.head_cursor are the ordering primitive — a commit is accepted only if it names the current head, and accepting it advances the head by one; this single monotonic integer is the total order every device replays. Third, the block index is sharded by hash prefix, not by namespace, because a block is shared across users and namespaces — that is the whole point of dedup — so it cannot live on any one namespace's shard. Fourth, refcount lives with the block, because with dedup a block is deletable only when no version anywhere references it, and that count is the delete path's whole safety story.

Component internals¶

Component 1 — The chunker (content chunking + block-level dedup)¶

Responsibility: turn a file into an ordered list of block hashes, and turn a changed file into the minimal set of new blocks to upload.

The baseline is fixed-size 4 MB blocks, the Dropbox choice. Walk the file, cut a boundary every 4 MB, hash each block with SHA-256, and the file's recipe is that ordered hash list. Diffing a new version against the old is a positional comparison of two hash lists.

BLOCK = 4 * 1024 * 1024   # 4 MB

def chunk_fixed(path) -> list[str]:
    hashes = []
    with open(path, "rb") as f:
        while (buf := f.read(BLOCK)):
            hashes.append(sha256(buf).hexdigest())
    return hashes

def blocks_to_upload(new_list, old_list, store) -> list[str]:
    candidates = set(new_list) - set(old_list)      # hashes not in the prior version
    return store.probe(list(candidates))            # of those, which the store lacks

Fixed blocks are cheap to compute and give clean positional diffs for in-place edits that don't change length — which is exactly the scenario. They have one known weakness: an insertion that shifts all following bytes changes every subsequent block boundary, so a naive fixed-block scheme would re-upload the whole tail of the file. The alternative is content-defined chunking (CDC): slide a rolling hash (Rabin fingerprint) over the bytes and cut a boundary wherever the low bits of the rolling hash hit a target pattern, so boundaries are anchored to content, not offset. An insertion then only disturbs the one or two chunks around it. The tradeoff is concrete: CDC costs meaningfully more CPU per byte and yields variable-size blocks, in exchange for far better dedup on files that get insertions rather than in-place edits. The pragmatic call is fixed 4 MB blocks as the default (simpler, faster, and enough for the common edit-in-place and cross-file-dedup cases) with CDC reserved for workloads dominated by inserts.

Component 2 — The metadata service (commit + cursor)¶

Responsibility: serialize commits into a per-namespace total order, using optimistic concurrency on the cursor, and detect conflicts.

class MetadataService:
    def commit(namespace_id, path, blocklist, parent_cursor, device_id) -> CommitResult
    def get_delta(namespace_id, since_cursor) -> (changes, new_cursor)

commit is one transaction against the namespace's shard. It reads head_cursor, compares it to the caller's parent_cursor, and only if they match does it write the new file_version, repoint file.current_version, and advance head_cursor. The compare-and-advance is the optimistic-concurrency guard; because it is a single-row conditional update inside one shard, it needs no distributed lock.

def commit(ns, path, blocklist, parent_cursor, device_id):
    with txn(shard_for(ns)):
        head = SELECT head_cursor FROM namespace WHERE namespace_id = ns FOR UPDATE
        if head != parent_cursor:
            return Conflict(current_cursor=head)          # someone else committed first
        new_cursor = head + 1
        vid = insert_file_version(ns, path, blocklist, new_cursor, device_id)
        upsert_file(ns, path, current_version=vid)
        UPDATE namespace SET head_cursor = new_cursor WHERE namespace_id = ns
        return Committed(new_cursor, vid)

get_delta is the read side: given a device's last-synced cursor, return every file_version in the namespace with commit_cursor > since_cursor, ordered, plus the new head. The idx_ns_cursor index makes this a range scan, so a device that was offline for a week pulls its backlog in one ordered pass.

Component 3 — The conflict resolver¶

Responsibility: when a commit's parent is stale, produce a deterministic outcome that loses no data.

When commit returns a conflict, the client does not overwrite and does not blindly retry with the new head. It re-pulls the delta to learn the winning version, then re-commits its own version under a new path as a conflicted copy, so both survive:

def resolve_conflict(ns, path, my_blocklist, device_id, server_head):
    winner = get_delta(ns, since=my_parent).latest_for(path)   # the version that won
    # Preserve my work beside the winner instead of discarding it.
    copy_path = conflicted_name(path, device_id)  # 'demo (Device-B's conflicted copy).mp4'
    commit(ns, copy_path, my_blocklist, parent_cursor=server_head, device_id=device_id,
           is_conflict=True)

Determinism comes from two facts. The namespace's single serialization point gives every device the same winner (whoever the shard ordered first), and the conflicted-copy name is a pure function of the losing device_id, so every device independently derives the identical two-file result. There is no vote and no clock comparison to disagree on.

Component 4 — The blob store (content-addressed, refcounted)¶

Responsibility: store immutable 4 MB blocks under their content hash, dedup on write, and reclaim blocks only when safely unreferenced.

A PUT /blocks/{hash} verifies the uploaded bytes actually hash to the claimed key (rejecting a lying or corrupt client) and, if the key is absent, writes it; if present, it is a no-op — the dedup happens here, silently. refcount is incremented when a file_version referencing the block commits and decremented when a version is finally purged past its retention window. Garbage collection is a background mark-and-sweep: a block with refcount = 0 is not deleted immediately but tombstoned with a grace period, because a commit in flight may be about to reference it — deleting on the instant the count hits zero is the classic dedup GC race that loses a block out from under a concurrent upload.

Core algorithm — the scenario, stepped through¶

Walk the 1 GB video and its concurrent one-line edit end to end with the real numbers.

Step 1 — first upload (chunking + dedup on cold content). The client chunks the 1 GB video: 1,024 MB / 4 MB = 256 blocks, hashed to 256 SHA-256 keys. probe reports all 256 missing (cold content), so all 256 upload — 1,024 MB across the wire. The client commits file_version v1 with the 256-hash blocklist against parent_cursor = N, and the namespace head advances to N+1 = call it N₁. Cost recorded: 256 blocks stored, refcount 1 each.

Step 2 — the edit is made on two devices at once. Device A and Device B both hold v1 and cursor N₁. Each makes the same one-line edit. Fixed-block chunking re-hashes the file; because the edit lands inside block 40 (say) and does not change the file's length, blocks 0–39 and 41–255 hash identically to v1, and only block 40 gets a new hash. Each device's probe therefore reports exactly one block missing, and each uploads 4 MB — the 256:1 saving the whole design exists to deliver. Note the two devices produce the same new block-40 hash if their edits are byte-identical (dedup means only one 4 MB block is stored even though two devices uploaded it), or two different hashes if the edits differ; either way the block rail just stores what it is given.

Step 3 — the concurrent commit collides. Both devices now commit a new version of /videos/demo.mp4 with the new blocklist and parent_cursor = N₁. Say Device A's commit reaches the shard first: head == N₁ matches, so A wins — v2 is written, file.current_version points at it, and the head advances to N₂. Device B's commit arrives microseconds later with parent_cursor = N₁, but the head is now N₂, so the guard fails and B gets 409 Conflict.

Step 4 — deterministic resolution, no loss. Device B re-pulls the delta, sees A's v2 as the winner for /videos/demo.mp4, and re-commits its own version at /videos/demo (Device-B's conflicted copy).mp4 against the current head N₂, advancing it to N₃. Now the namespace holds two files: A's edit under the original name and B's edit preserved beside it. Every other device pulls deltas N₁→N₃ in order and reconstructs the identical two-file state — A's block-40 fetched once, B's block-40 fetched once, everything else already local. The collision cost the system one extra 4 MB block and one extra metadata row; it cost the users zero lost work.

Sequence diagram — concurrent edit and deterministic resolution¶

Device A        Device B        MetadataSvc (ns shard)      BlockSvc/Blob
  │ edit blk40     │ edit blk40         │                        │
  ├─ probe ────────┼────────────────────┼───────────────────────▶│  (both: 1 missing)
  ├─ PUT blk40 ────┼────────────────────┼───────────────────────▶│  (4 MB)
  │                ├─ PUT blk40 ────────┼───────────────────────▶│  (4 MB / dedup)
  ├─ commit(parent=N1) ─────────────────▶│  head==N1 ✓ -> head=N2 │
  │◀── 200 committed, cursor N2 ─────────┤                        │
  │                ├─ commit(parent=N1) ─▶│  head==N2 ✗ (409)      │
  │                │◀── 409 conflict, head=N2 ──┤                  │
  │                ├─ get_delta(since=N1) ▶│  returns A's v2        │
  │                │◀── winner = v2 ───────┤                        │
  │                ├─ commit(copy_path, parent=N2) ─▶│ head=N3      │
  │                │◀── 200 committed, cursor N3 ─────┤             │
  │  ... all devices pull delta N1->N3: converge on 2 files ...    │

One serialization point orders the two commits; the loser is preserved as a conflicted copy rather than discarded, and every device derives the same result from the same ordered log.

Concurrency and edge cases¶

Idempotent block upload. Content addressing makes PUT /blocks/{hash} naturally idempotent — a retry after a timeout re-writes identical bytes under the same key, a no-op. There is never a "duplicate block" to reconcile.
Idempotent commit. A commit that times out on the network may have actually landed. The client retries with the same parent_cursor; if the first attempt succeeded, the head already advanced, so the retry gets a 409 and the client reconciles via delta rather than committing twice. Optionally the client attaches a commit UUID the service dedups, collapsing the retry cleanly.
Orphaned blocks. Blocks uploaded before a commit that never happens (client crash between PUT and commit) are referenced by nothing, so their refcount stays 0 and the GC sweep reclaims them after the grace period — never on the hot path.
GC-versus-commit race. A block's refcount can hit 0 just as a new commit is about to reference it (the same content re-appearing). Deleting immediately would corrupt that commit, so a zero-refcount block is tombstoned with a grace window and only physically deleted if it stays unreferenced through it; a commit that references it during the window simply resurrects it.
Hash collision. SHA-256 collision is astronomically unlikely, but a paranoid store can verify bytes on a hash match before treating two blocks as identical; the design assumes "same hash ⇒ same content," and the verify-on-match option is the escape hatch if that assumption is ever doubted.
Move / rename is metadata-only. Renaming /a.mp4 to /b.mp4 changes the file's path and writes a new version, but the blocklist is unchanged, so zero blocks transfer — a 1 GB file moves for the cost of one metadata row, which whole-file systems get wrong by re-uploading.
Offline reconciliation. A device offline for a week replays its queued local commits in order; each is an optimistic commit against the head it will discover on reconnect, so any that collide with intervening remote edits fall into the same conflicted-copy path — the offline case is not special, it is just the concurrent case stretched over time.
Atomic local apply. Reconstructed files are written to a temp path and atomically renamed into place, so a crash mid-write never surfaces a half-downloaded file to the user or to the folder watcher.