raft 协议

首推：http://thesecretlivesofdata.com/raft/

分布式存储系统通常通过维护多个副本来进行容错，保证高可用性。要做到这个，就必须解决分布式存储系统的核心问题：维护多个副本的一致性。

raft 协议就是一个一致性协议。

在一个具有一致性的性质的集群里面，同一时刻所有的结点对存储在其中的某个值都有相同的结果，即对其共享的存储保持一致。集群具有自动恢复的性质，当少数结点失效的时候不影响集群的正常工作，当大多数集群中的结点失效的时候，集群则会停止服务（不会返回一个错误的结果）。

raft协议的系统每一个节点都会有三个组件：

状态机：保持一致性，就是保持状态机的一致。状态机从 log 里取出所有的命令，执行一遍，得到的结果就是保证了一致性的数据。
Log：保存了所有的修改
一致性模块：一致性模块就是用来保证写入的 log 的命令的一致性。

raft 协议主要的功能，选主(leader election)、日志复制(log replication)、安全性保证(safety)，维护成员变化(membership changes)。

首先第一个问题是，这几台机器中都有数据，我们的目标是保证里面保存的数据都是一样的，那假如其中有一台数据不一样，那么到底应该以谁的为准？这就是选主问题，在Raft里面，有一个Leader的服务器，一切以Leader的数据为准。那么谁当Leader呢？那就靠Raft中的选主算法（Leader election）决定。

第二，为了保证客户端对数据的每一个操作，都能真正地保证操作成功（或者告知不能操作成功），Raft依靠的还是两阶段提交方法。学过两阶段提交协议的同学可能会比较熟悉。其实很简单。就像很多人去交电费。由于交电费的地方比较落后，因此那边的工作人员对于来排队缴费的人，操作流程是：首先对每一个来交电费的人进行登记，登记你要买多少电费，先记在本子上。然后到了晚上再统一将登记本上登记的电划给用户。在本文场景中，Raft首先将用户对数据的操作，保存在Log中。比如“将X赋值为3”这个操作先保存起来，然后在统一将这个操作真正去运行，持久化在State Machine中。因此日志是对于数据一致的关键保证。因此我们做数据副本，其实就是做日志副本，需要考虑日志怎么样才能安全复制到其他机器上去。这就是日志复制(log replication)。

而要对这一系列流程进行安全性保障，就需要一致性模块进行算法上的控制。安全性保证(safety)

当然，由于集群一般会不断变化，比如机器坏了，比如机器配置需要升级等等，导致集群的数量、配置等会发生变化。那么如何保证在集群变化的时候，也能使得一致性能够得到保证呢？那么就需要进行维护成员变化(membership changes)。

Leader election（选主）

raft协议的每一个副本都会处于三中状态之一： Leader，Follower，Candidate。

Leader，Follower，Candidate 的互相转换就是状态机了。

Leader：所有 client 发来的请求的处理者，leader 副本接受 client 的更新请求，自己处理后，在同步到其他副本
Follower：请求的被动更新者，从 Leader 接受请求，写入本地日志文件
Candidate：如果 Follower副本在一段时间内没有接收到 Leader 的心跳，就任务 Leader 空缺了，此时启动选主过程，切换为 Candidate 状态，直到选主结束。

选主可以认为就是 Follower 变成 Candidate，收集投票的过程。

raft协议将时间定为 Term(任期)，长度随机并且连续，Term 有唯一的 id。每一个 Term 就会进行选主。

选主发生在： 1.一个新 Term 的开始 2.Follower 发现一段时间没有接收到 Leader 的心跳

选主开始时： 1.Follower将自己维护的当前Term 的id term_id 自加 1； 2.切换状态为 Candidate； 3.发送请求投票（会包含自己的 term_id）给其他的副本。

term_id 大 == 节点的 log 比较新：Candidate 发出的 term_id 就是用来表示自己当前的 log 有多新，其他 server 会这个 term_id 和自己的 id 比较的，谁的数值大，就表示谁的 log 更新。

节点投票时会采取先到先得的原则，对于某个 term_id，最多投出一票（后面还会再对投票加一些限制）。这样能保证某个 term_id 中，最多只会产生一个 leader。当一个 Candidate 变成主节点后，它会向其它所有节点发送心跳信息，这样其它的 Candidate 也会变成 Follower。

一个 Candidate 发出投票请求后，迎接它的将有三种命运：

成为 Leader。 Candidate Server 得到了大多数的 server 的投票，成为 Leader。成为Leader后，就会定期给其他 server 发心跳信息用来告诉其他server，自己就是当前 term_id 这个任期的 Leader。当一个 server 接收到一个 term_id 大于自己本地存的 id，就更新自己本地存的 id，并且自己如果是 Leader/Candidate，就需要切换状态为 Follower。
其他 server 成为 Leader，自己是Follower。 Candidate Server 在等待投票时，发现有个 server 给自己发了它的 term_id（并且它还说自己是 Leader），比自己的大，就主动认输，切换状态为 Follower，用这个其他server 发过来的 term_id 做自己的用。
没有选出主。各个 server 该投票的，都投过票了，没有任何一个 Candidate 得到大多数 server 的投票，没有 Leader 被选出来。每一个等待投票结果的 Candidate 的都会超时，接着 Candidate 们都会将自己的 term_id 自加 1，随机等待一段时间后再重新发起投票请求。

PS：等待的时间是随机的，这样更有利于选出 Leader。

Log Replication（日志复制）

当一个机器中出现了 Leader，就可以接收 client 的请求了，每个请求包含一条需要被 replicated state machines 执行的命令。Leader 会将其作为一个 log entry append 到日志中，然后发给其他 server。当 Leader 确定了一个 log entry 被大多数 follower 写入日志（safely replicated）了，就将这条 log entry apply 到状态机中然后返回结果给 client。

