LSM-Trees and SSTables: Write-Optimized Storage Architecture

1. The Core Engineering Challenge: Random Disk Write Penalties

Every persistent database must confront the physical characteristics of storage hardware. Whether operating on spinning magnetic disks, SATA solid-state drives (SSDs), or PCIe Gen5 NVMe flash devices, random write throughput is fundamentally slower and more resource-intensive than sequential write throughput.

The In-Place Mutation Trap (B-Trees)

Traditional relational database engines (e.g., MySQL InnoDB, PostgreSQL) organize data on disk using variants of the $B^{+}$-Tree (whose 16 KB slotted page internals we just examined in Step 16 (CORE-M08-004), and whose buffer pool interactions we extend in Step 21 (CORE-M10-001)). In a $B^{+}$-Tree:

1. Data is organized into fixed-size pages (typically 4 KB, 8 KB, or 16 KB).
2. When a record is updated or inserted, the database locates the specific page containing that key and mutates the page in place.
3. In the worst case—an unbatched random update where a single 50-byte record dirties an otherwise cold 16 KB leaf page before buffer-pool eviction—the storage engine must flush the entire 16 KB page back to disk (plus WAL logging, and $2\times$ page writes when MySQL InnoDB’s doublewrite buffer is enabled):

On flash storage (SSDs/NVMe), in-place updates cause severe wear. Flash memory cannot overwrite existing cells without first erasing an entire erase block (often 2 MB to 8 MB in size). The SSD controller’s Flash Translation Layer (FTL) must copy surviving valid pages elsewhere, perform an erase cycle, and write back the data. This phenomenon, known as device-level write amplification, destroys flash endurance and creates unpredictable I/O latency spikes when the garbage collector struggles to keep pace.

+-------------------------------------------------------------------------------+
|                       The Fundamental Trade-off                               |
|                                                                               |
|   B+ Tree:  Optimizes READS. In-place pages mean a key lives in exactly one   |
|             known leaf page. Reads cost O(log_B N). Writes cost random I/O.   |
|                                                                               |
|   LSM-Tree: Optimizes WRITES. Append-only logs mean writes cost O(1) disk I/O.|
|             Keys may reside in multiple files. Reads cost multi-file merges.  |
+-------------------------------------------------------------------------------+

The Log-Structured Merge-Tree (LSM-Tree), introduced by Patrick O’Neil, Edward O’Neil, and Gerhard Weikum in 1996, resolves this fundamental dilemma. It turns random writes into sequential appends, deferring the expensive work of sorting and de-duplication to background asynchronous merges.

2. Mental Model & Architectural Anatomy

An LSM storage engine decouples write ingestion from on-disk layout by dividing the system into three synchronized tiers:

SYSTEM ARCHITECTURE BLUEPRINTDATA STRUCTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 6

1. Client Write Ingestion

Client issues put(key, value) or delete(key). Request enters the storage engine; no random disk I/O is performed.

Architectural Invariant: Write Amplification vs Latency: Decouples client write latency from disk seek times entirely.

ARCHITECTURAL FLOW · STEP 2 OF 6

2. Sequential Append to Write-Ahead Log (WAL)

Before acknowledging the write, the operation is appended sequentially to the WAL file on disk for durability.

Architectural Invariant: Sequential I/O: Append-only disk writes achieve up to 100x higher throughput than random disk seeks.

ARCHITECTURAL FLOW · STEP 3 OF 6

3. In-Memory SkipList Insertion

Record is inserted into the Active MemTable (Concurrent SkipList in RAM), keeping all in-memory keys sorted in O(log N) time.

Architectural Invariant: Sorted Order: In-memory sorting ensures that subsequent flushes to disk can be written as contiguous sorted runs.

ARCHITECTURAL FLOW · STEP 4 OF 6

4. MemTable Saturation & Flush to Level 0

Active MemTable hits capacity (~64MB). It is frozen into an Immutable MemTable while a new active MemTable is allocated. Background thread flushes to L0 SSTable.

Architectural Invariant: Zero Allocation Stall: Freezing into immutable table allows concurrent writes to continue unblocked into the new active MemTable.

ARCHITECTURAL FLOW · STEP 5 OF 6

5. Multi-Way Leveled Compaction (L0 -> L1 -> L2)

Compaction thread reads overlapping L0 files and merges them into non-overlapping contiguous key range partitions in Level 1 and Level 2, purging tombstones.

Architectural Invariant: Space Reclamation: Deletions in LSM-trees write a tombstone marker; garbage collection and space reclamation happen strictly during compaction.

ARCHITECTURAL FLOW · STEP 6 OF 6

6. SSTable Layout: Bloom Filter & Index Block Probing

