1 概要

本节课继续 Lecture 5 的内容，对 Raft 论文剩下的内容进行了讨论，主要是包含日志复制的一些异常处理、持久化、压缩和快照，其中论文中的 Raft 集群新旧配置变化的联合一致相关内容略过没有详细讨论，但是课堂上学生比较多的问题都是围绕着这个点提出的。此外，还稍微提及了一致性模型中的线性一致性(linearizability)相关内容。

本课相关的材料:

• 课堂 Paper: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
• 课堂录像: https://youtu.be/h3JiQ_lnkE8
• 课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-raft2.txt

PS. Lecture 6 是 TA 代讲的 lab1 MapReduce 的 Q&A，没太多感兴趣的内容，所以就直接跳过了。

2 要点

2.1 Raft 日志

客户端对一个有 leader 节点，正常运行的 Raft 集群的访问：

• 客户端只能与 leader 节点交互；
• 客户端看不到 follower 节点的状态或者日志；

但是，当 Raft 集群中的 leader 进行切换时，很多异常和错误都有可能发生，从应用的角度来说，我们希望能保证：

• 当任意服务节点执行一条日志条目中的命令，其他的服务节点不能从同一条日志目录中执行不同的命令

这主要是为了保证状态机的安全性，避免在 leader 切换后对客户端展示不一致的状态，违背了集群对外展示为一个单独整体系统的初衷。

不过服务节点之间的日志的确是有可能产生冲突：

• leader 节点在接收到客户端请求，保存到自身的日志队列，发送 AppendEntries RPC 请求给其他 follower 节点之前宕机；
• 其他节点选举后成为新的 leader，再次接收其他客户端的请求，之前的 leader 恢复启动后可能就出现节点间日志队列不一致的情况；

在服务节点之间的日志数据产生冲突时，Raft 强制 follower 节点同步 leader 节点日志来维持一致性，也就是以有效的 leader 节点的日志队列为准。这就涉及到 leader 和 follower 节点之间日志同步的处理，这块内容是上节课涉及的 Raft 论文部分有详细的步骤。简单来说，整个同步方案还是通过 AppendEntries 来实现的，在 follower 发现自身的日志和 leader 不一致时，将会返回错误响应给 leader ，然后 leader 回退同步给该 follower 的日志，直到一致，之后就按 leader 同步过来的进行覆盖。

选举限制：Raft 集群中的节点处理 RequestVote 请求时只给至少和节点日志一样新的 candidate 投票，这个新的定义是：

• candidate 最后一条日志有更高的 term 值；
• candidate 最后一条日志有一样的 term 值，但是有一样或者更长的日志索引；

这个选举限制可以保证新的 leader 能包含所有可能已经提交的日志，这块内容也是上一节课论文部分包含的。

2.2 持久化

当一个服务节点宕机时，我们希望 Raft 集群可以正常运行，但是宕机的节点也需要尽快恢复或者被替换，以避免整个集群的可用节点数量低于半数，有两个策略：

1. 用一个新的服务节点替换：需要同步整个当前的日志和恢复状态机状态；
2. 重启宕机的服务节点，重新加入到集群中，并追上落后的日志和恢复状态一致；

本节主要是关注第二个方案，以及需要实现的服务节点数据持久化处理。

持久化和恢复时需要的数据相关，以下是相关的数据：

• 日志队列数据：维持日志队列，保证已提交的日志不会丢失；
• 当前的 term 值：保证 term 值只会增加，不能恢复为 0 ，影响后续的选举；
• 投票给的节点 voteFor：防止一个节点投票给一个 candidate 节点后，重启又参与这轮选举；

持久化通常是会对性能产生影响的：

• 普通磁盘写要 10ms，而 SSD 写只需要 0.1ms ；
• 实现上可能需要每个日志都进行持久化操作，这样限制整个集群的处理能力为 100 ~ 10000 操作/s ；

进行了关键数据持久化处理后，服务节点又要怎么启动恢复状态和数据呢？通常是下面两种方案：

• 初始为空状态，将整个持久化的日志队列中已经提交的命令重新执行，这样可以恢复到宕机前状态，但是耗时会比较长，并且对于运行很久产生了很多日志的 Raft 节点这个方案也不现实；
• 使用快照，只重新执行后面的一部分日志，这个方案就是下一部分的主题；

2.3 日志压缩及快照

当一个 Raft 集群运行足够长时间后，通常会面临一个问题：日志会越来越大，甚至有可能比整个状态机要大很多，这样无论是重启进行日志的重新执行还是发送给另外一个新启动的服务节点，都需要非常长的时间。

考虑实际应用时，客户端实际上并不关心和需要整个运行中产生的日志，只是需要状态机中的状态，而在一般的应用场景中，状态机往往是比日志要小得多的(指的是有限数量的 key 不断被更新、删除的场景)，所以一个考虑方案是对状态数据进行持久化保存。

对状态机数据的保存成为一个快照，而快照成功保存后，快照的最后一条相关日志及之前的都是可以被安全地删除的，这也就实现了对日志队列压缩的效果。

服务节点不能删除的日志条目：

• 未执行的日志条目：还没有被状态机应用；
• 未提交的日志：有可能在将来被 leader 确认提交，保存在多数服务节点上；

解决方案：

• 服务定时创建一个当前状态的快照：以一个特别的日志执行条目的方式；
• 服务将快照写到一个持久化存储中 (比如磁盘)；
• 快照记录了包含的最后一条日志目录的索引，通知到 Raft ；
• Raft 撤销日志队列该索引之前的所有日志；

宕机后重启：

• 服务从磁盘读取快照；
• Raft 模块从磁盘读取日志；
• 服务通知 Raft 模块设置 lastApplied 为快照最后包含的日志条目的索引，避免重新执行已快照保存的命令；
• 接下来就是 Raft 正常的应用日志流程；

还有个问题需要考虑：当 follower 宕机，但是 leader 节点执行了快照，导致部分还没同步到 follower 节点的日志被取消时要怎么处理？Raft 新增了一个 InstallSnapshot RPC 请求来处理这种情况，同时也应用于新 follower 节点加入集群同步状态的处理。

实现时有几个点需要注意：

• Raft 的快照方案适合于状态空间相对小的情况，对于大数据库，比如状态空间就包含几个 GB 数据，实行起来就不是那么合适；
• 这种情况，状态数据可能需要一直保存在磁盘上，使用 B-Tree 或者 LSM 等数据结构；

2.4 线性一致性(linearizability)

对于一个支持 Put/Get 操作的 kv 存储服务来说，对于客户端需要能够对并发操作下操作的执行顺序有一定的预期。通常这称为一致性模型，有助于我们明白要怎么正确地处理复杂的情况，比如并发、复制、异常、RPC 请求的重传、leader 切换等等。

线性一致性是对于期待能够表现为一个单服务(强一致性)的分布式最常见并且最直接的正式定义：如果我们可以为所有的操作找到一个完全的执行顺序，并且这个顺序符合时间顺序，每个读操作可以看到顺序上紧接着的前一个写操作的值，那么这个执行历史就是线性的。简单来说，在这个系统中，如果一个数据对象被更新了，那么时间上后续的读操作应该可以读到这个新的值。

2.5 重复 RPC 检测

当客户端和 Raft leader 之间出现网络异常导致请求超时的时候，通常是要求客户端不断地进行重试请求的。这样的情况下，服务端需要考虑对重复 RPC 的检测相关的问题，以便实现操作的幂等性。

• Raft 模块上层的 k/v 服务负责重复客户端请求检测
• 客户端每次请求选择一个 id ，包含在请求中
• k/v 服务保持一个根据 id 索引的表，每个 rpc 请求都创建一个条目，并且保存执行后的结果
• 如果另外一个 rpc 请求也包含了同样的 id ，从表中检测确定为重复的请求，则直接把记录的值返回给客户端；

上面这个设计有几个问题需要考虑：

• 什么时候这个记录 rpc id 和值的表可以安全删除？不删除的话会占用资源
• 如果进行了 leader 切换，那么这个表要怎么同步给新的 leader ?
• 如果服务节点宕机，那重新期待时怎么恢复这个表？

一些想法：

• 每个客户端一个表条目，不用每个 rpc 请求一个条目，这样可以减少整个表的大小
• 每个客户端每次只能有一个 RPC 请求
• 每个客户端递增地标识 RPC 请求
• 当服务接收到客户端一个新的 RPC 请求，比如 #10，那么更前的请求可以放弃重复检测了，因为客户端不会重复发送更旧的 RPC 请求

2.6 只读操作

在一个 Raft 集群中，对于读请求也需要先进行同步日志和提交才能向客户端响应，不然会出现下面一种情况：

• leader 接收到客户端的 Get(k) 请求；
• 此时，Raft 集群的 leader 进行了切换，原 leader 状态已经切换为 follower；
• 原 leader 并没意识到新的选举，从自身的 kv 表获取 k 对应的 value 返回给客户端；

这个情况可能会导致客户端读取到旧的数据，也就违背了 Raft 线性一致的保证。但是通常情况下，大部分的应用都是读多于写的，每次读都需要进行一次日志同步实现上会相对低效，性能可能不太理想。

有一种解决方案是使用租约 (lease) ，需要对 Raft 算法进行调整:

• 定义一个租约的时长，比如 5 秒；
• 每次 leader 得到一次的 AppendEntries RPC 请求的多数成功响应，就表明当前这个 leader 有权力在租约时间内响应只读的请求，而不需要提交任何的日志；
• 如果在租约有效期内，发生了新的选举，新的 leader 在原租约过期前都不能处理 Put 请求；

本课程的实验中并不要求实现租约机制。

3 Paper

lecture 5 的内容是到 Raft 论文的第五节，本节课对论文剩余的内容进行阅读讨论。其中第六节关于 Raft 集群成员变化相关的内容本来在课程安排上是略过的，但是在课程中不少学生都提及了相关的问题。在这里，我也决定不跳过这一部分内容，毕竟也属于 Raft 实际实现时需要考虑的非常重要的一个主题。

剩余部分内容包含以下：

• 集群成员变化
• 日志压缩
• 客户端交互

其他部分则是实现和性能及教学效果的评估，和最后的总结内容，不包含在这里对论文的阅读思考内容中。

3.1 集群成员变化

对于一个真实业务上运行的分布式系统来说，集群的成员并不是一成不变的，服务器的替换和更新以及因为异常或者性能缺口导致的增补，都是日常系统运维中不可避免的事情。这也就意味着，Raft 集群的运行中，可能会发生成员的数量变化，也就是集群的配置发生了变化。

在业务持续运行的过程中，停机更新不是一个好的选择，因为停机意味着业务的停止，同时复杂的运维操作也可能会产生灾难性的意外后果。基于减少配置变更对正常业务影响的考虑，Raft 提出了一种把配置更新和融合进一致性算法里的自动更新配置的方案。

成员配置发生变化时，在集群节点新旧切换的过程中，一定要尽量避免出现 2 个 leader 的情况，这样会直接影响到数据的一致性，违背了 Raft 算法保证的各种安全性原则。而直接从旧成员切换到新成员的方案，因为难以实现原子性地同时切换所有节点，所以集群还是可能会出现脑裂的情况。

基于保证安全性的考虑，通常是需要采用两步 (two-phases) 的方案来实现，不同的系统有多种实现方案，在 Raft 这里，线上将集群切换为一个被称为联合一致的过渡的配置状态，一旦联合一致相关日志被提交，整个系统就切换为新的配置。

联合一致的情况同时包含了新旧的配置：

• 日志条目会被复制到两个配置的所有服务节点上；
• 两个配置中的服务节点都有可能被选为 leader；
• 选举和日志条目的提交需要同时分别获得两个配置中的多数节点一致同意；

联合一致支持新旧配置中的所有节点在不同的时间切换配置并且不会影响到算法的安全性。并且，在配置切换过程中，集群还能够继续对外部提供服务，响应客户端请求。

集群的配置是通过特别的日志条目来保存配置及通信的，如上图所示，配置切换的处理流程如下：

1. 当 C‘old 配置下的 leader 接收到更新配置的请求时，将会保存这个请求及配置为联合一致处理的一条日志，也就是图中的 C'old,new ，然后将这条日志复制到新旧服务节点上；
2. 一个服务节点一旦处理到这条日志，将会将新配置中的服务节点信息添加到其日志中，并且在将来的所有决策中都会使用这个新的配置，注意并不要求这条日志已经复制到多数节点；
3. 这过程中如果 leader 节点宕机，新的 leader 将会基于 C'old,new 的配置选出，一旦 C'old,new 被提交，则独立的 C'old 或者 C'new 都不可能缺少彼此的情况下作出决策，基于 leader 完整性的原则，只有包含了 C'old,new 的节点才能赢得选举;
4. 在 C'old,new 被提交后，现在 leader 可以基于联合一致的状态创建一条描述了新集群配置的日志并且复制到多数节点上，也就是上图中 C'new 出现的位置，同样，每个服务节点接收到新的配置后会立即生效，也就是会清除旧的配置；
5. 当 C'new 被复制到多数节点后，旧的配置项对于集群来说就再也不会有任何的影响了，其中不在新配置项的节点都可以被安全地关闭，这时候不在新配置节点中的 leader 将会退出。

从上面的处理流程来看，在新旧配置切换过程中，并不会出现新、旧配置的节点同时成为 leader 分别进行决策的情况，也就保证了 Raft 算法在配置切换中的安全性。

对于配置更新的处理，下面还有 3 个值得注意的问题：

1. 新加入集群的节点并没有任何日志数据，如果新节点一加入集群就开始上面这个流程，那么配置切换可能需要等待该新节点的日志同步追上最新进度才能开始，为了减少这其中的时间差，Raft 新增了一个新的额外阶段，新的节点加入集群后会被视为非投票节点，leader 会复制同步日志到这些节点，但是不会视其为决策中的多数，一旦新节点的日志追上集群其他服务，就可以按照上面的流程继续处理；
2. 在配置切换过程中，集群中的 leader 节点可能不包含在新的配置中，这个时候在 C'new 日志提交后，leader 将会退出转换为 follower 状态，而新配置中的节点将开始新的选举，从新配置中节点选出一个新的 leader，这是一种比较特别的情况，也就是旧配置中的 leader 进行着不包含自身的决策；
3. 被移除的服务节点如果并没有关闭，有可能在选举超时后在集群中发起新的投票，导致整个集群进行选举处理，并且每次选举超时都会触发，为了解决这个问题，Raft 的服务节点在处理 RequestVote 请求时，如果认为当前存在有效的 leader 节点，则忽略该请求，实际上指的就是在自身的选举超时前成功收到了 leader 的心跳；

3.2 日志压缩

在一个 Raft 集群的正常运行中，其日志队列和数据随着客户端请求不断增加，从目前看到的实现来看，如果没有任何处理，那么理论上日志数据会无限制地增长，占据所有可用的磁盘空间。更糟糕的是，存在大量日志数据时，一个节点重启时，需要重新执行大量的历史日志保存的命令才能恢复状态到最近，这显然不是实际业务系统可以接受的。

对于 Raft 运行中产生的历史日志，我们有没有必要一直原样保存呢？我们知道日志里面最重要的数据是客户端的命令，而命令是用来改变状态机的状态数据的，状态机的数据才是外部客户端请求需要的。从这个方面来看，Raft 集群中重要的不是所有的历史执行的命令，而是这个状态机。

所以，一种常见的解决方案是使用快照，简单来说，就是将当前状态机所有数据写入一个快照文件，保存在一个可靠存储上。然后整个日志队列的数据，一直到快照数据对应提交的最后一条日志之前的所有日志条目都可以安全地删除。因为通常的业务系统中，状态机的总数据量是有限的，所以这样可以将日志数据量压缩为状态机状态数据大小，从而减少了日志的占用的空间大小。对于状态机本身就特别大的系统，快照方案可能并不太适用，这类型系统可以考虑直接把状态数据保存在可靠存储上。

如上图所示，Raft 中的快照方案主要是有以下几点：

