1.  系统架构

GFS文件被划分为固定大小的数据块(chunk)，由主服务器创建时分配一个64位全局唯一的chunk句柄。系统中共有三种角色：

-    GFS ChunkServer（CS,数据块服务器）：以普通linux文件将chunk存储在磁盘中。为了保证可靠性，chunk在不同的机器上复制多份，默认为3

-    GFS Master（主控服务器）：维护系统的元数据，包括文件及chunk命名空间、文件到chunk之间的映射、chunk位置信息。也负责整个系统的全局控制(chunk租约管理，垃圾回收无用chunk，chunk复制)。主控服务器会定期与CS通过心跳的方式交换信息。

-    GFS客户端：GFS提供给应用程序的访问接口，是一组专用接口，以库文件的形式提供。客户端访问主控服务器节点，获取与之进行交互的CS信息，然后直接访问这些CS，完成数据存取工作。GFS客户端并不缓存文件数据，只缓存主控服务器中获取的元数据。

2.  关键问题

a)   租约机制

GFS数据追加以记录为单位，如果每次记录追加都需要请求Master，那么Master显然会成为系统的性能瓶颈，因此GFS系统中通过租约机制将chunk写操作授权给ChunkServer。拥有租约授权的ChunkServer称为主ChunkServer，其他副本所在ChunkServer称为备ChunkServer。租约授权针对单个chunk，在租约有效期内，对该chunk的写操作都由主ChunkServer负责从而减轻Master的负载。一般租约有效期比较长【比如60s】，只要没有出现异常，主ChunkServer可以不断向Master请求延长租约有效期直到整个chunk写满。

假设chunkA在GFS中保持了三个副本，其中A1是主副本，如果副本A2所在ChunkServer下线后又重新上线，这一过程中A1和A3有更新，则A2需要被当作垃圾回收掉。GFS为每个chunk维护一个版本号，每次给chunk进行租约授权或者主ChunkServer重新延长租约有效期时，Master会将chunk版本号加1,。Master的垃圾回收任务定期检查回收版本号过低的chunk，由ChunkServer将其回收。

b)  一致性模型

GFS使用追加而不是改写，一是因为改写的需求较少，即使有也可以用追加实现；二是追加的一致性模型比改写更加简单有效。考虑chunkA有三个副本，如果采用改写，副本1,2成功3失败，这样读取副本3的数据可能读到错误数据；而追加，最多读到过期的数据。

追加过程中，可能有的副本追加成功而有的副本失败，失败的副本会出现一些可识别的填充(padding)记录，追加失败将会重试，当所有副本都至少追加了一次后(有的副本可能追加了多次也有可能存在一些padding记录)，返回用户追加成功。

GFS支持多个客户端并发追加，这会导致多个客户端之间的顺序无法保证，同一个客户端的多条连续追加可能会被打断。

c)   追加流程

1)  客户端向Master请求chunk每个副本所在的ChunkServer，其中Primary ChunkServer持有修改Lease。如果没有Chunk Server持有Lease，说明该chunk最近没有写操作，Master会发起一个任务，按照一定的策略将chunk的Lease授权给其中一台chunkServer。

2)  Master返回客户端Primary和其它Chunk Server的位置信息，客户端将缓存这些信息供以后使用。如果不出现故障，客户端以后读写该chunk都不需要再次请求Master。

3)  客户端将要追加的记录发送到每一个副本。每一个Chunk Server会在内部的LRU结构中缓存这些数据。

4)  当所有副本都确认收到了数据，客户端发起一个写请求控制命令给Primary。由于Primary可能收到多个客户端对同一个chunk的并发追加操作，Primary将确定这些操作的顺序并写入本地；

5)  Primary把写请求提交给所有的Secondary副本。每一个Secondary会根据Primary确定的顺序执行写操作；

6)  Secondary副本成功完成后应答Primary；

7)  Primary应答客户端，如果有副本发生错误，将出现Primary写成功但是某些Secondary不成功的情况，客户端将重试。

GFS追加流程有两个特色：流水线及分离数据流与控制流。

-    流水线操作用来减少延时。当一个ChunkServer接收到一些数据，它就立即开始转发。由于采用全双工网络，立即发送数据并不会降低接收数据的速率。抛开网络阻塞，传输B个字节到R个副本的理想时间是B/T +RL，其中T是网络吞吐量，L是节点之间的延时。

-    分离数据流与控制流主要是为了优化数据传输，每一个机器都是把数据发送给网络拓扑图上”最近”的尚未收到数据的数据。假设有三台ChunkServerS1，S2和S3，S1与S3在同一个机架上，S2在另外一个机架，客户端部署在机器S1上。按照GFS的策略，数据先发送到S1，接着从S1转发到S3，最后转发到S2，只需要一次跨机架数据传输。

