MiniOB LSM-Tree 存储引擎¶

LSM-Tree 背景介绍¶

LSM-Tree 是一种数据结构，可用于存储键值对。LSM-Tree 采用了多层的结构，存储部分可以分为内存和磁盘两个部分。内存中的部分称为 MemTable，磁盘中的部分称为 SSTable(Sorted String Table)。LSM 树通过 Append-Only 的方式提供高效的数据写入，为了优化读取性能，LSM-Tree 通过 Compaction 操作定期重新组织数据。

OceanBase 数据库的存储引擎也是基于 LSM-Tree 架构，将数据分为静态基线数据（放在 SSTable 中）和动态增量数据（放在 MemTable 中）两部分，其中 SSTable 是只读的，一旦生成就不再被修改，存储于磁盘；MemTable 支持读写，存储于内存。数据库 DML 操作插入、更新、删除等首先写入 MemTable，等到 MemTable 达到一定大小时转储到磁盘成为 SSTable。在进行查询时，需要分别对 SSTable 和 MemTable 进行查询，并将查询结果进行归并，返回给 SQL 层归并后的查询结果。同时在内存实现了 Block Cache 和 Row cache，来避免对基线数据的随机读。关于 OceanBase 数据库的更多细节可以参考：https://www.oceanbase.com/docs/oceanbase-database-cn

ObLsm 是一个为教学设计的 LSM-Tree 结构的 Key-Value 存储引擎。ObLsm 本身是一个独立于 MiniOB 的模块，可以独立编译使用。ObLsm 包含了 LSM-Tree 中的关键结构，可以帮助大家学习 LSM-Tree 架构。 MiniOB 中也基于 ObLsm 实现了一个基于 LSM-Tree 的表引擎，可以将表数据以 Key-Value 的格式存储到磁盘。

ObLsm 存储引擎¶

下面会对 ObLsm 的各个模块作简单介绍，便于大家对 ObLsm 有一个初步的了解，更多细节可以参考源代码 src/oblsm。

MemTable¶

MemTable 是一种内存数据结构，用作处理即将到来的操作（insert/delete/update）的缓冲区（buffer）。很多数据结构都可以用于 MemTable 的实现，现有的 LSM-Tree 实现（如 LevelDB/RocksDB）中多采用 SkipList，ObLsm 目前也使用 SkipList 作为 MemTable 的底层数据结构。ObLsm 将 insert/update/delete 都视作一条记录来插入到 MemTable 中。

insert：将一条记录插入到 MemTable 中。
update：将一条时间戳更大的记录插入到 MemTable 中。
delete：将一条 value 为空的记录插入到 MemTable 中。

MemTable 将插入的 Key-Value 编码为如下的记录存储。

    ┌───────────┬──────────────┬───────┬──────────────┬──────────────────┐
    │           │              │       │              │                  │
    │key_size(8)│ key(key_size)│ seq(8)│ value_size(8)│ value(value_size)│
    │           │              │       │              │                  │
    └───────────┴──────────────┴───────┴──────────────┴──────────────────┘

其中，key_size 和 value_size 分别表示 key+seq 和 value 的长度，seq 表示记录的时间戳。括号中表示占用字节数。

MemTable 的实现位于：src/oblsm/memtable/，在代码中，我们将上图中的key 称为 user_key，将 key + seq 称为 internal_key，将key_size + key + seq 称为 lookup_key。

SkipList¶

SkipList（跳表）是用于有序元素序列快速搜索的一个数据结构，SkipList 是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。SkipList 在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。

SkipList 的实现位于：src/oblsm/memtable/ob_skiplist.h

MemTableIterator¶

MemTableIterator 提供了一种遍历 MemTable 的机制。它可以按序访问 MemTable 中的所有键值对。

MemTableIterator 的实现位于：src/oblsm/memtable/ob_memtable.h::ObMemTableIterator

MemTable 转储¶

MemTable 转储是将内存中的 MemTable 持久化到磁盘上的过程。当 MemTable 达到一定大小时，会被转储为不可变的 SSTable。转储过程通常包括排序数据、生成 SSTable 文件并将其写入磁盘。

