Four integers, and a lot of wrong assumptions

Sign in<br>Subscribe

I've been thinking about what the bottom of a database should look like if we stop asking it to understand the database.<br>That sounds a bit backwards, so let me be more specific. Most databases make an early decision about the shape of the world. Rows belong to tables. Documents have fields. Graphs have vertices and edges. RDF stores have subjects, predicates, objects, and graphs. Those decisions are useful, but they also pull indexing, query planning, and data modelling into the storage layer before the storage layer has had a chance to become very good at its one job.<br>I wanted to try the opposite. Store a fact as four opaque 64-bit integers. In Rust, the entire model is pub struct Quad(pub [u64; 4]);.<br>That's it. The engine doesn't know whether the first lane is a subject, a timestamp, a tenant, or the number of sandwiches ordered at lunch. It doesn't choose an index. It doesn't even insist that every user project the same meaning onto the four lanes. It stores the canonical facts, returns stable identifiers for them, and lets projections live above it.<br>Once the problem is reduced to that, it sounds almost embarrassingly easy. Four integers are 32 bytes. NVMe drives are fast. Memory is plentiful. Append the bytes and go home early.<br>Naturally, none of that survived contact with the benchmark.<br>What are we actually building?<br>The project is called quad-arena, and I think arena is the important word. A fact is written once into a canonical, append-only store. Callers receive a FactId, and that ID remains stable even if the physical representation changes later.<br>The current ID divides a u64 into a logical chunk and a slot:<br>Notice what isn't in there: a file offset. Putting an offset in the ID would be wonderfully simple right up until compaction, cleaning, or a new physical layout moved the data. A stable logical address gives the storage engine somewhere to evolve.<br>The other important choice is that the lanes are encoded independently. One lane might be constant across an entire chunk. Another might contain small deltas around a common base. A third might be completely random. Treating the quad as one 32-byte blob would force all four lanes to accept the worst lane's encoding.<br>So each lane chooses one of three representations:<br>Constant , when every value is the same. There is no payload to read.<br>Frame-of-reference bit packing , when values fit into small deltas from a base value.<br>Raw , when compression would only make the CPU feel industrious.<br>The file itself is deliberately boring:<br>Every commit is one checksummed frame. Recovery walks complete frames and ignores a torn tail. Inserted chunks are immutable, while deletion is represented as a logical retirement at an epoch. A snapshot can therefore still see a fact that was valid when the snapshot began, even if a later commit retired it.<br>This is not a query engine. It is the thing a query engine, graph projection, secondary index, or application-specific view can build on. Keeping that boundary firm made the rest of the experiment much easier to reason about.<br>The benchmark gets a vote<br>Storage code has a special talent for making plausible ideas look correct. A tight loop over a warm file can prove almost anything if you choose the loop after writing the code.<br>So before spending too much time making one path fast, I built a harness that could be disagreeable in several different ways. It measures structured and high-entropy ingestion, batch sizes from 64 to 65,536 facts, buffered and durable commits, point and batch gathers, individual lane masks, ordered and random IDs, hot and cold caches, retirements, recovery, and reader concurrency from one to eight threads. It also sweeps chunk sizes from 256 to 65,536 rows.<br>Then there is a separate Linux I/O harness. It compares blocking O_DIRECT reads with plain io_uring and with registered files and fixed buffers, across queue depths and I/O sizes. If a fashionable API was going to win, it would have to do so on the machine rather than in the design document.<br>The main storage results came from a Ryzen 7 7800X3D with 32 GiB of memory and a Samsung 980 PRO NVMe drive on Linux 7.0. The CPU and memory experiments also use tmpfs to remove the device from the picture. This distinction matters because a storage engine can be CPU-bound, memory-bound, syscall-bound, flush-bound, or device-bound, sometimes in the same request.<br>The first useful implementation was not terrible:<br>Those improvements did not come from one exotic data structure. Most came from discovering where the machine was doing work that the storage contract never asked it to do.<br>First, stop asking the disk three times<br>The early gather path could issue a separate read for each requested lane payload. Ask for three adjacent lanes and the engine would politely make three system calls.<br>That is logically tidy and physically silly.<br>The chunk directory already knows where every lane begins and ends, so...