柯南说：“真相，只有一个！”我说，您丫说话要说完全，真相，对每个人来说，只有一个。至于是哪一个，就看你信啥了。

我信明星的话。这是有理论依据的。

第一，真理是掌握在少数人手里的。网上千百万网友骂饭明星。记者采访被打的浇水工人，也说饭明星的不是。只有人家明星一个人说自己是去劝架的。一对多，饭明星是少数，所以人家明星掌握真理。

第二，明星的素质高，工人的素质低。按照鲁迅的说法，连汗都是臭的。所以，我相信高素质人的话。

第三，根据几张模糊不清的照片，就能确定是饭明星吗？拍照的人，你确定吗？你敢为你的证词承担法律责任吗？不敢吧？你丫怕了吧？在美国，这也是判不了的事情。我们要和国际接轨，判饭明星无罪。

第四，饭明星明显比我有钱。我说饭明星不好，就是仇视饭明星，就是仇视比我富的人，就是仇富心态，是社会发展到一定阶段的产物，是不利于社会发展进步的，所以，我不仇富，我媚富还不行么，老大？

好了，我现在是跟明星一条路上的了，让我给明星几个小贴士：

1.劝架要讲究架式。不能因为没有众多观众，就不摆出个架式来。架式好看了，效果去他的，跟踢球一样。

2.劝架要用上半身：用嘴说用手拦，不能因为职业关系，就下半身指挥上半身。

3.做事情要注重细节。怎么能让人偷拍了去，还不把那人给做了呢？

我和彼岸合作翻译了google的bigtable论文中第一到第六章，基本包括了bigtable的概述和实现细节。论文一共有十一章，后面的章节包括：

7性能评估，8实际应用，9经验教训，10相关工作，11结论。以及感谢和参考文献。

我和彼岸认为，这些章节我们的兴趣不大，考虑到翻译是件脑力+体力的活，我们就不继续了。

翻译的过程中得到很多网友的支持，无论是留言也好，摘录也好，给出链接也好，我们（这里代替彼岸一把）都很感谢。彼岸给我的支持很大。彼岸的翻译比我精准，我翻译的原则是传达意思为主，字句的选择都没有彼岸那么认真。翻译的过程中难免有不准确的地方…（此处省略1500字言不由衷的谦虚）

我翻译这篇论文，其实也是想帮助自己，尽管我看论文很快，但是要写下来，就需要更多的思考和琢磨，会记的更清楚。如果这种“利己”行为能够帮助其他的朋友，那就最好了。

这里说一点做研究的体会：如果你仔细看美国的研究论文，就会发现，其实很多东西都不是新的，而是前人研究的点滴成果的组合和微小改进。以大表一文为例，其中为了性能所做的取舍，都是体系结构里面的常用招数；而算法也都是前人研究过的。他们对研究成果记录的非常详细，一方面是便于后人使用借鉴，另外也是说服别人相信自己研究的有力手段。这种脚踏实地，逐步积累的做法，其效果是惊人的。

翻译是件很累人的工作，远没有写blog好玩。 里面唯一的乐趣就是把自己的想法写下来，所以如果你看见很多的{}里面的内容，就说明当时我已经很无聊了。

我来到了一个大集市。身边是各色的人等，嘈杂而且拥挤，空气里是煎饼果子小笼包豆腐花和凤爪的味道，还混合着牛屎的气息，熟悉而亲切。

集市里照例有很多的老板在叫卖，一个戴着大礼帽，帽子上画着红白条和蓝底白星的老板在吆喝：“要不要看看查尔斯公司的狐狸围脖？很适合女士的！”等我走近了，才看到他还有一条京吧，老板说：“它鼻子可灵了，不比外国狗差！”见我要走，老板赶紧说：“这狗还会写字儿哪！”不过，我的注意力已经被另外一个人吸引住了，他很大声的说：“要不要看看名人的私生活？比如说老徐？不要钱的！”最后这四个字完全让我没有了胃口，免费的隐私有啥意思呢？我饶过一辆中巴，司机在喊：“去西游了，还有位子！”其实，我对一个跳蚤市场更有兴趣。一边看着企鹅游行，我喝完一碗豆花，眼光却落在集市尽头的一座建筑上。

建筑的风格是哥特式的，高耸的尖顶指向阴云密布的天空。云中隐隐有一道道紫色的闪电，还有一些声音。不过，这些并不影响建筑中的人们。他们身着洁白的衣裳，两个一对，三个一组，五个一群，七个一列，十一个队。在没有人愿意提及的数字那里，为了保证数学的完美，他们很幽默的放了一幅《最后的晚餐》。他们用纯洁的声音唱着美丽的诗篇：“山间一寺一壶酒～”

我正望的出神，忽然被人拍了一下：“嘿，兄弟，看什么呢？”

我一看，原来我已经走到一片麦田旁边，问我的是一个穿着象大猫一样的人。我笑笑，指着建筑里面的闪光：“好象他们的人要出来了。你看，里面有很多准备好的东西，不过不知道是什么。”

“对，他们是要出来了。”那个人又往嘴里塞了一把薯片，说：“我觉得，他们要破门开店，与民同乐。”

“他们？！和我们同乐？”我看看自己沾了泥点的衣服，又看看那些人们的洁白衣裳，很难相信自己的耳朵。“可是他们是如此的纯洁…”

//更新:彼岸翻译了第5章的后面部分 

6.优化
前面一章描述了ＢＴ的实现，我们还需要很多优化工作来获得用户需要的高性能，高可用性和高可靠性．本章描述实现的一些部分，以强调这些优化．

局部性群组

客户可以将多个列族组合成局部性群族．对每个子表中的每个局部性群组都会生成一个单独的SSTable.将通常不会一起访问的列族分割成不同的局部性群组，将会提高读取效率．例如，Webtable中的网页元数据（语言和校验和之类的）可以在一个局部性群组，网页内容可以在另外一个群组：如果一个应用要读取元数据，它就没有必要去访问页面内容．

