Raft协议

在分布式系统中一致性是很重要的。1990年Leslie Lamport提出基于消息传递的一致性算法 Paxos 算法，解决分布式系统中就某个值或决议达成一致的问题。Paxos 算法流程繁杂实现起来也比较复杂。

2013年斯坦福的 Diego Ongaro、John Ousterhout 两个人以易懂为目标设计一致性算法Raft。Raft一致性算法保障在任何时候一旦处于leader 服务器当掉，可以在剩余正常工作的服务器中选举出新的Leader服务器更新新Leader服务器，修改从服务器的复制目标。

概念

复制状态机 (Replicated state machines)

• 将集群中的每个服务器看做一个状态机，它们接收外部的指令，进行状态的改变，例如机器的存储器就可以看做是一个状态机。不考虑硬件错误，这样的状态机是一个确定型状态机，即只要初始状态和接收到的指令是确定的，那么它任意时刻的状态也是确定的, 这样以来，所谓保持分布式一致性即是保证集群中所有状态机的状态一致性。

角色：领导人 (leader)、跟随者 (follower) 和候选人 (candidate)

• 所有服务器结点划分为 3 种角色：leader、follower、candidate。一旦 follower 在给定的时间内没有收到来自 leader 的心跳包，它便认为 leader 出了故障, 于是转变自己的身份为 candidate 进行领导人的竞选

任期 (term)

• raft 将系统时间划分为一个个任期 term，每一个任期都设置一个整型编号，称为任期号。每一个任期可以进一步划分为两个子段，其中第一个子段是选举期，第二个子段是任职期。选举期将竞选产生集群的领导人，若领导人选举成功，则进入了任职期，在任职期内只要领导人持续保持健康状态（即持续不间断地向其他跟随者发送心跳包），则这个任期可以无限期地持续。当然选举不一定都是成功的，可能存在没有任何候选人胜出的情况，这样会进行下一个任期，重新进行选举。raft 采用了特别的机制来尽可能地避免一个 term 中没有任何候选人竞选成功的情形出现

日志 (log) 与日志复制 (log replication)

• 在 raft 协议中，指令是以日志的形式的传递的，虽然集群中有 N 个结点, 但只有一个 leader 结点接收客户端的请求（注意 raft 本身是不涉及主从分离的，主从分离实现是业务代码实现的事）。其它所有结点接收来自 leader 的复制日志 Replicated log，从而进行状态的变更，所有服务器结点按序执行相同的日志，从而保持状态一致性

日志提交 (commit)

• leader 在接收到客户端请求之后，会产生一个相应的日志项 log entry，leader 不会立即执行这个指令，而是先会进行日志项复制，当日志项被成功地复制到集群中 半数以上 的结点后，领导人才会提交这个日志项，并执行其中的指令

Raft一致性算法

Raft 将一致性问题分解为了3个子问题：

1. leader 选举：leader 挂掉时，选一个新 leader，选举算法

2. 日志同步：leader 在时，由 leader 向 follower 同步日志

3. 安全性：确保每一个状态机都以相同的顺序执行相同的指令

1. 主节点选取 Leader Election

• 当 follower 超过特定的时间没有收到 leader 的心跳之后， follower 将变为 candidate，发起新一轮选举

• 选举投票依据三个变量：任期（选主轮数）、数据同步进度（日志索引偏移量）、随机超时时间

  • 每个结点拥有一个 currentTerm 变量，表示了当前的任期号，或者说选举轮数。发起选举时 follower 会将自己的 currentTerm 变量加一，然后向中其它结点发送投票 RPC 请求。同时它也会将自己的选票投给自己，当候选人收到了过半选票时便选举成功

  • 为了避免多个节点都发起选举、大家票数一样的情况，每轮选举都有超时时间，且每个点的超时时间都是随机的

  • 这样先超时的点将先进入下一轮选举，currentTerm 就更大。其他 candidate 碰见更大的任期将放弃参选

• follower 会拒绝 term 比自己小的 master 的数据，避免脑裂

2. 日志复制 Log Replication

• raft 将日志组织成线性结构，日志是由日志项串联而成的，同时会有一个索引来标识每一个日志项的相对位置

• 主节点接收到命令后，写入日志，同步给从节点。收到半数以上 ACK 时，才提交

• 每一个日志项可以用一个二元组来表征：

log entry := (term_number, command)

