Benchmarking against sled and RocksDB

Step 11 of 12, and the store stops taking its own speed on faith. Ten steps in, every change was judged by one bar: the tests pass. They still do — all forty-six of them — but “correct” says nothing about “fast enough”, and this store makes choices with a price. It syncs the log on every write. It opens a table file on every lookup. It rebuilds every index from a full scan at startup. This step puts numbers on those choices: the same workloads run through tinylsm, sled, and RocksDB on one machine, timed by criterion — and the interesting results are the ones where tinylsm loses.

You are continuing from lsm-ch10 — the tinylsm crate with range scans. This step leaves src/lib.rs untouched and changes two things: Cargo.toml grows dev-dependencies, and one new file appears, benches/throughput.rs.

Why not a stopwatch

The obvious way to measure code is Instant around a loop:

use std::collections::BTreeMap;
use std::time::Instant;

fn main() {
    for run in 1..=5 {
        let start = Instant::now();
        let mut map = BTreeMap::new();
        for i in 0..100_000u64 {
            map.insert(i, i);
        }
        println!("run {run}: {:?}", start.elapsed());
    }
}

▶Run this in the Rust Playground

run 1: 75.873166ms
run 2: 63.302584ms
run 3: 63.287916ms
run 4: 62.346ms
run 5: 61.416916ms

Five runs of identical work, and no two agree — the first lands well above the rest, then the times settle but keep wandering. Nothing changed except the machine’s mood — CPU frequency scaling, cache state, whatever else was running. One timing is one draw from a distribution, and one draw tells you almost nothing. Worse, a single number is an invitation to rerun until the number looks right.

criterion takes the temptation away: it warms up, collects samples, fits a distribution, and reports an interval — the same every time you quote it, because the quoting is mechanical. Here is a benchmark of the same work, with the sample count and measurement time turned down so it finishes in half a second. Run as its own program, it needs one dependency:

[dependencies]
criterion = "0.8"

The real benchmark file below wraps its benchmarks in the criterion_group! and criterion_main! macros, which generate the program’s main; this one drives Criterion directly so it reads as a plain program:

use std::collections::BTreeMap;
use std::hint::black_box;
use std::time::Duration;

use criterion::{Criterion, Throughput};

fn main() {
    let mut c = Criterion::default();
    let mut group = c.benchmark_group("tiny");
    group.throughput(Throughput::Elements(10_000));
    group.sample_size(10);
    group.warm_up_time(Duration::from_millis(100));
    group.measurement_time(Duration::from_millis(300));
    group.bench_function("btree-insert", |b| {
        b.iter(|| {
            let mut map = BTreeMap::new();
            for i in 0..10_000u64 {
                black_box(map.insert(i, i));
            }
        });
    });
    group.finish();
}

▶Run this in the Rust Playground

tiny/btree-insert       time:   [5.4448 ms 5.4801 ms 5.5198 ms]
                        thrpt:  [1.8117 Melem/s 1.8248 Melem/s 1.8366 Melem/s]

The time line is not a stopwatch reading. It is a confidence interval: 451 to 460 µs, with 455 µs as the estimate criterion is prepared to defend. The thrpt line is the same interval turned into elements per second — it only appears because the benchmark declared Throughput::Elements(10_000), which is worth doing whenever an iteration does a known number of operations. black_box stops the optimiser from deciding the map is dead code and deleting the benchmark’s subject.

What gets measured

Two workloads, one per half of the store:

• writes — 100 puts with 16-byte keys and 64-byte values, into a fresh directory every iteration. The fresh directory is created in the benchmark’s untimed setup; the writes and the teardown are timed.
• gets — a store of 2,000 keys, built and compacted once before any timing, then 1,000 gets per iteration. The reads walk a fixed stride through the keys — the same deterministic pattern for every engine — and after compaction every key is answered from a table, so each get pays the bloom filter and the block read.

The write workload runs four times, because “the write returned” does not mean the same thing in every engine:

benchmark	what a returned write means
tinylsm	the record is on disk — sync_all before the call returns
sled	the insert is in sled’s log buffer; one flush at the end covers all hundred
rocksdb	the WAL entry has reached the operating system, not the disk
rocksdb-sync	as rocksdb, plus an fsync per put — tinylsm’s bar

