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

标签: 分布式架构 Merge-Dump,存储引擎,MemTable,SSTable | 发表时间:2010-12-15 13:29 | 作者:chuanhui XiaoHui
分享到:
出处:http://www.nosqlnotes.net

单机存储引擎解决单机读写问题,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的特性,天然适应硬件的发展趋势。

相关 [系统工程 bigtable merge] 推荐:

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

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

BigTable小结

- MAGI-CASPER/Peter Pan - 博客园-唯有前进值得敬仰
读完Bigtable论文小结一下. 对于Bigtable的整体理解 . BigTable将数据存储分为两部分:最近的更新存储在内存(memtable)中,较老的更新则以SSTable的格式存储在GFS,后者是主体部分,不可变的数据结构. 写操作的内容插入到memtable中,当memtable的大小达到一个阈值时就冻结,然后创建一个新的memtable,旧的就转换成一个SSTable写入GFS.

mysql-merge合并表

- - CSDN博客编程语言推荐文章
注意: 1 每个子表的结构必须一致,主表和子表的结构需要一致, 2 每个子表的索引在merge表中都会存在,所以在merge表中不能根据该索引进行唯一性检索. 3 子表需要是MyISAM引擎 4 AUTO_INCREMENT 不会按照你所期望的方式工作. 建表语句 create table tablename(正常的字段)engine=merge insert_method=last insert_method: 有两个值如下: LAST 如果你执行insert 指令来操作merge表时,插入操作会把数据添加到最后一个子表中.

【转】Mysql MERGE引擎简介

- - 编程语言 - ITeye博客
一. 什么是MERGE 引擎. MERGE存储引擎把一组MyISAM数据表当做一个逻辑单元来对待,让我们可以同时对他们进行查询. 如果需要把日志纪录不停的录入MySQL数据库,并且每天、每周或者每个月都创建一个单一的表,而且要时常进行来自多个表的合计查询,MERGE表这时会非常简单有效. 执行select * from t;将会得到如下结果.

[转][转]LSM-Tree (BigTable 的理论模型)

- - heiyeluren的Blog
LSM-Tree理论模型:. 来源:http://www.cnblogs.com/raymondshiquan/archive/2011/06/04/2072630.html . Google的BigTable架构在分布式结构化存储方面大名鼎鼎,其中的MergeDump模型在读写之间找到了一个较好的平衡点,很好的解决了web scale数据的读写问题.

[转]MapReduce:详解Shuffle(copy,sort,merge)过程

- - 芒果先生Mango的专栏
Shuffle过程是MapReduce的核心,也被称为奇迹发生的地方. 要想理解MapReduce, Shuffle是必须要了解的. 我看过很多相关的资料,但每次看完都云里雾里的绕着,很难理清大致的逻辑,反而越搅越混. 前段时间在做MapReduce job 性能调优的工作,需要深入代码研究MapReduce的运行机制,这才对Shuffle探了个究竟.

Oracle中Merge Into 代替Insert/Update的应用

- - 数据库 - ITeye博客
在进行SQL语句编写时,我们经常会遇到大量的同时进行Insert/Update的语句 ,也就是说当存在记录时,就更新(Update),不存在数据时,就插入(Insert). 在一个同时存在Insert和Update语法的Merge语句中,总共Insert/Update的记录数,就是Using语句中的记录数.

解读BigTable类NoSQL数据库的选型与设计

- - searchdatabase
  BigTable类数据库系统(HBase,Cassandra等)是为了解决海量数据规模的存储需要设计的. 这里说的海量数据规模指的是单个表存储的数据量是在TB或者PB规模,单个表是由千亿行*千亿列这样的规模组成的. 提到这个数据规模的问题,不得不说的就是现在在NoSQL市场中,最火的四种NoSQL系统依次是MongoDB,Redis,Cassandra,HBase.

HTC 中国发布 CDMA/GSM 双模机:纵横 (Merge 行货版)

- 涛涛 - Engadget 中国版
HTC 终于把 HTC Merge 这款机型带到中国来卖,这将改变其没有双模机行货的局面. 将其取名纵横显然是因为其不但支持中国电信的 CDMA2000 网络,它还支持 WCDMA 和 GSM 网络. 外观和硬件规格和海外版一致,HTC 纵横(S610d )采用 3.8 英寸的屏幕,480×800 像素分辨率,高通 MSM 7630 800MHz 处理器搭配 512MB RAM,500万像素摄像头带自动对焦,有LED闪光灯.

Oracle的Filter,Nest loop,Merge sort join和Hash join(原创)

- - ITeye博客
按照Merge Sort Join连接的两表地位完全相同. 这种算法会把每个表按照连接列进行排序,生成两个排序集. 然后对两个排序集进行一次遍历便可以得到最终结果集. 这个算法的特点是,每个表都需要排序,排序后都需要遍历一次. 以下面的例子说明,Merge Sort Join的执行过程如下:. 1、根据tabs表的where条件,查找出符合条件的结果集.