Bigtable：面向结构化数据的分布式存储系统

概要

Bigtable是一个面向管理结构化数据的分布式存储系统，它是被设计为非常大的尺寸：TB的数据在上千个通用服务器。许多项目在Google上将数据存到Bigtable中包括了网站索引，谷歌地图和谷歌财经。这些应用对Bigtable提出了许多不同的要求，包括在数据大小（从URL到网站页面到卫星图像）与延迟要求（从后端批量处理到实时数据服务）。尽管他们有不同的需求，Bigtable很成功的提供了弹性， 高性能解决方案给所有的这些谷歌项目。在这个论文中我们描述Bigtable提供的简单数据模型，它使客户端能够动态控制数据布局和格式，并且我们描述Bigtable的设计和实现。

1介绍

在过去的俩年半里我们设计实现和开发了分布式存储系统以管理结构化的数据，在谷歌我们叫做Bigtable。Bigtable在谷歌被设计为可靠的的扩展到PB级别的数据和上千台的机器。Bigtable已经达到了几个目标：广泛的应用范围，可扩展性，高性能和高可用性。Bigtable被用在超过60个谷歌的产品和项目上，包括了规格分析，谷歌财经，Orkut，个性化搜索，Writely和规格地球。这些项目使用Bigtable以应对需求多变的工作负载。其范围从吞吐量为导向的批处理工作，到最终用户提供提供延迟敏感的数据服务。在许多方面，Bigtable类似于数据库：他们共享许多数据库的存储策略。并行的数据库和内存数据库已经达到了高可用，但是Bigtable提供了与这些系统不同的接口。Bigtable不支持完整的关系模型；相反，它给客户端提供了简单的数据模型，它支持动态控制数据布局和格式，允许客户端推断底层存储中表示的数据的局部属性。数据索引使用可以为仍以字符串的行名和列名。Bigtable还将数据视作未解释的字符串，尽管客户端经常将各种结构化和半结构化的数据序列化到这些字符串中。通过仔细的选择模式，客户端可以控制数据的位置。最后Bigtable的模式参数让客户端动态控制无论是在磁盘还是内存提供数据。章节2更详细的描述了数据模型，章节3提供了客户端API的总览。章节4描述了谷歌文件系统底层的结构。章节5描述了Bigtable实现的基本原理，章节6描述了一些让我们Bigtable性能提升的改进。章7提供了Bigtable的性能指标。在章节8中我们描述了几个不同的Bigtable在Google中使用的例子。在章节9讨论我们设计和支持Bigtable时学习到的一些经验。最后，章节10描述了相关工作，章节11提出了我们的结论。Bigtable是一个稀疏的，分布式的、持久的多维排序图。这个图通过行和列的key，时间戳进行索引；图中的每个值都是一个为解释的字节数组（行：string，列：string，time：int64）-->string

2数据模型

我们在检验了多重潜在的使用类似Bigtable的系统，选择了这个数据模型。作为一个确实的例子，它驱动了我们的一些设计决策，假设我们需要保证网页上大量数据和相关数据集的拷贝，这可能被用于许多不同的项目；让我们把这些的表叫做Webtable。在Webtable中，我们可能使用url作为行的键，网页的不同方面作为列名，在内容中存储web页面的内容：在获取的时间戳下面有一列，如图1所示。

图1：一个示例表的切片，它存储了web页面。它的行名是倒过来的url。content列族包含了页面内容，锚列族包含了引用该列的任何锚文本。《体育画报》和MY-look主页都引用了CNN的主页，因此，该行包含名为anchor:cnnsi.com和anchor:my.look.ca的列。每个锚单元格都有一个版本；内容列有3个版本，时间戳为t3、t5和t6。

在bigtable中表的组成分为

行

行

