笔记：Lecture 6: Fault Tolerance: Raft (1)
视频：Lecture 6: Fault Tolerance: Raft (1)
论文地址：In Search of an Understandable Consensus Algorithm
课程概要
Raft选举和日志处理（实验2A、2B），第二课讲Raft一致性、客户端行为、快照（实验2C、实验3）
正文内容
选择Raft的原因：Paxos太难理解
因为相比较Paxos而言，理解起来要容易。第一，Paxos的原论文也比较晦涩难懂。譬如Paxos的single-decree 版本管理。第二，实际生产系统中的应用并不广泛。multi-Paxos的协议也没有得到广泛应用。虽然有些系统使用了Paxos——Chubby。但并没有开源。
目前现存容错系统的处理方式
- MapReduce的复制计算，但是依赖单master
- GFS副本数据，依赖master另外选主
- VMware FT复制服务依赖
test-and-set选择master
虽然单点master可以避免“脑裂”，但是master始终是单点。
“脑裂”如何产生？这种故障会导致什么问题？
假设我们的复制服务是test-and-set模式：多个客户端发送set请求到服务，服务端收到写入请求后，返回当前值（假设是0）给客户端，此时当且只有一个客户端收到结果，且为0.（锁，其他客户端等待）
假设如下的场景：C1，C2，S1，S2。客户端C1可以与S1通信，但是不能和s2通信。那么此时只有S1上存在一份副本，当S1出现宕机时。整个系统就会出现问题。
请问C1是否应该当只有S1在线时，继续进行任务？
- 如果S2真的宕机，C1必须在没有S2的情况下继续进行。 否则，服务不允许出现故障!
- 如果S2工作正常，但是C1与S2之间因为网络故障无法连接。。此时C1不应该在没有S2的情况下进行。 因为S2可能还活着，并为C2客户提供服务
面对上面的情况，要么是认为正常故障，继续提供复制。要么因为“脑分裂”导致可能出现错误的操作。
面对上面的问题，计算机是无法区分“服务器故障”和“网络故障”：
两者产生的结果都是：发送给节点的请求无法被响应。
通常比较棘手的这种情况被称为网络分区：C1可以正常与S1通信，C2可以正常与S2通信。但C1+S1无法看到C2+S2的响应。这种情况处理起来比较棘手，在以往的场景下都是需要人介入来处理。或者是单点靠谱的master（FT的test-and-set 策略），或者是靠谱的网络（没有响应就是服务器崩溃）
面对上面的问题的处理方式还不够优美。是否还有更好的处理方式？
解决写复制分区的问题，可以利用：大多数投票的方式处理。
奇数台的服务器，譬如：3、5、7。只要超过一半的机器认可，就可以继续复制。例如3台时需要2台投票同意。
Q：为什么使用这种方式（大多数投票）可以是解决脑分裂遇到的问题？
A：只会出现其中一个分区拥有多数票，打破了不同客户端看到节点数目的对称性。少数票的节点应遵循拥有大多数票分区的复制。一般而言2f + 1可以容忍f个故障服务器，我们也把这样的系统称为仲裁系统。
多数票决策系统有一个特征，就是需要任意两个节点存在交集。譬如：Raft的leader选举，新的选举也不会丢失最新的复制日志。
分布式复制容错的研究已经持续了很多年，在1990前后，诞生了两种分布式复制容错技术Viewstamped Replication和Paxos。随后的15年，Raft诞生，并且得到在工业界的广泛应用。
下面来看看Raft
Raft数据结构
状态：
- 磁盘：
currentTerm、votedFor、log[] - 内存：
commitIndex、lastApplied - leader节点(内存)：
nextIndex()、matchIndex[]
日志追加RPC过程：
- 参数：
term、leaderId、prevLogIndex、prevLogTerm、entries[]、leaderCommit - 回调结果：
term、success - 接收者
- 当
term<currentTerm返回false preLogIndex与preLogTerm不匹配时返回falseentires[]存在冲突的条目（index相同，term不同）。应删除此日志以及>index后的所有条目- 添加任何在已有的日志中不存在的新条目
- 如果
leaderCommit > commitIndex，则commitIndex设置为min(leaderCommit,entries[].lastIndex)
- 当
投票RPC：
- 参数：term、candidateId、lastLogIndex、lastLogTerm
- 回调结果：term、voteGranted(true意味着收到投票)
接收者：
- 当
term<currentTerm返回false - 如果votedFor为空或者与candidateId相同，并且候选人的日志和自己的日志一样新，则给该候选人投票
协定：
- 所有服务器All node
- 如果
commitIndex > lastApplied：lastApplied增加，状态机状态设置为log[lastApplied] - 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm，则currentTerm赋值为 T，并切换状态为追随者（Follower）
- 如果
- 追随者Follower
- 响应候选者和leader的请求
- 如果超时还没有收到leader的AppendEntries请求或者是candidated的投票，自己就晋升为candidated
- 候选者Condidates
- 转换为候选者后开始选举：
currentTerm自增、投票给自己、重置选举计时器、请求投票RPC给其他服务器 - 如果大多数投票通过，则成为leader
- 如果收到来自leader的
AppendEntries请求，则成为follower - 如果超时，则开始新一轮选举
- 转换为候选者后开始选举：
- 领导人Leader
- 一旦成为leader，就需要向所有节点发送
AppendEntriesRPC心跳包；空闲时重复发送空包以防止选举超时 - 收到客户端请求，先追加到本地日志，然后更新状态机新值
- follower上次收到的日志缩影大于将要收到的日志索引
nextIndex，则通过AppendEntriesRPC把nextIndex之后的日志发送出去。
- 一旦成为leader，就需要向所有节点发送
- 发送成功则将该追随者的
nextIndex和matchIndex更新 - 因为日志不一致导致的发送失败，
nextIndex递减并且重新发送- 当存在一个N，使得
N > commitIndex和matchIndex[i]>=N，并且log[N].term == currentTerm。则更新commitIndex = N
- 当存在一个N，使得
在开发时，Raft作为library运行在每个副本中。如图
当客户端发送一条put写命令时：
- 客户端发送
put/get命令到leader的K/V层 - leader添加命令到日志
- leader发送AppendEntries RPC调用到follower
- follower存储日志到磁盘
- leader等待大多数的follower响应（包括自己）
- 当收到大多数响应时，标记此日志为commited（已提交）状态。这意味当集群机器出现故障时，数据不会丢失。出现leader选举时，下一个leader也能看到最新日志。
- leader执行命令告知客户端成功
- 与此同时，leader在下一次进行AppendEntries RPC告知follower这条日志可以执行存储
- follwer 看到是commit则会实际的写入到KV层
Q：为什么需要引入日志？
A：单独的KV DB存储无法完整的保存状态机的状态。日志可以保证命令执行的顺序（只做append），也可以帮助确保leader和follower日志一致。
日志存储临时命令直到提交，日志可以防止leader的命令重发导致重复执行，日志因为进行了持久化，即使服务器重启也能回放。
Q：是不是所有的副本日志都一样？
并不是，有些副本的日志可能出现滞后。短暂时间内，日志记录不同。不过，最终所有的副本会收敛为一致，commit机制可以确保所有的命令都被正确执行。
实验2 Raft接口
rf.Start(command) (index, term, isleader)`
- 实验3中 k/v 服务器的
Put()/Get()操作通过RPC调用Start() Start()只对leader有意义- 在新的日志记录启动Raft协议
- 添加到leader日志
- leader发送附属日志给AppendEntries RPC
Start()返回w/o调用RPC后的响应- 在
applyCh部分，k/v 层的Get()/Put()操作需等待commit才能算完成
- 如果服务器在commit之前失去leader，则此次通信可能会失败，执行的命令可能会丢失，客户端需要重发
- isleader: 如果服务器不是leader则为false，客户端识别此字段为false时需要重试另外一台
- term:
currentTerm, 给调用者区分leader是否被降级 - index：区分日志是否已经commit
ApplyMsg，包含日志的最新索引（index）和执行的命令：（command,index）
- 每个提交的日志在applyCh会发送一个ApplyMsg
- 接收消息后执行命令，更新本地副本状态
- leader通过RPC发送响应结果给等待的客户端
Raft设计有两个主要的部分：
- 选择新leader
- 即使出现故障，也能保证日志一致
讨论：Leader选举
Q：为什么只有一个leader？
A：保证所有的副本执行相同命令并且保证顺序一致（有些设计是没有leader的，譬如：Paxos）
Raft中Leader的序列编号意义（raft把时间分为多个周期，每个周期都有一个编号）
新leader–>新的周期
在新的周期内，最多只存在一个leader也可能没有。
编号可以帮助服务器找到那个是最新的leader，而不会再次请求旧的leader
Raft中成员何时开始新一轮的选举？
- 没有收到当前消息发送的选举超时消息时
- 增加自己的currentTerm,并发送RPC要其他节点投票
- 会有可能选举多次，导致选举时间变长。但保证了安全
- 旧的leader可能还活着，那么此时就认为它是领导者
如何确保在一个周期内只有一个leader？
- leader必须获得大多数节点的赞成投票（假设节点数为2n，则至少需要获得n+1）
- 每个节点每个周期内只能给投一票。
- 候选人则是投票给本身
- 非候选人则投票给第一个询问票的节点
- 同一个周期内，只有一个节点能获得大多数投票
- 即使网络分区也只会出现一个leader
- 当有服务器出现故障时也不影响选举
节点如何了解新选举的leader已经产生？
- 获得大多数的投票的leader，对于这些投票的机器认为对方是candidate
- 新leader的通过AppendEntries心跳包发送一个高的周期编号给其他节点。其他节点收到这个心跳包后停止选举，并认为对方是leader
选举失败的可能性原因可能有两个：
- 大多数的服务器无法响应
- 大家都是候选人状态，无法获得到多数票
如果选举不成功怎么办？
- 选举超时（没有心跳），开始新的选举（新的周期）
- 周期编号高的继续，低编号的候选人退出
Raft如何避免分裂投票？
每个节点的超时都是在150～300ms选择一个随机值。随机值打破节点之间的对称性，所有节点的随机值中会出现一个最小的随机值。有足够的时间在是一轮超时获得选举。其他节点看到新的leader发送的AppendEntries 心跳并且不会变为candidate。（随机延时在网络协议中也比较常见）
如何处理选举超时时间？
- 至少能容纳几个心跳包间隔（防止网络丢包），避免不必要的选举而浪费时间
- 随机部分足够长的时间，让一个候选人在下一个候选人开始前发起投票，然后再让下一个候选人开始。
- 足够短的时间对故障做出快速反应，避免长时间的服务中断。
- 足够短的时间，可以在短时间内，允许多重试几次选举。
- 一般要求在5秒内完成选举任务
如果旧的leader不知道新的leader当选怎么办？
- 旧的leader可能没有收到选举消息
- 旧的leader在少数量节点的分区网络中
- 新的leader意味着大多数节点的currentTerm已经递增
- 旧的leader无法通过AppendEntries获得大多数投票
- 旧leader无法执行和commit新的log
- 基于以上，这种情况下就不会产生“脑裂”，但是有一小部分会收到旧的AppendEntries，不过在旧的周期结束时，日志会被丢弃。
参考文献
- Students’ Guide to Raft
- In Search of an Understandable Consensus Algorithm
- Raft 一致性算法论文译文
- Raft Structure Advice
- Raft Locking Advice
- The Part-Time Parliament
- Paxos Made Simple
- Generalized Consensus and Paxos
- Raft在线演示
- Raft Consensus Algorithm
- Raft lecture (Raft user study)