此外，每个群组可以设定不同的调试参数．例如，一个局部性群组可以被设定在内存中．内存中的局部性群组的SSTable在被子表服务器装载进内存的时候，使用的装载策略是懒惰型的．一旦属于该局部性群组的列族被装载进内存，再访问它们就不必通过硬盘了{读不懂？知道机器翻译有多难了吧？人翻译都不行}．这个特性对于需要频繁访问的小块数据特别有用：在ＢＴ内部，我们用这个特性来访问元数据表中的地址列族．

压缩

客户可以控制是否压缩一个局部性群组的SSTable.每个SSTable块（块的大小由局部性群组的调试参数确定），都会使用用户指定的压缩格式．尽管这样分块压缩｛比全表压缩｝浪费了少量空间，但是在读取SSTable的一小部分数据的时候，就不必解压整个文件了｛那是，你们文件巨大，硬盘又便宜｝．很多客户使用两遍的订制压缩方式．第一遍是Bentley and McIlroy’s方式[6],该方式在一个大的扫描窗口中将常见的长串进行压缩．第二遍是一种快速压缩算法，在一个16KB的小扫描窗口中寻找重复数据．两个算法都很快，现有机器上压缩速率为100到200MB/s,解压速率是400到1000MB/s.

尽管我们选择压缩算法的重点是速率，而非空间效率，这种两遍的压缩方式空间效率也令人惊叹｛老大，别吹了，您老是在压字符串哪！你去压压运行代码看看？｝．例如，在Webtable,我们用这种压缩方式来存储网页内容．针对实验的目的，我们对每个文档只存储一个版本，而非存储所有能访问的版本．该模式获得了10比1的压缩率．这比一般的Gzip的3比1或者4比1的HTML页面压缩率好很多，因为Webtable的行是这样安排的：从一个主机获取的页面都存在临近的地方，这种特性让Bentley-McIlroy算法可以从一个主机那里来的页面里找到大量的重复内容．不仅是Webtable,其他很多应用也通过选择行名来将类似内容聚集在一起，因此压缩效果非常的好｛针对数据和程序特性选择的压缩算法｝．当在ＢＴ中存储同一数据的多个版本的时候，压缩效率更高．

使用缓存来提高读取性能

为了提高读操作性能，子表服务机构使用两层缓存．扫描缓存是高层，它缓存子表服务器代码从SSTable获取的关键字-值对．块缓存是底层，缓存的是从ＧＦＳ读取的SSTable块．对于经常要重复读取同一部分数据的应用程序来说，扫描缓存很有用．对于经常要读取前面刚读过的数据附近的其他数据（例如，顺序读｛性能提升老花招：预取｝，或者在一个热门的行中的同一局部性群组中，随机读取不同的列）的应用程序来说，块缓存很有用{后面这句比较拗口，是说一个局部性群组里的列都在缓存里，可以随机读取}．

Bloom过滤器{需要读参考文献才知道是什么意思．从标题看，bloom是一种杂凑函数，有相对低的不命中率，所以可以用它来猜测一个关键字对应的存储数据在哪里，从而减少访问硬盘的次数，以提高性能}

如5.3节所述，一个读操作要知道一个子表的所有状态，必须从所有SSTable中读取数据．如果这些SSTable不在内存，那么就需要多次访问硬盘．我们通过允许客户对特定局部性群组的SSTable指定bloom过滤器[7]，来降低访问硬盘的次数．使用bloom过滤器，我们就可以猜测一个SSTable是否可能包含特定行和列的数据．对于某些特定应用程序，使用少量内存来存储bloom过滤器换来的，是显著减少的访问磁盘次数．我们使用bloom过滤器也使当应用程序要求访问不存在的行或列时，我们不会访问硬盘．

修改日志｛commit-log｝的实现

如果我们把对每个子表的修改日志都另存一个文件的话，就会产生非常多的文件，这些文件会并行的写入ＧＦＳ．根据每个ＧＦＳ底层实现的细节，这些写操作在最终写入实际日志文件的时候，可能造成大量的硬盘寻道动作．此外，由于群组不大，为每个子表建立一个新的日志文件也降低了群组修改的优化程度．为了避免这些问题，我们将对每个子表服务器的修改动作添加到一个修改日志中，将多个子表的修改混合到一个实际日志文件中［18,20］．

使用单个日志显著提高了正常使用中的性能，但是将恢复的工作复杂化了．当一个子表服务器死掉时，它以前服务的子表们将会被移动到很多其他的子表服务器上：它们每个都装载很少的几个子表．要恢复子表的状态，新的子表服务器要按照原来的服务器写的修改日志来重新进行修改．但是，这些修改记录是混合在一个实际日志文件中的．一种方法是把日志文件都读出来，然后只重复需要进行的修改项．但是，用这种方法，假如有100台机器都装载了要恢复的子表，那么这个日志文件要读取100次（每个服务器一次）．

避免这个问题的方法是先把日志按照关键字排序．在排序以后，所有的修改项都是连续的了，只要一次寻道操作，然后顺序读取．为了并行的排序，我们将日志分割成64MB的段，并在不同的子表服务器上并行的排序．这个排序工作是由主服务器来协同的，当一个子表服务器表示需要从某些日志文件中开始恢复修改，这个过程就开始了．

有时，向ＧＦＳ中写修改日志文件会导致性能不稳定，原因很多（例如，正在写的时候，一个ＧＦＳ服务器不行了，或者访问某三个ＧＦＳ服务器的网络路由断了或者拥塞）．为了在ＧＦＳ延迟的高峰时还能保证修改顺利进行，每个子表服务器实际上有两个线程：各自写不同的日志文件；两个线程里只有一个活跃．如果一个线程的写操作性能不好，就切换到另外一个线程，修改的记录就写入新的活跃线程的日志文件．每个日志项都有序列号，在恢复的时候，由于线程切换而导致的重复的序列号将被忽略．

