前言:最近在了解学习 Rocksdb,在学习过程中发现里面挺多东西的,LSM树就是其中一环,于是乎就有了这篇文章。接下来会再写几篇,直到学习完 rocksdb,敬请期待啊~希望大家看完了也可以评论一下,给些反馈哈哈
虽然大家都是叫它 LSM 树,听着很像是一个树状的数据结构,但严格意义上,它是一种存储结构,全称 Log-Structured-Merge-Tree,即日志结构合并树
很多 NoSQL 存储都是采用 LSM 树进行支撑的,如 HBase、LevelDB、RocksDB 等
它的核心其实是牺牲部分读性能(存储分层设计),追求更好的写性能(顺序写)
那么问题来了,LSM 树究竟是要解决什么问题而提出的呢?
知道了 LSM 树的特点后,基于 LSM 的存储引擎会用来做什么,其实并不难猜出来,即写多读少(相对而言)的场景,比如说:
这些场景都是会有一定规模的数据量写入,同时对于数据读取的实时性要求并不高
接下来我们继续来了解一下 LSM 的核心原理吧~
这部分要分两块来讲,第一块是它如何保证顺序写?第二块是它有哪些东西组成?
与 InnoDB 不同,LSM 就是围绕追加写来展开的。因为追加写就是一种典型的顺序IO,将所有的用户操作,都像写日志一样,不断的追加记录写到磁盘中,而不是记录覆盖
如图中所示,不管操作是数据插入,还是更新删除,都会往磁盘文件中的尾部追加操作的记录,而不是去磁盘中找到之前的数据记录,然后覆盖或删除,通过这种方式保证了 LSM 树的顺序写,从而大大地提高了写入的性能
至于为啥都说要保证顺序 IO 以及为啥顺序 IO 可以提高性能其实是跟磁盘的结构有关,实际上说的就是顺序 IO 符合磁盘的扫描读取的行为模式,相比随机 IO 而言更高效,保证顺序 IO 的目的也是为了减少寻址的次数
这是摘自网上的一张图,主要展示的是磁盘、SSD、内存这三者对于随机写和顺序写的一些性能比较,我们可以看到磁盘顺序写的吞吐量甚至能够超过内存随机写的吞吐量!
更多关于磁盘 IO 的知识,这里就不再展开了,感兴趣的可以自己再去了解一下
要想理解 LSM 树的读写原理,要先了解它的一些核心模块。数据库都离不开内存和磁盘的交换,而 LSM 树也是一样的,我们可以从内存和磁盘两部分去看它的组成原理,如下图:
内存模块由三个部分组成:
磁盘模块由两个部分组成:
除了上面说的这几个模块,图中还有几个数据流向也是很关键的:
上面提到了 LSM 的核心其实就是通过顺序写来解决大量写时的性能问题,又因为分层设计牺牲了部分读取性能,那么接下来就从“增删改查”的角度去理解它的读写流程及原理
要预先说明的是,LSM 对所有数据的插入、修改、删除操作都是先写入 log,再保存到内存中,待数据量到达某个值后再批量顺序地写入到磁盘中,这样也会提高写的效率
以插入数据为例,它的数据流向如下图
更新数据、删除数据时依然是上面的流程,只不过是操作的记录有所变化,并且是追加写入,与之前的同个 key 的写入记录是可以同时存在的,最终形成类似的日志形式
现在来看一下读数据的流程,如下图所示
实际上,为了提高随机读取的性能,一般会在 SSTable 上加入布隆过滤器判断数据是否存在达到避免不必要的数据遍历,同时也会对数据建立索引,加快查找速度
如果仔细看的话,通过上面的读写流程可以发现读写操作流程可能会很长,而这就引申出了 LSM 树的三大经典问题:写放大、读放大、空间放大,下面提到的合并策略其实就是对这三个问题的权衡与取舍
为了解决上面提到的“三大问题”,就要用到合并策略了
LSM 树中有两种合并策略:size-tiered(分层策略),leveled(分级策略)
我们先来看下 size-tiered 分层策略是怎样的
每层限制 SSTable 为 N,当每层 SSTable 数量达到 N 后,则触发 Compact 操作合并这些 SSTable,并将合并后的结果写入到下一层成为一个更大的 SSTable,这就是分层合并策略,即
合并过程
假设 N 为 4,也就是每层 SSTable 数量最多为 4 个,一旦 SSTable 在这一层中数量到达 4,则会触发合并生成下一层的 SSTable
这种策略会有什么问题呢?
我们再来看一下 leveled 分级策略是怎样的,其实也跟名字含义一样,每一层都有一个层级 level 的概念
合并过程
假设此时 level 0 中有两个 SSTable 的 key 的范围与 level 1 的前两个有重合,则这几个 SSTable 触发 Compact 操作
需要注意的是:多个不相干的合并是可以并发进行的
如果 level 1合并后也超出 level 1的容量大小,重复上面的操作,于是乎...
既然说到合并策略是对读写、空间放大的问题的权衡与取舍,那它肯定也不是十全十美的,这种策略有什么样的问题呢?
LSM 树是一种利用磁盘顺序 IO 写入高性能的存储结构模型,它以牺牲了一定的读性能为代价,大幅度提升了写性能,适用于写多读少的特定应用场景,是一种兼顾成本及性能的存储解决方案。
很多数据库也是基于 LSM 树实现的,如 leveldb、rocksdb、hbase,大家可以去看一下理论演化成工程化实践落地具体会有什么不一样的地方或改进的地方
这篇文章主要讲解了 LSM 的结构组成、读写流程、三大问题以及合并策略,关于 LSM 树在内存、磁盘中数据的具体写入细节由于篇幅问题没有提及,感兴趣的可以去了解一下,数据是怎样顺序写入到内存的数据结构中,然后又如何持久化到磁盘的数据结构中,合并后读取对应的数据又是如何遍历这些数据结构的等等
最后留一个问题:你觉得分层合并与分级合并的区别是什么?什么情况选择哪一种策略更好?
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。