Raft算法解析
什么是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。
-
如图，初始状态下集群内的三台机器都处于Follower的状态：
Follower.PNG
-
如果Follower在一段时间内没有收到来自Leader的消息，那么它就自动转化为Candidate状态，如图，机器A成为了Candidate：
Candidate.PNG
-
机器A成为Candidate后，向集群中的其他机器发送投票请求，表示自己希望成为Leader。
-
机器A获得集群中大多数其他机器的投票后，自动成为Leader，如图：
Leader.PNG
上面的过程被称为领导者选举（Leader Election）。
日志复制（Log Replication）
在机器A成为Leader后，下面是一个例子来描述Raft协议如何同步此集群内的数据。
-
首先客户发送请求给集群，希望将X的值设置为5。
-
Leader收到请求后，首先将X=5的请求写入日志。此时日志尚未提交，因此X的值并没有产生变化。
log.PNG
-
Leader将X=5的请求发送给集群中的其他机器。
log.PNG
-
其他机器收到请求后也将X=5的请求写入日志，返回成功结果给Leader。此时X的值依旧未更新。
log.PNG
-
Leader收到其他机器写入日志成功的消息后（大部分成功即可），将X=5的请求日志提交，此时机器A中的X值成功更新为5。并通知其他机器日志已经提交。
commit log.PNG
-
其他机器收到日志提交命令后，将日志提交，此时X的值成功更新为5。
commit log.PNG
-
至此，这个集群真正达成了一致性状态。
领导者选举（Leader Election）
前面已经概述了领导者选举的步骤，下面我们将阐述其中两个关键的超时时间配置，它们控制着领导者选举的生命周期。
选举超时时间（Election Timeout）
选举超时时间是Follower在自动转化为Candidate前的等待时间。
- Raft算法开始时，集群中所有机器默认处于Follower状态，等待超过Election Timeout定义的时间后，自动转化为Candidate状态。
选举超时时间是在固定值（1000ms）的基础上，增加150ms到300ms随机值的值。
- 因此，集群内最先到达Election Timeout的机器转化为Candidate状态，开始一个选举任期（Term）。此时其他机器处于Follower状态。如下图所示，此时机器B成为了Candidate，并且已经获得了一张投票，这张投票来自于自己。
Candidate.PNG
- 成为Candidate后，机器C向其他机器发送投票请求（Request Vote）。
Candidate.PNG
- 其他机器收到投票请求后，如果在此任期内（Term）还没有投票，则会投票给该Candidate。然后重置自己的选举超时时间（Election Timeout）。
Vote.PNG
-
最终获得大多数投票的Candidate成功成为Leader。如图所示：
Leader.PNG
心跳时间（Heartbeat Timeout）
-
Candidate成为Leader后，会定时向Follower发送Append Entries消息，发送消息的时间间隔为Heartbeat Timeout，它的默认值为100ms。
Heartbeat.PNG
-
Follower收到Append Entries消息后，重置自己的选举超时时间。
-
如果Follower在选举超时时间内未收到Append Entries消息，则会自动转化为Candidate，开始新一轮的领导选举（Term++）。
Vote.PNG
选举失败
考虑集群中拥有四台机器，此时同时有两台机器都成为了Candidate，并且都获得2票，那么此轮选举失败。Raft协议会等待集群选举时间超时后重新发起下一次选举，直到选举成功。
