Introducing Varaq 0.1.0 · read the announcement ›

A fast embeddedB+tree, in Rust

An embedded, ACID-compliant, key-value database for Rust

Get started
See the benchmarks →
MediumMagnetic disk
Spindle7,200 RPM
Per read4.2 ms
Magnification×1.0
Track172 · 4 KiB sectors
Drag the disk · scroll to dive
disk · half a turn at 7,200 rpm, seek not counted
nvme · ~100 µs per 4 KiB random read (Haas & Leis, VLDB 2023)
ram · one tree lookup on one core, measured

Every read waits
for the platter.

NVMe SSD · M.2 · controller, DRAM cache, two flash packages

01 / 05

  1. A tree lookup whose pages are in RAM takes about a microsecond on one core.
  2. A page that is not in memory costs one 4 KiB read, shared by every thread that needs it; when memory is full, that thread first evicts a page.
  3. While that read is in flight, every worker that does not need that page keeps running.
  4. Tree lookups check versions instead of locking, so readers rarely wait on each other.
  5. Commits are ACID, with snapshot isolation, and are recovered from the log after a crash.

Varaq is a key-value store on a B+tree of 4 KiB pages. It keeps the pages you use in memory and reads the rest from the device, one read per missing page. It commits every transaction with snapshot isolation, and gives every worker its own log. A tree lookup checks versions instead of taking locks.

0

page, the unit of memory and disk

0

log for every worker

0

device read to bring back any page that is not in memory

One engine. Six layers.

From the workers that run transactions down to the files on the device.

    Press a layer to open it

    Every worker, its own log.

    Readers check a page’s version instead of taking a lock. Scroll through it, then take the controls.

      Live0requests / s · 4 workers · optimistic

      A simulation of the design, not a benchmark

        Three things
        the design gives you.

        What the design buys you, in plain terms. Each one comes from a layer you just scrolled through.

        Fig 0.1

        Larger than memory

        When no frame is free, pages picked at random start to cool. One touched while cooling stays; one left untouched leaves when memory is needed. Your data can be larger than the memory you give it.

        “Keep it all in RAM, or it gets slow.”the old trade

        “Hot pages stay in memory, the rest one read away.”cooling stage · one read per miss

        Fig 0.2

        Readers do not wait on readers

        A tree lookup checks a version number instead of taking a lock, so readers rarely wait on each other. Only after two failed tries does a read hold the leaf shared.

        “Add a thread, add a wait.”shared latches

        “Readers check a version and move on.”optimistic lock coupling

        Fig 0.3

        Commits recovered after a crash

        By default, commit returns once the transaction is in the log on disk. Opening the store after a crash replays the log, then undoes every transaction that did not commit or whose writes did not all survive; if it cannot, it refuses to open.

        “It was still in memory when the power went.”lost on crash

        “Committed means on disk, by default.”write-ahead log · recovery on open

          
                      

          Output

          Add a core,
          add its transactions.

          Each worker writes its own log and its own version tree; all share one tree. Measured on a 4-vCPU Linux VM: TPC-C over four warehouses, one thread per core. Four cores commit 3.24× as many transactions a second as one, 81% of linear, the median of three rounds; the curve between is Amdahl's law fitted to that point. Runs on large machines come in a later post.

          See every benchmark →

          1.00×TPC-C · 1 core
          1 core2 cores3 cores4 cores

          Fifty years of B-tree research, from spinning disks to memory and NVMe.

          Built from the work in

          Bayer & McCreight1970LeanStoreICDE 2018Rethinking LoggingSIGMOD 2020What Modern NVMe Storage Can DoVLDB 2023OSICPVLDB 2023LeanStore for NVMeVLDB 2024Autonomous CommitSIGMOD 2025Predictive TranslationSIGMOD 2026

          01 · Spinning disks

          A node is a disk block. Wide nodes keep the tree shallow, so any key is a few seeks away.

          1970
          “Organization and Maintenance of Large Ordered Indices.”

          Bayer & McCreight The paper that introduced the B-tree

          02 · Memory

          Keep the tree, drop the disk's costs: pages in memory at memory speed, and optimistic latches that readers do not write.

          2018 – 2020
          “In-Memory Data Management Beyond Main Memory.”

          LeanStore, ICDE 2018 Leis, Haubenschild, Kemper, Neumann

          03 · NVMe

          Pages sized to one device read, a log per worker, and commits that wait on the transactions they depend on.

          2020 – 2026
          “What Modern NVMe Storage Can Do, And How To Exploit It.”

          Haas & Leis, VLDB 2023 With Rethinking Logging, SIGMOD 2020, and Autonomous Commit, SIGMOD 2025

          Put a better tree
          under your data.

          A fast embedded key-value store in Rust, with ACID transactions.

          Embedded in Rust

          A library, four files, no server. The engine does no I/O of its own: backends behind its storage traits do, over a file, the browser’s file system or memory.

          On Linux

          An optional io_uring read path, one ring per worker, which can run over O_DIRECT. A page miss submits one read on its own worker’s ring; other workers keep running.

          In the browser

          A WebAssembly build over the Origin Private File System. The web package lets tabs share one store through a single leader.