Reads consult the SSTable Filter Block (Bloom filter) in memory. If positive, binary search probes the Index Block to pinpoint the exact 4KB data block.

Architectural Invariant: Read Optimization: Bloom filters prevent 99% of negative disk reads across non-matching SSTables.

1. Write-Ahead Log (WAL): An append-only file on persistent disk. Every incoming mutation is appended to the WAL before acknowledging the client. This guarantees crash durability ($D$ in ACID) with zero random disk seeks.
2. MemTable (In-Memory Buffer): An active in-memory sorted data structure (typically a lock-free SkipList or Red-Black Tree). While the WAL provides durability, the MemTable provides fast sorted random access and range scans in RAM.
3. Sorted String Tables (SSTables): Immutable, sequential files stored on persistent disk. When a MemTable reaches a size threshold (e.g., 32 MB–64 MB), it freezes into an Immutable MemTable and is flushed sequentially to disk as a new SSTable.
4. Compaction Engine: Background worker threads that merge multiple SSTables, purge overwritten values and deleted tombstones, and organize files into sorted, non-overlapping hierarchical levels ($L_0,L_1,L_2,\dots ,L_k$).

3. Deep Dive: The Write Path

The LSM-Tree write path is designed for minimal, deterministic latency. When a client executes put(key, value) or delete(key):

Client Request
      |
      +---> 1. Append record to Write-Ahead Log (WAL) on Disk (O(1) sequential I/O)
      |
      +---> 2. Insert record into Active MemTable (RAM) (O(log N) SkipList insertion)
      |
  Return OK (Total latency: microseconds)

Crash Recovery Invariant

Because the MemTable resides in volatile RAM, an ungraceful crash (power failure, kernel panic) loses all un-flushed writes in memory. However, because every write was appended to the WAL before acknowledging the client, recovery is deterministic:

1. Upon startup, the engine reads the WAL from start to end.
2. It replays each mutation into a fresh MemTable.
3. Once the MemTable matches the pre-crash state, normal operations resume, and old WAL segments are safely truncated.

MemTable Flushing: From RAM to Immutable Disk

When the active MemTable reaches its configured threshold (write_buffer_size, e.g., 64 MB):

1. The engine atomically marks the active MemTable as Immutable (ReadOnly).
2. A new, empty active MemTable and a new WAL segment are created immediately so incoming writes never block.
3. A background flush thread iterates through the Immutable MemTable in sorted order and writes it sequentially to disk as a Level 0 ($L_0$) SSTable.
4. Once written and fsync’d, the immutable MemTable and its corresponding old WAL file are reclaimed.

Notice the crucial property: The flush requires zero random disk head seeks or block overwrites. It is a single, uninterrupted sequential streaming write.

4. SSTable Structure & Anatomy

An SSTable (Sorted String Table) is an immutable file containing sorted key-value pairs organized into discrete, addressable blocks. A typical production SSTable (such as RocksDB’s Block-Based Table format) contains the following sections:

+-------------------------------------------------------------------------+
| Data Block 0: [k1: v1], [k2: v2], ... [Compressed, typically 4KB-64KB]  |
+-------------------------------------------------------------------------+
| Data Block 1: [k50: v50], [k51: v51], ... [Compressed]                  |
+-------------------------------------------------------------------------+
| ...                                                                     |
+-------------------------------------------------------------------------+
| Data Block N: [k900: v900], [k999: v999]                                |
+-------------------------------------------------------------------------+
| Filter Block: Bloom Filter bit-array (O(1) negative seek rejection)     |
+-------------------------------------------------------------------------+
| Index Block: Key offsets pointing to the start of each Data Block       |
+-------------------------------------------------------------------------+
| Meta Index Block: Pointers to Filter Block and Property Blocks          |
+-------------------------------------------------------------------------+
| Footer: Fixed 48-byte trailer with magic number and offset to Meta Index|
+-------------------------------------------------------------------------+

How the Read Path Traverses an SSTable

When searching for target_key within a single SSTable:

1. Bloom Filter Check: The engine queries the embedded Bloom Filter using the target key. If the filter returns 0 (definitely not present), the engine aborts disk reads entirely. No data blocks are read.
2. Index Block Binary Search: If the Bloom filter returns 1, the engine reads the SSTable’s Index Block (which is pinned in the operating system’s Page Cache or an application Block Cache). It performs a binary search on the boundary keys of each block to identify the exact 4 KB data block that could contain target_key.
3. Data Block Fetch & Scan: The engine reads the single target data block from disk (or cache), decompresses it (using Snappy, LZ4, or Zstandard), and binary-searches the internal block restart offsets to locate the exact record.