• Raft 集群中每个服务节点是独立地执行各自的状态机快照处理，数据主要是当前节点的状态机数据，并且只覆盖已提交的日志条目的命令执行结果；
• 快照包含了部分的元数据：最后一条被包含的日志的索引及任期值，主要是用于 AppendEntries 的请求，另外还有集群的当前配置信息；
• 快照文件写成功后，这个节点就可以删除掉旧的日志了，另外之前创建的快照数据也可以进行删除处理；
• 如果某个 follower 节点大幅度落后 leader 节点或者新的节点加入集群，这个情况下，为了加速节点的状态跟上 leader，可以考虑从 leader 节点发送快照给该节点，Raft 为这个操作新增了一个 InstallSnapshot 的 RPC 请求；
• follower 接收到来自 leader 的 InstallSnapshot 请求时，如果发现发送过来的快照包含的最后日志要比自身日志队列的数据要新，则可以直接删除掉当前的日志数据，加载快照数据恢复状态机，如果快照数据落后于节点日志，则只删除包含的日志条目，保留其余的日志数据；

整个日志方案是和 Raft 之前描述的强 leader 原则是分离的， follower 不需要了解 leader 信息就可以执行快照处理。主要是因为在执行快照时，每个服务节点的状态机的一致性已经由 Raft 算法的一致性保证了，所以不同节点的快照文件不会产生状态数据的冲突，只会有多少的差异。

在实现快照时，有两个性能相关的问题需要注意：

1. 快照执行的时机：太频繁，可能有太多的磁盘 IO ，太少，则冒着存储空间被耗尽的风险，并且启动时可能要更长的时间，因为有更多的日志条目未包含在快照文件中；一个简单的方案是当日志大小达到一个预定义的大小后就执行快照处理，这样额外的磁盘带宽及 IO 开销会比较小；

2. 写快照文件对正常业务的影响：写快照文件可能需要比较多的时间，另外一般来说也不希望在写快照时状态空间发生变化，所以可能会考虑在写快照时停止外部请求，这样的方案实际上就对正常业务造成了影响，所以一般是采用写时拷贝 (copy-on-write) 的方案来实现快照创建处理，以 linux 系统为例，简单来说就是利用 fork 系统调用创建一个子进程共享当前状态机数据，在分离的子进程将状态机数据写入快照文件，同时主进程在执行状态机的写业务时拷贝和修改相关的内存，不影响子进程的状态机副本数据；

3.3 客户端交互

除了 Raft 集群节点之间的交互之外，客户端与 Raft 集群的交互在实现上也有很多需要注意的点，本小节就是对这方面的内容进行了补充。

根据之前的描述，客户端应该只与 leader 进行交互，所有的数据应该通过 leader 节点同步日志到其他 follower 节点。但是在一个客户端刚开始连接到 Raft 集群时，它并不了解哪个节点是 leader，此外还存在 leader 异常宕机、leader 切换等情况。所以在实现时，如果客户端第一次请求的节点不是 leader，则这个服务节点将会拒绝客户端请求并提供 leader 的信息，然后客户端重新往 leader 节点发起请求。如果信息不正确，或者提供的 leader 节点请求超时无响应，客户端可以随机选择另外一个节点再次进行请求。

在异常情况下，如果客户端的请求超时没有收到响应，则应该重新再发起请求，这样 Raft 集群可能出现多次处理同一个请求的情况。比如 leader 在提交日志后响应给客户端前宕机了，客户端可能会往新的 leader 发起同样的一个请求，这样就会导致 Raft 集群两次处理同一个请求。解决方案是，客户端每次请求都指定一个唯一的序列号标识这个请求，然后状态机追踪每个客户端最近提交的请求的序号和对应的响应，这样在遇到重复的请求时，直接把已记录的响应返回，不再执行请求的命令。

对于只读请求，因为不会影响到状态机数据，理论上应该是可以不记录相关的操作日志的。但是实现时如果没有额外的操作，很有可能会导致返回过期数据给客户端，因为接收读请求的 leader 服务节点在处理时可能已经不是 leader 了，但是因为没有日志交互，它并没有意识到存在新的 leader 。

为了解决只读请求的问题，Raft 需要两个额外的预防措施来保证：

1. leader 节点在任期开始时提交一个空 (no-op) 的日志条目到日志队列：这样可以让 leader 与各个 follower 进行交互，并且了解最近已经提交的日志信息；
2. leader 节点处理读请求时，在返回给客户端前都需要和集群中多数的节点进行心跳请求，这样 leader 可以确保其自身还是一个有效的 leader ，避免返回过期的数据；

4 总结

从这两节课的阅读来看，Raft 论文内容细节丰富，理论性的内容较少，整个算法易于理解，包含了很多实际实现上的考虑，是分布式领域一致性算法相关不可多得的一篇好论文。将一致性算法分为选举和日志复制几个子问题显然更为清晰，而强 leader 的设计对比多 leader 决策的复杂处理逻辑要更易于实现，单一节点以天然有序的日志的方式决定操作的执行顺序也很好地支持了线性一致的实现。

虽然 Raft 论文易于理解，但是一个可以实际应用在生产环境的分布式系统在实现上还是会存在更多的细节和需要考虑的问题，部分性能上的考虑在论文也只是一笔带过，对于系统实现来说却是必须考虑的内容。比如只读操作的性能优化，论文中提及了基于租约 lease 的方式来实现，但是没有提供具体的方案，这只能由系统的实际开发者来进行设计实现了。

当前业界也有不少开源系统基于 Raft 算法实现了容错、可靠的分布式系统，并且实际应用到了生产环境，经受了实际业务的考验，从性能和可靠性都得到了充份验证，下面是几个比较出名的项目：

• etcd : 一个分布式的 k/v 存储系统，对标参考 Paxos 实现的 Zookeeper 项目，常用于可靠存储系统关键数据，比如配置等，或者用于分布式系统中作为服务发现等功能使用，也被 kubernetes 等著名开源系统使用；
• tikv : 也是一个分布式的 k/v 存储系统，主要是用于为分布式数据库 TiDB 提供可靠的分布式数据存储支持，除了简单的 k/v 操作之外，它还实现了保证 ACID 的事务相关操作，此外，其数据是持久化存储在磁盘上的；

这些开源的基于 Raft 算法实现数据一致的分布式系统在实现上对 Raft 算法有很多的优化和改进，也更多地考虑了实际业务的需求，非常值得参考阅读。

1 概要

本课主题是分布式系统中容错相关内容，主要是对一致性算法 Raft 进行分析讨论。Raft 是一个用于分布式系统中多副本之间维持数据一致性的算法，它能实现接近 Paxos 算法的性能和功能，但是更容易理解和实现。Raft 的一个创新点是在于将一致性的实现分离为更容易理解的选举及日志复制等几部分。

Raft 算法目前在业界已经有不少的实现及应用，比如 etcd 就是基于 Raft 算法构建了一个容错的分布式 kv 存储系统，并且广泛被应用在线上生产环境中，经受了真实应用场景的考验。对于 Raft 算法的讨论分为两节课，本节主要涉及到 Raft 基础的结构及概念，以及选举、日志复制相关内容。

本课相关的材料:

• 课堂 Paper: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
• 课堂录像: https://youtu.be/R2-9bsKmEbo
• 课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-raft.txt

2 要点

2.1 一种模式

• MapReduce 依赖单个 Master 来组织计算
• GFS 支持数据副本复制，但是依赖单个 Master 来选择数据副本的 Primary 节点
• VMWare FT 支持复制，但是需要依赖 test-and-set 来选择 Primary 节点

之前课程涉及到的分布式系统中，架构上都是依赖单个服务来做关键的决策，这有一点好处是可以避免多服务可以参与决策下因为网络分区等异常导致的脑裂现象。但是，在一个大型的分布式系统中，单点决策总是会影响到整个系统的健壮性和可用性。

2.2 脑裂

• 在一个存在多个复制节点的分布式系统中，当发生网络分区时，各个节点可能各自执行不同的用户操作，从而导致多个节点之间的状态无法维持一致，这样就出现了脑裂；
• 客户端对于服务宕机和网络故障导致的服务不响应这两种异常状态是无法识别的
• 这两种异常对于客户端来说，表现都是一致的：服务无网络响应

2.3 一种解决方案: 多数票决

• 奇数数量的服务节点：比如 3
• 对于任意关键操作 (用户修改命令、配置变更)都需要多数服务达到一致决策
• 发生网络分区时，最多只能有一个分区有多数服务节点，所以另外一个分区不会进行决策导致数据不一致，并且奇数量服务打破了偶数数量服务的对称可能性；
• 多数服务是指整体服务节点中的多数，而不是当前存活的服务节点中多数
• 如果需要容忍 f 个服务宕机：服务节点总数为 2f+1；
• 这种方案通常也被称为 quorum

早期的一致性算法(1990年左右)

• Paxos
• View-Stamped

近期算法(2014)：

• Raft

2.4 Raft 总览

在论文中， Raft 主要是从状态机副本复制的角度来描述的，架构上 Raft 层在状态机的每个副本中以库的形式被包含使用，多个状态机副本之间通过 Raft 算法来实现操作命令的同步和一致性维护。

架构：客户端 -> 3 副本 -> 副本 k/v 层+状态机 -> raft 层 + 日志

客户端命令流程

1. 客户端发生 put/get 命令到 leader 服务节点的 k/v 层;
2. leader 添加命令到日志队列；
3. leader 发送 AppendEntries 远程调用到 followers 服务节点以同步命令日志；
4. follower 添加命令到日志队列；
5. leader 等待多数服务响应，包含其自身；
6. 如果多数服务都成功把命令添加到其日志队列中，则该命令被视为已经提交 (committed)
7. leader 执行命令，并响应给客户端；
8. leader 在下一次发送给 followers 服务节点的 AppendEntry 请求中加上命令提交的信息；
9. follower 也在 k/v 层执行命令，更新状态；

为什么使用日志?

• 日志是追加操作，可以维持命令执行的顺序，每个服务节点的 k/v 层按顺序执行命令之后，可以保证多个状态机副本之间的状态一致；
• 多个副本可以保持一致的命令顺序；
• Leader 可以保证所有的 follower 都有同样的日志
• 日志队列可以用于提交执行前暂存
• 日志队列存储了命令可以方便 leader 重新发生旧的命令同步给 follower
• 日志队列持久化存储命令可以实现重启后回放执行命令，恢复状态机状态

Raft 设计的两个重点

1. 选主: 选择一个服务节点作为 leader
2. 保证各个服务节点之间的日志在异常失败的情况下还是一致的

2.5 Raft 选主

为什么需要一个 leader ?

• 需要所有的副本都按照一致的顺序执行同样的命令
• leader 接收客户端请求并确定执行的顺序，无 leader 多副本之间并发情况下保证一致执行顺序很困难

Raft 中多个服务节点都有可能担任 leader 角色

• 一个服务节点担任 leader 的时间内为一个 term
• 一个 term 内只能有一个 leader
• 一个 term 内可以没有 leader

开始选主的时机

• follower 节点在选定的选举超时时间内没有接收到来自 leader 的定时心跳
• 该节点当前的 term 值加一，然后开始尝试收集投票

如何保证一个 term 内只有一个 leader?

• 一个节点需要接收到来自集群中多数节点的投票同意
• 每个节点只能投一票：处于候选者 (candidate) 角色的会投给自己，非候选者角色则投票给第一个请求的

服务节点识别新 leader

• 新 leader 节点接收到多数的投票
• 其他服务节点接收到一个有更高 term 值的 AppendEntry 心跳请求

一次选举可能会没有 leader 产生

• 少于多数(过半)的服务节点无法访问
• 多个同时请求投票的候选者分离了选票，没有一个成功拿到多数节点的投票

一次选举失败后

• 在一次超时后还是没有接收到任何 leader 的心跳消息，term 值递增并开始新的选举
• 更高的 term 值优先级别高于旧 term 的候选者，旧的候选者退出选举

如何避免选票分离 (split vote)？

• 每个服务节点选择一个范围内随机的选举超时时间(election timeout)
• 在 leader 挂掉的时候，其他 follower 节点同时发起选举请求的可能性大大降低，避免了选票的分离

选举超时值选取？

• 至少几个心跳间隔，避免网络丢弃了一个心跳导致重新选主
• 随机的范围应该能支持一个 candidate 在另外一个开始前成功
• 尽量快速响应异常，避免长时间的停顿

3 Paper

本课阅读讨论的论文是 In search of an Understandable Consensus Algorithm (Extended Version) (2014)，这篇论文提出了一种新的分布式一致性算法 Raft，用于分布式系统中管理复制日志，维持多副本节点间的数据一致，以建立一个容错的分布式系统。Raft 算法对标传统的一致性算法 Paxos，从易于理解的角度出发进行设计及构建，能达到和 Paxos 一致的性能和功能。

本课对于论文的阅读只到第 5 节，后部分内容在下一节课进行阅读讨论。

3.1 简介

一致性算法通常是用于支持一组机器像一个整体一样工作，并且在部分成员失效时也能正常工作。正因为如此，在大规模可靠系统中，一致性算法有着重要的角色。在过去十年 (2014往前)中，Paxos 是最占主导地位并且最受广泛讨论的一致性算法，业界大多数的一致性实现都是基于其或者受其影响。同时，Paxos 也是一致性算法学习时最为重要的内容。

然而不幸的是，Paxos 算法难以理解，并且其架构需要复杂的调整来支持实现。所以学生和系统的构建者都饱受 Paxos 算法的折磨。本论文作者也曾经受理解 Paxos 算法的痛苦，决定尝试设计一个更好的一致性算法来支持教学及实现，并且整个算法是基于 "可理解" 的基本诉求来进行设计的。

Raft 算法就是作者这个工作的成果，其基于解耦、状态空间缩减等技术来提升算法的可理解性。算法设计完毕后，在两个大学 43 个学生中进行了和 Paxos 算法对比学习的实验，最终数据，33 个学生在同时学习 Raft 及 Paxos 算法后，对于 Raft 算法的问题的回答要优于 Paxos 算法问题。

Raft 算法和当前的其他几种一致性算法(Oki, Viewstamped Replication)有不少的相似点，不过其中也有几个创新的特性：

• 强 Leader (Strong leader)：整个系统只有 leader 负责接收客户端的请求日志，日志条目只能从 leader 流向其他服务，这个设计简化了日志复制的管理并且使得 Raft 更容易理解；
• 选主(Leader election)：使用随机时间超时来启动选主流程，轻微的机制调整就简单地解决了选主冲突的问题；
• 成员变化：Raft 算法使用了一个联合一致的方法来实现集群成员变化的处理机制，在不同配置转换过程中两个配置的多数成员会重叠，使得在配置变更时整个集群可以继续正常工作；

论文作者认为 Raft 算法在教学及实际实现中要优于 Paxos 及其他已有的一致性算法：

• 更简单并且更容易理解
• 算法细节描述充分完全，可以支持实际系统实现的需要
• 有多个开源的实现并且被多个公司使用
• 算法的安全性有形式化的指定及证明
• 算法的性能和其他算法基本差不多

3.2 复制状态机

一致性算法通常是在复制状态机中出现，在相关的方案中，集群中服务的状态机可以产生相同的状态副本，并且在集群中某些服务宕机的时候整个系统还可以正常运行。复制状态机一般用于分布式系统中解决各种容错相关的问题。比如单集群 leader 的大规模系统 GFS、HDFS 和 RAMCloud 等，通常会使用一个分离的复制状态机来管理选主和保存关键的配置信息。

如上图所示，复制状态机通常是基于复制日志实现。每个服务都存储了一个包含一系列命令的日志，由该服务的状态机按顺序执行。不同服务的日志都包含了同样的命令，并且顺序相同，这样可以保证它们的状态和输出保持一致。

而一致性算法的任务就是要保证复制日志的一致，包括内容及顺序。一个服务的一致性模块从客户端接收到命令后会将命令添加到它的日志中。然后和其他服务上的一致性模块进行通信交互，确保每个服务的日志上最终都在同样的顺序位置包含同样的请求，即使存在服务节点失效的情况。一旦命令被正确地复制到多个服务上，服务的状态机将可以按顺序执行日志的命令，变化状态，并且返回响应给客户端。最终结果，整个集群的服务对外展示为一个整体高可用的状态机。

用于实际系统的一致性算法通常包含以下属性：

