分布式系统理论：共识算法raft

2020, Mar 24    

在分布式系统中，其实有两种共识算法比较常见，一种是今天要分析的Raft算法，另一种是最出名的Paxos算法。相对来说，Raft算法比较容易理解，也比较好 实现，因此在真实世界中，其应用要比Paxos算法广泛，比如etcd、Kudu等就利用了Raft算法。而Paxos算法唯一比较被熟知的实现是其变种–Zookeeper中 用到的zookeeper atomic broadcast算法(ZAB)。

在实现上，Raft将复杂的分布式共识问题拆分为了leader election、log replication和safety三个子问题，并分别予以解决；另外，它还对状态空间进 行压缩，减少因状态过多引入的不确定性。

在共识算法中，所有的服务节点都包含一个有限状态自动机，也就是复制状态机。每个节点都维护着一个复制日志队列，复制状态机按序输入并执行该队列中的 请求，执行状态转换并输出结果。如果能够保证各个节点中日志的一致性那么状态机的状态转换和输出也就都一致。其执行过程如下：

  • 某个节点的共识模块(包含共识算法的实现)从客户端接收请求;

  • 共识模块将请求写入自身的日志队列，并与其它节点的共识模块交互，保证每个节点的日志都相同;

  • 复制状态机处理日志中的请求;

  • 将输出结果返回客户端;

我们知道，如果集群中超过半数的节点可用时，就能正确的处理分布式事务，因此在共识算法中的集群几乎总是使用奇数个节点(偶数个浪费机器资源且可能产生 脑裂)，使用ZAB协议的zookeeper集群也是这样。

在Raft中，任意节点只能处于leader、follower、candidate三种状态之一，每个节点都有一个倒计时器，时间随机在150ms-300ms之间，只有在收到选举 请求或收到leader的心跳时才会重置这个倒计时时间。在集群启动时，所有的节点都是follower节点，如果follower在经过这个倒计时时间之后发现仍然没有 leader节点，就会切换为candidate节点并发起选举，如果得到超过半数票数就会成为leader节点。如果发现了更新的leader节点，原leader节点就会重新 变为follower节点。leader节点负责从客户端接收请求，复制到follower节点，并告诉follower节点何时可以处理请求。如果leader节点故障或失联则会 重新进行选举。由此可见，leader节点是大家投票选出来的，每个leader工作一段时间，然后选出新的leader继续负责，因此每个leader都有履职期也叫做 任期term。任期从选举开始，然后经过一段或长或短的稳定工作时期，且任期是递增的，这样才能发现更新的leader节点。此外也可能没选出leader就结束了， 就需要发起新的选举。

上面提到过，如果follower在选举超时时间内没有收到leader的心跳，就会主动发起选举。具体过程如下：

  • 增加节点本地的当前任期，并切换到candidate候选者状态;

  • 投票给自己;

  • 并行的给其它节点发送请求投票的RPC请求;

  • 等待其它节点的回复;

根据其它节点的回复内容不同，可能出现三种情况：

  1. 包含自己的票数在内收到了超过半数的投票，赢得选举，称为leader;

  2. 被告知已有别的节点当选为leader，重新切换为follower;

  3. 一段时间内仍未收到超过半数的投票，也没有其它节点当选，保持candidate状态，重新发起选举;

对于第一种情况，如果赢得选举则会立即给其它节点发消息以避免重复选举，那么选举到底如何进行呢？在一次选举中，每个节点最多只能投一票，并且投票先到 先得，也就是谁最先给该节点发请求投票的RPC请求，该节点的票就会投给谁；对于第三种情况，为了避免同时有多个candidate而出现平票现象，Raft引入了随 机选举超时机制，也就是超时时长较短的节点会最终赢得选举。

在选举出leader节点后，就会开始处理客户端请求，客户端的所有请求都会发送给leader，并由leader调度这些请求的顺序，保证leader和follow状态的一致 性。Raft会将请求及请求的顺序告知follower，并以相同的顺序来执行请求，保证状态一致。在Raft中，leader将客户端请求封装到了一个个的log entry中， 再将这些log entries复制到所有的follower节点，以相同的顺序执行这些log entry中的命令，以保证状态一致。从leader节点的视角来看，请求的完整流程 如下：

  • leader节点收到来自客户端的请求，将请求封装到log entry;

  • leader节点并行的发送AppendEntries RPC请求，并等到follower的响应;

  • 当收到大多数的回复后，将请求应用到复制状态机，并通知follower节点也应用请求;

这个过程与两阶段提交(2PC)有点类似，但是Raft只需要大多数节点的确认，而不像2PC需要全部节点的确认。此外，由于网络等原因，leader节点和follower 节点的日志并不完全相同，但leader节点会不断重发AppendEntries RPC请求，直到所有节点的日志都达到一致以保证最终一致性。

分布式系统中可能面临着各种复杂的情况，在这样复杂的环境中，如何保证日志的最终一致性呢？ Raft协议保证以下五种属性：

  1. 选举安全性(election safety)：每个任期内只允许选出最多一个领导，如果集群中有多于一个领导，就发生了脑裂(ES中常见的一种异常情况)。Raft中 通过：一个节点在一个任期内最多只能投一票和只有获得多数票的节点才能称为leader节点保证了这个属性;

  2. 领导者只追加(leader append-only)：客户端发出的请求都是插入领导者日志队列的尾部，没有修改或删除的操作;

  3. 日志匹配(log matching)：如果两个节点的日志队列中，某两个log entry具有相同的下标log index和任期值term，那么它们携带的客户端请求以及 它们之前的所有的log entry都相同。Raft中通过：领导节点只追加和每条AppendEntries都会包含最新entry之前那个entry的下标与任期值，如果跟随节 点在对应下标找不到对应任期的日志，就会拒绝接受并告知领导节点;

  4. 领导者完全性(leader completeness)：如果有一条日志在某个任期被提交了，那么它一定会出现在所有任期更大的领导者日志里。Raft中通过：一个 日志被成功复制到大多数节点才算是提交和一个节点只有得到大多数节点的投票才能称为leader，而节点B投票给节点A的前提之一是节点A的日志必须比节点B 的日志更新;

  5. 状态机安全性(state machine safety)：如果一个节点已经向其复制状态机应用了一条日志中的请求，那么对于其他节点的同一下标的日志，不能应用 不同的请求。Raft不允许领导者在当选后提交”前任”的日志，而是通过日志匹配原则，在处理”现任”日志时将之前的日志一同提交。具体方法是：在领导者任 期开始时，立刻提交一条空的日志，并同时将”前任”的日志提交;