Documentation Index
Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
Use this file to discover all available pages before exploring further.
Consistency Models
Understanding consistency models is fundamental to designing distributed systems. This module covers the entire consistency spectrum, from the strongest (linearizability) to the weakest (eventual consistency). Here is the single most useful analogy for this entire chapter: think of consistency models as a spectrum of “how much does this system behave like a single computer?” Linearizability means “exactly like a single computer” — every operation appears atomic and instantaneous to every observer. Eventual consistency means “it will eventually act like a single computer, but right now different observers may see different states.” Everything in between is a carefully negotiated trade-off between how real the illusion of a single computer is and how fast and available you need the system to be.Module Duration: 12-16 hours
Key Topics: Linearizability, Serializability, Causal Consistency, Eventual Consistency, Session Guarantees
Interview Focus: Trade-offs between consistency levels, real-world examples
Key Topics: Linearizability, Serializability, Causal Consistency, Eventual Consistency, Session Guarantees
Interview Focus: Trade-offs between consistency levels, real-world examples
The Consistency Spectrum
Linearizability (Strict Consistency)
Definition
Real-World Linearizable Systems
- Zookeeper
- etcd
- Google Spanner
Cost of Linearizability
Sequential Consistency
Definition and Examples
Serializability
Definition
Isolation Levels
Causal Consistency
Definition and Intuition
Eventual Consistency
Definition and Variations
Session Guarantees
8.1 Implementing Session Guarantees
In high-scale systems (like DynamoDB or Cassandra), session guarantees are often implemented using Client-Side Metadata or Version Vectors.Read Your Writes (RYW)
To ensure a client sees their own update immediately, even if the database is eventually consistent:- Write: The client performs a write and receives a Version Token (or Timestamp/LSN) in the response.
- Storage: The client stores this token in their session (e.g., a cookie or local storage).
- Read: When reading, the client sends this token. The server ensures the read replica has at least reached that version before responding. If the replica is lagging, the server can:
- Wait for the replica to catch up.
- Route the request to a fresher replica.
- Read from the Leader.
Monotonic Reads
To prevent the “Time Travel” bug (where a user sees a post, refreshes, and it’s gone because they hit a lagging replica):- The client tracks the Max Version it has seen so far.
- Every read request includes this
min_versionfilter. - The load balancer or database proxy ensures that the request only hits replicas that are at or beyond this version.
9. Advanced Theoretical Frameworks
To truly master consistency, one must look beyond simple definitions and understand the mathematical foundations.9.1 The CALM Theorem
CALM stands for Consistency As Logical Monotonicity. This theorem provides a formal boundary for the CAP theorem: it identifies exactly which programs can be consistent and available without coordination.The Fundamental Insight
Distributed consistency is hard because nodes disagree on the order and absence of events. The CALM theorem states that:Consistency can be achieved without coordination if and only if the program is logically monotonic.
Monotonic vs. Non-Monotonic Operations
| Type | Description | Examples | Coordination? |
|---|---|---|---|
| Monotonic | Adding information never invalidates previous conclusions. “More is better.” | Set union, Reachability, Maximum, Logical OR/AND | No (Coordination-free) |
| Non-Monotonic | Adding information can change a previous “True” to “False.” “Absence matters.” | Set difference, Negation (NOT), Aggregation (Count/Sum), Garbage Collection | Yes (Requires locks/consensus) |
Why Monotonicity Matters
- Order Independence: In a monotonic system, messages can arrive in any order, be delayed, or be duplicated, and the final result will be the same. This is why CRDTs (Module 15) work—they are mathematically monotonic.
- Deterministic Convergence: Multiple replicas receiving different subsets of updates will always “eventually converge” to the same state as they receive more information.
- Availability: Monotonic programs are AP (Available under Partitions) because they don’t need to ask other nodes “Do you know anything that would make my current conclusion false?”
Practical Application: Garbage Collection
Consider a distributed system where you want to delete a file.- Problem: Deletion is non-monotonic. If Node A deletes
file1, but Node B hasn’t seen the delete yet and re-replicates it,file1“resurrects.” - Solution: Use a monotonic approximation. Instead of deleting, add a “Tombstone” (a record that says ‘this is deleted’). Adding a tombstone is monotonic (you are adding info). The actual space reclamation (purging) is non-monotonic and requires coordination or a background GC process with a grace period.
9.2 Linearizability vs. Sequential Consistency (The Proof of Non-Composability)
A critical (and often asked) property of linearizability is that it is composable.- If object is linearizable and object is linearizable, then the combined system is also linearizable.
- Sequential consistency is NOT composable. You can have two sequentially consistent objects that, when used together, violate sequential consistency. This is why multi-core memory models (which are often sequentially consistent) are so difficult to reason about at scale.
9.3 Formal Verification with TLA+
How do we know a consistency model is actually implemented correctly?- TLA+ (Temporal Logic of Actions): A language for modeling concurrent systems.
- You define your system’s state and allowed transitions (actions).
- You define Safety Invariants (e.g., “no two nodes are leader in the same term”).
- The model checker explores all possible interleavings to find violations.
10. Testing Consistency in the Wild: The Jepsen Framework
Created by Kyle Kingsbury, Jepsen is the industry standard for testing distributed systems.10.1 How Jepsen Works
- Setup: Spins up a cluster of nodes (e.g., 5 nodes).
- Client: A set of clients perform operations (reads, writes, CAS) on the cluster.
- Nemesis: A special process that causes “havoc”:
- Network partitions (
iptablesdrops). - Clock skew (
ntpdatejumps). - Process crashes (
kill -9).
- Network partitions (
- Checker: After the test, Jepsen analyzes the history of operations to see if they violate the claimed consistency model (e.g., using
Knossosfor linearizability).
10.2 Famous Jepsen Findings
- MongoDB: Found that “Strong Consistency” wasn’t actually strong in many edge cases (later fixed with WiredTiger and Raft).
- Cassandra: Found that lightweight transactions (LWT) could lose data during partitions.
- Redis (Redlock): Kingsbury’s critique of Redlock showed that without fencing tokens, distributed locks are not safe under clock skew.
11. Consistency in Practice: The Decision Matrix
| Model | Coordination | Availability | Latency | Typical Use Case |
|---|---|---|---|---|
| Linearizable | High (Quorum) | Low (CP) | High | Leader Election, Locks |
| Sequential | Moderate | Low (CP) | Medium | Memory models, CPU caches |
| Causal | Low (Metadata) | High (AP) | Low | Social feeds, comments |
| Eventual | None | High (AP) | Ultra-low | Analytics, background jobs |
| SEC (CRDTs) | None | High (AP) | Low | Collaborative editing |
12. Interview Playbook: “The Deep Dive”
“When discussing consistency, I distinguish between single-object models like linearizability and multi-object models like serializability. Linearizability provides the strongest recency guarantee but at the cost of availability during partitions—a trade-off described by the CAP theorem. For high-availability systems, I look towards Causal Consistency, which is the strongest model achievable without global coordination. I also apply the CALM theorem to identify non-monotonic operations that strictly require coordination. Finally, I verify these systems using frameworks like Jepsen to ensure that under network partitions or clock skew, the safety invariants of the chosen model still hold.”
13. Key Takeaways
Consistency is a Spectrum
From linearizable (strongest) to eventual (weakest). Choose based on your requirements.
Stronger = Slower
Strong consistency requires coordination, which adds latency and reduces availability.
CAP is About Partitions
During partitions, choose consistency (reject writes) or availability (accept divergence).
Session Guarantees Help
Read-your-writes and monotonic reads provide practical consistency within a session.
14. Next Steps
Consensus Protocols
Learn Paxos, Raft, and how consensus enables strong consistency
Replication Strategies
Understand how data is replicated and conflicts resolved
Interview Deep-Dive
What is the difference between linearizability and serializability? Many candidates confuse them -- explain precisely when each applies.
What is the difference between linearizability and serializability? Many candidates confuse them -- explain precisely when each applies.
Strong Answer:
- Linearizability is a single-object, real-time guarantee. It says: every operation on a single register (or key) appears to take effect instantaneously at some point between its invocation and its response, and all observers agree on the order. It is about recency — if a write completes before a read starts, the read must see that write.
- Serializability is a multi-object, transaction-level guarantee. It says: the result of executing a set of transactions concurrently is equivalent to executing them in some serial order. Crucially, that serial order does not have to match real-time order. Serializability is the “I” in ACID (Isolation).
- The confusion arises because both involve “ordering,” but they operate at different levels. A system can be serializable but not linearizable: transactions execute as-if serial, but individual reads within a transaction might see stale data because the serial order does not respect wall-clock time. A system can be linearizable but not serializable: each individual key is strongly consistent, but multi-key transactions might see inconsistent snapshots.
- Strict serializability (or external consistency) combines both: transactions are serializable AND the serial order respects real-time. This is the strongest guarantee, provided by Google Spanner.
Explain write skew. Why is it not prevented by repeatable read isolation, and how would you prevent it in a distributed database?
Explain write skew. Why is it not prevented by repeatable read isolation, and how would you prevent it in a distributed database?
Strong Answer:
- Write skew is an anomaly where two transactions each read the same data, make independent decisions based on what they read, and then write to different objects — resulting in a state that violates a cross-object invariant. The classic example: a hospital requires at least one doctor on call. Both Dr. Alice and Dr. Bob read “2 doctors on call” and each decides it is safe to go off call. They each write their own record (different objects). Result: 0 doctors on call, violating the constraint.
- Repeatable read prevents dirty reads, non-repeatable reads, and phantom reads within the same object. But it does not prevent write skew because the two transactions read the same data but write to different rows. There is no write-write conflict that repeatable read would catch — the writes are to different keys.
- To prevent write skew in a distributed database, you need serializable isolation. There are three common approaches: (1) Actual serial execution — run one transaction at a time, which is what Redis and VoltDB do. (2) Two-phase locking (2PL) — acquire shared locks on all reads and exclusive locks on all writes, preventing concurrent access. This catches write skew because both transactions would try to acquire shared locks on the “doctors on call” query, and the conflict would be detected. (3) Serializable Snapshot Isolation (SSI), used by CockroachDB and PostgreSQL 9.1+ — optimistically execute transactions but detect dangerous read-write conflicts at commit time and abort one of the conflicting transactions.
You are designing a social media platform. Walk me through which consistency model you would choose for different features and why.
You are designing a social media platform. Walk me through which consistency model you would choose for different features and why.
Explain the CALM theorem and its practical implications for designing highly available distributed systems.
Explain the CALM theorem and its practical implications for designing highly available distributed systems.
Strong Answer:
- CALM stands for Consistency As Logical Monotonicity. It provides a formal answer to a deep question: which computations can be made both consistent and available without any coordination? The answer: exactly the monotonic ones.
- A computation is monotonic if adding new information never invalidates previous conclusions. Set union is monotonic — adding an element to a set never removes existing elements. Set difference is non-monotonic — learning about a new element could change a subtraction result. Aggregations like COUNT are non-monotonic because the count changes with every new element and you need to know about absences (has everyone reported in?).
- The practical implication is a design principle: if you can refactor your operation to be monotonic, you can implement it without coordination (no Paxos, no Raft, no distributed locks). This is exactly why CRDTs work — they are mathematically monotonic data structures. A G-Counter only grows, an OR-Set only adds (tombstones are adds, not deletes), and these structures converge without coordination.
- The design heuristic I use: when I encounter a non-monotonic operation in a high-availability system, I ask “Can I make this monotonic?” Deletion becomes “add a tombstone.” Decrement becomes “add a negative event to a PN-Counter.” COUNT becomes “each node tracks its own count, merge by summing.” If I cannot make it monotonic, I know I need coordination for that specific operation, and I can minimize the coordination scope.