【分布式系统工程实现】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] 推荐:

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

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

【分布式系统工程实现】GFS&Bigtable设计的优势

- hikerlive - 淘宝核心系统团队博客
目前,知名度比较高的通用存储系统包括:Google GFS&Bigtable,Amazon Dynamo,Microsoft Azure存储系统及Yahoo PNUTS. 其中,GFS&Bigtable,Azure存储系统及Yahoo PNUTS都有总控节点,Amazon Dynamo采用去中心化的P2P设计.

BigTable小结

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

Bigtable:一个分布式的结构化数据存储系统[中文版]

- Bian Jiang - Alex && OpenCould
Bigtable:一个分布式的结构化数据存储系统. Bigtable是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服务器上的PB级的数据. Google的很多项目使用Bigtable存储数据,包括Web索引、Google Earth、Google Finance.

【分布式系统工程实现】CAP理论及系统一致性

- hikerlive - 淘宝核心系统团队博客
印象中CAP理论开始流行是从Amazon Dynamo的论文开始的,Amazon的CTO还在他的博客中介绍了最终一致性的概念,从此以后,各种会议和交流中都少不了CAP的影子. 然而,对于分布式系统工程设计和开发来说,CAP意味着什么呢. CAP 理论由 Berkerly 的 Brewer 教授提出,三者的含义如下:.

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

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

【分布式系统工程实现】如何检测一台机器是否宕机?

- Michael Liao - 淘宝核心系统团队博客
检测一台机器是否宕机的应用场景如下:. 1, 工作机器宕机,总控节点需要能够检测到并且将原有服务迁移到集群中的其它节点. 2, 总控节点宕机,总控节点的备份节点(一般称为Slave)需要能够检测到并替换成主节点继续对外服务. 检测一台机器是否宕机必须是可靠的. 在大规模集群中,机器可能出现各种异常,比如停电,磁盘故障,过于繁忙导致假死等.

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

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

[转载]投资是个系统工程

- - 穿过记忆的河流
原文地址: 投资是个系统工程 作者: 李白雨的投资博客.                               投资是个系统工程.                                              李白雨.     做投资的时间久了,难以避免地会碰到一些关于推荐股票的问题,直接的或者间接的.

Google的系统工程师(SA)如何工作

- freefish - Tim[后端技术]
本文根据系统管理领域知名博客 Thomas A. Limoncelli 的 What is system administration like at Google 整理而成,添加了部分笔者观点. Google的系统工程师(System Administrator)如何工作. 由于Google的服务已经集群化,系统工程师并不大量接触硬件比如做安装服务器等事情.