The Google File System 详解

什么是 GFS？

GFS 全称为 Google File System，是一个分布式的文件系统，GFS 实际上是部署在分布式的环境中，但是提供的文件服务好像就在单机上运行一样。程序员不需要知道分布式的任何细节，就像使用本地文件一样读取或写入在分布式环境上储存的文件。

GFS 为大型数据密集型的应用提供了高效存储和访问的文件系统，并作为分布式系统最基础的文件系统开启了大数据时代。通过一系列的设计，充分利用了多个服务器的性能（网络带宽），并设计了接口，使得其简单易用，为大数据的发展奠定了基石。

由于 GFS 是一个比较复杂的系统，其中有很多复杂的细节要处理，但是仅从宏观上理解，一些过于细节的内容可能会影响理解，所以本文主要从宏观的角度解释，一些过于细节的内容就舍弃了。

设计前提

1. 所储存的文件较大：通常是百兆（100 MB）或千兆（1 GB）以上的文件
2. 绝大部分顺序读取：绝大部分的读取是顺序读取，极小部分的随机读取
3. 绝大部分追加写入：绝大部分的写入是追加写入，极小部分的随机写入或修改
4. 设备通常容易坏：在数千台机器组成的分布式环境中，机器的故障和损坏几乎是必然的
5. 高带宽比低延时更重要：GFS 通常用作大文件的管理系统，要求能够高速率、大批量的处理数据，低延时就没那么重要
6. 应用场景不需要保证强一致性

角色

GFS 由一个 Master Server 和若干个 Chunk Server 组成。其中 Master 负责管理所有的 Chunk Server 和系统状态，Chunk Server 则负责实际的数据存储。

所以 Client 需要先向 Master Server 发出请求，然后 Master 告诉 Client 数据在哪个 Chunk Server 上，然后 Client 再向那个 Chunk Server 拿数据。

前置概念

• Chunk：一个 Chunk 代表一个文件块，在 GFS 中设置为 64MB，所以一个文件可能会被分成多个 Chunk 存储。其中每个 Chunk 都有其全局唯一的 64 位标识。
• 元数据（Mate data）：Master 中所管理的信息
  • 文件信息：文件路径、文件名、创建时间、访问权限等
  • Chunk 信息：标识号、版本号等
  • 文件到 Chunk 的映射
• 租约：Master 授予某一个 Chunk Server 在一定时间内有修改该 Chunk 的权限
• 副本：同一个 Chunk 会产生多个副本储存在不同的 Chunk Server 上，以实现容错性和负载均衡

所以对于一个文件，Master 中会储存一个 Chunk id 的列表，表示该文件数据储存在哪些 Chunk 上；同理对于一个 Chunk，会有一个 Server 列表，表示该 Chunk 储存在哪些 Chunk Server 上。

客户端如何读取数据？

简要流程

1. Client 将文件名和偏移量发送给 Master
2. Master 将会返回一系列的 Chunk Server 给 Client
3. Client 将决定选择一个较近的 Chunk Server 发送获取数据的请求
4. Chunk Server 将数据发送给 Client

如果 Client 的请求要返回的 Chunk 超过一个，则拆分成两次请求，每次请求只会获得一个 Chunk。这里的偏移量具体指的是第几块 Chunk，客户端可以计算出所要的数据是在文件 Chunk 列表的第几个。

客户端的优化

在 Master 返回 Chunk Server 之后，客户端会缓存这些 Chunk Server，当下次请求数据时发现数据是在同一个 Chunk 上（已缓存该 Chunk 所在的 Chunk Server），则直接向 Chunk Server 发送数据请求，而不再向 Master 发送请求。

如何保证可用性？

在机器损坏宕机几乎是必然的情况下，如何保证还能正常获取到数据？

每个 Chunk 都会复制多份，以保证一个 Chunk Server 宕机了，也还有其他 Chunk Server 可以请求。Master 所管理的一个 Chunk 所储存在的服务器是会动态定期更新的，也就是说，当一个 Chunk Server 宕机了，Master 联系不上时，会再选取另一个 Chunk Server 复制一份该 Chunk 存储。

