前面介绍了《分布式一致性算法：Paxos》。可以看出，Paxos算法的的原理其实是比较晦涩难懂的。因为 Paxos 难懂，也难以实现，所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行效率，但是更容易理解，也更容易被用在系统开发上。

etcd项目就是使用的Raft算法，etcd被广泛应用于分布式系统中，比如k8s就是使用etcd来作为信息存储的。

Raft算法是怎样实现分布式一致性的呢？它主要有两个过程：

• 选主过程
• 基于日志复制的数据同步过程

下面来介绍一下Raft具体是怎么做的。

三种状态

Raft中，一共有三种状态。每个节点都处于某个状态，每个节点都可以在三种状态中间转换。这三种状态分别是：

• Follower状态，从结点，我们用无边的圆来表示
• Candidate状态，有资格参与竞选的结点，我们用虚线边的圆来表示
• Leader状态，主结点，用实线边的圆来表示。

选举过程

正常状态的选举

先来看一下如果系统中各结点和网络都正常，它是怎么实线主结点的选举和数据同步的。

每个节点上都有一个倒计时器，时间随机在150ms到300ms之间。节点在以下两种情况下回重置倒计时器：

• 收到选举请求
• 收到Leader结点的心跳（Heartbeat）

然后看一下选举过程：

1. 一开始，三个结点都是Follower状态，每个节点开始自己的随机倒计时。
2. 最先倒计时结束的那一个，就变成Candidate状态，开始给其它结点发送选举请求。
3. 其它结点如果收到这个请求，就重置自己的倒计时器并返回“同意”的响应。
4. Condidate结点如果收到了超过半数（包括它自己）的结点同意，就变成Leader结点，然后会不断向其它结点发送心跳（Heartbeat）来维持这个状态。

如果Leader结点不可用

这个时候如果Leader结点宕机了或由于其它原因不可用，那Follower结点收不到心跳，倒计时结束后就会产生另一个选举过程，产生另一个Leader结点。

那这个时候Leader结点C醒来了怎么办呢？它会收到来自新Leader结点A的心跳，通过对比Term，发现它的Term更高，于是自动降级为Follower状态。

如果两个结点同时计时器结束

如果两个结点同时timeout，或者由于网络的原因，存在Leader确认之前多个Follower结点变成Candidate的情况。这个时候会发生什么呢？

我们其实可以设想一下。假如有4个结点。其中两个结点同时计时器结束。这个时候两个结点都会广播选主请求。这可能导致有些结点投票给C，有些结点投票给D：

这个时候，所有结点都会重新开始计时。直到进入正常状态（只有一个节点最先计时结束）。

这里有一个小细节：Follower结点只接受最先收到的选主请求，会丢弃后来的所有选主请求。

日志复制过程

正常状态的复制

日志复制过程是基于“心跳”来做的。过程如下：

1. 首先，客户端会给Leader结点发送一个写请求；
2. Leader结点会将这个写操作先放到日志里。这里我们用红色来表示它；
3. 然后，Leader会再下次心跳的时候发送这个“写请求”；

4. 然后从节点响应，并在本地也创建这个日志；
5. 一旦Leader结点收到过半数（包括它自己）结点的确认，就持久化这个修改（我们这里用黑色来表示）。

6. Leader结点返回响应给用户，修改成功；
7. 与此同时，发送心跳给从节点，告诉他们可以持久化这个修改了；
8. 从节点收到消息后，持久化这个修改；

网络分区如何处理？

网络分区是一种分布式网络故障的现象。通俗的说，就是原本在一个网络的结点，由于网络故障，变成了两个区域，结点只能与部分结点进行通信。这样就可能会导致两个Leader结点。如图：

假设最开始网络是好的，B结点选举为Leader结点。后来出现了暂时的网络分区，B结点仍然是Leader结点，而另一个分区里面重新进行了选举，C结点成功成为新的Leader结点。

这个时候，一个客户端给B结点发送了一个写请求，设置某个变量为3：

然后B结点按照正常流程走。但是因为收不到“过半数”从节点的确认，所以一直不能持久化，只是记录日志。

这个时候另一个结点给C结点发送了一个请求，设置同样一个变量为8。C结点按照正常流程处理，所有同一网络分区的结点都能够持久化，把这个变量设置成了8。

然后网络恢复了。

B结点收到来自C结点的心跳，并且发现它的Term比自己大，于是降级成为Follower结点，并丢弃本地的日志，并根据C结点心跳发来的信息，持久化设置变量为8。

这里其实笔者有一个疑问：如果恢复分区故障前，C结点还处理了其它客户端的请求，那再恢复分区故障后，会在心跳里带上这段时间所有的修改吗？它是如何判断哪些修改属于故障期间的呢？还是把本地的日志全部发出去，那这样会不会数据量太大？

我人为这个可能要看具体的实现。笔者的猜想是，C结点应该是能够知道什么时候故障发生的（即收不到来自B结点的心跳的时候），把这个时间点存下来。继而它是可以知道哪些是属于故障期间的修改的。在故障期间，它会把这些所有的修改都发送出去。直到恢复正常网络为止。

本文所有截图和动画均来自这个动画示例，非常生动明了，推荐可以看一遍。