d)  容错机制

1)  Master容错

通过操作日志加checkpoint的方式进行，并且有一个成为“shadow Master”的实时热备。

Master上保存了三种元数据信息：

u 命名空间，即整个文件系统的目录结构以及chunk基本信息

u 文件到chunk之间的映射

u Chunk副本的位置信息，每个chunk通常有三个副本

GFSMaster的修改操作总是先记录操作日志，然后再修改内存，当Master发生故障重启时，可以通过磁盘中的操作日志恢复内存数据结构；另外，为了减少Master宕机恢复时间，Master会定期将内存中的数据以checkpoint文件的形式转储到磁盘中，从而减少回放的日志量。为了进一步提高Master的可靠性和可用性，GFS中还会执行实时热备，所有的元数据修改操作都必须保证发送到实时热备才算成功。远程的实时热备将实时接收Master发送的操作日志并在内存中回放这些元数据操作。如果Master宕机，还可以秒级切换到实时备机继续提供服务。为了保证同一时刻只有一个Master，GFS依赖Google内部的Chubby服务进行选主操作。

Master需要持久化前两种元数据，即命令空间及文件到chunk之间的映射关系；对于第三种元数据，即Chunk副本的位置信息，Master可以选择不进行持久化，这是因为ChunkServer维护了这些信息，即使Master发生故障，也可以在重启时通过ChunkServer汇报来获取。

2)  ChunkServer容错

GFS采用复制多个副本的方式实现Chunk Server的容错，每一个Chunk有多个存储副本，分别存储在不同的Chunk Server上。对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入。如果相关的副本出现丢失或不可恢复的情况，Master自动将给副本复制到其它Chunk Server，从而确保副本保持一定的个数。

另外，Chunk Server会对存储的数据维持校验和。GFS以64MB为Chunk大小来划分文件，每一个Chunk又以Block为单位进行划分，大小为64KB，每一个Block对应一个32位的校验和。当读取一个Chunk副本时，Chunk Server会将读取的数据和校验和进行比较，如果不匹配，就会返回错误，客户端将选择其它Chunk Server上的副本。

3.  Master设计

a)   Master内存占用

内存是Master的稀有资源，下面估算Master的内存使用量。Chunk的元信息包括全局唯一的ID，版本号，每个副本所在的Chunk Server编号，引用计数等。GFS系统中每个chunk大小为64MB，默认存储3份，每个chunk的元数据小于64字节。那么1PB数据的chunk元信息大小不超过1PB* 3 / 64MB * 64 = 3GB。另外，Master对命名空间进行了压缩存储，例如有两个文件foo1和foo2都存放在目录/home/very_long_directory_name/中，那么目录名在内存中只需要存放一次。压缩存储后，每个文件在文件名字空间的元数据也不超过64字节，由于GFS中的文件一般都是大文件，因此，文件名字空间占用内存不多，Master内存容量不会成为GFS的系统瓶颈。

b)  负载均衡

GFS中副本的分布策略需要考虑多种因素，如网络的拓扑，机架的分布，磁盘的利用率等等。为了提高系统的可用性，GFS会避免同一个chunk的所有副本都存放在同一个机架的情况。

系统中有三种需要创建chunk副本的情况：chunk创建，chunk重新复制（re-replication）以及重新平衡（rebalancing）。

当Master创建了一个chunk，它会根据如下因素来选择chunk副本的初始位置：

(1) 新副本所在的Chunk Server的磁盘利用率低于平均水平；

(2) 限制每个Chunk Server”最近”创建的数量；

(3) 每个chunk的所有副本不能在同一个机架。

第二点容易忽略但却很重要，因为创建完chunk以后通常需要马上写入数据，如果不限制”最近”创建的数量，当一台空的Chunk Server上线时，由于磁盘利用率低，可能导致大量的chunk瞬间迁移到这台机器从而将它压垮。

当Chunk的副本数量小于一定的数量后，Master会尝试重新复制一个chunk副本。可能的原因包括Chunk Server宕机或者Chunk Server报告自己的副本损坏，或者它的某个磁盘故障，或者用户动态增加了Chunk的副本数，等等。每一个chunk复制任务都有一个优先级，按照优先级从高到低在Master排队等待执行。例如，只有一个副本的chunk需要优先复制，又如，有效文件的chunk复制优先级比最近删除的文件的chunk高，最后，GFS会提高所有阻塞客户端操作的chunk复制任务的优先级，例如客户端正在往一个只有一个副本的chunk追加数据，如果限制至少需要追加成功两个副本，那么这个chunk复制任务会阻塞客户端写操作，需要提高优先级。

最后，Master会定期扫描当前副本的分布情况，如果发现磁盘使用量或者机器负载不均衡，将执行重新平衡操作。

