副本一致性

本文介绍副本一致性模型。

1. 概述

在分布式系统中，我们希望副本保持一致，那么什么叫一致呢？数据完全一样？

针对不同场景，提出了不同的模型，这些模型对一致性的定义也不一样。下图展示了Jepson提出的一致性模型：

模型定义了哪些情况是允许的

不同的颜色代表了该模型在基于异步网络的分布式系统中的可满足程度：

蓝色：完全可用（Total Available），即使网络完全崩溃，蓝色标识的模型表示在每一个可用的节点上仍然可满足要求；
即每一个未崩溃的节点，在收到任何请求时，都必须能立刻给出成功的响应，而不允许因为无法联系其他节点而拒绝服务。
橙色：粘性可用（Sticky Available），橙色标识的模型表示在每一个可用节点上，只要客户端每次连接同一个服务器，即可满足模型要求；
粉色：不可用（Unavailable），粉色标识的模型表示，在发生了网络故障的情况下，某些节点或所有节点必须停止操作，以满足模型要求；

箭头表示了模型之间的关系，例如，Strict Serializable表示该模型既满足Serializable模型的要求，也满足Linearizable模型的要求。

在本文中，我们主要关注右侧模型（分布式系统中）。

2. 基本概念

2.1 系统

分布式系统在本质上是一种并发系统。诸如悲观锁、乐观锁、多版本并发控制（MVCC）以及事务的隔离级别（如串行化）等核心概念，最早都是为了解决单机多线程/多进程共同访问内存数据而设计的。当进入分布式环境时，这些理论依然是基石。

虽然理论相通，但分布式系统引入了两个单机系统难以企及的挑战：可用性（Availability）与性能（Performance）。

网络分区与部分失效（Partial Failure）： 在单机上，如果 CPU 访问内存失败，整个系统通常直接崩溃。但在分布式系统中，网络可能延迟、丢包或中断。部分节点可能死机，而其他节点还在运行。如何保证在部分组件失效的情况下，分布式系统仍然正常运转，是分布式系统中要解决的一个问题。
性能与物理限制： 单机并发通过内存总线通信，延迟通常在纳秒级别。分布式系统跨节点通信依赖网络，延迟在毫秒级别（相差百万倍）。为了提升性能，系统必须尽量减少节点间的同步等待，这便与数据的一致性产生了直接冲突（这也正是 CAP 定理的核心探讨点）。

整个系统在逻辑上可视为一个状态机，其状态会随着时间流逝而变化。无论是简单的整数（例如0，2，-28）、互斥锁（Mutex，只有两个状态：locked和unlocked），还是复杂的分布式 Key-Value 数据库（例如{cat: 1, dog: 1}），它们都可以被视为一个状态机。

2.2 节点

节点是一个逻辑概念，在分布式系统中，通常称为节点，在单机系统中，通常称为进程。

只要一个组件对外界表现出“一次只能做一件事”，无论它底层有多复杂，在模型中它就是一个“节点”。在模型中，一个“节点”的实现可能很复杂，可能是多线程系统，也可能是多进程系统，甚至是跨物理机的多进程系统，但是只要作为一个整体，表现出一次只做一件事，那就视为一个节点。

典型的例子就是 Raft 状态机集群（如 etcd、ZooKeeper）。

物理上（实现上）：它是由 3 台或 5 台独立的物理服务器组成的集群，节点之间充斥着复杂的网络通信、Leader 选举和日志复制。
逻辑上：对于客户端（Client）而言，这个集群表现出的行为与一台绝对安全、绝对不会宕机、且单线程运行的服务器一模一样。往里写一个数据，它要么成功，要么失败，不存在中间态。

因此，Raft状态机集群视为系统中的一个节点。

2.3 操作

一个操作可以让系统从一个状态迁移到另一个状态。例如，一个整数单值系统可能只有两种操作：read和write，分别用于读取和设置系统状态值，例如read-the-value-1, read-the-value-2, …和 write-1, write-2,...，像这样根据状态来罗列操作根本不现实，因为像状态 write-1, write-2 到无穷大是无法穷举的。

