LSMT存储引擎解析｜青训营笔记

2022-12-17 阅读 62

LSMT存储引擎解析｜青训营笔记

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

一、课程概述

介绍LSMT存储引擎的布景、优势与完结
介绍LSMT等模型理论
介绍LSMT存储引擎调优

二、具体内容

1. LSMT存储引擎

1.1 LSMT的历史

LSMT是log-structured merge-tree的缩写
相较而言B-Tree早得多
早起数据库一般采用B-Tree，近期则是LSMT为多

1.2 LSMT基础

Append-only write+择机compact来保护结构的索引树
manifest log传输给write-ahead-log WAL
写入memtable
当memtable满后 flush进L0 cache生成SST file
compaction（merge sort，remove）

1.3 存储引擎是什么

单机数据库MySQL大致分为核算层和存储层
- 核算层负责SQL解析、查询优化、计划履行
- 数据库ACID特性强依赖于存储引擎
  - Atomicity原子性：依赖于WAL/Redo Log
  - Consistency（correctness）：依赖于数据库整体
  - Isolation：存储引擎snapshot/2-phase-lock
  - Durability：flusher遵从sync语义
此外存储引擎还要负责
- 屏蔽IO细节供给更好抽象
  - 存储引擎不掌控IO细节，操作系统接收，例如运用mmap的问题：
    - 落盘时机不确定构成事务不安全
    - IO stall:用户态程序无法干预，不可控
    - 错误处理繁琐：硬件错误用户无法获知，需求完整性校验
    - 无法彻底发挥硬件功用：要切换到内核态
- 供给计算信息与predicate push down能力：parquet只需求部分column时下推给存储引擎读取部分即可

2.LSMT的优势和完结

2.1 LSMT与B+树存储

在B+树中数据刺进原地更新
B+树不平衡或节点容量阈值后有必要当即割裂来平衡
LSMT与B+树统一模型，二者能够互相转化
- LSMT表明append-only和lazy compact的索引树
- B+树表明inplace-update和instant compact的索引树
append-only和lazy compact更契合现代核算机设备特性

2.2 为何要采用LSMT模型

核算机存储/工程界运用indirection处理资源的不对称性
存储引擎面临的资源不对称性在不同时期不同
- HDD时代：次序与随机操作功用不对称；机械硬盘需求磁盘旋转和机械臂移动进行读写，次序写吞吐是随机读的25倍；
- SSD时代：次序写与随机写功用不对称；因为SSD随机写会对主控带来GC压力，次序写吞吐是随机写6倍；
次序写对设备友爱，LSMT契合次序写；B+树依赖原地更新导致大量随机写（不友爱）

2.3 LSMT存储引擎完结，以RocksDB为例

2.3.1 RocksDB写完结

WAL
- 需求写WAL（重启时能够确保原子性），多个写入者选出一个Leader，由Leader一次性写入WAL，防止小IO；写完后唤醒一切writer
- 不要求WAL强制落盘（sync）时，批量提交亦有好处；没有批量提交时只能链式唤醒，加大前台推迟
MemTable
- 在LevelDB基础上添加并发Memtable写入优化
- WAL一次性写入完结后唤醒一切writer并行写入MemTable
- 由最终一个完结MemTable写入的writer履行收尾工作（退出write group）

2.3.2 RocksDB snapshot和supervision

数据由MemTable/ImmemTable/SST组成，持有三部分数据并且供给快照功用的组件叫做supervision
MemTable和SST释放依赖于引用计数，关于读取只需有supervision从memtable一级一级向下就能查到记载；拿着supervision不释放等于拿到快照。
如果一切读者给supervision计数+1读完-1，原子引用核算器成为热门；运用了thread local cache
- 没有时，读取频频获取和释放supervision，对CPU缓存不友爱
- 运用thread local cache缓存，只需求检查supervision的version没过期，并标记thread local cache正在运用即可；对CPU缓存友爱
- 若superversion过期需求从头生成，当更新时需求标记一切人持有的superversion失效

2.3.3 RocksDB Get和BloomFilter

读取上和B+树类似，层层向下
- LSMT点查需求访问的数据块更多，加快点查一般LSTM会在SST中引用BloomFilter
- BloomFilter能够确保数据不在该块中，但只能大概率确保数据在该块中

