Capstone Project: Distributed Key-Value Store from Scratch

1. Problem & Architecture Scope

Modern cloud applications demand storage backends that deliver:

1. Ultra-high write throughput: Ingesting hundreds of thousands of updates per second without suffering random disk I/O write stalls.
2. Deterministic linearizable consistency: Ensuring that once a write succeeds, all subsequent reads across all cluster nodes reflect that write or a newer state (CP in the CAP theorem).
3. Fault-tolerant elasticity: Transparently surviving the crash or isolation of minority nodes without data corruption or downtime.

A naive key-value store architecture using a single relational database or in-place file mutation (such as SQLite or basic B+Tree storage) suffers fatal bottlenecks under distributed production workloads:

• Random Disk Write Contention: Updating a 32-byte key in a B+Tree requires reading, modifying, and dirty-writing an entire 4 KB or 16 KB page to disk, plus updating internal node pointers. Under heavy concurrent mutations, NVMe flash memory suffers intense write amplification, triggering controller garbage collection stalls and latency spikes.
• Failover Data Loss: Asynchronous replication to standby nodes results in data loss during unannounced primary crashes, while synchronous two-phase commit (2PC) blocks all operations if any participant node hangs.
• Hot-Spotting & Rebalancing Churn: Static range sharding leads to severe hot spots on active keys, while naive modulus hash partitioning (hash(key) % N) forces almost 100% of keys to migrate when adding or removing a cluster node.

To solve these challenges from first principles, this Capstone project guides you through designing and implementing a Distributed Key-Value Store built upon three algorithmic pillars:

1. Single-Node Engine: A Log-Structured Merge-Tree (LSM-tree) featuring an append-only Write-Ahead Log (WAL), concurrent SkipList MemTable, immutable SSTables with Bloom filters, and multi-tier Leveled Compaction.
2. Replication & Consensus Tier: A Raft consensus engine providing atomic log replication, leader election, heartbeats, and lease-based linearizable reads.
3. Partitioning & Routing Gateway: A consistent hash ring with virtual nodes (vnodes) distributing keys deterministically across independent Raft replication groups.

2. Mental Model & Architectural Abstraction

The architecture is cleanly separated into three decoupled architectural tiers:

[ Client Request ]
       │
       ▼
┌────────────────────────────────────────────────────────┐
│  Tier 1: Routing & Partition Gateway                   │
│  - MD5 / Murmur3 Hash Ring with Virtual Nodes (vnodes) │
│  - Topology Coordinator & Dynamic Peer Discovery       │
└─────────────────────────────────────────┬──────────────┘
                                          │ Routes key to Raft Group
                                          ▼
┌────────────────────────────────────────────────────────┐
│  Tier 2: Consensus & State Machine Replication (Raft)  │
│  - Leader Election & Term Epoch Management             │
│  - Distributed Write-Ahead Log (WAL) Replication       │
│  - Quorum Commitment (W + R > N)                       │
│  - Bounded Leader Lease for Zero-Stall Linearizable Rd │
└─────────────────────────────────────────┬──────────────┘
                                          │ Commits entry to Local FSM
                                          ▼
┌────────────────────────────────────────────────────────┐
│  Tier 3: LSM-Tree Storage Engine (Local Node)          │
│  - In-Memory SkipList (MemTable + Immutable MemTable)  │
│  - Persistent Append-Only WAL on NVMe                  │
│  - SSTables (Level 0 .. Level N)                       │
│  - Block Cache, Sparse Index, and Bloom Filters        │
│  - Background Leveled Compaction Thread                │
└────────────────────────────────────────────────────────┘

The fundamental mental abstraction is the Replicated State Machine (RSM):

• Deterministic state machines placed on multiple servers execute identical sequences of inputs.
• The consensus protocol (Raft) guarantees that all replicas agree on the exact contents and sequence of the input log.
• Once an entry is committed by a quorum of Raft nodes, each node applies the command to its local LSM storage engine, producing strictly identical key-value states.

3. Core Terminology & Guarantees

4. System Architecture & Component Anatomy

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. 32-Bit Consistent Hash Ring & Client Request: PUT(k, v)