无论是chunk创建，chunk重新复制，还是重新平衡，它们选择chunk副本位置的策略都是相同的，并且需要限制重新复制和重新平衡任务的拷贝速度，否则可能影响系统正常的读写服务。

c)   垃圾回收

GFS采用延迟删除的机制，也就是说，当文件被删除后，GFS并不要求立即归还可用的物理存储，而是在元数据中将文件改名为一个隐藏的名字，并且包含一个删除时间戳。Master定时检查，如果发现文件删除超过一段时间（默认为3天，可配置），那么它会把文件从内存元数据中删除，以后Chunk Server和Master的心跳消息中，每一个Chunk Server都将报告自己的chunk集合，Master会回复在Master元数据中已经不存在的chunk信息，这时，Chunk Server会释放这些Chunk副本。为了减轻系统的负载，垃圾回收一般在服务低峰期执行，比如每天晚上凌晨1:00开始。

另外，Chunk副本可能会因为Chunk Server失效期间丢失了对Chunk的修改操作而导致过期。系统对每个Chunk都维护了版本号，过期的Chunk可以通过版本号检测出来。Master仍然通过正常的垃圾回收机制来删除过期的副本。

d)  快照

快照（Snapshot）操作是对源文件/目录进行一个”快照”操作，生成该时刻源文件/目录的一个瞬间状态存放与目标文件/目录中。GFS中使用标准的copy-on-write机制生成快照，也就是说，”快照”只是增加GFS中chunk的引用计数，表示这个chunk被快照文件引用了，等到客户端修改这个chunk时，才需要在Chunk Server中拷贝chunk的数据生成新的chunk，后续的修改操作落到新生成的chunk上。

为了对某个文件做Snapshot，首先需要停止这个文件的写服务，接着增加这个文件的所有chunk的引用计数，以后修改这些chunk时会拷贝生成新的chunk。对某个文件执行Snapshot的大致步骤如下：

n  通过Lease机制收回对文件每一个chunk写权限，停止对文件的写服务；

n  Master拷贝文件名等元数据生成一个新的Snapshot文件；

n  对执行Snapshot的文件的所有chunk增加引用计数；

例如，对文件foo执行快照操作生成foo_backup，foo在GFS中有三个chunk C1，C2和C3。Master首先需要收回C1，C2和C3的写Lease，从而保证文件foo处于一致的状态，接着Master复制foo文件的元数据生成foo_backup，foo_backup同样指向C1，C2和C3。快照前，C1，C2和C3只被一个文件foo引用，因此引用计数为1；执行快照操作后，这些chunk的引用计数增加为2。以后客户端再次往C3追加数据时，Master发现C3的引用计数大于1，通知C3所在的Chunk Server本次拷贝C3生成C3′，客户端的追加操作也相应地转向C3′。

4.  ChunkServer设计

ChunkServer管理大小均为64MB的chunk，存储的时候需要保证chunk尽可能均匀地分布在不同的磁盘之中，可能考虑的因素包括磁盘空间，最近新建chunk数，等。另外，Linux文件系统删除64MB大文件消耗的时间太长，且没有必要，删除Chunk可以只将对应的chunk文件移动到每个磁盘中的回收站，以后新建chunk的时候可以重用。

ChunkServer是一个磁盘和网络IO密集型应用，为了最大限度地发挥机器性能，需要能够做到将磁盘和网络操作异步化，这会增加代码实现的难度。

5.  拓展

从GFS的架构中可以看出，GFS是一个具有良好可扩展性并能够在软件层面自动化处理各种异常情况的系统，但是自动化对系统的容错能力提出了很高的要求。在设计GFS时认为节点失效是常态，通过软件层面进行故障检测，并且通过chunk复制操作将原有故障节点的服务迁移到新的节点。系统还会根据一定策略比如磁盘使用情况，机器负载等执行负载均衡。由于软件层面的自动化容错，底层的硬件可以使用廉价的错误率较高的硬件。

GFS成功的经验表明：单Master的设计是可行的，不仅简化了系统，而且能够较好地实现一致性。但是单Master并不意味着实现GFS简单：基于性能考虑，GFS提出“记录至少原子性追加一次”的一致性模型，通过租约的方式将每个chunk的修改授权下放到ChunkServer从而减少Master负载，通过流水线的方式复制多个副本以减少延时，追加流程复杂繁琐。另外，Master维护的元数据很多，需要高效的数据结构，占用内存少且支持快照操作【支持写时复制的B树能满足Master的元数据管理需求，但是实现相当复杂】。

欢迎扫描二维码关注微信公众号 深度学习与数学   [每天获取免费的大数据、AI等相关的学习资源、经典和最新的深度学习相关的论文研读，算法和其他互联网技能的学习，概率论、线性代数等高等数学知识的回顾]