注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

【google论文二】Google文件系统(上)  

2010-10-01 17:01:45|  分类: 搜索与分布式 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载请注明:http://duanple.blog.163.com/blog/static/7097176720109145829346/ 

作者 phylips@bmy 

摘要

我们设计实现了google文件系统,一个面向大规模分布式数据密集性应用的可扩展分布式文件系统。它运行在廉价的商品化硬件上提供容错功能,为大量的客户端提供高的整体性能。 

尽管与现有的分布式文件系统具有很多相同的目标,我们的设计更多的来源于对于我们的具体应用的负载类型以及当前甚至未来技术环境的观察,这就使得它与早期的文件系统表现出明显的不同。这也使得我们重新审视传统上的设计选择,探索出一些在根本上不同的设计观点。

 这个文件系统成功的满足了我们的存储需求。伴随这研究和开发的努力,在google内部,它已经作为那些需要大数据集服务的数据生成处理的基础存储平台而广泛部署。迄今为止,最大的集群可以通过超过一千台机器的数千块硬盘提供数百T的存储,这些存储空间可以由数百个客户端并发访问。

 在本论文中,我们将描述为了支持分布式应用的文件系统扩展接口设计,讨论很多我们的设计观点,展示来自于beachmark和现实世界的一些测量数据。

 分类和主题描述:分布式文件系统 

 常用词:设计,可靠性,性能,测量

 关键词:容错,可扩展,数据存储,集群存储

 导引

为了满足google快速增长的数据处理需求,我们设计实现了google文件系统(GFS)。GFS与传统的分布式文件系统具有很多相同的目标比如性能,可扩展性,可靠性,可用性。然而,它的设计是由我们的具体应用的负载类型以及当前甚至未来技术环境的观察驱动的,所以与早期文件系统的设计假设具有明显的区别。我们重新审视传统上的设计选择,探索出一些在根本上不同的设计观点。

 一,组件失败成为一种常态而不是异常。文件系统是由成百上千台通过廉价的商品化部件组装起来的存储机器构成,可以被大量的客户端访问。组件的数量和质量在本质上决定了在某一时间有一些是不可用的,有一些无法从当前的失败中恢复过来。我们观察到,应用程序的bug,操作系统bug,人为的错误,硬盘的失败,内存,连接器,网络,电力供应都可以引起这样的问题。因此经常性的监控,错误检测,容错和自动恢复必须集成到系统中。

 二,与传统的标准相比,文件是巨大的。在这里,好几个G的文件是很普通的。每个文件通常包含很多的应用程序处理的对象比如网页文档。当我们日常处理的快速增长的数据集合总是达到好几个TB的大小,包含数十亿的对象时,去处理数十亿个KB级别的文件即使文件系统支持也会显得很笨重。这样设计中的一些假设和参数,比如IO操作和块大小就必须重新定义。

三,大部分的文件更新模式是通过在尾部追加数据而不是覆盖现有数据。文件内部的随机写操作几乎是不存在的。一旦写完,文件就是只读的,而且通常是顺序读。大量的数据都具有这样的特点。有些可能是被数据分析程序扫描的库组成,有些可能是由运行中的应用程序持续生成的数据流,有些可能是档案数据,有些可能是数据需要由一台机器产生,然后由另一台机器处理而产生的中间结果。假设在大文件上数据访问具有这样的模式,那么当当缓存数据在客户端失效后,append操作就成为性能优化和原子性的关键。

 四,应用程序和文件系统api的协同设计,增加了整个系统的灵活性。比如我们通过放松了GFS的一致性模型大大简化了文件系统,同时也没有给应用程序带来繁重的负担。我们也提供了一个原子性的append操作,这样多个客户端就可以对同一个文件并行的进行append操作而不需要彼此间进行额外的同步操作。这些都会在后面进行详细的讨论。

 目前已经有多个GFS集群为了不同的目的而部署起来。最大的那个具有1000个存储节点,超过300T的磁盘空间,被来自不同机器的数百个客户端持续访问着。

 2 设计概览

2.1 假设

