20221220-一致性算法学习笔记

• 理解一致性问题
  • 什么是一致性问题
  • 一致性≠正确性
  • 一致性问题的产生原因
• 了解一致性算法
  • 2PC、3PC9
  • 一致性哈希算法
  • NWR算法
  • OT算法
  • Lamport Clock
  • Vector Clock（向量时钟）
  • Paxos和Raft
• 参考资料

---

理解一致性问题

什么是一致性问题

一致性是指多个线程或进程在各自观察系统的时候能看到相同的现象。根据观察的客体不同，可以分为数据一致性和顺序一致性。

• 数据一致性：各副本之间的数据是否相同。¹
• 顺序一致性：所有进程观察到的数据操作顺序是一样的。^{1 2}

我认为数据一致性和顺序一致性不是相互独立存在的概念，而是一致性问题的两个面，共同构成了一致性问题。

除了上述两类一致性之外，还有各类一致性问题，我认为这些问题都是上述两类问题的特例，比如：

• 因果一致性：有因果关系的操作在所有进程看到的顺序的一样的，这里的因果关系是指在时序上有明确的先后关系。例如A的写和B的读存在因果关系（A前B后），那么B应该读出A写的数据。^{3 4}
• 读己之所写：自己写的数据自己能读出来。³
• 单调读一致性：读到某个数据，后续读不会读到更旧的数据。³
• 单调写一致性：来自同一个节点的写操作一定按顺序执行。³
• 一致性读和脏读：读的过程中数据发生修改，修改不应该表现在读出的结果中，否则就是脏读（Dirty Read）⁵

在系统设计和实现的时候可能无法保障上述所有类型的一致性，我们可能需要在上述各类一致性中做出权衡取舍。一致性问题还有一个权衡取舍的纬度是强一致性和弱一致性^{6 7}：

• 强一致性：任何时候的读，都返回最近一次写的值；操作顺序对所有进程表现为全局时钟一致。
• 弱一致性：系统不保证任何时候的读都能返回最近一次写的值，也不保证多久之后能读到最新的值。

强一致性不一定就好，弱一致性不一定就坏。这里需要提到CAP理论⁸。CAP分别代表分布式系统的三个基本需求：Consistency（一致性）、Availability（可用性）和Partition tolerance（分区容错性），CAP理论指出上述三个需求无法同时满足，最多只能同时满足两个。所以强一致性可以视为舍弃A或P而保障C，而弱一致性可以视为舍弃C而保障AP。

以CAP理论为基础，业界在实践分布式系统时，对C和A做出取舍，并提出了BASE理论。BASE是Basically Available（基本可用）、Soft state（软状态）、Eventually consistency（最终一致性）的缩写：^{3 7 8}

• 基本可用：允许系统局部故障，而保障系统的大部分功能或核心功能可用。
• 软状态：数据或操作尚未完全同步到系统的每个节点或进程的中间状态。
• 最终一致性：系统保证在没有其他更新操作的情况下，经过一段有限的时间后，数据最终能达到一致的状态。

一致性≠正确性

一个典型的例子是：在多人协作文档中，AB两人分别写了两段相互矛盾的段落。文档应用将两段文字合并之后产生的文档，其内容显然是不具有正确性的。

另一个典型的例子是：在保障最终一致性的分布式数据库中，两个进程分别修改了同一个字段，且写入的值不同。数据库在保障一致性的时候需要处理上述冲突，可以总是用其中一个值覆盖另一个，但不管用谁覆盖谁，产生的结果可能都不具有正确性。

文档的正确性依赖于应用甚至用户来定义和评价，而文档系统和算法本身不具备代替应用和用户评价正确性的能力。为尽量保障正确性，应用或用户可以把对正确性的需求抽象为对系统的技术指标或用例，或者系统将一致性算法的某些决策或冲突环节交给应用或用户来处理。

一致性问题的产生原因

产生一致性问题的典型原因有：

• 分布式系统中各节点和链路不可靠，比如发生故障、扩容缩容、程序异常、负载太高等。
• 非原子性操作或事务操作中某个步骤异常失败。
• 数据在多个线程或进程中有多个副本，且多个副本之间存在并发读写。

