Designing Distributed Consensus
1. Understanding Consensus Algorithms
| Algorithm | Properties | Used By |
|---|---|---|
| Paxos | Crash fault-tolerant; foundational; complex | Chubby, Spanner |
| Raft | Same guarantees, easier to understand | etcd, Consul, CockroachDB |
| Zab | Atomic broadcast for primary-backup | ZooKeeper |
| VR (Viewstamped) | State-machine replication | Research; influenced Raft |
| EPaxos | Leaderless, low latency | Niche |
2. Understanding Multi-Paxos and Fast Paxos
| Variant | Property |
|---|---|
| Basic Paxos | One value; 2 round trips |
| Multi-Paxos | Stable leader skips Phase 1; pipelines |
| Fast Paxos | 1 RTT in fast path; needs larger quorum |
| Cheap Paxos | Auxiliary acceptors |
| Generalized | Commutative ops can commit out of order |
3. Designing Leader Election System
| Mechanism | Detail |
|---|---|
| Bully algorithm | Highest ID wins |
| Ring | Token passed in ring |
| Lease-based | Time-bounded leadership; renew before expiry |
| Coordinator-backed | etcd/ZK ephemeral node |
| Raft-internal | Term + vote |
4. Designing Distributed Locks
| System | Approach | Caveat |
|---|---|---|
| Redis SETNX + TTL | Simple lock | Not safe under failover |
| Redlock | Quorum across N Redis | Disputed safety; Martin Kleppmann critique |
| ZooKeeper / etcd | Ephemeral sequential nodes | Strong; higher latency |
| DB row lock | SELECT FOR UPDATE | Tied to DB availability |
| Fencing token | Monotonic ID validated by resource | Required for correctness |
5. Designing Coordination Services
| Service | Strength |
|---|---|
| ZooKeeper | Mature, used by Kafka (legacy), HBase |
| etcd | Raft-based, Kubernetes backing store |
| Consul | Service discovery + KV + health |
| Chubby | Google internal |
6. Designing Split-Brain Prevention
| Technique | Description |
|---|---|
| Quorum (majority) | Only majority side proceeds |
| Fencing tokens | Older leader's writes rejected |
| STONITH | "Shoot The Other Node In The Head" |
| Witness/arbiter node | Tiebreaker in 2-DC setup |
7. Designing Quorum-Based Systems
| Param | Meaning |
|---|---|
| N | Replica count |
| W | Writes ack required |
| R | Reads ack required |
| Strong | R + W > N |
| Examples | Cassandra QUORUM, Dynamo |
8. Designing Conflict Resolution with CRDT
| CRDT Type | Operation | Use |
|---|---|---|
| G-Counter | Increment-only | Stats, likes |
| PN-Counter | Inc + Dec | Vote counts |
| G-Set | Add only | Append-only logs |
| OR-Set | Add/remove | Tags, members |
| LWW-Element-Set | Timestamp-based | Simple sets |
| RGA / Logoot | Sequences | Collab text editing |
| Used in | Riak, Redis CRDTs, Automerge, Yjs | — |
9. Designing Distributed Configuration Management
| Tool | Strength |
|---|---|
| etcd / Consul | Strong consistency, watchers |
| Spring Cloud Config | Git-backed config |
| AWS AppConfig / Parameter Store | Managed |
| LaunchDarkly / Unleash | Feature flags |
10. Designing Service Registration and Discovery
| Pattern | Tool |
|---|---|
| Client-side discovery | Eureka + Ribbon, Consul agent |
| Server-side discovery | K8s Service, AWS ALB |
| DNS-based | K8s CoreDNS, SRV records |
| Service mesh | Envoy/Istio sidecar discovery |
11. Designing Fencing Tokens
Example: Fencing token in storage write
// Lock service returns monotonically increasing token
long token = lockService.acquire("resource-A");
storage.write(payload, token); // storage rejects if token < lastSeenToken| Property | Detail |
|---|---|
| Monotonic | Strictly increasing per resource |
| Validated by resource | Storage stores last seen token |
| Use case | Prevents stale leader from writing |
12. Designing Lease-Based Coordination
| Element | Detail |
|---|---|
| Lease | Time-bounded grant of authority |
| Renewal | Heartbeat before expiry |
| Clock | Use monotonic clocks; account for skew |
| Use cases | Leader election, cache leases, file locks |