Raft | BN Stack

简介

Raft 是分布式一致性协议 Paxos 的一个变种，最早是在 2013 年由斯坦福大学的 PhD 学生 Diego Ongaro 和他的导师 John Ousterhout 在论文“In Search of an Understandable Consensus Algorithm”中提出。根据论文中的介绍，其主要目的就是为了阐述一种易于理解的分布式一致性算法，把易于理解放于作为最主要的目标，因此，借于 Raft 协议的易于理解的特性，这篇论文得到了大量的赞誉和推崇。目前，基于 Raft 协议所产生的变种协议也很多（比如：Multi-Raft 等），而在工业界，基于 Raft 原理所实现的一致性协议更是得到了广泛的应用（比如 etcd）。

Raft 协议天生简单而易与理解，这篇文章我将根据其原始论文来详细解读 Raft 协议，由于是采用论文导读的方式，因此我会大量引用论文原句来进行解析。

Raft 协议

一个 Raft 集群包含若干个服务器节点。假如服务器节点数为n个（n通常是>=3的奇数），这允许整个系统容忍个(n-1)/2节点的失效。

Raft 协议的理论部分主要分为三个方面：

Leader Election
Log Replication
Safty

1. Leader Election 领导者选举

Raft 把时间分为terms. 每一个 term 开始时都进行一次选举. 每一个 term 期间最多有一个leader, 或者没有 leader。

Raft servers communicate using remote procedure calls (RPCs), and the basic consensus algorithm requires only two types of RPCs.

(1). RequestVote 由 Candidate 在选举期间发起
(2). AppendEntries 由 Leader 发起，用于 replicate log entries 和发送心跳

还有一个 RPC 请求，作用是在节点之间传输快照信息（transferring snapshots between servers）。
并发的重试 RPC 请求 Servers retry RPCs if they do not receive a response in a timely manner, and they issue RPCs in parallel for best performance.

Leaders send periodic heartbeats (AppendEntries RPCs that carry no log entries) to all followers in order to maintain their authority.

Followers only respond to requests from other servers.
If a follower receives no communication in a period of time (e.g. 150ms - 300ms), it becomes a candidate and initiates an election.
If a follower receives no communication over a period of time called the election timeout, then it assumes there is no viable leader and begins an election to choose a new leader.

(1) 选举过程

先把自己的 term ID 加1，然后从 Follower 状态变为 Candidate 状态，每个 Candidate 都会获得一个随机的 term timeout 在 150 到 300 ms 之间。
当一个 Candidate 在 Timeout 到期前收到了大多数人的 Votes，就赢得这次选举。每个 Candidate 在自己的 term 期间只能 vote 一票，先收到谁的 request 就先投票给谁。
一旦一个 Candidate 赢得选举，它就开始发送心跳信息给其他所有 servers 来维持统治。

在选举期间，Candidate 可能会收到其他也宣称是 leader 的 Server 发来 AppendEntries rpc 请求。
如果这个 rpc 请求中所附的 term id 大于等于当前 Candidate 的 term id，那么认为那个 leader 是合法的，并立即把自己置为 Follower 状态。
如果这个 rpc 请求所附的 term id 小于当前 Candidate 的 term id，那么就拒绝那个请求，并把自己继续维持在 Candidate 状态。简单来说，Term ID 越大表示状态越新。

(2) 选举结果

如果没有任何节点赢得当前 term 的选举（这种情况可能会在很多 followers 同时变成 candidates 时发生，因为 votes 可能被 split（平分），导致没有 candidate 赢得多数票），
这种情况发生的时候，每个 candidate 都会 timeout（随机 Timeout 值），并且开始一轮新的选举：把自己的 term id 加1，发送新的 RequestVote RPCs。
Raft 使用了一个随机的 timeout 时间 150 ms - 300 ms，这样可以在大多数情况下，选举失败时只有一个 server 会 timeout。

2. Log Replication

选举结束之后，Leader 就开始接受 Clients’ requests。
Leader 每接受一个 request，就在 Log 中写一条记录（appends the command to its log as a new entry, then issues AppendEntries RPCs in parallel to each of the other servers to replicate the entry.）。
一旦 log entry 被安全的 replicated，leader 就 applies the entry to its state machine and returns the result of that execution to the client. 如果这时候 follower 崩溃了，那么 leader 会无限地发送 AppendEntries RPC 请求。

Log 的格式：
Each log entry stores a state machine command along with the term number.
Each log entry also has an integer index identifying its position in the log.

什么时候认为 log 是 commited 的呢？
A log entry is committed once the leader that created the entry has replicated it on a majority of the servers
一旦当前这条 log 被认为是 commited，那么这条 log 之前记录的所有 log 都会被 commited，包括由其他 leader 所记录的 log。

如何消除 leader 的 log 和 follower 的 log 不一致的情况？

