CUBELinux · The Addressed Store: Coordinates as Places

Abstract

The first whitepaper ended its benchmark section with a recommendation rather than a claim: the coordinate ordering is not the win by itself — pre-align the query. Snap a request outward to the covering aligned block, read one contiguous run, filter in memory.

This paper reports the store that does it. In format v3 the image carries its own addresses: a space table, a fixed-stride index, and values packed in index order. A coordinate is no longer only a way to name a record; it is a way to reach one — a lookup is a binary search over arithmetic addresses, a listing starts at its space's first index entry and streams, and a spatial region becomes a contiguous run of index entries. Work is proportional to what is asked for, not to what the store holds.

Everything below is measured on the workhorse — a Surface-class i5-1035G4, 7.5 GB, the live sealed store of 69,638 records — with the kernel's own gates, and compared claim by claim against the first paper.

1. Why the layout had to change

The packed format — space | key | value_len | value, repeated — cannot answer "where is this coordinate". Record N's offset is the sum of every value before it, so the key gives order and order is not an address. The consequence is not one slow path but all of them: no binary search is possible either, because the middle record's offset is equally unknowable, and every operation has to re-derive the whole store.

Measured on the live store before v3, through cube(2):

2. Format v3: the image carries the addresses

[header 46]                       magic, version, curve, extents, counts
[space table: space_count × 48]   space | first index | records
[index: record_count × 40]        key | value offset | value length
[values: packed, in index order]

The index is fixed-size and sorted by key, so a reader computes a record's place as index_off + i × INDEX_ENTRY. An index entry is 40 bytes against the packed frame's 64, so the addressed image is also smaller: the live store went from 18,835,712 to 17,164,952 bytes, with every record and every value identical (same fnv1a64 digest before and after the fold that converted it).

And the format is described once. The kernel's Rust build compiles what is in its own module tree and a cargo crate is not that, so the two sides share a file: drivers/cube/cube_format.rs, declared by the driver and included by userspace. The kernel's constants are aliases of it and the functions that validate a header delegate to it. Two descriptions of one format is what shipped an hour of unsupported-version; there is no longer a copy to drift from.

3. Cost, measured by growing the store

One gate asks the same four questions of a 500-record store and a 20,000-record one, inside the guest, and compares:

On the live store, same box, before and after the fold that converted it: spaces 79 ms → 9 ms, and listing a 6,127-record space 69 ms → 24 ms. The §2.3 recommendation is now a property of the bytes.

Those two were taken by hand on the box, and they are the kind of number that should not be quoted without saying so: they have no gate behind them, so they cannot be re-run or contradicted by a machine. The reproducible version of the same claim is kernel/verify-enum-cost.sh, which builds two stores that differ by 40× and asks both the same questions inside the guest — a listing costs what it returns, not what the store holds. Quote that one.

4. The first whitepaper's claims, re-run on this build

The micro-benchmarks are not reproduced because the contract changed, and the change is the point. Those numbers came from an in-process store that skipped disk, durability and concurrency, in a daemon that no longer holds the store. Today the store lives in the kernel and every operation is a cube(2) round trip, measured in the guest by kernel/verify-enum-cost.sh — and the numbers moved as the layout did. When this page was written the gate measured the packed path: listing the same ten records in a 500-record store and a 20,000-record one cost 5.46 ms and 6.24 ms, reading a coordinate that is there 2.45 ms and 2.17 ms, one that is not there 2.39 ms and 1.76 ms. Re-run against build #79, whose fold writes the addressed v4 image this page is about, the same gate reports a coordinate read at 0.12 ms and 0.11 ms — flat across a store forty times larger, and the address is why: a lookup is a binary search over a fixed-stride index rather than a walk. That is the honest comparison — a syscall and a durability boundary on one side, a memory-resident hash on the other — and what remains is not the average but the bound: the figure is a mean of twenty calls in a store that was just folded, so it does not include a day's unfolded log, and the gate's ceiling on a read is 250 ms. A control loop is what makes those two sentences matter.

5. What verification found

Three defects that only real work surfaced, each now covered by a gate:

• The walk stopped at its first batch. A batch is full only when a record lands on the boundary, so a short batch means nothing — reading it as "the space is exhausted" truncated a 3,006-record listing to 747. The end of a walk is the cursor alone.
• An index entry written four bytes short. The value length was written as four bytes while the header's arithmetic and both readers assumed eight, so the last entries overlapped the values. A hand-built unit test could not see it — it built its index with the same mistake. The guard is a kernel-written image committed as a fixture.
• A store could be folded exactly once. The first fold reads packed and writes addressed; every fold after that reads addressed — and the reader only knew packed. Found on the live store minutes after it was folded for the first time, where the second checkpoint answered -EINVAL. No gate folded twice; one does now: "a store can be folded once and then never again, which is not a layout."

6. Where this leaves CUBELinux

Coordinates address bytes, the store's layout now says where, and the kernel holds it. Verified on hardware: the live sealed store walks identically through cube(2) and through userspace reading the same bytes, record for record, 69,638 of them; the fold that converted it preserved every value; and the encryption is untouched by any of it — the store is sealed at rest, and the walk returns envelopes, not plaintext.

What is next: keeping the store open in the kernel between calls (the remaining milliseconds), a persisted sparse directory so a probe reads a page rather than an index run, and the same addressing extended to the regions the first paper's §2.3 benchmarked.