Bigtable Google论文阅读笔记

0. Abstract && 1. Instruction

• bigtable是一个用于结构化数据的分布式存储系统（TODO 为什么是结构化？）
• 很强的应用性：从专注于低延迟的面向用户的请求处理，到专注于吞吐量的批量分析处理
• 可扩展性：可扩展到PB数据量级，数千台服务器
• 高性能、高可用
• 类似于数据库：it shares many implementation strategies with databases.
• 内部描述：数据用row\column name来做索引，可以是任意字符串。其中存储的data是一个不做解释的字串，由client来决定反序列化的方法。

2. Data Model

是一个稀疏、分布式、持久化的多维sorted map，根据row key\column key\timestamp作为索引，value是一个无指定含义的byte数组。论文中给了一个形象简单的描述：
(row:string, column:string, time:int64) → string
以下分为几个概念详细解释：

[row]

• 可以是任意字符串，10~100bytes是常见长度范围，上限是64KB。
• 任意row数据的读写是原子的（不用管读写了row上的几个column都是原子的）
• bigtable数据按row key字典序（lexicographic order ）存放，一张表的row范围是动态分区的，每个row range也叫一个tablet，是分布式和lb的一个最小单位。所以小范围的读取一个row的区间通常很快，通常只需要和少部分机器交互。
• 客户端可以利用这个特性设计row值，以读取连续的一片区间来提高效率

[Column Family]

• Column key组成的一个集合叫Family，组成了access control的基本单元。存在一个ColumnFamily中的数据通常是一个类型的，bigtable把它们压缩在一起。
• column family先创建出来以后，column才能存进去。我们期望一张表中的family数量尽可能少（最多上百个），并且很少发生变动。
• column key的格式是family:qualifier。其中family name必须是printable的，但qualifier name可以是任意字符串。
• Access control and both disk and memory accounting are performed at the column-family level. (TODO access control是什么？控制客户端访问权限？)

[Timestamps]

• 每个cell可以有多个版本的数据，版本以timestamps表示是一个64位整数。可以由bigtable设置为当前毫秒时间，也可以由客户端明确定义这个值。一个cell的不同版本是按逆timestamp序存放的。
• 为避免有版本的数据过于繁重，提供了两种按column-family划分的设置，bigtable会根据这个对版本做自动的垃圾回收。（可以指定最后的n个版本保留，或足够新的的版本保留如七天内）

3. API

• Bigtable API提供增删table\column family，更新cluster\table\column family metadata的函数。可以删或改column value，或scan一个column family等。此处略过不记。
• 可以支持单一row上的事务（不支持跨row）
• 可支持将cell视为一个整数counter（TODO 这有啥特别的？）
• 可执行由client提供的脚本（用一种特殊的Sawzall语言）现在不支持写数据但是可以做数据的过滤、整合等操作。
• Bigtable可以用来做Map Reduce（TODO 可以了解一下）

4. Building Blocks

Bigtable是建立在google其它几个基础设施上的：

• Bigtable使用了GFS（Google File System）来存储log与data文件；
• Bigtable集群通常跑在共享资源的机器上，不是独享的机器；

内部使用Google SSTable文件格式来存储数据:

• SSTable是一个有序、持久化、不可变的map，KV均是byte数组，支持根据key查找按key range查找。 每个SSTable文件包含一系列的blocks，每个block标准64KB但可配置。
• SSTable block有一个index用于定位，存放在SSTable的尾部，打开SSTable文件的时候会将index载入内存。用二分在内存中定位index对应的block所在的文件位置。（也可选：把整个SSTable载到内存里，以避免后续读取文件）

Bigtable用了一个高可用、持久化、分布式的锁服务Chubby，使用了Paxos方法（TODO 可以简单了解一下Chubby怎么实现的，类似于zookeeper）。Bigtable用它实现了元数据管理，是强依赖（Chubby不可用导致Bigtable不可用）

5. Implementation