加速子表的恢复

如果主服务器将一个子表从一个子表服务器移动到另外一个服务器，第一个子表服务器对子表进行轻度压缩．该压缩减少了子表服务器的日志文件中没有被紧缩的状态，从而减少了恢复时间．压缩完成以后，该服务器就停止服务该子表．然后，在卸载该子表前，该服务器再次进行一次（通常很快）轻度压缩，以消除在前面一次压缩时遗留下来的未紧缩的状态．第二次压缩做完以后，子表就可以被装载到另外一个服务器上，而不必请求从日志中恢复了．

利用不变性{immutability，不可写，可以并行读取}

除了SSTable缓存以外，由于所有生成的SSTable都是不变的，所以ＢＴ的很多其他部分都变的简单了．例如，当从SSTable读的时候，就不必进行同步．这样一来，对行的并行操作就可以非常有效的实现了．内存表是唯一一个被读和写操作同时访问的可变数据结构．为了减少在读操作中对内存表的竞争，内存表是写复制的，这样一来就可以并行进行读写操作．

因为SSTable是不变的，因此永久消除被删除的数据的问题，就转换成对过时的SSTable进行垃圾收集的问题了．每个子表的SSTable们都在元数据表进行注册．主服务器对SSTable集合进行标记-扫除的垃圾收集工作[25]，元数据表保存了根SSTable集合。

最后，SSTable的不变性使分裂子表的操作更加快速。我们不必为每个分裂出来的子表建立新的SSTable集合，而是让分裂的子表集合共享原来子表的SSTable集合。

//这里是第二部分.我发现如果一篇文章太大,我的blog就打开特别慢,不知是WORDPRESS的问题还是什么.所以这里另起一篇.

５．实现
ＢＴ的实现有三个主要组件：客户程序库，一个主服务器和多个子表服务器．针对负载的变化，可以动态的从服务器群中添加（或者去除）子表服务器．主服务器的任务是：给子表服务器指定子表，检测加入或者失效的子表服务器，子表服务器负载均衡，以及对google文件系统的文件进行垃圾收集．除此之外，它还处理诸如建立表和列族之类的表模式改变工作．

每个子表服务器管理一个子表集合（通常每个服务器处理数十乃至上千个子表）．子表服务器负责处理对它管理的子表进行的读写操作，当子表变的太大时，服务器会将子表分割．和很多单个主服务器分布式系统［17.21］一样，客户数据不经过主服务器．客户的读写操作是通过直接和子表服务器通信完成的．由于ＢＴ的客户不必通过主服务器获取子表位置信息，大多数客户完全不和主服务器通信．因此，实际使用中主服务器的负载很轻．

一个ＢＴ集群存储多个表．每个表由一些子表组成，每个子表包含一个行域内的所有数据．在起始状态下，一个表只有一个子表．当一个表长大以后，它自动的分割成多个子表，每个子表的缺省大小是100到200MB.

5.1 子表的地址

子表地址信息是存储在一个三层类似Ｂ＋树[10]的结构中的(图4)．

图4:子表地址结构

第一层是Chubby中的一个文件，它存储根子表的地址．根子表里存储一个特殊的表里的所有子表的地址，地址这个特殊的表是元数据表．每个元数据子表里存储一组用户子表的地址．根子表其实是元数据表里的第一个子表，但是对它的处理比较特殊：根子表永远不会被分割，这样一来保证了子表地址结构不会超过三层．

元数据表里面，每个子表的地址都对应一个行关键字，这个关键字是由子表所在的表的标识符，和子表的最后一行编码而成的．每个元数据行在内存里存储大约1kb的数据．元数据子表的大小限制是128MB，限制看似不大,不过已经可以让这个三层的地址树足够表示2^34个子表了（如果每个子表存储128MB数据，一共是2^61字节数据）．

客户程序库缓存了子表地址．如果客户没有一个子表的地址，或者它发现地址不正确，客户就递归的查询子表地址树．如果缓存是空的，那么寻址算法需要三次网络来回通信来寻址，其中包括一次Chubby读操作．如果缓存数据过期，那么寻址算法可能最多需要６次网络来回通信才能更新数据，因为只有在缓存不命中的时候才能发现数据过期｛三次通信发现过期，另外三次更新数据｝（这里的假定是，元数据子表没有频繁的移动）．子表的地址是放在内存里的，所以不必访问google文件系统ＧＦＳ，我们通过预取子表地址来进一步的减少了访问开销｛体系结构里的老花招：缓存，预取｝：每次读取子表的元数据的时候，都读取几个子表的元数据｛为什么不说预取几个子表地址？俩？四个？这里就是有价值的东西了，需要时间去积累经验｝．

在元数据表中还存储了次要信息，包括每个子表的事件日志（例如，什么时候一个服务器开始服务该子表）．这些信息有助于排错和性能分析｛一笔代过重要信息，比如都存了什么事件，事件属性是什么等｝．

5.2子表分配

在任一时刻，一个子表只会分配给一个子表服务器．主服务器知道当前有哪些活跃的子表服务器，还知道哪些子表分配到哪些子表服务器，哪些以及哪些子表没有被分配．当一个子表没有被分配到服务器，同时又有一个服务器的空闲空间足够装载该子表，主服务器就给这个子表服务器材发送一个装载请求，把子表分配给这个服务器．

