Skip to content
Arjit Kulkarni
02Storage Engines

LSM-KV

An embedded key-value store, written from the disk up
Role
Solo — design, implementation, testing
Context
Personal systems project
Stack
C++17CMakeGoogleTestThreadSanitizerLinux perfCI
Source
arjitkulkarni/lsm-kv
01  The problem

A C++17 storage engine with skiplist memtables, Bloom-filtered SSTables, leveled compaction and crash recovery — built to understand durability by having to implement it.

A key-value store is easy to write and hard to trust. The interesting problems are the ones that only appear under concurrency and failure: does a write survive a crash mid-flush, does a reader see a torn state, and where does throughput actually go when several threads contend for the same memtable.
02  Approach
  1. 01

    Built the engine behind an abstract DB interface with RAII throughout, so lifetimes and ownership are enforced by the type system rather than by discipline.

  2. 02

    Layered the read path: skiplist memtables in front, Bloom-filtered SSTables behind, leveled compaction to keep read amplification bounded, and an O(1) LRU block cache on top.

  3. 03

    Made writes durable and fast at once with write-ahead logging and group-commit, then sharded memtables by hash to cut contention on the write path.

  4. 04

    Separated concurrent read and write paths and implemented crash recovery from the WAL as a first-class code path, not an afterthought.

  5. 05

    Validated it the way storage engines have to be validated: fault injection, ThreadSanitizer, GoogleTest coverage, CI automation, benchmarking and Linux profiling.

03  Outcome

  • A working embedded store with durability guarantees that survive injected faults.

  • Concurrency bottlenecks identified through profiling rather than guesswork.

  • A test harness — fault injection plus TSan plus CI — that catches regressions in the paths that matter.

LRU block cache
O(0)LRU block cache
Group-commit writes
WALGroup-commit writes
Race detection in CI
TSanRace detection in CI

Concepts applied

  • Memory management
  • Synchronisation
  • File I/O
  • Caching & indexing
  • Persistence
  • Storage-engine design
All work