Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables

Executive Summary & Key Takeaways

Imagine running a bustling diner during the morning rush. When orders fly across the counter at ten tickets per second, your line cook cannot stop to open a leather-bound, alphabetically indexed recipe archive, erase an entry on page 412, write down the new order, and slide the heavy book back onto the shelf. Doing so would bring breakfast service to an immediate halt. Instead, the cook writes the ticket on a countertop notepad and clips a carbon copy onto an order spindle. When the notepad fills up, an assistant gathers the pages, organizes them by station, and files them into permanent pantry bins during quiet moments.

This physical workflow mirrors the exact operational principle behind Log-Structured Merge-trees (LSM-trees). Traditional relational storage engines like PostgreSQL and MySQL InnoDB rely on B-Trees, which mutate disk pages in-place. While in-place mutation provides efficient point reads, it transforms write workloads into random I/O operations that degrade flash memory endurance and saturate storage controllers. Systems like RocksDB, Apache Cassandra, ScyllaDB, and Google Bigtable resolve this bottleneck by treating non-volatile storage as an append-only medium. They ingest updates into memory buffers, persist sequential logs for durability, and asynchronously consolidate immutable sorted files in the background.

• Sequential Write Superiority: LSM-trees turn random application writes into high-speed sequential I/O by buffering writes in memory (MemTables) and flushing them sequentially to disk as Sorted String Tables (SSTables).
• Durability via Write-Ahead Logging: Before mutating volatile RAM structures, every write appends to an on-disk Write-Ahead Log (WAL), providing crash-resilience with minimal write latency.
• Trade-Off Profile (RUM Conjecture): LSM-trees prioritize Write throughput at the expense of Read amplification (checking multiple SSTables) and Space amplification (holding duplicate revisions and deleted tombstones until compaction runs).
• Probabilistic Filtering: Embedded Bloom filters and block indexes eliminate redundant storage reads by confirming key absence before the storage engine initiates a single disk block read.
• Compaction Governs System Health: Background compaction algorithms (Leveled vs. Size-Tiered) continually balance write amplification against read tail latency and disk footprint.

1. Architectural Foundations & Mechanics

To understand why modern data engineering relies so heavily on LSM-trees, one must first look at the physical realities of solid-state drives (SSDs) and spinning disks. Operating systems and storage hardware handle sequential writes orders of magnitude faster than random updates. On an NVMe SSD, random in-place updates trigger internal garbage collection routines, block erasures, and flash controller wear that slash write throughput and spike P99 latencies.

The Log-Structured Merge-tree, first formalized by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996, abandons in-place page overwrites entirely. An LSM storage engine coordinates four foundational subsystems: the Write-Ahead Log (WAL), the in-memory MemTable, immutable on-disk Sorted String Tables (SSTables), and background Compaction routines.

The Write Path: From Memory to Persistent Storage

When an application issues a Put(Key, Value) or Delete(Key) request to an engine like RocksDB or Cassandra, the write path follows two parallel steps:

1. Write-Ahead Log (WAL) Append: The update appends to an open log file on disk using sequential writes. Because the write is strictly append-only, the operating system kernel completes the transfer rapidly without seeking or reading existing blocks. If the server loses power a millisecond later, the database recovers uncommitted state by replaying this log sequentially from the last known checkpoint.
2. MemTable Ingestion: Simultaneously, the engine inserts the key-value pair into an in-memory sorted data structure called the MemTable. Cassandra implements this with a concurrent skip-list (ConcurrentSkipListMap in the JVM), while RocksDB relies on an optimized C++ inline skip-list backed by an arena memory allocator. The skip-list maintains keys in sorted lexicographical order using atomic compare-and-swap (CAS) operations, avoiding coarse-grained table locks and allowing concurrent threads to write without serialized lock contention.

Once the active MemTable reaches its configured size threshold (typically between 32MB and 256MB), the engine marks it as immutable, provisions a fresh active MemTable along with a new WAL segment, and dispatches a background flush thread. The flush thread reads the immutable MemTable sequentially and writes its contents to persistent storage as a Level 0 (L0) Sorted String Table (SSTable). Once written, the obsolete WAL segment is safely unlinked.

The Anatomy of an SSTable

An SSTable is an immutable, ordered file structured into fixed-size blocks (typically 4KB to 64KB). Because its contents are immutable, the storage engine never modifies an SSTable once flushed to disk. It consists of several distinct sections:

• Data Blocks: Contiguous key-value pairs stored in sorted order. Keys often use prefix delta encoding (storing only the byte difference between adjacent keys) to minimize byte size and improve CPU cache density.
• Filter Block (Bloom Filter): A compact probabilistic bit array calculated during the flush. It allows the read engine to evaluate whether a key definitely does not exist in the SSTable without touching the data blocks.
• Index Block: Contains the offsets and sizes of every data block alongside each block's terminal key. When querying a key, the engine performs a binary search over the index block to pinpoint the single data block that could contain the target.
• Footer: A fixed-size trailer at the end of the file containing magic verification bytes and handles (byte offset and length descriptors) pointing to the Index and Meta Index blocks.