在设计一个满足我们需求的文件系统时,我们以一些充满了挑战和机遇的假设作为指南,之前我们曾间接的提到过一些关键的点,现在我们把这些假设再详细的列出来。

 系统是由廉价的经常失败的商品化组件构建而来。必须进行经常性的监控和检测,容错,并且能够从组件失败中迅速的恢复,这些都应该像是例行公事。

 系统存储了适度个数的大文件。我们期望有数百万个文件,每个100mb或者更大。上GB的文件大小应该是很普通的情况而且能被有效的管理。小文件也应该被支持,但我们不需要为它们进行优化。

 工作负载主要由两种类型的读组成:大的顺序流式读取和小的随机读取。在大的流式读取中,单个操作通常要读取数百k,甚至1m或者更大的数据。来自于同一个客户端的连续读取,通常读完文件的一个连续区域。小的随机读取通常在某个任意的偏移位置读取几kb的数据。具有性能意识的应用程序会把这些小的随机读取按批次,排序使得读取可以稳步的穿越整个文件而不是来回读取。

 工作负载有很多大的对文件数据的append操作,通常操作的大小类似与读操作。一旦写完,件就很少改变,在文件内部的随机写操作可以被支持,但是性能不必是很高的。

 系统对于良好定义的多个客户端对相同文件的并行append操作必须提供有效的实现。我们的文件通常是用来作为生产者消费者队列或者进行多路归并。数百个生产者(每个机器上运行一个)将会对同一个文件进行append。因此具有最小化同步开销的原子性是必要的。文件之后可能会被读取,或者消费者可能并行的读取这个文件。

 高的持续带宽比低延时更重要。我们大部分的目标应用都希望得到高速的批量数据处理速度,很少有对于单个的读写有严格的响应时间需求。

 2.2接口

GFS提供一个熟悉的文件系统接口,尽管它并没有实现一个诸如POSIX那样的标准API。文件通过目录进行层次化组织,通过路径来标识文件。支持常见的那些文件操作:create,delete,open,close,read,write。

 另外,GFS还具有快照和append操作。快照以很低的开销创建一个文件或者目录数的拷贝。Append操作允许多个客户端向同一个文件并发的操作,同时保证每个独立客户端的append操作的原子性。这对于实现多路归并的结果以及生成者消费者队列很有帮助,这样客户端不需要额外的锁操作就可以并行的append。我们发现这种文件类型,对于构建大型的分布式应用简直就是无价之宝。快照和append操作将会在3.4和3.3分别讨论。

 2.3架构

一个GFS集群由一个master和多个chunkserver组成,可以被多个client访问,如图1所示。

它们都是一个运行着用户级服务进程的商品化linux机器。可以很容易的在同一台机器上运行一个chunkserver和client,只要机器资源允许以及由于运行可能的片状应用程序代码带来的低可靠性是可以接受的。

 文件被划分成固定大小的chunk。每个chunk是由chunk创建时由master分配的一个不可变的全局唯一的64bit句柄来标识。Chunkserver将chunk作为linux文件存储在本地,对于chunk数据的读写通过chunk的handle和字节边界来表示。为了可靠性,每个chunk存储在多个chunkserver上。尽管用户可以为不同文件名字空间区域指定不同的备份级别,默认地我们存储三个备份。

 Master维护所有的文件系统元数据。包括名字空间,访问控制信息,文件与chunk的映射信息,chunk的当前位置。它也控制系统范围内的一些活动,比如chunk租赁管理,僵死chunk的垃圾回收,chunkserver间的chunk迁移。Master与chunkserver通过心跳信息进行周期性的通信,以发送指令和收集chunkserver的状态。

应用程序链接的GFS客户端代码实现了文件系统API以及代表应用程序与master和chunkserver进行通信以读写数据。客户端如果需要操作元数据则需要与master通信,但是所有的纯数据通信直接与chunksever通信。我们没有提供POSIX API,因此也就不需要与linux vnode layer关联。

 客户端或者chunkserver都不会进行文件数据缓存。客户端缓存只能得到很少的好处,因为大部分的应用需要直接读取整个大文件或者工作集合太大根本无法缓存。没有cache简化了客户端和整个系统,因为不需要考虑缓存一致性问题(实际上客户端会缓存元数据)。Chunkserver不需要进行文件数据缓存,是因为chunk是作为本地文件存储,这样linux自身会将那些经常访问的数据进行缓存。

 2.4 单Master

 只有一个master大大简化了我们的设计,而且使得master可以利用全局信息对chunk的放置和备份进行更好的判断。然而,我们必须最小化它在读写中的参与性,使得它不会成为一个瓶颈。Client永远不会通过master读取文件数据,它只是问master它应该同哪个chunkserver联系。并且client将这些信息在有限的时间段内进行缓存,直接与chunksever交互进行很多后续的操作。

