Distributed systems coordinate without shared memory. Nodes communicate only via messages, and messages can be delayed, reordered, or lost. The Three Hard Problems are: reaching agreement, establishing order, and detecting failures.
Two Generals Problem
Two armies must attack simultaneously but can only communicate via messengers that may be captured. Proved that guaranteed agreement over an unreliable channel is impossible — no finite number of messages suffices. This is the intuition behind why consensus requires a majority quorum rather than unanimous acknowledgement.
FLP Impossibility
Fischer, Lynch, and Paterson (1985): in an asynchronous system where even one process may crash, no deterministic consensus algorithm can always terminate. Practical systems escape this by using timeouts (partial synchrony) or randomization.
Quorums
A quorum is a subset of nodes large enough to guarantee overlap with any other quorum. For a cluster of n nodes, a simple majority quorum requires ⌊n/2⌋ + 1 nodes. Any two majority quorums share at least one node, which is the mechanism that prevents split-brain.
| Cluster size (n) | Quorum needed | Max failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
| 9 | 5 | 4 |
Brewer's CAP theorem states that during a network partition a distributed system must choose between Consistency (every read gets the latest write) and Availability (every request gets a response). Partition tolerance is non-negotiable in real networks.
CP — Consistent + Partition-tolerant
Returns an error or times out rather than serving stale data. Examples: etcd, ZooKeeper, HBase. Correct for leader election and distributed locks.
AP — Available + Partition-tolerant
Always returns a response, potentially stale. Examples: Cassandra (with eventual consistency), CouchDB, DynamoDB (default). Correct for shopping carts, DNS, read-heavy caches.
PACELC Extension
Even when there is no partition, systems trade off latency vs. consistency. Cassandra: EL (low latency, eventual consistency). Spanner: EC (higher latency, strong consistency).
Consistency Models (strongest → weakest)
| Model | Guarantee | Example system |
|---|---|---|
| Linearizability | Operations appear instantaneous; reads always see latest write | etcd, ZooKeeper, Spanner |
| Sequential | All nodes see operations in the same order; order may not match real time | CPU memory models |
| Causal | Causally related ops are seen in order; concurrent ops may differ | MongoDB (causal sessions) |
| Read-your-writes | A client always sees its own writes | Cassandra LOCAL_QUORUM |
| Eventual | Writes propagate eventually; reads may be stale | Cassandra ONE, DNS |
Algorithms make different assumptions about how nodes can fail. The stronger the failure model, the more expensive the protocol.
Crash-stop
Node stops and never recovers. The simplest model. Most practical systems assume crash-stop or crash-recovery.
Crash-recovery
Node stops, then restarts with durable state intact. Raft assumes this: a restarted node reloads its log from disk.
Byzantine
Node behaves arbitrarily — sends conflicting messages, lies, or is actively malicious. PBFT tolerates ⌊(n-1)/3⌋ Byzantine nodes. Blockchain consensus (PoW, PBFT) is designed for this.
Network partition
Nodes are alive but cannot communicate. From each partition's perspective, the other nodes have crashed. This is the P in CAP.
Paxos (Lamport, 1989) is the foundational consensus algorithm. Single-decree Paxos agrees on a single value. Multi-Paxos extends it to a replicated log by electing a stable leader and skipping Phase 1 for subsequent entries.
Roles
Proposer
Drives consensus. Generates proposal numbers, runs both phases, retries on failure. Typically the leader node.
Acceptor
Votes on proposals. Stores the highest promise and accepted value. A majority of acceptors must agree for a value to be chosen.
Learner
Receives the decided value. In practice the same process can play all three roles.
Two-Phase Protocol
Phase 1 — Prepare / Promise
Proposer Acceptors (majority)
│ │
│── Prepare(n) ────────▶│ n = unique proposal number
│ │ acceptor promises: won't accept < n
│◀─ Promise(n, v_prev) ─│ v_prev = previously accepted value (if any)
│ │
Phase 2 — Accept / Accepted
│ │
│── Accept(n, v) ──────▶│ v = v_prev if any, else proposer's value
│ │ acceptor writes (n, v) durably
│◀─ Accepted(n) ────────│
│ │
▼ value v is chosen once a majority returns Accepted
round_number * num_nodes + node_id. This ensures two proposers never use the same number while allowing any node to generate a valid proposal.
Multi-Paxos optimization
Once a leader is established, Phase 1 (Prepare/Promise) is run once for many log entries. Subsequent entries only need Phase 2 (Accept/Accepted), halving message count for the common path. Leader failure requires a new Phase 1 round.
Cassandra — Lightweight Transactions (LWT)
Cassandra implements single-row Paxos for compare-and-set operations via IF NOT EXISTS / IF condition clauses. Four phases: Prepare, Promise, Propose, Commit.
-- Insert only if the user does not already exist (Paxos CAS) INSERT INTO users (id, email, created_at) VALUES (uuid(), 'alice@example.com', toTimestamp(now())) IF NOT EXISTS; -- Conditional update UPDATE accounts SET balance = 500 WHERE id = :id IF balance = 600; -- only applies if current value matches
Raft (Ongaro & Ousterhout, 2014) was designed to be understandable. It decomposes consensus into three relatively independent sub-problems: leader election, log replication, and safety. Every Raft cluster has exactly one leader at a time per term.
State & Terms
Each node is in one of three states: Follower, Candidate, or Leader. Time is divided into terms (monotonically increasing integers). A new term begins whenever an election starts. Terms act as logical clocks — stale messages from old leaders are rejected.
timeout, starts election
Follower ─────────────────────────────▶ Candidate
▲ │
│ discovers leader or new term │ receives majority votes
│ (AppendEntries from valid leader) ▼
└────────────────────────────────── Leader
│
│ sends AppendEntries (heartbeat)
│ to all followers every heartbeat interval
▼
Log is replicated and
committed once majority ACKs
Log Replication
Leader Followers (F1, F2)
│ │
│─── AppendEntries(term=3, │
│ prevLogIndex=5, │
│ prevLogTerm=2, │
│ entries=[{term:3, cmd}], │
│ leaderCommit=5) ─────────▶│
│ │ check prevLogIndex/Term match
│◀── Success ───────────────────│ append entry, ACK
│ │
│ once majority ACK, leader
│ advances commitIndex and
│ applies to state machine
│─── AppendEntries(leaderCommit=6) ──▶│ followers commit too
Go — Minimal Raft Node Sketch
package raft import ( "math/rand" "sync" "time" ) type State int const ( Follower State = iota Candidate Leader ) type LogEntry struct { Term int Command interface{} } type Node struct { mu sync.Mutex id int peers []int state State currentTerm int votedFor int // -1 if none log []LogEntry commitIndex int lastApplied int // leader-only volatile state nextIndex []int matchIndex []int electionTimer *time.Timer heartbeatTimer *time.Timer } func (n *Node) resetElectionTimer() { timeout := time.Duration(150+rand.Intn(150)) * time.Millisecond if n.electionTimer != nil { n.electionTimer.Stop() } n.electionTimer = time.AfterFunc(timeout, n.startElection) } func (n *Node) startElection() { n.mu.Lock() n.state = Candidate n.currentTerm++ n.votedFor = n.id term := n.currentTerm votes := 1 n.mu.Unlock() for _, peer := range n.peers { go func(p int) { granted := n.sendRequestVote(p, term) n.mu.Lock() defer n.mu.Unlock() if granted && n.state == Candidate && n.currentTerm == term { votes++ if votes > (len(n.peers)+1)/2 { n.becomeLeader() } } }(peer) } } type RequestVoteArgs struct { Term int CandidateID int LastLogIndex int LastLogTerm int } type RequestVoteReply struct { Term int VoteGranted bool } // Vote granted if: term is current, not already voted, and candidate log is at least as up-to-date func (n *Node) HandleRequestVote(args RequestVoteArgs, reply *RequestVoteReply) { n.mu.Lock() defer n.mu.Unlock() if args.Term > n.currentTerm { n.currentTerm = args.Term n.state = Follower n.votedFor = -1 } reply.Term = n.currentTerm lastIndex := len(n.log) - 1 lastTerm := 0 if lastIndex >= 0 { lastTerm = n.log[lastIndex].Term } logOK := args.LastLogTerm > lastTerm || (args.LastLogTerm == lastTerm && args.LastLogIndex >= lastIndex) reply.VoteGranted = args.Term == n.currentTerm && (n.votedFor == -1 || n.votedFor == args.CandidateID) && logOK if reply.VoteGranted { n.votedFor = args.CandidateID n.resetElectionTimer() } } func (n *Node) becomeLeader() { n.state = Leader for i := range n.nextIndex { n.nextIndex[i] = len(n.log) n.matchIndex[i] = -1 } n.sendHeartbeats() }
Safety guarantee
prevLogIndex / prevLogTerm check in AppendEntries — a follower rejects entries that don't match its own log at that position, forcing the leader to walk back and resend.
Read linearizability
A leader might be stale (a network partition elected a new leader). To serve a linearizable read, the leader must confirm it is still the leader by getting a majority heartbeat ACK before responding. etcd implements this as the ReadIndex optimization: the leader records the current commit index, broadcasts a heartbeat, and serves the read once that index is applied.
Leader election is the sub-problem of choosing a single coordinator from a set of candidates. The elected leader is responsible for driving decisions; other nodes defer to it until it fails.
Bully Algorithm
Each node has a unique numeric ID. When a node detects the leader has failed, it sends an Election message to all nodes with higher IDs. If no one responds within a timeout, it declares itself leader and broadcasts a Coordinator message. A higher-ID node that receives an Election message bullies the sender out and continues the election.
import threading, time, random class Node: def __init__(self, node_id, peers): self.id = node_id self.peers = peers # list of Node references (higher IDs) self.leader = None self.alive = True def start_election(self): higher = [p for p in self.peers if p.id > self.id and p.alive] if not higher: # no higher node alive — I am the leader self.become_leader() return responses = [] for peer in higher: if peer.receive_election(self.id): responses.append(peer) if not responses: self.become_leader() # higher nodes didn't respond — crashed def receive_election(self, challenger_id): if not self.alive: return False # I have a higher ID — bully the challenger, start my own election threading.Thread(target=self.start_election).start() return True # OK message def become_leader(self): self.leader = self.id print(f"Node {self.id} is now the LEADER") for p in self.peers: p.leader = self.id # broadcast Coordinator message
Ring-Based Election (Chang-Roberts)
Nodes are arranged in a logical ring. A candidate sends its ID around the ring. Each node forwards the message only if the incoming ID is larger than any it has seen. When a node receives its own ID back, it has won (it was the maximum).
from collections import deque class RingNode: def __init__(self, node_id): self.id = node_id self.next = None # clockwise neighbour self.leader = None self.seen_max = node_id def start_election(self): self.next.receive(self.id) def receive(self, candidate_id): if candidate_id == self.id: # Our own ID came back — we won self.leader = self.id self.next.announce(self.id) elif candidate_id > self.seen_max: self.seen_max = candidate_id self.next.receive(candidate_id) # forward larger ID # drop smaller IDs — they cannot win def announce(self, leader_id): self.leader = leader_id if self.id != leader_id: self.next.announce(leader_id) # propagate around ring
Raft Leader Election (production)
Raft uses randomized election timeouts (150–300 ms typical) so that one follower usually times out before others and starts an election. A candidate wins if it receives votes from a majority of nodes. The log-completeness check in RequestVote ensures only a candidate with the most up-to-date log can win — this is the mechanism that preserves committed entries across elections without a separate phase.
Lamport clocks assign a scalar counter to each event such that if event A happens-before event B (A → B), then L(A) < L(B). They capture causal precedence but not concurrency — if L(A) < L(B) you cannot conclude A caused B.
Rules
1. Each process increments its counter before each local event.
2. When sending a message, include the current counter value.
3. On receiving a message with timestamp T:
local_clock = max(local_clock, T) + 1
import threading class LamportClock: def __init__(self): self._time = 0 self._lock = threading.Lock() def tick(self) -> int: """Increment before a local event.""" with self._lock: self._time += 1 return self._time def send(self) -> int: """Get timestamp to attach to outgoing message.""" return self.tick() def receive(self, msg_timestamp: int) -> int: """Update clock on receiving a message.""" with self._lock: self._time = max(self._time, msg_timestamp) + 1 return self._time # Usage clock_a = LamportClock() clock_b = LamportClock() t1 = clock_a.tick() # A: local event at t=1 ts = clock_a.send() # A: send message at t=2 t3 = clock_b.receive(ts) # B: receives, clock becomes max(0,2)+1 = 3 t4 = clock_b.tick() # B: local event at t=4
Vector clocks extend Lamport timestamps to detect concurrency. Each process maintains a vector of counters, one per process. Two events can be compared: A happened-before B, B happened-before A, or they are concurrent (neither causally precedes the other).
from __future__ import annotations from typing import Dict class VectorClock: def __init__(self, node_id: str, nodes: list[str]): self.node_id = node_id self.clock: Dict[str, int] = {n: 0 for n in nodes} def increment(self): self.clock[self.node_id] += 1 def send(self) -> Dict[str, int]: self.increment() return dict(self.clock) def receive(self, msg_clock: Dict[str, int]): for node, ts in msg_clock.items(): self.clock[node] = max(self.clock.get(node, 0), ts) self.increment() def happened_before(self, other: VectorClock) -> bool: """self → other: self[i] <= other[i] for all i, strict for at least one.""" leq = all(self.clock.get(k, 0) <= other.clock.get(k, 0) for k in other.clock) lt = any(self.clock.get(k, 0) < other.clock.get(k, 0) for k in other.clock) return leq and lt def concurrent_with(self, other: VectorClock) -> bool: return not self.happened_before(other) and not other.happened_before(self) # Example with 3 nodes: A, B, C nodes = ["A", "B", "C"] vc_a = VectorClock("A", nodes) vc_b = VectorClock("B", nodes) msg = vc_a.send() # A: {A:1, B:0, C:0} vc_b.receive(msg) # B: {A:1, B:1, C:0} vc_a.increment() # A: {A:2, B:0, C:0} — concurrent with B's state print(vc_a.concurrent_with(vc_b)) # True
HLC (Kulkarni et al., 2014) combines a physical clock (wall time) with a logical component so that: (1) HLC timestamps closely track wall time, (2) causality is preserved like Lamport clocks, and (3) the logical component is bounded (typically 0–65535). Used in CockroachDB and YugabyteDB for transaction ordering.
import time class HLC: def __init__(self): self.l = 0 # max physical timestamp seen self.c = 0 # logical counter def now_ms(self) -> int: return int(time.time() * 1000) def send_or_local(self): """Call before sending a message or on a local event.""" pt = self.now_ms() if pt > self.l: self.l = pt self.c = 0 else: self.c += 1 return (self.l, self.c) def receive(self, msg_l: int, msg_c: int): """Call on receiving a message with timestamp (msg_l, msg_c).""" pt = self.now_ms() old_l = self.l self.l = max(old_l, msg_l, pt) if self.l == old_l == msg_l: self.c = max(self.c, msg_c) + 1 elif self.l == old_l: self.c += 1 elif self.l == msg_l: self.c = msg_c + 1 else: self.c = 0 return (self.l, self.c) # HLC timestamps are sortable: compare l first, then c def hlc_before(a, b) -> bool: return a[0] < b[0] or (a[0] == b[0] and a[1] < b[1])
Gossip (epidemic) protocols disseminate information by having each node periodically select a few random peers and exchange state. After O(log n) rounds, information has reached the whole cluster with high probability. They are resilient because there is no single point of failure and message redundancy is the self-healing mechanism.
Modes
Push
Infected node sends its state to k random peers. Converges fast initially; slow near completion (healthy nodes rarely picked).
Pull
Node asks k peers for their state. Efficient near completion. Slower startup.
Push-Pull
Exchange state bidirectionally. Best convergence in practice. Used by Cassandra and Consul.
import random class GossipNode: FANOUT = 3 # peers contacted per round def __init__(self, node_id: str): self.id = node_id self.state: dict = {} # key → (value, version) def update(self, key: str, value): version = self.state.get(key, (None, 0))[1] + 1 self.state[key] = (value, version) def gossip_round(self, all_nodes: list[GossipNode]): peers = random.sample([n for n in all_nodes if n.id != self.id], min(self.FANOUT, len(all_nodes) - 1)) for peer in peers: self._merge(peer) peer._merge(self) # push-pull def _merge(self, other: GossipNode): """Accept state with higher version.""" for key, (val, ver) in other.state.items(): _, my_ver = self.state.get(key, (None, -1)) if ver > my_ver: self.state[key] = (val, ver) # Simulate: one node gets an update, count rounds until full convergence def simulate(n_nodes: int = 20): nodes = [GossipNode(f"n{i}") for i in range(n_nodes)] nodes[0].update("leader", "n0") for rnd in range(1, 20): for node in nodes: node.gossip_round(nodes) informed = sum(1 for n in nodes if "leader" in n.state) print(f"Round {rnd}: {informed}/{n_nodes} informed") if informed == n_nodes: break simulate(50) # Typical output: ~log2(50) ≈ 6 rounds to full convergence
Anti-entropy
Anti-entropy is a gossip variant specifically for repairing diverged replicas. Nodes exchange Merkle trees of their data and reconcile differences. Cassandra's nodetool repair uses anti-entropy to fix replicas that missed writes during downtime.
A failure detector tells each node which other nodes appear to have crashed. Perfect failure detection is impossible in asynchronous systems (FLP), so practical detectors make probabilistic or timing-based assumptions.
Heartbeat / Timeout
Each node sends a heartbeat every interval T. If no heartbeat is received within T + Δ (where Δ accounts for network jitter), the node is suspected. Simple and predictable but sensitive to network jitter — a high Δ slows detection; a low Δ causes false positives.
Phi Accrual Failure Detector
Used by Akka (Erlang-inspired) and Apache Cassandra. Instead of a binary up/down decision, it outputs a continuous suspicion level φ (phi). The application sets a threshold (e.g., φ > 8 = dead). φ is computed from the statistical distribution of heartbeat inter-arrival times, making it adaptive to varying network conditions.
import math, time from collections import deque from statistics import mean, stdev class PhiAccrualDetector: def __init__(self, window: int = 200, threshold: float = 8.0): self.threshold = threshold self._arrivals: deque = deque(maxlen=window) self._last_time: float = None def heartbeat(self): now = time.monotonic() if self._last_time is not None: self._arrivals.append(now - self._last_time) self._last_time = now def phi(self) -> float: """Suspicion level. phi > threshold ⟹ suspect dead.""" if len(self._arrivals) < 2 or self._last_time is None: return 0.0 elapsed = time.monotonic() - self._last_time mu = mean(self._arrivals) sd = max(stdev(self._arrivals), 0.001) # avoid division by zero # Cumulative distribution of exponential (simplified Gaussian) p_later = 1.0 - (math.erf((elapsed - mu) / (sd * math.sqrt(2))) + 1) / 2 return -math.log10(max(p_later, 1e-300)) def is_alive(self) -> bool: return self.phi() < self.threshold
SWIM — Scalable Weakly-consistent Infection-style Membership
SWIM (used by Consul and HashiCorp Serf) separates failure detection from dissemination. Detection uses indirect probing: instead of direct pings, node A asks B and C to ping D — a failed ping does not immediately mean D is down, only that A's path to D is broken.
A suspects D is down: A ──ping-req(D)──▶ B A ──ping-req(D)──▶ C B ──ping──▶ D ──ack──▶ B ──ack──▶ A (D is alive, path A-D broken) C ──ping──▶ D (timeout) (C also can't reach D) Both B and C timeout → A marks D as suspected → broadcasts suspicion After a protocol period with no refutation → D marked dead
2PC coordinates a distributed transaction across multiple participants. The coordinator drives two rounds: Prepare (can you commit?) and Commit (commit!). All participants must vote Yes for the transaction to commit; a single No aborts it.
Coordinator Participant A Participant B
│ │ │
│── Prepare ─────────▶│ │
│── Prepare ──────────────────────────────▶│
│ │ │
│◀─ Vote: YES ────────│ │
│◀─ Vote: YES ──────────────────────────── │
│ │ │
│ (all YES → Commit) │ │
│── Commit ───────────▶│ │
│── Commit ────────────────────────────────▶│
│ │ │
│◀─ Ack ──────────────│ │
│◀─ Ack ──────────────────────────────────│
from enum import Enum, auto class Vote(Enum): YES = auto() NO = auto() class Participant: def __init__(self, name: str, will_commit: bool = True): self.name = name self._will_commit = will_commit def prepare(self, txn_id: str) -> Vote: # validate, acquire locks, write to redo log print(f" [{self.name}] Prepared txn={txn_id}") return Vote.YES if self._will_commit else Vote.NO def commit(self, txn_id: str): print(f" [{self.name}] Committed txn={txn_id}") def abort(self, txn_id: str): print(f" [{self.name}] Aborted txn={txn_id}") class Coordinator: def __init__(self, participants: list[Participant]): self._participants = participants def execute(self, txn_id: str) -> bool: # Phase 1: Prepare votes = [p.prepare(txn_id) for p in self._participants] if all(v == Vote.YES for v in votes): # Phase 2: Commit — must persist decision before sending for p in self._participants: p.commit(txn_id) return True else: for p in self._participants: p.abort(txn_id) return False # Usage participants = [ Participant("orders-db"), Participant("inventory-db"), Participant("payments-db"), ] coord = Coordinator(participants) success = coord.execute("txn-42") print(f"Transaction {'committed' if success else 'aborted'}")
The Saga pattern breaks a distributed transaction into a sequence of local transactions, each with a corresponding compensating transaction that undoes its effect. If a step fails, compensations are executed in reverse order. Sagas avoid distributed locks and are preferred for long-running workflows.
Choreography
Each service listens for events and decides when to execute its local transaction or compensation. No central coordinator — services are coupled only through events. Harder to trace and debug.
Orchestration
A central saga orchestrator tells each participant what to do and when. Easier to trace but the orchestrator becomes a bottleneck and single point of failure if not made durable.
from dataclasses import dataclass, field from typing import Callable, List import logging log = logging.getLogger(__name__) @dataclass class SagaStep: name: str action: Callable[[], None] compensate: Callable[[], None] class Saga: def __init__(self, steps: List[SagaStep]): self._steps = steps def execute(self): completed: List[SagaStep] = [] for step in self._steps: try: log.info(f"Executing: {step.name}") step.action() completed.append(step) except Exception as e: log.error(f"Step {step.name} failed: {e}. Running compensations.") for done in reversed(completed): try: done.compensate() except Exception as ce: # Compensation failure — log for manual intervention log.critical(f"Compensation for {done.name} failed: {ce}") raise # Order placement saga: reserve inventory → charge payment → confirm order order_saga = Saga([ SagaStep( name="reserve-inventory", action=lambda: inventory_service.reserve(order_id, items), compensate=lambda: inventory_service.release(order_id), ), SagaStep( name="charge-payment", action=lambda: payment_service.charge(user_id, amount), compensate=lambda: payment_service.refund(user_id, amount), ), SagaStep( name="confirm-order", action=lambda: order_service.confirm(order_id), compensate=lambda: order_service.cancel(order_id), ), ]) order_saga.execute()
etcd is a strongly consistent, distributed key-value store used as the backing store for Kubernetes. It implements Raft via the etcd-io/raft library and persists the Raft log to bbolt (an embedded B-tree). All cluster state — Pods, Services, ConfigMaps, Secrets — lives in etcd.
Key guarantees
package main import ( "context" "fmt" "log" "time" clientv3 "go.etcd.io/etcd/client/v3" "go.etcd.io/etcd/client/v3/concurrency" ) func main() { cli, err := clientv3.New(clientv3.Config{ Endpoints: []string{"localhost:2379"}, DialTimeout: 5 * time.Second, }) if err != nil { log.Fatal(err) } defer cli.Close() // Create a session with a 10-second lease TTL session, err := concurrency.NewSession(cli, concurrency.WithTTL(10)) if err != nil { log.Fatal(err) } defer session.Close() election := concurrency.NewElection(session, "/my-service/leader") ctx := context.Background() // Campaign blocks until this node becomes leader if err := election.Campaign(ctx, "node-1"); err != nil { log.Fatal(err) } fmt.Println("I am the leader!") // Do leader work here... // The lease TTL keeps the key alive via keep-alive heartbeats. // If this process dies, the lease expires and a follower wins Campaign. if err := election.Resign(ctx); err != nil { log.Fatal(err) } } // Distributed lock using etcd mutex func withLock(cli *clientv3.Client) { session, _ := concurrency.NewSession(cli) mutex := concurrency.NewMutex(session, "/locks/critical-section") ctx := context.Background() mutex.Lock(ctx) // blocks until acquired defer mutex.Unlock(ctx) // critical section }
// Atomically update a value only if the current version matches resp, err := cli.Txn(ctx). If(clientv3.Compare(clientv3.Version("/config/timeout"), "=", currentVersion)). Then(clientv3.OpPut("/config/timeout", "30s")). Else(clientv3.OpGet("/config/timeout")). Commit() if resp.Succeeded { fmt.Println("Updated") } else { fmt.Println("CAS failed — value changed by another writer") }
Apache ZooKeeper implements Zab (ZooKeeper Atomic Broadcast) — a primary-order broadcast protocol similar to Paxos but with stronger ordering guarantees. Unlike Raft (which replicates a log), Zab guarantees that all writes from a given leader epoch are delivered in order before any writes from the next leader.
Data model
ZooKeeper exposes a hierarchical namespace of znodes (similar to a filesystem). Znodes can be persistent, ephemeral (auto-deleted when the client session expires), or sequential (auto-numbered). Clients receive watches — one-time notifications when a znode changes.
import org.apache.zookeeper.*; import org.apache.zookeeper.data.Stat; import java.util.*; public class LeaderElection implements Watcher { private final ZooKeeper zk; private final String ELECTION_PATH = "/election"; private String myNode; public LeaderElection(ZooKeeper zk) throws Exception { this.zk = zk; // Create an ephemeral sequential node — ZK assigns a unique suffix myNode = zk.create(ELECTION_PATH + "/node-", new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL); } public void electLeader() throws Exception { List<String> children = zk.getChildren(ELECTION_PATH, false); Collections.sort(children); String smallest = ELECTION_PATH + "/" + children.get(0); if (myNode.equals(smallest)) { System.out.println("I am the leader: " + myNode); } else { // Watch the node immediately before me — not the leader node // This avoids the "herd effect" where all watchers fire at once int myIndex = children.indexOf(myNode.substring(ELECTION_PATH.length() + 1)); String predecessor = ELECTION_PATH + "/" + children.get(myIndex - 1); Stat stat = zk.exists(predecessor, this); if (stat == null) { electLeader(); // predecessor already gone, retry } else { System.out.println("Following " + predecessor); } } } @Override public void process(WatchedEvent event) { if (event.getType() == Event.EventType.NodeDeleted) { try { electLeader(); } catch (Exception e) { e.printStackTrace(); } } } }
Kafka originally used ZooKeeper for broker metadata, controller election, and topic partition assignments. KRaft (Kafka Raft, KIP-500) replaces ZooKeeper with a Raft-based metadata log managed by a dedicated controller quorum. The metadata topic __cluster_metadata is the single source of truth.
Clients / Producers / Consumers
│
┌─────────▼───────────────────────────────┐
│ Broker nodes │
│ (handle produce/fetch, replication) │
│ │
│ broker-1 broker-2 broker-3 │
└──────────────────┬──────────────────────┘
│ metadata fetch / register
┌──────────────────▼──────────────────────┐
│ Controller Quorum (Raft) │
│ │
│ ctrl-1 (leader) ctrl-2 ctrl-3 │
│ │ │
│ __cluster_metadata topic (Raft log) │
│ Partition assignments, ISR changes, │
│ broker registrations, topic configs │
└─────────────────────────────────────────┘
# server.properties for a combined broker+controller node (small cluster)
process.roles=broker,controller
node.id=1
controller.quorum.voters=1@localhost:9093,2@localhost:9094,3@localhost:9095
listeners=PLAINTEXT://:9092,CONTROLLER://:9093
inter.broker.listener.name=PLAINTEXT
controller.listener.names=CONTROLLER
log.dirs=/var/kafka/data
metadata.log.dir=/var/kafka/metadata
Partition leader election
For topic partition leadership (separate from controller leadership), Kafka maintains an In-Sync Replica (ISR) set. The controller elects the first ISR member as leader when the current leader fails. A replica stays in ISR only if it has replicated within replica.lag.time.max.ms.
from kafka import KafkaProducer import json producer = KafkaProducer( bootstrap_servers=["localhost:9092"], # Idempotent producer: exactly-once delivery within a session enable_idempotence=True, acks="all", # wait for all ISR replicas to acknowledge retries=5, max_in_flight_requests_per_connection=5, value_serializer=lambda v: json.dumps(v).encode(), ) def publish_order_event(order_id: str, event_type: str): producer.send( topic="order-events", key=order_id.encode(), # same key → same partition → ordered value={"order_id": order_id, "event": event_type}, ) producer.flush() # block until broker confirms
Cassandra is a leaderless, AP database that uses consistent hashing for data placement, gossip for cluster membership, hinted handoff for write availability during node downtime, and read repair for eventual consistency. Lightweight transactions (Paxos) are available for compare-and-set operations at the cost of 4x latency.
Consistency levels
| Level | Writes | Reads | Trade-off |
|---|---|---|---|
ONE | 1 node ACK | 1 node | Lowest latency; stale reads possible |
QUORUM | ⌊RF/2⌋+1 ACKs | ⌊RF/2⌋+1 nodes | Strong consistency if RF ≥ 3 |
LOCAL_QUORUM | Local DC quorum | Local DC quorum | Multi-DC; no cross-DC latency |
ALL | All replicas | All replicas | Strongest; fails if any replica down |
SERIAL | — | Paxos read | Linearizable read (for LWT use cases) |
from cassandra.cluster import Cluster from cassandra.policies import DCAwareRoundRobinPolicy from cassandra import ConsistencyLevel from cassandra.query import SimpleStatement cluster = Cluster( ["10.0.0.1", "10.0.0.2"], load_balancing_policy=DCAwareRoundRobinPolicy(local_dc="us-east"), ) session = cluster.connect("my_keyspace") # Strong read — safe for financial data stmt = SimpleStatement( "SELECT balance FROM accounts WHERE id = %s", consistency_level=ConsistencyLevel.LOCAL_QUORUM, ) row = session.execute(stmt, [account_id]).one() # Lightweight transaction — read your own writes guaranteed result = session.execute( """ UPDATE accounts SET balance = %s WHERE id = %s IF balance = %s """, [new_balance, account_id, expected_balance], ) applied = result[0].applied # True if CAS succeeded # Async write with explicit consistency for throughput future = session.execute_async( SimpleStatement( "INSERT INTO events (id, data) VALUES (%s, %s)", consistency_level=ConsistencyLevel.ONE, ), [event_id, payload], ) future.add_callbacks( callback=lambda _: None, errback=lambda err: log.error(f"Write failed: {err}"), )
Gossip in Cassandra
Each Cassandra node gossips with up to three peers every second, exchanging endpoint state (generation, version, status, load, schema version, tokens). The gossiper uses an anti-entropy mechanism with a Phi Accrual Failure Detector per peer to decide when nodes are down. nodetool gossipinfo shows the raw gossip state for every node in the cluster.
Consensus Algorithms
| Algorithm | Fault model | Leader | Message rounds (happy path) | Used in |
|---|---|---|---|---|
| Paxos | Crash-stop | Optional (Multi-Paxos) | 2 (prepare+accept) or 1 (with stable leader) | Chubby, Spanner, Cassandra LWT |
| Raft | Crash-recovery | Required | 1 round-trip (AppendEntries + ACK) | etcd, CockroachDB, TiKV, Consul |
| Zab | Crash-recovery | Required (Primary) | 2 (Propose + Commit) | Apache ZooKeeper |
| PBFT | Byzantine | Primary | 3 (pre-prepare + prepare + commit) | Hyperledger Fabric (early versions) |
| Viewstamped Replication | Crash-stop | Primary | 2 | Academic; influenced Raft design |
Distributed Time
| Clock type | Captures causality | Detects concurrency | Overhead | Used in |
|---|---|---|---|---|
| Lamport | Yes (one-way) | No | O(1) per message | Distributed databases, ordering events |
| Vector Clocks | Yes (bidirectional) | Yes | O(n) per message | Riak, Dynamo, version vectors |
| HLC | Yes | No (scalar) | O(1) per message, bounded skew | CockroachDB, YugabyteDB |
| TrueTime (Spanner) | Yes | — | GPS + atomic clock hardware | Google Spanner |
Distributed Transaction Patterns
| Pattern | Blocking? | Isolation | Best for |
|---|---|---|---|
| 2PC | Yes (on coordinator crash) | Full ACID | Short transactions, same datacenter, XA-compatible databases |
| 3PC | No (fail-stop only) | Full ACID | Rarely used; partitions break it |
| Saga (choreography) | No | ACD (no I) | Long workflows, microservices, event-driven architectures |
| Saga (orchestration) | No | ACD (no I) | Complex workflows where centralized visibility is needed |
| Paxos Commit | No | Full ACID | Google Spanner, transactions across shards |
Key tuning knobs
| System | Parameter | Effect |
|---|---|---|
| Raft (etcd) | heartbeat-interval | Leader heartbeat frequency; lower = faster failover detection but more traffic |
| Raft (etcd) | election-timeout | Must be > heartbeat × 10; too low causes spurious elections |
| etcd | snapshot-count | Log entries before compaction; lower = smaller logs, more frequent snapshots |
| Cassandra | phi_convict_threshold | Higher = slower failure detection, fewer false positives on noisy networks |
| Cassandra | endpoint_snitch | Controls rack/DC awareness for replica placement and LOCAL_QUORUM routing |
| Kafka | min.insync.replicas | Minimum ISR for writes with acks=all; prevents data loss at cost of availability |
| Kafka | unclean.leader.election.enable | false = never elect out-of-ISR replica (safer); true = higher availability, risk of data loss |
- Lamport, "Time, Clocks, and the Ordering of Events" (1978)
- Fischer, Lynch, Paterson, "Impossibility of Distributed Consensus" (1985)
- Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014)
- Das et al., "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership" (2002)
- Kulkarni et al., "Logical Physical Clocks" (HLC, 2014)
- Kleppmann, Designing Data-Intensive Applications, chapters 8 & 9
- TLA+ specifications for Raft: github.com/ongardie/raft.tla
Found this guide useful? Buy me a coffee ☕