介绍
bigtable是一个管理结构化数据的分布式存储系统，支持数千台机器和PB级的数据，被广泛用于google内部的产品和项目。
bigtable在许多方面与数据库相似，但有不同的接口层，不支持完整的关系数据模型，它提供一种简单的数据模型，支持客户端动态控制数据布局和格式，通过参数可以控制数据在内存或者磁盘。
数据模型
bigtable可以看作是一个稀疏的、分布式的、一致的和多维的有序map。map由row key，column key和时间戳来索引。
(row:string, column:string, time:int64) -> string
例如上图所示，需要保存web pages的相关信息，将这个table称作Webtable。在Webtable中，使用url作为row key，web pages的不同层作为column name，contents列保存page的文本，timestamp列保存它们被fetch的时间。
rows
row key可以是任意的字符串，无论一行有多少不同的column，单行key下的读写都是原子的。Bigtable以row key维护字典序，一个table通过row range划分不同的partitions，每个row range称作tablet，tablet是个很重要的概念，它是分布式和负载均衡的基本单元。客户端可以利用这个特性选择它们的row key，在访问时获得更好的局部性。
column families
多个column keys可以组合在一起叫作column family，形成访问控制的基本单元。通常相同类型的列被放在同一cf中(相同cf的数据是一起压缩的)。内存和磁盘上的访问控制都是column family级别的。
timestamps
bigtable中相同的数据是有多版本的，通过timestamp区分，timestamp可以由bigtable或者客户端分配，必须是独一无二的。不同timestamp的cell的多个版本根据timestamp逆序存放，以便于读取最新版本的数据。
bigtable支持两种gc多版本数据的方式，一种是保留最近的n个版本，一种是保留足够新的数据，例如最近七天的数据版本。
API
bigtable提供的api包括创建、删除tables和column families，也提供变更集群、table和column families的元信息，例如访问控制权限。
客户端应用可以写或者删除bigtable的数据，查找单行或者扫描数据集。bigtable支持单行事务，支持单个row key上原子的read-modify-write。不支持跨row key的并发事务。
构建模块
bigtable构建在几个google的基础设施之上，使用分布式文件系统GFS存储日志和数据文件，bigtable集群与其它不同的分布式应用共享机器资源池，bigtable进程也与其它应用进程共享机器。bigtable依赖于一个集群管理系统来调度job、管理资源、处理机器failures和监控机器状态。
使用sstable的格式存储数据，sstable按照key有序存放且不可更改，key和value是任意的字符串。sstable内部由多个blocks组成，通常64kb，可以通过参数配置。index block用于索引data block，当sstable open时，index block被放入内存中。对于某些数据，sstable也可以完全放入内存中以避免磁盘seek。
bigtable依赖一个高可用、一致性分布式锁服务叫作chubby。一个chubby服务包含五个副本，其中一个为master，服务请求。chubby使用paxos算法保证副本的一致性。chubby提供包含目录和小文件的域空间，每个目录或者文件通过lock控制使用，读写文件都是原子的。
bigtable使用chubby实现多种的task:
- 确保任何时刻最多只有一个活跃的master
- 保存bigtable数据的bootstrap location
- 发现tablet server的存在和控制tablet server的death
- 存储bigtable schema信息
- 存储访问控制列表
可见chubby对于bigtable是非常重要的，chubby如果不可用，bigtable也就不可用了。
实现
bigtable主要由三个重要的组件组成：
- 被链接到每个客户端的库
- one master server
- many tablet servers
master主要负责分派tablets到tablet server、检测tablet server的添加和过期、平衡tablet server的负载和GFS文件的gc。
每个tablet server管理一定数量的tablets(一般10到一千)，处理读写请求，split增长过大的tablet等。
与许多单节点master的分布式系统一样，客户端的数据不经过master，直接与tablet server交互进行读写操作。bigtable的客户端不依赖于master来得到tablet的位置信息，大多数客户端从来不与master交互，因此master是一个非常轻量负载的节点。
bigtable集群存储大量的table，每个table包含tablets的集合，初始时，一个table只有一个tablet，随着数据的增长会自动分裂成多个tablets，每个大约100M～200M。
tablet location
使用类似b-tree的结构存储tablet的location信息，共分三层。
第一层是存储在chubby中的一个文件，包含root tablet的位置，root tablet包含所有tablets meta data的位置信息，每个meta data包含user tablet集合的位置信息。root tablet永远不会分裂，保证整个层次体系不会超过三层。
客户端缓存了tablet location，如果客户端不知道一个tablet的location或者发现缓存的信息是错误的，它会根据层次结构递归的将其移除。tablet location保存在内存中，不会产生GFS访问，为了进一步减少开销，还增加了预取tablet locaton信息的机制。
tablet assigment
master负责将tablet分派到某一tablet server中，追踪可用的tablet servers和当前tablet的分派信息，也包含未被分派的tablet。当一个tablet未被分派，一个tablet server包含一个tablet的可用空间时，master通过发送一个对这个tablet的load请求到tablet server上来分派tablet。
bigtable使用Chubby追踪tablet servers，tablet server在创建时获得一把排他锁和unique name的file，file保存在chubby的特定目录下，master通过监控这个目录来找到tablet server。当tablet server失去这把锁时，会停止对其tablet的服务，只要这个file存在tablet server会再次尝试获得这把锁，如果file不存在了，tablet会kill掉自己不再进行服务。tablet server结束时会释放锁。
master通过周期地ask每个tablet server它们的lock status来检测是否tablet server停止服务，当master检测到一个tablet server停止服务时，它会重新assign它的tablets。当tablet server失去它的lock，master能够获得它的锁，表明chubby是可用的而tablet server不可用或者与chubby失去连接，因此master为了确保tablet server不再服务将其file删除，然后master将其tablets放入unassigned set中等待重新分派。如果chubby session过期了，master kill掉自己。
当master被集群管理系统启动时，执行以下步骤：
- 从chubby获取一把独一无二的master lock以防止并发的master实例
- 扫描chubby的目录获取可用的tablet servers
- 与每个可用的tablet server交流以获取tablets 分派信息
- 扫描metadata table以获取tablets的集合，并将unassigned tablets放入unassigned集合。
一个复杂的问题是如果metadata tablet未被分派，将无法进行扫描。因此在扫描前，master先将root table加入unassigned tablets中确保被分派，从root tablet中可以获得所有metadata tablets的信息。
当前的tablets set只有新增、删除tablet或者tablet split时才会变动，新增和删除master可以感知，split比较特殊，由tablet server负责，tablet server通过在metadata table中记录信息来提交这次split，并且提交后通知master。以防通知丢失，当master请求tablet server load这次split tablet的数据时，由于与metadata table中记录不一致，tablet server会再次通知master split的信息。
tablet server
sst数据和redo 日志持久化在GFS中。update之前会写redo日志，数据率先被写到memtable中有序存放，较早的数据存储在sstables中。恢复tablet时，tablet server从metadata table中读取其元信息，元信息中包含sst list和redo point的集合，server读取sst的信息到内存并通过回放日志来重构memtable。
对于写操作，server检查它是否符合写规则和sender是否有权限修改。权限通过读取chubby中的写权限列表获取。合法的修改先commit 日志，server通过group commit提升吞吐，日志提交后，数据被写入memtable中。
对于读操作，类似写先检查是否符合读规则和权限。读的结果由memtable和sst的数据merge后所得，memtable和sst都是字典序的，merge也会很快完成。
tablet在split和merge时不影响读写。
compaction
包含三种compaction: minor 、merge 和 major。
当memtable的size超出限制时，当前memtable被冻结并创建一个新的可写的memtable，冻结的memtable转换为sstable写入GFS中叫作minor compaction，minor compaction可以减少内存使用和推进日志回放位点减少恢复时所回放的日志量。
每次minor compaction都会新生成一个sstable，当sstables越来越多时，读操作由于要merge sstables会变得很慢，因此 server限制了sstable的数量，当到达上限时会执行merge compaction，将几个sstables和memtable一起合并成为一个新的sstable。
将所有sstable重写为一个新的sstable的merge compaction叫作major compaction。通过major compaction，Bigtable可以回收deleted数据的资源，也确保一段时间后deleted的数据消失(影响scan)，这对于敏感数据的查询很重要。
优化
一些优化细节描述。
locality groups
将经常一起访问的column families放在一起形成locality group，可以提升读效率，每个tablet的locality group存放在单独的sstable中。例如WebTable的page元信息可以放在一个locality group中，page的内存放在不同的group中，读取元信息的应用一般不会读取page内容。
另外一些参数可以被设定在group上，比如group可以被声明放在内存中，这种策略对频繁访问的小数据量很有效，例如metadata table。
compression
客户端可以指定localiy group中sstable的压缩方式，压缩单位为sstable的block，这样虽然每个block会额外使用一些空间存放压缩等信息，但是避免了在解压缩的时候解压整个文件。
许多客户端使用两遍压缩的方式，第一遍使用Bentley-McIlroy，一种公共字符串的压缩方式，第二遍使用一种快速的压缩算法，在16kb的窗口内查找重复的数据。这两种方式都是非常快的，压缩在100-200M/s，解压在400-1000M/s。在WebTable的实验中，使用两遍压缩方式来压缩web page文本，压缩率可以达到10，相比Gzip的3或者4是非常出色的，主要是因为webtable的行是按host排列的，相同host会有大量的相同文本。所以，对于许多应用来讲，如何选择row name来使得相似的数据聚集在一起对于提高压缩率获取更高的性能很关键。
缓存
为了提升读性能，tablet server使用两层缓存:scan cache和block cache，上层scan cache缓存sstable接口返回的kv对(行缓存？)，下层block cache缓存从gfs中读出的sstable blocks。scan cache对于重复读的数据比较有用，scan cache用于加速近期被读过的邻近数据的读取，例如顺序的读或者相同group不同column family中热点行的随机读。
bloom filters
bloom filter，常用做法，过滤访问不存在数据的读，避免读盘。
commit-log 实现
每个tablet使用单独的log文件会带来并发写多个gfs物理文件引起io问题，也会减小group commit优化的效果，因此bigtable使用每个tablet server的不同tablets写相同的物理文件的方式。
但是这种方式会使得恢复变得复杂，当一个tablet server失败后，这个server的tablets会分派给其它的servers，每个server一般会被分派小数量的tablets，当恢复这些tablets时，需要回放相关的日志，由于所有tablets的日志在一个物理文件上，这个物理文件会被读很多遍，每个server从中遍历查找符合自己的tablets的日志。为了避免这个问题，bigtable会在最初对日志按照<table,row name,log seq>进行排序，这样每个tablet的日志是连续存放的，只需要一次disk seek。
加速tablet的恢复
加速tablet server停止服务后tablet在其它server上的恢复时间。本质上是减少回放的日志量，通过两次minor compaction将内存中的数据全数刷盘，这样在恢复时可以不用回放一条日志。第一次minor compaction完成后，原tablet server停止服务，再做一次minor compaction，目的是将第一次minor compaction期间写入内存的数据全部刷盘。
利用不变性
除了memtable会有读写并发之外，其它部分都是只读的，单行的并发控制就变得简单，memtable使用对每行copy-on-write方式以使得读写可以并行操作。
因为sstable是不变的，移除delete数据的任务就由gc来做了。
sstable的不可变性也使得tablet split可以快速完成，相比为每个子tablet生成新的sstable， bigtable使用子tablet共享父tablet的sstable的方式。
结尾
论文最后做了性能评估和介绍了google内部使用bigtable的应用。不详述。