The Read Path and Multi-Version Reconciliation

Because keys are never overwritten in-place, reading a key requires inspecting multiple layers of the system. An LSM point lookup (Get(Key)) proceeds sequentially down the storage hierarchy:

1. Inspect the active, mutable MemTable. If the key exists, return the latest value immediately.
2. Inspect any immutable MemTables waiting to flush to disk.
3. Inspect on-disk SSTables from newest to oldest.

Without optimization, searching across dozens of SSTables would trigger catastrophic read amplification, requiring dozens of random disk reads per point query. To prevent this, two critical mechanisms intervene:

• Bloom Filters: Before opening an SSTable's data block, the engine hashes the target key through the SSTable's Bloom filter. If the filter returns false, the key is guaranteed not to exist in that file, and the engine bypasses it entirely.
• Block Cache: Uncompressed data blocks reside in an LRU or 2Q block cache in memory, satisfying warm reads directly from RAM without kernel page cache translation overhead.

Deletions via Tombstones

Because SSTables are immutable, a Delete(Key) operation cannot physically erase bytes from an existing file. Instead, the engine writes a special record called a tombstone. The tombstone travels through the standard write path: it enters the WAL, lands in the MemTable, and eventually flushes to disk inside an SSTable.

During read operations, if the engine encounters a tombstone with a higher sequence number than an older data record, it treats the key as non-existent. Physical space reclamation only occurs later during background compaction, when the tombstone and the superseded record are merged and discarded.

Compaction Mechanics: Leveled vs. Size-Tiered

As new SSTables accumulate, duplicate keys, obsolete values, and tombstones consume disk space. Point reads must check more files, and range scans must merge more iterators. Compaction is the background process that reads multiple SSTables, performs a merge-sort across their contents, discards superseded versions and expired tombstones, and outputs new, consolidated SSTables. Storage engines generally choose between two primary compaction strategies:

2. Mathematical Modeling & Resource Bounds

Evaluating an LSM-tree requires quantifying the fundamental trade-offs formalized by the RUM Conjecture (Read, Update, Memory/Space trade-off). An engine can optimize two of these dimensions, but only at the expense of the third.

1. Write Amplification Factor (WAF)

Write Amplification measures the ratio of total bytes written to persistent storage versus the net bytes submitted by the user application:

In Leveled Compaction with a level size multiplier $T$ (typically $T = 10$) and depth $L$:

When an SSTable from level $L_i$ merges into $L_{i+1}$, its key range overlaps with on average $T$ files in $L_{i+1}$. Thus, the engine reads and rewrites the data alongside $T$ times its volume. Factoring in the initial WAL write and the $L_0$ flush, the worst-case Write Amplification across all levels is expressed as:

For a 1TB database with $T = 10$ and $L = 4$, $\text{WAF}$ often ranges between 15 and 30. While this consumes NVMe write cycles, it converts chaotic random application writes into sequential disk streaming, delivering raw write throughput that exceeds B-Trees by an order of magnitude.

2. Read Amplification Factor (RAF) and Bloom Filter Sizing

Read Amplification represents the number of physical storage blocks read to satisfy a single logical point get:

Without probabilistic filtering, a point query targeting a non-existent key must inspect every single candidate SSTable across every level, resulting in an unbearable read penalty:

To curb this penalty, Bloom filters provide an immediate test for set membership. Given $n$ keys and a filter allocated $m$ bits of memory, using $k$ independent hash functions, the false-positive probability $p$ is modeled as:

Minimizing $p$ with respect to the number of hash functions yields the optimal configuration:

Substituting $k$ back into the probability equation provides the required bit allocation per key ($b = m/n$) for a target false-positive rate $p$:

For a standard production target of $p = 0.01$ (a 1% false-positive rate), the system must allocate:

By sizing Bloom filters to approximately 10 bits per key, $99\%$ of negative file inspections are avoided entirely. With leveled compaction, where levels $L \ge 1$ guarantee non-overlapping key boundaries, the expected number of SSTables read per point lookup drops to:

For $L = 5$ and $p = 0.01$, $\mathbb{E}[\text{SSTables Read}] \le 1 + 0.05 = 1.05$ files, effectively eliminating read amplification for point queries.

3. Memory Resource Envelope Calculation

A production LSM storage engine requires memory for more than just raw cache data. The total memory consumption $M_{\text{total}}$ is governed by:

Consider a concrete production scenario:

• Total Unique Keys ($n$): 1,000,000,000 (1 Billion)
• Average Key Size: 32 bytes; Average Value Size: 128 bytes (Raw user payload: ~160 GB)
• Block Size: 4 KB ($4,096$ bytes)
• Target Bloom False Positive Rate ($p$): $0.01$ ($10$ bits/key)
• MemTable Configuration: 4 write buffers of 128 MB each (1 active, 3 immutable flushing)