【google论文一】Google文件系统 - 星星 - 银河里的星星

 

 根据图1,我们简单解释一些一个读操作的交互过程:首先,通过固定大小的chunk,客户端将应用程序中标识的文件名和offset转换为chunk的index。然后给master发送一个包含文件名和chunk index的请求,master返回相应的chunk的handle和所有备份的位置。客户端以文件名和chunk index为key将这条信息进行缓存。

 然后客户端给其中一个备份发送一个请求,通常是最近的那个。请求标识了chunk 的handle以及在那个chunk内的字节边界。直到缓存信息过期或者重新打开文件之前,对于相同chunk的后续读操作就不需要client-master的通信了。事实上,客户端通常在一个请求中查询多个chunk的信息,master也可以将这些被请求的多个chunk的信息包裹在一块进行返回。这种特别的信息,并没有额外的花费就避免了未来的client-master的多次通信。

 2.5 chunk大小

Chunk大小是一个关键的设计参数。我们选择了64mb,远远大于现有的文件系统块。每个chunk的副本作为普通的linux文件存储在chunkserver上,如果需要才会进行扩展。Lazy空间分配避免了内部碎片造成的空间浪费,很可能最大的碎片有向一个chunk那么大。

 大的chunk size提供了几个重要的优势。首先,降低了client与sever的交互需求,因为在相同chunk上的读写只需要一个初始化请求就可以从master得到chunk的位置信息。这个减少对于我们的应用负载是非常明显的,因为我们应用大部分需要顺序的读写整个大文件。即使对于小的随机读取,客户端也可以很容易的缓存一个几TB工作集的所有chunk的位置信息。其次,由于chunk很大,那么客户端就很有可能在一个给定的chunk上执行更多的操作,这样可以将一个与chunkserver的TCP连接保持更长的时间,这就减少了网络开销。再者,降低了存储在master上的元数据大小。这样就允许我们将元数据存放在内存中,反过来就带来了我们将在2.6.1中讨论的其他优势。

 另一方面,大的chunk size,即使采用了lazy空间分配,也有它的缺点。小的文件可能只有少数几个chunk,或许只有一个。如果很多的client都需要访问这个文件,这样那些存储了这些chunk的chunkserver就会变成热点。实际中,热点还没有成为一个主要的考虑点因为我们的应用绝大部分都是在顺序读大的多chunk文件。

 然而,当GFS第一次使用在一个批处理队列系统时,热点确实出现了:一个可执行文件作为一个chunk的文件写到GFS,然后同时在数百台机器上开始执行。存储了该可执行文件的那些chunkserver被数百个并发请求瞬间变成超载。我们通过更高的备份级别存储这样的可执行文件以及减慢队列系统的应用程序启动时间解决了这个问题。一个潜在的长远的解决方案是在这种情况下,允许客户端从其他客户端读取数据。

 2.6元数据

Master存储了三个主要类型的元数据:文件和chunk名字空间,文件到chunk的映射信息,每个chunk的备份的位置。所有的元数据都保存在master的内存中。前两种类型还通过将更新操作的日志保存在本地硬盘和备份在远程机器来保持持久化。使用log允许我们简单可靠地更新master的状态,不用担心当master crash的时候的不一致性。Master并没有永久保存chunk的位置信息,而是在master启动或者某个chunkserver加入集群时,它会向每个chunkserver询问它的chunks信息。

 2.6.1 内存数据结构

由于元数据存储在内存里,master的操作是很快的。因此对于master来说,可以简单有效地对在后台整个状态进行周期性扫描。这个周期性的扫描是用来实现chunk垃圾回收,chunkserver出现失败时进行的重复制,以及为了平衡负载和磁盘空间在chunkserver间的chunk 迁移。4.3 4.4将进一步讨论这些活动。

 这样全内存策略存在一个潜在的限制就是chunk的数目,因此整个系统的容量取决于master有多少可用内存。实际中这不是一个很严重的限制。Master为每个64MB的chunk维护少于64byte的数据。大部分的chunk是满的,因为大部分的文件包含多个chunk,只有最后一个chunk可能是未慢的。类似的,每个文件名字空间数据通常需要少于64byte因为文件名称存储时会使用前缀压缩算法进行压缩。

 如果需要支持更大的文件系统,只需要往master里添加内存。这点开销与通过将元数据存储到内存所得到简单性,可靠性,性能和灵活性,将是很小的一笔花费。

 2.6.2 chunk location

 Master并没有提供一个永久性的存储保存对于一个给定的chunk都是那些chunkserver保存了它的副本。它只是在启动时,简单地从chunkserver那里把这些信息拉过来。Master能够保证它自己是更新过的,因为是由它来控制chunk的放置,以及通过周期性的心跳信息来监控chunkserver。

 起初,我们尝试将chunk位置信息永久保存在master,但是我们发现在启动时去chunkserver请求这些数据更简单。这样避免了当chunkserver在加入或者离开集群,改名,失败,重启等待时需要的master与chunkserver间的同步。在一个数百台机器的集群中,这样的事件太经常了。

 理解这个设计决定的另一个方式是chunkserver对于自己有还是没有某个chunk具有最终的发言权。在master上维护一个这些信息一致性视图是没有意义的,因为发生在chunkserver上的错误可能使得一些chunk突然间不见了(比如硬盘可能会坏掉或者不可用),一个操作可能将chunkserver重命名。

 2.6.3操作日志

