gfs 原理分析总结

Question

1. Introduction

本文是读 GFS 论文的总结，收录在我的 github 中 papers 项目 ，papers 项目旨在学习和总结分布式系统相关的论文。

全文主要分为以下几方面：

• Design Motivation
• Architecture
• System Interactions
• Master Operation
• Fault Tolerance and Diagnose
• Discussion

2. Design Motivation

google 对现有系统的运行状态以及应用系统进行总结，抽象出对文件系统的需求，主要分为以下几个方面。

• 普通商用的机器硬件发生故障是常态
• 存储的问题普遍比较大，几个 G 的文件很常见
• 大部分的文件操作都是在追加数据，覆盖原来写入的数据的情况比较少见，随机写几乎不存在
• 读操作主要包括两种，large streaming read 和 small random read
• 为了应用使用方便，多客户端并行地追加同一个文件需要非常高效
• 带宽的重要性大于时延，目标应用是高速读大块数据的应用，对响应时间没有过多的需求

3. Architecture

本部分讨论 gfs 的总体架构，以及在此架构上需要考虑的一些问题。

3.1 Overview

GFS 的整体架构如下图：

(图片来源：gfs 论文)

GFS 中有四类角色，分别是

• GFS chunkserver
• GFS master
• GFS client
• Application

3.1.1 GFS chunkserver

在 GFS chunkserver 中，文件都是分成固定大小的 chunk 来存储的，每个 chunk 通过全局唯一的 64 位的 chunk handle 来标识，chunk handle 在 chunk 创建的时候由 GFS master 分配。GFS chunkserver 把文件存储在本地磁盘中，读或写的时候需要指定文件名和字节范围，然后定位到对应的 chunk。为了保证数据的可靠性，一个 chunk 一般会在多台 GFS chunkserver 上存储，默认为 3 份，但用户也可以根据自己的需要修改这个值。

3.1.2 GFS master

GFS master 管理所有的元数据信息，包括 namespaces，访问控制信息，文件到 chunk 的映射信息，以及 chunk 的地址信息（即 chunk 存放在哪台 GFS chunkserver 上）。

3.1.3 GFS client

GFS client 是 GFS 应用端使用的 API 接口，client 和 GFS master 交互来获取元数据信息，但是所有和数据相关的信息都是直接和 GFS chunkserver 来交互的。

3.1.4 Application

Application 为使用 gfs 的应用，应用通过 GFS client 于 gfs 后端(GFS master 和 GFS chunkserver) 打交道。

3.2 Single Master

GFS 架构中只有单个 GFS master，这种架构的好处是设计和实现简单，例如，实现负载均衡时可以利用 master 上存储的全局的信息来做决策。但是，在这种架构下，要避免的一个问题是，应用读和写请求时，要弱化 GFS master 的参与度，防止它成为整个系统架构中的瓶颈。

从一个请求的流程来讨论上面的问题。首先，应用把文件名和偏移量信息传递给 GFS client，GFS client 转换成（文件名，chunk index) 信息传递给 GFS master，GFS master 把(chunk handle, chunk 位置信息) 返回给客户端，客户端会把这个信息缓存起来，这样，下次再读这个 chunk 的时候，就不需要去 GFS master 拉取 chunk 位置信息了。

另一方面，GFS 支持在一个请求中同时读取多个 chunk 的位置信息，这样更进一步的减少了 GFS client 和 GFS master 的交互次数，避免 GFS master 成为整个系统的瓶颈。

3.3 Chunk Size

对于 GFS 来说，chunk size 的默认大小是 64MB，比一般文件系统的要大。

优点

• 可以减少 GFS client 和 GFS master 的交互次数，chunk size 比较大的时候，多次读可能是一块 chunk 的数据，这样，可以减少 GFS client 向 GFS master 请求 chunk 位置信息的请求次数。
• 对于同一个 chunk，GFS client 可以和 GFS chunkserver 之间保持持久连接，提升读的性能。
• chunk size 越大，chunk 的 metadata 的总大小就越小，使得 chunk 相关的 metadata 可以存储在 GFS master 的内存中。

缺点

• chunk size 越大时，可能对部分文件来讲只有 1 个 chunk，那么这个时候对该文件的读写就会落到一个 GFS chunkserver 上，成为热点。