5. Deep Dive: The Read Path

Because mutations are appended over time and SSTables are immutable, a single key might have different versions stored across multiple files. The read path must search from newest to oldest:

                       Read Query: get("user:1042")
                                   |
                                   v
                    +------------------------------+
                    | Check Active MemTable (RAM)  |
                    +------------------------------+
                        |                      |
                     (Found)              (Not Found)
                        |                      v
                    Return val   +-------------------------------+
                                 | Check Immutable MemTable (RAM)|
                                 +-------------------------------+
                                     |                       |
                                  (Found)               (Not Found)
                                     |                       v
                                 Return val   +-------------------------------+
                                              | Check Level 0 SSTables (Disk) |
                                              +-------------------------------+
                                                  |                       |
                                               (Found)               (Not Found)
                                                  |                       v
                                              Return val   +-------------------------------+
                                                           | Check Level 1+ SSTables (LCS) |
                                                           +-------------------------------+

The Level 0 Search Penalty

Because Level 0 files are direct dumps of MemTables, their key ranges overlap. An $L_0$ file written at 10:00 AM may contain keys [aaa to zzz], and another $L_0$ file flushed at 10:05 AM may also contain keys [aaa to zzz]. Therefore, in $L_0$, a read must check every single SSTable in reverse chronological order until the key is found or all $L_0$ files are exhausted.

This is why Bloom Filters (studied in CORE-M08-001) are mathematically indispensable for LSM-Trees: without them, a query for a non-existent key would trigger a physical disk read for every $L_0$ SSTable!

6. Deletions & Tombstones: Soft Deletion Economics

In an immutable storage engine, you cannot delete a record by overwriting its disk bytes with zeros. Doing so would violate the append-only invariant and require random disk writes.

Instead, a deletion is executed as an append-only write:

1. The engine creates a special marker called a Tombstone: put(key, TOMBSTONE).
2. The tombstone is appended to the WAL and inserted into the active MemTable.
3. During point queries, if the engine encounters a tombstone before any older value, it returns NotFound.
4. The obsolete value is only physically eradicated from disk during a subsequent Compaction cycle when the tombstone and the original record are merged together.

The Tombstone GC Hazard

A tombstone cannot be discarded during a compaction cycle unless the engine can prove that no older SSTables in any lower level contain the deleted key. If a tombstone were prematurely removed at Level 1 while an older version of the key still existed at Level 3, the deleted record would mysteriously “resurrect” during future queries!

HAZARD SCENARIO: PREMATURE TOMBSTONE DELETION
Level 1: [Key: 'alice' -> TOMBSTONE]  (Flushed 10:15 AM)
Level 3: [Key: 'alice' -> 'active']     (Flushed 08:00 AM)

If Level 1 compacts into Level 2 and purges the tombstone:
Level 2: (No record for 'alice')
Level 3: [Key: 'alice' -> 'active']

Result: A query for 'alice' misses Level 1 and Level 2, falls through to Level 3,
and resurrects a deleted account!
Rule: A tombstone can only be dropped when it reaches the bottom-most level of the LSM-tree.

7. Compaction Strategies: Leveled vs. Size-Tiered

Without maintenance, an LSM-tree would accumulate thousands of SSTables, causing read latency and disk consumption to spiral out of control. Compaction is the background reconciliation process that reads multiple SSTables, performs a multi-way merge sort, eliminates obsolete versions and tombstones, and writes clean, sorted SSTables back to disk.

Two dominant compaction algorithms exist in production:

1. Leveled Compaction Strategy (LCS / RocksDB Default)

Leveled Compaction arranges SSTables into an exponential hierarchy of levels ($L_0,L_1,L_2,\dots ,L_{\max }$), typically with a size multiplier $T=10$:

• $L_0$: Up to 4 SSTables (~256 MB total). Key ranges overlap.
• $L_1$: Capacity limit = 256 MB. Key ranges do NOT overlap.
• $L_2$: Capacity limit = 2.56 GB ($10\times L_1$). Key ranges do NOT overlap.
• $L_3$: Capacity limit = 25.6 GB ($10\times L_2$). Key ranges do NOT overlap.

+---------------------------------------------------------------------------------+
|                         Leveled Compaction Hierarchy                            |
|                                                                                 |
| Level 0: [ Key: a - z ] [ Key: c - m ] [ Key: b - y ]  (Overlapping ranges)     |
|                                                                                 |
| Level 1: [ a - d ]  [ e - h ]  [ i - m ]  [ n - s ]  [ t - z ] (Partitioned)   |
|                                                                                 |
| Level 2: [ a-b ] [ c-d ] [ e-f ] ... [ w-x ] [ y-z ] (Strict non-overlapping)   |
+---------------------------------------------------------------------------------+