• 在非拜占庭条件下确保安全性 (永远不返回一个错误结果)，包含网络延迟、分区及数据包丢失、重复和乱序重组等情况；
• 只要集群中的多数服务是正常运行并且彼此及客户端之间都是可以正常通信的，整个集群就是可用的。比如，一个包含 5 个服务的集群可以容忍任意 2 个服务的失效。一个服务只要停止工作就被视为失效，后续可能再恢复过来并且重新加入集群；
• 不依赖时序来保证日志的一致性，错误的时钟和极端的消息延迟在最坏的情况下才可能导致可用性问题；
• 通常情况下，一个命令只要集群中多数服务节点都响应一轮的远程调用后就可以立即执行完成，少数的执行得慢的服务不会影响整体系统的性能；

3.3 Paxos 的问题

在过去十年中，Paxos 算法几乎就是一致性算法的代名词，最多的被在课堂上教授，也最多业界的具体实现，很多系统实现都是参考和扩展了 Paxos 算法。在本文作者看来，虽然 Paxos 在一致性算法领域曾经是绝对统治地位，但是其也存在两点非常严重的缺陷。

首先，Paxos 算法特别地难以理解，其内容非常晦涩，很少人能完全地理解它，而且还需要非常大的努力。结果是，很多人都尝试对于 Paxos 算法进行更简化的解释，而这些解释主要是在其单一决策 ()(single-decree) 的子域，也非常有挑战性。

Paxos 算法定义了一个能对单个决策达到一致意见的协议，这个被称为单一决策 Paxos (single decree Paxos)，然后再将多个协议的实例组合为多决策 Paxos (multi-Paxos)。单一决策 Paxos 是 Paxos 算法的基础，作者认为这正是其晦涩的地方。单一决策 Paxos 非常紧凑和精妙，它被分为两个阶段并且缺乏简单直接的解释，也没办法独立地被理解。所以一般难以对单一决策协议可行性建立一种直觉，更别说组合单一决策构成决策 Paxos 更增加了整个算法的复杂性。

Paxos 算法存在的第二个问题是并没有为建立一个实际的系统实现提供很好的基础。一个原因是， Lamport 的原始论文里面大部分内容是围绕单一决策 Paxos 的，对于 multi-Paxos 只是简单提供了可能的方案，并且缺少细节。所以业界对于 multi-Paxos 的实现也没有一个被广泛认同的算法方案，有很多类似的方案，但是各自的实现细节也存在不同的地方。

并且，也是由于单一决策协议，Paxos 的架构也难以建立一个实际的系统。作者这里主要是认为 Paxos 的日志的处理和对称多主决策方案在实际实现时存在比较多的问题。从当前实际实现了类 Paxos 算法的系统来看，它们很少是完全按照 Paxos 算法来实现的，每个都是从 Paxos 出发，然后设计实现了差异非常大的架构。Chubby 开发者的评论非常典型 "Paxos 算法的描述和真实世界系统的需求之间存在非常大的差距...最终实现的系统将是基于一个未证明的协议"。

作者对 Paxos 算法的吐槽正是其设计 Raft 算法的初衷，他认为 Paxos 算法既不适用于教学，也不能很好达到实际系统实现的需求。

3.4 基于可理解性的设计

作者设计 Raft 算法时是基于可理解性来进行的，下面是几个需要达成的目标：

• 必须为系统构建提供一个完整并且具备实际意义的基础;
• 在所有条件下都保持安全性，并且在常规的运维操作中保持可用性；
• 对于场景的操作效率高；
• 最重要的目的：可理解性，必须能够让大量的阅读者舒适地理解整个算法，可以对算法建立需要的直觉，易于在实际实现中进行扩展；

基于以上的目标，特别是易于理解和实现的考虑，Raft 算法的设计应用了下面两个常见的技术手段：

• 问题解耦：将大问题解耦为小问题，再逐个解决；
• 简化问题空间：主要是通过减少需要考虑的状态来实现，使得整个系统没有复杂的状态和尽量消除未定义的状态；

从算法设计方面来说，一般是尽量考虑消除非确定性的操作步骤，但是在 Raft 算法中，作者在选主操作中应用了随机的方案，也达到了一个很好的效果。

3.5 Raft 一致性算法

Raft 算法主要是用于管理复制日志，如上面提到的日志一样。Raft 算法的一致性实现首先是选择一个唯一 leader 节点，然后让这个 leader 完全负责管理所有日志复制的逻辑。leader 接收来自客户端的请求日志，然后把日志复制到其他的服务节点，并且通知其他节点可以安全应用日志到状态机的时机。日志条目只会从 leader 流向其他服务节点，leader 异常失效时会进行新的 leader 选举操作。

Raft 单一 leader 的设计在实现上简化了整个系统的实现，并且也便于理解。整个 Raft 算法解耦为下面 3 个部分内容：

1. 选主操作：当前 leader 失效时，集群必须选举出一个新的 leader ；
2. 日志复制：leader 必须接收来自客户端的请求日志然后复制到集群的其他服务节点，并强制要求其他服务节点接受 leader 同步过去的日志，也就是说， leader 的日志条目可能会导致部分服务节点的日志被覆盖；
3. 安全性：Raft 算法是为了保证多个服务节点的状态机状态一致的，需要保证如果一个服务节点应用了某条日志，那么在同样的顺序，其他服务节点都不能执行不一样的日志条目，Raft 算法设计了不少的限制机制来保证算法的安全性；

3.5.1 基础内容

一个 Raft 集群通常包含多个服务节点，5 是一个典型的数量，允许整个集群容忍 2 个节点异常。这些服务节点通常是以下 3 种状态：

1. 领导者 (leader)：接收所有客户端请求；
2. 跟随者 (follower)：只响应来自 leader 和 candidate 节点的请求，如果碰到客户端请求，则转发给 leader；
3. 候选者 (candidate)：用于选举一个新的 leader；

正常运行中，一般只有一个服务节点是 leader，其他服务节点为 follower。

如上图为 Raft 中服务节点各个状态之间的转换图：

• 初始启动时所有服务节点都为 follower 状态；
• follower 有一个选举超时时间，超时后开始选举，转换为 candidate 状态；
• candidate 接收到多数服务节点的选票后转换为 leader 状态；
• candidate 接收到新的 leader 的请求或者新的 term 值会转换为 follower 状态；
• 同样，一个 leader 如果也接收到新的 leader 的请求或者新的 term 值，也转换为 follower 状态；

以上只是简单的状态转换说明，这里面还有比较复杂的处理逻辑和限制，将在后续详细说明。

Raft 在运行中，将时间分为不同的任期 (term) ，每个任期的长度非固定，实现上 term 用递增的整型数值表示。term 有下面这些特性：

• 一个 term 起始于一次选举，并且最多只能有一个 leader，在这个 term 结束前都是作为整个集群的 leader 响应外部请求；
• 一个 term 可以没有 leader，新的选举将会启动一个新的 term；
• 服务节点之间的请求都包含了发送请求节点的 term 值，当一个节点发现自己的 term 值小于请求服务节点的 term ，将执行相关的状态转换处理逻辑，并且更新自己的 term 值为更大的；

Raft 服务节点相互之间用 RPC 进行通信，基础的只有两个 RPC：

• RequestVote: 由 candidate 节点在选举阶段开始时发起请求；
• AppendEntries: 由 leader 发送日志给 follower ，也作为 leader 与 follower 服务节点之间的心跳请求；

3.5.2 选主 (Leader Election)

Raft 使用心跳机制来维持 leader 和触发选举:

• 服务节点启动时都为 follower 状态，并且只要有来自 leader 节点有效的请求就会一直维持着；
• leader 会定期发送心跳请求给 follower ，实际上就是不携带任何日志条目的 AppendEntries RPC 请求；
• 当 follower 节点在一段时间 (election timeout) 后没有接收到 leader 的有效请求，就会假设当前集群无有效的 leader，并且转换状态，开始进行选举；

当一个 follower 开始选举时，将会：

• 增加其当前的 term 数值；
• 转换状态为 candidate；
• 然后投票给自己；
• 再并发地发送 RequestVote RPC 请求给集群中的其他服务节点；

一个 candidate 节点会一直维持状态直到：

1. 这个节点赢得了选举，将会转换为 leader；
2. 另外一个服务节点成功赢得选举，此节点将会转换为 follower；
3. 这个 term 没有任何的服务节点成功被选为 leader,则启动下一次选举；

candidate 需要接收到来自多数服务节点的选票才能成功赢得选举，每个节点只能投票给一个服务节点(包含其自身)，并且是按照投票给第一个请求的原则执行的。当一个 candidate 赢得选举后，将转换为 leader 状态，并且开始给其他服务节点发送 AppendEntries 心跳请求宣告新的 leader，并且避免其他服务节点发起选举。

当一个 candidate 等候其他服务节点投票时，可能会接收到其他服务节点宣称其为新的 leader 的 AppendEntries RPC 请求。如果请求方的 term 值大于或者等于 candidate 当前的 term 值，则承认该服务节点为合法的 leader，并且转换为 follower 状态，否则会拒绝该请求并保持 candidate 状态。

Raft 中服务节点需要等待一个选举超时时间没有收到 leader 的心跳后才会启动选举，如果两个节点同时超时发起选举并争夺其他服务节点的选票，是有可能出现没有任何 candidate 节点得到多数选票的情况。为了避免这种情况，Raft 对于这个超时时间的值选择使用了随机化的设计。每个节点在开始一轮选举时都会重置其选举超时时间 (election timeout)，具体值通常在 150~300ms 之间。这样即使此轮存在两个节点同时发起选举分离了选票，总是会有一个节点先启动新的一轮选举。

3.5.3 日志复制

当一个节点成功选举为 leader 后，它就可以开始对外部的客户端提供服务了。每个客户端的请求实际上是包含了一个由服务节点状态机执行的命令，而 leader 接收到客户端请求后，会将这个执行命令包装为日志条目，并且追加到其日志队列中。然后 leader 并发地把日志条目发生给所有的其他 follower 节点进行复制。当日志条目成功复制后，leader 将会应用这个日志条目的命令到其状态机，然后响应结果给客户端。follower 节点异常无响应时，leader 将会无限重试发送日志条目的 RPC 请求。

如上图所示，每个服务节点都维持着一个日志队列，里面的每个日志条目包含了以下内容：

• 执行命令：由客户端提交，将会由状态机执行；
• term 值：该日志被 leader 接收添加到队列时的任期，用于检测服务节点之间日志的一致性；
• 索引序号: 用于标记这个日志条目在日志队列的位置；

只有 commited 状态的日志条目才能安全地由状态机执行，而一个日志条目是否为 commited 则是由 leader 来决定的。一旦 leader 成功将创建的日志条目复制到多数的服务节点中，这条日志就会被视为 commited，同时，leader 在该日志之前的其他日志也应该被视为 commited。此外，leader 还会保持及持续更新当前最新 commited 的日志索引，并且在发生给 follower 节点的 AppendEntries 请求中携带上这个索引值。而 follower 一旦了解到某个日志索引及之前的日志都已经处于 commited 状态，就可以安全地在本地的状态机按顺序执行相关日志的命令，更新状态与 leader 保持一致。

Raft 中的日志机制保持以下两个特性：

1. 如果不同节点日志队列的两条日志有相同的索引序号和 term 值，那么它们保存了同样的操作命令；
2. 如果不同节点日志队列的两条日志有相同的索引序号和 term 值，那么这些节点上日志队列在这条日志之前的所有日志条目都是一样的；

一个 leader 在特定的 term 和特定的日志索引位置只能创建一条日志，并且日志条目的位置永远不会发生变化，所以第一个特性得以保证。而第二个特性则是通过一个简单的一致性检查来保证的：

• 当 leader 发送一个 AppendEntries 请求用于复制新的日志条目到 follower 节点时，会附加上这条新日志之前的日志索引及 term 值；
• 当 follower 处理请求时，发现 AppendEntries 携带的前一个日志索引和 term 值在本地的日志队列找不到，将会拒绝该请求；

这个一致性检查可以保证服务节点的日志队列从初始状态到每次扩展都保持着上面两个特性，这样，当 leader 发送给 follower 的 AppendEntries 请求成功返回时，就可以确认 follower 的日志是维持和自己一致的。

在 Raft 集群正常运行中，通常各个服务节点之间的日志是保持一致的，但是实际环境是复杂的，因为各种因素影响，节点之间的日志非常有可能出现不一致的情况。在这个时候，就需要尽快恢复各个节点之间日志的一致性。Raft 中，主要是由 leader 节点来负责处理不一致的情况，采用的方案是以 leader 的日志队列数据为准，强制各个 follower 节点的日志和 leader 节点同步保持一致。这个方案意味着，当 follower 节点和 leader 节点之间的日志存在差异和冲突时，follower 节点的日志将会被 leader 覆盖。实际上这个操作需要一个额外的限制保证，下面会有一节详细论述这个处理的安全性。

leader 主要是通过下面的处理逻辑来实现 follower 节点和 leader 节点的日志保持一致：

• 首先 leader 上会为每个 follower 节点维持一个 nextIndex 的值，用于标识 leader 要发给该 follower 节点的下一条日志的索引；
• leader 当选后将会为每个 follower 初始化 nextIndex 值为 leader 日志队列的下一条；
• 如果 follower 节点的日志和 leader 不一致，来自 leader 的 AppendEntries 请求将会因为日志不一致而被拒绝；
• 当 leader 的 AppendTries 请求被拒绝后，对应 follower 的 nextIndex 将会被递减，然后再重新发起日志请求，直到 nextIndex 标识的日志和 follower 的对应上；
• 接下来 leader 的日志将会覆盖和移除 follower 节点上的日志，最终达到 follower 保持和 leader 节点一致日志的效果；

从上面的逻辑可以看到，Raft 中 leader 及 follower 之间的日志维持一致是在正常的节点交互请求中实现的。这也就意味着，当 follower 和 leader 之间产生日志不一致的情况时，并不需要进行额外的状态切换处理，只需要按照正常的处理逻辑进行处理，follower 的日志将自动会维持和 leader 的一致。

对于 follower 保持和 leader 日志一致的处理，其中可以看到，当 follower 的日志队列和 leader 日志队列相差较多的时候，因为 leader 维持的 nextIndex 每次都只是递减一，所以可能会导致比较多的 AppendEntries 请求被拒绝，从而产生比较多的来回请求响应。一种可以考虑的优化方案是，由 follower 在拒绝一个 AppendEntries 请求时，附加上产生冲突日志条目的 term 值和该 term 下保持的第一个日志，这样 leader 可以跳过该 term 所有冲突的日志，而不再需要每个日志都产生一个新的请求。这个方案理论上是有优化的效果，但是实际应用上，不一定能产生很重大的优化，毕竟实际应用时，异常并不是很常见的情况，另外产生很大日志差异的情况概率也不是很大。

从上面描述的日志复制整个机制来看，在一个 Raft 集群中，只要多数的节点都是正常可用的，那么整个集群都可以对外提供正常的请求处理。内部的服务节点可以根据日志复制机制来维护数据的一致，并且也不会产生数据异常、不一致、丢失的情况。

3.5.4 安全性

论文到目前为止描述了 Raft 中选主及日志复制相关的机制，但是并未能保证不同节点的状态机以一致的顺序执行同样的命令，也就是无法保证服务节点的状态机保持一致。所以，本节将会就选主的流程添加一个限制，以保证相关的安全性。

这个限制是针对能被选为 leader 节点的状态的限制，需要保证任意 term 被选为 leader 的服务节点都包含了之前所有 term 已经 commited 的日志条目。在本节同时也对日志提交的相关规则进行更详细的描述。

3.5.4.1 选举限制

这个限制是在 candidate 发起的 RequestVote 请求中的，具体很简单：请求需要包含 candidate 的日志信息，接收请求的节点如果发现其自身的日志要比 candidate 的日志更新，则拒绝给这个 candidate 投票。

日志更新的定义和比较如下，主要是根据最新的一条日志的 term 及索引值：

• 如果 term 值不一样，则 term 更大的节点日志队列更新；
• 如果 term 值一样，则日志索引值更大的更新；

3.5.4.2 提交前一个任期的日志

上面有描述到，一个 leader 如果将日志复制到多数的节点上，则会认为该日志已经被提交。但是还是存在一种可能性是，leader 复制日志到多数节点上，然后在本地尝试提交日志前宕机，这时，对于下一个 leader ，判断这个日志是否已经提交会存在困难。