｛这里是协议描述｝ＢＴ使用Chubby来追踪子表服务器．当一个子表服务器启动时，它在一个特定的Chubby目录里建立一个有唯一名字的文件，并获取该文件的独占的锁．主服务器监视这个目录{服务器目录}，就可以发现新的子表服务器．一个子表服务器如果丧失了对文件的锁，就停止对它的子表们的服务．服务器可能丧失锁的原因很多，例如：网络断开导致服务器丢失了Chubby会话（Chubby提供一种有效的服务，使子表服务器不必通过网络就能查询它是否还拥有文件锁｛这个比较神，难道是tablet server自己只查本地文件，chubby server来帮它在本地建立文件？要认真看看chubby的协议才知道｝）．如果文件依然存在，子表服务器会试图重新获得对文件的独占锁．如果文件不存在了，那么子表服务器就不能服务了，它就退出．当子表服务器终止时（例如，集群管理系统将子表服务器的机器从集群中移除），它会试图释放文件锁，这样一来主服务器就能更快的把子表分配给其他服务器．

当一个子表服务器不再服务它的子表的时候，主服务器有责任发现问题，并把子表尽快重新分配．主服务器发现问题的方法是定期询问子表服务器的文件锁状态．如果一个子表服务器报告丢失了文件锁，或者过去几次询问都没有反应，主服务器就会试图获取子表服务器的文件锁．如果主服务器能够获取锁，说明Chubby是好的，子表服务器或者是死了，或者不能和Chubby通信，主服务器就删除子表服务器的文件，以确保子表服务器不再服务子表．一旦一个服务器的文件被删除，主服务器就可以把它的子表都放入未分配的子表集合中．为了保证在主服务器和Chubby之间有网络故障的时候ＢＴ仍然可以使用，主服务器的Chubby会话一旦过期，主服务器就退出．但是，如前所述，主服务器故障不影响子表到子表服务器的分配．

当一个集群管理系统启动一个主服务器时，它需要发现当前的子表分配状态，然后才能修改分配状态｛设计思想：永远考虑失效＋恢复｝．主服务器执行以下启动步骤：(１)主服务器在Chubby中获取唯一的主文件锁，来阻止其他主服务器实例｛singlton｝．(2)主服务器材扫描Chubby服务器目录,获取当前活跃服务器列表.(3)主服务器和活跃子表服务器通信，获取子表分配状态｛注意子表分配不是主服务器存储的，保证了失效时主服务器不会成为性能瓶颈｝．（４）主服务器扫描元数据表，每次遇到一个没有分配的子表，就加入未分配子表集合，这个子表就可以被分配了．

这里有一个复杂的情况：在元数据表没有被分配之前，是不能扫描元数据表的｛鸡和蛋｝．因此，在开始第四步的扫描之前，如果第三步的扫描没有发现根子表没分配，主服务器就把根子表加入未分配的子表集合．这一附加步骤保证了根子表肯定会被分配．由于根子表包括了所有元数据子表的名字，主服务器在扫描过根子表以后，就知道了所有的元数据子表．

现存子表集合仅在以下事件中才会改变：一个子表被建立或者删除，两个子表被合并，或者一个子表被分割成两个．主服务器可以监控所有这些事件，因为前三个事件都是主服务器启动的．最后一个事件：分割子表，是由子表服务器启动的．这个事件是特别处理的．子表服务器在分割完毕时，在元数据表中记录新的子表的信息．当分割完成时，子表服务器通知主服务器．如果分割的通知没有到达（两个服务器中间死了一个），主服务器在请求子表服务器装载已经分割的子表的时候，就会发现这个没有通知的分割操作｛设计的时候一定要考虑到错误和失败的恢复．古人云，未思进,先思退｝．子表服务器就会重新通知主服务器，因为在元数据表中找到的子表入口只包含要求装载的子表的部分信息｛细节，细节呢？｝．

//今天比较忙,只有这些了.抱歉.

//更新:彼岸翻译了第5章的剩余部分,贴在这里:

5.3 子表服务

子表的状态存放在GFS里，如图5所示。更新内容提交到存放redo记录的提交日志里｛比较绕，看原文可能清楚点｝。在这些更新中，最近提交的那些存放在内存里一个叫memtable的有序缓冲里；老一点的更新则存放在一系列SSTable里。若要恢复一个子表，子表服务器从METADATA表中读取元数据。元数据包括了由一个子表和一系列redo点｛redo怎么翻好？｝组成的SSTable列表，这些是指向可能含有该子表数据的提交日志的指针｛烦死定语从句了｝。 该服务器把这些SSTable的索引读进内存，并通过重复redo点之后提交的更新来重建memtable。

当一个写操作到达子表服务器时，该服务器检查确信这个操作完整无误，而且发送方有权执行所描述的变换。授权是通过从一个Chubby文件里读取具有写权限的操作者列表来进行的（几乎一定会存放在Chubby客户缓存里）。合法的变换会写到提交日志里。可以用成组提交来提高大量小变换的吞吐量［13，16］。写操作提交后，写的内容就插入到memtable里。

当一个读操作到达子表服务器时，会作类似的完整性和授权检查。合法的读操作在一个由SSTable系列和memtable合并的视图里执行。由于SSTable和memtable是字典序的数据结构，合并视图可以很有效地形成。

进来方向的｛incoming｝读写操作在子表分拆和合并时仍能继续。

5.4 紧缩｛compaction｝

在执行写操作时，memtable的大小不断增加。当memtable大小达到一定阈值时，memtable就会被冻结，然后创建一个新的memtable，冻结住的memtable则被转换成SSTable并写到GFS里。这种次要紧缩过程有两个目的：缩小了子表服务器的内存用度，以及减少了在服务器当机后恢复过程中必须从提交日志里读取的数据量。 进来方向的读写操作在紧缩进行当中仍能继续。

每一个次要紧缩会创建一个新的SSTable。如果这种行为一直继续没有停止的迹象，读操作可能需要合并来自任意多SSTable的更新。相反，我们通过定期在后台执行合并紧缩来限定这类文件的数量。合并紧缩读取一些SSTable和memtable的内容，并写成一个新的SSTable。一旦紧缩完成，作为输入的这些个SSTable和memtable就可以扔掉了。

