Google三大论文（一）——Bigtable：一个分布式的结构化数据存储系统_外国关于数据结构的论文

资源地址（百度云）：链接：https://pan.baidu.com/s/14LgPQpjV-IWIepznDpQu3A 密码：k57n。这是某个大神翻译的中文版论文资料。

在重新阅读这篇论文的时候，本想对其进行一些提取总结，没想到越写越多。里面涉及到了较多的专业名词以及抽象概念，我加了一些个人注释便于理解。（有些注释是翻译的那个大神加的）。

一、应用场景

1.处理海量数据：通常是分布在数千台普通服务器上的PB级数据。

2.Bigtable对具有不同需求的应用提供了一个灵活的、高性能的解决方案。（无论是在数据量上还是响应速度上）

3.通过Bigtable提供的简单数据模型，用户可以动态地控制数据的分布和格式。

二、介绍

1.设计目的：可靠的处理PB级别的数据，并且能够部署到上千台机器上。

2.目前已实现：适用性广泛、可扩展、高性能和高可用性。

概念解释：

A.可扩展性（可伸缩性）是一种对软件系统计算处理能力的设计指标，高可伸缩性代表一种弹性，在系统扩展成长过程中，软件能够保证旺盛的生命力，通过很少的改动甚至只是硬件设备的添置，就能实现整个系统处理能力的线性增长，实现高吞吐量和低延迟高性能。简单说就是，你的系统能不能在访问用户量增大时，通过较小改动就可以保持原来较快的响应速度。如果你的系统对一个用户来说是快的，但是在用户不断增长的高访问量下就慢了，这叫说明你的系统出现了扩展性问题。

延迟和吞吐量是衡量可扩展性的一对指标，我们希望获得低延迟和高吞吐量的系统架构。所谓低延迟，也就是用户能感受到的系统响应时间，比如一个网页在几秒内打开，越短表示延迟越低，而吞吐量表示同时有多少用户能够享受到这种低延迟，如果并发用户量很大时，用户感觉网页的打开速度很慢，这意味着系统架构的吞吐量有待提高。

扩展性的目标是用可接受的延迟获得最大的吞吐量。可靠性(可用性)目标：用可接受的延迟获得数据更新的一致性。

B.高可用性（High Availability）通常来描述一个系统经过专门的设计，从而减少停工时间，而保持其服务的高度可用性。

3.数据格式：并行数据库和内存数据库已经具备可扩展性和高性能，但是Bigtable提供了一个和这些系统完全不同的接口。Bigtable不支持完整的关系数据模型，与之相反，它为客户提供了简单的数据模型，利用这个模型，用户可以动态控制数据的分布和格式。（也就是对Bigtable而言，数据是没有格式的，用户自己去定义数据格式），用户也可以自己去推测底层储存数据的位置相关性（比如树状结构，具有相同前缀的数据的存放位置接近，在读取的时候，可以把这些数据一次读取出来）。

4.数据存放：数据的下标是行和列的名字，名字可以是任意的字符串。Bigtable将储存的数据都是字符串，但是Bigtable本身不去解析这些字符串，客户程序通常会把各种结构化和半结构化的数据串行化到这些字符串里。通过仔细选择数据的模式，客户可以控制数据的位置相关性。最后可以通过Bigtable的模式参数来控制数据是存放在内存中还是硬盘上。

三、数据模型

Bigtable是一个稀疏的、分布式的、持久化存储的多维度排序Map。Map的索引是行关键子、列关键字以及时间戳；Map中的每一个value都是未经解析的byte数组。（以往我们用的较多的可能就是一维的，就是一个value对应一个关键字。多维度一方面储存的数据量会比较大，另一方面也可以更好地满足现实的需求，比如时间戳。当我们在浏览网页时，它可以帮我们缓存不同时间段的浏览信息，以便我们后续回过头来查看）

具体的数据模型：我们姑且称这个特殊的表尾Webtable。在Webtable里，我们使用URL作为行关键字，使用网页的某些属性作为列名（比如content，anchor-锚链接等），并用时间戳作为标识（即按照获取时间的不同出承诺了多个版本的网页数据）。如下图。其中行名是一个反向URL。content列族存放的是网页的内容，有三个版本（分别由t3,t5,t6标识）。anchor列族存放的是引用该网页的锚链接文本，每个锚链接只有一个版本。

表中的行关键字可以是任意的字符串（目前支持最大64kB的字符串）对同一个行的读或者写操作都是原子的（不管读或者写这一行里多少个不同列），这个设计决策能够是用户很容易理解程序在对同一个行进行并发更新操作时的行为。（这样子还能并发吗？）

概念：原子操作