为了消除这种异常情况，Raft 算法中不允许通过计算日志复制的数量是否达到多数来提交日志，只有 leader 当前的 term 才能以这种方式来提交日志。在这个情况下，还是有可能来自上个 term 的日志被默认已经提交，比如日志已经复制到所有节点上。

3.5.4.3 安全性论证

接下来是对 Raft 算法的 leader 完整性原则(Leader Completeness Property)的论证，具体是通过反证的方式来进行的。首先假设任期 T 的 leader 在其任期提交了一条日志，但是这条日志并没有被其后任期的 leader 存储，我们定义这个最小的不保存 T 任期已提交日志的任期为 U，且 U > T ，下面是论证的详细步骤：

1. 因为 leader 不删除或者覆盖其自身的日志队列，所以这条日志一定不会存在于 U 任期的 leader 节点中；
2. 如果 T 任期的 leader 将日志复制到了集群中多数节点，U 任期的 leader 接收到了集群中多数节点的投票，则至少有一个服务节点即复制了 T 任期 leader 的日志，又给 U 任期的 leader 投了同意的票，下面的论述将基于这个特殊的节点继续；
3. 步骤 2 提到的这个特殊节点一定是先接受来自任期 T leader 的日志，再投票给任期 U leader，否则根据日志复制的机制，节点的 term 大于任期 T leader 时会拒绝 AppendEntries 请求；
4. 这个节点在投票给任期 U 的 leader 时应该还保存着这个日志条目，因为每个相关的 leader 都包含这条日志， leader 不删除日志条目，而 follower 只有和 leader 冲突时才会删除；
5. 这个节点投票给任期 U 的 leader 节点，所以任期 U 的 leader 的日志必须至少和这个节点一样新，这就和假设矛盾；
6. 首先，如果这个节点最后的日志和任期 U 的 leader 有一样的 term 值，则 leader 必须至少和这个节点的日志一样新，所以 leader 的日志队列包含了投票节点的所有日志条目，这也与假设矛盾，因为投票节点包含了任期 T 提交的日志条目，而 leader U 假设没有；
7. 否则，任期 U leader 的最后日志任期必须要大于这个投票节点的，此外，还要求大于 T，那么任期 U 之前创建了 U leader 最后的日志条目的 leader 也必须包含了任期 T 的这个已提交日志。所以，根据日志匹配原则，U leader 的日志队列也必须包含这条 T 已提交的日志，这也与假设矛盾；
8. 这就完成了整个反证，所以，大于 T 的所有任期的 leader 必然包含了所有任期 T 已经提交的日志条目；
9. 日志匹配原则同时也保证了未来任期的 leader 也包含了间接提交的日志条目；

基于领导者完整性原则，我们也可以证明状态机安全性原则成立，也就是如果一个服务节点应用了某个索引位置的日志到其状态机，则其他服务节点不会在同样的索引位置应用不同的日志条目。

3.5.5 Follower 和 Candidate 宕机

follower 和 candidate 节点宕机的处理相对简单，并且他们的处理逻辑是一致的：

• 当 follower/candidate 节点宕机时，发生给它的 RPC 请求将会失败，leader 将会无限的进行请求重试，当节点启动时，将会收到并处理请求；
• 如果节点在完成 RPC 请求后，发生响应给 leader 之前宕机，则启动后还是会接收到重复的请求，因为对于请求的处理实现是要求幂等的，所以重复的请求不会导致任何的异常；

3.5.6 时间及可用性

Raft 算法设计上尽量避免安全性存在对时间的依赖，但是实际实现时，系统的可用性不可避免会受到时间的影响。Raft 算法中，时间最为关键的地方是选举的逻辑，Raft 如果要成功选举并维持一个稳定的 leader 运行，有以下时间相关的需求：

broadcastTime ≪ electionTimeout ≪ MTBF

broadcastTime: 广播时间，服务节点并发地发生 RPC 请求给集群中每个节点并且成功接受到响应的平均时间；

electionTimeout: 上文提到的 follower 节点选举超时时间；

MTBF： mean time between failure，也就是单个服务节点异常失效的平均时间；

广播时间应当比选举超时时间小几个数量级，这样 leader 可以稳定发生心跳请求避免 follower 启动选举流程。选举超时时间也应该比 MTBF 时间小几个数量级，这样整个集群可以相对稳定运行。

广播时间和 MTBF 是底层系统的特性，选举超时时间的选择则需要我们进行考虑。因为 Raft 的 RPC 请求通常意味着持久化存储接收到的数据，所以广播时间可能范围是 0.5ms ~ 20ms。这样，选举时间应该在 10ms 到 500ms 之间。通常 MTBF 时间在几个月甚至更长，所以通常比较容易满足算法的时间需求。

4 总结

课程对 Raft 算法论文的阅读讨论分为了两个部分，上面这部分内容其实也是 Raft 算法最为基本，最重要的内容，包含了基础的模型、选举、日志复制和安全性的描述及论证。从目前所阅读的内容来看，Raft 算法整体上还是很容易理解的，论文包含了不少实现上的细节，易于参考实现，并且也有足够的安全性保证。

在分布式系统中，各种类型的错误和异常是难以避免的，而 Raft 算法在容错和异常恢复方面也有相关的应对方案。通过相关的机制实现下面几个原则，Raft 算法可以在真实系统应用中容错，稳定地运行：

• 选举安全性: 在一个 term 中，最多只能存在一个 leader；
• Leader 只追加写: leader 节点永远不能覆盖或者删除其日志队列的条目，只能追加写入新的条目；
• 日志匹配原则: 如果两个节点的日志队列包含了一个同样 term 和索引的日志条目，那么这两个日志队列上，在这条日志之前的所有日志条目都是完全一致的；
• Leader 完整性原则: 如果一个日志条目在某个任期已经被提交，则这个日志条目一定会出现在更高任期的 leader 的日志队列中；
• 状态机安全性: 如果一个服务节点应用了指定索引的日志条目包含的命令到状态机，那么其他服务节点的状态机在同样的日志索引位置不会应用不同的日志；

上面这些原则之间也存在支撑的关系，比如日志匹配原则就支持了 leader 完整性原则的实现，而 leader 完整性原则又保证了状态机安全性原则。这种基于原则来进行设计的方法也很值得我们在系统设计时进行参考，只要定义好原则，然后满足原则，那么我们的系统就可以达到预期的目标。

1 概要

本课主要是对分布式系统中复制这个主题进行了讨论，复制是为了容错而存在的，而复制本身又会带来更多的挑战。本课的论文是来自虚拟机提供商 VMWare 的 VMware vSphere Fault Tolerance 产品论文，这个产品是一个虚拟机指令级别的复制系统，是一个切实使用的企业级产品中的一个功能。虚拟机级别的复制对应用甚至操作系统都是透明的，VM 之上程序完全无感知，并且复制状态和粒度非常精确，可以带来很强大的复制功能，但是另一方面实现上也存在很多的困难。

本课相关的材料:

• 课堂 Paper - https://pdos.csail.mit.edu/6.824/papers/vm-ft.pdf
• 课堂录像: https://youtu.be/gXiDmq1zDq4
• 课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-vm-ft.txt

2 要点

2.1 异常与失效

• Fail-stop: 异常导致服务器宕机，完全无效 -> 网络、硬件、掉电等等;
• 逻辑 bug: 分布式系统自身的代码逻辑错误导致异常；
• 配置错误导致异常；
• 不考虑恶意服务和黑客导致的异常；
• 物理世界的异常：地震、台风等等导致机房出现异常或者网络中断；

2.2 挑战

• 判断主节点 (Primary) 已经失效: 网络异常导致脑裂，备份节点认为主节点失效尝试提升为主节点并对外提供服务，在网络恢复后系统处于异常状态；
• 维持主节点/备份节点数据同步：期待对于客户端无感，主备节点需要保证修改的顺序一致，并且处理好非确定性的执行结果同步；
• Fail-over : 异常出现时，备份节点怎么才可以正常成功接管对外服务？应该尽量减少对外的影响，外部无感知；

2.3 复制同步方案

• 状态传输：定时创建状态的 checkpoint，然后同步到备份节点，实现上可以考虑对比上个 checkpoint，只传输差异；
• 复制状态机 (RSM) : 主节点同步操作命令到备份节点，备份节点按顺序执行一致的操作，以保证主备状态一致；

目的都是为保证主备节点的状态一致，状态传输的方式在状态很大的情况下会比较耗时，并且对网络带宽要求很大。

而复制状态机是常见的方法，上节课的 GFS 也是应用了复制状态机的方案。复制状态机的方案还需要考虑非确定的执行，比如获取当前时间的操作、或者随机数的操作。

操作复制的级别

1. 应用级别的操作: 比如 GFS 的文件追加写操作，和应用强相关;
2. 机器级别的操作指令: 机器执行的指令，与应用无关，不关注运行的应用程序；

2.4 VMware FT

虚拟机级别的复制，直接复制虚拟机执行指令操作，对应用程序透明，对请求的客户端隐藏具体实现，尽量减少复制对性能的影响。VMware FT 是真实的应用产品，是商用的。

2.4.1 总览

• 层级：硬件 -> 虚拟机 (VM / Hypervisor/VM FT) -> 操作系统(linux) -> 应用程序；
• 捕获操作系统的中断，由 VM FT 执行复制到备份 VM，通过日志通道；
• 主备之间存在一个日志通道用于传输主节点的非确定相关操作指令；
• 客户端只与主节点交互和通信；
• 备份节点和主节点执行一样的操作指令，但是不会直接与客户端交互，不会对外输出；
• 备份节点操作系统的对外写数据会被 VM FT 处理掉；
• 主备节点同网络内会存在一个存储服务，用于主备之间的协调处理和数据存储；
• 主备节点之间如果存在网络分区，需要依赖共享存储去协调进行主备切换，备节点状态切换为单节点的主节点状态，并开始接收和处理客户端的请求及进行响应；
• 主备节点在共享存储上利用一个类锁机制标识(flag)来实现状态切换；
• 主节点失效，备份节点转换为主节点对外服务，这时候就是单点状态，需要考虑启动一个新的备份节点继续执行复制，VM FT 是利用 VMMotion 复制主虚拟机来实现创建新的备份虚拟机的；

主节点通过日志通道发送给备份节点的情况：

1. 有可能会导致主备执行出现分离的时候，相关执行指令及数据会发送给备份节点：外部事件，客户端的 packet 数据，中断等；
2. 非确定性执行指令的结果需要发送给备份节点；

备份节点必须要落后主节点一个日志条目的执行，以保证备份节点的执行不会超出主节点，导致和主节点出现分离。

2.4.2 设计

目标是希望对外能表现为一个单节点服务器一样，外部客户端对主备异常下的切换无感知。

指令类型：

1. 确定性指令：inc, dec, ... 需要保证执行的顺序一致；
2. 非确定性指令：执行多次结果产生的结果不一样，如果直接复制到备份节点执行会影响到结果，导致主备的状态不一致 -> 获取时间操作，计时器中断

多核的情况：多个线程执行是抢占式的，难以保证主备的多核执行指令顺序一致，本论文中应用的是单核虚拟机，暂不考虑多核的实现。

操作系统执行非确定指令时，操作被 FT 捕获，执行结果并记录结果，然后将非确定执行转换为确定性的执行，通过日志通道传输结果给备份节点，在备份节点执行同样的指令时也会捕获指令并返回一致的结果给备份节点的操作系统。

主备复制机制的存在，为了避免在异常切换主备时对外输出存在不一致，主节点对外输出需要特别考虑：

• 主节点执行输出前，需要确保产生输出的操作指令已经同步到备份节点；
• 只是延迟对外输出，主节点接下来指令的执行还是继续的；

客户端可以进行重试或者重置连接，但是基于输出规则，不会存在数据不一致。这个输出机制在实际应用时，比如流量大的应用，会导致应用带宽大幅度下降(40%)，因为主节点需要等待指令操作复制到背节点后再对外响应数据接收，所以运行时带宽就会下降。

3 Paper

本课讨论的论文是来自 VMware 公司的企业级商用系统 VMware vSphere Fault Tolerance，下文简称 FT。FT 包含在其商用产品 VMware vSphere 4.0 ，是一个虚拟机指令级别复制的容错系统，实现了主备虚拟机之间完整的指令及状态复制，应用性能影响不超过 10%，并且对运行的应用无需额外实现应用层的复制。

我们常见的分布式系统中，为了容错而考虑复制机制时，通常采用的是应用级别的操作日志复制实现，而本论文的思路是对应用及操作系统运行的虚拟机级别指令进行复制。这个方案可以使得主备虚拟机之间无论上层运行的应用是什么，都可以完成无感透明的复制容错。

这不是一个常见的方案，在具体实现上，涉及到虚拟机底层及硬件指令级别的诸多细节，可想而知存在着很多的难点。本论文主要描述了 FT 整体的设计思路及实现，其中详细讨论了几个关键点，但是整个系统的实现肯定是存在着大量的细节难点，甚至本论文实现的还是针对单核的虚拟机的复制。虽然这个方案并没有被广泛应用，但是 FT 实现中的一些实际考虑和设计也值得我们参考。

3.1 简介

当我们想要实现一个支持容错的分布式系统时，一个常见的方案是主备机制，备份服务始终保持和主服务的状态同步，这样在主服务挂掉时，备份服务可以直接接手对外提供一直的服务。主备服务之间状态的同步通常是通过复制实现的，而无论是什么级别的复制，我们实现一个主备复制支持容错的系统时有两种常见的方案：

1. 状态变化数据复制：把主节点的所有状态变化数据(CPU/Memory/IO设备等等)同步到备份节点；
2. 状态机复制：将主备节点视为启动时状态一致的状态机，这样只需要把会导致主节点状态变化的指令和数据同步到备份节点，然后由备份节点按和主节点一致的顺序执行，这样可以保证主备的状态完全一致，也就实现了同步的效果；

状态变化数据复制需要对比状态差异，并且如果内存因为指令发生大量的变化，需要同步的数据将会是非常大的，而状态机复制是关注导致变化的指令，只需要同步指令，这样实际需要同步的数据就小很多。但是因为虚拟机有很多指令是非确定性的，每次执行的结果可能都不一致，这种指令需要额外的机制来协调处理，以保证主备节点之间的状态不会出现分离。

在物理机器上实现指令级别的复制是很难的，特别是多核的服务器，各种非确定性指令难以实现同步。而本论文产品是基于 hypervisor 实现的虚拟机级别的指令复制，hypervisor 拥有对虚拟机执行指令的完全控制，可以捕获所有非确定性操作的必要信息，并且同步到备份虚拟机进行重放执行，保证状态一致。

基于 hypervisor 实现的虚拟机状态机复制方法不需要硬件修改，可以直接运行在商用机器机器上，并且因为这个方案对于带宽要求不大，还可以考虑部署在不同地点服务器上，以保证更高的容错和可用性。

本论文实现的 FT 是基于 x86 架构的，可以对操作系统及其上运行的应用提供透明的容错支持，实现上是依赖确定性指令回放 (deterministic replay) 的方式，当前版本只支持单处理器的虚拟机复制。

3.2 基本设计

如上图是 FT 的整体架构，主备 VM 分布部署在物理上分离的两个服务器上，只有主 VM 接收外部的请求和输入，并且通过 logging channel 把数据传输到备份 VM 上进行同步。除了外部输入数据之外，传输的还包含了非确定性的指令及相关信息会同步到备份 VM，备 VM 执行一致的指令和产生一致的结果，以保证主备 VM 状态安全一致。对于指令执行产生的对外输出，只有主 VM 的输出会响应到客户端，备份 VM 的输出将会被 hypervisor 丢弃。

3.2.1 确定性回放实现

FT 复制是基于确定性状态机复制来实现的，如果两个状态机初始状态一致，那么只要保证输入数据和顺序完全一致，这两个状态机就可以保证一致的状态变化，产生一样的输出。

VM 的输入包含以下：

• 网络数据包
• 磁盘读
• 键盘及鼠标等外设的输入信息

非确定性的事件(虚拟中断)及操作(读取处理器的时钟)也会影响到 VM 的状态，对于实现 VM 的执行复制，主要是面临着下面三个挑战：

1. 正确捕获所有的输入和非确定性操作；
2. 正确地把输入和非确定操作应用到备份 VM；
3. 完成以上两点并且不会降低整体的性能，或者尽量要减少影响；