That table is not a footnote to the numbers. It is the comparison: the engines are not selling the same durability, and the fourth row exists so the headline write numbers can be read at equal terms.

The Cargo.toml

Benchmarks are development dependencies — nobody who installs tinylsm should compile RocksDB to get a key-value store. The [[bench]] entry tells cargo that benches/throughput.rs has its own main, so cargo runs it as a program instead of feeding it to the test harness:

[package]
name = "tinylsm"
version = "0.1.0"
edition = "2024"

[dependencies]

[dev-dependencies]
criterion = "0.8"
rocksdb = "0.25"
sled = "0.34"
tempfile = "3"

[[bench]]
name = "throughput"
harness = false

rocksdb 0.25 bundles RocksDB 11.8.1 and compiles it from source — the first build takes a while. sled’s stable line is 0.34.7, untouched since October 2024; its 1.0 line is still alpha. Both are real, heavily used stores, which is the point of the comparison.

The benchmark file

This is benches/throughput.rs in full:

//! Throughput benchmarks: `tinylsm` against sled and RocksDB, on the
//! same machine, over the same workloads. Run with `cargo bench`.

use std::hint::black_box;

use criterion::{criterion_group, criterion_main, BatchSize, Criterion, Throughput};
use tempfile::TempDir;

use tinylsm::TinyLsm;

/// Distinct keys the read benchmark populates before measuring.
const KEYS: usize = 2_000;
/// Gets per measured iteration.
const READS: usize = 1_000;
/// Puts per measured iteration.
const WRITES: usize = 100;
/// Key length, in bytes.
const KEY_BYTES: usize = 16;
/// Value length, in bytes.
const VALUE_BYTES: usize = 64;

/// The `i`-th key: the decimal digits of `i`, zero-padded to 16 bytes,
/// so every engine sees exactly the same key shapes.
fn key(i: usize) -> [u8; KEY_BYTES] {
    let mut k = [b'0'; KEY_BYTES];
    let digits = format!("{i:05}");
    k[KEY_BYTES - digits.len()..].copy_from_slice(digits.as_bytes());
    k
}

/// A fresh 64-byte value.
fn value() -> Vec<u8> {
    vec![b'x'; VALUE_BYTES]
}

/// The `i`-th key the read benchmark touches: a fixed stride over the
/// populated keys, coprime with `KEYS`, so the thousand reads cycle
/// through every key before repeating — the same pattern for every
/// engine.
fn read_key(i: usize) -> [u8; KEY_BYTES] {
    key((i * 7_919) % KEYS)
}

fn writes(c: &mut Criterion) {
    let mut group = c.benchmark_group("writes");
    group.throughput(Throughput::Elements(WRITES as u64));

    // tinylsm syncs the log after every write — the durability bar step
    // 8 set — so each put pays its own fsync.
    group.bench_function("tinylsm", |b| {
        b.iter_batched(
            || TempDir::new().unwrap(),
            |dir| {
                let mut store = TinyLsm::open(dir.path().join("tinylsm.log")).unwrap();
                for i in 0..WRITES {
                    store.put(key(i).as_slice(), value()).unwrap();
                }
            },
            BatchSize::PerIteration,
        );
    });

    // sled batches: the inserts land in its log buffer, and one fsync at
    // the flush covers all hundred of them.
    group.bench_function("sled", |b| {
        b.iter_batched(
            || TempDir::new().unwrap(),
            |dir| {
                let db = sled::Config::new().path(dir.path()).open().unwrap();
                for i in 0..WRITES {
                    db.insert(key(i).as_slice(), value()).unwrap();
                }
                db.flush().unwrap();
            },
            BatchSize::PerIteration,
        );
    });

    // RocksDB's default write reaches the operating system, not the
    // disk: the WAL entry is written, nothing is fsynced.
    group.bench_function("rocksdb", |b| {
        b.iter_batched(
            || TempDir::new().unwrap(),
            |dir| {
                let db = rocksdb::DB::open_default(dir.path()).unwrap();
                for i in 0..WRITES {
                    db.put(key(i).as_slice(), value()).unwrap();
                }
            },
            BatchSize::PerIteration,
        );
    });

    // The same writes with sync on: one fsync per put, the durability
    // bar tinylsm holds on every write.
    group.bench_function("rocksdb-sync", |b| {
        b.iter_batched(
            || TempDir::new().unwrap(),
            |dir| {
                let db = rocksdb::DB::open_default(dir.path()).unwrap();
                let mut opts = rocksdb::WriteOptions::new();
                opts.set_sync(true);
                for i in 0..WRITES {
                    db.put_opt(key(i).as_slice(), value(), &opts).unwrap();
                }
            },
            BatchSize::PerIteration,
        );
    });

    group.finish();
}

