基于 LSM-tree 的关系型数据库中，通过被动的数据持久化方式移除双重日志记录
1. 介绍
自 1970 年代以来，关系数据库 (RDB) 一直在企业系统的核心发挥着核心作用。存储引擎作为 RDB 的核心组件，通常采用基于 B 树的结构，针对在线事务处理和在线分析处理等传统数据库工作负载进行了大量调整和优化。
随着互联网服务和应用的出现，经典的基于 B 树的存储引擎在主导数据库系统数十年后，面临着几个关键的挑战。与传统的数据库工作负载不同，这些新应用程序及其支持系统通常会产生写入密集型工作负载 [1]。它们中的许多使用相对简单和固定的数据模式 [2]。一些系统采用昂贵的闪存[3-9]，因此它们对存储空间的使用非常敏感，需要高效的数据压缩以节省成本。相应地，存储引擎设计必须满足一组新的要求——可扩展性、空间效率、可压缩性、I/O 顺序性等。
为了应对这些新的挑战和需求，最近的技术趋势是在 RDB 中部署基于日志结构合并树 (LSM-tree) 的存储引擎 [10-18]。一个典型的例子是 Facebook 的 MyRocks [7]。与 MySQL 的传统结构不同，MyRocks 将原来基于 B 树的存储引擎 InnoDB [19] 替换为基于 LSM 树的存储引擎 RocksDB [12]。虽然这种基于 LSMtree 的存储引擎在性能和存储空间使用方面明显优于基于 B 树的引擎，但它带来了一个关键的新问题，它可能会产生沉重且不必要的性能开销。
如图 1 所示，基于 LSM 树存储引擎的 RDB 本质上创建了一个两层结构：(1) 在顶层 RDB 层，RDB 逻辑处理数据库相关的复杂性，例如缓冲池管理、查询优化、SQL查询处理、事务支持、数据恢复等； (2) 在底层的存储引擎层，存储引擎处理来自 RDB 层的请求，负责将数据可靠、高效地进行持久化存储。 这样的设计具有很大的灵活性、效率和可移植性，允许两层独立优化而不影响彼此。然而，基于 LSM-tree 的存储引擎，如 RocksDB [12] 作为一个完整的数据存储本身，具有许多类似于其上的 RDB 的功能。其中一些功能是多余的和不必要的，这会导致严重的资源浪费和负面的性能影响。其中一个关键组件是日志，这是本文的重点。
双重日志记录问题。 在 RDB 系统中，一个 binlog 记录了所有处理过的 SQL 语句。一旦系统崩溃，将重放 binlog 中的 SQL 语句进行数据恢复。使用基于 LSM 树的存储引擎，每个 SQL 语句都被转换为一系列键值项 (KV)，这些键值项存储在底层 LSM 树中以进行持久存储。在基于 LSM-tree 的存储引擎中，会维护一个 Write-ahead Log (WAL) 来记录所有的 KV 更新操作。每个 KV 都必须先写入 WAL，然后再插入到树结构中，这也是为了系统崩溃时的数据恢复。在整个堆栈中，对数据库所做的任何更改都受到两次 “保护” —— 一个冗余副本保存在数据库的 binlog 中，另一个保存在存储引擎的 WAL 中。 这种冗余显然会导致不必要的空间使用，但更糟糕的是，这些与日志相关的 I/O 操作是同步的，并且驻留在系统的关键路径中，导致大量不必要的 I/O 开销，严重影响系统性能。
我们将上述问题称为双重日志记录问题，这是一种通过多次保留数据库更改来过度保护数据的系统情况。 据我们所知，这是第一次在基于 LSM-tree 存储引擎的 RDB 中透露此问题。
在基于 LSM-tree 存储引擎的 RDB 中。 值得注意的是，双重日志记录问题不是“log-on-log”问题 [20]，它通常出现在日志结构闪存 FTL 上运行日志结构文件系统时。 在 log-on-log 问题中，上层日志存储在另一个下层日志结构上。 相比之下，在双日志记录问题中两个日志是独立的，分别存储（binlog 不存储在 WAL 或依赖 WAL）。 因此，双重日志问题并不涉及 log-on-log 问题中已知的问题，例如数据重新映射、未对齐的段和未协调的垃圾收集等。相反，它更多地关注 I/O 操作中不必要的冗余和存储空间使用情况。
我们的解决方案。 为了解决双重日志记录问题，我们的核心思想是从基于 LSM-tree 的存储引擎中完全移除 WAL，完全依赖 binlog 进行数据恢复。 一个天真的解决方案是直接禁用 WAL（例如，RocksDB 提供了一个可配置的选项）。 然而，由于 SQL 和 KV 操作不协调，系统完整性无法得到保证，可能导致恢复不完全或错误。即使我们通过回放 binlog 来进行数据恢复，我们也得把整个 binlog 中的所有记录都回放，一个接一个的顺序。 这会导致非常耗时的数据恢复过程，
在本文中，我们提出了一种称为 被动数据持久性方案 (PASV) 的新颖解决方案来应对这些挑战。它包括三个主要组件：（1）为了弥合 RDB 层和存储引擎层之间的语义鸿沟，我们创建了一个特殊的数据结构，称为 Flush Flag，以传递关键的 RDB 层语义，包括关键数据持久点，每个 KV 项的逻辑序列号等。 (2) 为了避免对当前模块化系统设计的侵入性更改，我们提出了一种被动内存缓冲区刷新策略，为每个 LSM-tree 传递一个刷新标志，随着在存储引擎的定期下刷操作。无需显式刷新内存缓冲区，我们可以避免刷新造成的不良性能影响，并最大限度地减少对两层的结构更改。(3) 我们还制定了基于Epoch的持久化 (EBP) 策略来确定全局数据持久化点，保证我们只需要进行部分数据恢复来恢复必要的数据，并消除系统之前已经持久化的冗余 KV 操作碰撞。
我们已经实现了一个基于 Facebook 的 MyRocks [8] 的功能齐全的开源原型。我们的原型涉及微小的变化（只有大约 500 行 C/C++ 代码）并且是公开可用的 [21]。 基于 LinkBench [1] 和 TPC-C [22] 的评估结果表明，我们的解决方案可以有效地将吞吐量提高高达 49.9%，将延迟降低高达 89.3%，并且还节省了磁盘 I/O 和恢复时间高达 分别为 42.9% 和 4.8%。
本文的其余部分安排如下。第 2 节介绍了背景。第 3 节和第 4 节解释了问题和挑战。第 5 节描述了设计细节。第 6 节给出了评估结果。第 7 节讨论相关工作。最后一节总结了本文。
2 背景
2.1 Log-structured Merge Tree
LSM-tree 结构。 LSM-tree 采用独特的 append-only 结构 [10]，专为处理密集型小型 KV 而量身定制。在 LSM-tree 中，传入的小而随机的 KV 首先在称为 MemTable 的内存缓冲区中进行缓冲和排序。一旦 MemTable 满了，它就会变成一个不可变的缓冲区，并作为 SSTable 刷新到存储中。 SSTable 是 LSM-tree 中的基本存储单元。每个 SSTable 按键的顺序存储其 KV。
存储上的 SSTable 以多级结构组织，除第一级外，每一级都维护一系列具有非重叠键范围的 SSTable。两个不同的级别可能具有重叠的键范围。下层通常比相邻的上层维护多几倍（更宽）的 SSTable，形成树状结构。如果某一层级的 SSTables 数量超过了 size limit，则将选中的 SSTables 通过归并排序合并到较低层级，称为 Compaction。在查询时，执行二进制搜索，从上到下逐级搜索，直到找到该项目或返回 “Not Found”。图 1(a) 说明了典型的 LSM-tree 的结构。
为了防止系统故障时内存中的数据丢失，对内存缓冲区（又名 MemTable）所做的所有更新必须首先写入磁盘上的日志结构，称为预写日志（WAL）[23 , 24]。当系统在崩溃后重新启动时，WAL 中的记录将被重放以重建内存缓冲区中的原始数据。
基于多 LSM 树的结构。 现代 KV 存储引擎通常维护多个 LSM-tree 来为高速存储设备（如 SSD）创建 I/O 并行性，以实现更好的性能。让我们以 RocksDB [12] 为例。在 RocksDB 中，它维护着几个所谓的列族 (CF)。每个列族对应一个LSM-tree。所有 LSM-trees 只维护一个 WAL，称为 Group Logging [25] 或 Group Commit [26]。虽然为所有 LSM-tree 保留一个 WAL 可以带来事务处理的性能优势，但它会导致一个问题，即记录在 WAL 中的批量 KV 请求可能以不同的速度插入 LSM-tree，导致故障时恢复过程效率低下.我们将在本文后面更详细地解释这个问题。