Spec: record body storage — history, retention, reclamation#

Status: research, options for decision

Tracking: hydrant-6vo (description predates this framing); related hydrant-715,

hydrant-u93, hydrant-w8q, hydrant-iis

Decision update#

The permanent layout below landed: current bodies live inline in heads

(the v10 migration builds that keyspace with zstd at every level — v9 had

persisted "never compress" into the old records keyspace's on-disk config),

superseded bodies move to history, and HYDRANT_HISTORY_TTL optionally bounds

that history. The queryable-ephemeral extension did not land. Ephemeral remains

the shipped separate architecture: it stores create/update bodies only inside

monotonic events, exposes no record-body XRPCs, and event TTL removes metadata

and body bytes together. Storage mode is immutable per database. The remaining

sections preserve the measurements and alternatives that led to those choices.

What this is actually about#

The first version of this spec asked "how do we delete from the CAS". That was

the wrong question, for two reasons that came out of review:

1. The orphaned bodies are the permanent history. They are what makes

cursor-0 replay of a deleted or superseded record resolve today. Same bytes,

different name. Deleting them on death would not fix a leak, it would delete a

capability the indexer advertises.

2. Permanent history needed an explicit policy. The original implementation

had only ephemeral and ephemeral_ttl; the landed layout adds

HYDRANT_HISTORY_TTL while leaving unset history permanent.

So the real subject is: give the archive a shape, and make retention depth a

policy instead of an accident. Reclamation falls out of that; it is not the goal.

Landed permanent behaviour: updates, protocol deletes, and repo purges move

superseded bodies from records into record-keyed history; operator deletion

can replace selected head/history bodies with durable CID redaction markers.

Ephemeral mode never enters either keyspace.

The constraint that decides everything#

Bodies are addressed two ways, and the two want opposite sort orders.

• Query wants key order. getRecord/listRecords/generate_car reach a body

through records ({did}|{col}|{rkey}), so bodies must be findable by record

identity.

• Bulk expiry wants time order. The only cheap reclamation primitive is

drop_range, which drops only tables fully contained in the range

(OwnedBounds::contains, lsm-tree/src/compaction/drop_range.rs:38-54, choose

at :75-99). That is free when old data occupies whole tables, i.e. when the

keyspace is monotonically keyed by time, and useless when the expiring keys are

scattered.

Nothing bridges the two orders except an index mapping one to the other, and any

index proportional to live records is disqualified by the budget arithmetic below.

**This is why ephemeral mode exists as a separate architecture rather than a

setting**: it picks time order (events, monotonic, drop_range-pruned) and gives

up getRecord entirely, while the indexer picks key order and gives up cheap

expiry. That split is the LSM's constraint, not an implementation accident.

Secondary constraint, from the same place: event replay needs the body *as of the

event*, not the current one. stored_to_event resolves StoredData::Ptr(cid) via

keys::block_key(collection, cid) (src/control/stream/indexer.rs:157-195),

jetstream likewise (src/jetstream.rs:101-128), and records holds only the head

CID (src/db/txn.rs:239-243) — so a record that has merely been updated is

already unresolvable through its record key.

Measured#

Live jetstream samples, whole network (method at the end).

Churn#

At the measured compacted body size of 122.4 B/record (hydrant-715 sizing,

volsinii, zstd:3): 271 MB/day, 98.8 GB/year of superseded bodies.

What permanent history costs#

$$underbrace{36.7\,\mathrm{M} \times 173.6\ \mathrm{B} = 2.33\ \mathrm{TB/yr}}_{\text{live growth}}

qquad\text{vs}\qquad

underbrace{98.8\ \mathrm{GB/yr}}_{\text{history}}

;=\; 4.2\ \%\ \text{overhead}$$

Permanent history costs about 4 % on top of growth you are already paying for.

That number is why this is a shaping problem and not a reclamation problem:

optimising away 98.8 GB/yr while adding 2.33 TB/yr is not where the leverage is.

In the version-keyed layout below the ratio simplifies: a superseded version costs

the same as a live one, so the overhead is exactly the death rate, 6.02 %. Both

numbers are small, and neither justifies bookkeeping that scales with the live set.

The budget rule#

Implied live record count at that sizing is 27.1 G, which prices every

candidate bookkeeping structure:

Anything proportional to live records loses to what it manages. Only

churn-scale (6 % of writes) or segment-scale structures can pay. Not theoretical:

the removed GC (src/db/gc.rs + src/db/refcount.rs at 41096cf, deleted in

2505c2c a week later) held an scc::HashMap<cid, i64> for every block — ~1.4 TB

of RAM at network scale — plus a persisted block_refs keyspace, a block_reflog

delta WAL, a startup rebuild scanning all records and all events, and

/stream/ack so consumers could release event references. [INFERENCE] that, not

the compaction filter, is why it was removed; the commit messages give no reason,

but f85858a [db] do the whole gc check in read_sync shows the map was already a

contention problem at test scale.

Age at death#

From TID rkeys (1 577 of 16 797 rkeys were not TIDs and are excluded). The top 10

deleting DIDs are 56.5 % of deletes, so this shape is bulk-purge dominated and

moves hour to hour; treat it as indicative.

Two thirds of deaths are of records older than a week, so a short retention window

only covers ~30 % of them.

Record sizes#

77 322 writes, JSON bytes: 94.5 % of records are < 512 B; records ≥ 1 KiB are

1.0 % of records and 8.1 % of bytes; 0 % of measured superseded bytes came from

collections whose mean record is ≥ 1 KiB. This is what rules out KV separation

(see rejected).

CAS sharing is not zero#

This is the finding that forced the redesign. hydrant-715 recorded "CAS dedup is

~zero in practice" from a 30k-repo uniform sample (19 731 596 blocks vs

19 731 589 records). That instrument cannot see sharing: a collision needs both

byte-identical records inside the sample, and 30k of ~41M repos makes that

