Distributed Coordination & Consensus with etcd: Leases, Revision Watches, and Fencing Tokens

1. Problem and Motivation

Project Identity, Version & License Baseline

In modern cloud architectures, operating complex distributed systems requires solving fundamental control-plane synchronization challenges:

• Service Discovery: How does a microservice find the dynamic IP addresses of 500 auto-scaled worker pods?
• Configuration Management: How do hundreds of services receive instant, atomic configuration updates without polling?
• Distributed Master Election: When three scheduler nodes run concurrently, how does exactly one node become active while two remain standby, without split-brain?
• Distributed Locking: How can multiple independent processes coordinate exclusive access to a shared resource across unreliable networks?

+---------------------------------------------------------------------------------------------------+
|                              THE DISTRIBUTED COORDINATION PROBLEM                                 |
+---------------------------------------------------------------------------------------------------+
|  1. The Split-Brain Disaster: Under a datacenter network partition, two isolated nodes both       |
|     believe they are the active primary, writing conflicting records to storage simultaneously.    |
|  2. Zombie Leaders & GC Pauses: A process holding a lock experiences a 15-second Stop-The-World   |
|     Garbage Collection pause. Its lock expires, but upon waking, it continues writing as leader.  |
|  3. The Polling Overhead Tax: 10,000 microservices polling a relational database every second for |
|     configuration changes consumes 10,000 QPS of pure wasteful read traffic.                      |
|  4. Ephemeral Cleanup Failure: If a service instance crashes abruptly, its registry entry must   |
|     be purged automatically to prevent dead traffic routing.                                      |
+---------------------------------------------------------------------------------------------------+

These challenges led to the development of etcd (a CNCF graduated project), the distributed key-value store that acts as the brains of Kubernetes, storing all cluster states, pod manifests, and API objects.

2. Mental Model & Architectural Overview

etcd integrates a Raft Consensus Engine, an In-Memory B-Tree Index, an On-Disk MVCC Storage Engine (bbolt), and an HTTP/2 gRPC API:

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Kubernetes API Server / Client & etcd Raft Cluster (Quorum = 2 of 3)

Establishes the ingress and structural boundary across Kubernetes API Server / Client & etcd Raft Cluster (Quorum = 2 of 3): PUT /registry/pods/default/nginx Linearizable Write Request; Node 1 (Leader): Proposes Raft entry; Node 2 (Follower): Appends log → ACK.

Architectural Invariant: Quorum achieved: Leader commits entry.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Compaction & Defragmentation & Lease Lifecycle & KeepAlive

Coordinates core data-plane execution and state transitions through Compaction & Defragmentation & Lease Lifecycle & KeepAlive: Compaction discards revisions < target rev. etcdctl compact 10000 → defrag Reclaims physical disk space; Worker pod registers for service discovery: lease = client.Grant(TTL = 10s) client.Put("/svc/auth/pod-1", ip, lease) Background thread streams KeepAlive pings to renew TTL every 3 seconds; If worker pod crashes or partitions.

Architectural Invariant: etcd automatically DELETES key Zero ghost services in registry!.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Sequential Ephemeral Locks & Lock Winner & Watch Queue

Enforces durability, state convergence, and output verification across Sequential Ephemeral Locks & Lock Winner & Watch Queue: Clients compete for distributed lock: PUT /locks/leader/ (with Lease); Client A: revision = 101; Client B: revision = 102.

Architectural Invariant: Client with LOWEST revision wins! Client A holds lock (Rev 101) Client B watches key created by immediate predecessor (Client A). Zero Thundering Herd on release!.

The Three Foundational Subsystems:

1. Raft-Backed State Machine Replication:
   • Cluster typically operates with 3 or 5 nodes to tolerate $F$ failures ($2F+1$ nodes).
   • All mutations are proposed to the Raft Leader, replicated to a quorum of followers, and committed before updating disk storage.
2. Multi-Version bbolt Storage & Revision Watches:
   • Implements a global 64-bit monotonically increasing Revision counter.
   • Every mutation increments the revision.
   • Clients establish gRPC Streaming Watches on keys or prefixes. If a client disconnects, it reconnects specifying its start_revision to receive a complete, gapless replay of all intermediate mutations.
