Key-Value Store Internals

Engines cluster into a few families. A hash index over an append-only log (Bitcask-like) optimizes point gets when all keys fit in RAM. An LSM stack (RocksDB, LevelDB, Cassandra storage) optimizes sustained writes with memtables and SSTables. A B+ tree / page engine (classic InnoDB-style) updates pages in place with a WAL—covered deeply in storage-engine notes; here we focus on the log-structured KV patterns interviews expect when they say “how does the node store keys?”

Across families the contract is the same: after a successful put, a crash must not lose the acknowledged value (under the stated fsync policy), a get must see a single modern value (or a defined version), and a delete must stay deleted until every older copy is gone.

PUT user:42 → value V
  1. append record {key, value, crc} to data.log  → offset 8192
  2. hash_index[user:42] = 8192
  3. fsync policy: every write | group commit | periodic

GET user:42
  1. offset = hash_index[user:42]   // miss → not found
  2. pread(data.log, offset) + verify crc
  3. return value

Limits:
  - all keys (not values) must fit in RAM
  - range scan ≈ full scan unless you add another structure
  - crash: rebuild index by scanning log, or keep index snapshots

This shape is excellent for high churn of values with a bounded key cardinality (session stores, feature flags). It collapses when you have tens of billions of tiny keys: the index itself becomes the capacity bottleneck. LSM designs push more index structure onto disk with sparse indexes and Bloom filters.

The write path separates acknowledge from organize. Durability is the WAL (and its fsync). Visibility is the memtable. Organization is flush + compaction. Confusing those three steps is how people mis-diagnose latency: a slow put is often WAL fsync or a write stall, not “compaction is evil” in the abstract.

PUT k → v (simplified LSM node)
  append(WAL, {k,v,seq})
  durable_flush_if_required()      // sync or group commit
  memtable.insert(k, v, seq)
  if memtable.size >= limit:
    immutable_memtables.push(memtable)
    memtable = new_empty()
    schedule_flush()

flush:
  write SSTable from immutable memtable (sorted)
  fsync table + manifest pointing to new file
  free WAL segments covered by this flush
  schedule compaction if L0 / debt thresholds hit

Sequence numbers (or hybrid timestamps) order versions. A reader merging memtables and SSTables always prefers the highest seq for a key. That merge cursor is the heart of get and of compaction.

Each SSTable carries a Bloom filter and a sparse index. Block cache holds hot data blocks; index/filter blocks are often pinned or cached aggressively because they are tiny relative to values.

Range scans cannot skip with Bloom filters (membership is per key). They merge iterators across memtables and overlapping files, which is why leveled layouts that limit overlap help scan latency even when point gets already looked fine.

A delete is a write: append a tombstone with a new sequence. Gets that see the tombstone return not-found. Compaction may drop covered older values immediately, but the tombstone itself must survive until every replica and every snapshot that could still read an older file has moved past it.

Engines that offer repeatable-read style snapshots implement light MVCC: readers pin a sequence number, and garbage collection refuses to drop versions newer than that pin. A stuck snapshot is a classic “disk never shrinks” bug.

Versions for key K (high seq wins):
  seq 10: put "a"
  seq 20: put "b"
  seq 30: tombstone

Reader at seq 25 → "b"
Reader at seq 35 → not found
Compaction after all readers > 30 → drop all of K

Too-early drop of tombstone + old SSTable still around
  → resurrect "b"  (split-brain of time, not of replicas)

write amplification is the price of reorganizing. Reading amplification is how many files/blocks a get touches. Space amplification is how many obsolete bytes linger. You cannot minimize all three at once; pick the axis your workload cares about (write-heavy ingest vs read-heavy serving).

Every record and data block should carry a checksum. A manifest (CURRENT / MANIFEST in LevelDB vocabulary) records which SSTables are live. Recovery: open the last consistent manifest, delete orphan files, replay WAL into memtables. Never advertise an SSTable until its bytes and the manifest update that references it are durable in the right order.

Engines expose iterators that heap-merge memtables and SSTables by key, then pick the winning sequence. With a snapshot sequence, any version newer than the snapshot is invisible—this is local MVCC, not distributed isolation. Long-lived iterators that pin sequences delay compaction garbage collection the same way stuck transactions do in page engines.

iterator for snapshot S:
  streams = [memtables..., sstables...]
  while next_key = min(stream.peeks):
    candidates = all versions of next_key with seq <= S
    pick highest seq among candidates
    if live value: yield
    if tombstone: skip
    advance all streams past next_key

Pinning S for hours ⇒ obsolete files cannot drop
  ⇒ disk usage climbs until the iterator closes