解决方案是将操作抽象为“函数（Function） + 参数/返回值（Arguments/Return Values）”。无论是简单的赋值，还是复杂的 SQL 事务（包含多个读写），要么全部发生导致状态改变，要么完全不发生。

也就是说，对于一个操作，从状态机角度来看，这个操作是原子化的，要么全部成功导致系统状态发生跃迁，要么全部失败系统状态保持原状，外界永远看不到这个操作执行了一半的“中间状态”。

但实际上，操作需要耗费时间（不可能是瞬间发生的），每一个操作都有一个明确的“开始（Invocation）时间”和“结束（Completion）时间”，并且结束时间大于开始时间。在单机系统中，一个操作意味着一次函数调用，操作开始时间是函数调用时间，操作结束时间是函数执行完成时间；在分布式系统中，一个操作意味着一个消息的发送与接收，操作开始时间是发送消息时间，操作结束时间是接收消息时间。

在以上操作说明中，引入了一个非常关键的假设：一个想象中完美的、全球同步的绝对真实时钟（Real-time clock）。基于这个时钟，每个操作被拆分为两个事件点：

调用时间（Invocation Time, $t_{i n v}$ ）：请求发出的瞬间；
完成时间（Completion Time, $t_{c o m p}$ ）：收到响应的瞬间，且必然满足 $t_{c o m p} > t_{i n v}$ ；

由于操作需要耗费时间，如果两个操作的时间段有交集（Overlap），那它们就是并发的。

非并发（顺序）： A 彻底结束后 B 才开始（ $t_{c o m p} (A) < t_{i n v} (B)$ ），此时 A 一定先于 B 发生。
并发： A 还没结束，B 就已经开始了。在分布式系统中，这意味着我们无法在物理时间上立刻分辨出谁先谁后，必须依赖一致性协议来“决定”它们的逻辑顺序。
节点的限制： 因为前面定义了节点是逻辑单线程的，所以同一个节点内部的两个操作绝对不可能并发，必然是前一个收到响应后，才能发起后一个。

当一个操作没有完成时间，我们无法得知它到底执行了没有，这就发生了崩溃（crash）：

没有完成时间： 如果一个请求发出去后，由于连接断开或节点组件崩溃，那这个操作只有 $t_{i n v}$ ，没有 $t_{c o m p}$ ；
假设在分布式系统中，节点A在t1发生请求，然后t2时刻到达节点B，t3时刻节点B执行完成返回响应，t4时间节点A收到响应。
在以上理论模型中，操作（Operation）的主体是发起请求的“进程”（也就是节点 A）。
- 调用时间（Invocation Time）： 节点 A 发出请求的瞬间，即 $t_{1}$ 。
- 完成时间（Completion Time）： 节点 A 真正收到响应、得知这个操作已经完成的瞬间，即 $t_{4}$ 。
所以，站在整个系统的视角来看，这个操作在时间轴上占据的区间是 $[t_{1}, t_{4}]$ 。在这个区间内，任何其他操作如果也正在执行，就会被判定为与该操作“并发”。
生效点（Commit Point）： 尽管操作的生命周期是 $[t_{1}, t_{4}]$ ，但这个操作真正改变系统状态的原子瞬间（即实际生效的时刻），必然发生在 $[t_{1}, t_{4}]$ 之间的某一个逻辑点上（在以上例子中，正是节点 B 写入数据的 $t_{3}$ 这一时间点）。
与未来所有操作并发： 在分布式系统中，如果一个操作（发送消息）没有完成时间，可能有以下情况：
- 情形一：这个请求是被服务器收到了，并且执行了，但是返回的响应丢失了。在这种情况下，操作实际上是执行了。
- 情形二：这个请求由于网络中断，没有达到服务器，在这种情况下，操作实际上没有执行。
在理论模型中，这个操作就像一个游荡在系统里的“幽灵”。它可能在未来某个不可预知的物理时间点，因为网络的恢复或者服务器的重启，突然在后端生效（数据被修改），必须假设它可能在未来的任意一个时间点突然生效。因此，它与发起它之后的“所有操作”都算作并发。
节点的“死亡”： 既然操作一直没有 $t_{c o m p}$ （悬而未决），根据单线程节点“一次只能做一件事”的约束，这个节点就被永远卡死（Stuck）了，它再也无法发起任何新的操作。在模型中，这个节点等同于“死亡”。

