Architecture Study: etcd Internals — MVCC, Bbolt & Raft Consensus

1. Problem & Architecture Scope

Project Identity, Version & License Baseline

etcd is the distributed, strongly consistent key-value store that serves as the single source of truth for Kubernetes, storing the entire cluster state: Pods, Services, CRDs, Deployments, and Secrets.

A control-plane data store for orchestrating distributed infrastructure faces unique engineering demands:

1. Strict Linearizable Correctness: Two controllers attempting to acquire the same leader lease or allocate the same IP address must never both succeed.
2. Deterministic Historical Revisions: Controllers need to watch resource changes continuously. If a network blip disconnects a controller for 30 seconds, it must be able to reconnect and request: “Give me all events since revision 104,291 without missing a single transition.”
3. High-Throughput Watchers: Thousands of kubelet agents and API server components maintain long-running watch connections on specific key prefixes (e.g., /registry/pods/node-1/).
4. Predictable Latency: Disk writes must complete in single-digit milliseconds; long compaction stalls or garbage collection pauses directly cascade into Kubernetes API server timeouts and worker node flapping.

In this architecture study, we deconstruct etcd v3’s layered internals:

• The decoupled Raft Consensus Engine (etcd/raft).
• The MVCC Architecture: Global 64-bit revisions, generations, and the in-memory treeIndex.
• The persistent Bbolt Copy-on-Write Storage Backend.
• High-performance read paths: ReadIndex vs LeaseRead.
• Operational realities: Bbolt fragmentation, compaction debt, and disk quota alarms.

2. Mental Model & Architectural Abstraction

The architecture is cleanly layered into four decoupled tiers:

[ Client / Kube-API-Server ]
             │ gRPC / HTTP/2
             ▼
┌────────────────────────────────────────────────────────┐
│  Tier 1: gRPC API Server & Watch Hub                   │
│  - KVServer, LeaseServer, WatchServer                  │
│  - SyncedWatchers (in-memory) & UnsyncedWatchers (disk)│
└──────────────────────────┬─────────────────────────────┘
                           │ Write Proposal / Linearizable Read
                           ▼
┌────────────────────────────────────────────────────────┐
│  Tier 2: Raft Consensus Engine (etcd/raft)             │
│  - Monotonic Terms, Leader Election, Quorum Matching   │
│  - Persistent Append-Only WAL (`*.wal` on disk)        │
│  - Raft Snapshots (`*.snap` on disk)                   │
└──────────────────────────┬─────────────────────────────┘
                           │ Apply Committed Entry
                           ▼
┌────────────────────────────────────────────────────────┐
│  Tier 3: In-Memory treeIndex (B-Tree in RAM)           │
│  - Maps user key -> keyIndex{revisions, generations}   │
│  - Resolves (key, rev) -> revision(main, sub) in < 1µs │
└──────────────────────────┬─────────────────────────────┘
                           │ Fetch Value by Revision Key
                           ▼
┌────────────────────────────────────────────────────────┐
│  Tier 4: Persistent Bbolt Storage Engine (Disk)        │
│  - Copy-on-Write B+Tree over Memory-Mapped File (mmap) │
│  - Bucket "key": revision(main, sub) -> KeyValue proto │
│  - Freelist Page Allocator & Asynchronous Fsync        │
└────────────────────────────────────────────────────────┘

The fundamental design insight of etcd v3 is the separation of user keys from disk keys:

• In the persistent disk storage (bbolt), the key is NOT the user string (/registry/pods/default/nginx).
• The disk key is the composite monotonic revision tuple (main_rev, sub_rev) ($16\text{–}17\text{ bytes}$: an 8-byte big-endian main_rev transaction counter + _ separator + an 8-byte big-endian sub_rev operation index within the transaction).
• Because revisions only increase, all writes to bbolt are sequential appends to the right edge of the B+Tree.
• The in-memory treeIndex maintains the mapping from user keys to their respective revision timelines.

3. Core Terminology & Guarantees

4. System Architecture & Component Anatomy

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. gRPC Server and API Facade & gRPC Multiplexing