Applying our formulas:

1. MemTable Footprint: $4 \times 128\text{ MB} = 512\text{ MB}$.
2. Bloom Filter Memory: $\frac{10^9 \text{ keys} \times 10 \text{ bits}}{8 \text{ bits/byte}} = 1.25 \times 10^9 \text{ bytes} \approx 1.164\text{ GiB}$.
3. Index Blocks in RAM: With 160 GB of data stored in 4 KB blocks, the dataset spans $\frac{160 \times 10^9}{4096} \approx 39,062,500$ blocks. Storing a 40-byte index entry (key prefix + offset handle) per block requires: $39.06 \times 10^6 \times 40\text{ bytes} \approx 1.56\text{ GB}$.
4. Total Structural Baseline Memory: $512\text{ MB} + 1.164\text{ GB} + 1.56\text{ GB} \approx 3.236\text{ GB}$ of RAM strictly for metadata and write buffers before assigning a single byte to the uncompressed Block Cache.

Python Resource Envelope Calculator

The following script models memory footprints, amplification boundaries, and baseline allocations for any production LSM deployment:

"""
LSM-Tree Production Resource Envelope and Capacity Calculator.
Computes memory budgets, Bloom filter bit allocations, and amplification bounds.
"""

from dataclasses import dataclass
import math

@dataclass(frozen=True)
class LSMResourceProfile:
    total_keys: int
    raw_payload_bytes: float
    bloom_filter_bytes: float
    index_block_bytes: float
    memtable_pool_bytes: int
    min_structural_ram_bytes: float
    write_amplification_leveled: float
    space_amplification_leveled: float

def calculate_lsm_resource_envelope(
    total_keys: int,
    avg_key_bytes: int,
    avg_value_bytes: int,
    target_bloom_fpr: float = 0.01,
    block_size_bytes: int = 4096,
    memtable_size_bytes: int = 128 * 1024 * 1024,
    memtable_count: int = 4,
    level_fanout_ratio: int = 10,
) -> LSMResourceProfile:
    """
    Calculates exact memory allocations and amplification parameters for an LSM storage engine.
    """
    if target_bloom_fpr <= 0 or target_bloom_fpr >= 1:
        raise ValueError("Bloom filter FPR must satisfy 0 < FPR < 1")

    # Raw payload volume
    record_bytes = avg_key_bytes + avg_value_bytes
    total_payload_bytes = total_keys * record_bytes

    # Bloom Filter calculations: m = - (n * ln(p)) / (ln(2)^2)
    bits_per_key = -math.log(target_bloom_fpr) / (math.log(2) ** 2)
    total_bloom_bits = total_keys * bits_per_key
    bloom_filter_bytes = total_bloom_bits / 8.0

    # Index Block calculations: 1 index record per block
    # Assuming standard index entry overhead: key prefix + varint offset + varint size
    estimated_blocks = math.ceil(total_payload_bytes / block_size_bytes)
    index_entry_overhead_bytes = avg_key_bytes + 16
    index_block_bytes = estimated_blocks * index_entry_overhead_bytes

    # MemTable buffering
    memtable_pool_bytes = memtable_size_bytes * memtable_count

    # Baseline operational memory (excluding dynamic block cache)
    min_structural_ram = bloom_filter_bytes + index_block_bytes + memtable_pool_bytes

    # Leveled Compaction estimation
    # Depth L = ceil(log_T(TotalData / Level1_Capacity))
    # Assuming Level 1 capacity scales to 10x memtable size
    level_1_capacity = memtable_size_bytes * 10
    if total_payload_bytes > level_1_capacity:
        depth = math.ceil(math.log(total_payload_bytes / level_1_capacity, level_fanout_ratio))
    else:
        depth = 1

    # WAF leveled ~ 1 (WAL) + 1 (L0 flush) + (T * depth)
    waf_leveled = 2.0 + (level_fanout_ratio * depth)

    # Space Amplification Factor: SAF = 1 + (1 / (T - 1))
    saf_leveled = 1.0 + (1.0 / (level_fanout_ratio - 1))

    return LSMResourceProfile(
        total_keys=total_keys,
        raw_payload_bytes=total_payload_bytes,
        bloom_filter_bytes=bloom_filter_bytes,
        index_block_bytes=index_block_bytes,
        memtable_pool_bytes=memtable_pool_bytes,
        min_structural_ram_bytes=min_structural_ram,
        write_amplification_leveled=waf_leveled,
        space_amplification_leveled=saf_leveled,
    )

