本文讲解Raft分布式一致性理论算法，阅读了raft算法论文，帮助后面大家更好的理解Raft分布式一致性算法。

1、什么是分布式一致性

分布式一致性问题，简单的说，就是在一个或多个进程提议了一个值应当是什么，使系统中所有进程对这个值达成一致意见。它是指多个服务器在状态达成一致，但是在一个分布式系统中，因为各种意外可能，有的服务器可能会崩溃或变得不可靠，它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议，一致性协议是为了确保容错性，也就是即使系统中有一两个服务器当机，也不会影响其处理过程。为了以容错方式达成一致，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2+1 就超过半数，代表大多数了。

实际分布式系统一般是基于消息传递的异步分布式系统，进程可能会被杀死或者重启，消息可能会延迟、丢失、重复、乱序等。在一个可能发生上述异常的分布式系统中如何就某个值达成一致，形成一致的决议，保证不论发生以上任何异常，都不会破坏决议的一致性，这些正是一致性算法要解决的问题。

这样的协定问题在分布式系统中很常用，比如：
领导者选举（leader election）：进程对leader达成一致；
互斥（mutual exclusion）：进程对进入临界区的进程达成一致；
原子广播（atomic broadcast）：进程对消息传递（delivery）顺序达成一致。
对于这些问题有一些特定的算法，但是，分布式一致性问题探讨这些问题的一个更一般的形式，如果能够解决分布式一致性问题，则以上的问题都可以解决。

2、raft算法应用场景

1.主从同步方式
首先，写请求首先发送给主节点，主节点同步更新到其它从节点后返回，之后写请求执行成功。
优点：这种方式可以保证副本之间数据的强一致性，写请求执行成功之后从任意副本读到的数据都是一致的。

缺点：可用性很差，只要任意一个从节点写失败，写请求将执行失败。主从同步的弱可用性。

2.主从异步方式
如果采用异步同步的方式，主节点写成功后立即返回，然后在后台异步的更新其它从节点。
优点：这种方式可用性较好，只要主节点写成功，写请求就执行成功。

缺点：不能保证从节点之间数据的强一致性，写成功返回之后从各个从节点读取到的数据不保证一致，只有主节点上是最新的数据，其它从节点上的数据落后，只能提供最终一致性。可能出现以下失效的情况：异步同步数据失败。如果出现断网导致后台异步同步数据失败，则主节点和其它节点将长时间不一致，其它从节点上的数据一直无法更新，直到网络重新连通。

3、raft算法

Raft 通过选举一个领导人，然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目(log entries)，把日志条目复制到其他服务器上，并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从领导人流向其他服务器。一个领导人可能会宕机，或者和其他服务器失去连接，在这种情况下一个新的领导人会被选举出来。

通过领导人的方式，Raft 将一致性问题分解成了两个相对独立的子问题：

1.领导选举：当现存的领导人宕机的时候, 一个新的领导人需要被选举出来
2.日志复制：领导人必须从客户端接收日志条目(log entries)然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。

这篇文章只详细讲解raft算法中领导选举的过程。

3.1 raft角色
一个 Raft 集群包含若干个服务器节点；5 个服务器节点是一个典型的例子，这允许整个系统容忍 2 个节点失效。在任何时刻，每一个服务器节点都处于这三个状态之一：领导人(leader)、跟随者(follower)、候选人(candidate)。在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。跟随者都是被动的：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求，候选人是用来在选举新领导人时使用。如图所展示了这些状态和他们之间的转换关系。
1.跟随者:
响应来自候选人和领导者的请求
如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，就自己变成候选人
2.候选人：
在转变成候选人后就立即开始选举过程
自增当前的任期号（currentTerm）
给自己投票
重置选举超时计时器
发送请求投票的 RPC 给其他所有服务器
如果接收到大多数服务器的选票，那么就变成领导人
如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
如果选举过程超时，再次发起一轮选举
3.领导者：
一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时
如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端

3.2 领导人选举
Raft 使用一种心跳机制来触发领导人选举。当服务器程序启动时，他们都是跟随者身份。一个服务器节点继续保持着跟随者状态只要他从领导人或者候选者处接收到有效的 RPCs。领导者周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加日志项 RPCs）来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。选举步骤如下图所示：
1.增加节点本地的 current term ，切换到candidate状态
2.开始选举之后都会有一个随机的超时时间，最先走完time out时间的一个节点B发起投票，向还在time out 期间的的A节点和C节点发起请求投票(Request vote)并等待回复，此时B节点只能投给自己。
3.B节点等待其他节点A和C的回复
4.当A和C节点回复后，然后raft会统计票数，在计数器时间内，得票最多的节点B成为leader。选择出leader后，该任期term加1，并且leader向所有follower节点发送心跳信息保持连接。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。
候选人会继续保持着当前状态直到以下三件事情之一发生：(a) 他自己赢得了这次的选举，(b) 其他的服务器成为领导者，© 一段时间之后没有任何一个获胜的人。

3.2.1 当前候选人自己成为leader

如下图所示，当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票，那么他就赢得了这次选举并成为领导人。每一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则。要求大多数选票的规则确保了最多只会有一个候选人赢得此次选举。一旦候选人赢得选举，他就立即成为领导人。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。

3.2.2 其他的服务器成为领导者

如下图所示，在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导人的附加日志项 RPC。如果这个领导人的任期号（包含在此次的 RPC中）不小于候选人当前的任期号，那么候选人会承认领导人合法并回到follow状态。 如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。

3.2.3 多个候选人同时发起选举

如下图所示，第三种可能的结果是候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。

Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时；然后他赢得选举并在其他服务器超时之前发送心跳包。同样的机制被用在选票瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。

3.3 选举完成后leader宕机
如下图所示，每次当leader对所有的followe发出Append Entries请求的时候,follower会有一个随机的超时时间,如果在超时时间内收到了leader的请求就会重置超时时间,如果超过超时时间，follower没有收到 Leader的心跳，follower会认为 Leader 可能已经挂了，此时第一个超时的follower会发起投票,注意这个时候它依然会向宕机的原leader发出Reuest Vote,但原leader不会回复。raft设计的请求投票都是幂等的,会检测状态。当收到集群超过一半的节点的RequestVote reply后,此时的follower会成为leader。

4、总结

像 Raft 一样，VR 和 ZooKeeper 也是基于领导人的，因此他们也拥有一些 Raft 的优点。但是，Raft 比 VR 和 ZooKeeper 拥有更少的机制因为 Raft 尽可能的减少了非领导人的功能。本文是在看完raft论文后自己的总结，文章讲解了leader选举这一小块内容。个人觉得，如果想深入了解，还是要看论文，论文中对raft算法进行了详细的介绍。

作者：卓一航