2.4 操作历史

操作历史就是操作集合。

一些论文把操作表示为如下结构：

txt

(operation, invocation_time, completion_time)

例如：

txt

(write(1), 1, 5)
(read(),   3, 7)

因此，操作历史可以表示如下：

txt

{
  (write(1), 1, 5),
  (read(),   3, 7)
}

并发关系通过比较两个操作的时间区间得到。

在Jepson中，操作被拆分为两个：开始和结束。例如：

txt

[
  {:type :invoke :process 0 :time 1 :f :write :value 1}
  {:type :invoke :process 1 :time 3 :f :read}
  {:type :ok     :process 0 :time 5 :f :write}
  {:type :ok     :process 1 :time 7 :f :read}
]

2.5 一致性模型

一致性模型本质上不是一种实现方式，而是一种“允许哪些行为发生”的规范（specification）。所以它自然可以被定义为：所有满足该规范的操作历史的集合。

假设现在有很多操作，通过不同的排列，可以组成不同的操作历史，在不同的一致性模型中，一些操作历史是合法的，一些操作历史是不合法的。

在上图的一致性模型示意图中，箭头表示模型的关系，更进一步，假设A $\to$ B，也就是说模型B的操作历史集合是模型A的操作历史集合的子集，也就是说，模型B相比模型A，是更强、范围更窄、限制更多的模型。但是，并不是所有模型都是包含关系。

3. 模型介绍

3.1 Monotonic Reads

Monotonic Reads，译为单调读，是指对于同一个节点而言，先后执行read操作 $r_{1}$ 和 $r_{2}$ ，那么 $r_{2}$ 的结果不能早于 $r_{1}$ 的结果。

例如，现在在节点A上先后执行如下操作（系统状态为单值整数）：

txt

write(20)
write(50)
read()   // r1
read()   // r2

如果第一次读取 $r_{1}$ 的结果是50，那么第二次读取 $r_{2}$ 的结果不能是20。

单调读模型只针对单个节点，只需要单个节点满足读取不会回退的要求，就符合单调读的要求，单调读并不要求其他节点必须读取到最新的结果。

即使发生网络分区，单调读也始终是能保证的，可以用版本号机制实现：

原理：客户端进程在内存中维护一个自己见过的最新版本号（或逻辑时间戳）max_version。
读请求（ $r_{1}$ ）：客户端向任意节点发起读请求。节点返回数据和该数据的版本号 $V_{1}$ 。客户端更新本地的 max_version = $V_{1}$ 。
随后的读请求（ $r_{2}$ ）：客户端发起下一次读，并将 max_version（即 $V_{1}$ ）随请求一起发送给服务端节点。
服务端节点的处理：如果接收请求的节点发现自己本地的数据版本 $V_{n o d e} \geq V_{1}$ ，说明自己的数据足够新，直接返回。
- 如果服务端发现自己本地的数据版本 $V_{n o d e} < V_{1}$ （它是个慢节点），它不能直接返回旧数据。它必须做两件事之一：要么等待（同步最新日志），要么向客户端报错/重定向，让客户端去试别的节点。

3.2 Monotonic Writes

Monotonic Writes，译为单调写，单调写的含义是如果同一个节点（客户端）先后发起了两个写操作 $w_{1}$ 和 $w_{2}$ ，那么在系统中的任何节点看来， $w_{1}$ 发生的时间都必须在 $w_{2}$ 之前。也就是说，对于同一个节点发出的写操作，必须按顺序执行，不允许乱序，没有任何一个观察者（其他进程或节点）能先看到 $w_{2}$ 的结果，后看到 $w_{1}$ 的结果。

为什么会乱序？由于网络原因，可能前一个操作被阻塞在网络中，后一个操作先到达系统

