KVLab: Investigating the Trade-offs Inside an LSM Storage Engine

Ajoy Deb Nath — Sun, 16 Aug 2026 16:41:03 +0000

What actually happens between put() and durable storage?

I’ve used databases for years without thinking much about what happens after calling put(). The application sends a write, gets an acknowledgement, and moves on. But what exactly happened before that acknowledgement? Something was written to a WAL, something was sitting in memory, eventually something was flushed to an SSTable, and somewhere in the middle there was an fsync().

I knew what all of those terms meant individually. I wasn't sure I understood how they fit together. That was what I wanted to figure out.

I started with a few basic questions:

How does the database recover after a crash?
If data eventually goes into SSTables, why write it to a WAL first?
Why are SSTables immutable?
What problem does compaction actually solve?
How much work does a Bloom filter really save?
Where does read amplification come from?

Instead of answering those questions only by reading LevelDB or RocksDB, I decided to build a small storage engine myself.

That became KVLab, an LSM-based key-value store written in Java. The LSM implementation ended up being roughly 1,300 lines, along with a benchmark harness that records the results as CSV files.

I wasn't trying to build a production database, or even a particularly fast one. I wanted to implement the pieces myself and see what actually changed when I added them.

And some of the results were not what I expected.

The shape of the engine

Write path:

Read path:

Each record is stored as [4-byte key length][4-byte value length][key][value]. At the end of the file, there’s a Bloom block, an index block, and a 32-byte footer containing their offsets and the AKV2 magic number.
Deletes are handled with tombstones. Since SSTables are immutable, you can't just go back and remove a record. Instead, a delete writes a record with a sentinel value length, which tells the reader that the key has been deleted.
There’s also no block cache or background compaction yet. Compaction runs directly on the writer thread. That turned out to matter more than I expected later.

WAL, MemTable, SSTable — and why that order

The write ordering in KVLab is simple:

WAL append → MemTable update → return to caller

The order matters. Before telling the caller that a write succeeded, the WAL needs to have the write on disk. The MemTable is then updated so the write can be served from memory instead of touching an SSTable for every key.

SSTables are immutable, which also means readers never have to deal with a file being modified underneath them.

Recovery is straightforward because of this:

KVLab's WAL is deliberately simple. Each record is stored as a text line, with values Base64-encoded:

PUT user1 QWpveQ==
DELETE user1

I kept it this way because I wanted to be able to cat the WAL while debugging. It's easy to inspect and easy to reason about. It's also not particularly efficient, which shows up later in the storage benchmarks.

The same immutability that makes SSTables easier to read also means deletes need special handling. If key A exists in an older SSTable, we can't go back and remove it. Instead, the newer layer gets a tombstone.

The read path checks newer data first, so it sees the tombstone before reaching the older value and treats the key as deleted. The old record stays on disk until compaction removes it.

The problem immutability creates

Immutable files make writes simpler because nothing has to rewrite an existing file. The downside is that the files start to pile up:

SSTable 1  SSTable 2  SSTable 3  ...  SSTable 20

For a hit, we might get lucky and find the key in a recent file. A miss is different. To know that a key doesn't exist, we may have to check every SSTable. With twenty files, that's twenty files to check and potentially twenty unnecessary reads.

So the first problem is simple: how do we make searching each SSTable cheaper?

Two ways to make one file cheaper to search

The index

Instead of scanning key1, key2, key3, … key10000 looking for a match, we keep a sorted key-to-offset table at the end of the file and binary-search it.

KVLab's index is dense: there is one entry for every key, stored as [4-byte key length][8-byte offset][key bytes].

The Bloom filter

Before searching the index, we can ask a cheaper question: could this key be in the file?

If the filter says no, we can skip the file completely. If it says yes, the key might be there, so we continue with the index lookup.

A Bloom filter never gives a false negative, but it can give a false positive. KVLab uses a plain BitSet, with 10 bits per key by default and 3 hash functions derived from a 31-polynomial hash using double hashing (h1 + i·h2).

Both the index and Bloom filter are stored at the end of the SSTable. That makes them easy to find from the footer, but they also add to the size of every file.

That's where the next set of measurements gets interesting.

Experiment 1 — does the index actually help?