Establishes the ingress and structural boundary across gRPC Server and API Facade & gRPC Multiplexing: HTTP/2 Sub-Stream Per Watcher; ReadIndex RPC confirms leader quorum Bypasses Raft log write disk IO; Heartbeat TTL management Keys bound to lease expire together.

Architectural Invariant: Pure state machine design: zero network or disk IO inside core logic.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Persistent Raft WAL & Quorum Replication

Coordinates core data-plane execution and state transitions through Persistent Raft WAL & Quorum Replication: Sequential disk write Pre-allocated 64MB files O_SYNC / fsync flushed; Leader broadcasts to peers Majority (N/2 + 1) ACKs Advance commitIndex; Triggers snapshot when WAL exceeds 10,000 entries (configurable) Truncates older WAL files; fast recovery for lagging learner nodes Ensures constant bound on startup recovery time.

Architectural Invariant: Triggers snapshot when WAL exceeds 10,000 entries (configurable) Truncates older WAL files; fast recovery for lagging learner nodes Ensures constant bound on startup recovery time.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. In-Memory treeIndex (B-Tree) & Google B-Tree in RAM

Enforces durability, state convergence, and output verification across In-Memory treeIndex (B-Tree) & Google B-Tree in RAM: Maps user key to revision history "foo" -> keyIndex{revisions}; keyIndex: generations and tombstones; main: increments per Raft transaction.

Architectural Invariant: Given key and rev, returns Bbolt rev key Range scans walk RAM B-tree leaves Zero disk seek during key lookup Resolves target revisions in sub-microsec.

Deep Component Breakdown:

1. The Pure State Machine Raft Library (etcd/raft):
   • Unlike many Raft implementations that entangle networking, disk I/O, and timers inside consensus logic, etcd/raft is a pure deterministic state machine.
   • It performs zero disk writes and zero network system calls.
   • The application feeds messages (raft.Step()) and ticks (raft.Tick()) into the engine. The engine emits a Ready struct containing:
     • Entries: Uncommitted log entries to write to the WAL.
     • Messages: Outbound network RPCs to send to peers.
     • CommittedEntries: Entries agreed upon by quorum ready to be applied to the MVCC state machine.
2. Persistent Raft WAL (wal/wal.go):
   • Pre-allocates 64 MB disk files to eliminate filesystem metadata allocation stalls.
   • Appends entries sequentially and issues an explicit fsync before acknowledging consensus.
3. The MVCC Storage Subsystem (mvcc/):
   • Maintains the dual index: RAM-resident treeIndex and disk-resident bbolt.
   • Manages the WatchableKV: Separates watchers into synced (up to date with latest revision, notified directly from memory) and unsynced (catching up on historical revisions, reading from bbolt).
4. Bbolt Backend (mvcc/backend/):
   • Maps the entire database file into the process’s virtual address space via mmap(2).
   • Read transactions execute concurrently without locks; write transactions are strictly serialized via a single mutex.

5. Detailed Request Flows & Protocols

5.1 Mutating Write Path (Put / Txn)

Client             KVServer             Raft Core              WAL (Disk)            MVCC / Bbolt
  │                   │                     │                      │                       │
  ├── Put(k, v) ─────>│                     │                      │                       │
  │                   ├── Step(MsgProp) ───>│                      │                       │
  │                   │                     ├── Ready: Entries ───>│ (Append & fsync)      │
  │                   │                     ├── Ready: Messages ──────────────────────────>│ (Broadcast to Peers)
  │                   │                     │<── Quorum ACKs ──────────────────────────────┤
  │                   │                     │                      │                       │
  │                   │<── CommittedEntries ┤                      │                       │
  │                   ├── Apply Entry ────────────────────────────────────────────────────>│
  │                   │                                                                    ├── 1. Rev = ++curRev
  │                   │                                                                    ├── 2. Bbolt.Put(Rev, KV)
  │                   │                                                                    ├── 3. treeIndex.Put(k, Rev)
  │                   │                                                                    └── 4. Notify Watchers
  │<── OK (Rev) ──────┤                                                                    │

