Building an LSM-Tree So I Could Kill It

#database #java #showdev #distributedsystems

I ran a burst of 400 writes against a storage engine I'd built, then sent the JVM a SIGKILL at write 200 — no graceful shutdown, no final flush. I restarted it from the same disk volume and counted how many of the 200 acknowledged writes came back.

Some didn't. That was the correct outcome, not a bug — but it took building the test to know that for certain instead of assuming it.

This is Aegis: a from-scratch implementation of the LSM-tree storage engine underlying Apache Cassandra's write path — CommitLog, MemTable, SSTable, compaction — in Java 21, no framework dependencies.

Repo: github.com/joshuabvarghese/aegis

git clone https://github.com/joshuabvarghese/aegis
cd aegis
docker compose run --rm demo

The goal wasn't to build a production database. It was to build a database where every correctness claim had a test that could fail — not "it should be durable," a script that kills the process and checks.

The write and read paths

                         WRITE PATH
                         ──────────
  client.write(key, col, value)
        │
        ▼
  ┌─────────────────────────────────────────────────────────┐
  │  CommitLog  (durability before anything else)           │
  │  *.clog  │  [Length:4B][Record:nB][CRC32C:4B]           │
  │  fsync every 200ms (PERIODIC mode, Cassandra's default) │
  └─────────────────────┬───────────────────────────────────┘
                        │ CommitLogPosition returned
                        ▼
  ┌─────────────────────────────────────────────────────────┐
  │  MemTable  (in-memory write buffer)                     │
  │  ConcurrentSkipListMap<PartitionKey, Row>               │
  │  Sorted by Murmur3 token                                │
  │  Flush threshold: 8MB                                   │
  └─────────────────────┬───────────────────────────────────┘
                        │ threshold crossed → async flush
                        ▼
  ┌─────────────────────────────────────────────────────────┐
  │  SSTable  (immutable, sorted, on-disk)                  │
  │  ├── Data.db       sorted partition data                │
  │  ├── Index.db      sparse partition index               │
  │  ├── Filter.db     Bloom filter (1% FPP)                │
  │  ├── Statistics.db metadata + CommitLog position        │
  │  └── Summary.db    sampled index summary                │
  └─────────────────────────────────────────────────────────┘

                          READ PATH
                          ─────────
  client.read(key)
        │
        ├─► 1. MemTable          ConcurrentSkipListMap.get()   O(log n)
        └─► 2. SSTables          newest → oldest
                ├─ Bloom filter  mightContain(key)?  zero I/O on miss
                ├─ Summary index binary search → index file range
                ├─ Index.db scan → data file offset
                └─ Data.db read  → deserialise partition

                        COMPACTION (background)
                        ───────────────────────
  Every 2s: group SSTables into size buckets
            ≥4 SSTables of similar size → k-way merge → new SSTable
            tombstones past GC grace period → purged

Each component solves exactly one problem. The CommitLog exists so the MemTable is allowed to be volatile. The MemTable exists so writes don't touch disk on the hot path. SSTables are sorted and immutable specifically so a Bloom filter and a sparse index are possible at all. Compaction exists to undo the fragmentation the first three decisions create.

With the paths laid out, the interesting work was deciding what not to build — and catching the one decision I got wrong.

Three decisions, and the one that broke silently

Sparse index instead of dense. A dense index costs roughly 32 bytes per partition. At 10 million partitions, that's 320MB — larger than the 256MB heap budgeted for the whole engine, index included. Cassandra's sparse index samples one entry per 64KB of data instead of per key, which brings the same 10M-partition index under 1MB. The lookup cost changes from O(n) to O(sample size): binary search over the summary, then a short linear scan.

Bloom filter checked before the index, not after. At 1% false-positive rate, 99% of lookups for keys that don't exist are answered without touching a disk file. For anything with a high miss rate — a cache-miss path, for example — this ordering is the single biggest lever in the read path, and also the cheapest: a handful of hashes versus an index seek plus a data read.

STCS and LCS, as two real strategies rather than one plus a comment. Every compaction strategy trades off two of three properties: write amplification, read amplification, space amplification. Size-Tiered Compaction (STCS, Cassandra's default) groups SSTables by size regardless of key range — cheap to run, but a point read may check every SSTable on disk, since ranges overlap freely. Leveled Compaction (LCS, RocksDB and LevelDB's default) enforces non-overlapping ranges within a level, so a read touches at most one SSTable per level, paid for by rewriting data every time a level compacts into the next.

Aegis runs both behind the same CompactionStrategy interface, switchable with an environment variable. scripts/compare-compaction-strategies.sh runs the same workload against both and prints the measured difference in SSTables-opened-per-read and bytes-written-during-compaction.

Here's where an assumption broke. My first pass at LCS expanded "which next-level SSTables overlap the one being pushed down" in a single hop, then merged. It compiled. It passed a quick manual check. It was wrong: pulling in one overlapping table can widen the merged range enough to newly overlap a second table that didn't intersect the original range at all. Miss that second expansion and the non-overlap invariant the whole level depends on breaks silently — no exception, no crash, just a level that's quietly no longer leveled.

The fix, expandToOverlapClosure(), keeps expanding until a full pass adds nothing new, which is the actual termination condition. There's now a dedicated test that runs real writes and compactions through the full engine and asserts no two SSTables in the same level ever overlap — because a manual check had already told me it was fine once, and it wasn't.

Testing the durability claim, not just stating it

The claim: any write acknowledged by /write with an HTTP 200 will survive a crash. For anything backed by an in-memory structure, that's a claim worth being suspicious of.

scripts/chaos-crash-test.sh writes a burst of rows against a live engine, sends the container a hard SIGKILL mid-burst, restarts it from the same volume, and checks whether every acknowledged write comes back after CommitLog replay. Two configurations, two different honest outcomes, matching Cassandra's real commitlog_sync trade-off:

=== PERIODIC mode (fsync every 200ms) ===
Acknowledged before kill: 200
Recovered after restart:  XXX
Lost in fsync window:     XXX   ← expected, not a failure

=== BATCH mode (fsync before every ack) ===
Acknowledged before kill: 200
Recovered after restart:  200
Lost:                     0     ← required; non-zero here is a real bug

(Run ./scripts/chaos-crash-test.sh yourself to fill in the exact PERIODIC numbers for your machine before publishing — the script prints them directly, and quoting your own real run is the whole point of this section.)

PERIODIC losing data in that window isn't a flaw — every production Cassandra cluster runs this way deliberately, trading a small bounded loss window for 3–10x the throughput of BATCH. What matters is that the engine can say exactly which writes were at risk and why, rather than asserting durability without a way to check it.

The JUnit suite runs the same skepticism under concurrency: dozens of virtual threads doing simultaneous writes, same-key contention, and reads during writes, asserting zero lost writes, zero torn values, zero exceptions.

Numbers

JMH benchmarks, run in the same container image used everywhere else in the project. Reproducible with ./scripts/update-benchmark-numbers.sh — nothing here is hand-picked.

Benchmark	What it measures	Avg time/op	Throughput
`benchmarkBloomFilterMiss`	Definitive miss, zero disk I/O	0.02 µs/op	50.6 ops/µs
`benchmarkBloomFilterHit`	Probable hit check	0.0244 µs/op	39.1 ops/µs
`benchmarkMurmur3Token`	Partition key hashing	0.00782 µs/op	130 ops/µs
`benchmarkEngineReadMemTable`	ConcurrentSkipListMap.get()	0.0265 µs/op	32.9 ops/µs
`benchmarkCommitLogAppend`	Full FileChannel write, PERIODIC	1.48 µs/op	0.669 ops/µs
`benchmarkFullEngineWrite`	CommitLog → MemTable, end-to-end	2.45 µs/op	0.404 ops/µs
`benchmarkRowMerge`	Compaction reconciliation per row	0.0202 µs/op	50.9 ops/µs
`benchmarkTombstonePurge`	Tombstone GC-grace check	1.58 µs/op	0.677 ops/µs

The gap that matters in practice: a Bloom filter miss resolves in 0.02µs with zero disk I/O; a full engine write takes 2.45µs. That two-orders-of-magnitude difference is the entire case for checking the filter before anything else touches disk — it isn't an optimization on top of the read path, it's most of the read path's speed budget.

What's still simplified

The current LCS implementation writes a single output SSTable per compaction round instead of splitting into fixed-size files, and picks the largest over-budget SSTable to push down rather than using a persistent round-robin cursor, the way LevelDB does. Both are documented as known simplifications in LeveledCompactor's class javadoc, and both are fine at this project's data volumes. Neither would survive a real production dataset without revisiting — a single compaction thread merging one table at a time stops being sufficient once the write rate and dataset size grow past what this project was built to test.

What killing it 400 times actually taught me

PERIODIC mode losing writes inside its fsync window isn't a bug. It's the system behaving exactly as specified. The real bug would have been claiming durability without a script that could prove otherwise — the same way the single-hop LCS overlap check would have shipped clean if nothing had ever forced it to run against a real, growing dataset.

Building Aegis didn't teach me how to prevent data loss. It taught me how to know, with certainty, when I'm allowing it — and that the two are not the same skill.

Aegis is MIT-licensed: github.com/joshuabvarghese/aegis. The repo includes the interactive shell, the JMH benchmark suite, the chaos-test script, and a live dashboard that polls a running instance's stats.