所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。如果这个操作所处的层(layer)的更高层不能发现其内部实现与结构，那么这个操作是一个原子(atomic)操作。原子操作可以是一个步骤，也可以是多个操作步骤，但是其顺序不可以被打乱，也不可以被切割而只执行其中的一部分。将整个操作视作一个整体是原子性的核心特征。

行：Bigtable通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。（对行分区而不是对某一行中的列分区）每个分区叫做一个"Tablet"，Tablet是数据分布和负载均衡调整的最小单位。这样做的结果是，当操作只读取行中很少几列的数据时效率很高，通常只需要很少几次机器间的通信即可完成。用户可以通过选择合适的行关键字，在数据访问时有效利用数据的位置相关性，从而更好地利用这个特性。具体来说，我们可以把maps.google.com/index.html的数据存放在关键字com.google.maps/index.html下面一行，把相同的域中的网页存储在连续的区域可以让基于主机域名的分析更加有效。

列族：列关键字组成的集合叫做“列族”，列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型（我们可以把同一个列族下的数据压缩在一起）。根据我们的设计意图一张表中的列族不能太多（最多几百个），并且列族在运行期间很少改变。与之对应的，一张表中可以有无限多个列。刚看到这个地方感觉有点矛盾，我们可以看下下面这个示意图。其中"anchor:cnnsi.com"和"anchor:my.look.ca"这两个列关键字可以组成一个"anchor"列族，因为他们都是锚链接，而"contents."可以自成一个"text"列族，因为它属于文本内容。其中像"anchor"、"text"这些列族不能太多，但是像"contents."、"anchor:cnnsi.com"和"anchor:my.look.ca"这些列关键字是可以无限多的。

列关键字的命名语法如下：列族：限定词。列族的名字必须是可打印的字符串（可打印字符是指除ASCII码0～31及127(共33个)是控制字符或通信专用字符，剩余的都属于可打印字符。也就是可打印的字符串中不能包含这些特殊字符），而限定词的名字可以是任意的字符串。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的Webtable的例子中上述的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数据，一些应用可以读取基本数据并创建继承的列族，一些应用则只允许浏览数据甚至因为隐私的原因不能浏览所有的数据。

时间戳：在Bigtable中，表的每一个数据都可以包含同一份数据的不同版本；不同版本的数据通过时间戳索引。Bigtable时间戳的类型是64位整型。Bigtable可以给时间戳赋值，用来表示精确到毫秒的“实时”时间；用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突，那么它必须自己生成一具有唯一性的时间戳。数据项中，不同版本的数据按照时间戳倒序排序，即最新的数据排在最前面。

为了减轻多个版本数据的管理负担，我们对每一个列族配有两个设置参数，Bigtable通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据，或者只保存“足够新”的版本的数据（比如，最保存最近7天的内容写入的数据）。

在Webtable的举例里，contents：列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据。

四、API

Bigtable提供了建立和删除表以及列族的API函数。Bigtable还提供了修改集群、表和列族的元数据的API，比如修改访问权限。

客户程序可以对Bigtable进行如下操作：写入或者删除Bigtable中的值、从每个行中查找值、或者遍历表中的每一个数据子集。客户程序可以遍历多个列族，并对扫描输出的行、列和时间戳进行限制。Bigtable可以对数据进行更复杂的处理。首先，Bigtable支持单行上的事务处理，利用这个功能，用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操作。虽然Bigtable提供了一个允许用户跨行批量写入数据的接口，但是，Bigtable目前还不支持通用的跨行事务处理。其次，Bigtable允许把数据项用作整数计数器。最后，Bigtable允许用户在服务器的地址空间内执行脚本。

Bigtable可以和MapReduce一起使用，MapReduce是Google开发的大规模并行计算框架。我们已经开发了一些Wrapper类，通过使用这些类，Bigtable可以作为MapReduce框架的输入和输出。

五、Bigtable构件

Bigtable使用Google的分布式文件系统（GFS）储存日志文件和数据文件。Bigtable集群通常运行在一个共享的机器池中，池中的机器还会运行其他的各种各样的分布式应用程序，Bigtable进程经常要和其他应用的的进程共享机器。Bigtable以来集群管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。

Bigtable内部存储数据的文件时Google SSTable格式的。SSTable是一个持久化的、排序的、不可更改的Map结构，而Map是一个key-value映射的数据结构，key和value的值都是任意的byte串。SSTable是一系列的数据块（通常每个块的大小时64KB，可以自己配置）。SSTable使用块索引来定位数据块：在打开SSTable的时候索引被加载到内存。每次查找都可以通过一次磁盘搜索完成：首先使用二分查找法在内存中找到数据块的位置，然后在从硬盘中读取相应的数据块。也可以把整个SSTable都放在内存中，这样就不必访问硬盘了。

