BigTable论文阅读&个人翻译

Bigtable是2005年谷歌的论文：《Bigtable: A Distributed Storage System for Structured Data》中介绍的一种分布式存储系统，后来被Hadoop社区实现为HBase。读懂这篇论文，那么理解HBase也就非常容易了。本篇博客略去了性能评估、API和应用实例的部分，只讲比较关键的设计与机制部分。

这篇论文在不少的地方已经有人翻译了，我为什么还要再翻译一遍嘞？一是这些都是别人翻译的，可能会有些疏漏(比如这篇厦大数据库实验室的翻译，我在看论文看不懂的时候就会去找它来对照理解，但是对照英文版本就会发现有些地方的翻译是有问题的)，还是看英文原版比较准确地理解意思。另一方面，能够把论文翻译出来，也就说明比较清楚地了解论文的意思了，这也算是一种检验。

Abstract

Bigtable是一个分布式存储系统，它被设计来为近万台商用服务器规模的、PB级别的数据提供服务。包括网页索引、Google Earth、Google Finance( 注:这些应用都是2005年论文发表的时候列举的，现在Google貌似已经抛弃Bigtable使用下一代产品了 )在内的许多Google项目都使用Bigtable来存储数据。这些应用在数据粒度和实时性方面的要求都大相径庭，但Bigtable却能很好地为这些应用提供灵活、高性能的解决方案。在这篇论文中我们讨论Bigtable提供的 简单数据模型 ，这个模型让用户能够动态地控制数据布局和格式。接着我们介绍Bigtable的设计和实现。

Introduction

在过去两年半，我们设计、实现和部署了一个管理结构化数据的分布式存储系统，称之为Bigtable。Bigtable的设计目标是在PB级数据和数千台服务器的条件下可靠工作。Bigtable完成了多个目标：广阔的适用范围、高扩展性、高性能、高可用性。Google Analysis、Google Finance、Orkut、Personalized Search、 Writely、和Google Earth都使用了Bigtable，他们的需求可谓千差万别，从高吞吐量到批处理任务再到低延迟的数据服务。这些服务的Bigtable Cluster配置环境也不尽相同，服务器数量从数个到数千个的都有，存储量也达到数百个TB。

从很多意义上来说，Bigtable构造了一个数据库。它借鉴了很多数据库设计的策略。并行数据库和内存数据库达到了可扩展性和高性能，但是Bigtable提供了一种和这些系统不同的接口。Bigtable不支持完整的关系型数据模型。它提供 简单数据模型 ，这个模型可以支持动态控制数据布局和格式，并允许用户推测底层存储的数据的位置属性。

Data Model

Bigtable是一个稀疏、分布式、持久化的多维排序map，通过行键、列键和时间戳来索引。map中的每个值都是原始的字节数组（在使用HBase接口时，经常需要对bytes进行转换就是这个原因）。

webtable数据模型

上图是一个webtable的数据模型， com.cnn.www 是row name( 注:之所以写成逆序的url，是为了让相同的网址尽量在物理上存在同一个位置，因为Bigtable的数据是有序排列的 )。 contents 和 anchor 都是列族，而 anchor:cnnsi.com 和 anchor:my.look.ca 分别是 anchor 列族下的两个列。 contents 有三个时间戳，时间戳也是按序排列的，默认按照降序排列，这样的话就可以方便地获得最近的数据。

我们在考察了多种具有和Bigtable相似需求的系统后，选择了这种数据模型。下面是我们为什么选择这种数据模型的例子：假设我们想要保存大量的网页和相关信息的拷贝，这个信息会被很多不同的项目使用到，我们把它命名为Webtable。在Webtable中，我们使用URL作为行键，网页不同类别的信息作为列键，并且把网页内容存入 contents: 列中，就像上图那样以抓取时的timestamp作为版本。

Rows

行键可以任意的字符串(当前最多允许64KB大小，对于大多数用户，10-100字节已经够了)。对于单个行键的读/写操作都是原子的(不管这个行有多少列)，这个设计决策让用户更清楚地知道系统在并行更新时的行为。

