publication across two stores

two stores that fail independently cannot share a transaction: an object store and a database, a data page and the pointer that names it, a PDS blob and the record that references it. what survives the split is an asymmetric promise:

• safety — a published reference always resolves to the exact bytes it names. Never violated, not even briefly.
• liveness — bytes that never got published eventually disappear. Briefly orphaned is fine; forever orphaned is not.

The asymmetry is what makes the problem solvable. The protocol below keeps both promises with ordinary row locks and an idempotent sweeper, and the same shape appears inside single-file storage engines.

the schedule that breaks "check, then commit"

Writing bytes first and garbage-collecting unreferenced ones later sounds sufficient. It is not:

1. the store persists the object; the success reply is delayed;
2. a collector sees no reference and deletes the object;
3. the reply arrives; the uploader inserts the reference.

An existence check immediately before the insert leaves the same gap, because the collector can run between the check and the commit. Unreferenced is an observation; abandoned has to be a decision, and it has to be made in the place publication is also decided.

the protocol

Publication and abandonment are terminal, mutually exclusive, and serialized on the row, so whichever locks it first wins: a reaped writer cannot publish a reference to deleted bytes, and a writer that is mid-publication cannot be reaped underneath. Expiry is permission to reclaim, not proof the writer is dead — a paused process wakes up, and its late publish must fail on the row, not on a stale reply.

The proof obligations are one safety invariant (ref(k) ⇒ object(k) = expected_bytes) and one liveness claim (abandoned(k) ⇒ eventually always absent(k)), and the liveness half needs assumptions worth writing down: finitely many late writes, fair sweeping, eventual service recovery. Finite tombstone retention is not free — it needs a bound on late writes, storage-side fencing, or a recurring inventory that still classifies every abandoned key.

content-addressed keys break the base model

The proof assumes a key belongs to exactly one attempt. A content-hash key does not: two uploads of the same bytes stage the same object, and a published track and an abandoned duplicate name the same key. Abandoning one attempt must not delete the other's bytes, so a sweep needs ownership on top of the state machine — a refcount over every live reference, plus a claim by any unfinished attempt whose intent names the key (which works only because intent precedes bytes).

the same shape inside a storage engine

A copy-on-write B+ tree with alternating superblocks is this protocol with the "database" collapsed into one 8-byte pointer write:

The superblock alternation is LMDB's; the in-memory write buffer merged into the on-disk tree at commit is the two-component tree from the original LSM paper. The single-module implementation is public domain and explicitly invites vendoring.

other instances

• Resumable uploads with a job row as the intent: cleanup hints are written before bytes are promoted; record creation locks the job row FOR UPDATE inside the reservation transaction and refuses a failed job; the reaper claims with FOR UPDATE SKIP LOCKED, commits, then deletes; terminal states reject progress and heartbeat writes; a perpetual sweep re-deletes recently failed jobs' media through a refcount-guarded discard and skips any key an unfinished job claims.
• A search index rebuilt in place is the same problem across two stores: a completion marker in one and mutable rows in another expose a partial replacement under the old marker when a build fails, and a version token derived from metadata does not pin a multi-page read. Publish immutable generations and retire the previous one only when no reader holds it.
• atproto PDS blob lifecycle is the same problem with the store and the database on one host: uploadBlob creates a temporary blob (the intent), the record write references it (the publish), and unreferenced blobs are garbage-collected (the sweep). A PDS that GC's on "unreferenced" alone has the schedule above; see atproto blobs for the lifecycle in one implementation.
• Local segment storage can take a different stance: fsync the bytes first, let metadata lag, and rebuild the manifest from the segment files on recovery. Bytes written before a metadata failure are rediscovered rather than swept — a valid answer when the "database" is yours to rebuild.

Admission slots follow the same rule from the other side: see leases and expiry.

sources

• garrison (@garrison.corporate.fm), "Two writes, one promise", 2026-09-19 — essay and verification brief (thirteen adversarial schedules T1–T13); original question bsky post 3mvsjkpecfs2a, 2026-09-18.
• garrison, XB — README.md "Design" and "Format", lib/xb.ex, master at f79d66d, 2026-09-18.
• plyr.fm, PR #2075 and docs/internal/backend/resumable-uploads.md, 2026-09-19; the content-hash ownership incidents are #1732–#1735.
• pensieve, docs/OPERATIONS.md (generation and admission design), 2026-09-20.
• atproto, blob lifecycle.
• LMDB, design overview; O'Neil et al., "The Log-Structured Merge-Tree", 1996, pdf.