MIT6.824学习笔记（三） -- GFS

• 1. 背景
• 2. GFS论文
  • 2.1. 引言
  • 2.2. 整体架构
  • 2.3. 读操作简要流程
  • 2.4. 系统交互
    • 2.4.1. 租约
    • 2.4.2. 写操作简要流程
    • 2.4.3. record append原子操作
    • 2.4.4. 快照
  • 2.5. master操作
    • 2.5.1. 命名空间管理和锁
    • 2.5.2. 副本分配
    • 2.5.3. chunk创建、重做副本、重均衡
    • 2.5.4. 垃圾回收
    • 2.5.5. 陈旧副本检测
  • 2.6. 容错和诊断
  • 2.7. 其他
  • 2.8. 结论
• 3. 课程笔记
  • 3.1. 设计分布式存储的难点
  • 3.2. 讲解GFS
    • 3.2.1. 一些设计特征
    • 3.2.2. 论文发表的背景
    • 3.2.3. GFS Master节点
    • 3.2.4. 读写流程相关说明
    • 3.2.5. 一致性说明
• 4. 小结
• 5. 参考

MIT6.824（2020）学习笔记，Lecture 3 - GFS。

1. 背景

MIT6.824（2020）学习，本篇继续学习：Lecture 3 - GFS。

说明：本博客作为个人学习实践笔记，可供参考但非系统教程，可能存在错误或遗漏，欢迎指正。若需系统学习，建议参考原链接。

2. GFS论文

论文和找的中文翻译，两者结合看下（部分翻译处还是要对比下英文原文）：

• GFS论文
• 《The Google File System》论文翻译（GFS-SOSP2003）

下面只做部分学习笔记，细节还是要看论文内容，常需要回头看上面参考链接的论文内容。

2.1. 引言

GFS（Google File System）在2003年提出，是由Google设计并实现的为大规模分布式数据密集型应用程序设计的可伸缩（scalable）的分布式文件系统。

GFS为在廉价商用设备上运行提供了容错能力，并可以在有大量客户端的情况下提供较高的整体性能。

Google碰到的问题和设计探索：

• 1、设备故障经常发生，系统必须具有持续监控、错误检测、容错与自动恢复的能力
  • 故障包括：应用程序bug、操作系统bug、人为错误和硬盘、内存、插头、网络、电源等设备故障
• 2、文件比传统标准更大，数GB大小的文件十分常见，数据集由数十亿个、总计数TB的对象组成，并且还在快速增长，管理数十亿个几KB大小的文件是非常不明智的。因此需要重新考虑像I/O操作和block大小等设计和参数。
• 3、实际场景中，大部分文件会以“追加”（append）的方式变更（mutate），而非“覆盖写”（overwrite）
• 4、应用程序和文件系统API两者同时设计便于提高整个系统的灵活性。
  • 例如，我们放宽了GFS的一致性协议，从而大幅简化了系统，减少了应用程序的负担
  • 我们还引入了一种在不需要额外同步操作的条件下，允许多个客户端并发将数据追加到同一个文件的原子性操作

2.2. 整体架构

架构设计基于的假设：

• 系统有许多可能经常发生故障的廉价的商用设备组成
• 系统存储一定数量的大文件（此处>100MB左右）
• 系统负载主要来自两种读操作：大规模的流式读取（几百KB、1MB或更多）和小规模的随机读取（几KB）
• 系统负载还来自很多对文件的大规模追加写入
• 系统必须良好地定义并实现多个客户端并发向同一个文件追加数据的语义
• 持续的高吞吐比低延迟更重要。我们的大多数应用程序更重视高速率处理大量数据，而很少有应用程序对单个读写操作有严格的响应时间的需求。

整体架构：

整体架构如下图所示，一个GFS集群包括单个master（主服务器）和多个chunkserver（块服务器），并被多个client（客户端）访问。每个节点通常为一个运行着用户级服务进程的Linux主机。如果资源允许且可以接受不稳定的应用程序代码所带来的低可靠性，那么可以轻松地在一台机器上同时运行chunkserver和client。

GFS架构图：

文件和chunk划分：

• 文件被划分为若干个固定大小的chunk（块）。每个chunk被一个不可变的全局唯一的64位chunk handle（块标识符）唯一标识，chunk handle在chunk被创建时由主节点分配。
• chunkserver将chunk作为Linux文件存储到本地磁盘中，通过chunk handle和byte range（字节范围）来确定需要被读写的chunk和chunk中的数据。
• 为了可靠性考虑，每个chunk会在多个chunkserver中有副本。我们默认存储三份副本，用户也可以为不同的命名空间的域指定不同的副本级别。
• chunk大小是关键的设计参数之一。GFS选择了64MB，其远大于通常的文件系统的块大小。选择较大的chunk大小提供了很多重要的优势。
  • 减少了client与master交互的次数，因为对一个chunk的读写仅需要与master通信一次以请求其位置信息
  • 因为chunk较大，client更有可能在一个chunk上执行更多的操作，这可以通过与chunkserver保持更长时间的TCP连接来减少网络开销
  • 减少了master中保存的元数据大小

master和元数据：

