Consistency Models
JEPSEN
Consistency Models
Jepsen analyzes the safety properties of distributed systems–most notably,<br>identifying violations of consistency models. But what are consistency<br>models? What phenomena do they allow? What kind of consistency does a given program really need?
In this reference guide, we provide basic definitions, intuitive explanations,<br>and theoretical underpinnings of various consistency models for engineers and<br>academics alike.
This clickable map (adapted from Bailis, Davidson, Fekete et<br>al. and Viotti and<br>Vukolic) shows the relationships between<br>common consistency models for concurrent systems. Arrows show the relationship<br>between consistency models. For instance, strict serializable implies both<br>serializability and linearizability, linearizability implies sequential<br>consistency, and so on. Colors show how available each model is, for a<br>distributed system on an asynchronous network.
This map shows consistency models arranged in a hierarchy. The strongest<br>model shown is strict serializable.<br>Strict serializable unifies two disjoint families of consistency models: those<br>over multi-object transactions, and those for single object operations. When we<br>say that model x implies y, we mean that for every history where x holds, y does<br>too; x is “stronger” than y.
On the multi-object side, strict serializable implies<br>serializable, which in turn implies<br>repeatable read and snapshot<br>isolation. Snapshot isolation (assuming<br>a generalized definition) and repeatable read both imply monotonic atomic<br>view. Repeatable read implies<br>cursor stability. Cursor stability and<br>monotonic atomic view both imply read<br>committed, which implies read<br>uncommitted.
For single-object models, strict serializable implies<br>linearizable, which implies<br>sequential, which implies<br>causal. Causal implies writes follow<br>reads and<br>PRAM. PRAM implies monotonic<br>reads, monotonic<br>writes,and read your<br>writes.
All models at or stronger than cursor stability, snapshot isolation, and<br>sequential cannot be totally available in asynchronous networks. All models<br>at or stronger than read your writes can be at most sticky available. Weaker<br>models (of those listed here) can be totally available.
Fundamental Concepts
Systems
Distributed systems are a type of concurrent system, and much of the<br>literature on concurrency control applies directly to distributed systems.<br>Indeed, most of the concepts we’re going to discuss were originally formulated<br>for single-node concurrent systems. There are, however, some important<br>differences in availability and performance.
Systems have a logical state which changes over time. For instance, a simple<br>system could be a single integer variable, with states like 0, 3, and 42.<br>A mutex has only two states: locked or unlocked. The states of a key-value<br>store might be maps of keys to values, for instance: {cat: 1, dog: 1}, or<br>{cat: 4}.
Processes
A process1 is a logically single-threaded program which performs<br>computation and runs operations. Processes are never asynchronous—we model<br>asynchronous computation via independent processes. We say “logically<br>single-threaded” to emphasize that while a process can only do one thing at a<br>time, its implementation may be spread across multiple threads, operating<br>system processes, or even physical nodes—just so long as those components<br>provide the illusion of a coherent single-threaded program.
Operations
An operation is a transition from state to state. For instance, a<br>single-variable system might have operations like read and write, which get<br>and set the value of that variable, respectively. A counter might have<br>operations like increments, decrements, and reads. For an SQL store, an<br>operation might be a transaction, composed of some number of selects,<br>update, deletes, and so on.
Functions, Arguments & Return Values
In theory, we could give every state transition a unique name. A lock has exactly two transitions: lock and unlock. An integer register has an infinite number of reads and writes: read-the-value-1, read-the-value-2, …, and write-1, write-2, ….
To make this more tractable, we break up these transitions into functions<br>like read, write, cas, increment, etc., and values that parameterize<br>those functions. In a single register system, a write of 1 could be written:
{:f :write, :value 1}
Given a key-value store, we might increment the value of key “a” by 3 like so:
{:f :increment, :value ["a" 3]}
In a transactional store, the value could be a complex transaction. Here we read the current value of a, finding 2, and set b to 3, in a single state transition:
{:f :txn, :value [[:read "a" 2] [:write "b" 3]]}
Invocation & Completion Times
Operations, in general, take time. In a multithreaded program, an operation might be a function call. In distributed systems, an operation might mean sending a request to a server, and receiving a response.
To model this, we say that each operation has an invocation time and, should<br>it complete, a strictly greater...