fn gets(c: &mut Criterion) {
    let mut group = c.benchmark_group("gets");
    group.throughput(Throughput::Elements(READS as u64));

    // tinylsm: populated and compacted once, so every read lands in a
    // table and goes through the bloom filter and the block read.
    {
        let dir = TempDir::new().unwrap();
        let mut store = TinyLsm::open(dir.path().join("tinylsm.log")).unwrap();
        for i in 0..KEYS {
            store.put(key(i).as_slice(), value()).unwrap();
        }
        store.compact().unwrap();
        group.bench_function("tinylsm", |b| {
            b.iter(|| {
                for i in 0..READS {
                    black_box(store.get(read_key(i).as_slice()).unwrap());
                }
            });
        });
    }

    // sled: the same population, flushed, read back the same way.
    {
        let dir = TempDir::new().unwrap();
        let db = sled::Config::new().path(dir.path()).open().unwrap();
        for i in 0..KEYS {
            db.insert(key(i).as_slice(), value()).unwrap();
        }
        db.flush().unwrap();
        group.bench_function("sled", |b| {
            b.iter(|| {
                for i in 0..READS {
                    black_box(db.get(read_key(i).as_slice()).unwrap());
                }
            });
        });
    }

    // RocksDB: the same population, read back the same way.
    {
        let dir = TempDir::new().unwrap();
        let db = rocksdb::DB::open_default(dir.path()).unwrap();
        for i in 0..KEYS {
            db.put(key(i).as_slice(), value()).unwrap();
        }
        group.bench_function("rocksdb", |b| {
            b.iter(|| {
                for i in 0..READS {
                    black_box(db.get(read_key(i).as_slice()).unwrap());
                }
            });
        });
    }

    group.finish();
}

criterion_group!(benches, writes, gets);
criterion_main!(benches);

Three details carry the fairness of the whole comparison. iter_batched splits each write iteration into untimed setup (the fresh directory) and timed routine (the writes) — without it, directory creation would be billed to whichever engine creates the most files. The key and value shapes are fixed: 16-byte keys, 64-byte values, digits padded to a constant width, so no engine sees a friendlier workload. And the read stride i * 7_919 mod 2_000 is coprime with the key count, so the thousand reads visit every key before repeating — no engine gets a hot subset.

The numbers

cargo bench prints one block per benchmark. The medians from one run:

workload	tinylsm	sled	RocksDB	RocksDB, synced
100 puts	149 ms	8.6 ms	3.0 ms	5.3 ms
1,000 gets	14.8 ms	0.25 ms	0.55 ms	—

Same run, per operation: 1.49 ms per synced put against 86 µs for sled’s flushed batch and 30 µs for RocksDB’s unsynced write. On reads, 14.8 µs per get against 249 ns for sled and 551 ns for RocksDB.

The machine: Apple M2 Max, 64 GB of RAM, macOS 27.0.1, rustc 1.99.0, benchmarks compiled with optimisations. These are criterion medians from one run on one afternoon; rerunning moves the absolute numbers by tens of percent. The ratios are the signal. Do not compare your laptop against this table — benchmark your own workload on your own machine, which is what the rest of this step is for.

Where tinylsm loses, and why

Start with the writes, because the 1.49 ms put is suspicious. The store’s put does three things: append a 97-byte record, sync_all, update the memtable. Appending is microseconds. A probe settles where the rest goes — the same 97 bytes appended to a fresh file a hundred times, with the sync switched between off, data-only, and the store’s sync_all:

use std::fs::OpenOptions;
use std::io::Write;
use std::time::Instant;

/// Median over `runs` fresh files of the time to append `n` records,
/// syncing per `mode`: never, data only, or data and metadata.
fn probe(label: &str, mode: u8, n: usize, record: &[u8], runs: usize) {
    let mut times: Vec<u128> = Vec::new();
    for run in 0..runs {
        let path = std::env::temp_dir().join(format!("sync-probe-{mode}-{run}"));
        let start = Instant::now();
        {
            let mut f = OpenOptions::new()
                .create(true)
                .append(true)
                .open(&path)
                .unwrap();
            for _ in 0..n {
                f.write_all(record).unwrap();
                match mode {
                    1 => f.sync_data().unwrap(),
                    2 => f.sync_all().unwrap(),
                    _ => {}
                }
            }
        }
        times.push(start.elapsed().as_micros());
        std::fs::remove_file(&path).unwrap();
    }
    times.sort();
    println!("{}: {} µs for {n} appends", label, times[runs / 2]);
}

fn main() {
    // one tinylsm put record: 8 bytes of framing + 1 op + two 4-byte
    // lengths + a 16-byte key + a 64-byte value
    let record = vec![b'x'; 97];
    probe("no sync", 0, 100, &record, 10);
    probe("sync_data", 1, 100, &record, 10);
    probe("sync_all", 2, 100, &record, 10);
}

▶Run this in the Rust Playground

no sync: 774 µs for 100 appends
sync_data: 179492 µs for 100 appends
sync_all: 188517 µs for 100 appends

Ninety-seven bytes appended with no sync: about 8 µs each. With a sync: about 1.8 ms each, roughly 240 times more — and sync_data and sync_all land in the same place. That second result kills the tempting fix. Step 8 chose sync_all over sync_data because the log’s length lives in the file’s metadata and every append changes it; the probe says that on this filesystem the metadata half costs nothing measurable, and the sync itself is the price. No cheaper flavour of fsync is coming. The only real saving is fewer syncs — appending many records and syncing once, which is what sled’s flush does and what RocksDB’s WAL does between its periodic syncs. Group commit is the difference between 1.49 ms and 86 µs per write.

The honest complication: rocksdb-sync also fsyncs on every put and comes in at 5.3 ms for the same hundred writes — twenty-eight times faster than tinylsm at the same durability bar. What RocksDB does inside its write-ahead log to get there, this step is not going to guess at; what the probe establishes is that the fix on tinylsm’s side is batching, not a better sync call.

The reads tell a similar story with a different culprit. Every table lookup in this store opens the table file, seeks, reads one block, and closes — the file handle from the last lookup is gone. A bare probe of exactly that sequence — open a 174 KB file, seek, read 350 bytes, close — ran a thousand times in 13.8 ms on this machine. The whole get benchmark is 14.8 ms. The open is ninety-three percent of the read. The bloom filter is doing its job — a miss never opens the file — but every hit pays for a fresh handle, and sled and RocksDB keep their hot pages and handles in memory so their reads rarely leave userspace.

The fixes are all real: cached file handles, a block cache, the table footer that saves the startup scan. They are also the subject of the final step, which is about what a real database does that this one didn’t — so they stop here.

See it run

From the tinylsm directory:

cargo bench

The command first runs the library’s tests (ignored, in bench mode), then the benchmark:

Benchmarking writes/tinylsm
Benchmarking writes/tinylsm: Warming up for 3.0000 s

Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 13.7s, or reduce sample count to 30.
Benchmarking writes/tinylsm: Collecting 100 samples in estimated 13.739 s (100 iterations)
Benchmarking writes/tinylsm: Analyzing
writes/tinylsm          time:   [144.25 ms 148.97 ms 153.90 ms]
                        thrpt:  [649.75  elem/s 671.27  elem/s 693.24  elem/s]
Benchmarking writes/sled
Benchmarking writes/sled: Warming up for 3.0000 s
Benchmarking writes/sled: Collecting 100 samples in estimated 5.2835 s (600 iterations)
Benchmarking writes/sled: Analyzing
writes/sled             time:   [8.4111 ms 8.6185 ms 8.8278 ms]
                        thrpt:  [11.328 Kelem/s 11.603 Kelem/s 11.889 Kelem/s]