• GFS采用单master节点，大大简化了设计。并需最小化master节点在读写中的参与，以避免其成为系统瓶颈。
  • client不会直接从master读取文件数据，而是询问master它需要与哪个chunkserver通信
  • client会在一定时间内缓存信息，并直接与对应的chunkserver通信以完成后续操作。
• master维护系统所有的元数据。元数据包括文件和chunk的命名空间（namespace）、文件到chunk的映射和chunk每个副本的位置这3种，此外还有访问控制（access control）信息。
  • 所有元数据被存储在master的内存中。
  • 前两种类型（命名空间和映射），还通过将变更（mutation）记录到一个操作日志（operation log）的方式持久化存储在master的磁盘上，并在远程机器上备份。
  • 通过日志(operation log)，我们可以简单、可靠地更新master的状态，即使master故障也没有数据不一致的风险。
  • master不会持久化存储chunk的位置信息，而是在启动时和当chunkserver加入集群时向chunkserver询问其存储的chunk信息。
• master还控制系统级活动如chunk租约（chunk lease）管理、孤儿chunk垃圾回收（garbage collection of orphaned chunks）和chunkserver间的chunk迁移（migration）。master周期性地通过心跳（HeartBeat）消息与每个chunkserver通信，向其下达指令并采集其状态信息。

master通过 重放（replay）操作日志(operation log)来恢复其文件系统的状态。操作日志要尽可能小以减少启动时间。当日志超过一定大小时，master会对其状态创建一个检查点（checkpoint），这样master就可以从磁盘加载最后一个检查点并重放该检查点后的日志来恢复状态。

检查点的结构为一个紧凑的B树（B-tree）这样它就可以在内存中被直接映射，且在查找命名空间时不需要进行额外的解析。这进一步提高了恢复速度，并增强了系统的可用性。

GFS client：

• 被链接到应用程序中的GFS client的代码实现了文件系统API，并与master和chunkserver通信，代表应用程序来读写数据。
• 进行元数据操作时，client与master交互。而所有的数据交互直接由client与chunkserver间进行。GFS不提供POXIS API，因此不会陷入到Linux vnode层（这里的vnode是抽象概念，对于Linux可以理解成inode和dentry）。

缓存说明：

• 无论client还是chunkserver都不需要缓存文件数据（元数据另说）。
• 在client中，因为大部分应用程序需要流式地处理大文件或者数据集过大以至于无法缓存，所以缓存几乎无用武之地。不使用缓存就消除了缓存一致性问题，简化了client和整个系统。（当然，client需要缓存元数据）
• chunkserver中的chunk被作为本地文件存储，Linux系统已经在内存中对经常访问的数据在缓冲区缓存，因此也不需要额外地缓存文件数据。

一致性模型：

GFS宽松的一致性模型(relaxed consistency model)可以很好地支持我们的高度分布式应用程序，且实现起来简单高效。

文件命名空间的变更（例如创建文件）操作是原子性的。它们仅由master处理。命名空间锁保证了原子性和正确性；master的操作日志定义了这些操作的全局总顺序。

文件区域（file region）的一致性状态有下面几种：

• consistent（一致的）：如果一个文件区域的任意一个副本被任何client读取总能得到相同的数据，那么这个文件区域状态为consistent（一致的）
• defined（确定的）：在一个文件区域的数据变更后，如果它是一致的，且client总能看到其写入的内容，那么这个文件区域的状态为defined（确定的）
  • defined状态包含了consistent状态
• consistent but undefined（一致的但非确定的）：文件区域在并发变更执行后的状态为consistent but undefined（一致的但非确定的）
  • 所有客户端能看到同样的数据，但数据可能并不反映任何一个变更写入的数据。

通常，数据融合了多个变更的内容。文件区域在一个失败的变更后状态会变为inconsistent（不一致的）（且undefined）：不同client在不同时刻可能看到不同的数据。

2.3. 读操作简要流程

结合上述架构图，说明下“读”操作的流程：

1. 首先，通过固定的chunk大小，client将应用程序指定的文件名和chunk偏移量翻译为该文件中的chunk index（块序号）
2. 然后，client向master发送一个包含了文件名和chunk index的请求
3. master会返回其相应的chunk handle和副本所在的位置
4. client将这个信息以文件名和chunk index为键进行缓存
5. client接着向一个副本（最有可能是拓扑中最近的一个副本）发送请求。请求中指定了chunk handle和byte range。
6. 之后，client再次读取相同的chunk时不再需要与master交互，直到缓存过期或文件被重新打开

事实上，client通常会在同一个请求中请求多个chunk，master也可以返回包含多个chunk的响应。这种方式避免了client与master进一步的通信，在几乎不需要额外开销的情况下得到更多的信息。

2.4. 系统交互

2.4.1. 租约

改变chunk或元数据的操作被称为“变更”，如write或append，chunk变更时，其每个副本都会应用变更。

GFS使用租约（lease）来维护副本间变更顺序的一致性。

chunk变更时，master向其中一个副本授权一个变更的租约，该副本称为 primary（有时也代指primary副本所在的chunkserver）。

primary为该chunk的其他副本来应用变更。这种租约机制是为了最小化master的负载设计的。

2.4.2. 写操作简要流程

上面说明了读操作的流程，这里讲下写操作流程。