把所有SSTable重写成唯一一个SSTable的合并紧缩叫作主要紧缩。 由非主要紧缩产生的SSTable可以含有特殊的删除条目，它们使得老一点但仍活跃的SSTable中已删除的数据不再出现。而主要紧缩则产生不包含删除信息或删除数据的SSTable。Bigtable在它所有的子表中循环，并且定期对它们执行主要紧缩。这些主要紧缩使得Bigtable可以回收已删除数据占有的资源，并且还能保证已删除数据及时从系统里小时，这对存放敏感数据的服务很重要。

大表(Bigtable):结构化数据的分布存储系统

http://labs.google.com/papers/bigtable-osdi06.pdf
｛中是译者评论,程序除外｝

{本文的翻译可能有不准确的地方,详细资料请参考原文.}
摘要
bigtable是设计来分布存储大规模结构化数据的，从设计上它可以扩展到上２^50字节，分布存储在几千个普通服务器上．Ｇoogle的很多项目使用ＢＴ来存储数据，包括网页查询，google earth和google金融．这些应用程序对ＢＴ的要求各不相同：数据大小（从URL到网页到卫星图象）不同，反应速度不同（从后端的大批处理到实时数据服务）．对于不同的要求，ＢＴ都成功的提供了灵活高效的服务．在本文中，我们将描述ＢＴ的数据模型．这个数据模型让用户动态的控制数据的分布和结构．我们还将描述ＢＴ的设计和实现．

１．介绍

在过去两年半里，我们设计，实现并部署了ＢＴ．ＢＴ是用来分布存储和管理结构化数据的．ＢＴ的设计使它能够管理2^50 bytes(petabytes)数据，并可以部署到上千台机器上．ＢＴ完成了以下目标：应用广泛，可扩展，高性能和高可用性（high availability）. 包括google analytics, google finance, orkut, personalized search, writely和google earth在内的60多个项目都使用BT.这些应用对ＢＴ的要求各不相同，有的需要高吞吐量的批处理，有的需要快速反应给用户数据．它们使用的ＢＴ集群也各不相同，有的只有几台机器，有的有上千台，能够存储2^40字节(terabytes)数据．

ＢＴ在很多地方和数据库很类似：它使用了很多数据库的实现策略．并行数据库［１４］和内存数据库［１３］有可扩展性和高性能，但是ＢＴ的界面不同．ＢＴ不支持完全的关系数据模型；而是为客户提供了简单的数据模型，让客户来动态控制数据的分布和格式{就是只存储字串，格式由客户来解释}，并允许客户推断底层存储数据的局部性｛以提高访问速度｝．数据下标是行和列的名字，数据本身可以是任何字串．ＢＴ的数据是字串，没有解释｛类型等｝．客户会在把各种结构或者半结构化的数据串行化｛比如说日期串｝到数据中．通过仔细选择数据表示，客户可以控制数据的局部化．最后，可以使用ＢＴ模式来控制数据是放在内存里还是在硬盘上．｛就是说用模式，你可以把数据放在离应用最近的地方．毕竟程序在一个时间只用到一块数据．在体系结构里，就是：locality, locality, locality｝

第二节描述数据模型细节．第三节关于客户ＡＰＩ概述．第四节简介ＢＴ依赖的google框架．第五节描述ＢＴ的实现关键部分．第6节叙述提高ＢＴ性能的一些调整．第7节提供ＢＴ性能的数据．在第8节，我们提供ＢＴ的几个使用例子，第9节是经验教训．在第10节，我们列出相关研究．最后是我们的结论．

２．数据模型
ＢＴ是一个稀疏的，长期存储的｛存在硬盘上｝，多维度的，排序的映射表．这张表的索引是行关键字，列关键字和时间戳．每个值是一个不解释的字符数组．｛数据都是字符串，没类型，客户要解释就自力更生吧｝．

(row:string, column:string,time:int64)->string {能编程序的都能读懂，不翻译了}

//彼岸翻译的第二节

我们仔细查看过好些类似bigtable的系统之后定下了这个数据模型。举一个具体例子（它促使我们做出某些设计决定）， 比如我们想要存储大量网页及相关信息，以用于很多不同的项目；我们姑且叫它Webtable。在Webtable里，我们将用URL作为行关键字，用网页的某些属性作为列名，把网页内容存在contents:列中并用获取该网页的时间戳作为标识，如图一所示。

图一：一个存储Web网页的范例列表片断。行名是一个反向URL｛即com.cnn.www｝。contents列族｛原文用 family，译为族，详见列族｝存放网页内容，anchor列族存放引用该网页的锚链接文本。CNN的主页被Sports Illustrater｛即所谓SI，CNN的王牌体育节目｝和MY-look的主页引用，因此该行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本｛由时间戳标识，如t9，t8｝；而contents列则有三个版本，分别由时间 戳t3，t5，和t6标识。

行

表中的行关键字可以是任意字符串（目前支持最多64KB，多数情况下10－100字节足够了）。在一个行关键字下的每一个读写操作都是原子操作（不管读写这一行里多少个不同列），这是一个设计决定，这样在对同一行进行并发操作时，用户对于系统行为更容易理解和掌控。

Bigtable通过行关键字的字典序来维护数据。一张表可以动态划分成多个连续行。连续行在这里叫做“子表”｛tablet｝，是数据分布和负载均衡的单位。这样一来，读较少的连续行就比较有效率，通常只需要较少机器之间的通信即可。用户可以利用这个属性来选择行关键字，从而达到较好数据访问地域性｛locality｝。举例来说，在Webtable里，通过反转URL中主机名的方式，可以把同一个域名下的网页组织成连续行。具体来说，可以把maps.google.com/index.html中的数据存放在关键字com.google.maps/index.html下。按照相同或属性相近的域名来存放网页可以让基于主机和基于域名的分析更加有效。

列族

