一文搞懂Raft算法-Raft算法详解

本文已收录于：github.com/danmuking/a…

哈喽，大家哈，我是 DanMu。最近在在学习一些分布式的知识，在网上看了不少分布式的文章，但总觉得它们要么太过专业，看了等于没看，学了等于没学，要么就过于简化，看了还是等于没看，学了还是等于没学。想要找到一篇既易懂又深入的分布式文章确实不易。既然网络上的资源无法满足我的需求，我决定亲自下场，为大家带来这篇深入分析Raft分布式共识算法的文章。通过这篇文章，你将能够深入理解Raft的精髓，掌握其背后的原理和机制。拒绝“如会”，从我做起，Let's go。

什么是分布式共识算法

在传统的单体系统中，通常只有一个节点，这个节点负责完成系统的所有功能，如果想要修改某个数据，只需要考修改单个节点的数据。但是在分布式系统当中，同一份数据可能会在多个节点中存在多个副本，那么我们在修改数据就涉及到多个节点的操作。由于多节点操作很难保证操作的原子性，所以在某一个时刻，不同节点中的数据可能存在不一致，要如何保证多个节点的数据一致性，这就是分布式共识算法的作用。 总结一下，分布式共识算法主要目的是为了保证同一份数据在多个节点上的一致性，以满足**CP**要求。

如果不了解什么是CP可以看这篇文章

共识（Consensus）与一致性（Consistency）的区别：一致性是指数据不同副本之间的差异，而共识是指达成一致性的方法与过程。由于翻译的关系，很多中文资料把 Consensus 同样翻译为一致性，导致网络上大量的“二手中文资料”将这两个概念混淆起来，如果你在网上看到“分布式一致性算法”，应明白其指的其实是“Distributed Consensus Algorithm”。

Raft算法

接下来，我们就要进入今天的主题，Raft算法，先用一张图片来粗略认识一下Raft算法： 这张图片大致描述了Raft工作的基本流程，客户端向Leader发送命令，然后由Leader将状态同步到所有的Follower中，在这个过程中客户端只会与Leader进行交互，数据只会单向由Leader流向Follower。Raft的大致流程还是相当简单的，别急，这才是开始，接下来，正式进入Raft算法详解。

Raft中的角色

在Raft算法中，一共存在三种角色，分别是Leader、Follower以及Candidate。这些角色各自扮演着不同的作用，并在特定条件下进行转换。

• **Leader**：**Leader**负责处理所有的客户端请求；如果一个客户端向Follower发起请求，后者会将它重定向到Leader。正常情况下，集群中有且只有一个**Leader**，剩下的都是Follower。Leader会不断地向Follower发送心跳信息以维护其领导地位，并确保集群的稳定性。
• **Candidate**：Candidate是一个特殊的角色，在正常运行是不会出现，主要用于在集群中的**Leader**下线时选出重新选出**Leader**。
• **Follower**：**Follower**** 都是被动的的角色**，它们不会主动发出请求，只会简单响应来自**Leader**和 **Candidate**的请求。

在任意时刻，Raft中的每个节点处于总是处于三种角色之一，这三种角色之间的转换关系是这样的

• 如果一个Follower某段时间内收不到Leader的请求，它会变成一个Candidate然后发起一轮选举；
• 获得大多数选票的Candidate将成为新的Leader
• 通常情况下，除非发生故障，否则在任的**Leader**不会主动放弃**Leader**身份。

任期（Term）

Raft算法，作为一个由Leader引领的强一致性算法，引入了“任期”（Term）的概念。Term的变化反应了Leader的变化，每个Term的开始都伴随着Leader的选举。一旦Leader成功当选，它将在整个Term期间负责管理整个集群。Term通过单调递增的数字来表示，确保了我们能够清晰地区分不同的领导周期。

为什么需要区分消息是由哪任Leader发出的呢？前面不是说同一个时刻只存在一个Leader吗？确实是这样，但是不要忘记，消息在网络中传递是需要时间的。有可能在消息传递过程中，当前的Leader出现了问题，并且完成了新Leader的选举，那么当消息到达时，当前Leader就已经不是发送消息的Leader了。生活就是这样出处充满惊喜。

通过上面这部分，现在对于Raft的名词，我们已经有了基本的了解，接下来，就是Raft算法的重头戏，Raft是如何保证同一份数据在多个节点上的一致性的呢？这主要由两个部分组成：

1. 同一个时刻最多只允许存在一个Leader，保证客户端只会与同一个Leader进行交互。
2. 客户端提交的变更操作需要由Leader同步给所有Follower，Leader现将操作记入日志，只有半数以上的Follower返回ACK后，Leader才将该日志提交，并向客户端返回成功。

这其中就包含两个重要的问题：

1. 如何保证同一时刻只存在一个**Leader**
2. **Leader**如何将数据同步给所有**Follower**

此外，Raft还额外引入了一些限制来保证算法的安全性，接下来我们逐个进行分析。

Leader选举

Raft 使用心跳（heartbeat）触发Leader选举。在正常情况下Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就将认为当前Leader已经下线，需要发起一次Leader选举。 Follower首先会将当前Term加一，然后转换为Candidate角色。它首先给自己投票并且要求其他节点进行投票，在一次选举中，每个节点只能进行一次投票。

投票规则

节点投票需要遵守两个规则：

1. 先到先得，谁先请求就把票投给谁
2. 只有请求投票的节点的日志进度不落后于当前节点的日志进度，才进行投票，否则忽略请求。具体规则会在之后进一步详细说明。

为什么要有2.这个限制呢？ 前面提到了，日志只有被同步到半数以上的节点后才会提交，因此集群中一定有半数以上的节点具有最新的日志，2.能够保证选出的Leader一定含有最新的数据。所以Raft中的Leader一定是包含已经提交的全量数据。这可以避免Leader覆盖已经提交的数据

需要获得“大多数选票”这一限制条件，决定了最多只会有一个Candidate赢得选举 。 投票结果有以下三种情况：

• 该节点赢得了多数的选票，成功选举为Leader；
• 该节点收到了新Leader的消息，表示有其它服务器已经抢先当选了Leader，这时候就需要根据Term来判断这个Leader的合法性（这个合法性只是对于当前节点来说，就算当前节点认为Leader不合法，但是只要半数以上节点同意，那么该节点仍然是Leader），如果这个 Leader的任期Term：
  1. 大于等于这个Candidate的Term：那该Candidate就承认这个Leader是合法的，然后回归到Follower状态。
  2. 小于这个Candidate的Term：拒绝这个通知，仍然留在Candidate状态。
• 没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。如果没有额外的预防措施，这种投票分裂的情况可能会无限持续下去。因此需要一些额外的处理。

避免无限循环的投票分裂：随机选举超时

在投票过程中有这样一种情况，如果集群中有三个节点，在某个时刻，Leader下线，三个节点同时开始选举，那么每个节点都会先给自己一票，没有一个节点可以获得半数以上的选票。每个节点都会超时，然后开始又同时开始第二轮选举，又投自己一票。然后第三轮、第四轮... 为了避免这种情况的发生，Raft使用随机选举超时来确保投票分裂只会非常偶然地发生，并且发生之后能很快恢复正常。在设置超时时间的时候，会从一个区间内随机选择一个超时时间，让节点的超时时间分散，避免上述情况的发生。

日志同步

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目加入到它的日志中（注意，这时候没有提交），然后并行的向Follower复制这条日志。当这条日志被复制到大多数服务器上，Leader将这条日志提交并向客户端返回执行结果。 某些Followers可能没有成功的复制日志，Leader会无限的重试直到所有的Followers最终存储了所有的日志条目。

日志的结构

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（Term）和内容。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。这里直接引用原论文的图 Raft日志同步保证如下三点：

• 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
• 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。
• Leader绝不会覆盖或删除自己的日志，只会追加 （Leader Append-Only）

第一条特性源于Leader在一个Term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。 第二条特性源于同步日志时的一个简单的一致性检查。当发送一个同步日志请求时，Leader会把新日志条目紧接着之前的条目的log index和Term都包含在里面。如果Follower没有在它的日志中找到log index和Term都相同的日志，它就会拒绝新的日志条目。 第三条特性是因为选举时的限制，根据前面提到的投票规则，成为Leader的结点里的日志一定拥有所有已被多数节点拥有的日志条目，所以先前的日志条目很可能已经被提交，因此不可以删除之前的日志。

日志不一致的场景

一般情况下，Leader和Followers的日志保持一致，因此日志同步时的一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。 上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。 **Leader**通过强制**Followers**复制它的日志来处理日志的不一致，**Followers**上的不一致的日志会被**Leader**的日志覆盖。 Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。 Leader会最新的日志位置往前试，每次同步日志失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

安全

前面介绍了 Raft 如何选举Leader及如何同步日志。但是，到目前为止已经描述的那些机制，还不足以确保Leader不会覆盖或删除自己的日志。 Raft额外增加了如下两条限制以保证安全性：

• 拥有最新的已提交的日志的**Follower**才有资格成为**Leader**，这一点实际上在前面已经提到，在这里对它进行更详细的说明。

这个保证是在投票时实现的，Candidate在请求其他节点投票时，要带上自己的最后一条日志的Term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的新，则拒绝投票。 日志比较有两个原则：

1. 如果本地的最后一条log entry的Term更大，则Term大的更新，
2. 如果Term一样大，则log index更大的更新。

• **Leader**只能提交自己任期内的日志，如果存在之前任期的日志，只能通过提交当期任期的日志来间接提交。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况，来看看下面这种情况：

1. 在阶段a，Term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步（没提交）写入了S2；
2. 在阶段b，S1下线，触发一次新的选主，此时S5被选为新的Leader，此时系统Term为3，且写入了日志（term, index）为（3， 2）;
3. S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统Term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）被提交了。
4. 在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. Term = 5 > 4，2. 最新的日志为（3，2），比大多数节点（如S2/S3``/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。这就违背了Raft算法已提交日志不能被修改的要求。

增加上述限制后，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前Term（2）的日志，直到S1在当前Term（4）产生的日志（4， 4）被大多数Followers确认，见e，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

点关注，不迷路

好了，以上就是这篇文章的全部内容了，如果你能看到这里，非常感谢你的支持！ 如果你觉得这篇文章写的还不错， 求点赞👍 求关注❤️ 求分享👥 对暖男我来说真的 非常有用！！！ 白嫖不好，创作不易，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！ 如果本篇博客有任何错误，请批评指教，不胜感激 ！

最后推荐我的IM项目DiTing（github.com/danmuking/D…），致力于成为一个初学者友好、易于上手的 IM 解决方案，希望能给你的学习、面试带来一点帮助，如果人才你喜欢，给个Star⭐叭！

参考资料

www.cnblogs.com/yrxing/p/16… www.qin.news/Raft/ zhuanlan.zhihu.com/p/32052223