In a deduplicating cloud-drive store, how can garbage-collecting a chunk whose reference count reached zero corrupt a file being uploaded at the same time?

seniorshould knowfreq 42%

answer

time of check, time of use
'have it' answered too early
wait before deleting zero counts
lock and re-check at commit

basics

~20 s

An upload can skip a chunk the server says it already holds while the collector deletes that zero-reference chunk; the committed manifest then points at missing bytes. A deletion grace period plus a locked check at commit closes the gap.

solid answer

~50 s

Dedup shares chunks, so deleting a file only decrements each chunk's reference count; at zero the chunk becomes garbage. The race: a client asks which hashes are missing, the server answers 'have it' for chunk X, whose count is zero but which has not been swept yet, and the client skips uploading X. The collector then deletes X, and the client commits a manifest referencing X — a file whose bytes are gone, discovered only on read. Fixes: first, record when a count hit zero and delete only after a grace period longer than the longest has-check-to-commit gap; second, at commit, lock each referenced chunk record, reject the commit if any is missing or tombstoned, and increment the counts in the same transaction, so the client re-uploads; third, have the sweeper re-check the count under the same lock before tombstoning. A periodic mark-and-sweep pass then catches count drift from crashes.

Dedup shares chunks, so deleting a file only decrements each chunk's reference count; at zero the chunk becomes garbage. The race: a client asks which hashes are missing, the server answers 'have it' for chunk X, whose count is zero but which has not been swept yet, and the client skips uploading X. The collector then deletes X, and the client commits a manifest referencing X — a file whose bytes are gone, discovered only on read. Fixes: first, record when a count hit zero and delete only after a **grace period** longer than the longest has-check-to-commit gap; second, at commit, lock each referenced chunk record, reject the commit if any is missing or tombstoned, and increment the counts in the same transaction, so the client re-uploads; third, have the sweeper re-check the count under the same lock before tombstoning. A periodic mark-and-sweep pass then catches count drift from crashes.

code

pseudocode · 8 lines

pseudocode

for chunk in chunks where refcount == 0 and zero_since < now - GRACE:
    begin transaction
    row = lock chunk record chunk.hash
    if row.refcount == 0 and row.zero_since < now - GRACE:
        row.tombstoned = true
    commit
for row in tombstoned chunks:
    delete stored copy row.copy_id from the object store

go deeper

for a junior

Remember that shared chunks cannot be deleted with the file; each chunk counts its references and is removed only when nothing uses it anymore.

for a middle

Explain how counts change on manifest commit and delete, and lay out the step-by-step timeline in which a has-check answer goes stale before the commit.

for a senior

Show the fixes and how they interact: grace period, tombstoning under a lock, commit-time verification, per-copy deletion, and reconciliation that treats undercounts as incidents.

for a principal

Weigh reclaim speed against safety: a longer grace period and full reconciliation cost storage and scan time, while aggressive collection risks silent data loss that surfaces much later.

Why dedup forces reference counting

In a deduplicating cloud-drive store, a chunk — a byte range stored under the SHA-256 of its content — can be referenced by many manifests, the ordered chunk lists that describe file versions: older versions of the same file, copies, and possibly other users' files. Deleting a file version therefore cannot delete its chunks directly. Instead, the store keeps a reference count per chunk, incremented when a committed manifest starts referencing it and decremented when a manifest is deleted. A chunk whose count reaches zero is garbage, and a garbage collector (the sweeper) eventually removes its bytes.

That sounds simple, but the sweeper runs concurrently with uploads, and dedup opens a window in which a chunk is both garbage and about to be reused.

The dedup-versus-delete race

Delta sync uploads only missing chunks, which requires a has-check first. A timeline that corrupts a file:

A user deletes an old file version; chunk X's count drops to zero.
Another device in the same dedup scope starts syncing a file that contains X. Its client asks which hashes are missing; the server sees X is still stored and answers 'have it'.
The sweeper deletes X's bytes.
The client uploads its other missing chunks and commits a manifest that references X.
Nothing fails yet. The damage appears when someone opens the file and X cannot be fetched.

The has-check answer was true when given and false when relied on — a time-of-check to time-of-use gap. The failure is silent at write time and may surface weeks later.