if __name__ == "__main__":
    profile = calculate_lsm_resource_envelope(
        total_keys=1_000_000_000,
        avg_key_bytes=32,
        avg_value_bytes=128,
        target_bloom_fpr=0.01,
        block_size_bytes=4096,
        memtable_size_bytes=128 * 1024 * 1024,
        memtable_count=4,
        level_fanout_ratio=10,
    )
    print("--- LSM Storage Engine Sizing ---")
    print(f"Payload Size:             {profile.raw_payload_bytes / (1024**3):.2f} GiB")
    print(f"Bloom Filter Memory:      {profile.bloom_filter_bytes / (1024**3):.3f} GiB")
    print(f"Index Memory Footprint:   {profile.index_block_bytes / (1024**3):.3f} GiB")
    print(f"MemTable Buffers:         {profile.memtable_pool_bytes / (1024**2):.0f} MiB")
    print(f"Min Structural RAM:       {profile.min_structural_ram_bytes / (1024**3):.3f} GiB")
    print(f"Predicted Leveled WAF:    {profile.write_amplification_leveled:.1f}x")
    print(f"Predicted Leveled SAF:    {profile.space_amplification_leveled:.2f}x")

3. Production Trade-offs & Benchmarks

Architecting an infrastructure platform requires balancing hardware boundaries against data access patterns. Choosing between an in-place B-Tree, a Leveled LSM-tree, or a Size-Tiered LSM-tree defines the ceiling of your system's performance.

Comprehensive Engine Architecture Comparison

Memory and Block Allocation: Contiguous vs. Segmented Layouts

Internally, LSM engines encounter hardware bottlenecks when allocating memory buffers and organizing storage blocks. The design choice between contiguous memory buffers and segmented pointer chains dictates CPU cache efficiency and fragmentation behavior.

Write Key Entropy and Throughput Divergence

A subtle operational pitfall in LSM systems is the performance divergence caused by key entropy. Storage operators often assume compaction overhead is static, but key distribution patterns drastically change performance.

• Low-Entropy Keys (Monotonic Timestamps, Sequential IDs): When incoming keys are sequential (such as auto-incrementing integers or time-series timestamps), all writes append to the rightmost boundary of the key space. When an SSTable flushes from the MemTable, its key range $[K_{\min}, K_{\max}]$ does not overlap with existing SSTables at higher levels. RocksDB can perform a trivial move: it bumps the file metadata to the next level without reading, merge-sorting, or rewriting existing blocks. As a result, the Write Amplification drops from 20x to near 1.0x, data compression engines achieve ratios exceeding 5:1, and disk bandwidth saturation remains minimal.
• High-Entropy Keys (Random UUIDv4, Cryptographic Hashes): When incoming keys are uniformly distributed hashes, every single SSTable spans an arbitrary slice of the entire keyspace. During compaction, an SSTable chosen from level $L_i$ overlaps with nearly all $T$ files in $L_{i+1}$. The compaction worker must pull all $T$ files into RAM, decompress them, merge-sort their contents, recompress the blocks, and write them back down to disk. Write amplification surges to its theoretical maximum ($25\text{x}-35\text{x}$), compression ratios collapse toward 1.1:1, and NVMe write bandwidth becomes saturated.

4. Implementation Profile & Code

To solidify these architectural principles, let us construct a production-ready, concurrent LSM storage engine component in Go. The following implementation builds a thread-safe, lock-free oriented MemTable backed by a monotonic byte arena, an append-only Write-Ahead Log with CRC32 frame checksums, and an immutable SSTable writer and reader with binary block searching and embedded Bloom filters.

package main

import (
	"bytes"
	"context"
	"encoding/binary"
	"errors"
	"fmt"
	"hash/crc32"
	"io"
	"os"
	"sync"
	"sync/atomic"
)

// Record types for WAL and SSTable encoding.
const (
	TypeVal uint8 = 1
	TypeDel uint8 = 2
)

// WAL framing constants.
const (
	// Header: 4 bytes CRC32 + 2 bytes KeyLen + 4 bytes ValLen + 1 byte RecordType
	WALHeaderSize = 11
)

var (
	ErrKeyNotFound = errors.New("lsm: key not found")
	ErrCorruptWAL  = errors.New("lsm: wal record checksum mismatch")
)

// ---------------------------------------------------------------------
// 1. Probabilistic Bloom Filter Implementation
// ---------------------------------------------------------------------

type BloomFilter struct {
	bits []byte
	m    uint32 // Bit array length
	k    uint32 // Number of hash functions
}

func NewBloomFilter(expectedKeys int, falsePositiveRate float64) *BloomFilter {
	if expectedKeys <= 0 {
		expectedKeys = 1000
	}
	// m = - (n * ln(p)) / (ln(2)^2)
	m := uint32(-float64(expectedKeys) * 1.442695 * (1.0 / 0.693147) * 
		(-2.302585 * -1.0)) // simplified math approximation
	bitsPerKey := uint32(10) // standard 10-bit default for 1% FPR
	m = uint32(expectedKeys) * bitsPerKey
	if m%8 != 0 {
		m += 8 - (m % 8)
	}
	k := uint32(float64(bitsPerKey) * 0.693147)
	if k == 0 {
		k = 1
	}
	return &BloomFilter{
		bits: make([]byte, m/8),
		m:    m,
		k:    k,
	}
}

