本文共 5068 字，大约阅读时间需要 16 分钟。

Big Table算是非关系型数据库，数据的下标是行和列的名字，名字可以是任意的字符串。Bigtable将存储的数据都视为字符串，但是Bigtable本身不去解析这些字符串，客户程序通常会在把各种结构化或者半结构化的数据串行化到这些字符串里。和BDB的数据库类似，数据是通过key/value存储的，key.data是一个void *类型的指针，指向一个记录的查找关键字内容，而key.size指名key.data的大小；而data存储记录的内容，同样data也有data和size两个字段，指明存储记录的内容信息。

• 数据模型

Bigtable：是一个稀疏的、分布式的、持久化存储的多维度排序Map。

tablets：Bigtable通过行关键字的字典顺序来组织数据。表中的每个行都可以动态分区。每个分区叫做一个”Tablet”，每个Tablets大概有 100-200 MB，每个机器存储100个左右的 Tablets。Tablet是数据分布和负载均衡调整的最小单位。这样做的结果是，当操作只读取行中很少几列的数据时效率很高，通常只需要很少几次机器间的通信即可完成。用Tablets的机制后，可以获得很好的负载均衡。比如：可以把经常响应的表移动到其他空闲机器上，然后快速重建。

行，列，时间戳：用来标识一个记录，一个记录可以有多个版本，用时间戳区分，可用于垃圾回收

• Bigtable组件

.GFS：BigTable 是建立在 GFS ，Scheduler ，Lock Service 和 MapReduce 之上的，BigTable使用Google的分布式文件系统(GFS)存储日志 文件和数据文件。BigTable内部存储数据的文件是Google SSTable格式的。SSTable是一个持久化的、排序的、不可更改的Map结构，而Map是一个key-value映射的数据结构。SSTable是一系列的数据块（通常每个块的大小是64KB，这个大小是可以配置的）。SSTable使用块索引（通 常存储在SSTable的最后）来定位数据块；在打开SSTable的时候，索引被加载到内存。每次查找都可以通过一次磁盘搜索完成：首先使用二分查找法 在内存中的索引里找到数据块的位置，然后再从硬盘读取相应的数据块。也可以选择把整个SSTable都放在内存中，这样就不必访问硬盘了。

chubby：Bigtable使用Chubby完成以下的几个任务：确保在任何给定的时间内最多只有一个活动的Master副本；存储BigTable数据 的自引导指令的位置；查找Tablet服务器，以及在Tablet服务器失效时进行善后（5.2节）；存储BigTable的模式信息 （每张表的列族信息）；以及存储访问控制列表。如果Chubby长时间无法访问，BigTable就会失效。

链接到客户程序中的库：

Master服务器：bigtable中只有一个Master服务器。它负责为Tablet服务器分配Tablets、检测新加入的或者过期失效的Table服务器、对Tablet服务器进行负载均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外，它还处理对模式的相关修改操作，例如建立表和列族。（可以和分布式文件系统中的Metadata server类比）

Tablet服务器：Bigtable可以有多个Tablet服务器，并且可以向系统中动态添加或是删除Tablet服务器。每个tablet服务器都管理一个Tablet的集合（通常每个服务器有大约数十个至上千个Tablet）。每个Tablet服务器负责处理它 所加载的Tablet的读写操作，以及在Tablets过大时，对其进行分割。（可以类比分布式文件系统中的存储节点data server）

tablet表是可以动态分裂的，系统初始时，只有一个tablet表，当表增长到一定的大小时，会自动分裂成多个tablet。同时，master服务器会负责控制是否需要将tablet转交给其他负载较轻的tablet服务器，从而保证整个集群的负载均衡。

• tablet

chubby file存储在chubby中，记录了root tablet的信息，而root tablet则记录了所以tablets的位置信息，被成为metadata tablet，root tablet不会被分割。客户端可以缓存tablet的位置信息。读取tablet时采用了预取策略，每次从METADATA tablet中读取tablet地址信息时，会多读取几个tablet的地址信息。

在任何一个时刻，一个Tablet只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的Tablet服务器、哪些 Tablet分配给了哪些Tablet服务器、哪些Tablet还没有被分配。当一个Tablet还没有被分配、并且刚好有一个Tablet服务器有足够 的空闲空间装载该Tablet时，Master服务器会给这个Tablet服务器发送一个装载请求，把Tablet分配给这个服务器。

master是如何监控tablet的服务器的加入和退出的？答案是通过chubby跟踪tablet服务器的状态。当一个Tablet服务器启动时，它在Chubby的一个指定目录下建立一个 有唯一性名字的文件，并且获取该文件的独占锁。Master服务器实时监控着这个目录（服务器目录），因此Master服务器能够知道有新的Tablet 服务器加入了。如果Tablet服务器丢失了Chubby上的独占锁 — 比如由于网络断开导致Tablet服务器和Chubby的会话丢失 — 它就停止对Tablet提供服务。这个独占锁的管理是由chubby完成的。当Tablet服务器终止时（比如，集群的管理系统将运行该Tablet 服务器的主机从集群中移除），它会尝试释放它持有的文件锁，这样一来，Master服务器就能尽快把Tablet分配到其它的Tablet服务器。当然，master不能仅仅通过监控chubby服务器上指定目录的状态就断定一个tablet server是否宕机，它还需要进一步确认。 具体的步骤应该是（这部分是根据《bigtable探明Google分布式存储系统》推测的处理步骤，不一定准确）：1.master监控chubby服务器上的指定目录，发觉某个tablet server服务器对应的文件锁失效；2.master试图向chubby申请该文件的独占锁，如果master能够获得该锁，则说明是tablet server出现异常，于是将该tablet server视为失效节点处理；3.master删除相应tablet server在chubby上对应的文件；4.master将失效tablet server管理的tablet分配给其他的tablet server。当然，如果master也无法申请到相应的文件锁，则可能是master自身失效了，也可能是chubby服务器失效了。

