阅读论文 Raft，参考 FAQ1，note1，FAQ2，note2。

概述

MapReduce 的 master、GFS 的 master 和 VM FT 的共享磁盘都存在单点故障（即使 GFS 的 master 存在副本，其依然是单点故障，因为故障时系统会停止），从而可以很简单的避免脑裂。脑裂会发生的根本原因在于，无法区分机器故障和网络分区故障。共识算法使用多数原则（仲裁协议，quorum），可以在复制的同时避免脑裂。如果集群中有 \(2f+1\) 个服务器，则共识算法可以容忍 \(f\) 个服务器故障。共识算法通常使用状态机复制，以复制日志的方式实现。客户端、服务器以及共识算法和状态机的关系见下图。

Raft 的主要设计目标是可理解性，通过分解问题和减少状态来实现。问题被分解为多个子集，例如：领导者选举、日志复制、安全性和成员变更。使用随机化超时时间、限制选举保证日志单向流动等方式，来减少状态。

实现

基础知识

服务器有三种状态：leader、follower、candidate，服务器初始时都是 follower。正常情况下，只有一个 leader 和多个 follower。只有 leader 会处理客户端的请求，如果客户端将请求发送给 follower，该 follower 会将其重定向到 leader。服务器之间使用远程过程调用（RPC）进行通信，基本的 Raft 算法使用两种 RPC，candidate 在选举时会发起 RequestVote RPC，leader 在复制日志和发送心跳时会发起 AppendEntries RPC（心跳消息是没有日志条目的 AppendEntries RPC）。Raft 保证 RPC 是幂等的。

时间被划分为任期（term），使用单调递增的连续整数表示。每个服务器都会持久存储当前任期，不同服务器的任期可能不同（由于故障）。服务器之间进行通信时会交换任期，处于旧任期的服务器会更新其任期。如果 leader 或 candidate 发现自己包含旧任期，它会成为 follower。如果服务器收到具有旧任期的请求，它会拒绝该请求。

领导者选举

如果一个 follower 在超时时间（该时间被称为选举超时，election timeout）内没有收到来自 leader 或 candidate 的有效 RPC（何为有效，参考图 2），它将递增其任期成为 candidate，开始选举新的 leader。它为自己投票，然后向集群中的其它服务器发送 RequestVote RPC。

• 如果 candidate 收到大多数服务器的投票，它会成为新的 leader，同时向其他服务器发送心跳消息，以建立其权威防止新的选举。每个服务器在给定的任期内，只能投票给一个 candidate。服务器是否投票给某个 candidate 存在限制，将在安全性中讨论。
• 如果在等待投票时，candidate 收到 leader 的 AppendEntries RPC，且 leader 的任期大于等于 candidate 的任期，那么 candidate 会成为 follower。如果 leader 的任期更小，则 candidate 会拒绝该 RPC。或者收到其他 candidate 的 RequestVote RPC，且其任期大于当前 candidate 的任期，当前 candidate 同样会成为 follower。
• 如果存在多个 candidate 使选票分裂，使得没有 candidate 可以得到大多数服务器的投票，则每个 candidate 都会超时，继续递增任期，重新开始选举。Raft 使用随机 election timeout 来确保选票分裂很少发生（避免同时超时），election timeout 是从一个固定间隔中随机选择的（例如 [150, 300] 毫秒），每个候选人在开始选举时会重新随机化 election timeout。

如果 follower 在执行完成 AppendEntries RPC 之后，回复之前发生崩溃，则 leader 会重试 RPC。如果 follower 重新上线，它会忽略重复请求中的日志条目。如果 candidate 在发送 RequestVote RPC 之后崩溃，重启之后它会重新发送 RPC，follower 会持久存储其投票的 candidate，避免在同一任期内多次投票。

为了保证系统的可用性，election timeout 存在如下要求：

其中 \(broadcastTime\) 是发送 RPC 的平均往返时间，\(electionTimeout\) 是 follower 的超时时间，\(MTBF\) 是单个服务器的平均故障间隔时间。broadcast time 应该比 election timeout 小一个数量级，防止 follower 开始不必要的选举。election timeout 应该比 MTBF 小几个数量级，这样在 leader 真正发生故障时客户端不会等待太久。