先看下write操作的控制和数据流示意图：

下面对上图的write各步骤进行说明（编号一一对应）：

1. 客户端向master询问哪个chunkserver持有指定chunk的租约和该chunk其他副本的位置。若没有chunkserver持有租约，则master选择一个副本对其授权租约
2. master返回该chunk对应的各副本位置，包含primary副本和其他副本（secondary）。client为后续的变更缓存这些信息。
3. client将数据推送到所有副本。每个chunkserver都会将数据在内部的LRU中缓存，直到数据被使用或缓存老化失效（age out）。
   • 如上图中所示，控制流和数据流是解耦的。在控制流从client向primary再向所有secondary推送的同时，数据流沿着一条精心挑选的chunkserver链以流水线的方式线性推送（链式传给离它最近的chunkserver）。
   • 即数据流的推送并不是client将数据推送多份。每台机器会将数据传递给在网络拓扑中最近的且还没有收到数据的机器。基于网络拓扑技术来提高数据流传输性能，与哪台chunkserver是primary无关。
   • GFS会通过 流水线的方式基于TCP连接传输数据，以最小化时延。当chunkserver收到一部分数据时，它会立刻开始将数据传递给其他chunkserver。由于交换网络是全双工的，发送数据不会减少接受数据的速度，，所以流水线可以大幅减少时延。
4. 一旦所有副本都确认收到了数据，client会向primary发送一个write请求。
   • 这个请求标识了之前推送到所有副本的数据的作用。
   • primary会为其收到的所有的变更分配连续的编号，这一步提供了重要的顺序，primary按照该顺序对本地应用该变更。
5. primary将write请求继续传递给其他secondary副本。每个secondary副本都按照primary分配的顺序来应用变更。
6. 所有的secondary副本通知primary其完成了变更操作。
7. primary回复client。
   • 任意副本遇到的任何错误都会被报告给client。错误发生时，write操作可能在primary或部分secondary子集中已经被成功执行了（如果primary中发生错误，则不会分配顺序，也不会继续传递下发给其他副本）
   • 只要错误发生，该请求都会被认为是失败的，且被修改的区域的状态为inconsistent
   • client中的代码会通过重试失败的变更来处理这种错误。首先它会重试几次步骤（3）到步骤（7），如果还没有成功，再从write请求的初始操作开始重试。

如果应用程序发出的一次write请求过大或跨多个chunk，GFS的client代码会将其拆分成多个write操作。

2.4.3. record append原子操作

GFS提供了一种叫做record append的原子性append操作。在record append中，client仅需指定待追加的数据。GFS会为其选择一个偏移量，在该偏移量处至少一次地、原子性地将数据作为一个连续的字节序列追加到文件，并将该偏移量返回给client。这很像Unix系统中，在不存在多writer并发写入带来的竞态条件下，写入以O_APPEND模式打开的文件的情况。

record append是变更的一种，也遵循上述write写的控制流，仅在primary端稍有点额外的逻辑。在client将数据推送到所有副本的最后一个chunk之后，client会向primary发送一个请求。primary会检查当新记录追加到该chunk之后，是否会导致该chunk超过最大的chunk大小限制（64MB）。如果会超出chunk大小限制，primary会将该chunk填充到最大的大小，并通知secondary也做相同的操作，再回复客户端，使其在下一个chunk上重试该操作。

record append操作限制了每次最多写入最大chunk大小的四分之一的数据，以保证在最坏的情况下产生的碎片在可接受的范围内。

2.4.4. 快照

快照操作几乎会在瞬间对一个文件或一个目录树（被称为源）完成拷贝，同时能够尽可能少地打断正在执行的变更。

用户使用快照操作来快速地对一个庞大的数据集的一个分支进行拷贝（或对其拷贝再进行拷贝等等），或者在变更前对当前状态创建检查点(checkpoint)，这样就可以轻松地提交或回滚该变更。

基于写时复制技术来实现快照。

• 当master收到快照请求的时候，它首先会撤销快照涉及到的文件的chunk上所有未完成的租约。这确保了对这些chunk在后续的写入时都需要与master交互以查找租约的持有者。
• 在租约被收回或过期后，master会将快照操作记录到日志中，并写入到磁盘。
• 随后，master会通过在内存中创建一个源文件或源目录树的元数据的副本的方式来进行快照操作。新创建的快照文件与源文件指向相同的chunk。

快照操作后，说明下对应的write操作。下面以chunk C为例（注意C和C'有区别）：

1. 在快照操作后，首次想要对chunk C进行write操作的client会向master发送一个请求以找到当前的租约持有者。
2. master会检测到chunk C的引用数超过1个，并会推迟对client的响应，且选取一个新的chunk handler C'
3. 接着，master请求每个当前持有chunk C副本的chunkserver去创建一个新chunk C'。通过在与源chunk相同的chunkserver上创建新chunk，可以保证数据只在本地拷贝，而不会通过网络拷贝。
4. 在这之后，请求的处理逻辑就与处理任何其他chunk的请求一样了：master向新chunk C'的一个副本授权租约并将其响应client的请求。
5. 这样，client就可以像平常一样对chunk进行write操作，且client并不知道这个chunk是刚刚从一个已有的chunk创建来的。