Bigtable以字典序对数据进行维护，一个表的行区间是动态划分的，每个行的区间被称为 tablet ，它是数据分发和负载均衡的基本单位。正是由于一个tablet包含很多行，读取很小的一段行区间十分高效，并且通常只会和少数几台机器通信（ 注:读取很小一段行区间意味着很可能只涉及一两个tablet ）。利用这种特性，用户可以选择恰当的行键来让数据读取很好地本地化。比如，在Webtable中，通过使用逆序的URL域来让相同域下的page存储在毗邻的列中。例如，我们将 maps.google.com/index.html 存储在键 com.google.maps/index.html 下，在相同域的数据就会邻近存储，使得域相关的分析更加高效。

Column Families

列键被分组到一个叫做 列族(column family) 的集合中，它构成了访问控制的基本单元。通常存储在同一个列族中的数据都是相同的类型(我们对同一个列族的数据放在一起进行压缩)。数据被存储在列族中的列里面，所以在列中的数据被存储之前，列族必须先被创建出来。一旦列族创建完成，列族下的任意列都可以被使用( 注：换言之，可以直接将数据存入” family:col1 “而不用关心’ col1 ‘是否被创建过。可以存储在 family 的任意 column 下 )。我们鼓励一个表中的列族尽可能地少(最多数百个)，并且列族应该在使用时很少变更。但是一个表的列数量是没有限制的。

列族的命名使用” family:qualifier “这样的格式。列族名必须是可打印字符，但是qualifier可以使任意字符。Webtable的一个列族例子就是language，它存储了一个页面使用的语言。我们在language列族中只使用一个列键，它存储了每个网页的language ID。Webtable另一个有用的列族是anchor，anchor下的每个列键都代表了一个anchor。它的qualifier是引用的站点，它的内容是链接的文本信息。

访问控制和磁盘/内存计算都在列族层面上进行。在Webtable这个例子中，这些控制让我们可以管理多种不同类型的应用：有的应用负责增加新的基本数据，另一些只能查看现存的数据(甚至只能看到一部分列族的数据)。

Timestamps

Bigtable的每个单元都可以保存同一个数据的多个版本，这些版本以timestamp索引。Bigtable的timestamp是64位的整数。当它们被Bigtable赋值时，它们代表以微秒计算的“当前时间”。同时它们也可以被用户程序赋值。应用程序需要自己保证生成唯一的timestamp。不同版本的数据单元以timestamp的降序排列，这样就可以先读到最近版本的数据了。

为了减轻数据版本管理的复杂性，我们有两个列族层面的设置可以让Bigtable自动回收单元的版本。用户可以设定只有最近的n个单元版本可以留下来，也可以设定只有在最近多久之内的单元版本可以保存。

在Webtable这个例子中，我们将保存在” contents:“列的timestamp设置为被爬取的时间，版本回收机制被设置为只保存最近的3个版本的页面。

Building Blocks

Bigtable是构建在其他几个Google基础设施上的。Bigtable使用了分布式Google File System(GFS, 注:Hadoop社区比照其实现了HDFS )来存储日志和数据文件。一个Bigtable Cluster通常在一个共享的机器池中运行，这个共享的机器池会运行很多其他的分布式应用，Bigtable通常和其他应用的进程共享一个机器。Bigtable依赖cluster管理系统来调度任务，管理共享及其上的资源，处理机器失败情况，监控机器的状态。

Google SSTable文件类型是存储Bigtable数据的内部格式，一个SSTable提供持久化、有序的、不变的键值映射，其中键和值都是任意的字节字符串。Bigtable提供了查找与某个键相关的值的操作，也允许对所有的键值对在一个特定的键区间进行遍历。在内部实现中，每个SSTable包含了一系列块(通常块大小为64KB，也可以进行特殊指定)。块索引(存储在SSTable的末尾)用来定位块，当SSTable被打开时，索引就会被读入到内存中。一个查询操作只会涉及一次磁盘扫描:首先通过二分查找法找到合适的块，然后从磁盘中读取相应的块。我们也可以选择将SSTable完全读入内存，这样我们就不需要在查询这个SSTable的数据时进行磁盘操作了。

