Building CascadeStore: A Java LSM Engine

How I went from “I understand LSM trees” to shipping a working storage engine with 177k writes/sec

The problem with understanding databases

I thought I understood storage engines.

I’d read the papers. I could sketch an LSM-tree on a whiteboard. I knew the words: write amplification, compaction, bloom filters, SSTables. But when I tried to explain why RocksDB makes certain choices, or what actually happens when you write a million keys, the answers came up empty.

There’s a gap between knowing the concepts and understanding the reality. The only way across it is to build the thing yourself.

So I did. CascadeStore is a Log-Structured Merge-tree key-value engine written in Java 17 — complete with durable writes, three compaction strategies, off-heap memory management, and a full benchmark suite comparing it against RocksDB and LevelDB.

This isn’t a toy. It handles 177,000 writes per second at 1M keys. It recovers from crashes correctly. And it taught me more about storage systems than any paper ever could.

GitHub: https://github.com/ArnabKarmakar1108/CascadeStore

— -

First principles: Why LSM trees exist

Before we talk about CascadeStore, let’s understand the fundamental problem that LSM trees solve.

The write problem

Traditional B-tree databases do random writes. Every insert or update means:

1. Finding the right disk page

2. Reading it into memory

3. Modifying it

4. Writing it back

This is slow. Disks are optimized for sequential access, not random seeks. Even SSDs hate random writes at scale.

The LSM insight

What if we never updated data in place? What if writes were always sequential?

That’s the core LSM idea: batch writes in memory, append them to a sequential log, and periodically flush sorted runs to disk. Reads check the hot in-memory table first, then progressively older on-disk tables.

You trade one kind of work (random writes) for another (periodic merging of sorted files). For write-heavy workloads — event logging, time-series data, messaging queues — this trade-off wins decisively.

Disk access patterns

— -

The three amplifications

Every storage engine makes a deal with three devils: write amplification, read amplification, and space amplification.

1. Write amplification: How many bytes you write to disk per byte of user data. LSM trees rewrite data during compaction — a single user write might cause 10–20x disk writes over time.
2. Read amplification: How many disk structures you must check per lookup. In an LSM, a key might be in the memory table, or in any of several on-disk tables. Bloom filters help, but you still pay.
3. Space amplification: How much extra space you use for duplicate or dead data. Until compaction catches up, you might have three versions of the same key across different tables.

You can’t optimize all three simultaneously. CascadeStore lets you pick your poison through compaction strategies — we’ll get to that.

— -

Building blocks: The pieces before the whole

Before diving into CascadeStore’s architecture, let’s understand the four core components every LSM needs.

1. The MemTable

This is your write buffer — a sorted in-memory data structure that accepts all incoming writes. When it fills up, you freeze it and flush to disk.

Most implementations use a skip list or a B-tree. CascadeStore uses Java’s ConcurrentSkipListMap for keys, but stores value payloads off-heap in direct ByteBuffers.

Why off-heap? Because a million 1KB values sitting on the Java heap creates GC pressure that tanks throughput. Moving bulk data outside the heap keeps GC pauses low.

2. The Write-Ahead Log (WAL)

The MemTable is fast because it’s in RAM. But RAM is volatile. If the process crashes before a flush, you lose data.

The WAL is your durability guarantee: every write appends to a sequential log on disk. After a crash, you replay the WAL to rebuild the MemTable.

The tricky part is when to sync the log to disk. Sync after every write? Too slow. Sync never? Not durable. CascadeStore uses group commit: accumulate 1MB of writes, then fsync once. This batching is what makes the engine fast.

Write path flowchart

3. SSTables (Sorted String Tables)

When the MemTable fills, you flush it to disk as an immutable SSTable — a sorted file of key-value pairs.

Each SSTable has three pieces:

• .data — the actual key-value records

• .index — a sparse index mapping keys to file offsets

• .filter — a bloom filter for quick “definitely not here” checks

“Sparse” is important. You don’t index every key (that would use too much RAM). CascadeStore indexes one key every 16KB of data. Reads do a binary search in the index, then a short forward scan in the data file.

4. Compaction

Over time you accumulate many SSTables. Reads slow down because you have to check all of them.

Compaction merges overlapping tables into larger, sorted tables. It also removes deleted keys (tombstones) and expired TTL entries.

This is where the strategy choice matters. Merge aggressively and you get fewer tables (fast reads, slow writes). Merge lazily and you get fast writes but slow reads.

k-way merge of sorted files

— -

CascadeStore architecture: Putting it together

Now that we understand the pieces, here’s how CascadeStore orchestrates them:

Client put/get/delete
↓
┌─────────────────────────────────────┐
│ WAL append (group fsync)            │
│ MemTable put (off-heap values)      │
└─────────────────────────────────────┘
↓ (when full)
┌─────────────────────────────────────┐
│ Freeze MemTable → Immutable         │
│ FlushService → SSTable L0           │
│ Advance MANIFEST checkpoint         │
│ Purge old WAL segments              │
└─────────────────────────────────────┘
↓ (background)
┌─────────────────────────────────────┐
│ CompactionService merges SSTables   │
│ Removes tombstones & expired TTLs   │
│ Publishes new StorageVersion        │
└─────────────────────────────────────┘

Reads check layers in order: active MemTable → immutable MemTables → SSTables (newest first). Each SSTable check goes through bloom filter → sparse index → data file scan.

Recovery loads a MANIFEST file (checkpoint of which SSTables exist), opens all known tables, then replays only the WAL tail after the last flushed sequence number. No full log replay.

CascadeStore Architecture

— -

Design decisions that mattered

Here are the choices that moved CascadeStore from “demo” to “usable.”

1. Off-heap values: Keeping the GC quiet Early versions stored byte[] values directly in the skip list. At 1M keys with 1KB values, the JVM spent more time in GC than doing useful work. Solution: keys stay on-heap, values live in off-heap direct buffers managed by a slab allocator. Reads copy out only what the caller needs. GC pressure dropped, throughput went up.
2. WAL group commit: The 300x speedup The first 1M-key YCSB run did 50 ops/sec. Profiling showed fsync after every single WAL append. Fix: accumulate 1MB of writes, then sync. Forced syncs still happen at safety boundaries (MemTable rotation, shutdown), so you don’t lose durability. Result: 50 ops/sec → 15,000+ ops/sec on update workloads. This single change made the engine viable.
3. Sparse indexes: O(keys) → O(data size) Indexing every key in every SSTable consumed hundreds of megabytes of heap at 1M keys. The flush loop would OOM. SparseIndexPolicy emits one index entry every 16KB of data. Lookups do binary search in the (small) index, then a short forward scan — typically 3–5 records per YCSB lookup. Index memory usage dropped from O(number of keys) to O(data file size).
4. Storage versioning: Lock-free concurrent reads Compaction rewrites SSTables while readers are active. How do you do this safely? CascadeStore pins a StorageVersion snapshot: readers hold a reference to their starting SSTable list, writers publish a new version atomically after compaction. No global read lock on the hot path. Readers see a consistent view; writers make progress; nobody blocks anybody.

— -

Three compaction strategies, three workloads

Not every workload wants the same amplification profile. CascadeStore offers three strategies:

In YCSB benchmarks:

• Size-tiered wins pure write workloads (lower write amplification)

• Level-tiered wins pure read workloads (fewer files to check per lookup)

• Threshold is a good middle ground

The headline benchmark numbers use different strategies for write vs read tests — 177k writes/sec uses size-tiered, 93k reads/sec uses level-tiered. This is honest framing: pick the right tool for your workload.

— -

Observability: Watch the engine breathe

Metrics are off by default (benchmarks stay clean), but enabling them starts a tiny HTTP server with two endpoints:

• GET /metrics — Prometheus text format

• GET / — Live browser dashboard with auto-refresh

Prometheus Dashboard

Counters track:

• Read/write throughput

• Bloom filter probes and negatives

• Block cache hit rate

• Flush and compaction latency histograms

• Amplification gauges: read amp, write amp, files probed per lookup

You can watch compaction catch up after a heavy write burst. You can see bloom filter effectiveness change as the LSM deepens. It’s like attaching a profiler, but the engine is doing the profiling for you.

— -

Benchmarks: What the numbers say

All results are under benchmark/ in the repo. Hardware: 2× Xeon E5–2630 v3, 32GB RAM, local disk.

Headline at 1M keys (8 shards × 8 threads)

Throughput v/s Scale

vs RocksDB and LevelDB (compaction stress, 1 shard)

At 250k keys under a compaction-stress config (64MB MemTable, aggressive compaction):

CascadeStore sits in the same ballpark on mixed workloads. Native C++ engines lead on pure writes at smaller scales — which is expected. The point isn’t to beat RocksDB; it’s to build something that works correctly and understand why the numbers come out this way.

Comparison against RocksDB & LevelDB

Next steps

The engine is a learning project that happens to be fast — not a RocksDB replacement for every production workload. But the roadmap includes:

• Stronger crash recovery guarantees

• Optional async replication

• Compaction tuning (right now it’s a bit eager)

• Better memory pressure management

— -

Resources

• GitHub repo: https://github.com/ArnabKarmakar1108/CascadeStore

• LSM-tree paper: O’Neil et al., 1996

• Full benchmark suite: See benchmark/ directory in repo

• Architecture deep-dive: See ARCHITECTURE.md in repo

If you found this useful, follow me for more deep-dives on systems programming, databases, and learning by building.