Bigtable还依赖一个高可用、序列化的分布式锁服务组件，叫做Chubby。一个Chubby服务包括五个活动的副本，其中一个副本被选为master，并且处理请求。只有在大多数副本都是正常运行，并且彼此之间能够互相通信的情况下，Chubby服务才是可用的。当有副本失效的时候，Chubby使用Paxos算法（？？？）来保证副本的一致性。Chubby提供了一个名字空间，包含目录和小文件。每个目录和小文件都可以当成一个锁，读写文件的操作都是原子的。Chubby客户程序提供对Chubby文件的一致性缓存。每个Chubby客户程序都维护一个与Chubby服务的会话。如果客户程序不能在租约到期的时间内重新签订会话的租约，这个会话就过期失效了。当一个会话失效时，它所拥有的锁和打开的文件句柄都失效了。Chubby客户程序可以在文件和目录上注册回调函数，当文件或目录改变、或者会话过期时，回调函数会通知客户程序。

Bigtable使用Chubby函数完成以下的几个任务：确保在任何给定的时间内最多只有一个活动的Master副本；存储Bigtable数据的自引导指令的位置；查找Tablet服务器，以及在Tablet服务器失效时进行善后；存储Bigtable的模式信息（每张表的列族信息）；以及存储访问控制列表。如果Chubby长时间无法访问，Bigtable就会失效。

六、介绍

Bigtable包括了三个主要的组件：链接到客户程序中的库、一个Master服务器和多个Tablet服务器。针对系统工作负载的变化情况，Bigtable可以动态地向集群中添加（或者删除）Tablet服务器。

Master服务器主要负责以下工作：为Tablet服务器分配Tablets，检测重新加入的或者过期失效的Table服务器、对Table服务器进行负责均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外，它还处理对模式的相关修改操作，例如建立表和列族。

每个Tablet服务器都管理一个Tablet的集合（通常每个服务器有大约数十个至上千个Tablet）。每个Tablet服务器负责处理它所加载的Tablet的读写操作，以及在Tablets过大时，对其进行分割。

和很多Single-Master类型的分布式存储系统类似，客户端读取的数据都不经过Master服务器：客户程序直接和Tablet服务器通信进行读写操作。由于Bigtable的客户程序不必通过Master服务器来获取Tablet的位置信息，因此，大多数客户程序甚至完全不需要和Master服务器通信。在实际应用中，Master服务器的负载是很轻松的。（Master只需要跟应用程序指明Tablet所在的服务器即可。）

。一个Bigtable集群存储了很多表，每个表包含了一个Tablet的集合，而每个Tablet包含了某个范围内的行的所有相关数据。初始状态下，一个表只有一个Table。随着表中数据的增长，它被自动分割成多个Tablet，缺省情况下，每个Tablet的尺寸大约是100MB到200MB。

6.1Tablet的位置

我们使用一个三层的、类似B+树的结构存储Tablet的位置信息。

第一层是一个存储在Chubby中的文件，它包含了Root Tablet的位置信息。METATABLET表的每个Tablet包含了一个用户Tablet的集合。Root Tablet实际上是METADATA表的第一个Tablet，如下图

只不过对它的处理比较特殊——Root Tablet永远不会被分割——这就保证了Tablet的位置信息存储结构不会超过三层。

在METATABLET表里面，每个Tablet的位置信息都存放在一个行关键字下面，而这个行关键字（应该是行关键字里面存放的内容）是由Tablet所在的表的标识符和Tablet的最后一行编码而成的

METATABLET中的每一行都存储了大约1KB的内存数据。在一个大小适中的、容量限制为128MB的METADATA Tablet中，采用这种三层结构的存储模式，可以标识2^34个Tablet的地址（如果每个Tablet存储128MB数据，那么一共可以存储2^61字节数据）。（？？？）

客户程序使用的库会缓存Tablet的位置信息。如果客户程序没有缓存某个Tablet的地址信息，或者发现它缓存的地址信息不正确，客户程序就会在树状的存储结构中递归地查询Tablet位置信息；如果客户端缓存是空的，那么寻址算法需要通过三次网络来回通信寻址，这其中包括了一次Chubby读操作；如果客户端缓存的地址信息过期了，那么寻址算法可能最多需要6次网络来回通信才能更新数据，因为只有在缓存中没有查到数据的时候才能发现数据过期（其中的三次用于发现缓存过期，另外三次更新缓存数据）。尽管Tablet的地址信息是存放在内存里的，对它的操作不必访问GFS文件系统，但是，通常我们会通过预期Tablet地址来进一步地减少访问的开销：每次需要从METADATA表中读取一个Tablet的元数据的时候，它都会多读取几个Tablet的元数据。（有点像空间局部性原理）。