列key在表中是一个随机字符串（目前最大可达64KB，尽管10-100字节是我们大部分用户的典型大小），每一个对于单行的读和写操作都是原子的（无论在行中读取或写入的不同列的数量如何），在对同一个记录进行更新时，使客户端更容易推断系统行为的设计决策。Bigtable按字典顺序维护数据。表的行范围是动态分区的。每个行的范围被叫做tablet，它是一个分布和负载均衡的单元格。因此，读取短行的范围通常是高效的，通常只修要与几个小数量的机器进行交流。客户端可以通过查询这些行的key来利用这个特性，这样他们就能得更号的数据访问的局部性。例如在Webtable中，通过翻转url的主机名组件将同一域中的页面分组到连续的行中。举个例子，我们将maps.google.com/index.html数据存储到键com.google.maps/index.html下面。将来自同一域的页面存储在彼此相邻的位置，让一些主机和域分析更加有效。

列族

列键被分组为集合，称为列族它是访问控制的基本单元格。所有的数据被存储在列族中，他们通常是一个类型（我们将同一列族的数据压缩）。在数据可以被存储在列族的任何列键下之前，列族组必须被创建；在列族被创建之后，任何列族中的键都可以使用。我们希望表中不同列族的数量劲量少，并且列族很少在操作途中修改。作为对比，一个表可以有无限多的列。

一个列键使用以下语法命名：family:qualifier。列族名必须是可打印的，但是限定名可以是任意字符串。Webtable的一个列族是 language，它存储了编写网页采用的语言。我们在语言族中只使用一个列键，并且它存储了每个网页的语言ID。这个表另一个有用的列族是anchor；在这个家族中的每个列键代表一个锚，如图1所示。推荐语是引用网站的名称；单元格内容是连接文本。

访问控制和磁盘内存统计在列族级别执行。在我们的Webtable例子中，这些控制允许我们管理几个不同类型的应用：其中一些添加新的基础数据，其中一些读取基本数据并创建派生列族，还有一些只允许查看现有数据（处于隐私原因甚至不会查看所有的族）

时间戳

每个在Bigtable中的单元格可以包含多个版本；这个版本是根据时间索引的。Bigtable的时间戳是64位的整数。它可以通过Bigtable进行指定，在这个例子中它代表以微妙为单位的实时，或者通过客户端应用进行清晰的指派。为了避免冲突，应用自生必须生成独一无二的时间戳。一个单元格的不同版本是按照时间戳降序的，所以大部分最近的版本可以被第一个读取到。

为了让数据的管理更加简单，我们支持俩个列族的设置，告诉Bigtable自动对单元格版本进行垃圾收集。客户端可以指定只有最后的单元格n个版本被持有，或者只有一个足够新的版本被保留（即保留最后7天的值）

在我们的Webtable例子中，我们设置存储内容在抓取页面的时间戳。列中显式了这些页面版本实际被抓取的时间。上面描述的垃圾收集机制允许我们只保留每个页面的最近三个版本。

3 API

Bigtable API提供了函数以创建和删除表以及列族。它也提供了函数以改变集群，表和列族元数据，例如访问控制权限。

// 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

客户端应用可以写入或者删除Bigtable中的值。从各自的行中查找值，或者迭代表中的数据子集。图2展示了C++代码使用RowMutation抽象来执行一系列的更新（不相关的细节被取消了以保证例子的简短）。调用Apply对Webtable执行原子性改变：它添加一个锚到www.cmm.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展示了C++代码，使用scanner抽象在特定的行中迭代所有的锚。客户端可以迭代多个列族，客户机可以遍历多个列族，并且有几种机制可以限制扫描产生的行、列和时间戳。例如，我们可以将上面的扫描限制为只生成其列与正则表达式anchor:*.cnn.com匹配的锚，或者只生产那些时间戳在当前十点之前的锚。