How LCS Compaction Works:

When level $L_i$ exceeds its capacity limit:

1. The engine picks an SSTable from $L_i$ (e.g., covering keys [f - k]).
2. It finds all SSTables in $L_{i+1}$ whose key ranges overlap with [f - k].
3. It performs a streaming merge sort of the input files, producing new, non-overlapping SSTables in $L_{i+1}$.
4. The old input SSTables are deleted.

Characteristics of LCS:

• Read Performance: Exceptional. Because levels $L_1+$ have zero internal key overlap, a point lookup checks at most 1 SSTable per level.
• Space Amplification: Low ($\approx 10\%-20\%$). Obsolete records are purged rapidly.
• Write Amplification: High ($10\times -30\times$). A single byte may be read, merged, and rewritten to disk multiple times as it cascades down levels.

2. Size-Tiered Compaction Strategy (STCS / Cassandra Default)

Size-Tiered Compaction does not partition data into non-overlapping key ranges. Instead, it groups SSTables that are of similar file size:

1. When 4 SSTables of roughly the same size exist (e.g., four 100 MB files), the engine merges them into a single 400 MB file.
2. When four 400 MB files accumulate, they are merged into a single 1.6 GB file.

Characteristics of STCS:

• Write Performance: Very high throughput. Minimal write amplification ($2\times -8\times$).
• Read Performance: Poor for point reads. Because key ranges overlap across all tables, reads must probe multiple files.
• Space Amplification Disaster: Requires up to 50% free disk headroom. When compacting the largest SSTable (e.g., merging four 100 GB files into one 400 GB file), the system must store both the old 400 GB input and the new 400 GB output simultaneously until the merge finishes!

8. Mathematical Performance Model: Amplification Factors

The behavior of any storage engine is governed by three interrelated amplification metrics:

1. Write Amplification Factor ($WA$)

In Leveled Compaction with level size multiplier $T$ (commonly $T=10$) and $L$ non-overlapping levels ($L_1\dots L_L$):

• Every byte is first written once to the WAL ($1\times$) and flushed once to $L_0$/$L_1$ ($1\times$).
• Across each of the $L-1$ inter-level compactions ($L_1\to L_2\to \cdots \to L_L$), merging one SSTable from $L_{i-1}$ into $L_i$ rewrites up to $T$ overlapping SSTables in the worst case (uniform keys spanning the full keyspace), and $\approx \frac{T}{2}$ SSTables on average when RocksDB selects the candidate file with minimal overlap:

For a 4-level database ($L=4$) with $T=10$, $W{A}_{\text{avg}}\approx 2+5\times 3=17\times$ (typically $15\times$ to $30\times$ in production, with a worst-case bound near $32\times$). Every gigabyte of ingested client data generates roughly 17–25 GB of physical SSD writes over its lifetime.

2. Space Amplification Factor ($SA$)

• Leveled Compaction: In the worst case where every record in upper levels $L_0\dots L_{L-1}$ is an overwrite of an existing key in the bottommost level $L_L$, the geometric series of upper-level capacities relative to $L_L$ ($\frac{1}{T}+\frac{1}{T^2}+\cdots =\frac{1}{T-1}$) bounds steady-state space amplification to: $$S{A}_{\text{LCS}}\approx 1+\frac{1}{T-1}=\frac{T}{T-1}$$ For $T=10$, $S{A}_{\text{LCS}}\approx \frac{10}{9}\approx 1.111$ (only $11.1\%$ space overhead).
• Size-Tiered Compaction: $S{A}_{\text{STCS}}$ regularly reaches $2.0\times$–$2.5\times$ due to unmerged stale versions across tiers plus the temporary $2\times$ working-space requirement during major compactions.

3. Read Amplification Factor ($RA$)

Read amplification is measured both in expected disk block reads per point lookup and byte-level read amplification ($\frac{\text{Block Size}}{\text{Record Size}}\times \text{Disk Block Reads}$, e.g. reading one 4 KB data block for a 100-byte record $=40.96\times$ byte amplification).

Without Bloom filters, a worst-case point lookup (or negative lookup for an absent key) must read one data block from every $L_0$ SSTable ($N_{L_0}$) and one data block from each partitioned level ($L_{\max }$):

With per-SSTable Bloom filters configured at $\approx 10$ bits per key (false-positive probability $p\approx 0.01$), assuming SSTable index and filter blocks reside in RAM:

• Negative lookup (absent key): $\mathbb{E}[{\text{Disk Reads}}_{\text{miss}}]=p\cdot (N_{L_0}+L_{\max })$. For $N_{L_0}=4,L_{\max }=4,p=0.01$, this drops from $8$ disk seeks to $0.08$ disk seeks!
• Worst-case positive lookup (key resides in $L_{\max }$): $$\mathbb{E}[{\text{Disk Reads}}_{\text{hit}}]=1+p\cdot (N_{L_0}+L_{\max }-1)=1+0.01\times (4+4-1)=1.07\text{ disk reads}$$

The RUM Conjecture

Formulated by Manos Athanassoulis and Stratos Idreos at Harvard, the RUM Conjecture proves that storage engines exist on a 3-dimensional Pareto frontier:

                      Read Overhead (R)
                             /\
                            /  \
                           /    \
                          /      \
                         /  RUM   \
                        /  Space   \
                       /            \
 Update Overhead (U)  +--------------+  Memory / Space Overhead (M)

You cannot minimize Read overhead, Update overhead, and Space overhead at the same time:

• $B^{+}$-Tree: Minimizes Read overhead ($R$) and Space overhead ($M$) at the expense of terrible Update overhead ($U$).
• LSM-Tree (Size-Tiered): Minimizes Update overhead ($U$) at the expense of Read overhead ($R$) and Space overhead ($M$).
• LSM-Tree (Leveled): Minimizes Space overhead ($M$) and Read overhead ($R$) at the expense of high Update/Write amplification ($U$).

9. Real-World Systems Comparison

10. Operational Failure Modes & Production Debugging

Failure Mode 1: The Level 0 Write Stall (Backpressure)

When write ingestion outpaces disk compaction throughput, $L_0$ files accumulate rapidly. In RocksDB:

• level0_slowdown_writes_trigger (default 20 files): Ingestion is artificially throttled.
• level0_stop_writes_trigger (default 36 files): All incoming writes are frozen completely.

Symptom: P99 write latency spikes from 200 microseconds to 15 seconds. Client connection pools become exhausted.
Diagnostic: Inspect RocksDB statistics or run nodetool compactionstats in Cassandra. Check pending compaction bytes.
Resolution:

1. Increase background compaction worker threads (max_background_compactions).
2. Allocate high-IOPS NVMe storage or stripe across multiple disks.
3. Increase write_buffer_size to reduce the frequency of flushes.

Failure Mode 2: Cassandra Tombstone Overwhelm

An application issues a query: SELECT * FROM user_events WHERE user_id = '101' LIMIT 50. If the application previously deleted 500,000 events for user 101, Cassandra’s read engine must read and evaluate all 500,000 tombstone records before locating 50 surviving rows.

Symptom: The coordinator node throws ReadTimeoutException or crashes with OutOfMemoryError: Java heap space. The logs warn: Scanned over 100000 tombstones in user_events; query aborted.
Diagnostic: Inspect TombstonesScanned histogram in Cassandra JMX metrics.
Resolution:

1. Avoid anti-pattern queue tables in LSM engines (frequent insert-then-delete cycles).
2. Tune gc_grace_seconds down for dedicated transient tables.
3. Use partition deletion rather than row-level deletions.

11. Concrete Implementation: In-Memory LSM Engine

The following production-grade TypeScript implementation demonstrates the core mechanics of an LSM-Tree: in-memory SkipList MemTable, SSTable formatting with embedded Bloom Filters, a two-level block index, and a streaming multi-way merge compaction engine.

/**
 * Portable 32-bit FNV-1a + MurmurHash3 avalanche mixer for Bloom Filter gating
 * Zero Node-specific imports; runs identically in browser and server runtimes.
 */
const utf8Encoder = new TextEncoder();

