google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型

所需积分/C币:36 2011-12-02 18:09:50 2.4MB PDF
收藏 收藏
举报

google三大论文 gfs bigtable mapreduce hadoop hdfs hbase原型,学hadoop 必看
张表可以有无限多个列。 列关键字的命名语法如下:列族:限定词。列族的名字必须是可打印的字符串,而限定词的名字可以是 任意的字符串。比如, Webtable有个列族 language, language列族用来存放撰写网页的语言。我们在 anguage列族中只使用一个列关键字,用来存放每个网页的语言标识|D。 Webtable中另一个有用的列族 是 anchor;这个列族的每一个列关键字代表一个锚链接,如图一所示。 Anchor列族的限定词是引用该网 页的站点名; Anchor列族每列的数据项存放的是链接文本 访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的 Webtable的例子中,上述的控制权 限能帮助我们管理不同类型的应用:我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数 据并创建继承的列族、一些应用则只允许浏览数据(甚至可能因为隐私的原因不能浏览所有数据) 时问鼗 在 Bigtable中,表的每一个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索 引。 Bigtable时间戳的类型是64位整型。 Bigtable可以给时间戳赋值,用来表示精确到亳秒的“实时”时 司;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突,那么它必须自己生成具有唯一 性的时间戳。数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。 为了减轻多个版本数据的管理负担,我们对每一个列族配有两个设置参数, Bigtable通过这两个参数可以 对废弃版本的数据白动进行垃圾收集。用户可以指定只保存最后n个版本的数据,或者只保存“足够新的 版本的数据(比如,只保存最近7天的内容写入的数据)。 在 Webtable的举例里, contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾 收集机制可以让我们只保留最近三个版本的网页数据 3 API Bigtable提供了建立和删除表以及列族的AP函数。 Bigtable还提供了修改集群、表和列族的元数据的 AP|,比如修改访问权限 //Open the table Table *T= Open Or Die("/bigtable/web/ webtable") Write a new anchor and delete an old anchor Row Mutation rI(T, com. cnn WWW"); rl.set("anChor:www.c-span.org","cnn): rl.delete("anchor:www.abc.com") Operation op Apply(∝Op,&r1) Figure 2: Writing to Bigtable. 客户程序可以对 Bigtable进行如下的操作:写入或者删除 Bigtable中的值、从每个行中查找值、或者遍历 表中的一个数据子集。图2中的C++代码使用 RoW Mutation抽象对象进行了一系列的更新操作。(为了 保持示例代码的简洁,我们忽略了一些细节相关代码)。调用Appy函数对 Webtable进行了一个原子修改 操作:它为www.cnn.con增加了一个锚点,同时删除了另外一个铺点。 Scanner scanner(T) Scan stream *stream: stream scanner Fetch Column Family("anchor"); stream->SetReturnAlVersions() scanner Lookup("com. cnn WWw") for ( Istream->Done(; stream->Next()i printi(“%s%s%ld%sⅦn", scanner. Row Name stream->ColumnName( stream->MicroTimestamp() stream->Value) Figure 3: Reading from Bigtable. 图3中的C十+代码使用 Scanner抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族,有几种 方法可以对扫描输出的行、列和时间戳进行限制。例如,我们可以限制上面的扫描,让它只输出那些匹配 正则表达式* cnn. com的铺点,或者那些时间戳在当前时间前10天的错点。 Bigtable还支持一些其它的特性,利用这些特性,用户可以对数据进行更复杂的处理。首先, Bigtable支 持单行上的事务处理,利用这个功能,用户可以对存储在一个行关键字下的数据进行原子性的读更新写 操作。虽然 Bigtable提供了一个允许用户跨行批量写入数据的接口,但是, Bigtable目前还不支持通用的 跨行事务处理。其次, Bigtable允许把数据项用做整数计数器。最后, Bigtable允许用户在服务器的地址 空间内执行脚本程序。脚本程序使用 Google开发的 Sawzall【28】数据处理语言。虽然目前我们基于的 saW乙a语言的AP函数还不允许客户的脚本程序写入数据到 Bigtable,但是它允许多种形式的数据转换 基于任意表达式的数据过滤、以及使用多种操作符的进行数据汇总 Bigtable可以和 MapReduce【12】一起使用, Map Reduce是 google开发的大规模并行计算框架。我们 已经开发了一些 Wrapper类,通过使用这些 Wrapper类, Bigtable可以作为 Map Reduce框架的输入和输 出 4 Big Table构件 Bigtable是建立在其它的几个 Google基础构件上的。 Big Table使用 Google的分布式文件系统(GFS 【17】存储日志文件和数据文件。 Big Table集群通常运行在一个共享的机器池中,池中的机器还会运行其 它的各种各样的分布式应用程序, Big table的进程经常要和其它应用的进程共享机器。 Big Table依赖集群 管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。 Big Table内部存储数据的文件是 Google SSTable格式的。 SSTable是一个持久化的、排序的、不可更改的 Map结构,而Map是一个 key-value映射的数据结构,key和vaue的值都是任意的Byte串。可以对 SSTable进行如下的操作:查询与一个key值相关的vaue,或者遍历某个key值范围内的所有的key value对。从内部看, SSTable是一系列的数据块(通常每个块的大小是64KB,这个大小是可以配置 的)。 SSTable使用块索引(通常存储在 SSTable的最后)来定位数据块;在打开 SSTable的时候,索引被 加载到内存。每次查找都可以通过一次磁盘搜索完成:首先使用二分查找法在内存中的索引里找到数据块 的位置,然后再从硬盘读取相应的数据块。也可以选择把整个 SSTable都放在内存中,这样就不必访问硬 盘了。 Big Table还依赖一个高可用的、序列化的分布式锁服务组件,叫做 Chubby【8】。一个 Chubby服务包括 5个活动的副本,其中的一个副本被选为 Master,并且处理请求。只有在大多数副本都是正常运行的 并且彼此之间能够互相通信的情况下, Chubby服务才是可用的。当有副本失效的时候, Chubby使用 阳axos算法【9,23】来保证副本的一致性。 Chubby提供了一个名字空间,里面包括了目录和小文件。每 个目录或者文件可以当成一个锁,读写文件的操作都是原子的。 Chubby客户程序库提供对 Chubby文件 的一致性缓存。每个 Chubby客户程序都维护一个与 Chubby服务的会话。如果客户程序不能在租约到期 的时间内重新签订会话的租约,这个会话就过期失效了(aex注:又用到了ease。原文是: A Client's session expires if it is unable to renew its session lease within the lease expiration time. ) y 个会话失效时,它拥有的锁和打开的文件句柄都失效了。 Chubby客户程序可以在文件和目录上注册回 调函数,当文件或目录改变、或者会话过期时,回调函数会通知客户程序。 Bigtable使用 Chubby完成以下的几个任务:确保在任何给定的时间内最多只有一个活动的 Master副本 存储 Big Table数据的自引导指令的位置(参考5.1节);查找 Tablet服务器,以及在 Tablet服务器失效时进 行善后(5.2节);存储 Big Table的模式信息(每张表的列族信息);以及存储访问控制列表。如果 Chubby长时间无法访问, Big Table就会失效。最近我们在使用11个 Chubby服务实例的14个 Big Table 集群上测量了这个影响。由于 Chubby不可用而导致 Big Table中的部分数据不能访问的平均比率是 0.0047%( Chubby不能访问的原因可能是 Chubby本身失效或者网络问题)。单个集群里,受 Chubby 失效影响最大的百分比是0.0326%(aex注:有点莫名其妙,原文是: The percentage for the single cluster that was most affected by Chubby unavailability was 0.0326%.) 5介绍 Bigtable包括了三个主要的组件:链按到客户程序中的库、一个 Master服务器和多个blet服务器。针对 系统工作负载的变化情况, Big Table可以动态的向集群中添加(或者删除) Tablet服务器 Master服务器主要负责以下工作:为 Tablet服务器分配 Tablets、检测新加入的或者过期失效的Tbe服务 器、对 Tablet服务器进行负载均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外,它还处理对模 式的相关修改操作,例如建立表和列族 每个 Tablet服务器都管理一个 Tablet的集合(通常每个服务器有大约数十个至上千个 Tablet)。每个 Tablet服务器负责处理它所加载的 Tablet的读写操作,以及在 Tablets过大时,对其进行分割。 和很多 Single- Master类型的分布式存储系统[1721】类似,客户端读取的数据都不经过 Master服务 器:客户程序直接和 ab let服务器通信进行读写操作。由于 Big Table的客户程序不必通过 Master服务器来 获取 Tablet的位置信息,因此,大多数客户程序甚至完全不需要和 Master服务器通信。在实际应用 中, Master服务器的负载是很轻的 个 Big Table集群存储了很多表,每个表包含了一个Tbet的集合,而每个 Tablet包含了某个范围内的行 的所有相关数据。初始状态下,一个表只有一个 Tablet。随着表中数据的增长,它被自动分割成多个 Tablet,缺省情况下,每个 Tablet的尺寸大约是100MB到200MB 51 Tablet的位置 我们使用一个三层的、类似B+树[0]的结构存储Tbet的位置信息(如图4) User tablet Other METADATA tablets Root tablet Chubby file (st MEIADA IA tadle.) ---=--=--= 二二二二二二二二二二 User tablen Figure 4: Tablet location hierarchy 第一层是个存储在 Chubby中的文件,它包含了 Root tablet的位置信息。 Root tablet包含了一个特殊 的 METADATA表里所有的Tabe的位置信息。 METADATA表的每个 Table包含了一个用户Tabe的集合 Root tab let实际上是 METADATA表的第一个Tbet,只不过对它的处理比较特殊一 Root tablet永远不会 被分割一这就保证了 Tablet的位置信息存储结构不会超过三层。 在 METADATA表里面,每个 Tab let的位置信息都存放在一个行关键字下面,而这个行关键字是由 Tab let所 在的表的标识符和Tbet的最后一行编码而成的。 METADATA的每一行都存储了大约1KB的内存数据。在 个大小适中的、容量限制为128MB的 METADATA Table中,采用这种三层结构的存储模式,可以标识 2^34个Tbt的地址(如果每个Tbet存储128MB数据,那么一共可以存储2^61字节数据)。 客户程序使用的库会缓存Tbet的位置信息。如果客户程序没有缓存某个 Tablet的地址信息,或者发现它 缓存的地址信息不正确,客户程序就在树状的存储结构中递归的查询able位置信息;如果客户端缓存是 空的,那么寻址算法需要通过一次网络来回通信寻址,这其中包括了一次 Chubby读操作;如果客户端缓 存的地址信息过期了,那么寻址算法可能需要最多6次网络来回通信才能更新数据,因为只有在缓存中没 有查到数据的时候才能发现数据过期(ax注:其中的三次通信发现缓存过期,另外三次更新缓存数据) (假设 METADATA的 Table没有被频繁的移动)。尽管 Tablet的地址信息是存放在内存里的,对它的操作不 必访问GFS文件系统,但是,通常我们会通过预取lbet地址来进一步的减少访问的开销:每次需要从 METADATA表中读取一个abe的元数据的时候,它都会多读取几个Tabe的元数据 在 METADATA表中还存储了次级信息(aex注: secondary information),包括每个able的事件日志 (例如,什么时候一个服务器开始为该labe提供服务)。这些信息有助于排查错误和性能分析 52 Tablet分配 在任何一个时刻,一个abet只能分配给一个 abet服务器。 Master服务器记录了当前有哪些活跃的 Tablet服务器、哪些 Tablet分配给了哪些 abet服务器、哪些 Tablet还没有被分配、当一个 Tablet还没有被 分配、并且刚好有一个 Tablet服务器有足够的空闲空间装载该abe时, Master服务器会给这个Tbet服 务器发送一个装载请求,把阳bet分配给这个服务器 Big Table使用 Chubby跟踪记录 Tablet服务器的状态。当一个ab|e服务器启动时,它在 Chubby的一个 指定目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。 Master服务器实时监控着这个目录 (服务器目录),因此 Master服务器能够知道有新的 Tablet服务器加入了。如果 Tablet服务器丢失了 Chubby上的独占锁一比如由于网络断开导致 Tablet服务器和 Chubby的会话丢失一它就停止对 Tablet 提供服务。( Chubby提供了一种高效的机制,利用这种机制, Tablet服务器能够在不增加网络负担的情 况下知道它是否还持有锁)。只要文件还存在, Tablet服务器就会试图重新获得对该文件的独占锁;如果 文件不存在了,那么Tbet服务器就不能再提供服务了,它会自行退出(alex注: so it k∥/ s tse)。当 Tablet服务器终止时(比如,集群的管理系统将运行该 abet服务器的主机从集群中移除),它会尝试释 放它持有的文件锁,这样一来, Master服务器就能尺快把 Tablet分配到其它的 abet服务器 Master服务器负责检查一个 Tablet服务器是否已经不再为它的 Tablet提供服务了,并且要尽快重新分配它 加载的 Tablet。 Master服务器通过轮询 Tablet服务器文件锁的状态来检测何时hbe服务器不再为 Tablet 提供服务。如果一个Tbet服务器报告它丢失了文件锁,或者 Master服务器最近几次尝试和它通信都没有 得到响应, Master服务器就会尝试获取该lbet服务器文件的独占锁;如果 Master服务器成功获取了独占 锁,那么就说明 Chubby是正常运行的,而 Tablet服务器要么是宕机了、要么是不能和 Chubby通信了 因此, Master服务器就删除该abet服务器在 Chubby上的服务器文件以确保它不再给Tbet提供服务 且 Tablet服务器在 Chubby上的服务器文件被删除了, Master服务器就把之前分配给它的所有的Tbet 放入未分配的 Tablet集合中。为了确保 Bigtable集群在 Master服务器和 Chubby之间网络出现故魔的时候 仍然可以使用, Master服务器在它的 Chubby会话过期后主动退出。但是不管怎样,如同我们前面所描述 的, Master服务器的故障不会改变现有lbet在 Tablet服务器上的分配状态。 当集群管理系统启动了一个 Master服务器之后, Master服务器首先要了解当前 Tablet的分配状态,之后才 能够修改分配状态。 Master服务器在启动的时候执行以下步骤:(1) Master服务器从 Chubby获取一个 唯一的 Master锁,用来阻止创建其它的 Master服务器实例;(2) Master服务器扫描 Chubby的服务器文 件锁存储目录,获取当前正在运行的服务器列表;(3) Master服务器和所有的正在运行的Tabe表服务 器通信,获取每个Tbe服务器上Tbet的分配信息;(4) Master服务器扫描 METADATAz表获取所有的 Tab let的集合。在扫描的过程中,当 Master服务器发现了一个还没有分配的 Tablet, Master服务器就将这 个 Tablet加入未分配的Tbet集合等待合适的时机分配 可能会遇到一种复杂的情况:在 METADATA表的 Table还没有被分配之前是不能够扫描它的。因此,在开 始扫描之前(步骤4),如果在第三步的扫描过程中发现 Root Tablet还没有分配, Master服务器就把Root Tabt加入到未分配的 Table集合。这个附加操作确保了 Root tablet会被分配,由于 Root tablet.包括了 所有 METADATA的 Table的名字,因此 Master服务器扫描完 Root Tablet以后,就得到了所有的 METADATA表的Tbe的名字了 保存现有b|e的集合只有在以下事件发生时才会改变:建立了一个新表或者删除了一个旧日表、两个 Tablet被合并了、或者一个 Tablet被分割成两个小的 Tablet。 Master服务器可以跟踪记录所有这些事件, 因为除了最后一个事件外的两个事件都是由它启动的。lblt分割事件需要特殊处理,因为它是由 Tablet 服务器启动。在分割操作完成之后,Tbe服务器通过在 METADATA表中记录新的 Tablet的信息来提交这 个操作;当分割操作提交之后, Tablet服务器会通知 Master服务器。如果分割操作已提交的信息没有通知 到 Master服务器(可能两个服务器中有一个宕机了), Master服务器在要求lbe服务器装载已经被分割 的子表的时候会发现一个新的 Tablet。通过对比 METADATA表中 Table的信息, Tab let服务器会发现 Master服务器要求其装载的Tblt并不完整,因此, Tablet服务器会重新向 Master服务器发送通知信息 53 Tablet服务 memtable Read Op Memory GFS tablet log Write Op SSTable files Figure 5: Tablet Representation 如图5所示, abet的持久化状态信息保存在GFS上。更新操作提交到REDO日志中(aex注: Updates are committed to a commit log that stores redo records)。在这些更新操作中,最近提交的那些 存放在一个排序的缓存中,我们称这个缓存为 memtable;较早的更新存放在一系列 SSTable中。为了恢 复一个Tbet,Tble服务器首先从 METADATA表中读取它的元数据。 Tablet的元数据包含了组成这个 Tablet的 SSTable的列表,以及一系列的 Redo point(aex注: a set of redo points),这些Redo Point指向可能含有该 Tablet数据的已提交的日志记录。 Tablet服务器把 SSTable的索引读进内存,之后通 过重复 Redo point之后提交的更新来重建 memtable 当对 abet服务器进行写操作时, Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执 行这个操作的权限。权限验证的方法是通过从一个 Chubby文件里读取出来的具有写权限的操作者列表来 进行验证(这个文件几乎定会存放在 Chubby客户缓存里)。成功的修改操作会记录在提交日志里。可 以采用批量提交方式(a/ex注: group commit)来提高包含大量小的修改操作的应用程序的吞吐量 【13,16】。当一个写操作提交后,写的内容插入到 memtable里面 当对Tbet服务器进行读操作时, Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个 由一系列 SSTable和 memtable合并的视图里执行。由于 SSTable和 memtable是按字典排序的数据结 构,因此可以高效生成合并视图 当进行 Tablet的合并和分割时,正在进行的读与操作能够继续进行。 5.4 Compactions (alex注:这个词挺简单,但是在这节里面挺难翻译的。应该是空间缩减的意思,但是似平又不能完全概括 它在上下文中的意思,干脆,不翻译了) 随着写操作的执行, memtable的大小不断增加。当 memtable的尺寸到达一个门限值的时候,这个 memtable就会被冻结,然后创建一个新的 memtable;被冻结住 memtable会被转换成 SSTable,然后 写入GFS(ax注:我们称这种 Compaction行为为 Minor Compaction)。 Minor Compaction过程有 两个目的: shrink(aex注: shrink是数据库用语,表示空间收缩) abet服务器使用的内存,以及在服务 器灾难恢复过程中,减少必须从提交日志里读取的数据量。在 Compaction过程中,正在进行的读写操作 仍能继续 每一次 Minor Compaction都会创建一个新的 SSTable。如果 Minor Compaction过程不停滞的持续进行 下去,读操作可能需要合并来自多个 SSTable的更新;否则,我们通过定期在后台执行 Merging Compaction过程合并文件,限制这类文件的数量。 Merging Compaction过程读取一些 SSTablei和 memtable的内容,合并成一个新的 SSTable。只要 Merging Compaction过程完成了,输入的这些 SSTable和 Imemtable就可以删除了 合并所有的 SSTable并生成一个新的 SSTable的 Merging Compaction过程叫作 Major Compaction。由 非 Major( com pactioη产生的55 Table可能含有特殊的删除条目,这些删除条目能够隐藏在旧的、但是依 然有效的 SSTable中已经删除的数据(aex注:令人费解啊,原文是S57 ables produced by non- mayor compactions can contain special deletion entries that suppress deleted data in older SSTab/ es that are still live)。而 Major Compaction过程生成的 SSTable不包含已经删除的信息或数 据。 Bigtable循环扫描它所有的 Tablet,并且定期对它们执行 Major Compaction。 Major Compaction 机制允许 Bigtable回收已经删除的数据占有的资源,并且确保 Big Table能及时清除已经删除的数据(a/eⅹ 注:实际是回收资源。数据删除后,它占有的空间并不能马上重复利用;只有空间回收后才能重复使 用),这对存放敏感数据的服务是非常重要。 6优化 上一章我们描述了 Bigtable的实现,我们还需要很多优化工作才能使 Bigtable到达用户要求的高性能、高 可用性和高叮靠性。本章描述了 Bigtable实现的其它部分,为了更好的强调这些优化工作,我们将深入细 局部性群组 客户程序可以将多个列族组合成一个局部性群族。对 Tab leti中的每个局部性群组都会生成一个单独的 SSTable。将通常不会一起访冋的列族分割成不同的局部性群组可以提高读取操作的效率。例如,在 Webtable表中,网页的元数据(比如语言和 Checksum)可以在一个局部性群组中,网页的内容可以在 另外一个群组:当一个应用程序要读取网页的元数据的时候,它没有必要去读取所有的贞面内容 此外,可以以局部性群组为单位设定一些有用的调试参数。比如,可以把一个局部性群组设定为全部存储 在内存中。τable服务器依照惰性加载的策略将设定为放入内存的局部性群组的 SSTable装载进内存。加 载完成之后,访问属于该局部性群组的列族的时候就不必读取硬盘了。这个特性对于需要频繁访问的小块 数据特别有用:在 Bigtable内部,我们利用这个特性提高 METADATA表中具有位置相关性的列族的访问速 度。 压缠 客户程序可以控制个局部性群组的 SSTable是否需要压缩;如果需要压缩,那么以什么格式来压缩。每 个 SSTable的块(块的大小由局部性群组的优化参数指定)都使用用户指定的压缩格式来压缩。虽然分块 压缩浪费了少量空间aex注:相比于对整个SS7be进行压缩,分块压缩压缩率较低),但是,我们在 只读取 SSTable的一小部分数据的时候就不必解压整个文件了。很多客户程序使用了“两遍的、可定制的 压缩方式。第一遍采用 Bentley and Mcllroy's方式[6],这种方式在一个很大的扫描窗口里对常见的长字 符串进行压缩;第二遍是采用快速压缩算法,即在一个16KB的小扫描窗口中寻找重复数据。两个压缩的 算法都很快,在现在的机器上,压缩的速率达到100-200MB/s,解压的速率达到400-1000MB/s。 虽然我们在选择压缩算法的时候重点考的是速度而不是压缩的空间,但是这种两遍的压缩方式在空间压 缩率上的表现也是令人惊叹。比如,在 Webtable的例子里,我们使用这种压缩方式来存储网页内容。在 次测试中,我们在一个压缩的局部性群组中存储了大量的网页。针对实验的目的,我们没有存储每个文 档所有版本的数据,我们仅仅存储了一个版本的数据。该模式的空间压缩比达到了101。这比传统的Gzp 在压缩HTML页面时3:1或者4:1的空间压缩比好的多;“两遍"的压缩模式如此高效的原因是由于 Webtable的行的存放方式:从同一个主机获取的页面都存在临近的地方。利用这个特性, Bentley Mc|roy算法可以从来自同一个主机的页面里找到大量的重复内容。不仅仅是 Webtable,其它的很多应用 程序也通过选择合适的行名来将相似的数据聚簇在一起,以获取较高的压缩率。当我们在 Bigtable中存储 同一份数据的多个版本的时候,压缩效率会更高。 通过缓存提高读操作的性能 为了提高读操作的性能, Tab let服务器使用二级缓存的策略。扫描缓存是第一级缓存,主要缓存 Tablet服 务器通过 SSTable接口获取的 Key-value对; Block缓存是一级缓存,缓存的是从GFS读取的 SSTable的 Block。对于经常要重复读取相同数据的应用程序来说,扫描缓存非常有效;对于经常要读取刚刚读过的 数据附近的数据的应用程序来说,Bock缓存更有用(例如,顺序读,或者在一个热点的行的局部性群组 中随机读取不同的列 B|oom过滤器 (alex注Bloom又叫布隆过滤器,什么意思?请参考Google黑板报httpllgooglechinablog.con 22007107/b00m- flter htn请务必先认真阅读 如5.3节所述,一个读操作必须读取构成 Tablet状态的所有 SSTable的数据。如果这些 SSTable不在内存 中,那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的 SSTable指定 bloom过滤器 【7】,来减少硬盘访问的次数。我们可以使用 Bloon过滤器查询一个 SSTable是否包含了特定行和列的数 据。对于某些特定应用程序,我们只付出了少量的、用于存储 bloom过滤器的内存的代价,就换来了读操 作显著减少的磁盘访问的次数。使用B|oom过滤器也隐式的达到了当应用程序访问不存在的行或列时,大 多数时候我们都不需要访问硬盘的目的 Comm志的实现 如果我们把对每个 Tablet的操作的 Commit日志都存在一个单独的文件的话,那么就会产生大量的文件, 并且这些文件会并行的写入GFS。根据GFS服务器底层文件系统实现的方案,要把这些文件写入不同的磁 盘日志文件时(aex注: different physical log files),会有大量的磁盘seek操作。另外,由于批量提交 (alex注: group commit)中操作的数目一般比较少,因此,对每个 Tablet设置单独的日志文件也会给批 量提交本应具有的优化效果带来很大的负面影响。为了避免这些问题,我们设置每个 Tablet服务器一个 Commit日志文件,把修改操作的日志以追加方式写入同一个日志文件,因此一个实际的日志文件中混合 了对多个 Tablet修改的日志记录。 使用单个日志显著提高了普通操作的性能,但是将恢复的工作复杂化了。当一个Tbet服务器宕机时,它 加载的abet将会被移到很多其它的habe服务器上:每个habe服务器都装载很少的几个原来的服务器 的 Tablet。当恢复一个 Tablet的状态的时候,新的 Tablet服务器要从原来的 Tablet服务器写的日志中提取 修改操作的信息,并重新执行。然而,这些 abet修改操作的日志记录都混合在同一个日志文件中的 种方法新的 Tablet服务器读取完整的Comm日志文件,然后只重复执行它需要恢复的 Tablet的相关修改 操作。使用这种方法,假如有100台 Tablet服务器,每台都加载了失效的Tbet服务器上的一个 Tablet 那么,这个日志文件就要被读取100次(每个服务器读取一次)。 为了避免多次读取日志文件,我们首先把日志按照关键字( table, row name, log sequence number)排序。排序之后,对同一个 Tablet的修改操作的日志记录就连续存放在了一起,因此,我们只 要一次磁盘Seek操作、之后顺序读取就可以了。为了并行排序,我们先将日志分割成64MB的段,之后在 不同的 Tablet服务器对段进行并行排序。这个排序工作由 Master服务器来协同处理,并且在一个 Tablet服 务器表明自己需要从 Commit日志文件恢复 Tab let时开始执行。 在向GFS中写 Commit日志的时候可能会引起系统颠簸,原因是多种多样的(比如,写操作正在进行的时 候,一个GFS服务器宕机了;或者连接三个GFS副本所在的服务器的网络拥塞或者过载了)。为了确保在 GFS负载高峰时修改操作还能顺利进行,每个 Tablet服务器实际上有两个日志写入线程,每个线程都写自 己的日志文件,并且在任何时刻,只有一个线程是工作的。如果一个线程的在写入的时候效率很 低, Table服务器就切换到另外一个线程,修改操作的日志记录就写入到这个线程对应的日志文件中。每 个日志记录都有一个序列号,因此,在恢复的时候, Tablet服务器能够检测出并忽略掉那些由于线程切换 而导致的重复的记录 Tablet恢复提速 当 Master服务器将一个 abet从一个able服务器移到另外一个 Tablet服务器时,源 Tablet服务器会对这 个 Tablet做一次 Minor Compaction。这个 Compaction操作减少了Tbe服务器的日志文件中没有归并 的记录,从而减少了恢复的时间。 Compaction完成之后,该服务器就停止为该lbet提供服务。在卸载 Tablet之前,源 Tablet服务器还会再做一次(通常会很快) Minor Compaction,以消除前面在一次压缩 过程中又产生的未归并的记录。第二次 Minor Compaction完成以后, Tablet就可以被装载到新的 Tab let 服务器上了,并且不需要从日志中进行恢复 利用不变性 我们在使用 Bigtable时,除了 SSTables缓存之外的其它部分产生的 SSTable都是不变的,我们可以利用这 点对系统进行简化。例如,当从 SSTable读取数据的时候,我们不必对文件系统访问操作进行同步。这 样一来,就可以非常高效的实现对行的并行操作。 memtable是唯—一个能被读和写操作同时访问的可变 数据结构。为了减少在读操作时的竞争,我们对内存表采用COW(Copy-on-wrte机制,这样就允许读写 操作并行执行。 因为 SSTable是不变的,因此,我们可以把永久删除被标记为“删除"的数据的问题,转换成对废弃的 SSTab|e进行垃圾收集的问题了。每个Tbet的 SsTable都在 METADATA表中注册了。 Master服务器采用 ‘标记删除"的垃圾回收方式删除SS阳able集合中废弃的 SSTable【25】, ME TADATA表则保存了Root SSTable的集合 最后, SSTable的不变性使得分割Tbe的操作非常快捷。我们不必为每个分割出来的 Table建立新的 SSTable集合,而是共享原来的 Tablet的 SSTab|e集合。 7性能评估 为了测试 Bigtable的性能和可扩展性,我们建立了一个包括N台abet服务器的 Bigtable集群,这里N是可 变的。每台 Tablet服务器配置了1GB的内存,数据写入到一个包括1786台机器、每台机器有2个|DE硬盘 的GFS集群上。我们使用N台客户机生成工作负载测试 Bigtable。(我们使用和 Tablet服务器相同数目的 客户机以确保客户机不会成为瓶颈。)每台客户机配置2Gz双核 Opteron处理器,配置了足以容纳所有进 程工作数据集的物理内存,以及一张 Gigabit的以太网卡。这些机器都连入一个两层的、树状的交换网络 里,在根节点上的带宽加起来有大约100-200Gbps。所有的机器采用相同的设备,因此,任何两台机器 间网络来回一次的时间都小于1ms Tablet服务器、 Master服务器、测试机、以及GFS服务器都运行在同一组机器上。每台机器都运行一个 GFS的服务器。其它的机器要么运行 Table服务器、要么运行客户程序、要么运行在测试过程中,使用这 组机器的其它的任务启动的进程 R是测试过程中, Bigtable包含的不同的列关键字的数量。我们精心选择R的值,保证每次基准测试对每台 Tablet服务器读/写的数据量都在1GB左右。 在序列写的基准测试中,我们使用的列关键字的范围是0到R-1。这个范围又被划分为10N个大小相同的区 间。核心调度程序把这些区间分配给N个客户端,分配方式是:只要客户程序处理完上一个区间的数据, 调度程序就把后续的、尚未处理的区间分配给它。这种动态分配的方式有助于减少客户机上同时运行的其 它进程对性能的影响。我们在每个列关键字下写入一个单独的字符串。每个字符串都是随机生成的、因此 也没有被压缩(aex注:参考第6节的压缩小节)。另外,不同列关键字下的字符串也是不同的,因此也 就不存在跨行的压缩。随机写入基准测试采用类似的方法,除了行关键字在写入前先做Hash,HaSh采用 按R取模的方式,这样就保证了在整个基准测试持续的时间内,写入的工作负载均匀的分布在列存储空间 内 序列读的基准测试生成列关键字的方式与序列写相同,不同于序列写在列关键字下写入字符串的是,序列