Closing the gap

Grace period: when a count reaches zero, record the time in zero_since instead of deleting. The sweeper only considers chunks that have sat at zero longer than a grace period chosen to exceed the longest plausible gap between a has-check and a manifest commit. This makes the race rare and doubles as a short undo window for accidental deletes.
Tombstone, then delete: the sweeper marks a chunk as tombstoned under a row lock, re-checking the count at that moment, and removes the bytes only afterwards.
Commit-time verification: the commit locks each referenced chunk record, rejects the commit if any is missing or tombstoned, and otherwise increments the counts and clears zero_since in the same transaction. The client re-uploads the rejected chunks. This turns 'rare' into 'impossible', which matters because upload sessions can resume long after the has-check.
Honest has-checks: report tombstoned chunks as missing, so clients re-upload them up front instead of failing at commit.
Per-copy deletion: if a tombstoned hash is uploaded again, the pending deletion of the old bytes must not erase the new copy, so deletions should target a specific stored copy or generation, not just the hash.

pseudocode

commit_manifest(hashes):
  begin transaction
  for h in distinct(hashes):
    row = lock chunk record h
    if row is missing or row.tombstoned:
      abort and tell the client to re-upload h
    row.refcount += 1
    row.zero_since = null
  insert manifest
  commit

Because the sweeper takes the same row lock and re-checks refcount == 0 before tombstoning, the two operations serialize: either the commit wins and the sweeper sees a live count, or the sweeper wins and the commit is rejected.

Keeping counts honest

Reference counts drift. A crash between writing a manifest and incrementing counts, a decrement applied twice by a retry, or a bug in a rarely used path all leave a count wrong. The two directions have very different consequences:

Drift	Effect	Severity
Count too high	chunk is never collected	wasted storage, a leak
Count too low	chunk is collected while still referenced	data loss

Defences:

Update counts in the same transaction as the manifest insert or delete, and make each update idempotent, for example by recording which manifest applied which increment.
Run a periodic mark-and-sweep reconciliation: walk every live manifest, compute the true counts, and compare. Repair leaks routinely; treat any undercount as an incident to investigate.
Where affordable, confirm a chunk appears in no live manifest before its bytes are removed.

Reference counting versus mark-and-sweep

Approach	Strength	Weakness
Reference counting	incremental, frees space promptly	drifts; touched on every write
Mark-and-sweep	recomputes the truth from manifests	scans every manifest; slow at scale

Many large stores use counting for day-to-day collection and mark-and-sweep as the periodic auditor.

What to watch in production

Commits rejected for tombstoned chunks: a small steady rate is expected; a spike suggests the grace period is too short.
Reconciliation differences, split into over- and undercounts.
Storage held by zero-count chunks inside the grace period — the price of safety.