3. Leases, KeepAlives & Fencing Tokens:
   • Clients bind ephemeral keys to a Lease with a time-to-live (e.g., 10 seconds).
   • If the client fails to stream periodic KeepAlive heartbeats, etcd automatically deletes all associated keys.
   • Distributed locks issue monotonically increasing Fencing Tokens (derived from the key creation revision) to protect storage engines against zombie lock holders.

3. Terminology & Core Mechanics

• Revision: A 64-bit integer tracking the total logical age of the etcd database. Every PUT or DELETE operation advances the global revision by 1.
• bbolt: An embedded, ACID-compliant, single-process B+ Tree key-value database written in Go, used by etcd for persistent disk storage.
• Lease: An allocation of time that a client can attach to keys; when the lease expires, all attached keys are automatically deleted.
• KeepAlive: A bidirectional gRPC stream where a client periodically sends refresh requests to reset the TTL of its active lease.
• ReadIndex: A consensus protocol allowing the Raft leader to execute linearizable reads by confirming quorum leadership with followers without appending a disk-bound Raft log entry.
• Fencing Token: A monotonically increasing integer assigned to a distributed lock holder; backing storage engines reject any write with a token lower than the highest token observed so far.

4. Internal Workings & Algorithms

1. The Multi-Version Concurrency Control (MVCC) Engine

Unlike Redis or ZooKeeper, etcd does not overwrite data in-place:

• It maintains an in-memory B-Tree index (keyIndex) mapping human-readable keys (e.g., "/services/auth") to their physical revision numbers.
• The on-disk bbolt database uses the Revision as its physical key: $$\text{Disk Key}=(\text{revision},\text{sub\_revision})⟶\text{Disk Value}=\text{User Payload}$$

Client Operation: PUT /foo "bar"  (at global revision 10)
Client Operation: PUT /foo "baz"  (at global revision 11)

In-Memory keyIndex:
  "/foo" -> [Rev 10, Rev 11]

On-Disk bbolt Storage:
  Key: {main: 10, sub: 0} -> Value: "bar"
  Key: {main: 11, sub: 0} -> Value: "baz"

Because old revisions are preserved on disk, a client can execute a point-in-time query at revision = 10 and receive "bar", even though the current database revision is 11!

2. Linearizable Reads via ReadIndex

In distributed systems, reading from a leader without verification risks reading stale data if the leader was silently deposed during a network partition (a Stale Leader Read).

How etcd ReadIndex Solves This Without Disk I/O:

1. Client issues a read request to the Raft Leader.
2. The Leader records its current commit_index as ReadIndex.
3. The Leader broadcasts a lightweight heartbeat round (zero disk writes) to a quorum of followers.
4. Once a majority responds, the Leader knows with mathematical certainty that it is still the legitimate leader and no newer term has begun.
5. The Leader waits until its local state machine processes changes up to ReadIndex.
6. The Leader reads the value directly from bbolt memory and returns it to the client.

5. Mathematical & Failure Models

1. Cluster Quorum Formulation

Let $N$ be the number of nodes in an etcd cluster. The cluster can tolerate up to $F$ simultaneous failures: $$N=2F+1$$ $$\text{Quorum Size}=\lfloor N/2\rfloor +1$$

2. The Martin Kleppmann GC Pause Dilemma & Fencing Tokens

Consider what occurs when a distributed lock relies strictly on time leases:

Timeline:
T0: Client 1 acquires Lock with Lease = 10s.
T1: Client 1 enters an unexpected Stop-The-World Garbage Collection (GC) pause.
T2: 10 seconds elapse -> etcd Lease expires!
T3: Client 2 requests Lock -> Granted Lock with Lease = 10s.
T4: Client 2 writes data to Backing Storage (Database).
T5: Client 1's GC finishes -> Wakes up unaware of pause!
T6: Client 1 sends its pending write to Backing Storage -> OVERWRITES Client 2!
Result: Silent Data Corruption!

                 +------------------------------------------------------+
                 |               THE FENCING TOKEN SOLUTION             |
                 +------------------------------------------------------+
                 | 1. Lock issued with Monotonic Token:                 |
                 |    Client 1 receives Token = 101                     |
                 |    Client 2 receives Token = 102                     |
                 |                                                      |
                 | 2. Backing Storage Enforces Rule:                    |
                 |    Write accepted ONLY IF Token >= StorageLastToken! |
                 |                                                      |
                 | 3. Execution:                                        |
                 |    Client 2 writes (Token 102) -> Storage sets 102   |
                 |    Client 1 wakes and writes (Token 101)             |
                 |    Storage checks: 101 < 102 -> REJECTED (409)!      |
                 +------------------------------------------------------+

