分布式数据库原理、架构与实践
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

2.3　次序一致性

参考文献[26]给出了多种分布式一致性之间的关系，如图2-5所示。为满足这些一致性，需要对并发事件或消息排序，本书将这些需要排序的一致性称为次序一致性。次序一致性包括多种一致性，其中的线性一致性是最强的一致性。

058-1

图2-5　参考文献[26]定义的各种分布式一致性关系图

059-1

图2-5　（续）

下面基于2.1节对多种重要的一致性进行较为详细的讨论。

2.3.1　线性一致性

参考文献[183]最早提出了线性一致性（linearizability）的概念。参考文献[26]对线性一致给出了严格的形式化定义（见式2-1～式2-4）。线性一致性由3个部分构成。

  • 单一顺序（singleorder）：在符合vis和ar概念的基础上定义并发操作间的全序关系。vis表示结果的可见性关系，ar表示结果集的排序关系。就公式的数学含义而言，单一顺序表明；存在一个历史调度H'，相关操作（属于H的操作）的结果在其返回值返回之前（op.oval=∇），操作结果的可见性是在全序集合上去掉（去掉之意是“做集合差运算”，式2-2中使用“\”表示）该操作不可见的情况（即单一顺序强调最终结果的可见性和前后事件之间的顺序关系，事件之间的顺序关系是通过实际时间描述的）。
  • 实际时间（realtime）：见式2-3，其中rb为return-before，表示返回值的偏序关系，即实际时间限制全序的ar符合rb限定的偏序关系。请注意，此处没有刻意强调实际时间为物理时间，只是表明事件之间的“序”的关系（有的定义会把线性一致性和物理时间绑定，但这种方法不是必需的；但实际时间确实表示了一个与真实时间同步的顺序关系，即事件发生的真实序），顺序关系通过Ea-endtime < Eb-starttime来定义（每个事件都有开始时间和结束时间，事件a的结束时间小于事件b的开始时间，所以线性一致性把事件的整个生命周期与其他事件的生命周期串行化，而顺序一致性把会话内的结果串行化，两者存在不同，前者着眼于整个系统，后者落脚点在一个会话内）。
  • 返回值（RVAL(060-1)）：返回值属于一个预期的集合范围限定的值。式2-4表明对于任意的操作，返回值符合上下文的逻辑；对于多副本的系统暗含之意是副本间数据保持一致后返回一致的、在预期内的集合范围内的值。返回值被一致性的级别所限定。
060-2

式中：

  • vis是一种无环的自然关系，它解释了写操作的可见性。直观地说，a对b可见（即a−vis→b）意味着a的结果对调用b的进程可见（例如，b可以读取a所写的值）。如果两个写操作不是由vis排序的，那么它们彼此是不可见的。
  • ar是历史操作的全序，指定系统如何解决由于并发和不可见操作引起的冲突。在实践中，这种全序可以通过多种方式实现，比如采用分布式时间戳（由Lamport于1978提出）、采用共识协议（最早由Birman等人在1991年提出，后Hadzilacos和Toueg在1994进行了完善，2001年Lamport进行了进一步完善）、使用中心化的可串行化器或使用确定性冲突解决策略。

参考文献[26]把线性一致性（强）变种为两种新的一致性（弱），见式2-5～式2-8，一种是REGULAR一致性，一种是SAFE一致性。这两种情况的一致性，与线性一致性的区别主要体现于式2-7中，其限制所发生的操作为“写读”操作且这两个操作是有序的。这三者之间的差别是，在写操作和读操作并发的时候，返回值可见的结果不同。

060-3

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

061-1

图2-6　参考文献[26]中的3种线性一致性的示例

2.3.2　顺序一致性

参考文献[84]最早提出了顺序一致性（sequential consistency）的概念。参考文献[26]对顺序一致性进行了严格的形式化定义，见式2-9和式2-10。顺序一致性由3个部分构成，其中有两部分与线性一致性相同，本节不再赘述，不同之处在于PRAM的定义。顺序一致性用会话内的顺序so作为约束条件限定了vis，即可见的结果应该满足会话内的顺序要求。

061-2

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

2.3.3　因果一致性

参考文献[184]最早提出了因果一致性的概念。参考文献[26]对因果一致性进行了严格的形式化定义，见式2-11。因果一致性由如下3个部分构成。

  • CAUSALVISIBILITY：hb（happened-before）表示事件发生的偏序关系，即CAUSALVISIBILITY限制偏序的vis符合偏序关系的hb[1]。识别这个事件非常重要。
  • CAUSALARBITRATION：限制全序的ar符合偏序关系的hb。
  • 返回值（RVAL(061-4)）：返回值属于一个预期的集合范围限定的值。

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

061-3

式中：

  • 061-5
  • 061-6

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

062-1

图2-7　参考文献[26]中的因果一致性示例

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

062-2

图2-8　因果一致性和反例示例图

另外，参考文献[26]还给出了其他几种因果一致性的定义，有兴趣的读者可自行学习。

2.3.4　会话一致性

参考文献[185][2]最早提出了会话保证（Session Guarantees）的概念，本节称之为会话一致性。2.3.3节介绍的因果一致性可以包容本节的会话一致性，即因果一致性更“强”、更趋于“一致”。参考文献[26]认为，会话一致性包含4种情况（会话是指发自客户端的连接请求所建立起的服务器端进程），且重点都是操作间存在单调性（此类系统通常情况下都会期待最终一致性，如DNS、网页），具体形式化定义见式2-12～式2-15，对式中涉及的部分重点内容说明如下。

  • MONOTONICREADS：单调读，如果一个会话进程成功读取了一个值v，则之后发生的其他读操作不会再读取到比v值还旧的值。
  • READYOURWRITES：读自己的写，同一个会话进程一定能够读到自己写过的值。
  • MONOTONICWRITES：单调写，同一个会话中的所有写以同样的顺序写到多个副本中。
  • WRITESFOLLOWREADS：又称session causality，即同一个会话中，在一个写操作发生后发生的读操作，所读到的值必是之前写操作影响的值。这意味着连续发生的先写后读在数据项上存在单调性。
  • so的含义为session order，即会话上的偏序关系。
063-1

[1]参考文献[178]提出了一个happened-before模型，即hb，参见3.2节。

[2]参考文献[185]还提出了最终一致性（eventual consistency）。

上一章目录下一章