当一个新的Leader被选出来时，它的日志和其它的Follower的日志可能不一样，这个时候，就需要一个机制来保证日志的一致性.

一个新leader产生时，集群状态可能如下:

    1 2 3 4 5 6 7 8 9 10 11 12
 l  1 1 1 4 4 5 5 6 6  6
(a) 1 1 1 4 4 5 5 6 6
(b) 1 1 1 4
(c) 1 1 1 4 4 5 5 6 6  6  6
(d) 1 1 1 4 4 5 5 6 6  6  7  7
(e) 1 1 1 4 4 4 4 
(f) 1 1 1 2 2 2 3 3 3  3  3

新Leader产生后，就以Leader上的log为准。其它的follower要么少了数据比如b，要么多了数据，比如d，要么既少了又多了数据，比如f。

因此，需要有一种机制来让leader和follower对log达成一致，leader会为每个follower维护一个nextIndex，表示leader给各个follower发送的下一条log entry在log中的index，初始化为leader的最后一条log entry的下一个位置。leader给follower发送AppendEntriesRPC消息，带着(term_id, (nextIndex-1))， term_id即(nextIndex-1)这个槽位的log entry的term_id，follower接收到AppendEntriesRPC后，会从自己的log中找是不是存在这样的log entry，如果不存在，就给leader回复拒绝消息，然后leader则将nextIndex减1，再重复，知道AppendEntriesRPC消息被接收。

以leader和b为例：

初始化，nextIndex为11，leader给b发送AppendEntriesRPC(6,10)，b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。接着，leader将nextIndex减一，变成10，然后给b发送AppendEntriesRPC(6, 9)，b在自己log的9号槽位中同样没有找到term_id为6的log entry。循环下去，直到leader发送了AppendEntriesRPC(4,4)，b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。随后，leader就可以从槽位5开始给b推送日志了。

Safety

哪些follower有资格成为leader?

Raft保证被选为新leader的节点拥有所有已提交的log entry，这与ViewStamped Replication不同，后者不需要这个保证，而是通过其他机制从follower拉取自己没有的提交的日志记录

这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的最后一条日志记录的term_id和index，其他节点收到消息时，如果发现自己的日志比RPC请求中携带的更新，拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。

哪些日志记录被认为是commited?

leader正在replicate当前term（即term 2）的日志记录给其它Follower，一旦leader确认了这条log entry被majority写盘了，这条log entry就被认为是committed。如图a，S1作为当前term即term2的leader，log index为2的日志被majority写盘了，这条log entry被认为是commited
leader正在replicate更早的term的log entry给其它follower。

Election safety

选举安全性，即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。

在raft中，两点保证了这个属性：

一个节点某一任期内最多只能投一票；
只有获得majority投票的节点才会成为leader。

log matching

很有意思，log匹配特性，就是说如果两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的。如何做到的？依赖于以下两点

If two entries in different logs have the same index and term, then they store the same command.
If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.

首先，leader在某一term的任一位置只会创建一个log entry，且log entry是append-only。其次，consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index，如果follower在对应的term index找不到日志，那么就会告知leader不一致。

    1 2 3 4 5 6 7 8 9 10 11 12
    1 1 1 4 4 5 5 6 6  6
(a) 1 1 1 4 4 5 5 6 6
(b) 1 1 1 4
(c) 1 1 1 4 4 5 5 6 6  6  6
(d) 1 1 1 4 4 5 5 6 6  6  7  7
(e) 1 1 1 4 4 4 4 
(f) 1 1 1 2 2 2 3 3 3  3  3

注意：上图的a-f不是6个follower，而是某个follower可能存在的六个状态。和上一次使用不一样

leader、follower都可能crash，那么follower维护的日志与leader相比可能出现以下情况

比leader日志少，如上图中的ab
比leader日志多，如上图中的cd
某些位置比leader多，某些日志比leader少，如ef（多少是针对某一任期而言）

当出现了leader与follower不一致的情况，leader强制follower复制自己的log

leader会维护一个nextIndex[]数组，记录了leader可以发送每一个follower的log index，初始化为eader最后一个log index加1，前面也提到，leader选举成功之后会立即给所有follower发送AppendEntries RPC（不包含任何log entry，也充当心跳消息）,那么流程总结为：

s1 leader 初始化nextIndex[x]为 leader最后一个log index + 1
s2 AppendEntries里prevLogTerm prevLogIndex来自 logs[nextIndex[x] - 1]
s3 如果follower判断prevLogIndex位置的log term不等于prevLogTerm，那么返回 False，否则返回True
s4 leader收到follower的回复，如果返回值是False，则nextIndex[x] -= 1, 跳转到s2. 否则
s5 同步nextIndex[x]后的所有log entries

leader completeness vs elcetion restriction

leader完整性：如果一个log entry在某个任期被提交（committed），那么这条日志一定会出现在所有更高term的leader的日志里面。这个跟leader election、log replication都有关。

一个日志被复制到majority节点才算committed
一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。下面的引文指处了如何判断日志的新旧。

上面两点都提到了majority：commit majority and vote majority，根据Quorum，这两个majority一定是有重合的，因此被选举出的leader一定包含了最新的committed的日志。

raft与其他协议（Viewstamped Replication、mongodb）不同，raft始终保证leade包含最新的已提交的日志，因此leader不会从follower catchup日志，这也大大简化了系统的复杂度。

参考： https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf https://www.cnblogs.com/xybaby/p/10124083.html#_label_7

raft