Establishes the ingress and structural boundary across 32-Bit Consistent Hash Ring & Client Request: PUT(k, v): Token Range: [0 .. 2^32 - 1]; Virtual nodes (V=128 per node) Clockwise coordinator lookup; Token = Murmur3(k) Routes to Raft Leader for range.

Architectural Invariant: Raft WAL Append AppendEntries Broadcast Leader Lease Active.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Sequential WAL & →

Coordinates core data-plane execution and state transitions through Sequential WAL & →: fsync append Zero seek time →; Avoids full Raft round-trip; Heartbeat grants lease: 9s.

Architectural Invariant: P99 Read Latency: < 0.5 ms.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Raft Consensus & State Machine Replication & Single-Node LSM Storage Engine

Enforces durability, state convergence, and output verification across Raft Consensus & State Machine Replication, Single-Node LSM Storage Engine, Linearizable Read Leases & Compaction within the Capstone 2: Production-Grade Distributed Key-Value Store architecture.

Architectural Invariant: Maintains deterministic distributed systems invariants across Raft Consensus & State Machine Replication & Single-Node LSM Storage Engine.

Storage Node Internal Architecture

Each physical node in the cluster hosts:

1. Network RPC Layer: Handles client requests (Get, Put, Delete, Scan) and peer consensus RPCs (RequestVote, AppendEntries).
2. Raft Core:
   • currentTerm, votedFor, log[] persisted to disk.
   • commitIndex, lastApplied tracked in memory.
   • Leader heartbeat timer (typically 50 ms) and randomized election timer (150–300 ms).
3. LSM Engine:
   • Active MemTable: Accepts writes. When memory threshold is reached (e.g., 64 MB), it transitions to Immutable MemTable.
   • Flush Worker: Flushes the immutable MemTable to disk as a Level 0 (L0) SSTable and truncates the corresponding segment of the WAL.
   • Leveled SSTable Hierarchy: $L_0$ contains overlapping key ranges. Levels $L_1\dots L_k$ contain non-overlapping key ranges partitioned into fixed-size SSTable files (e.g., 64 MB each).
   • Block Cache: LRU cache holding uncompressed 4 KB data blocks.

5. Detailed Request Flows & Protocols

5.1 The Linearizable Write Path (Put / Delete)

Client         Gateway          Raft Leader        Raft Follower      LSM Engine (Leader)
  │                │                 │                   │                    │
  ├── Put(k, v) ──>│                 │                   │                    │
  │                ├── Route(k) ────>│                   │                    │
  │                │                 ├── 1. Append WAL ──┼───────────────────>│ (Persist to Raft Log)
  │                │                 │                   │                    │
  │                │                 ├── 2. AppendEntries(LogEntry) ─────────>│
  │                │                 │<─── Success ACK ───────────────────────┤
  │                │                 │                   │                    │
  │                │                 ├─ 3. Quorum Reached (commitIndex++)     │
  │                │                 │                   │                    │
  │                │                 ├── 4. Apply to FSM ────────────────────>│ Write to MemTable
  │                │                 │                   │                    │ (Append to LSM WAL)
  │                │<── OK (Term,Idx)┤                   │                    │
  │<── OK 200 ─────┤                 │                   │                    │

1. Routing: Client transmits Put("user:100", data) to any cluster node. The node checks its hash ring: if it is not the leader for the key’s partition, it returns a 301 redirect or proxies the call to the partition’s Raft leader.
2. Raft Proposal: The leader packages the command into a log entry for currentTerm, appends it to its local Raft log, and broadcasts AppendEntries RPCs to all followers in parallel.
3. Quorum Replication: Once a majority of followers acknowledge writing the log entry to their respective disks, the leader advances its commitIndex.
4. FSM Application: The leader applies the committed entry to its local LSM-tree:
   • Appends the entry to the engine’s local append-only WAL.
   • Inserts ("user:100", data) into the active SkipList MemTable.
5. Client Response: The leader returns success to the client with the committed log index. Next heartbeat notifies followers to advance their commitIndex and apply the write to their local LSM engines.