简单来说，在 Master 管理下，一个 Chunk 可用的副本数必须保持在一个数字，一旦某一个副本不可用，Master 会立刻创建一个新副本出来。

另外，每个 Chunk 还有其校验和，在 Chunk Server 自主定期扫描时会检查，如果校验和出错，会将错误信息报告给 Master，Master 会创建一个新的副本。在响应客户端读取也会进行检查，如果校验和出错，则通知 Client 去另一个 Chunk Server 请求数据，并如上流程一样通知 Master。

客户端如何修改数据？

修改绝大部分、几乎是追加操作，所以这里讨论的都是追加操作。

简要流程

1. Client 将文件名和偏移量发送给 Master
2. Master 将选出一个 Primary Chunk Server，并授予其租约，返回该 Server 给 Client
3. Client 将和该 Server 发出修改请求
4. Primary Chunk Server 会组织其余的 Secondary Chunk Server 一起完成修改，并返回结果给 Client，如果失败，则 Client 可以重新请求 Master 发出修改请求

和读取一样，修改也只能基于一个 Chunk，如果跨 Chunk，则会拆分成多次请求。即如果 Chunk Server 发现当前 Chunk 的剩余空间存储不下，则会用 padding 填充，然后告知客户端去请求一个新的 Chunk。

如何选出 Primary Chunk Server

Master 在持有 Chunk 的 Chunk Server 中随机选择一个作为 Primary Chunk Server，并授予其租约（版本号必须一致）。如果已经存在一个租约未过期的 Primary Chunk Server，则不进行选举，直接视其为 Primary Chunk Server。

如果一个 Primary Chunk Server 仍处在修改状态中，但是租约快过期了，可以向 Master 申请延长租约，避免重新选举所产生的开销。（延长租约的请求可以包含在周期性的心跳信息中）

当 Primary Chunk Server 宕机之后，只能等租约过期之后才能选举新的 Primary Chunk Server，这是为了防止宕机的 Primary Chunk Server 在宕机恢复之后出现两个 Primary Chunk Server。

另一方面，Master 联系不到 Primary Chunk Server 有可能是因为网络问题，但此时也许 Primary Chunk Server 并没有宕机，其仍然可以和 Client 进行交互，此时如果选举新的 Primary Chunk Server，就会导致两个 Primary Chunk Server。

Primary Chunk Server 如何组织修改（一致性）

首先 Client 可以将数据推送到任何 Chunk Server 上，当所有 Chunk Server 都收到该数据之后，再向 Primary Chunk Server 发出修改请求。此时 Primary 可能收到多个 Client 并发的请求，Primary 就负责决策这些修改请求的顺序。

Client 将数据推送到一个 Chunk Server 之后，该 Chunk Server 会自动将该数据推送到其他 Chunk Server 上，此时数据会先被缓存起来。这种链式传输数据的方式可以充分利用网络带宽，而不是一个设备集中传给好几个，形成网络带宽的瓶颈。

一旦决定之后，Primary 会通知所有 Secondary 执行写入操作，并要求其返回结果。如果所有 Secondary 都修改成功，返回成功结果给客户端；如果任意一个 Secondary 修改失败，则返回失败结果给客户端，期待客户端发起下一次修改请求。

这里会产生一个弱一致性的问题，即某一些 Chunk Server 写入成功了，而另一些 Chunk Server 写入失败，写入失败的那些会用 padding 填充，此时就产生了数据的不一致。但是总体来说，如果客户端收到成果，说明写入的数据至少写入了一次，在 GFS 所面对的应用场景中，重复写入和存在 padding 是不影响的。但如果所面对的应用场景不能容忍弱一致性，则这部分需要重新设计。

一个写入例子如下：B 写入发生错误，所以重新写入了一次

Request order: A B(fail) C B

Primary:     | A | B | C | B |
Secondary 1: | A |   | C | B |
Secondary 2: | A | B | C | B |

同时注意 ABC 是来自不同的客户端的并发写入，其顺序是由 Primary 决定的，所以如果应用场景对写入顺序有要求，则该方案也是不适用的。该方案并不保证写入顺序，其是随机的，其只能保证如果返回成功，则数据一定至少写入一次。