2.5. master操作

master执行所有命名空间操作。除此之外，master还管理整个系统中chunk的副本：master做chunk分配（placement）决策、创建新chunk与副本、协调各种系统范围的活动以保持chunk副本数饱和、平衡所有chunkserver的负载并回收未使用的存储。

2.5.1. 命名空间管理和锁

• GFS在逻辑上用一个完整路径名到元数据的查找表来表示命名空间。通过前缀压缩技术，这个查找表可在内存中高效地表示。
• 在命名空间树上的每个节点（既可能是一个文件的绝对路径名，也可能是一个目录的绝对路径名）都有一个与之关联的读写锁（read-write lock）
• master的每个操作执行前都会请求一系列的锁。如果master的操作包含命名空间/d1/d2/…/dn/leaf，master会在目录/d1、/d1/d2，…，/d1/d2/…/dn上请求读取锁，并在完整路径名/d1/d2/…/dn/leaf上请求读取锁或写入锁
• 快照操作时，如果有文件创建操作，由于加锁冲突，两个操作会保证串行。
• 这种锁机制提供了一个非常好的性质：允许在同一目录下并发地执行变更。例如，在同一目录下的多个文件创建操作可以并发执行：每个文件创建操作都获取其父目录的读取锁与被创建的文件的写入锁。目录名上的读取锁足够防止其被删除、重命名或快照。文件名上的写入锁可以防止相同同名文件被创建两次。此外，为了防止死锁，锁的获取顺序总是一致的：首先按照命名空间树中的层级排序，在同一层级内按照字典顺序排序。

2.5.2. 副本分配

• chunk副本分配策略有两个目标：最大化数据可靠性和可用性、最大化网络带宽的利用。
• GFS在机架间分散chunk的副本。这样可以保证整个机架异常时，chunk的一些副本仍然存在并保持可用状态；同时对chunk的流量（尤其是读流量）可以充分利用各个机架的网络带宽。
  • 而另一方面，写流量必须流经多个机架，这是设计上做出的权衡（tradeoff）。

2.5.3. chunk创建、重做副本、重均衡

chunk副本的创建可能由三个原因引起：chunk创建、重做副本（re-replication）和重均衡（rebalancing）。

chunk创建（chunk creation）：

创建chunk时需要选择空副本的位置，位置的选择会考虑很多因素：

• 我们希望在磁盘利用率低于平均值的chunkserver上放置副本，随着时间推移，这样将平衡chunkserver间的磁盘利用率。
• 我们希望限制每台chunkserver上最近创建的chunk的数量。尽管创建chunk本身的开销很小，但是master还要会可靠的预测即将到来的大量的写入流量。
• 另外，按上面讨论的副本分配原则，我们希望将chunk的副本跨机架分散。

重做副本（re-replication）：

当chunk可用的副本数少于用户设定的目标值时，master会重做副本（re-replication）。每个需要重做副本的chunk会参考一些因素按照优先级排序，比如副本数量离目标数量多的优先、非删除状态的文件chunk优先、被阻塞的client对应的chunk优先等。

master选取优先级最高的chunk，并向若干chunkserver发送命令让其直接从一个存在且合法的副本来拷贝这个chunk的数据。新副本位置的选取与创建新chunk时位置选取的目标类似：均衡磁盘空间利用率、限制在单个chunkserver上活动的克隆操作数、在机架间分散副本。

重均衡（rebalancing）：

每隔一段时间master会对副本进行重均衡：master会检测当前的副本分布并移动副本位置，使磁盘空间和负载更加均衡。

在这个过程中，master会逐渐填充一个新的chunkserver，而不会立刻让来自新chunk的高负荷的写入流量压垮新的chunkserver。新副本放置位置的选择方法与我们上文中讨论过的类似。

此外，master必须删除一个已有副本。通常，master会选择删除空闲磁盘空间低于平均的chunkserver上的副本，以均衡磁盘空间的使用。

2.5.4. 垃圾回收

在文件被删除后，GFS不会立刻回收可用的物理存储空间。master仅在周期性执行懒式垃圾回收（lazily garbage collection）时回收物理存储空间，其中垃圾回收分为文件级垃圾回收和chunk级垃圾回收。

• 当一个文件被应用程序删除时，master会像执行其他操作时一样立刻将删除操作写入日志。但是master不会立刻对资源进行回收，而是将待删除的文件重命名为一个带有删除时间戳的隐藏文件名。当master周期性地扫描文件系统命名空间时，它会删除已经存在超过三天（用户可以配置这个间隔时间）的这种隐藏文件。
• 在进行chunk级垃圾回收时，master会周期性扫描chunk命名空间，并找出孤儿chunk（orphaned chunk）（例如哪些无法被任何文件访问到的chunk）并删除这些chunk的元数据。

2.5.5. 陈旧副本检测

如果chunkserver因故障离线时错过了对其中的chunk的变更，那么该chunkserver中chunk的副本会变为陈旧的副本。

master会为每一个chunk维护一个chunk版本号（chunk version number），用来区分最新的和陈旧的副本。

版本号更新时机：master每当为一个chunk授权新租约时，都会增加chunk的版本号并同时其最新的副本。master和这些副本都持久化保存这个新版本号。