1. Client Proposal: Client sends a gRPC Put(key, value) request to the leader.
2. Raft Replication: The leader wraps the command in an internal protobuf proposal and passes it to etcd/raft. The entry is written to the local WAL file (fsync) and broadcast to followers via Netty/HTTP2.
3. Quorum Commitment: Once a majority of nodes acknowledge writing the entry to disk, the leader marks the entry committed.
4. Application to MVCC:
   • The global revision counter is incremented: currentRev++.
   • A mvccpb.KeyValue protobuf is constructed and written to bbolt bucket "key" using the composite big-endian revision tuple (main_rev, sub_rev) as the primary key.
   • The user key string is inserted into treeIndex in RAM, appending the new revision to the key’s active generation.
   • Active watchers monitoring this key prefix are immediately notified.
5. Response: The committed revision is returned to the client.

5.2 Linearizable Read Path (ReadIndex)

Client             KVServer              Raft Core              Peers (Followers)       Local Bbolt / RAM
  │                   │                      │                         │                        │
  ├── Get(key) ──────>│                      │                         │                        │
  │                   ├── ReadIndex() ──────>│                         │                        │
  │                   │   (Records commitIdx)├── Heartbeat (Quorum) ──>│                        │
  │                   │                      │<── Majority ACKs ───────┤                        │
  │                   │<── ReadIndex OK ─────┤                         │                        │
  │                   ├── Wait applied >= commitIndex                  │                        │
  │                   ├── Read from local storage ─────────────────────────────────────────────>│
  │                   │   1. treeIndex.Get(key) -> targetRev                                   │
  │                   │   2. bbolt.Get(targetRev) -> Value                                     │
  │<── OK (Value) ────┤                                                                        │

1. Read Request: Client requests Get(key, WithSerializable=false).
2. Quorum Verification: The leader captures its current commitIndex and sends a lightweight heartbeat round to peers. If a majority responds, the leader confirms it remains the valid leader.
3. Applied Index Barrier: The leader waits until its state machine has finished applying all entries up to commitIndex.
4. Local Execution: The leader resolves the user key in treeIndex in RAM, retrieving the latest revision $R$, and reads the value directly from bbolt’s memory-mapped pages without writing to disk.

6. Mathematical Modeling & Hardware Physics

6.1 Bbolt Storage Layout & Page Allocation Math

A bbolt database consists of contiguous $4\text{ KB}$ disk pages:

• Meta Pages (Pages 0 & 1): Hold database root pointers, page size, and alternating transaction IDs for copy-on-write consistency.
• Branch Pages: Internal B+Tree nodes storing child page IDs and separator keys.
• Leaf Pages: Store key-value pairs. In etcd, on-disk keys are composite revision tuples (main_rev, sub_rev) ($8\text{ bytes}$ big-endian main_rev + $8\text{ bytes}$ big-endian sub_rev, plus a 1-byte _ separator in revToBytes):

If a leaf page has $4096\text{ bytes}$ and each key-value entry has average value size $S_v=1000\text{ bytes}$: $$\text{Entries Per Leaf Page}\approx \frac{4096-\text{PageHeader}(16\text{ B})}{16\text{ B (key)}+1000\text{ B (val)}+16\text{ B (leafElem)}}\approx 3.9⟹3\text{ entries per page}$$

6.2 Write Amplification during Compaction

When writing at a sustained rate of $W_{\text{rate}}=5,000\text{ writes/sec}$ with $1\text{ KB}$ values:

In a 2 GB database, reaching the quota takes: $$\text{Time to Quota}=\frac{2000\text{ MB}}{300\text{ MB/min}}\approx 6.6\text{ minutes!}$$

Without frequent automated compaction (--auto-compaction-retention=1h), etcd will exhaust its storage quota and lock into a read-only state.

6.3 Memory Overhead of treeIndex

Each distinct key in etcd is maintained in RAM by treeIndex:

• keyIndex struct: $\approx 128\text{ bytes}$
• Key string: $\approx 64\text{ bytes}$
• Historical revisions (average 5 versions): $5\times 16\text{ bytes}=80\text{ bytes}$
• Total RAM per key: $\approx 272\text{ bytes}$

