Designing a Key-Value Store: Hash Tables, LSM Trees, and Compaction Strategies

Every database you use is built on a handful of fundamental storage primitives. Key-value stores are the most exposed version of those primitives: a map from bytes to bytes, with the complexity hiding in how you make that map fast, durable, and scalable. Redis, DynamoDB, RocksDB, LevelDB, and Cassandra all solve the same underlying problem with different tradeoffs baked in.

This article walks through those tradeoffs from first principles. We’ll implement a simplified version in TypeScript at each layer, then end with a concrete decision framework for production use.

The Problem: You Can’t Have It All

Before choosing a data structure, name the failure modes you’re designing against:

• Write amplification: writing more bytes to disk than the logical write size requires.
• Read amplification: reading more data from disk than a single value requires.
• Space amplification: storing more bytes on disk than the logical dataset size requires.

Every key-value store trades these three against each other. There is no configuration that minimizes all three simultaneously. Understanding which one you can afford to sacrifice determines the right architecture for your workload.

In-Memory Hash Tables

The simplest approach: a hash map in memory, with a durability log on disk.

class InMemoryKVStore {
  private map = new Map<string, Buffer>();
  private wal: WriteAheadLog;

  constructor(walPath: string) {
    this.wal = new WriteAheadLog(walPath);
  }

  async set(key: string, value: Buffer): Promise<void> {
    // Write to WAL first, then update in-memory map
    await this.wal.append({ op: 'set', key, value });
    this.map.set(key, value);
  }

  get(key: string): Buffer | undefined {
    return this.map.get(key);
  }

  async delete(key: string): Promise<void> {
    await this.wal.append({ op: 'delete', key, value: Buffer.alloc(0) });
    this.map.delete(key);
  }

  async recover(): Promise<void> {
    // Replay WAL on startup to rebuild in-memory state
    for await (const entry of this.wal.replay()) {
      if (entry.op === 'set') {
        this.map.set(entry.key, entry.value);
      } else {
        this.map.delete(entry.key);
      }
    }
  }
}

This is essentially what Redis does at its core, with significant additions for persistence options (RDB snapshots, AOF replication), data structures on top of raw bytes, and cluster coordination.

Where this breaks down: the entire dataset must fit in RAM. Once you exceed available memory, you need a spill strategy or a fundamentally different approach. Hash tables also fragment poorly on disk if you try to persist them directly, because they scatter data at arbitrary offsets rather than writing sequentially.

Write-Ahead Logs

The WAL implementation above deserves more detail because it’s load-bearing for every storage engine, not just in-memory ones.

import { createWriteStream, createReadStream } from 'fs';
import { Writable } from 'stream';

interface WALEntry {
  op: 'set' | 'delete';
  key: string;
  value: Buffer;
  checksum: number;
}

class WriteAheadLog {
  private stream: Writable;

  constructor(private path: string) {
    this.stream = createWriteStream(path, { flags: 'a' });
  }

  async append(entry: Omit<WALEntry, 'checksum'>): Promise<void> {
    const payload = this.serialize(entry);
    const checksum = crc32(payload);
    const frame = Buffer.concat([
      encodeUInt32(payload.length),
      payload,
      encodeUInt32(checksum),
    ]);

    return new Promise((resolve, reject) => {
      // fsync after each write for crash safety
      this.stream.write(frame, (err) => {
        if (err) return reject(err);
        (this.stream as any).fd !== undefined
          ? require('fs').fsync((this.stream as any).fd, resolve)
          : resolve();
      });
    });
  }

  async *replay(): AsyncIterable<WALEntry> {
    // Read entries back in order, verify checksums, skip corrupted tail
    const readable = createReadStream(this.path);
    for await (const entry of parseFrames(readable)) {
      if (verifyCRC(entry)) yield entry;
    }
  }
}

Two things matter here. First, the write must hit the WAL before the in-memory state changes. If the process crashes after writing to the WAL but before updating the map, recovery replays the write correctly. Reversed order means the write is permanently lost. Second, fsync is not optional for crash safety. Calling write() without fsync only guarantees the data reached the OS page cache, not disk. This distinction is responsible for a significant fraction of data loss incidents in systems that claim durability.

On-Disk Storage: LSM Trees

When the dataset outgrows memory, you need an efficient on-disk structure. The two dominant approaches are B-trees (used by PostgreSQL, MySQL InnoDB, SQLite) and Log-Structured Merge trees (used by RocksDB, LevelDB, Cassandra, DynamoDB’s storage layer).

LSM trees are optimized for write throughput at the cost of read amplification and background compaction overhead. The core mechanism:

1. Writes land in an in-memory sorted buffer called a MemTable.
2. When the MemTable reaches a size threshold (typically 64MB), it flushes to disk as an immutable Sorted String Table (SSTable).
3. Background compaction merges and garbage-collects SSTables over time.

