LSM 树 (Log-Structured Merge Tree) 存储引擎
代表数据库: nessDB,leveldb,hbase 等
核心思想的核心就是放弃部分读能力, 换取写入的最大化能力. LSM Tree , 这个概念就是结构化合并树的意思, 它的核心思路其实非常简单, 就是假定内存足够大, 因此不需要每次有数据更新就必须将数据写入到磁盘中, 而可以先将最新的数据驻留在磁盘中, 等到积累到最后多之后, 再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的, 可以通过合并排序的方式快速合并到一起).
日志结构的合并树 (LSM-tree) 是一种基于硬盘的数据结构, 与 B-tree 相比, 能显著地减少硬盘磁盘臂的开销, 并能在较长的时间提供对文件的高速插入(删除). 然而 LSM-tree 在某些情况下, 特别是在查询需要快速响应时性能不佳. 通常 LSM-tree 适用于索引插入比检索更频繁的应用系统 http://www.2cto.com/os/ .Bigtable 在提供 Tablet 服务时, 使用 GFS 来存储日志和 SSTable, 而 GFS 的设计初衷就是希望通过添加新数据的方式而不是通过重写旧数据的方式来修改文件. 而 LSM-tree 通过滚动合并和多页块的方法推迟和批量进行索引更新, 充分利用内存来存储近期或常用数据以降低查找代价, 利用硬盘来存储不常用数据以减少存储代价.
磁盘的技术特性: 对磁盘来说, 能够最大化的发挥磁盘技术特性的使用方式是: 一次性的读取或写入固定大小的一块数据, 并尽可能的减少随机寻道这个操作的次数.
LSM 和 Btree 差异就要在读性能和写性能进行舍和求. 在牺牲的同事, 寻找其他方案来弥补.
1,LSM 具有批量特性, 存储延迟. 当写读比例很大的时候(写比读多),LSM 树相比于 B 树有更好的性能. 因为随着 insert 操作, 为了维护 B 树结构, 节点分裂. 读磁盘的随机读写概率会变大, 性能会逐渐减弱. 多次单页随机写, 变成一次多页随机写, 复用了磁盘寻道时间, 极大提升效率.
2,B 树的写入过程: 对 B 树的写入过程是一次原位写入的过程, 主要分为两个部分, 首先是查找到对应的块的位置, 然后将新数据写入到刚才查找到的数据块中, 然后再查找到块所对应的磁盘物理位置, 将数据写入去. 当然, 在内存比较充足的时候, 因为 B 树的一部分可以被缓存在内存中, 所以查找块的过程有一定概率可以在内存内完成, 不过为了表述清晰, 我们就假定内存很小, 只够存一个 B 树块大小的数据吧. 可以看到, 在上面的模式中, 需要两次随机寻道(一次查找, 一次原位写), 才能够完成一次数据的写入, 代价还是很高的.
3,LSM Tree 放弃磁盘读性能来换取写的顺序性, 似乎会认为读应该是大部分系统最应该保证的特性, 所以用读换写似乎不是个好买卖. 但别急, 听我分析一下.
a, 内存的速度远超磁盘, 1000 倍以上. 而读取的性能提升, 主要还是依靠内存命中率而非磁盘读的次数
b, 写入不占用磁盘的 io, 读取就能获取更长时间的磁盘 io 使用权, 从而也可以提升读取效率. 例如 LevelDb 的 SSTable 虽然降低了了读的性能, 但如果数据的读取命中率有保障的前提下, 因为读取能够获得更多的磁盘 io 机会, 因此读取性能基本没有降低, 甚至还会有提升. 而写入的性能则会获得较大幅度的提升, 基本上是 5~10 倍左右.
下面说说详细例子:
LSM Tree 弄了很多个小的有序结构, 比如每 m 个数据, 在内存里排序一次, 下面 100 个数据, 再排序一次...... 这样依次做下去, 我就可以获得 N/m 个有序的小的有序结构.
在查询的时候, 因为不知道这个数据到底是在哪里, 所以就从最新的一个小的有序结构里做二分查找, 找得到就返回, 找不到就继续找下一个小有序结构, 一直到找到为止.
很容易可以看出, 这样的模式, 读取的时间复杂度是(N/m)*log2N . 读取效率是会下降的.
这就是最本来意义上的 LSM tree 的思路. 那么这样做, 性能还是比较慢的, 于是需要再做些事情来提升, 怎么做才好呢?
来源: http://www.bubuko.com/infodetail-2563878.html