Bigtable依赖一个高可用、持久化的分布锁服务，名为 Chubby 。一个Chubby服务包括五个活跃的副本，其中一个被选作master并且为request提供服务。当大部分副本是活跃的，并且可以互相通信的时候，这个服务就是存货的。Chubby使用Paxos算法来保证在服务失败时副本的一致性。Chubby提供了一个包含目录和小文件的命名空间，每个目录/文件都可以被用作一个锁，对于它们的读/写都是原子的。Chubby客户端函数库提供了针对Chubby文件的持久性缓存。每个Chubby客户端都维持一个和Chubby服务的缓存，如果它无法在到期之前更新session，那么session就过期了，这时客户端就丢失了所有的锁和打开的句柄( 注:可以理解为已经被打开的文件 )。Chubby客户端也可以在Chubby文件和目录上注册回调函数来通知session过期或者其他的变化。

Bigtable使用Chubby来完成多种任务:

保证同时最多只有一个活跃的master;
保存Bigtable的bootstrap位置( 注:见下节 );
发现tablet服务器,确定tablet服务器是否死亡;
保存Bigtable的概要信息(每个表的列族信息);
存储访问控制表。

如果Chubby不可用了一段时间，那么Bigtable也会变得不可用。我们最近对保护焊11个Chubby实例的14个Bigtable Cluster进行测试，发现由于Chubby不可用(由Chubby中断或网络问题导致)导致Bigtable数据不可用占到总共服务时间的0.0047%，导致单个cluster不可用占到总服务时间的0.0326%。

Implementaion

Tablet Location

使用三层结构的B+树来保存tablet位置信息

Tablet定位层次

第一层是在Chubby中存储的一个文件，保存有root tablet的位置信息。root tablet保存在METADATA表中所有tablet的位置信息，它自己本身也是METADATA表中的一个tablet，但是为了保证tablet location hierarchy不超过三层，它不会分裂成两个tablet。

METADATA表存储了某个行键下tablet的位置，行键是表标识和最后一行的编码。每个METADATA行在内存中大约占用1KB，在128MB的METADATA tablet限制下，三层位置策略足以表示$2^{34}$个tablet，也就是128MB大小tablet情况下可以存储$2^{21} PB$。

每个METADATA tablet的大小限制是128MB,而每行占用大约1KB，可得一个METADATA tablet可以存储$2^{17}$个tablet位置信息。

作为一个METADATA tablet，root tablet可以存储$2^{17}$个第二层的METADATA tablet位置信息，而每个第二层的METADATA tablet又可以存储$2^{17}$个用户表的tablet位置信息，所以一共可以存储$2^{34}$个用户表的tablet位置信息。

假如每个用户表的tablet大小限制是128MB，那么一共可以表示$2^{61} B$也就是$2^{21}PB$。

客户端缓存tablet位置。如果客户端不知道tablet的位置信息或者它发现缓存的位置信息已经不对，那么它就会在tablet Hierarchy中递归向上寻找。如果客户端缓存不存在，那么定位算法需要三次通信，包括从Chubby读取一次数据。如果客户端缓存过期了，那么定位算法最多可能会进行六次通信，因为只有在访问无效的时候才会发现entry过期了。

尽管已经把tablet位置信息存储在内存中来避免对GFS进行请求，我们更进一步减少开销：每次读取METADATA表都请求不止一个tablet位置信息。

我们也在METADATA表中存储了二级信息，包括一个日志，它记载了和每个tablet有关的所有事件（比如什么时候服务器开始对其提供服务），这些信息对于性能分析和程序调试非常有用。

Tablet Assignment

每个tablet一次会被指派到一个tablet server，master监控一组存活的tablet server 和当前tablet的分配情况，包括已分配的和未分配的。当一个tablet是未分配的，而一个tablet server又有充足的空间可以使用，那master就会发送一个tablet load请求给tablet server，由此tablet server管理这个tablet。

Bigtable使用Chubby来监控tablet server。当一个tablet server启动的时候，它会在Chubby的一个目录上创建并获得一个排它锁。 master通过监控目录来发现tablet server。当tablet server丢失了这个排它锁(比如网络问题导致server丢失了Chubby的session)，它就不再管理它的tablets了。只要文件还在，tablet server会尝试重新获得一个排它锁，反之，它就会终止自己的进程。当tablet server终止的时候，它会尝试释放自己的排它锁，这样的话master可以更快地重新分配它管理的tablets。

