Cascade — build a toy LSM Tree from scratch
Hands-on workshop going from zero to a working LSM Tree in Go — Rootconf Topical Edition on Databases
🎯 Target audience
- Engineers with moderate systems programming experience who want to understand how LSM Trees work internally — and why they are designed the way they are
- No prior database internals knowledge required, but comfort with a systems programming language is expected
📘 Workshop overview
This workshop goes in depth on how a Log-Structured Merge Tree works — the storage engine architecture behind RocksDB, LevelDB, Cassandra, and Couchbase. By the end, you will have written your own LSM Tree in Go that handles writes, reads, and deletions; persists data to disk in SSTable format; and runs a full tiered compaction pass across levels.
The central tension the workshop explores: what are you paying for reads when writes are relatively cheap? Every design decision in an LSM Tree is a response to that question. You will feel this tradeoff directly through a read IO counter that tracks how many IOs a read requires as data accumulates across levels.
✅ Learning outcomes
By the end of the workshop, participants will be able to understand:
- The write-optimised tradeoff at the heart of LSM Trees, and why it exists
- The on-disk layout of an SSTable and how it is written and read
- Why L0 is unsorted, and what that costs on the read path
- How tombstones work and why deletes are non-trivial
- How reads degrade as SSTables accumulate, and how compaction recovers them
- The tiered compaction algorithm: what it costs in write amplification, what it saves in implementation complexity
- What real systems like LevelDB and RocksDB extend from this foundation
🧩 Workshop stages
1. Setup
Get the skeleton repository running, understand the testing harness, and run the first milestone tests. Sets the feedback loop for the rest of the workshop.
2. Flush
Persist data to disk as an SSTable. Introduce the on-disk format and discuss encoding choices.
3. L0 Reads
Implement reads from L0. Introduce the read IO counter. See directly what a read costs when data is scattered across SSTables.
4. Checkpointing and Recovery
Handle restarts gracefully: checkpoint current state and recover it on startup.
5. Compaction in Isolation
Understand the compaction algorithm as a standalone problem — merging and sorting two SSTable streams, handling tombstones, producing a new SSTable.
6. Tiered Compaction End-to-End
Wire compaction into the engine. Implement a full tiered compaction pass across L0, L1, and L2. Observe the reduction in read IOs as compaction runs.
🛠 Tooling
Go, with third-party libraries for the in-memory map and disk encoding. A skeleton repository with sample data, a load generation harness, and per-milestone tests will be provided.
📚 Further reading
- O’Neill et al. (1996) — The Log-Structured Merge-Tree — the canonical paper that introduced LSM Trees. Read this after the workshop to see how much of what you built was already in the original design.
- LevelDB source code — a direct, readable implementation of the ideas from the workshop, and the direct ancestor of RocksDB. Every component will look familiar.
- RocksDB Wiki: Compaction — how a production system extends tiered and leveled compaction, and the operational tradeoffs between them.
About the instructor
Anirudh Rowjee, Software Engineer — Storage @ Couchbase.
How to attend this workshop
This workshop is open for Rootconf members and for Rootconf Database Edition ticket buyers
This workshop is open to 30 participants (in-person) & hybrid access for remote attendees. Seats for in-person participants will be available on first-come-first-served basis. 🎟️
Contact information ☎️
For inquiries about the workshop, contact +91-7676332020 or write to info@hasgeek.com.