## Why dedup forces reference counting In a deduplicating cloud-drive store, a **chunk** — a byte range stored under the SHA-256 of its content — can be referenced by many **manifests**, the ordered chunk lists that describe file versions: older versions of the same file, copies, and possibly other users' files. Deleting a file version therefore cannot delete its chunks directly. Instead, the store keeps a **reference count** per chunk, incremented when a committed manifest starts referencing it and decremented when a manifest is deleted. A chunk whose count reaches zero is **garbage**, and a **garbage collector** (the sweeper) eventually removes its bytes. That sounds simple, but the sweeper runs concurrently with uploads, and dedup opens a window in which a chunk is both garbage and about to be reused. ## The dedup-versus-delete race Delta sync uploads only missing chunks, which requires a has-check first. A timeline that corrupts a file: 1. A user deletes an old file version; chunk X's count drops to zero. 2. Another device in the same dedup scope starts syncing a file that contains X. Its client asks which hashes are missing; the server sees X is still stored and answers 'have it'. 3. The sweeper deletes X's bytes. 4. The client uploads its other missing chunks and commits a manifest that references X. 5. Nothing fails yet. The damage appears when someone opens the file and X cannot be fetched. The has-check answer was true when given and false when relied on — a **time-of-check to time-of-use** gap. The failure is silent at write time and may surface weeks later. ## Closing the gap - **Grace period**: when a count reaches zero, record the time in `zero_since` instead of deleting. The sweeper only considers chunks that have sat at zero longer than a grace period chosen to exceed the longest plausible gap between a has-check and a manifest commit. This makes the race rare and doubles as a short undo window for accidental deletes. - **Tombstone, then delete**: the sweeper marks a chunk as tombstoned under a row lock, re-checking the count at that moment, and removes the bytes only afterwards. - **Commit-time verification**: the commit locks each referenced chunk record, rejects the commit if any is missing or tombstoned, and otherwise increments the counts and clears `zero_since` in the same transaction. The client re-uploads the rejected chunks. This turns 'rare' into 'impossible', which matters because upload sessions can resume long after the has-check. - **Honest has-checks**: report tombstoned chunks as missing, so clients re-upload them up front instead of failing at commit. - **Per-copy deletion**: if a tombstoned hash is uploaded again, the pending deletion of the old bytes must not erase the new copy, so deletions should target a specific stored copy or generation, not just the hash. ```pseudocode commit_manifest(hashes): begin transaction for h in distinct(hashes): row = lock chunk record h if row is missing or row.tombstoned: abort and tell the client to re-upload h row.refcount += 1 row.zero_since = null insert manifest commit ``` Because the sweeper takes the same row lock and re-checks `refcount == 0` before tombstoning, the two operations serialize: either the commit wins and the sweeper sees a live count, or the sweeper wins and the commit is rejected. ## Keeping counts honest Reference counts drift. A crash between writing a manifest and incrementing counts, a decrement applied twice by a retry, or a bug in a rarely used path all leave a count wrong. The two directions have very different consequences: | Drift | Effect | Severity | |---|---|---| | Count too high | chunk is never collected | wasted storage, a leak | | Count too low | chunk is collected while still referenced | **data loss** | Defences: - Update counts in the **same transaction** as the manifest insert or delete, and make each update idempotent, for example by recording which manifest applied which increment. - Run a periodic **mark-and-sweep reconciliation**: walk every live manifest, compute the true counts, and compare. Repair leaks routinely; treat any undercount as an incident to investigate. - Where affordable, confirm a chunk appears in no live manifest before its bytes are removed. ## Reference counting versus mark-and-sweep | Approach | Strength | Weakness | |---|---|---| | Reference counting | incremental, frees space promptly | drifts; touched on every write | | Mark-and-sweep | recomputes the truth from manifests | scans every manifest; slow at scale | Many large stores use counting for day-to-day collection and mark-and-sweep as the periodic auditor. ## What to watch in production - Commits rejected for tombstoned chunks: a small steady rate is expected; a spike suggests the grace period is too short. - Reconciliation differences, split into over- and undercounts. - Storage held by zero-count chunks inside the grace period — the price of safety.

Why do reference counts drift, and which direction of drift is dangerous?
Crashes between a manifest write and its count update, retried decrements applied twice, and bugs in rare paths all skew counts. An overcount only leaks storage, because the chunk is never collected. An undercount is dangerous: the chunk reaches zero while still referenced and gets deleted. Keep updates transactional and idempotent, and run periodic mark-and-sweep reconciliation, treating any undercount as an incident.
How long should the deletion grace period be?
Longer than the maximum time a client may hold a has-check answer before committing, including resumed upload sessions, plus a margin for clock skew. It often doubles as a recovery window for accidental deletes. The cost is storage held for garbage during that window, and it only makes the race rare; a locked check at commit is what makes it impossible.

saying these in an interview costs you the question

Deleting a file should delete its chunks right away.
An inflated reference count is as dangerous as an undercounted one.
A 'have it' answer guarantees the chunk still exists at commit.
With a grace period, commit-time checks are unnecessary.
Correct code means reference counts never need reconciliation.

In a deduplicating cloud-drive store, how can garbage-collecting a chunk whose reference count reached zero corrupt a file being uploaded at the same time?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why dedup forces reference counting

The dedup-versus-delete race

Closing the gap

Keeping counts honest

Reference counting versus mark-and-sweep

What to watch in production

▾common follow-ups2 questions

▾red flags5 flags

Why dedup forces reference counting

The dedup-versus-delete race

Closing the gap

Keeping counts honest

Reference counting versus mark-and-sweep

What to watch in production

answer

go deeper