Bigtable可分为三个主要部分，一个lib连向所有的client，一个master server，还有很多的集群中的tablet server（TODO 是什么？）可以动态的增减以适应负载：

• master server负责分配tablet server、探测到新增与过期的tablet server、负载均衡、垃圾回收等。还负责schema change如table\column family变化。
  *每个tablet server管理着多个tablets（十到千个），处理读写请求到已加载的tablets上，同时也负责分割已经过大的tablets。
• 与其它单master的分布式系统一样，client不经过master而是直连到tablet server上读写。大部分client也不需要与master交互，不需要依赖master获得tablet位置信息，所以master的负载很轻。
• A Bigtable cluster stores a number of tables. Each table consists of a set of tablets, and each tablet contains all data associated with a row range
• 初始时一个table只有一个tablet，随着其容量变大而自动分裂，一个tablet默认100~200MB大小。

5.1 Tablet Location（比较重要）

使用了一个三级的类似B+树的结构存储tablet location信息：

1. 首先通过Chubby找到一个root tablet
2. root tablet存储了所有METADATA的tablet位置（其自身就是第一个METADATA表但它是永不自动拆分的，防止这个关系树超过三层）
3. 每个METADATA表包含了一部分user table的位置，存储一个tablet的位置在一条row key上（key格式是table名与它的end row）

每个row按1KB计算、每个metadata tablet 128MB来算，三级结构共可以定位2³⁴个tablet，即存储2⁶¹字节的数据。实际上root table不会拆分大小无限，所以理论上可以存储无限大小的量。
client缓存了tablet位置，若不知道位置或者访问发现miss，client会递归的往上找,至多会找到Chubby这一层，再往下递归。即是说最多需要六次网络访问来定位。
另有优化：当访问metadata表时，会让client读取多个tablet位置，以降低常见场景下的开销。

5.2 Tablet Assignment（非常重要）

• 同一时间点下，每个tablet只会分配给一个tablet server。
• master会维护一个active tablet server集，以及tablet的分配情况。如果tablet未分配且有一台active tablet server有足够的空间，master会发送一个tablet load request命令给这台tablet server以完成这次分配。
• Bigtable用chubby来维护tablet server信息。当一个tablet server启动时会创建一个特定名字的Chubby目录并获取一个独占锁，master监控到这个目录就发现了这台tablet server。
• 同样如果tablet server失去了独占锁，就停止维护它的tablets（例如丢失了与Chubby的网络连接）tablet server会在失去锁后，重新尝试获取目录上的锁，如果无法再获得锁了就会将自己杀掉。无论何时一个tablet server关闭时会尝试释放锁，使master能更快的重新分配对应的tablet。
• master有义务监控好这些tablet server，如果tablet server不再维护它们的tablets，master负责重新分配这些无主的tablets。master定期询问每个tablet server的锁占有情况，如果一个tablet server失去了它的锁或者master几次无法访问它，master会尝试占掉这个tablet server对应文件的锁。如果能占有，说明Chubby没问题而tablet server有问题，master删掉这台server对应的文件，并将对应的tablets置为unassigned。如果master拿到的chubby session过期了，会关掉自己以保证Bigtable稳定。
• 当master启动时：向chubby占有一个唯一的master文件锁（防止多个master）；扫描Chubby目录下的active tablet servers；与每个server通信获得所有的已分配tablet；扫描METADATA得到全部的tablet，并标出unassigned tablets。（root table有必要的话要在扫描METADATA前标为unassigned）
• 一个tablet server分割一个tablet，记录新tablet信息到METADATA表中，然后周知到master。如果周知失败，也会有办法在master下一次要求load tablet时发现（TODO 没理解怎么发现和解决）

5.3 Tablet Serving