一组列关键字组成了“列族”，这是访问控制的基本单位。同一列族下存放的所有数据通常都是同一类型（同一列族下的数据可压缩在一起）。列族必须先创建，然后在能在其中的列关键字下存放数据；列族创建后，族中任何一个列关键字均可使用。我们希望，一张表中的不同列族不能太多（最多几百个），并且列族在运作中绝少改变。作为对比，一张表可以有无限列。

列关键字用如下语法命名：列族：限定词。 列族名必须是看得懂｛printable｝的字串，而限定词可以是任意字符串。比如，Webtable可以有个列族叫language，存放撰写网页的语言。我们在language列族中只用一个列关键字，用来存放每个网页的语言标识符。该表的另一个有用的列族是anchor；给列族的每一个列关键字代表一个锚链接，如图一所示。而这里的限定词则是引用该网页的站点名；表中一个表项存放的是链接文本。

访问控制，磁盘使用统计，内存使用统计，均可在列族这个层面进行。在Webtable举例中，我们可以用这些控制来管理不同应用：有的应用添加新的基本数据，有的读取基本数据并创建引申的列族，有的则只能浏览数据（甚至可能因为隐私权原因不能浏览所有数据）。

时间戳

Bigtable表中每一个表项都可以包含同一数据的多个版本，由时间戳来索引。Bigtable的时间戳是64位整型。可以由Bigtable来赋值，表示准确到毫秒的“实时”；或者由用户应用程序来赋值。需要避免冲突的应用程序必须自己产生具有唯一性的时间戳。不同版本的表项内容按时间戳倒序排列，即最新的排在前面。

为了简化对于不同数据版本的数据的管理，我们对每一个列族支持两个设定，以便于Bigtable对表项的版本自动进行垃圾清除。用户可以指明只保留表项的最后n个版本，或者只保留足够新的版本（比如，只保留最近7天的内容）。

在Webtable举例中，我们在contents:列中存放确切爬行一个网页的时间戳。如上所述的垃圾清除机制可以让我们只保留每个网页的最近三个版本。

//我开始翻译3,4节 

3.API
BT的ＡＰＩ提供了建立和删除表和列族的函数．还提供了函数来修改集群，表和列族的元数据，比如说访问权限．

// Open the table
Table *T = OpenOrDie(”/bigtable/web/webtable”);
// Write a new anchor and delete an old anchor
RowMutation r1(T, “com.cnn.www”);
r1.Set(”anchor:www.c-span.org”, “CNN”);
r1.Delete(”anchor:www.abc.com”);
Operation op;
Apply(&op, &r1);
图 2: 写入Bigtable.