日志复制

客户端会向 leader 发送请求，请求包含由复制状态机执行的命令，leader 会将当前任期和命令作为一个条目（entry）追加到日志中（只读命令可以不记录日志，但有额外的限制，在可线性化中描述），由日志索引标识其位置。然后 leader 向其他服务器并行发送 AppendEntries RPC 以复制该条目，当大多数服务器确认复制该条目时，leader 将条目应用到其状态机（即状态机执行条目中的命令），并将执行结果返回给客户端，之后 leader 通过不断地失败重试保证剩余服务器会复制该条目。

只要创建日志条目的 leader 将其复制到大多数服务器上，该日志条目就是已提交的（committed）。注意，是创建日志条目的 leader，而不是之后的 leader，这将在安全性中讨论。Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。leader 提交其创建的日志条目时，也会提交 leader 日志中在该日志条目之前的所有日志条目，包含由之前 leader 创建的条目（会在安全性中解释原因）。leader 会跟踪其已提交日志条目的最高索引，并且在之后的 AppendEntries RPC 中包含该索引，以通知 follower 哪些日志条目已提交，之后 follower 会应用已提交的日志条目到本地状态机（按照日志顺序）。

Raft 的日志匹配（Log Matching）属性保证不同服务器之间日志的一致性：如果两个日志在同一索引位置的条目具有相同任期，则两个日志中所有小于等于该索引位置的条目都相同。如何实现该属性？leader 在给定任期只会对自己的日志进行追加，而不会覆盖。当 leader 向 follower 发送 AppendEntries RPC 时，会进行一致性检查。请求中会包含上一个条目的索引和任期，如果 follower 中对应索引的任期不同，则 follower 会拒绝该请求，回复 leader 匹配失败。如果系统正常运行，那么所有服务器上的日志都会相同。

但是当发生故障时，服务器之间的日志会产生不一致。如何处理不一致？leader 会为每个 follower 维护一个 nextIndex，表示 leader 下次向 follower 发送该索引位置的日志条目，如果 follower 拒绝 leader 的 AppendEntries RPC，则 leader 会将该 follower 对应的 nextIndex 递减，然后重试 RPC 直到 follower 和 leader 的日志完全相同（冲突条目将被删除）。整个过程表现为，递减 follower 的 nextIndex 到和 leader 日志最长相等前缀之后的一个位置，然后追加条目到 follower 直到其 nextIndex 和 leader 日志的尾后索引相等。

可以对上述算法进行优化，不是将 nextIndex 每次递减 1，而是递减整个任期，这通过在 follower 回复的信息中包含冲突条目的任期以及该任期在其日志中的第一个索引位置来实现。从而，每个冲突的任期都需要一个 AppendEntries RPC，而不是每个冲突的条目一个 RPC。为什么直接返回第一个索引位置，论文并没有描述之后该如何处理。我的理解是，其实并不是从该索引位置开始重传日志条目，因为这样可能会导致不必要的重传已提交的日志条目。在 leader 接收到冲突的任期和第一个索引之后，应该会递增该索引直到任期不同为止（之所以可以这样，是因为日志匹配属性），然后再传递该位置的日志条目。这样关于课程中提出的问题，为什么需要返回任期，而不是只返回第一个索引，也可以得到解答。

安全性

选举限制

即使日志一致，两个状态机也可能执行不同的命令序列。例如，leader 提交日志时，某个 follower 可能发生故障，如果它成为 leader，它将覆盖旧 leader 中的条目，而这些条目可能已经应用于旧 leader 的状态机上。为此 Raft 的领导者完整性（Leader Completeness）属性保证在某个任期被提交的日志条目必定会出现在更高任期的 leader 日志中，从而可以保证所有状态机执行相同的命令序列。

如何实现该属性？candidate 在发送 RequestVote RPC 时，会包含其日志信息，如果投票者的日志比 candidate 的日志更（读第四声）新，则投票者会拒绝投票。更新的定义如下：如果两个日志的最后一个条目具有不同任期，则更大任期的日志更新；否则，更长的日志更新。上述限制使得，只有包含所有已提交日志条目的 candidate 才有可能当选 leader，日志只会从 leader 流向 follower。

提交之前任期的条目

在日志复制中提到，创建日志条目的 leader 将其复制到大多数服务器上，则该日志条目就是已提交的。之所这样定义，是因为即使 leader 将之前任期的条目（不是由当前 leader 创建）复制到大多数服务器上，依然可能会被之后的 leader 覆盖（根据之前描述的日志匹配属性）。如果将其视为已提交，则会违反领导者完整性属性，导致状态机不一致。那么之前任期的条目何时视为已提交？当前任期的一个日志条目被提交时，由于日志匹配属性，之前任期的条目将会间接提交。

日志压缩

日志可能会变得很大，导致崩溃恢复需要花费很多时间重放所有日志，以及日志占用大量空间，Raft 通过使用快照来压缩日志。每个服务器会定期创建快照（通常是当日志达到固定大小时），快照中包含状态机的状态、状态对应的最后一个日志条目的索引和任期（以支持 AppendEntries PRC 的一致性检查）、当时的配置信息（用于集群成员变更）。当服务器将快照持久化之后，可以删除该快照之前的日志和之前的快照（剩余日志的索引并不会重置为从 1 开始，或许会新开一个数组从 1 开始存储，但是对外来说索引总是会加上某个偏移量）。

如果有一个严重滞后或新加入集群的 follower，它需要的日志可能已经被 leader 删除，此时 leader 需要使用 InstallSnapshot RPC 向滞后的 follower 发送快照。通常快照会比 follower 的日志更新，follower 会丢弃整个日志，使用快照替代。但是，由于重传或错误，follower 可能会收到描述其日志前缀的快照，此时仅会删除快照覆盖的日志，快照之后的日志将被保留。

为了避免在创建快照时停止操作，可以使用写时复制技术。状态机可以通过实现某种数据结构支持写时复制，或者使用操作系统的写时复制支持（例如，Linux 的 fork）来创建状态机的内存快照（作者使用该实现方式）。具体来说，Linux 的 fork 创建的子进程会共享和父进程相同的内存页面，如果父进程更新页面，则操作系统会对该页面执行写时复制。

可线性化

什么是可线性化？每个操作似乎在其调用和响应之间的某个时刻以原子的方式执行。Raft 如何实现可线性化语义？如果 leader 在执行命令之后回复客户端之前崩溃，然后客户端在新的 leader 重试请求，将会多次执行同一个命令。如果客户端向新 leader 发送读请求，由于旧 leader 在回复客户端之后发送下一个 AppendEntries RPC 之前崩溃，新 leader 可能并没有将某些已提交的命令应用到状态机，此时客户端可能会从新 leader 读取到旧数据。如果出现网络分区故障，旧 leader 可能不知道它已经被新 leader 取代，此时客户端可能从旧 leader 读取到旧数据。

首先，客户端需要为每个命令分配唯一的序列号，状态机会跟踪为每个客户端处理的最后的序列号以及相关响应。如果状态机收到已被执行的命令，它不会执行该命令而是直接返回响应。注意，日志中依然包含重复命令的日志条目。其次，每个 leader 在任期开始时会提交一个无操作日志条目，从而确定哪些日志条目已被提交并将其应用到状态机。能否通过心跳消息确定哪些日志条目已提交，个人认为不能，就是之前提到的旧任期日志条目不能通过计数判断是否已提交。最后，leader 在回复读请求之前，需要和集群中的大多数交换心跳消息，以确保它仍然是 leader（或者可以使用租约，论文中没有详细介绍，不过课程笔记中有提到具体方式）。

问题

Q：Raft 集群是部署在一个数据中心，还是多个数据中心？

A：通常是一个数据中心，这样可以避免 leader 跨数据中心向多个 follower 发送 RPC（网络延迟）。

Q：客户端如何知道谁是新的 leader？

A：客户端包含所有 server 的地址，它可以随机发送请求，follower 会将请求重定向到它认为的 leader。

Q：为什么日志的索引从 1 开始？

A：可以将其视为从 0 开始，索引 0 包含任期为 0 的空日志条目，以方便 AppendEntries RPC 在初始时的一致性检查。个人认为，类似于求数组的前缀和时从索引 1 开始。

Q：Raft 何时将其状态（currentTerm、votedFor、log）持久化到磁盘？

A：在内存中修改状态的同时刷盘，只有持久化之后 leader 才能向 follower 发送 RPC，follower 才能回复 leader，leader 才能将命令应用到状态机。否则，如果服务器发生崩溃，Raft 的各种属性将无法得到保证。

Q：图 2 中的 lastApplied 为何不需要持久化？如果发生崩溃，服务器如何知道日志条目是否应用于状态机？

A：论文作者在会话中对该问题以及下一个问题进行了解释（推荐阅读）。实际上 lastApplied 是否被持久化取决于状态机是否被持久化。如果状态机不被持久化，那么崩溃恢复之后需要重放所有日志，所以 lastApplied 会被初始化为 0。否则，只需重放 lastApplied 之后的日志。按我的理解，由于快照的存在，以及更新状态机的同时持久化产生的随机 I/O 开销较大，所以状态机一般不会实时持久化。如果存在快照，lastApplied 会被赋值为快照中包含的索引。

Q：图 2 中的 matchIndex 有什么作用？

A：matchIndex 表示 follower 和 leader 匹配的最高日志条目的索引（可能会小于实际值），只要大多数 follower 的 matchIndex 超过 leader 的 commitIndex，并且 log[matchIndex] 条目的任期是当前 leader 的任期（参见提交的定义），则 leader 可以增加 commitIndex。

Q：图 7 的 leader 崩溃之后，谁有可能成为新的 leader？

A：服务器 acd 都有可能成为新的 leader。首先日志 9 是最后一个提交的日志条目，根据领导者完整性属性，只能从 acd 中选择 leader。同时，acd 都有可能得到大多数服务器的投票，对于 a 来说是 abef，对于 c 来说是 abcef，对于 d 来说是 abcdef。有一点需要注意，服务器最后一个日志条目的任期可能并不是其当前任期。

总结

Raft 共识算法实现可线性化一致性模型，核心内容包括领导者选举、日志复制和安全性。论文中还提到 Raft 的集群成员变更机制，我并没有做介绍。然后日志压缩可以看作是 Raft 的额外补充。如课程中所述，论文中也有很多细节没有介绍，单个机制可以有多种不同的实现方式。课程视频、问答和笔记是对论文很好的补充，其中还提到一篇文章 Raft does not Guarantee Liveness in the face of Network Faults，讲述 Raft 在特定情况下无法建立稳定的领导者，除非使用 PreVote 和 CheckQuorum 技术。可见这篇论文介绍的仅仅是 Raft 的基本实现，现实中面临各种复杂场景，或许需要添加很多额外的机制。

附录

阅读论文 Fault-Tolerant Virtual Machines，参考 FAQ，note。

概述

论文使用虚拟机、机器级别的主从复制（一主一从）和共享磁盘的方式设计容错系统，目前只支持单处理器的虚拟机。

有两种复制方式，状态转移复制和状态机复制。状态转移复制是将主节点的所有状态复制到从节点；而状态机复制要求节点是一个确定性状态机，不同节点从同一个状态以相同的顺序执行操作，可以得到相同的结果。

比较有意思的是，不像我所了解的常规数据复制，论文实现的系统使用机器级别的复制，状态包含 CPU、内存和 I/O 设备的状态，操作是 x86 指令。在机器级别上，状态转移复制的缺点是会将所有状态的更改通过网络进行传输，发送状态需要很多带宽；状态机复制使用更少的网络带宽，但是需要特殊处理非确定性操作（例如：获取时间、定时中断）来保证主从一致，这在物理服务器上很难实现，特别是当处理器频率增加时。

PS：时间是非确定的很好理解，但是定时中断为什么是非确定的，我的想法是虽然主从的状态是一致的（如果没有中断），但是执行速度也不是完全一致，所以中断的时机可能不同。

论文设计的系统使用状态机复制，利用虚拟机（VM）由虚拟机管理程序完全控制的特性，当主虚拟机执行非确定性操作时，虚拟机管理程序可以捕获必要的信息发送给从虚拟机，将非确定性操作转化为确定性操作，从而保证主从一致。只支持单处理器虚拟机，因为多处理器产生的并发操作是非确定性的，存在显著的性能问题。

主从虚拟机运行在不同的服务器上，从虚拟机和主虚拟机以相同的方式运行，并且总是有较小的延迟（小于 100 毫秒），课程讲义提到至少滞后一个日志项。只有主虚拟机在网络上发布其存在，输入（例如：网络、磁盘、键盘、鼠标）只会发送给主虚拟机，主虚拟机通过网络连接（称为日志通道，logging channel）将其转发给从虚拟机。同时，只有主虚拟机会产生输出，从虚拟机的输出将被虚拟机管理程序丢弃。

确定性重放

VMware FT 使用确定性重放，使从虚拟机能够通过重放日志达到和主虚拟机相同的状态。具体来说，主虚拟机的输入和非确定性操作都会被虚拟机管理程序捕获，然后生成日志（不会写入磁盘），发送给从虚拟机。对于非确定性操作，日志会记录必要的信息，保证主从一致。例如，对于中断操作，日志会记录操作发生时所完成的指令数量。论文提到该技术的实现有使用硬件性能计数器（HPC）。

特别注意，日志仅包含输入和非确定性操作相关的信息，确定性操作在从虚拟机的本地执行。具体来说，主虚拟机和从虚拟机都是状态机，会自动执行操作（由 VM 中的 Linux 和 App 发起，这也说明了为什么主从虚拟机的初始状态必须相同），只不过输入只会发送给主虚拟机，以及存在非确定性操作，所以输入和非确定性操作需要以日志的形式包含额外信息发送给从虚拟机。

容错协议

但是仅使用确定性重放还不够，需要额外的机制保证系统的容错性。如果主虚拟机在执行输出操作之后发生故障，而日志没有发送给从虚拟机，那么从虚拟机接管之后，在其输出之前的非确定性操作（未收到日志的）可能会得到不同的输出结果，从而产生不一致（不一致主要是针对客户端的感知而言）。

解决方案是在主虚拟机发送输出之前，向从虚拟机发送输出操作的日志并等待其确认，当从虚拟机接收到该输出操作及之前的所有日志之后，从虚拟机回复一个确认，然后主虚拟机可以向外部发送输出。注意，主虚拟机只是延迟发送输出，但是没有停止执行（即在等待输出的同时会继续执行其他操作，就像在某个线程等待磁盘 I/O 时会切换到其他线程一样）。该机制在主虚拟机发生故障时，可能会产生两次相同的输出，因为从虚拟机无法得知主虚拟机是否发送输出，但是论文随后提到 TCP 可以保证网络数据包的去重（我的理解是 TCP 是根据序列号去重的，由于主从虚拟机状态相同，所以会产生相同的序列号）。

故障检测和恢复

系统通过监控节点的心跳（使用 UDP），以及日志通道上的流量来判断节点是否发生故障（使用定时中断，保证流量不会停止）。

• 从虚拟机故障：主虚拟机继续执行，但是停止发送日志。
• 主虚拟机故障：从虚拟机重放日志以追赶主虚拟机，然后将从虚拟机提升为主虚拟机。VMware FT 会在网络上发布新的主虚拟机的 MAC 地址，以便交换机知道其位于哪个服务器上。
• 网络分区故障：主虚拟机可能由于网络问题和从虚拟机中断连接，如果此时将从虚拟机提升为主虚拟机，将会导致脑裂。为避免该问题，容错协议要求在检测到故障时，主从虚拟机需要在共享磁盘上执行 test-and-set 原子操作。操作成功的虚拟机作为主虚拟机存活，操作失败的虚拟机会自行中止。

不论是启动系统时，还是故障恢复时，都需要保证存在一个从虚拟机。VMware FT 使用 FT VMotion 功能，将虚拟机复制到集群中的某个服务器上（根据资源使用情况和其他约束条件选择）。该功能会建立从源虚拟机到目标虚拟机的日志通道，并且将源虚拟机设置为主虚拟机（记录日志模式），目标虚拟机设置为从虚拟机（重放日志模式）。该功能仅会中断源虚拟机小于 1 秒的时间，在复制的过程中源虚拟机仍会正常执行，日志会被存放在缓冲区中。

总结

论文介绍容错虚拟机的实现，还提到磁盘 I/O 和网络问题及其解决方案，不同设计的决策以及对各个负载的性能测试，详情参见论文。PS：课程讲义很不错，可以加深对论文内容的理解，我的理解还是太浅。

阅读论文 GFS，参考 FAQ，note。

概念

GFS 是一个分布式文件系统，用于大型分布式数据密集型应用程序，例如 MapReduce。系统的设计基于以下场景：

• 系统由许多机器组成，所以会频繁发生故障。
• GB 级别的文件很多，普通文件系统会将文件划分为很多块，不便管理。
• 读负载由大量顺序读和少量随机读组成，写负载由大量追加写和少量随机写组成。
• 高持续带宽比低延迟更重要，应用程序需要快速进行批处理，而对响应时间没有严格要求。

实现

GFS 集群由单个 master 和多个 chunkserver 组成，由多个客户端访问。文件被划分为 64 MB 的块（chunk），每个块都是 chunkserver 中的一个文件。在分配空间时使用懒分配策略，避免产生内部碎片从而浪费空间。master 在创建块时，会为其分配一个不可变且全局唯一的 64 位块句柄（chunk handle）。每个块都会被复制到多个 chunkserver 上（默认三个），以保证系统的可靠性。

master 主要负责维护系统的元数据、存储日志和检查点、租约管理以及控制垃圾收集、重新复制、负载均衡和快照创建。元数据包括命名空间、访问控制信息、从文件名到块句柄数组的映射，以及为每个块维护版本号和副本所在 chunkserver 的列表。master 通过心跳消息定期与 chunkserver 通信，向其发出指令和收集其状态。chunkserver 主要负责存储文件数据、版本号和校验和，64 MB 的 chunk 被划分为 64 KB 的 block，每个 block 都有一个 32 位的校验和。

链接到应用程序的 GFS 客户端代码实现文件系统 API，通过与 master 和 chunkserver 通信来代表应用程序读写数据。客户端从 master 获取元数据，从 chunkserver 获取文件数据。客户端不需要缓存文件数据（但会缓存元数据），因为负载通常是顺序读和追加写。客户端没有实现 POSIX API，因此不需要挂钩到 Linux vnode 层。PS：我没有查到 Linux vnode 相关的资料，vnode 似乎是 BSD 中的概念，和 VFS 有关。

块大小

Linux 文件系统的默认块大小为 4 KB，GFS 使用 64 MB 的块大小是基于其 GB 级文件场景而设计的，优势如下：

• 由于应用程序通常是顺序读写文件数据，所以 64 MB 的块大小可以减少客户端和 master 的交互次数。
• 许多操作会发生在同一个块中，使得客户端和 chunkserver 保持长 TCP 连接，有利于减少网络开销。
• master 中的元数据更少，从而可以全部放入内存，避免磁盘 I/O。

同时，论文提到小文件可能只有一个块，面对多个应用程序的访问，存储该块的 chunkserver 有可能成为热点。GFS 的解决方案是使用更高的复制因子存储小文件，同时使批处理队列系统错开应用程序访问小文件的时间。潜在的解决方案是允许客户端在该情况下从其他客户端读取数据。

元数据

命名空间和映射会以操作日志（operation log）的形式持久化到 master 的本地磁盘和复制到远程机器，保证 master 能够在崩溃之后恢复。为保证一致性，只有在本地和远程将相应的日志刷新到磁盘之后，master 才会响应客户端的操作。可以对刷新和复制批处理，从而减少开销。当日志超过一定大小时，会创建检查点（使用 B 树），从而避免崩溃恢复时重放所有日志。由于创建检查点比较耗时，master 会切换到新的日志文件，并在单独的线程中创建检查点，以避免在创建检查点时停止执行（写）操作。检查点同样也会被复制到远程机器。

master 不会持久化块的位置列表，而是在启动时以及 chunkserver 加入集群时，向 chunkserver 询问其包含的块。因为块是否存在于某个 chunkserver 是由该 chunkserver 决定的，所以在 master 中持久化该信息没有任何意义，反而会面临同步问题。PS：说明 master 内存中的位置列表可能因为 chunkserver 故障，从而产生不一致。

