第一个论文阐述了一种构建分布式文件系统的范式方法第二个论文详细介绍了Google的分布式锁实现机制Chubby第三个是第一个全球意义上的分布式数据库，也是Google的作品张表可以有无限多个列。列关键字的命名语法如下:列族:限定词。列族的名字必须是可打印的字符串,而限定词的名字可以是任意的字符串。比如, Webtable有个列族 language, language列族用来存放撰写网页的语言。我们在anguage列族中只使用一个列关健字,用来存放每个网页的语言标识|D。 Webtable中另一个有用的列族是aηchor;这个列族的每个列关键字代表一个锚链接,如图所示。 Anchor列族的限定词是引用该网页的站点名; Anchon列族每列的数据项存放的是链接文本疠冋控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的 Wetable的例子中,上述的控制权限能帮助我们管理不同类型的应用:我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并仓建继承的列族、一些应用则只允许浏览数据(甚至可能因为隐私的原因不能浏览所有数据时问戳在 Bigtable中,表的每—个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索引。 Bigtable时间戳的类型是64位整型。 Bigtable可以给时间戳赋值,用来表示精确到毫秒的“实时"时间;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本沖突,那么它必须自己生成具有唯一性的时间戳。数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。为了减轻多个版本数据的管理负担,我们对每一个列族配有两个设置参数, Bigtable通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据,或者只保存“足够新"的版本的数据(比如,只保存最近7天的内容写入的数据)。在 Webtable的举例里, contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据3 APIBigtable提供了建立和删除表以及列族的AP函数。 Bigtable还提供了修改集群、表和列族的元数据的AP|,比如修改访问权限//Open the tableTable *T= Open OrDie("/bigtable/web/webtable")Write a new anchor and delete an old anchorRow Mutation rl(T, com. cnn WWW")r1.set(“anchor:WWW.c-span.org",“CNN");rl.delete("anchor:www.abc.com")Operation opApply(sop, &rl)Figure 2: Writing to Bigtable.客户程序可以对 Bigtable进行如下的操作:写入或者删除 Bigtable中的值、从每个行中查找值、或者遍历表中的一个数据子集。图2中的C++代码使用 ROW Mutation抽象对象进行了一系列的更新操作。(为了保持示例代码的简洁,我们忽略了一些细节相关代码)。调用Appy函数对 Webtable进行了一个原子修改操作:它为www.cnn.com增加了一个锚点,同时删除了另外一个错点。Scanner scanner(TScan stream *stream;stream scanner. Fetch Column Family"anchor ")stream->SetReturnAlIVersions(scanner. Lookup("com.cnnWWw")for (; lstream->Done(; stream->Next()fprintf("%s %s %lld %s\nscanner. Row Nameostream->Column Name(stream->MicroTimestamp()stream->Value()Figure 3: Reading from Bigtable.图3中的C++代码使用 Scanner抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族,有几种方法可以对扫描输岀的行、列和时间戳进行限制。例如,我们可以限制上面的扫描,让它只输出那些匹配正则表达式*Cn.com的锚点,或者那些时间戳在当前时间前10天的锚点。Bigtable还支持些其它的特性,利用这些特性,用户可以对数据进行更复杂的处理。首先, Bigtable支持单行上的事务处理,利用这个功能,用户可以对存储在一个行关键字下的数据进行原子性的读更新写操作。虽然 Bigtable提供了一个允许用户跨行批量写入数据的接口,但是, Bigtable目前还不支持通用的跨行事务处理。其次, Bigtable允许把数据项用做整数计数器。最后, Bigtable允许用户在服务器的地址空间内执行脚本程序。脚本程序使用 Google开发的SaWz叫ll【28】数据处理语言。虽然目前我们基于的Sawzall语言的AP函数还不允许客户的脚本程序写入数据到 Bigtable,但是它允许多种形式的数据转换、基于任意表达式的数据过滤、以及使用多种操作符的进行数据汇总Bigtable可以和 MapReduce【12】一起使用, MapReduce是 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 ss table格式的。 SSTable是一个持久化的、排序的、不可更改的Map结构,而Map是一个 key-value映射的数据结构,key和vaue的值都是任意的Byte串。可以对SSTable进行如下的操作:查询与一个key值相关的vaue,或者遍历某个key值范围内的所有的keyva|ue对。从内部看, SSTable是一系列的数据块(通常每个块的大小是64KB,这个大小是可以配置的)。 SSTable使用块索引(通常存储在 SSTable的最后)来定位数据块;在打开 SSTable的时候,索引被加载到内存。每次查找都可以通过一次磁盘搜索完成:首先使用二分查找法在内存中的索引里找到数据块的位置,然后再从硬盘读取相应的数据块。也可以选择把整个 SSTab|e都放在内存中,这样就不必访问硬盘了Big table还依赖一个高可用的、序列化的分布式锁服务组件,叫做 Chubby【8】。一个 Chubby服务包括了5个活动的副本,其中的一个副本被选为 Master,并且处理请求。只有在大多数副本都是正常运行的并且彼此之间能够互相通信的情况下, Chubby服务才是可用的。当有副本失效的时候, Chubby使用Paxos算法I9,23】来保证副本的一致性。 Chubby提供了一个名字空间,里面包括了目录和小文件。每个目录或者文件可以当成一个锁,读写文件的操作都是原子的。 Chubby客户程序库提供对 Chubby文件的一致性缓存。每个 Chubby客户程序都维护一个与 Chubby服务的会话。如果客户程序不能在租约到期的时间内重新签订会话的租约,这个会话就过期失效了(aex注:又用到了 lease。原文是: A client'ssession expires if it is unable to renew its session lease with in the lease expiration time. ) o个会话失效时,它拥有的锁和打开的文件句柄都失效了。 Chubby客户程序可以在文件和目录上注册回调函数,当文件或目录改变、或者会话过期时,回调函数会通知客户程序。Bigtable使用 Chubby完成以下的几个任务:确保在任何给定的时间内最多只有一个活动的 Maste副本存储 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 thesingle cluster that was most affected by Chubby unavailability was 0.0326%.)5介绍Bigtable包括了三个主要的组件:链接到客户程序中的库、一个 Master服务器和多个able服务器。针对系统工作负载的变化情况, Big Table可以动态的向集群中添加(或者删除)Tble服务器。Master服务器主要负责以下工作:为 Tablet服务器分配 Tablets、检测新加入的或者过期失效的Tble服务器、对 Tablet服务器进行负载均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外,它还处理对模式的相关修改操作,例如建立表和列族。每个Tblt服务器都管理一个 Table的集合(通常每个服务器有大约数十个至上千个 Tablet)。每个Tablet服务器负责处理它所加载的 Tablet的读写操作,以及在 blets过大时,对其进行分割。和很多 Single-Master类型的分布式存储系统[17.21】类似,客户端读取的数据都不经过 Master服务器:客户程序直接和 Tablet服务器通信进行读写操作。由于 Big table的客户程序不必通过 Master服务器来获取 Tablet的位置信息,因此,大多数客户程序甚至完全不需要和 Master服务器通信。在实际应用中, Master服务器的负载是很轻的一个 Big table集群存储了很多表,每个表包含了一个 able的集合,而每个Tabe包含了某个范围内的行的所有相关数据。初始状态下,一个表只有一个 Tablet。随着表中数据的增长,它被自动分割成多个Tablet,缺省情况下,每个Tab|et的尺寸大约是100MB到200MB。51 Tablet的位置我们使用一个三层的、类似B+树[10]的结构存储 Tablet的位置信息(如图4)User table1Other二2二二二二二二2二2METADATAtablets上==二二=======Root tablet二二二2二二二二二二Chubby file (1st METADA IA tablet二二二二二2二二二2二二二二二二二二二二二User tableN二二二二二二二二2二二二二二二二-二二二二二二Figure 4: Tablet location hierarchy第一层是一个存储在 Chubby中的文件,它包含了 Root tablet的位置信息。 Root table包含了一个特殊的 METADATA表里所有的 Table的位置信息。 METADATA表的每个be包含了一个用户 Table的集合。被分割一这就保证了be的位置信息存储结构不会超过层处理比较特殊一 Root tablet永远不会Root Tablet实际上是 METADATA3表的第一个 Tablet,只不过对它在 METADATA表里面,每个abet的位置信息都存放在一个行关键字下面,而这个行关键字是由 Tab let所在的表的标识符和Tbet的最后一行编码而成的。 METADATA的每一行都存储了大约1KB的内存数据。在个大小适中的、容量限制为128MB的 METADATA Tab let中,采用这种三层结构的存储模式,可以标识2^34个 Table的地址(如果每个 Tablet存储128MB数据,那么一共可以存储2^61字节数据)。客户程序使用的库会缓存bet的位置信息。如果客户程序没有缓存某个Tabe的地址信息,或者发现它缓存的地址信息不正确,客户程序就在树状的存储结构中递归的查询blet位置信息;如果客户端缓存是空的,那么寻址算法需要通过三次网络来回通信寻址,这其中包括了一次 Chubby读操作;如果客户端缓存的地址信息过期了,那么寻址算法可能需要最多6次网络来回通信才能更新数据,因为只有在缓存中没有查到数据的时候才能发现数据过期(a/ex注:其中的三次通信发现缓存过期,另外三次更新缓存数据,假设 METADATA的bet没有被频繁的移动)。尽管bet的地址信息是存放在内存里的,对它的操作不必访问GFS文件系统,但是,通常我们会通过预取Tbet地址来进步的减少访问的开销:每次需要从METADATA表中读取一个able的元数据的时候,它都会多读取几个 Table的元数据在 METADATA表中还存储了次级信息aex注: secondary information),包括每个able的事件日志(例如,什么时候一个服务器开始为该 Tablet提供服务)。这些信息有助于排查错误和性能分析52 Tablet分配在任何一个时刻,一个 Tablet只能分配给一个 Tablet服务器。 Master服务器记录了当前有哪些活跃的Tablet服务器、哪些 Tablet.分配給给了哪些 abet服务器、哪些 Tablet还没有被分配、当一个 Tablet还没有被分配、并且刚好有一个 Table服务器有足够的空闲空间装载该向be时, Master服务器会给这个lbet服务器发送一个装载请求,把 able分配给这个服务器。Big Table使用 Chubby跟踪记录 Tablet服务器的状态。当一个 Tablet服务器启动时,它在 Chubby的一个指定目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。 Master服务器实时监控着这个目录(服务器目录),因此 Master服务器能够知道有新的able服务器加入了。如果able服务器丢失了Chubby上的独占锁一比如由于网络断开导致 Tablet服务器和 Chubby的会话丢失一它就停止对 Tablet提供服务。( Chubby提供了一种高效的机制,利用这种机制, Tablet服务器能够在不增加网络负担的情况下知道它是否还持有锁)。只要文件还存在, Tablet服务器就会试图重新获得对该文件的独占锁;如果文件不存在了,那么Tbet服务器就不能再提供服务了,它会自行退出(alex注: so it k∥ s itse)。当Tablet服务器终止时(比如,集群的管理系统将运行该blt服务器的主机从集群中移除),它会尝试释放它持有的文件锁,这样一来, Master服务器就能尽快把 Tablet分配到其它的 Tablet服务器Master服务器负责检查一个Tabe服务器是否已经不再为它的Tabe提供服务了,并且要尽快重新分配它加载的 Tablet。 Master服务器通过轮询Tab|et服务器文件锁的状态来检测何时Tble服务器不再为 Tablet提供服务。如果一个 Tablet服务器报告它丢失了文件锁,或者 Master服务器最近几次尝试和它通信都没有得到响应, Master服务器就会尝试获取该 Tablet服务器文件的独占锁;如果 Master服务器成功获取了独占锁,那么就说明 Chubby是正常运行的,而 Tablet服务器要么是宕机了、要么是不能和 Chubby通信了,因此, Master服务器就删除该abet服务器在 Chubby上的服务器文件以确保它不再给Tbe提供服务。且Rabe服务器在 Chubby上的服务器文件被删除了, Master服务器就把之前分配给它的所有的hbet放入未分配的 Tablet集合中。为了确保 Bigtable集群在 Master服务器和 Chubby之间网络出现故障的时候仍然可以使用, Master服务器在它的 Chubby会话过期后主动退出。但是不管怎样,如同我们前面所描述的, Master服务器的故障不会改变现有hab|e在 Tablet服务器上的分配状态。当集群管理系统启动了一个 Master服务器之后, Master服务器首先要了解当前abet的分配状态,之后才能够修改分配状态。 Master服务器在启动的时候执行以下步骤:(1) Master服务器从 Chubby获取一个唯一的 Master锁,用來阻止创建其它的 Master服务器实例;(2) Master服务器扫描 Chubby的服务器文件锁存储目录,获取当前正在运行的服务器列表;(3) Master服务器和所有的正在运行的 Table表服务器通信,获取每个 Table服务器上 Tablet的分配信息;(4) Master服务器扫描 METADATA表获取所有的Tablet的集合。在扫描的过程中,当 Master服务器发现了一个还没有分配的 Tablet, Master服务器就将这个blt加入未分配的labt集合等待合适的时机分配。可能会遇到一种复杂的情况:在 METADATA表的Tabl还没有被分配之前是不能够扫描它的。因此,在开始扫描之前(步骤4),如果在第三步的扫描过程中发现 Root tab let还没有分配, Master服务器就把RootTabe加入到未分配的Tabe集合。这个附加操作确保了 Root tab let会被分配,由于 Root tablet包括了所有 METADATA的able的名字,因此 Master服务器扫描完 Root Tab let以后,就得到了所有的METADATAE表的Tbe的名字了保存现有Tbet的集合只有在以下事件发生时才会改变:建立了一个新表或者删除了一个旧表、两个Tablet被合并了、或者—个 Tablet被分割成两个小的 Tablet。 Master服务器可以跟踪记录所有这些事件,因为除了最后一个事件外的两个事件都是由它启动的。Tbet分割事件需要特殊处理,因为它是由Tbl服务器启动。在分割操作完成之后, Tablet服务器通过在 METADATA表中记录新的Tabe的信息来提交这个操作;当分割操作提交之后,Tabe服务器会通知 Master服务器。如果分割操作已提交的信息没有通知到 Master服务器(可能两个服务器中有一个宕机了), Master服务器在要求be服务器装载已经被分割的子表的时候会发现一个新的 Tablet。通过对比 METADATA表中bet的信息, Tab let服务器会发现Master服务器要求其装载的Tabt并不完整,因此,Tabe服务器会重新向 Master服务器发送通知信息53 Tablet服务memtableRead oPMemoryGFStablet logWrite OpSSTable filesFigure 5: Tablet Representation如图5所示, Tablet的持久化状态信息保存在GFS上。更新操作提交到REDO日志中(aex注: Updatesare committed to a commit log that stores redo records)。在这些更新操作中,最近提交的那些存放在一个排序的缓存中,我们称这个缓存为 memtable;较早的更新存放在一系列 SSTable中。为了恢复一个 Tablet, Table服务器首先从 METADATA表中读取它的元数据。 Tablet的元数据包含了组成这个Tablet的 SSTable的列表,以及一系列的 Redo point(aex注: a set of redo points),这些RedoPoint指向可能含有该 Tablet数据的已提交的日志记录。 Tablet服务器把 SSTable的索引读进内存,之后通过重复 Redo point之后提交的更新来重建 memtable当对 abet服务器进行写操作时, Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是通过从一个 Chubby文件里读取出来的具有写权限的操作者列表来进行验证(这个文件几乎一定会存放在 Chubby客户缓存里)。成功的修改操作会记录在提交日志里。可以采用批量提交方式(aex注: group commit)来提高包含大量小的修改操作的应用程序的吞吐量【13,16】。当一个写操作提交后,写的内容插入到 memtable里面当对 Tablet服务器进行读操作时, Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个由一系列 SSTable和 memtable合并的视图里执行。由于 SSTable和 memtable是按字典排序的数据结构,因此可以高效生成合并视图当进行 Table的合并和分割时,正在进行的读写操作能够继续进行。5. 4 Compactions(alex注:这个词挺简单,但是在这节里面挺难翻译的。应该是空间缩减的意思,但是似乎又不能完全概括它在上下文中的意思,干脆,不翻译了)随着写操作的执行, memtable的大小不断增加。当 memtable的尺寸到达一个门限值的时侯,这个memtable就会被冻结,然后创建一个新的 memtable;被冻结住 memtable会被转换成 SSTable,然后写入GFS(aex注:我们称这种 Compaction行为为 Minor Compaction)。 Minor compaction过程有两个目的: shrink(aex注: shrink是数据库用语,表示空间收缩) Tablet服务器使用的内存,以及在服务器灾难恢复过程中,减少必须从提交日志里读取的数据量。在 Compaction过程中,正在进行的读写操作仍能继续每一次 Minor Compaction都会创建一个新的 SSTable。如果 Minor Compaction过程不停滞的持续进行下去,读操作可能需要合并来自多个 SSTable的更新;否则,我们通过定期在后台执行 MergingCompaction过程合并文件,限制这类文件的数量。 Merging Compaction过程读取一些 SSTable和memtable的内容,合并成一个新的 SSTable。只要 Merging Compaction过程完成了,输入的这些SSTable和 memtable就可以删除了合并所有的 SSTable并生成一个新的 SSTable的 Merging Compaction过程叫作 Major Compaction。由非 Major Compaction产生的 SsTable可能含有特殊的删除条目,这些删除条目能够隐藏在旧的、但是依然有效的 SSTable中已经删除的数据(aex注:令人费解啊,原文是 SSTables produced by non- mayorcompactions can contain special deletion entries that suppress deleted data in older557ab/ es that are still live)。而 Major Compaction过程生成的5Sabe不包含已经删除的信息或数据。 Bigtable循环扫描它所有的 Tablet,并且定期对它们执行 Major Compaction。 Major Compaction机制允许 Bigtable回收已经删除的数据占有的资源,并且确保Bigτable能及时清除已经删除的数据(a/eⅹ注:实际是回收资源。数据删除后,它占有的空间并不能马上重复利用;只有空间回收后才能重复使用),这对存放敏感数据的服务是非常重要6优化上一章我们描述了 Bigtable的实现,我们还需要很多优化工作才能使 Bigtable到达用户要求的高性能、高可用性和高叮靠性。本章描述了 Bigtable实现的其它部分,为了更好的强调这些优化工作,我们将深入细局部性群组客户程序可以将多个列族组合成一个局部性群族。对Tbet中的每个局部性群组都会生成一个单独的SSTable。将通常不会一起访问的列族分割成不同的局部性群组可以提高读取操作的效率。例如,在另外一个群组:当一个应用程序要读取网页的元数据的时候,它没有必要去读取所有的页邮家可以在Webtable表中,网页的元数据(比如语言和 Checksum)可以在一个局部性群组中,网页的内此外,可以以局部性群组为单位设定一些有用的调试参数。比如,可以把一个局部性群组设定为全部存储在内存中。 Tablet服务器依照惰性加载的策略将设定为放入内存的局部性群组的 SSTable装载进内存。加载完成之后,访问属于该局部性群组的列族的时候就不必读取硬盘了。这个特性对于需要频繁访问的小块数据特别有用:在 Bigtable内部,我们利用这个特性提高 ME TADATA表中具有位置相关性的列族的访问速度压缩客户程序可以控制一个局部性群组的 SSTable是否需要压缩;如果需要压缩,那么以什么格式来压缩。每个 SSTable的块(块的大小由局部性群组的优化参数指定)都使用用户指定的压缩格式来压缩。虽然分块压缩浪费了少量空间aex注:相比于对整个 SSTab/e进行压缩,分块压缩压缩率较低),但是,我们在只读取 SSTable的一小部分数据的时候就不必解压整个文件了。很多客户程序使用了“两遍"的、可定制的压缩方式。第一遍采用 Bentley and mcllroy's方式[6],这种方式在一个很大的扫描窗口里对常见的长字符串进行压缩;第二遍是采用快速压缩算法,即在一个16KB的小扫描窗口中寻找重复数据。两个压缩的算法都很快,在现在的机器上,压缩的速率达到100-200MB/s,解压的速率达到400-1000MB/s。虽然我们在选择压缩算法的时候重点考虑的是速度而不是压缩的空间,但是这种两遍的压绵方式在空间压缩率上的表现也是令人惊叹。比如,在 Webtable的例子里,我们使用这种压缩方式来存储网页内容。在次测试中,我们在一个压缩的局部性群组中存储了大量的网页。针对实验的目的,我们没有存储每个文档所有版本的数据,我们仅仅存储了一个版本的数据。该模式的空间压缩比达到了101。这比传统的 Gzip在压缩HTML页面时3:1或者4:1的空间压缩比好的多;“两遍"的压缩模式如此高效的原因是由于Webtable的行的存放方式:从同一个主机获取的页面都存在临近的地方。利用这个特性, BentleyMcoy算法可以从来自同一个主机的页面里找到大量的重复内容。不仅仅是 Webtable,其它的很多应用程序也通过选择合适的行名来将相似的数据聚簇在一起,以获取较高的压缩率。当我们在 Bigtable中存储同一份数据的多个版本的时候,压缩效率会更高通过缓存提高读操作的性能为了提高读操作的性能, Tablet服务器使用二级缓存的策略。扫描缓存是第一级缓存,主要缓存 abet服务器通过 SSTable接口获取的 Key-value对; Block缓存是一级缓存,缓存的是从GFS读取的 SSTab|e的Block。对丁经常要重复读取相同数据的应用程序来说,扫描缓存非常有效;对丁经常要读取刚刚读过的数据附近的数据的应用程序来说,Blok缓存更有用(例如,顺序读,或者在一个热点的行的局部性群组中随机读取不同的列)Boom过滤器(aex注:Bom,又叫布隆过滤器,什么意思?请参考Goe黑板报htto/ googlechinablog. com200707b/ oom-filter htm请务必先认真阅读)如5.3节所述,一个读操作必须读取构成 Tablet状态的所有 SsTable的数据。如这些 SSTable不在内存中,那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的 SSTable指定 Bloom过滤器【刀】,来减少硬盘访问的次数。我们可以使用 Bloom过滤器查询个 SSTable是否包含了特定行和列的数据。对于某些特定应用程序,我们只付出了少量的、用于存储 Bloom过滤器的内存的代价,就换来了读操作显著减少的磁盘访问的次数。使用 Bloom过滤器也隐式的达到了当应用程序访问不存在的行或列时,大多数时候我们都不需要访问硬盘的目的C。mm旦志的实现如果我们把对每个lbet的操作的Comm日志都存在一个单独的文件的话,那么就会产生大量的文件,并且这些文件会并行的写入GFS。根据GFS服务器底层文件系统实现的方案,要把这些文件写入不同的磁盘日志文件时(aex注: different physical log files),会有大量的磁盘Seek操作。另外,由于批量提交(alex注: group commit)中操作的数目一般比较少,因此,对每个Tbe设置单独的日志文件也会给批量提交本应具有的优化效果带来很大的负面影响。为了避免这些问题,我们设置每个Tbet服务器一个Commit日志文件,把修改操作的日志以追加方式写入同一个日志文件,因此一个实际的日志文件中混合了对多个lbet修改的日志记录。使用单个日志显著提高了普通操作的性能,但是将恢复的工作复杂化了。当一个abet服务器宕机时加载的 Tablet将会被移到很多其它的lbe服务器上:每个able服务器都装载很少的几个原来的服务器的 Tablet。当恢复一个Tbet的状态的时候,新的Tabe服务器要从原来的 Table服务器写的日志中提取修改操作的信息,并重新执行。然而,这些 Tablet修改操作的日志记录都混合在同一个日志文件中的种方法新的 Tablet服务器读取完整的Comm日志文件,然后只重复执行它需要恢复的 Tablet的相关修改操作。使用这种方法,假如有100台Tblt服务器,每台都加载了失效的Tbet服务器上的一个 Tablet,那么,这个日志文件就要被读取100次(每个服务器读取一次)。为了避免多次读取日志文件,我们首先把日志按照关键字( table, row name, log sequencenumber)排序。排序之后,对同—个 Tablet的修改操作的日志记录就连续存放在了一起,因此,我们只要一次磁盘Seek操作、之后顺序读取就可以了。为了并行排序,我们先将日志分割成64MB的段,之后在不同的 Tablet服务器对段进行并行排序。这个排序工作由 Master服务器来协同处理,并且在一个 Tablet服务器表明自己需要从 Commit日志文件恢复 Tablet时开始执行。在向GFS中写 Commit日志的时候可能会引起系统颠簸,原因是多种多样的(比如,写操作正在进行的时候,一个GFS服务器宕机了;或者连接三个GFS副本所在的服务器的网络拥塞或者过载了)。为了确保在GFS负载高峰时修改操作还能顺利进行,每个 Table服务器实际上有两个日志写入线程,每个线程都写自己的日志文件,并且在任何时刻,只有一个线程是工作的。如果一个线程的在写入的时候效率很低, Tab let服务器就切换到另外一个线程,修改操作的日志记录就写入到这个线程对应的日志文件中。每个日志记录都有一个序列号,因此,在恢复的时侯, abet服务器能够检测出并忽略掉那些由于线程切换而导致的重复的记录Tablet恢复提速当 Master服务器将一个 Tablet从一个 Tablet服务器移到另外一个 Tablet服务器时,源lbet服务器会对这个 Tablet做一次 Minor Compaction。这个 Compaction操作减少了Tabe服务器的日志文件中没有归并的记录,从而减少了恢复的时间。 Compaction完成之后,该服务器就停止为该 Tablet提供服务。在卸载Tablet之前,源 Tablet服务器还会再做一次(通常会很快) Minor Compaction,以消除前面在一次压缩过程中又产生的未归并的记录。第二次 Minor Compaction完成以后,Tbet就可以被装载到新的 Tablet服务器上了,并且不需要从日志中进行恢复。利用不变性我们在使用 Bigtable时,除了 SSTable缓存之外的其它部分产生的 SSTable都是不变的,我们可以利用这点对系统进行简化。例如,当从 SSTable读取数据的时候,我们不必对文件系统访问操作进行同步。这样一来,就可以非常高效的实现对行的并行操作。 memtable是唯—个能被读和写操作同时访问的可变数据结构。为了减少在读操作时的竞争,我们对内存表采用 COW( Copy- on- write)机制,这样就允许读写操作并行执行。因为 SSTable是不变的,因此,我们可以把永久删除被标记为“删除"的数据的问题,转换成对废弃的SSTable进行垃圾收集的问题了。每个abet的 SSTable都在 METADATA表中注册了。 Master服务器采用标记删除“的垃圾回收方式删除 SSTable集合中废弃的 SSTable【25】, METADATA表则保存了RootSSTable的集合。最后, SSTable的不变性使得分割 Tablet的操作非常快捷。我们不必为每个分害出来的Tabe建立新的SSTable集合,而是共享原来的 Tablet的 SSTable集合。7性能评估为了测试 Bigtable的性能和可扩展性,我们建立了一个包括N台blet服务器的 Bigtable集群,这里N是可变的。每台 Tablet服务器配置了1GB的内存,数据写入到一个包括1786台机器、每台机器有2个IDE硬盘的GFS集群上。我们使用N台客户机生成工作负载测试 Bigtable。(我们使用和Tb|e服务器相同数目的客户机以确保客户机不会成为瓶颈。)每台客户机配置2GZ双核 Opteron处理器,配置了足以容纳所有进程工作数据集的物理内存,以及一张 Gigabit的以太网卡。这些机器都连入一个两层的、树状的交换网络里,在根节点上的带宽加起来有大约100-200bps所有的机器采用相同的设备,因此,任何两台机器间网络来回一次的时间都小于1msTablet服务器、 Master服务器、测试机、以及GFS服务器都运行在同一组机器上。每台机器都运行一个GFS的服务器。其它的机器要么运行 Tablet服务器、要么运行客户程序、要么运行在测试过程中,使用这组机器的其它的任务启动的进程R是测试过程中, Bigtable包含的不同的列关键字的数量。我们精心选择R的值,保证每次基准测试对每台Tablet服务器读/写的数据量都在1GB左右在序列写的基准测试中,我们使用的列关键字的范围是0到R-1。这个范围又被划分为10N个大小相同的区间。核心调度程序把这些区间分配给N个客户端,分配方式是:只要客户程序处理完上一个区间的数据,调度程序就把后续的、尚未处理的区间分配给它。这种动态分配的方式有助于减少客户机上同时运行的其它进程对性能的影响。我们在每个列关键字下写入一个单独的字符串。每个字符串都是随机生成的、因此也没有被压缩(ax注:参考第6节的压缩小节)。另外,不同列关键字下的字符串也是不同的,因此也就不存在跨行的压缩。随机写入基准测试采用类似的方法,除了行关键字在写入前先做Hash,HaSh采用按R取模的方式,这样就保证了在整个基准测试持续的时间内,写入的工作负载均匀的分布在列存储空间内序列读的基准测试生成列关键字的方式与序列写相同,不同于序歹写在列关健字下写入字符串的是,序列