参考文献：Chang F, Dean J, Ghemawat S, et al. Bigtable: A distributed storage system for structured data[J]. ACM Transactions on Computer Systems (TOCS), 2008, 26(2): 4.
一、Bigtable简介
Bigtable是谷歌在其分布式文件系统GFS上设计的一个用于解决GFS无法对结构化数据进行访问与管理的结构化数据存储访问管理系统。基于HDFS的Apache HBase就是它的一个开源实现版本。谷歌将许多自己提供服务的数据使用Bigtable进行管理，例如Google Earth、Google Finance、Gmail等等。所以Bigtable不仅需要应对种类繁多的数据，在处理后端容量巨大的同时，还要保证对延迟敏感任务数据服务的及时性。同时由于谷歌众多的服务都由Bigtable提供支持，在系统设计中，除了上述的高适用性外，更要考虑系统设计的高容错性、高可用性以及可扩展性。
二、数据模型
首先要说明Bigtable中数据是以什么形式存储的。在Bigtable中，为了数据的高效管理与使用，数据被设计通过三个层次进行索引，它们分别是：
- 行 (rows)
行标识可以有任意不超过64KB的字符串组成，任何在同一行内的读或者写操作都具有原子性。在维护数据表的过程中，数据按照行关键字进行字典序划分，同时，根据行关键字还可以将数据动态地划分为一个个称作“子表” (Tablet) 的区间，存储在不同的子表服务器上做负载均衡。一般来说字典序相接近的两个行关键字下数据被划分在同一个子表服务器的概率较大，存取的效率也更高。 - 列族 (column families)
实际的数据表中，通常拥有较多的列，但是传统关系型数据库中按列为粒度进行权限管理，给数据管理带来了很大的难度。Bigtable将数据表中的列先划分为不同的列族，在列族中还可以再定义相应的列关键字，组成形如family:qualifier的列关键字，来存储一些相似的数据。列族的设计目的是在能够容纳同样数量的列数的同时，将相同类型的列聚集为一个族来统一管理，甚至可以统一进行数据压缩，方便了数据管理，也提高了数据存储的灵活度。 - 时间戳 (timestamps)
数据表中的数据通常有版本上的更替，为了防止版本间的冲突，Bigtable设计了时间戳维度，同行同列的数据按照时间关系被赋予一个时间戳，时间戳既可以由客户机应用程序自行设置，也可以由时间的毫秒数来决定以64位整数形式存储，并且时间戳按照降序排列，方便获取最新的一个版本。Bigtable支持两种自动回收旧版本的机制，一是保留最新的几个版本，另一种策略是仅保留一定时间内的所有版本。
所以，Bigtable中的每一个数据单元格式如下：
(row:string, coloum:string, time:int64) -> string
文中举了一个例子如图1所示，这是一个网页数据表，row值中存储着所记录网页的倒叙URL，即“com.cnn.www”。倒叙存放可以使同一个域名下的不同页面根据字典序存放在一起。“content:”是一个列族，但这个列族中没有其他的qulifier，下面存放着网页html的内容，这里的内容一共有三个版本，按时间顺序的时间戳为t3, t5, t6。“anchor：”为第二个列族，这个列族中有两个不同的column keys，分别是“cnnsi.com”和“my.look.ca”，记录着所有连接到row值存储页面的所有页面，而对应列下存储的就是这些页面中连接到row页面的anchor。
三、系统组成
本章将会介绍Bigtable系统中的几个关键组成部分或者支撑技术。
- 主服务器 (master)
主服务器上不存储子表，也不是用来提供表定位信息的，而是主要负责子表服务器的分配、负载均衡，监控子表服务器的状态，当子表服务器的租约到后仍然没有回应则要重新安排新的子表服务器来代替，同时当子表服务器的所存的子表过大的时候还要分配新的子表服务器进行负载均衡。同时，主服务器还要负责处理表模式更改、列族增加和GFS上垃圾回收等任务。 - 子表服务器 (tablet server)
Bigtable在存储表的时候会将表划分为一个个子表来进行存储。子表服务器上存储着子表信息，由于为了减小主服务器的负载，数据请求不会经过主服务器，子表服务器还需要直接响应客户机对字表服务器上存储的子表的读和写操作。在所存储的子表过大的时候需要对子表进行切分操作。需要注意的是，子表服务器也不是直接存放数据的，数据只是存放在GFS中，然后由子服务器来进行分片管理 - 客户端的库
客户端的库用于缓存子表的位置，只有当没有缓存子表的位置或子表的位置出错的情况下，客户机才会启动子表定位。 - GFS
Bigtable底层所使用的分布式文件系统 (Google File System)，存放着数据文件和日志文件。 - SSTable
Bigtable内部使用的文件格式，提供不变有序的键值映射，键与值都是用任意的字节串组成的。SSTable内部包含一系列默认大小为64KB的块 (block)，并将这些块的索引值存放在文件末尾。每一个子表可能对应着多个SSTable文件。 - Chubby
Chubby是Google设计的一个锁服务，每个Chubby服务都利用Paxos算法保留了5个副本，其中一个作为主副本提供服务。Chubby提供了一系列的目录与文件，每个目录与文件都被当成“锁”来使用以保证，使用Chubby服务的客户机需要保持和Chubby服务之间的会话，并维护一个租期的关系，超出租期如果Chubby没有收到客户机的续约申请，那么客户机就会失去在Chubby服务中的所有锁。
Chubby在Bigtable中有非常重要的作用，以至于一旦Chubby服务失效，整个Bigtable就无法工作。无论是在主服务器的确定、子表服务器定位、子表服务器分配、表的权限控制等等方面都运用到了Chubby服务。这些运用将会在后面的章节中提到。
四、子表操作
本章将会介绍子表的定位、子表分配以及子表的读写操作。
子表定位
Bigtable将子表按照三层关系进行组织，三层关系如图1所示：第一层，存储在Chubby file中，里面包含了Root tablet的位置信息。
第二层，根子表 (Root tablet) ，元数据子表 (METADATA tablets) 中的第一个子表，它存储着元数据表里其他子表的位置信息，根子表随着大小的增长是不会被分割的。
第三层，原数据子表 (METADATA tablets) ，保存其他用户数据表的子表信息。
在查找子表的时候，客户机首先会检查自己的库，看是否已经有这个子表位置的缓存，如果存在这个缓存且这个缓存还有效，就会按照这个位置去获取子表信息。如果这个子表的缓存信息错误，那么客户机将会递归向上一层的子表服务器进行查询。若缓存为空，则客户机将会从Chubby file开始获取根子表的位置，查询根子表查寻相应元数据子表的位置，再在元数据字表中找到需要的数据子表的位置，完成完整的一次询问的查找。子表分配
前文中有提到主服务器master主要负责监控子表服务器状态以及子表的分配。主服务器需要通过Chubby确认每个子表服务器是否还在正常工作，跟踪子表都分配给了哪些子表服务器以及哪些子表还没有被分配。当一个子表服务器启动的时候，它会在Chubby特定的目录下建立一个自己的文件并获得互斥锁，主服务器通过文件来监控存在哪些子表服务器，通过周期性尝试获取这些文件的互斥锁来确认这些子表服务器是否还在正常工作。当子表服务器失去与Chubby的连接后，就会失去这个互斥锁。但是只要子表服务器上的数据还存在并且Chubby相应文件还存在，它还会不断试图请求会这个互斥锁。一旦主服务器获得了这个互斥锁，它就会删除这个文件，导致子表服务器的最终停止。而子表服务器主动停止服务的时候，也会释放这个互斥锁，以便主服务器更快意识到这个子表服务器的退出。
当主服务器和Chubby连接被断开后，当前的主服务器会主动关闭自己，这时候系统就会重新选择一个新的主服务器出来。主服务器启动时，会首先获取一个Chubby上的master锁以防止其他服务器同时成为主服务器；然后新主服务器会扫描Chubby的特定目录尝试获取互斥锁来获得当前正在工作的子表服务器；之后再询问每个子表服务器被分配的子表；最后再统计METADATA子表中还未被分配的子表，准备将其分配 (若元数据子表还未被分配，则需先将根子表加入到待分配的子表集合中) 。
子表的读写操作
读写操作的基本示意图如图3所示。其中SSTable Files是已经持久化在GFS中的数据，memtable是还未存入SSTable Files的数据缓存，tablet log是写操作的日志，用于子表服务器启动时从重做点开始恢复子表。读操作首先要经过权限的验证，通过验证后，由于数据的不同版本分布在位于内存的memtable中以及位于GFS的SSTable Files中，所以需要事先进行合并。
写操作也类似，首先要经过权限验证，然后使用日志先行 (WAL) 的方式先提交到日志中，然后再把变更插入到memtable中。
子表压缩
每当进行一次写操作，新写的记录不会覆盖原有记录，而是被添加到memtable后面，当memtable的大小达到一定程度的时候，就要用新的一个memtable来代替原来的memtable并把原来的table保存为一个SSTable文件。这个操作过程叫作minor compaction。但是minor compaction会逐渐增加SSTable的数量，会影响文件维护的效率。因此需要周期性的对SSTable文件和memtable进行合并，这个操作叫作merging compaction。
还有一种特殊的merging compaction叫作major compaction。这种compaction会把所有的SSTable和memtable都merge到一个单独的SSTable中，并且与前两种方法不同的是，major compaction将会删除掉那些已经无效的数据，节省集群空间，释放资源以适应巨大的容量需求。
五、总结
这篇文章介绍了谷歌在GFS上搭建的结构化数据表存储系统Bigtable，本篇笔记首先在其使用的数据模型、系统组成方面进行的简单的介绍，然后分别详细讨论了在Bigtable上如何进行数据定位、数据分配以及数据读写操作。讨论了主服务器如何产生，当主服务器以及子表服务器出现问题后应该如何将正在管理数据移交出去，新启动的服务器应当如何加入到系统中并获得数据。还提到了Bigtable底层如何维护与压缩保存的数据文件。虽然这里面每个问题谷歌设计的方法看似都并不复杂，但是通过一个个简单的模型，我们体会到了一些经典模型，是如何被运用到实际系统中的，是如何满足谷歌所提供的数据服务的大容量、低延迟的要求，这也激发了我们进一步对底层理论的了解与研究的兴趣。