Layered stores

Implementation note (non-normative). An implementation of this draft lives in src/internal/multi.ts (multiStore), with a key-namespacing helper in src/internal/prefixed.ts (prefixedStore). Its authoritative layer flag declares authority over every key space at once — a conforming specialization of §18.5's per-space declaration — and it drains automatically by default (§18.4).

#18.1 Model

A layered store presents one §10 key–value store composed of an ordered sequence of layers, each itself a §10 store. Layer 0 is the top.

• Reads consult layers top-down and stop at the first hit.
• Writes land eagerly in the layers above a designated durable layer, and are queued for the durable layer in an ordered write-back log, drained by a flush — invoked explicitly or initiated automatically as local policy (§18.4).
• A layer MAY be declared read-only: it receives neither writes nor cache fills.
• The durable layer is the deepest writable layer. Layers below it are read-only fallbacks. If no writable layer exists below the top, the top layer is durable and there is no log.

The arrangement is local policy. It is invisible in the stored bytes, it changes no key, and the §10 layout — meta:format, blocks: and refs: — is unchanged regardless of how many layers those keys are striped across.

Two motivations drive the design, and they pull in different directions. Caching wants reads served from the nearest layer. Write-back wants writes acknowledged before they are durable. §18.2–§18.4 are the rules that make the combination safe.

#18.2 The pending-write overlay

The write-back log MUST be part of the read path, not only of the drain. A read MUST consult, in order: the eager layers top-down, then the log, then the remaining layers. In the log, a pending tombstone is a definitive absence and a pending value is authoritative.

Precisely: the log joins the read order at the first layer that does not receive eager writes — the first read-only layer above the durable one, if any — not at the durable layer itself. A read-only layer's copy of a key can be arbitrarily stale, and it never receives the write the log holds pending. Consulted ahead of the log, it would shadow a pending value or tombstone.

This applies to every read operation the store exposes — single reads, existence checks, batched reads and batched existence checks, and enumeration. The batched forms are the easy omission and the costly one: a mark–sweep collector (§15.2) typically loads its frontier in batches, and proves its raw leaves present in batches too, so a batched read or probe that bypasses the overlay walks past a tombstone and marks a block the caller deleted.

Without the overlay, two failures follow directly:

• A delete applies to the eager layers and queues a tombstone; a read then misses those layers and falls through to the durable layer, which still holds the value. The key resurrects — a deleted ref reappears as a collector root, a swept block reads as present.
• A bounded eager layer (§18.6) may evict an entry whose value exists nowhere below it.

Note that the rule is stated in terms of write eagerness, not durability. This inverts the naive intuition: under write-through, the mutable refs: space would be most correctly read from the durable layer; under write-back it MUST be read from the top. The formulation above is the one that is correct under both.

#18.3 Residency of the mutable key space

The refs: and meta: key spaces MUST be fully resident in the top layer, populated before the store serves any request.

Refs are the store's only mutable pointers, and every mutation writes one. If ref writes were write-through, every mutation would block on the durable layer. So refs must be write-back, and by §18.2 must therefore be read from the top. A top layer that is only a bounded cache may evict a ref, after which the read falls through to a stale durable copy and the store silently rolls back to an earlier root.

The severe failure is in collection, not in reading. A mark–sweep collector takes its roots by enumerating refs:. An enumeration that misses one layer's refs makes the collector sweep blocks that are live under a root it never saw — unrecoverable data loss, with no error at the time. Block enumeration has the opposite, safe failure mode: an incomplete keys("blocks:") under-collects. Therefore:

• Every read of a resident space — lookup, existence check and enumeration alike — MUST be served by one authority: the top layer plus the log, never by a descent or a best-effort union across layers. A split regime (lookups by descent, enumeration top-only) lets get and keys disagree the moment a mutation partially fails in a lower eager layer. That is exactly the divergence §18.2 exists to prevent. No descent is ever needed: residency puts every live resident key in the top layer.
• An enumeration whose range spans resident and non-resident spaces MUST apply the same rule to its resident portion: resident keys contributed by any layer below the top are excluded from the union.
• The top layer MUST be writable — residency fills and every resident mutation land in it. An implementation MUST refuse an arrangement whose top layer is read-only.
• Every layer below the top MUST support enumeration, or residency cannot be established; an implementation MUST refuse such an arrangement rather than operate on a partial root set.
• Until residency is established, the store MUST refuse reads and writes in the resident key spaces rather than answer from an empty top layer.

