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

1. 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。

1. O(Write_ Level) = LT1/B =T*L/B

Tier

1. 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。

1. O(Write_ Tier) = L 1 1/B = L/B

总结：Tier 策略降低了写放大，增加了读放大和空间放大，Level 策略增加了写放大，降低了读和空间放大。