分布式原理（2）——分布式环境下的各种一致性

概述

分布式一致性问题通常存在于分布式内存共享、分布式存储（例如：分布式文件系统、多级缓存）等分布式系统中。该问题可用如下列场景描述：

1. 节点N1和N2上都存放着数据X的副本（同一份数据多个副本）；

2. 客户端A更新节点N1上的数据X；之后，客户端B从节点N2上读取数据X；

3. 在该场景中，客户端B从节点N2上是否可以读取到客户端A在节点N1上的数据更新？

这就是分布式一致性问题。

图1是历史上各种一致性之间关系的总结。

图2是从系统和数据的角度，分别看分布式一致性和隔离级别与各种序和一致性之间的关系。但这个世界比较混乱，不能讲清楚其内在关系。

图1 文献《Consistency in Non-Transactional Distributed Storage Systems》定义的各种分布式一致性概念间的关系图

图2 文献《Making Consistency More Consistent: A Unified Model for Coherence, Consistency and Isolation》定义了分布式一致性和事务一致性之间的关系图

线性一致性

文献[4]最早提出了线性一致性（LINEARIZABILITY）概念。文献[1]对线性一致给出了严格的形式化定义，如图3所示，线性一致性由三个部分构成：

1.单一顺序（SINGLEORDER）：在符合“vis”和“ar”概念的基础上定义并发操作间的全序关系。“vis”和“ar”的含义参见图4，“vis”表示结果的可见性关系，“ar”表示对结果集的排序关系[1]。就公式的数学含义而言，其表明：存在一个历史调度H’，相关操作（属于H的操作）的结果在其返回值返回之前（op.ocal=▽），操作结果的可见性是全序集合上去掉（去掉之意是“做集合差运算”，公式(8)中使用“\”表示）该操作不可见的情况（即SINGLEORDER强调最终结果的可见性和前后事件之间的顺序关系，事件之间的顺序关系是通过如下的REALTIME描述的）。

2.实际时间（REALTIME）：“rb”为“return-before”表示返回值的偏序关系，即REALTIME限制全序的“ar”符合“rb”限定的偏序关系。请注意，此处没有刻意强调REALTIME为物理时间，只是表明了事件之间的“序”的关系（而有的定义，会把线性一致性和物理时间绑定，但这种方法不是必须的；但REALTIME确实表示了一个与真实时间同步的一个顺序关系，即事件发生的真实序），顺序关系通过“Ea-endtime < Eb-starttime”来定义（每个事件都有开始时间和结束时间，事件a的结束时间小于事件b的开始时间，所以线性一致性把事件的整个生命周期与其他事件的生命周期串行化，而顺序一致性把会话内的结果串行化，两者有着不同，前者着眼于整个系统后者落脚点在一个会话内）。

3.返回值（RVAL(Ƒ)）：返回值属于一个预期的集合范围限定的值。图2-6中的公式(4)表明对于任意的操作，返回值符合上下文的逻辑；对于多副本的系统暗含之意是副本间数据保持一致后返回一致的、在预期的集合范围内的值。返回值被一致性的级别所限定。

图3 文献[1]，线性一致性的定义图

图4 文献[1]，各种一致性的辅助定义图

文献[1]把LINEARIZABILITY（强）变种为两种情况（弱），如图5所示，一种是REGULAR一致性，一种是SAFE一致性。这两种情况的一致性，与LINEARIZABILITY的区别，主要在于图5所示的“公式(12)”的定义，其限制所发生的操作为“写-读”操作且此两个操作有序。这三者之间的差别，是写操作和读操作并发的时候，返回值可见的结果不同。

图5文献[1]，线性一致性的变种定义图

例如，如图6所示，PA写数据项，值分别写为1和2，PB和PC进程分别读PA所写数据项的值，在LINEARIZABILITY一致性下，PC进程读到的x值要么是0要么是1，即假设可满足同等情景时的多次读的结果只能是其一（多次/多个进程所读到的值一定是稳定的）；REGULAR一致性读到的x值要么是0、或1、或2；SAFE一致性x值可以是0、或1、或2中的任意值（如多次读所读到的值是不稳定的）。

图6文献[1]，三种线性一致性的类型示例图

顺序一致性

文献[2]最早提出了顺序一致性（Sequential Consistency）概念。文献[1]对顺序一致给出了严格的形式化定义，如图7所示，顺序一致性由三个部分构成，其中有两部分与线性一致性相同，本节不在赘述，而不同之处在于PRAM的定义，用会话内的顺序“so”作为约束条件限定了“vis”，即可见的结果应该满足会话内的顺序。

图7文献[1]，顺序一致性的定义图

顺序一致性，也是一种强一致性，因为其顺序在全局范围内确定（即满足会话内的序的同时，满足全局有序）。