在ＢＴ中，客户应用可以写或者删除值，从每个行中找值，或者遍历一个表中的数据子集．图2的Ｃ＋＋代码是使用RowMutation抽象表示来进行一系列的更新（为保证代码精简，没有包括无关的细节）．调用Apply函数，就对Ｗebtable进行了一个原子修改：它为http://www.cnn.com/增加了一个锚点，并删除了另外一个锚点．

Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily(”anchor”);
stream->SetReturnAllVersions();
scanner.Lookup(”com.cnn.www”);
for (; !stream->Done(); stream->Next()) {
printf(”%s %s %lld %s\n”,
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
图3: 从Bigtable读数据.

图3的Ｃ＋＋代码是使用Scanner抽象来遍历一个行内的所有锚点．客户可以遍历多个列族．有很多方法可以限制一次扫描中产生的行，列和时间戳．例如，我们可以限制上面的扫描，让它只找到那些匹配正则表达式*.cnn.com的锚点，或者那些时间戳在当前时间前10天的锚点．

ＢＴ还支持其他一些更复杂的处理数据的功能．首先，ＢＴ支持单行处理．这个功能可以用来对存储在一个行关键字下的数据进行原子的读-修改-写操作．ＢＴ目前不支持跨行关键字的处理，但是它有一个界面，可以用来让客户进行批量的跨行关键字处理操作．其次，ＢＴ允许把每个表项用做整数记数器．最后，ＢＴ支持在服务器的地址空间内执行客户端提供的脚本程序．脚本程序的语言是google开发的Sawzall[28]数据处理语言．目前，我们基于的Sawzall的ＡＰＩ还不允许客户脚本程序向ＢＴ内写数据，但是它允许多种形式的数据变换，基于任何表达式的过滤和通过多种操作符的摘要．

ＢＴ可以和MapReduce[12]一起使用．MapReduce是google开发的大规模并行计算框架．我们为编写了一套外层程序，使ＢＴ可以作为MapReduce处理的数据源头和输出结果．

4.建立ＢＴ的基本单元
ＢＴ是建立在其他数个google框架单元上的．ＢＴ使用google分布式文件系统(GFS)[17]来存储日志和数据文件{yeah, right, what else can it use, FAT32?}．一个ＢＴ集群通常在一个共享的机器池中工作，池中的机器还运行其他的分布式应用{虽然机器便宜的跟白菜似的，可是一样要运行多个程序，命苦的象小白菜}，ＢＴ和其他程序共享机器｛ＢＴ的瓶颈是ＩＯ/内存，可以和CPU要求高的程序并存｝．ＢＴ依赖集群管理系统来安排工作，在共享的机器上管理资源，处理失效机器并监视机器状态｛典型的server farm结构，ＢＴ是上面的应用之一｝．

ＢＴ内部存储数据的格式是google SSTable格式．一个SSTable提供一个从关键字到值的映射，关键字和值都可以是任意字符串．映射是排序的，存储的｛不会因为掉电而丢失｝，不可改写的．可以进行以下操作：查询和一个关键字相关的值；或者根据给出的关键字范围遍历所有的关键字和值．在内部，每个SSTable包含一列数据块（通常每个块的大小是64KB,但是大小是可以配置的｛索引大小是16 bits，应该是比较好的一个数｝）．块索引（存储在SSTable的最后）用来定位数据块；当打开SSTable的时候，索引被读入内存｛性能｝．每次查找都可以用一个硬盘搜索完成｛根据索引算出数据在哪个道上，一个块应该不会跨两个道，没必要省那么点空间｝：首先在内存中的索引里进行二分查找找到数据块的位置，然后再从硬盘读去数据块．最佳情况是：整个SSTable可以被放在内存里，这样一来就不必访问硬盘了．｛想的美，前面是谁口口声声说要跟别人共享机器来着？你把内存占满了别人上哪睡去？｝

ＢＴ还依赖一个高度可用的，存储的分布式数据锁服务Chubby[8]｛看你怎么把这个high performance给说圆喽｝．一个Chubby服务由5个活的备份｛机器｝构成，其中一个被这些备份选成主备份，并且处理请求．这个服务只有在大多数备份都活着并且互相通信的时候才是活的｛绕口令？去看原文吧，是在有出错的前提下的冗余算法｝．当有机器失效的时候，Chubby使用Paxos算法[9,23]来保证备份的一致性｛这个问题还是比较复杂的，建议去看引文了解一下问题本身｝．Chubby提供了一个名字空间，里面包括了目录和小文件｛万变不离其宗｝．每个目录或者文件可以当成一个锁来用，读写文件操作都是原子化的．Chubby客户端的程序库提供了对Chubby文件的一致性缓存｛究竟是提高性能还是降低性能？如果访问是分布的，就是提高性能｝．每个Chubby客户维护一个和Chubby服务的会话．如果一个客户不能在一定时间内更新它的会话，这个会话就过期失效了｛还是针对大server farm里机器失效的频率设计的｝．当一个会话失效时，其拥有的锁和打开的文件句柄都失效｛根本设计原则：失效时回到安全状态｝．Chubby客户可以在文件和目录上登记回调函数，以获得改变或者会话过期的通知．｛翻到这里，有没有人闻到java的味道了？｝

ＢＴ使用Chubby来做以下几个任务：保证任何时间最多只有一个活跃的主备份；来存储ＢＴ数据的启动位置（参考5.1节）；发现小表（tablet）服务器，并完成tablet服务器消亡的善后（5.2节）；存储ＢＴ数据的模式信息（每张表的列信息）；以及存储访问权限列表．如果有相当长的时间Chubby不能访问，ＢＴ就也不能访问了｛任何系统都有其弱点｝．最近我们在使用11个Chubby服务实例的14个ＢＴ集群中度量了这个效果，由于Chubby不能访问而导致BT中部分数据不能访问的平均百分比是0.0047%,这里Chubby不能访问的原因是Chubby本身失效或者网络问题．单个集群里，受影响最大的百分比是0.0326%｛基于文件系统的Chubby还是很稳定的｝.

看到两则新闻:”李开复透露Google中国研发方向 半年内出杀手锏“和”Google释中国份额下降内因 称半年内打败百度“.王怀南和李开复两人的时间表是一致的,就是谷歌未来半年会有大动作.

商业上的东西我不懂,单从技术上说,在第一条新闻里,李开复列出了5条:”互联网时代的超级计算机”、” 大规模分布式搜索”、”中文搜索技术”、”人工智能”和”本地化产品创新”.

“互联网时代的超级计算机”.最大的可能是大的server farm,类似在google的这种,利用大量便宜的linux PC的并行处理能力和存储能力来进行并行运算和海量存储.如今没有OS的PC已经便宜的跟白菜一个价了,美国这边我见过的有150美元一个的,批发肯定更便宜,虽然慢了点,但是谷歌的运算瓶颈目前好象还在硬盘那里吧?所以也够了.这里的问题是:电费.谷歌总部那里的电费可不便宜啊,搞不好的话,弄的跟美国这边一样,电费比机器还贵就麻烦了.

“大规模分布式搜索”.莫非,不是要做集中的server farm,而是要把计算/存储/带宽分布的放在全国各地?我想起前几天和彼岸,tiny还有霍大侠关于p2p存储的讨论来了.当然我相信谷歌的工具条不会偷偷摸摸的在用户不做事情的时候用他们的CPU cycle来搜点东西藏在用户的空闲磁盘空间上(那还不如改名叫3721算了),那么这个大规模的分布式搜索,看来还是要用谷歌自己的机器群.放在不同的ISP那里?有可能,电信的主干上连一群,联通的主干上连一群,省得从电信搜联通还联不通.

“中文搜索技术”.这个比较玄,什么意思呢?除了老套路的分词,或许还有高频词统计,在分词的时候看到高频词就停下来?这样一来就不会把我输入的东西给割成单字来搜索了.或者有针对中文用户语言习惯的特殊调整?总之比较模糊,不好猜,就不猜了.

“人工智能”和”本地化产品创新”,这两个大家伙,一个高不可攀,一个大的没边,我就不猜了,肯定猜不着.

这里点名”TV的Google观察Blog“,要么你们俩也猜猜?

今天去探访laobai的blog,终于明白老白为什么在照片里看起来很憔悴了

这个题目很大，我去年和彼岸讨论的时候，说了一个上午也没完全弄明白。现在tinyfool也发表了他的见解，看来，这个东西很可能要写成一个系列。我很不想把这个东西写成论文，实在是没有乐趣，不过很难避免了。

最早知道p2p存储是在系里听一个教授谈研究方向，当时的论点是，计算机的空闲磁盘容量是如此的多，而p2p又是如此的成功，因此应该搞一个p2p的共享磁盘空间应用。事实上，个人计算机的空闲能力非常的多，而已经有很多应用来利用这些能力。最早的例子是使用空闲ＣＰＵ时间，比如说NASA的SETI at home,就是利用个人计算机的空闲ＣＰＵ时间，用屏幕保护程序来处理射电望远镜接受的数据，看里面有没有一串类似这样的东西：１０，１１，１０１，１００１，１０１１，１１０１．．．Google在其早期还有好奇和共享精神的时候，也干过利用插件帮助计算蛋白质的空间结构的事情，现在反而在google lab里找不到了。

对空闲磁盘空间的利用，学术届有oceanstore， 工业界的应用，彼岸的“在线存储：现实还是明天？”里有很多例子。但是，存储数据的商业应用，还是有很多问题需要认真定义。我当时和彼岸的讨论中，有几个问题是比较重要的：技术上，p2p的服务质量。商业上，p2p的保密问题。后来还提出了服务的问题。

先说服务质量。tinyfool指出，要实现p2p的共享，一定要有两台机器同时在线。这里说的是服务质量的一个指标：可访问性。tinyfool同学认为，有人会提供这种服务。没错，比如说，tinyfool和keso要共享mp3，我愿意提供优质服务。可是，他们愿意用吗？我的机器跟他们之间的连接质量是怎样的？估计没有virushuo的好吧？不过，我的机器能一直在线，我不在乎电费，virushuo的机器就可能因为保证首都用电而被迫断电。那么，我的机器好，还是virushuo的机器好？我当时给了一个公式：Q = b * d * t ，量纲是byte^2。

这个公式里：b是两台机器之间可见的网络带宽，d是提供的共享空间，t是在线时间。这里有一个假定，就是机器的ＣＰＵ都足够快。

那么，一台能够被高速访问到的，提供大容量磁盘空间的，7*24在线的机器，就是服务质量好的机器。目前美国的网络上，很多人家是用ADSL，磁盘很空，永远开机。所以Ｑ应该是很好的。有了Ｑ，就有可能象oceanstore里提到的，用自己家的机器为别人提供服务来赢利，Ｑ是分红的指标。但是从中国的目前情况看，由于应用和ＩＳＰ的问题，很多时候b和t都还不能保证，所以我当时提出，需要存在中央服务器群来作为补充。

为了保证可访问性，除了指望其他用户一直在线，从系统结构的角度说，还要有冗余和分布存储。keso共享出来的文件，应该是分布在不同的机器上的，我的机器上有几块，virushuo的机器上有几块，有的数据块是我们俩都有的(冗余)，还有不认识的人的机器上也有。这样一来才能保证，当部分机器因为通信网或者电网的问题不能访问的时候，用户察觉不到。这样做的直接结果是：每个用户能够使用的磁盘空间，必定远小于他提供共享的空间。所以，allmydata的免费版本里，比例是1:10。

再说商业上的保密问题。

很可惜，我们的社会里有坏人。所以，当你使用第三台机器的时候，somebody is watching you!前面说的分布式存储可以从一定程度上防止第三台机器的主人偷你的全部源文件。但是，有的时候一段文字泄露也是要命的。所以，要加密。这个时候，前面说的公式里面，就要加进ＣＰＵ主频f了：Q’=b*d*t*f.当然，如果你只是存点照片什么的，本来就是要跟大家共享，那就不必了。真的吗？且慢！keso共享给tinyfool的mp3，根据tinyfool交代（ ），有几百首，那么，都是有版权的吗？当然，科学实验就不必追究责任了。不过，真的有人喜欢把银行帐号和密码存在一个文本文件里，然后放在共享盘上的…

最后的这个服务的问题，是比较新的想法。因为有了共享磁盘应用，还仅仅是有了一台裸机，实际的用户里面，能主动使用这种服务的人，少而又少。应当提供对用户的应用界面来把这个裸露的服务包装起来。在美国，因为Ｑ已经很好，所以针对普通用户的应用会启动。

和以往一样，本文对很多技术细节都没有详述，所以是不完备的，不严谨的。本人也是不负任何责任的。:)

更新:

我当时在写出Q的公式以后,困惑了很久,因为byte的平方是一个很奇怪的东西,以前好象没有这个单位.那么,是否是公式有问题呢?现在看来,这两个byte描述的东西是不一样的.一个byte描述的,是存储的需求;另外一个byte描述的,是对更新的需求.因为使用这个服务的用户有两种:一种是要用空间来存东西的,另外一种是用空间来传递更新的.前者用的是d,后者用的是b * t.但是,从服务者的角度来说,一个新的用户的目的是不明确的(连用户自己可能也不知道),所以,用byte平方来描述一个用户所提供的空间质量,是适合的. 或者,为了区别,用于存储的应该叫byte,而用于更新的,应该叫bit.毕竟,更新速度慢.

我今天无意中去看了ysearchblog.cn，感觉比黑板报要好。为什么呢？因为它贴近我，让我感觉很舒服，感觉是一群和我差不多的中国人在做事，写东西，要跟我交流。里面什么都有，连员工和老板的8g也有。

而黑板报的感觉，总是好象一群说中国话的外国人在写东西-你看着吧，都是一个个的汉字，读起来呢，也通顺（这点比自动翻译工具还是进步了很多很多地），可是，就是感觉人家在跟你宣扬：看，我们有企业文化，我们有自己的理念。而且每篇都写的滴水不漏。不知道为什么，虽然我对这种外企的味道很熟悉了，但是我总觉得笑脸后面还有点什么。有点什么呢？我嘴笨，说不出来，举个例子吧：

雅虎中国宣传马云的blog,写道：“马总第一博，来看啊！”这句话就很中国，就跟我同学当年喊“食堂今天鸡腿很大！”一个感觉。要是黑板报呢，估计会这么写：“开复开始写博客了，欢迎访问。”让我想起第一次去必胜客，坐的笔直，一边小心着不要把餐巾弄掉了，一边拿着刀叉奋力的锯比萨饼。

感觉是说不出来的，不过我每次看黑板报，总是不由自主的把椅子放低一点，抬着头看。我也不知道为什么。而且我看着看着，就有把中文翻译成英文的冲动，的确很奇特的感受。

当然，天才聚集地还是有好东西的，数学之美系列是我看黑板报的动力。雅虎也是有很多问题的，比如他家email对中文的支持，从来就没有好过…