Bigtable支持几个其他的特性，这允许用户以更复杂的方式随意操作数据。受限GFS支持单行的处理，它可以被用作在单行键下的数据存储执行原子读-修改-写序列。Bigtable目前不支持跨行键的事务，虽然它提供了客户端在不同行键之间批量写的接口。第二，Bigtable允许单元格用作证书计数。最后，Bigtable支持在服务的地址空间中执行客户端提供的脚本。这个脚本是通过谷歌开发的用于加工数据的语言Sawzall写的。 现在基于Sawzall的API不允许客户端脚本写回Bigtable。但是它的确允许各种形式的数据转换，基于任意表达的过滤，并通过各种运算进行总结。

Bigtable可以和MapReduce一起使用，一个由谷歌开发被用于运行大规模并行计算的框架。我们已经写了一套包装，它允许Bigtable作为MapReduce的输入数据源，也可以作为输出目标。

4构建模块

Bigtable是构建在几个谷歌其他基础设施上的。Bigtable使用了分布式的谷歌文件系统来存储日志和数据文件。Bigtable集群通常在共享的机器池进行操作，机器池广泛运行着各种分布式应用程序，Bigtable进程通常和其他的应用进程共享同一个机器。Bigtable依赖于集群管理系统进行任务的调度，管理共享机器的资源，处理机器故障和监控机器状态。

SSTable（Sorted String Table）是一种用于存储已排序数据的文件格式，它被多种数据库系统所采用，包括但不限于Google的Bigtable、Apache Cassandra 和 Apache HBase。

Google SSTable文件格式在内部使用并存储Bigtable的数据。SSTable提供了持久化有序不可变的从key到value的映射，其中的键和值都是任意字节的字符串。提供操作以查找与指定的键相关的值，并且迭代所有规定范围内的键值对。在内部每个SSTable包含一个块序列（通常每个块是64KB，不过这是可配置的）。块索引（存储在SSTable的结尾）被用来确定块。当SSTable被打开时，index索引被装载到内存中。查找可以通过简单的磁盘检索来执行：我们首先在内存索引中执行二分查找来找到合适的块，然后从磁盘中读取合适的块。可选的，SSTable可以完全映射到内存中，它允许我们进行查找和扫描而不需要接触磁盘。

Bigtable以来高可用和叫做Chubby的持久分布式锁服务。Chubby服务包含了五个活动副本，其中一个被选为主副本并主动处理请求。当主要的副本正在运行并且能和其他的副本交流时，服务器就是存活的。Chubby使用了Paxos算法以保持它副本面对失败时保持一致。Chubby提供了命名空间，它包含了由目录和小文件组成的命名空间。每个目录或者文件可以使用一个锁，并原子性的读写文件。Chubby的客户端库提供了Chubby文件的一致的缓存。每个客户端维护维护一个与Chubby服务的会话。如果在租约到期的时间之间不能重新租约，那么客户端的会话将会到期。当客户端会话到期，它丢失了任何锁并打开句柄。Chubby客户端还可以在Chubby文件和目录上注册回调，以通知更改或会话到期。

Bigtable使用Chubby来进行多种任务：以保证它在任何时间只有一个活动的主；来存储Bigtable数据的引导位置（见章节5.1）；来发现tablet服务并判决tablet服务的死亡（见5.2章）;来存储Bigtable的模式信息（每个表的列族信息）；存储访问控制列表。如果Chubby变得在很长一段时间不可用，Bigtable将会变得不可用。我们最近在跨越11个Chubby实例的14个Bigtable集群中测量了这个效果。由于Chubby不可用(由Chubby中断或网络问题引起)而导致Bigtable中存储的某些数据不可用的Bigtable服务器小时数的平均百分比为0.0047%。单个集群被Chubby的不可用最多的影响在0.0326%。

5实现

Bigtable实现了三个主要的组件：连接到所有客户端的库，一个主服务和几个Tablet服务。Tablet可以从集群中动态添加（或者删除）以适应工作负载的变化。主负责指派tablet到tablet服务上，探测添加的和到期的tablet服务，均衡tablet服务的负载，并在GFS中进行垃圾收集。此外，它还处理模式更改，例如表和列族的创建。

