Varaq 0.1.0 · Announcement ·

Introducing Varaq: a fast embedded B+tree in Rust

Releasing Varaq 0.1.0, a fast, embedded, ACID, key-value store in Rust.

Contents 9 sections
  1. Two kinds of waiting
  2. Shared writes
  3. Varaq
  4. The B+tree
  5. Transactions
  6. Measurements
  7. Comparison
  8. What's next
  9. Sources

How close can one storage engine get to memory speed while the data fits in memory, and to the device's speed once it doesn't, on every core of the machine? Put as a target: a page of data should cost what a lookup costs while it is in memory, one read from the device when it isn't, and nothing more.

B-trees are the standard index of relational databases and the core of many key-value stores. They were designed for spinning disks, and most B-tree engines still manage their pages the way they did then, with bookkeeping on every page access that was invisible next to a millisecond seek. SSDs are now fast and cheap, machines have dozens of cores, and that bookkeeping is no longer invisible.

Since 2018, research on the LeanStore engine at the Technical University of Munich has worked on that problem. Its first paper reports an engine with "little overhead in comparison with a pure in-memory system when all data resides in main memory" that, "like a traditional buffer manager", can "manage very large data sets effectively"1. That work shaped how I think about the problem. Over the past months I built Varaq, a new embedded, transactional key-value store in Rust, on the principles that research established, and today I'm releasing version 0.1.0.

Two kinds of waiting

A storage engine keeps more data than fits in memory. The data lives on a device, cut into fixed-size blocks called pages, and the engine keeps the pages in use in memory. So every access to a page pays for up to two things:

  1. waiting for the device, if the page isn't in memory;
  2. the engine's own work around the page, whether it is in memory or not: finding it, making sure no one changes it underfoot, and keeping track of what to throw out when memory fills.

For decades only the first one mattered. To see how the two compare today, I measured both on the machine every measurement in this post comes from, a Linux VM with 4 vCPUs. One lookup through a B+tree of 4 KiB pages, with every page already in memory, takes 1.04 µs on one thread2. One 4 KiB random read from the VM's disk takes 25.0 µs3, the time of 24 lookups. A 7,200 rpm hard disk waits on average 4.17 ms just for the platter to turn under the head, before any seek4: the time of 4,018 lookups.

Figure 1 sends one request from a core to each device and piles up, beside the core, the lookups it could have finished while it waited. Drag the scene to turn it.

Figure 1What a page costs
Interactive: plays on its own · pick a device or scrub · drag to turn the view a littleOpen standalone

