论文下载
前言
2014年，一个名为 Raft 的算法被提出，这是一个以易于理解和方便实现为目的一致性算法。作者在同一年分别发表了名为 《In Search of an Understandable Consensus Algorithm》的论文，以及它的 Extended Version，较为详细地描述了 Raft。除此之外，作者的博士论文则以一个更详细的表述方式来描述了 Raft 的各个特性，所以 2014 年的版本被后人称为“ Raft 小论文”，本文就是小论文的阅读笔记与一些思考。
Raft 要解决什么问题
在讨论 Raft 的特性前，我认为明确它要解决的问题是更重要的。首先，Raft 是一个一致性算法，这类算法服务于分布式场景，试图在集群中的成员间就某件事情达成一致。导致不一致的原因会有很多，较为常见的就是 CAP 中的 P，也就是网络分区。
举例来说，单 Leader 多 Follwer 的模式被很多分布式系统所采用，Follwer 多数负责分摊读取的流量，Leader 则负责写入。基于这个假设，底层存储的设计会变得简单，因为它只需要考虑来自一台机器的写流量即可。但是一旦 Leader 与 Follwer 之间出现网络分区，Follwer 们就会因为长时间收不到 Leader 的心跳而选出新的 Leader，此时整个系统就会出现两个 Leader，因为旧的 Leader 可能并没有意识到自己在其他机器看来是下线的状态，这被称为脑裂，是一种因为 Follower 和 Leader 间信息不一致而导致的现象。
所以，一致性算法的出现就是为了解决这类问题，即，在将网络分区或节点宕机等现象视为必然的条件下，保证节点间相互一致，对外继续提供稳定可靠的服务。而 Raft 就是这样的算法。
Raft 概述
Raft 是一个非常依赖 Leader 的算法（论文中称之为 Strong leader），所以它本身就是一个单 Leader 多 Follower 的系统，和一般系统所不同的是，为了保证一致性，它的读写都需要通过 Leader 来进行。这个算法服务于分布式状态机，Leader 以日志的方式向 Follower 发送状态的变化，并以“所有节点中的大多数所达成的一致”作为整个系统的一致。也就是说，如果整个系统中有 3 个节点，那么只要 2 个节点达成一致，就认为整个系统是一致的，与之类似的，如果整个系统中有 5 个节点，那么至少需要有 3 个节点达成一致。反过来讲，5 个节点的系统最大可以容忍 2 个节点失效。
通常而言，Raft 的节点数是奇数，多为 3 个或 5 个，因为 Raft 其实是一个节点间通讯非常频繁的系统，它需要保证整个集群中的任意两个节点都可以发起 RPC 通信，所以如果集群中节点数量很多，那么节点间的 Raft 通信本身就是网络的一个压力来源。正是由于节点的数量并不多，所以采用 Raft 的系统并不会直接作为用户使用的大流量一致性存储系统，而是作为一个协调系统，帮助其他系统简单而可靠地达成一致。
节点状态与通信
在 Raft 中，时间被划分为一个个任期，每个任期通过一个递增的数字来标明。Raft 的节点被分为三种状态，分别是 Leader，Follower 和 Candidate，各自的说明如下：
- Leader：整个系统的老大，客户端的读写都通过它来进行，应用层的状态由它说了算
- Candidate：有机会成为老大
- Follower：老大的小跟班，有时会成为 Candidate
三类节点的任意两两间都可以通过 RPC 进行交流。要想实现 Raft 的基本功能，只需要有两种 RPC，这两种 RPC 都会携带发送者认为的当前的任期号，仅当这个任期号大于等于接受者的任期号时，请求才被视为有效的。论文的 Figure2 中有两个 RPC 详细的参数说明，所以这里仅简单说明下对应的功能：
- AppendEntries：发送日志、说明已提交的日志位置、心跳检测，由 Leader 发起
- RequestVote：发起投票，由 Candidate 发起
当一个节点刚刚加入到 Raft 集群中时，它的状态是 Follower，这种状态的节点会维护一个计时器，在计时器到期之前它需要收到来自 Leader 的 AppendEntries，如果成功收到，那么它会重置计时器，等待下一个 AppendEntries 的到来，这个状态会一直重复下去。另一方面，如果计时器到期，那么节点就从 Follower 转换为 Candidate。这时它会给自己投一票，然后对其他节点发出 RequestVote。如果它能够收到集群中大多数节点的认可，那么它的状态就会变为 Leader。Leader 节点负责与客户端通信，并将状态的变化以日志的方式通过 AppendEntries 发送给其他节点。
上面描述的是一般情况下节点的状态变化，但是如前所述，其实任意状态的两个节点都可以进行 RPC 交流。比如 Leader 在发送 AppendEntries 时并不区分接受者的状态，所以 Candidate 也是可以收到 AppendEntries；与之类似的，Candidate 在发送 RequestVote 时也不区分接受者的状态，所以 Leader 也可以收到 RequestVote。作为一个接受者，不论它收到的是什么 RPC，也不论它当前是什么状态，如果 RPC 参数中的任期号大于它当前所记录的任期号，那么它就会变为 Follower，因为集群中的有效任期号以节点中最大的那个为准，所以小于这个任期号的节点都被视为过期。
另一方面，当多个节点同时变为 Candidate 并发起 RequestVote 时，就很有可能无法选出 Leader。比如 5 个节点中有 4 个都变为 Candidate，那么它们会分别给自己投一票，但是 Raft 规定，每个节点在同一个任期中只可以给一个节点投票，所以不论最后的那个节点把票投给谁，集群中都最多只能达成“两个节点投票给同一个节点”，而这并不符合“大多数”的 3 个节点。所以为了避免这种情况，Raft 规定 Follower 的计时器时长应该为一定范围内的随机值，并且当 Follower 收到 AppendEntries 并重置计时器时，也会重新计算一个新的随机值，从而通过这种随机性来打散节点变为 Candidate 的时机，以尽量避免前文所述的多个节点同时变为 Candidate 的情况。
此外，作为一个分布式系统，支持节点的数量变化也是一种刚需。Raft 的很多机制都离不开“大多数”，但节点的变化就可能导致出现多个“大多数”。举例来说，一个 3 节点的 Raft 集群被增加为 5 个节点，那么这个增加操作也需要得到大多数节点的同意。我们将节点从 1～5 编号，假设前 3 个是原有的节点，4、5 是新加入的节点。那么很可能 2、3 是同意增加节点的，它们会和 4、5 一样，认为此时 3 个节点的一致性才是集群的一致性。但 1 由于一些原因还没有同意增加节点，此时它还是认为集群中只有 3 个节点，所以只要有 2 个节点达成一致，那么整个集群就是一致的。
这会导致什么问题呢？如果 1 和 4 同时发起选举，1 很可能共得到 2 个投票，4 则会得到 3 个投票，由于实际集群中有 5 个节点，所以 4 会成为 Leader 是符合 Raft 对大多数的定义的；但由于 1 仍然认为集群中只有 3 个节点，所以它也会成为 Leader。同一个集群中出现了两个 Leader，也就是发生了脑裂，Raft 作为一个对 Leader 强依赖的算法，在这样的情况下就无法保证一致性了。
怎么解决这个问题呢？Raft 提供了两种思路，这里仅对易于工程实现的思路做解释。具体来说，Raft 规定不论是增加节点还是删除节点，每次都只能操作一个节点。这就可以保证即便集群中的节点对节点总数的判断不一致也不会出现脑裂的情况，因为整个集群中对于“大多数”的判断只会有两个答案，比如原来有 4 个节点，为了选出 Leader 就需要获得 3 个节点的投票，现在变成 3 个节点就需要获得 2 个节点的投票，而两类节点的“大多数”之和会大于原来集群中节点的数量，即 2 + 3 = 5 > 4，所以一定会有一个节点同时属于两个“大多数”，这个节点就是非常关键的角色，它的投票会影响系统的最终结果。如前所述，节点数量的变化需要经过“大多数”节点的同意，所以这个关键的节点一定知道集群数量的变化，那么它一定会把票投给知道集群数量变化的那个 Candidate 来帮助它成为 Leader。
可以证明，对于新增节点的场景也是类似的，那个关键的节点会把票投给更新的 Candidate。怎么定义哪个 Candidate 更新呢，要用它所拥有的日志来判断。
Raft 的日志
我们前面提到，Raft 算法是服务于分布式状态机的。那么对于状态机本身而言，就需要有一种机制可以同步状态的变化，通常而言就是日志。与客户端直接交互的节点会更新自己的日志，然后将新的日志同步给其他的 replica 们，这些 replica 接收到日志后在本地重放（replay），最终其内部的状态就会与其他节点达成一致。
发送日志的时机取决于系统本身的要求，我们曾讨论过同步发送和异步发送的利弊。对于 Raft 这样一个聚焦于一致性的算法，它选择在执行命令前先同步日志，也就是所谓的 WAL。但与其他系统不同的是，Raft 在日志同步上也仅需要达成大多数的一致，比如集群中有 5 个节点，那么它只需要成功同步给其中的 2 个节点，加上它自己本地的一份，整个集群中就有 3 个节点对日志达成一致，这在机制上就可以保证一致性了。通过这种方式，采用 Raft 的系统在同步日志的效率上不会受制于那些 struggler，也就是因为各种原因显著慢于其他节点的节点。
我们前面提到为了保证一致性，采用 Raft 的系统的读写都要通过 Leader 来完成。我们假设使用 Raft 的是一个分布式 kv 系统，那么它所支持的最基本的操作就是 get/set。当一个节点成为 Leader 后，它就会开始接收来自客户端的请求。收到请求后，Raft 模块会把这个命令以 Log Entry 的形式追加进自己的本地日志中，然后发送 AppendEntries 的 RPC 来将日志同步给其他节点，当收到大多数节点的同意后，Raft 模块会把相关状态同步给应用层，在这种情况下应用层就会将命令的效果应用在本地状态机中，然后把最终结果返回给客户端。
每个 Log Entry 会有它自己的下标、创建它时系统的任期号（是当时的 Leader 以为的任期号，实际可能不准确）以及包含的命令。通常情况下，Leader 和 Follower 的日志应该是一致的，但 Raft 把不一致视为必然现象，那么怎么定义不一致呢，大体有两类。首先第一种就是日志的长度不一致，比如前面提到的 struggler，这些节点通常只有 Leader 节点上前半部分的日志，后面的部分由于各种原因还没有被同步过来；另一种就是同一个下标对应的 Log Entry 不同，导致这一现象的原因有很多，比如 Leader 收到命令 put x 1 来将 x 写入 1，但它在将对应的 Log Entry 追加到本地后就发生了网络分区，在它离线期间其他节点中选出了新的 Leader，并收到了 put x 2 的命令并成功同步，此时旧的 Leader 在同样的位置上的 Log Entry 就与其他节点不一致。
Raft 怎么处理这种不一致呢？首先在前面我们提到，选举 Leader 时，节点在投票时要考虑两方面的因素，第一是目标 Candidate 的本地任期号是否大于自己，第二是目标 Candidate 是否有比自己更新的的日志。这里的更新有两个含义，如果 Log Entry 的任期号相同，那么具有更大下标的日志更新；如果日志的下标相同，那么具有更高任期号 Log Entry 更新。可以发现，这其实就是对齐了前面提到的两种不一致。因为只有具有更新的日志的节点才有机会成为 Leader，而客户端的读写又通过 Leader 进行，所以客户端还是可以读到更新的结果。另一方面，Leader 采用 AppendEntries 来做心跳检测，这个 RPC 本身就是用来同步日志的。通过这个机制，Leader 是可以发现 Follower 的日志与自己日志间的不一致的。在这种情况下，Leader 会对不一致的部分进行调整，少日志就加，错日志就覆写，最终 Follower 的日志状态就会和 Leader 达成一致。
和其他依赖日志的系统一样，随着系统的运行日志会变得越来越大，最终耗尽持久化设备的空间。Raft 对这种问题的解决方案是 snapshot，就是把当前已有的日志通过某种方式变成一个等价的、但是占用空间更少的表现形式，实现这种效果的方案有很多。比如对于一个使用 Raft 的分布式 kv 系统而言，就可以采用类似 Redis 的 AOF 重写的机制。具体而言，如果日志中的内容包含对同一个键的一系列操作，那么最终有效的其实只有最后一个操作，所以只需要在日志中保留这个值的最终状态即可。论文中把这个操作称为 Log Compaction，也就是日志的“压实”，我觉得这个词还是非常贴切的。
那么会不会出现经过 Log Compaction 后，日志占用的磁盘空间还是很大的情况呢？我觉得这种情况是很少的，因为如果距离上一次压实后（我们称它为 snapshot）并没有新的命令被执行，那么实际上内存中的状态和 snapshot 是一致的。对于一个使用 Raft 的分布式 kv 系统而言，snapshot 里记录的大概就是每个 key 对应的 value 是什么，这和内存中的信息是一样的，如果这些信息都可以被保存在内存中，那么保存在持久化设备上就不是什么大问题了。
一些细节
接下来讨论一些其他方面的问题。
首先，我们前面提到，为了保证一致性，采用 Raft 的系统的读写都需要在 Leader 上进行，但是读操作为什么需要呢？可以确定的是，从 Raft 系统中读出的内容一定是被“大多数”节点承认的内容，因为只有被多数节点承认，这个内容才会被应用到状态机中。但是尽管这个内容是被承认的，它也有可能是过期的，比如如果允许从 Follower 上读取内容，那么与客户端交互的有可能就是一个 struggler，也就是说它内部的日志是延后于其他节点的。那么此时客户端通过它来读取，就可能读到曾经的某个时刻有效、但是在当前实际已经被修改的值。而这其实就回到了主从复制系统的一个共有问题，也就是同步延迟带来的问题，一些业务场景是可以容忍这短暂的不一致的。因此，如果不要求读的强一致性，那么读操作也不是一定要发生在 Leader 上的。
那么，是不是只要从 Leader 上读取，就一定可以读到最新的内容了呢？原理上是这样的，但是问题在于 Leader 并不能很轻易地判断它自己是不是 Leader。比如说，曾是 Leader 的节点与其他节点间发生了网络分区，导致其他节点因为收不到它的心跳而开始选举新的 Leader，并在选举成功后写入了新的内容。那么对于那些还在与旧 Leader 交互的客户端而言，它们与旧 Leader 都没有意识到新 Leader 的产生，如果此时旧 Leader 直接从自己的状态机中取出对应的状态返回给客户端，那么这其实就和上面提到的直接从 Follower 上读取是一样的场景了。
所以为了保证一致性，读操作也要写入日志，并且通过 Raft 模块同步到其他节点上，只有得到多数节点的同意，Leader 才能确保它确实是 Leader，然后放心地将自己状态机中的状态返回给客户端。把读操作放进日志中可能看起来有些奇怪，但是本身日志的内容就不是既定的，比如 etcd 的 Raft 模块中甚至有 Dummy Log Entry，用来避免论文 Figure8 描述的现象，这里就先不展开了。
另一个问题是，当客户端发送了更新状态的命令给 Leader，那么 Leader 将其写入日志后会同步到其他节点，如果同步失败了会怎样？当有新的客户端发送其他更新状态的命令时，Leader 会用这个命令对应的日志将前面同步失败的日志覆盖掉吗？对于这个问题，论文的 Figure3 里明确说明了 Leader 是 Append-Only 的，也就是不会覆写自己日志中已有的内容（但是会覆写其他节点的，因为它是老大它说得算）。可是，这样一来不就有脏数据在日志中了吗，因为同步失败时 Leader 会返回客户端命令执行失败，但是经过几轮心跳检测的 AppendEntries，这个当时被认为失败的日志还是会被同步并应用到其他节点的状态机中，此时系统的状态就和客户端预期的不一致了。
我觉得这个问题还是应该看具体的场景，比如还是以分布式 kv 系统举例，那么客户端在收到命令执行失败的响应后可以直接发起重试，因为它的操作是幂等的，这次重试对应的日志会被放在失败的那条日志后面，并且被同步到其他节点上，这时的这个日志是被认为有效的，前面的那条被客户端认为失败的日志可以简单地理解为被后面的日志覆盖掉了，这其实也是 kv 系统的日志可以做 Log Compaction 的原因，因为对于同一个 key 而言，最后一次的操作才是其最终的状态。
