0. 前置：Lamport时间戳获取锁

给send和recv事件打时间戳的原理见：这里。

根据Lamport时间戳维护因果序原理，可实现分布式锁，原理见：这里。

但算法不能容错，不过却是分布式共识算法的鼻祖。

1. 共识的使用场景

共识算法常用于以下几个场景：

• 主节点选取：主从复制的数据库中，所有节点需要就谁当主节点达成一致。

• 原子事务提交：所有节点必须对事务的结果达成一致，要么全部提交，要么全部回滚。

2. 原子事务提交

2.1. 2PC

2PC是一种共识算法，实现多节点之间的事务原子提交。

2PC引入一个新组件：协调者（事务管理器，可嵌入请求事务的进程中，也可以独立成为一个服务）。协调者负责向节点读写数据，并负责事务提交。

2.1.1. 执行过程

1. 应用启动分布式事务时，向协调者请求事务ID（全局唯一）；
2. 应用在相关节点执行单节点事务，请求会捎带事务ID（若执行失败，协调者和其它节点都能回滚）；

3. 应用准备提交事务：

   • 协调者在日志上记录PREPARE，向其它参与者发送准备请求
   • 参与者收到准备请求，根据自己情况
     • 若OK，则日志记录READY，返回结果给协调者
     • 否则，日志记录NO，返回结果给协调者
   • 协调者收到所有参与者的消息
     • 若全部READY，则提交事务，日志记录COMMIT，并向所有参与者让它们提交事务
     • 否则，回滚事务，日志记录ABORT，并向所有参与者让它们回滚事务
   • 参与者收到提交/回滚消息，日志记录COMMIT/ABORT，响应给协调者
   • 协调者返回给客户端

2.1.2. 协调者故障

若日志没有PREPARE：回滚事务

若日志有了PREPARE但没有COMMIT/ABORT：重新向参与者发送准备请求，然后按正常的2PC规则执行下去

若日志有了COMMIT：重放日志并提交，直到成功为止

若日志有了ABORT：重放日志并回滚，直到成功为止

2.1.3. 参与者故障

若日志有了READY：重放日志，并向协调者询问是否提交，若协调者故障，需要等待

若日志有了NO：重放日志并回滚

若日志有了COMMIT：重放日志即可

若日志有了ABORT：重放日志并回滚

若什么都没有：重放日志并回滚，并向协调者告知，协调者可通知其它参与者回滚事务

2.2. 3PC

3PC是非阻塞的，流程可简化成下图：

然而，3PC假定网络延迟有界，且节点在一定规定时间内可做出响应（因为大量运用超时，而用超时检测故障是不可靠的），而在实际情况下不可行，因此不能保证原子性。

通常非阻塞原子提交依赖一个完美的故障检测器，而超时检测不完美。

3. 实践中的分布式事务

3.1. Exactly-once

需要有：

• 可无限的重试次数；
• 重复检测；
• 服务可容错。

采用分布式事务也是可行的，但是系统的相关部分必须使用一样的原子提交协议。

3.2. XA事务

一个与事务协调者通信的API，协调者需要实现该API（跟踪事务、协调参与者等）。通过XA API，应用（DB、MQ等）和协调者共同完成一个分布式事务。

而XA事务底层的算法通常是2PC。

3.3. 停顿时仍持有锁

分布式事务中，尤其2PC，协调者失效时，参与者可能停顿，锁不释放，导致整个系统停顿（不可用）。所以，停顿的事务需要及时清理。

3.4. 从协调者故障中恢复

当协调者日志损坏，就难以恢复，参与者就永远阻塞。解决方式有：

• 手动回滚/提交
• 破坏2PC协议的一部分，强制放弃/继续停顿的事务，不需要协调者的指令（启发式决策）

3.5. 分布式事务的限制

• 若协调者是单点，易造成系统的单点故障，而集群的协调者难以高可用；
• 协调者的日志让服务不再是无状态的；
• XA的兼容性标准低，功能少；
• 2PC潜在限制：要求所有都同意才能提交，不符合容错系统的目标。

4. 支持容错的共识

共识算法的性质：

• 协商一致性：所有节点都接受相同的决议；
• 诚实性：所有节点不能返回，对某项决议不能有多次的决定（即不重复且不能不同）；
• 合法性：若决定了值$v$，那么该值一定是由某个节点提议的；
• 可终止性：集群中存在不崩溃的节点，则最终一定能达成协议（通常是大部分节点存活下）。

共识算法不建立在拜占庭错误假设下。

4.1. 共识算法和全序广播

共识算法包括：VSR，Paxos，Raft，Zab。算法相似，但不完全相同。后面我会详细整理Raft的论文，说明Raft的原理。

总体上讲，它们是决定了一系列值，然后采用全序关系广播算法。

4.2. 主从复制与共识——Epoch & Quorum

许多共识算法采用一种弱化的保证：定义一个世代（Epoch）编号，保证在该世代里，主节点唯一。

过程：

• 主节点失效，节点开始选举新节点，每次选举会赋予一个递增的epoch号

• 若出现2个不同主节点对应不同的epoch号，则epoch更高的获胜

  主节点做出决定前，要检查是否有更高的epoch编号。

  主节点可通过quorum知道自己是否被取代。

  节点会记录收到的最大的epoch，不会对小于该epoch的提议进行投票quorum。

实际上，存在两轮投票:

• 投票选举主节点
• 对主节点的提议投票（带有epoch）

两轮quorum必须重叠（重叠部分若过程中没出现更高的epoch，则得出结论——主节点没变，可安全地对该提议投票）

4.2. 共识的局限性

• 它是同步复制过程，性能不高；
• 需要严格的多数节点才能运行，网络分区会让少数节点处于停顿状态；
• 多数不能动态添加/删除节点；
• 依赖超时机制，若配置不当容易造成频繁主节点的选举，降低可用性；
• 对网络问题敏感（如Raft在边界条件下反复切换主节点）。

5. 成员与协调服务——ZooKeeper

ZooKeeper特性：

• 实现共识算法（Paxos）和全序广播，从而实现了线性化存储（
• 线性化原子操作（因此ZooKeeper的CAS可以用于实现分布式锁，可参考这里）
• 操作全序（实现了Fencing令牌，每次操作都全序排序，赋予递增的zxid和cversion）
• 故障检测（维护会话，并通过心跳互相检测是否存活，若长时间心跳停止，则终止会话，会话持有的资源，即临时节点，可自动释放）
• 更改通知（客户端可通过订阅机制，监听键值的变化，因此可以知道其它客户端何时加入/离开集群，加入/离开可通过向ZooKeeper写入临时节点实现）

5.1. 节点任务分配

可借助ZooKeeper的CAS，临时节点和通知机制实现。（如负载平衡，作业调度，自动故障恢复等）

5.2. 服务发现

节点只要向ZooKeeper注册（临时）节点即可，其它人只要向ZooKeeper询问即可。

5.3. 成员服务

ZooKeeper可看作成员服务的一部分。成员服务用来确定哪些节点处于活动状态并属于集群有效成员。

• Previous
  DDIA-一致性与共识（顺序保证）
• Next
  论文阅读-Raft-1