master负责尽快重新分配终止的tablet server所管理的tablet。为了侦测到不再提供服务的tablet server，master会周期性地要求tablet server报告自己的锁状态。如果tablet server报告自己丢失了锁或多次没有应答，那么master会尝试获得tablet server文件上的排它锁。如果得到了锁，那么Chubby是存活的，且tablet server不是死亡了就是无法与Chubby进行通信，所以master认定tablet server无法再提供服务，会删除掉它的tablet server文件。一旦文件被删除，master就会把那个server管理的文件放入“未分配tablet”集合中。为了避免master和Chubby之间的网络问题让Bigtable服务变得脆弱，master会在它的Chubby session到期的时候终止自己。master进程出现异常不会改变tablet到tablet server的分配。

当一个master被cluster管理系统启动的时候，它需要先知道现存的tablet分配情况，然后才能管理和修改它们。当master启动的时候，它会进行以下的活动：

master在Chubby中获得一个唯一的master锁，这才能保证一次只有一个master在管理
master扫描Chubby的server directory来发现正在服务的tablet server
master和每一个存活的server进行通信，得到每个server管理的tablet情况
master扫描METADATA表，得到tablet集合。当发现METADATA表中的tablet没有被分配，就把它归入“未分配tablet”集合中，

只有在METADATA表已经被分配的时候才能遍历它。如果master在第3步中没有发现root tablet被某个tablet server管理，就说明METADATA表还没有被分配，这样的话master会在第四步把root tablet添加到“未分配tablet”集合中。在root tablet被分配之后，master就可以通过root tablet获得整个METADATA表。

“已存在tablet”集合只会在以下的情况下会被改变：

创建/删除表
两个存在的tablet被合并成一个大tablet
一个tablet被分裂成两个小的tablet

master发起了创建/删除表和合并tablet的操作，所以master本来就能追踪这些操作。而tablet分裂是由tablet server发起的，tablet server会通过将新tablet记录到METADATA来分裂tablet，当分裂完成的时候，它会通知master。如果通知丢失了，在master要求tablet server加载已经分裂的tablet时，tablet server会发现在METADATA表中的tablet条目只构成master要求加载的tablet的一部分(master要求加载的tablet还是未分裂时的状态，所以会比分裂后的tablet大)，这时tablet server会再次把tablet的分裂消息通知给master。至此，master完成了对上述三种修改tablet集合操作的追踪。

Tablet Serving

Tablet的持久化状态存储在GFS里面，如下图所示：

TabletRepresentation

所有的更新操作都会提交给一个commit log，最近提交的一些操作还会被缓存在内存中，这个缓存叫做 memtable ，而比较老的修改则会被保存在一系列的SSTable中。当需要恢复一个tablet的时候，tablet server就会从METADATA表中读取元数据，这个元数据包括一个SSTable列表，列表由一个tablet和一组redo point组成，redo point是指向所有可能包含此tablet提交日志的指针。server将SSTable的索引读入内存，通过执行redo point之后所有的提交日志来恢复数据。

当一个写操作到达tablet server之后，server会首先检查它的格式，然后检查提交者是否在Chubby的写入者列表中。然后将一个有效的修改操作被记录到commit log中。当有大量小文件操作的时候，会使用分组提交来提高吞吐量。当写操作被提交之后，它的内容会被写入memtable。

当一个读操作到达tablet server的时候，他也会被检查格式和读权限，一个有效的读操作是通过合并SSTable和memtable获得的。由于SSTable和memtable是字典排序的，所以合并操作很高效。

当tablet在被分裂/合并的时候，读写操作依然能够继续进行。

Compactions

当进行写操作的时候，memtable会不断增长。当memtable到达一个阈值之后，它会被冻结并创建一个新的memtable。冻结的memtable会被转换成SSTable并写入GFS中。这个过程被称为“次压缩” (minor compaction) ，它由两个目标：减少tablet server的内存占用，并且如果tablet server意外终止了，可以减少恢复数据时需要从commit log中重做的操作。在进行“次压缩”的时候，读写操作依然可以继续进行。