实现上，一些复杂的操作系统在 x86 处理器上也有一些未定义的指令执行副作用，对于这些的捕获和在备份 VM 上重放也是一个额外的挑战。

VMware 的 FT 在限定的范围内解决了上面提的这些挑战，其中的确定性回放机制记录了 VM 的输入和关联的非确定性操作指令，以日志条目的形式写到日志文件，再同步到备份 VM 完全按照顺序执行，产生一致的结果和状态。

对于非确定性的指令操作，需要记录主 VM 执行时的额外信息同步到备份 VM，比如 timer 或者 IO 完成中断，这种非确定性事件发生时的指令也会被记录下来，在备份 VM 重放时，执行到该记录指令时，也会产生同样的中断事件。

3.2.2 FT 协议

FT 中使用确定性回放来产生相关的操作日志，但是日志记录还需要通过日志通道传输到备份 VM 执行，为了确保实现容错支持，FT 对日志通道和传输提出了一个协议 (个人感觉应该是成为原则) ，其中基本的需求是：

• 输出需求：备份 VM 在主 VM 失效接管后，需要以保证和主 VM 已经发送到外部的所有输出完全一致的方式继续执行；

对于一个基于复制机制实现高可用的分布式系统来说，高可用不仅要求节点异常时其他节点可以进行故障切换接管对外服务，还需要实现对于外部客户端来说，整个故障切换过程是无感知的。而系统对外的沟通就是输出，所以这里只要能保证主备切换时对外输出是一致的，那么对于外部客户端来说，整个切换就是无感知的。

在这里，FT 提出了一个规则：

• 输出规则：主 VM 在备份 VM 接收并且确认产生输出的关联指令之前都不能发送输出数据到外部；

从这个输出规则来看，只要备份 VM 接收到了产生输出的所有关联指令，包含输出的那个指令，那在主 VM 失效时，备份 VM 是可以顺利接管并且和之前输出保持一致对外继续产生输出。如果相关的指令没有接收到就接管对外服务，因为主 VM 并未对外产生输出，那么接下来的输出就由备份 VM 产生了，即使执行产生了非确定的事件，对于外部客户端来说整个输出也是一致的。

值得注意的一点是，输出规则并不会限制主 VM 继续执行其他的指令，只是延迟了主 VM 对外部输出的命令。因为输出相关基本也是 IO 操作，而操作系统可以支持非阻塞的网络 IO 和磁盘输出，并且通过异步中断来指示输出完成，所以延迟对外部输出对于操作系统执行其他的指令并不会产生太大的影响。

如上图是一个示例，从左到右是主备节点按时间顺序执行指令，而主备之间的线是同步相关的日志，其中主 VM 往备份 VM 同步日志，备份 VM 向主 VM 响应收到日志，上图相关的执行顺序如下：

1. 异步事件从主 VM 同步到备份 VM；
2. 输入指令及数据从主 VM 同步到备份 VM；
3. 主 VM 输出操作同步到备份 VM ，但是这时主 VM 并未对发生输出，而且暂时延迟了；
4. 备份 VM 响应收到输出相关的指令给主 VM，此时主 VM 可以执行真正的对外输出；
5. 主 VM 发生异常失效时，备份 VM 进行故障切换，接管对外服务，因为输出相关指令已经接收到，备份 VM 可以和主 VM 一致地对外输出；

此外，FT 并不保证对外输出是仅有一次的，比如主 VM 接收到备份 VM 的输出相关日志确认后，对外进行输出，然后出现异常，备份 VM 接管后也可能会再次对外进行输出。这种情况，需要依赖操作系统及传输协议来进行容错，比如 TCP 协议对于重复的数据包会自动进行识别和丢弃，这样对于应用来说也是无感知的。

3.2.3 检测和响应故障

在实际运行的过程中，主 VM 和备份 VM 都有可能发生故障：

• 备份 VM 故障时：主 VM 需要从复制日志的模式切换到普通执行模式，停止往日志通道发生日志记录；
• 主 VM 故障时：备份 VM 接管，但是需要先执行完毕所有从主 VM 同步并且已经确认的指令，然后就从回放模式转换为普通执行模式，并且被提升为主 VM，被允许对外产生输出；

备份 VM 接管时，系统会自动广播新的主 VM MAC 地址到网络中，这样物理网络设备可以识别主 VM 的位置。

故障的检测有下面几点相关的：

1. FT 系统会通过 UDP 心跳来检测运行 VM 的服务器的状态；
2. FT 还会检测日志通道的流量情况，包括主向备发送的日志和备向主发生的确认，因为操作系统总是存在定期的 timer 中断，所以主备之间的流量是不会完全消失的；
3. 网络分区总是可能存在的，如果只按上面两点，是有可能存在脑裂的情况，备份 VM 以为主 VM 发生故障而自提升为主 VM，同时存在两个主 VM；
4. FT 中主要是利用共享的存储来处理脑裂的情况，主备 VM 尝试接管对外服务时，会在共享存储上执行一个原子的 test-and-set 操作，如果操作成功就会被允许继续，失败则停止；

最后，当 FT 出现一个 VM 故障时，在另外一个 VM 成功接管后，FT 会再启动一个冗余的备份 VM，继续进行复制和维持与主 VM 的状态一致。

3.3 FT 的实践设计

3.3.1 VM 的启动与重启

在 FT 中的一个 VM 启动或者重启时，能够快速地将 VM 的状态和已有 VM 同步是一个很关键的问题，并且我们希望这个 VM 的启动不会影响到现有 VM 的性能和执行。在 FT，这主要是通过使用 VMware VMotion 功能修改版本来实现的。VMotion 是设计用于实现将 VM 在不同服务器上迁移的，在 FT 中，具体实现调整为复制，创建日志通道并且让主 VM 进入日志记录模式，并且尽量减少影响，整个过程不会导致主 VM 中断超过一秒。

FT 中的所有 VM 都是运行在同一个 VMware vSphere 集群服务器上的，共享了同样的存储，所以在 VM 需要启动一个新的备份 VM 时，可以由集群管理服务根据资源和情况选择一个合适的服务器进行复制和启动，整个过程完全自动并且外部无感知。

3.3.2 日志通道管理

日志通道相关的实现上，FT 系统是通过 hypervisor 在主备 VM 上都维持一个很大的缓存空间，主 VM 把需要同步的操作日志写到主 VM 的缓存空间上，备份 VM 从其缓存空间消费和处理执行操作日志。日志被写到主 VM 的缓存空间后立即就会备刷入到日志通道上，并且尽快地读取到备份 VM 的日志缓存上。日志从网络到备份 VM 的日志缓存后就会立即给主 VM 发生日志确认消息，以方便主 VM 执行输出规则相关逻辑。

下面几个情形会影响整体的执行：

1. 主 VM 的日志缓存被写满：主 VM 会停止执行，这将会影响到外部客户端；
2. 备份 VM 的日志缓存被写满：备份 VM 会进入停止状态，因为备份 VM 本来就不对外输出，所以对外部无影响；

主 VM 的日志缓存是有可能被写满的，虽然备份 VM 理论上执行速度应该是和主 VM 基本一致的，但是在极端压力的情况下，备份 VM 运行的服务器上可能会存在资源不足，包括 CPU， 内存等资源可能都缺乏，从而导致了相关操作的执行慢于主 VM，随着运行时间增长，主备之间的差距可能会越来越大，也就有可能导致主 VM 的日志缓存被写满。

从 FT 系统的实现来考虑，我们也不希望主备 VM 之间的指令间隔越来越大。因为在主 VM 失效之后，备份 VM 需要接管对外进行服务，在正式对外输出之前，备份 VM 也需要将同步到的日志按顺序执行完毕才行。如果间隔过大，那在备份 VM 在能正式对外提供服务之前会有比较大的一段时间，这样外部也会感知到了 FT 下的主备 VM 异常。

基于降低 FT 中主备 VM 操作日志间隔的考虑，FT 对于这种异常情况的处理方案是，通过额外的信息记录主备 VM 之间的执行间隔和保证大小 (100 毫秒)。当执行间隔大于一定值时 (大于 1 秒)，主 VM 的执行速度将会被减缓，直到主备 VM 之间的执行间隔恢复到正常范围，如果备份 VM 的执行速度跟上来，主 VM 的 CPU 限制也会被逐渐放开，整体的执行性能也慢慢恢复到正常值。

3.3.3 FT VM 运维

对于 FT 中的 VM 正常运维操作也需要进行考虑：

• 主 VM 执行正常关机操作，备份 VM 也应该进行关机，而不应该尝试接管对外服务；
• 主 VM 的资源比如 CPU、内存进行了调整，备份 VM 也应该执行相对应的调整；

这些运维操作，会生成特定的控制日志并发生到日志通道上传输给备份 VM 执行。对于大部分针对 VM 的运维操作，一个原则是这些操作只能在主 VM 上执行，然后再通过特定的控制日志同步给备份 VM 执行。

唯一例外的运维操作是 VMotion 的执行，这个操作可以针对备份 VM 进行，用于调整备份 VM 的运行服务器或者恢复备份 VM。VMotion 操作给 FT 的实现带来很大的复杂性：

• 主 VM 进行 VMotion 操作时，备份 VM 需要断开和原来主 VM 的日志通道连接，再重新连接到新的主 VM；
• 备份 VM 进行 VMotion 时，也需要主 VM 进行日志通道的切换；

在进行 VMotion 操作时，FT 要求所有的磁盘操作都完全暂停，对于主 VM 来说，磁盘操作暂停很容易，直接执行就可以了，而备份 VM 则面临更复杂的情况。因为备份 VM 是执行主 VM 的指令的，这也可能包含正常的磁盘 IO 操作，对于备份 VM 来说难以保证在正确的地方停止磁盘 IO。实现上，当备份 VM 在 VMotion 操作最后切换的阶段时，会通过日志通道通知主 VM 临时停止所有的 IO 操作，这样备份 VM 消费到主 VM 同步过来的 IO 停止后会按照顺序执行，然后再执行后续的正常操作。

3.3.4 磁盘 IO 相关实现问题

在 FT 实现上，关于磁盘 IO 有几类问题需要考虑和解决。

第一是磁盘 IO 操作的非确定性执行。磁盘 IO 操作是非阻塞并且可以并行执行访问同一个磁盘位置的，并且在使用 DMA 操作进行内存和磁盘之间的数据传输时，也可能会并发访问同一个内存位置，而并发带来不确定性。FT 主要是通过检测这类型的 IO 操作并转换为顺序的执行来解决这个问题的。

第二个问题是磁盘操作和应用内存操作之间的冲突。磁盘操作包含了 DMA 可以直接读取内存数据，而当应用和磁盘操作同时访问内存同样位置时，也会带来不确定性。FT 主要是通过一个临时的弹性缓存 (bounce buffer) 来解决这个问题的。这个弹性缓存空间和磁盘操作要访问的内存大小一致，磁盘读操作的数据将会先缓存到这个弹性缓存空间中，直到读 IO 完成才会将数据拷贝到操作系统内存。而写磁盘操作则先写到弹性缓存空间，然后再从弹性缓存写到磁盘上。

第三个问题是主 VM 的磁盘操作可能在主 VM 发生异常失效时还没有完成，对于即将要被提升为主 VM 的原备份 VM 来说这个是不可知结果的，并且也不会接收到相关的磁盘 IO 操作完成事件。新的主 VM 也不能直接对操作系统返回一个磁盘 IO 操作失败，因为这样可能会导致不确定的情况，操作系统未必能正常处理磁盘 IO 错误。FT 的方法是重新执行等待完成事件的磁盘 IO 操作，配合之前并发 IO 调整为顺序执行，这样可以保证重新执行也不会产生异常的不一致的情况。

3.3.5 网络 IO 相关实现问题

VMware vSphere 对于 VM 的网络相关内容有特别的性能优化，主要是基于 hypervisor 的异步更新虚拟机的网络设备来实现的。但是异步操作往往意味着非确定性，对于 FT 的 VM 来说，很有可能会导致主备 VM 的状态发生分离。所以，在 FT 中，异步网络优化被取消了，异步地将接受到的数据包更新到 VM ring buffer 的代码会被 hypervisor 拦截并记录下来再应用到 VM 上。

取消网络的异步优化对于性能有一定的影响，在 FT 的实现上，主要是采用以下两个方法来提升 VM 的网络性能：

1. 基于集群优化 VM 的相关拦截和中断：hypervisor 在流式数据传输时可以按数据包分组进行拦截处理，同样相关的中断也可以分组批量进行；
2. 减少数据包传输的延迟：如上面提及的，基于输出原则，主 VM 需要延迟对外的数据传输直至备份 VM 确认相关联的日志已经收到，hypervisor 支持在 TCP 协议栈上注册函数，在接收到数据时可以从一个延迟执行的上下文调用，这样备份 VM 在接收到日志和主 VM 接收到确认都可以快速处理，而无需进行上下文切换。

3.4 参考设计

本节内容主要是一些实现方案的参考设计方案。

3.4.1 共享和非共享磁盘

FT 的默认设计实现中，主备 VM 是共享相同的虚拟磁盘的，这样两个 VM 之间的数据天然就是保持一致，只要维持只有主 VM 对外输出，在故障切换时，备份 VM 可以直接在同样的虚拟磁盘上进行读写操作。

另外一个方案是主备 VM 使用分离的磁盘，各自维护各自的磁盘数据状态，备份 VM 也需要执行写磁盘相关操作。这种方案在主备 VM 物理上的距离太长而不能共享虚拟磁盘的情况，此外对于无法使用共享磁盘的场景也可以支持。非共享磁盘的方案有几点需要注意的：

1. 因为主备 VM 各自维护分离的磁盘，所以对于磁盘写，主 VM 不需要根据输出规则进行延迟；
2. 首次启用主备 VM 时，需要把主 VM 磁盘数据快速同步到备份 VM 的磁盘；
3. 主备可能发生不同步的情况，在同步恢复之后还需要额外考虑磁盘数据的同步处理；
4. 对于脑裂的场景，因为不存在共享磁盘来处理，主备 VM 需要依赖额外的第三方来进行协调；

3.4.2 备份 VM 执行磁盘读操作

FT 的默认设计中，备份 VM 不会从其虚拟磁盘中读数据，只会从主 VM 读取后再视为输入操作同步日志到备份 VM 执行进行同步。

一个替代方案是支持备份 VM 读取磁盘数据，这样主 VM 就不再需要同步磁盘读取的数据，这样可以降低整个日志通道的带宽和数据。不过这个方案也有几点问题：

1. 首先因为备份 VM 也需要执行磁盘读操作，而磁盘读操作有可能会延迟，备份 VM 的执行速度将有可能受到影响，从而影响到主备 VM 的同步处理，此外主 VM 磁盘操作完成后，备份 VM 有可能还没完成；
2. 备份 VM 读取磁盘的操作是有可能失败的，这样还需要进行额外的处理，比如主 VM 读取磁盘成功但是备份 VM 读取失败的情况，或者反过来，实现上都需要更复杂的处理；
3. 在共享磁盘的方案下，如果主 VM 对磁盘的同样位置进行读写，那为了让备份 VM 后续同步后能读取到同样的数据，还需要考虑延迟主 VM 的写磁盘操作。

总而言之，支持备份 VM 也执行磁盘读操作会带来实现上很大的复杂性，而优点只是降低日志通道的带宽和流量。这个方案只是在特定的应用场景下适用，比如磁盘读操作非常多而写相对少的应用。

4 总结

VMware 的 FT 系统是非常有意思的一个实现，在看到本篇论文之前，个人对于复制相关的系统基本上都是基于应用层的一个理解和场景印象，而 FT 基于虚拟机指令级别的复制的确给我带来的一定的震撼。当然，FT 的实现还是有其前提条件的，一个是基于 hypervisor 对虚拟机的管理，使得 FT 系统可以拦截和处理虚拟机的任何执行指令，进行复制相关的逻辑，另外，本论文实现的 FT 还是只针对单处理器的虚拟机，对于并行多核的虚拟机暂未有实际的支持和实现。

虽然 FT 的应用和实现比较受限，但是最终还是实现了一个完整商用的虚拟机级别的复制容错分布式系统，在 FT 上运行的任意操作系统及应用，都可以无需任何额外处理即可获得分布式容错的能力。而 FT 实现中的很多设计和考虑，在我们实现应用层级别的复制时也是可以进行参考的。