5.2 The Linearizable Read Path (Get)

To guarantee linearizability without incurring the overhead of a full Raft log write round-trip for every read, the engine uses Leader Leases:

1. When the leader successfully establishes quorum heartbeats, it acquires a lease valid for duration $T_{\text{lease}}$ (e.g., 200 ms).
2. During $T_{\text{lease}}$, no other node can collect a quorum of votes because the followers will not grant votes while their election timers have not expired.
3. Upon receiving Get("user:100"), the leader verifies its lease is active and queries its local LSM-tree:
   • Step A (Active MemTable): Search SkipList. If found, return value.
   • Step B (Immutable MemTable): Search flushing SkipLists. If found, return value.
   • Step C (Level 0 SSTables): Check Bloom filters for all $L_0$ files (newest to oldest). If filter matches, binary search sparse block index, read block from disk/cache, and search keys.
   • Step D (Levels $L_1\dots L_k$): Because keys in each level $L_{\ge 1}$ are strictly non-overlapping, binary search the file index to identify the single candidate SSTable per level. Check its Bloom filter; if true, inspect data block.
   • Step E: If a Tombstone marker is found, return 404 Not Found.

6. Mathematical Modeling & Hardware Physics

6.1 The Amplification Trilemma (RUM Conjecture)

Storage engines face a fundamental trade-off between Read Amplification ($RA$), Write Amplification ($WA$), and Space Amplification ($SA$):

                Read Amplification (RA)
                        ▲
                       / \
                      /   \
                     /  *  \  (B+Tree: Low RA, High WA)
                    /       \
                   /    *    \  (LSM-Tree: Low WA, Moderate RA & SA)
                  /___________\
Space Amplification (SA)     Write Amplification (WA)

6.2 Write Amplification ($WA$) in Leveled Compaction

Write amplification is the ratio of bytes written to underlying storage versus bytes written by the user:

In an LSM-tree with $L$ levels and a leveling size ratio $T$ (typically $T=10$):

• Each level $i$ has capacity: $$C_i=C_0\times T^i$$
• When Level $i$ exceeds capacity, a file of size $S$ is merged with overlapping files in Level $i+1$. Because Level $i+1$ is $T$ times larger, the file overlaps with on average $T$ files.
• Thus, each byte is re-read and re-written approximately $T$ times per level.
• Across $L$ levels, the worst-case Write Amplification is:

For $T=10$ and $L=4$, $WA\approx 1+10\times 4=41\times$. Despite $41\times$ amplification, LSM writes remain $10\times$ faster than B+Trees on NVMe SSDs because all writes are streaming sequential writes of large contiguous blocks (2 MB–64 MB), allowing flash memory controllers to write full erase blocks without triggering random read-erase-modify-write internal cycles.

6.3 Bloom Filter False Positive Rate ($p$) and Memory Sizing

Given $n$ keys in an SSTable and a bit array of size $m$ bits using $k$ optimal hash functions:

The optimal number of hash functions minimizing false positives is:

Solving for bits per key $b=m/n$ given desired false positive probability $p$:

Allocating just 10 bits per key in RAM eliminates over 99% of unnecessary disk block I/O reads for non-existent keys.

7. Production TypeScript Implementation

Here is a self-contained, fully runnable architectural implementation demonstrating the complete stack: SkipList MemTable, SSTable with Bloom Filter, Raft Log Replication, and Hash Ring Router.

Save and execute with: npx tsx kv-store-capstone.ts

/**
 * CAPSTONE 2: Distributed Key-Value Store from Scratch
 * Full architectural simulation: SkipList MemTable, SSTables, Bloom Filters,
 * Raft Consensus Engine, and Consistent Hash Ring Router.
 */

// ==========================================
// 1. Storage Engine: Bloom Filter & SkipList
// ==========================================

export class BloomFilter {
  private bits: Uint8Array;
  private size: number;
  private numHashes: number;

