LSMT存储引擎浅析 | 青训营笔记

这是我参与「第四届青训营 」笔记创作活动的第15天

LSMT存储引擎浅析

介绍

LSMT，即Log-Structured Merge-Tree，这是一个经典的数据结构，在大数据系统中有着非常广泛的应用。很多耳熟能详的经典系统，底层就是基于LSMT实现的。早期的数据库系统一般都采用B-Tree家族作为索引，例如MySQL。2000年后诞生的数据库大多采用LSMT索引，例如Google BigTable，HBase等，是通过Append-only Write+择机ompact来维护结构的索引树。

存储引擎

以单机数据库MySQL为例，存储引擎大致可以分为计算层和存储层（存储引擎层）。

计算层主要负责SQL解析、查询优化、计划执行。数据库的ACID特性，在MySQL中全部强依赖于存储引擎实现。

除了保障ACID以外，存储引擎还要负责屏蔽IO细节以提供更好的抽象，提供统计信息于PredicatePush Down能力。

存储引擎不掌握IO细节，让操纵系统接管，例如使用mmap，会有如下问题：落盘时机不确定造成的事务不安全、IO Stall、错误处理繁琐、无法完全发挥硬件性能

LSMT存储引擎的优势与实现

LSMT与B+Tree的异同

在B+Tree中，数据插入是原地更新的。B+Tree在发生不平衡或者节点容量达到阈值后，必须立即进行分裂来平衡。

LSMT与B+Tree可以用统一模型描述，从高层次的数据结构角度来看，二者没有本质的不同，可以互相转化

在工程实践上还是用LSMT来表示一个Append-only和Lazy Compact的索引树，B+Tree来表示一个Inplac-Update和Instant Compact的索引树。这是因为Append-only和Lazy Compact这两个特性更符合现代计算机设备的特性。

为什么采用LSMT模型？

在计算机存储乃至整个工程界都在利用Indirection处理资源的不对称性，存储引擎面对的资源不对称性在不同时期是不同的

在HDD时代，顺序与随机操作性能不对称，由于机械硬盘需要磁盘旋转和机械臂移动来进行读写，顺序写吞吐是随机读的25倍。（顺序操作远快于随机操作）

在SSD时代，顺序写与随机写性能不对称，由于SSD随机写会给主控带来GC压力，顺序写吞吐是随机写的6倍。（顺序写操作远快于随机写操作）

这二者的共性是顺序写是一个对设备很友好的操作，LSMT符合这一点，而B+Tree依赖原地更新，导致随机写

LSMT存储引擎的实现

RocksDB是一款十分流行的开源LSMT存储引擎，最早来自Fackbook(Meta)，应用于MyRocks，TiDB等数据库。在字节内部也有Abase，ByteKV，ByteNDB，Bytable等用户。接下来就以RocksDB为例，介绍LSMT存储引擎实现。

Write

写入流程主要有两个优化，批量WAL写入与并发Memtable更新

• 多个写入者会选出一个leader，由这个leader来一次性写入WAL，避免小IO
• 不要求WAL强制落盘（Sync）时，批量提交亦有好处，Leader可以同时唤醒其余writer，降低了系统线程调度开销

• 如果没有批量提交，只能链式唤醒，链式唤醒加大前台延迟

• 写完WAL还要写MemTable，RocksDB在继承LevelDB的基础上又添加了并发MemTable写入的优化。

• WAL一次性写入完成后，唤醒所有writer并行写入Memtable，由最后一个完成Memtable写入的writer执行收尾工作

在真正执行修改之前会先将变更写入WAL，WAL写成功则写入成功

Snapshot & SuperVision

• RocksDB数据由3部分组成，Memtable / Immemtable / SST，持有这三部分数据并提供快照功能的组件叫做SuperVision
• Memtable和SST的释放依赖于引用计数，对于读取来说，只要拿着SuperVision，从Memtable一级一级向下，就能查到记录。拿着SuperVision不释放，等于是拿到了快照。

如果所有读者都给SuperVersion的计数加1，读完后再减1，那么这个原子引用计数器就会成为热点。CPU在多核之间同步缓存是有开销的，核越多开销越大。为了让读操作更好的scale，RocksDB做了一个优化是Thread Local SuperVersion Cache

没有Thread Local缓存时,读取操作要频繁Acquire和Release SuperVersion，对CPU缓存不友好

Thread Local Supervision Cache：读取只需要检查一下SuperVision并标记Thread Local缓存正在使用即可，CPU缓存友好

Get&BloomFilter

RocksDB的读取在大框架上和B+Tree类似，就是层层向下。相对于B+Tree，LSMT点查需要访问的数据块更多。为了加速点查，一般LSMT引擎都会在SST中嵌入BloomFilter

Compact

Compact在LSMT中是将Key区间有重叠或无效数据较多的SST进行合并，以此来加速读取或者回收空间。Compact策略可以分为两大类，Level和Tier。

Level

Level策略来自于LevelDB，也是RocksDB的默认策略。每一个层不允许有SST的Key区间重合。有写放大的问题

Tier

Tier策略允许每层有多个区间重合的SST；读放大的增加来换写放大的减少

LSMT模型理论分析

LSMT模型算法时间复杂度分析

T:size ratio，每层LSMT比.上一层大多少,L0大小为1，则L1大小为T，L2为T^2,以此类推 L: level num，LSMT层数B:每个最小的io单位能装载多少条记录 M:每个BloomFilter有多少bits N:每个BloomFilter生成时用了多少条Key S:区间查询的记录数量

Level

• Tier策略降低了写放大，增加了读放大和空间放大
• Level策略增加了写放大，降低了读和空间放大

LSMT存储引擎调优案例与展望

TerarkDB

TerarkDB aka LavaKV是字节跳动内部基于RocksDB深度定制优化的自研LSMT存储引擎，其中完全自研的KV分离功能，上线后获得了巨大的收益，

KV分离简单的来说就是Value较长的记录的Value单独存储

Flink

在字节内部Flink流处理状态存储场景实测的收益结论：

• 平均CPU开销在3给作业上降低了26%~39%,
• 峰值CPU开销在广告作业上有明显的收益，降低了67%,
• 平均容量开销在3个作业上降低了17%~31.2%
• 直播业务某集群容量不收缩，TDB的schedule TTL GC 彻底解决了该问题

发展

硬件

随着硬件的发展，软件设计也会随之发生改变。近年来，出现了许多新的存储技术，例如SMR HDD ,Zond SSD /OpenChanned SSD,PMem等。如何在这些新硬件上设计/改进存储引擎是一大研究热点

模型

经典LSMT模型是比较简单的，有时候不能应对所有工况，可以提出新的模型来解决问题。

参数/工况

已有的模型,在新的或者现有工况下，参数设置的不合理，可以通过更精确的参数设置来提升整体性能。

总结

• 单机数据库的ACID特性依赖于存储引擎
• LSMT存储引擎的顺序写特性更适合现代计算机体系结构
• LSMT和B+Tree可以用同一模型描述并互相转化
• Level Compaction策略，降低了读放大和空间放大，增加了写放大。
• Tier Compaction策略，降低了写放大，增大了读放大和空间放大
• 分布式KV存储，如HBase，背后的理论模型与单机存储引擎RocksDB一样都是LSMT