共计 6565 个字符，预计需要花费 17 分钟才能阅读完成。
欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/
本文来自 OceanBase 社区分享，仅限交换探讨。原作者马伟，长期从事互联网广告检索系统的研发，对数据库，编译器等畛域也有浓厚兴趣。
上文讲到，传统单机数据库受制于底层存储技术及扩大瓶颈，无奈满足互联网席卷而来的海量存储和并发读写事务需要。由此衍生出各类数据库扩大技术，其中以 NewSQL 为代表的分布式数据库多采纳 LSM 树用于构建底层的存储系统，对存储和读写申请的扩大都有十分好的反对。那么，LSM 树到底有何独特之处？本文从利用及操作层面进行介绍。
1. 概念介绍
LSM-Tree 全称是 Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分利用 磁盘的程序写性能要远高于随机写性能这一个性，将批量的随机写转化为一次性的程序写 。其最早是在 1996 年的论文《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 Key
BigTable 的 RowKey 概念与关系数据库的 PrimaryKey 相似，是一行数据的惟一标识。RowKey 能够是任意二进制字符串，最大容量为 64KB。然而在大多数场景下，字节数只有 10～100 Bytes 左右。Bigtable 的表依照 RowKey 的字典序组织数据。即 BigTable 表中的数据是全局有序的。 - Column Key 与 ColumnFamily
ColumnKey 相似关系数据库中的列，个别示意一种数据类型，也能够是一个简单 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.co…
- 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.co…
- Spanner 论文(2017):https://static.googleusercontent.com/media/research.google.co…
- 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-d…
- OB 数据存储管理：https://www.oceanbase.com/docs/oceanbase-database/oceanbase-d…
- OB 数据库压缩个性：https://zhuanlan.zhihu.com/p/49161275
- OB 存储引擎详解：https://www.modb.pro/db/137286
- OB 博客文章全系列：https://open.oceanbase.com/articles