Found 3 outliers among 100 measurements (3.00%)
  3 (3.00%) high mild
Benchmarking writes/rocksdb
Benchmarking writes/rocksdb: Warming up for 3.0000 s
Benchmarking writes/rocksdb: Collecting 100 samples in estimated 5.1507 s (1700 iterations)
Benchmarking writes/rocksdb: Analyzing
writes/rocksdb          time:   [3.0017 ms 3.0247 ms 3.0494 ms]
                        thrpt:  [32.794 Kelem/s 33.061 Kelem/s 33.315 Kelem/s]
Found 5 outliers among 100 measurements (5.00%)
  2 (2.00%) high mild
  3 (3.00%) high severe
Benchmarking writes/rocksdb-sync
Benchmarking writes/rocksdb-sync: Warming up for 3.0000 s
Benchmarking writes/rocksdb-sync: Collecting 100 samples in estimated 5.2719 s (1000 iterations)
Benchmarking writes/rocksdb-sync: Analyzing
writes/rocksdb-sync     time:   [5.2552 ms 5.2929 ms 5.3335 ms]
                        thrpt:  [18.749 Kelem/s 18.893 Kelem/s 19.029 Kelem/s]
Found 5 outliers among 100 measurements (5.00%)
  4 (4.00%) high mild
  1 (1.00%) high severe

Benchmarking gets/tinylsm
Benchmarking gets/tinylsm: Warming up for 3.0000 s
Benchmarking gets/tinylsm: Collecting 100 samples in estimated 6.0275 s (400 iterations)
Benchmarking gets/tinylsm: Analyzing
gets/tinylsm            time:   [14.790 ms 14.847 ms 14.907 ms]
                        thrpt:  [67.084 Kelem/s 67.355 Kelem/s 67.612 Kelem/s]
Found 5 outliers among 100 measurements (5.00%)
  5 (5.00%) high mild
Benchmarking gets/sled
Benchmarking gets/sled: Warming up for 3.0000 s
Benchmarking gets/sled: Collecting 100 samples in estimated 6.2153 s (25k iterations)
Benchmarking gets/sled: Analyzing
gets/sled               time:   [248.00 µs 248.84 µs 249.70 µs]
                        thrpt:  [4.0049 Melem/s 4.0186 Melem/s 4.0322 Melem/s]
Found 6 outliers among 100 measurements (6.00%)
  2 (2.00%) low mild
  4 (4.00%) high severe
Benchmarking gets/rocksdb
Benchmarking gets/rocksdb: Warming up for 3.0000 s
Benchmarking gets/rocksdb: Collecting 100 samples in estimated 5.5964 s (10k iterations)
Benchmarking gets/rocksdb: Analyzing
gets/rocksdb            time:   [548.69 µs 551.45 µs 554.30 µs]
                        thrpt:  [1.8041 Melem/s 1.8134 Melem/s 1.8225 Melem/s]
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) low mild
  1 (1.00%) high mild

The warning on writes/tinylsm is criterion being honest on its own: each iteration takes about 150 ms — the hundred fsyncs — so 100 samples don’t fit in the default 5-second budget and criterion stretched the run to 13.7 s. The outlier lines are not errors; criterion compares each sample against the fitted distribution and reports the ones that don’t fit, which is how it keeps one slow interruption from dragging the median around.

criterion also writes its full reports — distributions, regression lines, comparisons with the previous run — to target/criterion/, where each benchmark gets an HTML page.

Where this lands in the repository

This step’s state is tagged lsm-ch11 in the examples repository:

git clone https://github.com/hackingwithrust/examples
cd examples/toy-database
git checkout lsm-ch11

The tag adds benches/throughput.rs and the dev-dependencies to Cargo.toml; src/lib.rs is byte-for-byte the one from lsm-ch10. If your build misbehaves, diff your files against the tag’s. The track overview keeps the step list current.

Next

One step left. What a real database does that we didn’t closes the track with the list this benchmark earned its place on: group commit, cached handles, the index-in-file footer, and the machinery — transactions, MVCC, crash recovery — that separates a teaching store from one you can run a service on.