• 领导人对所有的跟随者维护了一个 nextIndex 列表，记录下一个同步给 follower 的进度

• 如果因为选主导致从节点同步进度滞后，从节点将会拒绝新数据，主节点会不断补发旧数据，直到追上进度为止

• 如果主节点落后于其他从节点呢？参见下面

3. 安全性约束 Safety

1. 领导者追加日志

1. 领导者永远不会覆盖已经存在的日志条目

2. 日志永远只有一个流向：从领导者到追随者

2. 选举限制：投票阻止没有全部日志条目的服务器赢得选举

1. 为了保证主节点进度不落后于其他从节点的情况，raft 限制那些进度落后的候选人，不允许成为新的领导人

2. 节点发起投票请求时，会带上自己最新的日志的索引和任期，收到该请求的结点会检查自身的日志是不是比候选人的更新

3. 永远不提交任期之前的日志条目（只提交任期内的日志条目）

1. 领导人不允许直接提交任期号为之前任期的日志

4. 候选者和追随者崩溃

1. 主向从同步数据时，可能因为节点挂了、网路波动收到不到从的回复

2. raft 的应对方案是简单的无限重试，为此需要保证结点之间信息传递的幂等性。比如直接忽略已处理的日志

4. 集群成员变更 Cluster Membership Changes

• 直接从一种配置转到新的配置是十分不安全的。可能会有的节点转新失败。raft 采用了两阶段提交的方案

• 首先当集群要进行扩容或缩容时，需要向领导人发送配置变更请求

• 领导人收到请求后会将旧配置和新配置取并集 C，形成一个过渡配置，然后将该配置作为一个日志项广播给集群中的所有其它结点

  • 只有收到 C 的节点才有资格参与选主

• 领导人会再生成一个新的日志项, 该日志项中只含新配置，作为第二阶段的提交

上面的论述仅仅解决了更新配置过程中的安全性问题，但还有一些性能问题需要进一步分析。

1. 首先第一个问题是当集群中有新结点加入的时候，它的历史日志是空的，因为可能需要耗费很久的时间来追日志

   1. 因此新节点加入后只同步主节点，不参与竞选。直到追平后才变为正常节点

2. 领导人可能被下线，即领导人不在新配置中

   1. raft 会把它变为从节点。由于系统没有领导人，所以一段时间之后会自发启动领导人选举，进而产生新配置下的领导人

3. 更新配置之后，某个结点可能不在新配置中了，但如果它没关机，收不到心跳会触发选举，扰乱集群

   1. raft 规定如果从节点能正常收到主的心跳，则无视其他点的选举请求

   2. 被下线的节点收到新配置、发现自己被下线后，应停止发送数据

日志压缩

日志会随着系统的不断运行会无限制的增长，这会给存储带来压力，几乎所有的分布式系统(Chubby、ZooKeeper)都采用快照的方式进行日志压缩，做完快照之后快照会在稳定持久存储中保存，而快照之前的日志和快照就可以丢弃掉。

Client交互

1. Client 只向 leader 发送请求；如果向非 leader 发送请求，会被拒绝并重定向到 leader 节点

2. Client 请求失败，会超时重新发送请求；

Raft 算法要求 Client 的请求线性化，防止请求被多次执行。有两个解决方案：

1. 每个请求有个唯一标识；

2. Raft 的请求保持幂等性；

Raft 协议应用

• redis 选主（采用了类似的做法，但不是直接应用 raft

  • redis 哨兵/集群模式下半数节点将主标记为客观下线才会触发选主，这和 raft / ZAB 一个从节点连不上就触发选主不同

• kafka 2.8 抛弃了 zk，改用 raft，实现了个叫 kraft 的

  • zk 选举时整个集群不可用。一般选举很快，但也有慢的情况，例如碰上 FullGC

• 分布式数据库：TiDB

• 服务发现：Consul、etcd

和 Paxos 区别

• Paxos 侧重于大方向上理论，实现方案各家都不同。Raft 作者包含了很多细节，都有伪代码了。

• Raft 中，leader 必须存有全部 commited 的日志。Paxos 则不一定，节点即使不包含所有日志也可能选上 leader，选上后再靠别的机制补日志。

参考

论文原文

论文译文

牛吃草-Raft协议原理详解

raft算法与paxos算法相比有什么优势，使用场景有什么差异？

孙同学 - Raft 一致性协议完整解析

何约什 - Raft一致性算法笔记