缘起：BigTable

Google的三篇论文，Google File System，MapReduce以及Big Table可以说是整个大数据领域的三驾马车，这里，我们简单介绍下这三驾马车基本都是干哈的，重点解读下Bigtable: A Distributed Storage System for Structured Data。

2003年的GFS：GFS是一个可扩展的分布式文件系统，主要解决传统单机文件系统中磁盘小，数据存储无冗余等问题；

2004年的MapReduce：MapReduce是一个基于分布式文件系统（例如，GFS）的分布式计算框架，主要用来处理大规模数据集；

2006年的BigTable：BigTable是一个用来管理结构化数据的分布式存储系统，其本质上一个分布式KV存储系统。

BigTable是个啥？

BigTable是Google内部用来管理结构化数据的分布式存储系统，BigTable可以轻易地扩展到上千台机器，BigTable具有以下优点：

1. 适用场景广泛：从需要高吞吐量的批处理作业到低延迟的用户数据服务，BigTable都可以胜任。
2. 可伸缩：集群规模可水平扩展，BigTable部署规模可以小到3~5台，大到数千台，从而支撑不同的数据量；
3. 高性能：性能这个，想必不用我BB了吧，各位看官，你们怎么看呢？
4. 高可用：BigTable是主从结构，不会产生单点故障；底层是GFS，数据冗余备份；这还不具有高可用嘛？？？

与关系型数据库不同，BigTable并不支持完整的关系数据模型，也就是说，BigTable是一个NoSQL数据库，BigTable为用户提供了一个简单的数据模型，该模型主要有以下两个特点：

1. 客户端可以对数据的布局和格式动态控制；这点与关系型数据库有很大的差别，关系型数据库中，表创建完成后，表中存储的数据格式基本就固定了，列的数量及格式都无法再改变了，BigTable则不同，BigTable的列可以动态增加，完全由客户端控制。
2. 客户端可以推理底层数据存储系统中表示的数据的局部属性（有点不太理解）。

BigTable中的数据是通过行(row)和列(column)进行索引的，行和列可以是任意字符串。

客户端可以将各种形式的结构化和半结构数据序列化字符串，但BigTable只是将数据(Data)看做是未解释字符串(字节数组)进行处理。

客户端可以通过模式(Schema)参数来控制底层数据存储的位置，BigTable的模式参数允许客户端动态控制是从内存还是磁盘提供数据。

BigTable数据模型

让我们先来看看BigTable论文中是如何对BigTable定义的吧~

A BigTable is a Sparse, Distributed, Persistent Multi-Dimensional Sorted Map. The Map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.

BigTable是一个Map，即Key/Value键值对，这个Map有啥特点呢？稀疏的，分布式的，持久化存储的且多维度排序的。

对于Map数据结构来说，最常用的操作就是通过Key检索Value，BigTable中的Value是通过行，列，时间戳进行索引的。

# BigTable/Map的索引结构
(row:string, column:string, time:int64) ==> string

上图是为Web页面创建的BigTable表Webtable：

1. row为url地址的逆序；
2. 列族contents用来存储Web页面内容；
3. 列族anchor中存储Web页面中任何引用其他页面的锚点连接；

注意：BigTable中，每个Cell都有多个Version，每个Version对应一个时间戳。

Row Key

BigTable中的row key可以是任意字符串(大部分场景下，用户使用的row key大小为10-100字节，但BigTable当前分配大小为64KB)。

客户端每次读取/写入数据时，指定row key时，无论有多少列同时被读取/写入，该读写操作都是原子操作的。

BigTable底层是按row key的字典顺序存储的，给定BigTable表，其row key range是动态分区的，每个分区称为一个Tablet。

Tips：较小范围的row key数据读取会更高效，原因在于，这些数据读取时，只需要与很少的机器通信即可，效率较高。

Tips：客户端可以充分利用上述属性，从而加快其数据访问，获取更高的吞吐量。例如，在Webtable中，使用url的逆序作为row key，这样做的好处是，访问同一网站的页面时，这些页面通常会对应同一台机器，不需要与集群中多个节点通信，读取效率更高。

Column Families

多个Column Key构成的集合称为列族Column Families，Column Key是最基本的访问控制单元。

