Back
+30 XP
Concept

Capstone Coordination: Distributed Leader Lease & Fencing Tokens

Network partitions and GC pauses inevitably produce zombie leaders that believe they still own the cluster. The Capstone coordinator issues time-bounded leases paired with monotonically increasing fencing tokens. Storage nodes reject writes stamped with outdated tokens, preventing split-brain corruption 👑🛡️⏱️.

python
class FencingCoordinator:
    def __init__(self):
        self.token = 0
        self.leader = None

    def grant(self, node):
        self.token += 1
        self.leader = node
        return self.token

class StorageServer:
    def __init__(self):
        self.max_token = 0

    def accept(self, token, data):
        if token < self.max_token:
            raise PermissionError("Stale zombie write 🛑")
        self.max_token = token
        return "COMMITTED"

coord = FencingCoordinator()
srv = StorageServer()
t1 = coord.grant("node_a")
srv.accept(t1, "first")
t2 = coord.grant("node_b")
srv.accept(t2, "second")
print("Storage protected from stale tokens 🚀")

# 111. Capstone Coordination: Distributed Leader Lease & Fencing Tokens The most subtle and catastrophic bug in distributed systems is the **zombie leader problem** (Martin Kleppmann's famous critique of naive distributed locks) 🛑. ```python # The Zombie Leader Disaster: # 1. Node 1 acquires lock/lease from coordination service. # 2. Node 1 pauses for a 15-second Stop-The-World GC freeze. # 3. Lease expires in coordinator; Node 2 is elected as new leader. # 4. Node 2 writes to shared storage with high sequence number. # 5. Node 1 wakes up from GC, unaware time passed, and sends its write! # 6. If storage accepts Node 1's write, the newer data is overwritten by old data! ``` ### The Fencing Token Armor The solution is **Fencing Tokens**: - Every time the coordinator issues or renews a lease, it increments a monotonically increasing counter ($token = 1, 2, 3 \dots$). - When the leader talks to storage nodes, it must include its token. - Storage nodes track the highest token ever observed. - If a write arrives with $token < highest\_token$, storage immediately rejects it with `PermissionError`! - Result: Even if zombie Node 1 wakes up, its write is harmlessly blocked 👑🛡️⏱️. --- ### Interactive Pop-Quiz 🧠 #### Why can't simple time-based leases alone guarantee mutual exclusion without fencing tokens? - [ ] A leader node can experience a long garbage collection pause or hypervisor freeze, waking up after its lease expired and writing stale data thinking it is still leader 🛑 - [ ] Because NTP time is encrypted by the router - [ ] Because Linux does not support floating-point clocks - [ ] Time-based leases require GPS atomic clocks on every CPU --- ### Practical Challenge 🎯 Implement `LeaseCoordinator(lease_duration: float = 0.1)` with `acquire_lease(candidate_id: str) -> (token, expires_at)`. Implement `StorageGuard` with `highest_token: int` and `write(token: int, key: str, val: str)`. Verify that Node-1 acquires token 1, writes 'k1', lease expires, Node-2 acquires token 2, writes 'k2', and subsequent write attempt by Node-1 with token 1 raises `PermissionError`. Print results. <details> <summary>Solution</summary> ```python import time class LeaseCoordinator: def __init__(self, lease_duration: float = 0.1): self.lease_duration = lease_duration self.current_token = 0 self.leader_id = None self.expires_at = 0.0 def acquire_lease(self, candidate_id: str) -> tuple[int, float]: now = time.time() if now >= self.expires_at or self.leader_id == candidate_id: self.current_token += 1 self.leader_id = candidate_id self.expires_at = now + self.lease_duration return self.current_token, self.expires_at raise RuntimeError("Lease held by another node") class StorageGuard: def __init__(self): self.highest_token = 0 self.committed = {} def write(self, token: int, key: str, val: str): if token < self.highest_token: raise PermissionError("Stale fencing token") self.highest_token = token self.committed[key] = val coord = LeaseCoordinator(lease_duration=0.05) guard = StorageGuard() tok1, _ = coord.acquire_lease("node-1") guard.write(tok1, "k1", "v1") time.sleep(0.06) # Let lease expire tok2, _ = coord.acquire_lease("node-2") guard.write(tok2, "k2", "v2") try: guard.write(tok1, "k3", "v3") assert False, "Failed to block zombie leader" except PermissionError: pass assert "k3" not in guard.committed print(f"Fencing tokens verified: Node-2 token={tok2}, zombie write blocked") ``` </details>

Checkpoint

Why can't simple time-based leases alone guarantee mutual exclusion without fencing tokens? 🧠

Practice

Implement `LeaseCoordinator(lease_duration: float = 0.1)` with `acquire_lease(candidate_id: str) -> (token, expires_at)`. Implement `StorageGuard` with `highest_token: int` and `write(token: int, key: str, val: str)`. Verify that Node-1 acquires token 1, writes 'k1', lease expires, Node-2 acquires token 2, writes 'k2', and subsequent write attempt by Node-1 with token 1 raises `PermissionError`. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks