Übung macht den Meister

介绍

这是一篇上世纪九十年代的论文，在当时的环境下，安装新工作站的需求与日俱增，而针对大量工作站的文件系统管理却费时费力。为了保存更多的文件和服务更多的用户，就需要更多的磁盘，并挂载到更多的机器上。某一组文件经常会被手动分配给某些特定的磁盘，当磁盘空间不足，异常或者成为性能热点时，就需要手动移动或者复制文件到其他磁盘上。使用 RAID 技术管理多个磁盘只能解决部分问题；当系统增长到需要多个磁盘阵列和多台服务器时，系统管理问题也随之而来。

Frangipani 是一个可扩展的分布式文件系统，它能统一管理挂载在不同机器上的磁盘，对外来说，这些磁盘构成了一个独立的共享存储池。组成 Frangipani 的机器默认能够被统一管理而且相互间能安全的通信。在 Frangipani 之前已经有了一些分布式文件系统的实现，并且在吞吐和容量上有很好的扩展性。Frangipani 的一个显著特性是它的内部结构非常简单——各台协作的机器共同访问一个通用的存储，并使用锁来保证访问的同步性。这种简单的结构使得只需要少量的机器就能处理系统恢复，重配置和负载均衡。Frangipani 的另一个关键特性是相比于已知的分布式文件系统，它结合了一系列功能使得 Frangipani 更易于使用和管理：

1. 所有用户读取到的文件内容都相同。
2. 可以轻易的向 Frangipani 添加更多的服务器来增加存储容量和吞吐，而无需修改已有服务器的配置，或者中断其操作。这些服务器可以像积木一样根据需要搭建来构建更大的文件系统。
3. 系统管理员添加新用户时无需关心新用户的数据会由哪台服务器管理或者保存在哪个磁盘上。
4. 系统管理员可以对整个文件系统进行完整和一致的备份，而无需停止服务。备份可以在线进行，使得用户可以快速访问被意外删除的文件。
5. 文件系统可以在无需人工干预的情况下容忍机器、网络、磁盘异常并自行恢复。

Frangipani 构建于 Petal 之上，Petal 是一个易于管理的分布式存储系统，为客户端提供了虚拟磁盘。和物理磁盘一样，Petal 的虚拟磁盘也是以块（block）的方式来读取和写入。和物理磁盘不同的是，一个 Petal 虚拟磁盘提供了$2^{64}$字节的稀疏地址空间，并且只在需要的时候才会分配物理存储。Petal 也支持数据备份来保证高可用。Petal 同时提供了高效的快照功能来支持一致性备份。Frangipani 从下层存储系统继承了扩展性，容错和易于管理的特性，不过将这些特性扩展到文件系统还需要些细致的设计。下一节将会详细描述 Frangipani 的结构以及和 Petal 的关系。

上图展示了 Frangipani 的层级设计。多个可替换的 Frangipani 服务器运行于一个共享的 Petal 虚拟磁盘之上，不同的用户程序可以各自通过连接的 Frangipani 服务器来访问相同的文件，而各 Frangipani 服务器间通过分布式锁服务来保证数据的一致性。通过添加 Frangipani 服务器可以实现对文件系统层的扩展。Frangipani 通过异常服务器的自动恢复和借助依然存活的服务器来提供服务实现了容错。相比于中心化的网络文件服务器，Frangipani 通过将负载分摊到各个正在使用文件的机器上来提供更好的负载均衡。出于扩展性，容错和负载均衡的考虑，Petal 和 Frangipani 用到的锁服务也是分布式的。

Frangipani 服务器默认信任 Petal 服务器和锁服务。Frangipani 的最佳使用场景是在同一个管理域下的工作站集群，虽然它也可以扩展到其他管理域下。因此，Frangipani 可以被看做是一个集群文件系统。

论文的作者在 DIGITAL Unix 4.0 之上实现了 Frangipani。得益于 Frangipani 在 Petal 之上构建的简洁的层级设计，使得在几个月内实现了一个可用的系统。

Frangipani 的目标运行环境的场景是程序开发和工程。测试表明在这样的负载下，Frangipani 有着优秀的性能并且能很好的扩展，而最终的性能上限则受限于网络能力。

系统结构

上图展示了 Frangipani 系统下各机器的一种典型职责分配。最上方的机器运行着用户程序和 Frangipani 的文件服务模块，这些机器无需挂载磁盘。最下方的机器运行着 Petal 和分布式锁服务。

不过在实际场景中，组成 Frangipani 的机器无需严格按照上图中的描述承担职责。Petal 和 Frangipani 文件服务不一定要运行在不同的机器上；每台运行着 Petal 的机器也可以同时运行着 Frangipani 文件服务，特别是当 Petal 的机器负载不高时。分布式锁服务独立于系统中的其他服务，上图中描述了每个 Petal 机器上运行着一个锁服务，不过它们也可以运行在 Frangipani 或者其他可用的机器上。

组件

如前面的图中所示，用户程序通过标准的系统调用接口来访问 Frangipani。运行在不同机器上的应用程序能访问到相同的文件，而且看到的文件内容也是相同的；也就是说，如果在某台机器上修改了某个文件或者文件夹，那么运行在其他机器上的程序也能马上看到这个修改。对于使用 Frangipani 的程序来说，Frangipani 提供的文件操作语义保证和本地 Unix 文件系统提供的文件操作语义保证相同：程序对文件的修改会先暂存在内核的缓冲区中，在下一次的 fsync 或者 sync 系统调用之前，系统不保证对文件的修改会保存到非易失存储上，不过系统会记录对文件元数据的修改并且可选的保证当系统调用返回时，文件的元数据修改已经保存到了非易失存储上。和本地文件系统的文件操作语义有点小小的不同，Frangipani 中文件的最后访问时间是一个近似值，从而避免了每次读取文件时都需要写元数据。

每台机器上的 Frangipani 文件服务模块运行在操作系统内核中。通过内核的 file system switch Frangipani 将自己注册为一个可用的文件系统实现。Frangipani 的文件服务模块使用了内核的缓冲区来缓存最近使用的文件数据。它通过本地的 Petal 设备驱动来实现对 Petal 虚拟磁盘的读写。每个文件服务器使用相同的数据结构来读取和写入文件到共享的 Petal 磁盘上，不过各服务器会在 Petal 磁盘的不同区域上针对进行中的修改维护各自的重做日志。因为 Frangipani 的重做日志保存在 Petal 中，所以当某个 Frangipani 服务器异常时，其他的服务器可以通过 Petal 访问日志并进行数据恢复。各 Frangipani 服务器之间无需通信；它们只会和 Petal 和分布式锁通信。这就简化了服务器的添加，删除和恢复。

Petal 的设备驱动程序掩盖了 Petal 分布式的特性，对操作系统的上层应用来说，Petal 就等同于是一块本地磁盘。驱动程序负责和正确的 Petal 服务器通信，以及如果当前的服务器发生异常，能切换到另一台可用的服务器。类似 Digital Unix 的文件系统都可以运行在 Petal 之上，不过只有 Frangipani 提供了多客户端下访问同一文件的数据一致性特性。

Petal 的各服务器基于本地挂载的物理磁盘并通过协作来向 Frangipani 提供大型，可扩展，容错的虚拟磁盘。Petal 可以容忍一个或多个磁盘或者服务器异常，只要大多数的 Petal 服务器依然存活并且相互之间可以通信，以及每个数据块都至少有一个副本保存在物理存储上并且能够被访问。

Frangipani 用到的锁服务能够为网络中的客户端提供通用的读写锁服务。出于容错和扩展性考虑，它的实现是分布式的。Frangipani 使用锁服务来协调对虚拟磁盘的访问，以及保证各服务器内文件缓存的一致性。

安全和客户端/服务器配置

如 Fugure 2 所示，每台运行着用户程序的机器同时运行着 Frangipani 的文件服务模块。虽然这种配置有利于负载均衡和扩展，不过存在安全隐患。每个 Frangipani 机器都可以对共享的 Petal 虚拟磁盘上的数据块进行任意读写，所以 Frangipani 必须运行在受信任的操作系统上；类似于 NFS 的远程文件访问协议中的身份认证还不足以保证安全性。完整的安全性也要求 Petal 和锁服务运行在受信任的操作系统上，并且 Frangipani、Petal、锁服务这三个组件都需要能够互相认证。最后，为了保证文件数据的私有性，也需要保证没有人能够窃听 Petal 和 Frangipani 机器间的网络通信。

一种解决方案是运行用户程序的机器被设置为不允许运行自定义修改的操作系统，同时这些机器间通过一个私有网络连接并且用户程序没有权限访问。不过这并不是说需要将所有的机器放在同一个机房中并通过私有的物理网络相连；可以借助某些加密技术来实现系统的安全启动，以及某些认证技术和加密链路来保证通信安全性。另外，对于某些应用程序来说，一个不完整的解决方案也是可以接受的；典型的如 NFS 就不能防止网络窃听以及杜绝用户在自己的工作站上运行修改后的操作系统。论文的作者并没有实现所有的安全措施，不过 Frangipani 基本也可以达到 NFS 的安全级别，Petal 服务器只会接受来自已知网络地址的 Frangipani 服务器的请求。

如上图所示，Frangipani 文件系统可以扩展到外部非受信的管理域中。图中区分开了 Frangipani 客户端和服务端。只有受信的 Frangipani 服务端可以和 Petal 以及锁服务通信。这三个组件可以放置在一个受限制的环境中并且通过私有的网络连接。而外部的非受信远程客户端只能和 Frangipani 服务端通信，而不能直接访问 Petal 服务器。

客户端可以和 Frangipani 服务端以任何操作系统支持的文件访问协议通信，例如 DCE/DFS，NFS，SMB，因为对于运行着 Frangipani 服务端的机器来说，Frangipani 就类似于是个本地文件系统。当然，如果访问协议本身支持一致性访问是最好的（例如 DCE/DFS），从而使得 Frangipani 的多服务器间的一致性不会在上一层丢失。理想情况下，客户端的访问协议需要支持故障转移。上述提到的协议并不直接支持故障转移，不过在其他系统中如果某台服务器发生异常，会有另一台服务器接管并复用异常服务器的 IP 地址，因此可以在这里应用同样的手段。

除了安全之外，还有第二个原因要使用上述的客户端/服务端配置。因为 Frangipani 运行在操作系统内核，不能快速的适配不同的操作系统甚至是不同版本的 Unix。所以通过远程客户端的方式就能使得运行不支持的操作系统的客户端也能够使用 Frangipani。

讨论

构建文件系统的分层思想——低层提供存储服务，高层提供命名，文件夹和文件服务，并不是 Frangipani 独有的。最早应用这个思想的是 Universal File Server。不过，Petal 提供的存储功能和早先的系统大有不同，从而引申出不同的上层结构设计。

Frangipani 的设计是基于 Petal 提供的抽象存储服务，作者还未充分考虑为了适配其他的存储服务（例如 NASD）需要对 Frangipani 做出哪些修改。

Petal 提供了高可用的存储服务并且能够通过添加资源来实现对吞吐和容量的扩展。不过，Petal 不提供协同功能或者在多个客户端间共享存储。另外，大部分的应用程序不能直接使用 Petal 的接口因为 Petal 面向的是磁盘而不是文件。Frangipani 在 Petal 之上构建了文件系统层使得在保留和扩展了 Petal 有用的特性的同时对应用程序更加易用。

Frangipani 的一个优势是能够透明的添加服务器，删除服务器以及实现故障恢复。通过将预写日志、锁和提供一致性访问、高可用的存储结合使用，Frangipani 能轻易的实现这个特性。

Frangipani 的另一个特性是能在文件系统运行时生成一致性的备份。这个机制会在后面介绍。

不过 Frangipani 的设计可能在三个方面上存在问题。基于启用了副本的 Petal 虚拟磁盘构建的 Frangipani 有时候会记录重复的日志，一次是 Frangipani 自己写入的日志，这里是 Frangipani 为客户端提供服务；另一次是 Petal记录的日志，这里以 Petal 的视角来说 Frangipani 成为了客户端。第二，Frangipani 无法根据磁盘的位置来选择在哪里保存数据，因为 Petal 提供的是虚拟的磁盘，之所以有这个需求可能是因为类似于 GFS 选择在哪里放置副本一样，如果 Frangipani 能知道具体磁盘的位置，它就能选择一个距离客户端近的磁盘保存文件。最后，Frangipani 会对整个文件或者文件夹加锁而不是对某个数据块加锁。不过作者还没有足够的使用经历来评估这三个问题的影响，不过撇开它们不谈，在作者所处环境下测试出的 Frangipani 的性能还是不错的。

磁盘布局

Frangipani 使用 Petal 提供的巨大、稀疏的磁盘地址空间来简化其数据结构。这个想法是受之前有着巨大内存空间的计算机上的相关工作所启发。因为有着如此巨大的地址空间所以可以将其任意切分。

一个 Petal 虚拟磁盘有$2^{64}$字节的地址空间。Petal 只会在物理磁盘空间写入后才会将其提交到虚拟地址中。Petal 同时提供了 decommit 原语用来释放某个范围内的虚拟地址所关联的物理磁盘空间。

为了使内部的数据结构足够小，Petal 会以较大的数据块来提交（commit）和回收（decommit）虚拟地址，目前的数据块大小是 64 KB。也就是说，对于每个 64 KB 的虚拟地址空间$[a * 2^{16}, (a + 1) * 2^{16})$，如果有数据写入且没有被回收，那么同时就需要分配 64 KB 的物理磁盘地址空间。因此 Petal 客户端写入的数据不能太稀疏，否则可能由于碎片化造成物理磁盘空间浪费。下图展示了 Frangipani 如何切分 Petal 的虚拟磁盘空间：

图中的第一个区域用于保存共享的配置参数和其他信息。这个区域的最大大小是 1 T，不过目前实际上只用了几 K。

第二个区域用于保存日志。每个 Frangipani 服务器会在这块区域中选择一部分来保存自己的私有日志。这里总共预留了 1 T 的空间，并切分为256个分区，所以可以保存256份日志。这就限制了一个 Petal 虚拟磁盘最多支持256个 Frangipani 服务器，不过这可以轻易的通过调整分区个数来扩展。

第三个区域用于保存分配位图，从而知道余下的虚拟空间中哪些是可用的。每个 Frangipani 服务器会独占式的锁住这块区域中的某一部分。当某台 Frangipani 服务器的分配位图空间不够时，它会再次找到可用的区域然后加锁使用。整个区域的大小是 3 T。

第四个区域用于保存 inode。每个文件需要一个 inode 来保存元数据，例如访问的时间戳和指向文件数据位置的指针。对于符号链接来说它们的数据直接保存在了 inode 中。每个 inode 的大小为512字节，和磁盘块的大小相同，从而避免了两个服务器同时访问同一个磁盘块上保存的不同 inode 所带来的竞争（也就是 false sharing，FAQ for Frangipani, Thekkath, Mann, Lee, SOSP 1997 中对这个问题有所解释，磁盘数据的读取以块为单位，如果 inode 小于512字节，某个 Frangipani 服务器先读取了磁盘数据块并缓存，此时另一个服务器需要读取和修改同一个磁盘数据块上的 inode，那么为了保证缓存一致性，第一个服务器再次读取 inode 时就需要重新读取磁盘数据块并刷新缓存，造成两个服务器交替的读取修改同一个数据块的内容，缓存也就失去了意义，而本质上两个服务器之间并不应该有竞争。）。整个区域的大小是 1 TB，所以可以保存$2^{31}$个 inode。在位图分配区域中的比特位和 inode 的映射是固定的，也就是说根据位图分配区域中的比特位地址就能推算出对应 inode 的地址，所以每个 Frangipani 为新文件所创建的 inode 地址在第四个区域中的偏移比例和该 inode 对应位图分配区域中的比特位的偏移比例是一致的。不过任何一个 Frangipani 都可能读写或释放某个已经存在的文件的 inode。

第五个区域用于保存小数据块，每个数据块大小为 4 KB（$2^{12}$字节）。一个文件的前 64 KB（16个数据块） 的内容会保存在小数据块中。如果某个文件的大小超过 64 KB，则超过的部分会保存在一个大数据块中。Frangipani 在一个 Fetal 虚拟磁盘上最多可以分配$2^{47}$字节（128 T）的小数据块，共计$2^{35}$块，是 inode 最大数量的16倍。

Petal 虚拟磁盘剩下的地址空间用于保存大数据块。每个大数据块有 1 TB 空间。

选择 4 KB 作为数据块大小会比更小的数据块的策略更容易产生磁盘碎片。同时，一个 inode 512字节在某种程度上也是空间浪费。可以将小文件直接保存在 inode 中来缓解这个问题。虽然存在碎片和空间浪费的问题，不过出于设计简洁性的考虑，作者认为这是一种合理的折中选择。

在当前的设计下，Frangipani 能保存的大文件个数小于$2^{24}$（1600万，大文件需要保存在大数据块中，一个大数据块 1 T，而虚拟空间最大地址$2^{64}$，即$2^{24} T$，又因为不是整个空间都用来保存大文件，所以实际个数小于$2^{24}$），大文件是指大于 64 KB 的文件。另外，Frangipani 能保存文件的最大大小是16个小数据块加上一个大数据块（64 KB 加 1 TB）。如果需要保存更多的文件，可以通过减小大数据块的大小来解决；以及允许一个大文件可以保存在多个大数据块中，这样就可以提高最大能保存文件的大小。如果$2^{64}$字节的地址空间不够，则一个 Frangipani 服务器可以支持扩展为多个 Petal 虚拟磁盘组成的 Frangipani 文件系统。

作者基于之前文件系统的使用经验设定了上述的系统参数。作者认为这种配置已经足够满足需求，不过还是需要时间和实际使用来检验。Frangipani 的设计足够灵活所以可以通过备份和恢复来验证合适的磁盘布局。

日志和恢复

Frangipani 通过元数据的预写重做日志来简化异常恢复和提高性能；不过用户的数据并不会记录到日志中。每个 Frangipani 服务器会将自己的日志保存在 Petal 中。当某个 Frangipani 服务器需要修改某个元数据时，它会首先生成一条日志来描述具体的修改内容并将其添加到内存日志中。这些内存中的日志会周期性的按照修改请求发起的顺序写入到 Petal 中（Frangipani 同时也支持将日志同步的写入到 Petal 中，这会稍微提高容错性不过会增加元数据更新操作的延迟。）。只有当某条日志写入 Petal 之后，系统才会真正修改对应文件的元数据。实际文件的元数据更新会交由一个 Unix 的 update 守护进程来周期性（大概每隔30秒）的更新。

在当前的实现中，Frangipani 写到 Petal 的日志的最大大小为 128 KB。根据 Petal 的空间分配策略，一份日志会拆分到两个不同的物理磁盘上，每个磁盘上的大小为 64 KB。Frangipani 会以环形缓冲（circular buffer）的方式来管理所分配的日志空间。当日志空间满时，Frangipani 会回收25%的最老的日志空间来存放新的日志。一般来说，被回收的日志所对应的元数据修改都应该已经写入到了 Petal 中（通过之前的 sync 操作），因此回收日志时不需要额外的写操作。如果回收日志时发现存在某些待回收的日志所对应的元数据修改还没有写入到 Petal，则需要先执行元数据的写入操作再回收日志。根据日志缓冲区和单条 Frangipani 日志的大小（80-128字节），如果在两个 sync 周期内存在1000-1600个元数据修改操作就能写满整个日志缓冲区。

如果某个 Frangipani 服务器发生异常，系统最终能检测到异常并根据该 Frangipani 服务器的日志进行恢复。Frangipani 服务器异常可以被所访问的客户端发现，或者当锁服务向持有锁的 Frangipani 服务器要求返回锁而没有响应时发现。当异常发生时，负责恢复的守护进程会临时拥有异常的 Frangipani 服务器的日志和锁的所有权。异常恢复进程会先找到异常服务器日志的起始位置和结束位置，然后逐条检查每一条日志，判断哪些日志所对应的元数据更新还没有被执行。当日志处理完成后，异常恢复进程就会释放所持有的锁并清空日志。其他的 Frangipani 服务器就可以在不受异常服务器影响的情况下继续工作，而异常的服务器可以在稍后被重启（对应的日志为空）。只要底层的 Petal 磁盘依然可用，系统就能容忍任意数量的 Frangipani 服务器异常。

为了确保异常恢复进程能找到异常服务器的日志的结束位置（即使磁盘控制器没有按照顺序写数据），系统为每512字节的日志数据块分配了一个递增的序号。只要发现某个数据块的序号小于前一个数据块的序号，那就说明前一个数据块就是日志的结束位置。

Frangipani 确保了日志和异常恢复能正确的处理多条日志。不过这在细节上有几点要注意。

首先，在下一节会介绍到 Frangipani 的锁协议保证了多个服务器对同一个数据的更新请求会被串行执行。某个持有写锁且修改了数据的服务器需要先将修改的数据写回到 Petal 后才能释放锁，所以要么是该服务器在正常情况下数据更新完成后主动释放锁，要么是服务器异常后由异常恢复进程在数据更新完成后释放锁。这说明对于任意的数据块来说，整个系统中最多只可能有一条数据修改的日志还未完成。

第二，Frangipani 确保了异常恢复进程只会处理异常服务器在持有锁之后但还未释放锁期间记录的日志。这是为了确保锁协议保证的更新串行化不会被破坏。Frangipani 使用了更强的条件限制来实现这一保证：异常恢复进程永远不会重新执行一个已经执行完成的数据更新。为了保证这一点，Frangipani 给每512字节的元数据块分配了一个版本号。而类似于文件夹的元数据有可能会跨多个数据块，所以也会有多个版本号。对于每个日志要修改的数据块，日志会记录修改的内容及新的版本号。在异常恢复时，恢复进程会比较当前元数据块最新的版本号和日志中记录的版本号，只有当日志中的版本号大于当前最新的版本号时，恢复进程才会执行重做日志。

由于 Frangipani 记录更新日志时不会记录用户数据，而只有元数据块给版本号预留了空间。这就带来了一个潜在问题。如果某个数据块一开始被用于保存元数据，后来空间被释放，然后又被用来保存用户数据，那么恢复进程就不能正确的跳过依然引用了这个元数据块（现在的用户数据块）的日志，因为原来保存元数据块中的版本号信息已经被用户数据所覆盖，所以恢复进程就无法比较日志中的版本号的大小。Frangipani 通过要求被释放的元数据块只能用于保存新的元数据来避免这个问题。

最后，Frangipani 保证在任一时刻只会有一个异常恢复进程在恢复重做某个异常服务器的日志。Frangipani 通过对日志文件的互斥锁来实现这一保证。

Frangipani 的日志和异常恢复机制假定当出现磁盘写异常时，单个扇区中的内容要么都是旧的，要么都是新的，而不会是两者的混合。如果某个磁盘扇区已损坏并且在读操作时返回 CRC 异常，那么 Petal 内置的副本机制通常能恢复对应的数据。如果某个扇区的副本都损坏了，或者 Frangipani 内部的数据结构由于软件 bug 造成损坏，则需要对元数据进行一致性检查以及需要一个恢复工具（例如 Unix 的 fsck）进行数据恢复。不过论文的作者写论文时还未实现这个工具。

Frangipani 的日志并不是为了给用户提供高层次的执行语义保证。它的目的是为了提高元数据更新的性能以及发生服务器异常时通过避免执行 fsck 这样的恢复工具来加快异常恢复速度。因为 Frangipani 的日志只会记录元数据的更新，不会记录用户数据，所以站在用户的视角来说，当系统发生异常时，文件系统的状态和异常发生前并不能保证一致。论文的作者并不是声明这样的语义是理想的，不过这个行为和标准的本地 Unix 文件系统的行为是一样的。在本地 Unix 文件系统和 Frangipani 中，用户都可以在合适的时间点调用 fsync 来确保更好的数据一致性保证。

Frangipani 所使用的日志技术最早被应用于数据库，并在之后应用到其他某些基于日志的系统中。Frangipani 本身不是个日志结构（log-structured）的文件系统；它不会将所有的数据都保存在日志中，而是将数据按约定维护在磁盘中，通过较少的日志 Frangipani 实现了较好的性能和异常恢复的原子性。和其他基于日志的文件系统不同，但是和例如 Zebra 这样的日志结构文件系统相同，Frangipani 也会保存多份日志。

同步和缓存一致性

由于会有多个 Frangipani 服务器修改 Petal 的共享数据，所以需要一个细致化的同步手段来确保各服务器读取到的数据是一致的，以及当系统负载增加或者添加新的服务器时能通过有效的并发手段来提高性能。Frangipani 使用多读一写的读写锁来实现必要的同步。当锁服务侦测到冲突的锁请求时，它会要求锁的持有者释放锁或者进行锁降级（写锁降级为读锁）来消除冲突。

读锁允许一个 Frangipani 服务器从磁盘中读取相应的数据并缓存。如果该服务器被要求释放锁，则在释放锁前必须先清空缓存。写锁允许一个 Frangipani 服务器读取或者修改数据并将其缓存。只有当某个服务器持有写锁时，它所缓存的数据才有可能和磁盘上保存的数据不同。因此，如果持有写锁的服务器被要求释放写锁或者降级为读锁，则必须先将修改的数据写回到磁盘。如果该服务器降级为了读锁，则依然可以保留缓存，不过如果释放了锁则必须清空缓存。

相比于释放写锁或者降级为读锁时将缓存中的数据写回到磁盘，还可以选择直接将缓存中的数据发送给请求方。不过出于简洁性考虑 Frangipani 并没有这么做。首先，在 Frangipani 的设计中，Frangipani 服务器之间无需通信。它们只会和 Petal 以及锁服务通信。第二，当某台服务器异常时，Frangipani 的设计保证了系统只需要处理异常服务器的日志即可。如果选择将未写入到磁盘中的数据直接发送给请求方，而接收方发生异常时，指向未持久化的数据的日志可能分散在了多台服务器中。这就给系统恢复和日志空间回收都带来了问题。

Frangipani 将磁盘数据结构拆分为了一个个逻辑段，每个逻辑段都对应一把锁。为了避免 false-sharing，Frangipani 确保了一个磁盘扇区不会保存超过1个可共享的数据结构。将磁盘数据结构拆分为可加锁的段是为了将锁的数量控制的足够小，同时又能避免正常情况下的锁竞争，从而使得锁服务不会成为系统的瓶颈。

每个 Frangipani 服务器的日志都是一个可加锁的段，因为这些日志都是私有的。磁盘布局中的位图区域也切分为了一个个段，并且相互之间加了互斥锁，所以分配新文件时不会发生竞争，因为每个服务器都在自己持有的段内分配。还未分配给文件的数据块或者 inode 也同时被位图中的同一把锁保护，只是该位置的空间当前被标记为可用状态。最后，每个文件，文件夹，或者符号链接都是一个段；也就是说，inode 和其指向的数据都被同一把锁保护。这种每个文件一把锁的锁粒度对于作者所在的工作负载来说已经足够了，因为文件几乎很少会被并发的修改。而对于其他的工作负载来说则可能需要更细粒度的锁。

有些操作会要求原子的更新被多把锁保护的磁盘数据结构。Frangipani 通过对锁全局排序以及使用两阶段获取锁来避免死锁。首先，某台服务器先确定需要获取哪些锁。这个过程中会涉及获取或者释放某些锁，例如查找文件夹中的某些文件名。然后，服务器对锁按照 inode 的地址排序然后依次获取锁。同时服务器会检查在第一阶段中读取的对象是否在第二阶段发生了修改，如果发生了修改，那么该服务器会释放所有的锁然后重新执行第一阶段。否则，该服务器就可以开始执行具体的操作，在缓存中修改某些数据并记录一条日志。在缓存中的数据写回到磁盘前，该服务器都会持有相关的锁。

上述描述的缓存一致性协议类似于 Echo、Andrew File System、DCE/DFS 和 Sprite 中的客户端文件缓存协议。这里使用的避免死锁的技术和 Echo 类似。和 Frangipani 一样，Oracle Parallel Server 同样是将缓存中的数据写回到磁盘，而不是直接将缓存中的数据发送给下一个写锁的持有者。

锁服务

Frangipani 只需要一小部分，通用的锁功能，并且不希望锁服务在日常操作中成为性能瓶颈，有很多种实现可以满足这些需求。在 Frangipani 项目中，一共尝试了三种不同的锁服务的实现，其他已有的锁服务也可以提供需要的功能，只是在其之上可能需要编写额外的代码来适配。

锁服务提供了多读一写的读写锁。这里的锁不会用完就马上释放，只要没有其他客户端请求相同的锁，这把锁就会一直被某个客户端持有（这里锁服务的客户端指的是 Frangipani 服务器）。

锁服务通过租约来处理客户端异常。当某个客户端请求锁服务时，它会先获取一个租约。该客户端获取的所有锁都和这个租约绑定。每个租约有一个过期时间，目前是锁创建或者延期后30秒过期。客户端在租约过期前必须先延期，否则锁服务会认为客户端发生了异常。

网络异常会妨碍 Frangipani 服务器延长租约，即使 Frangipani 服务器没有发生异常。当某个 Frangipani 服务器无法延长租约时，它会释放所有的锁并清空缓存。如果缓存中的数据被修改了，那么该服务器会打开某个内部标记使得后续的客户端请求都返回一个错误。相应的文件系统必须取消挂载才能删除这个异常。Frangipani 使用这种粗暴的方式来报告异常从而避免了异常被忽略。

第一版的锁服务实现使用了单节点中心化的服务器，所有的锁状态都保存在了内存中。这种设计对于 Frangipani 来说是足够的，因为 Frangipani 的日志中记录了足够的信息，所以即使锁服务发生异常丢失了所有的状态系统也能够恢复。不过，锁服务异常会导致严重的性能问题。

第二版的锁服务将锁的状态保存在 Petal 中，每个对锁状态的修改都会先写到 Petal 中，然后才会返回给客户端。如果锁服务的主节点异常，那么会由某个备份节点读取 Petal 中的锁状态然后接管异常的主节点并继续提供服务。在这个设计下，异常恢复更加透明，不过日常操作的性能会低于第一种锁实现。作者还未完全实现所有异常的自动恢复就开始了第三种锁服务的实现。

第三版的锁服务是分布式的，并且能很好的支持容错和性能。它由一组相互间协作的锁节点组成，同时每个 Frangipani 服务器内嵌了一个 clerk 模块。

锁服务将锁以表（tables）的形式组织，每个表以 ASCII 字符串的形式命名。每个表中的锁以64位的整型命名。一个 Frangipani 文件系统只使用一个 Petal 虚拟磁盘，虽然多个 Frangipani 文件系统可以挂载到同一个机器上。每个文件系统都绑定了一个关于锁的表。当一个 Frangipani 文件系统挂载时，Frangipani 服务器会请求内嵌的 clerk，然后 clerk 就会打开绑定的锁表。当 clerk 成功打开锁表时，锁服务会返回一个租约标识符，这个租约标识符会在后续通信中使用。当文件系统取消挂载时，clerk 就会关闭锁表。

clerk 和锁节点间使用异步消息而不是 RPC 来通信，这样做能减少内存的使用并同时有着足够好的灵活性和性能。和锁相关的基础消息类型是 request，grant，revoke 和 release。request 和 release 消息是由 clerk 发送给锁节点，而 grant 和 revoke 消息则是由锁节点发送给 clerk。锁的升级和降级同样由这四种消息类型来处理。

锁服务使用了支持容错，分布式的异常监测机制来检测锁节点的异常。这个机制同时也被用于 Petal。该机制基于各节点间定期的心跳交换，同时使用了共识算法来容忍网络分区。

一把锁会在服务端和 clerk 侧都需要消耗内存。在当前的实现中，服务端会为每个锁分配112字节，每个 clerk 如果有进行中或者已分配的锁请求则额外还需要104字节。所以每个客户端每个锁最多使用232字节。为了避免长时间持有锁带来的内存消耗，clerk 会丢弃长时间（1小时）未使用的锁。

一小部分全局且不经常修改的状态信息会由 Lamport 的 Paxos 算法复制到所有的锁服务器上。锁服务复用了为 Petal 实现的 Paxos 算法。全局的状态信息包括锁服务器列表，每个锁服务器负责的锁列表，以及打开还未关闭锁表的 clerk 列表。这些信息用于达成共识，即在各个锁服务器间重新分配锁，当某个锁服务器发生异常时能恢复某个锁的状态，以及协助 Frangipani 服务器的异常恢复。从效率考虑，所有的锁被划分到100个不同的锁组中（lock groups），然后以组的形式分配给锁服务器，而不是以单个锁的形式。

有时候一把锁会被重新分配给其他的锁服务器，一方面是为了故障转移，另一方面是为了充分利用刚异常恢复的锁服务器，避免流量集中。当某个锁服务器被永久的添加到集群或者从集群中删除时，会发生类似的锁重分配。在这种情况下，所有的锁始终会被重分配，因为需要保证每台锁服务器持有的锁的数量是均衡的，锁重分配的次数要尽可能的少，以及每个锁都只会分配给一台锁服务器。锁的重分配也是由两阶段进行。在第一阶段，各个锁服务器丢弃保存在内部状态中的锁。第二阶段，锁服务器会和 clerk 通信，根据其所打开的锁表来重新分配锁。锁服务器根据 clerk 的锁表来重新生成锁的状态，同时通知 clerk 每把锁在重新分配后对应的锁服务器。

当某个 Frangipani 服务器异常时，在正确的恢复操作执行前，它所持有的锁不能被释放。特别的，系统需要先处理异常 Frangipani 服务器的日志并将未持久化的元数据更新写入到 Petal。当 Frangipani 服务器的租约到期时，锁服务会通知另一台 Frangipani 服务器上的 clerk 来执行恢复操作，并撤销原来异常服务器持有的全部锁。负责恢复的 clerk 会获取一把异常服务器的日志的互斥锁。这把锁同样分配了一个租约，所以当负责恢复的服务器异常时锁服务会再找一台服务器重新开始恢复任务。

一般来说，Frangipani 系统能够容忍网络分区，并在可能的情况下继续运行，否则就停止服务。特别的，Petal 可以在网络分区的情况下继续运行，只要大多数的 Petal 服务器依然存活并且相互之间可以通信，不过如果某些 Petal 虚拟磁盘在大多数的 Petal 服务器上没有备份的话，那么这些磁盘无法被继续访问。同样的，只要大多数的锁服务器依然存活并且相互之间可以通信，整个锁服务也依然可用。如果某个 Frangipani 服务器无法和锁服务通信，那么它将再也不能延长租约。此时锁服务会认为这个 Frangipani 服务器发生异常，然后会基于它的日志挑选一个新的 Frangipani 服务器发起恢复流程。如果某个 Frangipani 服务器无法和 Petal 通信，那么它将无法读取和写入虚拟磁盘。不管在哪种情况下，Frangipani 服务器都会拒绝后续受影响的文件系统的用户请求，直到网络分区恢复以及文件系统被重新挂载。

当 Frangipani 服务器的租约过期时存在一个潜在的问题。如果服务器依然存活而只是由于网络原因造成无法和锁服务通信，那么这台服务器可能依然会在租约过期后访问 Petal。Frangipani 服务器会在写入 Petal 前检查租约是否依然有效（并确保在未来的$t_{margin}$秒内依然有效）。不过，Petal 并不会校验某个写入请求是否还在租约有效期内。所以，如果 Frangipani 服务器检查租约和写请求到达 Petal 的时间大于剩余租约的时间，那就会带来一个问题：当 Petal 收到写请求时，租约已经过期，该服务器持有的写锁已经分配给了其他服务器。Frangipani 为$t_{margin}$选择了一个足够大的值（15秒）来确保在正常情况下上述问题不会发生，不过依然不能确保一定不会发生。

在未来 Frangipani 会尝试解决这个问题，论文给出了一个可能的解决方案。Frangipani 会给每一个 Petal 的写请求附加一个过期的时间戳。这个时间戳的值为生成写请求时的租约过期时间减去
$t_{margin}$。这样 Petal 就可以忽略任何时间戳小于当前时间的写请求。只要 Petal 和 Frangipani 服务器的时钟在$t_{margin}$内保持同步，Petal 就能够可靠的拒绝租约过期的写请求。

另一种解决方案则不依赖时钟同步，但是需要将锁服务和 Petal 集成，并且将 Frangipani 服务器获取的租约标识符附加到写请求中，Petal 收到写请求后就可以根据租约标识符校验租约是否过期，从而拒绝过期的写请求。

添加和删除服务器

系统管理员有时需要添加或者删除 Frangipani 服务器。Frangipani 被设计成能够轻易的处理这些场景。

添加一台服务器到运行中的系统只需要一点点的系统管理工作。新添加的服务器只需要知道使用哪块 Petal 虚拟磁盘以及锁服务的地址即可。新添加的服务器会和锁服务通信来获取租约，然后根据租约标识符决定使用哪部分的日志空间，然后就开始提供服务。系统管理员不需要修改其他服务器的配置，其他服务器能自动适配新服务器的上线。

删除一台 Frangipani 服务器则更简单。可以直接关闭这台服务器。不过更可取的方式是让这台服务器先将未持久化的数据写入到 Petal，然后释放持有的锁，最后再停机，不过这不是强制要求的。当服务器异常停机时，如果后续该服务器持有的锁需要被使用，则系统会自动发起恢复流程，并最终使得共享磁盘的数据达成一致。同样的，系统管理员也不需要修改其他服务器的配置。

如 Petal 的论文所描述，Petal 服务器同样可以无缝的添加和删除，锁服务器也同理。

备份

Petal 的快照功能提供了一个简便的方法来备份一份完整的 Frangipani 文件系统快照。Petal 的客户端可以在任意时刻创建一个虚拟磁盘的快照。所创建的快照的虚拟磁盘和普通的虚拟磁盘一样，只不过它是只读的。实际快照实现时采用了写时复制（copy-on-write）技术来提高效率。Petal 创建的快照是崩溃一致的（crash-consistent）：也就是说，快照中保存的是在 Petal 虚拟磁盘中的数据，Frangipani 服务器内存中的数据不会记录到快照中。

因此，我们可以简单的通过创建 Petal 快照并将其拷贝到磁带中来备份一个 Frangipani 文件系统。快照会包含所有的日志，所以可以将其复制到一个新的 Petal 虚拟磁盘中然后根据日志运行恢复程序来恢复一个 Frangipani 文件系统。归功于崩溃一致的特性，从快照中恢复系统后要解决的问题就简化成了和发生系统级别的停电后恢复系统所要解决的问题一样。

可以对 Frangipani 稍作修改来改进这个恢复机制，即创建一个系统文件级别一致的快照，从而也无需执行恢复操作。可以让备份程序先强制要求所有的 Frangipani 服务器进入一个栅栏，这个功能可以由锁服务提供的全局锁来实现。每个 Frangipani 服务器以共享的模式获取这把锁然后执行修改操作，而备份程序以互斥的方式来处理请求。当 Frangipani 服务器收到请求要求释放锁时，它会阻塞所有新的修改数据的文件系统调用然后进入栅栏，接着清空缓存中已修改的数据，最后释放锁。当所有的 Frangipani 服务器进入栅栏后，备份程序会以互斥的模式获取锁，然后创建一个 Petal 快照并释放锁。之后各 Frangipani 就可以继续以共享的模式获取锁，然后恢复服务。

在后一种方案下，一个 Frangipani 的快照可以无需进行恢复就直接挂载使用。用户就可以从新的磁盘卷中在线获取单个文件，或者将其以一个更方便的格式转储到磁带中而无需 Frangipani 参与数据恢复。新添加的卷必须以只读的格式挂载，因为底层的 Petal 快照是只读的。在未来作者可能扩展 Petal 的快照使其可写，或者在 Petal 之上再抽象一层来模拟写操作。

参考

• Frangipani: A Scalable Distributed File System
• FAQ for Frangipani, Thekkath, Mann, Lee, SOSP 1997
• What is the difference between crash-consistent and file-system consistent snapshots?

陈皓在 什么是工程师文化？ 中谈到工程师文化由两点组成：自由和效率。不过我认为可以再加一点，那就是实事求是。实事求是要求尊重客观事实，不弄虚作假，不过现实中往往大相径庭。

不尊重客观事实

福尔摩斯里有一句话：

Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth.

对应了软件开发中一个烂大街的场景：在尽可能的考虑了所有的因素之后，不管完成一个工程所需要的时间是多么的不符合非执行者的预期，最终完成这个工程的时间也只会只多不少。如果无法正视客观事实，则会使得工程从开始到结束都弥漫着自我焦虑。而工程实施时往往只会拙劣的采用10个女人1个月生10个孩子的方式，最终也容易造成工程的反复返工，不过这倒能在总结大会上提供丰富的演讲素材，以及时间紧、任务重的自我感动，然后下次一定。

避实就虚

优秀的团队能正视问题，如果一个团队在面对问题分析时首先想的是哪些问题该提，哪些问题不该提，哪些问题提了会赢得芳心，那这种问题分析就是表演作秀，最终也继续重蹈覆辙。

形式主义

陈皓在 什么是工程师文化？ 中关于工程师文化如何落地提到引入绩效考核，不过这可能会造成形式主义和和团队间无意义的攀比。例如，如果将 Code Review 作为考核指标，难免会出现：快到月末了，还需要再提20个 comment；某部门的人均 comment 有 xx 个，本部门才 yy 个，每个人努努力，提到 zz 个。

移花接木

在成果导向的规则下，如果通过 A，B，C 达成了 D，则直接对外宣称通过 A 达成了 D。

参考

• 什么是工程师文化？

Lab 3 需要我们实现一个基于 Raft 的键值数据库，支持三个操作：

• Put(key, value)
• Append(key, value)
• Get(key)

3A

客户端

客户端要做的只有一件事，就是向某个服务端发送请求。不过由于客户端不知道哪个服务端是主节点，所以需要不断轮询各服务端发送请求。为了避免每次轮询所有服务端浪费时间，客户端可以记录每次请求成功后的服务端编号，这个服务端就是当次请求中的主节点；当客户端再次发起请求时，可以先假定之前的服务端依然是主节点，从而先向该服务端发送请求，如果请求失败并返回 ErrWrongLeader 异常，则再尝试下一个服务端。

服务端

Lab 3 要求服务端将客户端请求成功的结果放到 RPC 响应中，不过 Raft.Start() 的执行成功不代表最终日志的应用成功，所以服务端调用 Raft.Start() 后需要阻塞等待，直到 Raft 将对应日志应用到状态机。等待/唤醒的模式可以想到使用条件变量 sync.Cond，不过 Go 中有 channel 这个更方便的特性来实现。

正常情况下，服务端调用 Raft.Start() 添加日志的顺序和之后从 applyCh 中收到日志的顺序一致，也就是说客户端请求到达服务端并被处理的顺序和服务端从 applyCh 中收到日志的顺序一致。所以，服务端可以维护一个客户端请求的队列，队列中存放的是 channel，每当服务端从 applyCh 中收到日志，就将日志发送到队首的 channel 中，并从队列中移除。这样阻塞等待中的 RPC 服务端线程就能被唤醒，并响应客户端。

不过在异常情况下，客户端请求队列和服务端从 applyCh 中收到日志的顺序并不是一一对应，因此服务端收到日志时需要剔除掉队列中无效的请求，并通过 channel 发送一个 ErrWrongLeader 异常，这样客户端就能换一个服务端来重试。由于通过日志索引无法唯一确定一条 Raft 日志，所以需要在 ApplyMsg 中添加 CommandTerm 来标识日志所属的任期，这样服务端从 applyCh 中收到日志后就能通过比较客户端请求队列中的日志任期和索引来判断请求是否有效。

记客户端请求队列队首日志的任期和索引为 (term_client, index_client)，记服务端从 applyCh 收到的日志的任期和索引为 (term_applied, index_applied)。正常情况下有 term_client == term_applied 以及 index_client == index_applied。从服务端角度来说，异常情况有两种，一种是当前服务端不再是主节点，另一种情况是当前服务端依然是主节点，不过中途发生了主从切换可能造成当前的日志和最初的不同。对于第一种情况可以直接清空客户端请求队列，虽然 (term_applied, index_applied) 有可能匹配部分客户端请求，不过由于当前服务端不再是主节点，下次客户端请求的时候本身就要再轮询所有的服务端，所以这里等同于是提前让客户端轮询。对于第二种情况（也考虑原来是从节点后来变成主节点的场景），可以从队首开始遍历客户端请求队列，剔除掉比 (term_applied, index_applied) 小的 (term_client, index_client) 请求，并通过 channel 返回异常（这里需要一个自定义异常，告诉客户端直接重试，因为当前服务端依然是主节点，所以客户端没有必要轮询）。这里的剔除掉比 (term_applied, index_applied) 小的 (term_client, index_client) 请求，指的是仅保留 term_client >= term_applied 和 index_client >= index_applied 的请求，因为根据 Raft 日志的性质，其他情况下的客户端请求都已经不可能被提交。

因此，服务端需要开启一个单独的 goroutine，并不断的从 applyCh 中获取日志，然后根据日志的指令内容更新本地的键值数据库，最后唤醒客户端请求队列中的请求。而如何实现本地键值数据库不是本实验的重点，所以简单使用了一个 map。

客户端请求去重

6.824 Lab 3: Fault-tolerant Key/Value Service 中提到：

It’s OK to assume that a client will make only one call into a Clerk at a time.

一个客户端一次只发送一个请求，加上请求阻塞的特性，任何时刻每个客户端都最多只有一个进行中的请求。为了对请求去重，每个客户端可以生成一个唯一的客户端 id，每次发请求时生成一个递增的请求序号，而服务端只需要维护每个客户端已提交到状态机的最大请求序号即可，这是因为当前场景下每个客户端的请求序列是个递增的序列（非严格递增，相邻数字之间可能存在重复）。所以，当服务端收到请求时，如果发现请求中的序号小于等于该客户端的最大请求序号，则说明该请求是重复的。

不过，处理重复的读请求有两种方案，一种是返回当前值，另一种是返回第一次收到读请求时的值。两种方式都可解释，本实验中直接返回当前值即可。

那么服务端收到 Raft 日志时如何知道这个日志对应的客户端请求序号？这个属于应用层面的数据，可以将客户端 id 和请求序号放到 Op 中，服务端收到 Raft 的日志后，将 ApplyMsg.Command 进行类型转换，转为 Op 即可。

问题

TestSpeed3A

TestSpeed3A 要求每个心跳周期至少完成三次客户端请求，不过在做 Lab 2 时，Raft 收到日志后不会马上发起共识，而是在下一次发送心跳时批量对收到的日志发起共识。又由于 TestSpeed3A 会循环发起请求，每个请求阻塞，服务端只有在收到 applyCh 的日志后才会通知客户端，所以本质上在这个测试中服务端约等于一个心跳周期只处理一个请求。所以需要修改 Raft.Start()，收到日志后开启一个 goroutine 发起心跳。

客户端请求队列无法被唤醒

服务端收到 Raft 的日志后才唤醒客户端请求队列会造成客户端请求队列永远不会被唤醒，因为这强依赖于某条日志被提交，而客户端的日志不一定会被提交。例如，某个服务端收到客户端的请求，将请求放到队列中，此时服务端发生异常，其他服务端成为新的主节点，而新的主节点并没有收到客户端的日志，在没有其他客户端请求的情况下，最开始的客户端请求永远不会被唤醒。所以，这里也额外开启了一个 goroutine，如果当前服务端不是主节点且客户端请求队列不为空，则清空客户端请求队列，并通知 ErrWrongLeader 异常。

不过，这个策略也会带来一个请求重复执行的问题。当前身为主节点的服务端成功提交了某个客户端的请求，注意这里是 commit，而不是 apply，此时服务端发生异常，另一个服务端成为新的主节点，原来的服务端发现自己不是主节点并且请求队列不为空，则清空了请求队列，然后客户端发起重试，新的主节点收到了请求并成功提交，最后 Raft 的日志中就会有两条内容一样的日志，但是 Raft 并不关心两条日志的内容是否相同。所以这个去重需要在服务端处理，服务端从 applyCh 收到日志后，需要判断日志中对应的请求是否已被处理。造成这个问题的主要原因在于 Raft 处理日志的 commit 和 apply 之间存在时间差，而服务端只通过 applyCh 和 Raft 进行交互。

3B

引入快照之后，服务端从 applyCh 收到日志时需要判断是否是快照消息，如果是快照消息则执行快照逻辑。3B 整体难度低于 3A，快照的代码逻辑类似于 Lab 2 中的快照代码，不过要注意两点：

1. 快照会通过 RPC 发送，所以涉及快照的字段命名注意首字母大写
2. Raft 收到快照 RPC 后，再通过 applyCh 发送快照，但是服务端从 applyCh 中收到的快照消息不一定是最新的，即快照的最远日志索引有可能会落后于服务端已经应用到状态机的最远日志索引（因为 Raft 层收到的快照可能只覆盖了当前日志的一部分，而 Raft 往 applyCh 中发送已应用的日志或快照间没有顺序关系，所以对于服务端来说已经应用到状态机的日志索引可能会大于快照中的日志索引。）。如果快照不是最新的，服务端直接忽略即可，避免覆盖当前的状态机。如何知道当前快照不是最新的？服务端可以记录已提交到本地状态机的最大 ApplyMsg.CommandIndex，收到快照消息后将其和快照消息中的 ApplyMsg.SnapshotIndex 比较即可

参考

• 6.824 Lab 3: Fault-tolerant Key/Value Service

Students’ Guide to Raft 是 MIT 6.824: Distributed Systems 之前的助教写给学生看的实验生存指南。在 MIT 6.824 - Lab 2 (1): Students’ Guide to Raft 中介绍了关于 Lab 2 的部分，本文将继续介绍关于 Lab 3 的部分。

在 Lab 3 中，我们需要实现一个基于 Raft 的 Key-Value 数据库，本文描述了某些对实现可能有帮助的细节。

提交客户端操作

实现客户端请求时可能会先直接发一个请求给客户端所认为的主节点，然后对应的服务端等待 Raft 应用日志，接着服务端执行客户端的请求逻辑，最后再把结果返回给客户端。这种方式适合单客户端的系统，不过不适合多客户端并发的系统。在多客户端请求下，每个客户端请求都有可能修改系统状态，即使各 Raft 节点的日志保持一致，由于各客户端请求间可能相互交替执行，服务端本地状态可能和 Raft 节点的最新日志不一致，除非使用全局的锁隔离各客户端请求，不过系统会退化为串行程序。

文中建议将服务端当做状态机处理，每个客户端的请求本质上都是将状态机从一个状态转变为另一个状态。服务端中有一个专门的线程来处理客户端请求，该线程每次获取一个客户端请求，然后将其提交给 Raft，之后收到 Raft 应用日志的通知后，按顺序将客户端命令应用到服务端的本地状态机中，这里虽然看起来也是串行处理客户端请求，不过由于 Raft.Start() 方法会立即返回，当有大量请求时，Raft 在实现时会批量发送日志。这个线程是整个服务端中唯一能修改本地状态机的地方，所以服务端的 RPC 就简化为了向任务队列中提交任务，并且当 applyCh 接收到可以执行的日志时，将日志所对应的命令应用到本地状态机中，然后响应客户端。

不过，这也带来了一个问题：什么时候知道某个客户端请求执行完成了？这在一切正常的情况下非常简单，因为我们是按序将客户端请求提交给 Raft，所以最后从 applyCh 中出来的日志的顺序就是提交客户端请求的顺序。不过，当前客户端所通信的服务端有可能在中途不再是主节点，所以客户端所发送的日志有可能被丢弃，此时客户端需要能够知道发生了异常，然后尝试换一个服务端。

一个简单的方法是记录提交客户端请求时 Raft 返回的日志索引，然后从 applyCh 收到对应索引的日志时，判断该条日志是否对应最初的客户端请求（可以向 ApplyMsg.Command 添加额外的信息来标识是否是当初的请求）。如果不是同一条请求，则说明发生了异常。

识别重复请求

因为客户端异常重试的机制存在，所以服务端需要能识别出重复的客户端请求：例如某个客户端发送 APPEND 请求，当前服务端成功执行但是客户端没有收到响应，客户端会选择一个新的服务端发送请求，新的服务端需要确保 APPEND 请求不会被执行两次。因此，每个客户端请求需要一个唯一的标识，使得服务端能够识别已经执行的请求。另外，由于客户端会选择不同的服务端发送请求，各服务端需要对已执行的客户端请求达成共识。

有很多方法来为客户端请求生成唯一的标识符。一种简单并且相对有效的方法是先给每个客户端分配一个唯一的标识符，然后给每一个请求附带一个递增的序列号。如果某个客户端重新发送请求，则会复用之前的请求序列号。各服务端需要维护每个客户端最新的请求序列号，如果服务端发现客户端的请求序列号已处理，则直接忽略该请求。

难以定位的边界条件

如果按照上述的方式实现，有可能会遇到两个难以定位的问题。

重复出现的日志索引

Raft.Start() 会返回所添加的日志的索引，不过在实际实现时可能会认为这个索引不会重复返回，或者遇到重复的索引时会认为前一个相同索引的日志所对应的请求已经执行失败。不过实际上这两种看法都不正确，即使没有个任何一个服务端发生异常。

假设有 S1 到 S5 五个节点，一开始 S1 是主节点，并且没有日志，然后系统发生以下交互：

1. S1 收到两个客户端请求 C1 和 C2
2. S1 分别返回日志索引1和2给 C1 和 C2
3. S1 发送包含了 C1 和 C2 的 AppendEntries 请求给其他从节点，其中 S2 收到请求，其余节点均未收到
4. S3 成为候选节点
5. S1 和 S2 不会投票给 S3，但是 S4 和 S5 会，所以 S3 成为新的主节点
6. S3 收到新的客户端请求 C3
7. S3 调用 Start() 方法并返回日志索引1给 C3
8. S3 发送包含 C3 的 AppendEntries 请求给 S1，S1 丢弃 C1 和 C2 的日志后添加 C3
9. S3 在给其他从节点发送 AppendEntries 请求前发生异常
10. S1 成为候选节点，由于它的日志最新，所以再次成为主节点
11. S1 收到新的客户端请求 C4
12. S1 调用 Start() 方法并返回日志索引2给 C4（在之前的步骤中，日志索引2也返回给了 C2）
13. S1 在给其他从节点发送 AppendEntries 请求前发生异常，此时 S2 成为候选节点
14. S1 和 S3 不会投票给 S2，但是 S4 和 S5 会，所以 S2 成为新的主节点
15. S2 收到新的客户端请求 C5
16. S2 调用 Start() 方法并返回日志索引3给 C5
17. S2 成功将 AppendEntries 请求发送给其他所有从节点，在后续的心跳中，leaderCommit = 3

最终 S2 的日志为 [C1, C2, C5]，此时所有节点在索引位置2处的日志为 C2，这就为开头的两个观点提供了反例：Start() 方法可能返回重复的日志索引，以及遇到重复的索引时不代表前一个相同索引的日志所对应的请求已经执行失败。

四方死锁

课程的另一个助教 Steven Allen 发现在实现 Lab 3 时很容易遇到一个四方死锁问题。

不管具体的 Raft 代码如何实现，一般来说都会有一个类似于 Raft.Start() 的方法来使得应用程序添加日志，以及很有可能有一个单独的线程将位于 [lastApplied + 1, commitIndex] 范围内的日志通过 apply() 方法发送给应用程序（Students’ Guide to Raft 这篇文章写于2016年，在最新的课程中 Raft 通过 applyCh 来发送日志）。这两个方法很可能都需要持有锁 a。而在应用程序中，很可能会在某个 RPC 中调用 Raft.Start() 方法，然后同样可能有个线程会等待 Raft 的日志应用通知，当这个线程收到通知后，就可以响应客户端。由于这两个方法需要通信（例如，RPC 方法需要知道什么时候客户端请求执行完成），所以很可能也都需要持有锁 b。

上述的方法用 Go 描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

func (a *App) RPC(args interface{}, reply interface{}) {
    // ...
    a.mutex.Lock()
    i := a.raft.Start(args)
    // update some data structure so that apply knows to poke us later
    a.mutex.Unlock()
    // wait for apply to poke us
    return
}

func (r *Raft) Start(cmd interface{}) int {
    r.mutex.Lock()
    // do things to start agreement on this new command
    // store index in the log where cmd was placed
    r.mutex.Unlock()
    return index
}

func (a *App) apply(index int, cmd interface{}) {
    a.mutex.Lock()
    switch cmd := cmd.(type) {
    case GetArgs:
        // do the get
	// see who was listening for this index
	// poke them all with the result of the operation
    // ...
    }
    a.mutex.Unlock()
}

func (r *Raft) AppendEntries(...) {
    // ...
    r.mutex.Lock()
    // ...
    for r.lastApplied < r.commitIndex {
      r.lastApplied++
      r.app.apply(r.lastApplied, r.log[r.lastApplied])
    }
    // ...
    r.mutex.Unlock()
}

假设此时系统处于以下状态：

• App.RPC 获取锁 a.mutex 然后调用 Raft.Start
• Raft.Start 正在等待锁 r.mutex
• Raft.AppendEntries 持有锁 r.mutex，然后调用 App.apply

此时就发生了死锁，因为：

• Raft.AppendEntries 在 App.apply 返回前无法释放锁 r.mutex
• App.apply 在获取锁 a.mutex 前无法返回
• a.mutex 在 App.RPC 返回前无法被释放
• App.RPC 在 Raft.Start 返回前无法返回
• Raft.Start 在获取锁 r.mutex 前无法返回
• Raft.Start 需要等待 Raft.AppendEntries 释放锁 r.mutex

有几种方法来避免死锁。其中最简单的就是在 App.RPC 中，调用 a.raft.Start 之后再尝试获取锁。不过这可能会带来个问题，在 a.raft.Start(args) 和 a.mutex.Lock() 执行之间可能触发 app.Apply，造成错失日志通知。所以另一种方法是从 Raft.AppendEntries 中分离出 r.app.apply，由一个单独的线程来调用 r.app.apply，这就保证了服务端不会错过日志的通知，同时又避免了死锁。

参考

• Students’ Guide to Raft

介绍

一个存储系统一般来说会实现一些接口使得客户端能够存储，获取，或者修改数据。文件系统和数据库系统是最广为人知的例子。对于文件系统来说，对单个文件的操作（读和写）是原子的；对于数据库系统来说，每个操作（事务）可能会访问多个对象，并且是可串行化的。

本文关注的存储系统介于文件系统和数据库系统之间。特别的，本文关注的存储系统，在这之后称之为存储服务，有以下功能：

• 存储对象
• 支持查询操作，能够返回单个对象的衍生数据
• 支持更新操作，能原子的基于单个对象之前的状态根据某些预编程的计算（可能是非确定性的）来修改对象的状态

文件系统的写操作是上述存储服务的更新操作的一个特例，而上述存储服务的更新操作又是数据库事务的一个特例。

越来越多的在线零售商（例如 Amazon.com），搜索引擎（例如 Google 和 FAST），以及很多信息密集型服务通过将大型存储系统使用网络互联来提供服务。相对于文件系统和数据库系统来说，存储系统对于这些应用来说是较为适合的方案，因为数据库系统成本和代价过大，而文件系统则缺少丰富的操作语义。

构建大型存储服务的一个挑战是如何伴随着异常和配置更改（异常组件能被检测到并被替换）的同时维持系统的高可用和高吞吐。

一致性保证对于存储服务来说同样很重要。即使不重要，如果有了强一致性的保证，则能简化基于存储服务的应用程序构建，强一致性保证了：

1. 对单个对象的读写操作会按照某个顺序执行
2. 读操作一定能读取到之前的更新操作的结果

强一致性保证经常被认为和高吞吐、高可用是冲突的。系统设计者一般不会牺牲系统的吞吐或者可用性，而是牺牲强一致性保证。The Google File System（GFS）就体现了这样的思想。实际上，大型存储服务的强一致性保证和高吞吐、高可用并不是冲突的。本文介绍的 chain replication 方式在对 fail-stop 类型异常容错的同时，能同时支持高吞吐，高可用和强一致性。

存储服务接口

客户端会向存储系统发起查询和更新操作的请求。虽然能做到每一个到达存储服务的请求都能保证被执行，不过在论文 End-to-end arguments in system design 中提到这样做意义不大。存储服务可以简单的只处理能到达的请求，并在请求完成时响应客户端，这样就不用区分对待请求丢失和响应丢失这两种情况：客户端可以在一段时间没有收到响应后重新发起请求。

本文描述了两种接口：

• query(objId, opts) 会返回 objId 对应的对象的衍生数据；opts 指定了需要返回对象中的哪部分数据。objId 所对应对象的值不会被修改。
• update(objId, newVal, opts) 的返回值取决于 opts，一般来说，返回值 V 会基于 objId 对应的对象的当前值和（或）新值 newVal 根据某些预编程的非确定性计算求得；V 会成为 objId 对应的对象的新值。

查询操作是幂等的，但是更新操作不一定幂等。当客户端重新发起某个非确定性的更新操作时，必须确保上一次的请求并没有被执行。例如，客户端在重新发起更新操作前可以先执行一个查询操作，来确认该对象的值是否已经被更新。

如果某个请求没有响应，那么并不能区分是因为客户端的请求在到达存储服务前丢失还是客户端的请求被存储服务所忽略。这样当存储服务经历短暂的异常而丢弃了客户端的请求时，客户端可以简单的重新发起请求，而无需对这一异常场景单独处理。当然出于客户端性能的考虑，会尽可能降低系统异常的频率和持续时间。

在链式复制（chain replication）模式下，系统异常的时间远小于移除一个异常的节点或者增加一个新节点的时间。所以，遇到系统异常，恢复和其他配置变更时，对客户端请求的影响能降低到最小。而其他大多数的副本管理协议（replica-management protocols）要么会阻塞某些操作，要么在异常后或者配置变更期间牺牲一致性保证。

通过客户端视角下对象的状态以及查询和更新操作下客户端状态的转换，本文定义了所描述的存储系统的功能。下图通过伪代码的方式描述了该存储系统的功能：

上图通过两个变量定义了 $objID$ 所对应对象的状态：$Hist_{objID}$ 表示 $objID$ 所对应对象已执行的更新操作，$Pending_{objID}$ 表示待处理的请求。

上图也同时列出了可能的状态转换。T1 声明了新到达的请求会被添加到 $Pending_{objID}$。T2 声明了 $Pending_{objID}$ 中的请求被系统忽略时会从 $Pending_{objID}$ 中移除，不过这种情况不会频繁发生。T3 展示了高层次的请求处理过程：首先请求 r 会从 $Pending_{objID}$ 中移除；然后查询操作会生成相应的响应，而更新操作在生成响应之外还会将请求 r 添加到 $Hist_{objID}$ 中。

链式复制协议

本文描述的服务器假定具有 fail-stop 特性：

• 每台服务器发生异常时会停机，而不是继续执行错误的状态转换
• 服务器的异常能够被系统检测

对于有 t 个副本的对象来说，可以容忍 t - 1 个副本异常而不影响可用性。所以存储对象的可用性就取决于所有持有该对象副本的服务器都发生了异常的概率。因此，本文假定最多有 t - 1 个服务器会同时发生异常。

如上图所示，在链式复制模式下，各节点以一条链的形式来复制对象。链中的第一个节点被称为头节点，最后一个节点被称为尾节点，系统以如下的方式处理请求：

• 生成响应：每个请求的响应都只由尾节点生成并发送给客户端。
• 查询处理：每个查询请求都只由尾节点处理，并根据 $objID$ 查询尾节点本地的数据。
• 更新处理：每个更新请求都交由头节点处理。首先头节点根据 $objID$ 更新本地的数据，然后将更新请求以 FIFO 的顺序交由后继节点处理，以此类推，一直传递到尾节点处理。

在上述流程下，系统能保证强一致性，因为查询操作只由尾节点处理，而直到尾节点处理更新操作前，该更新结果都不会暴露给客户端，一旦尾节点更新完成，则后续的查询操作就能读到最新的请求。另外，各节点间 FIFO 的请求传递顺序也保证了某个对象更新的全局顺序性。

因为查询操作只涉及单个节点，所以查询操作是一个轻量级的操作。对于更新操作来说，前 t - 1 个节点的更新操作和最后一个节点生成响应没有直接关联，属于冗余操作，不过也正是这种冗余操作提高了系统的容错性。

如果更新操作不是单纯的直接写入而是需要涉及一系列计算，则该计算只会在头节点计算一次，后续节点的更新可以直接复用头节点计算的结果然后直接写入。这也表明系统可以接受非确定性的更新请求，因为非确定性计算只会在头节点计算一次。

协议细节

客户端不会直接操作 $Hist_{objID}$ 和 $Pending_{objID}$，所以可以以适合的方式来实现它们。当使用链式复制来实现 Fugure 1 中的规范时：

• 使用 $Hist_{objID}^T$ 来表示 $Hist_{objID}$，表示尾节点所存储的 $Hist_{objID}$。
• $Pending_{objID}$ 表示链中任一节点收到但还未被尾节点处理的客户端请求集合。

根据规范描述的如何实现 $Hist_{objID}$ 和 $Pending_{objID}$（假设此时不会发生异常），可以发现唯一能影响 $Hist_{objID}$ 和 $Pending_{objID}$ 的系统状态转换为：

1. 链中的某个节点收到了来自客户端的请求（影响 $Pending_{objID}$）
2. 尾节点处理客户端请求（影响 $Hist_{objID}$），这里应该是处理更新请求

由于这里假设此时系统不会发生异常，所以上述两种情况已经能够覆盖 Fiture 1 中的状态转换。然后具体来看这两种情况：

• 链收到来自客户端的请求：客户端将请求发送给头节点（更新）或者尾节点（查询）。在请求未被尾节点处理前，请求 r 会被先添加到 $Pending_{objID}$ 中，并符合 T1 的转换。
• 尾节点处理请求：处理请求时会先从 $Pending_{objID}$ 中移除请求 r，也就是 T3 的第一步。尾节点处理完后会将请求 r 添加到 $Hist_{objID}$ 中，而在本文的定义下为 $Hist_{objID}^T$。

处理节点异常

如果发现链中某个节点异常（根据 fail-stop 的假设，所有该种类型的异常都能被监测到），则链需要更新配置来剔除异常的节点。针对此，需要引入一个主节点来处理：

• 监测节点异常
• 通知链中的每个节点在删除异常节点后的新链中的前继和后继节点
• 通知客户端新链中的头节点和尾节点

在本文接下来的内容中，本文假设主节点是个永远不会发生异常的单进程。这虽然简化了描述但显然不是一个现实的假设；在作者的原型实现中，主节点有多个副本，并使用 Paxos 协议来协调各节点，所以对外来说整个系统就有了一个不会发生异常的主节点。

主节点能监测三种类型的异常：

1. 头节点异常
2. 尾节点异常
3. 中间节点异常

这三种异常的处理方式取决于更新操作如何在链中传递。

记链的头节点为 H，则下一个节点为 H + 1，以此类推。再记尾节点为 T，定义下述关系表示节点 i 的 $Hist_{objID}^i$ 是节点 j 的 $Hist_{objID}^j$ 的前缀：

$$Hist_{objID}^i \preceq Hist_{objID}^j$$

因为更新操作以 FIFO 的顺序从一个节点传给下一个节点，所以每个节点收到的更新序列是前一个节点收到的更新序列的前缀。所以有：

• Update Propagation Invariant：对于满足 $i \leq j$ 的节点 i 和 j（即 i 在链中是 j 的前继节点），有 $Hist_{objID}^j \preceq Hist_{objID}^i$。

头节点异常

头节点异常时，系统会从链中移除头节点，并将头节点的下一个节点作为新的头节点。因为系统最多容忍 t - 1 个节点异常，所以必然存在一个新的头节点。

由于删除头节点属于系统转换，所以需要证明这等同于一个空操作或者满足 Figure 1 中的 T1，T2 和（或）T3。修改链中的节点可能会改变 $Pending_{objID}$ 的值，因为 $Pending_{objID}$ 表示链中任一节点收到但未被尾节点处理的请求，所以从链中删除头节点 H 会一并删除 $Pending_{objID}$ 中被 H 接收但还没有传递给下一个节点的请求。而从 $Pending_{objID}$ 中删除请求符合 Figure 1 中的 T2，所以从链中删除头节点 H 符合 Figure 1 中的规范。

尾节点异常

尾节点异常时，系统会从链中移除尾节点 $T$，并将尾节点的前一个节点 $T^-$ 作为新的尾节点。和前面描述的一样，因为系统最多容忍 t - 1 个节点异常，所以必然存在一个新的尾节点。

删除尾节点会同时影响 $Pending_{objID}$ 和 $Hist_{objID}$，不过也能满足 T3：因为 $Hist_{objID}^T \preceq Hist_{objID}^{T^-}$（根据 Update Propagation Invariant 可得，因为 $T^- \lt T$），对于新的尾节点来说，它未处理的请求相比于旧的尾节点少，所以 $Pending_{objID}$ 序列的大小会减少。另外，根据 T3 的要求，已完成的请求需要追加到 $Hist_{objID}$ 中，在更新了尾节点后，某些未被 $T$ 完成的请求可能已被 $T^-$ 完成，所以此时以 $Hist_{objID}^{T^-}$ 来表示 $Hist_{objID}$。

中间节点异常

中间节点 $S$ 异常时，系统会从链中移除节点 $S$。主节点会首先通知 $S$ 的后继节点 $S^+$ 和 $S$ 的前继节点 $S^-$，告诉它们新的前继和后继节点。不过这有可能会违反 Update Propagation Invariant，因为 $S$ 收到的某些请求可能还没有转发给 $S^+$（这些请求必然在任一 $S$ 节点前面的节点 i 的 $Hist_{objID}^i$ 中）。最适合将这些请求发送给 $S^+$ 的就是 $S^-$，不过需要些额外的协作。

记 $U$ 表示一个请求集合，$<_U$ 表示该集合中所有请求的顺序。如果下述条件满足，则认为请求序列 $\overline{\vphantom{M}r}$ 和 $(U, <_U)$ 一致：

1. $\overline{\vphantom{M}r}$ 中的所有请求都在 $U$ 中
2. $\overline{\vphantom{M}r}$ 中的所有请求以符合 $<_U$ 的顺序升序排序