不管是什么样的原因，只要是在分布式系统中，就存在一致性问题。

了解一致性算法

业界有很多一致性算法，各类算法实现了不同的一致性，或解决了一致性问题的不同方面。但不管是哪个算法，都不解决如何处理冲突，因为冲突的处理方案依赖于应用和用户的需求，不属于算法的一部分。

因为有很多关于这些算法做详细解释的帖子，故本文并不打算对这些算法展开讨论，下面仅对一些典型的一致性算法记录其要点和我的理解。

2PC、3PC⁹

通过分布式事务把一次写操作提交到分布式系统的每个数据库，保障每个数据库的数据一致性。本类算法在CAP中舍弃了A和P，保障强一致性。

2PC即两阶段提交，其核心思想是将事务分割为两个阶段：投票和执行。各参与者在投票阶段执行本地事务，然后根据所有阶段的投票结果决定是保留执行结果还是回滚本地事务。在2PC的整个流程中，需要对资源加锁，保障操作的原子性。2PC不能保障高并发性能，且在一个节点宕机后可能引发一系列问题。

3PC是对2PC的改进。3PC=CanCommit+PreCommit+DoCommit，并引入超时机制。3PC相比2PC可以避免某些场景下的同步阻塞。

一致性哈希算法

一致性哈希算法并不是保障数据或顺序一致性的算法，而是解决动态网络拓普中对数据进行分发和路由的问题。该算法可以在分布式系统节点发生增减时保障同一个请求可以尽量由同一个节点处理，避免发生大面积的哈希重定位，导致系统性能下降。

该算法的核心思想是：¹⁰

• 把哈希值映射成虚拟圆环。
• 把服务器节点分配到圆环上。
• 以哈希值在圆环上的位置为起点，以顺时针方向把最近的节点作为哈希映射结果。

其效果是：当发生节点增减时，只有少量请求会发生哈希重定位；大部分请求不会受到节点变化的影响。该算法的缺点是：查询节点的时间复杂度是O(n)。

当服务器节点较少的时候，可能导致请求或数据在各节点上的分布不均匀。该问题可以通过引入虚拟节点来解决¹¹，即为每个服务器节点在圆环上分配多个节点。

NWR算法

该算法的核心思想¹²：

• N=数据副本个数。这里副本个数不能等同于系统中节点的个数。
• W=写一致性级别，即写入W个副本才算写入成功。
• R=读一致性级别，从R个副本读出数据才算读成功。

当 W+R＞N 时，R个副本中一定包含了最新写入的数据。借助时间戳、数据版本等手段，在满足顺序一致性的系统中可以实现强一致性。当 W+R≤N 时，系统只能保证弱一致性。

NWR算法可以视为一种分布式事务的变体，容忍更高的分区容错。如果设置W=1、R=N，则可以实现高可写；如果设置W=N、R=1，则可以实现高可读¹³。但正因为引入了分区容错性，需要考虑在旧副本上写的问题、读出脏数据的问题、写失败回滚的问题¹⁴等。上述问题并未在该算法中提供统一的解决方案。

OT算法

OT 即 Operation Transformation，是一种操作合并的指导思想，是一类算法的总称，在不同应用场景下可以有不同实现¹⁵。OT算法的典型应用场景是在线多人文档。OT算法可以提供最终一致性。

OT算法的核心思想是操作的传输、变换和合并¹⁵。一个典型的OT系统是维护基于字符的编辑操作，但OT算法并不仅限于字符操作，只要底层数据模型可以被线性寻址就可以使用OT算法¹⁶。OT系统的实现极大依赖于系统计划支撑的应用，因为需要根据应用的需求定义数据的操作集合、操作的变换函数等。

跟OT算法类似的还有CRDT算法，这里不做展开。

Lamport Clock

Lamport Clock 是由 Lamport 在一篇论文¹⁷中提出的一种逻辑时钟。逻辑时钟是一种保障顺序一致性的算法。

逻辑时钟的核心思想是定义时钟计数（Clock Condition）¹⁸：

• 计数C初始值为0。
• 当在节点内发生新事件后，该事件的计数在当前计数上加一。
• 一个节点发送了一个事件到另一个节点，目标节点的计数在源节点计数的基础上加一。
• 一个节点收到事件后，该事件的最终计数=本地计数和收到计数的最大值再加一。

根据上述规则对每个事件赋予时钟计数，就可以制定全局统一的事件排序规则，达到顺序一致性。

当任意两个操作a和b，如果能确定a发生在b之前，或ab存在因果关系，那么可以设置 C(a)<C(b)。但当已知 C(a)<C(b) 时，并不一定能推导出a发生在b之前，即不能计算出因果关系。

逻辑时钟并不保障时序的正确性，只保障各节点的发生的事件具有全局统一的偏序关系。

Vector Clock（向量时钟）

向量时钟是一种保障顺序一致性的算法，通过向量时钟可以计算两个事件的因果关系。

向量时钟的核心思想是¹⁹：

• 每个节点上的向量时钟都要记录系统中所有节点的 Lamport Clock，假设第i个节点的向量时钟是Vi。
• 节点内发生新事件时：Vi[i] = Vi[i] + d (d > 0)。
• 节点j收到节点i发来的消息时：Vj[k] = max{ Vi[k], Vj[k] }。
• 如果对任意k ( 0 ≤ k ≤ n)均有 Vi[k]≥Vj[k]，则Vi > Vj，即这两个事件有因果关系，节点j的事件happen-before节点i。
• 如果Vi和Vj基于上述规则无法比较，则两个事件没有因果关系，而可能是并发事件，需要处理冲突。

基于向量时钟可以实现一种满足最终一致性的分布式K/V数据库。如果两个进程操作了同一个字段，如果两个操作事件具有因果关系，就可以正确的确定两个操作之间是谁覆盖谁。

Paxos和Raft

Paxos和Raft都是用来实现强一致性的算法。Raft是Paxos的一种变体，同样可以实现一个高容错的分布式系统，其容错性和性能于Paxos同等，且由于Raft把算法分解为多个子问题，比Paxos更容易实现²⁰。

Raft的核心思想是Leader选举和日志同步²¹：

• 每个节点有三个身份：Follower、Candidate、Leader。
• 在一个随机的时间点，所有Follower自动变成Candidate，并发起选举投票，如果有半数以上节点回复，该节点就变成Leader。
• 由Leader向其他节点发起日志同步，同步过程类似2PC，如果超过半数节点（含Leader）返回了成功，则日志就从Uncommitted变成Committed。

Raft算法在并发操作和分区容错的情况下也能很好的保障一致性。

参考资料

1. 浅谈数据一致性 ↩ ↩²

2. 什么是顺序一致性 ↩

3. 分布式 基本理论 BASE | 分布式 ↩ ↩² ↩³ ↩⁴ ↩⁵

4. 浅谈数据一致性 ↩

5. 什么是数据库的“读一致性”和“写一致性”？ ↩

6. 强一致性、弱一致性、顺序一致性、最终一致性概述 ↩

7. 分布式系统数据一致性的6种方案 ↩ ↩²

8. 目前最详细、最常见的一致性协议算法-2PC、3PC、Paxos、Raft、ZAB、NWR ↩ ↩²

9. 2pc和3pc的详解与对比 ↩

10. 一致性哈希-baidu百科 ↩

11. 一致性Hash算法详解-知乎 ↩

12. 分布式一致性之Quorum NWR算法 ↩

13. 目前最详细、最常见的一致性协议算法-2PC、3PC、Paxos、Raft、ZAB、NWR ↩

14. NWR模型下的一致性问题 ↩

15. OT算法-知乎 ↩ ↩²

16. Operational Transformation Frequently Asked Questions and Answers ↩

17. Time, Clocks, and the Ordering of Events in a Distributed System Leslie Lamport  ↩

18. 分布式系统：Lamport 逻辑时钟 ↩

19. 分布式系统-向量时钟(Vector Clock) ↩

20. https://raft.github.io/ ↩

21. 目前最详细、最常见的一致性协议算法-2PC、3PC、Paxos、Raft、ZAB、NWR ↩