什么是Raft算法?

Raft算法是用于解决分布式系统中一致性问题的算法。在Raft算法之前，Lamport老爷爷提出的Paxos算法过于晦涩，工程实现难度高。因此Raft算法作为Paxos的替代算法出现。Raft算法相比于Paxos算法，更易理解，实现简单。

什么是一致性（Consensus）？

在描述Raft算法前，我们先确定一致性的概念。一致性是分布式系统中的经典问题。简单的来说，一致性就是指多台机器中的数据保持一致。而一致性算法就是确保多台机器能够同步数据的算法。

考虑下面的一个场景，现在拥有一个只包含一台服务器的单点服务，服务中保存着一个变量X，现在客户端希望将X的值设置为8。

客户端-服务器.PNG

如果服务仅仅运行在一台服务器上，那么客户端直接向该服务器发送设置X=8的请求即可。如下图所示，服务器的值被设置为8。

客户端-服务器.PNG

然而如果服务运行在拥有三台机器的集群中呢？

客户端-集群.PNG

此时只有节点A中的X被设为了8。然而我们不希望简单的向A，B，C三台服务器发送三次X=8的请求，我们希望服务对外的接口依旧保持简单不变。此时就依赖于一致性算法来对集群中的数据进行同步了。

一致性从严格程度上大致上可以分为三类：

• 强一致性
  强一致性可以理解为在任意时刻，系统总能返回正确的数据，并且所有节点中的数据是一样的。同一时间点，你在节点A中获取到key1的值与在节点B中获取到key1的值应该都是一样的。根据CAP 理论，这种实现需要牺牲可用性。
• 弱一致性
  系统并不保证客户的访问都会返回最新的更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。
• 最终一致性
  最终一致性是弱一致性的一种特例，它保证用户最终能够读取到某操作对系统特定数据的更新。但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。也可以简单的理解为在一段时间后，节点间的数据会最终达到一致状态。对于最终一致性最好的例子就是DNS系统，由于DNS多级缓存的实现，所以修改DNS记录后不会在全球所有DNS服务节点生效，需要等待DNS服务器缓存过期后向源服务器更新新的记录才能实现。

Raft算法描述

Raft一致性算法中主要包含两个重要步骤：领导者选举（Leader Election）和日志复制（Log Replication）。

领导者选举（Leader Election）

首先Raft将集群中的机器角色分为三种：领导者（Leader），跟随者（Follower）和候选者（Candidate）。

每一台机器的默认开始时的角色是Follower。

1. 如图，初始状态下集群内的三台机器都处于Follower的状态：

   
   Follower.PNG

2. 如果Follower在一段时间内没有收到来自Leader的消息，那么它就自动转化为Candidate状态，如图，机器A成为了Candidate：

   
   Candidate.PNG

3. 机器A成为Candidate后，向集群中的其他机器发送投票请求，表示自己希望成为Leader。

4. 机器A获得集群中大多数其他机器的投票后，自动成为Leader，如图：

   
   Leader.PNG

上面的过程被称为领导者选举（Leader Election）。

日志复制（Log Replication）

在机器A成为Leader后，下面是一个例子来描述Raft协议如何同步此集群内的数据。

1. 首先客户发送请求给集群，希望将X的值设置为5。

2. Leader收到请求后，首先将X=5的请求写入日志。此时日志尚未提交，因此X的值并没有产生变化。

   
   log.PNG

3. Leader将X=5的请求发送给集群中的其他机器。

   
   log.PNG

4. 其他机器收到请求后也将X=5的请求写入日志，返回成功结果给Leader。此时X的值依旧未更新。

   
   log.PNG

5. Leader收到其他机器写入日志成功的消息后（大部分成功即可），将X=5的请求日志提交，此时机器A中的X值成功更新为5。并通知其他机器日志已经提交。

   
   commit log.PNG

6. 其他机器收到日志提交命令后，将日志提交，此时X的值成功更新为5。

   
   commit log.PNG

7. 至此，这个集群真正达成了一致性状态。

领导者选举（Leader Election）

前面已经概述了领导者选举的步骤，下面我们将阐述其中两个关键的超时时间配置，它们控制着领导者选举的生命周期。

选举超时时间（Election Timeout）

选举超时时间是Follower在自动转化为Candidate前的等待时间。

1. Raft算法开始时，集群中所有机器默认处于Follower状态，等待超过Election Timeout定义的时间后，自动转化为Candidate状态。

选举超时时间是在固定值（1000ms）的基础上，增加150ms到300ms随机值的值。

2. 因此，集群内最先到达Election Timeout的机器转化为Candidate状态，开始一个选举任期（Term）。此时其他机器处于Follower状态。如下图所示，此时机器B成为了Candidate，并且已经获得了一张投票，这张投票来自于自己。

Candidate.PNG

3. 成为Candidate后，机器C向其他机器发送投票请求（Request Vote）。

Candidate.PNG

4. 其他机器收到投票请求后，如果在此任期内（Term）还没有投票，则会投票给该Candidate。然后重置自己的选举超时时间（Election Timeout）。

Vote.PNG

5. 最终获得大多数投票的Candidate成功成为Leader。如图所示：

   
   Leader.PNG

心跳时间（Heartbeat Timeout）

1. Candidate成为Leader后，会定时向Follower发送Append Entries消息，发送消息的时间间隔为Heartbeat Timeout，它的默认值为100ms。

   
   Heartbeat.PNG

2. Follower收到Append Entries消息后，重置自己的选举超时时间。

3. 如果Follower在选举超时时间内未收到Append Entries消息，则会自动转化为Candidate，开始新一轮的领导选举（Term++）。

   
   Vote.PNG

选举失败

考虑集群中拥有四台机器，此时同时有两台机器都成为了Candidate，并且都获得2票，那么此轮选举失败。Raft协议会等待集群选举时间超时后重新发起下一次选举，直到选举成功。

参考文章：

• http://thesecretlivesofdata.com/raft/
• https://zhuanlan.zhihu.com/p/32052223
• https://www.zybuluo.com/zhangnian88123/note/485870