分布式系统之Raft共识算法

分布式系统除了提升整个体统的性能外还有一个重要特征就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台的机器故障不会使系统不可用或者丢失数据。保证系统可靠性的关键就是多副本，一旦有多副本，那么就面临多副本之间的一致性问题

一致性算法正是用于解决分布式环境下多副本之间数据一致性的问题的。业界最著名的一致性算法就是大名鼎鼎的Paxos，但Paxos是出了名的难懂，而Raft正是为了探索一种更易于理解的一致性算法而产生的，它将一致性拆分为leader选举、日志复制、安全性三个关键元素

1、leader选举

Raft算法将时间划分成为任意不同长度的任期(term),任期用连续的数字表示，每一个任期的开始都是一次选举。如果一个侯选人赢得了选举，它就会在该任期的余下时间担任领导人，如果没有选出领导人，将会开始另一个任期，并且立刻开始下一次选举

那么什么时候开始选举呢？实际上leader会向所有follower周期性发送心跳，来保证它们的leader地位，如果一个follower在一个周期内没有收到heartbeat信息，那么它就会假定没有可用的leader，自已就转换状态成为候选人，并且开始一次选举来选出一个新的leader

Raft选举过程有三个规则

（1)、规则：如果请求投票的服务器任期比自己的任期大，则给该服务器投票

(2)、规则：在一个任期内，一台服务器最多能给一个侯选人投票，按照先到先得的原则

(3)、规则：随机选举超时

为了避免选票被平分，没有服务器成为leader，每台服务器在一个固定的范围内随机选取，从而使每台服务器的选举超时时间均不相同，这种机制使得在大多数情况下只有一个服务器会率先超时，它会在其他服务器超时之前赢得选举并且向其它服务器发送heartbeat信息

当候选人收到大多数节点的选票则转换为leader，发现leader或者收到更高任期的请求则转换为follower，在角色转换的时候遵守选举安全原则，一个任期(term)内最多允许有一个leader被选上

2、日记复制

要理解为日记复制得先搞明白日记匹配原则和可被提交的日记这两个概念 日记匹配原则描述的是，如果在不同日记中的两个条目有着相同的索引和任期号，则它们存储的命令是相同的。如果在不同日记中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全相同的 可被提交的日记描述的是，一旦被leader创建的条目已经复制到了大多数服务器上，这个日记就称为可被提交的。leader日记中之前的条目都是可被提交的，包括由之前的leader创建的条目

在日记复制流程中，leader需要找到follower同它的日记一致的地方，然后删除follower在该位置之后的条目，然后将自己在该位置之后的条目发送给follower

完整流程是，client向leader发出请求，leader将日记条目加入到它的日志中，并行向follower服务器发起日记复制请求，leader确认日记条目被安全复制后，将该条目应用到状态机，然后向client返回结果，向follower发出可以提交该日记条目的请求。当一个服务器已经将给它索引位置的日记条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目

在日记复制中，可能会出现各种各样的异常

(1)、异常：数据发送到leader,但未复制到follower

leader异常，client接收不到ack,重新选举后，client可重新向leader发出请求 (2)、异常：数据到达leader节点，成功复制到follower所有节点，但未向leader响应接收

重新选举后，虽然数据在follower节点处于未提交状态但保持一致，重新选举出leader后可完成数据提交，由于原leader异常，client无法接收到ack,会重新向leader发出请求，Raft要求RPC幂等，所以服务器要实现去重机制 (3)、异常：数据到达leader节点，成功复制到follower所有或多数节点,数据在leader处于已提交状态，但在follower处于未提交状态

这个阶段leader挂掉，重新选出新leader

（4）、异常：由于网络”分区”导致出现双leader 以5个服务器节点为例，正常情况下A节点为leader，接收client的请求，并将日记同步到B、C、D、E四个follower节点。由于网络原因，A、B节点无法与C、D、E进行通信，C、D、E重新选举，选择leader，假设E节点胜出，此时出现双leader。随后网络恢复，A、B将做为E的follower

3、安全性 Raft通过比较日记中最后一个条目的索引和任期号来决定两个日记哪一个更新，如果两个日记的任期号不同，任期号大的更新，如果任期号相同，更长的日记更新 Raft为了保证安全性，约定了一些选举限制，RequestVote RPC中包含候选人的日记信息，如果服务器自己的日记比候选人还要新，则会拒绝为该候选人投票

这个行为背后是leader完全原则，如果一个日记条目在一个给定任期内被提交，那么这个条目一定会出现在所有任期号更大的leader中。所有的日志条目都只会从leader节点往follower节点写入，且leader节点上的日志只会增加，绝对不会删除或者覆盖

参考

1、https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf （Raft一致性算法论文原文) 2、http://www.infoq.com/cn/articles/raft-paper（Raft一致性算法论文译文） 3、http://thesecretlivesofdata.com/raft/ (Raft一致性算法演示动画) 4、https://raft.github.io/ （Raft一致性算法官网） 5、相关BLOG http://blog.csdn.net/cszhouwei/article/details/38374603 http://www.cnblogs.com/mindwind/p/5231986.html