I built the same key set two ways: v1 with records only, and v2 with the Bloom filter, index, and footer. I tested 100, 1K, and 10K keys, with 2,000 probe keys per run — half hits and half misses, using a deterministic seed.
One detail turned out to matter a lot: I created a new SSTableReader for every probe, so each lookup opened the file from scratch, matching what KVLab's real lookup path does.
That wasn't how the benchmark started. My first version opened one reader and reused it for all 2,000 probes. The v2 miss cost came out to roughly zero bytes read from the SSTable, which delighted me for about ten minutes. Then I realized I was measuring a reused reader, while the actual lookup path opens a fresh reader each time.
The whole benchmark was flattering itself.
It's a good reminder that a number without a proper baseline isn't really a measurement. It's just a result you haven't investigated yet.

Results, 2,000 probes each:

Keys	Reader	File size	Bytes/miss	Read amp (miss)	Miss p50	Miss p99
100	v1 scan	2,180	2,180	1.00	0.22 ms	0.38 ms
100	v2 index	4,150	1,938	0.47	0.019 ms	0.054 ms
1,000	v1 scan	23,780	23,780	1.00	2.15 ms	2.81 ms
1,000	v2 index	43,976	20,164	0.46	0.055 ms	0.146 ms
10,000	v1 scan	257,780	257,780	1.00	21.5 ms	26.4 ms
10,000	v2 index	469,226	211,414	0.45	0.44 ms	0.83 ms

v1's miss amplification is exactly 1.00 at every size, which is what a full scan means: to prove absence you read the whole thing.

The headline is the latency column. At 10K keys, a miss goes from 21.5 ms to 0.44 ms — about fifty times faster at the median, thirty at p99.

Now look at the bytes column, because that's where I stopped being pleased with myself. v2 read 211 KB per miss. v1 read 258 KB. That's an 18% improvement in bytes for a 50× improvement in time. Those two numbers don't line up, and the gap is the actual finding: v1's scan walks the file record by record — two channel reads per record, 10,000 records, ~20,000 syscalls. v2 does four reads: the footer, the Bloom block, the index block, and then (if Bloom says maybe) one record. Same order of magnitude of bytes, three orders of magnitude fewer operations.

I had been thinking about read amplification as a byte ratio, because that's how it's usually defined. For this workload the byte ratio was almost the least interesting thing about it.

Why v2 still reads 211 KB

The v2 file is larger than the v1 file — 469 KB versus 258 KB for the same 10,000 records. Where did 211 KB come from?

Bloom block (10 bits/key)      12,516 B    2.7%
Index block (dense, 1/key)    198,894 B   42.4%
Block headers + footer             40 B
                              --------
                               211,450 B

211,450 is, to the byte, the difference between the two files. It's also — again to the byte — what v2 reads on every cold open, because SSTableReader's constructor eagerly loads the footer, then the Bloom block, then the index block, before anyone has asked it a question.

So the honest statement of the result is that my index is nearly as large as my data, and I load all of it before I look at anything. The Bloom filter is 2.7% of the file and does real work. The index is 42% of the file and I pay for all of it to look up one key.

The obvious next step is to make the index sparse: one entry per block of records instead of one entry per record. You binary-search to the right block, then scan the records inside it. LevelDB uses this general approach with block indexes and restart points.
I'd read about sparse indexes before and filed the idea under "optimization." After this experiment, I don't think of it that way anymore. The index worked. I just hadn't considered what it cost to load before it could actually help a lookup.

Experiment 2 — how much does the Bloom filter help?

At 8, 10, 12, and 16 bits per key, I ran 2,000 probes per key-count — 100, 1,000, 10,000 — using keys that are definitely absent, and counted how many the filter rejected outright versus how many slipped through. The internal check passed first: bloom_rejected + false_positives = 2000 in every single row. Whatever else turned out to be wrong, the counting was right.

At 10,000 keys:

Bits/key	Bloom block	Rejected	False positives	Actual FP	Theoretical FP (k=3)
8	10,016 B	1,946	54	2.70%	3.06%
10	12,516 B	1,969	31	1.55%	1.74%
12	15,016 B	1,980	20	1.00%	1.08%
16	20,015 B	1,985	15	0.75%	0.50%

