【分布式系统工程实现】Bigtable Merge-Dump存储引擎

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

【分布式系统工程实现】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的特性,天然适应硬件的发展趋势。

上一篇:Java File创建新目录和文件


下一篇:用U盘制作Win7系统盘