对于热点问题，google 给出的解决方案是应用层避免高频地同时读写同一个 chunk。还提出了一个可能的解决方案是，GFS client 找其他的 GFS client 来读数据。

64MB 应该是 google 得出的一个比较好的权衡优缺点的经验值。

GFS master 存储三种 metadata，包括文件和 chunk namespace，文件到 chunk 的映射以及 chunk 的位置信息。这些 metadata 都是存储在 GFS master 的内存中的。对于前两种 metadata，还会通过记操作日志的方式持久化存储，操作日志会同步到包括 GFS master 在内的多台机器上。GFS master 不持久化存储 chunk 的位置信息，每次 GFS master 重启或者有新的 GFS chunkserver 加入时，GFS master 会要求对应 GFS chunkserver 把 chunk 的位置信息汇报给它。

3.4.1 In-Memory Data Structures

使用内存存储 metadata 的好处是读取 metadata 速度快，方便 GFS master 做一些全局扫描 metadata 相关信息的操作，例如负载均衡等。

但是，以内存存储的的话，需要考虑的是 GFS master 的内存空间大小是不是整个系统能存储的 chunk 数量的瓶颈所在。在 GFS 实际使用过程中，这一般不会成为限制所在，因为 GFS 中一个 64MBchunk 的 metadata 大小不超过 64B，并且，对于大部分 chunk 来讲都是使用的全部的空间的，只有文件的最后一个 chunk 会存储在部分空间没有使用，因此，GFS master 的内存空间在实际上很少会成为限制系统容量的因素。即使真的是现有的存储文件的 chunk 数量超过了 GFS master 内存空间大小的限制，也可以通过加内存的方式，来获取内存存储设计带来的性能、可靠性等多种好处。

3.4.2 Chunk Locations

GFS master 不持久化存储 chunk 位置信息的原因是，GFS chunkserver 很容易出现宕机，重启等行为，这样 GFS master 在每次发生这些事件的时候，都要修改持久化存储里面的位置信息的数据。

3.4.3 Operation Log

operation log 的作用

• 持久化存储 metadata
• 它的存储顺序定义了并行的操作的最终的操作顺序

怎么存

operation log 会存储在 GFS master 和多台远程机器上，只有当 operation log 在 GFS master 和多台远程机器都写入成功后，GFS master 才会向 GFS client 返回成功。为了减少 operation log 在多台机器落盘对吞吐量的影响，可以将一批的 operation log 形成一个请求，然后写入到 GFS master 和其他远程机器上。

check point

当 operation log 达到一定大小时，GFS master 会做 checkpoint，相当于把内存的 B-Tree 格式的信息 dump 到磁盘中。当 master 需要重启时，可以读最近一次的 checkpoint，然后 replay 它之后的 operation log，加快恢复的时间。

做 checkpoint 的时候，GFS master 会先切换到新的 operation log，然后开新线程做 checkpoint，所以，对新来的请求是基本是不会有影响的。

4. System Interactions

本部分讨论 GFS 的系统交互流程。

4.1 Leases and Mutation Order

GFS master 对后续的数据流程是不做控制的，所以，需要一个机制来保证，所有副本是按照同样的操作顺序写入对应的数据的。GFS 采用 lease 方式来解决这个问题，GFS 对一个 chunk 会选择一个 GFS chunkserver，发放 lease，称作 primary，由 primary chunkserver 来控制写入的顺序。

Lease 的过期时间默认是 60s，可以通过心跳信息来续时间，如果一个 primary chunkserver 是正常状态的话，这个时间一般是无限续下去的。当 primary chunkserver 和 GFS master 心跳断了后，GFS master 也可以方便的把其他 chunk 副本所在的 chunkserver 设置成 primary。

4.1.1 Write Control and Data Flow

(图片来源：gfs 论文)