For a cluster with $1,000,000$ active Kubernetes keys: $$\text{treeIndex RAM Footprint}\approx 10^6\times 272\text{ bytes}\approx 272\text{ MB of RAM}$$ This lightweight memory footprint explains why etcd easily holds millions of keys in memory while delegating payload storage to disk.

7. Production TypeScript Implementation

This self-contained TypeScript simulation implements:

1. Revision: 64-bit monotonically increasing (main, sub) revisions.
2. TreeIndex: In-memory multi-version revision mapping.
3. BboltBackend: Simulated copy-on-write key-value page storage.
4. EtcdServer: Complete transaction coordinator supporting Put, Get with ReadIndex, Compaction, and Watches.

Execute with: npx tsx etcd-internals-capstone.ts

/**
 * ARCHITECTURE STUDY: etcd Internals — MVCC, Bbolt & Raft Consensus
 * Simulation of etcd v3 MVCC Engine: treeIndex, Bbolt Backend,
 * Monotonic Revisions, and Compaction Mechanics.
 */

// ==========================================
// 1. Revision & Generation Data Structures
// ==========================================

export interface Revision {
  main: number; // Incremented on each transaction
  sub: number;  // Order within multi-op transaction
}

export function revToString(rev: Revision): string {
  return `${rev.main.toString().padStart(10, '0')}_${rev.sub.toString().padStart(5, '0')}`;
}

export interface KeyGeneration {
  createdRev: Revision;
  revisions: Revision[];
}

export class KeyIndex {
  public key: string;
  public generations: KeyGeneration[] = [];

  constructor(key: string, initialRev: Revision) {
    this.key = key;
    this.generations.push({
      createdRev: initialRev,
      revisions: [initialRev],
    });
  }

  put(rev: Revision): void {
    if (this.generations.length === 0) {
      this.generations.push({ createdRev: rev, revisions: [rev] });
    } else {
      const activeGen = this.generations[this.generations.length - 1];
      activeGen.revisions.push(rev);
    }
  }

  tombstone(rev: Revision): void {
    const activeGen = this.generations[this.generations.length - 1];
    activeGen.revisions.push(rev);
    // End current generation
    this.generations.push({ createdRev: rev, revisions: [] });
  }

  /**
   * Finds the latest revision <= targetRev
   */
  findRevision(targetRev: number): Revision | null {
    for (let i = this.generations.length - 1; i >= 0; i--) {
      const gen = this.generations[i];
      for (let j = gen.revisions.length - 1; j >= 0; j--) {
        if (gen.revisions[j].main <= targetRev) {
          return gen.revisions[j];
        }
      }
    }
    return null;
  }

  /**
   * Prunes revisions strictly older than compactRev
   */
  compact(compactRev: number): boolean {
    for (const gen of this.generations) {
      gen.revisions = gen.revisions.filter((r) => r.main >= compactRev);
    }
    this.generations = this.generations.filter((g) => g.revisions.length > 0);
    return this.generations.length > 0;
  }
}

// ==========================================
// 2. Persistent Bbolt Storage Simulation
// ==========================================

export interface KeyValueProto {
  key: string;
  value: string | null; // null represents Tombstone
  createRevision: Revision;
  modRevision: Revision;
  version: number;
}

export class BboltBackend {
  // Simulates B+Tree where primary key is revToString(rev)
  private diskStore: Map<string, KeyValueProto> = new Map();
  public freePageCount: number = 0;

  put(rev: Revision, kv: KeyValueProto): void {
    this.diskStore.set(revToString(rev), kv);
  }

  get(rev: Revision): KeyValueProto | undefined {
    return this.diskStore.get(revToString(rev));
  }

  compact(compactRev: number): number {
    let purged = 0;
    for (const [revKey] of this.diskStore) {
      const mainRev = parseInt(revKey.split('_')[0], 10);
      if (mainRev < compactRev) {
        this.diskStore.delete(revKey);
        this.freePageCount++;
        purged++;
      }
    }
    return purged;
  }