1 概要

本课主要是针对分布式系统中容错这个主题进行了讨论，关注的领域是分布式存储系统。先是概述了分布式存储系统的关键点和挑战，然后围绕 GFS 的实现进入了更深入的探讨。GFS 是一个曾经在谷歌中大规模应用的真实分布式系统，对之前课程中涉及到的 MapReduce 应用提供了底层的文件系统支撑。

本课相关的材料:

• 课堂 Paper - GFS: https://pdos.csail.mit.edu/6.824/papers/gfs.pdf
• 课堂录像: https://youtu.be/6ETFk1-53qU
• 课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-gfs.txt

PS. 从课程官网发现 2021 学年新的课程录像已经同步更新到了 Youtube 上，因为疫情原因，课程是线上授课的形式。和 2020 年度现场授课的课程录像相比，线上授课可以直接打开论文进行讨论，整体的信息更丰富一点。所以从第 3 课开始，切换为 2021 年的课程录像进行学习，之前的两课就不再更新了。此外，课程安排相对旧学年有所调整。

2 要点

2.1 存储系统

构建容错的分布式存储系统是分布式领域的一个关键领域:

• 分布式存储保持全局的持久状态
• 应用可以基于分布式存储无状态部署和运行

2.1.1 分布式存储为什么困难?

• 高性能 -> 数据分片(多服务器)，提升系统吞吐量
• 大量的服务器 -> 错误是常态: 一台计算机一年出现一次错误，一千台服务器，每天都可能会出现错误
• 容错设计在大型分布式系统中是必须考虑的 -> 复制
• 复制 -> 数据同步问题(可能存在潜在的不一致)
• 强一致性 -> 一致性协议 -> 复杂消息交互和传输 -> 性能降低

在系统引入了复杂性之后，往往会带来另外一个问题，复杂系统就是需要不断地解决不同的问题，然后在实现时对不可能的点做权衡取舍。

2.1.2 分布式系统中的一致性 (high level)

• 理想的一致性: 就和单服务器表现一样 (完全隐藏背后的大量服务器和复杂交互)
• 服务器在并发时也能逐次执行客户端操作

• 读取到的数据是最近写的数据

• 并发: 单机在应对大量客户端请求时，也需要处理好并发

为了容错引入复制机制，让分布式系统实现强一致性更困难，对于复制协议的实现需要更多的考虑。而复制协议的选择需要考虑实际系统的需求和真实的业务场景。

2.2 GFS

本课的论文是 Google File System，在谷歌当年广泛应用在各种大数据应用(MapReduce, 爬虫, 日志存储分析)中的底层文件系统。

• 高性能: 复制+容错+某种程度的一致性
• 成功的系统: 在谷歌内部广泛应用，MapReduce 的底层文件系统，成千台的服务器

2.2.1 Non-standard design

• 单 Master: 存在单点故障问题
• 存在不一致性: 弱一致性实现

GFS 的实现不是一个完美实现分布式算法或者理论的标准分布式系统，它是一个谷歌基于自身实际业务特征实现的一个可大规模部署应用的成功的分布式系统。

2.2.2 特点

• 大规模: 大量的数据集
• 文件自动分片
• 全局性: 上千台存储服务器对于所有应用代码来说都是同一个文件系统
• 容错: 错误比如会出现，容错及自动恢复
• 业界应用的真实大型分布式系统

2.2.3 设计

• 应用: 类似 MapReduce 中的 Map 或者 Reduce 任务，作为 GFS 的客户端
• Master: 应用与 Master 进行通信执行创建、打开、写入文件操作 -> chunk locations
• Chunk: 64 MB，可以多副本
• 读写: 应用直接与 ChunkServer 通信 -> 系统吞吐量可以很大，多个应用可以并发操作访问
• ChunkServer: 文件没有特殊格式，就是以 64MB 保存到 Linux 文件系统中

2.2.4 Master 状态数据

• filename -> chunk handles 数组: 一个文件可以由多个 chunk 组成
• Chunk handle: 版本号+chunkserver 列表(primary + secondaries)+租约(lease)
• Log + Checkpoint : 操作日志及检查点数据
• Log -> 持久存储: 操作先写入到 Log
• Checkpoint -> 持久存储: Master 内存数据的快照，方便重启时快速启动

单点的 Master 受限于单服务器资源限制，整个 GFS 系统能容纳的文件是存在一个上限的，而且根据后面谷歌工程师的访谈记录，这个限制在谷歌实际应用时，随着业务的发展和数据量的扩大，的确达到了，成为了一个瓶颈。谷歌后来也开始实现了多 Master 的类似系统来优化这个系统。

2.2.5 读文件

• 客户端向 Master 发送读请求，带上文件名和 offset

• Master -> 客户端: chunk handle + chunk servers + version number

• 客户端: 缓存 Master 返回的数据 -> 降低对 Master 的压力
• 客户端从最近的 chunk server 读取 -> 减少网络传输时间及降低集群网络流量
• chunk server 检查 version number -> ok， 发生数据，避免读取到旧数据

2.2.6 写文件

• Append 是常见的操作场景: MapReduce 场景，Map 写中间文件和 Reduce 写最终文件都是 Append 操作
• 写操作需要考虑 chunk 是否有 primary
• 如果没有 primary 需要提升一个 secondary 为 primary ，并且增加 verison number
• version number 必须保存在持久存储中：恢复时需要读取
• 客户端可以从 Master 拿到该 chunk 的所有 Primary 及 Secondary 节点信息
• 数据先从客户端写到该 chunk 所有节点: pipeline 的方式，流水线传输数据
• Master 需要检测客户端写操作的 version number + lease
• 存在一个 secondary 写失败，会返回错误给客户端，客户端需要重新尝试写操作
• at least once
• Chunk 的多个节点之间的数据文件可能不一致

3 Paper

本课的论文是来自谷歌的 GFS，即 Google File System，发表于 2003 年。GFS 在谷歌的服务器集群中是作为 MapReduce 框架等大数据应用的底层分布式文件系统，运行于大量的廉价商用服务器上，并且实现了容错机制，对于大数据任务提供了很不错的性能。GFS 对业界分布式系统设计和实现影响很大，Hadoop 生态中的 HDFS 就是它的开源实现版本。

3.1 简介

GFS 的设计和实现来自谷歌中对于大数据处理急剧增长的需求，是一个基于实际业务需求而设计的分布式系统。实现上，除了考虑传统分布式系统中的扩展性、鲁棒性和可用性等常见特性之外，还根据谷歌的应用实际负载模式和技术环境有额外的考虑：

• 组件失效是常态而不是异常：硬件是廉价的商用服务器，各种组件都很可能出错，应用 bug、操作系统 bug、磁盘、内存、连接器、网络，甚至电源都会出现问题；
• 要处理的文件很大：GB 级别，对于当年常见的数据文件来说是非常巨大的；
• 大部分文件写是追加写：这个是基于类似 MapReduce 这类型应用来说的，并且文件内容一旦写入了，比较少更新，大部分情况下是读取文件内容进行处理，这就说明 GFS 不是用于替换操作文件系统的；
• 系统 API 设计上是基于应用实际需求来进行的，比如对应用提供的原子 Append 操作支持，在谷歌的应用常见下就非常有用；

GFS 不是设计用来作为操作系统基础的文件系统的，所以并没有提供 POSIX 兼容的文件系统 API。

3.2 设计与实现

3.2.1 假设

GFS 的设计是基于下面这些假设来进行的，在设计一个系统时，先对系统的应用场景进行假设和限制，这样我们最终实现的系统才是真正需要的系统：

• 系统是在廉价的商业服务器上构建的，服务器经常会失效， 这意味着系统必须要时刻检测自身的节点状态，实现容错和快速及时地从错误恢复；
• 系统存储的是大量的大文件，可能会有上百万个 100 MB 甚至更大的文件，几个 GB 大小的文件也是常见的，小文件可以支持，但是不会考虑特别的优化；
• 工作负载常见是两种读方式：数据量大的流式读和小数据量的随机读，流式读通常是每个操作几百 KB 或者 1MB 的数据量，同一个客户端一般会顺序读取一个文件的内容，随机读则是在文件的任意 offset 读取几 KB 的数据，对于关注性能的应用来说，通常是将随机读批量打包为顺序往前读取的操作，而不是前后移动；
• 写方式则常见是大量顺序的追加写文件，操作大小和流式读差不多，并且一旦写入文件内容，基本是不再进行修改，小数据量的随机写也支持，但是不会做特别的优化，效率不会很高；
• 对于多客户端并发写入到同一个文件的场景，系统必须高效地实现相关的并发语义支持。常见的应用方式是基于文件做生产者和消费者队列的方式，数百个分布在数百个服务器的生产者并发追加写入到一个文件，并发操作的原子同步实现尽量要最少的额外开销，这是很关键的一点；文件读取可能是滞后的，也可能是和写同时进行的；
• 对于系统来说，高吞吐量要比低延迟更重要，系统支持的应用对于数据处理的吞吐量需求要高于处理延迟，批量大数据处理才是整个系统的目标；

总结下来，GFS 应该是一个支持容错、支持大量大文件和超大文件(GB 级别)存储、特别对顺序流式写和读优化、支持并发追加写和关注整体系统吞吐量的一个分布式存储系统。对于上面的这些假设或者说需求，GFS 是怎么实现的呢？下面是详细的一个架构和交互设计。

3.2.2 接口

GFS 虽然没有实现一个标准的 POSIX 文件系统 API，但是也提供了和常见文件系统非常相似的接口。文件也是层级组织的目录，并且根据路径名标识，支持常见的 create, delete, open, close, read 和 write 操作接口。

除了常见的文件操作之外，GFS 还支持两个比较独特的操作， snapshot 和 record append 。snapshot 操作主要是用来对数据进行备份，支持对目录树或者文件进行低成本的拷贝，实现上是基于 copy on write 的。而 record append 则是特别针对 GFS 的常见应用场景和需求而实现提供的，支持多客户端原子并发写入到同一个文件。

3.2.3 整体架构

上图是 GFS 整体的一个架构，包含了主要的交互节点角色及部分的数据流转和控制交互。在 GFS 中，关键的节点和组件如下：

• Master：单节点部署，保存整个 GFS 集群中所有文件的元数据，包括文件命名空间、访问控制信息、文件到 chunk 列表的映射关系、每个 chunk 保存的 chunkserver 位置等；还会进行整个系统基本的操作处理，比如 chunk 的租约信息管理、孤儿 chunk 的垃圾回收检索处理、chunk 在 chunkserver 之间的迁移、复制，并且还会和每个 chunkserver 定时有心跳消息，下发指令及采集状态；
• Chunk：文件被划分为多个 chunk，每个 chunk 是固定大小的一个文件，由 Master 分配的一个不可变且唯一的 64 位的 chunk handle 唯一标识，读写操作都是基于 chunk handle 进行的；chunk 保存在普通的 linux 文件系统上，由 chunkserver 管理，并且基于高可用考虑每个 chunk 会有复制的备份保存在多个 chunkserver 上；
• ChunkServer：每个数据服务器上都会部署 chunkserver 来负责对文件的 chunk 进行维护，所以一个 GFS 集群中会有大量的 chunkserver；chunkserver 会与 Master 进行心跳交互，向 Master 汇报维护的 chunk 列表及信息，并且根据 Master 的指令进行 chunk 的迁移复制等操作；chunkserver 直接和客户端交互传输和接收文件数据，大量的 chunkserver 可以实现很大的吞吐量；
• Client：应用代码会链接上 GFS 的客户端库，通过库提供的文件操作 API 和 GFS 进行读写操作交互，客户端和 Master 交互获取和执行元数据相关操作，然后直接和 chunkserver 进行文件数据传输，GFS 库不提供 POXISX API 支持文件操作，不会接入到 linux 的 vnode 层；

上面所有的节点组件都是运行在廉价的商用服务器上，不会依赖特别高性能或者特殊的硬件。

3.2.4 单节点 Master

从上节的架构中，我们可以注意到，在 GFS 集群中，Master 是单节点部署的。在 GFS 中，单节点 Master 的设计极大简化了整个系统的复杂度，让 Master 可以基于全局完整的信息对文件的 chunk 位置和复制等操作进行策略决定。

另外一方面，GFS 必须对读写等操作交互仔细考虑设计，尽量降低操作和 Master 的相关性，避免单点的 Master 成为整个系统的瓶颈。具体设计上，客户端只会向 Master 请求获取操作相关的 chunkserver 信息，并且将获取到的数据缓存下来作为后续操作的依据，然后直接和 chunkserver 进行文件数据读写交互。文件数据永远不会经过 Master 节点。

一个简单的读流程如下：

1. 首先，根据 chunk 的大小值，客户端将文件名和要读取的字节位置 offset 信息转换为文件中的 chunk 索引位置；
2. 客户端发生一个包含了文件名和 chunk 索引位置信息的读请求到 Master 节点；
3. Master 节点给客户端回复该文件的 chunk 对应的 chunk handle 值和 chunk 所在的 chunkserver 列表信息，这里应该包含 chunk 的复制数据位置；
4. 客户端根据文件名和 chunk 索引缓存 Master 返回的信息；
5. 客户端直接请求该 chunk 复制数据所在 chunkervser 节点中的一个，提供 chunk 的 handle 值和要读取的字节范围信息，接下来的读操作是由 chunkserver 和客户端进行交互，不再需要 Master 参与；

实现上，客户端选择 chunk 的 chunkserver 节点原则上是尽量选择最近的一个，而谷歌内部集群的服务器 IP 地址是经过精心编排的，可以根据 IP 地址来计算哪个节点是最近的。此外，在应用中，常见的方式是客户端向 Master 请求多个 chunk 的位置信息，缓存到本地，后续再读取文件时，都可以直接和 chunkserver 交互，大大减少了 Master 的压力。

3.2.5 Chunk 大小

chunk 文件的大小是 GFS 中一个关键的设计点，通常是采用 64 MB ，比一般的文件系统块大小要大得多。每个 chunk 都是以普通 linux 文件的方式保存在服务器上。GFS 的每个chunk 在创建时不会一下子分配 64MB 的文件，而是采用了延迟分配的方式，只有在实际写数据的时候才按需进行分片。这样可以避免空间浪费和文件碎片。

一个大的 chunk 文件大小值有几个好处：

1. 减少了客户端和 Master 的交互，因为读写都是可以基于客户端向 Master 初始请求拿到的 chunk 相关信息缓存数据进行；
2. 因为 chunk 比较大，一段时间内客户端和 chunkserver 的交互都是对于同一个 chunk 进行操作，这样实现上可以采用持久的 TCP 连接，降低网络相关的开销；
3. 减少了 Master 需要保存的元数据数量，实现上 Master 会将元数据保存到内存中，整体数据的大小很关键；

同时这个设计也存在不好的地方，比如对于一个只包含几个 chunk 的小文件，如果过多的客户端同时从这个小文件读取数据，有可能会成为系统中的一个热点文件，相关应用的性能会出现问题。

在 GFS 的使用中，这种情况曾经出现过，在一个批量队列的系统应用中，一个程序往 GFS 写入一个单 chunk 的文件，然后触发数百个服务器同时执行读操作，导致保存这个文件的 chunkserver 严重超负载，影响到了这些 chunkserver 上其他文件 chunk 数据的读写操作。简单的一个处理方案是对于这种类型的应用，在执行写操作时，提高文件的复制系数，把文件分散到足够多的 chunkserver 中，降低单个 chunkserver 的可能负载。

3.2.6 元数据

Master 主要是保存以下三种元数据：

1. 文件和 chunk 的命名空间，也就是目录结构及文件路径信息；
2. 文件到 chunk 的映射关系，一个文件可以由多个 chunk 组成；
3. 每个 chunk 的每个副本的位置信息，也就是保存在哪个 chunkserve 上；

对于命名空间和文件到 chunk 的映射信息，Master 会保存相关的修改操作本地磁盘的操作日志文件上持久化存储，并且还会复制到一个远程备用的服务器上。这种方式可以简单地保证 Master 崩溃时相关操作和数据的一致性和可靠性。至于 chunk 的位置信息，Master 不会持久化保存下来，只会在每次启动时或者一个 chunkserver 加入到集群时，直接和每个 chunkserver 节点交互获取相关的信息。