例如，假设现在我的银行账户余额为0元，首先我向账户充值100元（ $w_{1}$ 操作），再向其他账户转账100元（ $w_{2}$ 操作）。系统必须先处理 $w_{1}$ 操作，后处理 $w_{2}$ 操作。

单调写只约束同一个进程内部的写操作顺序。

如果节点 A 发起了 $w_{1}$ ，节点 B 发起了 $w_{2}$ ，它们之间没有任何因果或顺序约束。
不同的节点完全可能先执行 $w_{2}$ 后执行 $w_{1}$ ，这并不违反单调写。它只对“单进程线性的写操作”提供历史顺序的尊重。

即使发生网络分区，单调写始终能保证，同样使用版本号机制实现：

做法：客户端进程在本地维护一个递增的计数器（序列号）。发送 $w_{1}$ 时带上 seq=1，发送 $w_{2}$ 时带上 seq=2。
节点处理：任何分布式节点在收到写请求时，如果发现收到了 seq=2 但本地还没收到 seq=1，它会把 $w_{2}$ 放入缓冲区暂存，直到通过复制或其他渠道收到了 $w_{1}$ 并执行后，才执行 $w_{2}$ 。
为什么可用？当网络分区发生时，数据复制可能中断，节点在收到 $w_{2}$ 时可能会被阻塞（不应用 $w_{2}$ ）。但对于发起写的客户端本身而言，它的写请求只要送达当前系统的任意一个节点即可，不需要跨分区等待另一个孤岛的确认。因此，写入操作正常情况下不会被网络分区阻塞。

3.3 Read Your Writes

Read Your Writes（Read My Writes），也就是说如果一个节点（客户端）执行了一个写操作 $w$ ，紧接着该节点又执行了一个读操作 $r$ ，那么 $r$ 必须能够看到 $w$ 所带来的影响。

这同样是针对单节点的约束。假如节点1执行了写操作，节点2并不保证能读到写操作的结果。

Read Your Writes是粘性可用的，实现方案是保证客户端始终与同一个服务端对话：

客户端进程与集群中的节点 A 建立了连接（绑定会话）。
客户端向节点 A 发起写操作 $w$ ，节点 A 本地写入成功并回应客户端。
随后网络发生分区，节点 A 与集群中的其他节点（B、C）断开，无法把数据复制过去。
此时客户端发起读操作 $r$ ：
- 如果客户端保持“粘性”： 它的读请求依然发给节点 A。由于节点 A 本地已经有了 $w$ 的记录，它会立刻把最新数据返回给客户端。即便发生了网络分区，这个节点依然能提供服务（Make progress），且完美满足 Read Your Writes要求。
- 如果客户端切换了服务器： 假设客户端因为某种原因断连，重连到了孤岛另一边的节点 B。由于分区存在，节点 B 压根不知道 $w$ 的发生，客户端就会读到旧数据，从而破坏了 Read Your Writes要求。

Read-Your-Writes（写后读/读己之所写）约束的是“单节点自己”；
Read-After-Write（写后读一致性/强一致性）约束的是“全网所有人”；

3.4 PRAM

PRAM=Monotonic Reads + Monotonic Writes + Read Your Writes

3.5 Writes Follow Reads

Writes Follow Reads ，译为读后写，是指如果一个写操作 $w_{2}$ 是基于某次读取 $r_{1}$ 结果做出的，那么这个写操作 $w_{2}$ 必须排在产生该读取 $r_{1}$ 结果的写操作 $w_{1}$ 之后。

也就是说，如果节点A执行了写操作 $w_{1} ： x = 1$ ，然后节点B先执行读操作 $r_{1} ： x \to 1$ ，再执行写操作 $w_{2} ： y = 2$ ，就形成了因果链：

txt

x=1
 ↓
B看到了x=1
 ↓
B执行了y=1

由于 B 的写操作 $w_{2}$ 是建立在读到 $w_{1}$ 的结果之上的，

所以系统必须保证：

w1 happens-before w2

即：

w1 → w2