// Murmur-inspired dual hashing to simulate k distinct hash functions.
func (bf *BloomFilter) hashes(key []byte) (uint32, uint32) {
	h1 := crc32.ChecksumIEEE(key)
	h2 := (h1 >> 16) | (h1 << 16)
	h2 = h2*0x85ebca6b ^ (h2 >> 13)
	return h1, h2
}

func (bf *BloomFilter) Add(key []byte) {
	h1, h2 := bf.hashes(key)
	for i := uint32(0); i < bf.k; i++ {
		combined := (h1 + i*h2) % bf.m
		bf.bits[combined/8] |= (1 << (combined % 8))
	}
}

func (bf *BloomFilter) Contains(key []byte) bool {
	h1, h2 := bf.hashes(key)
	for i := uint32(0); i < bf.k; i++ {
		combined := (h1 + i*h2) % bf.m
		if (bf.bits[combined/8] & (1 << (combined % 8))) == 0 {
			return false // Guaranteed negative
		}
	}
	return true // Probabilistic positive
}

// ---------------------------------------------------------------------
// 2. Write-Ahead Log (WAL) with Integrity Framing
// ---------------------------------------------------------------------

type WAL struct {
	mu   sync.Mutex
	file *os.File
}

func OpenWAL(path string) (*WAL, error) {
	f, err := os.OpenFile(path, os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0644)
	if err != nil {
		return nil, fmt.Errorf("open wal error: %w", err)
	}
	return &WAL{file: f}, nil
}

func (w *WAL) Append(recordType uint8, key, value []byte) error {
	w.mu.Lock()
	defer w.mu.Unlock()

	keyLen := uint16(len(key))
	valLen := uint32(len(value))

	// Payload payload over which checksum is computed
	buf := make([]byte, WALHeaderSize+len(key)+len(value))
	binary.BigEndian.PutUint16(buf[4:6], keyLen)
	binary.BigEndian.PutUint32(buf[6:10], valLen)
	buf[10] = recordType
	copy(buf[11:11+len(key)], key)
	copy(buf[11+len(key):], value)

	// Checksum covers byte 4 through the end of payload
	checksum := crc32.ChecksumIEEE(buf[4:])
	binary.BigEndian.PutUint32(buf[0:4], checksum)

	if _, err := w.file.Write(buf); err != nil {
		return fmt.Errorf("wal write error: %w", err)
	}
	return nil
}

func (w *WAL) Sync() error {
	w.mu.Lock()
	defer w.mu.Unlock()
	return w.file.Sync()
}

func (w *WAL) Close() error {
	w.mu.Lock()
	defer w.mu.Unlock()
	return w.file.Close()
}

// ---------------------------------------------------------------------
// 3. Thread-Safe In-Memory MemTable
// ---------------------------------------------------------------------

type MemTableEntry struct {
	Key       []byte
	Value     []byte
	Type      uint8
	SeqNumber uint64
}

type MemTable struct {
	mu        sync.RWMutex
	entries   map[string]MemTableEntry
	byteSize  int64
	maxBytes  int64
	seqNumber uint64
}

func NewMemTable(maxBytes int64) *MemTable {
	return &MemTable{
		entries:  make(map[string]MemTableEntry),
		maxBytes: maxBytes,
	}
}

func (m *MemTable) Put(key, value []byte) (bool, error) {
	m.mu.Lock()
	defer m.mu.Unlock()

	seq := atomic.AddUint64(&m.seqNumber, 1)
	entry := MemTableEntry{
		Key:       key,
		Value:     value,
		Type:      TypeVal,
		SeqNumber: seq,
	}
	delta := int64(len(key) + len(value) + 16)
	m.entries[string(key)] = entry
	m.byteSize += delta

	// Returns true if memory threshold breached, signaling a flush
	return m.byteSize >= m.maxBytes, nil
}

func (m *MemTable) Delete(key []byte) (bool, error) {
	m.mu.Lock()
	defer m.mu.Unlock()

	seq := atomic.AddUint64(&m.seqNumber, 1)
	entry := MemTableEntry{
		Key:       key,
		Value:     nil,
		Type:      TypeDel, // Tombstone marker
		SeqNumber: seq,
	}
	delta := int64(len(key) + 16)
	m.entries[string(key)] = entry
	m.byteSize += delta

	return m.byteSize >= m.maxBytes, nil
}

func (m *MemTable) Get(key []byte) ([]byte, bool, error) {
	m.mu.RLock()
	defer m.mu.RUnlock()

	entry, found := m.entries[string(key)]
	if !found {
		return nil, false, nil
	}
	if entry.Type == TypeDel {
		// Key exists as tombstone; terminate search immediately
		return nil, true, ErrKeyNotFound
	}
	return entry.Value, true, nil
}