interface SSTableEntry {
  key: string;
  value: Buffer | null; // null = tombstone (deletion marker)
  sequence: bigint;     // monotonically increasing write sequence number
}

class MemTable {
  // Red-black tree or skip list keeps keys sorted
  private entries = new Map<string, SSTableEntry>();
  private sizeBytes = 0;
  readonly flushThreshold = 64 * 1024 * 1024; // 64MB

  write(key: string, value: Buffer | null, seq: bigint): void {
    const prev = this.entries.get(key);
    if (prev) this.sizeBytes -= estimateSize(prev);
    const entry: SSTableEntry = { key, value, sequence: seq };
    this.entries.set(key, entry);
    this.sizeBytes += estimateSize(entry);
  }

  shouldFlush(): boolean {
    return this.sizeBytes >= this.flushThreshold;
  }

  // Returns entries sorted by key for SSTable flush
  sortedEntries(): SSTableEntry[] {
    return [...this.entries.values()].sort((a, b) =>
      a.key < b.key ? -1 : a.key > b.key ? 1 : 0
    );
  }
}

Reading from an LSM tree requires checking multiple SSTables. For a given key, you consult the MemTable first, then SSTables from newest to oldest, stopping at the first hit. Each SSTable maintains a bloom filter (probabilistic set membership) to skip files that definitely don’t contain the key.

class LSMStore {
  private memtable = new MemTable();
  private wal: WriteAheadLog;
  private sstables: SSTable[] = []; // ordered newest to oldest
  private sequence = 0n;

  async set(key: string, value: Buffer): Promise<void> {
    const seq = ++this.sequence;
    await this.wal.append({ op: 'set', key, value });
    this.memtable.write(key, value, seq);
    if (this.memtable.shouldFlush()) {
      await this.flushMemTable();
    }
  }

  async get(key: string): Promise<Buffer | null> {
    // Check MemTable first (most recent writes)
    const memEntry = this.memtable.get(key);
    if (memEntry !== undefined) {
      return memEntry.value; // null means deleted
    }

    // Check SSTables newest to oldest
    for (const sstable of this.sstables) {
      if (!sstable.bloomFilter.mightContain(key)) continue;
      const entry = await sstable.get(key);
      if (entry !== undefined) {
        return entry.value;
      }
    }

    return null;
  }

  private async flushMemTable(): Promise<void> {
    const entries = this.memtable.sortedEntries();
    const sstable = await SSTable.write(entries, this.nextSSTablePath());
    this.sstables.unshift(sstable); // prepend = newest first
    this.memtable = new MemTable();
    // WAL can be truncated after successful flush
    await this.wal.truncate();
  }
}

Compaction Strategies

Left unchecked, SSTables accumulate indefinitely. Read performance degrades (more files to check per query), space amplification grows (same key exists in multiple files), and tombstones never get garbage-collected. Compaction is the background process that fixes this by merging SSTables and discarding obsolete versions.

Size-Tiered Compaction

Group SSTables by size. When a tier accumulates enough files (typically 4), merge them into a single larger file and promote it to the next tier.

Tier 0: [64MB] [64MB] [64MB] [64MB]  -> merge
Tier 1: [256MB] [256MB] [256MB] [256MB] -> merge
Tier 2: [1GB] [1GB] ...

Tradeoffs: Write amplification is low because each byte gets rewritten fewer times. Space amplification is high because during a compaction, you temporarily hold both input and output files on disk simultaneously. Read amplification is moderate; at steady state, a key might appear in one file per tier.

This strategy works well for write-heavy, append-heavy workloads where the dataset is largely immutable (time-series, event logs, analytics).

Leveled Compaction

Maintain size-bounded levels. Level 0 holds fresh SSTables from MemTable flushes. Each subsequent level is 10x larger than the previous. Within Levels 1+, key ranges are non-overlapping: a given key exists in exactly one SSTable per level.

L0: [a-z][a-m][d-p]   (overlapping ranges, from recent flushes)
L1: [a-b][c-e][f-h][i-k]...[x-z]  (non-overlapping, total 10x L0 size)
L2: [a-a][b-b]...                  (non-overlapping, total 10x L1 size)

class LeveledCompactor {
  async compact(levels: SSTable[][]): Promise<void> {
    // Pick L0 file to compact into L1
    const l0File = this.pickL0Candidate(levels[0]);
    const l1Overlap = this.findOverlapping(l0File.keyRange, levels[1]);

    // Merge and write new non-overlapping L1 files
    const merged = await this.mergeFiles([l0File, ...l1Overlap]);
    const newL1Files = await this.splitByRange(merged, this.l1TargetSize);

    // Replace old files with new ones atomically
    await this.atomicReplace(levels, 0, [l0File], 1, l1Overlap, newL1Files);
  }