假设其他节点能观察到 $w_{2}$ 的结果，那必然能观察到 $w_{1}$ 的结果。不能出现看到 $w_{2}$ ，但是没有看到 $w_{1}$ ，因为 $w_{2}$ 依赖 $w_{1}$ 。

读后写模型是始终可满足的，只需要在写操作中带上依赖元数据，如向量逻辑时钟。

假设系统中有 3 个节点： $N_{1}, N_{2}, N_{3}$ 。每一个节点和每一个客户端都会维护一个向量 $V$ ，例如 $[N_{1} : 0, N_{2} : 0, N_{3} : 0]$ ，分别记录它们所感知的各个节点的版本推进情况。

第一步：节点 1 发起写入 ( $w_{1}$ )，写入了数据 $x = A$ 。

$N_{1}$ 将自己的时钟加 1，生成向量时钟：[1, 0, 0]。
此时， $w_{1}$ 的身份标签就是 (x=A, VC=[1, 0, 0])。
$N_{1}$ 开始异步向其他节点广播这个消息。

第二步：节点 2 收到了 $w_{1}$ 请求的消息并交付消息

节点 2 读到了 $x = A$ ，更新自己的本地向量时钟为[1, 0, 0]。
消息交付规则如下（必须同时满足以下规则，才能交付消息）：
- 规则 1：这是来自 $N_{j}$ 的“下一个紧邻的全新事件”，系统要求接收方的本地时钟在 $N_{j}$ 这一位上，恰好只比发送消息少 1。
  $本地时钟 [j] = V_{m s g} [j] - 1$
  含义：这证明此消息是 $N_{j}$ 节点产生的连续的、没有丢包的下一个新消息。
- 规则 2：接收方已经看过了发送方看过的所有“其他节点的历史”：对于除了发送方 $N_{j}$ 之外的所有其他节点 $k$ （ $k \neq j$ ），接收方的本地时钟必须大于或等于消息的时钟：
  $本地时钟 [k] \geq V_{m s g} [k] (对于所有 k \neq j)$
  含义：只要接收方没有漏掉来自其他节点的历史，就符合接收资格。

第三步：节点 2 发起新的写入 ( $w_{2}$ ) —— “读后写”，把 $x$ 修改为 $B$ （ $w_{2}$ ）