2.6. 容错和诊断

GFS中的高可用策略：

• 快速恢复：在master和chunkserver的设计中，它们都会保存各自的状态，且无论它们以哪种方式终止运行，都可以在数秒内重新启动。
• chunk副本：如前所述，每个chunk会在不同机架的多个chunkserver上存有副本
• master副本：为了保证可靠性，master的状态同样有副本。master的操作日志和检查点被在多台机器上复制。只有当变更在被日志记录并被写入 master本地 和 所有master副本 的磁盘中后，这个变更才被认为是已提交的。
  • 若运行master进程的机器故障或其磁盘故障，GFS之外有负责监控的基础架构会在其它 持有master的操作日志副本的机器上 启动一个新的master进程。
  • client仅通过一个规范的命名来访问master结点（例如gfs-test），这个规范的命名是一个DNS别名，其可以在master重新被分配到另一台机器时被修改为目标机器。
  • 此外，“影子”master节点（“shadow” master）可以提供只读的文件系统访问，即使在主master结点脱机时它们也可以提供服务。不过可能稍稍滞后于master。

数据完整性：

每个chunkserver都使用 校验和 来检测存储的数据是否损坏。

• 一个chunk被分解为多个64KB的block（chunk自身的大小限制为64MB）。每个block有其对应的32位校验和。就像其他元数据一样，校验和也在内存中保存且会被通过日志的方式持久化存储。校验和与用户数据是分开存储的。
• 对于读取操作：无论请求来自client还是其他chunkserver，chunkserver都会在返回任何数据前校验所有包含待读取数据的block的校验和。
  • 如果一个block中数据和记录中低的校验和不匹配，那么chunkserver会给请求者返回一个错误，并向master报告校验和不匹配。
  • 随后，请求者会从其他副本读取数据，而master会从该chunk的其他副本克隆这个chunk。
  • 当该chunk新的合法的副本被安置后，master会通知报告了校验和不匹配的chunkserver删除那份损坏的副本。
  • 校验和对读取性能的影响很小。
• 对于写入操作：向chunk末尾append数据时，仅增量更新上一个block剩余部分的校验和，并为append的新block计算新校验和。
  • 即使最后一个block已经损坏但还没被检测到，增量更新后的该block的新校验和也不会与原来存储的数据匹配。在下一次读取该block时，GFS会像往常一样检测到数据损坏。
• chunkserver可以在空闲期间扫描并验证非活动的chunk的内容。这样可以让我们检测到很少被读取的chunk中的数据损坏。
  • 一旦检测到数据损坏，master可以创建一个新的未损坏的副本并删除损坏的副本。这样可以防止master将chunk的非活动的但是已损坏的副本识别成合法的副本。

诊断工具：

基于诊断日志辅助问题定位、调试和性能分析。

• 在诊断问题时，我们可以通过整合不同机器中的日志并将请求与响应匹配的方式，重建整个交互历史。
• 同样，这些日志也可用来跟踪压力测试、性能分析等情况。

2.7. 其他

性能测试暂时浏览一下，此处不做记录。其中统计各种核心io操作的对比情况、write和append write的对比、异常恢复时间等，实际项目中可能指标会比这更多。

GFS提供了与位置无关的命名空间，这样可以透明地（对client透明）移动数据，以实现负载均衡和容错。

2.8. 结论

Google File System论证了在普通商用硬件上支持大规模数据处理负载的必要特性。虽然很多设计是为Google特殊的场景定制的，但很多设计可能适用于规模和成本相似的数据处理任务。

• 通过持续的监控、备份关键数据、自动且快速的恢复来提供容错能力。
  • chunk副本让我们能够容忍chunkserver故障
  • 在线修复机制：周期性且client无感知地修复损坏的数据，并尽快补充丢失的副本
  • 另外，通过校验和的方式来检测磁盘或IDE子系统级别的数据损坏，因为GFS系统中磁盘数量很多，这类问题是非常普遍的
• 通过下述设计，为并发执行多种任务的reader和writer提供了很高的整体吞吐量
  • 将 通过master进行的文件系统控制 和 通过chunkserver、client的数据传输 分离开来
  • 选取较大的chunk大小和chunk租约（将数据变更授权给primary副本）的方式最小化了master对一般操作的参与度。这种方式让master变得简单，且中心化的master不会成为系统瓶颈。

3. 课程笔记

这门课程的主要内容是大型存储，而GFS是这门课里有关如何构建大型存储系统的众多案例学习的第一篇。

构建分布式系统大多都是关于如何设计存储系统，或是设计其它基于大型分布式存储的系统。

所以我们会更加关注如何为大型分布式存储系统设计一个优秀的接口，以及如何设计存储系统的内部结构，这样系统才能良好运行。

GFS论文涉及到很多本课程常出现的话题，例如并行性能、容错、复制和一致性。论文的内容也较为直观，容易理解。论文本身也是一篇优秀的系统论文，它从硬件到使用了GFS的软件都有讨论，并且它也是一个成功的现实世界的设计。

3.1. 设计分布式存储的难点

