图解：什么是Raft算法？

导读

在之前的文章《基于SpringCloud的微服务架构演变史？》中我们介绍了分布式注册中心Consul集群中使用了Raft这种分布式一致性算法，那么在这一篇的内容中就给大家详细介绍下什么是Raft算法。

我们知道进行微服务架构很重要的一个目标就是实现分布式提升整体系统的性能和可靠性。而提供系统可靠性的关键就是通过建立多个副本节点的方式来保证系统中一台或多台服务节点故障的情况下，系统仍然可用。但是多个副本之间的数据一致性如何保证，就成了一个新的问题，而分布式一致性算法就是为了解决分布式环境下多副本之间数据一致性问题的。

在基于SpringCloud的微服务体系中，Consul作为整个服务的注册中心，处于十分关键的位置，所以Consul在生产环境下都是以集群的方式来提供服务的，而整个Consul集群间的节点数据同步就需要像Raft这样的一致性算法来实现。

下面我们就以图解的方式来深入了解下Raft的工作机制！

Raft的角色

在Raft算法中节点存在Follower、Candidate、Leader三种状态。

Raft节点选举（Leader Election）

在初始状态下集群中所有的节点都处于Follower状态。

此时如果某个Follower节点，如Node a首先感知不到来自Leader节点发送的心跳，就会将自身的状态转换为Candidate。

这里有一个选举超时时间为随机分配的150ms~300ms之间，选举超时后，Follower节点就会转换为Candidate节点并开始新的选举任期Term。

此时进入Candidate状态的节点首先会给自己投上一张选票（Voted For a）然后会向其他节点发送选举请求（Vote For me），要求选举自己为Leader。

如果接收到Candidate Vote请求的其他节点在这个选举任期（Term=1）还没有进行过投票，那么它们就会给发送请求的Candidate进行投票响应,并且重置本节点的选举超时时间设置。

如果Candidate节点得到大多数节点的选票，那么它就会成为本届任期内新的Leader节点。

此时Leader节点与各个Follower节点之间就会通过发送heartbeats来感知彼此的状态，直到某个Follower节点率先感知不到Leader节点的心跳，变成Candidate状态后重新发起新一届选举为止。

Raft日志复制（Log Replication）

在选举产生新的Leader节点后，集群系统的所有改变都将通过Leader节点，并由Leader节点同步给其他所有节点。这是通过使用一种与心跳相同的，称之为“Append Entries”的消息来完成的。

下面我们就来具体看下这个过程具体是什么样的：

首先，客户端向Leader节点发送数据变化请求“SET 5”，Leader节点接收到这个改变后，会将其添加到节点的日志条目中。

然后这个改变会在下一次发送心跳时，同步给所有的Follower节点。一旦这个改变被大部分Follower节点所接受，那么Leader节点就会正式Commit这个条目，并向Client端进行响应。

之后Leader节点会再次向所有Follower节点同步Commit请求，Follower节点完成此条目的提交，此时集群就现在系统的状态达成了一致。

如果此时再次发起一个“ADD 2”的操作，过程也是一样的，最终集群中所有的节点的值会达成7的共识。

选举冲突

在前面的节点选举的示例中，某个Follower在选举超时时间内没有接收到Leader心跳后就会转换为Candidate角色发起选举，并由其他多数Follower节点选举为Leader节点，这是一种比较理想的状况。

实际上，一旦集群中Leader节点挂掉，此时可能多个Follower节点可能会同时过了选举超时时间而变成Candidate状态，从而同时发起新一届的选举请求。如图：

两个节点都开始了同一任期的选举…

并且每一个都先于另外一个得到一个Follower节点的选票，但此时在这届任期类两个Candidate都将不会得到更多的选票了，那么在这一届的选择中就无法选出新的Leader节点了。

此时所有的节点都将进入等待状态，并重新尝试开始下一次选举。如图：

经过下一届选举，最终Node d成为新的Leader。事实上这次选举也可能会出现选举分裂的情况的，所以在实际应用中，一般都建议在集群中部署奇数个节点，例如，之前的Consul集群我们就是部署5个节点，目前就是防止偶数节点导致选举出现冲突的情况。

集群分裂

我们再来考虑另外一种极端的情况，假设集群因为某些原因（如网络切断）导致集群被切割为两块，有Leader节点的一块继续运行、没有Leader节点的一块则进入选举状态，并选出自己新的Leader节点，如图：

此时c、d、e三个节点组成集群选举产生了新的Leader节点e，并且选举任期更新为2，比节点b更高，同时两个Client分别向这两块集群发起了SET请求。由于节点b不能复制到大多数节点，所以一直处于Uncommit状态，而节点c因为能够复制到大多数节点所以可以正常commit。

当集群分裂问题恢复后，原先的Leader节点B看到更高的选举任期就会主动下台，而A和B两个节点将回滚它们未提交的条目，并匹配新leader节点c的日志，从而实现日志在整个集群中的一致性（实际上是少数节点的集群学习多数节点的集群的leader，进而完成一致性过程）。

后记

Raft 和Paxos是目前分布式系统领域中两种非常著名的解决一致性问题的共识算法，两者都能解决分布式系统中的一致性问题，但是Paxos的实现被证明非常难以理解，Raft的实现则比较简洁并且遵循人的直觉，它的出现就是为了解决 Paxos 难以理解和和难以实现的问题。

后续有机会可以再和大家一起讨论关于Paxos算法的相关的知识，谢谢大家的支持！

参考： http://www.cnblogs.com/hzmark/p/raft.html http://thesecretlivesofdata.com/raft/ https://raft.github.io/

—————END—————