在METADATA表中还存储了次级信息，包括每个Tablet的事件日志，有助于排查错误和性能分析。

6.2Tablet分配

在任何时刻，一个Tablet只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的Tablet服务器，哪些Tablet分配给了哪些Tablet服务器。哪些Tablet还没有别分配。当一个Tablet还没有被分配，并且刚好有一个Tablet服务器有足够的空闲空间装载该Tablet时，Master服务器会给这个Tablet服务器发送一个装载请求，把Tablet分配给这个服务器。

Bigtablet使用Chubby跟踪记录Tablet服务器的状态。当一个Tablet服务器启动时，它在Chubby的一个指定目录下建立一个有唯一性名字的文件，并且获取该文件的独占锁。Master服务器实时监控着这个目录（服务器目录），因此、master服务器能够知道有新的Tablet服务器加入了。如果Tablet服务器丢失了Chubby上的独占锁——比如由于网络断开导致Tablet服务器和Chubby的会话丢失——它就停止对Tablet提供服务。（Chubby提供了一种高效的机制，利用这种机制，Tablet服务器能够在不增加网络负担的情况下知道它是否还持有锁）。只要文件还存在，Tablet服务器就会试图重新获取对该文件的独占锁。如果文件不存在了，那么Tablet服务器就不能再提供服务了，它会自行退出。当Tablet服务器终止时（比如，集群的管理系统将运行该Tablet服务器的主机从集群中移除），它会尝试释放它持有的文件锁，这样一来，Master服务器就能尽快吧Tablet分配到其他的Tablet服务器。

Master服务器负责检查一个Tablet服务器是否已经不再为它的Tablet提供服务了，并且要尽快重新分配它加载的Tablet。Master服务器通过轮训Tablet服务器文件锁的状态来检测何时Tablet服务器不再为Tablet提供服务，如果一个Tablet服务器报告它丢失了文件锁，或者Master服务器最近几次尝试和它通信都没有得到响应，Master服务器就会尝试获取该Tablet服务器文件的独占锁；如果Master服务器成功获取了独占锁，那么就说明Chubby是正常运行的，而Tablet服务器要么是宕机（宕(dang)机，指操作系统无法从一个严重系统错误中恢复过来，或系统硬件层面出问题，以致系统长时间无响应，而不得不重新启动计算机的现象。）、要么是不能和Chubby通信了，因此，Master服务器就删除该Tablet服务器在Chubby上的服务器文件以确保它不再给Tablet提供服务，一旦Tablet服务器在Chubby上的服务器文件被删除了，Master服务器就把之前分配给它的所有Tablet放入未分配的Tablet集合中。为了确保Bigtable集群在Master服务器和Chubby之间网络出现故障时仍然可以使用，Master服务器在它的Chubby会话过期后主动退出。但是不管怎样，如同我们前面所描述的，Master服务器的故障不会改变现有Tablet在Tablet服务器上的分配状态。

当集群管理系统启动了一个Master服务器之后，Master服务器首先要了解当前Tablet的分配状态，之后才能够修改分配状态。Master服务器在启动时执行以下步骤：（1）Master服务器从Chubby获取一个唯一的Master锁，用来阻止创建其他的Master服务器实例；（2）Master服务器扫描Chubby的服务器文件锁存储目录，获取当前正在运行的Master服务器实例；（3）Master服务器和所有正在运行的Tablet表服务器通信，获取每个Tablet服务器上Tablet的分配信息；（4）Master服务器扫描METADATA表获取所有Tablet集合。在扫描的过程中，当Master服务器发现了一个还没有分配的Tablet，Master服务器就将这个Tablet加入到未分配的Tablet集合等待合适的时机分配。

可能会遇一种复杂的情况：在METADATA表中的Tablet还没有被分配之前是不能够扫面它的。因此，在开始扫描之前（步骤4），如果在第三步的扫描过程中发现Root Tablet还没有被分配，Master服务器就把Root Tablet加入到未分配的Tablet集合。这个附加操作确保了Root Tablet会被分配。由于Root Tablet包括了所有METADATA的Tablet的名字，因此Master服务器扫描完RootTablet以后，就得到了所有的METADATA表的Tablet的名字了。