每一次“次压缩”都会生成一个SSTable文件,如果文件数量一直这样增长下去，读操作就需要合并很多SSTable文件，这会导致读操作变得很慢。为了解决这样的问题，我们周期性地在后台进行一次“合并压缩”( merge compaction )。一次合并操作会读取数个SSTable和memtable的内容，当合并压缩完成之后，这些SSTable和memtable的内容就会被丢弃。

一个合并所有SSTable到一个SSTable的操作称为“主压缩”( major compaction )。在BigTable中，删除操作其实只是在某个记录中进行标记，并没有真正释放这个记录的空间。长时间如此会导致SSTable中有大量已删除的记录依然占据空间。主压缩产生的SSTable会删除这些记录并释放空间。Bigtable周期性地检查所有的tablet，并执行主压缩。这样的操作可以收回被已删除数据占用的空间，且可以保证一些敏感数据在一定时间内从系统中彻底消失。

为了获得高性能、可用性和可靠性，我们需要进行一些优化。这章会对一些实现进行更详细的介绍。

Locality groups

用户可以将多个列族分组进同一个“位置组”( locality group )。每个tablet的位置组都会得到一个属于自己的SSTable，将通常分开访问的列族分隔到不同的位置组可以实现更高效的读操作。比如，网页的元数据(包括语言、校验码等)可以被放在一个位置组中，网页的内容则被放入另一个位置组中。这样的话，想要读取页面元数据的应用就不需要再访问网页的所有内容了。

另外，每一个位置组也提供了一些有用的参数。例如，位置组可以被设定为保存在内存中。常驻内存的位置组的SSTable采用lazy load的方式被加载到tablet server的内存中。一旦被加载到内存里，在这个位置组内的列族都可以直接在内存中被访问到。这个功能对于需要频繁访问的小数据非常有用。在内部，这个功能也被METADATA表用来给“location”列族加速。

Compression

用户可以控制某个位置组对应的SSTable是否被压缩/如何压缩。用户指定的压缩格式被应用到每一个SSTable块上。虽然将SSTable分块压缩而不是整体压缩会减弱压缩效果，但是我们可以在读取数据的时候避免解压缩整个SSTable。许多用户使用“两阶段自定义压缩方法”(two-pass custom compression scheme)。第一阶段使用"Bentley and McIlroy"压缩法，将长公共字符串进行压缩。第二阶段使用一种快速压缩算法，在16KB窗口内寻找重复数据。两种压缩都很快，编码速度是100-200MB/s，解码速度是400-1000MB/s。

在实践中，即使我们分段压缩，这种压缩方法的效率仍然非常高。在WebTable实验中，即时只存储一个版本的网页，压缩率依然达到了10:1，比传统的GZip效果要好很多。这样的性能优化和WebTable的存储方式也是密切相关的。来自同一个站点的网页都存储在相近的位置，这就让第一阶段的压缩可以找到大量相似的内容。如果保证相似的数据被存放在同一个cluster中，就可以获得很好地压缩率。当然，存储多个版本的内容时，压缩率还可以进一步提高。

Caching for read performance

为了提高读性能，tablet server使用两层cache。高层次的 Scan Cache 缓存从SSTable接口返回到tablet server的键值对，低层次的 Block Cache 缓存从GFS中读到的SSTable。 Scan Cache 适用于需要重复读取相同数据的应用，而 Block Cache 适用于需要读取邻近数据的应用。

Bloom filters

读操作必须读取构成这个tablet的所有SSTable，而假如有SSTable不在缓存中，就会产生很多的磁盘操作。我们通过允许用户指定为某个位置组的SSTable创建 Bloom filters 来减少磁盘读取。 Bloom filters 提供了查询一个SSTable是否包含某个行/列对的能力。对于特定的应用，少量的tablet server内存空间就能存储 Bloom filters ，可以极大减少磁盘读取次数。使用 Bloom filters 也意味着许多针对不存在的行/列查询不需要经过磁盘访问。

关于Bloom filter，可以参考博文。

Commit-log implementation

如果我们为每个tablet都分配各自的log文件来保存提交日志，那么大量的文件就会被同时写入GFS。在不同的GFS底层文件系统下，这些写操作会导致大量的磁盘寻道和写操作。每个tablet都有一个单独的log文件会导致分组提交时的一个组很小，降低优化效果。