The trend is right — more space, fewer false positives and 8→12 bits halves the FP rate for 5 KB more disk, tracking theory closely. At 16 bits it doesn't: measured 0.75% against a predicted 0.50%, half again worse than it should be. At 100 keys the numbers are noise (10 bits/key scored worse than 8, 2.95% vs 2.55%) with FP counts in the teens out of 2,000 probes there isn't enough signal to say anything. But 10K keys with 15 false positives isn't noise, and 16 bits is the one row that misses.

My first guess was the hash. hash() is a 31-polynomial over the key bytes, and the second hash is seeded from the first, so h1 and h2 aren't independent. At 8 bits per key the filter is saturated enough that mediocre hashing hides inside the collision rate; at 16 bits there's room for the hash quality to show.

But there's a bigger problem sitting in plain sight, and I only noticed it writing this up: NUM_HASHES is hardcoded to 3. The optimal number of hash functions for a Bloom filter is (m/n)·ln2 — about 7 for 10 bits per key, about 11 for 16. At k=3 and 16 bits/key I'm paying double the space of the 8-bit filter for a 3.6× improvement, when properly tuned it should be closer to 60×:

Bits/key	FP at k=3	FP at optimal k
10	1.7%	0.8% (k=7)
16	0.5%	0.05% (k=11)

I bought more space and left most of the return on the table, because I tuned one parameter and never touched the one it depends on. My "theoretical" column agreed with my measurements, which is exactly why I never questioned it, the formula was parameterized with the same wrong k. A theory that only ever predicts what you already built isn't a check on anything.

What the numbers don't show

The bytes_saved_per_miss column in my Bloom CSV is negative. Not zero — negative, by a few bytes, growing with file size.

That's not a bug in the filter. It's the cold-open problem from Experiment 1 again. Bloom rejection prevents a data-block read, which is a genuine win over a v1 scan. It does not prevent the metadata read, because the reader loads the Bloom block and the index block before mightContain() gets a chance to say no. The with-Bloom configuration reads slightly more than the without-Bloom one, because the Bloom block itself has to be loaded.

So on a cold open, the filter I built to avoid I/O is, strictly in bytes, a small net cost. It saves time (no scan), and it would save real I/O in a reader that loaded the filter first and the index only on a maybe. Mine doesn't — a filter can only skip the work that happens after it runs, and in KVLab, most of the expensive work happens before.

Experiment 3 — why compaction matters

This one is the cleanest result in the project, and I didn't have to argue with it at all.

I built 20 L0 SSTables, 500 keys each, same key set in every file with different values, simulating twenty flushes that all overwrote the same range, then ran 500 probes for keys that exist in none of them, before and after an L0→L1 merge:

before:  L0 L0 L0 L0 L0 ... L0   (20 files)
after:   L1                       (1 file)

	Before	After
Files probed per miss	20.0	1.0
Bytes read per miss	200,780	10,039
p50 latency	0.67 ms	0.034 ms
p95	0.85 ms	0.044 ms
p99	1.03 ms	0.054 ms

Twenty times fewer bytes, twenty times faster, and the ratio is exactly 20 because the cost is exactly linear in file count: 200,780 ÷ 20 = 10,039, which is precisely one file's Bloom block plus index block. Every one of those twenty opens loaded metadata, asked the filter, got told no, and closed. Nineteen of them were pure overhead.

One caveat worth stating plainly: all twenty files held the same 500 keys, so this is compaction's best case. Twenty files with disjoint key ranges wouldn't shrink to one file's worth of data. But the file-count effect — one metadata load per file per miss — doesn't depend on overlap at all. That part generalizes.

What I took from this is that I'd been filing compaction under housekeeping — reclaim space, drop tombstones, tidy up. That's the side effect. The main effect is that it's the only thing standing between you and a read path that gets linearly slower every time you flush. I'd built it as garbage collection and it measured out as a read-path mechanism.

What all of this cost

I spent three experiments optimizing reads. The fourth asks what the bill was: 1,000 puts of 100-byte values, into the LSM store and into a Bitcask-style single-append-file store, same API, same data.

