Implementation notes

What implementing the design in kladde-rs has shown: where kladde-rs falls short of these documents, and what it chose where they leave a question open.

This page is where kladde-rs’s findings are recorded as they come up, and proposed for the other documents from here. Paths like spec/journal.md are relative to content/, the root of these documents. Branches of kladde-rs that hold earlier designs, such as address-table, keep their own implementation-notes.md.

Where the implementation falls short

What the code does not do yet, or does less well than kladde-docs or its own goals ask, and what that costs.

• ⚠️ The span table has two levels only: the header, and the leaves it names. A leaf that names table pages of its own is refused at open. The header’s room for references to leaves, one or two bytes each, bounds a file to some 2,000 to 4,000 leaves, one to two million spans: a sequence of a few hundred MB in spans of the length the measurements find, and far more than any workload measured, the largest of which takes 21 to 26 leaves. Beyond the bound, a flush fails with Error::OutOfBounds, and since opening flushes the replayed journal, a file whose journal holds such a flush no longer opens. No workload measured comes near the bound: the world map’s sequence of 942 KiB takes 21 to 26 leaves. The fix: write interior table pages when the leaves’ references outgrow the header, with the path copy of impl/consolidation.md#unlinking-an-emptied-page, and read them at open, which load.rs refuses today; test it with the header’s capacity settable from tests.
• ⚠️ A single write or splice of 4 GiB or more corrupts the journal: Records::stash keeps a record’s length as a u32, so the record states a truncated length while the store counts all of it, and one of exactly 2^32 bytes even encodes the escape. spec/journal.md#framing bounds a transaction’s length by 2^32 − 1, so such a write must fail with Error::OutOfBounds; only the bound of 2^48 is checked today. No application writes values of 4 GiB in one piece, but the result is a file that does not open, not an error.
• Arithmetic on values read from the file is not checked: the entry decode adds deltas to page numbers, ids and ends, and the journal decode adds a move’s to_delta, without checking for overflow, so a file whose CRCs match but whose numbers do not panics in a debug build and wraps in a release build, which can accept entries out of order that the delta encoding is meant to make unrepresentable. kladde-cpp checks each of them.
• FileStorage takes no lock, where spec/file-format.md#concurrency has a second process refused cleanly, and create truncates whatever file is there; kladde-cpp locks with flock before it truncates.
• A CutId that escapes a transaction rolled back by Store::atomically can match a later record that reuses its index with a cut of the same length, and a paste of it then pastes that record’s bytes without an error. The typed layer never lets a cut out of a failed transaction, which poisons the store; only direct users of Store can meet it.
• The cut never gives fillers to the header: impl/flush.md#the-cut has the last leaf take them, or the header when there is no leaf, and kladde-rs fills the last leaf only.
• The budget loop filters offers by their floors before it picks the best ratio, where the pseudocode of impl/consolidation.md#the-budget-loop picks first and stops if the pick fails its floor; a table offer can then win when the data offer fails the fill floor.
• The fold’s output is not checked against the tracked length, which impl/write-phase-state.md asks for as a cheap guard against a fold bug.
• The decode recurses without a limit on its depth, where impl/opening.md asks for a limit or an iterative decode, so a file that nests deeply enough overflows the stack.
• A container’s index panics on sizes of 4 GiB or more, where spec/span-table.md#bounds asks every limit to fail cleanly: the Fenwick tree keeps sizes in u32 cells, and converts with expect.
• The load checks a reached Ref against its page’s frame, not against the page’s content_size. It refuses a Ref into page 0 or 1, into a page that is not a Data page of the header’s world, or reaching into the framing, but not one that reaches past the content into the padding.
• Nothing is kept in the private chain, where impl/consolidator-state.md designs what consolidation would carry there: every session starts its budget from Options::budget_pages, its rotating walk at the sequence’s start rather than where impl/opening.md seeds it, and each span’s heat from the epoch of the page that holds its entry.
• A span costs about 90 bytes in memory, not 32. The span table takes 48 bytes per span, since each record also holds the span’s chain, its rope node, its heat, its entry’s size and place in its table page, and its place in its data page’s reverse list, which impl/in-memory-state.md keeps beside the span table; and the rope is an implicit treap of 40 bytes per node rather than a counted B-tree of about 15 per span.
• DurableVec’s index takes 40 bytes even where it is empty or the elements are fixed-size: a Vec of cells, its cached total, and the count’s varint length. The total can live in the tree’s allocation, and the count’s length is the vector’s to pass in, which would leave 24 bytes, or 8 with a thin vector.
• None of the three refinements of impl/consolidation.md is implemented: evacuation writes a victim’s spans as they are, splitting the one that crosses the end of the page it fills, and merges no neighbours; the walk merges runs of cold spans and renumbers nothing; and the churn floor, budget controller and free filling are the address-table design’s, unchanged, over pages of spans.
• Compaction mode counts holes by scanning the page table once per flush. impl/consolidation.md#compaction-mode promises O(1) amortised; kladde-rs keeps the cached index of the highest live page it describes, but counts the reusable pages below it in O(pages) at the start of every flush, which is small next to what a flush writes.
• The budget loop never continues the last page of pack. impl/consolidation.md#the-budget-loop lets that page cut a victim’s span whenever the loop opens another page, so that only the flush’s very last data page can close short; kladde-rs’s loop always opens fresh pages, so pack’s last page is filled by free filling alone, and can close short even when the loop goes on.
• What rust/tutorial/durability.md says about close() was measured on the address-table design, and has not been checked since: that close truncates after the last live page only, so that a freshly created file keeps free pages below its data until a flush or two have consolidated them.
• The header’s eviction ranks by heat alone, rather than evicting the coldest runs contiguous in id, and merges each evicted span with its neighbours in the sequence, extending each run while a neighbour whose entry also goes to a leaf makes a pair shorter than the bound.
• A value is encoded into a buffer of its own, which the store copies into the record, a copy that a store method taking an encoding closure would save.
• Cuts exist on DurableVec only: its cut, insert_cut and push_cut; impl/values.md#moving-a-value-between-containers has every method that takes a value take a cut too, but a plain Vec, the map, fields, Option and enums neither make nor take them.
• split_at_mut and the count of changes are not implemented, only parts(), for derived structs and enums and for tuples. split_at_mut was left out only because the evaluation needs it nowhere; the vector’s Fenwick tree lies in cells and answers any element’s offset, so it would serve as the two runs’ index as it is.
• parts() on a temporary Mut works in a match but not in a let … else, which drops the temporary at the end of the statement. A consuming into_parts(self) would make the let form work too; it would need a line in rust/derive-macro.md and rust/tutorial/deriving.md, and is proposed rather than built.
• MemoryStorage models a power cut as any subset of the writes since the last sync, each write whole. It does not model a write torn within a page; the page CRCs are meant to catch those, but no test exercises them yet.
• Misusing the transaction and batch calls reports Error::Corrupt. Ending a transaction that is not open is a caller’s bug rather than a damaged file, and deserves an error variant of its own; the typed layers pair the calls through Transaction, Batch and Region::transaction, so only direct users of Store can hit it.