• 用GFS持久化tablet数据：写操作记录到commit log，较近的改动维护在memtable中（在内存里的sorted buffer），较老的改动存于sstable中。（TODO server如何把tablet加载出来，即如何加载sstable和memtable）
• 当tablet server收到写操作时，将验证请求格式正确并对来源鉴权。（通过读一个特定的chubby文件来确认权限，chubby client能缓存）确认请求合法后将写入commit log（有一些batch commit来优化），并随后插入memtable。
• 当tablet server收到读请求时，也会做同样校验，然后从sstable\memtable合并得到一个结果。因为这两块都是字典序的，结果的合并会很高效。
• 在tablet合并分割的时候，读写操作还是能继续的（TODO 为什么）

5.4 Compaction（非常重要）

minor compactiin：

• 当写操作足够多，memtable的大小达到了阈值，会触发一次minor compaction。此时冻洁老memtable并创建一个新的memtable，老memtable被转换为一个SSTable写入GFS之后被抛弃。这个过程中读写操作不会被堵塞。
• 目标是缩小tablet server的内存使用，减少服务启动或重启时读取commit log的量。（memtable在内存中所以随着服务关闭而消失了，需要重新从commit log中读取）

merging compaction：

• 由于每次minor compaction创建一个新SSTable，在持续运行一段时间后读操作需要合并未知数量的SSTable，因此需要周期性的执行merging compaction。
• merging compaction读取memtable与若干个SSTable，产出一个新的SSTable，这些老数据与文件会在compaction完成后被废弃。

major compaction：

• 如果merging compaction将所有SSTable与memtable合并，就称之为一次major compaction。
• 非major compaction留下的SSTable里，可能包含已删除的数据
• Bigtable定期对它的tablets做major compaction，将其上的全部SSTable合成一个。以保证已删除数据完全消失，取回已删除数据占有的空间，同时这个操作对那些敏感数据也是很重要的。

6. Refinements

本章描述一些Bigtable提高性能、高可用性、可靠性的改进。

6.1 Locality groups

bigtable client可以将多个column family汇总为一个locality group，每个tablet中会为localitiy group创建一个单独分离的SSTable。将通常不同时访问的column family分到不同的locality group中可以提高性能（TODO 为啥是由客户端指定group？为啥能提高性能，是因为一次只能读取一整个column family吗？）
还可以做一些参数设置，把一些locality group设置为in-memory的，会延迟加载但一旦加载就在内存中不再需要从磁盘加载，适合量小而访问频繁的数据。Bigtable内部就把METADATA设置为in-memory的。（TODO 能配置一个column family在一个locality group里？）

6.2 Compression

client能控制一个locality group的SSTable是否要压缩。大多数client使用一个两步 传统压缩格式方式，第一步使用Bentley and McIlroy’s scheme跨大窗口找相同的长字串，第二步使用快速的压缩方法在16KB的窗口间找重复字串。可以在现代机器上达到压缩100_{200MB/s，解压400}1000MB/s（06年的论文数据）。
字典序相近的row存储的数据如果类似，可以在单版本达到非常高的压缩率（10 to 1），多版本的话压缩率会更高。

6.3 Caching for read performance

tablet server使用两级缓存提高读性能：

• The Scan Cache： high-level cache，将SSTable返回到kv对缓存到tablet server的代码中。适用于热key。
• The Block Cache：lower-level cache，缓存从GFS中读出的SSTables blocks。适用于频繁读取一个范围的数据。

6.4 Bloom filters

client可以指定一个locality group对应的SSTable做bloom filter，其帮助查询一个SSTable是否包含指定的row\column，使用很小量的内存，极大的降低了读操作所需的磁盘访问次数，使不存在的数据读取无需触达磁盘。

6.5 Commit-log implementation