同一列族中的数据通常具有相同的数据类型(一般情况下，同一列族的数据会放在一起进行压缩存储)。

数据以列族(Column Families**)中某个列(**Column Key`)进行存储之前，必须先创建该列族才行。

Tips：通常情况下，一张BitTable表的列族得数量可能比较小(最多几百个)，而且在使用过程中，列族通常是不变的，相反的，每个表可以拥有无数个列，也就是说，每个列族都可以拥有无数个列，而且列是不需要提前定义的。

Column Key通常使用语法family:qualifier进行命名，列族必须由可打印字符构成，而列名可以由任意字符构成。

Timestamps

BigTable表中每个Cell包含同一数据的多个版本，这些版本通过时间戳进行索引，BigTable中的时间戳是64位整数。

时间戳可以由服务端生成，也可以由客户端生成，需要避免冲突的应用程序必须由自身生成相应的时间戳。

不同版本的Cell以时间戳降序的方式进行存储，以至于时间戳最近的版本最先会读取到。

为了避免Cell的数据版本过多，提供列族级别的配置项，以便BigTable自动删除旧的数据版本，一种是只保留最近的几个版本，另一种是只保留足够新的版本数据（例如，保留最近7天写入的数据版本）。

BigTable API

BigTable API提供创建/删除表和列族的方法。

BigTable API提供修改集群，表，列族元数据方法，例如，修改访问控制权限等。

客户端应用程序可以执行写入/删除BigTable中的值，根据row key查询值，迭代表中部分数据集等操作。

// Open the table
Table *t = OpenOrDie("/bigtable/web/wetable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
// 应用原子操作到Webtable中的r1上
Apply(&op, &r1);

客户端可以在多个列族上进行迭代操作，同时，BigTable提供了几种row, columns, timestamps构建方法来生成Scan实例。

Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
    printf("%s %s %lld %s\n",
    scanner.RowName(),
    stream->ColumnName(),
    stream->MicroTimestamp(),
    stream->Value());
}

另外，BigTable支持其他更复杂地操作数据的方式：

1. 支持单行(single-row)事务，可以实现给定row key时执行原子性的读-改-写操作。
2. BigTable提供了批量接口，但不支持多行的事务操作。
3. BigTable允许将Cell用作整数计数器。
4. BigTable支持在服务端地址空间内执行客户端脚本，该脚本为Sawzall语言（懵逼）。

BigTable构建基础

BigTable是基于Google的一些基础组件构建而成的。

BigTable使用GFS(Google File System)来存储日志(log)和数据(data)文件。

BigTable集群通常运行在一个共享的服务器集群中，BigTable的进程通常与其他分布式应用程序进程共享同一台服务器。

BigTable依赖集群管理系统来实现作业调度，管理共享机器上的资源，处理机器故障以及监视机器状态。

BigTable使用Google SSTable文件格式来存储内部数据，SSTable提供了从keys到values的持久化的，顺序的，不可变的映射，另外，SSTable中keys和values均是任意字节数组，另外，SSTable提供了根据key检索value以及根据key范围检索Value的功能。

SSTable由很多Block（每个Block默认大小为64KB，可配置的）组成，Block Index（存储在Block尾部）用来定位Blocks，当客户端打开SSTable时，会将Block Index加载到内存的。

从SSTable中检索指定key的values时可以通过Single Disk Seek实现：

? 首先加载Block Index到内存中，然后通过二分检索到key所在的Block，最后将磁盘中合适的Block加载到内存检索即可。

BigTable依赖高可用且可持久化的分布式锁服务Chubby，Chubby服务包含4个活跃的副本（节点），其中一个节点选举为Master并处理用户请求，当大多数副本副本正常运行且可以互相通信时，Chubby被认为是正常运行的。Chubby使用Paxos算法实现副本数据一致。

Chubby提供了包含目录和小文件的命名空间，每个目录或文件可以当成一个锁来使用，读取和写入文件时原子操作。

Chubby客户端会同步缓存Chubby文件，每个Chubby客户端会自动维护一个与Chubby服务的会话，在会话到期时，如果客户端无法通过Chubby服务更新到期时间，则会话会被中断，会话到期时，客户端会丢失所有所有锁且无法执行open操作。

Chubby客户端可以在Chubby文件/目录上注册回调方法，当会话到期或文件/目录改变是回调该方法。

BigTable使用Chubby完成各种各样的任务：

1. 保证集群内同时最多存在一个Master节点。
2. 存储BigTable表数据的启动位置。
3. 发现Tablet服务以及检测Tablet是否存活。
4. 存储BigTable表Schema信息(每张表的列族信息)。
5. 存储访问控制列表。

BigTable实现原理

BigTable实现主要包括三部分：

1. 客户端需要使用的库
2. 一个Master Server
   1. 分配Tablet到哪个Tablet Server上；
   2. 检测是否有Tablet Server新增或到期；
   3. Tablet Server负载均衡；
   4. GFS上垃圾文件回收；
   5. 处理BigTable表Schema修改（例如，创建/新增表列族）；
3. 多个Tablet Server：
   1. 每个Tablet Server维护一个Tablet集合（每个Tablet Server通常可以维护10到1000个Tablet）；
   2. 处理其负责的Tablet的读写请求，在Tablet太大时，负责Tablet的分裂；
   3. 根据集群负载情况，Tablet Server可以动态添加或移除。

Tips：与其他单Master分布式存储系统类似，客户端数据不会路由到Master，而是直接与Tablet Server通信，进而实现数据的读写。

Tips：很多BigTable客户端不需要依赖于Master定位Tablet信息，也就是说，大部分场景下客户端不需要与Master通信。

Tablet定位模型

BigTable使用类似B+树的三层结构来存储Tablet位置信息。

第一层：一个Chubby文件，该文件存储了root tablet的位置信息，由于该文件是Chubby文件，也就意味着，一旦Chubby服务不可用，整个BigTable就丢失了root tablet的位置，整个服务也就不可用了。

第二层：root tablet，root tablet其实就是元数据表METADATA Table的第一个Tablet，该Tablet中保存着元数据表其他Tablet的位置信息，root tablet很特殊，为了保证整个树的深度不变，root tablet从不分裂。

注意：对于元数据表METADATA Table来说，除了第一个特殊的Tablet来说，其余每个Tablet包含一组用户Tablet位置信息集合。

注意：METADATA Table存储Tablet位置信息时，row key是通过对Tablet Table Identifier和该Tablet的End Row生成的。

注意：每个METADATA Table的row key大约占用1KB的内存，一般情况下，配置METADATA Table的大小限制为128MB，也就是说，三层的定位模式大约可以寻址2^34个Tablets。

第三层：其他元数据表的Tablet，这些Tablet与root tablet共同构成整个元数据表。注意：元数据表虽然特殊，但仍然服从前面介绍的数据模型，每个Tablet也由专门的Tablet Server负责，这就是为什么不需要Master Server提供位置信息的原因，客户端会缓存Tablet的位置信息，如果在缓存中找不到指定Tablet的位置信息，则需要查询该三层结构了，一次访问Chubby服务，两次Tablet Server访问。

Tablet分配模型

每个Tablet只能分配给某个Tablet Server。

Master Server维护当前哪些Tablet Server是活跃的，哪些Tablet分配给了哪些Tablet Server，哪些Tablet还未分配，当某个Tablet还未被分配、且刚好存在Tablet Server有足够的空间装载该Tablet时，Master Server会向该Tablet Server发送装载请求。

BigTable使用Chubby服务来检测Tablet Server是否存活，当Tablet Server启动时，会在特定的Chubby目录下创建排它锁，BigTable会监控该目录来发现哪些Tablet Server存活，当Tablet Server丢失其排它锁时（例如，网络原因导致Tablet Server丢失Chubby会话）。

Chubby服务提供了非常高效地检测会话是否持有锁的机制，且不会导致网络拥塞。

当Tablet Server的排它锁文件存在时，Tablet Server可能会重新获取该锁，也就是，该锁是可重入的；排它锁文件不存在，则Tablet Server不会再次请求该锁，而是自杀。

Tablet Server进程终止是，会尝试释放锁，以便Master Server可以尽快地将其维护的Tablet分配到其他节点上。

Master负责检测Tablet Server是否还在为其他Tablet提供服务，并尽快重新分配其负责的Tablet到其他Tablet Server上。

问题是，Master是如何检测的呢？

Master会定期向每个Tablet Server询问其锁的状态，如果Tablet Server向其报告锁已丢失，或者Master最后几次尝试都无法访问服务器，则Master将尝试获取该Tablet Server对应的排他锁文件，如果可以获取，则说明Chubby处于活跃状态，而Tablet Server已死或者无法访问Chubby，Master可以通过删除其服务器文件来确保Tablet Server不再提供服务。一旦Tablet Server对应的排它锁文件被删除后，Master Server可以将先前分配给该Tablet SErver的所有Tablet移动到其他未分配的Tablet Server中。

为了确保Bigtablet集群不受Master Server与Chubby服务之间网络问题影响，如果Master的Chubbby会话到期，则Master会自动杀死自己，如上所述，Master Server设备故障不会更改Tablet分配到其他Tablet Server上。

当Master Server启动时，在其可以修改Tablet分配之前，需要先感知到当前Tablet分布才行，启动流程如下：

1. 获取Chubby文件(排它锁)，阻止并发实例化Master
2. Master会扫描Tablet Server排它锁的Chubby文件目录，拿到当前活跃Tablet Server信息
3. Master与所有Tablet Server通信获取其所维护的Tablet信息
4. Master会同时扫描METADATA表获取Tablets集合，在扫描的过程中，当Master发现了还未分配的Tablet时，Master将该Tablet加入未分配的Tablet集合等待合适的时机分配。

在第4不扫描METADATA表时可能会遇到一种复杂的情况：METADATA表的Tablet还未分配之前是不能够扫描它的。

步骤3扫描过程中，如果发现Root Tablet还没有分配，Master就把Root Tablet加入到未分配的Tablet集合。

上面这个附加操作确保了Root Tablet会被分配。Root Tablet包括了 所有METADATA的Tablet的名字，意味着Master扫描完Root Tablet后就得到了所有METADATA表的Tablet的名字了。

现有的Tablet集合只有在创建新表或者删除了旧表、两个 Tablet被合并了或Tablet被分割成两个小的Tablet时才会发生改变。

Master可以跟踪记录所有这些事件， 除了Tablet分割外的事件都是Master发起的的。

Tablet分割事件需要特殊处理，因为该事件是由Tablet 服务器发起的。

Tablet分割结束后，Tablet Server通过在METADATA表添加Tablet的信息来提交这 个操作；分割结束后，Tablet Server会通知Master。

如果分割操信息已提交，却没有通知到Master（可能两个服务器中有一个宕机了），Master在要求Tablet服务器装载已经被分割 的子表的时候会发现一个新的Tablet。对比METADATA表中Tablet的信息，Tablet Server会发现 Master要求其装载的Tablet并不完整，就会重新向Master发送通知信息，从而更新METADATA表。

Tablet Server

Tablet的数据持久化存储在GFS中，具体持久化流程如下图所示。

Updates操作会先提交到log(WAL)中，log主要用来进行数据恢复的。所有的Updates中，最近提交的那部分会存放在排序的缓存中，这个缓存称为MemTable，更早的Updates会存放在一系列SSTable中，这些SSTable本质上就是MemTablet刷盘生成的。

为了恢复Tablet，Tablet Server首先从MemTable中读取元数据信息，元数据信息包含组成该Tablet的SSTable列表及一系列重启点，这些重启点指向包含该Tablet数据的已提交日志记录，Tablet Server会把SSTable的索引读入内存，根据重启点恢复MemTable。

Tablet Server接收到数据写入请求时，Tablet Server首先要检查操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是根据从Chubby文件里读取出来的具有写权限的操作者列表来进行验证（这个文件几乎一定会存放在Chubby客户缓存里）。成功的修改操作会记录在提交日志里。可以采用批量提交的方式来提高大量小的修改操作的应用程序的吞吐量。

数据写如操作提交后，数据最终会被插入到MemTable里。

Tablet Server接收到数据读取请求时，Tablet Server会作类似的完整性和权限检查。一个有效的读操作在一个由一系列SSTable和memtable合并的视图里执行的。由于SSTable和memtable是按字典排序的数据结构，因此可以高效生成合并视图。

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

Compaction(合并)

随着数据的不断写入，MemTable占用的内存会不断增加。当MemTable占用的内存超过一定阈值时，内存中的MemTable会被冻结，切换为只读状态，同时创建一个新的MemTable，新的数据写入请求会写入到新的MemTable中，只读的MemTable会被转换为SSTable并最终写入底层存储系统(GFS)中，这个过程被称作小合并(Minor Compaction)。

小合并的作用主要有两个：

1. 降低Tablet Server的内存使用
2. 在Tablet Server意外宕机时，降低从WAL恢复MemTable时需要读取的数据量。

每次小合并都会生成SSTable，如果只有小合并，一直这么持续下去，那么，在Tablet Server接收到数据读取操作时，就需要充所有可能存在待检索row key的SSTable检索，然后合并所有更新操作，才能最终得到最新的value值。

为了避免上述这种情况发生，我们在后台周期性地执行大合并(Major Compaction)，大合并会读取几个SSTable，然后进行数据合并，合并结束后，即可将原先的SSTable文件删除。

优化及改进

前面一个章节描述了BigTable的底层实现原理，不过，为了满足用户所需的高性能，高可用和可靠性。在具体实现时需要各种优化才行。

Locality Groups

客户端可以将多个列族组成Locality Graph。每个Tablet会为Locality Group中的数据单独生成SSTable。

将通常不会一切访问的列族分离到单独的Locality Group中，可以实现更高效的数据读取。

例如，可以将Webtable中的页面元数据（例如，语言和检验和）放在同一Locality Group中，叶绵绵的内容在不同组中，当应用程序想要读取页面的元数据信息时，不需要读取所有的页面内容即可完成。

此外，还可以针对每个Locality Grou做相应的参数优化，例如，可以声明将某个Locality Group放到内存中。

内存中Locality Group对应的SSTable会被延迟加载到Tablet Server中，一旦加载完成，在不访问磁盘的情况下，实现Locality Group数据访问，此功能对于频繁访问的小块数据十分有用，Google内部用来存储元数据表。

Compression(压缩)

客户端可以控制是否压缩Locality Group的SSTables以及使用哪种方式进行压缩。

用户指定的压缩格式应用于每个SSTable Block（其大小可通过特定于局部性组的调整参数进行控制）。

通过单独压缩每个块会损失一些空间，但好处是可以读取SSTable的小部分，而无需对整个文件进行解压缩。

许多客户端使用两遍自定义压缩方案。第一遍压缩过程使用了Bentley和McIlroy的方案[6]，在一个大范围内使用前缀压缩算法对普通的长字符串进行压缩。第二遍压缩使用了一个快速压缩算法，该算法在一个16kb的小窗口中寻找重复数据。两种压缩过程都非常快，现代机器上，它们的编码速度为100-200 MB/s，解码速度为400-1000 MB/s。尽管我们在选择压缩算法时强调的是速度而不是空间缩减，但这种两遍压缩方案做得非常好。

Caching(缓存)

为了提升数据读取性能，Tablet Server使用两级缓存。

Scan Cache是Higher-Level缓存，该缓存会缓存SSTablet接口返回的Key-Value键值对。

Block Cache是Lower-Level缓存，该缓存会缓存从GFS中读取的SSTable Block。

Scan Cache对于需要频繁访问相同数据的应用程序来说是非常有用的。

Block Cache则对需要访问临近数据的应用程序来说非常有用。

Bloom Filters(布隆过滤器)

如上个章节中对BigTable底层实现原理描述的一样，数据读取操作最终是从Tablet的SSTable中读取的。如果SSTable不再内存中，最终就需要通过读取磁盘来实现数据读取了。通过为特定Locality Group的SSTable创建布隆过滤器，可以减少磁盘的访问次数。

布隆过滤器使得我们通过查询布隆过滤器来判断SSTable是否包含指定行/列的数据，对于某些应用程序，通过使用布隆过滤器可以显著降低Tablet Server的磁盘寻道次数。另外，使用布隆过滤器意味着对于不存在的行/列数据可以避免大量不必要的磁盘读取。

WAL(提交日志实现)

如果未每个Tablet都生成相应的WAL文件，那么GFS就需要同时写入很多文件，并发量很高，这种场景下，底层每个GFS服务器为了将日志数据写入不同的物理文件，会导致大量磁盘寻道，效率极低。此外，每个Tablet提交单独的日志文件也会降低批量提交优化性能，原因在与，由于分Tablet进行提交，对应的批量数据就回比较少。为了解决这些问题，我们将每个Talbet Server中所有的Tablet的数据写入日志追加到同一日志文件中，从而降低GFS的并发量，也降低底层GFS的物理磁盘寻道。

每个Tablet Server仅创建一个提交日志(WAL)文件，在正常操作场景下，可以大幅度提高性能，但数据恢复时却很复杂。

一台Tablet Server宕机时，其维护的所有Tablets将被转移到其他Tablet Server上，每台Tablet Server仅会装载少量原始Tablet Server的Tablet。为了恢复Tablet Server的状态，新的Tablet Server需要从原始Tablet写入的提交日志中重新应用该平板电脑的更新。然而，该宕机Tablet Server上的所有的Tablet的更新操作混合在同一个物理日志文件中。

一种方法是让每个新的Tablet Server读取完整的提交日志文件，并只应用它需要恢复的Tablet所需的条目。然而，在这种方案下，如果当前集群有100台机器从一台故障的Tablet Server上分别分配Tablet，那么日志文件将被读取100次（每台服务器一次）。

为了避免日志的重复读取，首先按照<table; row name; log sequence number>对提交日志条目进行排序。在已排序的输出中，特定Tablet的所有更新操作都是连续的，因此，可通过一次磁盘搜索和顺序读取有效地读取。为了并行排序，将日志文件按64MB切分，在不同的Tablet Server上并行排序。排序过程由Master协调，并指示每台Tablet Server需要从某些提交日志文件中恢复更新日志时启动。

WAL日志写入GFS有时会由于各种原因导致性能中断（例如，涉及写操作的GFS服务器计算机，或为到达三个GFS服务器的特定集合而穿越的网络路径遇到网络拥塞或负载过重）。

为了保护更新操作不受GFS延迟峰值的影响，每个Tablet Server实际上有两个日志写入线程，每个线程都写入自己的日志文件；这两个线程一次只有一个处于活动状态。如果对WAL日志文件的写入执行得很差，则日志文件写入将切换到另一个线程，提交日志队列中的更新操作将由新活动的日志写入线程写入。日志条目包含序列号，以便在恢复过程消除此日志线程切换过程中产生的重复条目。

加速Tablet恢复

如果Master将Tablet从一个Tablet Server移动到另一个Tablet Server，则源Tablet Server首先对该Tablet Server进行一次小合并。这种合并通过减少Tablet Server提交日志中未压缩状态的数量来缩短恢复时间。完成压缩后，Tablet Server停止为该Tablet提供服务。

在实际卸载Tablet之前，Tablet Server会执行另一次（通常非常快速）小合并，以消除执行第一次小合并时到达的Tablet Server日志中的任何剩余未压缩状态。完成第二次小压缩后，可以将Tablet加载到另一台Tablet Server上，而无需恢复任何日志条目。

总结

之所以写这篇博客，其实，是为了引出LevelDB，LevelDB又是啥呢？

LevelDB一个单机的开源的高效的KV存储系统，该单机KV存储系统，可以说是高度复刻了BigTable中的Tablet，而BigTable毕竟不是开源哒，我们通过Google的这篇论文，也只是能了解到BigTable的整体架构，但是具体细节就只能YY，或者去看HBase（参考BigTable实现的一个开源分布式列式数据库）的源码了。

不过呢，出于工作需要呢，目前对HBase需求不大，更需要弄懂单机KV系统是如何实现的，所以呢，我就屁颠屁颠地区看LevelDB了，相比于BigTable/HBase，仅仅是单机和分布式的区别了，而且，LevelDB代码量更小，更容易学习和掌控，接下来，我会通过一系列笔记来记录和分享自己学习LevelDB设计原理及底层细节的过程，希望大家多多关注呀。