By leveraging etcd’s CreateRevision as the monotonic fencing token, backing storage engines can immediately reject stale zombie writes.

6. Real Implementation & Systems Comparison

7. Production Code Engine: Distributed Coordinator Simulator

The following TypeScript implementation demonstrates:

1. An etcd-like Multi-Version Store with atomic revisions.
2. A Lease Manager with heartbeat renewals and automatic expiration.
3. A Distributed Mutex that issues monotonic fencing tokens based on key creation revisions.

/**
 * Production-Grade Distributed Coordinator Simulator (etcd Model)
 * Demonstrates MVCC Revisions, Leases, and Distributed Locks with Fencing Tokens.
 */

export interface VersionedRecord {
  key: string;
  value: string;
  createRevision: number;
  modRevision: number;
  version: number;
  leaseId?: number;
}

export class EtcdCoordinatorSimulator {
  private globalRevision = 0;
  private store = new Map<string, VersionedRecord>();
  private leases = new Map<number, { ttlMs: number; expiresAt: number; keys: Set<string> }>();
  private nextLeaseId = 1000;

  // ==========================================
  // MVCC KEY-VALUE OPERATIONS
  // ==========================================
  public put(key: string, value: string, leaseId?: number): { revision: number } {
    this.globalRevision++;
    const current = this.store.get(key);

    const record: VersionedRecord = {
      key,
      value,
      createRevision: current ? current.createRevision : this.globalRevision,
      modRevision: this.globalRevision,
      version: current ? current.version + 1 : 1,
      leaseId,
    };

    this.store.set(key, record);

    if (leaseId && this.leases.has(leaseId)) {
      this.leases.get(leaseId)!.keys.add(key);
    }

    return { revision: this.globalRevision };
  }

  public get(key: string): VersionedRecord | null {
    return this.store.get(key) ?? null;
  }

  // ==========================================
  // LEASE MANAGEMENT
  // ==========================================
  public grantLease(ttlSeconds: number, nowMs = Date.now()): number {
    const leaseId = ++this.nextLeaseId;
    this.leases.set(leaseId, {
      ttlMs: ttlSeconds * 1000,
      expiresAt: nowMs + ttlSeconds * 1000,
      keys: new Set(),
    });
    return leaseId;
  }

  public keepAlive(leaseId: number, nowMs = Date.now()): boolean {
    const lease = this.leases.get(leaseId);
    if (!lease) return false;
    lease.expiresAt = nowMs + lease.ttlMs;
    return true;
  }

  public sweepExpiredLeases(nowMs = Date.now()): number {
    let expiredCount = 0;

    for (const [leaseId, lease] of this.leases.entries()) {
      if (nowMs > lease.expiresAt) {
        // Automatically delete all keys attached to expired lease
        for (const key of lease.keys) {
          this.store.delete(key);
        }
        this.leases.delete(leaseId);
        expiredCount++;
      }
    }
    return expiredCount;
  }

  // ==========================================
  // DISTRIBUTED LOCK WITH FENCING TOKENS
  // ==========================================
  public acquireLock(
    lockPrefix: string,
    leaseId: number,
    nowMs = Date.now()
  ): { success: boolean; holderLeaseId?: number; fencingToken: number } {
    this.sweepExpiredLeases(nowMs);

    // Check if any existing key under lockPrefix is already held by an active (unexpired) lease
    for (const [key, rec] of this.store.entries()) {
      if (key.startsWith(`${lockPrefix}/`) || key === lockPrefix) {
        const activeLease = rec.leaseId !== undefined ? this.leases.get(rec.leaseId) : undefined;
        if (activeLease && nowMs <= activeLease.expiresAt) {
          return {
            success: false,
            holderLeaseId: rec.leaseId,
            fencingToken: 0,
          };
        }
      }
    }

    // Generate unique sequential ephemeral key
    const lockKey = `${lockPrefix}/${this.globalRevision + 1}`;
    this.put(lockKey, 'LOCKED', leaseId);
    const record = this.store.get(lockKey)!;
    return {
      success: true,
      holderLeaseId: leaseId,
      fencingToken: record.createRevision,
    };
  }
}