保存现有Table的集合只有在一下事件发生时才会改变：建立了一个新表或者删除了一个旧表，两个Tablet被合并了、或者一个Tablet被分割成两个小的Tablet。Master服务器可以跟踪记录所有这些事件，因为除了最后一个事件外的两个事件都是由它启动的。Tablet分割事件需要特殊处理，因为它是由Tablet服务器启动。在分割操作完成之后，Tablet服务器会通知Master服务器。如果分割操作已提交的信息没有通知到Master服务器（可能两个服务器中有一个宕机了），Master服务器在要求Tablet服务器装载已经被分割的子表时会发现一个新的Tablet。通过对比METADATE表中的Tablet的信息，Tablet服务器会发现Master服务器要求其装载的Tablet并不完整，因此，Tablet服务器会重新向Master服务器发送通知消息。

6.3Tablet服务

如图，Tablet的持久化状态信息保存在GFS上。更新操作提交到REDO日志中。在这些更新操作中，最近提交的那些存放在一个排序的缓存中，我们称这个缓存为memtable；较早的更新存放在一系列SSTable中。为了恢复一个Tablet，Tablet服务器首先从METADATA表中读取它的元数据。Tablet的元数据包含了组成这个Tablet的SSTable的列表，以及一系列的Redo Point，这些Redo Point指向可能含有该Tablet数据的已提交的日志记录。Tablet服务器把SSTable的索引读进内存，之后通过重复Redo point之后提交的更新来重建memtable。

当对Tablet服务器进行写操作时，Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是通过一个从Chubby文件里读取出来的具有写权限的操作者列表来进行验证（这个文件几乎一定会存放在Chubby客户缓存里）。成功的修改操作会记录在提交日志里。可以采用批量提交的方式来提高大量小的修改操作的应用程序的吞吐量。当一个写操作提交后，写的内容插入到memtable里面。

当对Tablet服务器进行读操作时，Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个由一系列SSTable和memtable合并的视图里执行。由于SSTable和memtable是按字典排序的数据结构，因此可以高效生成合并视图。

当进行Tablet的合并和分割时，正在进行的读写操作能够继续进行。

6.4Compactions

随着写操作的执行，memtable的大小不断增加。当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一个新的memtable；被冻结住的memtable会被转换成SSTable，然后写入GFS。Minor Compaction过程有两个目的：shrink（收缩）Tablet服务器的内存，以及在服务器灾难恢复过程中，减少必须从提交日志里读取的数据量。在Com怕窗体on过程中，正在进行的读写操作仍能继续。

每一次Minor Com爬梯on都会创建一个新的SSTable。如果Minor Com爬梯on过程中不停滞的持续进行下去，读操作可能需要合并来自多个SSTable的更新；否则，我们通过定期在后台执行Merging Compaction过程合并文件，限制这类文件的数量。Merging Compaction过程读取一些SSTable和memtable的内容，合并成一个新的SSTable。只要Merging Compaction过程完成了，输入的这些SSTable和memtable就可以删除了。

合并所有的SSTable并生成一个新的SSTable的Merging Compaction的过程叫做Major Compaction。由非Major Compaction产生的SSTable可能含有特殊的删除条目，这些删除条目能够隐藏在旧的、但是依然有效的SSTable中已经删除的数据。而Major Compaction过程生成的SSTable不包含已经删除的信息或数据。Bigtable循环扫描它所有的Table，并且定期定期对它们执行Major Compaction。Major Compaction机制允许Bigtable回收已经删除的数据占有的资源，并且确保Bigtable能及时清除已经删除的数据（回收资源。数据删除后，它占有的空间并不能马上重复利用；只有空间回收后才能重复使用），这对厨房敏感数据的服务是非常重要的。

七、优化

1.局部性群组。

客户程序可以将多个列族合成一个局部新群组。对Tablet中的每个局部性群组都会生成一个单独的SSTable.将通常不会一起访问的列族分割成不同的局部性群组可以提高读取操作的效率。例如，在Webtable表中，网页的元数据可以在一个局部性群组中，网页的内容可以在另外一个群组。当一个应用程序要读取网页的元数据时，它没有必要去读取所有的页面内容。

此外，可以以局部性群组为单位设定一些有用的调试参数。比如，可以把一个局部性群组设定为全部存储 在内存中。Tablet服务器依照惰性加载的策略将设定为放入内存的局部性群组的SSTable装载进内存。加 载完成之后，访问属于该局部性群组的列族的时候就不必读取硬盘了。这个特性对于需要频繁访问的小块 数据特别有用：在Bigtable内部，我们利用这个特性提高METADATA表中具有位置相关性的列族的访问速度。

压缩