操作日志包含了关键元数据改变的历史记录。它是GFS的核心。它不仅是元数据的唯一一致性记录,而且它也定义了那些并发操作的逻辑上的时间表。文件和chunk的版本都是唯一和永恒地由它们创建时的逻辑时间来标识的。

 因此操作日志是很关键的,我们必须可靠地保存它,在任何元数据变更被持久化之前不应当被客户端看到。否则,我们将丢失整个文件系统或者最近的客户端操作即使chunckserver自己保存了它们。因此我们将它备份在多个远程机器上,对于一个客户端操作只有当该操作对应的日志记录被刷新到本地和远程的磁盘上时才会发出响应。Master将几个操作日志捆在一块刷新,从而降低刷新和复制对于整个系统吞吐率的影响。

 Master通过重新执行操作日志来恢复它的文件系统。为了最小化启动时间,我们必须将日志是保持在很小的规模。当日志增长超过一定的大小后,Master给它的状态设置检查点,它可以通过从本地磁盘加载最新的检查点进行恢复,然后重新执行那些在该检查点之后的日志记录。检查点保存了一个压缩的类B树的结构,不需要额外的解析就可以直接映射到内存用于名字空间查找。这大大提高了恢复的速度和可用性。

 因为建立一个检查点会花费一些时间,master的内部状态的结构设计使得一个新的检查点可以不需要延时那些接受到的变化就可以被创建。Master会启动一个新的线程切换到一个新的日志文件然后创建新的检查点。这个新的检查点包含在切换之前的所有变更。对于一个包含几百万文件的集群大概需要几分钟就可以完成。结束后,它将会被写回本地和远程的磁盘。

 恢复只需要最新完全的检查点和后来的日志文件。更老的检查点和日志文件可以自由的删除,当然我们会保存了一些来应对某些突发情况。在创建检查点的时候发生的失败不会影响系统的正确性,因为恢复代码会检测和跳过不完全的检查点。

 2.7一致性模型

 GFS使用的一个放松的一致性模型不但很好的支持了我们的高度分布式的应用,而且实现起来也相对简单和有效率。我们现在讨论GFS所提供的保证以及它们对应用程序的意味着什么。我们也会讲述GFS如何维护这些保证,但是会将具体的细节留到其他论文里讲述。

 2.7.1 GFS提供的保证

文件名字空间的改变(比如文件创建)是原子性的。它们只由master进行处理:名字空间锁来保证原子性和正确性(4.1节)。Master的操作日志定义了这些操作的全局性的排序。

 当数据变更后,文件区域的状态取决于变更的类型,变更是否成功以及是否是并发进行的。表1是对结果的一个概述。

【google论文二】Google文件系统(上) - 星星 - 银河里的星星

 