  size(): number {
    return this.diskStore.size;
  }
}

// ==========================================
// 3. Complete etcd v3 MVCC Server
// ==========================================

export class EtcdV3Server {
  private currentMainRev: number = 0;
  private treeIndex: Map<string, KeyIndex> = new Map(); // In-memory B-Tree
  private bbolt: BboltBackend = new BboltBackend();     // On-disk B+Tree
  private compactRev: number = 0;

  put(key: string, value: string): { revision: Revision; prevKv: KeyValueProto | null } {
    this.currentMainRev++;
    const rev: Revision = { main: this.currentMainRev, sub: 0 };

    let keyIdx = this.treeIndex.get(key);
    let prevKv: KeyValueProto | null = null;
    let createRev = rev;
    let version = 1;

    if (!keyIdx) {
      keyIdx = new KeyIndex(key, rev);
      this.treeIndex.set(key, keyIdx);
    } else {
      const latestRev = keyIdx.findRevision(this.currentMainRev);
      if (latestRev) {
        prevKv = this.bbolt.get(latestRev) || null;
        if (prevKv && prevKv.value !== null) {
          createRev = prevKv.createRevision;
          version = prevKv.version + 1;
        }
      }
      keyIdx.put(rev);
    }

    const proto: KeyValueProto = {
      key,
      value,
      createRevision: createRev,
      modRevision: rev,
      version,
    };

    this.bbolt.put(rev, proto);
    return { revision: rev, prevKv };
  }

  get(key: string, targetRev?: number): KeyValueProto | null {
    const queryRev = targetRev ?? this.currentMainRev;
    if (queryRev < this.compactRev) {
      throw new Error(`ErrCompacted: Revision ${queryRev} has been compacted (current compactRev: ${this.compactRev})`);
    }

    const keyIdx = this.treeIndex.get(key);
    if (!keyIdx) return null;

    const target = keyIdx.findRevision(queryRev);
    if (!target) return null;

    const record = this.bbolt.get(target);
    if (!record || record.value === null) {
      return null; // Tombstone or not found
    }

    return record;
  }

  delete(key: string): { revision: Revision } {
    this.currentMainRev++;
    const rev: Revision = { main: this.currentMainRev, sub: 0 };
    const keyIdx = this.treeIndex.get(key);

    if (keyIdx) {
      keyIdx.tombstone(rev);
      const proto: KeyValueProto = {
        key,
        value: null, // Tombstone marker
        createRevision: rev,
        modRevision: rev,
        version: 0,
      };
      this.bbolt.put(rev, proto);
    }

    return { revision: rev };
  }

  compact(revision: number): { purgedRevisions: number } {
    this.compactRev = revision;
    const purged = this.bbolt.compact(revision);

    // Prune in-memory treeIndex
    this.treeIndex.forEach((keyIdx, key) => {
      const alive = keyIdx.compact(revision);
      if (!alive) this.treeIndex.delete(key);
    });

    return { purgedRevisions: purged };
  }
}

// ==========================================
// 4. Execution & Verification Harness
// ==========================================

