Consistency Models

Building Blocks

• Linearizability: Every operation appears to execute atomically at a single point in time between its invocation and response.
• Consensus: Protocols like Raft or Paxos let replicas agree on a single ordered log even when nodes fail.
• Quorum: Requiring a majority of replicas to accept a write bounds the chance of conflicting accepted values.
• Leader/Follower Replication: A single leader serializes writes; followers acknowledge before the write is committed.
• Fencing Tokens: Monotonic tokens that prevent a displaced leader from committing stale writes after a failover.

Definitions

Strong Consistency

Any successful read returns the value of the most recent successful write; all observers see the same ordered history.

• Also called linearizability in its strictest form.
• Requires coordination, which adds latency and reduces availability under partitions.
• Common for financial, inventory, and identity data.

Consensus

The process by which distributed nodes agree on a single value or log entry despite crashes and network failures.

• Raft and Paxos are the most widely taught algorithms.
• Consensus is the foundation of strongly consistent replicated state machines.
• It can only tolerate a minority of faulty nodes.

Quorum

A minimum number of replicas that must participate in an operation for it to be considered successful.

• A typical quorum requires more than half of N replicas.
• If R + W > N, a read and a write must overlap on at least one replica.
• Quorums let systems tune consistency without being fully CP.

Bonus Points

• Serializability is about transaction ordering; linearizability is about single-operation real-time ordering.
• Synchronous replication waits for follower acknowledgments; asynchronous replication can lose data on failover.
• TrueTime and GPS clocks let systems like Spanner offer external consistency without blocking globally.
• Fencing tokens prevent 'zombie leaders' from corrupting data after a failover.

Patterns

• Leader-Based Replication — When writes must be ordered and every replica must see the same sequence.
• Quorum Reads and Writes — When you want tunable consistency without a single leader.
• Distributed Locks with Fencing — When a leader lease is used to coordinate exclusive access to a resource.

Strategies

• Use Strong Consistency Only When Necessary When: Before choosing a storage layer. How: Classify operations by the real cost of staleness. Apply strong guarantees only to the smallest set of operations that need them. Example: A payment service uses strong consistency for ledger entries but eventual consistency for notification preferences.
• Shard the Leader When: When a single leader becomes a throughput bottleneck. How: Partition data so each shard has its own leader. Writes for different keys proceed in parallel. Example: Spanner splits data into Paxos groups; each group has its own leader and replication quorum.
• Bound Retry Timeouts When: When coordination can stall under network partitions. How: Define fail-fast behavior so clients receive a clear error instead of an unbounded wait. Example: etcd returns an error when a request cannot reach a majority rather than hanging indefinitely.

Tradeoffs

Real World

Quiz

What is the defining property of strong consistency?

1. Every read returns the most recent successful write
2. Reads may return stale data temporarily
3. Replicas converge only when no new writes occur
4. The system never replicates data

Strong consistency guarantees that any successful read observes the value of the most recent successful write.

Which mechanism helps prevent a displaced leader from writing stale data?

1. Fencing token
2. Read repair
3. Gossip protocol
4. Last-write-wins

Fencing tokens are monotonic values given to a leaseholder; a node with an older token is rejected.

A quorum typically requires at least how many replicas to accept a write?

1. A majority of replicas
2. Exactly half of replicas
3. Only the leader
4. All but one replica

A majority quorum ensures that any two quorums overlap, preventing divergent accepted values.

What is the main tradeoff of strong consistency under a network partition?

1. It may sacrifice availability to preserve correctness
2. It returns stale data to stay available
3. It ignores writes on the majority side
4. It increases write throughput

Strongly consistent systems often block or reject operations that cannot be safely coordinated, reducing availability.

Linearizability differs from serializability because it defines ordering in terms of:

1. Real-time between individual operation invocation and response
2. Transactions only
3. The order in which clients connect
4. Network packet size

Linearizability places every operation at a point in real time between its invocation and response, whereas serializability concerns transaction equivalence.

Building Blocks

• Anti-Entropy: A background process that compares replicas and copies missing updates so they converge.
• Version Vectors: Metadata that tracks which replicas have seen which writes, helping detect concurrent updates.
• Conflict Resolution: Rules or data structures that decide the final value when multiple versions exist.
• Replication Lag: The delay between a write on one replica and its visibility on all other replicas.
• Gossip Protocols: Peer-to-peer dissemination that propagates updates without central coordination.

Definitions

Eventual Consistency

If no new updates are made, eventually all replicas will return the last updated value.

• Reads may be stale for a bounded or unbounded time.
• The system must provide a convergence mechanism.
• Common in geo-distributed and highly available stores.

Anti-Entropy

A background mechanism that reconciles differences between replicas to keep them converging.

• Often implemented with Merkle trees for efficient comparison.
• Runs continuously or on a schedule.
• Complements read repair for stale replicas.

Conflict Resolution

The process of deciding the final value when concurrent writes produce divergent versions.

