Consistency Models

原文链接：https://jepsen.io/consistency

This clickable map (adapted from Bailis, Davidson, Fekete et al and Viotti & Vukolic) shows the relationships between common consistency models for concurrent systems. Arrows show the relationship between consistency models. For instance, strict serializable implies both serializability and linearizability, linearizability implies sequential consistency, and so on. Colors show how available each model is, for a distributed system on an asynchronous network.

这个可点击的地图（改编自 Bailis、Davidson、Fekete 等人和 Viotti & Vukolic）显示了并发系统的常见一致性模型之间的关系。 箭头显示一致性模型之间的关系。 例如，严格可串行化意味着可串行化和可线性化，可线性化意味着顺序一致性，等等。 颜色显示每个模型对于异步网络上的分布式系统的可用性。

​ Strict Serializability

Unavailable

Not available during some types of network failures. Some or all nodes must pause operations in order to ensure safety.

在某些类型的网络故障期间不可用。 为了确保安全，部分或全部节点必须暂停操作。

Sticky Available

Available on every non-faulty node, so long as clients only talk to the same servers, instead of switching to new ones.

只要客户端仅与相同的服务器通信，而不是切换到新的服务器，就可以在每个非故障节点上使用。

Total Available

Available on every non-faulty node, even when the network is completely down.

即使网络完全关闭，也可在每个无故障节点上使用。

Fundamental Concepts

Jepsen analyses the safety properties of distributed systems–most notably, identifying violations of consistency models. But what are consistency models? What phenomena do they allow? What kind of consistency does a given program really need?

Jepsen 分析分布式系统的安全属性，最值得注意的是，识别一致性模型的违规行为。 但什么是一致性模型？ 它们允许哪些现象发生？ 给定的程序真正需要什么样的一致性？

In this reference guide, we provide basic definitions, intuitive explanations, and theoretical underpinnings of various consistency models for engineers and academics alike.

在本参考指南中，我们为工程师和学者提供各种一致性模型的基本定义、直观解释和理论基础。

Systems

Distributed systems are a type of concurrent system, and much of the literature on concurrency control applies directly to distributed systems. Indeed, most of the concepts we’re going to discuss were originally formulated for single-node concurrent systems. There are, however, some important differences in availability and performance.

分布式系统是一种并发系统，许多有关并发控制的文献直接适用于分布式系统。 事实上，我们要讨论的大多数概念最初都是为单节点并发系统制定的。 然而，在可用性和性能方面存在一些重要差异。

Systems have a logical state which changes over time. For instance, a simple system could be a single integer variable, with states like 0, 3, and 42. A mutex has only two states: locked or unlocked. The states of a key-value store might be maps of keys to values, for instance: {cat: 1, dog: 1}, or {cat: 4}.

系统具有随时间变化的逻辑状态。 例如，一个简单的系统可以是一个整数变量，具有 0、3 和 42 等状态。互斥锁只有两种状态：锁定或解锁。 键值存储的状态可能是键到值的映射，例如：{cat：1，dog：1}或{cat：4}。

Processes

A process1 is a logically single-threaded program which performs computation and runs operations. Processes are never asynchronous—we model asynchronous computation via independent processes. We say “logically single-threaded” to emphasize that while a process can only do one thing at a time, its implementation may be spread across multiple threads, operating system processes, or even physical nodes—just so long as those components provide the illusion of a coherent singlethreaded program.

进程 是一个逻辑上的单线程程序，用于执行计算和运行操作。 进程从来都不是异步的——我们通过独立进程对异步计算进行建模。 我们说“逻辑上单线程”是为了强调，虽然一个进程一次只能做一件事，但它的实现可以分布在多个线程、操作系统进程、甚至物理节点上——只要这些组件提供了假象 一个连贯的单线程程序。

Operations

An operation is a transition from state to state. For instance, a single-variable system might have operations like read and write, which get and set the value of that variable, respectively. A counter might have operations like increments, decrements, and reads. An SQL store might have operations like selects and updates.

操作是从状态到状态的转换。 例如，单变量系统可能具有读取和写入等操作，分别获取和设置该变量的值。 计数器可能具有递增、递减和读取等操作。 SQL 存储可能具有选择和更新等操作。

Functions, Arguments & Return Values

In theory, we could give every state transition a unique name. A lock has exactly two transition: 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, ….

理论上，我们可以给每个状态转换一个唯一的名称。 锁只有两个转换：“lock”和“unlock”。 整数寄存器具有无限次数的读取和写入：“read-the-value-1”、“read-the-value-2”、…和“write-1”、“write-2”、…。

To make this more tractable, we break up these transitions into functions like read, write, cas, increment, etc., and values that parameterize those functions. In a single register system, a write of 1 could be written:

为了使这个过程更容易处理，我们将这些转换分解为“函数”，如“read”、“write”、“cas”、“increment”等，以及参数化这些函数的“值”。 在单寄存器系统中，可以写入 1：

{: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 it complete, a strictly greater completion time, both given by an imaginary2, perfectly synchronized, globally accessible clock.3 We refer to these clocks as providing a real-time order, as opposed to clocks that only track causal ordering.4

为了对此进行建模，我们说每个操作都有一个调用时间，并且如果完成，则有一个严格更大的完成时间，两者都由一个虚构的[2](https://jepsen.io/consistency#fn- 2)、完全同步、全局可访问的时钟。3 我们将这些时钟称为提供实时顺序，而不是仅跟踪的时钟 因果排序。4

Concurrency

Since operations take time, two operations might overlap in time. For instance, given two operations A and B, A could begin, B could begin, A could complete, and then B could complete. We say that two operations A and B are concurrent if there is some time during which A and B are both executing.

Processes are single-threaded, which implies that no two operations executed by the same process are ever concurrent.

Crashes

If an operation does not complete for some reason (perhaps because it timed out or a critical component crashed) that operation has no completion time, and must, in general, be considered concurrent with every operation after its invocation. It may or may not execute.

A process with an operation is in this state is effectively stuck, and can never invoke another operation again. If it were to invoke another operation, it would violate our single-threaded constraint: processes only do one thing at a time.

Histories

A history is a collection of operations, including their concurrent structure.

Some papers represent this as a set of operations, where each operation includes two numbers, representing their invocation and completion time; concurrent structure is inferred by comparing the time windows between processes.

Jepsen represents a history as an ordered list of invocation and completion operations, effectively splitting each operation in two. This representation is more convenient for algorithms which iterate over the history, keeping a representation of concurrent operations and possible states.

Consistency Models

A consistency model is a set of histories. We use consistency models to define which histories are “good”, or “legal” in a system. When we say a history “violates serializability” or “is not serializable”, we mean that the history is not in the set of serializable histories.

We say that consistency model A implies model B if A is a subset of B. For example, linearizability implies sequential consistency because every history which is linearizable is also sequentially consistent. This allows us to relate consistency models in a hierarchy.

Speaking informally, we refer to smaller, more restrictive consistency models as “stronger”, and larger, more permissive consistency models as “weaker”.

Not all consistency models are directly comparable. Often, two models allow different behavior, but neither contains the other.