1. GFS client 向 GFS master 请求拥有具有当前 chunk 的 lease 的 chunkserver 信息，以及 chunk 的其他副本所在的 chunkserver 的信息，如果当前 chunk 没有 lease，GFS master 会分配一个。
2. GFS master 把 primary chunkserver 以及其他副本的 chunkserver 信息返回给 client。client 会缓存这些信息，只有当 primary chunkserver 连不上或者 lease 发生改变后，才需要再向 GFS master 获取对应的信息。
3. client 把数据推送给所有包含此 chunk 的 chunkserver，chunkserver 收到后会先把数据放到内部的 LRU buffer 中，当数据被使用或者过期了，才删除掉。注意，这里没有将具体怎么来发送数据，会在下面的 Data Flow 讲。
4. 当所有包含 chunk 副本的 chunkserver 都收到了数据，client 会给 primary 发送一个写请求，包含之前写的数据的信息，primary 会分配对应的序号给此次的写请求，这样可以保证从多个客户端的并发写请求会得到唯一的操作顺序，保证多个副本的写入数据的顺序是一致的。
5. primary 转发写请求给所有其他的副本所在的 chunkserver(Secondary replica)，操作顺序由 primary 指定。
6. Secondary replica 写成功后会返回给 primary replica。
7. Primary replica 返回给 client。任何副本发生任何错误都会返回给 client。

这里，写数据如果发生错误可能会产生不一致的情况，会在 consistency model 中讨论。

4.2 Data Flow

4.1 中第三步的 Data Flow 采用的是 pipe line 方式，目标是为了充分利用每台机器的网络带宽。假设一台机器总共有三个副本 S1-S3。整个的 Data Flow 为：

1. client 选择离它最近的 chunkserver S1，开始推送数据
2. 当 chunkserver S1 收到数据后，它会立马转发到离它最近的 chunkserver S2
3. chunkserver S2 收到数据后，会立马转发给离它最近的 chunkserver S3

不断重复上述流程，直到所有的 chunkserver 都收到 client 的所有数据。

以上述方式来传送 B 字节数据到 R 个副本，并假设网络吞吐量为 T，机器之间的时延为 L，那么，整个数据的传输时间为 B/T+RL。

4.3 Atomic Record Appends

Append 操作流程和写差不多，主要区别在以下

• client 把数据推送到所有副本的最后一个 chunk，然后发送写请求到 primary
• primary 首先检查最后一个 chunk 的剩余空间是否可以满足当前写请求，如果可以，那么执行写流程，否则，它会把当前的 chunk 的剩余空间 pad 起来，然后告诉其他的副本也这么干，最后告诉 client 这个 chunk 满了，写入下个 chunk。

这里需要讨论的是，如果 append 操作在部分副本失败的情况下，会发生什么？

例如，写操作要追加到 S1-S3，但是，仅仅是 S1,S2 成功了，S3 失败了，GFS client 会重试操作，假如第二次成功了，那么 S1,S2 写了两次，S3 写了一次，目前的理解是 GFS 会先把失败的记录进行 padding 对齐到 primary 的记录，然后再继续 append。

4.4 Snapshot

Snapshot 的整个流程如下：

1. client 向 GFS master 发送 Snapshot 请求
2. GFS master 收到请求后，会回收所有这次 Snapshot 涉及到的 chunk 的 lease
3. 当所有回收的 lease 到期后，GFS master 写入一条日志，记录这个信息。然后，GFS 会在内存中复制一份 snapshot 涉及到的 metadata

当 snapshot 操作完成后，client 写 snapshot 中涉及到的 chunk C 的流程如下：

1. client 向 GFS master 请求 primary chunkserver 和其他 chunkserver
2. GFS master 发现 chunk C 的引用计数超过 1，即 snapshot 和本身。它会向所有有 chunk C 副本的 chunkserver 发送创建一个 chunk C 的拷贝请求，记作是 chunk C’，这样，把最新数据写入到 chunk C’即可。本质上是 copy on write。

4.5 Consistency Model

(图片来源：gfs 论文)

GFS 中 consistent、defined 的定义如下：

• consistent：所有的客户端都能看到一样的数据，不管它们从哪个副本读取
• defined：当一个文件区域发生操作后，client 可以看到刚刚操作的所有数据，那么说这次操作是 defined。

下面分析表格中出现的几种情况。