• Strategies include last-write-wins, application merge, and CRDTs.
• Wall-clock timestamps are unreliable for ordering concurrent events.
• CRDTs guarantee convergence without coordination.

Bonus Points

• Last-write-wins can silently discard updates when clocks skew or versions are concurrent.
• CRDTs are data structures that guarantee convergence without coordination.
• Read repair updates stale replicas when a client detects a mismatch during a read.
• Hinted handoff stores writes for unreachable replicas until they come back online.
• Dynamo and Cassandra made eventual consistency mainstream in large-scale systems.

Patterns

• Multi-Master Replication — When you need to accept writes in multiple regions and reconcile later.
• Read Repair — When you want to fix stale replicas on demand rather than waiting for background anti-entropy.
• Versioned Values — When clients need to detect and merge concurrent updates themselves.

Strategies

• Accept Staleness in the UX When: When the product can tolerate a small delay before showing the latest data. How: Show timestamps, 'just now' labels, or refresh indicators instead of pretending data is fresh. Example: A social feed shows a new post to the author immediately and propagates it to followers over seconds.
• Resolve Conflicts Deterministically When: Before replicas are allowed to diverge. How: Define rules such as user wins, last timestamp, or a merge function, and apply them consistently. Example: A shopping cart merges item additions but treats concurrent removals as explicit user actions.
• Choose Consistency Per Operation When: When only some operations need strong guarantees. How: Use strongly consistent reads or writes only for critical checks; keep the rest eventual. Example: DynamoDB defaults to eventual reads but offers strongly consistent reads for an extra round trip.

Tradeoffs

Real World

Quiz

What does eventual consistency guarantee?

1. If writes stop, all replicas eventually return the last value
2. Every read returns the latest write immediately
3. Replicas never diverge
4. Conflicts never occur

Eventual consistency promises convergence when no new writes occur; temporary divergence is allowed.

Which mechanism reconciles replicas in the background?

1. Anti-entropy
2. Fencing token
3. Two-phase commit
4. Sticky session

Anti-entropy is a background process that detects and repairs differences between replicas.

What is a common risk of last-write-wins conflict resolution?

1. It can silently discard concurrent updates
2. It requires a central leader
3. It guarantees strong consistency
4. It prevents replication lag

Clock skew and concurrent writes can cause last-write-wins to drop valid updates.

CRDTs are useful because they:

1. Guarantee convergence without coordination
2. Require a single leader
3. Provide linearizability
4. Eliminate replication lag

Conflict-free Replicated Data Types merge deterministically without requiring nodes to coordinate.

Which system is a classic example of eventual consistency?

1. DNS
2. etcd
3. ZooKeeper
4. Spanner

DNS propagation is a well-known eventually consistent system where cached records update slowly.

Building Blocks

• Cache: A fast, best-effort copy of data with its own TTL and invalidation policy.
• Best-Effort Delivery: Messages may be dropped or reordered without retry, prioritizing speed over reliability.
• Approximate Data Structures: Structures like HyperLogLog or Count-Min Sketch trade exactness for massive speed and space savings.
• TTL: Time-to-live expiry lets the system refresh values periodically instead of tracking every change.

Definitions

Weak Consistency

A consistency model that does not guarantee a read will see the most recent write.

• Often used for caches, analytics, and approximate metrics.
• No convergence guarantee by itself.
• The weakest but fastest consistency model.

Cache Coherency

The challenge of keeping cached copies consistent with the source of truth.

• Invalidation strategies include TTL, write-through, and write-behind.
• Cache misses and stale hits are normal.
• Coherency is usually relaxed for performance.

Best-Effort Delivery

A message delivery guarantee where the system does not retry lost messages.

• Common in metrics and logging pipelines.
• Reduces backpressure and latency.
• Accepts a small loss rate for scalability.

Bonus Points

• Monotonic reads and bounded staleness are stronger cousins of weak consistency.
• Cache invalidation is famously difficult because it requires tracking every change.
• CDN edge caches are weakly consistent by design to serve content quickly.
• Analytics counters often accept approximate counts for speed.

Patterns

• Cache-Aside — When the application can tolerate stale or missing cache entries.
• Fire-and-Forget Metrics — When high-volume counters can tolerate minor loss.
• CDN Edge Caching — When static assets need to be served close to users with minimal latency.

Strategies

• Use Weak Consistency for Non-Critical Data When: When exactness is not required for correctness. How: Route analytics, recommendations, and counts through weakly consistent layers. Example: A dashboard shows approximate active users instead of querying the authoritative transaction database.
• Pair with TTL When: When you want to bound how stale a value can become. How: Set an expiry so the cache refreshes periodically even without explicit invalidation. Example: A news feed cache refreshes every minute, so stale data is at most 60 seconds old.
• Never Use Weak Consistency for Authoritative State When: When correctness is required. How: Always read balances, inventory, and ownership from the source of truth. Example: A payment service bypasses the cache and reads the ledger directly during a transfer.