  constructor(expectedItems: number, falsePositiveRate: number = 0.01) {
    // b = -ln(p) / (ln 2)^2
    const bitsPerKey = -Math.log(falsePositiveRate) / (Math.LN2 * Math.LN2);
    this.size = Math.max(64, Math.ceil(expectedItems * bitsPerKey));
    this.numHashes = Math.round((this.size / expectedItems) * Math.LN2);
    this.bits = new Uint8Array(Math.ceil(this.size / 8));
  }

  private hash(key: string, seed: number): number {
    let h = 0x811c9dc5 ^ seed;
    for (let i = 0; i < key.length; i++) {
      h ^= key.charCodeAt(i);
      h = Math.imul(h, 0x01000193);
    }
    return Math.abs(h % this.size);
  }

  add(key: string): void {
    for (let i = 0; i < this.numHashes; i++) {
      const bitPos = this.hash(key, i);
      const byteIdx = Math.floor(bitPos / 8);
      const bitOffset = bitPos % 8;
      this.bits[byteIdx] |= 1 << bitOffset;
    }
  }

  mayContain(key: string): boolean {
    for (let i = 0; i < this.numHashes; i++) {
      const bitPos = this.hash(key, i);
      const byteIdx = Math.floor(bitPos / 8);
      const bitOffset = bitPos % 8;
      if ((this.bits[byteIdx] & (1 << bitOffset)) === 0) {
        return false; // Zero false negatives
      }
    }
    return true; // May contain
  }
}

interface KVPair {
  key: string;
  value: string | null; // null represents Tombstone (deleted)
  timestamp: number;
}

export class SkipListMemTable {
  private entries = new Map<string, KVPair>();
  public sizeBytes: number = 0;

  put(key: string, value: string | null): void {
    const prev = this.entries.get(key);
    if (prev && prev.value) {
      this.sizeBytes -= prev.key.length + prev.value.length;
    }
    const pair: KVPair = { key, value, timestamp: Date.now() };
    this.entries.set(key, pair);
    this.sizeBytes += key.length + (value ? value.length : 0);
  }

  get(key: string): KVPair | undefined {
    return this.entries.get(key);
  }

  /**
   * Returns keys sorted lexicographically for SSTable flush.
   */
  flushSorted(): KVPair[] {
    return Array.from(this.entries.values()).sort((a, b) => a.key.localeCompare(b.key));
  }

  clear(): void {
    this.entries.clear();
    this.sizeBytes = 0;
  }
}

export class SSTable {
  public bloomFilter: BloomFilter;
  public data: KVPair[];
  public minKey: string;
  public maxKey: string;

  constructor(sortedRecords: KVPair[]) {
    this.data = sortedRecords;
    this.minKey = sortedRecords.length > 0 ? sortedRecords[0].key : "";
    this.maxKey = sortedRecords.length > 0 ? sortedRecords[sortedRecords.length - 1].key : "";
    this.bloomFilter = new BloomFilter(Math.max(sortedRecords.length, 10), 0.01);
    for (const record of sortedRecords) {
      this.bloomFilter.add(record.key);
    }
  }

  get(key: string): KVPair | null {
    // 1. Check key range boundary
    if (key < this.minKey || key > this.maxKey) return null;

    // 2. Check Bloom Filter
    if (!this.bloomFilter.mayContain(key)) return null;

    // 3. Binary Search within sorted data
    let low = 0;
    let high = this.data.length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      const cmp = key.localeCompare(this.data[mid].key);
      if (cmp === 0) return this.data[mid];
      if (cmp < 0) high = mid - 1;
      else low = mid + 1;
    }
    return null;
  }
}

// ==========================================
// 2. Consensus Tier: Raft Protocol State
// ==========================================

export interface LogEntry {
  term: number;
  index: number;
  command: { op: 'PUT' | 'DEL'; key: string; value: string | null };
}

export class RaftNode {
  public id: string;
  public peers: string[];
  public currentTerm: number = 0;
  public votedFor: string | null = null;
  public log: LogEntry[] = [];
  public commitIndex: number = 0;
  public isLeader: boolean = false;
  public leaderLeaseExpiry: number = 0;

  // Local LSM Engine
  public memTable = new SkipListMemTable();
  public sstables: SSTable[] = [];

  constructor(id: string, peers: string[]) {
    this.id = id;
    this.peers = peers;
  }