1. Write(Serial Success)，单个写操作，并且返回成功，那么所有副本都写入了这次操作的数据，因此所有客户端都能看到这次写入的数据，所以，是 defined。
2. Write(Concurrent Successes)，多个写操作，并且返回成功，由于多个客户端写请求发送给 priamary 后，由 primary 来决定写的操作顺序，但是，有可能多个写操作可能是有区域重叠的，这样，最终写完成的数据可能是多个写操作数据叠加在一起，所以这种情况是 consistent 和 undefined。
3. Write(Failure)，写操作失败，则可能有的副本写入了数据，有的没有，所以是 inconsistent。
4. Record Append(Serial Success and Concurrent Success)，由于 Record Append 可能包含重复数据，因此，是 inconsistent，由于整个写入的数据都能看到，所以是 defined。
5. Record Append(Failure)，可能部分副本 append 成功，部分副本 append 失败，所以，结果是 inconsistent。

GFS 用 version 来标记一个 chunkserver 挂掉的期间，是否有 client 进行了 write 或者 append 操作。每进行一次 write 或者 append，version 会增加。

需要考虑的点是 client 会缓存 chunk 的位置信息，有可能其中某些 chunkserver 已经挂掉又起来了，这个时候 chunkserver 的数据可能是老的数据，读到的数据是会不一致的。读流程中，好像没有看到要带 version 信息来读的。这个论文中没看到避免的措施，目前还没有结果。

4.5.1 Implications for Applications

应用层需要采用的机制：用 append 而不是 write，做 checkpoint，writing self-validating 和 self-identifying records。具体地，如下：

1. 应用的使用流程是 append 一个文件，到最终写完后，重命名文件
2. 对文件做 checkpoint，这样应用只需要关注上次 checkpoint 时的文件区域到最新文件区域的数据是否是 consistent 的，如果这期间发生不一致，可以重新做这些操作。
3. 对于并行做 append 的操作，可能会出现重复的数据，GFS client 提供去重的功能。

5. Master Operation

GFS master 的功能包括，namespace Management， Replica Placement，Chunk Creation，Re-replication and Rebalancing 以及 Garbage Collection。

5.1 Namespace Management and Locking

每个 master 操作都需要获得一系列的锁。如果一个操作涉及到/d1/d2/…/dn/leaf，那么需要获得/d1,/d1/d2,/d1/d2/…/dn 的读锁，然后，根据操作类型，获得/d1/d2/…/dn/leaf 的读锁或者写锁，其中 leaf 可能是文件或者路径。

一个例子，当/home/user 被快照到/save/user 的时候，/home/user/foo 的创建是被禁止的。

对于快照，需要获得/home 和/save 的读锁，/home/user 和/save/user 的写锁。对于创建操作，会获得/home,/home/user 的读锁，然后/home/user/foo 的写锁。其中，/home/user 的锁产生冲突，/home/user/foo 创建会被禁止。

这种加锁机制的好处是对于同一个目录下，可以并行的操作文件，例如，同一个目录下并行的创建文件。

5.2 Replica Placement

GFS 的 Replica Placement 的两个目标：最大化数据可靠性和可用性，最大化网络带宽的使用率。因此，把每个 chunk 的副本分散在不同的机架上，这样一方面，可以抵御机架级的故障，另一方面，可以把读写数据的带宽分配在机架级，重复利用多个机架的带宽。

5.3 Creation, Re-replication, Rebalancing

5.3.1 Chunk Creation

GFS 在创建 chunk 的时候，选择 chunkserver 时考虑的因素包括：

1. 磁盘空间使用率低于平均值的 chunkserver
2. 限制每台 chunkserver 的最近的创建 chunk 的次数，因为创建 chunk 往往意味着后续需要写大量数据，所以，应该把写流量尽量均摊到每台 chunkserver 上
3. chunk 的副本放在处于不同机架的 chunkserver 上

5.3.2 Chunk Re-replication

当一个 chunk 的副本数量少于预设定的数量时，需要做复制的操作，例如，chunkserver 宕机，副本数据出错，磁盘损坏，或者设定的副本数量增加。

chunk 的复制的优先级是按照下面的因素来确定的：

1. 丢失两个副本的 chunk 比丢失一个副本的 chunk 的复制认为优先级高
2. 文件正在使用比文件已被删除的 chunk 的优先级高
3. 阻塞了 client 进程的 chunk 的优先级高（这个靠什么方法得到?)

chunk 复制的时候，选择新 chunkserver 要考虑的点：

1. 磁盘使用率
2. 单个 chunkserver 的复制个数限制
3. 多个副本需要在多个机架
4. 集群的复制个数限制
5. 限制每个 chunkserver 的复制网络带宽，通过限制读流量的速率来限制