Next to a hard disk, the engine's own work is a rounding error: shave a microsecond off it and the total barely moves. Next to flash, it isn't. (The VM's disk is a virtual device, not the dedicated NVMe drive the design targets, and a single read at a time is the slowest way to use an SSD.)

The pressure is even sharper when you look at throughput. Haas and Leis measured modern NVMe drives at about 1.5 million random 4 KiB reads a second each, and eight of them together at 12.5 million; on a server with 64 cores and those eight drives, their engine reached 12.5 million lookups a second5. Divide that across the cores and each core gets one page about every 5 µs, with everything the engine does included. An engine that spends a microsecond of its own on each page has used a fifth of its budget before the device has done anything. And when the page is already in memory, the engine's own work is all there is.

The buffer manager

Where does that work go? The LeanStore paper describes what it calls the classical design: every page sits behind a buffer manager, and the rest of the system "uses a simple interface that hides the complexities of the I/O buffering mechanism"1. It asks for a page by its id, uses the page, and hands it back. Going by the paper's account of the overheads it then removes, a traditional buffer manager does four things on every access1:

  1. Translate. Look the page id up in a hash table to find the memory frame holding it. The table is guarded by a latch, a short-lived lock on an in-memory structure (database people say latch to keep it apart from the locks a transaction holds on data).
  2. Pin. Increment a counter on the page so it can't be evicted while you're reading it.
  3. Record. Note the access for the replacement policy, for example by moving the page to the front of an LRU list.
  4. Latch. Latch the page itself, so no writer changes it while you read.

The paper calls this design "one of the pillars of classical database systems", and also "the major source of overhead in comparison with in-memory systems"1.

Shared writes

Why are four small steps expensive? Each of them is cheap on one core. What makes them expensive is that every one of them writes to memory that other cores also write.

The cost has a name: cache-line thrashing. A CPU core doesn't read and write memory directly; it works on 64-byte cache lines copied into its own cache. Many cores can hold a copy of a line to read it. To write a line, a core must hold the only copy, so every other copy is invalidated, and the line travels to the writer. When two cores keep writing the same line, it bounces between their caches like a ball in a game of catch, and each throw costs about as much as a miss all the way to memory. The cores spend their time passing the line back and forth instead of doing work.

Now look at the four steps again. The hash table's latch, the pin counter, the head of the LRU list and the page's own latch are each a word that every access writes. Every core has to take each of those lines in turn. Two threads looking up completely different keys still queue up behind each other on the root page's latch, because both write it. Add cores and the queue gets longer. A read that writes nothing shared has no queue at all.

That gives one question to ask of every step an engine takes:

Does this step write memory that other cores also write?

It also exposes the tension in the opening question. To run at memory speed, finding a page must take no lock, bump no counter and reorder no list. To run beyond memory, the engine still has to know which pages are in memory, which ones can leave, and which changes a crash would lose, and the classic way to know those things is the same bookkeeping the first goal rules out.

In-memory database systems resolve the tension by dropping the buffer manager altogether. In the LeanStore paper's words, "one of the defining characteristics of main-memory databases is that they do not have a buffer manager": data structures "use virtual memory pointers directly instead of page identifiers"1. That is fast, but it can't hold more data than memory. The LeanStore research keeps the buffer manager's interface and shows, one mechanism at a time, that each of the shared writes can be taken off the common path. Those results were published over several years and several papers, each measured in a research system built for it. Varaq is my attempt to take the principles and build one engine, as a library, that holds all of them together and survives a crash.

Varaq

Varaq is an embedded, transactional key-value store written in Rust. It keeps byte keys and values in order in a B+tree of 4 KiB pages6, holds the pages in use in memory, reads the rest from the device, and runs every transaction under snapshot isolation7.

The name comes from the Arabic waraq (ورق): the leaves of a tree, and the sheets of a book. A B+tree keeps all of its data in its leaves, and each of Varaq's leaves is one sheet, a 4 KiB page.

An application links Varaq as a library, picks a worker for the thread it runs on, and works in transactions:

let mut tx = db.begin(WorkerId(3))?;
let alice = tx.get(b"acct:alice")?;   // Some(b"100")
tx.insert(b"acct:alice", b"70")?;
tx.insert(b"acct:bob", b"130")?;
tx.commit()?;                          // durable when it returns

The engine itself never performs I/O. It reads and writes pages through two traits, PageStore and IoChannel, and backends implement them8. So the same engine runs over plain files, over io_uring with O_DIRECT on Linux9, and in a browser tab, over the browser's private file system10. The browser build will get a post of its own.

Two parts

Varaq has two parts, one on top of the other.

The B+tree is a complete storage engine on its own. It stores keys and values in order and manages the memory and the device beneath them. Its components:

  • pages, 4 KiB each, and the tree's search through them;
  • hybrid latches, one per page, which readers check without writing;
  • the buffer pool: a fixed array of memory frames and a table from page id to frame;
  • eviction, which picks pages to leave memory without tracking every access;
  • the devices and the backends that read and write them: one device for the tree's pages, one for old versions, one for the log, and a small catalog that records where recovery starts11.

The transaction layer sits on top of the tree and turns it into a transactional store. Its components:

  • workers, usually one per core, each with its own log, list of commits and store of old versions;
  • versions and snapshots, which let a reader see the store as of one moment;
  • the log and commit, which make writes durable;
  • checkpoints and recovery, which keep the log short and bring the store back after a crash.

The B+tree's design (its page format, splits and merges, translation and eviction) will be explained in a post of its own. This post gives a short tour of it, enough to follow a transaction, and spends more time on the transaction layer.

Figure 2 has two views: one sends the five lines down through both parts, the other shows where each idea lives; press an idea to jump to its section. The dashed parts are shared by every worker.

Figure 2Four layers, and what makes each fast
Interactive: two views · follow a line through the layers, or see where each idea lives · press a line, a beacon or a partOpen standalone

In short: begin touches only its worker and a shared clock. get walks down the tree through the buffer pool, and reaches a device only when a page isn't in memory. insert changes a leaf, saves the value it replaces, and appends a record to the log. commit makes the log durable and publishes the transaction's writes.

The common path

Varaq holds itself to one rule, the answer to the question above: a read whose pages are all in memory writes nothing that other cores write. Figure 3 runs four cores hitting the same pages, first with the classic hit's four shared writes, then with each one switched off in turn, the way Varaq removes them.

Figure 3Four cores read one page, write by write
Interactive: play or step through it · switch a write on or off, by its button or by pressing its blockOpen standalone

The rule has five exceptions, each a rare write and each described where it happens below: a counter bumped when a hot page sits in the wrong frame, a hint rewritten when a page's parent has moved, a shared hold taken when a read keeps getting interrupted, one compare-and-swap to rescue a page that was about to be evicted, and a read lock when a snapshot has to check on a very recent writer.

Principles and decisions

Each of the core mechanisms in Varaq rests on a published principle, and each section below credits the paper it comes from. The papers describe those mechanisms one at a time, each in a system built to measure it. Turning them into one engine took decisions that are Varaq's own: a latch whose readers fall back to a shared hold under contention, a page format with integer key heads, separated values that keep in the leaf the bytes a snapshot needs, freed pages written out empty before their ids are reused, a commit that waits only for what it depends on, the rules recovery uses to decide what to undo, and a core that performs no I/O.

The B+tree

Every get and insert in the transaction above becomes a lookup in the tree. tx.get(b"acct:alice") has to find the leaf that holds the key. It starts at the root and, at every level, does three things:

  1. search the page for the child that covers the key;
  2. check that no writer changed the page while it was reading;
  3. translate the child's page id into the memory frame that holds it.

A lookup in a three-level tree does each of these three times, and every lookup on every core does them on the same root page. So none of the three may write anything shared.

A page

A page is 4 KiB6. It is the unit the tree splits and merges, the pool caches, the device reads, and a checksum covers12, so its layout matters everywhere. Here is the start of it in Varaq's source, the size and the header's byte offsets13:

pub const PAGE_SIZE: usize = 4096;
pub(crate) const HEADER_BYTES: usize = 48;
pub const DATA_BYTES: usize = PAGE_SIZE - HEADER_BYTES;
pub mod offsets {
    pub const CHECKSUM: usize = 0;
    pub const COUNT: usize = 4;
    pub const SPACE_USED: usize = 6;
    #[allow(dead_code)]
    pub const DATA_OFFSET: usize = 8;
    pub const PREFIX_LEN: usize = 10;
    pub const KIND: usize = 12;
    #[allow(dead_code)]
    pub const PADDING: usize = 13;
    pub const LOWER_FENCE: usize = 16;
    pub const UPPER_FENCE: usize = 20;
    pub const UPPER: usize = 24;
    pub const RIGHT: usize = 32;
    pub const GSN: usize = 40;
    pub const DATA: usize = super::HEADER_BYTES;
}

After the 48-byte header, the page is a slotted page. A directory of 12-byte slots14 grows forward from the header, one per entry, in key order. The keys and values themselves are written into a heap that grows backward from the end of the page. Free space is the gap in the middle. Because the slots are fixed-size and sorted, inserting an entry of any length in the right place means shifting a few 12-byte slots, never the entries themselves.

Figure 4 fills one leaf an entry at a time. Hover any byte to see what it belongs to.

Figure 4A 4 KiB leaf, byte by byte
Interactive: hover a byte · play to fill the pageOpen standalone

Two details make the search through a page cheap. The fence keys (LOWER_FENCE, UPPER_FENCE) record the range of keys the page may hold, so the prefix all of its keys share is stored once (PREFIX_LEN) and cut from every key. And each slot keeps the first four bytes of its shortened key as an integer, its head, so a binary search mostly compares integers and only follows a slot into the heap when two heads tie.

Large values move out of the leaf onto value pages, and the leaf keeps a reference plus the 11 bytes a snapshot needs to decide whether it can see the value15. A value too large for any page becomes a run of contiguous pages, read up to 1 MiB at a time16.

Latches

Every core shares the tree's pages, so every page needs a latch. An ordinary reader-writer latch has a cost even for readers: taking it in shared mode means incrementing a reader count, which is a write to the latch's cache line. If every lookup did that at the root, every core would be playing catch with the root's latch, and reads that never conflict would still run one at a time.

The way out is an idea called optimistic latching: instead of announcing itself, a reader just checks afterwards whether anything changed. LeanStore made it the basis of its buffer manager, building on earlier work1. Varaq's version is a hybrid latch, one 64-bit word per page17:

const STATE_SHIFT: u32 = 56;
const STATE: u64 = 0xFF << STATE_SHIFT;
const EXCLUSIVE: u64 = STATE;
const ONE_SHARER: u64 = 1 << STATE_SHIFT;
const SHARED_MAX: u64 = 254;
const WAITING_SHIFT: u32 = 48;
const WAITING: u64 = 0xFF << WAITING_SHIFT;
const ONE_WAITER: u64 = 1 << WAITING_SHIFT;
const WAITING_MAX: u64 = 0xFF;
const VERSION: u64 = ONE_WAITER - 1;

The top byte is the state: free, a count of shared holders, or exclusive (all ones). The next byte counts readers waiting for a shared hold. The low 48 bits are a version number.

A reader never writes this word. It loads it, and if no writer holds it, remembers the version18:

pub fn optimistic(&self) -> Optimistic<OptimisticGuard<'_, T, W>> {
    let word = self.load();
    if exclusive_in(word) {
        return Err(Unwind);
    }
    Ok(OptimisticGuard { latch: self, version: word & VERSION })
}