最后，对于和 $(U, <_U)$ 一致的请求序列 $\overline{\vphantom{M}r}$ 和 $\overline{\vphantom{M}r^{'}}$，记 $\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}}$ 表示以出现在 $\overline{\vphantom{M}r}$ 中或者 $\overline{\vphantom{M}r^{'}}$ 中的请求组成的请求序列，所以 $\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}}$ 也和 $(U, <_U)$ 一致（所以 $\overline{\vphantom{M}r} \oplus \overline{\vphantom{M}r^{'}}$ 中的请求以符合 $<_U$ 的顺序升序排序）。

当节点 $S^-$ 的后继节点指向节点 $S^+$ 时，首先将 $Hist_{objID}^{S^-}$ 中存在但是可能没有发送给节点 $S^+$ 的请求通过 FIFO 通道发送给节点 $S^+$；只有当这些请求都发送给了节点 $S^+$ 之后，节点 $S^-$ 才能将新来的请求发送给节点 $S^+$。这样就保证了 Update Propagation Invariant。

每个节点 i 维护了一个已转发给后继节点但可能还没有被尾节点处理的请求列表，记 $Sent_i$。对 $Sent_i$ 的增删非常简单：每当节点 i 将某个请求 r 转发给后继节点时，就将 r 加入 $Sent_i$；当尾节点处理完某个请求 r 时，它就会给前继节点发送一个 ack(r) 请求，表示请求 r 已处理完毕。当前继节点收到 ack(r) 请求时，就将 r 从 $Sent_i$ 中移除，并同样给它的前继节点发送一个 ack(r) 请求。

如果尾节点收到了一个请求，那么这个请求必然被所有的前继节点收到，因此有：

• Inprocess Request Invariant：如果 $i \le j$，则 $Hist_{objID}^i = Hist_{objID}^j \oplus Sent_i$。

所以，当主节点通知节点 $S^-$ 新的后继节点是 $S^+$ 时，首先节点 $S^-$ 将 $Sent_{S^-}$ 中的请求发送给节点 $S^+$，而已经存在于 $Hist_{objID}^{S^+}$ 中的请求则无需发送，这就保证了 Update Propagation Invariant。

上图描述了中间节点发生异常时的流程。主节点发送消息1告诉节点 $S^+$ 新的前继节点，节点 $S^+$ 收到消息后发送消息2告知主节点已确认收到配置变更消息，同时也告知了主节点最后收到的更新消息序列号 sn；然后主节点发送消息3给节点 $S^-$ 新的后继节点以及节点 $S^+$ 最后收到的更新消息序列号 sn，节点 $S^-$ 就能计算出需要将哪些更新请求发送给节点 $S^+$；最后消息4就是节点 $S^-$ 发送给节点 $S^+$ 的更新请求。

扩展链

系统会将异常的节点从链中移除。不过链越短则能容忍的节点异常也就越少，最终由于节点数过少从而影响了对象存储的可用性。解决方法就是当链的长度减少到一定程度时，向链中增加新的节点。鉴于节点异常的概率不是很高，以及往链中添加一个节点不需要太长时间，链的长度基本能维持在期望的 t 个节点的水平（因此 t - 1 个节点都发生了异常才会造成可用性问题）。

理论上可以往链的任意位置插入一个新节点。不过，往链的结尾插入一个新的节点 $T^+$ 是最简单的。对于一个新的尾节点 $T^+$，它的 $Sent_{T^+}$ 永远是个空列表，所以初始化 $Sent_{T^+}$ 很简单。剩下的就是要初始化 $Hist_{objID}^{T^+}$ 来满足 Update Propagation Invariant。

可以让当前的尾节点 $T$ 发送自己的 $Hist_{objID}^T$ 给节点 $T^+$ 来完成 $Hist_{objID}^{T^+}$ 的初始化。这个过程（如果数据太大可能会需要一段时间）可以和节点 $T$ 处理来自客户端的查询请求和来自前继节点的更新请求并行执行，只要每一个更新请求都追加到列表 $Sent_T$ 中。因为整个过程中满足 $Hist_{objID}^{T^+} \preceq Hist_{objID}^T$，所以也满足 Update Propagation Invariant。因此，只要满足 $Hist_{objID}^T = Hist_{objID}^{T^+} \oplus Sent_T$，则也满足 Inprocess Request Invariant，节点 $T^+$ 就可以成为新的尾节点：

• 节点 $T$ 被通知不再是尾节点。节点 $T$ 就可以丢弃来自客户端的查询请求，不过更合适的策略是将这些查询请求转发给新的尾节点 $T^+$。
• 节点 $T$ 将 $Sent_T$ 中的请求按序发送给节点 $T^+$。
• 主节点被通知新的尾节点是节点 $T^+$。
• 所有客户端被通知新的查询请求需要发送给节点 $T^+$。

主从复制协议

链式复制也是主从复制协议的一种，而主从复制协议本身也是复制状态机的一种。在主从复制协议下，系统会指定一个节点为主节点，并且：

• 主节点强制按序执行客户端请求（因此保证了强一致性）
• 主节点按序将客户端请求或结果更新发送给从节点
• 主节点会等待所有非异常从节点的请求确认
• 主节点收到从节点的请求确认后，再响应客户端

如果主节点发生异常，某个从节点会被提升为主节点。

在链式复制模式下，保证请求的顺序性的主节点的角色由两个节点承担。头节点负责处理更新请求，尾节点负责处理查询请求。这种分工一方面拆分了任务，另一方面降低了处理查询请求的延迟和负载，因为只会有一个节点处理查询请求（对单个对象来说），而且这个查询请求不会依赖链中的其他操作。而在主从复制模式下，主节点必须先收到从节点之前更新请求的确认，才能响应客户端的查询请求。

不管是链式复制还是主从复制，更新请求都需要发送给所有的节点，否则副本间可能会出现数据不一致。链式复制以串行的方式分发更新请求，相比于主从复制的并行更新有着更高的延迟。在并行更新下，整个过程的时间就取决于最慢的从节点更新完成的时间；在串行更新下，整个过程的时间等同于所有节点更新完成的时间之和。

当系统发生异常时，其中一个关注的点是客户端感知到的系统异常会持续多久，在这期间系统检测到了异常并需要重新调整集群配置；另一个关注点是由于节点异常所带来的延迟增长。

当某个节点发生异常到这个异常被监测到的时间是主要耗时的地方，不过这个时间对于链式复制和主从复制来说都是一样的。所以，剩下的就是要比较两种方式下异常恢复所需要的时间；相比于 CPU 计算延迟，消息延迟在异常恢复时间中被认为是占据主导地位。

对于链式复制，有三种异常需要考虑：头节点异常，中间节点异常，尾节点异常：

• 头节点异常：客户端的查询请求不受影响。更新请求暂不可用，整体恢复时间受限于两个消息的处理，一个是主节点广播通知新的头节点和它的后继节点；二是主节点广播通知客户端新的头节点。
• 中间节点异常：客户端的查询请求不受影响。更新请求可能会延迟不过不会丢失，异常节点后的节点还能正常处理已收到的更新请求，而异常节点前的更新请求可能会延迟。整个过程的延迟取决于 Figure 3 中的四个消息的处理时间。
• 尾节点异常：客户端的查询和更新请求都不可用。整个过程的延迟取决于两个消息的处理，一个是主节点通知新的尾节点，另一个是主节点通知所有客户端新的尾节点。

在主从复制模式下，需要考虑两种异常：主节点异常和从节点异常。查询请求和更新请求需要处理的情况都一样：

• 主节点异常：整个过程的延迟取决于5个消息的处理。系统监测到主节点发生异常，然后广播通知所有的从节点，要求各从节点返回已处理的更新请求数量并告知从节点暂停处理请求。每个从节点发送响应给系统。系统收到所有的响应后，选举一个新的主节点，并将主节点的信息广播给所有的从节点。只有处理了最多数量的更新请求的从节点才有可能被选为主节点，之后新的主节点需要给其他从节点补发缺失的更新请求。最后，系统再通知所有客户端新的主节点信息。
• 从节点异常：客户端的查询请求不受影响，只要当前没有进行中的更新请求。如果有进行中的更新请求，则整个过程的延迟取决于一个消息的处理，系统需要通知主节点某个从节点异常，主节点就知道无须等待这个异常的节点对更新请求的确认。

所以异常情况下，链式复制的最差情况（尾节点异常）不会比主从复制的最差情况（主节点异常）还差；而链式复制的最好情况（中间节点异常）则好于主从复制的最好情况（从节点异常）。如果系统异常时的持续时间是设计存储服务的首要设计目标，那么需要结合请求的类型（查询请求多还是更新请求多）以及不同系统异常发生的概率来决定选择链式复制还是主从复制。

参考

• Chain Replication for Supporting High Throughput and Availability

介绍

大型分布式系统需要各式各样的协同。配置就是其中一种最基础的形式，在其最简单的形式中，配置只是一系列供系统使用的参数，而对于更复杂的系统来说，配置还可以动态更新。群组成员关系和选主同样在分布式系统中很常见：通常各进程需要知道哪些进程还存活，以及哪些进程在负责统一管理。另外，分布式锁作为一种强大的协调原语能够对临界资源提供互斥访问保护。

一种实现协同的方式是为每一个不同的协同需求开发一个服务。例如，Amazon Simple Queue Service 专注于消息队列。同时也存在专门为了选主和配置所开发的服务。针对较强的原语开发的服务能够用于实现较弱一级的原语。例如，Chubby 是一个强同步性保证的锁服务。则可以借助锁来实现选主，群组成员关系等服务。

相较于在服务端实现特定的协同原语，ZooKeeper 的作者选择暴露某些 API 来让应用开发者自行实现需要的原语。这种设计选择需要实现一个协同内核（coordination kernel）使得新原语的开发不需要修改核心服务端代码。这种方式能够适配应用程序对不同协同形式的需求，而不是让开发者受限于某几个固定的原语。

在设计 ZooKeeper 的 API 时，设计者移除了阻塞原语，例如锁。一个协同服务的阻塞原语会导致某些问题，缓慢或出错的客户端会拖慢快速的客户端的性能。如果服务处理请求时需要依赖响应以及负责客户端的异常检测，那么服务的实现会变得更为复杂。因此，ZooKeeper 实现了一套 API 能够操作以类似文件系统的方式组织的无等待（wait-free）对象。实际上，ZooKeeper 的 API 类似于其他任何的文件系统，以及和去除了加锁（lock），打开（open），关闭（close）这些方法的 Chubby 类似。实现了无等待对象的 ZooKeeper 显著有别于其他基于阻塞原语（例如锁）的系统。

虽然无等待这一特性对于性能和容错很重要，但是对于协同来说来不够。ZooKeeper 还需要对各操作提供其他保证。对客户端 FIFO 的操作保证和线性化写入的保证确保了服务的高效实现，同时也能够满足应用程序实现自定义协同原语的需求。实际上，利用 ZooKeeper 的 API 可以实现任意节点数量的共识算法。

ZooKeeper 服务通过服务器间的复制来实现高可用和性能。它的高性能使得大量客户端进程能通过协同内核来管理方方面面的协同需求。通过一种简单的管道架构来实现 ZooKeeper 使得服务在承受几百或上千的请求的同时依然保持着低延迟。这种管道方式天然的支持对同一个客户端的请求以 FIFO 的方式执行。对客户端请求的 FIFO 顺序执行的保证使得客户端能异步的提交请求。异步提交也使得客户端同一时间有多个操作。这个特性很有用，例如当某个客户端成为主节点后，它需要操作元数据然后更新。如果缺少了多操作同时进行的特性，那么这个主节点初始化的时间可能达到秒级的数量级而不是亚秒级。

为了满足写入的线性化保证，ZooKeeper 实现了一个基于主节点的原子广播协议，即 Zab。典型的 ZooKeeper 应用属于读密集型应用，所以需要保证读操作的扩展性。ZooKeeper 的读操作由当前服务器完成，不涉及和其他服务器的交互，也不会使用 Zab 来保证读取的顺序性。

在客户端缓存数据是提高读性能的重要手段。例如，客户端可以缓存当前主节点的信息而不是每次请求 ZooKeeper。ZooKeeper 同时提供了监听机制来协助客户端缓存数据而无需直接管理客户端的缓存。借助这个机制，客户端可以对某个数据进行更新监听，从而在数据更新时收到通知。而 Chubby 会直接管理客户端的缓存，它会阻塞某个数据的更新直到所有缓存了该数据的客户端都清除了缓存。在这个设计下，如果某个客户端运行缓慢或者出错，则会拖慢数据的更新。Chubby 使用租约来避免某个客户端永久的阻塞系统。不过，租约只是确保了运行缓慢或者出错的客户端对性能的影响的上限，而 ZooKeeper 的监听机制则是完全的避免了这个问题。

本文主要介绍了 ZooKeeper 的设计和实现。借助 ZooKeeper，我们可以实现应用程序所需要的所有协同原语，即使只有写入是线性化保证的。为了验证这个设计，本文介绍了如何使用 ZooKeeper 来实现某些协同原语。

本文的关键点如下：

• 协同内核（Coordination kernel）：本文提出了一种供分布式系统使用的无等待、宽松一致性保证的协同服务。特别的，本文描述了一种协同内核的设计和实现，并且已经在很多重要的应用程序中使用来实现各种各样的协同服务。
• 协同示例（Coordination recipes）：本文描述了如何使用 ZooKeeper 来实现高层次的协同原语，包括在分布式应用中经常用到的阻塞和强一致性的原语。
• 使用协同的经验（Experience with Coordination）：本文分享了使用 ZooKeeper 的方式以及评估了其性能。

ZooKeeper 服务

客户端通过 ZooKeeper 提供的客户端类库来向 ZooKeeper 提交请求。除了向客户端暴露 ZooKeeper 提供的 API 外，客户端类库还负责维护客户端和 ZooKeeper 服务器间的连接。

本节会首先从高层次来介绍 ZooKeeper 服务，然后再讨论客户端和 ZooKeeper 交互的 API。

术语：本文使用客户端（client）来表示使用 ZooKeeper 服务的一个用户；使用服务端（server）来表示 ZooKeeper 的服务提供者；使用 znode 来表示 ZooKeeper 的一个内存数据节点，这些数据节点以层次化的命名空间的形式所组织，即 data tree。同时，本文使用更新（update）和写入（write）来表示任何修改 data tree 状态的操作。客户端和 ZooKeeper 通过建立 session 进行连接，并且通过 session handle 发送请求。

服务概览

ZooKeeper 将数据抽象成数据节点（znodes）后供客户端访问，所有数据节点以层次化的命名空间进行组织。znodes 是客户端可通过 ZooKeeper 的 API 操作的数据对象。层次化的命名空间通常被用于文件系统。因为用户已经习惯了这种抽象，所以 ZooKeeper 很自然的以这种方式来管理数据，另外这也能更好的管理应用程序的元数据。ZooKeeper 使用和标准 UNIX 文件系统命名一样的方式来表示一个 znode。例如，A/B/C 表示 znode C 的路径，并且 C 的父节点是 B，B 的父节点是 A。每个 znode 都会保存数据，而且除了临时节点之外的所有节点都可以有子节点。

客户端可以创建两种类型的 znode：

• 常规（Regular）：客户端可以显式的创建和删除常规节点。
• 临时（Ephemeral）：客户端创建临时节点后，可以显式的删除，或者当客户端和 ZooKeeper 的 session 结束后（客户端主动断开连接或者由于异常失去连接）由系统自动删除。

另外，客户端在创建一个 znode 时可以设置一个顺序标记。设置了顺序标记所创建的节点会在节点名称后追加一个单调递增的序号。如果 n 是一个新的 znode，p 是 n 的父节点，那么 n 的序号一定不会比在 n 之前所创建的 p 的子节点的序号小。

ZooKeeper 实现了监听器使得客户端能及时的收到数据修改的通知而无需轮询。当客户端发起一个读操作并设置监听时，这个读操作会和普通的读操作一样正常返回，不过当数据更新时，系统能通知客户端。监听器在单次 session 内只会被触发一次，一旦监听器被触发或者 session 关闭，该监听器就会被注销。监听器被触发表示监听的数据发生了修改，但是不会告知被修改后的值。例如，如果一个客户端在 "/foo" 被修改了两次之前执行了 getData("/foo", true)，那么客户端会收到一次通知表示 "/foo" 指向的数据被修改了。一些 session 级别的事件，例如连接丢失，也能通过监听回调通知给客户端，那么客户端就会知道监听通知可能会延迟。

数据模型

ZooKeeper 的数据模型基本上等同于简化版 API 的文件系统，只能一次性读取或者写入全部数据；或者等同于是一个以层次结构组织键的键值表。层次结构的命名空间能够为不同的应用程序分配子命名空间，同时也方便为不同的子命名空间分配访问权限。同时 ZooKeeper 在客户端这层提供了文件夹的概念，能够用于构建高层次的原语。

和文件系统中的文件不同，znodes 的设计目的并不是为了通用数据存储。相反，znodes 是作为客户端应用程序的抽象，典型场景是用于保存协同目的的元数据。在下图中有两个子树，其中一个用于应用程序1（/app1），另一个用于应用程序2（/app2）。应用程序1对应的子树实现了一个简单的群组成员关系协议：每个客户端 p_i 在 /app1 下会创建一个 znode p_i，只要客户端还存活，对应的节点就会存在，那么，根据 /app1 下的节点数量就能知道当前应用程序有多少个存活的进程能提供服务。

虽然 znodes 的设计目的不是为了通用数据存储，不过 ZooKeeper 也允许客户端在 znode 中保存数据，例如分布式计算需要用到的元数据或者配置信息。例如，在一个基于选主的应用中，一个刚启动的应用程序节点需要知道当前的主节点是谁。为了实现这个目的，可以让当前主节点将主节点的信息写入到某个约定的 znode 路径中。此外，znode 本身也提供了时间戳和版本号这样的元数据，使得客户端能够监控 znodes 的数据变化，从而根据 znode 的数据版本进行数据更新。

会话

一个客户端连接到 ZooKeeper 时会初始化一个 session。每一个 session 伴随着一个超时时间。如果在一个超时时间之内 ZooKeeper 没有收到来自客户端的任何请求，那么 ZooKeeper 就会认为这个客户端发生了异常。客户端可以主动通过关闭 session handle 来结束一个 session 或者 ZooKeeper 监测到客户端发生异常而自动关闭 session。在一个 session 内，客户端所观察到的系统状态变化和其提交的操作一一顺序对应。在一个 session 内，如果当前客户端连接的 ZooKeeper 节点发生异常，ZooKeeper 客户端类库能无缝的将其连接到一台新的 ZooKeeper 节点上，从而在各节点间完成持久化。

客户端 API

ZooKeeper 提供了以下的核心 API：

• create(path, data, flags)：创建一个路径为 path 的 znode，并将数据 data[] 保存其中，然后返回新建的 znode 的名称。flags 用于指定 znode 的类型：常规节点，临时节点，以及设置顺序标记。
• delete(path, version)：如果指定路径 path 下的 znode 的版本号和 version 匹配，则删除该节点。
• exists(path, watch)：如果指定路径 path 下的 znode 存在则返回 true，否则返回 false。如果 watch 为 true，则当 znode 的数据发生变化时，客户端会收到通知。
• getData(path, watch)：获取指定路径 path 下的 znode 的数据和元数据，例如版本信息。watch 的功能和 exists() 中的 watch 的功能一致，只不过如果当前节点不存在，则 watch 不会生效。
• setData(path, data, version)：如果指定路径 path 下的 znode 的版本号和 version 匹配，则将数据 data[] 写入到该节点。
• getChildren(path, watch)：返回指定路径 path 下的 znode 的子节点的名称。
• sync(path)：阻塞等待直到在操作开始时所有进行中的更新操作都同步到了当前客户端所连接的服务端。path 参数当前未使用。

ZooKeeper 通过 API 为每个方法提供了同步和异步两个版本。当应用程序希望执行单一 ZooKeeper 操作而且没有其他并发任务要执行时，可以选择调用同步方法。而如果应用程序希望同时执行多个 ZooKeeper 操作以及有其他任务需要并发执行时，可以选择调用异步方法。ZooKeeper 客户端类库保证了异步方法的回调顺序和提交请求的顺序一致。

ZooKeeper 不直接通过 handles 来访问 znodes。每个客户端请求会带上所要操作的 znode 的全路径。这不仅简化了 API（没有 open() 或者 close() 方法），同时服务端也不需要维护额外的状态。

客户端对 ZooKeeper 每个更新操作都会带上一个期望的版本号，这就能实现按条件更新。如果当前 znode 的版本号和期望的版本号不一致，那么此次更新就会失败并返回版本不匹配错误。如果传入的版本号是-1，则表示不进行版本号校验。

ZooKeeper 的保证

ZooKeeper 有两个基本的顺序保证：

• 线性化写入（Linearizable writes）：所有对 ZooKeeper 的状态修改都会按序串行化执行。
• 先来先执行的客户端顺序（FIFO client order）：来自同一个客户端的所有请求会按照请求发送的顺序执行。

ZooKeeper 提出的线性化和 Herlihy 提出的线性化有所不同，ZooKeeper 的作者称之为 A-linearizability（asynchronous linearizability）。在 Herlihy 的线性化定义下，一个客户端只能有一个进行中的操作（一个客户端对应一个线程）。而在 ZooKeeper 中，一个客户端允许有多个进行中的操作，那么从设计上可以选择对多个进行中的任务不保证执行顺序，或者保证 FIFO 顺序。ZooKeeper 选择了后者。如果一系列操作的结果适用于 linearizable 的对象，那么也同时适用于 A-linerizalbe 的对象，因为 A-linearizability 本身就满足线性化。因为只有更新操作需要满足 A-linerizalbe，所以 ZooKeeper 的读操作可以直接通过本地副本执行。进一步使得添加新的服务器时能实现对服务的线性扩展。

下面将通过一个场景示例来说明上述两个保证是如何交互的。某个系统需要选举一个主节点来分配任务给其他工作节点执行。每当新选举了一个主节点，它需要更新大量的配置参数并且当更新完成时通知其他的工作节点。这就带来了两个重要的需求：

• 当主节点在更新配置参数时，其他工作节点不能使用还未更新完成的配置参数。
• 如果主节点在配置参数更新完成前发生异常，其他工作节点也不能使用未更新完成的配置参数。

类似 Chubby 提供的分布式锁能满足第一个需求，但是不足以满足第二个需求，因为当其他工作节点获取锁读取配置参数时，它并不能知道配置参数是否已更新完成。在 ZooKeeper 中，主节点可以在某个约定的路径创建一个 ready 节点，只有在 ready 节点存在的情况下，其他工作节点才可以认为配置参数已更新完成。在更新配置参数前，主节点会先删除 ready 节点，然后更新配置参数，最后再创建 ready 节点。所有这些操作都可以以管道的方式进行并异步提交请求，从而使得配置参数能快速更新。虽然一次更新操作的耗时是2毫秒的数量级，但是如果主节点需要阻塞的依次更新5000个配置参数的话则一共需要10秒才能完成；通过异步提交更新，所有的请求能在一秒内完成。因为 ZooKeeper 的顺序性保证，如果某个工作节点发现 ready 节点存在，那么就说明配置参数也必然更新完成了，因为 ready 节点的创建晚于配置参数的更新。如果主节点在配置参数更新完成前发生异常，那么也就不会创建 ready 节点，其他工作节点就知道配置参数更新未完成。

不过上述方案还存在一个问题：如果某个工作节点此时看见 ready 节点存在，但是同时主节点删除了 ready 节点然后开始更新配置参数，那么工作节点就会读取到正在更新的配置参数。这个问题通过监听通知的顺序性保证来解决：如果客户端对某个节点 A 开启了监听，此时系统先对节点 A 进行了修改，然后对另一个节点 B 进行了修改，此时客户端发起了对节点 B 的读请求，那么 ZooKeeper 会保证客户端先收到节点 A 修改的异步通知。所以，如果客户端在判断 ready 节点是否存在时开启了监听，那么它就会在读取到修改中的配置参数前先收到 ready 节点修改的通知，从而可以中断配置参数的读取。

如果客户端之间还有除了 ZooKeeper 之外的通信方式也会引发另一个问题。例如，两个客户端 A 和 B 通过 ZooKeeper 共享配置，然后通过其他某种方式通信。如果 A 修改了 ZooKeeper 中的配置然后告诉 B，那么 B 收到通知后读取 ZooKeeper 就期望能获取到修改后的配置。不过如果 B 连接的 ZooKeeper 副本落后于主节点，那么 B 可能无法读取到最新的配置。而采用写入 ready 节点再读取的方式能保证 B 读取到最新的配置。ZooKeeper 提供了 sync 方法来更高效的解决这个问题：如果 sync 请求之后有一个读请求，则 ZooKeeper 会暂缓这个读请求。sync 会同步在这之前进行中的写请求，而无需等待当前所有的待写入操作完成。这个原语类似于 ISIS 中的 flush 原语。

ZooKeeper 同时也有存活性（liveness）和持久性（durability）的保证：只要 ZooKeeper 集群中过半数的机器存活，那么访问 ZooKeeper 服务就没有问题；如果 ZooKeeper 成功响应了某个修改请求，只要过半数的机器在异常后最终能恢复，那么不管经历了多少次系统异常这个更新都不会丢失。

原语示例

本节描述了如何利用 ZooKeeper 的 API 来构建更强大的原语。对于 ZooKeeper 来说，它并不知晓这些原语的存在，因为这些原语是由客户端通过 API 自行实现的。一些通用的原语例如群组成员关系和配置管理都是无等待原语。对于其他原语如 rendezvous，客户端则需要等待某个事件发生。虽然 ZooKeeper 是无等待服务，客户端也同样可以实现阻塞的原语。ZooKeeper 的顺序保证可以高效的审视系统的状态，而监听机制则实现了高效的等待。

配置管理（Configuration Management）

ZooKeeper 可以用于分布式系统中实现动态配置管理。在最简单的形式中，配置信息保存在一个 znode 中，例如 z_c。应用启动时会读取 z_c 的数据并设置监听状态。如果 z_c 的数据更新了，那么应用就会收到通知，然后就可以读取最新的配置，并继续设置监听状态。

在这个例子以及其他大多数使用监听器的例子中，监听器确保了应用能获取到最新的数据。例如，如果某个监听 z_c 的应用收到了 z_c 的修改通知，而在这个应用读取 z_c 之前，z_c 又被修改了3次，那么这个应用不会再收到通知。这并不会影响应用的行为，因为 ZooKeeper 的变更通知不会返回更新后的数据，应用需要再次读取才能获得节点最新的数据，只通知一次已经使得应用知道当前节点的数据已经过期，没有必要重复通知。

Rendezvous

有时候在分布式系统中并不能清晰的预知系统的最终配置是什么。例如，某个客户端可能会希望启动一个主节点和几个工作节点，不过由于节点的启动是由某个调度器执行，客户端并不能事先知道某些需要的信息，例如工作节点需要连接的主节点的地址和端口号。这个问题可以由客户端通过 ZooKeeper 创建一个 rendezvous 节点 z_r 来解决。客户端将 z_r 的全路径作为启动参数传给主节点和工作节点。当主节点启动后，它就将自己的地址和端口号写入到 z_r 中。当工作节点启动后，它就能从 z_r 中读取主节点的地址和端口号，并设置节点的监听状态。如果工作节点启动时主节点还未写入数据到 z_r，那么工作节点就会等待数据写入的通知。如果 z_r 是临时节点，那么创建 z_r 节点的客户端下线后，主节点和工作节点就能收到节点删除通知，并在完成资源清理后退出。

群组成员关系（Group Membership）

客户端可以利用临时节点的特性来实现群组成员关系管理。这里利用了可以通过监听临时节点来观测创建该节点的 session 状态的特性。首先创建一个节点 z_g 来表示群组。当群组中的某个进程启动时，它会在 z_g 下创建一个临时的子节点。如果每个进程都有唯一的命名或标识，那么这个命名或标识就可以作为 ZooKeeper 节点的名称；否则就可以在创建节点时设置 SEQUENTIAL 标记让 ZooKeeper 自动在节点名称后追加一个单调递增的数字，以保证名称的唯一性。各进程可以将进程相关的信息放到临时节点中，例如当前进程的地址和端口号。

当进程在节点 z_g 下创建完临时进程后就可以正常启动。它不需要做其他任何事。如果这个进程发生异常或者主动结束，那么它所创建的临时节点也会自动被删除。

各进程可以简单的通过查询 z_g 的所有子节点来获取当前群组成员的信息。如果某个进程想要监控群组成员的变化，那么它可以设置监听标记（通过 getChildren(path, watch) 方法设置 watch），然后在收到通知时更新群组信息。

简单锁（Simple Locks）

虽然 ZooKeeper 不是一个锁服务，但也可以用来实现锁。使用 ZooKeeper 的应用通常使用同步原语来适配其需求。本节通过使用 ZooKeeper 实现锁来展示可以通过 ZooKeeper 来实现各种各样的通用同步原语。

最简单的锁实现借助于 lock files。使用一个 znode 来表示一把锁。为了获取锁，客户端会尝试以 EPHEMERAL 标记创建一个临时节点。如果创建成功，那么这个客户端就获得了锁。否则，客户端就会去读取这个 znode 并设置监听状态，从而当这个临时节点被删除时能收到通知。当持有锁的客户端发生异常或者主动删除该节点时，则代表释放了锁。其他监听的客户端就会收到通知并尝试重新创建临时节点来获取锁。

虽然这种方式能实现锁，不过也存在几个问题。首先，它会造成羊群效应（herd effect）。如果有大量的客户端在等待释放锁，那么当锁被释放时，这些客户端都会被通知然后都会尝试获取锁，而实际上只会有一个客户端能获得锁。第二，这种方式只实现了互斥锁。下面两种原语展示了如何解决这两个问题。

没有羊群效应的简单锁（Simple Locks without Herd Effect）

首先定义节点 l 来实现锁。然后，将所有希望获取锁的客户端按照请求顺序排序，之后这些客户端就能按照请求的顺序获取锁。客户端希望获取锁时需要执行下面的操作：

1
2
3
4
5
6
7
8
9
10

Lock
1 n = create(l + "/lock-", EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2

Unlock
1 delete(n)

第一行 SEQUENTIAL 的标记用来将所有希望获取锁的客户端进行排序。每个客户端首先在节点 l 下创建一个临时顺序的子节点，然后获取 l 的所有子节点。之后在第三行判断自己创建的节点是否在所有子节点中有着最小的序号，如果是，则表示当前客户端获得了锁。如果不是，说明有其他序号更小的子节点存在，当前客户端需要排在这之后获取锁。然后客户端会尝试判断排在当前序号前的子节点是否存在，如果存在则设置监听状态等待前一个节点删除的通知，如果不存在，则继续回到第二行执行。每个客户端只监听排在自己前面的子节点避免了羊群效应，因为任何一个子节点删除的通知只会发给其中的一个客户端。每当客户端收到前面节点删除的通知时，需要再次获取 l 的所有子节点来判断自己是否是最小子节点（因为排在前面的子节点并不一定持有锁，可能是更前面的子节点持有锁。这里能否直接复用第一次请求 getChildren 的信息？实现起来会较麻烦些，因为需要挨个判断排在前面的子节点是否还存在，不如直接拉取一份最新的子节点信息）。

释放锁就是简单的删除对应的临时节点 n。而通过 EPHEMERAL 创建节点能保证进程异常时自动释放锁或者放弃对锁的获取请求。

这种锁实现有以下几个优势：

1. 一个节点的删除只会唤醒一个客户端，因为每个节点都只会被一个客户端监听，所以也不会有羊群效应。
2. 锁的获取和释放不依赖轮询或超时。
3. 使用这种方式创建锁使得可以通过查看 ZooKeeper 中的数据来监测锁竞争的数量，以及调试锁相关的问题。

读写锁（Read/Write Locks）

在前面锁的基础上稍加修改就能实现一个读写锁。释放锁的操作和前面的相同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Write Lock
1 n = create(l + "/write-", EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2

Read Lock
1 n = create(l + "/read-", EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if no write znodes lower than n in C, exit
4 p = write znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 3

写锁是互斥锁，这里的实现和前面的锁的实现一模一样，只是改变了创建节点的名称。而由于读锁之间没有互斥，所以获取读锁时只需要检查有没有序号更小的写锁即可。另外，读锁实现时最后的 goto 直接跳到了第三行而没有到第二行，这个在 ZooKeeper FAQ 中也提到可能是个笔误。这里看起来会有羊群效应，即存在大量的客户端会监听某个写锁，当写锁被删除时这些客户端都会收到通知，不过这本身就是预期的行为，因为读锁之间没有互斥，写锁释放后就应该唤醒所有等待中的读锁。

双屏障（Double Barrier）

双屏障用于客户端在某个计算开始和结束时进行同步，当指定数量的进程加入到屏障中后，就可以开始各自的计算任务，每个进程在整个计算任务结束后就可以离开屏障。MapReduce 任务就是一个典型示例，reduce 任务的开始需要所有 map 任务的完成，当所有 map 任务完成后，各进程就可以进入屏障开始 reduce 任务，而整个 MapRecuce 任务的完成依赖所有 reduce 任务的完成，当所有 reduce 任务完成后，各进程就可以离开屏障。客户端可以使用一个 znode 来表示屏障，记作 b。每个进程在 b 下创建一个子节点来表示进入屏障，通过删除子节点来表示离开屏障。如果 b 下的子节点的数量超过了指定值，那么就允许开始执行计算任务。当 b 下的子节点都被删除后，进程就可以离开屏障。这里同样使用监听机制来高效的等待进入屏障和离开屏障的事件发生。一旦 b 下的子节点数量满足了阈值，创建最后一个子节点的进程会同时创建一个 ready 子节点，那么通过监听 ready 子节点是否存在就可以判断是否可以开始计算。另一方面，论文中提到通过监听某个特定的子节点来判断是否可以离开屏障，这里略显模糊，这个特定的子节点是谁创建的？创建了这个子节点的进程什么时候可以删除这个子节点？ZooKeeper FAQ 中提出了另一种方案，每个进程各自监听 b 下的子节点，并且在任务完成后删除所创建的节点，如果各进程发现 b 下没有子节点了，就说明可以离开屏障，整个计算任务已结束。

ZooKeeper 的实现

ZooKeeper 通过将数据复制到每台服务器上来实现服务的高可用。ZooKeeper 处理的服务器异常针对的是服务器宕机，且这些异常的服务器可能之后会恢复。下图展示了 ZooKeeper 服务的主要组件。当 ZooKeeper 服务收到一个请求时，会对这个请求进行预处理（request processor），如果这个请求需要各服务器协同完成（例如写请求），则会通过一致性协议处理（一种 atomic broadcast 的实现），最终 ZooKeeper 会将修改提交到各服务器副本中。而对于读请求，服务端则直接从本地数据库中读取数据然后返回给客户端。

上图中的复制数据库是包含了整个数据树（data tree）的内存数据库。每个 znode 默认最多保存 1MB 数据，不过这个值可以根据需要通过配置修改。从可恢复性考虑，ZooKeeper 会高效的将更新写入到磁盘，并且将更新写入到内存数据库前会先强制将数据刷新到磁盘中。类似于 Chubby，ZooKeeper 也会将提交的操作写入到重放日志中，并且会周期性的对内存数据库生成快照。

每个 ZooKeeper 服务端都能对客户端提供服务。客户端只会连接一个服务端然后提交请求。在之前提到过，读请求会直接返回当前服务端本地的数据。而修改系统状态的请求、写请求则会交由一致性协议处理。

作为一致性协议的一部分，客户端的写请求会转发给单台服务器，称之为主节点（leader）。其他的 ZooKeeper 服务器被称之为从节点（followers），从节点会收到来自主节点的状态更新请求，并就状态更新达成一致。

请求处理器（Request Processor）

由于 ZooKeeper 的消息层是原子的，它保证各副本的状态不会和主节点产生分歧，虽然在任一时间点有可能某些副本会比其他副本多提交一些事务。和客户端发送的请求不同，ZooKeeper 中的事务是幂等的。当主节点收到一个写请求时，它会先计算出系统提交了这个写请求后的系统状态，然后将其转化为一个能达到该系统状态的事务。这里之所以要先计算出将来的状态是因为当前可能存在未提交的事务。例如，当前客户端正在进行一个 setData 的条件更新，请求中的版本号和被修改的 znode 的某个未来的版本号所匹配，ZooKeeper 会生成一个 setDataTXN 事务，这个事务包含了更新后的数据，更新后的版本号，以及更新的时间戳。而如果发生了异常，例如 setData 期望的版本号不匹配或者要更新的 znode 不存在，则会生成一个 errorTXN 错误。

原子广播（Atomic Broadcast）

所有更新 ZooKeeper 状态的请求都会被转发给主节点。主节点会执行写请求然后将写请求通过 Zab 协议广播给所有的从节点，Zab 是一种原子的广播协议。当主节点就更新达成一致后，会返回结果给客户端。Zab 默认使用的是简单的大多数同意协议，所以只有过半数的节点存活时 Zab 和 ZooKeeper 才能正常工作（例如，由 2f + 1 个节点组成的 ZooKeeper 系统可以最多容忍 f 台节点异常）。

为了提高系统的吞吐，ZooKeeper 会尽量保持请求处理管道满载运行。请求管道的不同部分可能有着几千个请求。因为系统状态变更依赖于之前的状态变更，所以 Zab 比常规的原子广播协议提供了更强的顺序保证。具体来说，Zab 保证了主节点广播的状态变更被分发执行的顺序和主节点发出广播的顺序一致，同时 Zab 会先将之前主节点的修改先发送给新的主节点，等到这些修改都执行完成后，新的主节点才能广播自己的修改。

另外还有些实现细节有利于高性能。ZooKeeper 使用 TCP 协议来发送消息，所以消息的有序性天然得到了保证，这同时也简化了实现。ZooKeeper 使用 Zab 协议选择的主节点作为集群的主节点，这就使得创建事务的节点同时也能发起事务。ZooKeeper 使用日志来记录事务的发起，这同时也作为内存数据库的预写日志，从而避免了将消息写入到磁盘两次。

在正常情况下 Zab 协议能按序发送所有消息，且每条消息只发送一次，不过由于 Zab 不会持久化已发送的消息的 id，所以在宕机恢复时可能会重复发送消息。因为 ZooKeeper 的事务是原子的，所以只要消息依然能保证有序发送，重复发送就没有问题。实际上，ZooKeeper 会要求 Zab 再次发送至少上次快照开始后的所有已发送的消息。

复制数据库（Replicated Database）

每个副本在内存中都有一份 ZooKeeper 状态的拷贝。当 ZooKeeper 宕机重启后，它需要能恢复到宕机前的状态。如果重新发送所有已发送的消息来恢复状态则需要较长时间，尤其是当服务器已经运行了一段时间之后，所以 ZooKeeper 周期性的对系统状态建立快照，并且只重新发送快照之后的所有消息。ZooKeeper 的快照被称之为 fuzzy snapshots 因为执行快照时不会加锁；ZooKeeper 会对数据树进行深度优先搜索，并且能原子的读取每个 znode 的数据和元数据，然后将其写入到磁盘中。这种方式生成的快照有可能包含部分在生成快照期间执行的事务的结果，最终生成的快照可能不会和任一时间点的 ZooKeeper 状态一致。不过由于状态更新是原子的，ZooKeeper 可以在后续恢复阶段重新按序执行已提交的事务。

例如，当 ZooKeeper 开始执行快照时有两个节点 /foo 和 /goo，对应的节点值分别为 f1 和 g1，节点值的版本号都是1。此时，对系统状态的修改以 <transactionType, path, value, new-version> 的形式到达：

1
2
3

<SetDataTXN, /foo, f2, 2>
<SetDataTXN, /goo, g2, 2>
<SetDataTXN, /foo, f3, 3>

当系统执行了这些更新后，节点 /foo 的值变为 f3，对应版本号为3，而节点 /goo 的值变为 g2，对应版本号为2。不过，执行 fuzzy snapshot 后的快照中的节点 /foo 的值可能是 f3，而节点 /goo 的值可能是 g1，对应版本号分别为3和1，这并不是一个有效的 ZooKeeper 系统状态。如果服务器宕机后恢复，系统会先读取快照然后重新发送状态更新消息，由于消息执行的顺序性，最终系统的状态和宕机前的状态保存一致。

客户端-服务端交互（Client-Server Interactions）

当 ZooKeeper 处理了一个写请求时，它会给所有监听了该节点的客户端发送数据更新通知，并同时删除该节点的监听（因为监听只会触发一次）。服务端会按顺序处理写请求，而且同时不会并发的处理其他写请求或者读请求。这就保证了严格的监听通知顺序。不过服务端的监听通知是由各服务器自行负责，只有和当前服务器连接的客户端才会收到通知，其他客户端对同一节点的监听由其他服务器负责。

读请求由当前客户端所连接的服务端直接读取内存中的数据返回。每个读请求处理时会标记上一个 zxid，这个 zxid 对应当前服务端所知道的最新的事务。这个 zxid 定义了读写操作之间的相对顺序。通过直接读取内存中的数据返回的方式来处理读请求，ZooKeeper 能保证非常好的读性能，因为这不涉及任何磁盘 IO 或者其他一致性协议。这个设计是满足读密集型应用对性能要求的关键点。

直接从本地内存读取数据的一个缺点是不保证一定能读取到最新更新的数据，即可能返回过期的数据，即使当前节点的更新已经被 ZooKeeper 所提交，因为只要过半数的节点已完成数据更新就可以认为本次数据已提交，而当前节点可能还没有执行更新。对于必须保证读操作能读取到最新的数据的应用，ZooKeeper 提供了 sync 接口。sync 原语能异步执行，并且会由主节点将所有待写入的更新应用到当前副本中。如果希望读操作能读取到最新的数据，客户端需要在执行读操作前调用 sync 方法。ZooKeeper 对客户端操作的 FIFO 执行顺序保证以及 sync 写操作的全局顺序保证使得读操作在执行读时 sync 发起之前的所有写操作都已经应用到了当前服务器中。在 ZooKeeper 的实现中，执行 sync 操作时不需要原子广播协议，因为使用了基于主节点的算法，只需要将 sync 请求放在主节点和当前节点的请求队列的末尾即可。这种方式能正确工作的前提是当前的主节点依然是主节点。如果当前主节点还有进行中的事务并提交，那么从节点就可以认为当前主节点依然是主节点。如果主节点的请求队列为空，那么主节点就会先提交一个空的事务然后再发起 sync 请求。这样当主节点处于低负载运行时，不需要生成额外的广播请求。在 ZooKeeper 的实现中，主节点会有一段过期时间，所以主节点自己就能知道什么时候不再是主节点，从而不再发起空事务。

ZooKeeper 的服务器会以 FIFO 的顺序来处理客户端请求。响应结果中会附带上 zxid。即使客户端和服务端之间没有请求，在常规的心跳返回中也会附带上当前服务端所知道的最新的 zxid。如果客户端连接上了一台新的服务器，那么这个服务器会保证自己所知道的 zxid 不会比客户端的 zxid 旧。如果客户端发送的 zxid 更新，那么服务端在将自己本地的数据更新到最新前不会和客户端再建立连接。而 ZooKeeper 能保证客户端能连接上一台数据版本满足 zxid 的服务端，因为客户端连接到的服务器必然是过半数有着最新系统状态的服务器之一。这个行为对保证持久性来说至关重要。

ZooKeeper 使用超时来检测客户端的 session 异常。如果在 session timeout 期间没有一台服务器收到来自客户端的请求，那么主节点就会认为发生了异常。如果客户端发送请求的频率足够高，那么就不需要发送其他消息来告诉主节点没有异常。否则，在非活跃期间客户端会发送心跳来维持连接。如果客户端和某台服务器无法发送请求或者心跳，那么客户端会和另外一台服务器建立连接。为了避免客户端的 session 过期，ZooKeeper 客户端类库会在 session 空闲了 s/3 毫秒后发送心跳，并且如果在 2s/3 毫秒内没有收到响应则会连接上另外一台服务器，这里的 s 指的是 session 的过期时间，以毫秒为单位。

参考

• ZooKeeper: Wait-free coordination for Internet-scale systems
• ZooKeeper FAQ

准备工作

日志

Debugging by Pretty Printing 中介绍了如何高效的打印日志，这有助于在实验时进行问题排查。

首先在 Go 侧需要封装一个日志打印函数 PrettyDebug（raft 目录下已经有了 Debug 变量，所以这里重命名为 PrettyDebug），在 raft 目录下新建一个 Go 文件，复制以下内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

package raft

import (
	"fmt"
	"log"
	"os"
	"strconv"
	"time"
)

// Retrieve the verbosity level from an environment variable
func getVerbosity() int {
	v := os.Getenv("VERBOSE")
	level := 0
	if v != "" {
		var err error
		level, err = strconv.Atoi(v)
		if err != nil {
			log.Fatalf("Invalid verbosity %v", v)
		}
	}
	return level
}

type logTopic string

const (
	dClient    logTopic = "CLNT"
	dCommit    logTopic = "CMIT"
	dDrop      logTopic = "DROP"
	dError     logTopic = "ERRO"
	dInfo      logTopic = "INFO"
	dLeader    logTopic = "LEAD"
	dCandidate logTopic = "CAND"
	dLog       logTopic = "LOG1"
	dLog2      logTopic = "LOG2"
	dPersist   logTopic = "PERS"
	dSnap      logTopic = "SNAP"
	dTerm      logTopic = "TERM"
	dTest      logTopic = "TEST"
	dTimer     logTopic = "TIMR"
	dTrace     logTopic = "TRCE"
	dVote      logTopic = "VOTE"
	dWarn      logTopic = "WARN"
)

var debugStart time.Time
var debugVerbosity int

func init() {
	debugVerbosity = getVerbosity()
	debugStart = time.Now()

	log.SetFlags(log.Flags() &^ (log.Ldate | log.Ltime))
}

func PrettyDebug(topic logTopic, format string, a ...interface{}) {
	if debugVerbosity >= 1 {
		t := time.Since(debugStart).Microseconds()
		t /= 100
		prefix := fmt.Sprintf("%06d %v ", t, string(topic))
		format = prefix + format
		log.Printf(format, a...)
	}
}

PrettyDebug 会通过环境变量 VERBOSE 来决定是否打印日志，该方法接受三个参数，第一个是日志主题用于对日志分组，后两个参数则是传递给 log.Printf 进行格式化打印，使用方法如下：

1

PrettyDebug(dTimer, "S%d, apply log, log index=%v, log term=%v, log command=%v", rf.me, entry.Index, entry.Term, entry.Command)

日志信息中的 S%d 是关键，它表示当前节点的编号，如 S0，S1，按照这个模式打印日志，在后续日志处理时能将日志按照节点分组。

然后，就可以通过 VERBOSE=1 go test -run TestFigure82C 来进行测试（这里的 TestFigure82C 可以换成其他的测试用例）：

不过所有日志都混到了一起，不好区分，作者因此提供了一个 Python 脚本 dslogs 来美化日志。这个脚本用到了 typer 和 rich 两个库，可以通过 pip 全局安装。接着再执行测试 VERBOSE=1 go test -run TestFigure82C | pipenv run python dslogs.py（这里使用了 pipenv 来安装依赖和运行脚本，不使用 pipenv 的可以按照作者的方式执行），美化后的日志根据主题着色后有了更强的区分度：

更进一步，还可以将日志按照节点分组展示 VERBOSE=1 go test -run TestFigure82C | pipenv run python dslogs.py -c 3：

在上图中，每一列表示一个节点的日志，而且自上而下随时间排序。

批量测试

做实验时有时候测试用例成功了，有时候失败了，每次手动测试不方便抓取日志，Debugging by Pretty Printing 的作者提供了另一个脚本 dstest 来进行批量测试，并且当测试失败时自动保存日志到文件中，从而可以使用上面提到的脚本 dslogs 来处理日志，dstest 这个脚本也依赖 typer 和 rich 这两个库。

然后通过 pipenv run python dstest.py 2A -n 10 -v 1 进行批量测试，这里 2A 可以换成其他的测试用例，-n 10 表示测试多少次，默认是10，-v 1 表示设置环境变量 VERBOSE，这样就能告诉 Go 打印日志：

脚本貌似有个小问题，当设置 -v x 参数时，会多一个名为 x 的测试任务，不过并不影响使用。

如果某次测试执行失败，则会保存相应的日志：

实现

2A

第一个实验是选主，关键有两点：随机化的 election timeout 和什么时候重置 election timeout。

当候选节点发出 RequestVote 请求后，应该在哪里判断是否获得了足够的选票？一种是在遍历完所有从节点发出 RequestVote 请求后，不过由于 RPC 的异步性，需要某种异步通知机制来通知当前的 goroutine。可以使用 sync.WaitGroup，事先计算好需要多少张选票才能成为主节点，发送 RPC 请求前调用 WaitGroup.Add(1)，每当获得一张选票后就调用 WaitGroup.Done()，当获得了足够的选票后当前 goroutine 就能被唤醒，不过由于当前节点不一定能成为主节点，所以存在无法被唤醒的可能。虽然可以把 WaitGroup 设置成所有 RPC 都响应后再唤醒，不过整个响应时间就受限于最慢的 RPC 请求，等待时间可能会超过一个 election timeout 周期。使用这种方式的一个很大的问题就是无法及时响应其他候选节点成为主节点的情况，因为当前候选节点还阻塞在 WaitGroup.Wait()。

所以可以将是否获得了足够的选票的判断放在每个 RequestVote 的响应中。先初始化需要的选票数量，每次获得选票后使用原子方法 atomic.AddInt32 对票数减1，当返回票数小于等于0时，说明当前候选节点成为了主节点。

2B

第二个实验需要实现日志复制。日志是 Raft 的核心部分，首先定义 LogEntry，包含三个字段，索引、任期、指令：

1
2
3
4
5

type LogEntry struct {
	Index   int
	Term    int
	Command interface{}
}

之所以这里需要 Index 是因为需要对日志压缩，所以不能使用 rf.log 的数组下标作为日志项的索引。

复制日志时，可以选择在调用 Start 方法时就发送 AppendEntries 请求，并且在响应中判断从节点的日志是否匹配来更新 prevLogIndex，然后继续发送 AppendEntries 请求。不过，这会造成两个问题。

第一个问题是冗余的 RPC 请求，假设客户端连续调用了10次 Start，那么根据当前的 prevLogIndex 计算，主节点所发送的 AppendEntries 请求中分别包含1条日志，2条日志，…，10条日志。然而这10次 AppendEntries 请求完全可以由第10条请求替代，而如果 prevLogIndex 不匹配，主从节点间来回协调的过程又会带来更多的 RPC 交互，最终有可能导致测试用例 TestCount2B 的失败。

第二个问题是测试用例会模拟出特别不稳定的网络，如果在 AppendEntries 的响应中接着递归异步调用 AppendEntries，由于 goroutine 都在等待网络可能会造成同时存在的 goroutine 数量过多，导致测试失败。

所以，可以选择不在 Start 中发送带日志的 AppendEntries 请求，而是在常规心跳中根据 nextIndex 计算是否要发送日志。

2C

第三个实验是持久化，虽然从代码编写角度来说是所有实验中最简单和直白的，但是测试用例并不会比其他实验简单。特别是 TestFigure8Unreliable2C，容易在指定时间内无法提交某条日志，一方面是可以批量发送日志而不是逐条发送，另一方面是及时识别过期的 RPC 请求并丢弃，例如如果响应中的任期小于当前任期则可以直接忽略该响应，因为从节点收到请求时会更新任期（如果从节点的任期比主节点的小），并将更新后的任期放到响应中，所以在当前任期下主节点收到的响应中的任期必然等于当前任期，如果收到了小于当前任期的响应，必然是过期的响应。

2D

由于执行快照后会对日志压缩，所以 LogEntry.Index 和 rf.log 的数组索引不再一一对应，有两点需要改动，一是使用 len(rf.log) 表示日志长度的地方需要改为 rf.log[len(rf.log)-1].Index；二是使用 rf.log[i] 来引用 LogEntry 的地方需要将 i 减去某个偏移量，这个偏移量可以使用 lastIncludedIndex，例如，从节点想要判断 args.PrevLogIndex 所指向的日志的任期是否和主节点相同，需要改为 rf.log[args.PrevLogIndex-rf.lastIncludedIndex].Term 访问，因此 rf.lastIncludedIndex 也需要持久化。

另外还遇到两个死锁问题。第一个死锁发生在应用已提交的日志，日志的应用会由一个单独的 goroutine 执行，它会遍历所有需要应用的日志，然后发送到 applyCh，并且在整个期间持有锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func (rf *Raft) applyLog(applyCh chan ApplyMsg) {
	for rf.killed() == false {
		rf.mu.Lock()

		if rf.lastApplied < rf.commitIndex {
			for i := rf.lastApplied + 1; i <= rf.commitIndex; i++ {
				logEntry := rf.log[i]
				applyMsg := ApplyMsg{
					CommandValid: true,
					Command:      logEntry.Command,
					CommandIndex: logEntry.Index,
				}

				applyCh <- applyMsg
			}

			rf.lastApplied = rf.commitIndex
		}

		rf.mu.Unlock()

		time.Sleep(time.Millisecond * 10)
	}
}

这种处理方式在之前的实验中没有问题，不过在 2D 中，客户端从 applyCh 中取出数据后，有一定概率会调用 Snapshot 方法，而实现 Snapshot 方法时会继续获取锁，从而造成死锁：

1
2
3
4
5
6
7
8
9
10
11

if (m.CommandIndex+1)%SnapShotInterval == 0 {
	w := new(bytes.Buffer)
	e := labgob.NewEncoder(w)
	e.Encode(m.CommandIndex)
	var xlog []interface{}
	for j := 0; j <= m.CommandIndex; j++ {
		xlog = append(xlog, cfg.logs[i][j])
	}
	e.Encode(xlog)
	rf.Snapshot(m.CommandIndex, w.Bytes())
}

这个问题也在 Raft Locking Advice 中提到，不建议在等待某个事件时持有锁。

第二个死锁发生在 InstallSnapshot，从节点收到快照后也会通过 applyCh 将快照发送给客户端，这里将 applyCh 作为 Raft 的一个字段使用，不过由于忘记赋值造成 InstallSnapshot 往一个空 channel 中发数据，造成始终阻塞，并导致死锁。

其他工具

go-deadlock

如果怀疑有死锁，可以使用 go-deadlock 检测，只需要将 Raft 中的 sync.Mutex 替换成 deadlock.Mutex 即可，如果某个 goroutine 在较长的一段时间后依然无法获取锁，那么就有可能发生了死锁，go-deadlock 会输出持有锁的 goroutine 和希望获取锁的 goroutine，而且也会输出持有锁的 goroutine 阻塞在哪个代码上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

POTENTIAL DEADLOCK:
Previous place where the lock was grabbed
goroutine 240 lock 0xc820160440
inmem.go:799 bttest.(*table).gc { t.mu.RLock() } <<<<<
inmem_test.go:125 bttest.TestConcurrentMutationsReadModifyAndGC.func5 { tbl.gc() }

Have been trying to lock it again for more than 40ms
goroutine 68 lock 0xc820160440
inmem.go:785 bttest.(*table).mutableRow { t.mu.Lock() } <<<<<
inmem.go:428 bttest.(*server).MutateRow { r := tbl.mutableRow(string(req.RowKey)) }
inmem_test.go:111 bttest.TestConcurrentMutationsReadModifyAndGC.func3 { s.MutateRow(ctx, req) }


Here is what goroutine 240 doing now
goroutine 240 [select]:
github.com/sasha-s/go-deadlock.lock(0xc82028ca10, 0x5189e0, 0xc82013a9b0)
        /Users/sasha/go/src/github.com/sasha-s/go-deadlock/deadlock.go:163 +0x1640
github.com/sasha-s/go-deadlock.(*Mutex).Lock(0xc82013a9b0)
        /Users/sasha/go/src/github.com/sasha-s/go-deadlock/deadlock.go:54 +0x86
google.golang.org/cloud/bigtable/bttest.(*table).gc(0xc820160440)
        /Users/sasha/go/src/google.golang.org/cloud/bigtable/bttest/inmem.go:814 +0x28d
google.golang.org/cloud/bigtable/bttest.TestConcurrentMutationsReadModifyAndGC.func5(0xc82015c760, 0xc820160440)      /Users/sasha/go/src/google.golang.org/cloud/bigtable/bttest/inmem_test.go:125 +0x48
created by google.golang.org/cloud/bigtable/bttest.TestConcurrentMutationsReadModifyAndGC
        /Users/sasha/go/src/google.golang.org/cloud/bigtable/bttest/inmem_test.go:126 +0xb6f

pprof

6.824 Lab 2: Raft 的每个实验都给出了参考的执行时间，如果发现某个实验的执行时间相差太大，可以使用 pprof 分析。这里以 CPU 耗时分析为例，首先在测试时增加 -cpuprofile cpu.prof 参数，其中 cpu.prof 是输出文件名：

1

go test -run TestInitialElection2A -cpuprofile cpu.prof

然后安装 pprof 并执行 pprof -top cpu.prof 分析：

参考

• 6.824 Lab 2: Raft
• Debugging by Pretty Printing
• pprof
• go-deadlock

Raft Locking Advice 提供了些关于如何在 Lab 2 中使用锁的建议。

规则1

只要有多个 goroutine 访问同一份数据，并且至少有一个 goroutine 会修改数据，那么就需要对数据加锁保护。建议在测试时开启 Go 的竞争检测（添加 -race 标记）来识别这类问题。

规则2

如果有多个数据需要作为一个整体被修改，为了避免其他的 goroutine 看到部分数据更新而造成不正确的行为，此时也需要加锁。例如：

1
2
3
4

rf.mu.Lock()
rf.currentTerm += 1
rf.state = Candidate
rf.mu.Unlock()

上面的代码需要同时更新 rf.currentTerm 和 rf.state，如果不加锁其他 goroutine 有可能看到更新后的任期，但是节点状态还未更新。同时，其他任何地方用到 rf.currentTerm 或者 rf.state 的地方也必须先持有锁，一是保证可见性，二是避免在多处同时修改 rf.currentTerm 或者 rf.state。

规则3

如果需要对某个数据做一系列读操作（或者读写混合），那么为了避免其他 goroutine 在中途修改数据，就需要对这一系列操作加锁。例如：

1
2
3
4
5

rf.mu.Lock()
if args.Term > rf.currentTerm {
    rf.currentTerm = args.Term
}
rf.mu.Unlock()

上面的代码是典型的 如果满足某个条件，那么就执行 xxx 场景。如果不加锁，可能其他的 goroutine 将 rf.currentTerm 更新后，当前 goroutine 会将 rf.currentTerm 重置为 args.Term，在 Raft 中有可能造成任期倒退。

在真实的 Raft 代码中加锁的粒度可能会更大，例如可能在整个 RPC handler 处理期间都持有锁。

规则4

不建议在等待某个事件时持有锁，例如从 channel 中读取数据，向 channel 发送数据，计时器等待，调用 time.Sleep()，或者发送一个 RPC 请求并等待响应结果。因为有可能造成死锁，文中举了两个节点互发 RPC 请求并希望获取对方持有的锁的例子，这是个典型的死锁场景。

又或者某个 goroutine 先持有锁，但是使用 time.Sleep 来等待某个条件发生，其他的 goroutine 由于无法获取锁从而使得等待的条件永远无法成立，这个时候应该用 sync.Cond：

1
2
3
4
5
6
7

mu.Lock()

while (!someCondition) {
    time.Sleep(time.Millisecond * 1000)
}

mu.Unlock()

规则5

当释放锁然后重新获取锁之后，某些释放锁之前成立的条件可能此时已经不成立。例如下面的候选节点获取选票的实现是不正确的：

1
2
3
4
5
6
7
8
9
10
11
12
13

rf.mu.Lock()
rf.currentTerm += 1
rf.state = Candidate
for <each peer> {
    go func() {
        rf.mu.Lock()
        args.Term = rf.currentTerm
        rf.mu.Unlock()
        Call("Raft.RequestVote", &args, ...)
        // handle the reply...
    } ()
}
rf.mu.Unlock()

在每个 goroutine 中，重新获取锁后拿到的任期可能已经不是当初的任期。这里需要将 goroutine 中的 rf.currentTerm 提取到循环之外作为一个变量，然后在 goroutine 中访问这个变量。另外，在 Call 执行完成后，也需要再次获取锁并检查 rf.currentTerm 或其他变量是否还满足条件，例如需要检查下当前的任期是否还是最初的任期，如果不是那说明又开启了一轮选主或者已经有其他节点成为了主节点。

参考

• Raft Locking Advice

Students’ Guide to Raft 是 MIT 6.824: Distributed Systems 之前的助教写给学生看的实验生存指南。

实现 Raft

论文中的 Figure 2 和 Figure 13 描述了实现 Raft 的主要接口，以及各节点需要维护的状态和响应接口时的行为逻辑，所以在做 Lab 2 之前需要先充分理解这部分的内容。文中的建议是必须严格落实图中的每一句话，而不是仅仅实现了功能，否则就有可能遇到奇怪的问题或不正确的系统行为。

文中举了三个例子。第一，每次收到 AppendEntries 或 RequestVote 请求就重置 election timeout，因为收到这两个请求说明存在主节点或者正在选主。不过，图中还有描述：

If election timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate.

重置 election timeout 有两个关键条件：AppendEntries 要求发送请求的主节点是当前任期的主节点；RequestVote 要求成功投出选票。

先看第一个条件，假设当前任期的主节点异常，此时还有一个之前任期的主节点存活在不断发送 AppendEntries 请求，假设此时某个从节点马上要进入选主状态，但由于收到了 AppendEntries 请求又没有校验任期就重置了 election timeout，造成无主状态时间延长。这个场景下如果过期的主节点不实现下面的逻辑杀伤力倍增：

If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower

如果不实现上面的逻辑，那么过期的主节点会一直是主节点，然后一直重置其他本来可以成为候选节点的从节点。

再来看第二个条件，假设当前任期的主节点异常，各从节点准备进入选主状态，此时一个不可能成为主节点的从节点先变成了候选节点（该节点的日志相对于其他任何一个从节点来说都不够新，即最后一条日志的任期不够大，或者任期相同但是日志条数不够多），RequestVote 永远不会成功，如果各从节点一收到 RequestVote 就重置 election timeout，就会造成始终没有主节点的情况。

第二个例子，从节点收到心跳 AppendEntries 后就直接返回 success = true 和重置 election timeout。重置 election timeout 的危害上面已经说过，充当心跳的 AppendEntries 是不带日志的请求，文中提到学生在实现时容易将心跳 AppendEntries 特殊对待，而不进行 prevLogIndex 和 prevLogTerm 的校验。从节点返回 true 时主节点就会认为从节点的日志和自己匹配，从而错误的认为某些日志已经复制到了从节点上，从而可以提交日志。不过看到这里可能会有疑问，为什么主节点会在心跳响应中提交日志？通过心跳更新 nextIndex 和 matchIndex 是合理的，如果过半数节点已复制的日志是之前任期的，论文中有描述这是不允许提交的；如果过半数节点已复制的日志是当前任期的，那么可能是之前带日志的 AppendEntries 请求中从节点实际已完成了日志的复制，但是主节点没有收到响应，所以在最新的心跳中提交日志。

引申开来，假设系统中此时 x = 1，有个客户端发送了 write x = 2 的请求，主节点成功将日志复制到了过半数的节点上，但是还没有响应客户端就异常了。系统重新选主后，此时有个客户端发送请求 read x，x 应该返回多少？应该是2，因为在 Raft 层面，一条日志是否已提交只取决于是否在当前任期内复制到了过半数的节点上，而不是取决于客户端是否收到响应，而只要日志提交了就可以被应用到状态机。类似的场景可以想象一下平时填了某个表单，提交时提示系统异常，但是刷新页面后表单信息已更新。

第三个例子，学生在实现 AppendEntries 时，可能将 prevLogIndex 之后的日志都替换为请求中的日志。同样的，图中也有描述：

If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it.

因为当前的 AppendEntries 可能是个过期的请求，假设请求中的日志只是当前从节点已提交的日志的某一段子集，那么如果从节点将 prevLogIndex 之后的日志都替换为请求中的日志就会丢失已提交的日志。

调试 Raft

调试是实验中最花时间的一个部分，文中列举了四个常见的问题：活锁，不正确或不完整的 RPC 实现，没有遵循论文中的 Rules for Servers 以及任期混淆。

活锁

出现活锁时，等同于各节点都在做无用功。选主是最容易出现活锁的场景，例如始终无法选出一个主节点，或者某个候选节点获得了足够的选票后，马上有另外一个节点发起选主，使得刚成为主节点的节点重新退回到从节点（某个节点成为主节点后，还没来得及发送心跳，刚投了票的某个节点 election timeout 到期，发起新的选主，由于它的任期加了1比当前的主节点的任期大，主节点收到 RequestVote 后发现自己的任期小，从而转为从节点）。

常见的原因有以下几种：

第一，没有严格按照 Figure 2 的要求重置 election timeout。重置 election timeout 仅限于几种情况：

1. 收到当前任期的主节点的 AppendEntries 请求（如果 AppendEntries 中的任期比自身的任期小，则忽略该请求）。
2. 开启一轮新的选主，这个属于 election timeout 到期，选主的同时需要重置一个新的随机值。
3. 在某轮选举中，将票投给了某个候选节点。

第二，没有按照 Fiture 2 的要求开启选主。特别的，如果当前节点是候选节点，但是 election timeout 到期了，那么需要开启新的一轮选主。

第三，没有遵循 Rules for Servers 的第二条：

If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)

例如，当前节点已投票，按照 Raft 的要求，一个从节点在一个任期内只能投票一次，此时又收到了一个 RequestVote 请求，请求中的任期大于自身的任期，那么就需要再次投票并更新自身的任期，避免新的候选节点拿不到足够的选票。

不正确的 RPC 实现

这里总结了学生们过往在实现 RPC 接口时容易犯错的点：

• 如果某一步要求 reply false，那么这说明需要立即回复 false 并返回，不要再执行后续的步骤。
• 如果收到了一条 AppendEntries 请求，但是请求中的 prevLogIndex 比当前日志的最后一条的索引还要大，也要返回 false，这也属于日志不匹配。
• 如前面描述，即使 AppendEntries 没有包含任何日志，接收方也需要校验 prevLogIndex 和 prevLogTerm。
• AppendEntries 中的第五步的 min 是有必要的，而且是和新日志中的最后一条日志的索引相比较，而不是当前日志的最后一条索引。
  • 首先来看 leaderCommit < index of last new entry 的情况，假设 S1 为主节点，日志为 [1, 2, 3, 4, 5]，leaderCommit 为3（索引按从1开始算），S2 为从节点，日志为 [1, 2]，那么 S1 需要将 [3, 4, 5] 发给 S2，S2 收到后 index of last new entry 是5，但是 commitIndex 只能更新到 3，也就是 leaderCommit，因为 [4, 5] 还没有提交。
  • 然后来看 leaderCommit > index of last new entry 的情况，乍看之下好像不可能，因为对于主节点来说，在添加一条新日志的那个时刻，leaderCommit 肯定小于新的日志的索引，复制日志到从节点时这个关系也不会变。这里只能想到的是，leaderCommit 被并发修改了，因为主节点不会删除日志，所以 index of last new entry 不会变，当主节点和从节点的日志不匹配时，主从节点需要来回的就 prevLogIndex 和 prevLogTerm 达成一致（或者单纯就是因为执行的慢），在这个期间，可能过半数的节点已经达成了完成日志复制，主节点就可以提交这条日志，并更新 leaderCommit，所以在原先的 AppendEntries 中，如果 leaderCommit 引用的是全局变量，而 entries[] 是固定的，就会造成 leaderCommit 的值比 entries[] 的最后一条日志的索引还要大，这个时候从节点的 commitIndex 就需要取 index of last new entry。文中举了个例子说明为什么这时候不能取 leaderCommit，假设 S1 为主节点，日志为 [1, 2, 3, 6]，leaderCommit 为3，S2 为从节点，日志为 [1, 2, 3, 4, 5]，那么 S1 需要将 [6] 发给 S2，注意这里 prevLogIndex 和 prevLogTerm 校验通过，而论文中只提到校验不通过时才删除从节点的日志，所以这里就不会删除 S2 的 [4, 5]，又假设此时 S1 通过其他节点的交互将日志成功提交到了 [1, 2, 3, 6, 7]，leaderCommit 变为了第5个位置，S2 收到的 AppendEntries 中 leaderCommit = 5，entries = [6]，如果按照最新的 leaderCommit 更新就会造成把 S2 日志中的5归为已提交。
• 严格按照论文5.4节的描述来比较两个节点的日志哪个较新，不要只比较日志的长度。

未遵循 Rules for Servers

• 如果 commitIndex > lastApplied，说明可以应用新的日志到状态机中。应用到状态机的顺序必须严格按照日志的顺序，可以由一个单独的线程顺序执行，也可以由多个线程并行执行，但各线程间必须确保不互相干扰，避免执行覆盖，对于同一个变量的不同写请求，多线程间必须按照日志的顺序写入。
• 确保周期性的检查 commitIndex > lastApplied 或者在 commitIndex 更新后检查（在 matchIndex 更新后）。这里并没有太明白这个问题，作者举了个例子，假设现在主节点发出了 AppendEntries 请求并同时检查 commitIndex，如果这条日志被过半数的节点复制了，那么需要等到主节点再添加一条新日志后才能应用上一条日志到状态机。不过根据这个例子也没有看出两者的关联，因为如果采用单线程顺序应用日志到状态机的方式，如果 commitIndex > lastApplied 不满足，线程可以先睡眠然后再尝试，除此以外没有依赖其他条件。
• 假设主节点发出 AppendEntries 请求然后被拒绝了，如果不是因为日志不一致被拒绝，那么这个主节点就必须马上转为从节点，且不能更新 nextIndex，因为这说明当前主节点的任期小于从节点。如果错误的更新了 nextIndex，而这个主节点在转为从节点后又当选了主节点，就会造成 nextIndex 和从节点永远不会匹配的情况（相当于错位了一格）。
• 如果主节点发现某条过去任期的日志被大多数的节点复制了，但是自身的 commitIndex 却小于这条日志的索引，此时主节点也不能够更新 commitIndex，这个就是论文中 Figure 8 描述的问题，提交一条之前任期的日志存在被新一轮的主节点覆盖的风险。所以提交日之前需要判断 log[N].term == currentTerm。

有一个常见的困惑是 nextIndex 和 matchIndex 的区别。你可能会观察到 matchIndex = nextIndex - 1，然后用 nextIndex 来替代 matchIndex，然而这是有风险的。举一个很明显的反例，假设某个节点被选为主节点，此时收到一个客户端请求并添加了一条日志，那么它发给从节点的 nextIndex 就是最后一条日志的下一条，而 matchIndex 显然不是 nextIndex - 1（新添加的日志的索引）。

任期混淆

任期混淆指的是节点收到了来自之前任期的 RPC 请求。Figure 2 清晰的描述了收到过期任期的请求应该怎么做，但是并没有说明收到过期任期的响应应该怎么做。一个简单的做法就是比较响应中的任期和当前的任期，如果相等则执行相应的逻辑，如果当前任期小则转为从节点（只有主节点、候选节点才能发请求，才有收到响应的可能），如果当前任期大则不处理。

还有一个相关但不同的问题，假设主节点收到 AppendEntries 响应后设置 matchIndex = nextIndex - 1 或 matchIndex = len(log)，这都是不安全的，因为 nextIndex 和 len(log) 在这期间都有可能改变，正确的做法应该是使用原始请求中不变的参数，即 matchIndex = prevLogIndex + len(entries[])。

关于性能

实验中会要求实现两个关于性能方面的优化，一个是日志压缩，另一个是快速确认正确的 prevLogIndex。

关于日志压缩需要注意几点：

• 当执行快照时，需要确保快照中的状态和指定日志中的索引是严格对应的，即快照不能落后于日志，也不能超前。
• 论文中并没有描述当节点异常然后恢复后应该如何处理快照。论文中要求创建完快照后，需要删除快照所对应的日志，而系统可能在删除日志前异常，那么系统恢复后会根据快照和日志进行重放。文中说系统可能会重放已经在快照中的日志，这里有点疑问，因为快照中包含了 lastIncludedIndex 和 lastIncludedTerm，和当前日志进行对比就能知道哪些日志已经在快照中了，从而可以跳过。

论文中并没有详细描述如何快速确认正确的 prevLogIndex，这部分的逻辑可以参考 6.824 2022 Lecture 7: Raft (2) 或者文中的建议：

• 如果从节点在 prevLogIndex 处没有日志，说明从节点的日志较短，则返回 conflictIndex = len(log) 以及 conflictTerm = None。
• 如果从节点在 prevLogIndex 处有日志，但是日志对应的任期不匹配，那么返回 conflictTerm = log[prevLogIndex].Term，然后找到属于 conflictTerm 的第一条日志的索引。
• 主节点收到 conflictIndex/conflictTerm 后，首先在日志中搜索 conflictTerm，如果找到有日志属于 conflictTerm，那么 nextIndex 需要更新为主节点中属于 conflictTerm 的最后一条日志的索引加1。
• 如果主节点没有找到属于 conflictTerm 的日志，那么更新 nextIndex 为 conflictIndex。

其中一个不完善的实现是只考虑 conflictIndex 而忽略了 conflictTerm，这样会简化实现，不过主从节点交互的次数会变多，因为如果考虑了 conflictTerm，那么一次性能跳过的日志会更多。

最后一部分的 Applications on top of Raft 属于 Lab 3 的内容，即基于 Raft 构建应用，在 Lab 2 中暂不描述。

参考

• Students’ Guide to Raft

介绍

共识算法使得一批机器作为一个整体对外提供服务，同时当部分机器异常时系统仍能保证可用性。因此，共识算法在构建可靠的大型软件系统中扮演着至关重要的角色。而在所有的共识算法中，Paxos 占据了主导的地位：大部分共识算法的实现都是基于 Paxos 或者受其影响，并且它也成为了教授学生们共识算法的第一选择。

然而，尽管人们为了让 Paxos 易于理解做了大量的尝试，Paxos 依然非常难以理解。另外，如果要将 Paxos 应用到实际的系统中需要涉及复杂的修改。因此，系统开发人员和学生都受困于 Paxos。

在受困于 Paxos 之后，Raft 的作者开始尝试设计一种新的共识算法，从而能够为系统构建和教学提供一个更好的基础。和常见的共识算法的设计目标不同，这个新的共识算法的首要设计目标是可理解性：能否为实际的系统设计一个远比 Paxos 易于理解的共识算法？另外，对于系统构建者来说这个算法需要能易于实现。该算法仅仅是正确的还不够，重要的是能显而易见的被人们理解为什么是正确的。

这个新的共识算法就是 Raft。在设计 Raft 时为了提高可理解性作者借助了某些特定的手段，包括解耦（Raft 分离了选主，日志复制和安全性的处理）和减少了状态机的状态（相比于 Paxos，Raft 减少了非确定性的状态以及各服务器间不一致的情况）。根据两所大学共43名学生的调查反馈，Raft 明显比 Paxos 易于理解：在学习了两种共识算法后，有33名学生在回答关于 Raft 的问题时比回答关于 Paxos 的问题表现的更好。

Raft 和现今已有的共识算法有很多相之处（特别是 Oki 和 Liskov 的 Viewstamped Replication），不过也有几个方面的创新：

• 强主节点（Strong leader）：相比于其他共识算法，Raft 使用了更严格的主节点要求。例如，日志只会从主节点发往其他服务器。这简化了日志复制的管理，同时也使得 Raft 更易于理解。
• 选主（Leader election）：Raft 使用随机计时器来进行选主（后面会提到主节点和各从节点间会维持一个心跳，如果在一段时间内从节点没有收到心跳，那么就可以认为主节点异常，从而重新发起选主，对于每个从节点来说，这个等待的时间不是固定的，而是随机的）。因为心跳本身在共识算法中是一个必不可少的技术，使用随机计时器仅仅在这之上增加了一些额外的机制，却能简单快速的解决选主冲突问题（例如有两个节点瓜分了存活着的节点的全部选票，却没有任何一个节点获得了超过半数的选票，需要重新选主）。
• 节点变更（Membership changes）：当集群中的节点需要变更时，Raft 使用 joint consensus 机制来保证在变更时新旧两套集群下过半数的节点同时属于两套集群。这就保证了整个集群在节点变更时依然正常对外提供服务。

Raft 的作者认为不管是出于教学还是实现目的，Raft 都优于 Paxos 和其他共识算法。它相比于其他共识算法更简单和易于理解；也完全覆盖了实现一个实际系统的需求；它也有了一些开源的实现并且已经被一些公司所使用；它的安全性也已被正式定义和证明；其性能也不输给其他共识算法。

复制状态机

谈论共识算法时一般离不开复制状态机（replicated state machines）。在这个模型下，集群中的每台机器上的状态机能产生有着相同状态的副本，并且在某些机器异常时整个系统依然能对外提供服务。复制状态机被用于解决分布式系统中的一系列容错问题。例如，对于 GFS、HDFS 和 RAMCloud 这样的单主节点的大型系统来说，一般会用一个独立的复制状态机来管理选主，以及存储某些配置信息，并且主节点发生异常时这些信息也不会丢失。复制状态机的应用包括 Chubby 和 ZooKeeper。

复制状态机一般通过复制日志来实现。在上图中，每台机器保存的日志中包含了一系列命令，这些命令会被状态机按顺序执行。每份日志中以相同的顺序保存着相同的命令，所以每台状态机能以相同的顺序执行这些命令。因为状态机是确定性的，所以最终所有状态机的状态和输出的结果都是相同的。

共识算法的任务就是要保证这些日志数据的一致性。服务器上的共识模块收到客户端的命令后会将其添加到本地日志中。然后它会和其他服务器上的共识模块通信来保证即使在某些服务器异常的情况下，各服务器也会以相同的顺序记录下所有的请求日志。当客户端命令被正确复制后，每台服务器上的状态机会以日志中的顺序执行这些命令，然后将结果返回给客户端。从整体上来说，所有的服务器对外组成了一个独立，高可用的状态机。

针对实际系统的共识算法来说一般有以下几个特性：

• 保证在所有非拜占庭情况下的正确性（永远不会返回一个错误的结果给客户端），这里的场景包括网络延迟，网络分区，网络包丢失、重复和重排序等等。
• 只要系统中过半数的服务器依然存活并且相互间以及和客户端间可以通信，整个系统对外来说依然是可用的。因此，一个由五台服务器组成的集群可以容忍任意两台服务器的异常。如果某台服务器停止响应则会被认为是异常，它可能之后会自动恢复并加载持久化存储上的状态然后重新加入到集群中。
• 不依赖时间来保证日志的一致性：错误的时钟和极大的消息延迟在最坏的情况下会造成可用性问题。
• 在一般情况下，当集群中过半数的服务器在一轮 RPC 请求中成功响应时，这次的客户端请求就被视为完成，剩下少数响应缓慢的服务器不会影响整个系统的性能。

Paxos 的问题

Leslie Lamport 的 Paxos 协议几乎成为了共识算法的代名词：它是在课堂上被教授的最多的协议，以及大部分的共识算法的实现都以此为出发点。Paxos 首先定义了一个协议能够对单一决策达成共识，例如复制某一条日志。这个被称之为 single-decree Paxos。然后，Paxos 能组合多个单一决策以达成对一系列决策的共识（multi-Paxos），例如一整个日志文件。Paxos 保证了安全性和存活性，同时支持集群中的节点变更。它的正确性已经被证明而且在常规使用中已足够高效。

不幸的是，Paxos 有两个重大的缺点。第一个缺点是 Paxos 非常难以理解。它的完整的解释是众所周知的晦涩难懂，只有少数人拼尽全力后才能正确理解。因此，人们尝试用通俗易懂的方式来解释 Paxos。不过这些尝试主要针对的是 single-decree Paxos，虽然也足够具有挑战性。根据 NSDI 2012 与会者的一项非正式调查显示，即使在经验老到的研究者中，也只有少数人能掌握 Paxos。Raft 的作者自身也受困于 Paxos，直到它们读了某些简化的 Paxos 的解释和实现了 Raft 之后才理解了 Paxos 的完整的协议，而这花了几乎一年的时间。

Raft 的作者认为 Paxos 的晦涩难懂来源于 Paxos 选择 single-decree 作为其协议的基础。single-decree Paxos 难以理解：它被分为两阶段但是又缺少简单直白的解释来单独理解每个阶段。鉴于此，人们也很难理解为什么整个 single-decree 协议是正确的。而由 single-decree Paxos 组合而来的 multi-Paxos 则更添加了额外的复杂性。Raft 的作者相信多决策共识的问题能够以更直白的方式拆解。

Paxos 的第二个问题是没有为构建实际的系统提供坚实的基础。其中一个原因是还没有一个被广泛认可的 multi-Paxos 算法。Lamport 的论文中主要描述的是 single-decree Paxos；他只是概括性的描述了 multi-Paxos，但是缺少很多细节。虽然人们有很多尝试来补充和优化 Paxos，但是它们相互之间以及和 Lamport 的描述都各有不同。虽然有些系统如 Chubby 实现了类似 Paxos 的算法，但是实现的算法细节并没有公开。

另外，Paxos 的架构对于实际系统的构建来说不够友好，这也是一个将 single-decree 分为两阶段后造成的后果。例如，没有必要独立的选择一些日志然后再将其合并为有序的日志，这只会增加复杂性。相比而言，设计一个以日志为中心的系统并且只允许按照指定的顺序来追加写日志会更简单和高效。另一方面，Paxos 的核心实现采用了对等点对点的方式（虽然它最终建议一种弱主节点的方式来作为一种性能优化的手段）。这种设计适合于单一决策共识的场景，不过很少有实际的系统采用这种方式。当需要对一系列决策达成共识时，首先选择一个领导者然后由领导者协调做决策会更简单和高效。

因此，实际的系统很少采用 Paxos 的方式。每一种实现都基于 Paxos，然后在实现时遇到了困难，接着就演变出了大不相同的架构。这既费时又容易出错，Paxos 的难以理解又加剧了这个问题。Paxos 的描述可能非常适合证明其正确性，不过实际系统的实现却大相径庭，Paxos 的证明也没有什么太大的帮助。来自 Chubby 的实现者的评论一针见血的指出了这个问题：

Paxos 的描述和现实世界的系统的实现间存在巨大的鸿沟…最终的系统将会构建在一个没有被证明的协议上。

鉴于以上的问题，Paxos 即没有为系统构建也没有为教学提供一个坚实的基础。考虑到共识算法在构建大型软件系统中的重要性，Raft 的作者决定尝试能否设计成比 Paxos 更优秀的共识算法，Raft 因此应运而生。

为可理解性设计

作者在设计 Raft 时有几个目标：必须为系统构建提供完整坚实的基础，从而能大大减少开发人员的设计工作；必须在任何场景下保证安全性以及在特定操作场景下保证可用性；大多数的操作必须高效。不过最重要也是最困难的是可理解性。它必须能让大部分的受众易于理解。另外，这个算法必须能让人形成直观的认识，系统构建者就可以在实现时进行必要的扩展。

在设计 Raft 时有很多方面需要在多种方案中做选择。在选择哪种方案时基于的是可理解性：解释每种方案难度有多大（例如，其内部状态有多复杂），读者完全理解这个方案需要付出多大的努力？

虽然做这样的分析有很大的主观性，作者使用了两方面的手段来解决这个问题。第一个手段是众所周知的问题分解：只要有可能，作者都会先将一个问题分解为一系列独立可解决，可解释，可相对的单独理解的子问题。例如，在 Raft 中选主，日志复制，安全性，集群节点变更被分解为独立的模块。

第二个手段是通过减少系统状态的数量来简化系统状态，这样就使得系统更具一致性并尽可能的消除非确定性。特别的，系统中的日志不允许有空洞，Raft 也限制了各节点间日志不一致的场景。虽然在大多数情况下会尽可能的消除非确定性，不过在某些场景下非确定性却更有助于理解。特别是随机化会带来非确定性，不过它能以相似的手段来处理所有可能的场景来降低系统状态的复杂性。Raft 使用随机化来简化了选主算法。

Raft 共识算法

Raft 是一种管理第二节中所描述的复制日志的算法，下面描述了该算法的关键特性：

• Election Safety：在任一任期内最多只有一个节点被选为主节点。
• Leader Append-Only：主节点永远不会覆盖或者删除某些日志项，它只会追加写新的日志项。
• Log Matching：如果两份日志在同一索引处的日志项对应相同的任期，那么双方在这个索引之前的日志项都相同。
• Leader Completeness：如果某个日志项在某个任期内被提交了，那么这条日志会出现在后续所有新任期下的主节点的日志中。
• State Machine Safety：如果某台服务器将某个索引位置的日志应用到了自身的状态机中，那么不会有任何一台服务器在相同索引位置应用了一条不同的日志到状态机中。

Raft 在实现共识时会先进行选主，然后完全交由主节点来管理日志的复制。主节点接收来自客户端的日志请求，然后将日志复制到其他从节点上，最后在合适的时机告诉各从节点将日志中的内容应用到自身的状态机中。使用主节点的方式简化了复制日志的管理。例如，主节点可自行决定在哪里插入新的日志而不用和其他服务器交互，其他数据流也是类似的只会从主节点流向从节点。当主节点异常或无法和其他从节点连通时，系统会选举一个新的主节点。

通过主节点的方式，Raft 将共识问题分解成了三个相对独立的子问题：

• 选主：当主节点异常时，系统必须选举一个新的主节点。
• 日志复制：主节点必须从客户端接收日志请求，然后将其复制到其他从节点上，并强制要求其他从节点的日志以主节点的为准。
• 安全性：如果任意一台服务器已经将某条日志应用到了自身的状态机中，那么其他任何服务器都不能在这条日志对应的索引上应用不同的命令到状态机中。

Raft 基础

一个 Raft 集群包含若干台服务器，5台是一个常见的配置，这允许系统最多能容忍两台服务器的异常。在任一时刻，每台服务器只会处于其中一个状态：主节点（leader），从节点（follower），或者候选节点（candidate）。在正常操作下，系统中只有一个主节点，剩下的都是从节点。从节点是被动的：它们不会主动发起任何请求，只是简单的响应来自主节点和候选节点的请求。主节点会处理所有来自客户端的请求（如果客户端将请求发给了一个从节点，从节点会将其转发给主节点）。候选节点这个状态会在选举新的主节点时用到。下图展示了各节点状态间的转换：

如下图所示，Raft 将时间切分为任意长度的任期（term）。任期会以连续的整数来标记。每个任期以选举作为开始，一个或多个候选节点会尝试成为主节点。如果某个候选节点赢得了选举，那么在这个任期剩下的时间里它将作为主节点。在某些情况下，多个候选节点可能会分票，造成没有一个候选节点赢得半数的选票。在这种情况下，当前任期会以没有主节点的状态结束，接着系统会马上对新的任期发起新的一轮选举。Raft 保证在任一任期内至多只有一个主节点。

不同的服务器可能会观测到不同次数的任期转变，在某些情况下一台服务器可能观测不到某次选举的发生或者感知不到整个任期。任期在 Raft 中扮演了逻辑时钟的角色，它能允许服务器侦测过期的信息例如过期的主节点。每台服务器都会保存一个当前任期（current term）的数字，这个数字会随时间递增。在服务器间通信时双方会附加上当前任期，如果某台服务器的当前任期小于另外一台服务器，那么这个服务器会将当前任期更新为另一台服务器的值。如果某个候选节点或者主节点发现自己的当前任期过期了，那么它会马上转为从节点状态。如果某台服务器收到的请求中的任期过期了，那么它会拒绝这个请求。

Raft 服务器间通过 RPC 进行通信，基础的共识算法只需要两种 RPC。RequestVote 用于候选节点在选主期间获取选票，AppendEntries 用于主节点向各从节点复制日志以及充当心跳的作用。如果某个 RPC 请求在一段时间内没有响应，那么服务器会重新发起请求，同时服务器也会并行发送 RPC 请求来达到最佳性能。

选主

Raft 通过心跳机制来触发选主。当服务器启动时，它们的初始状态是从节点。只要服务器能收到来自候选节点或者主节点的有效请求，就会一直出于从节点状态。主节点会定期的向所有从节点发送心跳（不带任何日志的 AppendEntries 请求）来维持自己主节点的地位。如果在某段时间内某台从节点没有收到心跳，那么它就会认为此时没有存活的主节点，则会发起选主来选择一个新的主节点，这个等待时间就叫做 election timeout。

开始新的一轮选主时，从节点会先将当前任期递增然后转换为候选节点。接着，它会给自己投一票然后并行发起 RequestVote 请求给其他从节点来获取选票。一个候选节点会保持当前的状态直到下面三种情况之一发生：

1. 当前候选节点赢得了选举
2. 有另外一个候选节点赢得了选举
3. 一段时间之后没有一个候选节点赢得选举

当候选节点获得了集群中针对某个任期的过半数节点的选票时就赢得了选举。在某个任期内，每台服务器只会最多给一个候选节点投票，以先来后到为准。过半数的选票保证了在某个任期内最多只会有一个候选节点被选举为主节点（Election Safety Property）。当某个候选节点赢得选举时，它就成为了主节点。然后它就开始向其他服务器发送心跳来维持主节点的状态并阻止其他节点继续发起选主。

候选节点在等待选票时有可能收到其他自认为是主节点的 AppendEntries 的请求。如果请求中的任期号不小于当前候选节点记录的任期号，则该候选节点会将此主节点作为主节点并转为从节点状态。如果请求中的任期号小于当前候选节点记录的任期号，则该候选节点会拒绝此请求并继续处于候选节点状态。

第三种情况是没有一个候选节点赢得了选举：当很多从节点在同一时间转变为候选节点时，会分散选票，最终造成没有一个候选节点赢得过半数的选票。当发生这种情况时，候选节点会将此次选主作超时处理，然后再次将当前任期自增，重新发起新的任期的选主，并向其他从节点继续发起一轮 RequestVote 请求。不过，如果缺少额外机制，分票可能会一直持续下去。

Raft 通过随机的 election timeout 来确保分票极少会发生并且在发生时能快速解决。为了避免分票，首先 election timeout 的值会在一个固定区间内随机选择（例如150-300ms）。这就分散了各从节点的选主启动时机，使得在大多数的情况下只有一个从节点会进入选主状态；在其他从节点进入选主状态之前，这个节点就已经赢得了选举并向其他从节点发送了心跳，这就大大扼杀了分票的可能性。同样的机制也被用来解决当分票确实发生的场景，每个候选节点在启动新的选主时会重新设置一个随机的 election timeout，然后在这段期间内等待其他从节点的选票，或者新的主节点的心跳，假设第一轮选主发生了分票，那么由于随机 election timeout 的存在，不同的候选节点进入第二轮选主的时机也不会相同，这就降低了第二轮选主继续发生分票的可能性。

选主是一个很好的例子展示了可理解性这个设计目标如何来指导在不同设计方案中做出选择。在最初的方案中作者打算使用一个排序系统：每一个候选节点被分配了一个唯一的权重，用来在多个候选节点中选择最终的主节点。如果某个候选节点发现其他候选节点的权重比自己高，那么这个候选节点就会退回到从节点状态，这就使得有着更高权重的候选节点能更容易的赢得下一轮的选举。不过这种实现可能会造成难以察觉的可用性问题（在不采用随机 election timeout 的情况下，当某个高权重的候选节点异常时，由于低权重的候选节点已经退回到了从节点状态，它需要再等待一个 election timeout 周期才能再次转变为候选节点，而在正常的情况下本身各节点间的信息交换速度较快，其他候选节点可能都已经退回到了从节点状态，此时高权重的候选节点异常就会造成系统没有候选节点，而距离各从节点进入选主状态又还有较长时间，从而造成系统在这段期间的不可用）。虽然作者对该算法进行了多次调整，但是每次调整后都会出现新的边界问题。最终作者认为随机化的 election timeout 更胜一筹和易于理解。

日志复制

当某个候选节点被选为主节点后，它就开始处理客户端请求。每个客户端请求中包含了复制状态机需要执行的命令。主节点将这个命令以日志的形式追加到自己的日志文件中，然后并行的给所有从节点发送 AppendEntries 请求来复制日志。当日志在各从节点上被安全的复制后，主节点就将日志对应的命令应用到自身的状态机中，并将结果返回给客户端。如果某个从节点异常或者运行缓慢，或者网络包丢失，主节点会一直重发 AppendEntries 请求（即使主节点已经将结果返回给了客户端），直到所有从节点保存了所有的日志。

日志内容的组织如下图所示，每一条日志包含了状态机需要执行的命令以及主节点收到该请求时对应的任期。日志中的任期信息用来检测日志间的不一致性以及保证前面所提到的 Raft 的几个关键特性。每条日志同时有一个索引信息来标记这条日志在日志文件中的位置。

在上图中，方块中形如 x <- 3 表示客户端的命令，命令上方的数字表示任期。

主节点会决定什么时候能安全的将某条日志对应的命令应用到状态机中，该条日志就被称为已提交（commited）。Raft 保证已提交的日志是持久化了的，并且最终会被所有可用的状态机执行。当主节点将某条日志复制到集群中过半数的机器上时（例如上图中索引位置为7的日志），这条日志就会被标记为已提交。同时，该条日志之前的日志也都会被提交，包括从其他主节点复制而来的日志。主节点维护了已提交日志中的最大的索引值，并将其附加到后续的 AppendEntries 请求中（包括心跳），所以最终所有的机器都能知道当前的最远日志提交位置。当某个从节点发现某条日志已经提交了，它就会将该条日志对应的命令应用到自身的状态机中（以日志中出现的顺序执行命令）。

Raft 设计的日志机制能保证在不同机器间高层次下的一致性。这不仅简化了系统的行为和使得系统更有可预测性，同时也是保证安全性的重要组成部分。Raft 保证了下面两个性质（同时也组成了 Log Matching Property）：

• 如果两个日志文件中相同索引位置的日志保存着相同的任期，则它们保存着相同的客户端命令
• 如果两个日志文件中相同索引位置的日志保存着相同的任期，则在这个索引位置之前的日志都相同

第一个性质保证是因为主节点在某个任期内最多只会在某个索引位置创建一条日志，而日志的位置创建后就不会改变。第二个性质保证则是通过 AppendEntries 请求中的一致性检查来实现。当主节点发送 AppendEntries 请求时，主节点会附带上本次需要复制的日志的前一条日志的索引和对应任期。如果从节点没有在自己的日志中找到这个指定索引和任期的日志，那么它会拒绝新日志的写入请求。日志的一致性检查类似于数学归纳法：初始情况日志为空，所以满足 Log Matching Property，假设从索引位置1到 i 的日志都满足 Log Matching Property，那么当主节点在成功提交了新的日志即索引位置 i + 1 的日志后，则在 [i + 1, i + 1] 这个范围满足了 Log Matching Property，从而得出从索引位置1到 i + 1 的日志都满足了 Log Matching Property。因此，只要 AppendEntries 的请求成功返回，那么主节点就知道从节点的日志和自己的相同。

在正常的操作下，主节点的日志和从节点的日志始终能保持一致，所以 AppendEntries 的一致性检查从来不会失败。不过，当主节点异常时则会造成日志不一致（主节点还没有来得及复制所有的日志）。同样的，从节点的异常也会造成日志不一致（从节点没有收到所有的日志）。下图展示了从节点的日志可能和新的主节点不同的情况。一个从节点有可能缺少某些主节点拥有的日志，或者拥有一些主节点没有的日志，或者两者都有。这种日志的缺少或多余的情况可能会横跨几个任期。

在上图中，方块中的数字表示任期。当前已提交的日志的索引位置是1-9，一共有四台机器在1-9位置的日志相同，符合过半数的原则。a 和 b 相比于主节点来说缺少日志，c 和 d 相比于主节点来说有多余的日志，e 和 f 两种情况都有。对于 f 来说，它在任期2中被选为主节点，然后开始接受客户端请求并写入本地日志，但是还没有成功复制到其他从节点上就异常了，恢复后又被选举为任期3的主节点，又重复了类似的操作。

在 Raft 中，主节点通过强制从节点复制自己的日志来保证日志的一致性。也就是对于从节点来说，和主节点日志不一致的地方会被主节点的日志覆盖。

为了让从节点的日志和主节点保持一致，主节点必须知道到哪个索引位置为止主从节点间的日志是一致的，然后删除从节点在这个索引位置之后的日志，并替换为主节点中的日志。主节点为每个从节点维护了一个 nextIndex 变量，用来表示下一条由主节点发送给从节点的日志索引位置。当某个节点成为主节点时，它先将 nextIndex 初始化为自身日志文件中最后一条日志的索引位置加1。如果从节点的日志和主节点不一致，那么在下一次的 AppendEntries 请求中会返回失败。当主节点收到失败响应后，会将 nextIndex 减1并重新发送 AppendEntries 请求（前面提到，当主节点发送 AppendEntries 请求时，主节点会附带上本次需要复制的日志的前一条日志的索引和对应任期，从节点会根据这两个值来决定是否接受写入，当 nextIndex 减1时，在新的 AppendEntries 请求中这两个值也需要相应的往前移），最终 nextIndex 会等于某个值使得主从节点在 nextIndex 之前的日志都相同。此时 AppendEntries 会返回成功，从节点会将 nextIndex 及其之后的日志都替换为主节点的日志，至此，主从节点的日志就恢复了一致，并一直保持到当前任期结束。

如果需要的话，可以对上述的交互协议进行优化来减少 AppendEntries 的次数，尤其是从节点的日志落后主节点太多的时候。例如，当从节点需要拒绝 AppendEntries 的请求时，可以在响应结果中带上不一致的日志的任期，以及该任期下的第一条日志的索引位置。根据这个信息，主节点就可以大幅减少 nextIndex 的值从而直接跳过该任期下不一致的日志，而不是一次 RPC 请求识别一条日志。不过作者怀疑这个优化在实际中是否有必要，因为异常并不会频繁发生所以不太可能会有那么多的不一致。

针对上面的优化手段作者并没有描述过多的细节，在 6.824 2022 Lecture 7: Raft (2) 中 Robert Morris 提出了自己的猜想。在下图中，S1 是主节点，S2 到 S7 是从节点，其中 S2 到 S4 节点的日志和主节点不一致，日志索引1到3已提交，现在主节点要在索引位置4追加一条新日志，分别来看 S2 到 S4 如何处理。

Robert Morris 认为当从节点拒绝 AppendEntries 请求时，需要返回三个信息给主节点：

• XTerm：冲突的日志的任期（如果有的话）
• XIndex：冲突的日志的任期下的第一条日志的索引位置（如果有的话）
• XLen：整个日志的长度

记 prevLogIndex 表示主节点发送给从节点的上一条日志的索引位置，prevLogTerm 表示上一条日志所属的任期。则在主节点的第一轮 AppendEntries 中 prevLogIndex = 3，prevLogTerm = 6，对于 S2 到 S4 初始化的 nextIndex 为：

1
2
3
4
5

{
    "S2": 4,
    "S3": 4,
    "S4": 4
}

对于 S2，首先检查自己日志中索引位置为 prevLogIndex = 3 的日志，发现其任期为5，和 prevLogTerm = 6 不匹配，从而拒绝请求，并返回 XTerm = 5，XIndex = 2，XLen = 3。主节点收到结果后，发现 S2 中 prevLogIndex 指向的任期和自己不同，这里比主节点小所以主节点往前遍历日志，发现没有任期5的日志，说明 S2 中整个任期5的日志都可以跳过，因此主节点将 S2 的 nextIndex 修改为 XIndex，即 nextIndex = 2。在第二轮的 AppendEntries 请求中，prevLogIndex = 1，prevLogTerm = 4，同时主节点也会将索引位置2到3的日志连同最新的日志一起随请求发送。S2 再次收到请求后，发现这次 prevLogIndex/prevLogTerm 标记的日志和自己匹配，因此返回成功，并将主节点的日志覆盖到索引位置2到4中。

对于 S3，首先检查自己日志中索引位置为 prevLogIndex = 3 的日志，发现其任期为4，和 prevLogTerm = 6 不匹配，从而拒绝请求，并返回 XTerm = 4，XIndex = 1，XLen = 3。主节点收到结果后，发现 S3 中 prevLogIndex 指向的任期和自己不同，这里比主节点小所以主节点往前遍历日志，发现了任期4的日志，说明 S3 中任期4的日志比主节点多，因此主节点将 S3 的 nextIndex 修改为2，即主节点中任期4的最后一个日志的索引位置加1（这里 Robert Morris 的原话是 leader's last entry for XTerm，不过为了能统一处理下一次请求中的 prevLogIndex 和 prevLogTerm，这里加了1）。在第二轮的 AppendEntries 请求中，prevLogIndex = 1，prevLogTerm = 4，同时主节点也会将索引位置2到3的日志连同最新的日志一起随请求发送。S3 再次收到请求后，发现这次 prevLogIndex/prevLogTerm 标记的日志和自己匹配，因此返回成功，并将主节点的日志覆盖到索引位置2到4中。

对于 S4，首先检查自己日志中索引位置为 prevLogIndex = 3 的日志，发现不存在，所以拒绝请求，并返回 XTerm = null，XIndex = null，XLen = 1。主节点收到结果后，发现 XTerm 和 XIndex 都为空，说明 S4 的日志比自己短，因此主节点将 S4 的 nextIndex 修改为2，即 S4 的日志长度加1（这里 Robert Morris 的原话是 XLen，不过为了能统一处理下一次请求中的 prevLogIndex 和 prevLogTerm，这里加了1）。在第二轮的 AppendEntries 请求中，prevLogIndex = 1，prevLogTerm = 4，同时主节点也会将索引位置2到3的日志连同最新的日志一起随请求发送。S4 再次收到请求后，发现这次 prevLogIndex/prevLogTerm 标记的日志和自己匹配，因此返回成功，并将主节点的日志覆盖到索引位置2到4中，如果不匹配，则又会流转到上面两种情况中。

在这种机制下，主节点不需要采用其他特殊的操作就能保持从节点日志的一致性。通过正常的 AppendEntries 请求，结合其一致性检查的功能，从节点的日志就可以自行恢复一致。而对于主节点来说，它永远不会覆盖或者删除自己的日志（Leader Append-Only Property）。

这种日志复制机制展现了第二节中描述的共识算法所需要的特性：只要集群中过半数的机器存活，Raft 就能接收，复制和应用新的日志；在正常情况下，只需要一轮过半数机器的 RPC 请求响应成功就能复制一条新日志；一台运行缓慢的机器并不会影响整体的性能。

安全性

前面几节描述了 Raft 如何选主以及复制日志。不过，这些机制还不足以保证每个节点能以相同的顺序执行相同的命令。例如，某个从节点可能在某段期间内异常了，在这段期间内某个主节点已经提交了部分日志，此时假设主节点异常，之前异常的节点恢复并被选为主节点，根据前面所描述的 AppendEntries 的工作流程，它就有可能将其他从节点中之前提交的日志覆盖掉。因此，不同的节点可能会执行不同的命令序列。

本节通过描述了什么样的节点才允许被选为主节点来补充完善 Raft 算法。这个选主的限制保证了如果某个节点被选为了主节点，那么它就一定包含之前所有任期内由其他主节点提交的日志（Leader Completeness Property）。根据这个选主限制，我们可以使日志提交的规则更加清晰。

选主限制

在所有基于主节点的共识算法中，最终主节点必须保存所有已提交的日志。在某些共识算法中，例如 Viewstamped Replication，如果某个节点没有包含所有已提交的日志也能被选为主节点。这些共识算法有额外的机制来识别出缺失的日志，并在选主期间或之后将缺失的日志发送给主节点。然而，这就增加了额外的机制和复杂性。Raft 采用了一种更简便的方案来保证每一个被新选举的主节点一定包含了之前所有主节点提交的日志，而无需额外传输缺失的日志给主节点。这就表明日志始终是单向流动，即从主节点流向从节点，并且主节点永远不会覆盖已经存在的日志。

Raft 在选主阶段会避免某个没有完整提交日志的候选节点成为主节点。一个候选节点必须和集群中过半数的节点通信来获取选票，这说明每一条提交的日志都至少存在于其中一台节点上（假设有 S1 到 S5 五个节点，之前 S1 是主节点并将某条日志成功提交到 S1、S2、S3，此时 S1 异常假设 S4 成为新的主节点，并获得了 S3、S4、S5 的选票，由于过半数原则，新的主节点的选票必然和之前的主节点的选票存在重合，也就说明必然至少有一台机器上保存了之前主节点提交的日志）。如果候选节点的日志至少和过半数的节点的日志一样新（一样新的定义见后文描述），那么它将会拥有所有已提交的日志。RequestVote 接口实现了这个限制：发送请求时会带上候选节点的日志信息，如果其他节点的日志比这个候选节点还要新，则会拒绝这个候选节点的选票。

Raft 通过比较两个日志文件中的最后一条日志的索引位置和任期来决定哪个日志较新。如果两个日志的任期不同，则更高任期的日志较新；如果两个日志的任期相同，则索引位置大的日志较新。

提交之前任期的日志

对于主节点来说，如果当前任期下的某条日志被过半数的节点成功复制，那么这条日志就可以被提交。如果日志变为已提交前主节点异常了（已复制的副本未过半数或者还没有来得及执行提交），后续的主节点会尝试继续复制该日志。然而，主节点并不能马上下结论说某条之前任期产生的日志在过半数的节点上保存后就算被安全提交了。

上图描述了某条日志被过半数的节点复制后，有可能会被某个新的主节点的日志所覆盖的情况。在 a 中，S1 是主节点，并且部分复制了索引位置2的日志到其他从节点上；在 b 中，S1 发生异常，S5 被选为主节点，在索引位置2的地方追加了一条任期3的日志；在 c 中，S5 发生异常，S1 恢复并再次被选为了主节点，此时任期是4，S1 会继续通过 AppendEntries 的一致性检查将索引位置2的日志继续复制给过半数的节点，但是还未提交，同时又在索引位置3的地方追加了一条任期4的日志；在 d 中，S1 发生异常，S5 成为主节点，则 S5 会将自己的索引位置2的日志复制给其他的从节点；而在 e 中的另一种情况下，如果 S1 在异常前将当前任期下的索引位置3的日志复制到了过半数的节点上，那么索引位置3的日志就可以被提交，因为 S5 节点不可能会成为主节点（它的日志相比于其他过半数的节点来说不够新）也就不会覆盖，而在此时，索引位置3之前的日志也可以被认为是已提交的。

为了避免上面 d 所描述的情况，Raft 永远不会通过计算某条之前任期的日志副本的数量来判断这条日志是否能提交（也就是 c 中的情况，此时 S1 是主节点，任期是4，通过和其他从节点的通信将任期2的日志复制给了过半数的从节点，但是 S1 不会提交任期2的日志，因为一旦提交就有可能出现 d 中的情况）。只有当前主节点当前任期下生成的日志才会根据已复制的副本的数量来判断是否能提交；如果当前任期下的某条日志以这种方式提交了，那么根据 Log Matching Property 这条日志之前的日志也会间接的被提交。虽然在某些场合下，主节点可以知道某条之前任期的日志是被提交的（例如，如果这条日志在每个节点上都有保存），但是 Raft 出于简洁性的考虑采用了更保守的策略。回到上面的例子，在 c 中即使 S1 将索引位置2的日志提交了才发生异常，也依然有可能发生 d 的情况，因为 d 中的 S5 并不知道其他过半数的从节点提交了索引位置2任期2的日志（除非有额外的机制，所以这里说 Raft 采用了保守的策略没有引入其他机制），也就是说提交一个之前任期的日志并不能保证它不会被之后的主节点覆盖，所以这部分之前任期的日志就不能当做已提交或者做了提交也没有用。一直等到 e 中的情况，在当前任期4下，只要 S1 将索引位置3的日志复制到了过半数的节点上，即使此时 S1 异常了，这个日志在未来也能被其他主节点间接提交，因为下一轮的候选节点要么有索引位置3的日志，要么没有索引位置3的日志，而根据日志新旧原则，没有索引位置3的日志的候选节点不可能成为主节点，所以只有那些复制了索引位置3的日志的候选节点才有可能成为新的主节点，因为主节点不会增删日志，所以索引位置2、3的日志必然存在于新的主节点中，一旦新的主节点提交了一个更高任期的日志，索引位置2、3的日志也就被间接提交了。这就保证了在这种方式下索引位置3及其之前的日志不会被覆盖。

因为主节点将之前任期的日志复制到其他从节点时依然保留原始任期信息，所以 Raft 选择在提交日志时增加额外的机制（上述描述的日志提交规则，同时引入了一定的复杂性）来保证安全性。在其他共识算法中，如果一个新的主节点需要复制之前任期的日志，那么就必须以当前任期的名义。Raft 的做法可以很方便的识别每条日志属于哪个任期，因为每条日志的任期不会随时间而改变。另外，相比于其他共识算法，在 Raft 中新的主节点会发送更少的来自之前任期的日志（其他共识算法在提交日志前需要发送冗余的日志来重新编号）。

安全性证明

以完整的 Raft 算法为基础，现在可以更精确的验证 Leader Completeness Property 的正确性。这里使用反证法来证明，假设 Leader Completeness Property 不正确，继而推导出一个矛盾，从而证明假设不成立。假设在任期 T 内某个主节点 leader_T 提交了一条日志，然后这条日志不会出现在新的任期的主节点中。不妨令满足假设的最小的任期为 U（U > T），对应任期 U 的主节点为 leader_U，则 leader_U 没有 leader_T 提交的日志。

1. leader_T 提交的日志必然在选主时就不存在于 leader_U 中，因为主节点不会删除和覆盖日志。
2. leader_T 将日志复制给了集群中过半数的节点，而 leader_U 从集群中过半数的节点获得了选票，所以两者必然有重合，因此必然存在一个节点即复制了 leader_T 提交的日志，又投票选举了 leader_U 作为新的主节点，在上图中这个节点就是 S3。这个节点是推导出矛盾的关键。
3. S3 必然是先收到 leader_T 的复制日志请求然后才投票给 leader_U，否则的话如果 S3 先进入新的任期那么它会拒绝来自 leader_T 的 AppendEntries 的请求，因为 S3 的当前任期更大。
4. S3 在给 leader_U 投票前会完成日志的复制，因为我们这里假定的 U 是最小的一个不包含 leader_T 提交的日志的任期，所以根据这个假定在 [T + 1, U - 1] 之间的主节点都是必然包含 leader_T 提交的日志的，而主节点不会删除或覆盖日志，并且只在不一致的时候删除从节点的日志，所以在任期 U 内，S3 依然是保留 leader_T 提交的日志的。
5. S3 投票给了 leader_U，所以根据选主规则 leader_U 的日志至少是和 S3 一样新。这就导致了两个矛盾。
6. 首先，如果 S3 和 leader_U 的最后一条日志的任期相同，那么 leader_U 的日志索引就必然大于等于 S3，则 leader_U 必然就包含 S3 的每一条日志。假设双方最后一条日志的任期是 X，则 T <= X <= U - 1，在这个范围内的主节点都是有 leader_T 所提交的日志的，根据 AppendEntries 请求的日志一致性校验，只要 leader_U 在这期间收到了主节点的请求，那么主节点就会补齐 leader_U 的日志（如果不一致的话），所以 leader_U 必然就包含 S3 的每一条日志。因此这就产生了一个矛盾，因为根据开头的假设 leader_U 是不应该有 leader_T 提交的日志的。
7. 所以，要想让 leader_U 的日志比 S3 新，那就只能是 leader_U 的最后一条日志的任期大于 S3 的最后一条日志的任期。而这个任期也必然比 T 大，因为 S3 的最后一条日志的任期至少是 T。记这个任期的主节点为 leader_P，根据 Log Matching Property，leader_U 中到最后一条日志前的日志应该和 leader_P 相同，又因为任期 U 之前的主节点都包含 leader_T 所提交的日志，所以 leader_U 也应该包含 leader_T 所提交的日志，所以又产生一个矛盾。
8. 至此完成了所有矛盾的证明。因此，所有任期比 T 大的主节点都必然包含 leader_T 在任期 T 内所提交的日志。
9. 而 Log Matching Property 也保证了后续的主节点也包含了间接提交的日志。

根据 Leader Completeness Property，我们可以证明 State Machine Safety Property，即如果某台服务器将某个索引位置的日志应用到了自身的状态机中，那么不会有任何一台服务器在相同索引位置应用了一条不同的日志到状态机中。如果某台服务器要将某条日志应用到状态机中，那么这台服务器在这条日志之前的日志都是和主节点相同的，而且是已提交的。现在来考虑在某个最小的任期内，某一台服务器要应用某一条日志，根据 Log Completeness Property 的保证，后续更高任期的主节点都会存储这条日志，所以后续节点在后续任期中应用相同索引位置的日志时也必然是应用了相同的日志内容。因此 State Machine Safety Property 是正确的。

最后，Raft 要求各节点以日志的索引顺序来应用日志。结合 State Machine Safety Property，可以得出所有的节点会以相同的顺序应用相同的日志到自身的状态机中。

主节点和候选节点异常

截止目前我们讨论的都是主节点异常。从节点和候选节点异常相比于主节点异常来说更容易处理，而且能以相同的方式处理。当从节点或候选节点异常时，则其他节点发送的 RequestVote 和 AppendEntries 请求都会失败。Raft 通过无限重试来处理这个问题；如果异常的机器重启了，那么这些 RPC 请求就会成功。如果某台机器完成了某个请求但在响应前异常了，那么它会在重启后收到相同的请求。Raft 的 RPC 请求都是幂等的，所以这种情况不会造成影响。例如，某个从节点收到了 AppendEntries 请求然后发现请求中的日志已经在本地日志中了，那么这个节点就会忽略这个请求。

时间和可用性

Raft 的其中一个要求是安全性的保证不依赖于时间：系统不能因为某些事件发生的快了些或慢了些而产生不正确的结果。然而，可用性（系统可以及时的响应客户端）不可避免的要依赖时间。例如，如果服务器间的信息交换需要的时间大于服务器异常的间隔时间（例如信息交换需要5秒，而每隔2秒服务器就异常了），则候选节点没有足够的时间来赢得选举；而缺少主节点，系统也无法继续运行。

选主是 Raft 中对时间要求最关键的方面。只要遵循如下的时间要求那么 Raft 就能维持选主的正常运行：

1

broadcastTime << electionTimeout << MTBF

其中 broadcastTime 是服务器并行的给集群中的其他服务器发送 RPC 请求并收到响应的平均时间；electionTimeout 是前面描述的选主等待时间，如果在这个时间段内某个节点没有收到来自主节点的心跳，那么它就会启动选主流程；MTBF 则是单台服务器各次异常间的平均间隔时间。broadcastTime 应该比 electionTimeout 小一个量级，这样主节点才能来得及给从节点发送心跳来维持主节点的地位；再结合随机化的 electionTimeout，这种不固定的时间也避免了选主的分票。electionTimeout 应该比 MTBF 小几个量级从而使得系统能平稳运行。当主节点异常时，系统大概会在 electionTimeout 的时间段内不可用，如果 MTBF 足够大就可以避免这个现象频繁发生。

broadcastTime 和 MTBF 由底层系统决定，而 electionTimeout 则是需要由设计者决定。Raft 的 RPC 请求一般会要求接受者将数据持久化到可靠存储上，根据存储技术的不同 broadcastTime 的范围会在0.5毫秒到20毫秒之间。因此，electionTimeout 的设定范围一般是10毫秒到500毫秒之间。服务器的 MTBF 时间一般是几个月或更久，已经足够满足 Raft 对时间的要求。

集群节点变更

目前为止我们所讨论的都是基于集群配置（参与共识算法的服务器）不变的基础上。而实际上，集群的配置不是一成不变的，有时候就需要修改集群的配置，例如替换掉异常的服务器或者调整复制的级别。虽然操作时可以先下线集群中的全部机器，然后更新配置文件，最后再重启集群，不过在操作期间整个系统都是不可用的。另外，如果其中涉及了人工操作，那么就会有人为错误的风险。为了避免这些问题，Raft 的作者决定将集群配置设计为自动化并整合到 Raft 共识算法中。

为了使集群配置变更是安全的，需要保证在变更期间不会发生在某个任期内有两个主节点的情况。不幸的是，不管怎么样让服务器直接从旧的配置替换为新的配置都是不安全的。因为不可能原子性的将所有服务器一次性的完成配置替换，所以如下图所示，在转换期间整个集群有可能分裂成两个独立的群体。

在上图中，集群由原来3台机器扩展为5台，由于每台服务器实际替换配置文件的时机不同，如红色箭头所示，存在某一时刻集群中可能会有两个主节点，假设此时发生选主，由于在 Server 1 看来集群中的节点数量还是3个，所以它只要获取到 Server 2 的选票就可以声明自己为主节点；而在 Server 5 看来，此时集群中有5个节点，所以它在获取了 Server 3、Server 4 的选票后就成为主节点，此时集群中就存在了两个主节点。

为了保证安全性，机器配置变更必须使用两阶段提交。有很多种方式来实现两阶段提交，例如，某些系统在第一阶段会先禁用掉旧的配置从而使系统不再处理客户端请求；然后在第二阶段启用新的配置。在 Raft 中，集群会先切换为一个被称之为 joint consensus 的过渡配置；一旦这个过渡配置被提交，集群就会切换为新配置。joint consensus 包含了新老两套配置：

• 日志会复制到两套配置下的所有节点中。
• 新老配置下的节点都可以被选为主节点。
• 选主和日志提交需要同时获得新老配置下大多数节点的选票。

joint consensus 使得每台服务器能在不同的时间点切换配置而不会破坏 Raft 的安全性。另外，joint consensus 也保障了集群在切换期间能正常响应客户端请求。

集群配置通过日志文件中特殊的日志项来存储和通信，上图描述了配置变更的过程。当主节点收到需要将配置从 C_old 变为 C_new 的请求时，它首先将 joint consensus 的配置 C_old_new 写入到本地日志中，然后将其复制到过半数的从节点中。一旦某个节点将 C_old_new 写入到自己的日志中后，它后续的决定都会基于 C_old_new 的规则（Raft 中的节点始终使用最新的配置来做决策，不管这条日志是否已提交）。所以主节点会根据 C_old_new 需要的规则来决定 C_old_new 状态下的日志是否已提交。如果此时主节点异常，新的主节点可能来自 C_old，也可能来自 C_old_new，这取决于这个候选节点是否收到来自 C_old_new 的复制请求。不过不管哪种情况，在这期间 C_new 下的节点都不可能单方面做决策。

一旦 C_old_new 提交成功，说明集群中过半数的机器都有了 C_old_new 配置，此时不管是 C_old 还是 C_new 的机器都不可能单方面做决策，另外 Leader Completeness Property 也保证了后续没有 C_old_new 日志的节点不可能被选为主节点。所以此时主节点可以开始将 C_new 写入到日志中，然后再复制给其他从节点。同样的，各节点一旦收到 C_new 的配置就会以 C_new 的配置为准做决策。当 C_new 被提交后，旧配置就无关紧要了，那些不在新配置下的机器就可以被下线。在整个变更期间，没有任何一个时刻 C_old 和 C_new 的节点可以同时做决策，这就保证了安全性。

在配置变更时还有其他一些问题需要指出。第一个问题是新加入的节点一开始可能没有保存任何日志。如果它们以这个状态加入集群，那么它们可能需要很长一段时间来复制日志，可能会造成在这期间主节点无法提交新的日志。为了避免造成可用性问题，Raft 在配置变更前引入了额外的一个阶段，新加入的节点不会参与投票（主节点会将日志发给这些节点，但是在基于过半数节点原则做决策时会忽略这些节点）。当这些新加入的节点的日志追赶上其他节点后，Raft 就开始上面描述的配置变更流程。

第二个问题是在配置变更后当前的主节点可能不再属于新集群（例如归到其他集群或下线）。在这种情况下，一旦 C_new 的配置被提交，那么它就会退回到从节点状态。这说明存在某段时间（提交 C_new 的期间），当前主节点在管理集群时不会把自己计算在内；它在复制日志时依然会进行过半数的节点确认，但这个过半数的节点不包括自己。主节点状态的转变发生在 C_new 提交后，因为只有这个时间点 C_new 才能独立做决策（选出的主节点一定包含 C_new 的配置）。而在这个时间点之前，可能只有 C_old 的节点能被选为主节点。

第三个问题是被删除的节点可能会干扰集群（不在 C_new 中的节点）。因为这些节点不再收到心跳，所以过了 election timeout 后它们会发起选主流程。它们会向其他节点发送新任期的 RequestVote 请求，当前的主节点收到请求后因为新任期比自己的任期大（假设这些被剔除的节点在剔除时所属的任期和主节点相同；不过即使任期比主节点小也没关系，因为每次选主都会增加任期，这些被删除的节点不断的选主然后失败，任期会逐渐增加，最终超过主节点），主节点会认为自己的任期过期了，所以会转为从节点状态。最终系统会选择出一个新的主节点，不过这些被删除的节点又会再次超时然后再次发起选主，从而造成系统可用性问题。

为了避免这个问题，各节点在确认主节点存在的情况下会丢弃 RequestVote 请求。如果某个节点在最小 election timeout 内收到了 RequestVote 请求（前面提到，election timeout 的值是某个区间内的随机值，某个节点在收到主节点的心跳后，在还没有达到最小 election timeout 的时候就又收到 RequestVote 请求，例如 election timeout 的区间为 [150, 300]，这里最小 election timeout 指的就是100），则该节点不会更新自己的任期或者投票。这样做并不会影响正常的选主，因为正常的选择至少会等待一个最小 election timeout 时间。不过这样做却能避免那些被删除的节点对集群的干扰，只要主节点能给其他从节点发送心跳，那么它就不会受到被删除的节点所发送的更大的任期的影响。

日志压缩

在和客户端的日常通信中，Raft 节点的日志会逐渐增长，但是在实际的系统中，日志不可能无限增长。当日志越来越多，它占据的空间也越来越大，需要根据日志来重放的时间也越来越多。如果没有一个机制来丢弃过期的日志，那么这最终会导致可用率问题。

快照是压缩日志的最简便的方法。执行快照时，整个系统的状态被写入到保存在可靠存储上的快照里，那么一直到快照执行时的日志都可以被丢弃。快照技术也在 Chubby 和 ZooKeeper 中使用，在本节剩余的内容中将会介绍 Raft 中的快照。

类似 log cleaning 和 log-structured merge trees 这样的增量手段也能处理压缩日志。它们每次只操作一部分数据，所以就将压缩带来的负载影响随着时间摊平。它们首先会选择一片已经积累了大量被删除或被覆盖的对象的数据区域，然后以更紧凑的方式重写这片区域内存活的对象，最后释放这片区域。这种手段相对于快照来说需要引入额外的机制同时复杂性也更高，而快照通过始终操作整个数据集来简化了问题。log cleaning 技术需要对 Raft 进行修改，状态机可以使用和快照相同的接口来实现 log-structured merge trees。

上图展示了 Raft 快照的概念。每台服务器会独立的执行快照，并且只包含已提交的日志。执行快照时大部分的工作是状态机将当前的状态写入到快照中。Raft 同时添加了一小部分元数据到快照中：快照对应的最后一个日志的索引（last included index，状态机已应用的最后一条日志），以及最后一个日志对应的任期（last included term）。这两个元数据信息用于执行快照后的第一次 AppendEntries 请求的一致性检查，因为需要比对前一个日志的索引和任期。同时为了启用集群配置变更，快照中也保存了当前最新的集群配置。一旦服务器完成了快照的写入，那么它就可以删除到快照为止的所有日志，以及以前的快照。

虽然各节点能独立的创建快照，主节点有时必须将快照发给那些落后的从节点。这个发生在主节点已经丢弃了需要发送给从节点的日志的情况下。幸运的是，这种情况在正常情况下不大可能发生：一个时刻和主节点保持同步的从节点已经包含了需要的日志。然而，某个运行异常缓慢的从节点或者新加入集群的从节点可能会缺少很多日志。所以主节点通过直接发送快照的方式来同步从节点的状态。

主节点通过一个新的 RPC 请求 InstallSnapshot 来将快照发送给那些落后太多的从节点。当从节点收到这个请求后，它必须决定如何处理目前已有的日志。一般来说，快照会包含当前从节点还没有的日志。在这种情况下，因为快照捕捉的是整个状态机的状态，说明快照对应的日志范围大于当前从节点的日志范围，所以从节点直接丢弃自己的日志即可。当然从节点的日志可能会包含某些未提交的日志和快照冲突，不过因为是未提交所以也没有问题。不过，如果从节点收到的快照只覆盖了自己日志的前一部分（可能是因为重传或者错传。假设现在 S1 是主节点需要向从节点 S2 发送快照，不过此时主节点 S1 发生异常，快照请求也没有到达 S2，另一个从节点 S3 成为新的主节点，而 S3 的日志还未压缩，所以 S2 通过心跳交互从 S3 获取到了最新的日志，并在之后提交了几条日志；此时 S1 再次成为主节点，因为 Raft 通过 nextIndex 来计算需要发给从节点的日志范围，在 S1 的认知中，并不知道 S2 已经有了最新的日志，S1 会继续判断 rf.lastIncludedIndex 和 nextIndex 的大小，因为 nextIndex 还未更新，所以在 S1 看来，根据 nextIndex 计算出的 prevLogIndex 依然小于 rf.lastIncludedIndex，所以 S1 会认为 S2 需要的日志自己没有，从而继续发送快照信息，而此时的快照只覆盖了 S2 日志的一部分。），那么和快照重合的日志就可以被删除，不过在这之后的日志还依然有效而且也必须保留。

快照违背了 Raft 的强主节点规则（strong leader），因为从节点可以在不知晓主节点的情况下创建快照。不过，作者认为这个做法是合理的。虽然主节点避免了做决策时发生冲突，不过因为快照保存的是已经应用到状态机的日志，本身就没有冲突，所以也就不需要主节点的存在。数据流依然只从主节点流向从节点，只不过有了快照后从节点可以重新组织自己的数据。

作者曾经考虑过另一种基于主节点的快照实现方案：快照只能由主节点创建，然后由主节点将快照发给每一个从节点。不过，这种方案有两个缺点。第一，由主节点发送快照会浪费带宽并且减慢了快照的完成速度。每个从节点本身就有了执行快照所需要的全部信息，从自身状态创建快照相比于从网络接收快照来说成本更低。第二，主节点的实现会更加复杂。例如，主节点需要并行的发送快照和新的日志给从节点，这样才不会阻塞新的客户端请求。

还有两个问题会影响快照的执行速度。第一，服务器必须决定在什么时候进行快照。如果执行快照太频繁，那么就会浪费磁盘 IO 和资源。如果执行快照频率太低，那么它就有耗尽存储空间的风险，以及延长了节点异常重启后重放日志的时间。一个简单的策略是当日志的大小达到一个固定的大小后就执行快照。如果这个大小远大于快照的大小，那么快照所带来的的磁盘 IO 影响就足够小。

第二个性能问题是一次写快照可能会花费较长的时间，所以需要它不能延误正常操作。解决方法是使用写时复制技术（copy-on-write），这样节点也能同时接受新的更新而不会影响快照。例如，由函数式数据结构组成的状态机天然的支持写时复制。或者操作系统的写时复制支持（例如 Linux 的 fork）可以用来在内存中创建一份整个状态机的快照（Raft 的实现采用了这种方式）。

Raft (2) FAQ 中提到写时复制是如何来实现的：

当某个节点需要写快照时，它会调用 Linux 的 fork 方法，从而创建了一个子进程，子进程会复制父进程的内存空间，从而复制了状态机的状态。当然，如果单纯的复制内存显然是不现实的，Linux 不会整个复制内存，在这里就采用了写时复制技术，操作系统会将涉及的内存页标记为 copy-on-write，对于父进程和子进程来说都是只读的，当父进程或子进程想要写入某个内存页时会触发缺页中断（page fault），这个时候操作系统才会实际复制这个内存页。

客户端交互

本节描述了客户端如何与 Raft 交互，包括客户端如何找到集群中的主节点以及 Raft 如何支持线性化语义。这几个问题同时适用于其他基于共识的系统，Raft 的解决方案也和其他系统类似。

Raft 的客户端会将所有请求发送给主节点。当客户端首次启动时，它会随机与一台服务器建立连接。如果客户端选中的服务器不是主节点，那么这台服务器就会拒绝客户端的请求并告知客户端它所知道的最近一段时间的主节点（AppendEntries 请求中包含了主节点的网络地址）。如果主节点异常了，那么客户端的请求会超时，然后它会继续随机挑选一台服务器重复上述流程。

Raft 的实现目标是线性化语义（每个操作看起来都是立即执行，在请求和响应之间只执行了一次）。不过，通过对 Raft 的描述可以知道一个客户端的请求有可能被执行多次：例如，主节点在日志提交完成后但是在响应客户端前发生异常，那么客户端就会选择一个新的主节点发起重试，造成请求被执行两次。这个解决方案是让客户端在每次请求时生成一个唯一的编号。这样，状态机就可以跟踪每个请求的最新编号和对应的响应。如果某个节点收到的请求编号已经被处理过了，那么它就立即返回响应的结果而不会重新执行。

只读请求可以不记录日志而直接处理。然而，如果没有其他机制的保证，这有可能会返回过期的数据，因为和客户端通信的主节点已经有可能被其他的主节点所取代。在线性化语义下，Raft 不能够返回过期数据。Raft 需要额外的两个措施在不借助日志的情况下避免返回过期的数据。第一，主节点必须知道最新提交的日志的信息。虽然 Leader Completeness Property 保证了主节点有所有已提交的日志，但是在主节点任期开始的时候，它可能并不知道哪些日志是提交的。为了找到已经提交的日志，主节点需要在任期内提交一条日志。Raft 会要求主节点在任期开始时提交一条 no-op 的日志。Raft (2) FAQ 中解释了为什么这么做：

提交 no-op 日志本质和提交普通的日志没有什么不同，也需要过半数的节点响应，一旦提交完成，那就说明 no-op 之前的日志也必然是被提交的，所以主节点就可以根据这个 no-op 日志为界来知道哪些日志被提交了。

第二，主节点在处理只读请求前必须检查自己还是否是有效的主节点（如果有新的主节点，那么当前主节点持有的信息有可能过期了）。主节点会先和集群中过半数的节点交换心跳来确保自己还是主节点，然后再响应只读请求。另外，主节点也可以在心跳机制的基础上引入租约来确保自己是主节点，不过这就依赖时间来保证正确性（假设时间误差是有界的）。同样的，在 Raft (2) FAQ 中 Robert Morris 也提出了自己的设想：

例如主节点在发给其他从节点的心跳中要求在接下来的100毫秒内其他节点不允许成为主节点，那么在接下来的100毫秒内主节点就可以直接处理只读请求而不用担心会有新的主节点。

RPC

这部分的内容来自于论文中的 Figure 2 和 Figure 13，主要描述了 Raft 涉及的 RPC 接口的实现要求以及其他一些系统约束。

状态

本节描述了各个节点内部需要维护的状态。

所有节点都需要持久化的状态（先持久化再响应 RPC 请求）：

• currentTerm：当前节点所处在的最新任期（第一次启动时初始化为0，单调递增），如果这个不持久化，那么节点重启后由于不知道当前的准确任期从而无法发起选主流程，日志中虽然记录了任期但不一定是最新的，例如某个节点的日志可以一直为空但当前任期却一直在增长；同时也可以避免将选票投给任期更低的节点，以及识别出过期的主节点。
• votedFor：在当前任期内投票的候选节点 id，可以为空，因为 Raft 规定了在某个任期内每个节点最多只能投票一次，为了避免节点投票后发生异常然后重启并继续投票，所以需要持久化。
• log[]：日志是 Raft 的核心，是状态机重放的保证，必然要持久化。每条日志包含了发给状态机的命令和主节点收到请求时的任期，日志的索引位置从1开始。

所有节点无需持久化的状态：

• commitIndex：已知目前最远已提交的日志索引（初始化为0，单调递增）。对于主节点来说，只要在重启后提交了一条新的日志（或者自己主动提交一条 no-op 日志），那么这条日志之前的日志都会被间接提交，当前日志的索引就是最新的 commitIndex；对于从节点来说，后面 AppendEntries 中会提到它会发送主节点的最远提交索引，所以没有必要持久化。
• lastApplied：已知目前最远已应用到状态机的日志索引（初始化为0，单调递增）。对于不同的服务来说，它的状态机不一定是持久化的，例如内存数据库，这样的服务在重启后需要重放所有的日志来恢复状态，所以 lastApplied 从0开始，一直重放到 commitIndex。不过对于持久化的状态机来说，虽然从0开始重放不影响，但是效率太低，持久化 lastApplied 还是有必要的。

主节点无需持久化的状态（选主后重新初始化）：

• nextIndex[]：每个从节点插入下一条日志的索引位置（初始化为主节点最后一条日志的索引位置加1）。这个在前面提到过，根据主节点初始化的值，nextIndex 的有效值可以在多次 RPC 请求之间计算出来，所以没有必要持久化，而且持久化了有可能存在过期的风险。
• matchIndex[]：每个从节点已复制的日志的最大索引位置（初始化为0，单调递增）。这个值可以结合 AppendEntries 请求计算出来，只要 AppendEntries 成功了，那么 matchIndex 就等于主节点当前日志的索引位置。同样的，持久化了也有可能存在过期的风险。

另外，某个主节点重启后不一定还能当选主节点，持久化 nextIndex 和 matchIndex 也意义不大。

AppendEntries RPC

AppendEntries 由主节点发送给从节点，用于复制日志和作为心跳探测。

参数：

• term：主节点的任期
• leaderId：主节点 id，当客户端连接上一个从节点时，从节点可以将主节点的 id 发给客户端，客户端就能和主节点建立连接
• prevLogIndex：当前要写入的日志的前一个日志的索引
• prevLogTerm：当前要写入的日志的前一个日志的任期
• entries：需要从节点复制的日志（对于心跳来说这个字段为空），从效率考虑可能会包含多条日志，因为从节点的日志可能落后于主节点或者和主节点的不一致，这时就需要补齐从节点的日志
• leaderCommit：主节点已提交的日志索引

返回：

• term：当前从节点的任期，主节点收到以后如果发现自己的任期小于从节点的任期，就说明自己是个过期的主节点，从而会转为从节点状态，并更新当前的任期
• success：如果 prevLogIndex 和 prevLogTerm 和从节点当前的日志状态匹配，则返回 true，否则返回 false；主节点收到 false 就会更新 nextIndex 并继续发送新的 prevLogIndex 和 prevLogTerm 给从节点

接受者实现：

1. 如果主节点的任期小于从节点的任期，则返回 false
2. 如果 prevLogIndex 和 prevLogTerm 和从节点当前的日志状态不匹配，则返回 false
3. 如果新添加的日志和当前某个位置的日志冲突（相同的日志索引，不同的任期），则删除该位置及其之后的日志
4. 追加所有不在从节点中的日志
5. 如果 leaderCommit 大于自身的 commitIndex，则更新 commitIndex 为 min(leaderCommit, 最后一条新的日志的索引)

RequestVote RPC

RequestVote 在选主时由候选节点发起，用于向其他节点获取选票。

参数：

• term：候选节点的任期
• candidateId：候选节点的 id，在前面提到每个节点需要持久化 votedFor，从而避免二次投票
• lastLogIndex：候选节点的最后一条日志的索引
• lastLogTerm：候选节点的最后一条日志的任期

返回：

• term：其他节点的任期，如果候选节点发现自己的任期比其他节点的小，那么根据规则它就不能成为主节点，从而退回到从节点状态，并更新当前的任期
• voteGranted：true 表示候选节点获得了一张选票，false 表示没有获得选票

接受者实现：

1. 如果候选节点的 term 小于自身的任期，则返回 voteGranted 为 false
2. 如果 votedFor 为空或者等于 candidateId，并且候选节点的日志相比自身的日志一样新或者较新，则返回 voteGranted 为 true

InstallSnapshot RPC

InstallSnapshot 由主节点发起，用于向其他从节点发送快照块（chunk）。主节点始终会按顺序发送 chunk。

参数：

• term：主节点的任期
• leaderId：主节点 id，当客户端连接上一个从节点时，从节点可以将主节点的 id 发给客户端，客户端就能和主节点建立连接
• lastIncludedIndex：快照所对应的的最后一条日志的索引，快照执行成功后，这个索引以及之前的日志就都可以被删除
• lastIncludedTerm：快照所对应的的最后一条日志的任期
• offset：当前 chunk 在整个快照数据中的偏移位置
• data[]：当前 chunk 的原始数据，起始于 offset
• done：如果当前 chunk 是最后一个则为 true，否则为 false

返回：

• term：当前从节点的任期，主节点收到以后如果发现自己的任期小于从节点的任期，就说明自己是个过期的主节点，从而会转为从节点状态，并更新当前的任期

接受者实现：

1. 如果主节点的任期小于从节点的任期，则直接返回
2. 如果当前 chunk 是第一个（offset 为0），则新建一个快照文件
3. 以 offset 为起点，将 data[] 写入文件
4. 如果 done 是 false，则继续等待下一个 chunk
5. 当所有 chunk 接受完毕后，保存快照文件，丢弃所有旧的快照文件
6. 如果 lastIncludedIndex/lastIncludedTerm 对应的日志在自身中存在，则保留 lastIncludedIndex 之后的日志并返回
7. 删除全部的日志（符合第6条情况的日志除外）
8. 将快照的内容应用到状态机中，并加载快照中的集群配置

各节点需要遵循的规则

所有节点：

• 如果 commitIndex 大于 lastApplied，则自增 lastApplied，并应用 log[lastApplied] 到状态机
• 如果某个 RPC 的请求或响应中的 term T 大于 currentTerm，则设置 currentTerm = T，并转为从节点状态

从节点：

• 响应来自候选节点和主节点的 RPC 请求
• 如果在 election timeout 期间内没有收到来自当前主节点的 AppendEntries 的请求以及候选节点的 RequestVote 的请求，则转为候选节点

候选节点：

• 由从节点转换为候选节点后，开始选主：
  • 将 currentTerm 自增
  • 给自己投票，设置 votedFor 为自己的 id
  • 重置 election timeout
  • 并行给其他节点发送 RequestVote 请求
• 如果候选节点收到了过半数的选票，则转换为主节点
• 如果候选节点收到了某个主节点的 AppendEntries 的请求（任期校验有效），则转换为从节点
• 如果在一个 election timeout 期间内没有完成选主，则回到第一步重新开始选主

主节点：

• 一旦成为主节点，就开始向其他节点发送空的 AppendEntries 请求（心跳），并在空闲时周而复始的发送，避免其他节点进入选主过程
• 如果收到来自客户端的请求，则追加一条新的日志，并在将日志应用到状态机后返回结果给客户端
• 如果最后一条日志的索引大于等于某个从节点的 nextIndex，说明从节点的日志和主节点的日志不一致，则主节点会将 [nextIndex, 当前主节点的最后一条日志的索引] 范围内的日志通过 AppendEntries 请求发给从节点：
  • 如果执行成功，则更新该从节点对应的 nextIndex 和 matchIndex
  • 如果执行失败，说明当前 nextIndex 还不是最优解，将 nextIndex 减1后继续重试
• 如果存在某个数字 N 满足 N > commitIndex，且过半数的从节点的 matchIndex >= N，以及 log[N].term 等于 currentTerm，则将 commitIndex 设置为 N。这说明 N 是实质上已提交的日志索引，但是主节点还不知道

参考

• In Search of an Understandable Consensus Algorithm (Extended Version)
• Raft: Understandable Distributed Consensus
• Students’ Guide to Raft
• 6.824 2022 Lecture 7: Raft (2)
• Raft (2) FAQ
• How does raft handle committing entries from previous one?
• Raft Q&A