下面将会对 Master 元数据的关键设计点进行说明。

3.2.6.1 内存数据结构

Master 将数据保存到内存中有几个好处:

1. 内存访问速度快，也就意味着 Master 节点处理请求操作的速度很快；
2. Master 可以方便地定期扫描整个 GFS 集群的状态，根据状态执行一系列的后台处理；

Master 节点的后台处理是 GFS 集群中很重要的内容，对于 GFS 整体集群的数据一致性和高可用等等保证是关键的处理，包含以下内容：

1. 垃圾回收：处理异常导致的无效的 chunk；
2. 重新复制：对于一个 chunk ，如果有副本所在的 chunkserver 服务器挂掉导致复制系数达不到设定的值，需要选择新的 chunkserver 节点重新复制数据，以保证 chunk 数据的高可用；
3. 基于服务器的负载和磁盘空间信息将 chunk 数据在不同的 chunkserver 之间进行迁移，保持整个 GFS 集群的稳定和高效利用；

以上处理在实现上存在比较多的细节和考虑，论文下面的章节中都有具体地进行了讨论。

对于把元数据保存到内存中这个方案，一个常见的关注点是整个 GFS 集群的文件容量是受限于 Master 节点服务器的内存大小的。论文中给出了几点解释，一个是每个 64MB chunk 的元数据不会超过 64 字节，另外真的出现容量问题，在 Master 节点服务器上添加内存的代价是比较低的。相对于可能存在的容量限制和需要硬件更新的代价，完全内存数据结构带来的简单、高效、可靠、性能和灵活性是非常值得的。

PS. 在谷歌应用 GFS 的过程中，容量最终成为了一个不可忽略的问题，根据一个与 GFS 开发工程师的访谈记录 ，随着谷歌内部的数据量从数百 T 到 PB，甚至到数十 PB 级别，单节点 Master 的确成为了系统的瓶颈。所以后续 GFS 也实现了类似多 Master 的模式。这个访谈记录透露了关于 GFS 的不少有趣内幕，可以看看。

3.2.6.2 Chunk 位置

对于每个 chunk 数据及其复制在哪个 chunkserver 服务的位置信息，Master 虽然会在内存中保存完整的数据，但是不会将这部分数据持久化到磁盘上。Master 节点启动的时候，直接从每个 chunkserver 拉取所有 chunk 的信息，然后后续定期通过心跳消息维持数据的时效性。这个设计有几点考虑：

1. 实现起来比较简单，不需要考虑太多 chunk 位置信息在 Master 内存、磁盘及 chunkserver 状态变化时的同步处理；
2. 此外，chunkserver 是保存 chunk 数据的服务，应当有最准确的 chunk 信息，没必要在 Master 还保持一份持久化信息，chunkserver 的失败是很常见的，数据持久化了再处理同步就很麻烦；

3.2.6.3 操作日志

操作日志是 GFS Master 中很重要的一类数据，关系到 GFS 关键元数据的完整性和可靠性。此外，对于 GFS 上的并发操作，操作日志也天然存在一个逻辑顺序的时间线。对于元数据操作日志， GFS 有以下处理：

1. 用户的操作产生的元数据只有在成功持久化到磁盘后才会对客户端可见；
2. 操作日志会被复制备份到多个远程服务器上，并且要在 Master 本地和远程复制节点都把操作日志持久化到磁盘后才会返回响应给用户；
3. Master 会将操作日志批量写到磁盘上；

Master 重新启动时，会读取操作日志进行执行来恢复元数据的内存状态。为了减少加载时间，GFS 支持定时将 Master 内存状态数据作为 checkpoint 数据保存到磁盘上。checkpoint 是元数据按内存数据结构直接保存的，在重启时可以直接加载到内存中恢复数据状态，不再需要解析和执行操作。加载完最新的 checkpoint 数据后，Master 只需要将最新 checkpoint 后的操作日志进行重新执行就可以把整体状态恢复到最新了。创建 checkpoint 之前的操作日志可以直接删除掉以减少空间。

checkpoint 数据的创建也有需要注意的地方，在元数据比较多的时候，整个操作可能是比较耗时的，应该尽量避免对 GFS 正常的业务处理造成影响。所以实现上，Master 会在分离的线程上执行相关的创建操作，此外也会切换一个新的日志文件记录新的操作日志。在 checkpoint 创建完毕之后，会持久化到本地和远程磁盘上。

操作日志是现在一些分布式系统中比较常见的设计方案，有些系统也会将其称为 Binary Log (binlog), Write Ahead Log (WAL) 等等。实现上也是差不多，首先系统存在状态，操作日志记录的是对系统状态的变更操作，包括插入/更新/删除。正常业务和处理多节点复制之前，都需要保证操作日志持久化成功。然后为了加速服务重启加载，通常也是采用定时 checkpoint 整个状态数据的方式，此外，还可以对操作日志进行压缩处理，比如同一个 Key 的多个变更操作，可以压缩为最后一个更新或者删除操作。

现在常见的分布式系统中，操作日志也多应用于多复制节点间的数据同步处理，实现上也有差不多的考虑。

3.2.7 一致性模型

GFS 实现的一致性模型是宽松一致性模型，很好地支持了谷歌的大规模分布式应用，同时实现上也是比较简单和高效的。本节内容主要是具体讨论 GFS 提供的一致性保证，以及对于应用的实现上的影响和需要考虑的地方。

3.2.7.1 GFS 的保证

首先，文件命名空间，也就是文件目录树相关的变更操作是原子性的，实现上是通过 Master 的锁机制和操作日志来保证的。锁机制保证操作的原子性及数据的正确性，而操作日志则是明确了操作的全局执行顺序。

对于文件的数据变更操作则复杂得多，操作是否成功，是否并发，都需要考虑。首先需要明确对于文件数据的几个概念:

• 一致(consistent) : 所有客户端从所有的 chunk 数据副本总是能读到同样的数据;
• 确定(defined) : 如果对于文件数据的一个变更操作是一致的，并且所有客户端都读到这个写的内容，那么这个文件数据是确定；

变更操作一致性的几种情况：

• 非并发成功的变更操作，所有受影响的文件都是确定的，也就是这个操作是一致的： 所有客户端都可以读到同样的数据，并且看到变更操作的内容；
• 并发且执行成功的变更操作，所有受影响的文件是未定义状态，但是是一致的: 所有客户端可以读到同样的数据，但是数据可能不是来源同一个操作，更常见的情况是多个并发的变更操作数据混合在一起；
• 失败的操作会导致文件不一致：不同的客户端在不同的时间点可能从不同的复制节点文件读取到不一样的数据；

变更操作主要包含以下两种:

1. 写操作: 将数据写入到文件指定位置中；
2. 追加写操作: 将数据原子地写入到文件的当前位置，由 GFS 决定和解决并发写的情况；

成功的变更操作后，GFS 会保证相关的文件所有的节点都是确定的，实现的方式首先是在每个 chunkserver 上对 chunk 的多个变更操作顺序都是保持一致的，另外，还会利用 chunk 的版本号信息来判断 chunk 的副本数据是否过期失效。包含了失效数据的复制节点不会参与变更操作或者读操作，并且会尽快被执行回收处理。

之前有提到，客户端会缓存 chunk 的位置信息，所以这个缓存是的确有可能会导致客户端读取到已经过期的副本数据。这个情况无法完全避免，但是实现上会尽量缩减存在的时间窗口和影响。首先客户端的缓存数据是有超时的，在超时后会重新从 master 获取和刷新缓存。然后，对于谷歌来说，大部分的应用模式是追加操作，过期的副本节点一般是返回前面的位置信息，当读者重新从 Master 获取 chunk 信息时，会获取到当前的 chunk 位置信息。

在一个长期运行的 GFS 集群中，即使操作都是成功的，还是会存在组件失败导致数据损坏或者丢失。GFS 主要是通过定期的握手识别失效的 chunkserver 节点，然后通过 checksum 校验检测数据文件是否已经损坏。一个 chunk 的数据只会在 GFS 检测和处理异常之前完全丢失所有复制节点数据的情况下才会丢失，并且也只是丢失，而不是返回错误的数据。

3.2.7.2 应用实现的考虑

对于基于 GFS 的应用来说，要实现宽松的一致性模型很简单，只需要以下几个方式:

• 优先使用追加操作
• 数据检测点(checkpoint)快照
• 写数据自校验、自标识

论文中对于应用的常见提了两个常见的应用例子和实现上的一些细节：

writer 完整写入一个文件的内容：

• 完成数据写入后会原子地重命名文件；
• 定期 checkpoint 已写入的数据，可能会包含一些应用层的 checksum 信息；
• reader 只会校验和处理到最新 checkpoint 的数据；
• 追加操作相对随机写更高效并且对于应用错误有更好的容错性；
• checkpoint 支持 writer 重启时增量处理数据而不需要重新开始；
• checkpoint 可以让 reader 避免处理到已经成功写入但是从应用层面还是不完整的数据；

多 writer 追加写入到一个文件，作为一种生产者-消费者队列的模式:

• GFS 数据追加操作的 append-at-lease-once 语义实现保留每个 writer 的输出；
• 每个 writer 写的记录数据都包含额外的信息，比如 checksum ，这样 reader 可以进行校验；
• reader 在读取数据时可以利用 checksum 信息忽略掉额外的 padding 数据和记录数据碎片；
• 对于重复的记录数据，可以通过记录的唯一标识信息进行过滤处理，比如 web 文件的唯一信息；

3.3 系统交互

GFS 系统设计上考虑尽量减少系统操作交互中涉及到 Master 节点，以降低 Master 的压力。这一节内容主要是描述在 GFS 的数据变更操作、原子记录追加操作、和快照具体实现上，Master，Client 和 chunkserver 是如何交互的。

3.3.1 租约和变更顺序

在 GFS 中，变更是指会修改一个 chunk 的内容或者元数据的操作，比如写或者追加写操作。每个针对 chunk 的变更操作都会应用到该 chunk 的所有副本上。GFS 主要是利用租约机制来实现保证 chunk 变更操作在多个副本上的一致。首先 Master 会选择一个 chunk 的节点，并且给其分片一个租约，这个节点被成为该 chunk 的 primary 节点。然后对于该 chunk 的所有变更操作，primary 节点会选择分配一个顺序的操作序号，其他的 chunk 副本都会按照 primary 选择的顺序应用变更操作。

所以全局的变更顺序是由两个内容决定的:

1. Master 选择分配的租约顺序；
2. 在一个租约内，primary 节点指定的序列；

租约机制主要是基于减少 Master 的管理开销而设计的。一个租约初始的超时时长是 60 秒，不过，只要这个 chunk 一直被修改，primary 就可以一直请求 Master 扩展租约。租约扩展的请求和分配是附加在 chunkserver 和 Master 之间的定时心跳消息中实现的。Master 也可以在某个租约过期前主动地取消其有效期，以实现一些需要的处理操作。如果 Master 和 primary 节点之间的通讯丢失，Master 在上个租约过期后可以安全地将租约分配给一个新的副本。

下面是一个详细的写操作流程，租约在变更操作中有着非常大的作用：

1. 首先客户端会请求 Master 获取指定 chunk 当前持有租约的 chunkserver 信息和其他所有副本的位置信息，如果暂无节点持有租约，则 Master 会在所有副本中选择一个进行分配；
2. Master 响应 chunk 的 Primary 节点标识及其他副本位置信息给客户端，客户端缓存这些信息，在 Primary 节点无法访问或者响应不再持有租约时才需要再次和 Master 节点进行交互；
3. 客户端将数据推送到所有的副本节点，并且顺序可以随意选择，每个副本节点 chunkserver 会将数据保存到内部的一个 LRU 缓存中，知道数据被使用或者过期。这是将数据流和控制流解耦的方法，这样客户端可以根据副本节点的网络拓扑信息来优化数据流调度，提升整体的性能，而不用受到 Primary 节点的限制；
4. 一旦所有的副本节点都响应确认接收到数据，客户端会发生一个携带了之前推送的数据标识的写请求到 Primary 节点。Primary 会给这个写请求分配一个顺序的序号，如果存在多个客户端并发的写请求，Primary 节点会选择一个顺序进行分片，然后该写请求的数据将会按序号顺序保存到节点的本地存储中；
5. Primary 节点完成写操作序号的分配和本地保存后，将写请求发生给其他的复制节点，并且补充序号信息，每个 Secondary 节点都按照序号顺序保存写数据；
6. 所有的 Secondary 完成本地保存的操作后响应给 Primary 节点通知已经完成操作；
7. Primary 节点响应客户端，如果有任意的副本节点出现错误，这个错误信息也会响应给客户端。这种错误情况一般是 Primary 成功，然后 Secondary 节点的任意子集也成功的情况，这个通常也视为该客户端的请求已经失败，之前被修改的数据会保持在一个不一致的状态。客户端代码会通过重试几次 3 ~ 7 的步骤来处理这种异常，最后会从一开始再尝试整个请求。

如果一个应用的写请求数据大小超过一个 chunk 的大小，GFS 客户端会将这个写请求拆分为多个写操作，然后所有的写操作都会按照上面描述的顺序和各个节点进行交互，也有可能和其他客户端的写请求顺序重叠。所以最终文件的数据是很有可能不同客户端的写请求数据分段保存在一起的，不过所有的副本的有效文件数据内容是一致的，因为都是按照 Primary 节点分配的序号进行保存的。

3.3.2 数据流

在 GFS 中，数据流和控制流是分离的，控制流是从客户端到 Primary 再到各个 Secondary 节点，而数据则是根据具体的网络拓扑信息来流转的。首先，数据是线性地在选择好的一系列 chunkserver 节点中流转的，一台 chunkserver 不会同时把数据发生给多个其他 chunkserver。chunkserver 是基于网络拓扑选择最近的另外一个 chunkserver 发送数据，并且是利用以 pipeline 的模式进行数据转发，也就是每收到一些数据，立即就转发给下一个 chunkserver。chunkserver 之间的距离是可以通过 IP 地址信息来计算的，在服务器集群中，服务器的 IP 是经过特意设计，根据物理位置来进行分配的。

这种数据流转方式，一来每个 chunkserver 都只发生数据给一个其他 chunkserver ，可以最大地利用服务器之间的带宽，另外以 pipeline 的模式发送数据，可以极大地降低整体的数据推送延迟，每个 chunkserver 不需要等待接收到完整的数据再进行转发。

3.3.3 原子追加操作

GFS 对于指定位置的并发随机写并不能保证数据的顺序性，文件最终可能会包含来自多个客户端的数据分片。而对于追加写操作，客户端只是提供了具体的数据，但是最终的文件位置则是由 GFS 选择，原子写入后再返回位置信息给客户端。普通的写需要客户端使用类似分布式锁的机制来实现同步，实现上比较重而且性能开销大。 在谷歌的应用中，常见的是追加类型的写操作，一般都是将文件作为多生产者/单消费者的模式应用。追加写的流程和上面描述的类似，只是有一些额外的处理。当客户端推送数据到所有的副本节点后向 Primary 节点发起写请求时，Primary 节点会检查是否写入数据会导致 chunk 超过最大值 (64MB)，如果超过则将 chunk 填充到最大文件大小，并且指示客户端重新在下一个 chunk 发起追加写请求。

任意副本节点上的写失败都会导致客户端重试写请求，这样会导致同一个 chunk 在不同副本节点上可能会包含了不同的数据，有可能是同样数据全部或部分重复保存。GFS 只保证数据在一个原子操作中至少写入一次，并且只要写操作是成功的，对于同一个 chunk 的数据，所以复制节点都是写在同样的位置上。

3.3.4 快照

快照是针对文件或者目录树的，用于备份和数据回滚，实现上基于常见的写时拷贝 (copy-on-write) 技术。当 Master 节点接收到一个创建快照的请求时，会给相关的 chunk 分片一个新的租约，这样客户端进行写操作时就必须再与 Master 节点交互获取最新的 Primary 节点信息，这样 Master 有机会对已创建快照的 chunk 数据执行拷贝处理。

租约被废除或者过期后， Master 会记录这个快照操作日志到本地磁盘，然后再同步到内存的元数据状态中，复制记录一个快照涉及到的文件和 chunk 等元数据。快照创建后，当一个客户端尝试写到一个之前快照操作相关的 chunk 时，Master 会注意到这个 chunk 当前有大于 1 的引用，将会复制原来的数据创建一个新的 chunk ，之后的写操作就是基于新的 chunk 进行的了，和上面描述的流程类似，先选择一个 Primary 节点分配租约，然后进行相关的写流程。