每个tablet服务管理一组tablet（通常，我们每台tablet电脑服务器上有10到1000个tablet）。tablet服务处理读和写请求到已加载的tablet中，同时还拆分规模过大的tablet。就像单个主的分布式存储系统，客户端数据不通过主进行移动。客户端直接和其他tablet服务进行交流来和写。因为Bigtable的客户端不依赖于主来获取tablet的位置信息，大部分客户端从不与主交流。所以，主实际上只有很轻的负载。

一个Bigtable集群存储许多表。每个表由tablet集构成，每个tablet包含了行范围相关的所有数据。最初每个表只有一个tablet。随着tablet的增长，它被自动切分乘多个tablet，默认大小为每个接近100-200MB。

5.1 tablet位置

我们使用我们使用三层级的类似B+树来存储tablet的地址信息。如图4

图4：tablet的位置层级

第一个级别是一个存储在Chubby中的文件，根节点在一个特殊的元数据表中包含所有tablet位置。每个元数据表包含了一组用户表的信息。根tablet表只是在元数据表中的第一个，但是收到特殊对待—它从不切分—以确保tablet位置层级没有更多的树形层级。

元数据表将tablet的位置存储在行键下，行键是编码了tablet表的标识符和节数行。每个元数据行存储了接近1KB的数据在内存中。元数据tablet的限制是128MB的元数据，我们三层的地址模式足够处理$2^{32}$个tablet（或者在128MB的tablet中$2^{61}$字节）

客户端库缓存了tablet的位置。如果客户端不知道tablet的地址，或者如果它们发现缓存的地址信息是错误的，那么递归向上移动tablet地址层级。如果客户端缓存为空，地址算法需要三次网络往返，包括了一次从Chubby中读取。如果客户端缓存已经失效，客户端算法可能需要进行六次往返，因为过期的缓存只有在命中时才被发现（假设元数据tablets不会移动的非常频繁）。虽然tablet的位置存储在内存中，因此不需要GFS访问，在一般情况下，我们通过让客户端预读取tablet位置来进一步降低成本：当它读取元数据表时，它读取多个tablet的元数据。

我们也存储元数据表中次要的信息，包括了每个tablet的所有信息（例如当服务开始提供时）。这个信息有助于debug和性能分析。

5.2tablet指派

每个tablet一次指派给一个tablet服务在一个时间。主保持一组存活的tablet服务块以及分配给当前tablet服务的tablet吗，包括未分配的tablet。当tablet未被指派，并且tablet服务有足够大的空间可供tablet活动，主通过发送tablet负载请求到tablet以指派tablet。

Bigtable使用Chubby以保持跟踪块服务。当tablet服务启动，它会在特定的Chubby目录中创建并获取一个唯一命名的文件的独占锁。主监视了这个目录（服务器目录）以发现tablet服务。如果它失去了独占锁，tablet服务停止为其提供服务：即由于网络分区导致了服务丢失其Chubby的会话。（Chubby提供了有效的机制来允许tablet服务检查它是否仍然持有锁，而不增加网络流量）。tablet服务企图再次得到文件的独占锁，只要文件仍然存在。如果该文件不再存在，那么tablet服务器将永远无法再次提供服务，因为它会自杀。当tablet服务停止时（即因为集群管理系统从及群众移出了tablet服务机器），它企图替换它的锁，以便主能够更快的重新分配tablet。

主会检测合适tablet服务不再提供tablet，并且尽快的重新分配这些表。为了检测什么时候tablet服务不在服务它的tablet，主定时的询问每个tablet服务他们锁的状态。如果tablet服务上报它丢失了锁，或者如果主在最后几次尝试时不能访问服务，主会尝试持有服务文件上的独占锁。如果主能够获取到主，那么Chubby还活着，并且tablet服务服务还活着，那么tablet服务要么死了要么无妨访问Chubby，所以主通过删除这个服务文件确保tablet服务再也不能活动。一旦服务文件被删除，主可以将之前分配到那个服务的起的所有tablet移动到未分配的tablet中。为确保Bigtable集群不容易受到在主和Chubby之间网络问题的影响，如果Chubby的会话到期，主杀死自己。然而，如上所述，主的故障不会改变tablet的被分配到tablet服务上。

