Google文件系统研究
同济大学 计算机软件与理论 0720080247 李征
1 简介
为了适应Google日益增长的数据处理需求,Google设计并实现了Google文件系统(Google File System, GFS)。GFS在很多方面上与之前出现过的分布式文件系统有着相似的特性,比如性能、可扩展性、可靠性和可用性。但是,它的设计更多地基于我们对于我们的应用的特性的观察和技术环境,包括现在的和将来可能出现的,因此也与之前的文件系统设计有着显著的不同。Google仔细地考察过传统的取舍,并且在设计空间中对各种不同方案做了深入的研究。
首先,组件失败比出现异常更加常见。文件系统通常包含几百甚至几千台存储节点,每个节点由经济的部件组成,访问文件系统的客户端的数目通常也在差不多的量级上。这种组件的数量和质量几乎决定了要想在任意给定时刻访问任意组件是不可能的,并且有些组件不能自行从错误中恢复。我们经历过各种错误,包括应用程序的bug、操作系统的bug、人为错误、磁盘错误、内存错误、连接头错误、网络错误和电源错误等等。因此,常规性的系统监测、错误检测、容错和自动恢复必须集成在系统中。
其次,文件常常非常大。几个GB的文件很常见。每个文件往往包含很多应用对象,例如web文档。当我们经常处理那些快速增加的数据集的时候,每个数据集都有几个TB大小,并且包含几十亿的对象,管理几十亿个KB级别的文件是很笨拙的选择,即便有时候文件系统可以支持这样做。于是,例如I/O操作和块大小这样的设计假设和参数要重新考察。
第三,绝大部分的文件更多地是被扩展新的数据,而不是改写旧的数据。随机对文件内部进行写操作,更是在应用中不会出现的情况。一旦创建,文件即变成只读的,并且经常是顺序读。很多种数据都有这样的特点。有些是数据分析软件扫描用的大型数据集合,有些是运行着的应用程序创建的流数据,有些是存档的数据,有些是一台机器产生的即时数据,即将或者立即由另一台机器进行处理。结合这样的访问模式和大文件的特点,扩展文件就变成了性能优化和原子性保证的关键,而客户端缓冲数据块则失去了初衷。
第四,对于应用程序和文件系统API的合作设计,对于增加全系统的灵活性是有益的。例如,我们在不强制对应用增加负载的情况下,将GFS的一致性模型扩展到更加简化的文件系统上。我们同时引入了一个扩展文件的原子操作,这样就可以使得多个客户端可以同时扩展同一个文件,不至于带来同步和互斥问题。这些问题将在下面的内容中做详细介绍。
很多种GFS集群已经部署,并且被用于不同的目的。最大的一个集群包含超过1000台存储节点、超过300TB磁盘空间,并且被几百台客户端服务器连续高密度地访问。
2 设计概览
2.1 假定
为了设计符合我们需求的文件系统,我们首先必须确定一些包含挑战和机会的假定。我们之前已经提到过一些关键技术,下面将详细阐述一下各项假定。
- 系统由经济的、但是经常失败的组件构成。它必须经常监测并检测错误、容错并且能够迅速地从组件失败中恢复。
- 系统存储着适当数目的大文件。我们期望是几百万个文件,每个文件大约100MB或者更大。几个GB大小的文件是最常见的情况,应当能够有效率地处理。必须支持小文件,但是并不需要特别优化。
- 大部分工作主要有以下两种:大量的流读取和少量的随机读取。在大量的流读取中,每个典型的独立的操作读取几百KB,经常是1MB或者更多。同一客户端的连续操作往往发生在邻近的几个文件区域中。少量的随机读取典型地是从任意的偏移位置读取几个KB数据。性能敏感的应用程序会成批并且排序读取操作,使得操作是按照文件的前进顺序依次进行,而不是倒回去重新读某一个位置。
- 操作中也会有大量的大规模、对文件的顺序扩展写操作。典型的操作规模与读取操作一致。一旦写好,文件几乎不再被更改。少量的随机写操作也需要被系统所支持,但不需要特别进行性能优化。
- 系统必须在语义学上良好定义,使得多客户端可以进行同一个文件的并发扩展写。文件经常被用作生产者消费者模型的队列或者多路合并。几百个生产者,每台机器运行着一个生产者,将会对同一个文件进行并发扩展写。原子性保障和最小的同步化代价是必须的。这个文件可能会在不远的将来被读取,或者由一个消费者进程进行同时读取。
- 持续的高带宽要比低延迟更加重要。绝大部分的应用程序致力于以一个高速率处理批量数据,只有少量的应用要求单个读取或者写入操作要有很小的响应时间。
2.2 接口
GFS提供了一个熟悉的文件系统接口,虽然它并不是实现一个类似于POSIX那样的标准API接口。文件使用文件夹分层组织,并且由路径名识别。支持常见的创建、删除、打开、关闭、读取和写文件操作。
进一步地,GFS支持快照和记录扩展操作。快照操作以低代价创建一个文件或一个目录树的副本。记录扩展运行多客户端对同一个文件进行扩展写操作的同时,保证每个独立客户端的操作的原子性。这一特性对于多路合并结果和生产者消费者队列尤其有用,多个客户端可以同时操作,而不需要单独进行加锁操作。我们发现,在大型分布式应用程序中,这样的文件是无价的。
2.3 体系结构
一个GFS集群包含一个主节点和若干个子节点,能够由多个客户端所访问,如图1所示。每台机器都是典型的Linux主机,运行着用户级别的服务器进程。很容易地可以在同一台机器上同时运行子结点服务器程序和客户程序,机器资源是允许的,并且由运行脆弱的应用程序所导致的不可靠性是可以接受的。
文件被分割成固定大小的块。每个文件块由不变的且全局唯一的64位块标识唯一确定,这个标识由主节点在块被创建的时候指派。子结点把文件块作为普通Linux文件存储在本地磁盘上,并且根据块标识以及字节范围读取或写入块数据。为了可靠性,同一个块会在多台子结点上进行冗余存储,默认情况下存储三个副本,用户可以为不同的文件名字空间指定不同的冗余级别。
主节点存储关于文件系统的所有元数据。包含名字空间、访问控制信息、文件与文件块的对应信息以及文件块的位置信息。它也控制一些系统级别的活动,比如文件块租约管理、无关联文件块的垃圾收集以及子结点间的文件块合并。主节点使用心跳信息,不时地与各个子节点进行联系,发出指令并且收集这些子节点的状态信息。
连接到各个应用程序的GFS客户端代码通过文件系统API与主节点和子结点进行通讯,代替应用程序读取和写入数据。客户端从主节点进行元数据操作,读取数据块操作则直接去子结点完成。GFS并不提供POSIX式API,因此不需要引入Linux的vnode这一层概念。
客户端和子结点都不进行数据的缓存。客户端缓存数据只带来少量的好处,因为绝大部分应用程序按照流的方式读取大型文件或者所使用的工作数据集对于缓存来说过于庞大。不使用缓存机制可以简化客户端设计,并且使得整个系统消除了缓存不一致问题。(虽然如此,客户端仍然会缓存元数据)子节点不需要缓存文件数据,因为文件块是存储在本地文件系统中,Linux的缓存机制已经可以保证常用数据被缓存在内存当中了。
2.4 单主节点结构
使用单主节点设计能够大幅简化系统设计,并且使得主节点能够根据全局信息做出最优的块分配和冗余操作。但是我们必须对它的读取和写入操作进行优化,使得主节点不会成为一个瓶颈。客户端从不从主节点上读写文件数据。客户端仅仅询问主节点应该去联系哪台子结点。客户端会在一定时间内缓存这个信息,并且在随后很多操作中直接与子结点联系。
图1 GFS体系结构
下面结合图1对简单读操作进行详细解释。首先,利用固定的块大小信息,客户端将文件名和字节偏移量翻译成文件的块索引号。然后,它将这个索引号和文件名一起发送给主节点。主节点返回相应的块标识和副本的位置信息。客户端使用文件名和索引号作为索引缓存这个信息。
客户端向某一个副本所在的服务器发送请求,大部分情况是最近的那台。请求中指定了块标识和块内字节范围。接下来的对同一个块的读取将不再进行客户端与主节点的通讯,直到缓存到期或者文件被重新打开。实际上,客户端经常在同一个请求中要求多个块,主节点也可以同时返回这些信息。这些冗余信息可能会满足未来的需求,但又不在实际中带来多余的代价。
2.5 块大小
块的大小是一个系统设计中的关键参数。GFS选择了64MB,远远超过典型的文件系统中的块大小。每个块副本都作为普通Linux文件存储在各个子结点上,并且按照需要进行扩展。磁盘空间晚分配策略避免了内部碎片带来的空间浪费,空间浪费这一点可能是如此大的块大小所带来的最大的坏处。
较大的块大小带来了几个重要的优点。首先,它能够减少客户端与主节点的通信需求,因为对同一个块的读写只需要一次通讯来得到初始化的块位置信息。对于应用来说,这个通讯量减少相当有意义,因为应用程序经常读写大型文件。甚至对于少量的随机读取,客户端也可以顺利地缓存所有数TB级别大小的文件块位置信息。其次,使用较大的块大小时,客户端更可能会对给定的一个块进行很多操作,这可以减少网络开销,因为可以在一段时间内维持一个持久化的TCP连接。第三,可以减少主节点上存储的元数据数量。这可以使得主节点将元数据保存在内存中,带来我们将在2.6.1中讨论的诸多好处。
另外,较大的块大小,即便采取晚分配策略,仍然尤其缺点。一个小文件包含较少数量的块,也许只有一个块。存储这些块的子结点可能成为热点,因为很多客户端请求同一个文件。实际中,热点问题并未成为一个主要的问题,因为应用大部分读取的都是具有多个块的文件。
但是,热点问题在GFS刚刚应用于一个批队列系统的时候出现了:一个可执行文件被作为一个块写入GFS,然后几百台机器同时执行。这几个存储这个可执行文件的子结点因为并发请求而超过负载。我们通过在存储此类可执行文件的时候选用较大的副本数目,并且通过排队错开应用程序的执行时间解决了这个问题。一个可能的长期解决方案是,允许客户端从另一个客户端获取该文件。
2.6 元数据
主节点存储了三类元数据:文件和文件块名字空间、文件和文件块的对应关系和每个文件块副本的位置信息。所有的元数据保存在主节点的内存中。前两种元数据还作为日志保存在主节点磁盘上并且在远程机器上有一个备份。使用日志可以使得我们对于主节点的升级更加方便、可靠,并且不会担心由于主节点崩溃而导致数据不一致的风险。主节点并不持久化保存文件块位置信息。取而代之的是,每当一个子结点加入集群的时候,或者主节点启动的时候,主节点去询问该子结点上有哪些文件块。
2.6.1 内存内数据结构
因为元数据都保存在内存中,主节点的操作速度会很快。此外,主节点也可以很容易而且很有效率地定期在后台进行全局信息的扫描。这种定期扫描用于块垃圾回收、失败子结点上块的恢复以及为了平衡子结点负载或磁盘使用而进行的块的合并。
这种内存存储的方法的一个潜在问题是,整个系统所能包含的块的数目由主节点内存大小所限制。实际中这并不是一个严重的问题。主节点只为每64MB文件块数据保持不到64字节的元数据。大部分文件块是满的,因为大部分文件需要很多个文件块才能存储,只有最后一个才是不满的。类似地,文件名字空间数据往往对每个文件请求不到64字节的数据,因为使用了前缀压缩。
如果将来有支持更大的文件系统的需求,相对简洁性、可靠性、性能和可扩展性而言,为主节点添加内存所带来的代价是微乎其微的。
2.6.2 块位置分配
主节点并不存储一个给定的块在那台子结点上这种持久化信息。它只是在启动的时候简单地从子结点获取数据。主节点上的信息总是最新的,因为主节点可以控制所有的块位置信息,并且通过心跳信息监视各个子节点的状态。
我们一开始曾经尝试在主节点保持持久化的块位置信息,但是我们觉得启动的时候再从子结点获取信息更加简洁。主节点与子结点同步的问题主要是,如果子结点加入或者离开集群、改名、失败、重启之类的问题。在一个包含几百台服务器的集群中,这样的事件真的是太普遍了。
另一个理解这种设计方案的方式是认识到子结点自己对自己磁盘中包含或不包含哪些文件块有最终的发言权。在主节点上试图保持这样的信息是没有意义的,因为子结点上发生的错误会导致文件块丢失(例如磁盘可能坏掉或者不再可用),或者管理员可能重命名了子结点。
2.6.3 操作日志
操作日志记录了元数据的关键性改变。这是对GFS是很关键的。不仅仅因为它是元数据的唯一持久化记录,还因为它作为唯一的逻辑时间线,定义并记录了并发操作执行的顺序。文件和文件块,还有它们的版本都是在它创建的时候就在逻辑时间上永久且唯一确定了的。既然操作日志如此重要,我们必须可靠地保存它,并且在元数据更新到持久化存储之前,它的变化对客户端是不可见的。否则,即便文件块正常存储了,我们还是会丢失整个文件系统或者最近的客户端操作。因此,我们在远程机器上保留了备份,并且只在本地和远程都刷新日志到了磁盘,才发送客户端操作成功的相应。主节点将几个日志记录打包更新,从而降低了对系统吞吐量的影响。
主节点可以通过重新执行日志操作的方式恢复文件系统的状态。为了最小化启动时间,我们必须控制日志的大小在比较小的水平上。每当日志超过一定大小的时候,主节点设置一个检查点,这样主节点恢复状态的时候,就可以只执行最后一个检查点之后的有限条日志。检查点以紧凑B树格式存储在内存中,可以在名字空间查询是不带来多余的解析代价。这个特性更进一步地加速了恢复过程并且提升了可用性。
因为检查点的建立可能需要一定的时间,因此这样建立主节点的内部状态数据结构,可以使得检查点可以在变化发生前就建立起来。主节点切换到新的日志文件上继续记录,然后使用一个单独的线程创建新的检查点。新的检查点包含了所有切换前的变化。这可能需要一分钟或者更长的时间,因为一个集群可能会有几百万文件。一旦完成,将会立即写到本地和远程磁盘中。恢复操作只需要最近完成的检查点和之后的那部分日志。旧的检查点和日志可以删除,但是我们仍然会保持一些,防止大灾难的发生。创建检查点过程中发生的错误并不会影响正确性,因为恢复代码会监测并跳过不完整的检查点。
2.7 一致性模型
GFS放宽了一致性模型以便能够良好支持我们高度分布的应用程序,但是保持简单的关系和效率,以便可以方便地实现。下面讨论GFS能够保证的特性以及这些特性对于应用程序的意义。我们将重点放在GFS如何保持这些特性,具体细节将在其他部分去讨论。
2.7.1 GFS保证的特性
文件名字空间的变化(例如文件的创建)是原子操作。这些操作由主节点排他地处理:名字空间通过加锁保证原子性和正确性;主节点的操作日志定义了一个这些操作全局化的发生顺序。
表1 变化后的文件区域状态
一个数据变化发生后,文件区域是否受到影响,取决于变化的类型,而无论变化成功或者失败。表1概括了这个结果。如果所有客户端看到同样的数据,则文件区域是一致的,而不论它们分别读取的是哪个备份。如果一个文件的变化是一致的,则客户端可以看到全局上发生了怎样的变化,一个区域才因此而被定义。如果一个变化没有受到并行写入的影响而成功的时候,一个受影响区域因此定义(并且是一致的):所有的客户端将总会看到变化的情况。成功的并行变化将只是一致的,而并不定义区域:所有的客户端将看到同样的数据,但是可能反映变化的情况。典型地,多重变化会导致碎片的产生。一次失败的变化可能会导致区域的不一致(也是未定义的):不同的客户端可能会在不同的时候看到不同的数据。下面介绍一下应用程序是如何区别定义的和未定义的区域。应用程序不必进一步区分不同的未定义区域。
数据变化可能是以写入或者记录扩展的方式发生。一次写操作将使得数据在应用程序指定的文件偏移位置写入。一次记录扩展操作使得数据(即记录)自动被扩展至少一次,即便是在并行变化发生的过程中,但是发生在GFS指定的偏移位置上。(相比而言,正常的扩展操作是发生在客户端认为的文件结尾处)偏移将返回给客户端并且在包含这条记录的定义区域的开始做标记。更进一步地,GFS可能会在其中插入填充数据或者记录备份。它们占用了被认为是不一致的区域。在一系列变化成功完成之后,变化的文件区域被保证是已经定义的,并且包含了最后一次变化中写入的数据。GFS将记录这一变化,首先,在所有的文件块副本上应用这一变化,其次,使用文件块版本号确定某一个副本是陈旧的,可能由于子服务器down机而缺失了某次变化而导致。陈旧的副本不能参与任何新的变化,也不能在客户端请求块位置的时候作为结果返回给客户端。它们将会尽早地被作为垃圾清理掉。
因为客户端会缓存块位置信息,它们可能会在信息更新之前去读到一个陈旧的副本。这个窗口由缓存的生存期和下一次打开该文件的时间而决定,重新打开该文件会导致缓存全部更新。更进一步地,既然大部分的文件是只用来扩展的,陈旧的副本只会返回一个错误的文件尾位置,而不是过期的数据。当一个读文件的客户端重试的时候会联系主节点,然后会立即得到新的文件块位置。
一次变化成功很长时间之后,组件的故障依然会导致数据的破坏。GFS通过常规性的主节点与子结点之间握手以及检查校验和的方式识别故障的子结点。一旦发现一个问题,数据将尽快通过正确的副本恢复回来。一个文件块丢失的情况只会发生在当所有的文件块副本在GFS做出操作之前都丢失的情况,典型地是在几分钟之内。即便是这种情况,文件块只是不可用,而不是被毁坏:客户端将收到错误,而不是毁坏的数据。
2.7.2 对于应用程序的意义
GFS客户端可以适应这种宽松的一致性模型,这几种简单的技术已经用于其他的目的:依赖于扩展而不是复写、检查点、写自检、可自我检查的记录。实际中所有的应用程序修改文件的方式都是扩展而不是复写。在一种典型的应用中,一个写文件器从开始到结束完整地生成一个文件。在所有数据写完后,它会自动地重命名这个文件,或者周期性地生成检查点,控制多少数据已经成功地写入。检查点还可能会包含应用程序自己的校验和。写入器只处理和校验上次成功的检查点建立以来的文件区域,也即处于定义状态的部分。不考虑一致性和并发性的情况下,这种应用很好地处理了我们的需求。扩展写比起随机写更具效率和弹性。检查点可以使得写入器能够阶段性地重启下一操作,而不用再去处理已经成功写入的部分。
在另一种典型应用中,很多个写入器并发地扩展一个文件,合并结果或者排在生产者消费者队列中。记录被扩展的位置是语义学上最后一次写入的位置。读取器处理偶然的填充数据和冗余数据。每条记录都含有写入器生成的类似校验和的冗余数据,这样使得数据可以被校验。读取器可以根据校验和识别多余的填充和记录碎片。
3 参考资料
[1]. The Google File System, Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, Google.
你们这个GOOGLE搜索就是垃圾。。。
要是我做的Google就好了~