master的启动步骤为：当集群管理系统启动了一个Master服务器之后，Master服务器首先要了解当前Tablet的分配状态，之后才能够修改分配状态。 Master服务器在启动的时候执行以下步骤：（1）Master服务器从Chubby获取一个唯一的Master锁，用来阻止创建其它的Master服 务器实例；（2）Master服务器扫描Chubby的服务器文件锁存储目录，获取当前正在运行的服务器列表；（3）Master服务器和所有的正在运行 的Tablet表服务器通信，获取每个Tablet服务器上Tablet的分配信息；（4）Master服务器扫描METADATA表获取所有的 Tablet的集合。在扫描的过程中，当Master服务器发现了一个还没有分配的Tablet，Master服务器就将这个Tablet加入未分配的 Tablet集合等待合适的时机分配。

tablet数据持久化到GFS系统中。近期的更新操作被放到一个排序的缓存中，成为memtable。旧的数据被放到SSTable中。为了恢复一个Tablet，Tablet服务器首先从METADATA表中读取它的元数据。 Tablet的元数据包含了组成这个Tablet的SSTable的列表，以及一系列的Redo Point，这 些Redo Point指向可能含有该Tablet数据的已提交的日志记录。Tablet服务器把SSTable的索引读进内存，之后通过重复Redo Point之后提交的更新来重建memtable。

当对Tablet服务器进行读操作时，Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个由一系列SSTable和 memtable合并的视图里执行。

当进行Tablet的合并和分割时，正在进行的读写操作能够继续进行。

随着写操作的执行，memtable的大小不断增加。当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一 个新的memtable；被冻结住memtable会被转换成SSTable，然后写入GFS。Bigtable有两类compaction，分别是major Compaction和非major compaction。由非Major Compaction产生的SSTable可能含有特殊的删除条目，这些删除条目能够隐藏在旧的、但是依然有效的SSTable中已经删除的数据。Bigtable循环扫描它所有的Tablet，并且定期对它们执行 Major Compaction。Major Compaction机制允许Bigtable回收已经删除的数据占有的资源，并且确保BigTable能及时清除已经删除的数据。

• 优化

bigtable使用了几个优化策略：

局部性群组：将无关的记录放到不同的群组中，将有关的记录放到同一个群组中，从而加速访问；

压缩：主要是从性能的角度考虑选取的压缩算法（采用两次压缩），但是空间压缩效果却非常好，主要是和bigtable的数据组织方式有关；

缓存：采用二级缓存，扫描缓存和block缓存，提升访问效率；

bloom filter：允许客户程序对特定局部性群组的SSTable指定Bloom过滤器，迅速确定查找的记录是否在目标SSTable中；

commit日志：更新操作都是以日志的形式写入持久化设备，从而保证所有的写都是顺序的追加写，明显优化了写性能，但是将恢复工作复杂化了。为了避免多次读取日志文件，我们首先把日志按照关键字（table，row name，log sequence number）排序。排序之后，对同一个Tablet的修改操作的日志记录就连续存放在了一起，因此，我们只要一次磁盘Seek操作、之后顺序读取就可以 了。为了并行排序，我们先将日志分割成64MB的段，之后在不同的Tablet服务器对段进行并行排序。这个排序工作由Master服务器来协同处理，并 且在一个Tablet服务器表明自己需要从Commit日志文件恢复Tablet时开始执行。每个Tablet服务器实际上有两个日志写入线程，每 个线程都写自己的日志文件，并且在任何时刻，只有一个线程是工作的。

SSTable不变性：除了SSTable缓存之外的其他SSTable是不变的。（疑问：这意味着，所有的SSTable要修改之前都必须读入缓存？从而减少采用日志写造成的读性能瓶颈。因为如果采用日志写，如果读的数据不在缓存中命中，则需要到持久化设置中访问文件，而持久化设置上的最新记录需要根据SSTable的数据和日志一起恢复，从而造成性能严重下降，因此，必须要做所有正在更新的记录都必须在缓存中命中。而所有在缓存中没有命中的记录，SSTable中的记录必须是最新的。）

• 基于bigtable的实现

hadoop的HBase，以及Taobao的hypertable

参考文献：

http://blog.sina.com.cn/s/blog_4ed630e801000bi3.html

http://database.51cto.com/art/201008/218065.htm

http://database.51cto.com/art/201007/209107.htm（本文是对这篇技术文章的摘录~）

转载地址：http://vsztb.baihongyu.com/