...展开详情
试读 60P google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    一个资源只可评论一次,评论内容不能少于5个字
    wangfengmingqq hadoop入门必学资料
    2018-04-25
    回复
    小许2018 非常好,谢谢楼主u
    2017-02-13
    回复
    崇尚簡單 要学习Hadoop的入门的资料,好东西
    2015-11-04
    回复
    MOMO_star 可以和 英文的结合起来看,补充理解!
    2015-06-17
    回复
    hurtheart517 看过,没太多印象了。
    2015-04-27
    回复
    xiajlxiajl 要学习Hadoop的入门的资料,好东西
    2014-05-30
    回复
    forestsleeping 这个材料不错 但是论文感觉看不懂
    2014-05-27
    回复
    lovewangqi 不错不错的资源,正在学习使用,值得下载
    2014-05-08
    回复
    雾卡 超级赞,好东西,很好~
    2014-02-14
    回复
    Angelbaby3 打算用这个学习hadoop
    2013-10-08
    回复
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型 36积分/C币 立即下载
    1/60
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第1页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第2页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第3页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第4页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第5页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第6页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第7页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第8页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第9页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第10页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第11页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第12页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第13页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第14页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第15页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第16页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第17页
    google三大论文 gfs bigtable mapreduce hadoop hdfs hbase的原型第18页

    试读已结束,剩余42页未读...

    36积分/C币 立即下载 >