5.3.3 Rebalancing

周期性地检查副本分布情况，然后调整到更好的磁盘使用情况和负载均衡。GFS master 对于新加入的 chunkserver，逐渐地迁移副本到上面，防止新 chunkserver 带宽打满。

5.4 Garbage Collection

在 GFS 删除一个文件后，并不会马上就对文件物理删除，而是在后面的定期清理的过程中才真正的删除。

具体地，对于一个删除操作，GFS 仅仅是写一条日志记录，然后把文件命名成一个对外部不可见的名称，这个名称会包含删除的时间戳。GFS master 会定期的扫描，当这些文件存在超过 3 天后，这些文件会从 namespace 中删掉，并且内存的中 metadata 会被删除。

在对 chunk namespace 的定期扫描时，会扫描到这些文件已经被删除的 chunk，然后会把 metadata 从磁盘中删除。

在与 chunkserver 的 heartbeat 的交互过程中，GFS master 会把不在 metadata 中的 chunk 告诉 chunkserver，然后 chunkserver 就可以删除这些 chunk 了。

采用这种方式删除的好处：

1. 利用心跳方式交互，在一次删除失败后，还可以通过下次心跳继续重试操作
2. 删除操作和其他的全局扫描 metadata 的操作可以放到一起做

坏处：有可能有的应用需要频繁的创建和删除文件，这种延期删除方式会导致磁盘使用率偏高，GFS 提供的解决方案是，对一个文件调用删除操作两次，GFS 会马上做物理删除操作，释放空间。

5.5 Stale Replication Detection

当一台 chunkserver 挂掉的时候，有新的写入操作到 chunk 副本，会导致 chunkserve 的数据不是最新的。

当 master 分配 lease 到一个 chunk 时，它会更新 chunk version number，然后其他的副本都会更新该值。这个操作是在返回给客户端之前完成的，如果有一个 chunkserver 当前是宕机的，那么它的 version number 就不会增加。当 chunkserver 重启后，会汇报它的 chunk 以及 version number，对于 version number 落后的 chunk，master 就认为这个 chunk 的数据是落后的。

GFS master 会把落后的 chunk 当垃圾来清理掉，并且不会把落后的 chunkserver 的位置信息传给 client。

备注：GFS master 把落后的 chunk 当作垃圾清理，那么，是否是走 re-replication 的逻辑来生成新的副本呢？没有，是走立即复制的逻辑。

6. Fault Tolerance and Diagnose

6.1 High Availability

为了实现高可用性，GFS 在通过两方面来解决，一是 fast recovery，二是 replication

6.1.1 Fast Recovery

master 和 chunkserver 都被设计成都能在秒级别重启

6.1.2 Chunk Replications

每个 chunk 在多个机架上有副本，副本数量由用户来指定。当 chunkserver 不可用时，GFS master 会自动的复制副本，保证副本数量和用户指定的一致。

6.1.3 Master Replication

master 的 operation log 和 checkpoint 都会复制到多台机器上，要保证这些机器的写都成功了，才认为是成功。只有一台 master 在来做 garbage collection 等后台操作。当 master 挂掉后，它能在很多时间内重启；当 master 所在的机器挂掉后，监控会在其他具有 operation log 的机器上重启启动 master。

新启动的 master 只提供读服务，因为可能在挂掉的一瞬间，有些日志记录到 primary master 上，而没有记录到 secondary master 上（这里 GFS 没有具体说同步的流程）。

6.2 Data Integrity

每个 chunkserver 都会通过 checksum 来验证数据是否损坏的。

每个 chunk 被分成多个 64KB 的 block，每个 block 有 32 位的 checksum，checksum 在内存中和磁盘的 log 中都有记录。

对于读请求，chunkserver 会检查读操作所涉及 block 的所有 checksum 值是否正确，如果有一个 block 的 checksum 不对，那么会报错给 client 和 master。client 这时会从其他副本读数据，而 master 会 clone 一个新副本，当新副本 clone 好后，master 会删除掉这个 checksum 出错的副本。

主要是通过 log，包括重要事件的 log(chunkserver 上下线)，RPC 请求，RPC 响应等。

7. Discussion

