Imagine you need to ingest 500,000 writes per second into a storage engine. Your P99 write latency must stay under 2ms. Traditional B-tree storage engines - the kind powering PostgreSQL and MySQL - achieve this by performing random I/O: for every write, they find the exact page on disk, read it, modify it, and write it back. At 500k writes/second, that’s 500k random disk seeks per second. Even on NVMe SSDs capable of 500k IOPS, you’re already at the physical limit, with zero headroom for reads, compaction, or replication.

The insight behind the Log-Structured Merge-tree (LSM tree) is deceptively simple: never write to the middle of a file. Turn all writes into sequential appends. Sequential disk I/O on modern hardware is 10x to 100x faster than random I/O - a 7200 RPM HDD can handle 150 sequential MB/s but only 150 random seeks/second. By batching writes in memory and flushing them as immutable sorted files, an LSM tree engine converts the hardest problem (random writes) into the easiest operation (sequential writes).

The tradeoff is elegant but painful: reads get harder. When you write a key multiple times, older versions scatter across multiple files at different levels. Reading that key requires checking the current memory buffer, then potentially every file on disk until you find a fresh enough version. We spend compaction I/O (merging files in the background) to reclaim read performance. The entire design philosophy is: shift I/O cost from writes (synchronous, user-facing) to compaction (asynchronous, background).

Systems like RocksDB, LevelDB, Apache Cassandra, and HBase all bet their durability and performance on this architecture. At Facebook, RocksDB processes over 100 trillion operations per day across their storage fleet. Understanding how the memtable, sstable, bloom filter, and compaction interact is foundational knowledge for anyone building at scale.

Requirements and Constraints

Functional Requirements

• PUT(key, value) - write or update any key-value pair
• GET(key) - retrieve the latest value for a key, or signal not-found
• DELETE(key) - logically delete a key using a tombstone marker
• Range scans: SCAN(start_key, end_key) - return all key-value pairs in sorted order
• Atomic single-key operations (no cross-key transactions initially)

Non-Functional Requirements

• Write throughput: 100k-500k writes/second on commodity hardware
• Write P99 latency: under 5ms
• Read P99 latency: under 10ms for point lookups (bloom filter assisted)
• Durability: writes acknowledged only after WAL append (no data loss on crash)
• Storage efficiency: space amplification below 2x in steady state
• Background compaction must not starve foreground reads/writes

Design Constraints

• Data exceeds available RAM (cold storage scenario - 10TB on disk, 32GB RAM)
• Write-heavy workload: 80% writes, 20% reads (typical for time-series, logging, audit)
• Keys are arbitrary byte strings up to 4KB; values up to 1MB
• Single-node design first, sharded horizontally as a second layer

High-Level Architecture

The LSM tree organizes storage into a hierarchy of levels. Level 0 (L0) receives freshly flushed data from memory. Deeper levels contain progressively more compacted, sorted data. The key invariant: at any level below L0, no two sstable files contain overlapping key ranges.

The write path is simple: every write appends to an in-memory memtable (and a write-ahead log for durability). When the memtable reaches a size threshold (typically 64MB), it becomes immutable and gets flushed as a new L0 sstable. Background compaction threads continuously merge L0 files into L1, then L1 into L2, maintaining sorted order at each step.

The read path is more complex: we check the active memtable first, then any immutable memtables being flushed, then every level from L0 to Ln, consulting bloom filters to skip files that definitely don’t contain the key, and doing binary search into index blocks of files that might.

The MemTable Write Buffer

The MemTable is the heart of the write path. It’s an in-memory ordered data structure - typically a Red-Black tree or a skip list - that accepts all incoming writes and maintains them in sorted key order. Sorted order is essential because when we flush the memtable to disk, we need to emit key-value pairs in sorted sequence to produce a valid sstable.

Red-Black Tree vs Skip List

Both structures support O(log n) insert, delete, and lookup. The choice comes down to concurrency characteristics. Red-Black trees require exclusive locking during rebalancing rotations. Skip lists can be made lock-free using compare-and-swap operations on individual node pointers, enabling higher concurrent write throughput. RocksDB defaults to a skip list memtable; it also supports a HashSkipList variant for pure point-lookup workloads.

import sortedcontainers
import threading
from dataclasses import dataclass
from typing import Optional
import time

TOMBSTONE = b'\x00TOMBSTONE\x00'

@dataclass
class MemTableEntry:
    key: bytes
    value: bytes  # TOMBSTONE sentinel for deletes
    sequence: int  # monotonically increasing write sequence number