命名空间其实就是一个将目录名和文件名作为节点的树，通过使用读写锁保证写操作的正确性。具体来说，读/写操作会获取路径上所有祖先节点的读锁，以及目标节点的读/写锁。锁在层级间按照自顶向下的顺序获取，在层级内按照字典序获取，从而避免死锁。PS：这让我想到 B+ 树的蟹行协议只锁定会被修改的节点，大概是因为 B+ 树的数据和路径不像文件和路径那样具有很强的关联性。

读操作

客户端使用固定的块大小，将应用程序指定的文件名和字节偏移量转换为文件内的块索引。然后，它向 master 发送包含文件名和块索引的请求，master 回复相应的块句柄（handle）、副本的位置列表，客户端使用文件名和块索引作为键来缓存该信息（会有过期时间）。

然后，客户端选择其中一个副本发送请求（很可能是距离最近的副本），该请求指定块句柄和块内字节范围。在缓存信息过期或重新打开文件之前，客户端不需要和 master 进行交互。客户端可以在向 master 发送的一个请求中请求多个块，master 也可以在回复中包含请求块之后的多个块信息（利用空间局部性），从而减少客户端和 master 交互的次数。

写操作

在发生写操作时，需要保证多个副本之间的一致性。GFS 使用租约（lease）实现一致性（租约是按块授予的），持有租约的 chunkserver 被称为 primary，其他包含副本的 chunkserver 被称为 secondary。租约的超时时间为 60 秒，primary 可以根据需要续约，续约请求包含在定期的心跳消息中发送给 master，master 也可以在租约到期之前撤销租约（用于快照创建）。如果 master 和 primary 发生网络分区故障，master 可以在旧租约到期之后向另一个副本授予租约，从而避免脑裂。

写操作的流程如下：

• 客户端首先向 master 询问 primary 和 secondary 的位置并将其缓存。如果 primary 不存在，则 master 任选一个包含副本的 chunkserver 授予租约。客户端会缓存位置信息，当 primary 不可达或者回复其租约过期时，客户端会重新联系 master。然后，客户端以流水线的方式将数据发送到 primary 和 secondary（存储在缓冲区中），并且等待它们的确认响应。
• 客户端收到所有副本的确认之后，向 primary 发送写请求，该请求会使用之前发送的数据。primary 为其收到的来自多个客户端的请求分配序列号（单个客户端的请求肯定是同步的，在收到响应之前不会发送第二个请求，因为 GFS 没法保证客户端请求的 FIFO 顺序），只有当 primary 本地执行成功之后，才会转发给所有 secondary，请求在所有副本上都按照序列号的顺序执行。当 primary 收到所有 secondary 的完成响应时，primary 回复客户端完成。
• 论文提到，副本的任何错误都会被报告给客户端，客户端会首先从步骤三开始重试几次，然后从步骤一开始重试。论文有一个前后矛盾的点，首先提到 primary 分配序列号然后应用到本地，之后又说如果在 primary 执行失败就不会分配序列号和转发。不过无关紧要。

一致性模型

GFS 具有宽松的一致性模型，数据突变之后文件区域的状态，取决于突变的类型（随机写和追加写）以及是否存在并发，如下图所示。如果无论客户端从哪个副本读取，始终看到相同的数据，则文件区域是一致的。如果文件区域一致，且客户端将会看到整个突变的内容，则文件区域是定义的。PS：这里的一致并不是严格一致性（可线性化）。

随机写：顺序突变成功状态是定义的和一致的；并发突变成功状态是一致的但是未定义，因为 GFS 使用租约保证突变以相同的顺序应用到所有副本（一致的），但是突变没有对文件区域加锁（未定义）。

追加写：不论是顺序还是并发突变成功，状态都是定义的，因为追加是原子操作且按照指定顺序应用到所有副本。只要有一个副本追加失败，客户端会重试整个追加操作，使得在未失败的机器上多次追加相同的数据，在失败的机器上填充无效的数据（因为追加会指定偏移量），从而产生不一致。特别的，追加的偏移量由 primary 指定，而不是单纯的追加到文件末尾，这可以保证多个副本在成功执行追加的偏移位置的数据是一致的，即使之前发生过失败。也就是说，中间区域不一致，最后区域一致。

