背景
LSM树应用场景太多了,个人接触过的就有这些。。戳个FLAG,一定要弄明白。
- HBASE
- LevelDB/RocksDB
- Ceph底层osd的对象存储
- 图数据库Dgraph底层存储badger (+bloomfilter)
- Hadoop的对象存储OZone的container底层存储
- ClickHouse最主要的MergeTree引擎
- &
LSM是什么
首先,LSM是一种支持快速查找的存储结构。
各种查找算法,要么依赖哈希如HashMap,要么依赖排序如TreeMap/SkipList,而排序更泛用一些,比如空间更紧凑,支持区间获取等,所以应用更广泛。主流的数据库索引B+树就是优化后的排序好的树状结构,但是B+树的问题在于其插入和删除时需要动态调整树的结构以保持平衡,而这需要较多的随机磁盘读写,这也导致了B+树的写入性能不高。
LSM也是一种基于排序的树,在存储和检索上做了一些策略和优化。
存储的本质是IO性能的最大化利用,当然还得考虑到功能的支持。要知道所有的决策前提是:
- 内存读写速度比磁盘快几个数量级,但是内存有限
- 磁盘顺序读写速度又比随机读写快几个数量级(磁盘寻道的物理特性决定)
这样一来,尽可能的使用内存,尽可能的使用顺序读写是设计的关键。如Redis,全内存K-V系统,OPS能到每秒10万级别(配合管道更高),而消息队列kafka结合顺序读写和offset机制,吞吐能达到GB/s单节点(当然是多磁盘)。但是不同设计都是一些取舍的结合,Redis只支持KV操作,不支持区间查找,kafka本质是顺序写入和消费,甚至不支持随机读写,也不支持更新。
而LSM是各种折中的结果,即热点数据读写在内存,并且写入是顺序写,覆盖式更新,弱锁依赖,有很高的写入性能。并且结合数据局部性,排序,bloomfilter等特性,使读取也有很好的效果,是一个既支持k-v操作,也支持区间操作的综合效果较好的存储设计。
LSM起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》,日志合并树。
先看名字,log-structured,日志结构的,日志是软件系统打出来的,就跟人写日记一样,一页一页往下写,而且系统写日志不会写错,所以不需要更改,只需要在后边追加就好了。各种数据库的写前日志也是追加型的,因此日志结构的基本就指代追加。注意他还是个 “Merge-tree”,也就是“合并-树”,合并就是把多个合成一个。
下图是 LSM-tree 的组成部分,是一个多层结构,就更一个树一样,上小下大。首先是内存的 C0 层,保存了所有最近写入的 (k,v),这个内存结构是有序的,并且可以随时原地更新,同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上,每一层都是一个在 key 上有序的结构。
写入流程:一个 put(k,v) 操作来了,首先追加到写前日志(Write Ahead Log,也就是真正写入之前记录的日志)中,接下来加到 C0 层。当 C0 层的数据达到一定大小,就把 C0 层 和 C1 层合并,类似归并排序,这个过程就是Compaction(合并)。合并出来的新的 new-C1 会顺序写磁盘,替换掉原来的 old-C1。当 C1 层达到一定大小,会继续和下层合并。合并之后所有旧文件都可以删掉,留下新的。
注意数据的写入可能重复,新版本需要覆盖老版本。什么叫新版本,我先写(a=1),再写(a=233),233 就是新版本了。假如 a 老版本已经到 Ck 层了,这时候 C0 层来了个新版本,这个时候不会去管底下的文件有没有老版本,老版本的清理是在合并的时候做的。
写入过程基本只用到了内存结构,Compaction 可以后台异步完成,不阻塞写入。
查询流程:在写入流程中可以看到,最新的数据在 C0 层,最老的数据在 Ck 层,所以查询也是先查 C0 层,如果没有要查的 key,再查 C1,逐层查。
以上是LSM树的基本思想,实际工程实现上有很多考虑,但是核心不变。
为什么LSM结构是存储系统重要选型
主流的关系型数据库均以 B/B+ tree 作为其构建索引的数据结构,这是因为 B tree 提供了理论上最高的查询效率O(log n)。但对查询性能的追求也造成了 B tree 的相应缺点,即每次插入或删除一条数据时,均需要更新索引,从而造成一次磁盘 IO。这种特性决定了 B tree 只适用于频繁读、较少写的场景。如果在频繁写的场景下,将造成大量的磁盘 IO,从而导致性能骤降。这种应用场景在传统的关系型数据库中比较常见。
而 LSM tree 则避免了频繁写场景下的磁盘 IO 开销,尽管其查询效率无法达到理想的O(log n),但依然非常快,可以接受。所以从本质上来说,LSM tree 相当于牺牲了一部分查询性能,换取了可观的写入性能。这对于 key-value 型或日志型数据库是非常重要的。
技术细节和关键性取舍
LSM本质不是一个算法,当成一个方法更合适。是一个存储结构,然后可以有很多变体。这一点其实B树体系也像。
LSM和Btree差异就要在读性能和写性能进行舍和求。在牺牲的同时,寻找其他方案来弥补。
主要的影响因素:
- 内存数据多大(hot memory table)?
- 什么时候合并,选取哪些数据合并 ?(保持层内有序)
- 数据分为几层 ?(阈值,策略)
- 重复key怎么处理 ?(异步删)
- 怎么尽可能减少查询时的搜索次数 ?(过滤器,层内稀疏索引,跳跃表等)
LevelDB
下图是 LevelDB 的架构,首先,LSM-tree 被分成三种文件,第一种是内存中的两个 memtable,一个是正常的接收写入请求的 memtable,一个是不可修改的immutable memtable。
另外一部分是磁盘上的 SStable (Sorted String Table),有序字符串表,这个有序的字符串就是数据的 key。SStable 一共有七层(L0 到 L6)。下一层的总大小限制是上一层的 10 倍。分层也是LevelDB的名称由来。
写入流程:首先将写入操作加到写前日志中,接下来把数据写到 memtable中,当 memtable 满了,就将这个 memtable 切换为不可更改的 immutable memtable,并新开一个 memtable 接收新的写入请求。而这个 immutable memtable 就可以刷磁盘了。这里刷磁盘是直接刷成 L0 层的 SSTable 文件,并不直接跟 L0 层的文件合并。
每一层的所有文件总大小是有限制的,每下一层大十倍。一旦某一层的总大小超过阈值了,就选择一个文件和下一层的文件合并。
并且,合并后保持每层都是总体有序。
每一层可以维护指定的文件个数,同时保证不让key重叠。也就是说把key分区到不同的文件。因此在一层查找一个key,只用查找一个文件。
RocksDB在LevelDB上的改进
- 多核优化、锁优化、缓存控制优化
- 支持一次获取多个K-V,还支持Key范围查找。LevelDB只能获取单个Key
- 支持多线程合并,而LevelDB是单线程合并
- 增加了合并时过滤器,对一些不再符合条件的K-V进行丢弃,如根据K-V的有效期进行过滤
- 更多的压缩方式
- 可以允许根据需要开辟多个Memtable,以解决Put与Compact速度差异的性能瓶颈问题。在LevelDB里面因为只有一个Memtable,如果Memtable满了却还来不及持久化,这个时候LevelDB将会减缓Put操作,导致整体性能下降
- 前缀bloom过滤器
- 备份、统计、动态参数修改、命令工具等等
总体来说,RocksDB在很多方面对LevelDB做了优化和增强,更像是一个完整的产品。
小结
LSM树原理是把一棵大树拆分成N棵小树,它首先有序地写入内存中,(比如基于红黑树,或者跳跃表),随着小树越来越大,内存中的小树会flush到磁盘中,磁盘中的树定期可以做merge操作,合并成一棵大树,以优化读性能。
LSM逻辑和物理都是分层的,最上层是内存,层越下容量越大,通常是越老的数据。读取时类似自顶向下查找,先查最顶层,如果没有则查下一层,直到找到。同时每层辅助以布隆过滤器,稀疏索引等手段快速定位目标。
PS 202110. Hbase的写入和合并
- 写入的时候最底层封装是一个跳跃表(与红黑树类似 都是map结构 且排序,实现更简单,索引更紧凑,性能查了一下应该是差不多 )
MemStore-> Segment -> CellCet -> this.delegatee = new ConcurrentSkipListMap<>(c);
- 有多个层次 内存满了写入Hstore
- 后台有Compaction的检查线程 触发合并时,传入一个List StoreFile ,合并后写入到一个新的StoreFile
- 合并的过程:各个StoreFile创建Scanner,封装在一个优先队列里。然后就是迭代,比较,写入,持续循环 ... (这里和CarbonData的合并差不多好像)
KeyValueHeap
protected PriorityQueue<KeyValueScanner> heap = null;