大数据那些事(11):复活的LSM-Tree--BigTable的系统实现

BigTable是一个非常复杂的系统，发表的论文写得并不是很清楚。所幸Google开源了LevelDB这个Key-Value Store。这个项目的作者是Jeff Dean和Sanjay Ghemawat，被认为很大程度上重复使用了BigTable在单个节点上的实现，故而使得我们可以通过对LevelDB的代码的阅读获得进一步的了解。

在BigTable的实现上，一个BigTable的cluster有一个client library，一个Master server和很多个的Tablet Server组成的。按照论文的说法，一个大的sorted BigMap会被分成大小大致在100MB到200MB的tablets，而这些tablets则由若干个Tablet Server们来负责。Tablet Server会对tablet进行切分和合并。如果一个tablet超过了200MB则会被分成两个更小的tablet，反之亦然。

系统运行过程中的Tablet server的数量不是固定的，可以根据实际上的工作负载来增加或者减少，所以我们需要理解在这里Tablet server并不存储实际的文件，而是作为一种service和proxy来访问存在Google File System里的实际的tablet。

和Tablet server不一样的是，Master Server始终都存在。Master server存在主要是把tablet分配给Tablet server，增加或者减少Tablet Server，并且负责去平衡不同的Tablet server的load。如果用户要创建一个新的“Table”（Map），或者对已经有的Table做改动的话，譬如增加新的column family等，都是通过Master server来完成的。但是Master server本身并不负责对任何Tablet 的管理。

和大家直观上想象的不同，当一个client要访问BigTable的时候，client并不需要和Master server进行交流。这就保证了Master server的load并不是很重。那么，client是怎么样实现对BigTable的访问的呢。这需要用到Chubby。 Chubby是一个highly distributed lock service。可以认为开源Zookeeper是一个Chubby的copycat。具体的情况请阅读 The Chubby lock service for loosely-coupled distributed systems。Chubby实现的是一个类似文件系统那样的目录结构。使用者可以访问这些文件来获得对被访问对象的锁。按照BigTable论文的说法，Chubby的用处有很多处，包括对Tablet的定位，对Tablet server的监控等等。

对我们来说最重要的是了解client怎么样对数据进行操作。这个操作大致上是要通过访问一个三层的结构，其中第一层是一个Chubby file。通过Chubby file可以找到一个叫做Root Tablet的位置，Root Tablet下一层则是所有的metadata tablets。有一点非常的特别，Root Tablet从来不会被partition。所以一般来说client需要通过访问一个Chubby文件，一个Root Tablet和一个Metadata Tablet的三层结构去定位到对应的data。Client 会cache住它找到的metadata，但是cache并非必须。只要Chubby service是活着的，通过这个三层访问总是可以定位到对应的data的tablet的。通过Chubby，Master不需要承担任何datat活着metadata的发现。故而Master server的负担很轻。

Metadata的tablet是怎么样实现的，在论文里面基本上没有仔细谈及。最详细描述基于下面的论文原话： The Meadata Table store是跳河locationof啊tablet under a row key that is en encoding of the tablet's table identifier and its end row. 但是其实不重要，聪明的engineer总是可以设计出自己的metadata的，比如说HBase就实现了自己的一套metadata。

在BigTable里， SSTable(Sorted Strings Table)是一个基本的单元。论文里面并没有提到SSTable是怎么样实现的。每个Tablet有若干个SSTable。但是根据对开源的LevelDB的学习，我们可以大致上可以描述一下LevelDB是怎么实现的。这个实现复活了1993年由UMass Boston退休教授 Patrick O'Neil实现的LSM-Tree。我们把相关的论文放在下面供大家参考：

Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth (Betty) O'Neil, "The Log-Structured Merge-Tree," patent granted to Digital Equipment Corporation, December 1993; appeared in ActaInformatica 33, pp. 351-385, June 1996.

看起来这个tree是申请了专利的，专利授权给了已经挂掉的DEC公司。不知道Google用这个Tree是不是侵权，也不知道目前用了LevelDB的，以及Facebook克隆LevelDB做出来的RocketDB的各大公司们有没有获得专利公司的授权。还是说因为年代太久远而DEC公司已经挂掉了无数年了，大家可以肆无忌惮的用了呢？

整个SSTable的实现分为memTable和磁盘上的SSTable。在内存里使用的是skip-list。所以写的操作只是写内存，非常的快。而内存写满之后就会把这个memTable变成一个immutable的memTable。同时开一个新的可以写的memTable另外一个线程则会把这个immutable的内存表变成一个磁盘上的SSTable。当这个转变完成以后immutable的内存表被释放。如此往复磁盘上会产生很多的SSTable。这就需要compact。SSTable是有level1， level2，。。。的。其中进到level1的compact叫做minor compact。后面还有major compact。从level2开始以后任意两棵树的key之间不会有overlap，但是在level1这并不guarantee。

所以我们的一个读操作要读memTable，immutable memTable，level1的tree，和level2以及以下的level的1棵树。这说明读的操作相对写的操作会更贵一些。大家需要注意的是，如果我们访问的是最新的版本，那么有可能会在内存里，所以这个设计对于读的操作主要是优化了新版本的读。对于cool data的读则要慢很多。顺便补充一句，Facebook的copycat RocektDB和LevelDB最主要的区别据说是引入了一个叫做universal compact的东西。当然我没有研究过这个codebase，不清楚universal compact到底有多牛。

当然，就像任何一个类似的系统一样，BigTable的recovery基于log，所有的写操作进内存之前写进log。LevelDB的log format并不是太难懂，是经典的append only的操作，文件被分成了block。基于log的读写恢复是任何一个系统的基础了。我就不再展开叙述。

说起来非常的有意思，这个LSM-Tree是一个挺了不起的发明，但是波澜不兴的在Industry很多年。发明者Patrick O'Neil在DB界固然是混一个教授到退休，但是也没有获得和他发明相匹配的知名度。也不知道Google的员工们是怎么样从一本并不怎么知名的杂志里把这个东西给挖出来，复活了。有时候我在想，倘若当年没有成名可以理解，现在已经成为了BigTable的基础了，那么作为database research community是不是应该recognize一下。实际上当然是没有。出乎我意料之外的是今年2016的VLDB我居然在印度遇到了Patrick的PhD，实在无法想象这么老了还在带学生。Database community有一些时候对某些人的recognition可能确实是差了一些。比如说Peter Chen，这位在MIT没有拿到tenure在路易斯安那州立大学安家的人，发明了E-R model，为database的发扬光大做出了巨大的贡献。但是我觉得整个community对他的recognition非常的有限。比如说Goetz Graefe，这个在query optimization和query execution做出过巨大贡献的人，发明了Volcano optimizer和经典的Volcano execution model，包括今天大行其道的Exchange operator，居然到今天也没有获得 Sigmod Edgar Codd Innovations Award，我实在是不能理解。