《大规模分布式存储系统》 第4章 分布式文件系统【4.1】
分布式文件系统的主要功能有两个：一个是存储文档、图像、视频之类的Blob类型数据；另外一个是作为分布式表格系统的持久化层。
分布式文件系统中最为著名的莫过于Google File System（GFS），它构建在廉价
的普通PC服务器之上，支持自动容错。GFS内部将大文件划分为大小约为64MB的数
据块（chunk），并通过主控服务器（Master）实现元数据管理、副本管理、自动负
载均衡等操作。其他文件系统，例如Taobao File System（TFS）、Facebook Haystack
或多或少借鉴了GFS的思路，架构上都比较相近。
本章首先重点介绍GFS的内部实现机制，接着介绍TFS和Face book Haystack的内
部实现。最后，本章还会简单介绍内容分发网络（Content Delivery Network,CDN）技
术，这种技术能够将图像、视频之类的数据缓存在离用户“最近”的网络节点上，从
而降低访问延时，节省带宽。
4.1 Google文件系统
Google文件系统（GFS）是构建在廉价服务器之上的大型分布式系统。它将服务
器故障视为正常现象，通过软件的方式自动容错，在保证系统可靠性和可用性的同
时，大大降低系统的成本。
GFS是Google分布式存储的基石，其他存储系统，如Google Bigtable、Google
Megastore、Google Percolator均直接或者间接地构建在GFS之上。另外，Google大规
模批处理系统MapReduce也需要利用GFS作为海量数据的输入输出。
4.1.1 系统架构
如图4-1所示，GFS系统的节点可分为三种角色：GFS Master（主控服务器）、
GFS ChunkServer（CS，数据块服务器）以及GFS客户端。
图 4-1 GFS整体架构
GFS文件被划分为固定大小的数据块（chunk），由主服务器在创建时分配一个
64位全局唯一的chunk句柄。CS以普通的Linux文件的形式将chunk存储在磁盘中。为
了保证可靠性，chunk在不同的机器中复制多份，默认为三份。
主控服务器中维护了系统的元数据，包括文件及chunk命名空间、文件到chunk之
间的映射、chunk位置信息。它也负责整个系统的全局控制，如chunk租约管理、垃圾
回收无用chunk、chunk复制等。主控服务器会定期与CS通过心跳的方式交换信息。
客户端是GFS提供给应用程序的访问接口，它是一组专用接口，不遵循POSIX规
范，以库文件的形式提供。客户端访问GFS时，首先访问主控服务器节点，获取与之
进行交互的CS信息，然后直接访问这些CS，完成数据存取工作。
需要注意的是，GFS中的客户端不缓存文件数据，只缓存主控服务器中获取的元
数据，这是由GFS的应用特点决定的。GFS最主要的应用有两个：MapReduce与
Bigtable。对于MapReduce,GFS客户端使用方式为顺序读写，没有缓存文件数据的必
要；而Bigtable作为分布式表格系统，内部实现了一套缓存机制。另外，如何维护客
户端缓存与实际数据之间的一致性是一个极其复杂的问题。
4.1.2 关键问题
1.租约机制
GFS数据追加以记录为单位，每个记录的大小为几十KB到几MB不等，如果每次
记录追加都需要请求Master，那么Master显然会成为系统的性能瓶颈，因此，GFS系
统中通过租约（lease）机制将chunk写操作授权给ChunkServer。拥有租约授权的
ChunkServe称为主ChunkServer，其他副本所在的ChunkServer称为备ChunkServer。租
约授权针对单个chunk，在租约有效期内，对该chunk的写操作都由主ChunkServer负
责，从而减轻Master的负载。一般来说，租约的有效期比较长，比如60秒，只要没有
出现异常，主ChunkServer可以不断向Master请求延长租约的有效期直到整个chunk写
满。
假设chunk A在GFS中保存了三个副本A1、A2、A3，其中，A1是主副本。如果副
本A2所在ChunkServer下线后又重新上线，并且在A2下线的过程中，副本A1和A3有
更新，那么A2需要被Master当成垃圾回收掉。GFS通过对每个chunk维护一个版本号
来解决，每次给chunk进行租约授权或者主ChunkServer重新延长租约有效期时，
Master会将chunk的版本号加1。A2下线的过程中，副本A1和A3有更新，说明主
ChunkServer向Master重新申请租约并增加了A1和A3的版本号，等到A2重新上线后，
Master能够发现A2的版本号太低，从而将A2标记为可删除的chunk,Master的垃圾回收
任务会定时检查，并通知ChunkServer将A2回收掉。
2.一致性模型
GFS主要是为了追加（append）而不是改写（overwrite）而设计的。一方面是因
为改写的需求比较少，或者可以通过追加来实现，比如可以只使用GFS的追加功能构
建分布式表格系统Bigtable；另一方面是因为追加的一致性模型相比改写要更加简单
有效。考虑chunk A的三个副本A1、A2、A3，有一个改写操作修改了A1、A2但没有
修改A3，这样，落到副本A3的读操作可能读到不正确的数据；相应地，如果有一个
追加操作往A1、A2上追加了一个记录，但是追加A3失败，那么即使读操作落到副本
A3也只是读到过期而不是错误的数据。
我们只讨论追加的一致性。如果不发生异常，追加成功的记录在GFS的各个副本
中是确定并且严格一致的；但是如果出现了异常，可能出现某些副本追加成功而某
些副本没有成功的情况，失败的副本可能会出现一些可识别的填充（padding）记
录。GFS客户端追加失败将重试，只要返回用户追加成功，说明在所有副本中都至少
追加成功了一次。当然，可能出现记录在某些副本中被追加了多次，即重复记录；
也可能出现一些可识别的填充记录，应用层需要能够处理这些问题。
另外，由于GFS支持多个客户端并发追加，多个客户端之间的顺序是无法保证
的，同一个客户端连续追加成功的多个记录也可能被打断，比如客户端先后追加成
功记录R1和R2，由于追加R1和R2这两条记录的过程不是原子的，中途可能被其他客
户端打断，那么GFS的chunk中记录的R1和R2可能不连续，中间夹杂着其他客户端追
加的数据。
GFS的这种一致性模型是追求性能导致的，这增加了应用程序开发的难度。对于
MapReduce应用，由于其批处理特性，可以先将数据追加到一个临时文件，在临时文
件中维护索引记录每个追加成功的记录的偏移，等到文件关闭时一次性将临时文件
改名为最终文件。对于上层的Bigtable，有两种处理方式，后面将会介绍。
3.追加流程
追加流程是GFS系统中最为复杂的地方，而且，高效支持记录追加对基于GFS实
现的分布式表格系统Bigtable是至关重要的。如图4-2所示，追加流程大致如下：
图 4-2 GFS追加流程
1）客户端向Master请求chunk每个副本所在的ChunkServer，其中主ChunkServer持
有修改租约。如果没有ChunkServer持有租约，说明该chunk最近没有写操作，Master
会发起一个任务，按照一定的策略将chunk的租约授权给其中一台ChunkServer。
2）Master返回客户端主副本和备副本所在的ChunkServer的位置信息，客户端将
缓存这些信息供以后使用。如果不出现故障，客户端以后读写该chunk都不需要再次
请求Master。
3）客户端将要追加的记录发送到每一个副本，每一个ChunkServer会在内部的
LRU结构中缓存这些数据。GFS中采用数据流和控制流分离的方法，从而能够基于网
络拓扑结构更好地调度数据流的传输。
4）当所有副本都确认收到了数据，客户端发起一个写请求控制命令给主副本。
由于主副本可能收到多个客户端对同一个chunk的并发追加操作，主副本将确定这些
操作的顺序并写入本地。
5）主副本把写请求提交给所有的备副本。每一个备副本会根据主副本确定的顺
序执行写操作。
6）备副本成功完成后应答主副本。
7）主副本应答客户端，如果有副本发生错误，将出现主副本写成功但是某些备
副本不成功的情况，客户端将重试。
GFS追加流程有两个特色：流水线及分离数据流与控制流。流水线操作用来减少
延时。当一个ChunkServer接收到一些数据，它就立即开始转发。由于采用全双工网
络，立即发送数据并不会降低接收数据的速率。抛开网络阻塞，传输B个字节到R个
副本的理想时间是B/T+RL，其中T是网络吞吐量，L是节点之间的延时。假设采用千
兆网络，L通常小于1ms，传输1MB数据到多个副本的时间小于80ms。分离数据流与
控制流主要是为了优化数据传输，每一台机器都是把数据发送给网络拓扑图上“最
近”的尚未收到数据的数据。举个例子，假设有三台ChunkServer：S1、S2和S3，S1与
S3在同一个机架上，S2在另外一个机架上，客户端部署在机器S1上。如果数据先从
S1转发到S2，再从S2转发到S3，需要经历两次跨机架数据传输；相对地，按照GFS
中的策略，数据先发送到S1，接着从S1转发到S3，最后转发到S2，只需要一次跨机
架数据传输。
分离数据流与控制流的前提是每次追加的数据都比较大，比如MapReduce批处理
系统，而且这种分离增加了追加流程的复杂度。如果采用传统的主备复制方法，追
加流程会在一定程度上得到简化，如图4-3所示：
图 4-3 GFS追加流程（数据流与控制流合并）
1）同图4-2 GFS追加流程：客户端向Master请求chunk每个副本所在的
ChunkServer。
2）同图4-2 GFS追加流程：Master返回客户端主副本和备副本所在ChunkServer的
位置信息。
3）Client将待追加数据发送到主副本，主副本可能收到多个客户端的并发追加
请求，需要确定操作顺序，并写入本地。
4）主副本将数据通过流水线的方式转发给所有的备副本。
5）每个备副本收到待追加的记录数据后写入本地，所有副本都在本地写成功并
且收到后一个副本的应答消息时向前一个副本回应，比如图4-3中备副本A需要等待
备副本B应答成功且本地写成功后才可以应答主副本。
6）主副本应答客户端。如果客户端在超时时间之内没有收到主副本的应答，说
明发生了错误，需要重试。
当然，实际的追加流程远远没有这么简单。追加的过程中可能出现主副本租约
过期而失去chunk修改操作的授权，以及主副本或者备副本所在的ChunkServer出现故
障，等等。由于篇幅有限，追加流程的异常处理留作读者思考。
4.容错机制
（1）Master容错
Master容错与传统方法类似，通过操作日志加checkpoint的方式进行，并且有一
台称为"Shadow Master"的实时热备。
Master上保存了三种元数据信息：
●命名空间（Name Space），也就是整个文件系统的目录结构以及chunk基本信
息；
●文件到chunk之间的映射；
●chunk副本的位置信息，每个chunk通常有三个副本。
GFS Master的修改操作总是先记录操作日志，然后修改内存。当Master发生故障
重启时，可以通过磁盘中的操作日志恢复内存数据结构。另外，为了减少Master宕机
恢复时间，Master会定期将内存中的数据以checkpoint文件的形式转储到磁盘中，从
而减少回放的日志量。为了进一步提高Master的可靠性和可用性，GFS中还会执行实
时热备，所有的元数据修改操作都必须保证发送到实时热备才算成功。远程的实时
热备将实时接收Master发送的操作日志并在内存中回放这些元数据操作。如果Master
宕机，还可以秒级切换到实时备机继续提供服务。为了保证同一时刻只有一台
Master,GFS依赖Google内部的Chubby服务进行选主操作。
Master需要持久化前两种元数据，即命名空间及文件到chunk之间的映射；对于
第三种元数据，即chunk副本的位置信息，Master可以选择不进行持久化，这是因为
ChunkServer维护了这些信息，即使Master发生故障，也可以在重启时通过
ChunkServer汇报来获取。
（2）ChunkServer容错
GFS采用复制多个副本的方式实现ChunkServer的容错，每个chunk有多个存储副
本，分别存储在不同的ChunkServer上。对于每个chunk，必须将所有的副本全部写入
成功，才视为成功写入。如果相关的副本出现丢失或不可恢复的情况，Master自动将
副本复制到其他ChunkServer，从而确保副本保持一定的个数。
另外，ChunkServer会对存储的数据维持校验和。GFS以64MB为chunk大小来划分
文件，每个chunk又以Block为单位进行划分，Block大小为64KB，每个Block对应一个
32位的校验和。当读取一个chunk副本时，ChunkServer会将读取的数据和校验和进行
比较，如果不匹配，就会返回错误，客户端将选择其他ChunkServer上的副本。
4.1.3 Master设计
1.Master内存占用
Master维护了系统中的元数据，包括文件及chunk命名空间、文件到chunk之间的
映射、chunk副本的位置信息。其中前两种元数据需要持久化到磁盘，chunk副本的位
置信息不需要持久化，可以通过ChunkServer汇报获取。
内存是Master的稀有资源，接下来介绍如何估算Master的内存使用量。chunk的元
信息包括全局唯一的ID、版本号、每个副本所在的ChunkServer编号、引用计数等。
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的系统瓶颈。
2.负载均衡
GFS中副本的分布策略需要考虑多种因素，如网络拓扑、机架分布、磁盘利用率
等。为了提高系统的可用性，GFS会避免将同一个chunk的所有副本都存放在同一个
机架的情况。
系统中需要创建chunk副本的情况有三种：chunk创建、chunk复制（re-
replication）以及负载均衡（rebalancing）。
当Master创建了一个chunk，它会根据如下因素来选择chunk副本的初始位置：1）
新副本所在的ChunkServer的磁盘利用率低于平均水平；2）限制每个Chunk-Server“最
近”创建的数量；3）每个chunk的所有副本不能在同一个机架。第二点容易忽略但却
很重要，因为创建完chunk以后通常需要马上写入数据，如果不限制“最近”创建的数
量，当一台空的ChunkServer上线时，由于磁盘利用率低，可能导致大量的chunk瞬间
迁移到这台机器从而将它压垮。
当chunk的副本数量小于一定的数量后，Master会尝试重新复制一个chunk副本。
可能的原因包括ChunkServer宕机或者ChunkServer报告自己的副本损坏，或者
ChunkServer的某个磁盘故障，或者用户动态增加了chunk的副本数，等等。每个chunk
复制任务都有一个优先级，按照优先级从高到低在Master排队等待执行。例如，只有
一个副本的chunk需要优先复制。另外，GFS会提高所有阻塞客户端操作的chunk复制
任务的优先级，例如客户端正在往一个只有一个副本的chunk追加数据，如果限制至
少需要追加成功两个副本，那么这个chunk复制任务会阻塞客户端写操作，需要提高
优先级。
最后，Master会定期扫描当前副本的分布情况，如果发现磁盘使用量或者机器负
载不均衡，将执行重新负载均衡操作。
无论是chunk创建，chunk重新复制，还是重新负载均衡，这些操作选择chunk副本
位置的策略都是相同的，并且需要限制重新复制和重新负载均衡任务的拷贝速度，
否则可能影响系统正常的读写服务。
3.垃圾回收
GFS采用延迟删除的机制，也就是说，当删除文件后，GFS并不要求立即归还可
用的物理存储，而是在元数据中将文件改名为一个隐藏的名字，并且包含一个删除
时间戳。Master定时检查，如果发现文件删除超过一段时间（默认为3天，可配
置），那么它会把文件从内存元数据中删除，以后ChunkServer和Master的心跳消息
中，每一个ChunkServer都将报告自己的chunk集合，Master会回复在Master元数据中
已经不存在的chunk信息，这时，ChunkServer会释放这些chunk副本。为了减轻系统的
负载，垃圾回收一般在服务低峰期执行，比如每天晚上凌晨1:00开始。
另外，chunk副本可能会因为ChunkServer失效期间丢失了对chunk的修改操作而导
致过期。系统对每个chunk都维护了版本号，过期的chunk可以通过版本号检测出来。
Master仍然通过正常的垃圾回收机制来删除过期的副本。
4.快照
快照（Snapshot）操作是对源文件/目录进行一个“快照”操作，生成该时刻源文
件/目录的一个瞬间状态存放于目标文件/目录中。GFS中使用标准的写时复制机制生
成快照，也就是说，“快照”只是增加GFS中chunk的引用计数，表示这个chunk被快照
文件引用了，等到客户端修改这个chunk时，才需要在ChunkServer中拷贝chunk的数据
生成新的chunk，后续的修改操作落到新生成的chunk上。
为了对某个文件做快照，首先需要停止这个文件的写服务，接着增加这个文件
的所有chunk的引用计数，以后修改这些chunk时会拷贝生成新的chunk。对某个文件执
行快照的大致步骤如下：
1）通过租约机制收回对文件的每个chunk写权限，停止对文件的写服务；
2）Master拷贝文件名等元数据生成一个新的快照文件；
3）对执行快照的文件的所有chunk增加引用计数。
例如，对文件foo执行快照操作生成foo_backup,foo在GFS中有三个chunk：C1、C2
和C3（简单起见，假设每个chunk只有一个副本）。Master首先需要收回C1、C2和C3
的写租约，从而保证文件foo处于一致的状态，接着Master复制foo文件的元数据用于
生成foo_backup,foo_backup同样指向C1、C2和C3。快照前，C1、C2和C3只被一个文
件foo引用，因此引用计数为1；执行快照操作后，这些chunk的引用计数增加为2。以
后客户端再次向C3追加数据时，Master发现C3的引用计数大于1，通知C3所在的
ChunkServer本次拷贝C3生成C3'，客户端的追加操作也相应地转向C3'。
4.1.4 ChunkServer设计
ChunkServer管理大小约为64MB的chunk，存储的时候需要保证chunk尽可能均匀
地分布在不同的磁盘之中，需要考虑的可能因素包括磁盘空间、最近新建chunk数
等。另外，Linux文件系统删除64MB大文件消耗的时间太长且没有必要，因此，删除
chunk时可以只将对应的chunk文件移动到每个磁盘的回收站，以后新建chunk的时候可
以重用。
ChunkServer是一个磁盘和网络IO密集型应用，为了最大限度地发挥机器性能，
需要能够做到将磁盘和网络操作异步化，但这会增加代码实现的难度。
4.1.5 讨论
从GFS的架构设计可以看出，GFS是一个具有良好可扩展性并能够在软件层面自
动处理各种异常情况的系统。Google是一家很重视自动化的公司，从早期的GFS，再
到Bigtable、Megastore，以及最近的Spanner,Google的分布式存储系统在这一点上一脉
相承。由于Google的系统一开始能很好地解决可扩展性问题，所以后续的系统能够
构建在前一个系统之上并且一步一步引入新的功能，如Bigtable在GFS之上将海量数
据组织成表格形式，Megastore、Spanner又进一步在Bigtable之上融合一些关系型数据
库的功能，整个解决方案完美华丽。
自动化对系统的容错能力提出了很高的要求，在设计GFS时认为节点失效是常
态，通过在软件层面进行故障检测，并且通过chunk复制操作将原有故障节点的服务
迁移到新的节点。系统还会根据一定的策略，如磁盘使用情况、机器负载等执行负
载均衡操作。Google在软件层面的努力获得了巨大的回报，由于软件层面能够做到
自动化容错，底层的硬件可以采用廉价的错误率较高的硬件，比如廉价的SATA盘，
这大大降低了云服务的成本，在和其他厂商的竞争中表现出价格优势。比较典型的
例子就是Google的邮箱服务，由于基础设施成本低，Gmail服务能够免费给用户提供
更大的容量，令其他厂商望尘莫及。
Google的成功经验也表明了一点：单Master的设计是可行的。单Master的设计不
仅简化了系统，而且能够较好地实现一致性，后面我们将要看到的绝大多数分布式
存储系统都和GFS一样依赖单总控节点。然而，单Master的设计并不意味着实现GFS
只是一些比较简单琐碎的工作。基于性能考虑，GFS提出了“记录至少原子性追加一
次”的一致性模型，通过租约的方式将每个chunk的修改授权下放到ChunkServer从而减
少Master的负载，通过流水线的方式复制多个副本以减少延时，追加流程复杂繁琐。
另外，Master维护的元数据有很多，需要设计高效的数据结构，占用内存小，并且能
够支持快照操作。支持写时复制的B树能够满足Master的元数据管理需求，然而，它
的实现是相当复杂的。
页:
[1]