节点 2 发起写请求 $w_{2} (x = B)$ ，并在请求体里附带上该操作的因果依赖：Deps = [1, 1, 0]。
此时节点3收到了请求 $w_{2}$ ，应用消息交付规则：
条件 1（看发送方 $N_{2}$ ）： $T^{'} [2] = 1$ 是否等于 $T_{l o c a l} [2] + 1 = 0 + 1 = 1$ ？满足！（证明这是 $N_{2}$ 发给我的第 1 个写操作）。
条件 2（看其他方 $N_{1}$ ）： $T^{'} [1] = 1$ 是否 $\leq T_{l o c a l} [1] = 0$ ？ 不满足！（ $1 \leq 0$ 失败，证明 $N_{3}$ 还没收到过 $N_{1}$ 的那次写）。
所以 $w_{2}$ 消息在节点3上不会交付，而是阻塞等待 $w_{1}$ 操作请求。但是，对于 $w_{2}$ 操作请求，节点3仍然会返回接收成功。

从以上流程可以看到，节点3即使没有收到 $w_{1}$ 操作请求，但是对于 $w_{2}$ 操作请求，也会响应成功，并不会失败，所以这就是Writes Follow Reads始终可用的原因。

3.6 Causal Consistency

Causal Consistency，即因果一致性，要求具有因果关系的操作必须在所有节点上，都按照因果关系排序，而非因果关系的操作，在不同节点上，可以以不同的顺序排序。

例如，在群聊中，会出现以下情况：

班长在群里发了一句：“明天我们要去郊游。”（操作 A）
同学甲在自己手机上回复：“太棒了！”（操作 B）
同学乙在自己手机上同时回复：“带上我！”（操作 C）

这里，B 和 C 都是基于 A 发生的，但 B 和 C 之间没有任何因果关系（甲和乙并没有商量，他们是并发独立操作）。根据因果一致性：

从节点 1读取（可能离同学甲近）：展现的顺序是 [通知] ➔ [太棒了] ➔ [带上我]。
从节点 2读取（可能离同学乙近）：展现的顺序是 [通知] ➔ [带上我] ➔ [太棒了]。

系统完全允许节点 1 和节点 2 出现这种分歧，因为 B 和 C 是独立的。

因果一致性是粘性可用的，因为因果一致性包含了Read Your Writes。通常使用向量时钟实现因果一致性模型。

虽然因果一致性允许非因果操作（如上面的 B 和 C）在不同节点上乱序，但如果系统一直让他们乱下去，聊天历史可能永远对不齐。所以在实际工程中（如 Cassandra 或各种分布式存储），实际用的是 Causal+（收敛因果一致性）：系统允许在网络同步期间，大家短暂地看到不同的顺序；但一旦网络恢复、日志同步完毕，系统会通过一个兜底规则（比如按物理时间戳 LWW），让所有人最终看到的顺序收敛到完全一致。

3.7 Sequential Consistency

Sequential Consistency，译为顺序一致性。顺序一致性，就是在因果一致性的基础上，将没有因果关系的操作，也规定了一个统一的顺序。

还是以上面群聊的例子说明：

在节点1上：展现的顺序是 [通知] ➔ [太棒了] ➔ [带上我]。
在节点2上：展现的顺序是 [通知] ➔ [带上我] ➔ [太棒了]。

在顺序一致性模型中，这种分歧是不允许出现的，只允许有一个统一的顺序。

通常使用全序广播（Raft算法）来实现顺序一致性模型。

由于使用了全序广播（Raft算法），那么在发生网络分区的情况下，一些节点或全部节点就可能暂停工作，以保证操作顺序的正确性。

在顺序一致性模型中，一些节点可能落后其他节点很多，这种情况是允许的，例如：

txt

节点A：1 -> 2 -> 3 -> 4 -> 5 -> 6
节点B：1 -> 2

目前节点A的系统本地状态已经到了6，但是节点B的系统本地状态还是2。

如果此时客户端连接到节点B进行读取，读取到一个非常落后的状态，这种情况是可能发生并且允许的。

3.8 Linearizability

在顺序一致性模型中，对于没有因果关系的操作，也规定了一个统一的顺序，例如，现在有一个单值数值，初始值为0，现在有两个操作：

txt

write(1)
get()

在顺序一致性模型中，既可以 write(1) -> get()，也可以get() -> write(1)，这样get()的结果既可以是0，也可以是1。

但是，在Linearizability（线性一致性）模型中，操作的先后顺序必须依据真实物理时间。线性一致性核心要求是：让一个分布式系统看起来就像只有一个单机节点，并且这个节点处理操作是瞬时完成的一样。

假如get()的开始时间晚于write(1)的结束时间，那么只会有write(1)->get()这一个操作顺序，get()会返回1；
假如get()的结束时间早于write(1)的开始时间，那么只会有get() -> write(1)这一个操作顺序，get()会返回0；
假如get()和write(1)在真实时间上有重叠，那么返回0或返回1都是可以的；

要实现Linearizability模型，可以在读写操作上都采用多数读/多数写。因此，当发生网络分区时，系统可能无法提供服务。

在下图中，读写操作都采用了多数读/多数写，但是仍然不满足Linearizability模型要求。

首先，客户端1执行set(x, v1)操作，并且很快就在节点A上操作成功，但是由于网络原因，操作请求延迟到达节点B和节点C。一会儿，客户端2执行get(x)操作，节点A和节点B响应，客户端根据返回值版本号，返回了最新值 $v_{1}$ ；在客户端2结束之后（真实时间），客户端3也发起了get(x)操作，节点B和节点C响应（注意，此时节点B和节点C的值还是 $v_{0}$ ），所以客户端拿到的值是 $v_{0}$ 。

以上现象是不满足线性一致性要求的，因为客户端2已经获取到最新值了，说明现在系统已经演变到下一个状态了，而客户端3发生时间在客户端2结束之后，那么客户端3必须也能读取到系统最新状态，而此时客户端3读取到了旧值 $v_{0}$ 。

为了修复以上问题，Attiya, Bar-Noy和 Dolev提出了ABD算法：在get()操作时，如果发现某些节点返回了旧值或没有返回值，那么客户端需要在发送set()操作请求，以修复系统。只有当整个系统大多数节点达到了最新状态，get()操作才算完成。

在ABD算法中，只优化了get()操作，set()操作称为盲写（blind write）。

如果有多个客户端同时执行set()操作，并且采用LWW（last-writer-wins）算法解决冲突，那么只有最后一个写入有效，其他写入会被静默丢弃。为了更谨慎地修改值，可以采用CAS（compare and swap）算法。但是，在ABD算法中，单纯使用多数写来实现CAS算法是不可能的，因为在不同的节点，set()操作可能到达的顺序不同，最终导致系统节点数据的不一致。

假设现在系统值为0，有两个cas()操作
cas(0, 1)：如果值为0，将值改为1；
cas(0, 2)：如果值为0，将值改为2；
在ABD算法中，不同节点接收到操作的顺序不同：
在节点A上，先接收cas(0, 1)，后接收cas(0, 2)，最终节点A上值为1；
在节点B上，先接收cas(0, 2)，后接收cas(0, 1)，最终节点B上值为2；
这样系统节点就出现了不一致。

为了实现CAS，可以使用全序广播（Raft算法）：

txt

on request to perform get(x) do
	total order broadcast (get, x) and wait for delivery
end on

# 如果要执行cas，将消息通过全序广播给领导者节点
on request to perform CAS(x, old, new) do
	total order broadcast (CAS, x, old, new) and wait for delivery
end on

on delivering (get, x) by total order broadcast do
	return localState[x] as result of operation get(x)
end on

# 交付消息
on delivering (CAS, x, old, new) by total order broadcast do
  success := false
  if localState[x] = old then
  	localState[x] := new; 
  	success := true
  end if
  return success as result of operation CAS(x, old, new)
end on

3.9 Strict Serializability

Strict serializability，译为严格串行化，是一个事务模型，是分布式事务和并发控制中的最高安全级别。它结合了两个概念：

串行化（Serializability）：针对多对象、多事务。要求并发执行的多个事务，其最终结果等价于某种完全串行（一个接一个）执行的顺序。
线性一致性（Linearizability）：针对实时时间顺序（Real-time Order）。如果事务 T2 在事务 T1 提交之后才发起，那么在全局顺序中，T1 必须排在 T2 之前。

简单来说，严格串行化要求系统不仅看起来是串行的，而且必须尊重现实世界的时间先后顺序。

严格串行化，可以理解为线性一致性+事务ACID特性。

下面的例子演示了如果只满足线性一致性，在并发操作下可能出现的问题。

假设现在有一个账户，余额为0元。

操作1：分为两个原子操作，先充值200元，再扣款200元；
操作2：分为两个原子操作，先读取账户余额，然后判断如果余额大于100元，再扣款100元；

具体的操作顺序如下：

最终，账户余额为负数，显然，这是不正确的。

因此，在线性一致性的基础上，加上事务控制，才能保证数据的安全。

参考资料

[1] 一致性模型：https://jepsen.io/consistency/models

[2] Distributed Systems Notes By Dr. Martin Kleppmann

副本一致性 ​

1. 概述 ​

2. 基本概念 ​

2.1 系统 ​

2.2 节点 ​

2.3 操作 ​

2.4 操作历史 ​

2.5 一致性模型 ​

3. 模型介绍 ​

3.1 Monotonic Reads ​

3.2 Monotonic Writes ​

3.3 Read Your Writes ​

3.4 PRAM ​

3.5 Writes Follow Reads ​

3.6 Causal Consistency ​

3.7 Sequential Consistency ​

3.8 Linearizability ​

3.9 Strict Serializability ​

参考资料 ​