如何保证可用性？

在追加写入时，只会检查最后一个数据片的校验和，如果正确则进行追加
在覆盖写入时，会检查覆盖范围的第一个数据片和最后一个数据片，如果正确则进行覆盖

Chunk Server 的管理

定期扫描

Chunk Server 会定期扫描自身的数据，删除那些校验和错误的 Chunk，并上报给 Master，请求创建新的副本。

同时也会定期扫描缓存起来的来自客户端的写入数据，定期清除那些过期的。

Master 的管理

元数据内容

• 文件到 Chunk 的映射
• 每个 Chunk 的信息：
  • 所在的 Chunk Server：在动态问询中更新的，不固定
  • 版本号：每发一次新的租约时递增
  • Primary Chunk Server
  • 租约信息

元数据的更新

文件到 Chunk 的映射和 Chunk 版本号是需要写入到硬盘上的，其是持久化的数据信息，这样可以在 Master 宕机之后恢复这些信息。其余信息则可以不写入硬盘，只留存在内存中，这部分信息会在 Master 启动或 Chunk Server 加入集群时动态更新。

另外，元数据的更新是原子性的，其只在 Master 上修改，一致性比较容易保证。

定期心跳

Master 会定期向所有 Chunk Server 发送心跳信息，Chunk Server 会回复自己所拥有的 Chunk 信息，然后 Master 会回复自己所管理的 Chunk 信息，于是 Chunk Server 会根据 Master 的回复，删除那些无用的垃圾 Chunk（版本号过低、已删除的 Chunk）。

主备切换

只有一个 Master 无法处理 Master 宕机的情况，所以此时引入一个备用 Master 来应对这种情况。

当主 Master 宕机时，备用 Master 会立刻接管主 Master 的职责，由于主备 Master 之间会时刻同步系统信息，所以几乎可以没有影响地接替。在元数据更新写入本地磁盘时，只有主备 Master 都同步修改之后才视为成功。

主备切换之后备用 Master 仍然需要发送心跳信息先收集所有 Chunk Server 的信息，然后才能开始管理和接替主 Master 的工作。相当于主 Master 宕机之后立刻恢复。

版本号递增规则

版本号并不是修改一次递增一次，而是修改租约授予一次递增一次，无论修改租约的持续时间内修改多少次，其版本号只会增加一次。

一些零散的细节

Chunk 的设计

Chunk 的大小设置为 64MB 有以下好处：

1. 减少跨 Chunk 的操作，使得大部分操作可以在一个 Chunk 内完成，减少系统内部的交互
2. 同时也可以使得大部分操作可以在一个 TCP 连接中完成，减少网络开销
3. 减少 Chunk 数量，减轻 Master 的管理压力

Master 的设计

单 Master 有以下好处：

1. 简化设计，避免多个控制中心带来的复杂同步问题
2. 易于监测和调控，只需要关注 Master 就可以掌握系统的全局状态
3. 效率高，单 Master 掌握全局状态，可以从全局角度进行优化和调度，更容易提高性能

删除操作

在执行删除文件的命令后，GFS 不会立刻删除数据，而是将文件重命名成一个特殊名称（包含删除时间戳等信息），当删除时间超过 3 天时，才执行真正的删除操作，在此之前都可以执行回滚恢复删除。

垃圾回收机制

垃圾回收机制存在于定期心跳和扫描中，这样简单的垃圾回收机制有以下优点：

1. 在故障非常常见的大规模分布式系统中，它简单可靠
2. 为异常数据提供了一种统一可靠的清理方法
3. 为删除文件提供了一种延迟，让删除可以回滚，更加安全

快照功能

Copy On Write 的思想，仅当文件要进行修改时才进行复制，即把复制延迟到修改发生的那一刻。

当 Client 请求一个快照操作时，Master 会撤销所有租约，防止在快照生成期间发生修改，确保复制的一致性。然后复制文件的元数据来实现快照的创建，此时快照和原文件仍然共享同样的 Chunk。

