TL;DR Consistency is a problem when your system stores multiple copies of the same data. Consistency levels allow us to reason about the guarantees provided by a database system and what outcomes are allowed/forbidden.
A database is a system where you store data and retrieve it later. A traditional database is merely a process on a single computer and there's only a single copy of the data. In modern days, to scale up performance and achieve failure tolerance, data is replicated to multiple machines and stored as multiple copies. Each copy is called a replica. Ideally, each copy of the data is exactly the same but that's hard to achieve in practice, hence the problem of consistency. Some database systems also explicitly trade consistency for higher availability. Understanding the consistency models is helpful for reasoning about modern databases and using them correctly.
It's not very straightforward to reason about all the consistency levels. We'd like to discuss them with some concrete examples. To do that, we need to clarify the environment where the examples will come from.
In this environment,
Imagine there's no consistency guarantee, then any operation by any process can be served by any replica, which will of course cause all kinds of weird behaviors (e.g. you may not read the value you've just written).
Key definitions:
These are the consistency levels we will talk about.
In the following table, we will mention some concrete examples that are allowed or forbidden by a certain consistency level. A system meets a certain consistency level when its observable outcomes obey the constraints imposed by the consistency level. Here is the example scenario we'll use across the discussion:
# Process1: W1 W2 R1
# Process2: W3 R2 W4
# Process3: R3 R4
| Level | Example Constraints | Possible Implementation |
| No consistency | It's possible that R2→∅ | A read/write is routed to any replica with async replication. |
| Read Your Writes | It's required that R2→W1 or R2→W3 | Only read from replicas that you have written to. |
| Monotonic Writes | It's impossible to get (R3→W4 and R4→W3). | Ensure that writes of the same process are replicated to others in order. |
| Monotonic Reads | It's impossible to get (R3→non-∅ and R4→∅). | Read from the same replica all the time (sticky client) |
| PRAM |
It forbids all examples prevented by the above three consistency levels. Different processes may observe writes in different orders (while session orders are guaranteed). For example, it's possible that R2→W1, R3→W4, R4→W1. |
Read from the same replica all the time, which has to be the ones where you write your values to. Writes of one process are replicated in order (although no total order is required). |
| Writes Follow Reads |
This consistency level prunes certain sequence of writes for a certain read, but by itself doesn't prune any observable outcome. What may be interesting is that, the following outcome is possible with PRAM but not with PRAM+WFR: R2→W1, R3→W4, R4→W1 (Once R2 observes W1, W1 must be observed before W4) |
Writes need to be coupled with some metadata to establish precedence over previous writes. |
| Causal Consistency | It's impossible to get R2→W1, R3→W4, R4→W1 (same example as above). | When you read something, you get a vector timestamp, you update your timestamp before writing a new value. You'll be able to tell whether two writes are concurrent or one is causally before the other. |
| Sequential Consistency | It's impossible to get R1→W3, R2→W1 (the order of W3 and W1 is not consistent across two processes) | Use Lamport timestamp to generate a total order of events and use that total order to resolve conflicts. |
| Linearizability | It's impossible to get R3→∅ (the return-before relationship needs to be respected). |
Use a leader to serves all reads and writes while having followers to maintain fault tolerance. Note that if async replication is used and reads can be served by the follower, the system can return stale data, which violates linearizability. But sequential consistency can still be maintained in this case. |