由于多个tablet的commit log写入不同的日志文件，会便得文件seek操作非常多降低效率，所以Bigtable将多个tablet的commit log写入同一物理文件。
效率有了极大提升，但recover变得更困难。当一个tablet server挂了，它维护的多个tablet分发给其它若干个tablet server来重新载入，但这些tablet混合写在一个物理文件。如果读取整个commit log就会浪费io。
Bigtable会首先将commit log按<table, row name, log sequence number>的顺序重排一遍，排序后同一tablet的数据是连续的因此可以只做一次文件seek与一次数据的连续读取。这一步由master来协调，将commit log分割成64MB的文件给每个tablet server分别排序，并发执行。
为了防止写入GFS网络尖刺，每个tablet server同时有两个线程写入日志，同一时间只有一个生效。如果一个线程时延很可悲，就会切到另一个。由于每条log包含一个号码，所以不用担心重复记录。（TODO 两个线程写入不同的GFS吗）

6.6 Speeding up tablet recovery

如果master将一个tablet转移到另一server：

• 原server会对此tablet做一次minor compaction，（TODO 为啥只做一次minor？一个tablet有可能有巨多SSTable吧？）以降低这台server的commit log中未compact状态的数量。
• 此后server停止维护此tablet，在上传前再做一次通常很快的minor compaction，来消除第一次compaction过程中产生的uncompacted state的commit log。
• 两次compaction完成后，另一server直接加载此tablet，不再需要考虑commit log中的数据。

6.7 Exploiting immutability

• 由于SSTable是不变的，读取时不需做同步，跨行并发访问很快（TODO 为什么是跨行访问很快？）
• 唯一可变的数据结构在memtable中，为了防止读写memtable产生竞争，我们对每一个row做了COW并且允许读写同时进行（TODO 为什么是做COW？读写能同时进行为什么有竞争？需要了解memtable的实现）
• SSTable全记在METADATA表中，由master用mark-and-sweep方法做垃圾回收。
• 由于不变可以让分裂的子tablets共享parent的SSTable，（TODO 什么是child tablet？）

7. Performance Evaluation

相关性能测试

【单机】

• random read最慢，因为加载一整个64KB的SSTable Block，却只读取其中1000-byte的数据。只能达到1200qps
• random read (in-memory) 单机能达到10811qps
• random write, sequential write较快，因为请求先写到commit log中批量提交。random write与sequential write没有显著的区别因为都是写到一个commit log里。
• Sequential reads性能较好，加载出64KB的block是连续数据，可以用于64次读取。
• Scan性能最好，因为一片内容直接返回使得RPC往返次数减少。

【Scaling】

• random read (in memory)：在500台tablet server时QPS可以乘上300倍。因为每台机器的cpu是瓶颈，所以qps随着机器变多线性增长。
• 但大多数其它操作，随着机器从1~50增加，每台机器的qps有显著下降。是因为不平衡的加载，这个难以优化主要有两个原因：1. 限制rebalancing次数以减少tablet的移动（tablet移动会导致短时间内不可用）2. 加载的东西是我们benchmark程序随时间而变化的。
• random read下降的最为明显，其实是因为读取1000-byte数据需要读取整个block，即需要64KB的网络传输，使得机器越多qps越低。

8. Real Application

截止2006-08，有388台非测试的Bigtable集群，约24500台tablet server。其中14个较忙碌的集群有8069个tablet server，能够扛住1.2 million qps，入流741MB/s，出流16GB/s。（TODO 看起来也不高啊？一个tablet server容器需要多少资源，了解后可以和字节内的情况对比一下）

上图展示了一些Google现在使用中的产品，一些面向用户一些面向批量处理

• Google Analytics用Bigtable记录了用户点击表约200TB，压缩后是原大小的14。另有一张分析张约20TB，定期用map-reduce从原始表中产出，压缩为原来的29%。这个系统的吞吐量瓶颈是在GFS上。
• Google Earth在每一个row上存储一片地理区域，row的命名使得相邻位置存在一起。column family下有非常多column，是稀疏的（TODO 不确定bigtable的内部存储方式受到column family与row的什么影响）压缩率不高，因为图片不能再压缩了。
• Personalized Search：用户可搜索个人在google的历史使用记录包括搜索、点击、观看图片等。每个user_id有一条row，每种动作对应了一个column family

9. Lessons

在设计与实现、优化Bigtable的过程中收获到的经验得知：

