Raft概述
Raft 是工程上使用较为广泛的 强一致性、去中心化、高可用 的分布式协议，用于管理副本复制（Log Replication）。相比传统的 Paxos 算法，Raft 将大量的计算问题分解成为了一些简单的相对独立的子问题，并有着和 Multi-Paxos 同样的性能。
Raft的首要目标就是容易理解(Understandable)。
Raft相对来说易于实现主要归结为以下几个原因：
- 问题分解（模块化）：把一致性协议划分为 Leader 选举、MemberShip 变更、日志复制、SnapShot 等相对比较解耦的模块；
- 设计简化（状态简化）：比如不允许类似 Paxos 算法的乱序提交、使用 Randomization 算法设计 Leader Election 算法以简化系统的状态，只有 Leader、Follower、Candidate 等等。
Raft相比Paxos有很多相似之处，但是有这么几个新特性：
- Strong leader：使用strong leader可以简化管理。例如log entries只从leader流向其他server.
- Leader election：使用randomized timer来简化选举过程。相比其他共识算法增加了heartbeat机制
- Membership changes：Raft变更服务器集群的使用了一种新的方法，保证了服务器的配置变更也能继续运行。
概念
角色
Raft中节点存在三种状态，节点会根据集群的状态转变自己的状态：
- Leader：Leader 会一直工作，直到失败。Leader 节点负责处理所有客户端的请求，定期向集群中的 Follower 节点发送心跳消息，证明自己还健在。
- Follower：Follower 只响应来自其他服务器的请求。Follower 节点不处理 Client 的请求，而是将请求重定向给集群的 Leader 节点，由 Leader 节点进行请求处理。
- Candidate：如果 Follower 长时间没有收到任何通信，它将成为 Candidate 并发起选举。获得多数选票的 Candidate 成为新的 Leader。
选举
- Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖；
- Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举；
- Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。
角色变化
相比Paxos复杂的角色划分，Raft算法只有三种角色分类：Follower、Candidate和Leader。所有的Server都会在这三种角色中相互转换，转换流程如下：
初始状态，所有节点都是群众
- 群众->候选人：定时器先过期，选举开始
- 候选人->领导者：获得大多数投票
- 候选人->群众：发现已经有领导者或者更新的任期
- 候选人->候选人：定时器超时或者进入一轮新的任期
- 领导者->群众：发现有节点有更高的任期
系统中最多只有一个Leader，如果在一段时间里发现没有Leader，则大家通过选举-投票选出Leader。Leader会不停的给follower发心跳消息，表明自己的存活状态。如果Leader故障，那么follower会转换成candidate，重新选出Leader。
- 所有节点启动时都是follower状态；
- 在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举;
- 如果收到过半票（含自己的一票）则切换到leader状态；如果发现其他节点日志比自己更新，则主动切换到follower。
工作流程
数据的流向只能从 Leader 节点向 Follower 节点转移。当 Client 向集群 Leader 节点提交数据后，Leader 节点接收到的数据处于未提交状态（Uncommitted），接着 Leader 节点会并发向所有 Follower 节点复制数据并等待接收响应，确保至少集群中超过半数节点已接收到数据后再向 Client 确认数据已接收。一旦向 Client 发出数据接收 Ack 响应后，表明此时数据状态进入已提交（Committed），Leader 节点再向 Follower 节点发通知告知该数据状态变成了已提交。
从这里看出这个Leader 的作用是相当大的，事实也确实如此。Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。
在这个过程中，主节点可能在任意阶段挂掉， Raft 协议针对不同阶段也有保障数据一致性的解决方案。
1 数据到达 Leader 节点，但未复制到 Follower 节点
这个阶段 Leader 挂掉，数据属于未提交状态，Client 不会收到 Ack 会认为超时失败可安全发起重试。Follower 节点上没有该数据，重新选出新的主谋后可再次接收客户端的请求。原来的 Leader 节点恢复后作为 Follower 加入集群重新从当前任期的新 Leader 处同步数据，强制保持和 Leader 数据一致。
2 数据到达 Leader 节点，部分follower拿到复制的数据，但还未向 Leader 响应接收
这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为 Leader 再强制同步数据到 Follower，数据不会丢失并最终一致。
3 数据到达 Leader 节点，所有follower拿到复制的数据，但还未向 Leader 响应接收
这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态（Uncommitted）但保持一致，重新选出 Leader 后可完成数据提交，此时 Client 由于不知到底提交成功没有，可重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。
4 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态
这个阶段 Leader 挂掉，重新选出新 Leader 后的处理流程和阶段 3 一样。
5 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在所有节点都处于已提交状态，但还未响应 Client
这个阶段 Leader 挂掉，Cluster 内部数据其实已经是一致的，Client 重复重试基于幂等策略对一致性无影响。
Raft协议关键点
选举启动条件
Follower在Election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许Leader炸了；也许只是leader与该follower之间网线被老鼠咬断了），则会主动发起选举。
步骤
- 增加节点本地的 current term ，切换到candidate状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
- 等待其他节点的回复
出现结果
- 收到majority的投票（含自己的一票），则赢得选举，成为leader
- 被告知别人已当选，那么自行切换到follower
- 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
投票限制
- 在任一任期内，单个节点最多只能投一票
- 候选人知道的信息不能比自己的少
-
first-come-first-served 先来先得
Raft-Node-ABC.png
若有三个节点A B C（上图）。A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower。
若没有任何节点获得过半投票，比如上图。则等待超时，引入randomized election timeouts和奇数个节点避免
Log replication
共识算法基于Replicated state machines来实现，即相同的初识状态 + 相同的输入 = 相同的结束状态。
Leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则最终状态肯定是一致的。
请求完整流程
- leader append log entry
- leader issue AppendEntries RPC in parallel
- leader wait for majority response
- leader apply entry to state machine
- leader reply to client
- leader notify follower apply log
由于是远程请求，各个节点的操作都经过RPC实现
Log matching
每个log entry不仅包含client的command还包含log entry的leader term，每个节点不要求完全一致，只求最终一致。未达到最终一致的时候，leader会不断尝试给follower发log entry，直到完全一致。
由于server的连接可能出现问题，每个server的log entries都有可能不同，根据不同的情况可以进行分类做log matching:
- 出现follower的log index比master少或者term比当前term小，则进行额外的log commit
- log index大于当前index或者term高于当前log entries的，进行log删除
- log term小于或者不同于当前的term的，进行log覆盖
Safety
Raft通过上面几个属性保障在各类异常情况下仍然正常工作（数据中心被炸不算）
Log Compaction
由于Log只执行追加操作，而不进行删除和覆盖，Raft需要定期执行log compaction。snapshot可以分以下情况以提升性能。
- 定期做日志 snapshot，可使用copy-on-write技术
- 可以直接保留最新的log index和term
- Leader执行AppendEntries RPC时，节点log entry落后太多也可以直接发送snapshot
总结
Raft 主要包括两个独立的子问题，Leader election和log replication。流程就是先选举出Leader，然后由Leader负责复制和提交log。
为了保证算法的safety属性，Raft对其子问题加上了诸多约束：
Election restriction：
- 每个任期的节点在进行投票都只能投一票，原则是先来先到
- 选举人的信息必须比自己了解的多(term, log replication)
Log replication
- 一个log可以被复制到大多数节点（committed），且不能被回滚；
- Leader 一定包含最新的committed log,因此log只会追加而不会覆盖删除；
- 不同节点，某个位置上日志相同，那么这个位置之前的所有日志一定是相同的；
- Raft 不能够提交上个任期的log entries。
参考：