log 的 index 是按照数字从0开始顺序递增的，下一个将要插入的 log entry 的位置称为 nextIndex。
当一个新 leader 即位之后，他会发送 AppendEntries RPC Check 来检查 follower 的 log entry 是否跟 leader 的一致，
如果不一致，那么 follower 会 reject。然后 leader 会递减当前 index 然后继续发送 check，直到两者一直，然后 Leader 就把从该一致点的 index 到后面所有的 log entries 都发送给 follower，覆盖 follower 后面所有的 log entries，从而保证 leader 和 follower 的 log entries 一致。

一步一步递减 index 的方式可能会导致大量的 rejects，非常低效。如何减少被 reject 的次数？
Leader 发送 AppendEntries RPC check 时，带上 term Id 和这个 term 期间的第一条 log 的 index。这样的话就可以一次性跳过整个 term 的 entries。

注意：Leader 永远不会覆盖或者删除自己的 log entries。

3. Safety

安全性的意思是指一致性协调的最终结果必须是有效的，并且在所有节点都能达到一致的结果。
虽然前面描述了 Raft 算法是如何选举和复制日志的。然而，到目前为止上面所描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。

例如，一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目；因此，不同的状态机可能会执行不同的指令序列。

针对这种情况，Raft 使用了一种简单的方法，它可以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的领导人中，不需要传送这些日志条目给领导人。

这意味着日志条目的传送是单向的，只从领导人传给跟随者，并且领导人从不会覆盖本地日志中已经存在的条目。

下面就具体分析几个例子来阐述 Raft 协议为何能在各种情况下都保证 Safety。

（1） Leader Crash

可能出现的情况，leader crash 之后，new leader 不包含前一个 leader 所有的 commited entries，从而导致不一致。

Raft 提出了一些 restriction 去保证 new leader 包含上一个 leader 所有的 commited entries。
The restriction ensures that the leader for any given term contains all of the entries committed in previous terms
把这个 restriciton 称为：Leader Completeness Property。

Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries.
一个 Candidate 要想选举成为 new leader，那么它必然需要联系大多数 servers，那么至少有一个 server 会包含所有的 commited entries。
如果这个 Candidate 的 log 比这个 marjority 中所有的 server 的 log 都要新，那么它就包含了所有的 committed log entries。

这个 restriction 的具体流程就是：
Candidate 发送 RequestVote RPC 时会把自己的 log 信息附上，收到请求的 server 会检查 log 是否比自己当前的 log 更加 up-to-date，如果不，则否决，反之同意。

如何判定两个 log 谁更 up-to-date？
比较 last entry 所在的 term id 以及 index。

当 leader crash 时，还有可能出现的一种情况是：

根据 raft commit 原则，只有当 log 被大多数 server 确认 replicated 之后，才认为可以 commit了，这时候 leader 才会 apply。如果在 apply 之前正好 crash 了。那么就会出现如上图所示的情况。
如果所示，S1 是 Term T 的 leader，称之为 leader T，当它 crash 时，log entries 已经 replicated 到了大部分节点中（s1, s2, s3）
这时候 S5 参加选举，在 term U 中被选举为 new leader，我们称之为 leader U。

这时候有一个关键信息，S5 需要获得多数 server 才有可能成为 leader，那么必然包含一个 server，这个 server 有上次 committed log 信息。比如上图中的 S3 节点。
而且，这个 committed log entry 必然在它同意投票给 S5 之前发生，因为只有这样它（S3）的 term id 才不会大于 S5 的 term id，如果 S3 的 term id 大于 S5 的，必然会拒绝 S5 的 RequestVote RPC。

这里有个矛盾的地方就是，new leader 必须包含所有 up-to-date 的 entry，而 S5 却比 S3 少了一个 log entry (AE)。
所以，显然，S5 不可能被选举为 leader。这就保证了上述的 Leader Completeness Property 的正确性。也即 Safty 得到了保证。

（2） Candidate or Follower crashes

这种情况比 leader 发生 crash 要简单很多，follower 和 candidate（采用的是相同的处理方法）一旦 crash，其他 server 会 indefinitely 发送 RequestVote 或 AppendEntries 给它。
如果 crash 的 server 重启了，那么 RPC 请求就能够完成。
如果 Follower 成功收到 RPC 请求, 但是在其 respond 之前 crash 了，那么它重启之后还会收到相同的 RPC 请求。
根据论文所述，由于 Raft RPC 是幂等（idempotent）的，因此这种情况下的 crash has no harm。Safty 不会被违背。

Timing and Availability

Cluster MemberShip changes

4. Log Compaction

In a practical system, it cannot grow without bound. As the log grows longer, it occupies more space and takes more time to replay.
log 太多最终会导致 avaliability 问题，必须要想办法丢弃那些过时的 log。

Raft 采用了 snapshotting 的方式去压缩/减少日志。
In snapshotting, the entire current system state is written to a snapshot on stable storage, then the entire log up to that point is discarded.

Snapshotting technique is also used in Chubby and ZooKeeper

以上就是 Raft 算法的整个运转机制。

简介