Then it copies what it needs from the page (a slot, a key, a child's id) and loads the word again19:

pub fn unchanged_since(&self, version: u64) -> bool {
    fence(Ordering::Acquire);
    let word = self.load();
    !exclusive_in(word) && word & VERSION == version
}

If no writer holds the latch and the version hasn't moved, nothing changed in between, and the copy is good. If it did change, the reader throws the copy away and starts again from the root. A writer takes the word with one compare-and-swap, edits the page, and on release adds one to the version, which tells every reader in flight that its copy is stale20:

const fn released(word: u64) -> u64 {
    let next = (word & VERSION) + 1;
    (word & WAITING) | if next >= VERSION { 0 } else { next }
}

Figure 5 runs a reader against a writer under three schedules.

Figure 5An optimistic read and a writer
Interactive: pick a schedule · play or step through it · press a byteOpen standalone

On the way down, a reader checks each parent's version after picking the child and before following it, so it never follows a route through a page that a split just rewrote.

Optimism has one failure mode: if writers never stop, a reader may never get a clean copy. So a read that is interrupted twice in a row21 gives up on optimism and takes the leaf in shared mode, which does write the latch word: one of the five exceptions. If even that is refused, it adds itself to the waiting byte, and a writer that sees a waiting reader backs off until the read is done. A writer never waits for one latch while holding another; if a latch it needs is taken, it spins briefly, then lets go of what it holds and retries, so two writers can't deadlock.

No latch covers the whole tree22. A split walks down optimistically, then latches only the page it splits and that page's parent, and starts over if either changed since it looked. Only a split of the root also latches the root pointer. A merge takes its latches only if it can get all of them without waiting; if it can't, the merge doesn't happen, and the tree stays valid.

From page id to frame

A parent names each child by page id and nothing else23. So at every step of every descent, something has to turn "page 57" into the memory frame that holds page 57.

A plain hash table needs two memory accesses in a row to do it: one to read the table entry, and a second to reach the frame the entry names. The second can't start until the first has finished, so a lookup that misses the cache pays two full misses back to back.

LeanStore's first answer was pointer swizzling: once a page is in memory, the reference to it in the parent is replaced by the frame's address, so a hit becomes "a simple, well-predicted if statement rather than a costly hash table lookup"1. Its later retrospective names the cost: before a page can be evicted, every reference to it has to be changed back, so implementations restrict themselves to trees where each page has one parent and no sibling links24. Varaq wants leaves that point at their right neighbour, so it doesn't swizzle.

Instead Varaq is built on predictive translation, published at SIGMOD 202625. The hash table stays, but each page id also has a preferred frame, computed from the id alone26:

pub const fn mix(page: u64) -> u64 {
    let mut h = page;
    h ^= h >> 33;
    h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
    h ^= h >> 33;
    h = h.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
    h ^= h >> 33;
    h
}
#[inline]
#[must_use]
pub const fn preferred_frame_of(hash: u64, frames: u32) -> u32 {
    #[allow(clippy::cast_possible_truncation)]
    {
        ((hash as u128 * frames as u128) >> 64) as u32
    }
}
#[inline]
#[must_use]
pub const fn preferred_frame(page: PageId, frames: u32) -> u32 {
    preferred_frame_of(mix(page.get()), frames)
}

mix scrambles the id's bits, and preferred_frame_of scales the result into the number of frames. The same hash picks the table bucket. Since both addresses come straight from the id, a lookup can start reading the preferred frame's header and the table entry at the same time, and a modern core will overlap the two loads27. If the table says the page sits in its preferred frame, and the frame's header confirms it holds that page, the hit has cost about one cache miss instead of two. Otherwise the lookup follows the table to wherever the page is.

Figure 6 steps through the cases: a page in its preferred frame, a page somewhere else, a page that isn't in memory, and moving a hot inner page into its preferred frame.

Figure 6From page id to frame
Interactive: pick a case · play or step through it · press a frame or a bucketOpen standalone

The prediction only pays off once hot pages sit in their preferred frames, and how pages get there is where Varaq departs from the paper. The paper loads a page into its preferred frame when that frame is free, and otherwise into any free frame; from a page's second access on, it moves the page home with some probability, and with a lower one when that means displacing the page already there25. Varaq makes the choice narrower:

  • A page is always read into whichever frame is free; the load never tries the preferred frame.
  • Only inner pages (the few pages above the leaves that every descent passes through) are ever moved, and only during a descent. Leaves stay where they land, so a leaf lookup usually takes the table's two-step answer.
  • The odds are fixed: one pass in 32 through an out-of-place inner page moves it, and when the target frame holds a page that is itself in its preferred frame, a second roll of one in 16 has to win too, one in 512 in all2829.
  • The move happens only if the page is hot, has no write-back in flight, and both frames can be latched exclusively; otherwise it is skipped.
fn maybe_promote(&self, page: PageId, from: u32) {
    #[allow(clippy::cast_possible_truncation)]
    let frames = self.pool.len() as u32;
    let preferred = crate::bufmgr::preferred_frame(page, frames);
    if preferred == from {
        return;
    }
    let Some(target) = self.pool.slot(preferred) else { return };
    let roll = self
        .inline_seed
        .fetch_add(0x9E37_79B9_7F4A_7C15, core::sync::atomic::Ordering::Relaxed);
    if !crate::bufmgr::translate::mix(roll).is_multiple_of(PROMOTE_ODDS) {
        return;
    }

The roll is a relaxed add on a counter the tree keeps (inline_seed)30, on every pass through an out-of-place inner page: another of the exceptions.

Each frame also remembers which slot of which parent points at it, so that a merge can find a page's parent. A descent rewrites that hint only when it no longer matches, for example after the parent moved frames: the next exception.

Naming children by id costs a translation on every step, and buys two things. Each leaf can name its right neighbour, so a range scan walks along the leaf level in one pass31. And evicting a page means removing one table entry, however many places refer to the page.

The buffer pool

So far, every page get needed was in memory. What happens when one isn't?

A miss

The pool is a fixed array of frames, allocated once when the store opens, and a miss reads one page into a free frame. If two threads miss on the same page at once, reading it twice would waste a device read, so the first thread to miss on page 57 claims a row in an in-flight table and issues the read. A second thread that misses on page 57 finds that row and waits on it instead of reading again32. Traditional buffer managers do the same, and LeanStore does it with its I/O frames1.

Before the page becomes visible, its checksum is verified. The checksum covers the page's id as well as its bytes, so a page written to the wrong place is caught too12:

pub fn of_page(page: &[u8], pid: PageId) -> u32 {
    assert!(page.len() > COVERED_FROM, "a page is longer than its checksum field");
    crc32c_append(crc32c(&pid.get().to_le_bytes()), &page[COVERED_FROM..])
}

A page that fails the checksum or the structural checks after it is refused, never repaired.

Eviction

The harder question is which page has to leave when the pool is full. The classic answer, an LRU list updated on every access, is a shared write on every hit, the one thing the common path forbids. The principle Varaq follows instead is LeanStore's cooling stage1: don't watch every access; guess, and give the guess a chance to be wrong.

  • Cooling. When a miss finds no free frame, the thread that missed picks frames at random and moves them to a first-in, first-out cooling queue, until about 10% of the pool is cooling33. It never cools the root, a page being written, or a changed page whose log records aren't durable yet. A cooling page is still in memory and still readable.
  • Rescue. If anyone touches a cooling page, it goes back to hot. That costs one compare-and-swap on its frame, another of the exceptions.
  • Eviction. Pages that reach the end of the queue untouched are evicted. A page with changes the device doesn't have yet is written first, and only after the log records describing those changes are durable.

Hot pages are almost never left untouched for long, so they get rescued and stay; cold pages drift out. In the paper's words, the scheme identifies "infrequently-accessed pages without having to track each access"1. A hit on a hot page records nothing. Figure 7 runs a pool of 128 frames under a skewed workload: the popular pages warm back and stay, and the rest cycle through.

Figure 7A pool of 128 frames under a skewed workload
Interactive: play or scrub time · change the skew · hover a frame or a pageOpen standalone

Two more things follow from the design. Because no page holds a pointer to another page's frame, eviction doesn't care about the tree's shape: a child can leave memory before or after its parent. And because the frames are one array that lives as long as the store, a reader can never touch freed memory: eviction takes the page's latch exclusively and bumps its version, so a reader whose page was evicted mid-copy fails its version check and starts again, having read only valid memory17. LeanStore's first design protected readers with epochs, and its retrospective removed them for this same reason24; Varaq never had them.

The miss path is not yet measured at scale (see limitations). All the measurements below run with the data in memory.

Transactions

The tree stores one value per key and hands it to whoever asks. A transaction needs more: a stable view of the store while it runs, writes that appear all at once or not at all, and a promise that a committed write survives a crash. The transaction layer adds those on top of the tree.

Workers

The cheapest way to stop cores writing the same memory is to give each one its own. Varaq does that with workers. A store has a fixed number of them, usually one per core, and a transaction holds one from begin to commit34. db.begin(WorkerId(3)) claims worker 3; a worker runs one transaction at a time, and a begin on a busy worker is refused with WorkerBusy.

The line between what is private and what is shared follows from the question. What a transaction writes on every operation belongs to its worker:

  • its log ring, staged through 16 MiB of memory35;
  • its version tree, where old values go when they are overwritten;
  • its snapshot slot, which says what it can see;
  • its list of commits, which other workers read to decide visibility.

What is touched once per transaction, or rarely, is shared: the clock that hands out timestamps, the log device's flush36, the tree's pages and the buffer pool, and a background checkpointer. Figure 8 runs transactions on several workers at once and shows who owns what. Change the number of workers to see which parts stay private.

Figure 8Per worker, and shared
Interactive: play the ticks · change the worker count · hover a workerOpen standalone

With its worker in hand, begin reads the clock once and writes that timestamp into the worker's snapshot slot. That timestamp is the transaction's snapshot: it reads the store as it was at that moment in commit order, plus its own writes, and other transactions see its writes all at once, when it commits. This is snapshot isolation, Varaq's one isolation level7. It rules out dirty reads, non-repeatable reads, phantoms and lost updates. It is weaker than serializability: two transactions that each read what the other writes, and write different keys, can both commit (write skew).

Nothing in begin touches a page or a device.

Versions

When get reaches the leaf, it has one question left: which version of the key can its snapshot see?

Snapshot isolation needs old versions. If your snapshot was taken before someone overwrote acct:alice, you must still read the old value. Varaq keeps only each key's newest version in the tree. When a write replaces a version, the old one moves into the writing worker's own version tree37, and the new version records where it went. So a reader with a current snapshot stops at the leaf, and a reader with an old snapshot follows the links back. Each worker saves old versions only in its own tree, so two workers keeping history at the same time never write the same structure.

The version information lives in a small header at the front of each stored value38:

pub const CHAINED_HEADER_BYTES: usize = 1 + 2 + 8 + 8;
pub struct Version {
    pub writer: u16,
    pub tx_ts: u64,
    pub previous: u64,
}

A one-byte tag39, the writer's worker (writer), a timestamp (tx_ts), and the location of the previous version (previous): 19 bytes. Figure 9 shows a stored value byte by byte.

Figure 9A stored value, byte by byte
Interactive: pick a form · hover a byteOpen standalone

The interesting choice is which timestamp. The obvious one is the writer's commit timestamp, so a reader could compare it with its snapshot directly. But a transaction doesn't know its commit timestamp while it runs, so every version it wrote would have to be patched when it commits: one more write per version, and a moment when a reader could see half a transaction. Varaq follows the principle of Ordered Snapshot Instant Commit, from LeanStore's work on snapshot isolation40: stamp each version with its writer's start timestamp. Then a commit rewrites no version at all. It is one log record and one entry appended to the worker's list of commits.

The cost moves to the reader, who now has to answer: did the transaction that started at time t on worker w commit before my snapshot? Each worker keeps its commits in order, as (commit timestamp, start timestamp) pairs, so the answer is a binary search41:

fn cut(entries: &[Entry], snapshot: u64) -> Option<u64> {
    let at = entries.partition_point(|e| e.commit_ts < snapshot);
    if at == 0 { None } else { Some(entries[at - 1].start_ts) }
}

cut finds the newest transaction the worker committed before the snapshot and returns its start timestamp. Because a worker runs its transactions one after another, every version that worker wrote with a start timestamp up to that one is visible, and anything later isn't42:

pub fn visible(&self, worker: WorkerId, tag: u64, snapshot: Timestamp) -> Result<bool, Error> {
    if tag < self.all_lwm.get(worker.0).map_or(0, |m| m.load(Ordering::Acquire)) {
        return Ok(true);
    }
    Ok(match self.lcb(worker, snapshot)? {
        None => false,
        Some(cut) => tag <= cut,
    })
}

The first check is a shortcut: a version written before every live snapshot began (the worker's low-water mark, all_lwm) is visible to everyone, with no search. Only recent versions need the search, which takes a read lock on the writer's list43: the last of the exceptions. A transaction that hasn't committed has no entry yet, so its versions are invisible to everyone else. Figure 10 lets you drag the snapshot to see which versions it can read.

Figure 10Reading order:0042 at a chosen snapshot
Interactive: drag the snapshot plane or play it forward · press a pad or a versionOpen standalone

tx.insert(b"acct:alice", b"70") writes a new version. If two concurrent transactions write the same key, only the first can commit: the second is refused with Conflict as soon as it tries to write over a version its snapshot can't see44. Otherwise the insert moves the version it replaces into its worker's version tree, latches the leaf, and installs its own version, stamped with its start timestamp. Until the transaction commits, nobody else can see it.

Old versions are collected once every live snapshot has moved past them, behind the oldest live snapshot, the store's watermark45. A long-running reader holds the watermark back, and 0.1.0 doesn't bound the memory that costs; reads stay correct at any chain length.

The log

After the two inserts, both new versions sit in leaves in memory. The pool writes changed pages back to the device when it chooses, possibly long after the commit. If the machine crashed in between, a change the client was told had committed would be gone.

Storage engines close that gap with a log. Before a change counts, a short record describing it is appended to the log device, and a changed page may only be written back after the records describing its changes are durable. Appending is small and sequential, so it is cheap to make durable at commit; after a crash, recovery reads the log and redoes any change the pages on the device don't have.

A log per worker

A single log with a single sequence number that every write increments is, again, a shared write on every write. The principle Varaq builds on comes from Rethinking Logging, which extends distributed logging by Wang and Johnson: give each worker its own log46. In Varaq, each worker writes its own log ring, and there is no store-wide sequence number47.

Separate logs create one problem. When recovery replays the logs, it must apply the changes to each page in the order they happened. If two workers changed the same page, their records sit in different logs, and something has to say which came first. That something is the GSN (global sequence number), a clock that travels with each page48:

pub fn observe(&self, page_gsn: u64) -> u64 {
    let before = self.now.fetch_max(page_gsn, Ordering::AcqRel);
    before.max(page_gsn)
}
pub fn stamp(&self, page_gsn: u64) -> Option<u64> {
    self.observe(page_gsn);
    self.now
        .fetch_update(Ordering::AcqRel, Ordering::Acquire, |now| now.checked_add(1))
        .ok()
        .map(|before| before + 1)
}

When a worker changes a page, it first catches its own clock up to the page's (observe), then stamps the change one above (stamp). It is a Lamport clock, with pages playing the part of messages. Two changes to the same page are always ordered, whichever workers made them, and changes to unrelated pages need no order at all. Reads never touch a GSN.

Commit

A commit happens in two steps, a split Varaq takes from autonomous commit49.

At pre-commit50, the transaction appends its commit record to its worker's log, takes a commit timestamp from the clock, and adds one entry to its worker's list of commits. That entry is what makes its writes visible to new snapshots, and the worker is immediately free for its next transaction.

The client, though, isn't told "committed" yet. It waits for an acknowledgement, which comes once the transaction's own log record is durable, and everything it depends on is durable too: any other worker's earlier change to a page it changed, and any transaction whose writes it read or overwrote51.

Why wait for other workers? Because the logs are separate. Suppose B, on worker 2, reads a value that A wrote on worker 1. If a crash kept B's log record but lost A's, recovery would bring back B, whose result rests on a write that never happened. Waiting for A's acknowledgement first means no client is ever told B committed while a crash could still take it back. If B depends on nothing that isn't durable yet, it waits only for its own record; Rethinking Logging calls this remote flush avoidance46. The autonomous commit paper orders every transaction by GSN and waits until every worker's log has passed it; Varaq narrows the wait to the logs and transactions it depends on. Figure 11 steps two workers through a commit.

Figure 11Two workers commit, one barrier
Interactive: pick a durability · step through the commitsOpen standalone

Making the log durable means calling fdatasync. Every worker's ring is a region of the same log device, so one fdatasync makes every ring write that finished before it durable, for all workers at once36. At most one is in flight. Every committer waiting when it starts is covered by it, so a burst of commits shares a flush or two (the one in flight and the next) rather than paying one each.

When commit returns, the five lines are done. Two jobs keep running behind them.

Checkpoints

Each worker's log ring has a fixed size, so it can't grow forever. To reuse the oldest part of the log, the engine has to write back the pages those records describe; after that, recovery no longer needs them. That write-back is a checkpoint. Done all at once, it floods the device with writes and can stall the whole store while it catches up.

Varaq checkpoints a slice at a time, the principle of continuous checkpointing from the same logging work46. The pool is divided into partitions. Each increment covers about a tenth of them52: it notes how far every worker's log has reached, makes those logs durable, writes back every changed page in its partitions, waits for the data device to make them durable, and records the noted positions as those partitions' mark. Recovery starts from the lowest mark across all partitions, so it moves forward a tenth of the pool at a time, and no increment stops the store. Figure 12 plays the increments and shows recovery's starting point moving through the log.

Figure 12Ten increments move begin through a worker's log
Interactive: play or scrub the increments · hover a partitionOpen standalone

How much log to keep is a trade-off. By default the target is 20 GiB across a store's workers53: a large target means fewer write-backs while the store runs, and a longer recovery after a crash, about that much log while increments keep pace, and up to twice as much when they fall behind or a long transaction holds the marks back.

On open, recovery reads the catalog, scans each worker's ring from its mark, and redoes each page's changes in GSN order. Then it undoes every transaction without a commit record, every transaction whose pages couldn't be rebuilt, and every transaction whose dependencies didn't survive. A log that recovery can't read is refused, and the store doesn't open54.

Deletes

A delete can't just remove the key from its leaf, because a snapshot that started earlier must still find the value it saw. So a delete happens in four steps:

  1. Write a removal. The delete installs a version with no value, after saving the old value in its worker's version tree like any other write. New snapshots see "absent"; older ones follow the link back to the value.
  2. Collect. Once every snapshot has passed the removal and its transaction is acknowledged, the entry is removed from the leaf, and that removal is logged so recovery can repeat it.
  3. Merge. A leaf left too empty merges with a neighbour under the same parent, if all the latches it needs can be taken without waiting.
  4. Reuse. The page freed by the merge is written out empty by the next checkpoint before its id can be handed out again.

The data file never shrinks: a freed page id is reused before the file grows, so the file stays near the largest size the data has reached. Figure 13 follows one key through all four steps.

Figure 13One deleted key, from the delete to the reuse of its page
Interactive: play or step through it · press a chapter · drag to turn the sceneOpen standalone

Measurements

On four vCPUs, TPC-C reaches 81% of linear; these runs do not show which part of the work runs one core at a time.

Every run here used small cloud VMs of one family, in Claude Code sessions where Claude ran each benchmark, far from the dedicated machines the design targets, so the method matters as much as the numbers.

Machine: the runs used Firecracker VMs with 4 vCPUs and about 15 GiB of memory, on a shared host, over a virtual disk55. Table 1 has the rest.

Storage: every store is a buffered file, with no O_DIRECT and no io_uring in any run. Every Varaq store fits in its pool except in one crud-bench configuration that forces its log (--sync, below), where a 64 MiB pool sits under a 242 MB store and a quarter of its reads miss; elsewhere, after the first touch, the data is read from the pool.

Durability: only that --sync configuration forces its log; every other run writes its log without forcing it, so those numbers do not include the cost of making commits durable.

Builds: the TPC-C and crud-bench runs, and the runs in the comparison, measured the development tree on 7 November (the database-level runs one commit before the others), from which 0.1.0 was cut; the code changed between those builds and the release, and the lookups were measured on the 0.1.0 release.

The machine, in full
Linux VM
Platform Firecracker microVM under KVM, Linux 6.18.44, on a shared cloud host; CPU steal not measured
CPU Intel Xeon at 2.10 GHz (family 6, model 207), 4 vCPUs, no SMT, one NUMA node
Caches L1d 48 KiB and L1i 32 KiB a core, L2 2 MiB a core, L3 260 MiB shared
Memory 15.71 GiB, no swap
Storage virtio-blk, 256 GiB, ext4 (relatime, discard), mq-deadline
Toolchain rustc 1.97.0
Load no other build or benchmark beside a run

Table 1. The machine, as the record of the database-level runs describes it (kernel 6.18.44-fc-v310)56; the TPC-C and crud-bench records report the same kernel build, 4 vCPUs, 15 GiB and one virtio disk. The database-level runs also had a 13.35 GiB memory cgroup and 16 workers.

The device

Before Varaq's numbers, the kind of device under them. fio ran on a Linux VM of the same family on 28 October, 4 KiB blocks over a 4 GiB file, O_DIRECT through io_uring, 15 seconds a row57. The runs below used a later VM of that family, not the same host, and the 28 October record found its own disk 20 to 35% slower than an earlier VM's, so a disk under these runs may differ by as much. Apart from the configuration that forces its log, whose misses go to a buffered file and whose commits wait on fdatasync, no run below reads the disk after its first touch, so these rates bound none of the other numbers that follow; they are what the out-of-memory runs will be compared with:

fio row IOPS median latency
random read, queue depth 1 23,567 25.0 µs
random read, queue depth 16 105,852 113 µs
random read, queue depth 64 133,658 371 µs
random read, queue depth 256 224,623 1,004 µs
random write, queue depth 64 87,818 2,703 µs
4 KiB write and fdatasync 7,846 113 µs

Table 2. A Linux VM's disk, 28 October. It is a virtual device, not a dedicated NVMe drive: one thread waiting on one read sees 25 µs, and the device serves about 9.5 times as many reads a second only with 256 in flight.

Scaling with cores

On the common path, a hit writes nothing that other cores write, so reads in memory should scale with cores, but a lookup-only scaling run on this machine is not among this release's records. What the records hold is TPC-C, whose transactions write as well as read; its driver and method are in the next section.

Amdahl's law gives a way to read a speedup: if a fraction p of the work runs in parallel and the rest runs one core at a time, N cores give 1 / ((1 − p) + p / N). In a storage engine the serial part is anything cores do one at a time: a cache line that moves between them, a shared counter, a device flush, a hot page two writers both want. TPC-C exercises that, because its transactions write. On the 4-vCPU VM, four threads over four warehouses ran 3.24× as many transactions a second as one thread, 81% of linear, and eight threads over eight warehouses, sharing the same four vCPUs, ran 2.98× as many58. Figure 14 puts the speedups against linear and fits p to the four-thread point.

Figure 14TPC-C against linear and Amdahl's curve
Interactive: drag the handle to set p · press a point for its numbersOpen standalone

TPC-C

TPC-C runs on Varaq alone, through its own driver, with a fresh load for every row and three rounds a row59. Every round's TPC-C consistency checks held. Figure 15 draws the medians against threads; pick a point for its New-Orders a minute (the figure TPC-C reports as tpmC, here with no think or keying time), its aborts and its CPU per transaction. An aborted transaction lost a first-writer-wins race and is not retried.

Figure 15TPC-C on Varaq against threads
Interactive: press a point in any chart · switch the seriesOpen standalone

From one thread to four, CPU per transaction rises from 94.7 µs to 111.9 µs and 7.0% of transactions abort on write conflicts. I hypothesize two sources for the serial share, both already named in the design: TPC-C's New-Order transactions all update their district's row, so writers meet on a few hot pages, and every writing commit bumps the shared clock once. A 4-vCPU machine cannot say how far writes scale beyond that, and it is one of the main open questions for 0.1.0.

crud-bench on Varaq

crud-bench, a benchmark harness for key-value stores and databases, drives single-key creates, reads, updates and deletes, scans and batches of 100 and 1,000 keys over one million rows, with four clients, a 4 GiB data pool and 4 GiB of frames for old versions60. Figure 16 holds everything crud-bench reports for Varaq, one row per operation: its rate, and its latency from the median to the slowest61.

Figure 16Every operation on Varaq: its rate and its latency
Interactive: hover or press a row · step through the operations · sort the listOpen standalone

Limitations of these measurements

These numbers are a first look, and each of their limits narrows what they can show. Four vCPUs on a shared host cannot show how the hit path or the miss path scales on many cores. Apart from the durable configuration's 64 MiB pool, every store fit in memory, so the miss path, the half of the design built for the device, was not under load. And every store was a buffered file, so neither O_DIRECT nor io_uring was in play. Runs on large Linux machines with dedicated NVMe drives will come in a later post.

Comparison

In the same harness, Varaq reads 2.26× as fast as SurrealKV and scans 1.85× to 6.67× as fast; SurrealKV is still faster at single-key deletes and most batched writes. Through SurrealDB, a million-row run finished 1.66× as fast, though point reads were slower.

Within those limits, I compared Varaq with SurrealKV, an engine I created at my previous company, and the fastest Rust key-value store so far. SurrealKV is an LSM-tree: it collects writes in memory and writes them out in sorted batches, so a write is cheap and a read may have to look in several places. A B+tree makes the opposite trade, so one would expect Varaq ahead on reads and scans, and SurrealKV ahead on writes it can batch. The comparison runs first in the same harness, then underneath SurrealDB.

crud-bench against SurrealKV

The same harness, rows, clients and cache as Figure 16, with SurrealKV 1.3.0 underneath, the engines interleaved three rounds each62. Varaq read 2.26× as fast as SurrealKV, created keys 2.47× as fast, updated them 1.84× as fast, and ran every scan 1.85× to 6.67× as fast63. Figure 17 draws every row's ratio; press a row for both engines' rates and latencies64.

Figure 17crud-bench against SurrealKV, Linux VM
Interactive: hover or press a row for both engines · sort by ratioOpen standalone

Against the trade's prediction, Varaq was faster at single-key creates and updates too. The same record's durable configuration (--sync, 200,000 rows, a 64 MiB cache) went the other way on reads (0.53×, because SurrealKV answered from a 256 MiB memtable beside its cache; 1.13× when Varaq was given the same memory), updates (0.81×) and deletes (0.77×)63. SurrealKV is still faster at single-key deletes, and at most batched writes, as the trade predicts for batches. Both are on the list for the next release.

SurrealDB on SurrealKV and on Varaq

One level up, the same comparison runs through SurrealDB itself: built once, with the storage engine chosen by the connection string and nothing else changed, and crud-bench driving it with small records of about 150 bytes and four clients65. This build links SurrealKV 1.2.0. Each size ran once per engine, with no prediction recorded beforehand, so these rows are indicative. The whole crud-bench run took 188 s on Varaq against 219 s on SurrealKV at 20,000 rows, and 3,594 s against 5,970 s at one million rows, 1.66× as fast66.

Figure 18 breaks the million-row run down by query family, all 60 rows of it6768; switch it to 20,000 rows for the smaller run.

Figure 18SurrealDB on Varaq and on SurrealKV
Interactive: switch table size · press a band or a rowOpen standalone

Single-row creates, updates and deletes ran 2.70× to 3.28× as fast through SurrealDB on Varaq, and filtered scans over the whole table about twice as fast. Point reads were the largest exception, at 0.63×, although Varaq read 2.26× as fast in the harness; batched reads (0.79×, 0.85×), a batched delete of 1,000 (0.77×), a batched create of 1,000 (0.94×) and select(*) limit(100) (0.97×) were also slower on Varaq. The point-read gap is one of the first things I will look at. The SurrealDB backend for Varaq is new and not yet published. It passes 94 of the 114 applicable tests of SurrealDB's storage test suite, and the 20 it fails (savepoint rollback, one conflict-tracking read, and conflicts raised at write time) return errors, never wrong values69.

What's next

I chose to measure in a small, constrained place first. A 4-vCPU VM keeps the engine's own costs in view, but it can't show how the design scales. The next post will: Varaq on large Linux machines with dedicated NVMe drives, with reads scaling across many cores and the miss path under load. Varaq also runs in the browser, keeping a store in the Origin Private File System shared by several tabs70, and that will get a post of its own.

There is a lot still to improve in 0.1.0. The main areas:

  • Deletes and batched writes. Single-key deletes and most batched writes trailed SurrealKV.
  • Point reads through a query layer. They ran slower under SurrealDB, although Varaq reads faster in the harness.
  • Long readers. A collector that prunes versions between live snapshots would bound the memory they hold.

I'll measure each against the numbers in this post and report what I find.

Varaq was built with models, proofs and verifiers: formal models of the design run through model checkers, proofs over the code, and simulators that inject faults into the running engine, each shown able to fail before it was trusted. The code released today is a redacted form of that work. Code can now be copied and regenerated with little effort; the models, proofs and verifiers cannot, so the code is open source and they are not. The about page sets out that philosophy, and how the three kinds of evidence fit together.

Sources

Papers are cited by title and venue, linked where the authors publish them. Code is cited in Varaq's source at one commit, each line linked. Measurements are cited by what was measured, on which machine and when; the one measured for this post links to their full records.

  1. LeanStore: In-Memory Data Management Beyond Main Memory. Leis, Haubenschild, Kemper, Neumann · ICDE 2018.
  2. One lookup through the tree, one thread, Linux VM (4 vCPUs). Measured for this post, 11 November 2026: lookup-20261111.txt.
  3. fio, 4 KiB random read at queue depth one, Linux VM. Measured on the 4-vCPU Linux VM, 28 October 2026.
  4. Half a turn of a 7,200 rpm disk. Worked out from the numbers in the text.
  5. What Modern NVMe Storage Can Do, And How To Exploit It. Haas, Leis · PVLDB 16(9), 2023.
  6. The page size. Node.rs, line 3.
  7. A transaction reads the snapshot taken when it begins. Db.rs, line 1084.
  8. The kernel performs no I/O; backends implement two traits. Store.rs, line 2.
  9. The Linux io_uring backend. Uring.rs, line 20.
  10. The browser backend. Opfs.rs, line 12.
  11. A store is four devices. Devices.rs, line 24.
  12. A page's checksum covers its id and its bytes. Checksum.rs, line 13.
  13. The page header. Node.rs, line 4.
  14. A slot. Node.rs, line 14.
  15. What the leaf keeps of a separated value. Tuple.rs, line 4.
  16. Large values are runs of pages. Blob.rs, line 10.
  17. The hybrid latch word. Latch.rs, line 6.
  18. A reader records the latch's version. Latch.rs, line 61.
  19. A reader checks the version again. Latch.rs, line 180.
  20. A writer's release moves the version. Latch.rs, line 20.
  21. The shared fallback. Tree.rs, line 16.
  22. The tree's only tree-level state is its root reference. Tree.rs, line 93.
  23. A child reference is a page id. Child.rs, line 3.
  24. LeanStore: A High-Performance Storage Engine for NVMe SSDs. Leis · PVLDB 17(12), 2024.
  25. Predictive Translation: High-Performance Buffer Management Without the Trade-Offs. Zinsmeister, Nguyen, Leis, Neumann · SIGMOD 2026.
  26. The preferred frame. Translate.rs, line 80.
  27. A lookup samples the predicted frame and probes the table. Tree.rs, line 496.
  28. Moving a page into its preferred frame. Tree.rs, line 30.
  29. Displacing a page from its own preferred frame. Tree.rs, line 31.
  30. Moving an inner page home. Tree.rs, line 582.
  31. A leaf names its right neighbour. Node.rs, line 28.
  32. Reads in flight. Inflight.rs, line 48.
  33. The cooling stage. Cooling.rs, line 102.
  34. A thread binds to a worker for each call. Db.rs, line 1294.
  35. A worker's log ring in memory. Db.rs, line 6.
  36. One barrier, shared by every worker. Barrier.rs, line 65.
  37. A version tree per worker. Versions.rs, line 20.
  38. The version header. Tuple.rs, line 3.
  39. The version a value carries. Tuple.rs, line 17.
  40. Scalable and Robust Snapshot Isolation for High-Performance Storage Engines. Alhomssi, Leis · PVLDB 16, 2023.
  41. The newest commit before a snapshot. Commits.rs, line 16.
  42. Visibility. Commits.rs, line 211.
  43. Visibility by binary search. Commits.rs, line 203.
  44. Write conflicts are refused at write time. Db.rs, line 1385.
  45. The oldest live snapshot. Txn.rs, line 66.
  46. Rethinking Logging, Checkpoints, and Recovery for High-Performance Storage Engines. Haubenschild, Sauer, Neumann, Leis · SIGMOD 2020.
  47. A log ring per worker. Ring.rs, line 4.
  48. The GSN. Gsn.rs, line 15–16.
  49. Moving on From Group Commit: Autonomous Commit Enables High Throughput and Low Latency on NVMe SSDs. Nguyen, Alhomssi, Ziegler, Leis · SIGMOD 2025.
  50. Pre-commit. Db.rs, line 1556.
  51. Which logs a commit waits for. Driver.rs, line 31–32.
  52. Ten increments cover the pool. Db.rs, line 38.
  53. The log limit. Db.rs, line 8.
  54. Recovery: analysis, redo, undo. Recovery.rs, line 181.
  55. The VM of the TPC-C and crud-bench runs. Measured on the 4-vCPU Linux VM, 7 November 2026.
  56. The Linux VM of the 7 November runs. Measured on the 4-vCPU Linux VM, 7 November 2026.
  57. fio on a Linux VM's disk, 28 October (kernel 6.18.44-fc-v180). Measured on the 4-vCPU Linux VM, 28 October 2026.
  58. TPC-C on the Linux VM, medians. Measured on the 4-vCPU Linux VM, 7 November 2026.
  59. TPC-C on the Linux VM, every round. Measured on the 4-vCPU Linux VM, 7 November 2026.
  60. The crud-bench method. Measured on the 4-vCPU Linux VM, 7 November 2026.
  61. crud-bench's output for Varaq, every run. Measured on the 4-vCPU Linux VM, 7 November 2026.
  62. The crud-bench method. Measured on the 4-vCPU Linux VM, 7 November 2026.
  63. crud-bench against SurrealKV 1.3.0, Linux VM, medians of three. Measured on the 4-vCPU Linux VM, 7 November 2026.
  64. crud-bench's output, every run. Measured on the 4-vCPU Linux VM, 7 November 2026.
  65. SurrealDB over each engine. Measured on the 4-vCPU Linux VM, 7 November 2026.
  66. SurrealDB, wall time of the whole run. Measured on the 4-vCPU Linux VM, 7 November 2026.
  67. SurrealDB, 1,000,000 rows, Linux VM. Measured on the 4-vCPU Linux VM, 7 November 2026.
  68. crud-bench's output through SurrealDB. Measured on the 4-vCPU Linux VM, 7 November 2026.
  69. SurrealDB's storage test suite. Measured on the 4-vCPU Linux VM, 7 November 2026.
  70. Several tabs, one store. Share.js, line 261.