vanishingly unlikely. A mean over 19.7 M records is well-powered; a rare-event

join in the same sample is not.

Measuring the live stream instead — 388 316 create/update commits over 15 min,

grouping (collection, commit.cid) by owning (did, rkey) — finds **94 bodies

shared across distinct records, 0.0242 % of writes**, in a 15-minute window alone.

The true rate over 27 G records is strictly higher, since any two byte-identical

records anywhere in history collide.

The dominant source is structural: chat.bsky.actor.declaration is a

literal:self singleton whose body is two enum fields, so it is byte-identical

across accounts. Verified live against three unrelated PDS hosts —

did:plc:kh4m6rayj2kzracvkh5s3th7, did:plc:2673vqptjnevhots5iywanik and

did:plc:uj5rhp72z653hxzvkg56nlbu all return cid

bafyreidhqffzznrmwedtdpliuep2kja3j7lbt6nk3xymkymsinaxl7us5q for

{"$type":"chat.bsky.actor.declaration","allowIncoming":"none","allowGroupInvites":"none"}.

One block is therefore the body of an unbounded number of live records. Collisions

also occur within one repo (two same-millisecond likes under different rkeys

appeared in the sample), so a DID prefix alone does not make bodies unshared.

Two consequences:

1. Any in-place "delete the body when its record dies" is a live-data bug.

Knowing whether a body has other owners is the reverse index the budget rule

rejects.

2. Content addressing buys 0.024 % dedup while charging a 36 B CID value in

records, a 36 B incompressible CID in the blocks key, and a second point

read per getRecord. That is the entire case for addressing bodies by record

version instead of by content.

Key layout A/B (measured, and it refutes the obvious intuition)#

The objection to version-keying is that {col}|{cid} groups every record of a

lexicon together globally, so bodies within a data block are structurally similar

and compress well, whereas a DID-major layout separates them by repo. That is a

sound mechanism argument. It is also wrong, measurably, in both of its halves.

Corpus: 240 real repos, 269 177 records, 62 MB of DAG-CBOR bodies (mean body

230 B — which independently confirms the ~230 B DAG-CBOR estimate used elsewhere

in this doc), pulled by com.atproto.sync.getRepo from 12 active PDS hosts

sampled across a relay's listHosts (4 bsky mushrooms + 8 independents), MST

walked to recover real (collection, rkey) paths. Records per repo: p50 34,

p90 3 280, max 30 445. Blocks are modelled the way an LSM data block is built —

front-coded keys at restart interval 16, inline values, each block compressed

independently.

B/record and compression ratio, zstd:3:

(These three rows carried an all-zero 8-byte version stub, which compresses to

nothing — so they measure the unversioned key. See the correction below for what a

real rev suffix costs.)

zstd:5 (the L3+ policy) moves everything by ~1 %: 121.39 vs 75.33 vs 75.20 at

64 KiB.

The model is calibrated. col|cid at 64 KiB / zstd:3 comes out at

122.78 B/record against the production measurement of 122.4 B/record — 0.3 %

apart, on a keyspace tuned exactly that way (src/db/schema.rs:398-406). That

agreement is the reason to trust the other rows.

Decomposing where the 46 B/record goes (same corpus, 64 KiB, zstd:3, keys and

bodies compressed separately to isolate the two effects):

Two findings, both surprising:

1. The key side is where content addressing bleeds: 32.7 → 6.9 B/record. A

36-byte sha256 digest is incompressible by construction — front-coding shares

only the collection prefix and zstd recovers ~1.5 B. Replace it with

did+rkey+rev and every component is prefix-compressible: the DID repeats

across a run, TIDs share long prefixes, the rev suffix is near-constant. That is

−25.8 B/record, and it is the larger half of the win.

2. **Repo-major grouping compresses bodies better, not worse: 80.8 → 67.1

B/record, ratio 2.85× → 3.43×.** The reason the intuition fails: lexicon

similarity is schema similarity, and zstd already saturates that once a block

holds a few hundred records of one collection — which happens in every layout

here. What {col}|{cid} additionally destroys is value locality: CID order

is hash order, so records inside a collection are shuffled with respect to

author and time. {did}|{col}|{rkey} keeps one author's records of one

collection in TID order, so adjacent bodies share the author, share createdAt

prefixes, and often share subjects. Content addressing was paying for dedup

worth 0.024 % by randomising away 17 % of body compressibility.

And the layout question that prompted this is **noise: 76.24 vs 76.06 B/record,

a 0.24 % difference.** Bytes are dominated by large repos (p90 is 3 280 records),

and inside a large repo both orders produce the same local neighbourhood — one

author's records of one collection, in TID order. They only differ across the

small-repo tail, which carries little of the volume. Note the corpus is

8/12 independent hosts, whose users have more collection variety per repo than

bsky's; that bias works against DID-major, and DID-major still ties. On a more

bsky-weighted network the tie should hold or improve.

So the layout choice is not a storage decision. Pick it on access patterns:

did|col|rkey wins on everything except dictionary sampling, and

hydrant-iis already suspects dictionaries are net-negative at these block sizes