function hashString(key: string, seed: number): number {
  const bytes = utf8Encoder.encode(key);
  let h = (0x811c9dc5 ^ seed) >>> 0;
  for (let i = 0; i < bytes.length; i++) {
    h ^= bytes[i];
    h = Math.imul(h, 0x01000193);
  }
  // MurmurHash3 32-bit finalizer for uniform bit avalanche
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

class EmbeddedBloomFilter {
  private bits: Uint8Array;
  private size: number;
  private numHashes: number;

  constructor(expectedKeys: number, falsePositiveRate = 0.01) {
    const n = Math.max(1, expectedKeys);
    this.size = Math.max(8, Math.ceil(-((n * Math.log(falsePositiveRate)) / (Math.LN2 ** 2))));
    this.numHashes = Math.max(1, Math.round((this.size / n) * Math.LN2));
    this.bits = new Uint8Array(Math.ceil(this.size / 8));
  }

  add(key: string): void {
    const h1 = hashString(key, 0x1337);
    const h2 = hashString(key, 0x9e3779b9) || 1;
    for (let i = 0; i < this.numHashes; i++) {
      const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.size;
      this.bits[bitIndex >>> 3] |= 1 << (bitIndex & 7);
    }
  }

  mightContain(key: string): boolean {
    const h1 = hashString(key, 0x1337);
    const h2 = hashString(key, 0x9e3779b9) || 1;
    for (let i = 0; i < this.numHashes; i++) {
      const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.size;
      if ((this.bits[bitIndex >>> 3] & (1 << (bitIndex & 7))) === 0) {
        return false; // Definitely not present
      }
    }
    return true; // Might be present
  }
}

export interface Entry {
  key: string;
  value: string | null; // null represents a TOMBSTONE marker
  seq: number;
}

/**
 * An immutable Sorted String Table (SSTable) simulated in memory
 */
export class SSTable {
  public readonly id: string;
  public readonly level: number;
  public readonly minKey: string;
  public readonly maxKey: string;
  private filter: EmbeddedBloomFilter;
  private dataBlocks: Entry[][];
  private indexBlock: { firstKey: string; blockIndex: number }[];

  constructor(id: string, level: number, entries: Entry[], blockSize = 4) {
    this.id = id;
    this.level = level;
    this.minKey = entries[0].key;
    this.maxKey = entries[entries.length - 1].key;
    this.filter = new EmbeddedBloomFilter(entries.length, 0.01);
    this.dataBlocks = [];
    this.indexBlock = [];

    // Construct partitioned data blocks and two-level sparse index
    for (let i = 0; i < entries.length; i += blockSize) {
      const block = entries.slice(i, i + blockSize);
      const blockIdx = this.dataBlocks.length;
      this.dataBlocks.push(block);
      this.indexBlock.push({ firstKey: block[0].key, blockIndex: blockIdx });
      for (const e of block) {
        this.filter.add(e.key);
      }
    }
  }

  get(key: string): { found: boolean; value: string | null; diskSeeks: number } {
    if (key < this.minKey || key > this.maxKey) {
      return { found: false, value: null, diskSeeks: 0 };
    }

    // 1. Fast Bloom Filter rejection (RAM lookup)
    if (!this.filter.mightContain(key)) {
      return { found: false, value: null, diskSeeks: 0 };
    }

    // 2. Binary search across the Index Block to identify target data block
    let low = 0;
    let high = this.indexBlock.length - 1;
    let candidateBlock = -1;

    while (low <= high) {
      const mid = (low + high) >>> 1;
      if (this.indexBlock[mid].firstKey <= key) {
        candidateBlock = this.indexBlock[mid].blockIndex;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    if (candidateBlock === -1) {
      return { found: false, value: null, diskSeeks: 0 };
    }

    // 3. Simulated single physical disk block read (1 seek)
    const block = this.dataBlocks[candidateBlock];
    for (let i = block.length - 1; i >= 0; i--) {
      if (block[i].key === key) {
        return { found: true, value: block[i].value, diskSeeks: 1 };
      }
    }

    return { found: false, value: null, diskSeeks: 1 };
  }

  getAllEntries(): Entry[] {
    return this.dataBlocks.flat();
  }
}

/**
 * Log-Structured Merge-Tree Engine with MemTable, L0, and L1 Compaction
 */
export class LSMTreeEngine {
  private memTable = new Map<string, Entry>();
  private readonly memTableThreshold: number;
  private sequenceNumber = 0;
  private sstableCounter = 0;
  public l0: SSTable[] = [];
  public l1: SSTable[] = [];

  constructor(memTableThreshold = 4) {
    this.memTableThreshold = memTableThreshold;
  }

  put(key: string, value: string): void {
    this.sequenceNumber++;
    this.memTable.set(key, { key, value, seq: this.sequenceNumber });
    if (this.memTable.size >= this.memTableThreshold) {
      this.flushMemTable();
    }
  }

  delete(key: string): void {
    this.sequenceNumber++;
    this.memTable.set(key, { key, value: null, seq: this.sequenceNumber });
    if (this.memTable.size >= this.memTableThreshold) {
      this.flushMemTable();
    }
  }

  get(key: string): { value: string | null; found: boolean; totalSeeks: number } {
    let totalSeeks = 0;

    // 1. Check Active MemTable (RAM)
    if (this.memTable.has(key)) {
      const entry = this.memTable.get(key)!;
      return { value: entry.value, found: entry.value !== null, totalSeeks: 0 };
    }

    // 2. Check Level 0 SSTables (Newest to Oldest, overlapping ranges)
    for (let i = this.l0.length - 1; i >= 0; i--) {
      const res = this.l0[i].get(key);
      totalSeeks += res.diskSeeks;
      if (res.found) {
        return { value: res.value, found: res.value !== null, totalSeeks };
      }
    }

    // 3. Check Level 1 SSTables (Partitioned non-overlapping ranges)
    for (const table of this.l1) {
      if (key >= table.minKey && key <= table.maxKey) {
        const res = table.get(key);
        totalSeeks += res.diskSeeks;
        if (res.found) {
          return { value: res.value, found: res.value !== null, totalSeeks };
        }
      }
    }

    return { value: null, found: false, totalSeeks };
  }

  public flushMemTable(): void {
    if (this.memTable.size === 0) return;
    const sorted = Array.from(this.memTable.values()).sort((a, b) => a.key.localeCompare(b.key));
    const sstable = new SSTable(`sst-l0-${++this.sstableCounter}`, 0, sorted);
    this.l0.push(sstable);
    this.memTable.clear();

    // Trigger Leveled Compaction if L0 reaches 4 overlapping files
    if (this.l0.length >= 4) {
      this.compactL0ToL1();
    }
  }

  private compactL0ToL1(): void {
    const allEntries: Map<string, Entry> = new Map();
    const combinedTables = [...this.l1, ...this.l0];

    for (const table of combinedTables) {
      for (const entry of table.getAllEntries()) {
        const existing = allEntries.get(entry.key);
        if (!existing || entry.seq >= existing.seq) {
          allEntries.set(entry.key, entry);
        }
      }
    }

    // At the bottommost level (L1 here), tombstones are safely garbage-collected
    const activeEntries = Array.from(allEntries.values())
      .filter((e) => e.value !== null)
      .sort((a, b) => a.key.localeCompare(b.key));

    this.l0 = [];
    this.l1 = [];

    const chunkSize = 4;
    for (let i = 0; i < activeEntries.length; i += chunkSize) {
      const chunk = activeEntries.slice(i, i + chunkSize);
      this.l1.push(new SSTable(`sst-l1-${++this.sstableCounter}`, 1, chunk));
    }
  }
}

function runDemo(): void {
  console.log("=== Storage Engines: Log-Structured Merge (LSM) Tree ===");
  const engine = new LSMTreeEngine(4);
  engine.put("user:alice", "profile_v1");
  engine.put("user:bob", "profile_v1");
  engine.put("user:carol", "profile_v1");
  engine.put("user:dave", "profile_v1"); // Triggers Flush #1 to L0

  engine.put("user:alice", "profile_v2");
  engine.delete("user:bob"); // Tombstone in newer L0 SSTable
  engine.flushMemTable();

  console.log(`[L0=2, L1=0] get('user:alice'): ${JSON.stringify(engine.get("user:alice"))}`);
  console.log(`[L0=2, L1=0] get('user:bob') [tombstoned]: ${JSON.stringify(engine.get("user:bob"))}`);
  console.log(`[L0=2, L1=0] get('user:missing') [Bloom rejected]: ${JSON.stringify(engine.get("user:missing"))}`);

  // Trigger two more flushes so L0 reaches 4 SSTables and compacts into non-overlapping L1
  engine.put("user:erin", "profile_v1");
  engine.flushMemTable();
  engine.put("user:frank", "profile_v1");
  engine.flushMemTable();

  console.log(`[Post-Compaction] L0 files=${engine.l0.length}, L1 non-overlapping files=${engine.l1.length}`);
  console.log(`[Post-Compaction] get('user:alice'): ${JSON.stringify(engine.get("user:alice"))}`);
}

runDemo();

12. Summary & Decision Guide

+----------------------------------------------------------------------------------+
|                    Storage Engine Architecture Selection Matrix                  |
+--------------------------+-----------------------+-------------------------------+
| Criterion                | LSM-Tree (RocksDB)    | B+ Tree (InnoDB / Postgres)   |
+--------------------------+-----------------------+-------------------------------+
| Primary Optimization     | Heavy write workloads | High-concurrency point reads  |
| Write Path               | O(1) sequential I/O   | In-place random page updates  |
| Write Amplification (WA) | Moderate to High (LCS)| Extreme on SSDs (Random I/O)  |
| Read Amplification (RA)  | High (mitigated by BF)| Optimal (O(log_B N) pages)    |
| Space Amplification (SA) | Low (10-20% in LCS)   | Moderate (30-50% page gaps)   |
| Hardware Friendliness    | Maximizes flash life  | High write wear on SSD cells  |
+--------------------------+-----------------------+-------------------------------+

When to Select an LSM-Tree Architecture

• Time-Series and Telemetry Ingestion: When millions of sensor metrics, logs, or traces arrive per second (e.g., InfluxDB, Prometheus, ClickHouse).
• Key-Value State Stores: Distributed transactional engines requiring high throughput, low memory footprint, and compact storage (e.g., TiKV, RocksDB in CockroachDB).
• Large-Scale Distributed Databases: Systems where data must be partitioned, moved, and compacted across thousands of nodes (e.g., Apache Cassandra, ScyllaDB, Google Bigtable).

When to Select a $B^{+}$-Tree Architecture

• Read-Heavy Enterprise Systems: Workloads where 95%+ of traffic consists of complex random point queries and multi-column indexed range scans.
• Strict ACID In-Place Financial Systems: Where in-place row-level locking and transaction serialization are optimized around fixed disk pages (e.g., traditional ERP systems on PostgreSQL or Oracle).

13. Guided Design Exercises

Exercise 1: Leveled Compaction Write, Space & Read Amplification Math

A RocksDB instance stores a logical dataset of $D=256\text{ GB}$ using Leveled Compaction Strategy (LCS) with level multiplier $T=10$, $L_1$ capacity $=256\text{ MB}$, and $N_{L_0}=4$ overlapping $L_0$ SSTables.

1. Determine the number of non-overlapping levels $L$ required to hold $256\text{ GB}$ and calculate the steady-state Space Amplification ($S{A}_{\text{LCS}}$) and maximum total disk space consumed.
2. Compute the expected and worst-case Write Amplification ($W{A}_{\text{LCS}}$). If clients ingest $50\text{ MB/s}$ of logical user writes, how many $\text{MB/s}$ of physical NVMe write bandwidth are consumed by WAL + compaction?
3. Compare expected disk block reads per negative point lookup (absent key) and worst-case positive point lookup with vs. without per-SSTable Bloom filters ($p=0.01$, index/filter blocks pinned in RAM).

Exercise 2: Size-Tiered (STCS) vs. Leveled (LCS) Compaction Under Disk Constraints

An Apache Cassandra node has a $2.0\text{ TB}$ NVMe drive currently storing $1.3\text{ TB}$ of SSTables ($65\%$ disk utilization) under Size-Tiered Compaction Strategy (STCS), arranged as four $300\text{ GB}$ major-tier SSTables and several smaller SSTables.

1. Explain why triggering a major STCS compaction of the four $300\text{ GB}$ SSTables will fail with No space left on device (ENOSPC) even though $700\text{ GB}$ of disk space is currently free.
2. Calculate the temporary working-space requirement for compacting a single $64\text{ MB}$ SSTable from $L_2$ into $10$ overlapping $64\text{ MB}$ SSTables in $L_3$ under Leveled Compaction (LCS), and explain why LCS can safely operate at $80\%\text{–}85\%$ disk utilization.

Exercise 3: Debugging a RocksDB $L_0$ Write Stall & Cassandra Tombstone Storm

1. During a flash sale, RocksDB write p99 latency spikes from $0.4\text{ ms}$ to $12\text{ s}$ while rocksdb.num-files-at-level0 hits $36$. Trace the exact backpressure chain (level0_slowdown_writes_trigger $\to$ level0_stop_writes_trigger) and specify the three tuning and hardware levers to clear the stall without losing durability.
2. A team uses a Cassandra table job_queue (queue_id, job_id, status) as a FIFO worker queue, inserting and deleting $1,000\text{ jobs/sec}$ with default gc_grace_seconds = 864000 (10 days). After 2 hours, SELECT * FROM job_queue WHERE queue_id = 'payments' LIMIT 10 times out. Quantify how many tombstones a single LIMIT 10 query must scan after 2 hours and design the architectural fix.

14. Authoritative References & Version Context

• O’Neil, P., Cheng, E., Gawlick, D., & O’Neil, E. (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 33(4), pp. 351–385. https://link.springer.com/article/10.1007/s002360050048
• Athanassoulis, M., Kester, M. S., Maas, L. M., Stoica, R., Idreos, S., Ailamaki, A., & Callaghan, M. (2016). Designing Access Methods: The RUM Conjecture. Proceedings of EDBT 2016, pp. 461–466. https://openproceedings.org/2016/conf/edbt/paper-12.pdf
• Dayan, N., Athanassoulis, M., & Idreos, S. (2017). Monkey: Optimal Navigable Key-Value Store. ACM SIGMOD ‘17, pp. 79–94. https://dl.acm.org/doi/10.1145/3035918.3064054
• Meta RocksDB Official Engineering Wiki (RocksDB 9.x baseline). Leveled Compaction, Write Stalls, and Block-Based SSTable Format. https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
• Apache Cassandra Official Documentation (v4.1 / v5.0 baseline). Storage Engine, MemTables, SSTables, Tombstone gc_grace_seconds, and Compaction Strategies. https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/index.html