Choices kladde-docs leaves open

Where kladde-docs leaves a question open, or allows any answer, and what the implementation chose.

• The journal is replayed by folding the recovered transactions in a flush at open, before the decode, so that the decode reads the state after the last of them and needs no replay of its own; impl/opening.md#replaying-through-a-flush allows it.
• The rope is an implicit treap, one arena type of under 400 lines that also serves the fold’s piece table and the journal’s cuts, since a split at a position and a join of two trees are all three need.
• The span id allocator hands out the id after the predecessor’s, if it is free, and the lowest free id otherwise, which keeps the spans a flush makes one after another consecutive without looking for a run.
• The flush makes a run of 32 zeros or more among new bytes a Zero span.
• The span policy’s constants, chosen by the measurements of evaluation/one-sequence.md: Options::span_min, the bound L, 64 bytes; Options::rewrite_below, 64 bytes; Options::inline_threshold, 64 bytes; Options::cold_flushes, 16; Options::walk, 256 spans; and Options::mu, 0.02.
• A Box<T>’s FIXED_SIZE is None whatever T’s, since a type that holds itself through a box would otherwise ask its own size of itself while rustc evaluates it, which rustc refuses as a cycle (E0391); a vector of boxes then keeps an index it could do without.
• The Mut of a Fixed<T> replaces the value whole, since a Mut of one of T’s fields would have to write that field in its fixed form, which would take a second Mut for every type.
• The map’s hash table is its own: open addressing over 32-bit positions, probed linearly and at most half full.
• FileStorage grows the file with set_len, not with fallocate. The new region stays unallocated until it is written, so a full disk shows up as a failed write or fsync during a flush, which poisons the store, rather than as a failed growth before the flush starts; spec/durability.md#headroom asks only that failure be clean, which poisoning provides.
• The controller moves the budget multiplicatively, and measures fill against the whole file: after each commit it divides the live bytes by the capacity of every page but the headers, and multiplies the budget by exp(4 · (τ − fill)), within budget_min and budget_max. Counting only live pages would let holes go unnoticed.
• A page’s record holds what its state has, and nothing else: an enum over the page states, with a state of its own, filling, for pages a flush takes, and journal pages apart from live ones; only a live page has an epoch and a victim bucket.
• The churn floor also bounds each victim, and an offer takes whole victims by score, not by best fit.
• Free filling moves part of at most one victim per page, and the victim stays eligible. impl/consolidation.md#packing-in-sequence-order-with-look-ahead lists part of a victim too big to take whole as the last filler without saying how many victims to try; one per page is enough, and excluding a victim after a partial move would starve the budget loop of exactly the sparse pages it wants.
• Kladde::create_in and Kladde::open_in take any Storage and Options; Kladde::create and Kladde::open use a file and the default options, and Kladde::new is create_in with a MemoryStorage, which returns no Result, since a file in memory cannot fail to be created.