Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
You want your friends and colleagues to be consistent in the way they interact with you. Consistency is also a key concern when choosing a database. Consistency models define the rules by which distributed systems present data updates to clients.
They answer the question:
When I write something, when and how will others see it?
From the 1970s to today’s cloud databases, consistency trade-offs have shaped system design. This post briefly talks to common consistency patterns and why you should care.
1. Linearizability (Strong Consistency)
Operations appear to occur atomically and in real time. If one operation completes before another begins, all clients observe them in that order.
Origin: Defined by Herlihy & Wing (1990) in the context of concurrent objects.
https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
Examples:
- Google Spanner: Uses TrueTime API for globally synchronized clocks to achieve external consistency.
- PostgreSQL: Guarenteed on a single instance
- When to Use: Banking transactions, leader election, locking services.
- Trade-off: Sacrifices availability under network partitions (per CAP theorem).
2. Sequential Consistency
All operations appear in the same total order, consistent with the program order of each process, but without a real-time constraint.
Origin: Introduced by Leslie Lamport (1979) in How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs.
Difference from Linearizability: Sequential consistency allows reordering if it doesn’t violate per-process order, whilst linearizability does not.
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
Examples:
- Some Raft-based systems under relaxed clock sync.
- IBM’s early multiprocessor memory models.
When to Use: Distributed logs, replicated state machines where exact wall-clock order is less important.
3. Causal Consistency
If operation A causally affects B (e.g., B reads data from A), then all processes see A before B. Independent operations can be seen in different orders.
Origin: Ahamad et al. (1993) in Causal Memory.
Examples:
- Cassandra with QUORUM writes + read repair.
- Bayou system (1995, Xerox PARC) pioneered causal tracking.
- Amazon Dynamo (2007) influenced modern NoSQL approaches.
When to Use: Social media posts and replies, collaborative document editing.
4. PRAM / FIFO Consistency
Writes from a single process are observed in order, but no ordering guarantees across processes.
Origin: PRAM (Pipelined Random Access Machine) model in the 1980s, adapted for memory consistency.
ftp://ftp.cs.princeton.edu/techreports/1988/180.pdf
Examples:
- Early message-passing systems.
- Some log-structured key-value stores without cross-writer ordering.
When to Use: Logging, metrics pipelines, append-only feeds.
5. Monotonic Reads
Once you’ve read a value, you will never see an older value in later reads.
Examples:
- DynamoDB with strong read settings.
- Cosmos DB with monotonic read session guarantees.
When to Use: User profile pages, paginated content.
6. Monotonic Writes
Definition: Writes from a single process are applied in the order they were issued.
Examples:
- HBase region servers ensure this for client writes to a row.
- Most write-ahead log–based systems.
When to Use: Event streams, sequential data ingestion.
7. Read-Your-Writes Consistency
After writing data, a client will always read that same value (or a newer one).
Origin: Popularized in the mid-1990s in session-based web systems.
Examples:
- MongoDB with majority writes + read preference.
- Riak with read repair.
When to Use: Shopping carts, dashboards.
8. Session Consistency
A composite guarantee – typically read-your-writes + monotonic reads, but only within a session.
Examples:
- Azure Cosmos DB offers session consistency as a default option.
- AWS DynamoDB with session stickiness.
When to Use: Logged-in user workflows.
9. Bounded Staleness
Reads are guaranteed to lag writes by at most a fixed number of versions or time interval.
Origin: This paper introduces the PBS model, which quantifies how often and by how much reads may lag behind writes in quorum-replicated systems—providing both version-based (k-staleness) and time-based (t-visibility) bounds.
https://arxiv.org/pdf/1204.6082
Examples:
- Cosmos DB bounded staleness mode.
- Google Cloud Spanner read-only staleness queries.
When to Use: Analytics queries, dashboards where data freshness tolerance is known.
10. Eventual Consistency
In the absence of new updates, all replicas converge to the same value, but no guarantees about how long it takes.
Origin: Term formalized by Werner Vogels (Amazon CTO) in the mid-2000s, though used implicitly in systems like DNS since the 1980s.
https://www.allthingsdistributed.com/2007/12/eventually_consistent.html
Examples:
- Amazon Dynamo, Cassandra with consistency level ONE.
- DNS zone propagation.
When to Use: Social feeds, replicated caches, recommendation systems.
The History
Here is a non-exhaustive history of some key date in the consistency options.
- 1970s: Lamport formalizes sequential consistency for multiprocessor systems.
- 1980s: Memory consistency models diversify (PRAM, weak ordering).
- 1990s: Consensus protocols (Paxos) and causal models emerge; Bayou prototypes session and causal consistency.
- 2000s: Amazon Dynamo popularizes eventual consistency in web-scale NoSQL.
- 2010s: Cloud databases (Spanner, Cosmos DB) offer tunable and bounded staleness models.
You must be logged in to post a comment.