(hubble's sweep confirms it — see prior art). It is also the layout that

records already has, so the migration does not reorder anything.

The version suffix is not free (correction)#

The rows above used an all-zero !rev stub, which silently measured the

no-suffix layout. Re-measured with realistic revs — the record's own creation TID

where the rkey is a TID, else a per-repo rev:

An inverted TID is high-entropy in its low bytes and differs on essentially every

key, so neither front-coding nor zstd can touch it: +9.24 B/record, +12 %. A

one-byte generation is +0.13, i.e. free.

That kills the flat design. Putting a rev on every record spends

9.24 × 27.1 G ≈ **0.25 TB to serve the 6 % of records that ever have a second

version** — precisely the budget-rule violation this document opens with, and I

walked into it.

The two keyspaces, concretely#

records is today's keyspace with the value changed from a 36-byte CID to the body,

and the codec changed to MST order (below). history is new, `#[cfg(feature =

"indexer")] like blocks, declared in db/schema.rs + db/keyspaces.rs` +

db/registry.rs like any other.

death_rev, not the version's own rev. This is the correction that specifying it

forced: the head key carries no rev and the head value is just a body, so at death

time we do not know the rev the dying version was written at — recovering it would

mean storing 8 bytes on every live record, which is the 0.22 TB the budget rule

rejects. But we always know the rev of the commit doing the killing: RecordTxn is

constructed with it (Txn::records(state, &DbTid::from(&commit.rev), did),

src/ops.rs:234; RecordEmitter.rev, src/ops/record_events.rs:59). So key history

by when the version died, ascending, 8 bytes big-endian, no inversion.

That makes inflation a range seek instead of a point read: for an event at rev R on

record K, the body live at R is the one that died at the first death after R.

The range must be bounded to K's own entries, and getting that wrong is a

wrong-data bug rather than a miss:

Strictly after R, because a version that died at R was replaced by commit R

itself, and an event at R refers to the new body.

Two traps here, both load-bearing:

1. An unbounded upper bound makes the miss branch unreachable. The common case —

a record created and never touched — has zero history entries, so

range((Excluded(K‖R), Unbounded)).next() walks straight into the next record's

entries and returns a neighbour's body, which the "miss → head" branch would then

serve as K's point-in-time body. It never returns None in a populated keyspace.

2. A byte-range bound alone does not fix it, which is why the 00 before

death_rev is there and not decoration. rkeys are variable length, so one rkey can

be a true prefix of another (abc / abcd): without the separator, K‖FF×8 still

admits abcd's entries, because d = 0x64 < 0xFF. 00 is not in the atproto

rkey charset (0x2d–0x7e), so it sorts below every legal continuation and

[K‖00‖R, K‖01) is exactly K's own history. Verified against both cases.

Belt and braces, since the cost is one comparison on a cold path: assert the returned

key is exactly len(K) + 9 bytes with key[..len(K)] == K, and treat anything else

as a miss. That guard is sufficient on its own — a different record either fails the

prefix test or differs in length — so it also covers an implementation that forgets

the upper bound.

The invariant that makes the miss branch safe: history retention ≥ event

retention. If a history entry could be trimmed while an event referencing it is still

replayable, the miss branch would silently serve a newer head body for an older

event. With the invariant, a miss means nothing that old is replayable either, so

nobody can ask. Permanent events ⟹ permanent history; any bounded window must prune

events at least as aggressively as history. This is the one rule the whole design

rests on and it belongs in the config validation, not a comment.

Writers — all of them inside RecordTxn, which is already the single record

mutation path:

Readers: event inflation (src/control/stream/indexer.rs:157-195) and the

jetstream equivalent (src/jetstream.rs:101-128). Nothing else — getRecord,

listRecords, generate_car, backlinks and counts all stay on heads only. Backlinks

in particular must not index history (src/ops/backlink_ops.rs is called from

put_record/delete_record and stays where it is), and counts.records must keep

counting heads, so counts.add_blocks (src/db/counts.rs:39) either becomes a

history-entry counter or goes away.

Tuning: unlike blocks it is never read on the hot path, so it wants the

opposite settings — expect_point_read_hits(false), aggressive compression at every

level including L0, and large data blocks. Deaths within one commit share a

death_rev exactly and deaths within a repo share its prefix, so the suffix

front-codes well in practice despite being high-entropy across repos.

Cost: 2.21 M deaths/day × ~85 B ≈ 188 MB/day ≈ 68.6 GB/yr, ~3.3 %/yr against

a 2.06 TB core. Retention is a policy on this keyspace alone, so trimming never

touches the hot keyspace.

Migration (one re-key, three things at once)#

Since records is being rewritten anyway, the separator and rkey codec ride along

free — measured above at −2 B/record, so the codec change pays for itself:

1. body into the value (the point of the exercise),

2. SEP → NUL after the DID, / inside the path so collection order matches

MST/CAR order,

3. rkey as raw text instead of t+packed / s+string so rkey order matches too

(src/db/keys/indexer.rs:54-84; the tag is what puts every string rkey before

every TID rkey).

Needs Migration::Chunked from opt-work (c7d311a) — one resumable pass over

records, reading each body from blocks by its old {col}|{cid} key and writing

the new key. Peak disk is old + new until blocks is dropped, so the pass should

range-drop migrated prefixes from the old keyspace as it advances rather than at the

end.

Pre-migration superseded bodies cannot be reconstructed into history, because

their death revs were never recorded. Two options, and the simple one is better:

• (preferred) keep blocks read-only with a migration watermark event id, and have

inflation fall back to it for events below the watermark. No reconstruction, one

pass, and the existing orphans age out with event retention — or are simply kept, in

permanent mode, which is exactly their status quo.

• (rejected) rebuild history from a pass over events: an event gives

(did, col, rkey, rev, cid), so the next event for the same record supplies the

death rev — but that needs a resident map of every record with a pending version,

unbounded in permanent mode.

Collection interning (opt-work) under this layout: measured, and it stops paying#

Since this migration borrows Migration::Chunked from opt-work (c7d311a), the

obvious question is whether its collection interning (fa0a755, e76c2d5) should

ride along. Measured on the same 269 k-record corpus, same model, ids allocated by

frequency so hot collections get 1-byte varints:

Interning shrinks the plain key by 17.7 B/record but the on-disk size by

0.06 B/record (0.08 %, ~1.6 GB full-network) — front-coding and zstd already eat

the repetition in a did-major layout, because consecutive keys in a data block share

the whole did 00 col prefix. This is why hydrant-3kc.8's live-backfill A/B could

never resolve the effect: even in the old layout it was a few percent at most, and in

this layout it loses another order of magnitude. The plain-key win lands in

uncompressed structures (memtable, index blocks, bloom filters), not on disk.

It also conflicts with the codec change: interned ids sort by arrival order, not

NSID text, so stored collection order stops matching MST order (verified: the repo

with the most collections in the corpus stores its 16 collections in a different

order than the MST walks them). That kills the flat streaming merge-join the resync

section relies on. The escape hatch, if interning is ever wanted anyway, is a

per-collection merge-join — group MST leaves by collection (they are consecutive),

resolve each id, and prefix-scan {did} 00 {id} / per collection, taking vanished

collections from counts. Feasible, but it puts dictionary lookups and a reverse

map on the resync path to save 0.06 B/record.

Verdict: skip for records/history; keep the machinery. The varint codec

(collection_id.rs), dictionary keyspace, and chunked migration are well-built and

this migration needs the last of those regardless.

DID interning (hydrant-3kc.4, TrimmedDid's 16 B → u64) gets the same answer here

for a different reason: it does not break the merge-join (the DID is constant

within a repo join), but the measured on-disk saving in this layout is

0.18 B/record (75.96 → 75.78, ~5 GB full-network). The 8-byte figure is plain-key

only — in did-major order the DID is the shared prefix of every run, so front-coding

already amortizes it to ~1 B/key before zstd. The price is a 41 M-entry dictionary

(~2–3 GB resident, or a lookup on every record read/write) in place of TrimmedDid,

which is a stateless pure function. Same budget-rule shape, paid in RAM and hot-path

I/O instead of disk. The one place a DID segment genuinely never repeats is the

reverse backlinks key (r|{target}|{collection}|{path}|{did}|{rkey},

src/backlinks/store.rs:24 — every source DID under one target+path differs, and it

is a full 32-char string today); that is 3kc.4's only real target and it is

independent of this spec.

Two things worth knowing about why hubble interns, since their key does carry a

u64 DID (hubble/src/store/record.rs:1-50), and neither is a disk reason:

1. The u64 is their repo handle, not just a key segment. It is allocated when

a repo slot is created (hubble/src/sync.rs:89, `IdInterner::resume(db, "dids",

4096) at main.rs:313`) and used across the actor system — their in-memory

per-repo state keys on it instead of a 32-char string. Interning is their

in-memory architecture as much as their storage format, and their baseline was the

full DID string (a 24 B plain win), where ours is TrimmedDid (an 8 B plain win

we have already banked 16 B of, for zero state).

2. Where they measured a real win was value interning, and it was 1.8 %. Their

sweep replaced did:plc: strings inside CBOR record bodies (AT-URI subjects):

702 MB raw saved → 300 MB post-compression, 1.8 % of db size

(space-efficiency-check/readme.md:52-80, consistent across three configs). That

is the same finding as the table above from the value side: interning shrinks raw

bytes that compression had already mostly eaten. And it means interning moves

write amplification by the same ~nothing — WA is proportional to the compressed

bytes compaction rewrites, not the plain key length.

Their corpus is 4.35 M DIDs, ten times smaller than the full network — the

dictionary cost scales to us, the benefit does not.

Why the version key must be the rev — and why we do not want hubble's generation#

A one-byte counter is free on storage, but it cannot be the per-record version id:

• it needs a read. To write version n+1 you must know n. hubble gets away

with a u8 because its generation is per repo, held in the already-loaded

actor info slot (info_slot.resync_generation, hubble/src/sync.rs:38) — no I/O.

Per-record state would mean a point read on every write (36.7 M/day, 425/s) plus

somewhere to keep the counter.

• it cannot be ordered across a wrap. hubble never needs to: only two generations

are live and an explicit pointer says which is active. N versions need a total

order, so the suffix has to be monotonic and wide.

• the event only knows the rev. Any other version id needs a rev → id mapping,

which is a live-scale index.

And hydrant should not adopt the repo generation either — an earlier draft of this

section called it "orthogonal and free", which was wrong on both counts:

1. It does not buy us what it buys hubble. The generation exists so a resync can

replace a whole repo atomically without a read-back diff, which works because

hubble emits nothing per record on resync — its readme sends you elsewhere for

that: *"record set reconciliation: consider Tap if you want per-record

add/delete/removes emitted on resync"* (hubble-sync/readme.md:33-35). hydrant

must diff, because it synthesises per-record create/update/delete events for

/stream (src/backfill/worker/process.rs:377-408). A generation flip would sit

next to our diff, not replace it.

2. It is not free on the read path. +0.13 B/record is storage only. Every read

would first have to resolve the repo's active generation: hubble absorbs that in

its per-repo actor, but RepoHandle::get_record is a stateless single point read

today and would become two — or need a resident did → generation map at

live-repo scale (~41 M entries).

The versioned-history design also subsumes the trick: with a history keyspace the

previous state is not garbage awaiting a range-delete, it is the history we wanted. A

resync writes new heads, moves superseded bodies to history, and gives vanished

records a tombstone version. Nothing to flip, nothing to drop.

The actual resync problem, and the ordering bug in the way#

What hurts today is not the missing generation, it is that the diff materialises

every CID in the repo into a HashMap<(SmolStr, DbRkey), SmolStr> before applying

(src/backfill/worker/process.rs:326-353) — a per-repo memory spike proportional to

repo size, on the whale repos where it hurts most. The fix needs no key change and no

generation: both sides are already sorted, so the diff can be a **streaming

merge-join** with O(1) memory. The MST walk yields leaves in key order, and

records iterates in key order.

Except they are not the same order, and this is worth checking before relying on it

anywhere. SEP = b'|' (src/db/keys/mod.rs:10) is 0x7c, which sorts **above every

character legal in an NSID**, so a collection that is a prefix of another sorts

after it. The MST separator is / (0x2f), which sorts below, so it sorts before:

So hydrant's stored record order diverges from CAR order exactly for prefix-related

collections (post/postgate, list/listitem, like/… ), which blocks a

merge-join and is worth auditing for anywhere else that assumes stored order matches

repo order. hubble avoids it by construction with NUL after the DID and / inside

the path. If we want the O(1)-memory diff, the separator change rides along free with

the body merge, since that rewrites the keyspace anyway — but it is a re-key, so it

should not be attempted on its own.

What this does to the storage estimate#

The merged head keyspace replaces both records (51.2) and blocks (122.4):

$$173.6 rightarrow 76.0\ \mathrm{B/record} = -56\ \%,\qquad 4.7\ \mathrm{TB} \rightarrow \sim2.06\ \mathrm{TB}$$

plus ~68.6 GB/yr of history if permanent history is on. Better than

hydrant-715's −45 % estimate, measured on real bodies, and corroborated

independently by hubble at 666 M records (74.35 B/record for the same shape). The

records-compression caveat is unchanged and quantified: uncompressed the same

layout is 230.2 (raw body) + 12.9 (front-coded key) ≈ 243 B/record, i.e. worse

than today's 173.6. The entire −2.6 TB depends on hydrant-w8q landing first.

Design: head plus versioned history#

death_rev is the 8-byte DbTid of the commit that superseded the version, ascending

(see the keyspace section above for why it is the death rev and not the version's own

rev). DbTid is already exactly [u8; 8] (src/db/types.rs:193), and the

load-bearing detail is that StoredEvent already carries rev

(src/types/event/stream.rs:116), so a historical body is reachable by one bounded

range seek with no CID anywhere on the path — which is hydrant-u93's win

(42.2 → ~13 B/event, 1.14 → 0.35 TB full-network) arriving as a side effect rather

than a project.

What the shape gives:

• Permanent history is the default, not a leak. Every event resolves forever.

There is no "replay of a dead record degrades" decision to make.

• Sharing is structurally impossible. A body is addressed by record identity, so

the two identical chat.bsky.actor.declaration bodies are two entries. You give up

the 0.024 % dedup, which is the rounding error above.

• Deletes become explicit. A delete moves the body to history and leaves either

nothing or a tombstone marker at the head, so getRecord returns not-found while

history records when it died. Today you cannot distinguish never-existed from

deleted.

• The hot path does not regress. getRecord remains a point read on an exact

key; listRecords remains a clean prefix scan; generate_car and repo purge

remain one range each. History lives in its own keyspace and is only touched on

replay.

• It is smaller, measured: 173.6 → 76.0 B/record, −56 %. Two thirds of that is

the key side (a 36 B random digest replaced by prefix-compressible components), one

third is bodies compressing 17 % better under author-and-time ordering than under

CID-hash ordering. See the layout A/B above.

• Versions of one record land adjacent within history, so successive versions

of an update-heavy record (app.bsky.actor.profile 79 % churn,

dev.sensorthings.observationBatch 100 % updates at ~6.4 KB) sit in the same data

block and should delta-compress well. Still unmeasured — getRepo returns a

single snapshot, so the corpus has one version per record and the A/B above cannot

see this effect. It is upside on top of the −56 %, not part of it.

The cost this shape adds over hubble's head-only store is one body copy per death

(6.02 % of writes) and one usually-missing point read on the replay path. That is

the entire price of having a cursor-replayable stream.

Retention is a dial, not a mechanism#

Because rev is a TID, an item's age is in its key, and because heads live in a

different keyspace from history, a retention filter never has to work out which

version is current. Every policy is a purely local, key-only decision during

compaction — which is exactly what a CompactionFilter is for:

Splitting heads out removes the head-detection problem entirely: the earlier flat

design needed the filter to guess whether the first entry it saw for a prefix was

current (safe, but only because the failure mode was conservative). Here a filter on

history can never see a head, so there is nothing to guess. Verdict::Destroy

writes no tombstone, so trimming costs no write amplification

(lsm-tree/src/compaction/filter.rs:18-43).

The third row is the only one that needs anything extra: a head carries no rev in its

key, so expiring heads by age needs the write time somewhere — either an 8-byte

field in the head value (which the budget rule prices at 0.22 TB, i.e. only worth it

in ephemeral mode where the keyspace is a window, not the network) or the epoch-prefix

variant discussed under ephemeral below.

What this means per mode#

• Indexer, permanent (default). Keep all versions. 4.2 % on top of live

growth. No filter installed.

• Indexer, bounded history (new). Keep head plus a window. Reclamation is

lazy — it lands when compaction next covers the range — which is acceptable

because heads are never at risk and the window only covers ~30 % of deaths

anyway.

• Ephemeral. Remains event-only. StoredData::Block owns each create/update

body inline, no records or history entries are written, and record-body

XRPCs are unavailable. Because event IDs are monotonic, TTL keeps the hard

drop_range bound and cannot strand body bytes in another keyspace. The mode

is persisted and immutable rather than treated as an online configuration

dial. A queryable window would require a separate future design.

• Relay. Untouched. It uses its own relay_events keyspace and never writes

records/blocks.

Worth noting the asymmetry this exposes: indexer/relay are compile-time and

mutually exclusive (compile_error! in src/lib.rs), while ephemeral is a

runtime bool threaded as branches through shared write paths. It behaves like a

mode and is implemented like a parameter. If it stays a mode after this, that is

worth fixing in the same pass.

Costs and open risks#

• **records compression is off, and this flips the sign of the storage

estimate.** data_block_compression_policy(CompressionPolicy::disabled()),

rationale "cids arent compressable" (src/db/schema.rs:343-356). Bodies are

122.4 B/record because blocks runs zstd:3/zstd:5

(src/db/schema.rs:398-406). Merging into records as-is stores raw bodies:

$$20.9 (\text{front-coded key}) + 230.2\ (\text{raw body}) \approx 251\ \text{B/record} \Rightarrow \mathbf{+2.1\ TB}$$

versus the measured 173.6 → 76.2 B/record ⇒ −2.6 TB with zstd on. A ~4.5 TB

swing on one keyspace option, decided entirely by whether hydrant-w8q lands

first.

• Read path. Unchanged for heads: exact-key point read, same bloom calculus,

same clean listRecords scan. The replay path gains one usually-missing point read

on history. The one new cost is records block sizing — it is [8, 16] KiB

today because values were 36-byte CIDs (src/db/schema.rs:352); holding bodies it

wants 64 KiB+, or the merge gives back 8–13 % (hubble's sweep).

• Write path. One body copy per death (2.21 M/day) plus a point read to learn the

dying rev on update/delete, since apply_commit takes the action straight from the

firehose op and never reads the old record (src/ops.rs:236-266). Repo purge and

backfill resync already hold what they need

(src/db/indexer.rs:34-44, src/backfill/worker/process.rs:326-353).

• Version granularity is per-commit, so two ops on the same col|rkey in one

commit collapse to the last. Identical to today's head behaviour, so no

regression — just not "every intermediate state".

• Permanent means permanent from first sight. PDSes do not serve repo history

(getRepo returns the current MST), so nothing reconstructs versions from before

hydrant indexed a repo. This needs saying in user-facing docs, because "permanent

history" reads like a stronger promise than it is.

• Migration. blocks has to be re-keyed and merged. On main there is no

machinery: migrations are a flat list of single-batch functions

(MigrationFn = fn(&Db, &mut OwnedWriteBatch), src/db/migration/mod.rs:17-47).

Migration::Chunked — resumable key-ordered passes with a per-pass cursor in

counts under mig|{version}|{pass} — exists on opt-work (c7d311a) and must

land first. That branch also interns collection NSIDs as varints in

records/counts keys (fa0a755) while deliberately leaving block_key on the

raw NSID string, and carries a storage A/B driver

(tests/bench/collection_interning_ab.sh).

• Per-collection zstd dictionaries. blocks is collection-prefixed

specifically so dictionaries are samplable by prefix hop

(src/db/schema.rs:373-408, src/db/train.rs:26-45). DID-first grouping ends

that. hydrant-iis already suspects dictionary training is net-negative, so the

honest resolution may be to close it as "drop dictionary training" rather than

preserve the constraint.

Engine capabilities (verified in the pinned forks)#

• drop_range drops only fully-contained tables

(lsm-tree/src/compaction/drop_range.rs:38-54,75-99). Free for monotonic

keyspaces, useless for scattered keys. Already used for event TTL:

rotate_memtable_and_wait() then drop_range(..event_key(cutoff_seq))

(src/db/ephemeral.rs:165-185), with the cutoff from a persisted

1-second-resolution ewm|{ts} -> seq watermark in cursors (:113-145).

• User compaction filters, exposed at the fjall level and persisted through

recovery: Database::builder().with_compaction_filter_factories(assigner)

(fjall/src/builder.rs:170-189, fjall/src/db.rs:467-473,

fjall/src/recovery.rs:80-86); verdicts

Keep | Remove | RemoveWeak | ReplaceValue | Destroy

(lsm-tree/src/compaction/filter.rs:18-43); invoked for every non-tombstone item

during any compaction with Context { is_last_level }

(lsm-tree/src/compaction/stream.rs:145-165). Hydrant already shipped a filter on

this API (41096cf:src/db/gc.rs), so the seam is proven here — only its oracle

was unaffordable. ItemAccessor exposes key() and value() but **not the

seqno** (filter.rs:123-170); a seqno accessor would be a small fork addition,

though the TID-in-key design does not need one.

• FIFO compaction with a table TTL per keyspace

(lsm-tree/src/compaction/fifo.rs:31-46, wired through

fjall/src/keyspace/options.rs:262-326) — but it asserts L0 disjointness

(fifo.rs:82) and drops oldest tables, so it is only correct for

monotonically-keyed insert-only keyspaces.

• KV separation with blob GC (separation_threshold default 1 KiB,

file_target_size 64 MiB, staleness_threshold 0.25, age_cutoff 0.25 —

lsm-tree/src/config/mod.rs:76-99), stale accounting via FragmentationMap

(version/mod.rs:190-193), surfaced as Keyspace::fragmented_blob_bytes()

(fjall/src/keyspace/mod.rs:287-294).

• Replay already tolerates an unresolvable body: read_event_replay_chunk sets

last_seen_seq before inflating and continues on None

(src/control/stream/indexer.rs:106-118), bounded by

max_scanned = 4 × chunk_size (:76,83). With bounded history, a miss is

expected rather than a storage bug: stored_to_event downgrades the old

error!("record body not found, this is a bug") to debug! and counts it

on state.history_trim_misses, surfaced as history_trim_misses in

/stats only when HYDRANT_HISTORY_TTL is set.

Prior art#

hubble (microcosm.blue) — the closest comparable, and it corroborates the layout#

tangled.org/microcosm.blue/hubble is a whole-network public mirror in Rust on the

same jacquard stack, split into hubble-sync (sync/backfill/identity, engine-agnostic

over a Storage trait with both hubble-sync-fjall and hubble-sync-rocksdb

backends) and hubble (the mirror app, on RocksDB). Its readme scopes itself

explicitly against us: *"record storage: consider Hydrant if you want your sync tool

to store records for you. never going to be part of hubble-sync."*

(hubble-sync/readme.md:30-31.) So it is complementary, not competing — but it

stores records in the app layer, and that is directly comparable.

Their record key (hubble/src/store/record.rs:1-50):

value is the raw DAG-CBOR record. **No CAS, no CID stored anywhere, DID interned to

a u64, path suffix = {col}/{rkey}.** That is the layout this spec argues for,

arrived at independently. Deletion is correspondingly trivial — apply_commit does

wb.put_cf for added/updated and wb.delete_cf(records, key(repo, gen, op.path))

for deleted (hubble/src/sync.rs:47-59). No oracle, no refcount, no sweep, because

the key is the record identity. hubble is the existence proof for the central claim

here, at 666 M records.

And their space sweeps independently replicate my block model. 490 328 repos,

665 928 371 records, 246.5 GB of input CARs, RocksDB, key layout above

(space-efficiency-check/readme.md):

Two independent methods — my synthetic front-coded block model over 269 k records,

their real RocksDB over 666 M — agree within 1–4 % across the whole curve, and the

residual has an obvious explanation: their figure is real on-disk SST bytes including

bloom filters (~1.25 B/record at 10 bits/key) and index blocks, while mine counts

data-block bytes only. Corrected for that, the agreement is ~1 %.

The blunt comparison: hydrant today stores 173.6 B/record (blocks 122.4 +

records 51.2) where hubble stores 74.35 for the same records —

2.33× more per record, and the difference is almost entirely the two CID copies

that content addressing forces.

Things worth stealing, with citations:

1. DID interning to a u64 (hubble/src/store/id_interner.rs: crash-safe

monotonic counter, i|{name} -> u64_be, with a pre-covered range so the hot path

does no I/O). This is hydrant-3kc.4, running in production over there. Their key

spends 8 bytes where our TrimmedDid spends 16.

2. A separator that matches repo order. NUL after the DID and / inside the

path means hubble's stored order equals MST/CAR order; hydrant's SEP = b'|'

(0x7c) does not, for prefix-related collections. See the ordering section above —

this is what blocks an O(1)-memory resync diff.

3. A resync generation byte — examined and rejected for hydrant above: it does

not remove our diff (we owe per-record events, hubble does not) and it is not free

on our stateless read path. Noted here because it is the right answer for their

architecture, and because the underlying problem it solves — the per-repo

HashMap<(SmolStr, DbRkey), SmolStr> at src/backfill/worker/process.rs:326-353 —

is real and still ours to fix.

3. SST ingestion for resyncs — SstFileWriter + IngestExternalFileOptions

(hubble/src/sync.rs:11, RESYNC_CHUNK = 16_384) bulk-loads a repo as a

pre-built table instead of a giant WriteBatch. fjall has no external-SST

ingestion equivalent, so this is a genuine engine capability gap worth noting

before betting on very large resyncs.

4. zstd dictionaries are worthless for records — independently confirmed. Their

sweep at 4 K blocks with dictionary sizes 8, 16, 32, 64, 128, 256, 512, 1 k, 2 k,

4 k, 8 k, 16 k returns byte-identical db sizes (54 771 8xx bytes every time),

and their conclusion is recorded verbatim: ` so dictionaries are actually not

worth it (at least for records) `. That is the second independent signal to

close hydrant-iis as "drop dictionary training", and it removes the last

argument for keeping a collection-major prefix.

5. Data blocks want to be much bigger. 4 K → 64 K is −22 % for them; past 64 K is

flat. blocks currently uses [16, 64, 128] KiB and records uses [8, 16] KiB

(src/db/schema.rs:352, :398) — if bodies move into records, that policy has

to go up, or the merge silently gives back 8–13 %.

6. Restart interval wants to be larger too: their sweep improves through 8 → 16 →

32 → 64 and regresses at 128. We use [8, 16, 32] for blocks, [16, 32] for

records.

Where hubble does not help us, and it is the whole remaining delta: it is

head-only. Deletes are deletes, there is no version history, and getRepo is

reconstructed from current records plus a stashed commit signature and prev

(hubble/src/serve/get_repo.rs, store/commit_slot.rs). It has no cursor-replayable

event stream, so it never owes anyone a point-in-time body — which is exactly why it

can delete freely and why it has no GC problem to solve. The history keyspace and

the retention dial in this spec are precisely the surface hydrant needs because it

offers /stream replay. That also surfaces a real tension: their generation trick

makes resync O(new repo) with no read-back, but hydrant owes per-record events on

resync, so it needs the diff regardless — see the resync section above, where the fix

is a streaming merge-join rather than a generation.

One more datapoint on CAS sharing from their side: their count-record-dups branch

adds hubble/examples/count-record-dups.rs, which sha256-hashes every stored record

to find byte-identical values under multiple keys within one repo generation. Their

motivation is different — the sync 1.1 draft claims CAR block ordering lets parsers

keep "minimal MST state", and duplicate records break that for streaming parsers —

but it is the same underlying fact I measured at 0.0242 % of writes. Note the

asymmetry: for hubble, duplicate records are a storage inefficiency (it stores the

bytes twice); for hydrant's CAS they are a correctness hazard (deleting one blanks

the other). Same phenomenon, and content addressing is what converts it from waste

into a bug.

everyone else#

• atproto TS PDS and rsky delete bodies inline in the commit transaction,

using the MST diff's removedCids as the oracle — no index, no sweep

(packages/pds/src/actor-store/repo/sql-repo-transactor.ts:40-77;

rsky-pds/src/actor_store/repo/sql_repo.rs:242-246). They keep no history, so the

question does not arise for them.

• indigo carstore keeps append-only CAR shards plus a SQL staleRef table

and reclaims by rewriting a repo's shards keeping only live blocks

(CompactUserShards, carstore/bs.go:1073-1225) — per-repo mark and sweep,

O(repo bytes). The newer cmd/relay dropped block persistence entirely.

• Relay event stores (indigo pebblepersist, diskpersist) reclaim purely by

time — range-delete everything older than the window

(events/pebblepersist/pebblepersist.go:215-255). Same shape as hydrant's event

TTL, and the same time-ordered-keyspace requirement.

• AppViews (packages/bsky) and microcosm constellation keep no bodies at

all; spacedust drops delete events outright.

Nobody maintains a global CID refcount. The working patterns are *derive the dead

set from the commit and reclaim by time*.

Rejected, with evidence#

• "Inline bodies in events and drop the CAS." Not a proposal — this is already

implemented as ephemeral mode (StoredData::Block,

src/ops/record_events.rs:79-94). The earlier draft listed it as a novel option,

which was a mistake. Its cost as a general strategy is

+122.4 B × 36.7 M writes/day = +4.5 GB/day of retained window, i.e. every write

pays instead of the 6 % that die.

• Refcounts or a cid → owner reverse index. 40 B × 27.1 G = 1.08 TB to manage

98.8 GB/yr — 11 years to break even. Built and removed already (41096cf →

2505c2c), with a ~1.4 TB RAM-resident map at network scale.

• In-place deletion on death, under content-addressed keys. Measured 0.0242 %

of writes land on a body another live record owns; deleting blanks the other

owners. No cheap fix exists inside content keys, and a per-collection denylist is

not one either — ordinary likes, posts, follows and reposts collide too.

• Periodic full mark and sweep. A live-set filter needs a full records scan

(~1.4 TB) and the sweep needs the ~3.3 TB blocks scan, to find ~100 GB. The

filter is affordable (≈7 bits/key ribbon ⇒ ~24 GB, or per-collection passes); the

I/O is not. It stays the fallback for a **one-off cleanup of the garbage already

on disk**, which is a real need whichever design lands.

• KV separation / blob GC for bodies. 1.0 % of records and 8.1 % of bytes are

≥ 1 KiB, and ~0 % of superseded bytes come from ≥ 1 KiB collections. Below ~1 KiB

separation loses on pointer overhead and the extra read hop (WiscKey FAST '16

§4.3; Titan and Badger default min_blob_size to 1 KiB, RocksDB BlobDB to 4 KiB).

Blob GC also only accounts staleness after the index entry is deleted — it

answers "reclaim the bytes", never "which bytes are dead".

• A page-managed engine (redb / LMDB / canopydb) for bodies. None reuse freed

pages while an older read transaction is open; all have 50–100× write

amplification for random-order small-key inserts (4–6 CoW pages per ~300 B

insert) and ~1.5–2× space amplification from ~50–67 % page fill; none support

block-level value compression except sanakirja. The 122.4 B/record figure is

zstd on LSM data blocks — giving that up to make deletes free loses far more than

it saves.

• A bespoke append-only segment log with per-segment stale counters

(bitcask/WiscKey shape). That is what fjall blob files already are, plus a

hand-rolled framing, compression and crash-recovery story, and it reintroduces

the small-value problem.

• FIFO + TTL on a key-ordered keyspace. Drops oldest tables regardless of key

and asserts L0 disjointness (lsm-tree/src/compaction/fifo.rs:82) — it would

panic on a scattered keyspace, and eat live bodies if it did not.

To measure before committing#

• Version-adjacency compression across multiple versions of one record. The

one claim the layout A/B could not test, because getRepo returns a single

snapshot. Needs a corpus with real version history — either a hydrant instance

that has been running long enough to hold superseded bodies, or replaying a

firehose window and keeping every version. Update-heavy collections

(app.bsky.actor.profile, dev.sensorthings.observationBatch) are where it

would show.

• records with zstd enabled (hydrant-w8q) before anything else, since it

decides the sign of the whole storage estimate.

• Compaction reclamation lag for bounded permanent history: how long between a

filter deciding Destroy and disk_space() dropping, on a realistically deep

tree.

• Sharing rate over the whole keyspace, not a 15-minute window: count blocks

entries reachable from more than one live records entry on a real DB. The window

figure is a lower bound; the full number sizes how much data an in-place deletion

would have corrupted.

• Repo-purge volume: account deletions per day × records per repo. Bursty, not

in these numbers, and possibly dominant. Note purges are the one channel where the

old CIDs are already in hand (src/db/indexer.rs:34-44,

src/backfill/worker/process.rs:326-408).

• Read-path regression for seek-first getRecord and prefix-hopping

listRecords under public query load, with bloom filters both on and off.

Method#

Jetstream subscribers against wss://jetstream1.us-east.bsky.network/subscribe —

656 s for churn rates and age at death (a separate 179 s run agreed within 8 % on

every rate), 180 s for the size histogram, 900 s for the sharing rate — counting

ops by collection, decoding TID rkeys for age at death, attributing superseded

bytes by each collection's mean create size, and grouping (collection, commit.cid)

by owning (did, rkey) for sharing. The sharing result was confirmed out-of-band

with three com.atproto.repo.getRecord calls against the owners' own PDS hosts.

The layout A/B is a second, independent corpus: com.atproto.sync.listHosts on

relay1.us-east.bsky.network to enumerate active PDS hosts, every 10th host taken

to avoid one operator, com.atproto.sync.listRepos per host, then

com.atproto.sync.getRepo per repo (CARs over 48 MB skipped). Each CAR's MST is

walked to recover real (collection, rkey) paths, and the record leaf blocks are

kept as raw DAG-CBOR. 240 repos, 269 177 records, 62 MB of bodies, 57

collections. Each candidate key is built over that corpus, sorted, packed into

data blocks at a target uncompressed size, and each block compressed

independently with Bun.zstdCompressSync; keys are front-coded at restart

interval 16 with a 2-byte shared/suffix header, mirroring an LSM data block.

CIDs are recomputed as sha256 over the body so col|cid ordering is the real

hash order. The model's col|cid result (122.78 B/record) lands 0.3 % from the

production measurement (122.4), which is the only available validation that it is

faithful.

JSON byte counts are an upper bound on DAG-CBOR bytes. Per-record storage figures

(51.2 B records, 122.4 B blocks, 42.2 B/event, 4.7 TB core, 27.1 G records) come

from the hydrant-715 compacted sizing, not from these samples, and were not

independently re-verified here — except 122.4 B blocks, which the layout A/B

reproduces. Caveats worth repeating: the top 10 deleting DIDs are 56.5 % of

deletes, so the age-at-death shape is bulk-purge dominated; repo purges are absent

from all of it; the layout corpus is 8/12 independent hosts and 60 % likes; and it

holds one version per record, so it cannot measure multi-version adjacency.