关于“LSM-Tree”

作者:小鱼的互联网观察 发布时间:January 8, 2013 分类:技术

在分布式海量存储系统中,算法也发挥着重要的作用,本章分享的是在nosql等海量存储中两个比较重要的算法:The Log-Structured Merge-Tree(简称LSM-tree)、Bloom filter。这两个算法在bigtable、leveldb、cassandra、hbase等存储系统中都有用到。

 

 

The Log-Structured Merge-Tree

 

 

LSM-Tree软件解决方案的基本原理都非常简单,就是在内存中对最近的更新操作进行缓存,当更新积累到一定程度,然后进行批量的merge dump,从而把随机写变成批量顺序更新。

对于LSM-Tree,

 

拿update举个例子:

比如有1000万行数据,现在希望update table.a set addr='new addr' where pk = '833',

如果使用B-Tree类似的结构操作,就需要:

1. 找到该条记录所在的page,

2. load page到内存(如果恰好该page已经在内存中,则省略该步)

3. 如果该page之前被修改过,则先flush page to disk

4. 修改数据

上面的动作平均来说有两次disk I/O,

如果采用LSM-Tree类似结构,则:

1. 将需要修改的数据直接写入内存

可见这里是没有disk I/O的。

当然,我们要说,这样的话读的时候就费劲了,需要merge disk上的数据和memory中的修改数据,这显然降低了读的性能。

确实如此,所以作者其中有个假设,就是写入远大于读取的时候,LSM是个很好的选择。我觉得更准确的描述应该是”优化了写,没有显著降低读“,因为大部分时候我们都是要求读最新的数据,而最新的数据很可能还在内存里面,即使不在内存里面,只要不是那些更新特别频繁的数据,其I/O次数也是有限的。

所以LSM-Tree比较适合的应用场景是:insert数据量大,读数据量和update数据量不高且读一般针对最新数据。

文章读下来有以下几点感受:

1. 基本思想早就有了,作者给出了较好的表现形式。

2. Merge是page/block级别的,而不是BigTable中的文件级别的。这一点主要原因可能是BigTable在分布式场景下做block级别很困那,而且GFS也不支持修改。

3. 其提出的比较标准比较有趣,将磁盘容量,转速等结合起来给出一个以美元为单位的cost标准,然后跟B-Tree结构的实现做了比较,结果当然是大大胜出。但是这里我觉得作者有些比较是不合理的,比如LSM使用log而B-Tree没有使用,这显然对B-Tree不公,其实B-Tree如果使用log,写入性能应该不比LSM差,顺序读取可能差一些。

4. 在Multi components 中,提出Ci/Ci+1的比例达到20的时候是最优的,这个数字意义不大,但是其中的分析方法对于Merge策略的选择是个启发。

 

  1. 页码:
网站地图 京ICP证030173号