当主被集群管理系统启动时，它需要在它能够修改他们之前发现当前的tablet指派。主在启动时执行以下步骤。

1. 主获在Chubby中取唯一的锁，它防止了主的并发实例化。
2. 主扫描Chubby中的服务目录以查找存活的服务。
3. 主链接其他的存活的tablet服务以发现哪些tablet已经被指派了
4. master扫描元数据tablet以了解这组tablet。无论这次扫描是否遇到了还没有被分配的tablet，主添加tablet到一组未被指派的表中。这使得tablet有资格获得tablet的指派。

一个复杂的问题是在元数据tablet在被指派之前，元数据表的扫描无法进行。因此在在启动这个扫描之前（步骤4），如果在步骤3中没有发现根tablet的指派，主添加跟tablet到一组未指派的tablet。这一层架保证了主根tablet将会被指派。因为主tablet包括了所有元数据tablet的名字，在扫描根tablet之后主知道他们所有人。

一组已存在的tablet只有表被创建或者删除时才能被改变，或者现有的tablet被分为俩个tablet。主能够保持这些改变的块，因为除了最后一个其他都是启动的。tablet的切分是特殊处理的，因为它通过tablet服务初始化。tablet服务通过记录在元数据表中心的tablet的信息来提交切分。当切分被提交它通知主。如果被切分的通知丢失了（无论是因为tablet服务还是主的死亡），当它告诉tablet服务去加载现在被切分的tablet时，主会探测到新的tablet。tablet服务将通知主的分裂，因为它在元数据表中找到的tablet条目将只指定主机要求它加载的一部分。

5.3tablet服务

tablet的持久状态被存储在gfs 中，如图5所示，更新被提交重做记录的提交日志中。在这些更新中，最近的一次更新被存储在内存的缓冲区中被称为memtable；更老的更新被存储在SSTable序列中。为了回复tablet，tablet服务读取元数据表中的元数据。此元数据包含包含tablet和一组重做点的sstable列表，重做点是指向可能包含tablet数据的任何提交日志的指针。服务读取SSTable的索引到内存中，并且通过应用所有的自重做点以来的更新重建memtable。

到写入操作到达tablet服务，服务检查它的格式是否完好，并且发送方被授权进行修改。授权是通过读取来自Chubby的文件的允许写入者列表进行的。一个有效的改变被写入到了提交日志中。分组提交用来增强大量的小型修改的吞吐量。在写操作提交之后，它的内容被插入到memtable中。

当读取操作到达tablet服务端，它简单的检查和实现和适当的权限。在SSTable序列和memtable的合并试图上执行有效的读操作。因为SSTable和memtable是按字典序顺序排序的数据结构，合并后的试图可以有效的形成。

当tablet被拆分的时候到来的读和写操作是可以连续的。

5.4压缩

在执行写操作时，memtable的大小增大。当memtable大小到达预制，memtable被冻结，一个新的memtable被创建，冻结的memtable被转换成SSTable并写入GFS。这个小的压缩操作有俩个目标：它收缩了tablet服务内存的使用，并且它减少了那些在恢复期间必须要进行读取的数据量（如果服务器死亡）。进来的读和写操作可以压缩操作同时发生。

每次小的压缩都会创建一个新的SSTable。如果这个行为继续不受控制，读操作可能需要合并大量的来自任意SSTable数量的修改。相反，我们通过在后端定期执行合并压缩，限制了这类文件的数量。合并压缩读取几个SSTable和memtable的内容，并写一个新的SSTable。一旦压缩完成，输入的sstable和memtable就会被丢弃。