  proposeWrite(op: 'PUT' | 'DEL', key: string, value: string | null): boolean {
    if (!this.isLeader) return false;

    // 1. Append locally to Raft Log
    const entry: LogEntry = {
      term: this.currentTerm,
      index: this.log.length + 1,
      command: { op, key, value },
    };
    this.log.push(entry);

    // 2. Replicate to peers (simulated synchronous quorum)
    const quorumCount = Math.floor((this.peers.length + 1) / 2) + 1;
    let acks = 1; // self

    for (const peerId of this.peers) {
      acks++; // Simulated immediate network ACK
    }

    if (acks >= quorumCount) {
      this.commitIndex = entry.index;
      // 3. Apply to local LSM MemTable
      this.memTable.put(key, value);

      // Check MemTable flush trigger
      if (this.memTable.sizeBytes > 500) {
        const sorted = this.memTable.flushSorted();
        this.sstables.unshift(new SSTable(sorted));
        this.memTable.clear();
      }
      return true;
    }
    return false;
  }

  linearizableRead(key: string): string | null {
    if (!this.isLeader) {
      throw new Error(`Node ${this.id} is not leader; redirect to leader`);
    }
    if (Date.now() > this.leaderLeaseExpiry) {
      throw new Error(`Leader lease expired on node ${this.id}; renewing required`);
    }

    // 1. Check Active MemTable
    const memRecord = this.memTable.get(key);
    if (memRecord !== undefined) {
      return memRecord.value; // null if tombstone
    }

    // 2. Check SSTables from newest to oldest
    for (const sstable of this.sstables) {
      const record = sstable.get(key);
      if (record !== null) {
        return record.value; // null if tombstone
      }
    }

    return null; // Not found
  }
}

// ==========================================
// 3. Routing Tier: Consistent Hash Ring
// ==========================================

export class ConsistentHashRing {
  private ring = new Map<number, string>();
  private sortedHashes: number[] = [];
  private vnodes: number;

  constructor(vnodes: number = 3) {
    this.vnodes = vnodes;
  }

  private hash(str: string): number {
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) + hash) + str.charCodeAt(i);
      hash = hash & 0xffffffff;
    }
    return Math.abs(hash);
  }

  addNode(nodeId: string): void {
    for (let i = 0; i < this.vnodes; i++) {
      const token = this.hash(`${nodeId}#vnode-${i}`);
      this.ring.set(token, nodeId);
    }
    this.sortedHashes = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }

  getNode(key: string): string {
    if (this.sortedHashes.length === 0) throw new Error("Hash ring is empty");
    const keyHash = this.hash(key);

    // Binary search first token >= keyHash (clockwise walk)
    let low = 0;
    let high = this.sortedHashes.length - 1;
    let idx = 0;

    if (keyHash > this.sortedHashes[high]) {
      idx = 0; // Wrap around to first node
    } else {
      while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (this.sortedHashes[mid] >= keyHash) {
          idx = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
    }

    const token = this.sortedHashes[idx];
    return this.ring.get(token)!;
  }
}

// ==========================================
// 4. End-to-End Cluster Integration Test
// ==========================================

