LSMT与存储引擎介绍
LSMT是什么
通过Append-only Write +择机Compact来维护结构的索引树。
存储引擎是什么
大致分为:
- 计算层
- 存储层(存储引擎层)
计算层主要负责SQL解析/查询优化/计划执行。
数据库著名的ACID特性,在MySQL中全部强依赖于存储引擎。
ACID是什么/存储引擎哪些组件保障了这些特性?
- Atomicity
- Consistency(C orrectness)
- Isolation
- Durability
除了保障ACID以外,存储引擎还要负责:
- 屏蔽I0细节提供更好的抽象
- 提供统计信息与Predicate Push Down能力
LSMT存储引擎的优势与实现
LSMT与B+Tree的异同
- 在B+Tree中,数据插入是原地更新的
- B+Tree在发生不平衡或者节点容量到达阈值后,必须立即进行分裂来平衡
- LSMT与B+Tree可以用统一模型描述
- 从高层次的数据结构角度来看二者没有本质的不同,可以互相转化
- 工程实践上还是用LSMT来表示一个Append-only和Lazy Compact的索引树,B+Tree 来表示一个Inplace-Update和Instant Compact的索引树。
- Append-only和Lazy Compact这两个特性更符合现代计算机设备的特性。
为什么要采用LSMT模型
HDD时代:顺序与随机操作性能不对称
SSD时代:顺序写与随机写性能不对称
这二者的共性是顺序写是一个对设备很友好的操作,LSMT符合这一点,而B+ Tree依赖原地更新,导致随机写。
LSMT存储引擎的实现,以RocksDB为例
write
- RocksDB写入流程主要有两个优化,批量WAL写入(继承自LevelDB)与并发MemTable更新
- RocksDB在真正执行修改之前会先将变更写入WAL, WAL写成功则写入成功。
- 多个写入者会选出一个Leader,由这个Leader来一次性写入WAL,避免小I0。
- 不要求WAL强制落盘(Sync) 时,批量提交亦有好处,Leader可以同时唤醒其余Writer,降低了系统线程调度开销。
- 没有批量提交的话,只能链式唤醒。
- 链式唤醒加大前台延迟。
Snapshot & SuperVision
- RocksDB的数据由3部分组成,MemTable/ ImmemTable / SST.持有这三部分数据并且提供快照功能的组件叫做SuperVersion。
- MemTable和SST的释放依赖于引用计数。对于读取来说,只要拿着SuperVersion, 从MemTable一级一级向下,就能查到记录。拿着SuperVersion不释放,等于是拿到了快照。
- 如果所有读者都给SuperVersion的计数加1,读完后再减1,那么这个原子引用计数器就会成为热点。CPU在多核之间同步缓存是有开销的,核越多开销越大。
- 为了让读操作更好的scale, RocksDB做了一个优化是Thread Local SuperVersion Cache
Get & BloomFilter
- RocksDB的读取在大框架.上和B+ Tree类似,就是层层向下。
- 相对于B+Tree, LSMT点查需要访问的数据块更多。为了加速点查,一般LSMT引擎都会在SST中嵌入BloomFilter。
Level
- Compact在LSMT中是将Key区间有重叠或无效数据较多的SST进行合并,以此来加速读取或者回收空间。Compact 策略可以分为两大类,Level和Tier。下图是Level 策略。
- Level策略直接来自于LevelDB,也是RocksDB的默认策略。每一个层不允许有SST的Key区间重合。
B+ Tree和B Tree的最大区别是将所有数据都放在了叶子结点,从而优化了批量插入和批量查询的效率,而优化的核心逻辑就是无论是什么存储介质,顺序存储的效率一定优于随机存储。
LSMT的原理本质上就是在SSTable基础上增加了一个MemTable。
MemTable顾名思义,就是存放在内存中的数据结构,可以快速实现增删改查,比如红黑树,Skiplist都行。其次,我们还需要一个log文件,和数据库的binlog相当,记录数据发生的变化,用于服务器宕机时找回数据。
LSMT读取的时候,效率比B+树要低,但对于大数据的写入支持得更好。在大数据场景中,许多对于数据的吞吐量有着很高的要求,比如消息系统,分布式存储等。B+树就无法展现他的优势。
LSMT模型理论分析
- RocksDB是单机存储引擎,那么现在都说云原生,HBase 比RocksDB就更「云」一些,SST直接存储于HDFS上。
- 二者在理论存储模型上都是LSMT。
LSMT模型算法复杂度分析
- T: size ratio, 每层LSMT比上一层大多少,LO 大小为1,则L1大小为T, L2为T^2,以此类推
- L: level num, LSMT层数B:每个最小的10单位能装载多少条记录
- M:每个BloomFilter 有多少bits
- N:每个BloomFilter 生成时用了多少条Key
- S:区间查询的记录数量
Level
- Write
- 每条记录抵达最底层需要经过L次Compact,每次Compact Ln的一个小SST和Ln+1的一个大SST.
- 设小SST的大小为1,那么大SST的大小则为T,合并开销是1+T,换言之将1单位的Ln的SST推到Ln+1要耗费1+T的I0,单次Compact写放大为T。每条记录的写入成本为1/B次最小单位10。
- O(Write_ Level) = LT1/B =T*L/B
Tier
- Write
- 每条记录抵达最底层前同样要经过L次Compact,每次Compact Ln中T个相同尺寸的SST放到Ln+ 1。
- 设SST大小为1,那么T个SSTCompact的合并开销是T,换言之将T单位的Ln的SST推到Ln+1要耗费T的10,单次Compact的写放大为T/T=1。每条记录的写入成本为1/B次最小单位10。
- O(Write_ Tier) = L 1 1/B = L/B
总结:Tier 策略降低了写放大,增加了读放大和空间放大,Level 策略增加了写放大,降低了读和空间放大。