客户程序可以控制一个局部性群组的SSTable是否需要压缩；如果需要压缩，那么以什么格式来压缩。每 个SSTable的块（块的大小由局部性群组的优化参数指定）都使用用户指定的压缩格式来压缩。虽然分块 压缩浪费了少量空间（相比于对整个SSTable进行压缩，分块压缩压缩率较低），但是，我们在只读取SSTable的一小部分数据的时候就不必解压整个文件了。很多客户程序使用了“两遍”的、可定制的 压缩方式。第一遍采用Bentley and McIlroy’s方式，这种方式在一个很大的扫描窗口里对常见的长字 符串进行压缩；第二遍是采用快速压缩算法，即在一个16KB的小扫描窗口中寻找重复数据。

虽然我们在选择压缩算法的时候重点考虑的是速度而不是压缩的空间，但是这种两遍的压缩方式在空间压缩率上的表现也是令人惊叹。比如，在Webtable的例子里，我们使用这种压缩方式来存储网页内容。“两遍”的压缩模式非常高效，原因是由于 Webtable的行的存放方式：从同一个主机获取的页面都存在临近的地方。利用这个特性，BentleyMcIlroy算法可以从来自同一个主机的页面里找到大量的重复内容。不仅仅是Webtable，其它的很多应用程序也通过选择合适的行名来将相似的数据聚簇在一起，以获取较高的压缩率。当我们在Bigtable中存储同一份数据的多个版本的时候，压缩效率会更高。

通过缓存提高读操作的性能

为了提高读操作的性能，Tablet服务器使用二级缓存的策略。扫描缓存是第一级缓存，主要缓存Tablet服务器通过SSTable接口获取的Key-Value对；Block缓存是二级缓存，缓存的是从GFS读取的SSTable的 Block。对于经常要重复读取相同数据的应用程序来说，扫描缓存非常有效；（类似于时间局部性）对于经常要读取刚刚读过的数据附近的数据的应用程序来说，Block缓存更有用（类似于空间局部性)。

Bloom过滤器

一个读操作必须读取构成Tablet状态的所有SSTable的数据。如果这些SSTable不在内存中，那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的SSTable指定Bloom过滤器 ，来减少硬盘访问的次数。我们可以使用Bloom过滤器查询一个SSTable是否包含了特定行和列的数据。对于某些特定应用程序，我们只付出了少量的、用于存储Bloom过滤器的内存的代价，就换来了读操作显著减少的磁盘访问的次数。使用Bloom过滤器也隐式的达到了当应用程序访问不存在的行或列时，大多数时候我们都不需要访问硬盘的目的。

Commit日志的实现

如果我们把对每个Tablet的操作的Commit日志都存在一个单独的文件的话，那么就会产生大量的文件， 并且这些文件会并行的写入GFS。根据GFS服务器底层文件系统实现的方案，要把这些文件写入不同的磁盘日志文件时，会有大量的磁盘Seek操作。另外，由于批量提交中操作的数目一般比较少，因此，对每个Tablet设置单独的日志文件也会给批量提交本应具有的优化效果带来很大的负面影响。为了避免这些问题，我们设置每个Tablet服务器一个 Commit日志文件，把修改操作的日志以追加方式写入同一个日志文件，因此一个实际的日志文件中混合了对多个Tablet修改的日志记录。

使用单个日志显著提高了普通操作的性能，但是将恢复的工作复杂化了。当一个Tablet服务器宕机时，它加载的Tablet将会被移到很多其它的Tablet服务器上：每个Tablet服务器都装载很少的几个原来的服务器的Tablet。当恢复一个Tablet的状态的时候，新的Tablet服务器要从原来的Tablet服务器写的日志中提取修改操作的信息，并重新执行。然而，这些Tablet修改操作的日志记录都混合在同一个日志文件中的。一种方法，新的Tablet服务器读取完整的Commit日志文件，然后只重复执行它需要恢复的Tablet的相关修改操作。使用这种方法，假如有100台Tablet服务器，每台都加载了失效的Tablet服务器上的一个Tablet， 那么，这个日志文件就要被读取100次（每个服务器读取一次）。

为了避免多次读取日志文件，我们首先把日志按照关键字排序。排序之后，对同一个Tablet的修改操作的日志记录就连续存放在了一起，因此，我们只要一次磁盘Seek操作、之后顺序读取就可以了。为了并行排序，我们先将日志分割成64MB的段，之后在 不同的Tablet服务器对段进行并行排序。这个排序工作由Master服务器来协同处理，并且在一个Tablet服务器表明自己需要从Commit日志文件恢复Tablet时开始执行。

在向GFS中写Commit日志的时候可能会引起系统颠簸，原因是多种多样的（比如，写操作正在进行的时 候，一个GFS服务器宕机了；或者连接三个GFS副本所在的服务器的网络拥塞或者过载了）。为了确保在 GFS负载高峰时修改操作还能顺利进行，每个Tablet服务器实际上有两个日志写入线程，每个线程都写自己的日志文件，并且在任何时刻，只有一个线程是工作的。如果一个线程的在写入的时候效率很低，Tablet服务器就切换到另外一个线程，修改操作的日志记录就写入到这个线程对应的日志文件中。每个日志记录都有一个序列号，因此，在恢复的时候，Tablet服务器能够检测出并忽略掉那些由于线程切换而导致的重复的记录。

