关于“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策略的选择是个启发。