export function runEtcdDemo() {
  console.log("=== ARCHITECTURE STUDY: etcd v3 MVCC & Bbolt Engine ===");

  const server = new EtcdV3Server();

  console.log("\n[1] Executing Sequential Mutations (Incrementing Revisions):");
  const r1 = server.put("/registry/pods/default/nginx", '{"status":"Pending"}');
  console.log(`  Put v1 -> Revision: ${revToString(r1.revision)}`);

  const r2 = server.put("/registry/pods/default/nginx", '{"status":"Running","ip":"10.244.0.5"}');
  console.log(`  Put v2 -> Revision: ${revToString(r2.revision)}`);

  const r3 = server.put("/registry/services/default/web", '{"port":8080}');
  console.log(`  Put v3 -> Revision: ${revToString(r3.revision)}`);

  console.log("\n[2] Executing Point-in-Time Historical Reads (Time Travel):");
  const currentVal = server.get("/registry/pods/default/nginx");
  console.log(`  Latest Value: ${currentVal?.value} (modRev: ${revToString(currentVal!.modRevision)})`);

  const historicalVal = server.get("/registry/pods/default/nginx", 1);
  console.log(`  Historical Value at Rev 1: ${historicalVal?.value} (modRev: ${revToString(historicalVal!.modRevision)})`);

  console.log("\n[3] Deleting Key (Tombstone Generation):");
  const delRes = server.delete("/registry/pods/default/nginx");
  console.log(`  Deleted nginx at Revision: ${revToString(delRes.revision)}`);
  console.log(`  Read after deletion: ${server.get("/registry/pods/default/nginx")}`);

  console.log("\n[4] Executing etcdctl Compact at Revision 3:");
  console.log(`  Total Bbolt records before compaction: ${server['bbolt'].size()}`);
  const compRes = server.compact(3);
  console.log(`  Purged ${compRes.purgedRevisions} historical records. Bbolt freelist pages: ${server['bbolt'].freePageCount}`);

  try {
    server.get("/registry/pods/default/nginx", 1);
  } catch (err: any) {
    console.log(`  Attempt to read Rev 1 after compact: "${err.message}" (Expected Error)`);
  }

  console.log("\n=== etcd MVCC Simulation Complete. Invariants Verified. ===");
}

runEtcdDemo();

8. Real-World Case Studies

8.1 Kubernetes Control Plane

• Every Kubernetes API resource is stored in etcd under a hierarchical key path (e.g., /registry/pods/{namespace}/{name}).
• Kubernetes uses etcd’s resourceVersion parameter—which maps 1:1 to etcd’s 64-bit revision—for Optimistic Concurrency Control (OCC). If two controllers update a Deployment simultaneously, the second write is rejected with an HTTP 409 Conflict if its resourceVersion is stale.

8.2 Rook-Ceph and CoreOS Fleet

• Uses etcd distributed locks and leases to orchestrate zero-downtime rolling node updates across bare-metal server fleets.

8.3 Vitess (YouTube / Slack)

• Leverages etcd as a lock server and topology manager, registering tablet locations, shard boundaries, and active primary databases.

9. Edge Cases, Failure Modes & Antipatterns

9.1 The Database Quota Alarm (NOSPACE)

• Failure Mode: When the bbolt database exceeds quota-backend-bytes (default 2 GB), etcd raises a NOSPACE alarm. All write operations fail with etcdserver: mvcc: database space exceeded.
• Operational Antipattern: Running etcdctl compact frees revisions in treeIndex but does not shrink the file on disk. Operators must follow with etcdctl defrag to rewrite the bbolt file and then manually execute etcdctl alarm disarm.

9.2 Lease KeepAlive Starvation under Network Jitter

• Failure Mode: When high network load or CPU starvation delays client heartbeat renewals beyond the lease TTL, etcd revokes the lease, instantly deleting all attached keys (e.g., Kubernetes master leader election locks).
• Remediation: Configure client lease renewal to send keepalive heartbeats at intervals of $\frac{1}{3}\times \text{TTL}$ (e.g., a 15-second lease sends keepalives every 5 seconds).

9.3 In-Flight Watcher Lag and Memory Inflation

• Failure Mode: If a client opens a watch from revision 1 on a busy cluster, etcd moves the watcher to the unsynced queue, reading thousands of events from disk. If the client socket reads slowly, etcd buffers events in memory, triggering worker OOM.
• Remediation: Set --max-request-bytes and configure clients to reject watches requesting revisions older than the cluster’s compacted revision window.

10. Observability, Metrics & Production Telemetry

11. Guided Hands-On Lab / Engineering Exercises

Lab 1: Implement an MVCC Range Scanner with Compact Guards

• Objective: Extend EtcdV3Server with rangeScan(startKey, endKey, revision).
• Deliverable: Verify that scanning across a key range returns only the latest non-tombstone revision for each distinct key, throwing ErrCompacted if the requested revision is older than compactRev.

Lab 2: Simulate Kubernetes Optimistic Concurrency Control (OCC)