That last requirement is easy to under-state. Answering "absent" from an unpopulated top layer is not a stale read — it is an empty root set handed to a collector.

#18.4 Ordered drain

The drain MUST be prefix-ordered. Entries are made durable in the order they were queued, so that any partial or interrupted flush leaves a prefix of the write history.

This is sufficient because of a property of the core format: a root is written only after every block in its closure, so every prefix of a valid write history is itself a valid store state. An interrupted flush rolls the durable store back to an earlier consistent root. It never rolls it forward to a root whose blocks are absent. An unordered dirty-set drain has no such property and can produce a durable store no later run can repair.

When a drain runs is local policy: an implementation MAY initiate one automatically — in the background after a write, on a schedule, past a queue-size threshold. Every drain, however initiated, MUST follow this section's rules. Concurrent drains MUST be serialized: two interleaved drains issue log entries out of order against the same durable layer and forfeit the prefix property (§18.7 takes issue order to be landing order). Automatic draining narrows the window of unflushed data but does not replace the explicitly invoked flush, which remains the only durability barrier a caller can await — before collection (§18.9), at shutdown.

#18.4.1 Deduplication

An implementation MAY collapse repeated writes to one key, subject to:

• Identical value: keep the earliest position, drop the later append.
• Changed value: take the latest position.
• Deduplication MUST NOT reach entries a drain has already claimed.

The first rule is the counter-intuitive one, and the obvious alternative is wrong. "Keep the last value at its last position" is unsound:

1. set blocks:B = v      # v is B's content
2. set refs:R   = X      # closure(X) includes B
3. set blocks:B = v      # byte-identical re-store

That rule drains [refs:R, blocks:B], so an interruption after one write leaves a durable root pointing at an absent block. Byte-identity makes collapsing a no-op for the value. The rule moves the position. Under content addressing this is the common case, not a corner: it fires whenever new content shares blocks with already-queued content.

#18.4.2 Ordering of eager writes against the log

The overlay sits below the eager layers in the read order, so it can supply what they lack but cannot mask what they hold. Additive and subtractive mutations therefore take opposite orderings, and treating them as symmetric is a defect:

• An additive write (set) MAY append to the log before applying to the eager layers. If an eager write fails, the value is still readable through the overlay, which is a consistent state.
• A subtractive write (delete) MUST apply to every eager layer first and append its tombstone only if all of them succeed. A failed eager delete otherwise leaves a contradicting value above the overlay, which nothing below can mask: reads answer "present" for a tombstoned key while enumeration answers "absent", and after the drain the durable layer is empty while an eager layer serves the value indefinitely.

Applying only to the top layer first is not sufficient; with three or more eager layers the same defect reappears one layer down.

The subtractive ordering inverts in a resident space (§18.3), because the failure mode it guards against cannot occur there: resident reads never consult the lower eager layers, so a leftover copy in one of them masks nothing. A resident delete MUST queue its tombstone as soon as the delete has applied to the top layer, and only then clear the remaining eager copies. Holding the tombstone back until every eager layer succeeded (the non-resident rule) would let a single lower-layer failure leave the durable copy permanently undeleted, while every read and enumeration already answers absent. The result: a deleted ref that resurrects on the next open of the durable store.

A delete MUST queue a tombstone rather than apply to the durable layer directly, so that it takes its correct position in the drain order.

#18.5 Authoritative layers

A layer MAY be declared authoritative for a key space, meaning it holds every key in that space. Authority has three consequences:

• A miss in an authoritative layer is a definitive absence; layers below MUST NOT be consulted for that space.
• Enumeration of that space is served by the authoritative layer alone.
• A synchronous caller never falls through to an asynchronous layer, which is what allows a fully synchronous API over an asynchronous backing store.

Authority composes with the overlay rather than replacing it: an authoritative layer plus the log is the authority, and truncating the descent MUST NOT skip a pending tombstone or a pending value.

An authority declaration is a claim that can stop being true, and an implementation MUST treat it as revocable. If a write to an authoritative layer fails, that layer no longer holds every key, and a truncated descent will report a definitive absence over data that exists. On such a failure the implementation MUST withdraw the claim and widen the descent. Over an asynchronous backing store this means a later synchronous read may fail where it previously succeeded. That is the correct outcome: a loud failure is strictly better than a silent wrong absence.

A layer that evicts MUST NOT be declared authoritative. Eviction turns a fall-through into a wrong absence, and no runtime check can detect it, because a store cannot report what it has silently dropped.

A read-only layer above the durable one MUST NOT be authoritative, and an implementation MUST refuse such an arrangement at construction. The drain ships every write past that layer into the durable one, so from the first drained write onward its claim is false. The moment an upper layer misses, the claim hides the entire drained key space behind a definitive absence. (Below the durable layer the combination is sound: the descent reaches the durable layer's copy first.)

#18.6 Bounded layers

An eager layer that evicts MUST NOT evict:

• an entry whose value exists nowhere below it (a dirty entry), or
• any key in a resident space (§18.3).

Eviction is otherwise unconstrained. Note that these constraints and §18.5 together mean a bounded layer can serve as a cache but never as an authoritative layer.

#18.7 Requirements on the backing stores

A layered store depends on two properties of each backing store that a single-layer deployment never exercises:

• Deleting an absent key MUST be a no-op. A drain replays tombstones that may supersede writes the durable layer never received.
• Mutations to the same key MUST complete in the order they were issued. Operations on different keys MAY overlap and complete in any order, but two writes to one key MUST NOT be reordered against each other. The drain issues the log in order and takes the landing order to be the same; a reordering store defeats §18.4 at its root. A store that cannot promise this MUST be serialized per key before being layered.

#18.8 Capability negotiation

Layers may support different optional operations. A layered store MUST decide its own capability set at construction and expose it structurally. A capability it cannot serve MUST be absent, not present-and-failing. Callers of a §10 store commonly probe by presence to decide whether an operation is available at all. A method that exists but throws lets a caller begin work it cannot finish. A collector that has already marked before discovering it cannot sweep is the motivating case.

Deletion in particular MUST be exposed only if every layer that can hold a key supports it, and MUST apply to all of them. A surviving copy in a lower layer resurfaces on the next read.

#18.9 Interaction with collection, packs and synchronization

• Collection (§15.2). A collector requires exclusive write access, and over a layered store it MUST additionally see a drained log, so that tombstone and write interleavings stay out of mark–sweep reasoning. A collector SHOULD suppress cache fills for the duration of its run. Otherwise a dry run — which deletes nothing — faults the whole block space into the upper layers and never releases it.
• Packs (§12). Import and export are unaffected: both go through the same §10 operations and inherit the layering. An export walk of a large closure is the operation most likely to fill upper layers with data that will not be read again.
• Synchronization (§17). Unaffected, provided §18.2 holds — a sync session's presence checks are reads like any other, and a resurrected block causes a session to skip transferring content the durable store no longer has.

#18.10 Non-goals

• Cross-process coherence. An authoritative or resident layer asserts exclusive ownership of the key spaces it covers: no other writer may mutate them behind it. This is the same assumption collection already makes (§15.2). Nothing polls the backing layers, and a second process writing the same durable store is out of scope.
• Partial durability. There is no per-operation "write this through and leave the rest queued". A write's root closure references earlier still-pending blocks, so §18.4 makes write-then-drain-everything the only sound reading of a durability request. Data that should never reach durable storage belongs in a separate ref or a separate store, not in a layer-restricted write against a shared tree.