背景

在数据库开发中，有一个重要的操作叫“写盘”，就是将数据从内存转储到磁盘。在传统数据库如MySQL中，写盘包括几步，首先将数据写入缓存池；其次，保证数据的完整性，还会同时将数据写入“二进制日志文件”，保证系统故障时数据能够恢复；最后将数据写入磁盘。在此过程中，使用SSD盘、延迟写或增加缓存池大小等方式提升写入性能。

而在OceanBase 数据库中，写盘与传统数据库大不相同。由于OceanBase 存储引擎是基于LSM-Tree架构实现的，数据被分为了静态基线数据（放在 SSTable 中，存储于磁盘）和动态增量数据（放在 MemTable 中，存储于内存）两部分。当内存的增量数据达到一定规模的时候，会触发冻结转储操作，保证将要被转储的MemTable不再进行新的数据写入，同时生成新的活动MemTable（冻结，Freeze），以及将被冻结MemTable的数据存储到磁盘上以释放内存空间（转储，Mini Merge）。此时，一些小伙伴会存在疑问：到底如何读取那些所谓的"row"结构，才能将MemTable的数据存储到磁盘上？

本文从MemTable的结构、读行过程讲起，逐步带大家解开疑问，并对OceanBase 的MemTable产生新的认识。

MemTable的结构

OceanBase中的MemTable是由BTree和Hash Table两个数据结构结合而成，二者各司其职，BTree发挥其范围查询的能力，Hash Table发挥其点查的能力。什么意思呢？我们来看下面这张图。图中是BTree和Hash Table的一个结合结构，BTree的每个叶节点和Hash Table的节点都指向着某一个row节点，而row节点指向着一个链表（实现上是双向链表）。我们只需要知道，每个rowkey在MemTable中最终是对应着一个row节点（即一行数据），这行数据可能经过了insert、update、delete、insert的一系列操作，在OceanBase中，每个这样的操作都会通过一个MvccNode存储起来，并按照操作的先后顺序从尾到头组成一个MvccNode list，链表尾部是最新的操作。

好，到这里我们已经掌握了OceanBase中MemTable的"核心科技"了，也没那么复杂是不是？

接下来，我们一起经历一遍冻结后的MemTable在将要存储到磁盘时，逐行读取数据的过程，尽可能简单地加深我们对"核心科技"的理解。

Memtable迭代读行过程

为了方便大家自主阅读代码，后续介绍过程会贴出部分源码，所有源码都基于GitHub master分支。

容易理解的是，逐行读取数据是一个scan的过程，因此我们会通过遍历BTree而不是HashTable来完成读取。

整个迭代过程可以分为两个部分：一部分是对BTree的遍历，每次我们将得到一个rowkey对应的行，换句话说就是得到一个行的MvccNode list；另一部分则是对MvccNode list的遍历，过程中得到一个行的多版本数据。

那么，什么叫“行的多版本数据”呢？既然说到这，就不得不插入一段对MvccNode的解释。

我们刚才提到，每个MvccNode代表着一个操作，这个操作放到事务中来说的话，其事务的状态可能是已提交的，也可能是未提交的，就是图中的status（commit/uncommit）。MvccNode会记录事务的提交版本号，即图中的trans_version，对于未提交的操作来说，trans_version是MAX。

由于每个rowkey不允许多写，容易理解MvccNode list中的uncommit node一定是属于同一个事务的（即事务id相同），并且一定处在MvccNode list的最新位置，即链尾。

MvccNode的具体实现结构如下所示：

struct ObMvccTransNode {
  transaction::ObTransID tx_id_;  // 事务id
  share::SCN trans_version_; // 事务提交版本
  share::SCN scn_; // 数据所在日志的 scn
  int64_t seq_no_;  // 在事务中的sql numble // 可能一个存储过程有多个相同sql no的mvcc node
  share::SCN tx_end_scn_; // 数据所在事务的 commit/abort 日志的 scn // 未提交为max
  ...
  uint8_t type_;  // 标记是否是COMPACT
  uint8_t flag_;   // 事务状态 （F_COMMITTED/F_ABORTED 等等
};

需要注意的是，每个操作实际上是被包含在一个事务中的，因此该操作存在一个sql_no_，标记着其在整个事务中的序号，同时操作本身对应着一条日志，scn_记录了该日志的scn（简单理解为时间戳即可），而整个事务的提交对应着另一条日志，tx_end_scn_记录了该日志的scn。trans_version_记录着事务的提交版本，我们只需要知道这是和日志时间戳不同的两个维度的概念。