class MemTable:
    def __init__(self, size_limit_bytes: int = 64 * 1024 * 1024):
        # SortedDict provides O(log n) ops with sorted iteration
        self._data: dict[bytes, MemTableEntry] = {}
        self._sorted_keys: list[bytes] = []
        self._lock = threading.RWLock() if hasattr(threading, 'RWLock') else threading.Lock()
        self._size_bytes = 0
        self._size_limit = size_limit_bytes
        self._sequence = 0

    def put(self, key: bytes, value: bytes) -> bool:
        """Returns True if memtable is now full and should be flushed."""
        with self._lock:
            self._sequence += 1
            entry = MemTableEntry(key=key, value=value, sequence=self._sequence)
            old = self._data.get(key)
            if old is None:
                self._size_bytes += len(key) + len(value) + 16  # overhead
                # insert into sorted position
                import bisect
                bisect.insort(self._sorted_keys, key)
            else:
                self._size_bytes += len(value) - len(old.value)
            self._data[key] = entry
            return self._size_bytes >= self._size_limit

    def delete(self, key: bytes) -> bool:
        return self.put(key, TOMBSTONE)

    def get(self, key: bytes) -> Optional[bytes]:
        entry = self._data.get(key)
        if entry is None:
            return None
        if entry.value == TOMBSTONE:
            return None  # key was deleted
        return entry.value

    def scan(self, start_key: bytes, end_key: bytes):
        """Yield (key, value) pairs in sorted order within range."""
        import bisect
        lo = bisect.bisect_left(self._sorted_keys, start_key)
        hi = bisect.bisect_right(self._sorted_keys, end_key)
        for key in self._sorted_keys[lo:hi]:
            entry = self._data[key]
            if entry.value != TOMBSTONE:
                yield key, entry.value

    def flush_iterator(self):
        """Yield all entries in sorted key order for SSTable flush."""
        for key in self._sorted_keys:
            yield key, self._data[key]

    @property
    def size_bytes(self) -> int:
        return self._size_bytes

Write-Ahead Log (WAL)

Before any write touches the memtable, it must be appended to the Write-Ahead Log - a sequential append-only file on disk. If the process crashes before the memtable is flushed, we replay the WAL to reconstruct the memtable on restart. This is the only synchronous disk write in the hot path, and it’s sequential, so it’s fast.

import struct
import os
import zlib

class WAL:
    """Write-Ahead Log: append-only sequential file for crash recovery."""

    RECORD_HEADER_FMT = '>IIQ'  # crc32, length, sequence_number
    RECORD_HEADER_SIZE = struct.calcsize(RECORD_HEADER_FMT)

    def __init__(self, path: str):
        self._path = path
        self._fd = open(path, 'ab', buffering=0)  # unbuffered for durability

    def append(self, key: bytes, value: bytes, sequence: int) -> None:
        payload = struct.pack('>H', len(key)) + key + struct.pack('>I', len(value)) + value
        crc = zlib.crc32(payload) & 0xFFFFFFFF
        header = struct.pack(self.RECORD_HEADER_FMT, crc, len(payload), sequence)
        record = header + payload
        self._fd.write(record)
        self._fd.flush()  # fsync for true durability (or use O_DSYNC)
        os.fsync(self._fd.fileno())

    def replay(self):
        """Replay WAL records for crash recovery."""
        with open(self._path, 'rb') as f:
            while True:
                header_bytes = f.read(self.RECORD_HEADER_SIZE)
                if len(header_bytes) < self.RECORD_HEADER_SIZE:
                    break
                crc, length, sequence = struct.unpack(self.RECORD_HEADER_FMT, header_bytes)
                payload = f.read(length)
                if zlib.crc32(payload) & 0xFFFFFFFF != crc:
                    break  # truncated or corrupt record - stop here
                key_len = struct.unpack('>H', payload[:2])[0]
                key = payload[2:2+key_len]
                val_len = struct.unpack('>I', payload[2+key_len:6+key_len])[0]
                value = payload[6+key_len:6+key_len+val_len]
                yield sequence, key, value

Flush Triggers

The memtable flush is triggered when any of these conditions are met:

• Size threshold: memtable reaches the configured limit (default 64MB in RocksDB)
• Time threshold: a write-idle timeout (prevents data sitting in memory too long)
• WAL size threshold: the WAL file grows beyond a limit, preventing unbounded log replay time on restart

When flush triggers, the active memtable becomes immutable - it accepts no new writes but can still serve reads. A new empty memtable is created immediately so writes continue without pausing. The immutable memtable is flushed to disk by a background thread, producing a new L0 sstable.

The SSTable Format