将所有所有SSTable重写为一个SSTable的合并压缩被叫做主压缩（major compaction.）。通过非压缩产生的SSTable可能包含特殊的删除项，它阻止了旧的SSTable中存在的已删除数据。另一方面，一个主要的压缩，生成一个不包含输出数据的SSTable。Bigtable在所有的tablet上循环运行，并且定期对他们进行主要压缩。这些主要的压缩允许Bigtable去回收删除数据所使用的资源，并且也允许它确保删除数据在系统中即使的消失，它对于存储敏感的数据是非常重要的。

6精炼

前一章中描述的实现必须要许多的改进才能实现高性能，可用性和用户要求的可靠性。为了突出这部分改进，这一章更细节的描述的实现部分。

局部性组

客户端可以分组多个列族到局部性组。为每一个tablet的每个位置生成一个单独的SSTable。将不一起访问的列族分开到局部性组中可以提高读取效率。例如，page的元数据在WebTable中（例如语言和校验和）可以在一个局部性组，页的内容可以在不同的组中：需要读取元数据而不需要读通过所有的页内容的应用。

此外，可以在每个位置组的基础上指定一些有用的调优参数。例如局部性组可以被声明为在内存中。内存中局部性组的SStable是懒加载到tablet服务的内存中的。一旦接受负载，列族列族根据这些局部性组可以直接读取而不需要访问磁盘。这个特性被用在访问频繁的小的数据片段上：我们在内部使用它以让局部性列族在元数据tablet中。

压缩

客户端可以控制局部性组的SStable是否压缩，如果是，使用哪种压缩格式。用户指定了用户指定了每一个SStable block所使用的压缩格式（这个大小可以通过局部性组明确的调优参数进行控制）。虽然我们通过压缩损失了一些空间，我们收益于SStable的一小部分可以在不解压整个文件的情况下实现读取。许多客户端使用双通道自定义压缩。第一次使用了Bentley 和McIlroy的模式，在大的窗口中压缩长而且普通的字符串。第二次使用了快速压缩算法在16KB大小的窗口中查找重复数据。俩个压缩步骤都非常快速它们编码100-200MB/s，解码在400-1000Mb/s在现代的机器上。

即使我们在选择压缩算法的时候强调的是时间而不是空间，这俩个压缩方案都非常好。举个例子，在Webtable中，我们使用压缩模式存储Web页的内容。在一个实验中，我们将大量问的那个存储在压缩的局部性组中。为了实验目的，我们限制每个文档为一个版本，而不是存储所有可用的版本。该方案实现了10比1的空间缩减。这相比于常见的Gzip在html页面压缩3比1或者4比1要好的多：来自单个主机的所有页面都彼此靠近地存储。它通过Bentley-McIlroy压缩算法识别来自同一主机页面中的共享的大量共享样板文件。许多应用，不止是Webtable，选择他们的行名让相似的数据聚集在一起，一次实现非常好的压缩率。当我们存储相同值的多个版本在Bigtable中时，压缩率甚至还会更好。

为了读取性能的缓存

为了增加读性能，Tablet服务使用2级缓存。扫描缓存是高级缓存，它将SSTable接口返回的键值对缓存到tablet服务代码。Block缓存是第几缓存，它缓存了GFS中读取的SSTable block。块缓存是一个较低级的缓存，用于缓存从GFS读取的sstable块。扫描缓存对于倾向于重复读取相同数据的应用程序是最有用的。块缓存对于那些倾向于读取与它们最近读取的数据接近的数据的应用程序(例如，顺序读取，或者随机读取热行中的相同局部性组中的不同的列)是有用的。

布隆过滤器

如5.3描述的，读取操作必须从构成了tablet状态的所有的SSTable中读取。如果SSTable不在内存中，我们最终可能要做许多磁盘访问。我们通过客户端指定局部性组中SSTable创建的的布隆过滤器来减少访问次数。布隆过滤器允许我们询问SStable是否包含指定的行列对的数据。对于特定的应用，小的Tablet服务内存被使用在布隆管理器上，极大的减少了磁盘必须的访问。我们使用布隆过滤器也意味着，大部分对于不存在的行或者列的查找都不需要接触磁盘。

