分享：数据库存储与索引技术（二） 分布式数据库基石——LSM 树

欢迎访问 OceanBase 官网获取更多信息：https://www.oceanbase.com/

本文来自 OceanBase 社区分享，仅限交流探讨。原作者马伟，长期从事互联网广告检索系统的研发，对数据库，编译器等领域也有浓厚兴趣。

上文讲到，传统单机数据库受制于底层存储技术及扩展瓶颈，无法满足互联网席卷而来的海量存储和并发读写事务需求。由此衍生出各类数据库扩展技术，其中以 NewSQL 为代表的分布式数据库多采用 LSM 树用于构建底层的存储系统，对存储和读写请求的扩展都有非常好的支持。那么，LSM 树到底有何独特之处？本文从应用及操作层面进行介绍。

1. 概念介绍

LSM-Tree 全称是 Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分利用磁盘的顺序写性能要远高于随机写性能这一特性，将批量的随机写转化为一次性的顺序写。其最早是在 1996 年的论文[《The Log-Structured Merge-Tree (LSM-Tree)》](https://open.oceanbase.com/blog/The Log-Structured Merge-Tree (LSM-Tree))中提出。

LSM 树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中，称为 C0 tree，具体可以是任何方便健值查找的数据结构，比如红黑树、map 之类，甚至可以是跳表。另外一个存储结构常驻在硬盘中，称为 C1 tree，具体结构类似 B 树。

在 LSM 树中，最低一级即最小的 C0 树位于内存,而更高级的 C1、C2…树都位于磁盘里。数据会先写入内存中的 C0 树，当它的大小达到一定阈值之后，C0 树中的全部或部分数据就会刷入磁盘中的 C1 树，如下图所示。在实际应用中，为防止内存因断电等原因丢失数据，写入内存的数据同时会顺序在磁盘上写日志，类似于预写日志(WAL)，这就是 LSM 这个词中 Log 一词的来历。

1.1. BigTable

LSM 树在前互联网时代并未得到很好的重视，传统的关系型数据库的存储和索引结构依然以基于页面(Page)的 B+树和 HashTable 为主。随着互联网规模的扩大和普及，在面对十亿级的用户接入，以及 PB 规模数据的写入，传统的关系型数据库已经难以支撑。Google 2006 年发表的论文《Bigtable: A Distributed Storage System for Structured Data》提出了利用 LSM 树在 GFS 上构建可线性扩展的 KV 系统的方案，即大名鼎鼎的 BigTable 系统。

1.1.1. 数据模型

BigTable 的数据模型，每一个键值对的 Key 都为 Row key + Column key + Timestamp 的结构，Value 则是任意二进制字符串：

(row:string, column:string,time:int64) -> string

举一个具体的例子：比如，一个存储了大量网页及其相关信息的表 Webtable，Webtable 使用 URL 作为行名，使用网页的某些属性作为列名，网页的内容存入 contents 列中，并使用获取该网页的时间戳标识同一个网页的不同版本。在 Bigtable 中，Webtable 的存储范例如下图所示：

BigTable 引入了 RowKey, ColumnFamily, ColumnKey, TimeStamp 等概念来方便用户抽象和管理自己的数据。其各自作用如下：

• Row KeyBigTable 的 RowKey 概念与关系数据库的 PrimaryKey 类似，是一行数据的唯一标识。RowKey 可以是任意二进制字符串，最大容量为 64KB。但是在大多数场景下，字节数只有 10～100 Bytes 左右。Bigtable 的表按照 RowKey 的字典序组织数据。即 BigTable 表中的数据是全局有序的。

• Column Key 与 ColumnFamilyColumnKey 类似关系数据库中的列，一般表示一种数据类型，也可以是一个复杂 Object 序列化后的一串二进制字符串。若干个有业务含义的 ColumnKey 聚合在一起被称为 ColumnFamily(列族)。ColumnFamily 是 access control（访问控制）、disk and memory accounting（磁盘和内存计算）的基本单元。

• TimeStamp

Bigtable 中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是 64 位整型，既可以由系统赋值也可由用户指定。时间戳通常以 us（微秒）为单位。时间戳既可以由 Bigtable 进行分配，也可以由客户端进行分配，如果应用程序希望避免冲突，应当生产唯一的时间戳。表项的不同版本按照时间戳倒序排列（大的在前，时间戳越大表明数据加入的时间越晚），即最新的数据排在最前面，因而每次查询会先读到最新版本。为了简化多版本数据的管理，每个列族都有两个设置参数用于版本的自动回收，用户可以指定保存最近 N 个版本，或保留足够新的版本(如最近 7 天的内容)。

1.1.2. BigTable 中 LSM 树实现

BigTable 的数据模型，在概念上抽象出了完整的 Table, Row, Column 等概念，方便应用进行业务抽象。但是在实现上，BigTable 是如何何 LSM 树进行结合的呢？我们前面提到，LSM 是一个 K-V 结构的数据结构，在 BigTable 中，每个 Table 即对应一棵 LSM 树。BigTable 通过分隔符(这里假定为":")，将 Rwo, ColumnFamily, ColumnKey, TimeStamp 组合成一个 Key，由此来索引对应的 Value 值，即

RowKey:ColumnFamily:ColumnKey:TimeStamp->Value

BigTable 中即以这种格式的 K-V 数据对 LSM 树进行读写：

如上图的 BigTable 的 LSM 树实现中，提出了 MemoryTable 和 SSTable 的概念。在原始的 BigTable 论文中，只提到了这两种数据结构的作用，并未详细介绍其实现。2011 年 Google 开源了基于 LSM 树的单机 K-V 引擎 LevelDB，其中包含了 MemoryTable 和 SSTable 的具体实现：

• MemoryTable，即对应 LSM 树论文中的 C0 Tree，在 LevelDB 中被分为了可以随时修改(插入/删除)的 MemTable，以及不可变的**Immutable MemTable。**当 MemTable 数据写满之后(通常是看占用内存超过一定 Quota 之后)，将 MemTable 固化成 SSTable 格式并常驻内存中。

• SSTable，即对应 LSM 论文中的 C1, C2, ..., Ck Tree。LevelDB 中每个 SSTable 大小基本固定(2M)，SSTable 中的数据按照 Key 进行排序，每一层的 SSTable 都是按照 Key 全局有序的。当内存中的 Immutable MemTable 太多系统需要释放内存时，此时会将 Immutable MemTable 的数据写入到第一层的 SSTable 磁盘并与第一层的已有 SSTable 进行合并，从而保证 C1 层的所有 SSTable 是全局有序的。磁盘上的每一层的 SSTable 达到一定 Size 之后都会与下一层的 SSTable 进行合并。

1.2. LSM 树在分布式数据库中的应用

之所以称 LSM 树是各类分布式数据库的基石，是因为自从 2011 年 Google 开源 LevelDB 之后，各类分布式 NewSQL 数据库，基本都是基于 LSM 树来构建其存储系统的，有些甚至直接基于 LevelDB 的改进开源版版 RocksDB 来构建的。

以开源的 TiDB 为例(TiDB 开源且文档齐全，所以以它为例)，其是在开源的 RocksDB 基础上，加上自己开发实现的 Multi-Raft 协议，将 TiDB 的存储层统一封装成了独立的 KV 存储服务 TiKV。TiDB 的 SQL/事务层(TiDB Server)是无状态的，可以和 TiKV 分别独立扩容。

对比蚂蚁的 OceanBase，则是将 LSM 树结构和数据库其他核心功能实现在了一个单一的应用 OBServer 中。这样的好处是存储层和上层功能可以更好的进行整合和优化，对本地数据的访问可以减少一次 RPC 请求。与 TiDB 相比，则牺牲了一部分灵活性(TiDB 可以单独就计算或者存储扩容，OB 只能整体扩容)。

2. LSM 树各类操作

LSM 树将任何的对数据操作都转化为对内存中的 Memtable 的一次插入。Memtable 可以使用任意内存数据结构，如 HashTable，B+Tree，SkipList 等。对于有事务控制需要的存储系统，需要在将数据写入 Memtable 之前，先将数据写入持久化存储的 WAL(Write Ahead Log)日志。由于 WAL 日志是顺序 Append 到持久化存储的，因此无论对磁盘还是 SSD 都是非常友好的。

2.1. 数据变更

LSM 树支持常见的变更操作，插入，删除，更新。常见的实现里，为了统一变更的数据结构标识，往 MemTable 里写入的除了<Key, TimeStamp, Value>三元组外，还会带上操作的类型。所有的变更操作并不直接修改磁盘上的数据，而只是将变更写入 MemTable。因此数据变更除了 WAL 日志一次顺序 IO 之外，没有额外的任何随机 IO，插入效率非常高。

通常 MemTable 的大小有限，当 MemTable 占用的内存超过一定大小或者内存比例之后，LSM 需要将当前的 MemTable 先冻结为 Immutable MemTable，然后通过后台线程将其持久化为 SSTable 到外部存储。持久化的过程中，会创建一个新的 MemTable 用于接收新的数据变更，Immutable Memtable 则变成只读的。持久化过程在不同实现中不一样，有的实现会简单的将其写入磁盘，有的则会与磁盘上已有的 SSTable 进行合并。当持久化完成之后，Immutable MemTable 的内存将会被释放。

2.2. 数据读取

2.2.1. 点查

数据读取分为点查或者范围查询。点查即针对单行数据进行查询，如常见的 SQL 语句：

select id, name, grade, score from student where id = '3042111009';

我们假定这里 id 字段即是要查询的 LSM 树的 Key，那么点查询将会是如下过程：

在不考虑 SSTable 缓存的情况下，一次点读查询的代价是若干次内存查询 + n 次磁盘 IO，其中 n 是磁盘上的 SSTable 层数。可以看到，LSM 树一次数据变更只需要一次内存插入即可，而一次点查询却需要若干次磁盘 IO。

2.2.2. 范围查询

范围查询则是针对某一个范围的数据进行查询，如针对某个用户的 10 月份历史消费账单的数据查询：

select * from user_bill where id = '3042111009' and date >= '2021-10-01' and date <= '2021-10-31';

范围查询根据表的查询 Key 的范围区间[StartKey, EndKey]，通常会先对 StartKey 在 LSM 树上逐层做 LowerBound 查询，即每一层上找到大于或等于 StartKey 的数据的起始位置。由于 LSM 树每一层都是有序的(内存中的 MemTable 如果是无序的 Hash 表则需要全部遍历)，只需要从这个起始位置开始读取数据，直到读取到 EndKey 为止。

2.3. 数据合并(Compaction)

随着 LSM 树中写入数据的增多，不断的有 MemTable 被写入到磁盘上的作为 SSTable 存储。随着数据写入不断增多，转储的 SSTable 也会越来越多。但是太多 SSTable 会导致数据查询 IO 次数增多，因此后台尝试着不断对这些 SSTable 进行合并，这个合并过程称为 Compaction。Compaction 是 LSM 树实现中最复杂的部分，因为其持续对 IO 以及 CPU 资源的使用，会对系统的负载造成很大影响，影响上层业务的稳定性。业内也有很多不同的 Compaction 策略尝试缓解这一问题，这将在下篇文章《LSM 树实现案例》中详细介绍。

目前主流的 LSM 树实现，其 Compaction 分为两类：Minor Compaction 和 Major Compaction。

2.3.1. Minor Compaction

Minor Compaction 顾名思义，即代价较小的 Compaction，很多实现里，这步操作主要就是将内存中的 Immutable MemTable 作为 SSTable 写入到磁盘。实际并不做磁盘上的 SSTable 之间的合并。因此在这种实现下，磁盘上的第一层 SSTable，即 C1 层的 SSTable 之间，互相是可能会有数据重叠的。读取查询的时候需要将 C1 层的所有 SSTable 都读取才能进行正确查询。

2.3.2. Major Compaction

Major Compaction 的触发策略可能有多种，如某一层的数据达到一定的阈值，也可能是用户手动触发等。因为 Major Compaction 代价比较大，不同的实现里都有不同的触发策略。其主要的作用即是在和层之间进行 Merge Sort，将两层的数据归并到，去除删除或者旧版本的数据，保证同一层的数据之间是完全有序的。

3.小结

本文讲述了 LSM 树的历史、基本概念和各种重要操作，以及 Google 在此基础上的一系列开创性的贡献，如 LevelDB、BigTable、Spanner 等。下一篇文章我们将以 OceanBase v3.x 为例，重点介绍 LSM 树 OceanBase 中的实现和应用。

参考文献

1. LSM 树及 BigTable

• LSM 论文 1996：https://www.cs.umb.edu/~poneil/lsmtree.pdf

• LSM 树综述：https://zhuanlan.zhihu.com/p/351241814

• 深入浅出 LevelDB：https://mrcroxx.github.io/categories/%E6%B7%B1%E5%85%A5%E6%B5%85%E5%87%BAleveldb/
  

• RCFile 格式参考：https://cloud.tencent.com/developer/article/1328762

• BigTable 论文 2006:https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/bigtable-osdi06.pdf

• LSM 树综述：https://zhuanlan.zhihu.com/p/351241814

• 深入浅出 LevelDB：https://mrcroxx.github.io/categories/%E6%B7%B1%E5%85%A5%E6%B5%85%E5%87%BAleveldb/
  

2. 分布式数据库

• Spanner 论文(2012): https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/spanner-osdi2012.pdf

• Spanner 论文(2017):https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/46103.pdf

• Google Spanner 论文解读:https://cloud.tencent.com/developer/article/1131036

• TiDB 整体架构：https://docs.pingcap.com/zh/tidb/stable/tidb-architecture

• TiDB 存储架构：https://docs.pingcap.com/zh/tidb/stable/tidb-storage

• TiDB 博客全系列：https://pingcap.com/zh/blog/

• OB 数据库存储架构：https://www.oceanbase.com/docs/oceanbase-database/oceanbase-database/V3.2.1/overview-4

• OB 数据存储管理：https://www.oceanbase.com/docs/oceanbase-database/oceanbase-database/V3.2.1/consolidation-management-overview

• OB 数据库压缩特性：https://zhuanlan.zhihu.com/p/49161275

• OB 存储引擎详解：https://www.modb.pro/db/137286

• OB 博客文章全系列：https://open.oceanbase.com/articles