• 人们设计大型分布式系统或大型存储系统的出发点，通常是为了获得巨大的性能加成
• 于是设计将数据 分片（sharding），将其分布在大量服务器上，以并行从多台服务器读取数据
• 而在成百上千台服务器进行分片，将会看见常态的故障。于是引出了 容错（fault tolerance），系统需要自动容错
• 实现容错最有用的一种方法是使用 复制（replication），比如3副本（replicas）
• 这时需要考虑副本数据的 一致性问题（consistency）
• 需要通过额外措施解决一致性问题，但是为了达到这个效果，又会带来 性能问题，而性能降低和原始的出发点相悖

现实中，如果你想要好的一致性，你就要付出相应的代价。如果你不想付出代价，那就要忍受一些不确定的行为。

通常，人们很少会乐意为好的一致性付出相应的性能代价。

讲义里就是先抛出问题，然后进行分析和论述。像这里层层递进，这个方式特别容易让人代入进去。比如下面的讲义内容片段：

3.2. 讲解GFS

3.2.1. 一些设计特征

• 为了获得大容量和高速的特性，每个包含了数据的文件会被GFS自动的分割并存放在多个服务器之上，这样读写操作自然就会变得很快。因为可以从多个服务器上同时读取同一个文件，进而获得更高的聚合吞吐量。将文件分割存储还可以在存储系统中保存比单个磁盘还要大的文件。

一些并非设计目标的特征：

• GFS被设计成只在一个数据中心运行，所以这里并没有将副本保存在世界各地，单个GFS只存在于单个数据中心的单个机房里。理论上来说，数据的多个副本应该彼此之间隔的远一些，但是实现起来挺难的，所以GFS局限在一个数据中心内。
• 其次，GFS并不面向普通的用户，这是一个Google内部使用的系统，供Google的工程师写应用程序使用。所以Google并没有售卖GFS，它或许售卖了基于GFS的服务，但是GFS并不直接面向普通用户。
• 第三，GFS在各个方面对大型的顺序文件读写做了定制。
  • 在存储系统中有一个完全不同的领域，这个领域只对小份数据进行优化。例如一个银行账户系统就需要一个能够读写100字节的数据库，因为100字节就可以表示人们的银行账户。
  • 但是GFS不是这样的系统，GFS是为TB级别的文件而生。并且GFS只会顺序处理，不支持随机访问。某种程度上来说，它有点像批处理的风格。GFS并没有花费过多的精力来降低延迟，它的关注点在于巨大的吞吐量上，所以单次操作都涉及到MB级别的数据。

3.2.2. 论文发表的背景

（这部分光看论文了解不到）

• GFS论文发表在2003年的SOSP会议上，这是一个有关系统的顶级学术会议。通常来说，这种会议的论文标准是需要有大量的创新研究，但是GFS的论文不属于这一类标准。论文中的一些思想在当时都不是特别新颖，比如分布式，分片，容错这些在当时已经知道如何实现了。
• 这篇论文的特点是，它描述了一个真正运行在成百上千台计算机上的系统，这个规模远远超过了学术界建立的系统。并且由于GFS被用于工业界，它反映了现实世界的经验，例如对于一个系统来说，怎样才能正常工作，怎样才能节省成本，这些内容也极其有价值。
• 同时，论文也提出了一个当时非常异类的观点：存储系统具有弱一致性也是可以的。当时，学术界的观念认为，存储系统就应该有良好的行为，如果构建了一个会返回错误数据的系统，那还有什么意义？为什么不直接构建一个能返回正确数据的系统？GFS并不保证返回正确的数据，借助于这一点，GFS的目标是提供更好的性能。
  • 网上的投票、网页搜索结果这种场景对于错误有接受能力，而银行系统则需要保证正确。如果你通过广告向别人收费，你最好还是保证相应的数字是对的。
  • 另外，尽管GFS可能会返回错误的数据，但是可以在应用程序中做一些补偿。例如论文中提到，应用程序应当对数据做校验，并明确标记数据的边界，这样应用程序在GFS返回不正确数据时可以恢复。
• 最后，这篇论文还有一个有意思的事情。在一些学术论文中，你或许可以看到一些容错的，多副本，自动修复的多个Master节点共同分担工作，但是GFS却宣称使用 单个Master节点并能够很好的工作。

3.2.3. GFS Master节点

GFS中Master是Active-Standby模式，所以只有一个Master节点在工作。Master节点保存了文件名和存储位置的对应关系。

Master节点用来管理文件和Chunk的信息，而Chunk服务器用来存储实际的数据。

问题：GFS的一致性以及GFS是如何处理故障的？

1）先看下Master节点内保存的数据内容，主要关心这两个表单（table）：

• 第一个表单是文件名到Chunk ID或者Chunk Handle数组的对应。这个表单告诉你，文件对应了哪些Chunk。但是只有Chunk ID是做不了太多事情的，所以有了第二个表单。
• 第二个表单记录了Chunk ID到Chunk数据的对应关系。这里的数据又包含：
  • 每个Chunk存储在哪些服务器上
  • 每个Chunk当前的版本号
  • 所有对于Chunk的写操作都必须在Primary Chunk上顺序处理
  • Primary Chunk只能在特定的租约时间内担任Primary Chunk

2）上述数据都会在内存中，为了Master故障时数据丢失，部分数据存储在磁盘上