提交日志实现

我们保持每个tablet的操作日志在单独的日志文件中，大量的文件被并发写入了GFS中。根据每个GFS服务器上的底层文件系统实现，这些写入可能会导致大量磁盘寻道写入不同的物理日志文件。此外， 在每个tablet上使用单独的日志文件也会降低分组提交优化的有效性。为了弥补这个问题，我们将改变附加到每个tablet服务的单个提交日志中，在同一物理日志文件中对不同的tablet进行混合改变。

在正常操作期间使用日志可以显著的提升性能。但是这会让恢复变得复杂。当tablet服务器死了，它所服务的tablet服务奖被转移到大量的其他tablet服务上：每个服务通常装在少量的原始服务的tablet。为了恢复tablet的状态，新的tablet需要重演那个被源tablet服务写入的提交日志的改变。然而，这个tablet的改变被混合到了同一个物理机中。一个方法是，每个新的tablet服务读取这个完整的提交日志文件，并且只应用它需要恢复的tablet所需的条目。然而，在这样的模式下，如果100台机器从一个故障的tablet服务器上分配一个tablet，那么日志文件将会被读取100次（每个服务一次）。

我们通过受限按照键的顺序对提交日志进行排序来避免重复读取日志《表，列名，日志序号》。在排序后的输出中，所有特地tablet的改变是连续的，因此可以通过一次磁盘寻道和随后的顺序读来有效的读取。为了并发排序，我们将日志文件分割为64MB一个段，在不同的tablet服务上并行排序每个段。当tablet服务表明需要需要从一些日志文件中恢复改变，排序程序会通过主的协调进行开始。

将提交日志写入GFS有啥好会由于各种原因导致性能中断（比如，涉及写的GFS服务机器崩溃，或者到达特定的三台GFS服务器的网络路径遇到网络拥塞，或者沉重的负载）。为了保护免受来自GFS延迟峰值的影响，每个tablet服务实际上有俩个日志写入线程，一个写入它自己的日志文件；在同一时间，这俩个线程中只有一个处于活动状态。如果活动日志文件的写性能很差，日志文件写入会切换到另一个线程，提交日志队列中的变化由新线程写入。日志条目包含了连续的数字以允许恢复进程省略由日志切换进程产生的重复的条目。

加速tablet康复

如果主将tablet从从一个tablet服务移动到另一个，源tablet服务首先会在这个tablet上进行少量压缩。这个压缩通过减少tablet服务中不紧凑的tablet提交日志的状态，减少了恢复时间。在这个压缩结束后tablet停止位这个tablet提供服务。在真正的卸载tablet之前，tablet服务执行另一个（通常是更快的）以消除在第一次小规模压缩执行期间到达的平板服务器日志中的任何未压缩状态。在第二次小的压缩完毕后，可以加载到另一个tablet服务器上，而不需要任何日志条目的恢复。

利用不变性

除了SSTable缓存，Bigtable系统的其他部分通过所有的SSTable我们生成之后就不会变动这个事实进行简化。例如我们不需要任何对文件系统的在读取时SSTable的访问进行同步。所以可以有效的进行并发控制。唯一一个可变的数据结构并且能够通过渡河写访问的是memtable。为了减少在读取memtable时的冲突，我们让每个memtable行写时拷贝（copy-on-write）并且允许读和写同时进行。

因为SSTable是不可变的，所以永久删除数据被转换成了垃圾收集废弃掉的SSTable。每个tablet的SSTable都注册在元数据表中。主删除淘汰的SSTable就如同在SSTAble集合上进行标记清除垃圾收集算法，其中元数据表包括了跟集合。

最终SSTable的不变性是我们更快速的分离tablet。而不是给每个子tablet生成新的SStable集合，我们让子tablet共享父tablet的SSTable

性能评估

下面的性能评估和使用场景b话有点多懒得翻译了