因果一致性

文献[184]最早提出了因果一致性概念。文献[1]对因果一致给出了严格的形式化定义，如图8所示，因果一致性由三个部分构成：

1.CAUSALVISIBILITY：“hb”为 “happened-before”表示事件发生的偏序关系，即CAUSALVISIBILITY限制偏序的“vis”符合偏序关系的“hb”[2]。识别这个事件非常重要，示例如图2-10的左子图(a)中P2进程读取x的值a使得P1和P2在读取a值这个点和其后P2上写x的值为y这两个事件上构成偏序关系。

2.CAUSALARBITRATION：限制全序的“ar”符合偏序关系的“hb”。

3.返回值（RVAL(Ƒ)）：返回值属于一个预期的集合范围限定的值。

4.如上，“hb”事件发生的偏序关系表明了相关事件之间的因果关系，这对于定义因果一致性具有重要意义。

图8文献[1]，因果一致性的定义图

例如，具备因果一致的一个例子。如图9表示了具备因果关系的事件发生之间的关系。其中，PA和PB读写操作间的因果关系用虚线箭头表示，S1和S2是不具备因果关系的一个调度，因为对于S1而言，W5在W3的前面而不符合因果事件关系；对于S2而言，W6在W4前面不符合因果事件关系；S3和S4是具备因果关系的调度。

图9文献[1]，因果一致性的示例图

再如，如图10所示，左子图(a)中P2进程读取到了P1进程写x的结果值a，这个事件已经发生（a值应该位于b值之前的“happened-before”关系已经是事实这一事件），则在其后发生的事件要遵照此事件，即P3进程不应该先读取到x的b值之后又读到了x的a值，这违法了因果一致性（违反了“happened-before”）。而右子图(b)中进程P3和P4读取x的值的情况尽管和左子图相同，但是子图(b)中进程P2没有先发生读取到x的a值事件（a值和b值间不存在“happened-before”关系），所以没有可遵循的事件，尽管进程P3和P4读取x的值不同，但没有违反因果一致性。

图10 因果一致性和反例示例图

另外，文献[1]还给出了其他几种因果一致性的定义，详细内容请参考文献[1]。

会话一致性

文献[5][3]最早提出了“Session Guarantees” 概念，会话保证，本节称之为会话一致性。文献[1]认为，会话一致性包含四种情况（会话的含义是指发自客户端的连接请求所建立起的Server端进程），其重点都是操作间存在单调性（但此类系统通常情况下，期待最终一致性，如DNS、WWW pages），具体形式化定义参见图11：

1.Monotonic reads：单调读，如果一个会话进程成功读取了一个值v，则之后发生的其他读操作不会再读取到比v值还旧的值。比如，E-Mail系统需要符合单调读，从客户端A读过的邮件之后一定能被从客户端B再读取到。

2.Read-your-writes：读自己的写，同一个会话进程一定能够读取到自己写过的值。

3.Monotonic writes：单调写，同一个会话中的所有写以同样的顺序写到多个副本中。

4.   Writes-follow-reads：又被称为“session causality”，即同一个会话中，一个写操作发生后再发生的读操作，所读的对象值必是之前写操作影响的值。这意味着连续发生的先写后读在数据项上存在单调性。

5.“so”的含义为：session order，会话上的偏序关系。“vis”和“ar”参见图4。

6. 因果一致性可以包容本节的会话一致性，即因果一致性更“强”更趋于“一致”。

图11文献[1]，会话一致性的定义图

文献[1]还讨论了“Weak and Eventual Consistency”、“PRAM and Sequential Consistency”、“Synchronized Models”等内容，本书不再进一步展开，请参考原文。

脚注参考：

[1] 解决冲突后形成全序关系的方法有很多，文献[1]给出四种方式：a distributed timestamping （文献[3]） or consensus protocol（文献 [162]）, using a centralized serializer, or using a deterministic conflict resolution policy

[2] 文献[3]提出了一个happened-before模型，即“hb”，参加3.2节

[3] 文献[5]还提出了最终一致性（eventual consistency）

文献参考：

[1] Viotti P, Vukolić M. Consistency in Non-Transactional Distributed Storage Systems. ACM Comput. Surv., 2016, 49(1): 19:1-19:34.

[2] Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput., 28(9):690–691, September 1979.

[3] Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565 (1978)

[4] Maurice Herlihy and Jeannette M.Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463–492.

[5] Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike Spreitzer, Marvin Theimer, and Brent B. Welch. 1994. Session guarantees for weakly consistent replicated data. In Parallel and Distributed Information Systems (PDIS’94). 140–149.

扫码加关注，知数行云，专业有深度

声明：本文禁止用于开发“任何软件程序,包括但不限于训练机器学习或人工智能(AI)系统”。