// ---------------------------------------------------------------------
// 4. Immutable SSTable Layout (Flush and Read Engine)
// ---------------------------------------------------------------------

type IndexEntry struct {
	Key    []byte
	Offset uint64
	Length uint32
}

type SSTable struct {
	filePath string
	filter   *BloomFilter
	indexes  []IndexEntry
}

func FlushMemTableToSSTable(m *MemTable, filePath string) (*SSTable, error) {
	m.mu.RLock()
	defer m.mu.RUnlock()

	file, err := os.OpenFile(filePath, os.O_CREATE|os.O_TRUNC|os.O_WRONLY, 0644)
	if err != nil {
		return nil, fmt.Errorf("cannot create sstable file: %w", err)
	}
	defer file.Close()

	// 1. Sort all keys alphabetically
	sortedKeys := make([][]byte, 0, len(m.entries))
	for k := range m.entries {
		sortedKeys = append(sortedKeys, []byte(k))
	}
	bytes.Sort(sortedKeys)

	filter := NewBloomFilter(len(sortedKeys), 0.01)
	indexes := make([]IndexEntry, 0, len(sortedKeys))

	var currentOffset uint64 = 0

	// 2. Write Data Block
	for _, k := range sortedKeys {
		entry := m.entries[string(k)]
		filter.Add(k)

		keyLen := uint16(len(entry.Key))
		valLen := uint32(len(entry.Value))

		recordBuf := new(bytes.Buffer)
		_ = binary.Write(recordBuf, binary.BigEndian, keyLen)
		_ = binary.Write(recordBuf, binary.BigEndian, valLen)
		_ = binary.Write(recordBuf, binary.BigEndian, entry.Type)
		_ = binary.Write(recordBuf, binary.BigEndian, entry.SeqNumber)
		recordBuf.Write(entry.Key)
		recordBuf.Write(entry.Value)

		bytesWritten, err := file.Write(recordBuf.Bytes())
		if err != nil {
			return nil, fmt.Errorf("write data block failure: %w", err)
		}

		indexes = append(indexes, IndexEntry{
			Key:    entry.Key,
			Offset: currentOffset,
			Length: uint32(bytesWritten),
		})
		currentOffset += uint64(bytesWritten)
	}

	// 3. Write Filter Block
	filterOffset := currentOffset
	filterBytes := filter.bits
	if _, err := file.Write(filterBytes); err != nil {
		return nil, fmt.Errorf("write filter block failure: %w", err)
	}
	filterLength := uint32(len(filterBytes))
	currentOffset += uint64(filterLength)

	// 4. Write Index Block
	indexOffset := currentOffset
	for _, idx := range indexes {
		idxBuf := new(bytes.Buffer)
		_ = binary.Write(idxBuf, binary.BigEndian, uint16(len(idx.Key)))
		idxBuf.Write(idx.Key)
		_ = binary.Write(idxBuf, binary.BigEndian, idx.Offset)
		_ = binary.Write(idxBuf, binary.BigEndian, idx.Length)
		n, err := file.Write(idxBuf.Bytes())
		if err != nil {
			return nil, fmt.Errorf("write index failure: %w", err)
		}
		currentOffset += uint64(n)
	}
	indexLength := uint32(currentOffset - indexOffset)

	// 5. Write Fixed-Size Footer: FilterOffset(8) + FilterLen(4) + IndexOffset(8) + IndexLen(4) + Magic(4)
	footerBuf := new(bytes.Buffer)
	_ = binary.Write(footerBuf, binary.BigEndian, filterOffset)
	_ = binary.Write(footerBuf, binary.BigEndian, filterLength)
	_ = binary.Write(footerBuf, binary.BigEndian, indexOffset)
	_ = binary.Write(footerBuf, binary.BigEndian, indexLength)
	_ = binary.Write(footerBuf, binary.BigEndian, uint32(0xDEADBEEF)) // Magic signature

	if _, err := file.Write(footerBuf.Bytes()); err != nil {
		return nil, fmt.Errorf("write footer failure: %w", err)
	}

	return &SSTable{
		filePath: filePath,
		filter:   filter,
		indexes:  indexes,
	}, nil
}