Tradeoffs

Real World

Quiz

What is the main guarantee of weak consistency?

1. No formal guarantee that reads see recent writes
2. All replicas converge when writes stop
3. Every read returns the latest write
4. Reads always see at least one previous write

Weak consistency does not promise that a read will reflect any particular previous write.

Which component is a classic example of weak consistency?

1. An in-memory cache
2. A transactional database
3. A consensus log
4. A synchronous replica

Caches are intentionally weakly consistent to maximize speed and reduce load.

Why is cache invalidation considered difficult?

1. It requires tracking every change to the source of truth
2. It guarantees strong consistency
3. It prevents all stale reads
4. It eliminates the need for TTLs

Keeping every cache copy synchronized with the source of truth is complex at scale.

Bounded staleness improves weak consistency by:

1. Limiting how old a returned value can be
2. Guaranteeing every read sees the latest write
3. Removing the need for a cache
4. Making replicas converge instantly

Bounded staleness caps the age of data, giving a partial guarantee without full coordination.

Which use case is least suitable for weak consistency?

1. Bank account balance
2. Real-time analytics counter
3. CDN asset cache
4. Recommendation score

Bank account balances require strong correctness guarantees and should not rely on weak consistency.

Building Blocks

• Happens-Before: A partial order where event A influences event B; B must be observed after A.
• Vector Clocks: Compact metadata that captures which events a node has seen, used to detect causality and concurrency.
• Causal Broadcast: A messaging primitive that delivers causally related messages in order across replicas.
• Session Token: A token attached to a client session that routes reads to replicas containing the session's writes.
• Read-Your-Writes: A session guarantee that a client always sees its own updates.

Definitions

Causal Consistency

A model that preserves the happens-before relationship between operations; causally unrelated operations may be observed in different orders.

• Stronger than eventual consistency but weaker than linearizability.
• Can remain available during network partitions.
• Natural fit for social, messaging, and collaborative systems.

Session Consistency

Guarantees that apply to a single client's session, such as read-your-writes and monotonic reads.

• Often implemented with sticky routing or client-side tokens.
• Improves user experience without global coordination.
• Can be layered on top of eventual or causal consistency.

Read-Your-Writes

A client never reads a value older than one it previously wrote during the same session.

• Implemented by routing reads to replicas that have seen the session's writes.
• Common in comment systems and user profiles.
• Does not guarantee other clients see the write immediately.

Monotonic Reads

A client never sees an older value after having seen a newer one in the same session.

• Prevents time-travel effects where a user sees stale data after seeing fresh data.
• Requires session affinity or version tracking.
• A building block of session consistency.

Bonus Points

• Causal consistency is the strongest consistency model that remains available during network partitions.
• Vector clocks grow with the number of replicas; version vectors are a refinement for clients.
• Lamport timestamps capture a single partial order but cannot detect concurrency.
• Many databases offer session consistency via sticky routing or client-side tokens.

Patterns

• Sticky Sessions — When a user's reads should follow their own writes.
• Version Vectors — When replicas need to detect causally concurrent updates.
• Causal Broadcast — When message delivery order must respect causal relationships.

Strategies

• Use Sticky Routing for User Sessions When: When read-your-writes is required. How: Route a user to the same replica where they wrote so subsequent reads see the update. Example: A messaging service pins a user to a regional replica for a few seconds after they send a message.
• Track Causality with Vector Clocks When: When concurrent writes must be detected and merged safely. How: Attach vector-clock metadata to each value; replicas compare clocks to decide ordering or conflict. Example: A distributed key-value store uses version vectors to surface concurrent writes to the application.
• Defer Global Ordering When: When causal order is sufficient for correctness. How: Use cross-shard transactions or consensus only for operations that truly need a total order. Example: A social feed orders a user's own actions causally but does not globally order unrelated users' posts.

Tradeoffs

Real World

Quiz

What relationship does causal consistency preserve?

1. Happens-before between related operations
2. Total global order of all operations
3. Immediate visibility of every write
4. No ordering at all

Causal consistency ensures that if one operation influences another, observers see the first before the second.

Read-your-writes is an example of:

1. Session consistency
2. Eventual consistency
3. Linearizability
4. Weak consistency

Read-your-writes is a guarantee provided to a single client's session.

Which data structure is commonly used to track causal relationships?

1. Vector clock
2. Bloom filter
3. B-tree
4. Priority queue

Vector clocks capture which events a node has seen, making causal ordering detectable.

A key advantage of causal consistency over linearizability is:

1. It can remain available during network partitions
2. It provides a total global order
3. It never requires metadata
4. It guarantees every read sees the latest write

Causal consistency is the strongest model known to remain available under partitions.

Sticky sessions help implement session consistency by:

1. Routing a user's reads to replicas that have seen their writes
2. Blocking all writes during partitions
3. Requiring a global consensus for every read
4. Disabling caching entirely

Sticky routing ensures a client reads from a replica that has already processed its writes.