本部分主要讨论大规模分布式系统一书上，列出的关于 gfs 的一些问题，具体如下。

7.1 为什么存储三个副本？而不是两个或者四个？

• 如果存储的是两个副本，挂掉一个副本后，系统的可用性会比较低，例如，如果另一个没有挂掉的副本出现网络问题等，整个系统就不可用了
• 如果存储的是四个副本，成本比较高

7.2 chunk 的大小为何选择 64MB？这个选择主要基于哪些考虑？

优点

• 可以减少 GFS client 和 GFS master 的交互次数，chunk size 比较大的时候，多次读可能是一块 chunk 的数据，这样，可以减少 GFS client 向 GFS master 请求 chunk 位置信息的请求次数。
• 对于同一个 chunk，GFS client 可以和 GFS chunkserver 之间保持持久连接，提升读的性能。
• chunk size 越大，chunk 的 metadata 的总大小就越小，使得 chunk 相关的 metadata 可以存储在 GFS master 的内存中。

缺点

• chunk size 越大时，可能对部分文件来讲只有 1 个 chunk，那么这个时候对该文件的读写就会落到一个 GFS chunkserver 上，成为热点。

64MB 应该是 google 得出的一个比较好的权衡优缺点的经验值。

7.3 gfs 主要支持追加，改写操作比较少，为什么这么设计？如何设计一个仅支持追加操作的文件系统来构建分布式表格系统 bigtable？

• 因为追加多，改写少是 google 根据现有应用需求而确定的
• bigtable 的问题等读到 bigtable 论文再讨论

7.4 为什么要将数据流和控制流分开？如果不分开，如何实现追加流程？

主要是为了更有效地利用网络带宽。把数据流分开，可以更好地优化数据流的网络带宽使用。

如果不分开，需要讨论下。

7.5 gfs 有时会出现重复记录或者 padding 记录，为什么？

padding 出现场景：

• last chunk 的剩余空间不满足当前写入量大小，需要把 last chunk 做 padding，然后告诉客户端写入下一个 chunk
• append 操作失败的时候，需要把之前写入失败的副本 padding 对齐到 master

重复记录出现场景：

• append 操作部分副本成功，部分失败，然后告诉客户端重试，客户端会在成功的副本上再次 append，这样就会有重复记录出现

7.6 lease 是什么？在 gfs 中起到了什么作用？它与心跳有何区别？

lease 是 gfs master 把控制写入顺序的权限下放给 chunkserver 的机制，以减少 gfs master 在读写流程中的参与度，防止其成为系统瓶颈。心跳是 gfs master 检测 chunkserver 是否可用的标志。

7.7 gfs 追加过程中如果出现备副本故障，如何处理？如果出现主副本故障，应该如何处理？

• 对于备副本故障，写入的时候会失败，然后 primary 会返回错误给 client。按照一般的系统设计，client 会重试一定次数，发现还是失败，这时候 client 会把情况告诉给 gfs master，gfs master 可以检测 chunkserver 的情况，然后把最新的 chunkserver 信息同步给 client，client 端再继续重试。

• 对于主副本故障，写入的时候会失败，client 端应该是超时了。client 端会继续重试一定次数，发现还是一直超时，那么把情况告诉给 gfs master，gfs master 发现 primary 挂掉，会重新 grant lease 到其他 chunkserver，并把情况返回给 client。

7.8 gfs master 需要存储哪些信息？master 的数据结构如何设计？

namespace、文件到 chunk 的映射以及 chunk 的位置信息

namespace 采用的是 B-Tree，对于名称采用前缀压缩的方法，节省空间；（文件名，chunk index）到 chunk 的映射，可以通过 hashmap；chunk 到 chunk 的位置信息，可以用 multi_hashmap，因为是一对多的映射。

7.9 假设服务一千万个文件，每个文件 1GB，master 中存储元数据大概占多少内存？

1GB/64MB = 1024 / 64 = 16。总共需要 16 * 10000000 * 64 B = 10GB

7.10 master 如何实现高可用性？

• metadata 中 namespace，以及文件到 chunk 信息持久化，并存储到多台机器
• 对 metadata 的做 checkpoint，保证重启后 replay 消耗时间比较短，checkpoint 可以直接映射到内存使用，不用解析
• 在 primary master 发生故障的时候，并且无法重启时，会有外部监控将 secondary master，并提供读服务。secondary master 也会监控 chunkserver 的状态，然后把 primary master 的日志 replay 到内存中