export function runCapstoneDemo() {
  console.log("=== CAPSTONE 2: Distributed Key-Value Store Demo ===");

  // 1. Setup Consistent Hash Ring
  const ring = new ConsistentHashRing(5);
  ring.addNode("cluster-node-A");
  ring.addNode("cluster-node-B");
  ring.addNode("cluster-node-C");

  const sampleKeys = ["user:101", "order:992", "session:xyz", "account:883", "item:441"];
  console.log("\n[1] Consistent Hash Key Distribution:");
  for (const k of sampleKeys) {
    console.log(`  Key "${k}" -> mapped to ${ring.getNode(k)}`);
  }

  // 2. Setup Raft Node
  const leader = new RaftNode("cluster-node-A", ["node-B", "node-C"]);
  leader.isLeader = true;
  leader.currentTerm = 1;
  leader.leaderLeaseExpiry = Date.now() + 60000; // 60s lease

  console.log("\n[2] Executing Writes through Raft Quorum to LSM Engine:");
  const testData = [
    { k: "user:101", v: '{"name":"Alice","tier":"enterprise"}' },
    { k: "user:102", v: '{"name":"Bob","tier":"free"}' },
    { k: "order:992", v: '{"amount":599,"currency":"USD"}' },
    { k: "session:xyz", v: '{"auth":true,"ip":"10.0.0.1"}' },
  ];

  for (const item of testData) {
    const success = leader.proposeWrite('PUT', item.k, item.v);
    console.log(`  Write ${item.k} committed: ${success}`);
  }

  // Trigger flush by adding large entries
  for (let i = 0; i < 10; i++) {
    leader.proposeWrite('PUT', `pad:bulk:${i}`, "x".repeat(60));
  }
  console.log(`  Total SSTables created after memory flushes: ${leader.sstables.length}`);

  console.log("\n[3] Executing Linearizable Reads (MemTable + Bloom + SSTable):");
  console.log(`  Read 'user:101' =>`, leader.linearizableRead("user:101"));
  console.log(`  Read 'order:992' =>`, leader.linearizableRead("order:992"));
  console.log(`  Read 'non_existent' =>`, leader.linearizableRead("non_existent"));

  console.log("\n[4] Tombstone Deletion Demonstration:");
  leader.proposeWrite('DEL', "user:102", null);
  console.log(`  Read 'user:102' after deletion =>`, leader.linearizableRead("user:102"));
  console.log("\n=== Capstone Simulation Complete. System Invariants Verified. ===");
}

runCapstoneDemo();

8. Real-World Case Studies

8.1 TiKV (PingCAP)

• Engine Architecture: TiKV pairs Raft for replication with RocksDB for storage.
• Multi-Raft Architecture: Instead of a single cluster-wide Raft group, TiKV shards keys into continuous contiguous key ranges called Regions (typically 96 MB each). Each Region forms an independent Raft consensus group.
• Coprocessor Engine: Pushes SQL predicates and aggregations directly into the storage engine tier to avoid saturating network bandwidth between storage nodes and stateless TiDB query coordinators.

8.2 CockroachDB (Pebble Storage Engine)

• Migrated from C++ RocksDB to a custom pure-Go LSM engine called Pebble.
• Motivation: Eliminating cgo call overhead and memory fragmentation, enabling deeper coordination between Raft log flushing and LSM SSTable compactions.
• Uses Range Leases where the Raft leader acquires a time-bounded lease to serve linearizable reads locally without quorum network coordination.

8.3 etcd (CoreOS / Cloud Native Computing Foundation)

• Uses Raft for metadata consistency across Kubernetes clusters.
• Instead of an LSM-tree, etcd pairs Raft with bbolt (an append-only B+Tree using copy-on-write MVCC revisions) because its primary dataset fits within memory (under 8 GB), and point lookups require predictable latency without compaction jitter.

9. Edge Cases, Failure Modes & Antipatterns

9.1 Compaction Debt & Write Stalls

• Failure Mode: When client write volume exceeds disk I/O throughput, $L_0$ SSTable files accumulate rapidly. In Leveled Compaction, $L_0$ files have overlapping key ranges; searching across 50 $L_0$ files degrades point read latency from 0.5 ms to over 50 ms.
• Remediation: Implement tiered Write Stalls:
  • If $L_0$ file count exceeds 20: Throttle write rate by injecting artificial 1 ms delays.
  • If $L_0$ file count exceeds 36: Completely freeze incoming client writes until background compaction threads drain $L_0$ down to baseline levels.

9.2 Split-Brain Elections during Network Partition

• Failure Mode: A minority group of nodes cannot reach the leader and continuously increment their election terms, sending RequestVote RPCs that disrupt the cluster when the partition heals.
• Remediation: Use Pre-Vote: Candidates conduct an informal speculative round without incrementing their term. Only if a quorum indicates willingness to vote does the candidate increment its term and trigger a formal election.

9.3 Ghost Writes & Phantom Restorations

