业界最著名的一致性算法就是大名鼎鼎的Paxos（Chubby的作者曾说过：世上只有一种一致性算法，就是Paxos）。但Paxos是出了名的难懂，而Raft正是为了探索一种更易于理解的一致性算法而产生的。Raft是分布式环境下的一致性算法，它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像，然而Raft算法里不能存在拜占庭节点，而RBFT则能容忍BFT节点的存在。
Raft算法概述
Raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。也是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication）。raft协议就是一种leader-based的共识算法，与之相应的是leader-less的共识算法。
- leader-base（非对称的）：即有leader，在任意的某个时间点，只有一个leader，其他的节点接受leader的决定。客户端只和leader 节点发生交互。
- leader-less（对称的）：即没有leader，大家都是平等的，客户端可以连接任意的节点。
Raft名词解释
- Leader Election（选举）：Raft通过选举Leader并由Leader节点负责管理日志复制来实现多副本的一致性。
- Leader：负责接收客户端的请求，将日志复制到其他节点并告知其他节点何时应用这些日志是安全的
- Candidate：候选人，用于选举Leader的一种角色
- Follower：跟随者，类似于人民群众，负责响应来自Leader或者Candidate的请求
- Term（任期）： 类似总统当选后每4年一个任期，Raft把时间切割为任意长度的任期，每个任期都有一个任期号，采用连续的整数
- Log replication（复制日志集）：Leader复制日志集到Follower
- Heart Beat（心跳）：Leader会不停的给Follower发心跳消息，表明自己的存活状态。在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举。
此外Raft算法中，有三种很重要的超时时间：选举超时、最小选举超时、心跳超时。
election timeout：选举超时时间。raft中是随机的（随机很重要）。就是新一轮选举开始时，每个节点随机思考要不要做领导者的时间，这个时间一般100-到200ms，非常短。假设集群由3个节点组成，为了防止3个节点同时发起投票，Raft会给每个节点分配一个随机的选举超时时间（Election Timeout）。在这个时间内，节点必须等待，不能成为Candidate状态。现在假设节点a等待168ms，节点b等待210ms，节点c等待200ms。由于a的等待时间最短，所以它会最先成为Candidate，并向另外两个节点发起投票请求，希望它们能选举自己为Leader。另外两个节点收到请求后，假设将它们的投票返回给Candidate状态节点a，节点a由于得到了大多数节点的投票，就会从Candidate变为Leader。
heartbeat timeout：心跳是Leader发送心跳给Follower的时间。这个时间一旦超时，Follower会觉得Leader挂了，这样会开始新的选举周期。
最小选举超时间：在分布式系统中，有时候需要对集群中的成员数量进行更新的操作。对于被下线的服务器而言，如果它们没有及时关闭，那么它们将不会接收到心跳信息和日志信息，从而不断发生超时，最后导致任期不断增加(高于集群中所有成员的任期)，然后不断向集群中发送请求投票消息。集群中的Leader将变为Follower，集群中将不断开始新的选举，从而扰乱集群的正常运行。
解决方案：Raft引入了一个最小选举超时时间，意思是如果集群中存在Leader时，并且接收到心跳信息之后在最小选举超时时间内接受到请求投票消息，那么将会忽略掉该投票消息。
Leader Election 选举
Raft协议中，节点有三个角色，角色可以相互转化：Leader、Follower、Candidate。
- 所有节点初始状态都是Follower
- 超时时间内没有收到Leader的心跳，则转换为Candidate发起选举
- Candidate收到大多数节点的选票则转换为Leader
- Candidate发现Leader或者收到更高任期的请求则转换为Follower
- Leader在收到更高任期的请求后转换为Follower
选举过程
如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。步骤如下：
- 增加节点本地的 current term ，切换到Candidate状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
- 等待其他节点的回复
在这个过程中，根据来自其他节点的消息，可能出现三种结果：
- 收到majority（大多数）的投票（含自己的一票），则赢得选举，成为Leader
- 被告知别人已当选，那么自行切换到follower
- 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
对于选举过程，仅靠描述是难以说明白的，里面涉及很多细节。结合动图网站理解Raft 原理动画，这里可以一步一步的操作，然后理解整个选举过程。Raft官网上也有详细的解释
总结整个选举流程
集群初始没有Leader，各个节点最先经过election timeout的节点会成为Candidate候选者
Candidate会立即开启一个选举任期，首先它会投自己一票，并发送投票请求给其他节点
接着每个Follow会响应投票，并且每个选举任期只能投一票，并且会重置election timeout，防止Leader还活着呢，Follow就像篡位
一旦Candidate获得了大多数Follow的投票就会立马变成Leader，如果没办法票数不能超过一半就无法选出Leader，会清空计时重新选Candidate
接着Leader为了维护自己的地位，每搁一个heartbeat timeout就会向Follow发送心跳检测重置Follow的election timeout，Leader一句话:你们不要 BB! 按我说的做，做完了向我汇报!”
这个选举任期直到Leader挂了，Follow没有在election timeout内收到心跳检测为止
接下来是异常流程
Leader任期结束了，怎么重新选举？
- 如果Follow没有在election timeout内收到心跳检测就会变成Candidate，然后立马发起新一任的选举投票，投票成功就会当选新的Leader
如果有两个Follow同时成为Candidate怎么办？
- 如果同时有两个Candidate在同一任期内进行选举，并且票数相同，那么此时所有节点所有节点开始重新计时变为Candidate，由于election timeout是随机数，所以一定会出现一个唯一的Candidate
Log replication:日志复制过程
当我们选出Leader后，所有的请求必须经过Leader，整个集群又是如何达成数据一致性的呢？也就是说我们一旦选出了Leader，我们需要将对Leader的修改同步复制到所有的Follow，具体流程如下：
- 记得我们前文提到的心跳检测么？对于数据的同步操作就是追加在心跳包中一起发送给Follow
- 当Client发起一个请求比如set x = 5，首先这个请求会发给Leader，首先这条指令会加入到Leader的日志文件中，此时Leader并没有真正地修改数据
- 接着会把set x = 5请求加入到下次的心跳检测包中发给Follow，Follow会发送ACK给Leader并且把指令写到Log中并没有真正修改数据
- 当Leader收到全部数量的Follow，首先真正修改数据，然后返回给客户端请求结果，接着在下次心跳包中告诉Follow去真正地修改数据，Follow收到后进行数据修改
- 我们不难看到，也是两阶段提交协议，两阶段提交协议是保证一致性地常用手段
Raft分区容错性强
我们假设一种场景，原本正常地集群出现网络分区后怎么办？
此时可以看到虚线上方地三个Follow无法再接受到Leader的心跳检测了，所以三个Follow会开始再election timeout到时后成为Candidate重新选举Leader，并且两个Leader的任期是不同的，最终会变成下图状态
- 同时由于共5个节点，下半分区Leader在接收Follow反馈时，无法得到大多数节点反馈，所以不能此时指令只能写入到log中，无法真正写入，也就是无法执行二阶段提交的第二阶段执行
- 当分区恢复后，任期计数大的Leader会成为新集群的Leader，分区下方的节点会回滚还未提交的事务，并且同步新Leader的日志达成集群的一致性
- 所以即使强如Raft算法，再出现网络分区后，也会出现数据不一致地情况，比如客户端是无法感知出现网络分区地，我们向产生分区前地Leader发送请求，那么请求只能保证上图中下半分区一致，和上半分区也会出现不一致地情况，但一旦网络分区消除，整个集群又会达成一致性的场景
参考链接：
Raft 官网：https://raft.github.io/
Raft 原理动画：http://thesecretlivesofdata.com/raft/
Raft Paper： https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