如果所有的客户端无论从哪个副本读取数据总是看到相同的数据,那么我们就说文件区域是一致的。如果文件数据变更后是一致的,同时客户端可以看到它所有的变更,那么我们就说文件区是已定义的。当一个变更成功后,且没有受到其他并发写者的影响,那么被影响的区域就是定义良好的(肯定是一致性的):所有的客户端将会看到所做的变更。并发的成功的变更,会使区域进入未定义的状态但是还是一致的:所有的客户端可以看到一致的数据,但是它可能无法看到所有的变更(如果变更是针对相同的数据写这样有的变更就会被新的变更所覆盖,这样用户就无法看到最先的变更了,同时发生在跨chunk的操作会被拆分成两个操作,这样这个操作的一部分可能会被其他操作覆盖,而另一部分则保留下来,如3.1节末尾所述)。通常它看到的是多个变更组合后的结果。一个失败的变更会使区域进入非一致的状态(因此也是未定义的状态):不同的客户端在不同的访问中可能看到不同的数据。我们下面描述下我们的应用程序如何区分定义良好的区域和未定义的区域。应用程序不需要进一步区分未定义区域的各种不同的类型。

 数据变更可能是写或者记录append。写操作会使数据在应用程序指定的偏移位置写入。记录append操作会使数据原子性的append,如果是并发性的话则至少会被append一次,但是偏移位置是由GFS决定的(然而,通常的理解可能是在客户端想写入的那个文件的尾部)。偏移位置会被返回给客户端,同时标记包含这条记录的那个定义良好的文件区域的起始位置。另外GFS可能会在它们之间插入一些padding或者记录的副本。它们会占据那些被认为是不一致的区域,通常它们比用户数据小的多。

 在一系列成功的变更之后,变更的文件区域被保证是已定义的,同时包含了最后一次变更的数据写入。GFS通过两种方式来实现这种结果a.将这些变更以相同的操作顺序应用在该chunk的所有的副本上,b.使用chunk的版本号来检测那些老旧的副本可能是由于它的chunkserver挂掉了而丢失了一些变更。陈旧的副本永远都不会参与变更或者返回给那些向master询问chunk位置的client。它们会优先参与垃圾回收。

 因为客户端会缓存chunk的位置,在信息更新之前它们可能会读到陈旧的副本。时间窗口由缓存值的超时时间以及文件的下一次打开而限制,文件的打开会清楚缓存中该文件相关的chunk信息。此外,由于我们的大部分操作都是记录的append,因此一个陈旧副本通常会返回一个过早结束的chunk而不是过时的数据。当读取者重试并与master联系时,它会立即得到当前的chunk位置。

 成功的变更很久之后,组件失败仍有可能破坏或者污染数据。GFS通过周期性的在master和所有chunkserver间握手找到那些失败的chunkserver,同时通过校验和(5.2节)来检测数据的污染。一旦发现问题,会尽快的利用正确的副本恢复(4.3节)。只有一个块的所有副本在GFS做出反应之前,全部丢失,这个块才会不可逆转的丢失,而通常GFS的反应是在几分钟内的。即使在这种情况下,块不可用,而不是被污染:应用程序会收到清晰的错误信息而不是被污染的数据。

2.7.2 对于应用程序的影响

GFS应用程序可以通过使用简单的技术来适应这种放松的一致性模型,这些技术已经为其他目的所需要:依赖与append操作而不是覆盖,检查点,写时自我验证,自己标识记录。

 实际中,我们所有的应用程序都是通过append而不是覆盖来改变文件。在一个典型应用中,一个写操作者会从头至尾生成一个文件。当写完所有数据后它自动的将文件重命名为一个永久性的名称,或者通过周期性的检查点检查已经有多少数据被成功写入了。检查点可能会设置应用级的校验和。读取者仅验证和处理最后一个检查点之前的文件区域,这些区域处于已定义的状态。无论什么样的并发和一致性要求,这个方法都工作的很好。Append操作比随机写对于应用程序的失败处理起来总是要更加有效和富有弹性。检查点允许写操作者增量性的重启(不需要重新从头写),允许读取者可以处理那些已经成功写入的数据,虽然在应该程序的看来仍然是不完全的。

 另一种典型的应用中,很多写者同时向一个文件append为了归并文件或者是作为一个生产者消费者队列。记录的append的append-at-least-once语义保证了每个写者的输出。读取者这样处理偶然的padding和重复数据。写者为每条记录准备一些额外信息比如校验和,这样它的合法性就可以验证。如果不能容忍重复的数据(比如它们可能触发非幂等操作),可以通过在记录中使用唯一标识符来过滤它们,很多时候都需要这些标识符命名相应的应用程序实体,比如网页文档。这些用于record输入输出的功能函数是以库的形式被我们的应用程序共享的,同时应用于gongle其他的文件接口实现。所以,相同系列的记录,加上一些罕见的重复,总是直接被分发给记录读取者。

 在以上的描述中,存在一个基本的假定:数据是以record形式存储的,而且通常这些record都是可以重复的,比如一个网页文档我们可以重复存,这对于数百亿的网页文档来说,存储少数多余的很正常,也就是说这些数据通常是文本,而不是二进制,所以我们才可以在append或者写时用记录的副本来覆盖非一致的区域,所以提供了append的append-at-least-once语义,因为append二次也是可以的。如果我们要保证唯一性,可以在应用层增加逻辑。 

  评论这张
 
阅读(15279)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018