  private findOverlapping(range: KeyRange, level: SSTable[]): SSTable[] {
    return level.filter(
      (sst) => sst.maxKey >= range.min && sst.minKey <= range.max
    );
  }
}

Tradeoffs: Read amplification is minimal (at most one file per level for a point lookup). Space amplification is low (each key exists in at most two levels at any time). Write amplification is significantly higher because data gets rewritten many times as it moves through levels. RocksDB’s default write amplification under leveled compaction is roughly 10x to 30x the logical write size.

Dimension	Size-Tiered	Leveled
Write amplification	Low (5-10x)	High (10-30x)
Read amplification	Moderate (1 per tier)	Low (1 per level)
Space amplification	High (2x during compaction)	Low (1.1x steady state)
Best workload	Write-heavy, append-only	Read-heavy, mixed
Tombstone reclamation	Slow	Fast
Key range scans	Poor	Excellent

Production Considerations

Bloom filter sizing. A bloom filter with a 1% false positive rate requires roughly 10 bits per key. At 100 million keys per SSTable, that’s 125MB just for bloom filters in memory. Tune the bits-per-key parameter explicitly rather than using defaults. Too aggressive and you spill bloom filters to disk, adding an I/O round trip per SSTable check.

Compaction I/O throttling. Background compaction competes with foreground reads and writes for disk bandwidth. Without throttling, a compaction burst can push read latency from 1ms to 50ms. RocksDB exposes rate_limiter_bytes_per_sec; set it to 20-30% of your disk’s sequential write throughput as a starting point, then tune based on observed p99 latency during compaction windows.

Sequence number overflow. The sequence number in the LSM implementation above is a 64-bit integer. At 1 million writes per second, you exhaust a 64-bit counter in roughly 584,000 years. In practice, sequence numbers are scoped per MemTable flush, not globally. If you’re implementing from scratch, understand the scope before optimizing for compact representation.

Column family isolation. RocksDB exposes column families as logically separate LSM trees sharing a single WAL. Use them to isolate compaction pressure between hot and cold data. A frequently updated metadata column family should not share compaction bandwidth with a write-once log column family.

Crash consistency boundary. The WAL guarantees durability for the MemTable. But SSTable files written during a flush can be partially written if the process crashes mid-flush. Recovery needs to detect and discard partially written SSTables (validate the file-level checksum or presence of a completion marker) before replaying the WAL.

Choosing Between Redis, DynamoDB, and RocksDB-Based Stores

Start here: what does your workload look like in terms of dataset size, access latency requirements, and operational burden tolerance?

Is your dataset under 100GB and latency under 1ms is non-negotiable? Use Redis. The in-memory model is unbeatable for sub-millisecond reads. Accept that durability is probabilistic unless you enable AOF with fsync always, which halves your write throughput.

Is your dataset unbounded and you need managed operations? Use DynamoDB. It handles partitioning, replication, and compaction transparently. You pay in flexibility: access patterns must be declared up front via primary key and GSI design, and ad hoc scans are expensive. The storage layer is LSM-based internally, which is why write throughput scales better than read throughput at high volumes.

Do you need embedded storage inside your own process, with direct control over compaction and memory? Use RocksDB (or a library built on it: TiKV, CockroachDB’s storage layer, Cassandra’s SSTables). You get the full LSM internals exposed as configuration knobs, at the cost of operational complexity. Expect to spend non-trivial engineering time on tuning before hitting production throughput targets.

Are you building a time-series or event log where you append and never update? Size-tiered compaction with a columnar encoding (consider ClickHouse or Parquet-based storage) will outperform a general-purpose LSM store. The key insight is that general-purpose LSM trees are optimized for the case where old and new values for the same key coexist; if that never happens, the compaction overhead is pure waste.

Is your read pattern dominated by range scans rather than point lookups? Leveled compaction, B-trees, or a purpose-built sorted store (like FoundationDB’s ordered key-value layer) will serve you better than a write-optimized store. Bloom filters don’t help range queries; they only short-circuit point lookups.

The Mental Model

A key-value store is a machine for converting random writes into sequential I/O. The WAL converts in-memory writes to sequential disk writes. The MemTable sorts and batches those writes. SSTables store sorted immutable data that can be read with a single sequential scan. Compaction converts multiple overlapping SSTables back into fewer, non-overlapping ones.

Every design decision in this space is an answer to the same question: at what point in the write path do you pay the cost of sorting, and how often do you compact to reclaim the read performance you traded away?

Understanding that tradeoff is more useful than memorizing the defaults of any specific engine. The defaults are tuned for median workloads; your workload is not median.