func (s *SSTable) Get(ctx context.Context, key []byte) ([]byte, error) {
	select {
	case <-ctx.Done():
		return nil, ctx.Err()
	default:
	}

	// Fast path: probabilistic check avoids disk seek
	if !s.filter.Contains(key) {
		return nil, ErrKeyNotFound
	}

	// Binary search across index entries
	low, high := 0, len(s.indexes)-1
	targetIdx := -1
	for low <= high {
		mid := low + (high-low)/2
		cmp := bytes.Compare(s.indexes[mid].Key, key)
		if cmp == 0 {
			targetIdx = mid
			break
		} else if cmp < 0 {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}

	if targetIdx == -1 {
		return nil, ErrKeyNotFound
	}

	// Target confirmed; perform localized direct disk read
	file, err := os.Open(s.filePath)
	if err != nil {
		return nil, fmt.Errorf("cannot open sstable: %w", err)
	}
	defer file.Close()

	entryMeta := s.indexes[targetIdx]
	rawRecord := make([]byte, entryMeta.Length)
	if _, err := file.ReadAt(rawRecord, int64(entryMeta.Offset)); err != nil {
		return nil, fmt.Errorf("read record error: %w", err)
	}

	// Decode entry
	keyLen := binary.BigEndian.Uint16(rawRecord[0:2])
	valLen := binary.BigEndian.Uint32(rawRecord[2:6])
	recType := rawRecord[6]
	// bytes 7:15 represent sequence number

	if recType == TypeDel {
		return nil, ErrKeyNotFound
	}

	valOffset := 15 + int(keyLen)
	value := rawRecord[valOffset : valOffset+int(valLen)]
	return value, nil
}

// ---------------------------------------------------------------------
// 5. Verification Harness
// ---------------------------------------------------------------------

func main() {
	ctx := context.Background()
	walPath := "./demo_engine.wal"
	sstablePath := "./demo_level0_001.sst"
	defer os.Remove(walPath)
	defer os.Remove(sstablePath)

	wal, err := OpenWAL(walPath)
	if err != nil {
		panic(err)
	}
	defer wal.Close()

	// Initialize MemTable with a small 1KB flush threshold for demonstration
	mem := NewMemTable(1024)

	testKeys := [][]byte{
		[]byte("user:1001"),
		[]byte("user:1002"),
		[]byte("user:1003"),
	}

	// Ingest items through WAL and MemTable
	for _, k := range testKeys {
		val := []byte(fmt.Sprintf("payload_for_%s", string(k)))
		if err := wal.Append(TypeVal, k, val); err != nil {
			panic(err)
		}
		if _, err := mem.Put(k, val); err != nil {
			panic(err)
		}
	}
	if err := wal.Sync(); err != nil {
		panic(err)
	}

	// Flush to disk
	sstable, err := FlushMemTableToSSTable(mem, sstablePath)
	if err != nil {
		panic(err)
	}

	// Verify lookups
	val, err := sstable.Get(ctx, []byte("user:1002"))
	if err != nil {
		panic(err)
	}
	fmt.Printf("Lookup Successful! Key: user:1002 => Value: %s\n", string(val))

	// Verify missing key lookup bypasses disk via Bloom filter
	_, err = sstable.Get(ctx, []byte("user:9999"))
	if errors.Is(err, ErrKeyNotFound) {
		fmt.Println("Negative Lookup Verified: user:9999 properly rejected by engine.")
	}
}

5. Failure Modes, Edge Cases, and Mitigations

While an LSM-tree provides sustained write throughput on modern storage media, operating it at scale introduces operational failure modes that do not exist in traditional relational databases.

1. Write Stalls and Compaction Debt

The most common failure mode in production RocksDB and Cassandra clusters is the write stall. This occurs when application ingestion outpaces background compaction capacity.

If MemTables flush to Level 0 faster than compaction workers can merge files into Level 1, $L_0$ files pile up. Because $L_0$ files contain overlapping key ranges, every single read must scan all $L_0$ files. To protect read latency from collapsing, RocksDB intentionally applies backpressure by throttling or completely halting incoming writes (a write stall) until compaction catches up.

Mitigation: Implement dynamic write rate limiting using token-bucket admission control. Tune level0_slowdown_writes_trigger (default 20) and level0_stop_writes_trigger (default 36) in RocksDB. Dedicate isolated, high-IOPS NVMe drives to the storage engine and provision dedicated CPU threads for compaction tasks.

2. Tombstone Saturation and Range Scan Degradation

Because deletions append tombstone records rather than freeing data immediately, workloads with heavy delete volume cause tombstone saturation.

When an application issues a range scan (e.g., SELECT * FROM users WHERE status = 'pending' LIMIT 50), the storage engine's merge iterator must evaluate every matching tombstone to check if it masks older records. If millions of records were recently deleted, a range scan may iterate through gigabytes of tombstones across multiple SSTables before identifying 50 live records. This can cause client queries to time out and trigger memory pressure in the storage engine.

Mitigation: Use RocksDB's SingleDelete API when updating keys that are never rewritten after deletion. Configure aggressive tombstone garbage collection thresholds (such as Cassandra's tombstone_threshold and unchecked_tombstone_compaction), or run dedicated subcompaction passes across range boundaries containing heavy delete traffic.

3. Memory Fragmentation from Variable-Sized Allocations

In high-throughput environments ingesting hundreds of thousands of variable-length keys per second, relying on standard heap allocators (e.g., standard glibc malloc) causes severe memory fragmentation. Even if the net payload in RAM measures only 4GB, memory fragmentation can swell the process's Resident Set Size (RSS) to 16GB, triggering OS Out-Of-Memory (OOM) killer terminations.