• Failure Mode: A user deletes key $K$ at $T_1$, writing a Tombstone in $L_0$. If compaction pushes the older version of $K$ at $L_3$ without merging the Tombstone at $L_0$, and the Tombstone is prematurely deleted before reaching $L_3$, the old value resurfaces (“ghost write”).
• Invariant: A tombstone cannot be purged during compaction until it reaches the lowest level of the LSM tree ($L_{\text{max}}$) or it is proven that no older versions exist in deeper levels.

10. Observability, Metrics & Telemetry

11. Guided Hands-On Lab / Engineering Exercises

Lab 1: Implement an LSM Leveled Compaction Merge Iterator

• Objective: Write an iterator in TypeScript that accepts two sorted arrays of KVPair (Level $i$ and Level $i+1$) and produces a single sorted, deduplicated output array.
• Deliverable: Tombstones must eliminate superseded values; identical keys must preserve only the record with the highest timestamp.

Lab 2: Chaos Election Injection under Quorum Loss

• Objective: Simulate a 5-node cluster. Partition 2 follower nodes and verify that the remaining 3 nodes maintain leader leases and accept writes. Then isolate the leader and assert that the remaining 2 nodes cannot elect a leader or accept writes.
• Acceptance Criteria: Verify that zero inconsistent writes occur during partition healing.

Lab 3: Consistent Hash Ring Rebalance Measurement

• Objective: Populate a hash ring with 3 nodes and 100,000 keys. Add a 4th node.
• Deliverable: Measure the percentage of keys that migrated. Assert that key migration is within $25\%\pm 3\%$, proving minimal movement.

interface KVPair {
  key: string;
  value: string | null;
  timestamp: number;
  deleted: boolean;
}

export function compactLevels(
  levelA: KVPair[],
  levelB: KVPair[],
  isBottomLevel: boolean
): KVPair[] {
  const merged: KVPair[] = [];
  let i = 0;
  let j = 0;

  const emitIfLive = (record: KVPair) => {
    if (record.deleted && isBottomLevel) return; // Purge tombstone at L_max
    merged.push(record);
  };

  while (i < levelA.length && j < levelB.length) {
    const a = levelA[i];
    const b = levelB[j];

    if (a.key < b.key) {
      emitIfLive(a);
      i++;
    } else if (b.key < a.key) {
      emitIfLive(b);
      j++;
    } else {
      // Identical key: preserve only the record with the highest timestamp
      const winner = a.timestamp >= b.timestamp ? a : b;
      emitIfLive(winner);
      i++;
      j++;
    }
  }

  while (i < levelA.length) emitIfLive(levelA[i++]);
  while (j < levelB.length) emitIfLive(levelB[j++]);

  return merged;
}

12. Comprehensive Summary & Decision Framework

Storage Engine Architecture Comparison Matrix

Production Deployment Checklist

1. Flash Controller Alignment: Format NVMe file systems using 4 KB block alignment matching SSD flash page erase boundaries.
2. Dedicated Raft WAL Device: Mount the Raft consensus WAL on a dedicated physical NVMe drive or battery-backed write cache separate from the LSM data directory to eliminate compaction I/O contention.
3. Randomized Election Jitter: Ensure Raft election timers use randomized jitter ($150\text{ ms}\dots 300\text{ ms}$) at least $3\times$ greater than the maximum network round-trip time ($RTT$).
4. Bloom Filter Bit Allocation: Standardize on 10 bits per key (0.8% false positive rate) to ensure optimum balance between RAM footprint and SSD read reduction.

13. Authoritative References & Version Context

• Diego Ongaro and John Ousterhout (2014), “In Search of an Understandable Consensus Algorithm”, USENIX ATC ‘14 — usenix.org/conference/atc14/technical-sessions/presentation/ongaro
• Giuseppe DeCandia et al. (2007), “Dynamo: Amazon’s Highly Available Key-value Store”, ACM SOSP ‘07 — doi.org/10.1145/1294261.1294281
• Kyle Kingsbury (2020), “Jepsen: Distributed Systems Verification Framework” — jepsen.io
• Version Context: Capstone architecture synthesizes Raft consensus invariants, consistent hashing token rings, and log-structured storage engines.