LSM-Tree Storage Engine

The idea

I built this because I wanted to understand databases and storage engines below the level of calling PostgreSQL from an API. I had read about LSM trees, write-ahead logs, SSTables, compaction, and Bloom filters before, but there is a pretty big difference between knowing what those words mean and having to make all of them work together correctly.

So I started with a basic persistent key-value store and kept adding the pieces of an LSM-tree design one at a time.

What I’ve built

Writes are first appended to a write-ahead log and stored in memory before being flushed into immutable SSTables on disk. The SSTables use indexes and Bloom filters to avoid unnecessary reads, and the engine performs size-tiered k-way compaction with tombstone handling as data accumulates.

I added crash recovery, range scans, and randomized differential tests that run operations against both my engine and a std::map reference implementation and compare the results. I also built a benchmark harness so I could measure things like throughput and write amplification instead of just assuming an optimization made the engine faster.

The current implementation sustains around 113K buffered writes per second in my benchmark workload at roughly 2.86x write amplification.

Why I keep working on it

This is mostly a project for going deeper on systems work. I found that storage engines and databases intruiged me while building my other projects, since something like a fully managed storage engine abstracts away lots of complex, interesting engineering behind simply adding and searching for items. I found that storage engines involve lots of interesting systems-level concepts like disk I/O, durability, and memory usage that I find interesting.

There are still a lot of directions I want to take it, especially around concurrency, caching, compaction strategies, and more aggressive crash testing. Ip lan to keep coming back to whenever I want to understand another part of how real storage systems work.