单机存储引擎解决单机读写问题，Merge-Dump存储引擎设计成一种通用的存储引擎，同时支持数据写入，随机读取和顺序扫描功能。顺序扫描功能应用很广，比如MapReduce批处理，同一个广告主的所有关键词广告统计，用户浏览所有的收藏信息，淘宝卖家管理大量的商品等。简单的KV系统只需要支持随机读取，而类似Bigtable这样的通用表格系统需要考虑基于主键的顺序扫描功能。Bigtable中的Merge-Dump存储引擎结构如下：

    用户的操作首先写入到MemTable中，当内存中的MemTable达到一定的大小，需要将MemTable dump到持久化存储中生成SSTable文件。这里需要注意，除了最早写入的SSTable存放了最终结果以外，其它的SSTable和MemTable存放的都是用户的更新操作，比如对指定行的某个列加一操作，删除某一行等。每次读取或者扫描操作都需要对所有的SSTable及MemTable按照时间从老到新进行一次多路归并，从而获取最终结果。为了防止机器宕机，将用户的操作写入MemTable之前，会先写入到操作日志(commit log)中，这时一般会用到group commit操作，即将大量并发写操作聚合成一块一次性写入到commit log。由于写commit log为顺序追加，很好地利用了磁盘的顺序访问特性。

    为了防止磁盘中的SSTable文件过多，需要定时将多个SSTable通过compaction过程合并为一个SSTable，从而减少后续读操作需要读取的文件个数。Bigtable中将compaction分为三种：minor compaction，merge compaction以及major compaction。其中，minor compaction指的是当内存中的MemTable达到一定的大小以后需要生成SSTable；merge compaction将连续多个大小接近的SSTable及Memtable合并生成一个SSTable；major compaction合并所有的SSTable和Memtable生成最终的SSTable文件。Minor和Merge compaction生成的SSTable文件中包含的还是用户的更新操作，只有Major compaction生成的SSTable才包含最终结果。一般来说，线上服务的写操作比较少，我们总是能以很大概率使得每个子表只包含一个SSTable和MemTable，也就是说，读取操作基本只需要访问一个SSTable文件和内存；而线下或者半线下服务，比如网页库，虽然写入操作多，可能经常出现一个子表包含多个SSTable的情况，不过这种类型的服务一般用于大数据量顺序扫描，对延时要求不高。SSTable的compaction有几个需要注意的点：

    1, 限制SSTable的数量，必要时限制写入速度。如果写入速度持续大于compaction消化的速度，也就是大于系统的承载能力，SSTable将越积越多从而compaction永远无法成功。比如Cassandra存储节点采用了类似Bigtable的Merge-dump的做法，不过据说可能因为没有控制SSTable的最大个数也出现永远合并不成功的问题；

    2, Compaction及写操作并发控制。Compaction的过程很长，compaction不能阻塞写操作，并且minor compaction和merge/major compaction可能同时进行。Compaction成功提交的时候需要互斥修改子表记录的SSTable结构数组，多个compaction同时进行的时候有些麻烦；

    3, Minor compaction时机。当Memtable达到一定大小，比如4MB时，需要冻结Memtable并生成SSTable数据dump到磁盘中；同时，由于所有子表的操作日志写入到同一个commit log文件，当MemTable距离第一条数据写入超过一定的时间也需要执行minor compaction，否则，会出现机器宕机回放的commit log过多的问题；

    4, Merge compaction如何选取SSTable文件。Merge compaction合并SSTable以减少读取的文件个数，每次merge compaction都是把相应的SSTable文件分别读写一次。为了提高性能，一般会要求Merge compaction选取连续的大小接近的SSTable文件。举个例子，如果有4个大小为4MB的SSTable文件，如果merge的策略为((s1 & s2) & s3) & s4 (&表示merge操作)，读取的文件大小为s1 * 3 + s2 * 3 + s3 * 2 + s4 * 1 = 4M * 9 = 36M，如果merge的策略为(s1 & s2) & (s3 & s4)，读取的文件大小为s1 * 2 + s2 * 2 + s3 * 2 + s4 * 2 = 32M，并且SSTable文件个数越多差别越明显；

    数据在SSTable中连续存放，需要同时随机读取和顺序读取两种需求。SSTable被分成大小约为64KB的块(SSTable block)，由于单个tablet的大小一般为100MB ~ 200MB，我们可以认为SSTable的大小不超过256MB，包含的block个数为256MB / 64KB = 4KB，每个block需要包含起始行，结束行相关的索引信息，假设索引信息大小平均为256Byte，每个SSTable的索引大小为4KB * 256Byte = 1MB，磁盘内存比为256 : 1，16GB的索引可以存放16GB * 256 = 4TB的数据。SSTable的索引数据全部存放到内存中，随机读取需要先通过二分查找找到相应的block，然后从磁盘中读取相应的block数据。Bigtable系统使用的SATA盘的磁盘寻道时间一般为10ms左右，一次随机读取整个64KB的块造成的overhead是可以接受的。按照64KB划分块还带来了一个好处，数据量膨胀对性能的影响很小。顺序读取的做法类似，在Merge-dump引擎中是很高效的。与传统的数据库的数据格式不同，SSTable存放的数据一般都是稀疏的，大多数列可能都没有更新操作。

    按列存储&压缩：数据仓库的应用场景中需要支持按列存储，有两个好处：第一个好处是减少读取的数据量，第二个好处是提高压缩比率。Bigtable支持指定locality group，每个locality group中的列在SSTable中连续存储，每一个locality group之内按照行有序存储，当然，数据在MemTable中是不需要区分locality group的。这样，compaction是按照locality group进行的，读取每一个待归并的SSTable中相应的locality group的数据，合并生成一个新的SSTable locality group。某些跨多个locality group的更新操作，比如删除一行，需要将更新操作同时写入到多个locality group中。

    总之，Merge-dump是一种同时满足随机和顺序读取的通用存储引擎，可以广泛应用在各种NOSQL存储系统中，另外，Merge-dump存储引擎往commit log文件追加操作日志以及compaction过程都是顺序写文件，非常符合SSD的特性，天然适应硬件的发展趋势。

建议继续学习：

1. 分布式缓存系统 Memcached 入门    (阅读：14702)
2. HFile存储格式    (阅读：14521)
3. Zookeeper工作原理    (阅读：10353)
4. 我对技术方向的一些反思    (阅读：9853)
5. 淘宝图片存储架构    (阅读：9812)
6. GFS, HDFS, Blob File System架构对比    (阅读：9357)
7. Zookeeper研究和应用    (阅读：8503)
8. 分布式日志系统scribe使用手记    (阅读：8023)
9. 一致性哈希算法及其在分布式系统中的应用    (阅读：7912)
10. 分布式哈希和一致性哈希    (阅读：7635)