Tablet恢复提速

当Master服务器将一个Tablet从一个Tablet服务器移到另外一个Tablet服务器时，源Tablet服务器会对这 个Tablet做一次Minor Compaction。这个Compaction操作减少了Tablet服务器的日志文件中没有归并的记录，从而减少了恢复的时间。Compaction完成之后，该服务器就停止为该Tablet提供服务。在卸载Tablet之前，源Tablet服务器还会再做一次（通常会很快）Minor Compaction，以消除前面在一次压缩 过程中又产生的未归并的记录。第二次Minor Compaction完成以后，Tablet就可以被装载到新的Tablet 服务器上了，并且不需要从日志中进行恢复。

利用不变性

我们在使用Bigtable时，除了SSTable缓存之外的其它部分产生的SSTable都是不变的，我们可以利用这 一点对系统进行简化。例如，当从SSTable读取数据的时候，我们不必对文件系统访问操作进行同步。这样一来，就可以非常高效的实现对行的并行操作。memtable是唯一一个能被读和写操作同时访问的可变数据结构。为了减少在读操作时的竞争，我们对内存表采用COW(Copy-on-write)机制，这样就允许读写操作并行执行。

因为SSTable是不变的，因此，我们可以把永久删除被标记为“删除”的数据的问题，转换成对废弃的 SSTable进行垃圾收集的问题了。每个Tablet的SSTable都在METADATA表中注册了。Master服务器采用 “标记-删除”的垃圾回收方式删除SSTable集合中废弃的SSTable，METADATA表则保存了Root SSTable的集合。

最后，SSTable的不变性使得分割Tablet的操作非常快捷。我们不必为每个分割出来的Tablet建立新的SSTable集合，而是共享原来的Tablet的SSTable集合。

八、性能评估

单个Tablet服务器的性能

随机读的性能比其它操作慢一个数量级或以上。每个随机读操作都要通过网络从GFS传输64KB的SSTable到 Tablet服务器。

内存中的随机读操作速度快很多，原因是，所有1000-byte的读操作都是从Tablet服务器的本地内存中读取数据，不需要从GFS读取64KB的Block。

随机和序列写操作的性能比随机读要好些，原因是每个Tablet服务器直接把写入操作的内容追加到一个 Commit日志文件的尾部，并且采用批量提交的方式，通过把数据以流的方式写入到GFS来提高性能。

随机写和序列写在性能上没有太大的差异，这两种方式的写操作实际上都是把操作内容记录到同一个Tablet 服务器的Commit日志文件中。

序列读的性能好于随机读，因为每取出64KB的SSTable的Block后，这些数据会缓存到Block缓存中，后续的64次读操作直接从缓存读取数据。

扫描的性能更高，这是由于客户程序每一次RPC调用（RPC（Remote Procedure Call）——远程过程调用，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC采用客户机/服务器模式。请求程序就是一个客户机，而服务提供程序就是一个服务器。首先，客户机调用进程发送一个有进程参数的调用信息到服务进程，然后等待应答信息。在服务器端，进程保持睡眠状态直到调用信息到达为止。当一个调用信息到达，服务器获得进程参数，计算结果，发送答复信息，然后等待下一个调用信息，最后，客户端调用进程接收答复信息，获得进程结果，然后调用执行继续进行。）都会返回大量的value的数据，所以，RPC调用的消耗 基本抵消了。

性能提升

随着我们将系统中的Tablet服务器从1台增加到500台，系统的整体吞吐量有了梦幻般的增长，增长的倍率 超过了100。比如，随着Tablet服务器的数量增加了500倍，内存中的随机读操作的性能增加了300倍。

之所以会有这样的性能提升，主要是因为这个基准测试的瓶颈是单台Tablet服务器的CPU。 尽管如此，性能的提升还不是线性的。在大多数的基准测试中我们看到，当Tablet服务器的数量从1台增加 到50台时，每台服务器的吞吐量会有一个明显的下降。这是由于多台服务器间的负载不均衡造成的，大多数情况下是由于其它的程序抢占了CPU。 我们负载均衡的算法会尽量避免这种不均衡，但是基于两个主要原因，这个算法并不能完美的工作：一个是尽量减少Tablet的移动导致重新负载均衡能力受限（如果 Tablet被移动了，那么在短时间内 — 一般是1秒内 — 这个Tablet是不可用的），另一个是我们的基准测试程序产生的负载会有波动。 随机读基准测试的测试结果显示，随机读的性能随Tablet服务器数量增加的提升幅度最小（整体吞吐量只提升了100倍，而服务器的数量却增加了500倍）。这是因为每个1000-byte的读操作都会导致一个 64KB大的Block在网络上传输。这样的网络传输量消耗了我们网络中各种共享的1GB的链路，结果导致随着我们增加服务器的数量，每台服务器上的吞吐量急剧下降。