我们已经知道了uncommit和commit的概念，那么图中被标记为compact的node是什么呢？

简单来说，compact node是将后续所有已提交MvccNode中数据进行整合后得到的一个特殊的包含完整行的node。

如下图所示，三个MvccNode从尾到头分别是update/update/insert操作，其中insert node是包含全部列数据的完整行，update node只包含更新列的数据的部分行。对于一个想要全部列的查询来说（这里我们忽略版本的问题），每次都需要读取这三个node并整合成一个新的完整行。因此，compact node产生了。我们会将整合三个node所得到的完整行保留下来，最终形成一个包含当前最新完整行的compact node。

再回到最开始的问题："什么叫行的多版本数据？"

在逐行读取的过程中，对于每个rowkey，我们最终会读取出多个sql numble不一样的未提交行（如果有的话）、一个compact行以及多个多版本行，这就是所谓的“行的多版本数据”。

这里就涉及一个版本范围的限制，即(base_version, snapshot_version, multi_version_start) 三元组。我们的读取实际上附带着这样一个版本范围。我们所读取出的compact行是在遍历MvccNode list过程中，将多个提交版本在(base_version, snapshot_version)之间的compact node或者commit node再次整合所得。而读取出的多个多版本行分为两部分，一部分是将事务提交版本在(multi_version_start，snapshot_version)之间的node进行整合所得，可能会有多个结果，每个结果是由相同事务提交版本的node整合所得；另一部分是将事务提交版本在(base_version，multi_version_start)之间所有node整合所得，只有一个结果。

看完以上解释，大家其实已经掌握了七八了，整个逐行读取的过程就是根据所谓的版本范围，遍历BTree上的每个rowkey，再将每个rowkey所拥有的MvccNode通过一系列的整合操作，得到一条条提交或者未提交的行记录，最后将这些行依次写入微块、微块写入宏块、多个宏块形成SSTable。

如果对源码细节不感兴趣的同学，看到这已经可以转身离开了。但是剩下的同学别着急，让我们继续向细节探寻。

整个逐行读取过程通过ObMemtableMultiVersionScanIterator实现，参见ObMemtableMultiVersionScanIterator::inner_get_next_row。其中包含两个子迭代器ObMultiVersionRowIterator和ObMultiVersionValueIterator，两者分别用于迭代BTree和迭代MvccNode list：

class ObMultiVersionRowIterator {
  ...
  common::ObVersionRange version_range_; // (base_version,snapshot_version,multi_version_start)三元组
  ObMultiVersionValueIterator value_iter_;
  ...
  ObIQueryEngineIterator *query_engine_iter_;  // BTree迭代器
};

class ObMultiVersionValueIterator {
  ...
  common::ObVersionRange version_range_;
  ObMvccRow *value_;  // 装载着ObMvccTransNode *list_head_
  ObMvccTransNode *version_iter_; // value->list_head_
  ObMvccTransNode *multi_version_iter_; // 用于迭代多版本行，来自某一次的version_iter_
  int64_t max_committed_trans_version_; // 这一行的最大已提交版本
  share::SCN cur_trans_version_;
  bool is_node_compacted_;
  bool has_multi_commit_trans_;
  share::SCN merge_scn_; // 来自merge_param.scn_range_.end_scn_
};

迭代过程被实现为一个简易的状态机，每个状态以及每个状态的行为如下：

状态之间的转换过程如下：

需要注意的是，在SCAN_UNCOMMITTED_ROW向SCAN_COMPACT_ROW进行状态转换时会对multi_version_iter_进行初始化：
当前version_iter_是commit node，其trans_version为所有commit node中的最大已提交版本，如果该版本比multi_version_start_小，或者后续node没有比最大已提交版本小的trans_version，multi_version_iter_被初始化为null，否则初始化为当前version_iter_

以上迭代读行细节的描述，可能会有一定的门槛，如果现在没有理解也没有关系。如果大家真的对源码本身感兴趣并且做了一定的研究之后，回过头来看这些内容，相信会有更深入的思考。

后记

这篇博客依然省略了很多细节，旨在分享一个以存储视角对MemTable最基本的解读，希望能够让大家对相关源码产生兴趣（可以在Github上找到），只有真正的去探究了源码，才能领略到其中的艰涩与风光。当然，笔者也是一个小白，文中难免有不少纰漏，也欢迎大家指正和讨论，错误的订正也是加深理解的一个过程。