SD7.2 · LESSON 2 OF 6

Consistency models

Compare consistency contracts and distribute data while tracing stale reads, partitions and hot keys.

THE IDEA

Consistency models

Linearizability says each operation on an object appears to take effect at one instant between its start and its end, in an order that respects real time: once a write has finished, every later read must see it. Serializability is about transactions: the result must equal some one-at-a-time order, with no real-time requirement. They are related but different properties, and a system can offer one without the other.

register starts at 0 is there an order consistent with real time in which every read returns the latest write? YES: linearizable write, then read: fine

Linearizability is about operations on one object appearing to take effect in an order that respects real time. Serializability is about whole transactions behaving as if run one at a time. They are related but not the same property.

Check four small histories of a register that starts at 0.

Predict first. Are serializable and linearizable interchangeable words?

Chapter context

Replication copies data for resilience or read capacity; partitioning assigns different data to different owners. Both introduce coordination and failure behavior that an application must explicitly account for.

TRY IT YOURSELF

Part 1. Do it hands-on

Judge three histories by hand, then write a small linearizability checker.

register starts at 0 is there an order consistent with real time in which every read returns the latest write? YES: linearizable write, then read: fine

history A linearizable? (yes/no) history B history C serializable = linearizable? (yes/no)

To do: A register starts at 0. History A: write(1) during [0,1]; later a read during [2,3] returns 1. Linearizable? Type yes or no
To do: History B: write(1) during [0,1]; a read during [2,3] (after the write finished) returns 0. Linearizable?
To do: History C: write(1) during [0,10]; a read during [2,3] returns 0 and a later read during [4,5] returns 1. Linearizable?
To do: Are serializable and linearizable interchangeable words? Type yes or no

Part 2. Do it in code

An operation is {"op": "w" or "r", "value": v, "start": t0, "end": t1}: a write of v, or a read that returned v. A single register starts at 0.
precedes(a, b): True if a finished before b started (a['end'] < b['start']).
valid_order(history, order): order is a permutation of indexes. It is a legal linearization if (1) whenever a precedes b in real time, a appears before b, and (2) replaying the order, every read returns the register's current value (the value of the most recent write, or 0).
linearizable(history): True if SOME permutation is a legal linearization (try all permutations; histories are small).
stale_reads(history): the number of reads that start after a write has finished but return a value different from the latest finished write's value (a quick sign of non-linearizability; ignore histories with several concurrent writes).

import itertools

def precedes(a, b):
    pass

def valid_order(history, order):
    pass

def linearizable(history):
    pass

def stale_reads(history):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Are serializable and linearizable interchangeable words?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For fixed sets over N replicas, $|R\cap W|\ge |R|+|W|-N$ . Thus R=W=3 with N=5 forces at least one shared member. This is a set fact, not a complete consistency proof. Shard and replication counts describe different dimensions of the layout.

Worked example

Five replicas use read sets and write sets of size three. The lower bound on overlap is 3+3−5=1. Enumerating all three-member sets confirms every pair overlaps. A read still needs the right version-selection and concurrency rules; intersection alone does not tell which stored value is newest or committed.

Reference code

The following example uses the Python standard library and does not call a remote service.

from itertools import combinations
replicas=set(range(5))
sets=[set(x) for x in combinations(replicas,3)]
assert min(len(r&w) for r in sets for w in sets) == 1
assert 3+3-5 == 1
assert all(r&w for r in sets for w in sets)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Quorum arithmetic does not establish a full consistency contract. Sharding is not replication. CAP availability is a precise failure-model property, not the same as an ordinary monthly uptime percentage.