带你简易入门一致性算法Raft
当我们只有一个服务节点的情况下，是不存在节点共识的问题的，当存在多个不同服务节点时，才会引入分布式一致性的问题。
Raft是一种实现分布式共识的协议。所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。
主要应用场景：
Redis Sentinel的选举Leader
Etcd 主要是共享配置和服务发现，实现一致性使用了Raft算法
加密货币（比特币、区块链）的共识算法
主要解决什么问题？
分布式存储系统通常通过维护多个副本来提高系统的可用性，带来的代价就是分布式存储系统的核心问题之一：维护多个副本的数据一致性。
二、Raft算法实现流程
为了提高理解性，Raft将一致性算法分为了几个部分，包括领导选取（leader selection）、日志复制（log replication）、安全（safety），并且使用了更强的一致性来减少了必须需要考虑的状态。
本文通过一个小故事做示例，来便于大家快速理解。
2.1 Leader选举
部门需要成立一个新的服务小组，现在有三名同学A，B，C。
为了便于后期统一调配资源及管理需要，现需要从三名同学中选举出一名小组Leader。
A觉得自己有能力做好Leader职务，就向B、C说“来投票给我，我想当Leader”，这时候A成了候选人，并为自己事先投了一票。
1）假如B、C之前都没有想过要自己当Leader，那就说“好吧，投给你” → A获得3张选票，当选Leader
2）假如B之前想过自己当Leader，B投了自己一票 而C投了一票给A → A获得2张选票（3人中已超过半数），当选Leader
3）假如B、C都已经把票投给了自己 → A、B、C各获得自己的一票，选举失败重新发起
4）假如B之前想过自己当Leader，而且C已经把票投给了B → B获得2张选票（3人中已超过半数），当选Leader
从以上选举流程可以发现，一个节点任一时刻肯定处于以下三状态之一：
Leader（领导者）
Follower（跟随者）
Candidate（候选人）
这三个状态的转移过程如下图所示：
选举过程
第一步：Follower成为Candidate
如果Follower听不到Leader的意见，他们就可以成为Candidate
第二步：候选人争取票
投自己一票，并发送投票请求到其他节点，节点收到请求后进行回应
第三步：等待其他节点回复
如果候选人得到了超半数的节点的投票（包含自己的一票），它就成为Leader
如果候选人被告知Leader已产生，则自行切换为Follower
一段时间内没有收到超半数投票，保持候选人状态，重新发起选举
第四步：候选人 赢得选举
新Leader会立刻给所有节点发消息，避免其他节点触发新的选举。
2.2 日志同步
在经过上述2.1 的Leader选举之后，已经选定了小组Leader，这里我们假定A已当选Leader。可以承担一些对接方同学（称为Client 端）提出的操作任务了。
规定每次需求对接，必须要经过小组Leader才可以。那员工提出操作请求，Leader接收到后记录下来，同时向组内其他同学进行同步，直到其他同学都确认了此需求后Leader才会确认操作并同步执行结果到员工（Follower节点）。
Log Replication（日志复制）
经过Leader选举流程，产生了新的Leader节点，系统的所有变更都要通过Leader节点来实现。
第一步：Leader追加日志项（append log entry）
系统的每个更改都作为一个entry 添加到节点的日志中
第二步：Leader并行发出Append Entries RPC，并等待响应
Leader会一直等到超半数节点都写入entry，Leader节点提交，然后Leader通知Follower entry已提交。
第三步：Leader得到大多数回应，向状态机应用entry
状态机：可理解为一个确定的应用程序，所谓确定是指只要是相同的输入，那么任何状态机都会计算出相同地输出。
第四步：Leader回复Client，同时通知Follower应用log
目前集群已就系统状态达成了共识
log-based replicated state machine示意图：
关于应用过程中的几个问题
Q1
假如Client 请求访问到了Follower节点怎么办？
解答：Follower节点会转发请求到Leader节点。
Q2
当Leader与Follower的日志不一致，需要如何处理？
解答：
1）Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。
2）Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。
3）Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。
2.3 安全性保障
为了保证团队运行的稳定，有几个默认的要求：
2.3.1 选举安全
即任一任期内最多一个leader被选出。假如系统中同时有多于一个leader，被称之为脑裂（brain split），这会导致数据的覆盖丢失。
一个团队某个时期内仅允许存在一个Leader（选举失败情况特殊情况除外），否则多个Leader同时处理需求发号施令，容易造成团队内步调不一致情况。
在raft中，两点保证了这个属性：
1）一个节点某一任期内最多只能投一票；
2）只有获得majority投票的节点才会成为leader。
2.3.2 Log 匹配完整性
同一团队内两名同学假如目前手头负责的事务是一致的，那之前他们的工作记录应该也是一致的。即：相同的初始状态+相同的操作=相同的结束状态
Leader将客户端请求封装到一个个的log entry，将这些log entries复制到其他Follower节点，大家按顺序应用这些请求，那最终状态肯定是一致的。
Raft日志同步结论：
1）如果不同日志中的两个条目有着相同的索引和任期号（term），则它们所存储的命令是相同的。
2）如果不同日志中的两个条目有着相同的索引和任期号（term），则它们之前的所有条目都是完全一样的。
2.3.3 leader数据完整性
团队内后继的leader，肯定应该知晓这个团队之前的工作内容，因为所有Leader任期内的工作记录是会做交接的。
如果一个log entry 在某个任期被提交，那么这条log一定会出现在所有更高term的leader的日志里面。
Raft日志覆盖规则：
1）一个日志被复制到majority节点才算committed
2）一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。
三、总结
所有的算法实现原理，其实都是真实社会工作模式的影射，联系生活中的实际案例来理解复杂的一致性算法，可以让我们达到事半功倍的效果。
本文旨在让大家对raft协议有一个简单了解入门，如有兴趣去更深入了解，推荐给大家两个不错的链接：
1）Raft可视化测试以及各语言版本实现的Raft：https://raft.github.io/
2）Raft算法-动画演示（很好的入门教程）：http://thesecretlivesofdata.com/raft/
·················· END ··················
架构精进之路
十年研发风雨路，大厂架构师，CSDN博客专家。专注软件架构研究，技术学习与职业成长，坚持分享接地气儿的架构技术干货文章！
Official Account
十年研发路，大厂架构师，CSDN博客专家
专注架构技术学习及分享，职业与认知升级
坚持分享接地气儿的干货，期待与你一起成长
「架构精进之路」专注架构研究，技术分享