由于以上种种弊端，所以我们选择为整个tablet server设置唯一的提交日志文件。使用唯一的日志文件使得普通操作的性能显著提高，但是却让数据恢复得操作变得更加复杂。当一个tablet server死亡的时候，它管理的tablet会被移到大量其他的tablet server下。为了给tablet恢复状态，新的tablet server需要从原来的日志文件中读取操作记录，为这个tablet重新执行一遍。但是所有tablet的操作都混合在一起。容易想到的解决办法是让每个tablet server都读取整个日志文件，显而易见，这种方式的效率很低下。

我们通过以下的方式避免tablet server读取无用的日志，我们将日志中的条目以<table,row name,log sequence number>的键进行排序。这样，每个table的更新记录都是连续存放的，所以我们可以通过一次磁盘寻道顺序读取某个table的提交记录。为了完成并行的排序，我们把日志文件分割成64MB为单位的碎片，在不同的tablet server上并行地对这些碎片进行排序。master会对排序进行协调，排序过程在一个tablet server请求日志文件来恢复数据时启动。

对日志文件的写操作有时也会导致性能瓶颈，每个tablet server实际上拥有两个日志写入线程，每个线程都会写入自己的log文件。同时只会有一个线程是活跃的，如果当前活跃的日志文件写入缓慢，那么就会切换到另一个线程。在提交日志的队列中的更新就会被新的活跃线程写入。日志条目包含了日志序号，这可以帮助辨别重复写入的日志记录，避免重复恢复。

Speeding up tablet recovery

如果master将一个tablet从一个tablet server转移到另一个tablet server，那么源tablet server会先对那个tablet做一次次压缩。这次压缩减少了tablet server中提交日志的未压缩状态的数量，减少了恢复时间。完成了这次压缩之后，源tablet server就停止对这个tablet的服务。在卸载这个tablet之前，源tablet server还会做另一次次压缩，删除tablet server的日志中任何未压缩状态（这些未压缩状态是在第一次次压缩时到达的，所以通常这第二次次压缩是很快的）。在第二次压缩结束之后，tablet就可以被直接加载到另一个tablet server了，不需要请求日志条目来恢复状态。

Exploiting immutability

除了SSTable cache，BigTable系统的许多其他部分也已经被简化。这样的策略是基于一个前提：SSTable都是不变的。例如，当我们从SSTable中读取数据时，不需要进行任何文件系统访问的同步。这样就可以让我们高效执行行级别的并发控制。唯一会发生数据变化的是memtable，它可以同时被读和写。为了减少读取memtable的冲突，我们使每个memtable行采取"copy-on-write”，并且允许读操作和写操作同时进行。

在复制一个对象的时候并不是真正的把原先的对象复制到内存的另外一个位置上，而是在新对象的内存映射表中设置一个指针，指向源对象的位置，并把那块内存的Copy-On-Write位设置为1.在对这个对象执行读操作的时候，内存数据没有变动，直接执行就可以。在写的时候，才真正将原始对象复制一份到新的地址，修改新对象的内存映射表到这个新的位置，然后往这里写。

之前一直把快照理解成了copy整个gfs文件系统了。其实快照的是一个个的文件，这些文件大的几个G，小的可能就是一个几K的网页，即使是大文件，也被作为chunk分散在各台不同的机器上，所以copy其实还是挺快的。而且，根据COW原理，一开始是没有copy的，所谓的文件其实就是一个文件名（key）到具体数据（保存在chunk中的，value）的在master上的映射。创建快照其实就是多了这样一个键值对而已，而且value的地址都没变化（同一个chunk）。只有当有对该chunk进行写入请求时，才会进行相应的chunk copy过程，然后改掉master里其中一个键值对的值就行了。这也就是COW的原理。

本段摘自“阿亮的博客”

由于SSTable不可变，永久删除数据就变动成了收集废弃的SSTable。每个tablet的SSTable都会在METADATA表中进行注册。master会移除废弃的SSTable并使用“标记-清理”算法进行垃圾回收。

最后，SSTable的不可变性让我们可以更快地分裂tablet。我们可以让子tablet和父tablet共享一个SSTable集合，而不是为每个子tablet都生成新的SSTable集合。