九、实际应用

1.Google Analytics

Google Analytics是用来帮助Web站点的管理员分析他们网站的流量模式的服务。它提供了整体状况的统 计数据，比如每天的独立访问的用户数量、每天每个URL的浏览次数；它还提供了用户使用网站的行为报告，比如根据用户之前访问的某些页面，统计出几成的用户购买了商品。 Web站点的管理员只需要在他们的Web页面中嵌入一小段JavaScript脚本就可以使用这个服务了。 这个Javascript程序在页面被访问的时候调用。它记录了各种Google Analytics需要使用的信息，比如用户的标识、获取的网页的相关信息。Google Analytics汇总这些数据，之后提供给Web站点的管理员。

2.Google Earth

Google通过一组服务为用户提供了高分辨率的地球表面卫星图像，访问的方式可以使通过基于Web的 Google Maps访问接口，也可以通过Google Earth定制的客户端软件访问。这些软件产品允许用户浏览地球表面的图像：用户可以在不同的分辨率下平移、查看和注释这些卫星图像。

这个系统使用一个表存储预处理数据，使用另外一组表存储用户数据。 数据预处理流水线使用一个表存储原始图像。在预处理过程中，图像被清除，图像数据合并到最终的服务数据中。这个表包含了大约70TB的数据，所以需要从磁盘读取数据。图像已经被高效压缩过了，因此存储 在Bigtable后不需要再压缩了。

Imagery表的每一行都代表了一个单独的地理区域。行都有名称，以确保毗邻的区域存储在了一起。 Imagery表中有一个列族用来记录每个区域的数据源。这个列族包含了大量的列：基本上市每个列对应一个原始图片的数据。由于每个地理区域都是由很少的几张图片构成的，因此这个列族是非常稀疏的。

数据预处理流水线高度依赖运行在Bigtable上的MapReduce任务传输数据。在运行某些MapReduce任务的时候，整个系统中每台Tablet服务器的数据处理速度是1MB/s。 这个服务系统使用一个表来索引GFS中的数据。这个表相对较小（大约是500GB），但是这个表必须在保证较低的响应延时的前提下，针对每个数据中心，每秒处理几万个查询请求。 因此，这个表必须在上百个 Tablet服务器上存储数据，并且使用in-memory的列族。

3.个性化查询

个性化查询是一个双向服务；这个服务记录用户的查询和点击，涉及到各种Google的服务，比如Web查询、图像和新闻。用户可以浏览他们查询的历史，重复他们之前的查询和点击；用户也可以定制基于Google历史使用习惯模式的个性化查询结果。

个性化查询使用Bigtable存储每个用户的数据。每个用户都有一个唯一的用户id，每个用户id和一个列名绑定。一个单独的列族被用来存储各种类型的行为（比如，有个列族可能是用来存储所有的Web查询的）。每个数据项都被用作Bigtable的时间戳，记录了相应的用户行为发生的时间。个性化查询使用以 Bigtable为存储的MapReduce任务生成用户的数据图表。这些用户数据图表用来个性化当前的查询结果。

个性化查询的数据会复制到几个Bigtable的集群上，这样就增强了数据可用性，同时减少了由客户端和 Bigtable集群间的“距离”造成的延时。个性化查询的开发团队最初建立了一个基于Bigtable的、“客户侧” 的复制机制为所有的复制节点提供一致性保障。现在的系统则使用了内建的复制子系统。

十、经验教训

1.很多类型的错误都会导致大型分布式系统受损，这些错误不仅仅是通常的网络中断、或者很多分布式协议中设想的fail-stop类型的错误（fail-stop failture，指一旦系统fail就 stop，不输出任何数据；fail-fast failture，指fail不马上stop，在短时间内return错误信息，然后再stop）。比如，我们遇到过下面这些类型的错误导致的问题：内存数据损坏、网络中断、时钟偏差、机器挂起、扩展的和非对称的网络分区。

2.在彻底了解一个新特性会被如何使用之后，再决定是否添加这个新特性是非常重要的。

3.系统级的监控对Bigtable非常重要（比如，监控Bigtable自身以及使用Bigtable的客户程序）。

4.简单设计的价值。