2.3.4 Compact

Compact在LSTM中将Key区间有堆叠或无效数据较多的SST进行兼并以此加快读取或回收空间
- 战略：Level和Tier
Level 战略来自于LevelDB，每层不答应SST的key区间重合
- 例如用户写0-100 SST，和原有0-100SST merge构成一个新的0-100的大SST（小SST和大SST兼并）
- 写扩大问题/不均匀
Tier战略答应LSMT每层有多个区间重合的SST
- 当本层重合SST区间或总内存巨细到达上限，挑选多个重合SST向下推构成新的SST
- 理论上每层SST区间巨细挨近，merge功率高
- 读扩大添加交换写扩大减小：更多重合SST需求更多读取

3. LSTM理论分析

3.1 HBase：cloud-native

3.2 LSMT模型算法 复杂度分析

T：size ratio即每层比上层大多少，L0为1，L1为T…
L：level num，LSMT层数
B：每个最小IO单位能装载多少记载
M：每个BloomFilter有多少Bits
N：每个BloomFilter生成用了多少key
S：区间查询的记载数量
e^(-M/N)：bloom filter失功率

3.2.1 Level

写操作
- 每条记载需求经过L次Compact，每次Compact Ln的一个小SST和Ln+1的大SST
- 设小SST巨细为1，大SST为T，兼并1+T，单次写扩大为T
- 每条记载写入本钱为1/B次最小单位IO
- O（write_level）= L*T*1/B = T*L/B
point lookup
- 每条key最多L个堆叠区间
- bloom filter失功率为e^(-M/N)，失效时访问下一层
- O(pointLookup_level)=L*e^(-M/N)
- 不乘1/B因为写入能够批量提交拉低本钱，但读取时有必要对其最小读取单元尺寸

3.2.2 Tier

写操作
- 每条记载需求经过L次Compact，每次Compact Ln中T个相同尺寸的SST到Ln+1
- SST巨细为1，T个兼并开支为T；
- 将T单位Ln SST推到Ln+1需求T的IO，单次写扩大为1
- 每条记载写入本钱为1/B次最小单位IO
- O（write_level）= L*1*1/B = L/B
point lookup
- 每条key有L层
- 每层最多有T个堆叠区间SST，关于整体来说有T*L个或许射中的SST
- bloom filter失功率为e^(-M/N)，失效时访问下一层
- O(pointLookup_level)=T*L*e^(-M/N)
- 不乘1/B因为写入能够批量提交拉低本钱，但读取时有必要对其最小读取单元尺寸

3.2.3 其他复杂度

Short Range Scan复杂度：level-O(L)；Tier-O(T*L)
space amplification复杂度: level-上层都是垃圾 O(T+1/T)；Tier：O(T)

3.2.4 总结

Tier战略下降了写扩大，添加了读扩大和空间扩大；
Level战略添加了写扩大，下降了读和空间扩大；

4. 实例

4.1 TerarkDB

KV别离：分为value不同长度；value长的记载独自存储（防止compaction频频挪动）
小key大value，写多读少，推迟大幅度下降，长尾消失，能够接受比rocksDB高50%负载
Flink流处理状况存储
- 均匀CPU开支下降26%～39%
- 峰值CPU开支下降67%
- 均匀容量下降17%～31.2%

4.2 发展趋势

新硬件
- 新存储技术：SMR HDD/Zoned SSD/OpenChannel SSD，PMem
- 如何在新硬件上设计/改进存储引擎是热门
- L0->PMem下降写扩大
新模型
- LSMT不能应对一切工况
- WiscKey经过额定添加value store存储大value记载下降整体写扩大
- REMIX
新参数/新工况
- 在现有模型工况下进行参数调残
- LSMB在最终层运用level，上层tier，经过在最终一层外SST加大bloomFilter的bits数躲避Tier Compaction带来的点查劣化

三、个人总结

这节课学习了LSMT存储引擎的布景、优势、理论与完结，及其调优的进程。因为我没有接触过相关算法，进一步比对B+树学习相关算法是十分必要的。

APP MySQL 功率复杂度存储引擎笔记算法青训