• Objective: Implement a conditional transaction: Txn().If(ModRev(key) == expectedRev).Then(Put(key, newVal)).Else(Fail).
• Deliverable: Simulate two competing workers attempting to update the same pod status; prove that exactly one succeeds while the second receives an OCC failure.

Lab 3: Simulate Bbolt Freelist Fragmentation under Churn

• Objective: Populate 10,000 keys. Update them 10 times each. Compact to latest revision.
• Deliverable: Measure simulated file page count before and after compaction versus defragmentation.

// Extension method on EtcdV3Server:
public rangeScan(startKey: string, endKey: string, targetRev?: number): KeyValueProto[] {
  const queryRev = targetRev ?? this.currentMainRev;
  if (queryRev < this.compactRev) {
    throw new Error(
      `ErrCompacted: Revision ${queryRev} has been compacted (current compactRev: ${this.compactRev})`
    );
  }

  // 1. Traverse in-memory treeIndex keys in sorted lexicographical order [startKey, endKey)
  const matchingKeys = Array.from(this.treeIndex.keys())
    .filter((k) => k >= startKey && (endKey === '' || k < endKey))
    .sort((a, b) => a.localeCompare(b));

  const results: KeyValueProto[] = [];
  for (const key of matchingKeys) {
    const keyIdx = this.treeIndex.get(key)!;
    // 2. Resolve the highest revision <= queryRev in RAM
    const rev = keyIdx.findRevision(queryRev);
    if (!rev) continue;

    // 3. Fetch KeyValueProto from bbolt by composite revision key and skip tombstones
    const kv = this.bbolt.get(rev);
    if (kv && kv.value !== null) {
      results.push(kv);
    }
  }
  return results;
}

// Atomic Compare-And-Swap Transaction on EtcdV3Server:
public txnCompareAndSwap(
  key: string,
  expectedModMainRev: number,
  newValue: string
): { succeeded: boolean; revision: Revision; currentKv: KeyValueProto | null } {
  const currentKv = this.get(key);
  const actualModRev = currentKv ? currentKv.modRevision.main : 0;

  // If(ModRev(key) == expectedModMainRev) -> Then(Put)
  if (actualModRev === expectedModMainRev) {
    const { revision } = this.put(key, newValue);
    return { succeeded: true, revision, currentKv: this.get(key) };
  }

  // Else -> Return current state without mutating (Kubernetes API returns HTTP 409 Conflict)
  return {
    succeeded: false,
    revision: { main: this.currentMainRev, sub: 0 },
    currentKv,
  };
}

12. Comprehensive Summary & Decision Framework

Coordination Technology Comparison Matrix

Production Operations Runbook

1. Dedicated NVMe SSD: Always place the etcd WAL directory (--data-dir) on a dedicated physical NVMe SSD with sustained $p99\text{ fsync}<10\text{ ms}$.
2. Automated Compaction: Set --auto-compaction-retention=1h to ensure historical revisions are pruned continuously.
3. Scheduled Defragmentation: Run etcdctl defrag during maintenance windows on one member at a time to reclaim physical disk space without cluster downtime.
4. Cluster Sizing: Standardize on 3 or 5 members. A 3-node cluster tolerates 1 node failure; a 5-node cluster tolerates 2 node failures. Never deploy an even number of voting nodes.

13. Authoritative References & Version Context

• Diego Ongaro and John Ousterhout (2014), “In Search of an Understandable Consensus Algorithm”, USENIX ATC ‘14 (Raft Consensus) — usenix.org/conference/atc14/technical-sessions/presentation/ongaro
• etcd Project Documentation (v3.5+) — Storage Architecture and bbolt MVCC Internals — etcd.io/docs/v3.5/learning/
• Kubernetes Architecture Guide — Operating etcd Clusters for the Kubernetes Control Plane — kubernetes.io/docs/tasks/administer-cluster/configure-upgrade-etcd/
• Version Context: Architecture reflects etcd v3.5 / v3.6, Raft consensus invariants, bbolt B+ Tree storage, and Kubernetes 1.28+ control-plane coordination.