此外，失败的突变总是会导致不一致。即使突变成功，数据最终一致，客户端仍可能观察到不一致，因为数据可以从任何包含副本的 chunkserver 读取。假设突变由客户端 A 发起，首先应用到 primary，再发送到 secondary。客户端 B 和 C 在突变过程中分别读取 primary 和 secondary，可以观察到不一致的情况。如果突变很慢，由于网络延迟或故障重试，单个客户端也可以观察到不一致。应用程序需要自行适应 GFS 的宽松一致性模型。

版本检测

如果 chunkserver 发生故障，从而错过突变，其上的块副本将会过时。master 和 chunkserver 会为块维护一个版本号，以此来区分新副本和旧副本。当 master 授予某个块租约时，它会递增该块的版本号，同时和 chunkserver 通信来递增最新副本的版本号。任何包含旧副本的 chunkserver 都不会返回给客户端，master 会在心跳检测中检查副本的版本，然后 master 会指示 chunkserver 对旧副本垃圾收集。作为额外的保护措施，master 会在回复客户端请求或指示 chunkserver 复制时包含版本号，客户端和 chunkserver 会在执行操作时进行验证。

故障处理

master 故障

当 master 发生故障时，GFS 的外部监控基础设施会使用检查点和日志快速恢复，即使磁盘发生故障也可以在其他机器上使用检查点和日志的副本进行恢复。客户端仅使用 DNS 别名访问 master（CNAME），其映射可以随时更改，以适应 master 机器的变更。此外，GFS 使用 shadow master 在 master 故障时提供对文件系统的只读访问，shadow master 略微滞后于 master。由于它存储的是元数据，文件数据存储在 chunkserver 中，所以客户端实际上不会读取到旧数据。

PS：论文提到 shadow master 会按顺序执行操作日志的副本，似乎 master 和 shadow master 的关系就是主从复制，但是为什么 shadow master 只提供只读访问，即使在 master 故障之后。它和 master 应该是最终一致的，为什么论文没有说 shadow master 在执行完所有日志之后会被提升为 master，虽然可以肯定需要人工操作，以避免原 master 只是网络分区故障，从而导致脑裂。

chunkserver 故障

master 使用心跳消息判断 chunkserver 是否存活，如果 master 判断 chunkserver 故障，它会指示其他 chunkserver 对不满足复制因子的数据块重新复制。当故障的 chunkserver 上线时，master 也会删除多余的副本，以及因错过突变而过时的副本。

其他功能

使用写时复制实现快照功能；跨机架的块放置策略；根据服务器的负载进行块放置和块迁移；根据优先级重新复制块以恢复冗余；延迟删除和垃圾收集；使用校验和检测数据块是否损坏；生成诊断日志（包含 chunkserver 的启动/关闭，RPC 的请求/回复记录，不包括文件数据）。

问题

Q：租约具体是如何工作的，master 和 chunkserver 如何判断租约是否过期？如何撤销租约？

A：论文没有说明，我猜测：master 首先发送授予租约的请求，chunkserver 收到请求之后开始计时，同时发送响应给 master，master 收到响应之后开始计时。这样 chunkserver 和 master 都可以判断租约是否到期，以及 master 的计时总是晚于 chunkserver，可以保证避免脑裂。撤销租约只修改 master 本地元数据肯定是不行的，因为客户端可能正在和持有租约的 chunkserver 通信，master 必须直接向 primary 发送撤销请求。

Q：根据上述猜测，如果授予租约的响应丢失，master 该如何处理？是否需要考虑时钟同步问题？

A：如果 master 没有收到响应，它就不会把该 chunkserver 记作 primary 返回给客户端，那么该租约实际上是一个无效租约，master 可以重试或者另选一个包含副本的 chunkserver。计算超时使用的是单调时钟，不需要同步。也可以使用时间戳判断租约是否到期，但是使用的是墙上时钟，需要服务器之间时钟同步。

总结

GFS 使用复制进行容错，从而引入多个副本间的一致性问题。但是仅保证宽松的一致性，而将问题交由应用程序处理，该设计基于其特殊的使用场景，顺序读写以及用于批处理，似乎强一致性显得不是很重要。可以查看课程的笔记和问答加深对论文的理解，笔记结尾的优缺点总结还是很不错的，有一个全局的视角，我有点过于关注一致性了。更多关于 GFS 的讨论，可以阅读 GFS: Evolution on Fast-forward。