Four integers, and a lot of wrong assumptions
I've been thinking about what the bottom of a database should look like if we stop asking it to understand the database.
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.
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]);.
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.
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.
Naturally, none of that survived contact with the benchmark.
What are we actually building?
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.
The current ID divides a u64 into a logical chunk and a slot:
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.
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.
So each lane chooses one of three representations:
- Constant, when every value is the same. There is no payload to read.
- Frame-of-reference bit packing, when values fit into small deltas from a base value.
- Raw, when compression would only make the CPU feel industrious.
The file itself is deliberately boring:
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.
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.
The benchmark gets a vote
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.
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.
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.
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.
The first useful implementation was not terrible:
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.
First, stop asking the disk three times
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.
That is logically tidy and physically silly.
The chunk directory already knows where every lane begins and ends, so adjacent payloads can be coalesced into one read. The engine reads the containing range once and slices the requested lanes out of it. An all-lane point lookup went from three physical reads to one. Constant lanes still require no payload at all.
Batching matters even more. A gather request arrives as a list of stable IDs in whatever order the caller has. The engine groups those requests by logical chunk, reads each requested lane once for that chunk, decodes all required slots, and scatters the answers back into caller order.
The initial organizer used a BTreeMap, which was convenient and allocation-happy. Replacing it with a sortable vector removed per-chunk allocation, and a monotonic fast path skips sorting entirely for ascending or descending scans. This is one of those changes that sounds too ordinary for a database article, but ordinary work is still work when it happens millions of times per second.
On top of that sits a bounded, sharded cache of compressed lane payloads. It stores the bytes the decoder needs rather than expanded quads, so a hot lane does not drag three unwanted lanes into memory. Sixteen shards keep unrelated readers from fighting over a single lock, and numeric chunk keys use an identity hasher because these IDs do not need protection from an adversarial string hash table.
The result is 154 million IDs per second for an ordered 4,096-ID all-lane gather on the NVMe-backed file, and 166 million when cached. Eight threads doing cached random gathers reach 229 million IDs per second. At that point the interesting bottleneck is no longer the drive. It is the amount of grouping, decoding, scattering, and cache traffic we create in memory.
There is also a useful degenerate case: a lane mask with no lanes. That request asks only whether each fact exists at the chosen snapshot. It should not perform compression work or I/O, so the existence path walks IDs directly against chunk and retirement metadata, using a small temporary bitset only to count the chunks it touched. Random existence batches of 4,096 reach 543 million checks per second. Sometimes the fastest decoder is the one you never call.
The checksum was eating the database
Every commit frame has a CRC32C checksum. That gives recovery a clean rule: a complete, valid frame is publishable; a partial or corrupt tail is not. It is a small piece of the format with a fairly large appetite for CPU.
The first checksum implementation processed bytes in software. Replacing it with a slicing-by-eight implementation helped. Detecting SSE4.2 at runtime and using the CPU's CRC instructions helped much more, especially for entropy-heavy data where compression could not shrink the frame before the checksum saw it. The portable path remains format-compatible, so files do not become tied to one processor.
Frame construction had its own tax. Building several temporary buffers and joining them later means allocating, copying, and walking the same bytes repeatedly. The commit path now computes the layout up front and builds the complete frame in one preallocated Vec<u8>, with reusable scratch space for encoding.
The API matters here too. If a caller already owns a Vec<Quad>, accepting a slice requires the engine to allocate and copy the entire batch before it can take over the data. append_owned transfers the vector instead. On the standard tmpfs profile, a 65,536-fact structured insert moved from 51.7 million to 119.9 million facts per second; entropy-heavy insertion moved from 34.3 million to 95.1 million.
Then there was an extra ftruncate after each positional write. A successful pwrite past the old end of file has already extended the file, so the truncate was not making the commit safer. It was just another metadata operation. Removing it roughly doubled small structured ingest in the isolated CPU profile.
None of these changes altered the storage model. They only stopped charging for copies, checksums, and syscalls that did not buy a stronger guarantee.
The six millisecond wall
Buffered writes are entertainingly fast because they are not yet a promise about power loss. Durability begins when the engine asks the device to flush its volatile state.
On this machine an immediate durable commit takes about six milliseconds. Add more writers and the drive does not suddenly learn to flush sixty-four independent histories at once. Throughput remains around 165 durable commits per second, while queued callers develop spectacular tail latency.
The usual answer is group commit: let several writers share one flush. The difficult part is making sure “group” does not quietly weaken “commit.”
quad-arena assigns commits monotonically increasing epochs. Writers serialize while appending their frames, but a group-commit writer releases that lock before waiting for durability. One waiter becomes the leader, waits for the configured grouping window, takes the writer lock long enough to capture the current epoch, calls sync_data, advances a durable watermark, and wakes every waiter covered by that epoch.
A successful call still means that caller's frame is durable. The batching happens inside the acknowledgement path, not by redefining success.
With 64 writers committing 64 facts each, the difference is fairly dramatic:
The one-millisecond window adds roughly one millisecond to the median, but under load it turns a flush into an efficient bus rather than sixty-four private taxis. A zero-delay policy does not reliably form a group, so the window is deliberately explicit instead of pretending there is one universal setting.
There is a subtle visibility point as well. A group member's frame has been appended before its caller receives the durable acknowledgement, so in-process readers may observe it while that caller is still waiting. No successful commit returns early, but visibility and acknowledgement are not the same instant. If a higher layer requires those moments to coincide, it has to publish at the durable watermark rather than the append watermark.
Surely io_uring wins?
Modern NVMe drives support deep queues. Linux has io_uring. Therefore a modern storage engine should use io_uring, preferably before it has a file format.
It is a very appealing syllogism.
I tested aligned direct reads through blocking worker threads, an ordinary ring, and a ring with the file and buffers registered. A single 4 KiB random read had comparable latency, with the fixed-buffer ring slightly ahead. At high random concurrency, though, blocking calls distributed across threads won decisively on this Btrfs and NVMe stack:
The ring does win some large sequential cases at high queue depth, and it remains attractive when several operations can be composed without bouncing through dedicated threads. It just did not earn the default gather path here.
This is why the planned cold-data backend is a bounded pool of blocking I/O workers first, with io_uring retained as an optional backend. The API is an implementation choice, not a personality test. We can change it when the workload, filesystem, or kernel produces different evidence.
One chunk size to rule none of them
A logical chunk is a useful unit. It gives IDs stable slots, amortizes metadata, creates compression opportunities, and lets a gather decode many nearby facts together. It is tempting to make it the physical read unit too.
The chunk-size sweep is where that temptation became expensive.
At 256 rows, point reads have low amplification, and the structured test data occupies about 3.06 bytes per fact. A 4,096-row chunk is the most balanced current default and gives the fastest ordered 4,096-fact gather. At 65,536 rows, a large random batch touches fewer chunks, but a single point lookup can pull roughly 109 KiB of compressed payload.
There is no winning size because “chunk” is doing two jobs:
- It is the stable logical namespace addressed by a
FactId. - It is the physical compression and I/O granularity.
Those jobs want different things. Logical chunks should be large enough to keep IDs and metadata efficient. Physical blocks should be small enough to avoid reading a small novel for one integer.
The next format should split each logical chunk into independently compressed microblocks. Page-cache-backed files can keep compact variable-length blocks. A cold-data backend can optionally group or pad them to 4 KiB boundaries for direct I/O. The stable ID does not change; only the directory learns one more level of indirection.
That extra lookup is not free, but it lets point reads and large gathers stop negotiating over one global constant.
A hundred million small cuts
Once the large mistakes were gone, the profile turned into a tour of the memory hierarchy.
Bit-packed lanes originally decoded values through a small loop with more state movement than necessary. A 64-bit reservoir now pulls bits in bulk, and ordered scans use ascending and descending paths that avoid general scatter machinery where possible. Scan throughput roughly doubled.
Retirements began as a sorted sparse vector, which is excellent when only a few facts in a chunk are retired and increasingly awkward when many are. The current representation switches to a dense epoch array after one eighth of a chunk is retired. The threshold is not philosophically important; adapting to density is. Buffered retirement of 4,096 IDs now reaches 94.1 million facts per second on the NVMe-backed run.
Request grouping, scratch allocation, hashing, bit extraction, and branch shape all made measurable differences. None would rescue a bad physical layout or a flush per tiny commit. Together, after the larger design was sound, they decided whether the engine processed tens or hundreds of millions of facts per second.
This is the part of storage engineering I find most useful: the hierarchy of problems. First remove the I/O you did not need. Then remove the copying you did not need. Then make the unavoidable CPU work friendly to caches and registers. Reversing that order produces exquisitely optimized waste.
Where it landed
Here is the current representative NVMe-backed result set:
The numbers are satisfying, but the more important result is the shape of the engine that produced them. It is append-only and checksummed. IDs name logical facts instead of offsets. Compression is per lane. Reads are batch-oriented and lane-selective. Durability policy is explicit. Hot payloads are bounded and sharded in memory. The cold I/O API remains replaceable. Retirements preserve snapshot history.
And projections are still somebody else's problem, intentionally. A durable commit stream can feed any number of indexes or application-specific views without teaching the canonical store what its four integers mean. Users get to decide which projections deserve space, write amplification, and maintenance cost.
There is plenty left to build. Microblocks should separate logical identity from physical read size. A checkpointed chunk directory should make recovery proportional to recent work rather than the full log. Live bitmaps need to become persistent inputs to a cleaner that can relocate physical data without changing FactIds. Observed lane masks and gather sizes may eventually justify choosing among structures of arrays, arrays of structures, and hybrid layouts per microblock.
That sounds like a database roadmap, which is slightly alarming for something that began as four integers and an append call.
The honest part
These are local engineering results, not universal performance claims. The quick datasets often fit in memory or the page cache, and the direct-I/O comparison used a 512 MiB file on one Samsung 980 PRO, one Btrfs stack, and one Linux kernel. Different drives, filesystems, queue topologies, power-loss behavior, or workloads may reverse specific conclusions...especially the io_uring result. The durability tests exercise torn tails and sync_data, but they are not a substitute for hardware fault injection across the entire storage path.
The engine is also deliberately incomplete: it has one logical writer, no cleaner, no physical space reclamation, no checkpointed directory, and no built-in projection, index, or query planner. Group commit buys acknowledgement throughput by spending a small amount of latency, recovery is still log-proportional, and the cache may duplicate data already held by the operating system. So this is not yet a production database. It is a storage kernel with measured reasons for its current choices...and, perhaps more importantly, clear evidence about which choices need to change next.