function runDemo(): void {
  console.log("=== etcd Architecture: Distributed Leases, MVCC & Leader Coordination ===");
  const etcd = new EtcdCoordinatorSimulator();
  const leaseId = etcd.grantLease(10);
  console.log(`Granted distributed lease #${leaseId} with 10s TTL`);
  const put1 = etcd.put("/services/payment/leader", "node-prod-01", leaseId);
  console.log(`Put key with lease attached: revision=${put1.revision}`);
  const lock = etcd.acquireLock("/locks/orders", leaseId);
  console.log(`Acquired distributed lock: success=${lock.success}, fencingToken=${lock.fencingToken}`);
  const record = etcd.get("/services/payment/leader");
  console.log(`Read active leader: '${record?.value}' (modRevision=${record?.modRevision})`);
}

runDemo();

8. Operational Perspective: Compaction & Defragmentation

Because etcd maintains an immutable history of revisions, its disk file (member/snap/db) grows continuously over time:

[ Operations Continue Over Days ]
Revisions: Rev 1 ... Rev 500,000 ... Rev 2,000,000
Database File: Reaches 2.1 GB (Default Quota: 2 GB!)
Alarm Triggered: NOSPACE! Cluster rejects all subsequent PUT/DELETE operations!

The Two-Step Maintenance Lifecycle:

1. Compaction (etcdctl compact <revision>): Informs etcd to discard the historical index entries prior to the specified revision. However, bbolt does not immediately release disk space to the OS; it keeps the pages in its internal free list for future allocations.
2. Defragmentation (etcdctl defrag): Takes an exclusive database lock, copies live pages to a new physical file on disk, and releases unallocated blocks back to the Linux filesystem. Must be run in a rolling fashion across cluster nodes to avoid cluster downtime.

9. Failure Modes & Cluster Recovery

10. Knowledge Check

Review the core distributed coordination principles, then complete the 4-question interactive assessment quiz at the end of this lesson:

1. Fencing Tokens: Explain why monotonic tokens prevent zombie lock holders from corrupting storage after long process pauses.
2. ReadIndex Efficiency: Describe how etcd serves linearizable reads without appending to disk-bound Raft logs.
3. Revision-Based Watches: Contrast continuous streaming watches with legacy one-shot ZooKeeper triggers.
4. Compaction vs. Defrag: Articulate the difference between logical revision compaction and physical disk defragmentation.

11. Practical Exercises & Deliverables

Exercise 1: Simulate the Martin Kleppmann GC Pause Lock Hazard

Problem: Demonstrate how time-based locks fail without fencing tokens.
Deliverable:

1. Using the EtcdCoordinatorSimulator class from Section 7, grant a lease to Worker 1.
2. Advance time past the lease TTL without calling keepAlive().
3. Simulate Worker 2 acquiring the lock and receiving a newer fencing token.
4. Create a mock storage engine that verifies writeToken >= currentStorageToken. Verify that Worker 1’s delayed write is rejected.

Exercise 2: Benchmark Revision Reconnection Playback

Problem: Measure event streaming efficiency across network drops.
Deliverable:

1. Generate 1,000 sequential key-value mutations in an etcd cluster.
2. Simulate a client that disconnects at revision 400 and reconnects at revision 1,000.
3. Stream the missed events using watch(start_rev=400). Measure the time required to catch up to the current revision.

12. Summary & Architectural Decision Guide

• Always Use Fencing Tokens: Distributed locks must pass monotonically increasing revision numbers to storage to reject zombie writes.
• Keep Leases Short but Heartbeat Resilient: 5–10s TTL with KeepAlive interval at $TTL/3$ ensures quick failover without spurious expiration.
• ReadIndex for Linearizable Reads: Avoid expensive Raft disk writes on read paths by verifying leadership via heartbeat quorums.
• Compact Historical MVCC Revisions: Regularly compact etcd bbolt revisions to prevent disk bloat and memory fragmentation.

13. Authoritative References & Version Context

• Martin Kleppmann (2016), “How to do distributed locking”, Cambridge University Computer Laboratory — martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
• etcd Project Documentation (v3.5+) — Distributed Locks and Fencing Tokens — etcd.io/docs/v3.5/learning/
• Diego Ongaro and John Ousterhout (2014), “In Search of an Understandable Consensus Algorithm”, USENIX ATC ‘14 — usenix.org
• Version Context: Architecture reflects etcd v3.5/v3.6 with bbolt MVCC storage and Kubernetes 1.28+ cluster coordination.