转储相关代码位于：src/oblsm/oblsm_impl.h::ObLsmImpl::try_freeze_memtable

SSTable¶

MemTable 的大小达到限制条件，MemTable 的数据以按顺序被转储到磁盘中，被转储到磁盘中的结构称为（SSTable：Sorted Strings table）。

SSTable 是一种有序的键值对存储结构，它通常包含一个或多个块（block），每个块中包含一组有序的键值对。

SSTable 的存储格式示例如下：

      ┌─────────────────┐
      │    block 1      │◄───┐
      ├─────────────────┤    │
      │    block 2      │    │
      ├─────────────────┤    │
      │      ..         │    │
      ├─────────────────┤    │
      │    block n      │◄─┐ │
      ├─────────────────┤  │ │
 ┌───►│  meta size(n)   │  │ │
 │    ├─────────────────┤  │ │
 │    │  block meta 1   ├──┼─┘
 │    ├─────────────────┤  │
 │    │      ..         │  │
 │    ├─────────────────┤  │
 │    │  block meta n   ├──┘
 │    ├─────────────────┤
 └────┤                 │
      └─────────────────┘

其中，block 表示由若干键值对组成的数据块。block meta 用于存储 block 的元信息，包括 block 的大小、block 的位置信息，block 中的键值对数量等。

SSTable 的实现位于：src/oblsm/table/

Block¶

为了提高整体的读写效率，一个sstable文件按照固定大小划分为 Block。每个Block中，目前只存储了键值对数据。 Block 的存储格式如下：

      ┌─────────────────┐
      │    entry 1      │◄───┐
      ├─────────────────┤    │
      │    entry 2      │    │
      ├─────────────────┤    │
      │      ..         │    │
      ├─────────────────┤    │
      │    entry n      │◄─┐ │
      ├─────────────────┤  │ │
 ┌───►│  offset size(n) │  │ │
 │    ├─────────────────┤  │ │
 │    │    offset 1     ├──┼─┘
 │    ├─────────────────┤  │
 │    │      ..         │  │
 │    ├─────────────────┤  │
 │    │    offset n     ├──┘
 │    ├─────────────────┤
 └────┤  offset start   │
      └─────────────────┘

Block 的主要实现位于 src/oblsm/table/ob_block.h

SSTableBuilder¶

用于构造一个 SSTable，主要实现位于 src/oblsm/table/ob_sstable_builder.h

BlockBuilder¶

用于构造一个 Block，主要实现位于 src/oblsm/table/ob_block_builder.h

Compaction¶

Compaction 是 LSM-Tree 的关键组件，Compaction 会将多个 SSTable 合并为一个或多个新的 SSTable。Compaction 的实现主要位于 src/oblsm/compaction/

基于 ObLsm 的表引擎¶

MiniOB 基于 ObLsm 模块实现了一个 LSM-Tree 表引擎，用于以 Key-Value 格式存储表数据。表引擎的实现位于：src/observer/storage/table/lsm_table_engine.h。

LSM-Tree 表引擎使用方法：在创建表时指定 engine=lsm，即可使用 LSM-Tree 表引擎。当不指定engine 或指定 engine=heap，将使用堆表作为表数据的存储方式。

create table t1 (id int primary key, name varchar(20))engine=lsm;

在 MiniOB 中，使用关系型模型来描述表结构，而 LSM-Tree 表引擎将表数据以 Key-Value 的形式存储到磁盘，因此需要提供一种机制来将关系型模型转换为 Key-Value 模型。目前 MiniOB 中以自增列作为 Key，将行数据以 Table::make_record 编码为 Value。通过 orderedcode 来对 Key 列做编码，使得在编码后 Key 的字典序上比较与 Key 对应的原始序列（目前可以认为只有自增列一列，后续支持主键后，Key 会对应表中的多列）上进行比较具有相同的顺序。

此外，为了在同一个 LSM-Tree 引擎中存储多张表的数据，MiniOB 为每一张表分配一个 TableID，并在 Key 中加入 TableID 作为前缀。

因此，每行数据按照如下规则编码成 (Key, Value) 键值对：

Key:   t{TableID}r{AutoIncID}
Value: [col1, col2, col3, col4]