• Master节点读数据只会从内存读，但是写数据的时候，至少有一部分数据会接入到磁盘中。Master会在磁盘上存储log，每次有数据变更时，Master会在磁盘的log中追加一条记录，并生成CheckPoint（应该不是每次变更都生成？）
• 哪些需要存储在磁盘上，哪些不用？
  • Chunk Handle的数组（上面说的第一个表单）要保存在磁盘上，这里标记为NV（non-volatile, 非易失）
  • Chunk服务器列表不用保存到磁盘上。因为Master节点重启之后可以与所有的Chunk服务器通信，并查询每个Chunk服务器存储了哪些Chunk，所以我认为它不用写入磁盘。所以这里标记成V（volatile）
  • 版本号要不要写入磁盘取决于GFS是如何工作的，我认为它需要写入磁盘。我们之后在讨论系统是如何工作的时候再详细讨论这个问题。这里先标记成NV。
  • 主Chunk的ID，几乎可以确定不用写入磁盘，因为Master节点重启之后会忘记谁是主Chunk，它只需要等待60秒租约到期，那么它知道对于这个Chunk来说没有主Chunk，这个时候，Master节点可以安全指定一个新的主Chunk。所以这里标记成V。
  • 类似的，租约过期时间也不用写入磁盘，所以这里标记成V。
• 任何时候，如果文件扩展到达了一个新的64MB，需要新增一个Chunk或者由于指定了新的主Chunk而导致版本号更新了，Master节点需要向磁盘中的log追加一条记录。
  • 这里在磁盘中维护log而不是数据库的原因是，数据库本质上来说是某种B树（b-tree）或者hash table，相比之下，追加log会非常的高效，因为你可以将最近的多个log记录一次性的写入磁盘。因为这些数据都是向同一个地址追加，这样只需要等待磁盘的磁碟旋转一次。
  • 而对于B树来说，每一份数据都需要在磁盘中随机找个位置写入。所以使用Log可以使得磁盘写入更快一些。

3）Master节点会在磁盘中创建一些checkpoint点，这可能要花费几秒甚至一分钟。这样Master节点重启时，会从log中的最近一个checkpoint开始恢复，再逐条执行从checkpoint开始的log，最后恢复自己的状态。

3.2.4. 读写流程相关说明

读：

GFS论文说，客户端会选择一个网络上最近的服务器（Google的数据中心中，IP地址是连续的，所以可以从IP地址的差异判断网络位置的远近），并将读请求发送到那个服务器。因为客户端每次可能只读取1MB或者64KB数据，所以，客户端可能会连续多次读取同一个Chunk的不同位置。所以，客户端会缓存Chunk和服务器的对应关系，这样，当再次读取相同Chunk数据时，就不用一次次的去向Master请求相同的信息。

GFS读、写都是调用GFS的库。

写：

• 对于写文件来说，必须要通过Chunk的主副本（Primary Chunk）来写入。
• 对于某个特定的Chunk来说，在某一个时间点，Master不一定指定了Chunk的主副本。所以，写文件的时候，需要考虑Chunk的主副本不存在的情况。

3.2.5. 一致性说明

1、追写数据时，chunk有三个副本（包括一个Primary和两个Secondary），若出现某个非Primary副本写失败，则客户端会重发。

• 假设有3个客户端写数据，过程简要描述如下：

1）客户端1写A成功（3列分别表示3个chunkserver）

1
A A A

2）客户端2写B，一个副本写失败

1
2
B B
A A A

3）客户端3写C成功

1
2
3
C C C
B B
A A A

4）客户端2重发写B，成功

1
2
3
4
B B B
C C C
B B
A A A

之后，如果一个客户端读文件，读到的内容取决于读取的是Chunk的哪个副本。客户端总共可以看到三条数据，但是取决于不同的副本，读取数据的顺序是不一样的。

1. 如果读取的是第一个副本，那么客户端可以读到A、B、C，然后是一个重复的B。
2. 如果读取的是第三个副本，那么客户端可以读到A，一个空白数据，然后是C、B。

所以，如果读取前两个副本，B和C的顺序是先B后C，如果读的是第三个副本，B和C的顺序是先C后B。所以，不同的读请求可能得到不同的结果。

2、GFS这样设计的理由是足够的简单，但是同时也给应用程序暴露了一些奇怪的数据。这里希望为应用程序提供一个相对简单的写入接口，但应用程序需要容忍读取数据的乱序。

如果应用程序不能容忍乱序：

• 应用程序要么可以通过在文件中写入序列号，这样读取的时候能自己识别顺序，
• 要么如果应用程序对顺序真的非常敏感那么对于特定的文件不要并发写入。
  • 例如，对于电影文件，你不会想要将数据弄乱，当你将电影写入文件时，你可以只用一个客户端连续顺序而不是并发的将数据追加到文件中。

另外还分析了为了实现GFS强一致，要考虑的一些方面，这里暂不做记录。

GFS在它生涯的前5-10年在Google的出色表现：