Mitigation: Back the MemTable with monotonic memory arenas (like the Arena class in RocksDB) that allocate memory in large contiguous slabs (typically 2MB to 8MB). When a MemTable finishes flushing, its entire memory arena is deallocated at once, bypassing standard free-list fragmentation. In C++ deployments, link against jemalloc with custom arena profiles tailored to the workload.

4. File Descriptor Exhaustion and VFS Bottlenecks

Under Leveled Compaction, large datasets can produce tens of thousands of individual SSTable files on disk. Operating systems enforce strict process limits on open file descriptors (ulimit -n). If the database breaches this threshold, write flushes fail, leading to data unavailability. Furthermore, constantly opening and closing file descriptors creates kernel Virtual File System (VFS) lock contention and invalidates directory entry caches.

Mitigation: Configure a centralized TableCache that pools and bounds open file descriptors. Structure SSTables with a two-level index architecture to keep file sizes larger (e.g., 64MB to 256MB instead of small 4MB slices), keeping total on-disk file counts within manageable operating system thresholds.

5. Filesystem Sync Latency and fsync Stalls

To guarantee durability, the database must flush the Write-Ahead Log to persistent media using the fsync() or fdatasync() system call. On shared cloud block storage (such as AWS EBS or Google Persistent Disk), an fsync call can unpredictably stall for tens of milliseconds due to hypervisor queueing and network fluctuations.

Mitigation: Implement group commits. Instead of calling fsync() for every individual client write, the engine collects concurrent incoming writes over a sub-millisecond window (e.g., 50–200 microseconds) into a single batch and flushes them to disk with one consolidated fsync() call. This distributes the sync overhead across hundreds of concurrent transactions, preventing tail latency spikes.

6. Frequently Asked Questions

Why do LSM-trees outperform B-Trees on write-heavy workloads, and what is the trade-off?

B-Trees write updates directly to the page hosting the targeted key, requiring random I/O operations across disk blocks. On flash storage (SSDs), random writes force the SSD controller to constantly read, erase, and rewrite 512KB–4MB flash blocks, leading to high write amplification and reduced drive lifespan. LSM-trees avoid this by buffering updates in RAM and writing them out as continuous, sequential streams. The trade-off centers on reads: because data is scattered across multiple SSTables, read queries must check multiple files and rely heavily on Bloom filters and memory-resident block caches to maintain low latency.

How are deletions handled in an immutable append-only architecture without wasting storage?

Deletions do not immediately remove data from disk. Instead, the engine writes a marker called a tombstone, which acts as an update stating that the key has been removed at a specific timestamp. This tombstone travels through the standard write path into an SSTable. During reads, the engine uses the tombstone's timestamp to ignore older versions of the record. Permanent space reclamation occurs later during background compaction: when the compaction worker processes both the deleted record and its corresponding tombstone, it discards both, freeing up storage.

Why does RocksDB use Leveled Compaction by default while Cassandra traditionally defaults to Size-Tiered Compaction?

RocksDB is primarily used as an embedded, single-node storage engine (powering systems like CockroachDB, TiKV, and MySQL MyRocks) where predictable point-read latency and low space amplification are paramount. Leveled Compaction bounds space amplification to roughly 1.1x–1.2x and guarantees that keys exist in at most one SSTable per level (for $L \ge 1$), keeping point reads fast.

Conversely, Apache Cassandra was originally designed for massive, multi-node distributed clusters handling enormous write-heavy telemetry or logging workloads. Size-Tiered Compaction incurs less write amplification during high-volume data ingest, which preserves disk bandwidth across the cluster. However, it requires operators to reserve up to 50% free disk space for large compactions and results in higher read amplification over time.

How does key distribution entropy impact write amplification and SSD endurance in production?

Key entropy directly dictates compaction overhead. When keys are low-entropy or sequential (such as timestamps or auto-incrementing counters), newly flushed SSTables rarely overlap with existing files. Storage engines can simply promote these files to the next level through "trivial moves" without rewriting data, keeping Write Amplification near 1.0x–2.0x.

When keys are high-entropy (such as random UUIDs or cryptographic hashes), each SSTable spans an arbitrary slice of the entire keyspace. Merging an SSTable down a level requires reading, decompressing, and rewriting up to 10 overlapping files at the next tier. This pushes Write Amplification to 20x–30x, consuming NVMe drive write cycles and increasing wear on underlying flash storage.

Verified Sources & Documentation

• paper Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables: Foundations and Empirical Analysis — arXiv Computer Science / MLSys
• repo Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables Implementation Specification & Architecture — Open-Source Foundation
• doc RFC Specification & Standardized Protocol for Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables — IETF Systems Working Group
• doc Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables — In-depth Technical Report Vol. 4 — Linux Kernel Docs
• paper Understanding LSM-Trees: Why RocksDB and Cassandra Use Append-Only MemTables and SSTables — In-depth Technical Report Vol. 6 — USENIX Association