7.11 负载的影响因素有哪些？如何计算一台机器的负载值？

主要是考虑 CPU、内存、网络和 I/O，但如何综合这些参数并计算还是得看具体的场景，每部分的权重随场景的不同而不同。

7.12 master 新建 chunk 时如何选择 chunkserver？如果新机器上线，负载值特别低，如何避免其他 chunkserver 同时往这台机器上迁移 chunk？

如何选择 chunkserver

• 磁盘空间使用率低于平均值的 chunkserver
• 限制每台 chunkserver 最近创建 chunk 的次数，因为创建 chunk 往往意味着后续需要写入大量数据，所以，应该把写流量均摊到每台 chunkserver
• chunk 的副本放置于不同机架的 chunkserver 上

如何避免同时迁移

通过限制单个 chunkserver 的 clone 操作的个数，以及 clone 使用的带宽来限制，即从源 chunkserver 度数据的频率做控制。

7.13 如果 chunkserver 下线后过一会重新上线，gfs 如何处理？

因为是过一会，所以假设 chunk re-replication 还没有执行，那么在这期间，可能这台 chunkserver 上有些 chunk 的数据已经处于落后状态了，client 读数据的时候或者 chunkserver 定期扫描的时候会把这些状态告诉给 master，master 告诉上线后的 chunkserver 从其他机器复制该 chunk，然后 master 会把这个 chunk 当作是垃圾清理掉。

对于没有落后的 chunk 副本，可以直接用于使用。

7.14 如何实现分布式文件系统的快照操作？

Snapshot 的整个流程如下：

1. client 向 GFS master 发送 Snapshot 请求
2. GFS master 收到请求后，会回收所有这次 Snapshot 涉及到的 chunk 的 lease
3. 当所有回收的 lease 到期后，GFS master 写入一条日志，记录这个信息。然后，GFS 会在内存中复制一份 snapshot 涉及到的 metadata

当 snapshot 操作完成后，client 写 snapshot 中涉及到的 chunk C 的流程如下：

1. client 向 GFS master 请求 primary chunkserver 和其他 chunkserver
2. GFS master 发现 chunk C 的引用计数超过 1，即 snapshot 和本身。它会向所有有 chunk C 副本的 chunkserver 发送创建一个 chunk C 的拷贝请求，记作是 chunk C’，这样，把最新数据写入到 chunk C’即可。本质上是 copy on write。

7.15 chunkserver 数据结构如何设计？

chunkserver 主要是存储 64KB block 的 checksum 信息，需要由 chunk+offset，能够快速定位到 checksum，可以用 hashmap。

7.16 磁盘可能出现位翻转错误，chunkserver 如何应对？

利用 checksum 机制，分读和写两种情况来讨论：

1. 对于读，要检查所读的所有 block 的 checksum 值
2. 对于写，分为 append 和 write。对于 append，不检查 checksum，延迟到读的时候检查，因为 append 的时候，对于最后一个不完整的 block 计算 checksum 时候采用的是增量的计算，即使前面存在错误，也能在后来的读发现。对于 overwrite，因为不能采用增量计算，要覆盖 checksum，所以，必须要先检查只写入部分数据的 checksum 是否不一致，否则，数据错误会被隐藏。

7.17 chunkserver 重启后可能有一些过期的 chunk，master 如何能够发现？

chunkserver 重启后，会汇报 chunk 及其 version number，master 根据 version number 来判断是否过期。如果过期了，那么会做以下操作：

1. 过期的 chunk 不参与数据读写流程
2. master 会告诉 chunkserver 从其他的最新副本里拷贝一份数据
3. master 将过期的 chunk 假如 garbage collection 中

问题：如果 chunkserver 拷贝数据的过程过程中，之前拷贝的数据备份又发生了变化，然后分为两种情况讨论：

1. 如果期间 lease 没变，那么 chunkserver 不知道自己拷贝的数据是老的，应该会存在不一致的问题？
2. 如果期间 lease 改变，那么 chunkserver 因为还不能提供读服务，那么 version number 应该不会递增，继续保持 stable 状态，然后再发起拷贝。