顺序一致性(Sequential Consistency)
在强度上,线性一致性(linearizability consistency) > 顺序一致性(Sequential Consistency)
“ 线性一致性就是以顺序一致性为基础定义的。 顺序一致性在1979年提出,线性一致性则是1987年在顺序一致性的基础上增加了约束得来的。
顺序一致性(Sequential Consistency)提出了两个约束:
- 单个节点的事件历史在全局历史上符合程序的先后顺序
- 全局事件历史在各个节点上一致
如果在系统中找不到任何一个符合上述两个约束的全局事件历史,则说明该系统一定不满足顺序一致性;如果能找到一个符合上述两个约束的全局事件历史,这说明系统在这段过程内是满足顺序一致性的。
这个约束描述起来可能让人不明所以,我们整个实例解释一下:
首先介绍一下例子:在分布式场景下,假设有A,B,C 三个节点,初始值为x=0,y=0,各个服务在对应节点的上的运行情况,并在某个时刻完成了该操作。注意先执行的不一定先完成,但同一节点是有顺序的。
上面的图不满足顺序一致性。推导一下逻辑关系来解释说明一下:
- 当B2 读出 y=3 时,意味着从全局执行角度来看 (下文称为全局) ,A2在B2之前执行 。
- 记作 A2 -> B2
- 当B3 读出 x=0 时,从全局中理解为,B3在A1之前执行。
- 记作 A2 -> B2,且B3 -> A1
- 节点A的记录决定了 A2 在 A1 后执行
- 记作 B3 -> A1 -> A2 -> B2
- 节点B 的执行顺序又决定了B2 在B3 之前
- 记作B3 -> A1 -> A2 -> B2,且B2 -> B3
显然不存在一个全局历史能够将A1、A2、B2、B3排列起来,且满足上面的各个排序要求。
而下图所示的事件是满足顺序一致性的。
这个图,我们能够找到满足以上约束的全局历史,例如:
- B1 -> B2 -> A1 -> B3 -> A2 -> C1 -> C2
- B1 -> A1 -> B2 -> B3 -> A2 -> C1 -> C2
- B1 -> A1 -> C1 -> B2 -> A2 -> C2 -> B3
如果一个系统的工作中,其全部事件都能满足顺序一致性,那这个系统就满足顺序一致性。
但在用户角度来说,在对精度要求较高的情况下:不管有几个进程,几个节点,我们要求 进程(节点) 内部的操作要符合全局时钟的要求,即不能发生违背全局时钟的行为。而顺序一致性只要求符合进程间顺序执行即可。
引入全局时钟的概念,则顺序一致性将变为线性一致性。
在满足顺序一致性的基础上,顺序一致性只要求我们满足进程间的执行顺序即可,对全局时钟的顺序不作要求;若进一步的满足了全局时钟的要求,则是线性一致性。