《数据密集型应用系统设计》第9章-一致性与共识

共识

定义：所有节点就某一项提议达成一致。

最终一致性

定义：预期所有的副本最终会收敛到相同的值。这是一个弱保证，无法明确系统何时收敛。

可线性化

定义

让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。

性质

任何客户端的每个读操作必须返回最近写操作所设置的值。一旦新值被写入，所有后续的读看到的都是最新的值，直到被再次覆盖。如下图所示：

可线性化与可串行化的区别

可串行化(Serializability)：事务的隔离属性，用来确保事务执行的结果与串行执行的结果完全相同。

可线性化(Linearizability)：对单个对象的读写，提供其最新值的保证。并不要求将操作组合到事务中。

实现一个线性化系统

CAP理论

网络分区(P)情况下，选择一致性(C)还是可用性(A)。

因果关系与可线性化

全序关系

全序关系支持任意两个元素之间的比较，比如两个数字比较。但是数学集合之间无法比较，比如 $\{a,b\}$ 与 $\{c,d\}$ 之间无法直接比较，这种关系称之为偏序

可线性化是全序的

因为总是可以找到一个严格的全序操作序列，如上面的图9-3。

因果关系是偏序的

如果A事件Happens before B事件，则A、B事件可以排序，而对于并发操作，则无法比较。

由此可以推出：可线性化一定意味着因果关系，任何可线性化的系统都能正确的保证因果关系。

Lamport时间戳

定义

每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带上此值。当节点收到某个请求或者回复时，如果发现请求或者回复附带的最大计数器值大于节点自身的计数器值，则节点立即把更自身的计数器改为该最大值。如下图：

上图中，Client A从Node 2获取到计数器5，然后发送给Node 1，Node 1的计数器仅为1，于是Node 1将计数器更新为5。于是，下一个操作将获得计数器6

Lamport时间戳仍然不够

比如两个用户同时创建同名用户，我们期望时间戳较低的那个获胜。但是这样做的前提条件是：收集系统中的所有用户创建请求，而当节点刚刚收到用户创建请求时，它无法立即就做出决定，需要检查每个节点。此时就需要全序关系广播。

全序关系广播

定义

节点之间交换消息的协议，满足以下属性：

1. 消息不丢失，一旦消息发送到了某一个节点，则必须发送到所有节点。
2. 严格有序，消息总是以相同顺序发送给每个节点。
3. 不可回溯，消息发送成功，则不允许回溯地将某条消息插入到先前的某个位置。

可以将全序关系广播简单的理解为日志，比如replication log，而消息传递就是append only追加写日志。由于有序性保证，所有节点都会看到相同的日志序列。

原子提交

单节点的原子提交

依赖于数据持久化和写入磁盘的顺序关系：WAL，先写日志，再提交。

多节点的原子提交

1. 已提交事务的不可撤销性：因为一旦提交，就被其他事务可见，其他事务会基于此做出决策。如果撤销，则必会导致级联式的撤销。
2. 已提交事务，可以通过一笔新的事务来抵消掉，称之为补偿性事务。

两阶段提交

准备阶段 + 提交阶段

两点要注意的地方：

1. 参与者回答yes的时候，它做出了肯定提交的承诺，不可撤销。
2. 协调者做出了提交（放弃）的决定，同样也是无法撤销。

两阶段提交的缺点：协调者单点故障，一旦协调者挂了，参与者将陷入不知所措的状态。唯一方法就是等待协调者恢复。这也是为什么协调者在发送提交（放弃）决定前必须先写日志的原因，因为协调者重启时，必须读取日志来确定所有悬而未决的事务状态。

可以看到两阶段提交其实就是协调者在单节点上实现的原子提交。

三阶段提交

目的是为了解决二阶段提交中，一旦协调者挂了，参与者将陷入不知所措的状态的问题。它在准备和提交阶段中间加了一个预提交的阶段： 准备 + 预提交 + 提交。其目的也很简单：预提交后，此次事务是有很大概率可以成功的，所以哪怕预提交后，协调者挂了，参与者同样可以做出提交的决定。

关于两阶段提交和三阶段提交，可以看分布式系统的事务处理。

共识算法

1. 协商一致性，所有节点都接受相同的决议
2. 诚实性，所有节点不能反悔，对于一项提议不能有两次决定
3. 有效性，如果决定了某个值，则该值一定是某个节点提议的，这一点是为了防止原地空转，即什么决定都不做
4. 可终止性，节点不崩溃，则最终一定可以达成一致

投票

1. Epoch,纪元
2. quorum，法定票数

epoch大的节点获胜，然后从quorum节点中发起投票。所以实际有两轮选举，一是选举主节点，二是对主节点的提议进行投票。