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
4.2 msto read one 4 KiB page
Disk~4 ms spinNVMe~100 µsRAM lookup~1 µs
Now on NVMe
01 / 05
A tree lookup whose pages are in RAM takes about a microsecond on one core.
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.
While that read is in flight, every worker that does not need that page keeps running.
Tree lookups check versions instead of locking, so readers rarely wait on each other.
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.
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.