Chapter 4: CAP Theorem & Consistency Models
Introduction
The CAP theorem is the most misunderstood concept in distributed systems. Pop-engineering reduces it to "pick 2 of 3" with a triangle diagram, leading to dangerous oversimplifications. The reality: network partitions aren't optional, so every distributed system must choose between Consistency and Availability during a partition.
This chapter covers:
- What CAP actually means (formal definitions, not hand-wavy triangles)
- PACELC: the extension that matters more in practice
- The consistency model hierarchy from linearizability to eventual consistency
- How real systems (DynamoDB, Cassandra, Spanner, etc.) map to these models
- Quorum systems, conflict resolution, CRDTs, and split-brain scenarios
Interview Reality: Most candidates fail CAP questions not because they don't know "pick 2 of 3", but because they can't explain what happens during an actual partition, or they confuse consistency models with consensus algorithms.
1. CAP Theorem
1.1 Formal Definition
Brewer's Conjecture (2000): In a distributed system with data replication, you cannot guarantee all three of the following simultaneously:
- Consistency (C): Every read receives the most recent write or an error
- Availability (A): Every request receives a response (without guarantee it's the most recent write)
- Partition Tolerance (P): The system continues to operate despite arbitrary message loss/delay between nodes
Gilbert-Lynch Proof (2002): Formalized CAP as a theorem. Key insight: partitions are not optional in asynchronous networks, so the real choice is between C and A when a partition occurs.
graph TD
A[Distributed System] --> B{Network Partition Occurs?}
B -->|No| C[CA: Both Consistent and Available]
B -->|Yes| D{Choose Trade-off}
D -->|Prioritize C| E[CP: Consistent but Unavailable
Reject writes/reads to minority] D -->|Prioritize A| F[AP: Available but Inconsistent
Accept writes/reads everywhere] style C fill:#2ecc71 style E fill:#e74c3c style F fill:#f39c12
Reject writes/reads to minority] D -->|Prioritize A| F[AP: Available but Inconsistent
Accept writes/reads everywhere] style C fill:#2ecc71 style E fill:#e74c3c style F fill:#f39c12
Key Insight: "CA" systems don't exist in distributed environments. Single-node databases are CA because there's no partition. Once you distribute, you're either CP or AP during partitions.
1.2 What C/A/P Really Mean
Consistency (C) - Linearizability
CAP's "C" means linearizability, the strongest consistency model. After a write completes, all subsequent reads see that write. There's a total order of operations consistent with real-time ordering.
sequenceDiagram
participant Client1
participant System
participant Client2
Client1->>System: write(x, 5) at t1
System-->>Client1: ack at t2
Note over System: Write committed at t2
Client2->>System: read(x) at t3 (t3 > t2)
System-->>Client2: 5 (MUST see the write)
Note right of System: Linearizability: reads see
all completed writes
all completed writes
Availability (A) - Every Node Responds
CAP's "A" means every non-failing node must respond to requests in a bounded time. Not just "the system is up", but "every reachable node answers queries".
graph LR
C[Client] -->|Request| N1[Node 1]
C -->|Request| N2[Node 2]
C -->|Request| N3[Node 3]
N1 -->|Response| C
N2 -->|Response| C
N3 -->|Response| C
style N1 fill:#2ecc71
style N2 fill:#2ecc71
style N3 fill:#2ecc71
Not Availability: "The system is up" (that's fault tolerance). CAP's A is stronger: every accessible node must respond, even if it can't contact other nodes.
Partition Tolerance (P) - Continue During Split
The system keeps operating when network messages are lost or delayed. In async networks (the internet), partitions are inevitable, so P is not optional.
graph TB
subgraph Datacenter A
N1[Node 1]
N2[Node 2]
end
subgraph Datacenter B
N3[Node 3]
N4[Node 4]
end
N1 -.->|Partition| N3
N1 -.->|Partition| N4
N2 -.->|Partition| N3
N2 -.->|Partition| N4
style N1 fill:#e74c3c
style N2 fill:#e74c3c
style N3 fill:#3498db
style N4 fill:#3498db
classDef partition stroke:#f00,stroke-width:3px,stroke-dasharray:5,5
| Aspect | Popular Understanding | Formal Definition |
|---|---|---|
| Consistency | "All nodes see same data" | Linearizability: total order consistent with real-time |
| Availability | "System is up" | Every non-failing node responds in bounded time |
| Partition Tolerance | "Optional feature" | Must handle network splits (not optional in distributed systems) |
1.3 Gilbert-Lynch Proof Sketch
The proof shows you cannot have both C and A during a partition:
- Setup: Two nodes (N1, N2) with replicated data. Network partition splits them.
- Write to N1: Client writes x=5 to N1. N1 acknowledges.
- Partition: N1 cannot communicate with N2.
- Read from N2: Client reads x from N2.
- Contradiction:
- For Consistency: N2 must return x=5 (latest write) or error. But N2 hasn't received the update (partition).
- For Availability: N2 must respond. It can only return old value (breaking C) or refuse (breaking A).
sequenceDiagram
participant Client
participant N1
participant N2
Client->>N1: write(x, 5)
N1-->>Client: ack
Note over N1,N2: PARTITION OCCURS
Client->>N2: read(x)
alt Choose Consistency (CP)
N2-->>Client: Error (can't guarantee latest)
Note right of N2: Unavailable but Consistent
else Choose Availability (AP)
N2-->>Client: old_value (maybe x=0)
Note right of N2: Available but Inconsistent
end
Common Mistake: "My system is CA because it's consistent and available 99.9% of the time." Wrong. CAP is about what happens during a partition. You're CP or AP based on your behavior when the network splits.
2. CAP Misconceptions
2.1 "Pick 2 of 3" is Misleading
The triangle diagram is harmful:
graph TD
C[Consistency]
A[Availability]
P[Partition Tolerance]
C --- A
A --- P
P --- C
style C fill:#3498db
style A fill:#2ecc71
style P fill:#e74c3c
Why it's wrong:
- P is not optional: In distributed systems, partitions happen. You can't "not choose" P.
- CA doesn't exist: A single-node system is CA, but it's not distributed.
- It's not binary: Systems trade off degrees of consistency for degrees of availability.
2.2 Spectrum, Not Binary
Real systems aren't purely CP or AP. They offer tunable consistency:
graph LR
Strong[Strong Consistency
CP] --> T1[Tunable] T1 --> T2[Most Systems
Live Here] T2 --> T3[Tunable] T3 --> Weak[Eventual Consistency
AP] style Strong fill:#e74c3c style T2 fill:#f39c12 style Weak fill:#2ecc71
CP] --> T1[Tunable] T1 --> T2[Most Systems
Live Here] T2 --> T3[Tunable] T3 --> Weak[Eventual Consistency
AP] style Strong fill:#e74c3c style T2 fill:#f39c12 style Weak fill:#2ecc71
| System | CAP Label | Reality |
|---|---|---|
| DynamoDB | AP | AP by default, optional CP reads (strongly consistent) |
| Cassandra | AP | Tunable: can do CP with QUORUM writes/reads |
| MongoDB | CP | CP for primary writes, but tunable read concerns |
| Spanner | CP | CP with linearizability (sacrifices availability during partitions) |
| Riak | AP | AP with tunable consistency (R/W values) |
2.3 CAP Only Applies During Partitions
When network is healthy: Systems can be both consistent AND available. CAP constraints only kick in during a partition.
stateDiagram-v2
[*] --> Normal: System starts
Normal --> Partition: Network failure
Partition --> Normal: Network heals
state Normal {
[*] --> CA
CA: Consistent AND Available
note right of CA: CAP doesn't constrain here
}
state Partition {
[*] --> Choice
Choice --> CP: Prioritize Consistency
Choice --> AP: Prioritize Availability
note right of Choice: CAP forces a choice
}
Interview Trap: "Is DynamoDB CP or AP?" Answer: "AP during partitions, but offers optional strongly consistent reads during normal operation. The CAP classification describes partition behavior."
2.4 Latency is Not in CAP
CAP says nothing about latency. A CP system can be slow. An AP system can be fast. PACELC extends CAP to include latency trade-offs.
3. PACELC Extension
3.1 PACELC Definition
PACELC (Daniel Abadi, 2010) extends CAP:
If Partition: choose between Availability and Consistency
Else (no partition): choose between Latency and Consistency
This matters because systems spend 99%+ of time in the "Else" state. The Latency vs Consistency trade-off is what you experience daily.
graph TD
A[Request Arrives] --> B{Partition?}
B -->|Yes| C[CAP: Choose A or C]
B -->|No| D[Choose L or C]
C --> C1[PA: Available, Inconsistent]
C --> C2[PC: Consistent, Unavailable]
D --> D1[EL: Low Latency, Eventual Consistency]
D --> D2[EC: Higher Latency, Strong Consistency]
style C1 fill:#2ecc71
style C2 fill:#e74c3c
style D1 fill:#f39c12
style D2 fill:#3498db
Why Latency vs Consistency?
To ensure strong consistency during normal operation, you need:
- Synchronous replication to multiple nodes
- Waiting for acknowledgments from quorum/all replicas
- Coordination overhead (locks, consensus)
All of this adds latency. Async replication is faster but eventually consistent.
sequenceDiagram
participant Client
participant Primary
participant Replica1
participant Replica2
Note over Client,Replica2: Strong Consistency (High Latency)
Client->>Primary: write(x, 5)
Primary->>Replica1: replicate(x, 5)
Primary->>Replica2: replicate(x, 5)
Replica1-->>Primary: ack
Replica2-->>Primary: ack
Primary-->>Client: ack (SLOW: waited for replicas)
Note over Client,Replica2: Eventual Consistency (Low Latency)
Client->>Primary: write(x, 10)
Primary-->>Client: ack (FAST: immediate)
Primary--)Replica1: async replicate(x, 10)
Primary--)Replica2: async replicate(x, 10)
3.2 Real Systems on PACELC
| System | Partition (PA vs PC) | Else (EL vs EC) | PACELC Label |
|---|---|---|---|
| DynamoDB | PA (available) | EL (low latency, eventual) | PA/EL |
| Cassandra | PA (available) | EL (low latency) | PA/EL |
| Riak | PA (available) | EL (low latency) | PA/EL |
| MongoDB | PC (consistent) | EC (strong consistency) | PC/EC |
| HBase | PC (consistent) | EC (strong consistency) | PC/EC |
| Spanner | PC (consistent) | EC (strong, but optimized latency) | PC/EC |
| Cosmos DB | Tunable | Tunable (5 consistency levels) | Configurable |
| BigTable | PA (available) | EL (eventual) | PA/EL |
quadrantChart
title PACELC Positioning
x-axis Low Latency EL --> Strong Consistency EC
y-axis Available PA --> Consistent PC
quadrant-1 PA/EC Rare
quadrant-2 PC/EC MongoDB Spanner
quadrant-3 PC/EL Rare
quadrant-4 PA/EL DynamoDB Cassandra
DynamoDB: [0.2, 0.8]
Cassandra: [0.15, 0.75]
MongoDB: [0.7, 0.2]
Spanner: [0.6, 0.15]
Riak: [0.1, 0.85]
Pattern: Most AP systems (DynamoDB, Cassandra) are also EL (low latency). Most CP systems (MongoDB, HBase) are also EC (strong consistency). The trade-offs align naturally.
3.3 PACELC Decision Matrix
| Use Case | Partition Priority | Normal Priority | Recommendation |
|---|---|---|---|
| Bank account balance | PC (must be consistent) | EC (strong consistency) | PC/EC (MongoDB, Spanner) |
| Social media likes | PA (always available) | EL (fast) | PA/EL (DynamoDB, Cassandra) |
| E-commerce inventory | PC (no overselling) | EC (consistency) | PC/EC |
| Session store | PA (must login) | EL (fast auth) | PA/EL (Redis, DynamoDB) |
| Real-time analytics | PA (always up) | EL (low latency queries) | PA/EL (Cassandra) |
| Financial transactions | PC (correctness) | EC (strong consistency) | PC/EC (RDBMS, Spanner) |
4. Consistency Models Hierarchy
CAP's "consistency" means linearizability, but there's a spectrum of consistency models. Understanding this hierarchy is critical for system design.
graph TD
L[Linearizability
Strongest] --> S[Sequential Consistency] S --> C[Causal Consistency] C --> RYW[Read-Your-Writes] RYW --> MR[Monotonic Reads] MR --> MW[Monotonic Writes] MW --> E[Eventual Consistency
Weakest] style L fill:#e74c3c style S fill:#e67e22 style C fill:#f39c12 style RYW fill:#f1c40f style MR fill:#2ecc71 style MW fill:#1abc9c style E fill:#3498db
Strongest] --> S[Sequential Consistency] S --> C[Causal Consistency] C --> RYW[Read-Your-Writes] RYW --> MR[Monotonic Reads] MR --> MW[Monotonic Writes] MW --> E[Eventual Consistency
Weakest] style L fill:#e74c3c style S fill:#e67e22 style C fill:#f39c12 style RYW fill:#f1c40f style MR fill:#2ecc71 style MW fill:#1abc9c style E fill:#3498db
4.1 Linearizability (Strongest)
Definition: Operations appear to execute atomically and instantaneously at some point between invocation and response. There's a total order of all operations consistent with real-time ordering.
In plain English: The system behaves like a single, non-replicated data structure. After a write completes, all reads see that write.
Formal Properties:
- Total order: All operations have a global order
- Real-time ordering: If op1 completes before op2 starts, op1 appears before op2 in the total order
- Recency: Reads see the most recent write (in the total order)
sequenceDiagram
participant C1 as Client 1
participant Sys as System
participant C2 as Client 2
participant C3 as Client 3
Note over Sys: Initial: x=0
C1->>Sys: write(x, 1) starts
Sys-->>C1: ack (write completes at T1)
Note over Sys: Linearization point at T1
C2->>Sys: read(x) at T2 (T2 > T1)
Sys-->>C2: returns 1 (MUST see write)
C3->>Sys: read(x) at T3 (T3 > T1)
Sys-->>C3: returns 1 (MUST see write)
Note right of Sys: Linearizability: all reads
after write completion
see the new value
after write completion
see the new value
Example: Linearizable vs Non-Linearizable
Linearizable:
Time ---->
C1: write(x, 5) [completes at T1]
C2: read(x) → 5 [at T2 > T1] ✓
C3: read(x) → 5 [at T3] ✓
NOT Linearizable:
Time ---->
C1: write(x, 5) [completes at T1]
C2: read(x) → 5 [at T2 > T1]
C3: read(x) → 0 [at T3 > T2] ✗ VIOLATION
C3 saw old value after C2 saw new value
Cost of Linearizability:
- Latency: Must coordinate across replicas (quorum, consensus)
- Availability: Cannot serve requests if majority unreachable (CAP trade-off)
- Throughput: Coordination limits scalability
| System | Linearizable? | How/Why |
|---|---|---|
| Google Spanner | ✓ Yes | TrueTime API + Paxos |
| ZooKeeper | ✓ Yes (writes) | ZAB consensus, writes linearizable, reads sequential |
| etcd | ✓ Yes | Raft consensus |
| DynamoDB | ✗ No (default) | Eventually consistent by default |
| DynamoDB (strong) | ✓ Yes (optional) | Strongly consistent reads (slower, less available) |
| Cassandra | ✗ No | Tunable consistency, but not linearizable even with QUORUM |
Common Mistake: "QUORUM reads/writes in Cassandra are linearizable." No. Quorums provide consistency but not linearizability due to sloppy quorums, hinted handoff, and timestamp conflicts.
4.2 Sequential Consistency
Definition: Operations from all processes appear to execute in some sequential order, and operations from each process appear in the order they were issued. No real-time ordering constraint.
Difference from Linearizability: Sequential consistency doesn't require real-time ordering. If write1 completes before write2 starts (in real time), they can appear in either order in the sequential history.
sequenceDiagram
participant C1
participant System
participant C2
Note over System: Initial: x=0, y=0
C1->>System: write(x, 1) completes at T1
C2->>System: write(y, 2) completes at T2 (T2 > T1)
Note over System: Linearizability: x=1 MUST come before y=2
Sequential: Either order OK C1->>System: read(x) System-->>C1: 1 C1->>System: read(y) System-->>C1: 0 or 2 (either OK for sequential)
Sequential: Either order OK C1->>System: read(x) System-->>C1: 1 C1->>System: read(y) System-->>C1: 0 or 2 (either OK for sequential)
Example:
Sequentially Consistent (but not Linearizable):
Real time:
C1: write(x, 1) [completes at T1]
C2: write(y, 2) [starts at T3 > T1]
Observed:
C3: read(y) → 2
C3: read(x) → 0 ✗ NOT linearizable (saw y before x despite T1 < T3)
✓ IS sequentially consistent (some order exists)
Where It's Used:
- ZooKeeper reads: Writes are linearizable, but reads from any replica are sequentially consistent (see writes in order, but may lag)
- Multiprocessor memory models: Many CPUs provide sequential consistency (or weaker)
| Property | Linearizability | Sequential Consistency |
|---|---|---|
| Total order | ✓ | ✓ |
| Real-time ordering | ✓ | ✗ |
| Per-process order | ✓ | ✓ |
| Recency guarantee | ✓ (immediate) | ✗ (eventual) |
| Performance | Slower | Faster |
4.3 Causal Consistency
Definition: Causally related operations are seen in the same order by all processes. Concurrent (non-causally-related) operations can be seen in different orders.
Causality: Operation A is causally before B if:
- A and B are from the same process, and A happens before B
- A is a write, B is a read, and B reads A's value
- Transitivity: A → C and C → B implies A → B
graph LR
W1[Write x=1] -->|causal| R1[Read x → 1]
R1 -->|causal| W2[Write y=2
based on x] W3[Write z=3] -.->|concurrent| W1 style W1 fill:#3498db style R1 fill:#2ecc71 style W2 fill:#e74c3c style W3 fill:#f39c12
based on x] W3[Write z=3] -.->|concurrent| W1 style W1 fill:#3498db style R1 fill:#2ecc71 style W2 fill:#e74c3c style W3 fill:#f39c12
Example:
C1: write(x, 1) [W1]
C2: read(x) → 1 [R1 - causally after W1]
C2: write(y, 2) [W2 - causally after R1]
Causal consistency: Any process reading y=2 MUST also see x=1
C3: read(y) → 2
C3: read(x) → MUST be 1 (not 0)
Concurrent writes (no causality):
C1: write(x, 1) [W1]
C2: write(y, 2) [W2 - concurrent with W1]
C3: read(x) → 1, read(y) → 0 ✓ OK
C4: read(x) → 0, read(y) → 2 ✓ OK (different order is fine)
Implementation:
Use vector clocks or version vectors to track causality.
sequenceDiagram
participant C1
participant System
participant C2
Note over System: Vector clock: {C1:0, C2:0}
C1->>System: write(x, 1) with VC {C1:1, C2:0}
System-->>C1: ack
C2->>System: read(x) returns (1, {C1:1, C2:0})
Note over C2: C2 learns C1:1
C2->>System: write(y, 2) with VC {C1:1, C2:1}
Note right of System: y causally depends on x
System-->>C2: ack
| System | Causal Consistency? |
|---|---|
| COPS (Causal+ consistency) | ✓ Yes (research system) |
| Bolt-on Causal (research) | ✓ Yes |
| MongoDB (causal consistency option) | ✓ Yes (client session) |
| Cosmos DB (session consistency) | ✓ Yes (within session) |
| Cassandra | ✗ No (tunable but not causal) |
4.4 Session Guarantees
Weaker than causal consistency, but practical for many applications. Guarantees apply within a single client session.
Read-Your-Writes (RYW)
If a process writes x, subsequent reads by that process see the write (or later values).
sequenceDiagram
participant Client
participant Primary
participant Replica
Client->>Primary: write(x, 5)
Primary-->>Client: ack
Note over Primary,Replica: Async replication (not yet)
Client->>Replica: read(x)
alt Without RYW
Replica-->>Client: 0 (stale) ✗ VIOLATION
else With RYW
Replica->>Primary: Redirect or wait for replication
Primary-->>Replica: x=5
Replica-->>Client: 5 ✓ CORRECT
end
Monotonic Reads
If a process reads x=v1, subsequent reads return v1 or later (never go backwards).
Client reads x → 5 [from Replica1]
Client reads x → 7 [from Replica2] ✓ OK (progressed)
Client reads x → 3 [from Replica3] ✗ VIOLATION (went backwards)
Monotonic Writes
Writes from a process are applied in order.
Client: write(x, 1) then write(x, 2)
Monotonic writes: x=2 is applied after x=1 everywhere
Without: Some replicas might see x=2 before x=1 (wrong order)
Writes-Follow-Reads
If a process reads x=v1 then writes y, the write to y is applied after the write that produced v1.
| Guarantee | Violation Example | How to Prevent |
|---|---|---|
| Read-Your-Writes | Write to primary, read from stale replica | Sticky sessions, read-from-primary, version tracking |
| Monotonic Reads | Load balancer sends requests to different replicas with different lag | Session affinity, version vectors |
| Monotonic Writes | Network delays cause writes to arrive out of order | Per-client sequence numbers |
| Writes-Follow-Reads | Read v1, write v2, but v2 arrives at replica before v1 | Version dependencies |
Real Systems:
- DynamoDB: No RYW by default (eventual reads), but strongly consistent reads provide it
- Cosmos DB: "Session consistency" level provides all four guarantees
- MongoDB: "Causal consistency" (with client sessions) provides all four
4.5 Eventual Consistency (Weakest)
Definition: If no new updates are made to an object, eventually all reads will return the last updated value. No time bound.
In practice: Replicas may diverge temporarily, but will converge given enough time without writes.
stateDiagram-v2
[*] --> Diverged: Write happens
Diverged --> Converging: Replication begins
Converging --> Converged: All replicas updated
Converged --> Diverged: New write
note right of Diverged: Replicas have different values
Reads may return stale data note right of Converged: All replicas agree
Reads consistent
Reads may return stale data note right of Converged: All replicas agree
Reads consistent
How Convergence Works:
1. Anti-Entropy (Background Sync):
- Replicas periodically compare data with peers
- Exchange missing updates
- Merkle trees for efficient comparison (Cassandra, DynamoDB)
2. Read Repair:
- During read, coordinator queries multiple replicas
- If values differ, return newest, then push to stale replicas
3. Hinted Handoff:
- If replica is down during write, store hint at another node
- When replica recovers, deliver the hint
sequenceDiagram
participant Client
participant Coordinator
participant R1 as Replica 1
participant R2 as Replica 2
participant R3 as Replica 3
Client->>Coordinator: write(x, 5)
Coordinator->>R1: replicate(x, 5)
Coordinator->>R2: replicate(x, 5)
Coordinator->>R3: replicate(x, 5)
R1-->>Coordinator: ack
Coordinator-->>Client: ack (W=1, returns immediately)
Note over R2,R3: R2 and R3 may not have value yet
par Async replication
R2-->>Coordinator: ack (delayed)
R3-->>Coordinator: ack (delayed)
end
Note over R1,R3: Eventually, all replicas converge
Problems with Eventual Consistency:
| Problem | Example | Impact |
|---|---|---|
| Stale reads | User updates profile, refresh shows old data | User confusion |
| Read-your-writes violation | Write to leader, read from follower (stale) | Lost updates appear |
| Monotonic read violation | Read from R1 (v2), then R2 (v1) | Time goes backwards |
| Conflicting writes | Two users edit same doc simultaneously | Need conflict resolution |
When Eventual Consistency is OK:
- Social media likes/follows: Exact count doesn't matter immediately
- DNS: Records change infrequently, caching is fine
- Analytics/logging: Approximate counts acceptable
- Content distribution: Stale content for brief period is fine
When it's NOT OK:
- Bank balances: Incorrect balance = lost money
- Inventory: Overselling products
- Access control: Revoked permissions must take effect immediately
- Leader election: Must have single leader
Interview Question: "When would you use eventual consistency?" Look for: understanding of business requirements, recognition that many apps can tolerate staleness, ability to identify critical invariants that require strong consistency.
5. Real System Mappings
5.1 DynamoDB
- Default: Eventually consistent reads (faster, lower cost)
- Option: Strongly consistent reads (slower, double cost, less available)
- Writes: Synchronously replicate to 3 AZs, acknowledge after majority (W=2)
// Eventually consistent read (default)
const params = {
TableName: 'Users',
Key: { userId: '123' }
};
dynamodb.getItem(params); // May return stale data
// Strongly consistent read
const params = {
TableName: 'Users',
Key: { userId: '123' },
ConsistentRead: true // Forces read from leader
};
dynamodb.getItem(params); // Returns latest data
5.2 Cassandra
Tunable consistency: Set per-request consistency levels for reads (R) and writes (W).
| Consistency Level | Meaning | Latency | Availability |
|---|---|---|---|
| ONE | Any 1 replica responds | Lowest | Highest |
| QUORUM | Majority (N/2 + 1) respond | Medium | Medium |
| ALL | All replicas respond | Highest | Lowest |
| LOCAL_QUORUM | Majority in local datacenter | Low | High (within DC) |
| EACH_QUORUM | Majority in every datacenter | Very High | Low |
Strong consistency: R + W > N (quorum intersection)
Example: RF=3 (3 replicas)
R=2, W=2: R + W = 4 > 3 ✓ Strong consistency
R=1, W=3: R + W = 4 > 3 ✓ Strong consistency
R=1, W=1: R + W = 2 < 3 ✗ Eventual consistency
5.3 Google Spanner
- Linearizable: External consistency (stronger than linearizability)
- TrueTime API: GPS + atomic clocks provide tight time bounds
- Commit wait: Wait out clock uncertainty to ensure ordering
sequenceDiagram
participant Client
participant Spanner
participant TrueTime
Client->>Spanner: Transaction commit
Spanner->>TrueTime: Get time bounds [earliest, latest]
Note over Spanner: Assign commit timestamp = latest
Note over Spanner: Wait until earliest > commit_timestamp
Spanner-->>Client: Ack (commit visible)
Note right of Spanner: Commit-wait ensures external consistency
5.4 MongoDB
- Writes: Always go to primary
- Read Concern: local, majority, linearizable
- Write Concern: 1 (primary ack), majority, all
// Linearizable read (strongest)
db.users.find({ userId: 123 }).readConcern("linearizable");
// Majority read (causal consistency with session)
db.users.find({ userId: 123 }).readConcern("majority");
// Local read (fastest, may be stale)
db.users.find({ userId: 123 }).readConcern("local");
5.5 PostgreSQL Replication
- Synchronous replication: Primary waits for standby acknowledgment (strong consistency, higher latency)
- Asynchronous replication: Primary doesn't wait (eventual consistency, lower latency, risk of data loss)
sequenceDiagram
participant Client
participant Primary
participant Standby
Note over Primary,Standby: Synchronous Replication
Client->>Primary: INSERT ...
Primary->>Standby: WAL stream
Standby-->>Primary: ack (flushed to disk)
Primary-->>Client: Commit success
Note over Primary,Standby: Asynchronous Replication
Client->>Primary: INSERT ...
Primary-->>Client: Commit success (immediate)
Primary--)Standby: WAL stream (async)
5.6 System Comparison
| System | Consistency Model | Tunable? | CAP | PACELC |
|---|---|---|---|---|
| Spanner | Linearizable (external consistency) | No | CP | PC/EC |
| DynamoDB | Eventual (optional strong) | Yes | AP (default) | PA/EL |
| Cassandra | Tunable (ONE to ALL) | Yes | AP | PA/EL |
| MongoDB | Strong (tunable read concern) | Yes | CP | PC/EC |
| ZooKeeper | Linearizable writes, sequential reads | No | CP | PC/EC |
| Cosmos DB | 5 levels (strong to eventual) | Yes | Configurable | Configurable |
| etcd | Linearizable | No | CP | PC/EC |
| Riak | Eventual (tunable R/W) | Yes | AP | PA/EL |
6. Quorum Systems
Quorums enable consistency without full replication acknowledgment. Key insight: read and write quorums must overlap to guarantee consistency.
6.1 Quorum Formula
R + W > N
- N: Total number of replicas
- W: Write quorum (# replicas that must acknowledge write)
- R: Read quorum (# replicas queried for read)
Why R + W > N? Ensures at least one replica is in both read and write quorums, guaranteeing the read sees the latest write.
graph TB
subgraph "N=5 replicas"
R1((R1))
R2((R2))
R3((R3))
R4((R4))
R5((R5))
end
subgraph "Write Quorum W=3"
R1
R2
R3
end
subgraph "Read Quorum R=3"
R2
R3
R4
end
R2 -.->|Overlap| R3
style R2 fill:#e74c3c
style R3 fill:#e74c3c
6.2 Common Quorum Configurations
| N | R | W | R+W | Consistency | Use Case |
|---|---|---|---|---|---|
| 3 | 2 | 2 | 4 > 3 ✓ | Strong | Balanced read/write |
| 3 | 1 | 3 | 4 > 3 ✓ | Strong | Read-heavy (fast reads) |
| 3 | 3 | 1 | 4 > 3 ✓ | Strong | Write-heavy (fast writes) |
| 3 | 1 | 1 | 2 < 3 ✗ | Eventual | Low latency, high availability |
| 5 | 3 | 3 | 6 > 5 ✓ | Strong | Tolerate 2 failures |
6.3 Quorum Read/Write Process
Quorum Write (W=2, N=3):
sequenceDiagram
participant Client
participant Coordinator
participant R1
participant R2
participant R3
Client->>Coordinator: write(x, 5)
par Write to replicas
Coordinator->>R1: write(x, 5, version=10)
Coordinator->>R2: write(x, 5, version=10)
Coordinator->>R3: write(x, 5, version=10)
end
R1-->>Coordinator: ack
R2-->>Coordinator: ack
Note over Coordinator: W=2 satisfied (2 acks)
Coordinator-->>Client: Success
Note over R3: R3 ack arrives later (or fails)
Quorum Read (R=2, N=3):
sequenceDiagram
participant Client
participant Coordinator
participant R1
participant R2
participant R3
Client->>Coordinator: read(x)
par Read from replicas
Coordinator->>R1: read(x)
Coordinator->>R2: read(x)
Coordinator->>R3: read(x)
end
R1-->>Coordinator: (x=5, version=10)
R2-->>Coordinator: (x=5, version=10)
Note over Coordinator: R=2 satisfied
Return value with highest version Coordinator-->>Client: x=5 R3-->>Coordinator: (x=3, version=8) [stale] Note over Coordinator: Trigger read-repair: send v10 to R3 Coordinator->>R3: repair(x=5, version=10)
Return value with highest version Coordinator-->>Client: x=5 R3-->>Coordinator: (x=3, version=8) [stale] Note over Coordinator: Trigger read-repair: send v10 to R3 Coordinator->>R3: repair(x=5, version=10)
6.4 Sloppy Quorums & Hinted Handoff
Problem: What if W replicas are unavailable during write?
Strict quorum: Fail the write (unavailable).
Sloppy quorum: Write to different nodes temporarily, deliver later (hinted handoff).
graph TB
Client[Client] -->|write| Coordinator
Coordinator -->|Intended: R1,R2,R3| Intended[R1, R2, R3]
R1[R1 Down ✗]
R2[R2 Up ✓]
R3[R3 Up ✓]
R4[R4 Up ✓]
Coordinator -->|Write to R2| R2
Coordinator -->|Write to R3| R3
Coordinator -->|Hint for R1 → R4| R4
R1b[R1 Recovers]
R4 -.->|Deliver hint| R1b
style R1 fill:#e74c3c
style R2 fill:#2ecc71
style R3 fill:#2ecc71
style R4 fill:#f39c12
Trade-off: Sloppy quorums improve availability but weaken consistency guarantees. DynamoDB and Cassandra use them.
6.5 Why Quorums Don't Guarantee Linearizability
Even with R + W > N, you can have non-linearizable behavior:
- Concurrent writes: Multiple clients write simultaneously, last-writer-wins based on timestamps (clock skew issues)
- Sloppy quorums: Hinted handoff means writes may not overlap with reads
- Network delays: Version vectors resolve conflicts, but not in real-time order
Interview Trap: "Cassandra with QUORUM reads and writes is linearizable." No. Quorums provide strong consistency (see latest write eventually) but not linearizability (real-time ordering).
7. Conflict Resolution
In AP systems (or during partitions), concurrent writes to the same key create conflicts. The system must resolve them.
7.1 Last-Writer-Wins (LWW)
Strategy: Assign a timestamp to each write. Keep the write with the latest timestamp.
Node1: write(x, 5) at T=100
Node2: write(x, 7) at T=102
Resolution: x=7 wins (T=102 > T=100)
Problem: Relies on synchronized clocks. Clock skew can cause wrong resolution.
sequenceDiagram
participant C1 as Client 1
participant N1 as Node 1 (clock=100)
participant N2 as Node 2 (clock=95)
participant C2 as Client 2
C1->>N1: write(x, A) at T=100
C2->>N2: write(x, B) at T=95
Note over N1,N2: Clock skew: N2 is behind
Note over N1,N2: After merge
N1->>N2: x=A (T=100)
N2->>N1: x=B (T=95)
Note over N1,N2: LWW: x=A wins
But B was written after A in real time!
But B was written after A in real time!
When to use: Acceptable data loss, no strict ordering requirements (e.g., cache, session data).
7.2 Vector Clocks
Idea: Track causality with per-node counters. Detect concurrent writes without relying on wall-clock time.
Vector Clock: Map of {node → counter}. Each node increments its counter on write.
Example:
Initial: x=0, VC={}
Node A writes x=1: VC={A:1}
Node B writes x=2 (concurrent): VC={B:1}
Node C reads both:
- x=1 with VC={A:1}
- x=2 with VC={B:1}
Conflict: {A:1} and {B:1} are concurrent (neither dominates)
Node C must resolve (manual or application logic)
Node C resolves to x=3: VC={A:1, B:1, C:1}
Comparison Rules:
- VC1 < VC2: VC1 happened before VC2 (VC1[i] ≤ VC2[i] for all i, and VC1 ≠VC2)
- VC1 || VC2: Concurrent (neither dominates)
graph TD
Start[x=0, VC=empty] --> A["A writes x=1
VC A:1"] Start --> B["B writes x=2
VC B:1"] A --> C["C reads both
VC A:1 and VC B:1"] B --> C C --> Conflict["Conflict Detected
A:1 || B:1"] Conflict --> Resolve["Resolve: x=3
VC A:1, B:1, C:1"] style Conflict fill:#e74c3c style Resolve fill:#2ecc71
VC A:1"] Start --> B["B writes x=2
VC B:1"] A --> C["C reads both
VC A:1 and VC B:1"] B --> C C --> Conflict["Conflict Detected
A:1 || B:1"] Conflict --> Resolve["Resolve: x=3
VC A:1, B:1, C:1"] style Conflict fill:#e74c3c style Resolve fill:#2ecc71
Problem: Vector clocks grow over time (more nodes = larger vectors). Pruning strategies needed.
Real Systems:
- Riak: Uses vector clocks, exposes conflicts to application
- Voldemort: Vector clocks with automatic pruning
7.3 CRDTs (Conflict-Free Replicated Data Types)
Idea: Design data structures that can be merged automatically without conflicts. Strong Eventual Consistency: replicas that have seen the same updates have the same state (no manual resolution).
Two flavors:
- State-based CRDTs (CvRDT): Replicas send full state, merge function is commutative, associative, idempotent
- Operation-based CRDTs (CmRDT): Replicas send operations, operations commute
7.3.1 G-Counter (Grow-only Counter)
Increment-only counter (cannot decrement).
State: {A: 5, B: 3, C: 2} // Per-node counters
Value: sum = 5 + 3 + 2 = 10
Node A increments: {A: 6, B: 3, C: 2} → sum = 11
Merge: max of each node's counter
Replica1: {A: 6, B: 3, C: 2}
Replica2: {A: 5, B: 4, C: 2}
Merged: {A: 6, B: 4, C: 2} → sum = 12
graph LR
R1[Replica 1
A:5, B:3, C:2
sum=10] R2[Replica 2
A:5, B:3, C:2
sum=10] R1 -->|A increments| R1a[A:6, B:3, C:2
sum=11] R2 -->|B increments| R2a[A:5, B:4, C:2
sum=11] R1a -->|Merge| M[A:6, B:4, C:2
sum=12] R2a -->|Merge| M style M fill:#2ecc71
A:5, B:3, C:2
sum=10] R2[Replica 2
A:5, B:3, C:2
sum=10] R1 -->|A increments| R1a[A:6, B:3, C:2
sum=11] R2 -->|B increments| R2a[A:5, B:4, C:2
sum=11] R1a -->|Merge| M[A:6, B:4, C:2
sum=12] R2a -->|Merge| M style M fill:#2ecc71
7.3.2 PN-Counter (Positive-Negative Counter)
Counter that can increment and decrement.
State:
P (increments): {A: 5, B: 3}
N (decrements): {A: 1, B: 0}
Value: sum(P) - sum(N) = (5+3) - (1+0) = 7
Node A decrements: N = {A: 2, B: 0}
Value: 8 - 2 = 6
7.3.3 G-Set (Grow-only Set)
Add-only set (cannot remove).
Replica1: {a, b, c}
Replica2: {b, c, d}
Merged: {a, b, c, d} (union)
7.3.4 2P-Set (Two-Phase Set)
Set with adds and removes (remove wins).
State:
Added: {a, b, c}
Removed: {b}
Value: Added - Removed = {a, c}
Once removed, element cannot be re-added (tombstone)
7.3.5 OR-Set (Observed-Remove Set)
Set where removes only affect observed adds (allows re-adding).
Replica1: add(a, tag1) → {a_tag1}
Replica2: add(a, tag2) → {a_tag2} [concurrent]
Replica1: remove(a_tag1) → tombstone a_tag1
Merged: {a_tag2} → a is still in the set (tag2 not removed)
7.3.6 LWW-Register (Last-Writer-Wins Register)
Single value with timestamp (LWW resolution).
Replica1: write(x, "hello", T=100)
Replica2: write(x, "world", T=102)
Merged: x="world" (T=102 > T=100)
CRDT Comparison:
| CRDT | Operations | Merge Rule | Use Case |
|---|---|---|---|
| G-Counter | Increment | Max per node | View counts, likes |
| PN-Counter | Increment, Decrement | Sum(P) - Sum(N) | Up/downvotes |
| G-Set | Add | Union | Tag collection |
| 2P-Set | Add, Remove (once) | Added - Removed | Membership (no re-join) |
| OR-Set | Add, Remove (observed) | Remove only seen adds | Shopping cart |
| LWW-Register | Write | Latest timestamp | Session data |
Real Systems Using CRDTs:
- Riak: Riak Data Types (counters, sets, maps)
- Redis: CRDT-based modules (RedisGraph, etc.)
- Akka: Distributed Data (CRDTs for actor state)
- Automerge: CRDT library for collaborative editing
Key Advantage: CRDTs eliminate the need for coordination. Replicas can diverge and merge later without conflicts. Perfect for offline-first apps, collaborative editing, edge computing.
8. Consensus vs Consistency
Common confusion: "Consensus means strong consistency." Wrong. They're different problems.
| Aspect | Consensus | Consistency |
|---|---|---|
| Problem | Agreement among nodes | Data visibility guarantees |
| Question | "What value should we agree on?" | "What value does a read return?" |
| Algorithms | Paxos, Raft, ZAB | Quorums, versioning, replication strategies |
| Goal | All non-faulty nodes agree on same value | Define read/write visibility rules |
| Use Cases | Leader election, log replication, atomic commit | Read consistency, staleness bounds |
8.1 How Consensus Enables Consistency
Consensus algorithms can be used to implement strong consistency models:
- Raft/Paxos: Replicate writes in agreed order → linearizable reads from leader
- ZooKeeper (ZAB): Consensus on write order → sequential consistency for reads
- Spanner (Paxos): Consensus + TrueTime → external consistency
graph TB
subgraph Consensus Layer
C1[Propose Value]
C2[Nodes Vote]
C3[Agree on Value]
end
subgraph Consistency Layer
S1[Replicate Agreed Value]
S2[Define Read Rules]
S3[Guarantee Visibility]
end
C3 --> S1
style C3 fill:#e74c3c
style S3 fill:#2ecc71
8.2 Systems Without Consensus
You can have strong consistency without consensus:
- Primary-backup replication: Primary orders writes, backups follow (no voting needed for agreement)
- Quorum-based systems: Cassandra with QUORUM reads/writes (no consensus, but strong-ish consistency)
8.3 Systems Without Strong Consistency
You can use consensus without strong consistency:
- Leader election: Use Raft to elect a leader, but don't enforce linearizable reads
- Configuration management: Consensus on config changes, but applications read locally (eventually consistent)
Interview Signal: "I'll use Raft for strong consistency." Probe: "How does Raft ensure linearizable reads?" (Correct answer: reads go to leader, or use read indexes/lease mechanisms.)
9. Tunable Consistency
Modern systems offer tunable consistency: choose consistency level per operation based on requirements.
9.1 Cassandra's Tunable Consistency
Write Consistency Levels:
| Level | Acks Required | Latency | Durability |
|---|---|---|---|
| ANY | 1 node (even hinted handoff) | Lowest | Lowest (can lose write) |
| ONE | 1 replica | Low | Low |
| TWO | 2 replicas | Medium | Medium |
| QUORUM | Majority (N/2+1) | Medium | High |
| ALL | All N replicas | Highest | Highest (least available) |
Read Consistency Levels:
| Level | Replicas Queried | Latency | Consistency |
|---|---|---|---|
| ONE | 1 replica | Lowest | Eventual |
| TWO | 2 replicas (return first) | Low | Better |
| QUORUM | Majority | Medium | Strong (if R+W > N) |
| ALL | All replicas | Highest | Strongest |
Trade-off Matrix:
quadrantChart
title Cassandra Consistency Levels
x-axis Low Latency --> High Latency
y-axis Weak Consistency --> Strong Consistency
quadrant-1 Strong and Slow
quadrant-2 Balanced
quadrant-3 Weak and Fast
quadrant-4 Slow and Weak avoid
ONE/ONE: [0.1, 0.2]
ONE/QUORUM: [0.3, 0.5]
QUORUM/QUORUM: [0.5, 0.7]
QUORUM/ALL: [0.7, 0.8]
ALL/ALL: [0.9, 0.95]
9.2 DynamoDB's Consistency Modes
| Mode | Consistency | Latency | Cost | Availability |
|---|---|---|---|---|
| Eventually Consistent Reads | Eventual | ~10ms | 1 RCU | High |
| Strongly Consistent Reads | Strong | ~10-20ms | 2 RCU | Lower (leader only) |
| Transactional Reads | Serializable | ~20-50ms | 4 RCU | Lower |
9.3 Cosmos DB's 5 Consistency Levels
graph LR
Strong[Strong] --> Bounded[Bounded Staleness]
Bounded --> Session[Session]
Session --> Consistent[Consistent Prefix]
Consistent --> Eventual[Eventual]
style Strong fill:#e74c3c
style Bounded fill:#e67e22
style Session fill:#f39c12
style Consistent fill:#2ecc71
style Eventual fill:#3498db
| Level | Guarantee | Use Case |
|---|---|---|
| Strong | Linearizability | Financial transactions, inventory |
| Bounded Staleness | Staleness bounded by K versions or T seconds | Monitoring dashboards (5min lag OK) |
| Session | Read-your-writes, monotonic reads/writes within session | User profiles, shopping carts |
| Consistent Prefix | Reads never see out-of-order writes | Social media feeds (no reordering) |
| Eventual | Convergence eventually | Likes, view counts |
Design Principle: Use the weakest consistency that satisfies business requirements. Strong consistency is expensive (latency, availability, cost).
10. Consistency in Practice
10.1 Decision Framework
graph TD
Start[Choose Consistency Model] --> Q1{Monetary correctness?}
Q1 -->|Yes| Strong[Strong Consistency
Linearizable] Q1 -->|No| Q2{User sees own writes?} Q2 -->|Must| RYW[Read-Your-Writes
Session Consistency] Q2 -->|No| Q3{Order matters?} Q3 -->|Yes| Causal[Causal Consistency] Q3 -->|No| Q4{Bounded staleness OK?} Q4 -->|Yes| Bounded[Bounded Staleness
e.g., 5 min lag] Q4 -->|No| Eventual[Eventual Consistency] style Strong fill:#e74c3c style RYW fill:#f39c12 style Causal fill:#3498db style Eventual fill:#2ecc71
Linearizable] Q1 -->|No| Q2{User sees own writes?} Q2 -->|Must| RYW[Read-Your-Writes
Session Consistency] Q2 -->|No| Q3{Order matters?} Q3 -->|Yes| Causal[Causal Consistency] Q3 -->|No| Q4{Bounded staleness OK?} Q4 -->|Yes| Bounded[Bounded Staleness
e.g., 5 min lag] Q4 -->|No| Eventual[Eventual Consistency] style Strong fill:#e74c3c style RYW fill:#f39c12 style Causal fill:#3498db style Eventual fill:#2ecc71
10.2 Use Case Mappings
| Use Case | Consistency Model | Reasoning | System Example |
|---|---|---|---|
| Bank account balance | Linearizable | Cannot show incorrect balance, no double-spend | Spanner, traditional RDBMS |
| E-commerce inventory | Strong (or eventual with reservations) | Cannot oversell (or use separate reservation system) | MongoDB, DynamoDB + compensation |
| User profile | Read-your-writes | User must see their own updates immediately | DynamoDB (strongly consistent reads) |
| Social media feed | Consistent prefix | Posts should not appear out of order | Cosmos DB, Cassandra |
| Likes/follows | Eventual | Exact count doesn't matter immediately | Cassandra, DynamoDB |
| Shopping cart | Session consistency | User sees their additions, others don't need to | Cosmos DB session, DynamoDB |
| Leader election | Consensus (linearizable) | Must agree on single leader | ZooKeeper, etcd, Consul |
| DNS | Eventual | Records change infrequently, caching is fine | DNS system |
| Distributed lock | Linearizable | Must prevent concurrent access | ZooKeeper, etcd, Redlock (Redis) |
| Metrics/logs | Eventual | Approximate counts acceptable | Cassandra, InfluxDB |
| Collaborative doc editing | Causal + CRDTs | Maintain edit order, auto-merge conflicts | Automerge, Yjs |
10.3 Mixed Consistency Example: E-commerce
Real systems use different consistency models for different data:
| Data Type | Consistency | System |
|---|---|---|
| User account (balance, payment) | Strong | PostgreSQL |
| Order status | Strong | PostgreSQL / DynamoDB strongly consistent |
| Inventory (available count) | Strong or eventual + reservation | Redis (strong) or Cassandra + reservation system |
| Product catalog | Eventual | DynamoDB (eventual), CDN cache |
| Shopping cart | Session (read-your-writes) | Redis, DynamoDB |
| Search index | Eventual | Elasticsearch |
| Recommendations | Eventual | Cassandra, ML model cache |
Common Mistake: Using strong consistency everywhere "to be safe". This kills performance and availability. Use strong consistency only where business logic demands it.
10.4 Handling Consistency Violations
When eventual consistency causes user-visible issues:
- Compensation logic: Undo operations (e.g., cancel oversold item, refund)
- User communication: "Your order is being processed" (hide inconsistency window)
- Idempotency: Safe to retry operations (use idempotency keys)
- Optimistic UI: Show expected state immediately, correct if wrong
11. Split-Brain Problem
Split-brain: Network partition causes multiple nodes to believe they're the leader, leading to divergent state and data corruption.
graph TB
L[Leader]
F1[Follower 1]
F2[Follower 2]
L --- F1
L --- F2
L2["Leader A thinks it's leader"]
F1b["Follower 1 elects Leader B"]
F2b["Leader B thinks it's leader"]
style L2 fill:#e74c3c
style F2b fill:#e74c3c
11.1 Example: Split-Brain Scenario
Cluster: [Node A (leader), Node B, Node C]
Network partition: A isolated, B and C can communicate
Node A: Still believes it's leader, accepts writes
Nodes B & C: Elect B as new leader, accepts writes
Result: Two leaders writing to same dataset (DISASTER)
11.2 Prevention Strategies
1. Quorum-Based Leader Election
Require majority to elect leader. Partition with minority cannot elect new leader.
5 nodes: Need 3 votes to become leader
Partition: [Node A, Node B] vs [Node C, Node D, Node E]
Left partition (2 nodes): Cannot elect leader (2 < 3)
Right partition (3 nodes): Can elect leader (3 ≥ 3) ✓
Only one leader possible
2. Fencing Tokens
Leader obtains incrementing token. Storage rejects writes with stale tokens.
sequenceDiagram
participant LeaderA as Leader A token=10
participant Storage
participant LeaderB as Leader B token=11
Note over LeaderA: Network partition, A doesn't know B is new leader
LeaderA->>Storage: write(x, 5) with token=10
LeaderB->>Storage: write(x, 7) with token=11
Storage-->>LeaderB: OK (token=11 accepted)
Storage-->>LeaderA: REJECTED (token=10 < current=11)
Note right of Storage: Fencing: only accept highest token
3. STONITH (Shoot The Other Node In The Head)
When partition detected, forcibly power off the old leader (used in HA clusters).
4. Lease-Based Leadership
Leader holds time-bound lease. Must renew regularly. If lease expires, leadership lost.
Leader A obtains lease: valid until T=100
At T=90: Leader A renews lease (if it can contact quorum)
Partition: Leader A cannot contact quorum, lease expires at T=100
After T=100: Leader A stops accepting writes (stepped down)
Nodes B & C elect Leader B with new lease
11.3 Generation Numbers
Each leader election increments a generation/epoch number. Stale leaders are ignored.
Generation 1: Leader A
Network partition
Generation 2: Leader B (elected by majority)
Leader A tries to write: includes generation=1
Storage: Rejects (current generation=2)
Real Systems:
| System | Split-Brain Prevention |
|---|---|
| ZooKeeper | Quorum-based leader election + epoch numbers |
| etcd | Raft consensus (majority quorum) + term numbers |
| Consul | Raft consensus + leader leases |
| MongoDB | Primary election with majority, fencing with optime |
| Kubernetes | etcd-backed leader election (lease mechanism) |
11.4 Split-Brain in Practice
GitHub outage (2018): Network partition between US East and US West. Both sides elected leader, accepted writes for 24 seconds. Required manual data reconciliation.
Lesson: Even with quorum systems, edge cases exist (e.g., brief window before old leader realizes it's partitioned). Use multiple defenses (quorum + fencing + generation numbers).
Interview Red Flag: "I'll use Redis for distributed locking." Redis (single master) can have split-brain during failover. Use ZooKeeper/etcd, or Redlock with careful consideration of failure modes.
12. Interview Signals & Mistakes
12.1 Strong Signals
- Differentiates CAP from PACELC: Understands CAP is about partition behavior, PACELC includes latency trade-off during normal operation
- Knows consistency model hierarchy: Can explain linearizability vs sequential vs causal vs eventual
- Maps real systems correctly: DynamoDB is AP/PA-EL, Spanner is CP/PC-EC, Cassandra is tunable
- Understands quorum math: R + W > N, can calculate appropriate R/W for use case
- Explains consensus vs consistency: They're different; consensus can implement consistency but not the same thing
- Tailors consistency to use case: Doesn't default to "strong consistency everywhere" or "eventual is fine"
12.2 Common Mistakes
| Mistake | Why It's Wrong | Correct Answer |
|---|---|---|
| "CAP: pick 2 of 3" | P is not optional in distributed systems | "During partition, choose A or C. Without partition, can have both." |
| "CA systems exist" | Only single-node systems are CA | "Distributed systems are either CP or AP during partitions" |
| "DynamoDB is consistent" | Conflates optional strong reads with default behavior | "DynamoDB is eventually consistent by default, offers optional strong reads" |
| "Cassandra QUORUM is linearizable" | Quorums don't guarantee real-time ordering | "QUORUM provides strong consistency but not linearizability due to timestamps" |
| "Eventual consistency is bad" | Depends on use case | "Eventual consistency is fine for many use cases (likes, views) and enables high availability" |
| "I'll use Raft for consistency" | Conflates consensus with consistency | "Raft provides consensus (agreement on log). For linearizable reads, need leader reads or read indexes." |
| "Strong consistency is always better" | Ignores latency, availability, cost trade-offs | "Use weakest consistency that meets business requirements" |
12.3 Interview Questions to Expect
- "Explain the CAP theorem."
- Weak: "Pick 2 of 3: consistency, availability, partition tolerance"
- Strong: "During network partition, choose consistency (reject requests) or availability (serve stale data). Without partition, can have both. P is not optional in distributed systems."
- "Is DynamoDB CP or AP?"
- Weak: "AP" (incomplete)
- Strong: "AP during partitions by default (eventually consistent reads). Offers optional strongly consistent reads (CP) at cost of latency and availability."
- "How do you ensure strong consistency in a distributed database?"
- Weak: "Use consensus"
- Strong: "Options: (1) Quorum reads/writes with R + W > N, (2) Linearizable reads from leader after consensus (Raft/Paxos), (3) Synchronous replication with fencing tokens to prevent split-brain"
- "When would you use eventual consistency?"
- Weak: "For performance"
- Strong: "When business logic tolerates temporary inconsistency: social media likes, view counts, non-critical metrics. NOT for financial data, inventory, access control where correctness is critical."
- "Explain linearizability vs serializability."
- Weak: "They're the same" (WRONG)
- Strong: "Linearizability: single-operation consistency (reads see latest writes, real-time order). Serializability: multi-operation consistency (transactions execute as if serial). Linearizability is about consistency model, serializability is about isolation level."
- "Design a distributed counter."
- Weak: "Use a database with strong consistency"
- Strong: "Depends on requirements. Exact count: G-Counter CRDT (increment-only, merge by sum). Increment/decrement: PN-Counter CRDT. High write throughput: Shard counter, aggregate periodically (eventual). Low latency: Redis with Lua scripts (strong, single-node). Multi-datacenter: CRDTs with anti-entropy."
12.4 Deep Dive Questions (Senior/Staff Level)
- "How does Spanner achieve linearizability across datacenters?"
- Expected: TrueTime API (GPS + atomic clocks), commit-wait protocol, external consistency guarantee
- "Why can't you have linearizability with pure async replication?"
- Expected: Async replication means no acknowledgment before returning. Client might read from stale replica after write acknowledged. Violates linearizability's real-time ordering requirement.
- "Explain the difference between vector clocks and version vectors."
- Expected: Semantically similar (track causality), but version vectors are per-object, vector clocks are per-process. Version vectors track object history, vector clocks track message causality.
- "Design a system for collaborative document editing (Google Docs style)."
- Expected: CRDTs (operation-based, e.g., Yjs, Automerge), operational transformation (older approach), conflict-free merging, causal consistency, WebSocket for real-time sync, eventual consistency with fast convergence.
- "How would you implement read-your-writes consistency in a multi-datacenter setup?"
- Expected: Options: (1) Sticky sessions (read from same DC), (2) Version tracking (client sends last-seen version, wait until replica catches up), (3) Read-from-leader (sacrifices latency), (4) Causal consistency with version vectors
Pro Tip: In interviews, always ask clarifying questions about consistency requirements before designing. "Do we need linearizable reads, or is eventual consistency acceptable?" shows you understand the trade-offs.
Summary
Key Takeaways
- CAP Theorem: During partition, choose Availability (AP) or Consistency (CP). Partition tolerance is not optional.
- PACELC: Extends CAP: If Partition (A vs C), Else (Latency vs Consistency). More practical than CAP alone.
- Consistency Hierarchy: Linearizable > Sequential > Causal > Session Guarantees > Eventual
- Quorums: R + W > N guarantees consistency. Doesn't guarantee linearizability due to timestamps and sloppy quorums.
- Conflict Resolution: LWW (clock-based), Vector Clocks (causal), CRDTs (automatic convergence)
- Consensus ≠Consistency: Consensus enables agreement, consistency defines read/write visibility
- Tunable Consistency: Modern systems (Cassandra, DynamoDB, Cosmos DB) let you choose per-operation
- Split-Brain Prevention: Quorum-based elections, fencing tokens, generation numbers, leases
- Use Case Matters: Bank balance → strong, social likes → eventual. Choose weakest consistency that meets requirements.
Real System Quick Reference
| System | Consistency | CAP | PACELC | Best For |
|---|---|---|---|---|
| Spanner | Linearizable | CP | PC/EC | Global strong consistency (bank transactions) |
| DynamoDB | Eventual (optional strong) | AP | PA/EL | High availability, low latency (sessions, catalog) |
| Cassandra | Tunable | AP | PA/EL | Multi-DC, high write throughput (metrics, logs) |
| MongoDB | Strong (tunable reads) | CP | PC/EC | Strong consistency, flexible schema (orders, user data) |
| ZooKeeper | Linearizable writes, sequential reads | CP | PC/EC | Coordination (leader election, config) |
| Cosmos DB | 5 levels (configurable) | Configurable | Configurable | Multi-model, global distribution with SLAs |
Decision Tree
- Critical correctness (money, inventory)? → Strong consistency (CP)
- User must see own writes? → Read-your-writes (session consistency)
- Order of events matters? → Causal consistency
- Can tolerate staleness? → Eventual consistency (AP)
- High availability > correctness? → AP systems (DynamoDB, Cassandra)
- Correctness > availability? → CP systems (Spanner, ZooKeeper)