3.4 Master 操作

Master 节点负责着 GFS 中的命名空间的相关操作，包含 chunk 副本节点的控制

1. 决定 chunk 放置的服务器位置
2. 创建 chunk 和复制数据
3. 在整个系统层面协调处理，以保证每个 chunk 都能满足需求的复制程度，均衡整体负载
4. 回收未使用的存储空间

3.4.1 命名空间管理及锁定

Master 支持并发的操作，对于存在竞态的数据主要是使用锁机制来保证操作恰当的执行顺序。GFS 的文件逻辑上是以一个全路径的查找表形式来实现命名空间的管理的，路径管理到文件具体的元数据信息。而命名空间树以前缀压缩的形式保存在内存中，并且该树上每个节点都存在一个读写锁。

举个例子，/d1/d2/d3/.../dn/leaf ，这样一个路径文件的操作，需要获取整个路径上所有节点的锁才可以进行，具体锁类型，前缀的节点需要获取到读锁： /d1, /d1/d2, /d1/d2/d3, /d1/d2/d3.../dn, 而文件上 /d1/d2/d3/.../dn/leaf 根据操作类型需要获取到读或者写锁。

GFS 中的文件组织不存在目录或者类似 inode 的机制，对于子文件的写操作，只需要获取到父目录的读锁就可以避免文件创建时父目录被删除。并且当前的锁机制可以支持同个目录下多个文件的并发更新操作。

GFS 的锁机制还有两点值得注意：

1. 读写锁对象是延迟创建的，并且在不使用的时候就立即删掉；
2. Master 操作获取锁的时候为了避免死锁是按照一致的顺序进行：首先是按照命名空间树的层级顺序，然后同层级是按照字典顺序获取；

3.4.2 副本放置

在真实场景中 GFS 集群是高度分布的，具有很高的复杂性：

1. 数百个 chunkserver (服务器) 节点；
2. 数百个客户端请求访问 chunkserver ；
3. 多个服务器机架，机架之间可能需要跨越一个或者多个交换机；
4. 机架内部的带宽流量要大于机架之间的；

对于 chunk 副本的调度和放置，GFS 主要是基于以下两个原则进行的：

1. 最大化数据的可靠性和可用性；
2. 最大化利用带宽；

所以实现上，副本需要分布在多个机架上，这样读写的流量也可能是需要跨机架进行的，具体实现上存在很多的取舍权衡。

3.4.3 创建、重新复制、均衡负载

GSF 的 chunk 副本创建有三种情况:

1. 创建 chunk；
2. 重新复制：机器出现异常，副本数量不满足设置的值；
3. 负载均衡：需要在服务器之间基于访问和服务器空间均衡 chunk 的副本分布；

创建chunk 的第一个副本，会考虑以下内容：

1. 选择低于平均磁盘空间使用率的 chunkserver 放置新副本，这样随着系统的运行，不同的 chunkserver 服务器的磁盘使用率是趋于相等的；
2. 尽量限制每个 chunkserver 上最近创建的 chunk 副本数量：因为创建之后很可能接下来就是大量的写请求，特别是追加写的情况，这样可以均衡写的流量；
3. 基于 chunk 可用性的考虑，同一个 chunk 的副本也尽量要分布到不同的机架上；

异常发生时可能会让某个 chunk 的副本数量低于用于设置的值，这时候 GFS 集群需要尽快让副本恢复到原来的状态。多个 chunk 的重新复制是存在一个优先级的，基于以下因素考虑：

1. chunk 的副本数量距离设置值的差距，差距越大优先级越高；
2. 在用的文件的 chunk 优先级高于最近被删除的文件的 chunk；
3. 阻塞用户操作的 chunk 优先级会被提升到最高；

chunk 重新复制和上面副本创建的考虑一致，此外为了避免副本重新复制影响到正常的其他读写业务，整个集群中的重新复制的克隆操作数量是受限的，基于 chunkserver 和 集群都存在着一个限制值。此外，chunkserver 也会通过限制复制从源 chunkserver 读取的请求数量来限制复制流量。

GFS 会定期检测和计算 chunkserver 的磁盘使用状态，来进行 chunk 数据的重新负载均衡，尽量维持每个 chunkserver 的磁盘使用率接近平均值。

3.4.4 垃圾回收

GFS 对文件删除的磁盘空间回收不是立即的，而是延迟执行的，从文件和文件的 chunk 都是一样的处理机制。

对于应用主动请求删除的文件，Master 会将该文件重命名为一个新的隐藏的名字，并且补充删除的时间戳。在后续定时检查进行垃圾回收时，对于删除时间大于 3 天 (内部可配置) 的文件及其 chunk 数据，才会进行真正的数据删除和磁盘空间释放，相关的元数据也会被清理掉。在文件被真正删除前，数据都是可读可恢复的。

垃圾回收还存在另外一种情况，每个 chunkserver 都会和 Master 节点维持定时的心跳，心跳中包含了该 chunkserver 维护的 chunk 信息。而 Master 节点会检测并回复在 Master 已经不存在的 chunk 信息，这时候 chunkserver 需要进行对这些在 Master 已经被删除元数据的 chunk 进行删除处理。这种一般是在 Master 执行删除处理时与 chunkserver 的通信失败导致的情况，这些 chunk 也被称为孤儿 chunk。

延迟删除的机制有几点优点：

1. 实现简单，并且在一个大型的分布式系统中，因为组件和服务的异常总是会发生的，及时删除不一定是稳定可靠的，要实现稳定可靠，实现上也存在很多额外的处理和开销，延迟删除提供了一种一致的处理，并且一次失败还会在后续的定时执行的处理中再进行重试；
2. 随机的删除在定时执行检测时可以合并为批量处理，减少了 Master 节点和 chunkserver 之间的通信开销，并且删除时也可以进行批量的 IO 处理；
3. Master 可以选择在系统空闲时进行真的的删除操作，这样一方面避免影响了正常的应用业务，另外一方面也重复利用了服务器的资源；
4. 延迟删除也可以在无意或者恶意删除时恢复数据；

当然，延迟删除的机制也不一定是适应所有的场景的，并且也有其不足的地方。比如因为磁盘空间是延迟释放的，所以会存在一定的磁盘浪费问题，这样如果部署 GFS 集群的磁盘资源比较有限，也会存在一些问题。GFS 实现上支持对这种场景进行配置调优，可以对一些目录数下的文件 chunk 不进行复制，并且删除时是立即释放空间。

所有的机制都是取舍权衡，并不存在一个合适所有业务场景的方案，我们能做的只是根据具体的业务常见选择合适的方案，并且在实现上进行取舍。当然，我们也应该认识到方案存在的缺陷和不能解决的场景，在例外业务场景中更新方案或者调整规避。

3.4.5 无效副本检测

每个 chunk 都维护着一个版本号，每次 Master 给一个 chunk 的副本分配租约时，这个版本号都会增加。所以，对于出现异常不能接收数据更新版本号的 chunk 数据，Master 节点会将其视为已经过期无效，在读写中都会屏蔽掉这些 chunk 副本，并且在定期的垃圾回收中将其删除，释放空间。当然，定期检测 chunk 副本健康度的处理也会给这些 chunk 重新复制创建新的副本。

此外，Master 返回 chunk 信息给客户端时也会带上这个 chunk 版本号信息，这样客户端就可以在与 chunkserver 交互时提供最新的版本号信息，chunkserver 也可以根据这个版本号信息来决定是否可以执行相关的操作。这样，客户端总是能和有最新数据的 chunkserver 进行交互操作。

3.5 容错和诊断

论文从一开始就提及了，GFS 是设计运行在一个异常和错误普遍发生的硬件环境中，所以必须要考虑容错处理。此外，判断是否出现了异常，数据是否损坏也是很关键的内容。

3.5.1 高可用

GSF 的高可用是基于快速恢复和复制来实现的。快速恢复指的是无论 Master 还是 chunkserver 节点，在任何情况下出现异常终止，都会立即启动恢复状态，对于客户端和其他服务节点来说，必须要考虑连接失败和重试。

而复制则是指的 chunk 的副本数据分布在不同的 chunkserver 服务器上及不同的机架上，用户也可以基于实际应用的可用性需求来设置副本数量。Master 节点会在 chunk 副本数量不足或者存在副本的数据被检测到已经损坏的情况下对现有的 chunk 数据进行复制，创建新的副本。

至于 Master 节点，主要是基于可靠性的考虑针对其状态数据进行复制，变更操作日志和快照的创建都会复制到多个服务器上。并且对于状态数据的修改，只有在所有的 Master 副本上保存到磁盘上才被视为提交。这样在运行的 Master 节点失败挂掉时，另外一个 Master 的副本就可以立即基于复制的状态数据启动服务请求。

影子 Master 节点在 Primary Master 节点宕机时也可以作为只读的 Master 节点与客户端，因为通常与 Primary Master 的落后不是特别的大。影子 Master 节点会按照 Primary 节点的顺序应用操作日志修改状态，这样就可以和主 Master 节点保持一致的状态。

3.5.2 数据完整性

GFS 是通过 checksum 来判断存储的数据是否已经损坏的。每个 chunk 分为 64KB 大小的块，而每个块都有一个 32 位的 checksum，这个数据是和 chunk 的其他元数据一起保存在内存中的。chunkserver 在客户端读取请求数据时，在返回数据之前会进行 checksum 的检查，如果和内存的不一致，则说明数据已经损坏。这时候 chunkserver 一个是响应错误信息给客户端，让客户端再尝试从其他副本所在的 chunkserver 读取数据，另外还会汇报这个信息给 Master，Master 会创建新的副本，然后再删除这个数据损坏的副本。

checksum 对读操作有一定的影响，实现上客户端会对齐块大小来读取数据，方便校验 checksum。checksum 的计算对于追加写操作则有特别的优化，支持根据接收到的数据增量地进行 checksum 的计算和追加。对于指定位置的随机写则需要在写之前先校验文件覆盖区域的第一个和最后一个块的 checksum 值，这样如果写的范围是部分覆盖了这两个块数据，可以保证不会隐藏了已经损坏的内容。

chunkserver 也会在空闲的时候扫描和确认每个 chunk 的每个块的 checksum 值，这样也可以清理一些不太常用的 chunk 已经损坏的数据文件。

3.5.3 诊断工具

GSF 主要是基于日志进行诊断的，日志包含管家的事件，比如 chunkserver 的上下线信息，并且还包含了所有请求及响应信息，但是不会记录具体的文件数据。基于降低对主业务影响的考虑，日志的写是异步的，并且是顺序的磁盘写操作。

4 总结

整篇 GFS 的论文包含了大量的系统实现细节，讨论了一个业界真实应用的大型分布式系统中的方方面面，其中很多设计在现在很多新的开源分布式系统中都可以找到类似的实现。GFS 是基于实际的业务场景来设计，设计上即解决了实际的业务问题和硬件资源问题，同时也兼顾考虑实现上的简易性，最终还可以保持相当的健壮性和可靠性。

这是一篇值得不断重复阅读的论文。

5 后记

写这篇论文的阅读这节内容期间因为公司各种出差和事务繁忙，另外一方面也因为论文阅读这节内容一开始是逐句翻译，花费了大量的精力和时间。后面几节内容调整为记录重点内容和用自己的语言重新整理描述论文的实现和关键，整体的速度就快 了很多，而且还可以加强理解和思考。后续的课程论文阅读也计划用这个方式进行。

1 概要

本课没有涉及分布式系统方面的内容，主要是针对本课程 Lab 使用的编程语言 Go 进行了一个简单的介绍，然后讨论了一下多线程并发相关内容。最后是对一个 Go 写的多线程爬虫代码进行了解读，关注点在并发处理、竞态、锁、多线程协作这块。

本课相关的材料:

• 课堂 Paper: 本课无论文阅读
• 课堂录像: https://www.bilibili.com/video/BV1R7411t71W?p=2
• 课堂 Note: https://pdos.csail.mit.edu/6.824/notes/l-rpc.txt

2 要点

2.1 Why Go

• Thread (goroutine) 支持
• Lock: 锁机制应对并发执行和竞态
• 类型安全
• 方便的 RPC 库
• GC 内存安全: 垃圾回收

Go 要比 C++ 更容易使用，语言更简单直接，不会有特别的语法和特性，也不会有那么多奇怪的错误。

2.2 关注并发

对于 Go 来说，并发一般情况是多个 goroutine 在同一个地址空间并发执行。

• I/O concurrency: 客户端可以请求多个服务端并发等待响应，服务端处理多个客户端的连接请求，在一个请求进行 IO 操作时可以切换处理另外一个请求的计算；

• Parallelism: 多线程利用多核，实际系统中应该尽量利用所有 CPU 的计算力；

• Convenience: 后台运行，方便执行处理一些分离的任务；

不用多线程，可以用异步编程 event-driven 的方式:

• 单线程单 loop；
• 保存每个状态: 比如请求客户端的状态；
• 根据事件来执行切换执行任务；
• 单个运行无法充分利用多核 CPU；
• 实现相对复杂，使用起来也难以理解

相对大量线程的情况会更优秀，比如有上百万的连接，对应上百万个线程来说，事件驱动更好，节省资源，同时还可以减少线程切换带来的性能损耗。实现上通常可以多个线程，每个线程都有个独立的事件循环来执行任务，这样可以利用多核资源。比如 Nginx，是基于多 Worker 线程的事件驱动模型来实现高性能并发处理大量请求的支持。

2.3 多线程的挑战

共享数据、竞态数据: 多线程访问处理容易出现 bug，并发更新可能会出现问题，机器操作可能不是原子指令

• 需要使用锁来解决这个问题；
• 或者避免共享可变数据；

coordination 多线程协作执行

• channels
• sync.Cond
• waitGroup

死锁

• 锁或者 channel 误用，出现彼此依赖释放或者消费的情况，导致了死锁；

2.4 爬虫示例

示例代码主要是实现模拟爬虫处理页面抓取的功能，需要考虑以下内容：

• 一个页面可能还包含了其他的页面 URL
• 多个页面可能包含同一个 URL，不应该重复抓取
• 多个页面直接包含 URL 可能会构成一个环
• 页面抓取应当并发进行，可以加速整个任务的执行

课堂上主要是介绍了两个版本的并发抓取爬虫：

1. 基于锁的并发爬虫
2. 每个发现的 URL 都创建一个抓取页面的线程
3. 多个线程之间共享一个 map 数据来记录已经抓取到的页面，避免重复和循环抓取
4. 多个线程对共享的 map 数据操作时需要加锁，避免出现竞态并发更新/读取，在 Go 这会导致 panic 或者内部数据异常
5. 可以通过 go 编译器自身的 -race 工具来检查代码中的竞态问题
6. 基于 Channel 的并发爬虫
7. 区分为 Master 和 Worker 线程
8. Master 线程创建 Worker 线程去抓取单个页面
9. Master 和 Worker 线程之间共享一个 channel，Worker 把抓取到的页面里面包含的 URL 发送到这个 channel；
10. Master 记录 Worker 执行抓取过的 URL，从 channel 获取到新的页面，先检查是否已经抓取过，如果没有则启动新的 Worker 线程抓取，有则跳过；

基于 channel 不需要加锁，是因为记录抓取过页面的 map 数据实际上没有在多个线程中共享，也不存在多线程并发读取更新的情况。但是实际上，channel 数据结构本身在 Go 的实现应该是存在着锁的，这样多个线程每次只有一个线程可以把 URL 发送到 channel 中。

3 总结

本课内容相对简单，Go 语言对于并发的支持比较好，提供了方便的线程(goroutine) 启动方式，此外还对多线程间的协作提供了包括 channel 、sync 等工具来支持。课程原本是用 C++ 来实现 Lab 相关的编码的，近些年在 Go 语言成熟起来后就切换了。使用 Go 来学习和实现分布式系统，可以让学生更关注分布式系统本身相关的内容，而不是在 C++ 的语言特性和代码 Bug 中花费大量的时间。

Go 语言本身也比较适合网络编程，在业界中有不少的成熟的分布式系统实现，比如 etcd、TiDB、Kubernetes 等。