Bigtable: a distributed storage system for structured data
本文为翻译版
摘要
Bigtable是一个用于管理结构化数据的分布式存储系统，数据可扩展到非常大的尺寸：几千个商业服务器上的大数据。许多Google项目把数据存储在Bigtable中，包括web indexing, Google Earth, Google Finance。从数据大小的角度或是延迟要求的角度来说，这些应用对于Bigtable有不同的要求。但尽管需求不同，Bigtable能够为这些产品提供灵活的、高性能的解决方案。本文描述了Bigtable提供的简单数据模型，该数据模型使得客户端能够动态控制数据布局和格式，并描述了Bigtable的设计和实现。
Introduction
在过去的两年半时间里，我们设计、实现、部署了一个用于管理结构化数据的分布式存储系统——Bigtable。Bigtable的设计目的是使得大数据能够可靠地扩展到上千个机器上。Bigtable已经实现了几个目标：广泛的应用性、可扩展性、高性能、高可用性。Bigtable已经被用于六十多个Google产品和项目中。这些产品使用Bigtable来存放很多不同需求的负载，从面向吞吐量的批处理工作到延迟敏感的服务器数据。被这些产品所使用的Bigtable集群已经扩展了广泛的配置，存储了几百T的数据。
在许多方面，Bigtable类似于一个数据库：它与数据库共享许多实现方案。并行数据库和主存数据库已经取得了可扩展性和高性能，但Bigtable提供了跟这些系统不一样的接口。Bigtable不支持完整关系数据模型，相反，它为客户端提供了一个简单的可以支持对数据布局和格式动态控制的数据结构，使得客户端能够推测在底层存储中所表示的数据的位置属性。数据使用可以是任意字符串的行列名字作为下标。Bigtable把数据当成未翻译的字符串，尽管客户端经常将各种格式的结构化、半结构化数据序列化成这些未翻译字符串。客户端能够控制数据的位置(locality)通过选择他们的模式。最后，Bigtable模式参数使得客户端能够动态控制从内存还是硬盘中处理或访问数据。
数据模型
一个Bigtable是一个稀疏的、分布式的、持久的多维有序map。该map以一个row key、column key、timestamp作为index，map中的每个value是一个未翻译的字节数组。
在检查了一个类似于Bigtable系统的许多实用场景后我们选定了这个数据模型。一个具体的例子：假设我们想要保存一份存有大量网页和相关信息的表格，暂且将表格称为Webtable。在Webtable中，我们使用URL作为row key，使用网页的不同方面作为column names，将网页内容存储在contents中，contents是一个列。
行
表中的行key可以是任意字符串(目前大小上限为64KB，10-100字节是多数用户使用的大小)。对于一个row key的每次数据读写都是原子性的(atomic)，使得客户端能够在同一行中出现并发更新时更容易推断出系统行为。
Bigtable以row key的词典顺序维护数据。一个表的行区间(row range)是被动态分割的。每个行区间被称作一个tablet，是分布和负载均衡的单位。因此，短行区间的读是高效的并且通常只需要同少数机器进行通信。客户端能够通过选择他们的row key开发这个属性从而使得它们能够为数据访问获取数据的位置信息。例如，在Webtable中，某些领域的页面被并为一组存放在相邻的行中(通过翻转URL可以做到)。这种方式使得访问更加高效。
列族 column families
column keys被划分为一些集合，这些集合成为column families，组成了访问控制的基本单位。存储在同一column familiy中的所有数据通常是同一种类型的。一个column family必须在数据存储到任何该family中的key之前创建。当一个family被创建之后，这个family中的任何column key都可以被使用。我们故意使得column family的数量保持在少数（最多几百个），而且families很少在操作过程中改变。相反，一个表中可能有无数个列。
一个column key的命名方式要遵循语法：family:qualifier。Column family 的名字必须是可打印的，qualifier就可以是任意字符串。例如：Webtable中的一个column family是language，存储了该web page对应的语言，该family中只有一个key，存储了language ID。另一个family是anchor，里面的每个key表示一个单独的anchor。如图1所示，qualifier表示相关网站，表格中的内容则是链接文本。
访问控制和硬盘、内存统计是在column family层面执行的。以Webtable为例，这些控制使得我们能够管理一些不同种类的应用：添加新的基数据、读取基数据和创建衍生的column family以及只允许浏览现有数据。
时间戳 timestamps
Bigtable中的每个cell能够包含同一数据的不同版本。这些版本以时间戳为下表。Bigtable的时间戳是64位证书。它们能够被Bigtable本身所赋值或是被客户端应用显式赋值。客户端应用需要生成单独的时间戳以避免碰撞。一个cell的不同版本是按照时间戳递减顺序排列的，因此最近的版本会被最先访问。
为了更好地管理有版本的数据，我们支持两种设置使得Bigtable能够自动进行cell版本垃圾回收。客户端能够指定只有最新的n个版本能够被保留或是只有足够新的版本能够被保留(例如只保留最近7天内被写入的版本)。
以Webtable为例，我们设置这个存储在contents中的被爬下来的网页的时间戳…上面描述的垃圾回收机制使得每个页面只能保留最近的3个版本。
API
Bigtable API提供了一些用于创建和删除表、column family的方法。它也提供了一些改变cluster、table、column family metadata的方法，例如访问控制权限。
客户端应用能够写入或删除Bigtable中的数据，查找每个行中的数据或者是遍历表中数据的某个子集。
···
···
Bigtable支持一些其他的特性使得用户能够更复杂地操控数据。首先，Bigtable支持单行交易，能够用于执行原子性的对保存在单个row key中的数据的读写操作。Bigtable目前不支持通用的跨row key的交易，尽管它提供了一个跨row key批量写入数据的接口。其次，Bigtable允许每个cell被用作integer counters。最后，Bigtable支持在服务器的地址空间中执行客户端提供的脚本。这些脚本使用一种Google为了处理数据而开发的语言写的——Sawzall。目前，我们的基于Sawzall的API不支持客户端脚本写回Bigtable，但它允许不同的数据转化格式，以任意表达式过滤以及通过多种操作符总结。
Bigtable可以与MapReduce一起使用。MapReduce是Google开发的一个用于运行大规模并行计算的框架。我们已经封装了许多接口使得一个Bigtable既可以作为MapReduce job的输入又可以作为输出。
building blocks
Bigtable是基于一些其他的Google基础设施构建的。Bigtable使用分布式的Google File System(GFS)来存储日志文件和数据文件。一个Bigtable集群通常在一个共享池中被操作，池中包含了运行有其他分布式应用的机器。Bigtable进程经常与其他应用的进程共享同一台机器。Bigtable依赖一个集群管理系统来调度工作、管理共享机器的资源、处理机器错误以及监视机器状态。
Google SSTable文件格式用于存储Bigtable数据。一个SSTable提供了一个持久的、有序不变的map将key映射到value，其中key和value都是任意字符串。SSTable提供了查找跟特定key所关联的value的操作，或者是遍历特定key区间内的键值对。在内部，每个SSTable 包含一个块序列，通常每个块是64KB，但这个大小是可配置的。一个块的下标（储存在SSTable的末端）用于定位块，这个下标在SSTable被打开时载入内存。一个查找操作通过一次磁盘搜索便可以完成：首先通过对内存中的下标进行二分查找找到合适的块，再将该块从磁盘中读取出来。一个SSTable也可以完整映射到内存中，从而查找操作可以无需访问磁盘。
Bigtable依靠一个高可用和持久的分布式锁服务——Chubby。一个Chubby服务包含5个活跃的副本，其中一个被选举为master并响应请求。当多数的副本都处于运行状态并且能够互相通信时，服务即试做在线(live)。Chubby使用Paxos算法来保持副本之间的一致性。Chubby提供了一个命名空间包含了文件夹和一些小文件。每个文件夹或文件可以作为一个锁，对一个文件的读写是原子性的。Chubby客户端库提供一致的Chubby文件缓存服务。每个Chubby客户端维护一个session。当客户端的session无法在租约到期时间内更新他的session lease则session过期。当一个客户端session过期时，它释放所有的锁和已开启的handle。Chubby客户端能够为Chubby文件和文件夹注册回调函数用于通知变化或session过期时间。
Bigtable使用Chubby来完成各种任务：确保在任何时间最多只有一个活跃的master；保存Bigtable数据的bootstrap location；发现tablet服务器和中间tablet服务器的死亡；存储Bigtable的模式信息（每个表中的column family信息）；存储访问控制列表。如果Chubby持续一段时间内都不可用那么Bigtable也会变得不可用。我们在14个跨越了11个Chubby实例的Bigtable集群测量了这种影响。在Bigtable的服务时间内由于Chubby不可用造成存储在Bigtable中的数据不可用的时间平均占比为0.0047%，其中占比最高的单个集群为0.0326%。
Implementation
Bigtable包含三个主要组件：链接到每个客户端的库、一个master server和许多tablet server。集群中的tablet server 能够动态添加或删除来适应负载的变化。
master负责分配tablets给tablet server， 删除额外的和过期的tablet server， 均衡 tablet server 的负载以及GFS中的文件的垃圾回收。并且，它还处理模式的变化例如表或column family的创建。
每个tablet server管理一个tablet集合（通常每个tablet server有10-1000个tablet）。tablet server处理它载入的tablet的读写请求并将变得过大的tablet切分开来。
就像许多单master的分布式存储系统一样，客户端数据不通过mater移动：客户端直接与tablet server进行读写通信。因为Bigtable客户端不依赖master来获取tablet 定位信息，多数的客户端从不与master通信。因此，master 在实际上是轻载的。
一个Bigtable集群存储了许多表。每个表包含了许多tablet，每个tablet包含了与一个行区间关联的所有数据。一开始，每个表只包含一个tablet。随着表的增长，它自动切分成了多个tablet，每个默认大小为100-200MB。
tablet location （片位置）
我们使用一个类似于B+树的三层结构来储存片位置信息。
第一层是一个存储在Chubby中的文件，包含了根片（root tablet）的位置信息。根片包含了所有片的位置信息在一个特殊的METADATA表中。每个METADATA片包含了一个用户tablet集合的位置信息。根片是METADATA表的第一个片，它不会再被分解，确保了片位置信息层次不会超过三层。
METADATA表存储了一个片的位置信息在一个row key中，row key是这个片的表的标识以及它的末尾行的编码。每个METADATA行存储了大约1KB的数据在内存中。若METADATA的上限为128MB，那么这种三层的位置结构可以存储2^34个片。
客户端库存储了片位置。如果客户端不知道某个片的位置或者如果它发现了缓存中的位置信息是错误的，那么他就会递归地上升片位置层次。如果客户端缓存为空，那么定位算法需要3轮网络通信，包括一次对Chubby的读。如果客户端的缓存是被污染的，那么定位算法需要6轮网络访问，因为被污染的缓存条目只有在不命中时才会被发现。尽管片位置信息存储在内存中，已经无需访问GFS，我们还是进一步减少了内存开销，通过令客户端库预取片位置：无论何时读取METADATA表时都会读取不止一个片。
我们在METADATA表中也存储了一些次要信息，包括所有事件的日志等，有助于debug和性能分析。
tablet assignment 片分配
每个片一次只会分配给一个tablet server。master保持对活跃的tablet server集合的追踪，以及对tablet分配行为的追踪，包括未被分配的tablets。当一个片是未被分配的，并且有一个拥有足够空间的tablet server是可用的，那么master就会以发送一个tablet载入请求给server的形式将片分配给server。
Bigtable使用Chubby来追踪(track)tablet server。当一个tablet server开启，它创建并获得一个专用的锁在一个特殊Chubby文件夹的单一命名的文件上。master通过监控这个文件夹来发现其他的tablet server。如果这个专用的锁丢失了那么tablet server就会停止服务：例如：由于网络切分导致server丢失了Chubby session。Chubby提供了一个有效的机制能够使得tablet server在不引发网络拥塞的情况下可以检查它是否还保留着锁。只要文件还存在tablet server就会尝试重新获取文件锁。如果文件已经不存在了，则表示tablet server 无法再继续服务，因此它会将自己kill掉。当tablet server终结时(例如)它会尝试释放锁使得master能够更快地重新安排它的tablets。
master负责检测tablet server不再服务它的片了并且尽快重新安排这些片。为了检测tablet server是否不再服务它的片，master会定期询问每个server的锁状态。如果某个tablet server报告它已经丢失了它的锁，或者master经过几次尝试后都无法到达这个tablet server，master会尝试获取这个server的文件锁。如果master成功获取了这个文件锁那么Chubby是活跃的并且这个tablet server还未死亡或者只是无法获取Chubby，那么master会删除它的server文件来确保这个server不会再提供服务。一旦一个server的文件被删除，master能够移动这钱分配给这个server的所有的片进入未分配片的集合中。为了确保Bigtable集群不会轻易由于master和Chubby之间的网络原因受损，master会在Chubby session过期的时候杀死它自己。然而，尽管如上所述，master的failure不会改变对片的分配。
当master被集群管理系统启动的时候，它需要在改变片安排情况之前获取现有的片安排情况。master启动时执行这些操作：1)master在Chubby中抓取一个特殊的master锁，避免并发的master初始化；2)master扫描Chubby中的server文件夹来寻找存活的server；3)master和其他在线的tablet server通信以获取片分配情况；4)master扫描METADATA表。当扫描到了一个还未被分配的片时，master将这个片添加到未分配片集合中。
较为复杂的情况是对METADATA表的扫描只有在METADATA表已经被分配的情况下才能发生。因此，在扫描开始之前，master会添加根片到未分配片集合中如果在第3)步中对跟片的分配未被发现。这个附加条件确保了根片会被分配。因为根片包含了所有METADATA片的名字，master扫描根片之后便可以获取所有片名。
现有的片集合只有当一个表创建或删除、两个表的合并或一个表的切分时才会发生改变。master能够保持对这些变化的追踪。片切分会被特殊对待因为它们是被tablet server初始化的。tablet server会将新片的信息记录到METADATA表中。当信息成功提交后会通知master。万一切分的通知丢失了（由于tablet server或master的死亡引起的），master会检测新的片当它命令一个tablet server去载入已切分的片时。tablet server会通知master切分行为因为它在METADATA表中找到的tablet条目只会指定master要求装载的一部分片。
tablet serving
片的持久状态被保存在GFS中。更新会被提交到一个保存了重做记录的日志中。在所有的更新中，最近提交的更新会被保存在一个有序的内存缓存中，称为memtable。旧的更新保存在一个SSTable序列中。为了记录一个片，tablet server会从METADATA表中读取数据。被读取的数据包含了SSTable列表，这个列表包含了一个片，一个重做点集合（指向提交日志中那些可能与该片有关的数据）。server读取这些指数到内存中并重新构建memtable通过应用这些在重做点后提交的更新。
当一个写操作到达tablet server的时候，server会检查它是否完好并检查发送者是否已授权。授权操作是通过读取Chubby文件中的允许写入者列表来确认的。(这个操作在Chubby客户端缓存中几乎总是命中的)。一个有效的突变会被写入提交日志中。提交分组被用来提高小突变的吞吐量。当写操作成功提交后，它的内容会被插入到memtable中。
当一个读操作到达tablet server的时候，server也会检查它是否完好并检查发送者是否已授权。一个有效的读操作会被执行以SSTable序列和memtable合并的视角来看。由于SSTable和memtable是按字典顺序排序的数据结构，因此合并操作非常高效。
当tablet被切分或合并时即将到来的读写操作可以持续进行。
Compaction
当写操作执行时，memtable的大小增加。当大小增加到一定的阈值是，memtable会被冻结，一个新的memtable会被常见，被冻结的表会转化成SSTable并写入到GFS中。这个最小压实操作有两个目标：1)收缩服务器的内存使用情况；2)减少当服务器死亡后恢复过程中需要从日志中读取的数据量。未来的读写操作可以在压实操作过程中持续进行。
每个最小压实操作会创建一个新的SSTable，如果这个行为没有被检测出来，读操作可能需要从任意多个SSTable中合并更新。相反，我们限制了这种文件的数量通过在后台定时执行一个合并压实操作。一个合并压实操作会从一些SSTable和memtable中读取内容并写入到新的SSTable中。当压实操作完成后作为输入的SSTable和memtable就可以被丢弃了。
一个合并压实操作会重写所有的SSTable到一个SSTable这种，这种操作成为主压实操作。由非主压实操作产生的SSTable可以包含特殊的删除条目，这些条目会抑制已经被删除的数据(但是在旧的SSTable中还存活的数据)。而主压实操作产生的SSTable不会包含删除信息以及被删除的数据。Bigtable循环遍历它的片并规律地执行主压实操作。这些主压实操作使得Bigtable能够澄清被已删除数据占用的资源并确保已删除的数据能够及时从系统中消失(对于存储敏感数据的服务来说非常重要)。
Refinement
上述章节描述的实现方法需要一些改进以获取更高的性能、可用性和可靠性。
locality groups
客户端可以将多个column family分组到一个locality组中。一个独立的SSTable会被创建用于每个tablet的每个locality组。分离那些不是很经常被访问的column family到一个单独的locality组中能够提高读效率。例如，Webtable中的网页元数据(例如语言或是访问量)可以处于一个locality组中，而内容可以处于另一个组中：一个想要读取元数据的应用不会需要读取网页内容。
另外，一些有用的平衡参数也能够被指定针对每一个locality组。例如，一个组可以被声明是保存在内存中的。用于保存在内存中的locality组的SSTable会被惰性地载入tablet server的内存中。一旦被载入，这些组中的column family能够在不访问磁盘的情况下被读取。这个特性对于一些频繁被访问的小片数据来说非常有用：我们在内部使用它为了定位METADATA表中的column family。
Compression
客户端能够控制是否压缩一个locality组对应的SSTable，如果压缩，它还可以决定采用哪种压缩方式。用户指定的压缩方式会被应用到每个SSTable块中（块的大小是可控的通过一个特殊的参数）。尽管由于单独压缩每个块会浪费一些空间，但是读取的时候只需要取出一小部分而不是全部的文件就可以了。许多客户端采用传统的two-pass压缩方式。第一个pass使用Bentley and McIlroy’s Scheme，能够跨越大区间压缩长字符串。第二个pass是使用一个快速压缩算法来寻找一个16KB的小区间中的重复数据。两个pass都是非常快速的，编码速度100-200MB/s，解码速度400-1000MB/s。
尽管我们在选择算法时强调速度而不是节省的空间，这个压缩模式却表现优秀。例如，在Webtable中，我们使用这种压缩模式来存储网页内容。在我们的实验中，我们存储了很多文件在一个压缩的locality组中。为了达到实验目的，我们限制了每个文件只有1个版本。这种压缩方式实现了10:1的空间节省。这远好过GZip的3:1或4:1的压缩比，因为网页的行是这么分布的：单个host的所有网页存储的位置相邻。不仅是Webtable，还有很多应用选择行名使得相似的数据能够聚集在一块因而达到较高的压缩比。当Bigtable中存储了相同数据的多个版本时压缩比甚至能达到更高。
caching for read performance
为了提高读性能，tablet server使用2层缓存。高层的成为Scan Cache，缓存了由SSTable接口返回给tablet server代码的键值对。底层的是Block Cache，缓存了从GFS中读出来的SSTable块。Scan Cache对于那些倾向于重复读取相同数据的应用更有用。而Block Cache则对那些倾向于读取最近读取过的数据的应用更有用。
Bloom filers
一个读操作需要读取所有的SSTable来拼凑tablet的状态。如果SSTable不再内存中，最后还是需要访问磁盘。我们减少磁盘访问次数通过允许客户端指定在特定的locality组中的SSTable生成Bloom filter。一个Bloom filter可以使得我们可以询问一个SSTable是否包含某个特定行/列对的数据。对于某些应用，少量的tablet server内存用来存放Bloom filter可以减少由读操作引起的磁盘访问。我们使用Bloom filter同时也表明了大多数对不存在的行列的查找不需要访问磁盘。
commit-log implementation
如果我们将每个片的提交日志保存在不同的日志文件中，那么GFS将会同时有大量的文件写入。这些写操作可能导致大量的磁盘搜索取决于每个GFS服务器的底层实现。并且，每个单独的日志文件会减少分组带来的优化。为了解决这些问题，我们将突变拼接到每个tablet server的提交日志中，再混合不同server的日志到同一个日志文件中。
使用单个日志文件提供了良好的性能优化，但灾难恢复变得更复杂。当一个tablet server死亡时，它所服务的片会被移动到很多其他的tablet server上:每个server只会载入少量的片。为了恢复片的状态，新的server需要重新应用突变到原本写好的提交日志上。然而，这些片的突变已经在同一个日志文件中混合。一个方法是令每个新的tablet server去读取完整的日志文件并恢复那些需要恢复的条目。但效率太低。
通过对提交的日志条目进行排序我们避免了重读的日志读取(根据 table、row name、log sequence number排序)。在排序后的输出中，一个特定的片的所有转变是相邻的因此能够通过一次磁盘搜索高效地读取。为了并行化排序，我们将日志文件划分为64MB大小的段，然后在不同的tablet server上并行地排序每个段。这种排序过程是由master协调的并且当一个tablet server表明他需要从日志文件中恢复一些变化时被初始化。
写日志到GFS中有时会导致性能瓶颈，有很多原因，例如写操作冲撞涉及到的GFS server，或者到达三个GFS服务器的指定集合的网络路径被阻塞或是高负载。为了保护突变免受延迟峰值的影响，每个tablet server实际上有2个写日志线程，每个线程写入它自己的日志文件，一次只有一个线程工作。如果写入的文件性能很差，那么就会切换到另一个线程。日志条目包含了序列号使得恢复过程可以避免由于线程切换造成的重复条目。
speeding up tablet recovery
如果master将一个片从一个tablet server移动到另一个，源server首先对该片执行一个最小压实操作。这个操作减少了恢复时间通过减少日志中未被压实的状态数量。压实结束后，源tablet server不再服务于这个片，在它真正卸载这个片之前，server执行另外一个（通常都非常快）最小压实操作来消除在第一个压实过程中到达的残留的未被压实的状态。当这两个压实操作完成后，该片会被装载到另一个server中而无需进行日志条目恢复。
exploiting immutability
包括SSTable缓存在内，Bigtable系统的许多其他部分都被简化了，根据SSTable的不变性。例如，当读取SSTable时我们不需要任何对文件系统的并行访问。因此，对行的并行控制能够高效的实现。唯一可变的数据结构是memtable。为了减少读取memtable过程中产生的冲突，我们使每个memtable的行在写入时复制并且允许读写并行。
由于SSTable是不可变的，移除被删除的数据等同于对过时的SSTable进行垃圾回收。每个片的SSTable在METADATA表中注册。master移除过时的SSTable通过对SSTable集合进行一个mark-sweep垃圾回收操作，METADATA表中包含root集合。
最后，SSTable的不变性使得我们能够很快地切分片。我们令子片和父片共享一个SSTable而不是为每个子片重新生成SSTable。
performance evaluation
我们建立了N个tablet server的Bigtable集群来测量Bigtable随着N变化的性能和可扩展性。tablet server使用1GB内存，2个400GB IDE硬盘驱动来写入一个有1786个机器组成的GFS cell。N个客户端机器生成用来测试的Bigtable负载。我们使用同样数量的客户端作为tablet server来确保客户端不会成为瓶颈。每个机器有2个双核Opteron 2GHz芯片，足够的物理内存来装载正在运行的进程的工作集，以及一个单千兆以太网链路。这些机器会被安排成一个2层的树形的在根节点大约有100-200Gbps合成可用带宽的网络。所有的机器处于同一个主机中因此任何机器间的通信时间少于1毫秒。
tablet server、master、测试客户端、GFS server全都跑在同一个机器集合上，每个机器运行一个GFS server。一些机器也会运行tablet server或者一个客户端进程、或是同时处理其他工作。
R是测试中Bigtable的不同行key的数量。选择一个合适的R使得每个benchmark都会读写大约1GB的数据。
sequential write使用0-(R-1)作为行 key，行key空间被划分为10N个等大的区间。这些区间被一个中央调度器安排到N个客户端，只要客户端处理完上一个分配给它的区间这个调度器就会分配下一个可用的区间给客户端。这种动态分配消除了由其他运行在客户端上的进程产生的对性能的影响。我们在每个行key下写了一个字符串。每个字符串是随机生成的因此行是不可压缩的。而且，不同的行key下的字符串是不同的，因此跨行的压缩是不可能的。random write也是相似的除了行key被哈希后对R取模因此写负载被均匀得传播到每一个行空间。
benchmark介绍
—介绍sequential read
—介绍scan
—介绍random reads(mem)
single tablet-server performance
随机读取比任何其他操作都慢。每次随机读取涉及到将一个64KB的SSTable通过网络从GFS server传送到tablet server中，其中只有1000字节的值被使用。tablet server每秒大约执行1200次读，也就是能够从GFS中读取大约75MB每秒的数据。这样的带宽足够使得tablet server CPU饱和，由于网络堆栈中的开销、SSTable转化、Bigtable代码。而且这样的带宽也足够使得系统中的网络饱和。大多数Bigtable应用会减少块大小至8KB。
从内存随机读取是非常快的因为每1000字节的读取tablet server的内存就可以满足，而不需要从GFS读取一个大的64KB的块。
随机和顺序的写比随机读表现更好因为每个tablet server会拼接所有到来的写到一个单独的日志中并使用组提交来将这些写高效地流入GFS。在随机写和顺序写的性能方面没有太大差别。两种情况下，所有的写都会被记录到同一个日志中。
顺序读比随机读更优因为每个从GFS取出的64KB的SSTable块会被存储到块缓存中用于下一次的64读请求。
scaling
当我们增加tablet server数量从1到500时总吞吐量也增加。例如，从内存的随机读取增加了300倍，当tablet server数量增加了500倍时。这种行为是因为这个benchmark的性能瓶颈是每个tablet server的CPU。
然而，性能并没有线性增加。对于大多数的benchmark来说，当tablet server的数量从1变成50的时候，每个server的吞吐量反而下降了。这种下降是因为负载不均衡，通常是因为其他进程抢夺了CPU和网络。我们的负载均衡算法尝试解决这种不均衡，但是无法完美：重新均衡被限制为减少tablet的移动（移动时一个tablet会短暂不可用，通常少于1秒）；由benchmark产生的负载会到处挪动。
随机读的benchmark表明了最坏的扩展性（当tablet server数量扩大500倍时总体吞吐量只提高了100倍）。这种行为是因为每1000个字节的读取都需要通过网络传输一个64KB的块。这种传输 使得1千兆以太网链路饱和，因此每个服务器的吞吐量会随着奇迹数量的增加而下降。
Real Application
截止2006年8月，已有388个非测试的Bigtable集群运行在不同的Google机器集群上，共有约24500个tablet server。
Google Analytics
Google Analytics 是一个帮助webmaster在网站上分析交通模式的服务。它提供了总体的数据，例如每日访问量以及每个URL每天的阅读量，以及一些网站分析报告，例如已经浏览了某个网页后进行购买的用户比例。
为了实现这个服务，webmaster嵌入了一个小JS程序在网页中。这个程序在网页被访问时触发。它记录了不同的Google Analytic请求信息，例如一个用户标识符和网页读取相关信息。Google Analytic总结了这些数据并使得它对webmaster可用。
我们简单描述了Google Analytics使用的两个表格。原生点击表格为每个端用户session维护一行，行名为包含了网站名字和session创建时间的组合。这种模式确保了访问同一个网站的session是连续的并按时间顺序排列。这个表格压缩到原来尺寸的14%。
Google Earth
google为用户提供了高解决方案的卫星云图，通过基于网站的的Google地图接口和Google Earth。这些产品使得用户能够在地球表面穿梭：他们可以放大、旋转、浏览、标记卫星云图。这个系统使用一个表来预处理数据，还有一个不同表的集合来服务客户端数据。
预处理流水线使用一个表来存储原生图像数据。在预处理期间，图像被清洁和巩固到最终的服务数据。这个表包含了大约70T的数据因此是保存在磁盘中的。这些图像被有效压缩因此Bigtable压缩是不可用的。
图像表中的每行对应一个地理段。行的命名确保了相邻的地理段会保存在相近的位置。表中包含一个column family来追踪每个段的数据源。这个column family 有很多column：每个对应一个原生图像数据。由于每个段只是从几张图片构成的，因此这个column family十分稀疏。
预处理流水线十分依赖MapReduce来转化数据。总体的系统以1MB/s的速度处理每个tablet server的数据。
服务系统使用一个表来index存储在GFS中 数据。这个表非常小（大约500GB）但它必须在非常低的延迟下每秒每个数据中心服务成千上万个查询。因此，这个表由几百个tablet server持有并包含了存储在内存中的column family。
Personalized Search
Personalized Search是一个记录了用户对不同的Google产品例如网页搜索、图像、新闻的查询、点击操作。用户可以浏览他们的搜索历史来重新访问旧的查询和点击，他们可以寻求个性化的搜索结果。
Personalized Search在Bigtable存储了每个用户的数据。每个用户有单独的userid并且用这个userid命名了一个行。所有的用户行为被保存在一个表中。每种类型的行为预留一个单独column family（例如，有一个column family存储了所有web查询）。每个数据元素使用用户行为触发的事件作为Bigtable时间戳。Personalized Search使用对Bigtable的MapReduce生成用户描述，可以用于个性化的用户实时搜索结果。
Personalized Search数据在多个Bigtable集群中是重复的，为了提高可用性和由于客户端的距离产生的延迟。Personalized Search团队一开始创建了一个基于Bigtable的客户端副本机制为了确保所有副本的事件一致。这个系统现在使用服务器内部的一个复制子系统。
Personalized Search存储系统的这种设计使得其他的组能够添加新的用户信息到他们自己的column中，这个系统现在已经被多个其他需要个性化用户配置选项和设置的Google产品使用。不同组之间共享一个表造成了非常多的column family。为了支持这种共享，我们添加了一个简单的quota机制到Bigtable中来限制共享表中任一客户端的存储消耗。这种机制提供了不同的产品组之间的一些隔离。
Lessons
在设计、实现、维护和支持Bigtable的过程中，我们获得了有用的经历和有趣的教训。
一个教训是大的分布式系统对于很多类型的失败来说是易损的，不只是很多分布式协议中设想的标准的网络切分和fail-stop失败。例如，我们已经发现了很多由于以下原因导致的问题：内存和网络崩溃、大的时钟偏差、悬挂机器、扩展的和非对称的网络切分、其他正在使用的系统的bug、GFS quota移除、计划合非计划的硬件维护。我们使用多种协议来解决这些问题。例如，我们添加了校验和到RPC机制中。我们还通过移除了系统的一部分对另一部分所做的假设。例如，我们不再假设Chubby操作只能够返回固定的一组错误。
另一个教训是在新的特性没搞清楚之前不要急着添加。例如，我们一开始计划在我们的API中支持通用目的的交易。因为我们并没有立即用到这个功能，因此我们没有实现。现在我们已经有了很多真实的跑在Bigtable上的应用，我们能够检查他们实际的需求并且发现了大多数的应用只需要单行交易。当人们对分布式交易有需求时，最重要的是维护次要的指数，因此我们打算添加一个特殊的机制来满足这个需求。新的机制会比分布式交易更不通用一点，但会更高效（特别是对于跨越了几百个行的更新来说），并且会与我们的优化跨数据中心副本交互得更好。
一个很实用的教训是适当的系统层面监控是非常重要的（也就是说不仅监控Bigtable本身也监控使用了Bigtable的客户端进程）。例如，我们扩展了RPC系统使得对于一个RPC样来说他能够保持一个详细的对重要行为的记录。这个特性使得我们能够检测和修复许多问题，例如对tablet数据结构的锁争夺、提交Bigtable突变时写操作过慢、由于METADATA 片不可用造成的访问阻塞。另一个有效监控的例子是每个Bigtable集群都在Chubby中注册。这使得我们能够追踪所有的集群，发现他们的代销、观察我们的软件正在运行哪个版本、它们接收时是否拥塞、或者是否产生大的延迟等。
最终要的一个教训是简单设计的价值很高。由于系统的大小(大约10万行非测试代码)，以及代码随时间演变，我们发现代码和设计清晰度对后期的代码维护和debug非常重要。一个例子是tablet server的menbership协议。我们第一个协议非常简单：master定期发布租约到tablet server中，租约过期时tablet server杀死自己、然而这种协议在出现网络问题时可用性非常低，并且对master恢复时间敏感。我们又重新设计了协议。然而，最终的协议非常复杂并且依赖于一些很少被其他应用使用的Chubby特性的行为。我们在Chubby代码的晦涩案例上而不只是Bigtable代码上花费了太多时间。最终，我们废弃了这个协议并设计了一个新的简单协议，只依赖于那些广泛使用的Chubby特性。
Related Work
Boxwood项目有些组件与Chubby、GFS、Bigtable有重合，因为它提供了分布式agreement、锁、分布式chunk存储、分布式B树存储。在每种重合的情况下，Boxwood的组件针对的是更低层次的对象。Boxwood的目标是提供一个用于构建更高层次服务（例如文件系统或数据库）的框架，而Bigtable的目标是支持想要存储数据的客户端应用。
许多最近的项目已经解决了分布式存储或为广域网提供高层服务的问题。这包括对随着CAN、Chord、Tapestry等项目而开始的分布式哈希表的工作。这些系统强调了一些Bigtable没有出现的问题，例如高可变的带宽、不信任的参与者以及频繁的重配置。去中心化的控制和拜占庭容错不是Bigtable的目标。
从分布式数据存储模型的角度来说，我们相信有B树或分布式哈希表提供的键值对模型比较局限，相对于提供给应用开发者的模型来说。键值对是一个有用的构件块，但它们不应该是唯一一个提供给开发者的块。我们选择的模型比单一的键值对更丰富，并且支持稀疏的半结构化数据。尽管如此，它也是足够简单的，可以用高效的flat-file形式表示，并且足够透明，用户可以监控系统的重要行为。
许多数据库销售公司已经开发了并行数据库，可以存储大量的数据。Oracle的Real Application Cluster数据库使用共享磁盘来存储数据，一个分布式锁来管理。IBM的DB2 Parallel Edition基于一个与Bigtable类似的shared-nothing体系结构。每个DB2服务器负责一个表中的行子集，行子集存储在本地的关系数据库中。两个产品都提供了完整的关系模型，并支持交易。
Bigtable locality 组实现了相似的压缩和磁盘读取性能，通过以基于列的数据组织形式而不是基于行的形式来实现。另一个实现横向和纵向切分数据到平面文件中的系统并且实现了很高压缩率的系统是AT&T的Daytona数据库。Locality组不支持CPU缓存层面的优化。
Bigtable使用memtable和SSTable来存储对片的更新，这种形式与Log-Structured Merger Three存储更新的形式相似。两个系统中，被排序的数据在被写入磁盘之前都缓存在内存中，而读操作必须合并内存和磁盘的数据。
C-store和Bigtable有一些相似的特性：都使用一个shared-nothing体系结构并且有两种不同的数据结构，一种用于最近的写，一种用于存储长寿命的数据，并且拥有移动数据的机制。两个系统在API方面不同：C-store表现为关系型数据库，然而Bigtable提供了一个更低层次的读写接口而且支持每个服务器每秒几千次操作。C-store也是一个读优化的关系型数据库管理系统，然而Bigtable为读写敏感的应用提供了更优的性能。
Bigtable的负载均衡器解决了一些与shared-nothing数据库面临的相同的问题。我们的问题更加简单：1）我们不考虑相同数据可能会有多个副本；2）我们让用户告知我们哪些数据是在内存中的而那些数据应该在磁盘中，而不是动态地去决定。3）我们无需执行或优化复杂的请求。
Conclusions
我们已经描述了Bigtable——一个用于存储结构化数据的分布式系统。Bigtable集群自从2005年4月一来就投入生产，在此之前，我们已经花了将近7年的时间来设计和实现。截止2006年8月，超过60个项目正在使用Bigtable。我们的用户非常喜欢由Bigtable提供的性能和高可用性，他们能够简单地通过增加更多机器来扩展集群的容量。
考虑到Bistable一些不同寻常的接口，问题是对于用户来说他们适应的过程会有多难。新用户有时对于如何最好地使用Bigtable的接口并不确定，特别是当他们已经习惯于使用关系型数据库的情况下。尽管如此，许多成功使用Bigtable的Google产品证明了我们工作的实用性。
我们正继续开发几个额外的Bigtable特性，例如支持次要指数以及创建跨数据中心的Bigtable副本。我们也开始为产品组部署Bigtable作为服务，使得个人用户无需维护他们自己的集群。随着服务集群的扩展，我们需要解决很多Bigtable内部的资源共享问题。
最后，我们发现在Google搭建我们的解决方案有非常大的优势。我们在为Bigtable设计我们自己的数据模型时获得了大量的灵活性。而且，我们控制Bigtable的实现、以及其他Bigtable所依赖的Google组件，意味着我们能够随着问题的出现移除瓶颈和低效率的部分。