一、Raft 简介

1.1 Raft 简介

Raft 是一种为了治理日志复制的分布式一致性算法。Raft 呈现之前，Paxos 始终是分布式一致性算法的规范。Paxos 难以了解，更难以实现。Raft 的设计指标是简化 Paxos，使得算法既容易了解，也容易实现。

Paxos 和 Raft 都是分布式一致性算法，这个过程如同投票选举首领（Leader），参选者（Candidate）须要压服大多数投票者（Follower）投票给他，一旦选举出首领，就由首领发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。

Raft 能够解决分布式 CAP 实践中的 CP，即 一致性（C：Consistency）和 分区容忍性（P：Partition Tolerance），并不能解决 可用性（A：Availability）的问题。

1.2 散布一致性

分布式一致性 (distributed consensus) 是分布式系统中最根本的问题，用来保障一个分布式系统的可靠性以及容错能力。简略来说，分布式一致性是指多个服务器的放弃状态统一。

在分布式系统中，可能呈现各种意外（断电、网络拥塞、CPU/ 内存耗尽等等），使得服务器宕机或无法访问，最终导致无奈和其余服务器放弃状态统一。为了应答这种状况，就须要有一种一致性协定来进行容错，使得分布式系统中即便有局部服务器宕机或无法访问，整体仍然能够对外提供服务。

以容错形式达成统一，天然不能要求所有服务器都达成统一状态，只有 超过半数 以上的服务器达成统一就能够了。假如有 N 台服务器，大于等于 N / 2 + 1 台服务器就算是半数以上了。

1.3 复制状态机

复制状态机（Replicated State Machines）是指一组服务器上的状态机产生雷同状态的正本，并且在一些机器宕掉的状况下也能够持续运行。一致性算法治理着来自客户端指令的复制日志。状态机从日志中解决雷同程序的雷同指令，所以产生的后果也是雷同的。

复制状态机通常都是基于复制日志实现的，如上图。每一个服务器存储一个蕴含一系列指令的日志，并且依照日志的程序进行执行。每一个日志都依照雷同的程序蕴含雷同的指令，所以每一个服务器都执行雷同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生雷同的状态和同样的序列。

保障复制日志雷同就是一致性算法的工作了。在一台服务器上，一致性模块接管客户端发送来的指令而后减少到本人的日志中去。它和其余服务器上的一致性模块进行通信来保障每一个服务器上的日志最终都以雷同的程序蕴含雷同的申请，只管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机依照日志程序解决他们，而后输入后果被返回给客户端。因而，服务器集群看起来造成一个高牢靠的状态机。

理论零碎中应用的一致性算法通常含有以下个性：

安全性保障（相对不会返回一个谬误的后果）：在非拜占庭谬误状况下，包含网络提早、分区、丢包、冗余和乱序等谬误都能够保障正确。

可用性：集群中只有有大多数的机器可运行并且可能互相通信、和客户端通信，就能够保障可用。因而，一个典型的蕴含 5 个节点的集群能够容忍两个节点的失败。服务器被进行就认为是失败。他们当有稳固的存储的时候能够从状态中复原回来并重新加入集群。

不依赖时序来保障一致性：物理时钟谬误或者极其的音讯提早只有在最坏状况下才会导致可用性问题。

通常状况下，一条指令能够尽可能快的在集群中大多数节点响应一轮近程过程调用时实现。小局部比较慢的节点不会影响零碎整体的性能。

1.4 RAFT 利用

通过 RAFT 提供的复制状态机，能够解决分布式系统的复制、修复、节点治理等问题。Raft 极大的简化以后分布式系统的设计与实现，让开发者只关注于业务逻辑，将其形象实现成对应的状态机即可。基于这套框架，能够构建很多分布式应用：

分布式锁服务

分布式存储系统，比方分布式音讯队列、分布式块零碎、分布式文件系统、分布式表格零碎等，比方赫赫有名的 Redis 就是基于 Raft 实现分布式一致性

高牢靠元信息管理，比方各类 Master 模块的 HA

二、Raft 根底

Raft 将一致性问题分解成了三个子问题：选举 Leader、日志复制 、 安全性。

在后续章节，会具体解说这个子问题。当初，先理解一下 Raft 的一些外围概念。

2.1 服务器角色

在 Raft 中，任何时刻，每个服务器都处于这三个角色之一：

Leader – 领导者，通常一个零碎中是一 主（Leader）多从（Follower）。Leader 负责解决所有的客户端申请。

Follower – 跟随者，不会发送任何申请，只是简略的 响应来自 Leader 或者 Candidate 的申请。

Candidate – 参选者，选举新 Leader 时的长期角色。

图示阐明：

• Follower 只响应来自其余服务器的申请。在肯定时限内，如果 Follower 接管不到音讯，就会转变成 Candidate，并发动选举。

• Candidate 向 Follower 发动投票申请，如果取得集群中半数以上的选票，就会转变为 Leader。

• 在一个 Term 内，Leader 始终保持不变，直到下线了。Leader 须要周期性向所有 Follower 发送心跳音讯，以阻止 Follower 转变为 Candidate。

2.2 任期

Raft 把工夫宰割成任意长度的 任期（Term），任期用间断的整数标记。每一段任期从一次 选举 开始。Raft 保障了在一个给定的任期内，最多只有一个领导者。

如果选举胜利，Leader 会治理整个集群直到任期完结。

如果选举失败，那么这个任期就会因为没有 Leader 而完结。

不同服务器节点察看到的任期转换状态可能不一样：

服务器节点可能察看到屡次的任期转换。

服务器节点也可能察看不到任何一次任期转换。

任期在 Raft 算法中充当逻辑时钟的作用，使得服务器节点能够查明一些过期的信息（比方过期的 Leader）。每个服务器节点都会存储一个以后任期号，这一编号在整个期间内枯燥的增长。当服务器之间通信的时候会替换以后任期号。

如果一个服务器的以后任期号比其他人小，那么他会更新本人的编号到较大的编号值。

如果一个 Candidate 或者 Leader 发现自己的任期号过期了，那么他会立刻复原成跟随者状态。

如果一个节点接管到一个蕴含过期的任期号的申请，那么他会间接回绝这个申请。

数据可视化的利用场景越来越宽泛，数据能够出现为更多丰盛的可视化模式，使用户可能更加轻易、便捷的获取并了解数据传播的信息。

2.3 RPC

Raft 算法中服务器节点之间的通信应用 近程过程调用（RPC）。根本的一致性算法只须要两种 RPC：

RequestVote RPC – 申请投票 RPC，由 Candidate 在选举期间发动。

AppendEntries RPC – 附加条目 RPC，由 Leader 发动，用来复制日志和提供一种心跳机制。

三、选举 Leader

3.1 选举规定

Raft 应用一种心跳机制来触发 Leader 选举。Leader 须要周期性的向所有 Follower 发送心跳音讯，以此维持本人的权威并阻止新 Leader 的产生。

每个 Follower 都设置了一个 随机的竞选超时工夫，个别为 150ms ~ 300ms，如果在竞选超时工夫内没有收到 Leader 的心跳音讯，就会认为以后 Term 没有可用的 Leader，并发动选举来选出新的 Leader。开始一次选举过程，Follower 先要减少本人的以后 Term 号，并转换为 Candidate。

Candidate 会并行的向集群中的所有服务器节点 发送投票申请（RequestVote RPC），它会放弃以后状态直到以下三件事件之一产生：

本人成为 Leader

其余的服务器成为 Leader

没有任何服务器成为 Leader

3.1.1 本人成为 Leader

当一个 Candidate 从整个集群 半数以上 的服务器节点取得了针对同一个 Term 的选票，那么它就博得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票，依照先来先服务（FIFO）的准则。要求半数以上选票的规定确保了最多只会有一个 Candidate 博得此次选举。

一旦 Candidate 博得选举，就立刻成为 Leader。而后它会向其余的服务器发送心跳音讯来建设本人的权威并且阻止新的领导人的产生。

3.1.2 其余的服务器成为 Leader

期待投票期间，Candidate 可能会从其余的服务器接管到申明它是 Leader  的 AppendEntries RPC。

如果这个 Leader 的 Term 号（蕴含在此次的 RPC 中）不小于 Candidate 以后的 Term，那么 Candidate 会抵赖 Leader 非法并回到 Follower 状态。

如果此次 RPC 中的 Term 号比本人小，那么 Candidate 就会回绝这个音讯并持续放弃 Candidate 状态。

3.1.3 没有任何服务器成为 Leader

如果有多个 Follower 同时成为 Candidate，那么选票可能会被瓜分以至于没有 Candidate 能够博得半数以上的投票。当这种状况产生的时候，每一个 Candidate 都会竞选超时，而后通过减少以后 Term 号来开始一轮新的选举。然而，没有其余机制的话，选票可能会被有限的反复瓜分。

Raft 算法应用随机选举超时工夫的办法来确保很少会产生选票瓜分的状况，就算产生也能很快的解决。为了阻止选票起初就被瓜分，竞选超时工夫是一个 随机的工夫，在一个固定的区间（例如 150-300 毫秒）随机抉择，这样能够把选举都扩散开。

以至于在大多数状况下，只有一个服务器会超时，而后它博得选举，成为 Leader，并在其余服务器超时之前发送心跳包。

同样的机制也被用在选票瓜分的状况下：每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时工夫，而后在超时工夫内期待投票的后果；这样缩小了在新的选举中另外的选票瓜分的可能性。

了解了下面的选举规定后，咱们通过动图来加深意识。

3.2 单 Candidate 选举

1. 下图示意一个分布式系统的最后阶段，此时只有 Follower，没有 Leader。Follower A 期待一个随机的选举超时工夫之后，没收到 Leader 发来的心跳音讯。因而，将 Term 由 0 减少为 1，转换为 Candidate，进入选举状态。

2)此时，A 向所有其余节点发送投票申请。

1. 其它节点会对投票申请进行回复，如果超过半数以上的节点投票了，那么该 Candidate 就会立刻变成 Term 为 1 的 Leader。

1. Leader 会周期性地发送心跳音讯给所有 Follower，Follower 接管到心跳包，会从新开始计时。

3.3 多 Candidate 选举

1. 1 如果有多个 Follower 成为 Candidate，并且所取得票数雷同，那么就须要从新开始投票。例如下图中 Candidate B 和 Candidate D 都发动 Term 为 4 的选举，且都取得两票，因而须要从新开始投票。

2) 当从新开始投票时，因为每个节点设置的随机竞选超时工夫不同，因而能下一次再次出现多个 Candidate 并取得同样票数的概率很低。

四、日志复制

4.1 日志格局

日志由含日志索引（log index）的日志条目（log entry）组成。每个日志条目蕴含它被创立时的 Term 号（下图中方框中的数字），和一个复制状态机须要执行的指令。如果一个日志条目被复制到半数以上的服务器上，就被认为能够提交（Commit）了。

日志条目中的 Term 号被用来查看是否呈现不统一的状况。

日志条目中的日志索引（一个整数值）用来表明它在日志中的地位。

Raft 日志同步保障如下两点；图示阐明：

如果不同日志中的两个日志条目有着雷同的日志索引和 Term，则 它们所存储的命令是雷同的。

这个个性基于这条准则：Leader 最多在一个 Term 内、在指定的一个日志索引上创立一条日志条目，同时日志条目在日志中的地位也从来不会扭转。

如果不同日志中的两个日志条目有着雷同的日志索引和 Term，则 它们之前的所有条目都是齐全一样的。

这个个性由 AppendEntries RPC 的一个简略的一致性查看所保障。在发送 AppendEntries RPC 时，Leader 会把新日志条目之前的日志条目标日志索引和 Term 号一起发送。如果 Follower 在它的日志中找不到蕴含雷同日志索引和 Term 号的日志条目，它就会回绝接管新的日志条目。

4.2 日志复制流程

Leader 负责解决所有客户端的申请。

Leader 把申请作为日志条目退出到它的日志中，而后并行的向其余服务器发送 AppendEntries RPC 申请，要求 Follower 复制日志条目。

Follower 复制胜利后，返回确认音讯。

当这个日志条目被半数以上的服务器复制后，Leader 提交这个日志条目到它的复制状态机，并向客户端返回执行后果。

留神：如果 Follower 解体或者运行迟缓，再或者网络丢包，Leader 会一直的反复尝试发送 AppendEntries RPC 申请（只管曾经回复了客户端），直到所有的跟随者都最终复制了所有的日志条目。

上面，通过一组动图来加深意识：

1)来自客户端的批改都会被传入 Leader。留神该批改还未被提交，只是写入日志中。

2)Leader 会把批改复制到所有 Follower。

3)Leader 会期待大多数的 Follower 也进行了批改，而后才将批改提交。

4)此时 Leader 会告诉的所有 Follower 让它们也提交批改，此时所有节点的值达成统一。

4.3 日志一致性

个别状况下，Leader 和 Followers 的日志保持一致，因而日志条目一致性查看通常不会失败。然而，Leader 解体可能会导致日志不统一：旧的 Leader 可能没有齐全复制完日志中的所有条目。

4.3.1 Leader 和 Follower 日志不统一的可能

Leader 和 Follower 可能存在多种日志不统一的可能。

图示阐明：上图论述了 Leader 和 Follower 可能存在多种日志不统一的可能，每一个方框示意一个日志条目，外面的数字示意任期号。

当一个 Leader 胜利入选时，Follower 可能呈现以下状况（a-f）：

存在未更新日志条目，如（a、b）。

存在未提交日志条目，如（c、d）。

或两种状况都存在，如（e、f）。

例如，场景 f 可能会这样产生，某服务器在 Term2 的时候是 Leader，已附加了一些日志条目到本人的日志中，但在提交之前就解体了；很快这个机器就被重启了，在 Term3 从新被选为 Leader，并且又减少了一些日志条目到本人的日志中；在 Term 2 和 Term 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里始终处于宕机状态。

4.3.2 Leader 和 Follower 日志统一的保障

Leader 通过强制 Followers 复制它的日志来解决日志的不统一，Followers 上的不统一的日志会被 Leader 的日志笼罩。

Leader 为了使 Followers 的日志同本人的统一，Leader 须要找到 Followers 同它的日志统一的中央，而后笼罩 Followers 在该地位之后的条目。

Leader 会从后往前试，每次日志条目失败后尝试前一个日志条目，直到胜利找到每个 Follower 的日志统一位点，而后向后逐条笼罩 Followers 在该地位之后的条目。

五、安全性

后面形容了 Raft 算法是如何选举 Leader 和复制日志的。

Raft 还减少了一些限度来欠缺 Raft 算法，以保障安全性：保障了任意 Leader 对于给定的 Term，都领有了之前 Term 的所有被提交的日志条目。

5.1 选举限度

领有最新的已提交的日志条目标 Follower 才有资格成为 Leader。

Raft 应用投票的形式来阻止一个 Candidate 博得选举除非这个 Candidate 蕴含了所有曾经提交的日志条目。Candidate 为了博得选举必须分割集群中的大部分节点，这意味着每一个曾经提交的日志条目在这些服务器节点中必定存在于至多一个节点上。如果 Candidate 的日志至多和大多数的服务器节点一样新（这个新的定义会在上面探讨），那么他肯定持有了所有曾经提交的日志条目。

RequestVote RPC 实现了这样的限度：RequestVote RPC 中蕴含了 Candidate 的日志信息，Follower 会回绝掉那些日志没有本人新的投票申请。

5.1.1 场如何判断哪个日志条目比拟新？

Raft 通过比拟两份日志中最初一条日志条目标日志索引和 Term 来判断哪个日志比拟新。

先判断 Term，哪个数值大即代表哪个日志比拟新。

如果 Term 雷同，再比拟 日志索引，哪个数值大即代表哪个日志比拟新。

5.1.2 提交旧任期的日志条目

一个以后 Term 的日志条目被复制到了半数以上的服务器上，Leader 就认为它是能够被提交的。如果这个 Leader 在提交日志条目前就下线了，后续的 Leader 可能会笼罩掉这个日志条目。

图示阐明：上图解释了为什么 Leader 无奈对旧 Term 的日志条目进行提交。

• 阶段 (a)，S1 是 Leader，且 S1 写入日志条目为 (Term 2，日志索引 2），只有 S2 复制了这个日志条目。

• 阶段 (b)，S1 下线，S5 被选举为 Term3 的 Leader。S5 写入日志条目为 (Term 3，日志索引 2）。

• 阶段 (c)，S5 下线，S1 从新上线，并被选举为 Term4 的 Leader。此时，Term 2 的那条日志条目曾经被复制到了集群中的大多数节点上，然而还没有被提交。

• 阶段 (d)，S1 再次下线，S5 从新上线，并被从新选举为 Term3 的 Leader。而后 S5 笼罩了日志索引 2 处的日志。

• 阶段 (e)，如果阶段 (d) 还未产生，即 S1 再次下线之前，S1 把本人主导的日志条目复制到了大多数节点上，那么在后续 Term 外面这些新日志条目就会被提交。这样在同一时刻就同时保障了，之前的所有旧日志条目就会被提交。

Raft 永远不会通过计算正本数目的形式去提交一个之前 Term 内的日志条目。只有 Leader 以后 Term 里的日志条目通过计算正本数目能够被提交；一旦以后 Term 的日志条目以这种形式被提交，那么因为日志匹配个性，之前的日志条目也都会被间接的提交。

当 Leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的 Term，这在提交规定上产生了额定的复杂性。在其余的一致性算法中，如果一个新的领导人要从新复制之前的任期里的日志时，它必须应用以后新的任期号。

Raft 应用的办法更加容易分别出日志，因为它能够随着工夫和日志的变动对日志保护着同一个任期编号。另外，和其余的算法相比，Raft 中的新领导人只须要发送更少日志条目（其余算法中必须在他们被提交之前发送更多的冗余日志条目来为他们从新编号）。

六、日志压缩

在理论的零碎中，不能让日志有限收缩，否则零碎重启时须要花很长的工夫进行复原，从而影响可用性。Raft 采纳对整个零碎进行快照来解决，快照之前的日志都能够抛弃。

每个正本独立的对本人的零碎状态生成快照，并且只能对曾经提交的日志条目生成快照。快照蕴含以下内容：

日志元数据。最初一条已提交的日志条目标日志索引和 Term。这两个值在快照之后的第一条日志条目标 AppendEntries RPC 的完整性检查的时候会被用上。

零碎以后状态。

当 Leader 要发送某个日志条目，落后太多的 Follower 的日志条目会被抛弃，Leader 会将快照发给 Follower。或者新上线一台机器时，也会发送快照给它。

生成快照的频率要适中，频率过高会耗费大量 I/O 带宽；频率过低，一旦须要执行复原操作，会失落大量数据，影响可用性。举荐当日志达到某个固定的大小时生成快照。生成一次快照可能耗时过长，影响失常日志同步。能够通过应用 copy-on-write 技术防止快照过程影响失常日志同步。

阐明：本文仅论述 Raft 算法的核心内容，不包含算法论证、评估等

七、参考资料

1.Raft 一致性算法论文原文
2.Raft 一致性算法论文译文
3.Raft 作者解说视频
4.Raft 作者解说视频对应的 PPT
5. 分布式系统的 Raft 算法
6.Raft 算法详解
7.Raft: Understandable Distributed Consensus
8.sofa-jraft – 蚂蚁金服的 Raft 算法实现库（Java 版)

​作者：vivo 互联网服务器团队 -ZhangPeng