Store	Logical bytes	WAL	SSTables	Total on disk	Ratio
Bitcask (binary)	106,890	—	115,890	115,890	1.08×
LSM	106,890	148,890	135,307	284,197	2.66×

The LSM took 2.5× the disk of the append-only store for identical data. The WAL alone is larger than the user's data. I worked out where every byte went, and it's all explicable:

WAL, per record: "PUT " (4) + key (6.89 avg) + " " (1)
  + Base64(100-byte value) (136) + "\n" (1)
  = 148.89 B  <- 1.49x the logical bytes, from Base64 alone

SSTable, per key: header (8) + key (6.89) + value (100) = 114.89
  + index entry (4 + 8 + 6.89) = 18.89
  + bloom (10 bits) = 1.25
  = 135.03 B

Base64 is a 4/3 expansion, so my decision to keep the WAL human-readable cost 36 bytes per record — 36 KB across the run — before counting the PUT prefixes. And the WAL is never truncated after a flush, so at the end of the workload the engine is storing a complete second copy of everything it already wrote to SSTables. That's not an inherent LSM cost. That's a feature I didn't build.

The last row of that table needs a warning label. lsm_after_puts and lsm_after_compaction show identical totals, which looks like compaction did nothing. It's the opposite: the L0 threshold is 4, so compaction had already been running throughout the inserts. By the time the workload finished, there were zero L0 files and five L1 files — there was nothing left to merge.

One more caveat this table needs: it measures final footprint, not write amplification. Every byte that compaction wrote and then deleted is invisible here. Real write amplification counts cumulative bytes written — WAL appends, flushes, every rewrite — and I have no counters for that. Calling this "write amplification" would have been the most flattering possible misreading of my own data. It was labelled exactly that in an earlier version of the repo, which is how I know.

It's also the cleanest statement of a pattern that showed up everywhere in this project: every optimization moves the cost somewhere else. The index made lookups fast and made the file 82% bigger. The Bloom filter added 12 KB and 2.7% to every cold open. The WAL bought crash recovery and 1.4× the disk. There was no step where something got better and nothing got worse.

What KVLab isn't

It's an educational storage engine, not a database. Specifically missing:

WAL truncation or rotation after flush — the log grows without bound
Real write-amplification counters (bytes written, not bytes remaining)
Background compaction — it runs inline, on the writer's thread
Any concurrency story worth the name
A block cache, or any cache
A read path that loads Bloom before index
Crash testing beyond reopen-and-replay; no torn-write or partial-fsync injection
Production durability semantics — fsync happens every 10 records, so a crash can lose the last nine

Any one of those would disqualify it from real use. I'm listing them because the numbers above are only worth something if you know exactly which conditions produced them.

So What's Next?

A few things are still bothering me.

1. If the index were sparse, how much of that 42% goes away? One index entry per block instead of per key. I can predict the file gets smaller; I can't predict what it does to hit latency, because now every lookup scans within a block.

2. What is the actual write amplification when I count every byte written to disk? The 2.66× I measured doesn't tell me that yet. I need to separate WAL writes, memtable flushes, and compaction rewrites to see how much physical I/O each layer contributes.

3. How much of the cold-open cost is the open itself? If the reader kept the Bloom filter resident and loaded the index lazily, would misses stop touching the index at all? That's the experiment that would tell me whether Bloom filters are worth what everyone says they're worth — in my engine, I still don't know.

Closing

Before building KVLab, I could explain what a WAL, Bloom filter, and LSM tree were. What I didn't really understand was what they cost.

Building the thing changed that.

Adding an index made lookups cheaper, but made the SSTable much bigger and more expensive to open. The Bloom filter could save a lot of unnecessary work, but only if I actually let the reader use it before loading everything else. Compaction cleaned up old files, but also meant rewriting data that had already been written.

That ended up being the useful part of the project for me. Not implementing the individual components, but measuring what each one actually changed and then dealing with the result when it didn't match what I expected.

Three of my four experiments contradicted something I believed when I started.

That ratio feels about right.

Code, benchmark harness, and raw CSV results: KVLab on Github. Everything above reproduces with mvn test && mvn -q -Pbenchmark test-compile exec:java.

DEV Community: Ajoy Deb Nath