Answer

Sharded Content-Addressed Cache — Verified Solution

The full self-contained markdown (root-cause analysis, on-disk protocol, byte-exact code, tests, and verified output) is at ~/SOLUTION.md (copy at ~/cac/SOLUTION.md), with the runnable implementation in ~/cac/{cache.js,test.js,crash-child.js}.

Root-cause analysis

The failures are five missing guarantees, not one bug:

1. Duplicate/partial blobs — writing directly to the final path is non-atomic. Fix: temp → fsync → atomic link(2), which fails EEXIST, so identical concurrent uploads converge on one inode.
2. Eviction deletes a referenced blob — check-then-unlink TOCTOU. A manifest can acquire a reference between the refs==0 check and the unlink.
3. Crash between commit and metadata update — refcounts living only in a WAL either leak or, worse, replay a release and delete a live blob.
4. Global serialization — one lock keyed on the cache instead of on the data.
5. Crash mid-commit/mid-evict — no defined linearization point, so recovery guesses.

Exact fix (protocol)

• Two-phase reservation: a committing manifest durably reserves every newly referenced blob before the atomic rename that publishes it. Eviction succeeds only when refs == 0 && reserved == 0, under the same per-shard lock → the published manifest's reference set is undeletable from the instant it is visible.
• Manifests are the durable source of truth. Recovery recomputes refs from manifests; the per-shard WAL only records reservations (multi-process correctness) and evict intents (so an interrupted unlink is completed).
• Journal framing: <crc32>\t<json>\n; replay stops at the first bad/short record and truncates the torn tail.
• Sharding without global locks: shard = parseInt(hash[0:8],16) % S, one mutex + journal per shard, plus a per-manifest-name mutex. Reservations hold exactly one shard lock at a time and release before the next → no deadlock, no global serialization.

Linearization points: commit = rename; eviction = unlink (WAL evict written before it).

Verification

The document is self-contained: extracting its three js blocks reproduces the source files byte-identically, and running from the extracted directory passes:

ok   basic put/get and manifest commit/delete (8ms)
ok   concurrent identical uploads converge to one blob (25ms)
ok   commit-vs-evict race never yields a manifest with a dead blob (93ms)   # 300 raced trials
ok   sweep storm preserves committed blobs (13ms)                            # 600 concurrent ops
ok   crash recovery: torn tail, orphan reserve, interrupted evict (3ms)
ok   SIGKILL during commit/sweep loop is recoverable (370ms)                 # 5 real SIGKILLs

6 test group(s) passed

Run it yourself:

cd ~/cac && node test.js

The suite was run five consecutive times with identical results (no flakiness). The key invariant — if a manifest is committed, all of its blobs are present — is asserted both under in-process races and after real SIGKILL recovery.

Limitations are stated honestly in §5: the reference implementation is single-process with full intra-process concurrency; the same protocol extends to multi-process by adding a per-shard OS advisory lock around the reservation-append critical section, with no new invariants.