ToB企服应用市场:ToB评测及商务社交产业平台

标题: TiDB 底层存储结构 LSM 树原理介绍 [打印本页]

作者: 尚未崩坏    时间: 2023-1-11 15:06
标题: TiDB 底层存储结构 LSM 树原理介绍
作者:京东物流 刘家存

随着数据量的增大,传统关系型数据库越来越不能满足对于海量数据存储的需求。对于分布式关系型数据库,我们了解其底层存储结构是非常重要的。本文将介绍下分布式关系型数据库 TiDB 所采用的底层存储结构 LSM 树的原理。
1 LSM 树介绍

LSM 树(Log-Structured-Merge-Tree) 日志结构合并树由 Patrick O’Neil 等人在论文《The Log-Structured Merge Tree》(https://www.cs.umb.edu/~poneil/lsmtree.pdf)中提出,它实际上不是一棵树,而是2个或者多个不同层次的树或类似树的结构的集合。
LSM 树的核心特点是利用顺序写来提高写性能,代价就是会稍微降低读性能(读放大),写入量增大(写放大)和占用空间增大(空间放大)。
LSM 树主要被用于 NoSql 数据库中,如 HBase、RocksDB、LevelDB 等,知名的分布式关系型数据库 TiDB 的 kv 存储引擎 TiKV 底层存储就是用的上面所说的 RocksDB,也就是用的 LSM 树。
2 LSM 树算法大概思路

LSM 树由两个或多个树状的结构组成。
这一节我们以两个树状的结构构成的简单的双层 LSM 树举例,来简单说下 LSM 树大概思路,让大家对 LSM 树实现有个整体的认识。

原论文中的图
2.1 数据结构

双层 LSM 树有一个较小的层,该层完全驻留在内存中,作为 C0 树(或 C0 层),以及驻留在磁盘上的较大层,称为 C1 树。
尽管 C1 层驻留在磁盘上,但 C1 中经常引用的节点将保留在内存缓冲区中,因此C1经常引用的节点也可以被视为内存驻留节点。
2.2 写入

写入时,首先将记录行写入顺序日志文件 WAL 中,然后再将此记录行的索引项插入到内存驻留的 C0 树中,然后通过异步任务及时迁移到磁盘上的 C1 树中。
2.3 读取

任何搜索索引项将首先在 C0 中查找,在 C0 中未找到,然后再在 C1 中查找。
如果存在崩溃恢复,还需要读取恢复崩溃前未从磁盘中取出的索引项。
2.4 Compact 过程

将索引条目插入驻留在内存中的 C0 树的操作没有 I/O 成本,然而,与磁盘相比,容纳 C0 组件的内存容量成本较高,这对其大小施加了限制。达到一定大小后,我们就需要将数据迁移到下一层。
我们需要一种有效的方法将记录项迁移到驻留在成本较低的磁盘介质上的 C1 树中。为了实现这一点,当插入达到或接近每一层分配的最大值的阈值大小,将进行一个滚动合并(Compact)过程,用于从 C0 树中删除一些连续的记录项,并将其合并到 C1 中。
Compact 目前有两种策略,size-tiered 策略,leveled策略,我们将在下面的内容里详细介绍这两种策略。
2.5 崩溃恢复

在 C0 树中的项迁移到驻留在磁盘上的C1树之前,存在一定的延迟(延迟),为了保证机器崩溃后C0树中的数据不丢失,在生成每个新的历史记录行时,首先将用于恢复此插入的日志记录写入以常规方式创建的顺序日志文件 WAL 中,然后再写入 C0 中。
3 LSM 树的组成

LSM树有三个重要组成部分,MemTable,Immutable MemTable,SSTable(Sorted String Table),如下图。

这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT
这几个组成部分分别对应 LSM 树的不同层次,不同层级间数据转移见下图。这节就是介绍 LSM 树抽象的不同层的树状数据结构的某个具体实现方式。

3.1 MemTable

MemTable 是在内存中的数据结构,用于保存最近更新的数据,会按照 Key 有序地组织这些数据。LSM 树对于具体如何组织有序地组织数据并没有明确的数据结构定义,例如你可以任意选择红黑树、跳表等数据结构来保证内存中 key 的有序。
3.2 Immutable MemTable

为了使内存数据持久化到磁盘时不阻塞数据的更新操作,在 MemTable 变为 SSTable 中间加了一个 Immutable MemTable。
当 MemTable 达到一定大小后,会转化成 Immutable MemTable,并加入到 Immutable MemTable 队列尾部,然后会有任务从 Immutable MemTable 队列头部取出 Immutable MemTable 并持久化磁盘里。
3.3 SSTable(Sorted String Table)

有序键值对集合,是 LSM 树组在磁盘中的数据结构。
其文件结构基本思路就是先划分为数据块(类似于 mysql 中的页),然后再为数据块建立索引,索引项放在文件末尾,并用布隆过滤器优化查找。
4 LSM 树的 Compact 策略

当某层数据量大小达到我们预设的阈值后,我们就会通过 Compact 策略将其转化到下一层。
在介绍 Compact 策略前,我们先想想如果让我们自己设计 Compact 策略,对于以下几个问题,我们该如何选择。
不同的选择会造成不同的读写策略,基于以上 3 个问题,又带来了 3 个概念:
不同的策略实际就是围绕这三个概念之间做出权衡和取舍,我们主要介绍两种基本策略:size-tiered 策略和 leveled 策略,这两个策略对于以上 3 个概念做了不同的取舍。
4.1 size-tiered 策略


4.1.1 算法

4.1.2 总结

由此可以看出 size-tiered 策略几个特点:
4.2 leveled 策略


4.2.1 算法

4.2.2 总结

由此可以看出 leveled 策略几个特点:
5 LSM 树的插入、修改、删除

从 LSM 树的名字,Log-Structured-Merge-Tree 日志结构合并树中我们大概就能知道 LSM 树的插入、修改、删除的方法了——顺序追加而非修改(对磁盘操作而言)。
6 LSM 树的查找

7 LSM 树和 B+ 树的比较

8 总结

LSM 树特点:顺序写入、Compact 操作、读、写和空间放大。
LSM 树适用场景:对于写操作吞吐量要求很高、读操作吞吐量要就较高的场景,目前主要在 NoSql 数据库中用的比较多。

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!




欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4