Beginner System design concept · Thinking in Systems · 40 mins read
Consistency & CAP Theorem
Understand the CAP theorem, its implications for distributed systems, and when to choose consistency over availability and vice versa.
Availability vs Consistency
The fundamental tradeoff in distributed systems
Intuition
Replicas cannot update instantly because messages take time and networks can fail. That lag forces every distributed store to decide whether a read should wait for all replicas to agree or return the nearest copy immediately. The choice shows up everywhere: payment ledgers must avoid double spending, while a social-media like count can be slightly stale. Picking the wrong model for the workload causes outages, data loss, or frustrated users.
Mental Model
Strong consistency means every observer sees the same state at the same time; it requires coordination, which adds latency and reduces availability during faults. Eventual consistency means replicas may diverge briefly but converge when writes stop, trading immediate correctness for responsiveness and partition tolerance. Think of it like: A teacher writes an answer on a whiteboard. Strong consistency makes everyone wait until the board is erased and rewritten, then copy the same version. Eventual consistency lets each student copy from the nearest desk; some briefly have older answers, but after a few minutes everyone is in sync.
Building Blocks
- Strong Consistency: Every successful read reflects all previous writes. Linearizability and serializability are the strongest forms and require coordination.
- Eventual Consistency: If no new writes arrive, all replicas eventually return the same value. During convergence reads may return stale data.
- Read-After-Write Consistency: A process that writes a value will immediately read that value back, even if other replicas are stale. Common for user-facing writes such as profile updates.
- Consistency Latency Tax: The additional round-trip time and coordination overhead required to guarantee strong consistency, especially across regions or replicas.
Definitions
- Strong Consistency
-
A guarantee that every read returns the most recent successful write, as if there were only a single copy of the data.
- Strongest forms include linearizability and strict serializability.
- Requires coordination such as locks, consensus, or single leaders.
- Adds latency and reduces availability during partitions.
- Eventual Consistency
-
A guarantee that, if no new updates are made, all replicas will converge to the same value.
- Reads may return stale data during convergence.
- Common in DNS, Cassandra, DynamoDB, and CDN caches.
- Applications must tolerate temporary inconsistency.
- Read-After-Write Consistency
-
A session guarantee that a process will always see its own most recent writes.
- Weaker than strong consistency but enough for many user-facing flows.
- Often implemented by routing a writer's reads back to the replica it wrote.
- Useful for profile updates, posts, and settings.
Bonus Points
- Conflict Resolution: Rules for choosing or merging divergent versions, such as last-write-wins, vector clocks, CRDTs, or application-level merges.
- Reconciliation: Detecting and repairing differences between replicas after they reconnect following a partition.
- Quorum: A minimum number of replica acknowledgments required to consider a read or write successful.
- Tunable Consistency: Letting clients choose a consistency level per operation to trade latency and availability for stronger guarantees.
- Causal Consistency: Causally related operations are seen in the same order by all processes; concurrent operations may be seen differently.
- Monotonic Reads: A process will never see an older value after it has already seen a newer one.
- CAP Tradeoff: During a network partition, a shared-data system must choose between consistency and availability.
Patterns
- Read Replicas with Bounded Staleness — When you want to scale reads but cannot tolerate arbitrarily old data.
Strategies
- Choose Consistency per Operation, Not per System When: When the same product contains both critical and best-effort data. How: Identify operations where inconsistency causes real harm and route those through strongly consistent paths. Allow eventually consistent paths for everything else. Example: A payment service uses strongly consistent ledger entries but eventually consistent notifications to the user interface.
- Expose Consistency Levels to Clients When: When users can reasonably decide how much consistency they need. How: Offer strongly consistent reads, eventually consistent reads, and transactional writes. Document the latency and availability cost of each. Example: DynamoDB defaults to eventually consistent reads and charges more for strongly consistent reads, letting callers decide per request.
Consistency is a Spectrum, Not a Switch
Strong consistency makes every read return the latest write, but requires coordination that adds latency and can fail during partitions. Eventual consistency lets replicas serve reads locally and converge later, trading immediate correctness for availability and responsiveness. Read-after-write offers a practical middle ground for a user's own updates without the full cost of global coordination. The right choice depends on which application invariants actually matter.
Tradeoffs
| Decision | Upside | Downside |
|---|---|---|
| Strongly Consistent Reads vs Low-Latency Reads | Strong reads prevent stale data, anomalies, and duplicate actions. Low-latency reads improve responsiveness and user experience. | Strong reads require cross-replica coordination and fail or stall during partitions. Low-latency reads can return stale or conflicting values. |
| Single-Region Strong Consistency vs Global Availability | Single-region consistency is simpler and faster. Global replication improves latency and disaster recovery. | Single-region designs create a geographic single point of failure. Global replication introduces cross-region consistency challenges. |
Real World
| System | How it's used |
|---|---|
| Spotify Social Features | Follower counts and collaborative playlist updates are eventually consistent. The service favors availability because a slightly stale follower count is less harmful than a failed request. |
| Banking Core Ledgers | Ledger entries are strongly consistent; transfers are committed through a single primary or consensus group. Availability is sacrificed rather than risking double spending. |
| Amazon DynamoDB | Default reads are eventually consistent for low latency and high availability. Strongly consistent reads and transactions are opt-in for operations that need them. |
| DNS | DNS is a canonical eventually consistent system. Record updates propagate with TTL-based caching; resolvers may return stale values until caches expire. |
Interview
Questions interviewers ask
- What is the difference between strong and eventual consistency?
- When would you choose availability over consistency?
- How do you handle conflicts in an eventually consistent system?
- Give an example of a system that is strongly consistent and one that is eventually consistent.
- What is read-after-write consistency and when is it useful?
What a strong answer covers
Candidate should define strong and eventual consistency, explain the availability tradeoff, give concrete examples, describe at least one conflict-resolution strategy, and know that consistency is a spectrum.
Common traps
- Claiming eventual consistency is always enough for any application.
- Ignoring the latency cost of strong consistency.
- Confusing availability with latency.
- Failing to explain how conflicts are detected and resolved.
Quiz
Which statement best describes eventual consistency?
- If no new writes occur, all replicas eventually converge to the same value
- Every read returns the most recent write immediately
- Replicas are never allowed to diverge
- Writes are only accepted by a single leader
Eventual consistency means replicas may be temporarily stale but will converge if updates stop.
Strong consistency is usually more expensive than eventual consistency because it requires:
- Coordination such as locks, leaders, or consensus
- More disk space per record
- Fewer replicas
- No network communication
Strong consistency needs coordination across replicas, which adds latency and reduces availability during partitions.
Read-after-write consistency guarantees that:
- A process will always see its own recent writes
- All replicas update simultaneously
- Reads never return stale data
- Writes are ordered globally
Read-after-write ensures a writer observes the values it previously wrote, a useful session guarantee weaker than linearizability.
A system that accepts writes on both sides of a partition and merges divergent replicas later is prioritizing:
- Availability over strong consistency
- Strong consistency over availability
- Durability over availability
- Security over consistency
Accepting writes during a partition keeps the system available but requires later reconciliation and may expose stale data.
Which technique is most appropriate for resolving semantic conflicts that a database cannot decide automatically?
- Application-level reconciliation
- Last-write-wins on timestamps alone
- Ignoring the conflict
- Deleting both versions
When automatic rules would lose meaning, the application should detect the conflict and either merge values or surface choices to the user.
CAP Theorem
The formal constraint on distributed systems
Intuition
Distributed systems are expected to keep working when networks fail, but a partition isolates replicas and makes it impossible for every node to agree on the latest value. CAP theorem says that during such a partition, a system that shares mutable data must choose between returning consistent results and staying available. The real decision is not C versus A versus P, but which side to take when the network splits. The theorem is a quick sanity test for product claims and architectural choices. It explains why a bank ledger blocks transfers during a partition while a shopping cart keeps accepting clicks.
Mental Model
CAP applies only when the network partitions. A partition-tolerant system must keep running, so the only real choice is whether to block writes that cannot be coordinated (CP) or accept them and reconcile later (AP). In normal operation many systems are both consistent and available. Think of it like: A remote warehouse and a store share one inventory count. If the phone line between them is cut, they must either stop sales to avoid overselling or keep selling and fix the count later.
Building Blocks
- Consistency (C): Every read receives the most recent successful write or an error. In CAP this usually means linearizable consistency, where the distributed store behaves like a single copy.
- Availability (A): Every request receives a non-error response, without a guarantee that it contains the most recent write. Available systems keep serving under partitions.
- Partition Tolerance (P): The system continues to operate despite network partitions that prevent some nodes from communicating. Real distributed systems must tolerate partitions because networks fail.
- Network Partition: A failure that splits a system into groups that cannot communicate with each other, even though each group may be internally healthy.
Definitions
- CAP Theorem
-
A distributed shared-data system can guarantee at most two of Consistency, Availability, and Partition Tolerance, but since partitions are unavoidable, the practical choice is between CP and AP behavior during a partition.
- Formally articulated by Eric Brewer in 2000 and later proved by Gilbert and Lynch.
- Applies specifically to network partitions, not to all failure modes.
- Many systems are consistent and available in steady state and only become CP or AP when partitioned.
- Network Partition
-
A communication failure that divides a distributed system into disjoint groups that cannot exchange messages.
- Partitions can be complete or partial, symmetric or asymmetric.
- They are indistinguishable from slow messages or crashed nodes from the receiver's perspective.
- Systems react via timeouts, heartbeats, and gossip.
- Split Brain
-
A condition in which a partitioned system has two or more active writable partitions, each accepting independent writes.
- Split brain produces divergent data that must be reconciled.
- Common mitigations include quorums, fencing tokens, and majority-based leader election.
- It is one of the most expensive failure modes in distributed databases.
Bonus Points
- CP Behavior: Under a partition, the system refuses or delays writes to the minority side to keep data consistent, sacrificing availability.
- AP Behavior: Under a partition, the system keeps accepting reads and writes on both sides and reconciles divergence later.
- Quorum: A minimum number of nodes that must agree before an operation is considered successful.
- PACELC: If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.
- Linearizability: Strong consistency where every write appears to take effect instantaneously at some point between its invocation and response.
- Fault Tolerance: The ability to keep operating correctly in the presence of node crashes, disk failures, or network failures.
Patterns
- Majority-Quorum Writes — When you need strong consistency during partitions and can tolerate unavailability on the minority side.
- Graceful Degradation Under Partition — When you want to stay available for reads but protect critical writes during a partition.
Strategies
- Classify the Workload by Consistency Need When: Before choosing a database or replication model. How: Ask which operations must be strongly consistent and which can be eventually consistent. Route each workload to the appropriate store. Example: An e-commerce platform keeps inventory in a CP SQL database to avoid overselling, while product recommendations live in an AP cache.
- Use Quorums to Bound Inconsistency When: When you want tunable consistency without fully committing to CP or AP. How: Require R + W > N replicas for a read or write to succeed. Tune R and W for stronger consistency or higher availability. Example: Cassandra lets clients set ConsistencyLevel. QUORUM gives stronger guarantees than ONE at the cost of availability during partial failures.
- Detect Partitions Fast and Act Deliberately When: When you must choose between CP and AP behavior automatically. How: Monitor heartbeats, gossip, and request timeouts. When a partition is detected, either fence the minority or switch to local-mode operations with conflict resolution. Example: ZooKeeper detects leader disconnection via heartbeat timeouts; followers that lose the leader stop serving writes to avoid split brain.
CAP is About Partitions, Not a Permanent Label
CAP does not force a system to be CP or AP forever; it only constrains behavior during a partition. Most systems are consistent and available when the network is healthy and switch behavior when it fails. The practical lesson is to classify operations by their real consistency needs and route them to the right storage or replication model rather than labeling the entire stack as CP or AP.
Tradeoffs
| Decision | Upside | Downside |
|---|---|---|
| CP vs AP During Partitions | CP guarantees correctness and avoids split brain. AP keeps the system responsive and tolerant of network faults. | CP can reject requests and create outages for minority partitions. AP can return stale data and produce conflicts that must be reconciled. |
Real World
| System | How it's used |
|---|---|
| Google Spanner | Spanner defaults to CP with external consistency using TrueTime and Paxos groups. During a partition it favors consistency; transactions on the minority side block or fail. |
| Amazon DynamoDB | DynamoDB is designed to be AP by default. Writes succeed on replicated nodes and reads may be eventually consistent. It optionally supports strongly consistent reads and ACID transactions for CP workloads. |
| etcd | etcd is CP. It uses Raft to maintain a consistent log across members. If the leader is isolated, followers that cannot see a majority stop accepting writes until a new leader is elected. |
| Cassandra | Cassandra is configurable AP. Writes can succeed on any replica and reads use tunable consistency. During partitions, clients choose between availability and stronger guarantees per request. |
Interview
Questions interviewers ask
- What does CAP theorem state, and what is the real choice it forces?
- Can a system be both consistent and available? When does CAP matter?
- What is split brain and how do you prevent it?
- Name a CP system, an AP system, and why each made that choice.
What a strong answer covers
Candidate should define C, A, and P; explain that partition tolerance is mandatory in practice; describe CP versus AP behavior with concrete systems; and mention split brain and quorums.
Common traps
- Saying a system is 'CA' without explaining what happens during a partition.
- Treating CAP as a simple triangle where you discard one property forever.
- Confusing consistency in CAP with consistency in ACID.
- Forgetting that CAP only constrains behavior during partitions, not steady state.
Quiz
According to CAP theorem, what happens to a distributed system during a network partition?
- It must choose between consistency and availability
- It must choose between reads and writes
- It automatically becomes consistent and available
- It stops operating entirely
During a partition, CAP says a shared-data system must trade off consistency against availability; partition tolerance is not optional in real distributed systems.
Which property in CAP is considered effectively mandatory for real distributed systems?
- Partition Tolerance
- Availability
- Consistency
- Durability
Because networks can partition, any realistic distributed system must tolerate partitions. The practical tradeoff is therefore CP or AP.
A CP system under network partition will most likely:
- Reject or block writes on the minority side
- Accept all writes everywhere and reconcile later
- Switch to a single-node mode
- Delete conflicting data
CP systems preserve consistency by refusing operations that cannot be safely coordinated, which often makes the minority partition unavailable.
What is 'split brain' in a distributed system?
- Two partitions each believe they are authoritative and accept independent writes
- A single node fails silently
- All replicas agree too quickly
- A read returns the latest write immediately
Split brain occurs when disconnected partitions each act as the leader or primary, producing divergent writes that must later be reconciled.
Which statement about CAP is most accurate?
- It constrains behavior during network partitions, not the entire lifetime of a system
- A system must choose CP or AP when it is first built and cannot change
- It only applies to databases, not to other distributed services
- It guarantees that a system can be both consistent and available if it sacrifices partition tolerance
CAP applies during partitions. Many systems are consistent and available in steady state and switch behavior only when the network fails.
AP Systems
Availability and Partition-tolerant systems prioritizing availability
Intuition
Users expect services to work even when networks are flaky. A messaging app should let you send texts from a subway tunnel, and a shopping cart should survive a region-wide outage. AP systems accept writes locally and propagate them later, accepting temporary inconsistency that must be resolved. AP systems dominate large-scale consumer applications because availability and low latency directly impact trust and revenue. Designing them means learning how to gossip state, repair divergence, and merge concurrent updates.
Mental Model
An AP system treats each reachable replica as an independent source of truth. Writes succeed if any replica can accept them; reads return the local value. Replicas exchange updates through gossip, hinted handoff, or anti-entropy, and conflicts are resolved with timestamps, vector clocks, CRDTs, or application logic. Think of it like: A team edits a shared document while offline on airplanes. Each person works on their own copy; when they land and reconnect, the tool merges changes and flags conflicts. The team stayed productive the whole flight.
Building Blocks
- Eventual Consistency: A guarantee that all replicas will converge to the same value if no new updates are made. The system stays available even when replicas diverge.
- Gossip Protocol: A peer-to-peer dissemination mechanism where nodes periodically exchange state summaries with random neighbors. Gossip scales well and tolerates failures.
- Hinted Handoff: When a replica is temporarily down, a coordinating node stores a hint and replays the write once the replica recovers, reducing data loss without blocking.
- Anti-Entropy: Background processes that compare replicas and repair differences. Merkle trees are often used to efficiently find divergent key ranges.
Definitions
- AP System
-
A distributed system that favors availability over strong consistency during a network partition.
- AP systems accept reads and writes on any reachable replica.
- They reconcile divergent replicas after the partition heals.
- Examples include Cassandra, DynamoDB, Riak, and Couchbase.
- Gossip Protocol
-
A decentralized communication pattern in which nodes randomly exchange information with peers to propagate state.
- Gossip is robust because it does not require a central coordinator.
- It scales logarithmically with cluster size.
- Used in Cassandra, Consul, and distributed hash tables.
- Anti-Entropy
-
The process of detecting and repairing inconsistencies between replicas in the background.
- Merkle trees let nodes compare large datasets efficiently.
- Repair can be proactive or triggered by read repair.
- Essential for long-lived AP deployments.
Bonus Points
- Conflict Resolution: Rules that decide the winner when replicas hold divergent versions, including last-write-wins, vector clocks, CRDTs, and application merges.
- Read Repair: Reconciliation triggered by a read that discovers stale replicas, prompting repair in the foreground or background.
- Vector Clocks: A tuple of per-replica counters used to establish partial ordering of events and detect concurrent updates.
- CRDT: A Conflict-Free Replicated Data Type whose operations merge consistently so replicas converge without coordination.
- Last-Write-Wins (LWW): A simple conflict-resolution strategy that keeps the update with the latest timestamp; easy but can discard valid updates.
Patterns
- Dynamo-Style Replication — When you need high write availability, horizontal scalability, and can tolerate eventual consistency.
- Gossip-Based Membership — When nodes frequently join, leave, or fail and you need a scalable failure detector.
- Hinted Handoff with Read Repair — When transient replica failures are common and you want to minimize permanent data loss.
- Multi-Region Active-Active — When users are globally distributed and each region must serve writes with low latency.
Strategies
- Prefer Convergence Primitives When: When the workload involves counters, sets, flags, or maps that many nodes update concurrently. How: Use CRDTs or compare-and-set with vector clocks so replicas can merge automatically without application-level conflict resolution. Example: A video platform uses a G-Counter CRDT to track global view counts that many edge nodes increment.
- Design Idempotent and Associative Updates When: When messages may be delivered multiple times or out of order. How: Make operations safe to retry. Use idempotency keys for user actions and commutative data types for aggregates. Example: A distributed analytics pipeline counts events using idempotent increment operations so replaying a log segment does not corrupt totals.
- Run Periodic Anti-Entropy Jobs When: When relying on AP storage for durable data. How: Schedule repair scans that compare checksums or Merkle trees across replicas and stream missing updates. Monitor repair lag and tombstone age. Example: Cassandra operators run 'nodetool repair' regularly to ensure deleted records propagate before tombstones expire.
- Expose and Monitor Divergence When: When eventual consistency could cause user-visible anomalies. How: Track metrics for read repair rate, hinted handoff backlog, repair time, and conflict count. Alert when divergence exceeds a threshold. Example: An e-commerce cache alerts if the rate of version conflicts between checkout replicas rises above a baseline.
AP Systems Shift Complexity to the Application
AP systems promise availability but move correctness work into the application because replicas can diverge. A common mistake is treating an AP store like a single SQL database and then being surprised by duplicate writes, lost deletes, or stale reads. Success requires observability of repair lag, data models built around commutativity, and explicit conflict-resolution rules defined before partitions happen.
Tradeoffs
| Decision | Upside | Downside |
|---|---|---|
| Availability vs Immediate Consistency | AP systems remain writable and readable during partitions and offer low local latency. CP systems avoid stale data and conflicts. | AP systems can return stale values and require conflict resolution. CP systems can become unavailable when quorum is lost. |
| Read Repair vs Background Anti-Entropy | Read repair fixes inconsistencies at access time. Background anti-entropy avoids read latency spikes and catches cold data. | Read repair can slow hot reads. Background repair consumes bandwidth and may lag behind writes. |
Real World
| System | How it's used |
|---|---|
| Apache Cassandra | Cassandra uses gossip for membership, hinted handoff for transient failures, read repair, and Merkle-tree repair. It is highly available and tunably consistent across commodity hardware. |
| Amazon DynamoDB | DynamoDB inherited the Dynamo architecture: data is partitioned and replicated, writes succeed on available nodes, and replicas converge through gossip and anti-entropy. |
| Figma | Figma uses CRDTs in the browser and server so multiple designers can edit the same file concurrently, even while offline, without losing work. |
| Domain Name System | DNS is the original AP system. Updates propagate with TTL-based caching; resolvers serve possibly stale records rather than fail, prioritizing availability over immediate consistency. |
Interview
Questions interviewers ask
- What is an AP system and when would you choose one?
- How does gossip protocol work in distributed databases?
- Explain hinted handoff and anti-entropy.
- How do you resolve conflicts in an eventually consistent store?
What a strong answer covers
Candidate should define AP behavior, explain eventual consistency, describe gossip, hinted handoff, and anti-entropy, give examples like Cassandra or DynamoDB, and discuss at least one conflict-resolution technique.
Common traps
- Claiming AP systems never lose data.
- Ignoring the need for conflict resolution.
- Confusing AP with 'no consistency at all'.
- Forgetting that read repair and anti-entropy are necessary for eventual convergence.
Quiz
An AP system is best characterized by which priority?
- Availability over strong consistency during partitions
- Strong consistency over availability
- Single-leader serialization
- Centralized locking
AP systems keep serving requests during partitions and reconcile divergent replicas afterward.
Hinted handoff is used to:
- Store writes temporarily for an unavailable replica and replay them later
- Encrypt data between replicas
- Elect a new leader automatically
- Compress the replicated log
When a replica is down, a coordinator stores a hint and forwards it once the replica recovers, improving durability without blocking.
Which process compares replicas and repairs differences in the background?
- Anti-entropy
- Consensus
- Leader election
- Two-phase commit
Anti-entropy processes compare replicas and copy missing or divergent data so the system converges.
Gossip protocols are especially useful because they:
- Do not require a central coordinator and tolerate failures well
- Guarantee strong consistency on every read
- Prevent all network partitions
- Encrypt data at rest
Nodes randomly exchange information with peers, so gossip scales and survives individual failures.
Anti-entropy in an AP store refers to:
- Background reconciliation that repairs differences between replicas
- A technique for cooling data centers
- A leader election algorithm
- A cache eviction policy
Anti-entropy processes compare replicas and copy missing or divergent data so the system converges.
CP Systems
Consistency and Partition-tolerant systems prioritizing consistency
Intuition
Some data is too valuable to be wrong. A bank cannot credit the same withdrawal twice, and a scheduler cannot let two controllers believe they own the same pod. CP systems coordinate every change through a majority or a single authoritative leader, and stop accepting writes when coordination is impossible. CP systems back configuration stores, financial ledgers, metadata services, and resource schedulers. They trade availability for correctness, which is the right choice when the cost of inconsistency exceeds the cost of a brief outage.
Mental Model
A CP system behaves like a single logical copy of the data. Every write is ordered and acknowledged by enough replicas that a conflicting write cannot succeed elsewhere. If a node loses contact with the majority, it steps down or refuses writes until it rejoins. Think of it like: A parliamentary vote requires a quorum to pass laws. If too many members are stranded by a snowstorm, the chamber pauses legislation rather than let a small group pass laws that contradict the majority.
Building Blocks
- Consensus: The problem of getting multiple nodes to agree on a single value or log of operations. Paxos and Raft are the best-known solutions and are the foundation of CP replication.
- Leader Election: The process of choosing one node to coordinate writes. Only the leader accepts mutations; followers replicate its log to prevent concurrent conflicting writes.
- Quorum: A majority or supermajority of nodes whose agreement is required for an operation to commit. Quorums guarantee that any two successful operations overlap on at least one node.
- Replicated Log: An ordered, append-only record of commands shared across replicas. If all replicas apply the same log in order, they remain consistent.
Definitions
- CP System
-
A distributed system that prefers consistency over availability during a network partition.
- CP systems block or fail writes that cannot be safely coordinated.
- They rely on consensus, leader election, or majority quorums.
- Examples include etcd, ZooKeeper, and Spanner.
- Consensus
-
The process by which distributed nodes agree on a single value or sequence of values despite failures.
- Paxos and Raft are the most well-known consensus algorithms.
- Consensus requires a majority quorum to tolerate minority partitions.
- It is more expensive than simple replication but prevents divergence.
- Quorum
-
A minimum set of replicas that must participate in an operation for it to be valid.
- A majority quorum is the most common choice because any two majorities overlap.
- Quorums provide safety but reduce availability for minority partitions.
- Used in Raft, Paxos, and many distributed databases.
Bonus Points
- Minority Unavailability: When a node or partition cannot reach a quorum, it stops accepting writes to preserve safety.
- Failover: Promoting a new leader or primary when the current one fails; correct failover requires consensus to avoid split brain.
- Two-Phase Commit (2PC): An atomic commit protocol where a coordinator asks participants to prepare, then commits only if all vote yes.
- Fencing Tokens: Monotonic identifiers issued by a leader that lock holders must present, preventing stale leaders from interfering after failover.
- Raft/Paxos: Raft is a strong-leader consensus algorithm used by etcd and Consul; Paxos is a family of consensus algorithms used by Chubby and ZooKeeper's Zab.
- Synchronous Replication: Every write is durably replicated before the application proceeds, trading latency for durability and consistency.
Patterns
- Replicated State Machine with Consensus — When the system must maintain a single ordered history of state changes and survive leader failures.
- Majority-Quorum Leader Election — When you need a single coordinator but cannot tolerate split brain.
Strategies
- Keep CP Data Small and Stable When: When building a coordination or metadata service. How: Store only configuration, locks, service locations, and small metadata in CP systems. Offload large payloads to AP stores to keep consensus fast. Example: Kubernetes keeps pod specs and node status in etcd but stores container logs and metrics in separate scalable backends.
- Size Clusters for Fault Tolerance, Not Performance When: When choosing the number of nodes in a consensus cluster. How: Use odd numbers so a clear majority exists. Three nodes tolerate one failure; five tolerate two. More nodes increase election and replication latency. Example: A ZooKeeper ensemble of five members can lose two and still elect a leader, but seven members would slow normal writes.
- Use Timeouts and Leases to Bound Failover When: When a failed leader must be detected and replaced quickly. How: Set heartbeat and election timeouts based on measured network latency. Use leader leases so stale leaders cannot commit new writes. Example: etcd defaults tune heartbeats for LAN; multi-region deployments must increase timeouts to avoid spurious failovers.
Why Consensus Keeps CP Systems Safe
Consensus works because majorities overlap: if every operation must be acknowledged by more than half the nodes, any two successful operations share at least one replica. That overlap guarantees a single ordered history and prevents two conflicting values from being accepted. The cost is latency bounded by the slowest majority member and unavailability for minority partitions, which is why CP systems are usually reserved for small, stable metadata and coordination data.
Tradeoffs
| Decision | Upside | Downside |
|---|---|---|
| Consistency vs Write Availability | Strong consistency prevents split brain, stale reads, and duplicate processing. High availability keeps the system writable during partitions. | CP systems reject writes when a quorum is unreachable. AP systems accept writes but may produce conflicts that are expensive to reconcile. |
| Synchronous vs Asynchronous Replication | Synchronous replication guarantees durability and consistency. Asynchronous replication improves latency and throughput. | Synchronous replication is blocked by the slowest replica. Asynchronous replication can lose acknowledged writes on failover. |
Real World
| System | How it's used |
|---|---|
| etcd | etcd is a CP key-value store built on Raft. Kubernetes stores all cluster state in etcd and relies on its consistency guarantees to coordinate scheduler and controller decisions. |
| ZooKeeper | ZooKeeper uses Zab to maintain a consistent replicated log. It provides locks, configuration, and leader election for systems like Kafka and Hadoop. |
| Google Spanner | Spanner uses Paxos groups per data shard and TrueTime for external consistency. It is CP: writes require a quorum and block if a majority is unreachable. |
| MongoDB with Write Concern Majority | When configured with majority write concern, MongoDB acknowledges a write only after a quorum of data-bearing members have applied it, providing CP-like behavior. |
Interview
Questions interviewers ask
- What is a CP system and when would you use one?
- Explain how Raft or Paxos works at a high level.
- What is a quorum and why does it prevent split brain?
- Why does Kubernetes use etcd?
What a strong answer covers
Candidate should define CP behavior, explain leader election and quorums, sketch how Raft or Paxos uses a replicated log, and give concrete examples such as etcd, ZooKeeper, or Spanner.
Common traps
- Saying CP systems are always better than AP systems.
- Confusing consensus with two-phase commit.
- Ignoring that CP systems become unavailable for minority partitions.
- Claiming that a CP system never loses data.
Quiz
In a CP system, what happens when a node cannot reach a quorum?
- It typically stops accepting writes to preserve consistency
- It accepts writes and reconciles later
- It automatically becomes the new leader
- It deletes all local data
CP systems prefer consistency over availability, so minority partitions usually reject writes until they rejoin the majority.
What is the primary purpose of a quorum in consensus protocols?
- To guarantee that any two successful operations overlap on at least one node
- To maximize write throughput
- To replace the need for a leader
- To encrypt data in transit
Quorum overlap ensures that a conflicting value cannot be accepted by a disjoint set of nodes, preserving a single history.
Raft and Paxos are primarily designed to solve which problem?
- Consensus among distributed nodes
- Load balancing across web servers
- Database query optimization
- Image compression
Both Raft and Paxos are consensus algorithms that let distributed nodes agree on a value or ordered log despite failures.
Which of these is the defining cost of a CP system during a network partition?
- The minority partition becomes unavailable for writes
- All replicas diverge and must reconcile later
- Reads return arbitrarily stale data
- The system automatically promotes multiple leaders
CP systems preserve consistency by refusing writes that lack a quorum, so the minority partition cannot accept updates.
A fencing token is used to:
- Prevent a stale leader or delayed process from performing unsafe writes
- Encrypt network traffic
- Balance read traffic
- Compress the replicated log
Fencing tokens are monotonic identifiers that a new leader issues; older tokens held by a former leader are rejected.
Practice consistency & cap theorem in PRISM
Concepts stick when you watch them fail. Build an architecture that depends on consistency & cap theorem, push traffic through it in the PRISM simulator, and see the latency and error rates change as you adjust the design.