1. 分布式系统是脆弱的，如：网络分区, 内存与网络损坏, large clock skew, hung machines, extended and asymmetric network partitions, 依赖系统的bug如Chubby, 超过了GFS使用配额, 意料外的硬件维护等等。因此我们做了：

• 更改协议格式，在rpc协议上新增了checksum机制
• 不再猜想Chubby只会返回约定的错误

2. 不要急于加新feature，除非确定使用方想要怎么使用。（如一开始给Bigtable API提示了事务，但后来发现大多数应用只需要单row操作原子）
3. 做一个好的系统级监控是很重要的。比如改造了rpc调用系统，新增了很多日志来帮助查清慢操作、锁竞争、无法访问METADATA等问题；比如把每个Bigtable集群信息录入到Chubby上方便观察集群状态。
4. 最大的收获：意识到了the value of simple designs。给我们在Bigtable的编码和调式中给予了极大的帮助。例如我们为了高可用设计的tablet-server membership protocol过于复杂，且依赖于Chubby的一些特性，在上面花费了过多的时间来调试边缘条件，不仅要调Bigtable还要调试Chubby。最终还是放弃了这个protocal转而设计了一项更简单的。

10. Related Work

• Boxwood项目有很多组件与Chubby\GFS\Bigtable重叠，但其目标是提供一些更low-level的功能，如使用Boxwood来实现一个数据库等等。
• 还有一些提供分布式存储的project如CAN\Chord\Tapestry\Pastry，这些project解决了对Bigtable不会出现的问题，如高度可变的带宽、不受信任的使用者、频繁的配置变更等等非Bigtable的目标问题。
• 从提供分布式数据存储给开发者的角度来看，用分布式B树或者hash表来提供一个KV是有限制的。我们选型的数据结构比KV能提供更丰富的功能，且依然保持高效、透明。
• 一些db公司开发了并发的能存储大容量数据的db，Oracle’s Real Application Cluster database、IBM’s DB2 Parallel Edition，这二者都提供了有事务的关系模型。
• Bigtable locality group实现的相似压缩、读性能优化，吸收了其它列存储（而不是行存储）的数据库经验。如C-Store、Sybase IQ、SenSage、KDB+、the ColumnBM storage layer in MonetDB/X100。locality group不支持Cpu缓存级别的优化，可参考来自于Ailamaki的相关讨论。
• Bigtable memtable+sstable的设计类似于LSM树，都是写操作先存内存后落磁盘，读操作合并内存与磁盘上的数据。
• Bigtable与C-store都有以下特性：shared-nothing architecture（TODO 是什么？）；都有两个存储结构一个存储近期数据一个长期数据，用一个机制将其做转换。二者最明显不同在于：C-store对外接口是关系型数据库，且优化了读操作；而Bigtable提供更像底层的读写接口，对读写性能都很良好。
• (1) we do not consider the possibility of multiple copies of the same data, possibly in alternate forms due to views or indices; （TODO 什么意思？）(2) 我们让用户告知哪些数据在内存，哪些在磁盘而不是由Bigtable动态决定；(3) 我们没有复杂的查询语句执行需要优化。

11. Conclusions

Bigtable是一个Google开发的分布式存储结构化数据的系统，Bigtable集群从2005.04开始投入产品使用。之前花了七人年来设计与实现这个系统，到了2006.08已有超过六十个产品使用。
虽然Bigtable提供的特殊API让很多人不大有信心，尤其是习惯了关系型数据库的人。但实际在google产品使用中证明了，Bigtable是可以在实践中达到很好的效果的。我们还正在继续开发Bigtable的feature，例如：二级索引、跨数据中心的多备份master的基础设施。
最终我们发现，实现一个google自己的数据存储有显著的收益。我们有很大的灵活性来设计自己的数据结构，并且因为我们控制着Bigtable的实现，当出现瓶颈和低效时，我们可以更改Bigtable内部的组件依赖。

12. Acknowledgements

一些致谢