Key Formulas & Code Examples
CAP Theorem (Brewer, 2000):
At most 2 of 3: Consistency, Availability, Partition tolerance
Amdahl's Law: Speedup = 1/[(1-P) + P/N]
Little's Law: L = ฮปW (concurrency = throughput ร latency)
At most 2 of 3: Consistency, Availability, Partition tolerance
Amdahl's Law: Speedup = 1/[(1-P) + P/N]
Little's Law: L = ฮปW (concurrency = throughput ร latency)
Consistency Models: Strong โ Eventual โ Causal โ Read-your-writes
Vector Clocks: VC[i] = local counter; happens-before: VCa โบ VCb iff โi: VCa[i] โค VCb[i]
Vector Clocks: VC[i] = local counter; happens-before: VCa โบ VCb iff โi: VCa[i] โค VCb[i]
Raft Leader Election (Go-like pseudocode):
for {
if election_timeout: become_candidate(), term++
if votes > majority: become_leader()
if higher term: step down
}
for {
if election_timeout: become_candidate(), term++
if votes > majority: become_leader()
if higher term: step down
}
Paxos Phases: 1a Prepare(n) โ 1b Promise(n, v) โ 2a Accept(n,v) โ 2b Accepted(n,v)
Core Concepts
1. Consensus Algorithms
Paxos (Lamport) and Raft (Ongaro) ensure distributed systems agree on a single value despite failures. Raft: leader election, log replication, safety. Used in etcd, Consul, TiKV.
Paxos (Lamport) and Raft (Ongaro) ensure distributed systems agree on a single value despite failures. Raft: leader election, log replication, safety. Used in etcd, Consul, TiKV.
2. Replication Models
Primary-backup: writes go to primary, replicated to backups. Multi-primary: multiple nodes accept writes (conflict resolution needed). Chain replication: writes flow through a chain of replicas.
Primary-backup: writes go to primary, replicated to backups. Multi-primary: multiple nodes accept writes (conflict resolution needed). Chain replication: writes flow through a chain of replicas.
3. Partitioning (Sharding)
Distributing data across nodes by key range, hash, or consistent hashing. Enables horizontal scaling. Hotspots and rebalancing are key challenges. Example: user data sharded by user_id % N.
Distributing data across nodes by key range, hash, or consistent hashing. Enables horizontal scaling. Hotspots and rebalancing are key challenges. Example: user data sharded by user_id % N.
4. Failure Detection
Heartbeats with timeout. Gossiph style: nodes exchange state periodically. Phi accrual failure detector (Hayashibara) outputs suspicion level vs binary detection.
Heartbeats with timeout. Gossiph style: nodes exchange state periodically. Phi accrual failure detector (Hayashibara) outputs suspicion level vs binary detection.
5. Distributed Transactions
Two-phase commit (2PC): prepare + commit phases. Blocking if coordinator fails. Three-phase commit (3PC) adds pre-commit but adds latency. Modern alternative: Calvin (deterministic), Spanner (TrueTime), sagas (compensating transactions).
Two-phase commit (2PC): prepare + commit phases. Blocking if coordinator fails. Three-phase commit (3PC) adds pre-commit but adds latency. Modern alternative: Calvin (deterministic), Spanner (TrueTime), sagas (compensating transactions).
Core Definitions
Byzantine Fault: Arbitrary or malicious behavior โ nodes may lie, collude, or send conflicting messages. Tolerated by PBFT (Practical Byzantine Fault Tolerance) requiring 3f+1 replicas for f faults.
Idempotency: An operation that produces the same result whether executed once or multiple times. Critical for retry logic. Example: PUT /users/123 {name: "x"} is idempotent; POST /orders is not.
Eventual Consistency: Given enough time without updates, all replicas converge to the same value. Used in DNS, DynamoDB, Cassandra. Trade-off: writes are fast and available but may read stale data.
Backpressure: The ability of a system to signal upstream when it cannot keep up. Prevents cascading failure. Implemented via bounded queues, flow control, and load shedding.
Worked Examples
Example 1: CAP Trade-off
During a network partition: CP system (HBase, MongoDB): stops accepting writes to maintain consistency. AP system (Cassandra, DynamoDB): continues accepting writes on both sides, reconciles later.
During a network partition: CP system (HBase, MongoDB): stops accepting writes to maintain consistency. AP system (Cassandra, DynamoDB): continues accepting writes on both sides, reconciles later.
Example 2: Consistent Hashing
Nodes and keys mapped to a ring. Key k is stored on the next clockwise node. Adding/removing a node affects only adjacent keys โ minimal redistribution. Virtual nodes improve balance.
Nodes and keys mapped to a ring. Key k is stored on the next clockwise node. Adding/removing a node affects only adjacent keys โ minimal redistribution. Virtual nodes improve balance.
Example 3: Vector Clock Comparison
VCA = [2,1,0], VCB = [1,2,1]. Neither dominates (A[0]>B[0] but B[1]>A[1], B[2]>A[2]). These events are concurrent โ potential conflict requiring application-level resolution.
VCA = [2,1,0], VCB = [1,2,1]. Neither dominates (A[0]>B[0] but B[1]>A[1], B[2]>A[2]). These events are concurrent โ potential conflict requiring application-level resolution.
Practice Problems
Problem 1: State the CAP theorem and explain the trade-offs.
Answer: A distributed system can provide at most two of: Consistency (all nodes see same data), Availability (every request gets response), Partition tolerance (system survives network failures). During partitions, choose C or A.
Answer: A distributed system can provide at most two of: Consistency (all nodes see same data), Availability (every request gets response), Partition tolerance (system survives network failures). During partitions, choose C or A.
Problem 2: What is the difference between 2PC and 3PC?
Answer: 2PC: prepare + commit; blocks if coordinator fails during commit. 3PC: adds pre-commit phase; non-blocking but adds an extra round-trip and assumes bounded network delays.
Answer: 2PC: prepare + commit; blocks if coordinator fails during commit. 3PC: adds pre-commit phase; non-blocking but adds an extra round-trip and assumes bounded network delays.
Problem 3: How does Raft ensure safety during leader changes?
Answer: Election safety: at most one leader per term. Log matching: entries with same index and term are identical. Leader completeness: leader's log contains all committed entries.
Answer: Election safety: at most one leader per term. Log matching: entries with same index and term are identical. Leader completeness: leader's log contains all committed entries.
Problem 4: What is idempotency and why is it important?
Answer: Same result regardless of how many times an operation is executed. Enables safe retries in distributed systems. Implemented via unique request IDs, idempotency keys, or natural idempotency (PUT/DELETE).
Answer: Same result regardless of how many times an operation is executed. Enables safe retries in distributed systems. Implemented via unique request IDs, idempotency keys, or natural idempotency (PUT/DELETE).
Problem 5: Explain the split-brain problem and how to prevent it.
Answer: Two nodes both think they're leader during a partition. Prevented by: quorum-based voting (majority), fencing tokens (older epochs rejected), and external coordination (ZooKeeper).
Answer: Two nodes both think they're leader during a partition. Prevented by: quorum-based voting (majority), fencing tokens (older epochs rejected), and external coordination (ZooKeeper).