• 总的来说，它取得了巨大的成功，许多许多Google的应用都使用了它，许多Google的基础架构，例如BigTable和MapReduce是构建在GFS之上，所以GFS在Google内部广泛被应用。
• 它最严重的局限可能在于，它只有一个Master节点，会带来以下问题：
  • Master节点必须为每个文件，每个Chunk维护表单，随着GFS的应用越来越多，这意味着涉及的文件也越来越多，最终Master会耗尽内存来存储文件表单。
  • 除此之外，单个Master节点要承载数千个客户端的请求，而Master节点的CPU每秒只能处理数百个请求，尤其Master还需要将部分数据写入磁盘，很快，客户端数量超过了单个Master的能力。
  • 另一个问题是，应用程序发现很难处理GFS奇怪的语义（GFS的副本数据的同步，或者可以说不同步）
  • 最后一个问题是，从我们读到的GFS论文中，Master节点的故障切换不是自动的。GFS需要人工干预来处理已经永久故障的Master节点，并更换新的服务器，这可能需要几十分钟甚至更长的而时间来处理。对于某些应用程序来说，这个时间太长了。

扩展阅读：CubeFS大视野 - 分布式文件系统的历史演进

• 单机文件系统演进
  • 计算机发明初期并没有文件系统。60年代开始，IBM的计算系统开始包含文件系统，标志着文件系统开始成为操作系统的一部分。
  • 70 年代的 Unix 初创，就伴随了自己的文件系统，也形成了后期 POSIX 标准。
  • 80 年代的 FAT 系列，支持更大的空间，例如 FAT16 支持 2GB，而且实现简单。
  • 90 年代
    • windows 的 NTFS，开始支持了现代文件系统的高级特性，例如文件压缩、加密、细粒度权限控制、事务日志等，当然复杂性也逐步提高。
    • 同一时期，linux 的 EXT 系列也开始逐步演进，并以稳健著称，被广泛采用。
  • 2000 年前后，随着磁盘空间的增加，大容量磁盘，大分区、机柜等开始成为主流需求，EXT4、XFS 等开始普及。
  • 随后，一些新的文件系统出现，比如Btrfs、ZFS、F2FS 和 ReiserFS 等，具有某些特定场景特点，影响力和广泛使用程度相较于 EXT4 和 XFS 较小
• 虚拟文件系统
  • Linux 采用了虚拟文件系统（VFS），创建一个通用的文件模型，兼容不同类型的文件系统
  • Windows 也有类似于 VFS 的抽象层：文件系统驱动程序。这个层次的设计允许 Windows 支持多种文件系统，并提供统一的接口来访问这些文件系统
• 分布式文件系统演进
  • 共享文件系统：共享文件系统也是分布式文件系统核心的特性之一，换言之，共享文件存储相当于分布式文件系统种子。
    • 1989 年 NFS 发布了 v2 版本；
    • 同一时期，还有 SMB，不过 SMB2.0 得到广泛认可是在 2006 年
  • 分布式存储系统
    • GFS（Google File System）在 2000 年代初期由 Google 开发，旨在满足其大规模数据处理的需求
    • HDFS（Hadoop Distributed File System）可以视为 GFS 的开源实现。HDFS 参照 GFS 论文，放宽了一些 POSIX 要求，以实现对文件系统数据的流式访问。
  • 分布式文件系统
    • 2010 年前后，云的概念开始在头部厂商内部落地，各大厂商（国外如 AWS、Microsoft、Google、国内BAT）开始完善自己的海量存储系统，并基于底层系统构建不同的接入服务能力，从而来适配各自强劲的业务需求。
    • 2015 年，移动互联网经过了几年的高速发展，热潮达到了顶峰，海量存储和业务需求又到了一个新的阶段，集群成本的控制，性能、成本、稳定性、易维护、容灾调度能力等都又了新的需求。人们需要一套系统解决海量文件存储的各种问题，其中 Ceph 逐步成为影响力比较大的分布式文件存储系统。
      • CephFS 是基于 Ceph 的对象存储实现的分布式文件系统，它利用 Ceph 的底层对象存储来管理文件和目录，提供高可用性和可扩展性。
    • 后续出现了很多分布式文件系统，如参考链接中的CubeFS、国内的还有JuiceFS、CurveFS等

4. 小结

这一篇看GFS论文时间比较久，看过了一遍要写这篇笔记感觉又差点什么。自己当前工作是分布式存储相关的，涉及的存储系统类似HDFS架构，HDFS最早是雅虎根据GFS的论文概念模型来设计实现的，所以当前项目里的各个模块基本能跟GFS一一对应起来。这样映照学习并溯源设计思想是一个比较不错的体验，实践和理论结合起来后像是多打通了一条“经脉”。

看资料的过程中，发现了很多优秀的人和文章，有些还是在校的学生，但是实践经历和水平深度已经很优秀了，让自己挺汗颜。汗颜过后还是踏实补基础，别人的是别人的，现在是要让自己的技术飞轮转起来。在别人的分享基础上，结合开源结合GPT，能用更短的时间走过别人已经走过的验证正确的路，让正确的事持续发生。感慨有点多了，自勉。

5. 参考

1、GFS论文

2、《The Google File System》论文翻译（GFS-SOSP2003）

3、lecture-gfs 讲义

4、课程视频：Lecture 2 - GFS

5、课程中文翻译：Lecture 03 - GFS

6、CubeFS大视野 - 分布式文件系统的历史演进