每个 Chunk 都有一个引用计数，代表有多少个文件含有该 Chunk。当客户端发出修改请求，会检查其修改 Chunk 的引用计数，如果只有一个，则代表该 Chunk 被一个文件独享，可以直接修改，不会影响到其他文件。如果引用数大于 1，则代表有多个文件持有该 Chunk，此时要修改则要进行复制操作，复制完成之后再修改。

常见问题

为什么需要租约？Client 直接问 Master 谁是 Primary Chunk Server 不就好了？

考虑这样一种情况，客户端 A 向 Master 发出修改请求，Master 返回 Server 1 作为 Primary Chunk Server。但是在返回给客户端 A 之后，Master 联系不上 Server 1，立刻选举了另一个 Chunk Server 作为 Priamry。此时客户端 B 向 Master 发出修改请求，Master 返回了 Server 2，此时就出现了两个 Primary Chunk Server。此时的修改操作就会出现不同的两个修改版本，出现不一致的问题。

而租约的提出就是为了解决这个问题，租约是基于时间的，即使 Master 和 Primary Chunk Server 联系不上，通过租约的时限保证了一定时间内，只会存在一个 Primary Chunk Server，不管 Master 是否联系得到 Primary Chunk Server，或者 Primary Chunk Server 是否宕机。当然如果 Primary Chunk Server 真宕机了，会出现一定时间内服务器无法响应修改请求，这是弊端。通常租约的时限设置在 60s。

客户端请求的版本号？

客户端请求时可以不带版本号，也可以携带版本号，当不带版本号时 Master 和 Chunk Server 返回的是最新版本号的 Chunk。当客户端携带版本号请求时，Master 或 Chunk Server 会检查版本号是否一致，如果不一致，则返回失败。

这样设计的原因是为了客户端处的缓存优化，当客户端进行缓存时，需要保存其版本号，以在后续的交互中确认是同一个版本号的内容。

假设客户端缓存了一个版本号之后 Chunk 发生了修改，其版本号增加了，那么客户端使用下次请求 Chunk Server 时就能知道自己所缓存的版本号是一个过期的，从而重新向 Master 请求。

如果不携带版本号进行请求，客户端无法得知所获得的数据是否是所期待的数据，已缓存的信息是否过时。

如果客户端持有过期的数据并修改，GFS 如何响应？

如果客户端在过期的数据上修改，并发出修改请求，此时 GFS 视情况决定是否接受修改。

大部分情况修改不会发生在一个 Chunk 内，但是即使发生在一个 Chunk 内，GFS 也可以通过版本号来解决过期数据的问题。如果修改的版本号较低，则客户端会重新获取新的文件，在此基础上进行修改，再发送请求。

但实际上 GFS 面对的应用场景大部分是追加操作，它只会在文件末尾追加数据，同时也不太在乎写入顺序，所以这种情况几乎不存在。（在旧的数据或新的数据上追加没有什么区别）

如何处理读取和修改的并发？

由于修改几乎是追加操作，所以不会影响到读取，所以绝大部分情况下是可以并行不影响的。但假如读取和修改发生在同一处，此时就可能产生读取和修改冲突的问题，此时可以通过读取的版本号来解决。如果版本号不一致，则需要重新发送读取请求。

修改期间宕机的问题

假设 Primary 处理了两个并行的客户端请求，其中第一个成功执行了，第二个只有一半 Secondary 成功执行，另一半没有收到 Primary 的网络请求。此时所有 Secondary 的版本号是一致的，因为版本号只受租约更新的影响，而不受数据更新的影响。

此时 Primary 宕机，Master 选举了一个新的 Primary，但是通过版本号无法区分哪一个 chunk 是最新的，此时如何处理这种不一致性？

在 Master 选择一个新的 Primary 之后，会基于该 Primary 对所有 Secondary 进行数据同步，同步的实际上是偏移量。我们知道 GFS 不在意写入顺序和一些 padding，所以现在只要所有 Secondary 的数据偏移量和 Primary 一致即可。

如果新的 Primary 已经写入了第二个请求，Secondary 只需要填充 padding 至同一个偏移量即可，客户端没有收到成功的结果，仍然会再次请求。

如果新的 Primary 没有写入第二个请求，那么已经写入的 Secondary 也只需要回退偏移量，在下次请求时覆盖即可。

---