第2章 Google云计算原理 用户表1 ... 其他元数据子表 根子表 （元数据表中第一条记录） Chubby文件 ... ? ? . . . ? ... . . . 用户表N ... . . . ... 图2-17 子表地址结构
所需的元数据子表的位置，最后就可以从元数据子表中找到待查询的子表。除了这些子表的元数据之外，元数据表中还保存了其他一些有利于调试和分析的信息，比如事件日志等。
为了减少访问开销，提高客户访问效率，Bigtable使用了缓存（Cache）和预取（Prefetch）技术，这两种技术手段在体系结构设计中是很常用的。子表的地址信息被缓存在客户端，客户在寻址时直接根据缓存信息进行查找。一旦出现缓存为空或缓存信息过时的情况，客户端就需要按照图2-17所示方式进行网络的来回通信（Network Round-trips）进行寻址，在缓存为空的情况下需要三个网络来回通信。如果缓存的信息是过时的，则需要六个网络来回通信。其中三个用来确定信息是过时的，另外三个获取新的地址。预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取多个子表的元数据，这样下次需要时就不用再次访问元数据表。
3．子表数据存储及读写操作
在数据的存储方面Bigtable做出了一个非常重要的选择，那就是将数据存储划分成两块。较新的数据存储在内存中一个称为内存表（Memtable）的有序缓冲里，较早的数据则以SSTable格式保存在GFS中。这种技术在数据库中不是很常用，但Google还是做出了这种选择，实际运行的效果也证明Google的选择虽然大胆却是正确的。
从图2-18[8]中可以看出读和写操作有很大的差异性。做写操作（Write Op）时，首先查询Chubby中保存的访问控制列表确定用户具有相应的写权限，通过认证之后写入的数据首先被保存在提交日志（Commit Log）中。提交日志中以重做记录（Redo Record）的形式保存着最近的一系列数据更改，这些重做记录在子表进行恢复时可以向系统提供已完成的更改信息。数据成功提交之后就被写入内存表中。在做读操作（Read Op）时，首先还是要通过认证，之后读操作就要结合内存表和SSTable文件来进行，因为内存表和SSTable中都保存了数据。
在数据存储中还有一个重要问题，就是数据压缩的问题。内存表的空间毕竟是很有限的，当其容量达到一个阈值时，旧的内存表就会被停止使用并压缩成SSTable格式的文件。在Bigtable中有三种形式的数据压缩，分别是次压缩（Minor Compaction）、合并压缩（Merging Compaction）和主压缩（Major Compaction）。三者之间的关系如图2-19所示。
31 3 云计算
内存表 读操作 内存 GFS 子表日志 写操作 SSTable文件 图2-18 Bigtable数据存储及读写操作
SSTable . . . . SSTable SSTable 内存表 . . . . 内存表 次压缩 次压缩 SSTable . . . . SSTable 合并压缩 主压缩 SSTable 内存表 图2-19 三种形式压缩之间的关系
每一次旧的内存表停止使用时都会进行一个次压缩操作，这会产生一个SSTable。但如果系统中只有这种压缩的话，SSTable的数量就会无限制地增加下去。由于读操作要使用SSTable，数量过多的SSTable显然会影响读的速度。而在Bigtable中，读操作实际上比写操作更重要，因此Bigtable会定期地执行一次合并压缩的操作，将一些已有的SSTable和现有的内存表一并进行一次压缩。主压缩其实是合并压缩的一种，只不过它将所有的SSTable一次性压缩成一个大的SSTable文件。主压缩也是定期执行的，执行一次主压缩之后可以保证将所有的被压缩数据彻底删除，如此一来，既回收了空间又能保证敏感数据的安全性（因为这些敏感数据被彻底删除了）。
2.4.6 性能优化
上述各种操作已经可以实现Bigtable的所有功能了，但是这些基本的功能很多时候并不是很符合用户的使用习惯，或者执行的效率较低。有些功能Bigtable自身已经进行了优化，包括使用缓存、共享式的提交日志以及利用系统的不变性。这些手段在前面已经有了简单的介绍，这里不再讲解。除此之外，Bigtable还允许用户个人在基本操作基础上对系统进行一些优化。这一部分主要向读者介绍用户可以使用的几个重要优化措施。实际上这些技术手段都是一些已有的数据库方法，只不过Google将它具体地应用于Bigtable之中罢了。
1．局部性群组（Locality groups）
Bigtable允许用户将原本并不存储在一起的数据以列族为单位，根据需要组织在一个
32 3
第2章 Google云计算原理 单独的SSTable中，以构成一个局部性群组。这实际上就是数据库中垂直分区技术的一个应用。结合图2-13的实例来看，在被Bigtable保存的网页列关键字中，有的用户可能只对网页内容感兴趣，那么它可以通过设置局部性群组只看内容这一列。有的则会对诸如网页语言、网站排名等可以用于分析的信息比较感兴趣，他也可以将这些列设置到一个群组中。局部性群组如图2-20所示。
内容 语言 排名 com.cnn.www SSTable SSTable
图2-20 局部性群组
通过设置局部性群组用户可以只看自己感兴趣的内容，对某个用户来说的大量无用信息无需读取。对于一些较小的且会被经常读取的局部性群组，用户可以将其SSTable文件直接加载进内存，这可以明显地改善读取效率。
2．压缩
压缩可以有效地节省空间，Bigtable中的压缩被应用于很多场合。首先压缩可以被用在构成局部性群组的SSTable中，可以选择是否对个人的局部性群组的SSTable进行压缩。Bigtable中这种压缩是对每个局部性群组独立进行的，虽然这样会浪费一些空间，但是在需要读时解压速度非常快。通常情况下，用户可以采用两步压缩的方式[8]：第一步利用Bentley & McIlroy方式（BMDiff）在大的扫描窗口将常见的长串进行压缩；第二步采取Zippy技术进行快速压缩，它在一个16KB大小的扫描窗口内寻找重复数据，这个过程非常快。压缩技术还可以提高子表的恢复速度，当某个子表服务器停止使用后，需要将上面所有的子表移至另一个子表服务器来恢复服务。在转移之前要进行两次压缩，第一次压缩减少了提交日志中的未压缩状态，从而减少了恢复时间。在文件正式转移之前还要进行一次压缩，这次压缩主要是将第一次压缩后遗留的未压缩空间进行压缩。完成这两步之后压缩的文件就会被转移至另一个子表服务器。
3．布隆过滤器（Bloom Filter）
Bigtable向用户提供了一种称为布隆过滤器[12]的数学工具。布隆过滤器是巴顿·布隆在1970年提出的，实际上它是一个很长的二进制向量和一系列随机映射函数，在读操作中确定子表的位置时非常有用。布隆过滤器的速度快，省空间。而且它有一个最大的好处是它绝不会将一个存在的子表判定为不存在。不过布隆过滤器也有一个缺点，那就是在某些情况下它会将不存在的子表判断为存在。不过这种情况出现的概率非常小，跟它带来的巨大好处相比这个缺点是可以忍受的。
33 3 云计算
目前包括Google Analytics、Google Earth、个性化搜索、Orkut和RRS阅读器在内的几十个项目都使用了Bigtable。这些应用对Bigtable的要求以及使用的集群机器数量都是各不相同的，但是从实际运行来看，Bigtable完全可以满足这些不同需求的应用，而这一切都得益于其优良的构架以及恰当的技术选择。与此同时Google还在不断地对Bigtable进行一系列的改进，通过技术改良和新特性的加入提高系统运行效率及稳定性。
参考文献
[1] Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System,
Proceedings of 19th ACM Symposium on Operating Systems Principles, 2003, 20-43
[2] Sun “Lustre Networking: High-Performance Features and Flexible Support for a Wide
Array of Networks” https://www.sun.com/offers/details/lustre_networking.xml
[3] Soltis, Steven R; Erickson, Grant M; Preslan, Kenneth W (1997), “The Global File System:
A File System for Shared Disk Storage”, IEEE Transactions on Parallel and Distributed Systems
[4] Schmuck, Frank; Roger Haskin (January 2002). \A Shared-Disk File System for
Large Computing Clusters\Technologies. Monterey, California, USA
[5] Wikipedia. http://zh.wikipedia.org/wiki/MapReduce
[6] John Darlington, Yi-ke Guo, Hing Wing To. Structured parallel programming: theory meets
practice. Computing tomorrow: future research directions in computer science book contents Pages: 49-65
[7] Jeffrey Dean, Sanjay Ghemawant. MapReduce: Simpli_ed Data Processing on Large
Clusters
[8] Chang F, Dean J, Ghemawat S, Hsieh WC, Wallach DA, Burrows M, Chandra T, Fikes A,
Gruber RE. Bigtable: A distributed storage system for structured data. In: Proc. of the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006. 205-218
[9] Ghemawat S, Gobioff H, Leung ST. The Google file system. In: Proc. of the 19th ACM
Symp. on Operating Systems Principles. New York: ACM Press, 2003. 29-43
[10] Burrows M. The chubby lock service for loosely-coupled distributed systems. In: Proc. of
the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006. 335-350
[11] 陈康，郑纬民. 云计算：系统实例与研究现状。软件学报，2009，20(5)：1337-1348 [12] BLOOM, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13, 7
(1970), 422-426
[13] BURROWS, M. The Chubby lock service for loosely-coupled distributed systems. In Proc.
of the 7th OSDI,Nov, 2006
[14] LAMPORT, L. The part-time parliament. ACM TOCS 16,2 (1998), 133-169 [15] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (2001), 18-25
34 3