Write down the failing timeline
At 10:00, the collector takes a snapshot of the file catalog and begins its mark phase. At that instant no committed manifest references X, so X is marked unreachable. At 10:01, an upload worker notices that X already exists in the deduplicated chunk store and publishes a new file manifest referring to X. At 10:02, the collector uses its earlier mark result and physically deletes X. The new manifest remains committed, but restoring its contents fails.
This isn't a checksum problem. X was valid when uploaded, and its hash may still be correct in the manifest. It's a concurrency problem between adding a reference and reclaiming the referenced object. Strong consistency of individual chunk GETs also doesn't help because the collector made a decision using an earlier consistent view.
If a worker decrements X's count to zero, queues deletion, and another worker increments it after the deletion is already committed, the count can say one while the bytes are gone. A correct counter protocol needs atomic reference publication, explicit pending states or some other agreed barrier.
Define the invariant before picking a garbage collector
I want a simple safety property: a chunk referenced by any committed, retained manifest must not be physically deleted. A newly uploading session may reserve chunks before publication. A snapshot that is no longer visible to new readers may still be pinned by an existing restore operation.
One approach uses generations or epochs. A collector starts at generation G and marks reachable chunks from an authoritative metadata snapshot. All new manifest commits after G either write into a protected newer generation or record new references in a way the collector cannot miss. Sweep only chunks proven unreachable relative to both the snapshot and the allowed concurrent writes. This resembles the write barrier in a concurrent garbage collector for process memory, adapted to a distributed metadata store.
A second approach uses staged deletion. Instead of removing bytes immediately when the mark pass finds a candidate, transition the chunk from live to candidate, record the candidate's generation, and wait a safe interval. Before physical deletion, re-evaluate reachability through an authoritative metadata source under a suitable fence. If a publisher can still attach a reference after the last check but before removal, this is not sufficient. The publication path must reject attaching to a chunk whose deletion generation is active, or atomically revive and protect it before the sweep can proceed.
Make publication and reclamation agree on ownership
For a deduplicating system, a practical protocol is to allocate a chunk identity that includes an immutable content hash and a separate generation or storage-instance ID. When a writer wants to publish a manifest, it must first acquire or validate a live reference to each chunk within the coordinator's transaction or an equivalent fenced protocol. The writer can re-upload or explicitly restore it to a valid state through the same authority that owns deletion.
The collector, meanwhile, may transition candidate chunks into a terminal deleting state only after confirming that no committed or protected pending references remain. Storage deletion can happen asynchronously after that logical transition. This design has a conservative failure mode: it may leak some unreferenced chunks if a worker crashes, but it should not delete live chunks. A periodic reconciliation pass can recover space later.
What about a new writer uploading the same hash after the old instance was deleted? If physical names can be reused, an old delayed delete operation might arrive after the new upload and remove the replacement. Include a generation-qualified physical key or conditional deletion tied to a specific version. Fencing needs to reach the storage system where deletion actually occurs, not stop at a database row that a stale worker can ignore.
A long-running reader is another kind of reference
Suppose a restore begins reading a 500 GB file manifest. The user deletes the file while the restore runs. If the service promises that an authorized restore can finish once started, that reader must pin the relevant manifest and chunks for the required duration. A lease may work if workers renew it reliably, and the storage service ensures deletion cannot race a still-valid lease. Alternatively an immutable snapshot can remain retained for a known recovery window.
I would test the race with a deterministic scheduler that pauses GC after marking X unreachable, commits a new manifest pointing to X, then resumes deletion. Repeat with worker crashes before and after the final reachability check, delayed physical DELETE requests, duplicate retries, and simultaneous legal holds. Verify that every committed retained manifest has readable valid chunks, even if reclaimable storage leaks temporarily.
At Principal level, the interesting tradeoff is not 'how often do you run GC?' It's whether the publication protocol and deletion protocol share a provable ordering rule. A system can recover leaked disk space later. It cannot reconstruct a chunk that every physical copy has already been told to delete.
