简介：随着非易失内存产品的商业化推广，咱们对于其在云原生数据库中大规模推广的后劲越来越有趣味。X-Engine 是阿里云数据库产品事业部 PolarDB 新型存储引擎团队研发的一个 LSM-tree 存储引擎，目前在阿里云 PolarDB 产品上提供对外服务。咱们以 X -Engine 为根底联合非易失内存的劣势与限度，从新设计并实现了存储引擎的次要内存数据结构、事务处理和长久化内存分配器等根底组件，最终实现了不须要记录预写式日志的高性能事务处理，升高了整体零碎的写入放大并进步了存储引擎的故障复原速度。
作者 | 百叶
起源 | 阿里技术公众号
引言：随着非易失内存产品的商业化推广，咱们对于其在云原生数据库中大规模推广的后劲越来越有趣味。X-Engine 是阿里云数据库产品事业部 PolarDB 新型存储引擎团队研发的一个 LSM-tree 存储引擎，目前在阿里云 PolarDB 产品上提供对外服务。咱们以 X -Engine 为根底联合非易失内存的劣势与限度，从新设计并实现了存储引擎的次要内存数据结构、事务处理和长久化内存分配器等根底组件，最终实现了不须要记录预写式日志的高性能事务处理，升高了整体零碎的写入放大并进步了存储引擎的故障复原速度。该研究成果以论文《Revisiting the Design of LSM-tree Based OLTP Storage Engine with Persistent Memory》发表到 VLDB2021。论文容量较大，无论是对于后续的钻研还是利用落地都具备较高的参考价值。作为一个继续深耕数据库根底技术的团队，咱们在事务存储引擎 / 高性能事务处理 / 新型存储器件 / 异构计算设施 /AIforDB 上均有涉猎及钻研，欢送海内外有志之士加盟或交换。
一 背景介绍
1 长久化内存简介
PM 在提供相比 DRAM 更大容量、更低功耗的同时，还具备字节寻址等诸多特点，旨在大幅度晋升设施内存容量以及升高设施动态功耗的同时，提供可长久化字节寻址等个性以简化零碎的设计，为数据库存储引擎的设计带来了新的契机。Optane DCPMM 采纳 DDR4 DIMM 的产品状态，亦被称之为“长久内存模组”Persistent Memory Module/PMM。以后 DCPMM 单条容量提供三种抉择 128GB、256GB、512GB，理论可用容量别离为 126.4GiB、252.4GiB、502.5GiB。Optane DCPMM 以后仅实用于 Intel Cascade Lake 处理器，其和传统的的 DRAM 相似，通过 Intel iMC（integrated Memory Controller）连贯到处理器。DCPMM 尽管提供和 DRAM 雷同的字节寻址能力，但其 I / O 体现与 DRAM 存在较大差别，次要体现在介质拜访粒度、cache 管制、并发拜访以及跨 NUMA 节点拜访等方面。感兴趣的读者能够参考本文后续的文献[1,2]。
2 X-Engine 简介
X-Engine 是一种基于 LSM-tree 架构的 OLTP 数据库存储引擎，其实现架构如图 2 所示，其中单个数据库可由多个 LSM-tree 实例组成（称为 subtable），每个实例存储一个表或者索引或者分区表（table/index/table-partition），具体可参考 2019 年 SIGMOD 的论文[3]。LSM-tree 将数据分为多个依照肯定比例增长的层（level），别离位于内存以及磁盘，数据从下层到上层通过合并（compaction）的形式流动。鉴于 DRAM 是掉电易失的，其采纳写前日志（WAL）的形式将要写入的数据提前写入到磁盘中长久化，在内存中的数据刷入（flush）或者合并到磁盘后再革除对应的 WAL。在典型的设计中，内存中的数据通常采纳跳表（skiplist）实现，在大小超过限度后会被解冻（图中 Swtich 操作以及 immutable 内存表）并转储到磁盘中并创立新的内存表。磁盘中的每层数据采纳多个有序字符串表（SST，Sorted String Table）存储，每个 SST 相当于一颗 B 树。通常状况下同一层中的不同 SST 的键值对的范畴不产生交叠。但理论的零碎中为了减速内存表的刷盘操作，通常容许局部层的 SST 存在范畴交叠，如 LevelDB，RocksDB 等均容许 Level0 存在交叠，但乱序的 Level0 层数据布局会升高读取效率。
图 2 X-Engine 次要架构
3 时机与挑战
现有的基于 LSM-tree 架构的 OLTP 存储引擎的设计通常存在以下几个问题：（1）WAL 位于写入要害门路中，尤其是为了满足事务的 ACID 属性，WAL 通常以同步的形式写入到磁盘，因此拖慢写入的速度。此外，因为 DRAM 的易失性，设置过大的内存表尽管会进步零碎的性能，但会导致 WAL 过大，影响零碎的复原工夫。（2）level0 数据块通常容许乱序，以放慢内存中数据的刷盘速度。但乱序的数据块如果沉积过多，会重大影响读取性能，尤其是范畴读取性能。直观上，可长久化字节寻址的 PM 能够用来实现长久化内存表，代替 DRAM 中的易失性内存表，从而缩小保护 WAL 的开销。然而实际上，因为 PM 自身的个性，实现高效的长久化索引仍然存在较大挑战，包含相应的 PM 内存治理。另外，以后 PM 硬件仅能放弃 8 字节原子写入，导致为了实现原子写入语义，传统办法仍然须要引入额定的日志（又称为 PM 外部日志）。
为了应答这些挑战，该论文设计针对 LSM-tree 专用优化的高效 PM 内存管理器 Halloc，提出了优化的基于 PM 的半长久化内存表用以替换传统计划 DRAM 中的内存表，应用 ROR 无锁免日志算法去除传统计划依赖 WAL 放弃事务的 ACID 属性，设计全局有序的 Global Index 长久化索引层以及存内合并策略替换传统计划的 Level0 层，进步查问效率以及升高 Level0 数据保护的 CPU 和 I / O 开销。论文中次要改良点如图 3 所示，其中 mem 示意 active memtable，imm 示意 immutable memtable，sp- 前缀示意半长久化。这些设计次要带来以下三点益处：（1）防止了 WAL 写入以及 PM 编程库引入额定外部日志，实现更疾速的写入；（2）PM 中的数据间接长久化，防止了频繁的刷盘以及 level0 的合并操作，且容量能够设置更大而不必放心复原工夫；（3）level0 数据全局有序，不用放心 level0 的数据沉积问题。
图 3 论文中的次要计划和传统计划的比照
二 半长久化内存表
长久化索引的更新以及增加操作通常波及 PM 中多个超过 8 字节的小的随机写入，因而引入用于保护一致性的开销以及随机写入导致的写放大问题。实际上，基于 PM 的索引的设计能够分为上表中的三类。无长久化是指将 PM 当作 DRAM 应用，此种办法能够保障索引处于最高的性能，但掉电数据即失落。第二类是采纳全长久化的形式，即索引所有的数据（索引节点以及叶子节点等）做长久化，如 BzTree, wBtree 等。该种形式可做到极速复原，但长久化的开销个别较大，性能通常较低。一个比拟折中的办法是仅长久化必要的数据以换取性能和复原工夫的折中，例如 NV-Tree 和 FPTree 仅长久化叶子节点，索引节点在重启时重建。而在 LSM-tree 构造中，内存表通常较小，因而采纳半长久化的索引设计思维较为适合。论文中采纳两种办法用以升高保护长久化索引的保护开销。
图 4 半长久化内存表结构图
仅长久化叶子结点。在理论的利用场景中，云上基于 LSM-tree 的 OLTP 引擎通常不会设计较大的内存表，通常为 256MB，这次要是因为以下两个起因：（1）云上用户通常会购买较小内存的数据库实例；（2）LSM-tree 须要维持小的内存表以保障疾速的刷盘操作。对于 256MB 的内存表，咱们发现将仅长久化叶子结点时重启复原非叶子结点的开销小于 10 毫秒，其复原工夫绝对于所钻研的数据库系统已足够快。其次，该索引的设计中采纳序列号以及用户键拆散的形式用于减速键的查找以及满足内存表的 MVCC (Multi-Version Concurrent Control)并发管制束缚。如图 4 所示，对于仅有一个版本的值（9）将间接在索引中存储一个指向 PM 具体位置的指针，对于有多个版本的值，设计中应用可伸缩的数组用于存储多版本序列号及其具体的指针。因为索引是易失的，键并不显式存储在索引中，且索引在重启时通过扫描 PM 中的键值对重建。
批量程序写入以升高写放大。在 PM 中，小的随机写会被硬件控制器转换成随机的 256 字节的大块写，导致写放大问题，进而耗费 PM 硬件的带宽资源。鉴于内存表设计为程序追加的写入形式，为了防止该问题，半长久化内存表通过将小的写打包成大块的写（WriteBatch），并且程序地将该 WriteBatch 写入到 PM 中，之后别离将其中的记录写入到易失性索引中。如图 4 所示，batch 示意一个大块的 WriteBatch 写入，slot 用于记录从 Halloc 分配器中调配的 zone 对象的 ID。
三 ROR 无锁免日志事务提交算法
因为本文中 memtable 中的索引无需长久化，因而仅需保证数据的原子长久化即可。PM 尽管能够提供字节寻址的可久化写入，但其仅能提供 8 字节的原子化写入（仅指 intel optane DCPMM）。因而大于 8 字节的写入操作存在局部写（torn write）的危险。传统的计划是采纳数据即日志（log-as-data）保障原子写入，如图 5 所示，日志项程序写入，且每个日志项写入实现后更新 8 字节的 head 指针。因为 head 的更新总能由硬件保障原子性，因而 head 之前的日志项能够看作胜利写入；head 之后的日志项存在局部写危险，重启时被抛弃。
该种计划存在两个问题：（1）日志仅能程序写入，不利于施展多核零碎的并行写的能力；（2）日志项中存在不同生命周期的数据，导致日志项的回收较为艰难。如图 5 所示，log1 中的数据写入 3 个 LSM-tree 实例中，而其中不同的 LSM-tree 实例中 memtable 刷盘的工夫不同，可能会导致某个 LSM-tree 实例写入较少，进而刷盘周期较长，导致对应的 log1 长时间不能无效回收，升高 PM 的内存空间的利用率。
图 5 传统计划存在的问题
为了解决这些问题，文章提出 ROR 算法，其应用 ChainLog 数据结构拆散数据生命周期，利用无锁环（lock-free ring）实现日志的并发写入。其中，为了进一步减针对 PM 的随机写入进步写入的性能，ROR 算法中采纳 batch 的形式将小的 ChainLog 合并成更大的数据块。如图 6 所示，ChainLog 保障任意大小数据写入 PM 的原子性；batching 用于聚合小的事务缓存批量写入 PM 以缩小 PM 的随机写；并发环提供针对 ChainLog 无锁的流水线化写入到 PM 中以进步多核零碎的伸缩性。
图 6 ROR 算法整体框架
对于一个待提交的事务，其首先被封装成一个 WriteBatch。一个或者多个 WriteBatch 被进一步封装成一个 ChainLog，以批量写入到 PM 中。本文中沿用 LSM-tree 原初的两阶段锁 2PL 以及 MVCC 的事务并发控制策略。如图 6 所示，ROR 应用固定可调大小并发桶（bucket）用于管制并发写入，其中第一个进入某个 bucket 的线程成为 leader 线程用于执行具体的写入，其余进入该 bucket 的线程成为 follow 线程。Leader 将本人以及属于该 bucket 的所有 follow 线程的 WriteBatch 聚合成一个更大的 WriteBatch 用于理论的写入。
ROR 重点之一是 ChainLog，其通过在 8 字节的 head 中退出辨认日志生命周期的域以及标识写入地位的域。能够通过标识写入地位的域信息，定位到哪些 ChainLog 产生了局部写，从而在重启时抛弃。通过日志生命周期的域信息，能够使得 ChainLog 中写入不同 LSM-tree 实例中的数据写入到不同的内存空间互相隔离。另外，ChainLog 在高层视角上总是串行的写入，即一个 ChainLog 项仅当所有以前的 ChainLogs 都已长久化在 PM 中时才会被长久化。串行化的提交使得在零碎复原期间仅需查看最初一个 ChainLog 项，以确保最初一个 ChainLog 的写入是否产生局部写。
首先思考数据生命周期的拆散，一种较为直观的做法是针对每个 LSM-tree 实例设置独自的 head 指针，如图 7 所示，每个 head 负责批示其对应的内存空间的写入地位。不同的内存空间互相拆散，具备独立的生命周期，其对应的 LSM-tree 中的 memtable 刷盘后能够立刻回收而不须要期待其余 LSM-tree 实例。但该种做法存在一个显著的问题，单个事务可能会写入到多个 LSM-tree，因而导致单次更新波及到多个 head 的更新，进而硬件上无奈保障写入的原子性。
图 7 日志项生命周期示例
为了解决这个问题，ROR 在每个 LSM-tree 实例中用于批示写入地位的 8 字节的 head 中退出如下的地位信息，图 8 中的 gidx 即对应原始的 8 字节 head 指针。gidx 指针中高 4 字节用于记录上次写入的地位，低 4 字节用于记录以后写入的地位。每 4 字节中 6bit 用于记录 memtable 的 slot，26 字节用于记录对应 slot 的偏移，总共能够寻址 4GB 的空间。一个 ChainLog 项写入的数据分为 n 个子项，每个子项别离写入对应的 LSM-tree 实例。每个子项中均记录子项的个数以及以后 ChainLog 的 LSN。
图 8 gidx 的构造示意图
图 9 中的例子展现了该过程，其中 ChainLog2（R2）曾经被胜利提交，R3 期待被提交。但在 R3 提交的过程中零碎产生异样掉电，导致 R3 中子项 r31 被胜利提交，但 r32 未能胜利提交。在零碎复原时，通过扫描所有 LSM-tree 实例中的最初一个 ChainLog 子项，能够获知以后最大的 LSN 为 3。而 r31 曾经胜利提交，但其记录的子项数为 2，但 r32 未能胜利写入，因而其 LSM-tree 实例 1 的 gidx 会被回滚（通过简略疾速的右移运算）。回滚后 r31 被抛弃，LSN 回退到 2，此时零碎复原到全局一致性状态。
图 9 断电复原示意图
因为 ChainLog 须要满足串行化写入语义，进而保障在重启复原时仅需扫描所有 LSM-tree 的最初一个 ChainLog 子项即可正确建设全局统一的状态。保障串行化写入语义的一种办法是串行写入，但该形式无奈利用多核平台的高并发写入的个性，其本质上是先建序后写入的思维。ROR 算法中采纳写入后建序，即每个线程在写入的时候不关注序的问题。ROR 算法会在此过程中动静的抉择主线程收集以后已写完的 ChainLog 并建序。因为建序仅波及到 ChainLog 元数据的更新，因而显著进步写入性能。主线程建完序后退出，ROR 算法持续动静抉择其余主线程进行该过程。该过程由 lock-free ring 以及 lock-free 的动静选主算法管制，具体细节读者能够参考原始论文中的形容。
四 Global Index 与轻量级存内合并
GI（Global Index）次要用于在 PM 中保护一个可变索引化的数据层用以替换磁盘中无序化的 level0 层数据。为了简化实现，GI 采纳和内存表雷同的易失性索引，并将数据搁置在 PM 中。因为内存表同样将数据搁置在索引中，因而内存表的数据转移到 GI 时无需数据拷贝，仅需更新 GI 索引中的指针指向内存表中的数据。值得注意的是，GI 能够采纳任意的范畴索引，或者长久化索引用以进步零碎的复原速度。鉴于 GI 的更新并不需要设计多个 KV 更新以及写入的事务性需要，现有的无锁免日志的范畴索引均能够利用到 GI 中。
存内合并：存内合并是指从内存表到 GI 的合并。GI 采纳和内存表雷同的索引设计，行将键值对存储到 PM 中，叶子结点采纳伸缩的带数据版本的数组用于存储来自同一个键的数据。在存内合并时，如果在 GI 中不存在雷同的键，则间接将该键插入到 GI 中；如果已存在，则须要在 GI 中查看属于该键多个版本并在须要时执行多版本革除操作，以节俭内存空间。因为 PM 中的键值对都由 Halloc 治理，因而键值对粒度的内存开释是不容许的。实现存内合并时，仅开释内存表的内存。仅当 GI 中的所有键值对合并到磁盘时才批量开释 GI 中的 PM 内存。
快照：通过快照技术，能够确保在 GI 合并到磁盘时，存内合并操作能够同时进行，以防止阻塞前段的操作。在快照的实现中，GI 会解冻以后的数据并在外部创立一个新的索引用以排汇来自内存表的合并数据。该种设计防止了阻塞前端的操作，但因为查问可能会波及到两个索引，导致额定的查问开销。
PM 到磁盘的 compaction：因为合并到磁盘的 GI 数据是不可变且全局有序的，因而 PM 到磁盘的合并操作并不会妨碍前端的操作。而且因为 GI 的全局有序性，合并操作能够通过范畴且分并行化，进而放慢 PM 到磁盘的合并速度。
数据一致性：PM 到磁盘的合并波及到数据库状态的扭转，可能在零碎宕机时呈现数据一致性问题。针对该问题，本文通过在磁盘中保护形容日志（manifest log）的形式保障数据库状态扭转的数据一致性。因为形容日志不在前端写入的要害门路中，因而并不会影响零碎写入的性能。
五 Halloc 内存分配器
Halloc 是针对 LSM-tree 专用的 PM 内存分配器，其通过三个关键技术以解决传统通用 PM 内存分配器存在的效率低、碎片化等问题，基于对象池的内存预留计划、利用亲和的内存治理以及统一化地址空间治理。其次要架构如图 10 所示，halloc 通过间接创立 DAX 文件划分本人的内存地址以及治理本人外部的元数据信息，在地址空间上划分为四个区域别离存储 Halloc 元数据信息、subtable 元数据信息、内存表元数据信息以及若干内存快用于具体的内存应用。
图 10 Halloc 内存分配器总体架构图
基于对象池的内存预技术。Halloc 通过动态预留固定大小的对象池且内存地址互不交叠的地址空间以缩小 PM 治理中存在的内存碎片问题。每个对象池蕴含元数据区用于记录对象的分配情况，freelist 长久化链表用于追踪闲暇的对象，固定大小的对象区且其大小由创建对象池时显式指定。因为对长久化链表的操作设计到多个不间断的大于 8 字节的 PM 写入操作，因而存在数据不统一的危险。传统的计划应用 PMDK 以及 Mnemosyne 等外部日志保障操作的事务性，但改种计划会引入额定的日志开销。为了打消该日志开销，本文提出以下计划保障 freelist 操作的数据一致性。
图 11 freelist 外部结构图
如图 11 所示，对于一个 freelist，其在内存空间上是间断存储的，包含元数据区用于记录分配情况，通过索引区用于索引闲暇的对象，以及对象区用于存储具体的对象。每个对象对应一个 8 字节的索引，每个索引的最高位用于标记该对象的长久化状况以确保原子化的对象调配与开释。Freelist 提供四个接口用于实现一个对象的调配与开释：Get 用于从 freelist 中获取一个对象，Commit 用于告诉 Halloc 该对象已实现初始化能够从 freelist 中移除，Check 用于检测某个对象是否已被长久化防止故障重启时呈现对象谬误援用，Release 用于开释一个对象。核心思想是通过在对象的索引设置长久化标记，已在重启时通过扫描辨认出透露的对象。
对于对象池的启动复原，Halloc 首先扫描 freelist 的对象并在 bitmap 中标记，之后在扫描 index 域确认该对象是否在 freelist 中可达。对于不可达的对象将被回收。该种设计肯定水平上减少了重启的开销，但实际上该过程扫描很快，试验中扫描数百万个对象仅破费几毫秒工夫。重启开销在所钻研的零碎中能够忽略不计。
利用亲和的内存治理。Halloc 对于 LSM-tree 提供两种对象池服务：自定义对象池以及 zone 对象池。该种设计次要基于 LSM-tree 对于内存应用的独有的追加写以及批量回收的形式，对于内存的治理有较大的简化。对于自定义对象池，如图 8 所示，Halloc 保护了 memtable 以及 subtable 池别离用于存储引擎中的内存表元数据和 subtable 元数据。一个 subtable 对象蕴含一个链表用于记录其所有领有的 memtable 对象（通过 memlist 链接），其中第一个 memtable 对象为流动内存表，其余为解冻内存表。每个 memtable 对象索引无限个 zone 对象，每个 zone 对象记录具体的 memtable 数据。zone 对象池是 Halloc 内建的对象池用于利用本人依照本人的形式治理内存，该设计次要是因为自定义对象池仅能存储无限的且固定大小的对象。鉴于 Halloc 并非针对于通用 PM 内存调配，对于可变大小且为止数量对象的治理，利用须要本人基于 zone 对象池实现本人的内存治理计划。
统一化地址空间治理。为了便于易失性以及可持久性内存的联结治理，Halloc 在繁多 DAX 文件地址空间上同时反对长久化内存调配以及易失性内存调配，从而大大简化了 PM 资源应用。相似于 libmemkind，Halloc 同样实用 jemalloc 用于接管具体可变大小的易失性内存的调配。不同的是，Halloc 应用 zone 作为 jemalloc 的根本内存治理单元，即 jemalloc 总是从 zone pool 中获取 zone 对象并进一步细化治理。其从 zone pool 中调配的对象不再调用 Commit，从而其所有调配的 zone 对象在零碎重启后将全副被回收。该种设计方案的一个较大的限度是用户调配的易失性内存大小不能超过单个 zone 的大小，因为 zone 对象池仅能保障单个的 zone 的内存地址的连续性。然而对于较大的内存调配，用户能够抉择拆分的形式屡次调配，或者如果对象大小固定且数量无限应用自定义对象池进行动态调配。
六 试验评估
试验平台。试验采纳阿里云实例规格为 ecs.ebmre6p.26xlarg。该实例具备两颗 Intel(R) Xeon(R) Platinum 8269CY CPUs，每个 CPU 具备 52 个外围，共 104 外围。每个外围有一个 32KB 的 L1 缓存，一个 1MB 的 L2 缓存。每个 CPU 上所有的外围共享一个 32MB 的 L2 缓存。实例另有 187GB 的 DRAM 以及 1TB 的 PM。PM 被平均分配到两颗 CPU，即每个 CPU 配备 512GB 的 PM。实例总共配置 2TB 的 ESSD 作为云硬盘。试验中将所有的 PM 配置为两个 linux 设施，每个设施别离属于一个 CPU。所有的试验运行的 linux 内核版本为 4.19.81。
参数配置。如无特地阐明，试验中设置单个内存表的大小为 256MB，单个 subtable 的 GI 的最大为 8GB，单个 subtable 的 level1 为 8GB。改良前的系统配置 256MB 的 level0。所有的试验均采纳同步的 WAL，应用 Direct I/ O 以旁路掉 page cache 对系统的影响，敞开压缩以尽量评测零碎的最大性能体现。
1 综合评估
该试验首先采纳 YCSB 规范的测试基准，共事后在数据库中加载 80 亿记录，平均分配到 16 的 subtable，每个记录有 8 字节的 key 以及 500 字节的 value，总共约 500GB 的数据量。试验中配置了 4 种配置：（1）基准零碎且所有数据均搁置到 ESSD 中（标记为 XS），（2）改良的计划且配置应用 200GB 的 PM 空间由 Halloc 治理（标记为 XP），（3）基准零碎且将所有的数据搁置在速度更快的 PM 中（标记为 XS-PM），（4）改良的计划且将原先搁置于 ESSD 中的数据放在 PM 中（标记为 XP-PM）。配置（1）以及配置（2）是零碎理论应用时的标准配置；而配置（3）以及配置（4）是次要用于评估移除 ESSD 后的零碎性能体现。每个试验应用 32 个 client 线程，设置 50GB row cache 以及 50GB 的 block cache，且运行 30 分钟以保证系统 compaction 失去及时的运行。
图 12 YCSB 试验后果
试验后果如图 12 所示，对于写密集型的负载 A 且随机申请下，XP/XP-PM 的性能是 XS/XS-PM 的 3.8 以及 2.3 倍；在写密集型的负载 F 且随机申请下，XP/XP-PM 的性能是 XS/XS-PM 的 2.7 以及 2.2 倍。且在图 10 中显示，XP 的均匀拜访提早要比 XS 低 36%。在负载歪斜的状况下（Zipf=1），XP 与 XS 性能体现靠近，并且 XP-PM 体现要比 XS-PM 更低。这些结果表明，本文的计划比照基准零碎在整体上性能体现更优异且产生更少的磁盘 I /O。然而 XP-PM 的体现和 XS-PM 的体现差距不大，尤其是在负载歪斜下，XP-PM 体现的不如基准零碎 XS-PM。但实际上该配置将数据全副搁置于 PM 中，因为老本较为昂扬，理论中不会采纳。
对于读密集型的利用（B，C，D，E），在负载 B 且随机申请下，XP/XP-PM 比 XS/XS-PM 性能别离高 1.7 倍及 1.2 倍，在负载 D 中别离高 1.4 倍以及 1.1 倍，并且领有更低的提早，负载 B 的均匀提早升高 39%，负载 D 的均匀提早升高 26%。这次要是因为 XP 不须要写 WAL 日志，因而具备更低的写入提早。负载歪斜时，XP 的性能收益升高。在负载 B 中，XP/XP-PM 性能比照 XS/XS-PM 仅进步 1.1 倍以及 1.5 倍。在负载 C 以及负载 E 中，因为写入较少，此时数据全副被合并到 ESSD 中，因而 XP/XP-PM 比照 XS/XS-PM 性能体现类似。
图 12（续）零碎提早以及 CPU、IO 开销
CPU 以及 I / O 耗费。图 12(c)中展现了在运行 YCSB load 以及 A 负载时的 CPU 耗费以及累积 I / O 状况。后果展现，XP 领有更好的 CPU 应用效率，且在运行 A 负载时，其 I / O 的耗费绝对基线零碎升高了 94%。次要起因为 XP 采纳更大的 GI 用于缓存更多的更新在 PM 中，因此缩小数据的刷盘操作。
图 13 零碎提早以及 CPU、IO 开销
数据库大小敏感性。为了测试改良零碎的性能收益与数据库大小的关系，试验别离注入 100-600GB 大小的数据，之后运行 D 负载。结果表明，如图 13 所示，数据库大小从 100GB 增大到 600GB 时，基线零碎 XS 的性能降落了 88%，而 XP 仅降落 27%。次要是因为负载 D 尽可能读取最近的更新，而 XP 会将热数据搁置在高速的长久化的 PM 中，而基线零碎 XS 在每次启动零碎进行测试时均须要从慢速磁盘中读取数据。
图 14 单 LSM-tree 实例的试验后果（40GB dataset）
单个 LSM-tree 实例测试。为了同现有的最新的应用 PM 改良 LSM-tree 的计划进行比照，试验中抉择 SLMDB 以及 NoveLSM 进行比照。鉴于 SLMDB 以及 NoveLSM 均不反对同一个数据库中运行多个 LSM-tree 实例，本次仅设置单个 subtable。试验中应用 4 个 client 且加载 40GB 的数据。测试结果表明，如图 14 所示，XP 领有更高的数据加载性能，为 SLMDB 的 22 倍，NoveLSM 的 7 倍。次要是因为 SLMDB 以及 NoveLSM 尽管应用长久化 skiplist 作为内存表，但波及到事务处理时，依然依赖 WAL 以保障事务的原子性，另外两者均不反对并发写入。SLMDB 应用单层的构造以及全局的长久化 B +tree 用于索引磁盘上具体的数据。该种设计尽管可能进步数据的读取性能，但写入时波及到磁盘以及 PM 中长久化索引的一致性保护，因此写入性能较低。NoveLSM 仅引入长久化内存表，因而性能晋升较为无限（PS：不是很 novel）。
图 15 TPC- C 试验评估后果
TPC- C 性能体现。试验中将改良的计划集成到 MySQL 中作为一个存储引擎的插件，并事后加载 80GB 的初始数据库大小，之后启动 TPC- C 测试 30 分钟。试验结果显示（如图 15），XP 绝对 XS 的 TPS 性能进步到 2x，且 P95 提早升高了 62%。次要是因为 XP 防止了 WAL 的写入，且领有更大的 PM 以缓存更多的数据。然而 XP 在 TPS 的体现上绝对于 XS 抖动更大，次要是因为 XP 更偏向于执行 level0 到 level1 的 all-to-all compaction 策略，从而导致更激烈的 cache 淘汰行为。如何均衡 compaction 和 cache 的淘汰策略是将来一个比拟重要的方向。
2 半长久化内存表评估
为了评估改良的计划中半长久化内存表的性能，试验中关闭系统所有后盾的 flush 以及 compaction 操作，设置 ROR 的 batch=50 以尽量旁路掉 ROR 的影响（batch=50 已靠近 PM 硬件性能极限）。试验中次要对以下索引计划：（1）基于 DRAM 的 skiplist，基线零碎默认的内存表索引类型（标记为 SLM）；（2）基于 FAST&FAIR 实现长久化内存表（标记为 FFM）；（3）基于 FPTree 的变种（本试验中采纳 OLC 实现并发操作，原始的 FPTree 采纳 HTM 以及 leaf lock 实现并发操作）实现的半长久化内存表（标记为 FPM）；（4）本文计划，且使 DRAM 存储索引节点（标记为 SPM-D）；（5）本文计划，且应用 PM 存储索引节点（标记为 SPM-P）。计划（4）以及（5）用于检测将 PM 作为非长久化应用时的内存表性能体现。FAST&FAIR 以及 FPTree 是一种针对 PM 优化的长久化 B +tree，其中 FPTree 仅长久化叶子结点，因此同样为半长久化索引的一种。因为 FAST&FAIR 以及 FPTree 均不反对可变大小的 key，因而本试验对于这两种内存表增加一个运行时 KV 解析的流程，即索引中仅存储固定大小的 KV 对的指针。试验中插入 3000 万个 KV 对，8 字节 key，32 字节 value，总计约 1.5GB 数据。KV 对在内存表中将被转换成 17 字节的 key，以及 33 字节的 value。
图 16 内存表性能评估后果
insert 性能：图 16(a)(b)展现了不同内存表在并发线程从 1 减少到 32 时的写入性能体现。结果显示，在写入时 SPM- D 以及 SPM- P 的差异很小，即便 SPM- P 将索引节点搁置在速度更慢的 PM 中，次要是因为长久化开销绝对较大，是次要影响因素。另外，对于 SLM/FFM/FPM，SPM- D 在程序写入上别离晋升 5.9x/5.8x/8.3x，在随机写入上别离晋升 2.9x/5.7x/6.0x。即便 LSM 将索引搁置在速度更快的 DRAM 中，SPM-D/SPM- P 相比仍然具备较大的性能晋升，次要是因为 SPM 采纳基数树索引，具备更好的读写效率。即便 FPM 同样将索引节点搁置在速度更快的 DRAM 中，但其在本文实现中依赖运行时的 KV 解析以从速度更慢的 PM 中加载具体的 KV 数据。
lookup 性能：表 16(c)展现了点读的性能体现，在该试验中 SPM- D 绝对 SLM/FFM/FPM 性能晋升别离达到最高 2.7x/14x/16x。对于点读场景，SPM 采纳前缀匹配，然而 SLM/FFM/FPM 均采纳二分查找的形式。对于 key 广泛较短的场景下，基数树显然具备更高的读取效率。尽管 FPM 在叶子结点中采纳基于哈希的指纹标识技术以减速点读性能，理论在内存表中，点读会被转换成短的范畴查问用以获取对应 key 的最新的版本，因而 FPM 中的指纹技术难以发挥作用。此外，FPM 叶子结点采纳乱序寄存的策略以就义肯定的读取效率换取写入速度的晋升。SPM- D 在点读场景下比 SPM- P 更高，其次要因为 SPM- P 将索引节点搁置在速度更慢的 PM 中，在读取时，索引性能受限于 PM 的读取带宽限。对于范畴查问性能（图 16(d)），SPM- D 以及 SPM- P 体现均不如 SLM。尽管在 DRAM 中基数树的范畴查问性能广泛不高，但在本次试验中发现其性能更多是受限于 PM 的读取带宽。实际上，在进行系统分析表明，在范畴查问时，SPM- D 从 PM 读取数据耗费了 70% 的工夫占比。
3 ROR 评估
ROR 次要影响零碎的写入性能。为了缩小零碎后台任务的烦扰，试验中敞开所有的 flush 以及 compaction 操作，敞开内存表中的建索引操作。每个线程写入 100 万个大小为 24 字节的 KV 对。试验通过设定不同的线程数以及 batch 的大小用以评估这些参数对系统写入性能的影响。
图 17 ROR 算法评估后果
batch 的影响：在表 17(a)对应的试验中，通过固定线程数为 32，扭转 batch size 的大小以测试 batch size 对系统写入性能以及提早的影响。结果表明，调节 batch size 从 1 到 90 时，零碎的写入吞吐增长到 49x，而均匀提早以及 P99 提早别离净减少 1.3x 以及 1.7x。在 batch size=90 时，其写入的吞吐量甚至超过 PM 硬件的随机写入 24 字节的吞吐，次要是因为 ROR 总是尽量采纳程序写的形式。当 batch size 从 50 减少到 90 时，其性能收益增长较为迟缓，而提早减少较大，次要是因为此时 PM 的硬件靠近饱和。当 batch size 大于 90 时，零碎的吞吐量不升反降，这次要是因为大的 batch 会导致 ROR 阻塞，进而影响写入的吞吐。
线程数的影响：试验中固定 batch size=50，调节线程数从 1 减少到 64。图 17(b)中的结果表明，在线程数从 1 减少到 16 时，其吞吐量呈线性减少。但当线程数大于 16 时，性能增长较为迟缓，比方线程数从 16 减少到 64 时，吞吐减少到 1.1x，但 P99 提早回升到 2.9x。次要是因为较多的线程并发写入导致对 PM 硬件的拜访竞争加大。理论中，选取适合的线程数以及 batch size 须要依据具体的硬件设施以及工作负载。
4 Global Index 评估
图 18 全局索引 GI 评估后果
试验中敞开 level0 到 level1 的 compaction，以评估 GI 绝对于 XS 的乱序 level0 的劣势，其中 XS-PM 示意将基线零碎的 level0 以及 WAL 放入 PM 中。试验首先随机写入不同大小的 KV 对，大小从 64 字节到 4KB，总计 50GB 的数据，并测试随机点读以及范畴查问的性能体现。图 15(a)表明，对于不同大小的 KV 对的随机写，XP 都优于 XS 以及 XS-PM。在图 18(b)(c)中，XP 绝对于 XS 以及 XS-PM 有微小晋升，随机读性能为 XS-PM 的 113x，随机范畴查问是 XS-PM 的 21x。其次要是因为试验中敞开了 level0 到 level1 的 compaction，导致 level0 沉积过多的乱序的数据块（试验中观测超过 58 的乱序数据块）。因为 XP 中 GI 是全局有序的，因而具备较高的查问性能。
另一个试验应用 32 个 client 线程采纳读写比为 1:1 的形式高压力写入数据，运行 10 分钟并察看零碎性能随工夫的变动。图 18(d)并表明，XP 绝对于 XS/XS-PM 性能晋升高达 15x，并且性能体现更稳固。在试验中，XS 以及 XS-PM 性能升高了 85%，而 XP 仅升高 35%。尽管 XS-PM 将数据放在速度更快的 PM 中（将 PM 用作一般磁盘），但其性能体现绝对于 XP 仍具备较大差距，并且 level0 数据沉积仍然会产生较大的影响。而 XP 采纳全局有序的 GI 以及更高效的 in-memory compaction，大大降低 level0 的数据沉积的影响。
5 Halloc 评估
图 19 Halloc 评估后果
本试验通过比照 Ralloc 以及 pmemobj 以评估 Halloc 的长久化内存调配性能。Halloc 将非长久化内存的治理托管到 jemalloc 中，因而其性能体现与同类办法类似。读者能够进一步参考文献 [4] 以理解更多将 PM 用作非长久化内存的分配器的性能体现。试验运行在单线程下，通过执行 100 万次内存调配计算单次调配的提早，调配对象的大小从 128 字节到 16KB。因为 Halloc 并非通用内存分配器，试验中通过从对象池中调配（Halloc-pool）以及通过 grant（Halloc-zone）别离模仿通用内存调配的 malloc 操作。图 19 表明，Halloc-pool 以及 Halloc-zone 在所有的测试中调配对象的提早均小于 1us，次要是因为 Halloc 对每次调配仅应用一个 flush 以及 fence 指令。但 Halloc 仅被设计用来反对基于 LSM-tree 的零碎，通用性不如 Ralloc 以及 pmemobj。
6 重启复原体现
图 20 重启复原性能体现评
为了评估零碎的复原性能，试验中写入 32GB 的数据，其中 key/value 的大小别离为 8 字节 /500 字节，总计 7000 万个 KV 对。试验中 GI 采纳非长久化索引，并保持数据全副落在 GI。非长久化的 GI 使得零碎重新启动时须要复原 GI 中的所有索引，因此等价于须要复原 32GB 的内存表。对于基线零碎 XS 以及 XS-PM（将 WAL 搁置在 PM 中），零碎敞开 flush，因此保障至多 32GB 的无效 WAL。因为 XP 能够并行的重建索引，试验中设置复原线程的数量从 1 逐步减少到 104（所有的 CPU core）。图 20 表明，XP 通过并行重建索引能够实现近秒级启动，然而 XS 以及 XS-PM 均须要消耗数分钟级的工夫，其中一个比拟重要的起因是基线零碎仅反对单线程复原。因为 XP 能够并行复原，因而能够在系统启动时利用全副的 CPU 资源以放慢启动速度。理论的利用场景中，内存表的大小通常远小于 32GB，因而复原工夫可达秒级以下。极速的数据库可恢复性兴许能够扭转现有的通过主备等形式实现 HA 的计划，进而省略备用节点，具备升高一半的 ECS 实例潜能。
七 后记
本文仅仅是利用 PM 等新硬件，针对基于 LSM-tree 的 OLTP 存储引擎进行优化摸索而迈出的一小步。实际上实现一个可用的工业级存储引擎波及很多方面，如可靠性、可用性、稳定性、性价比等，更多是寻找多方面因素的一个均衡的过程。而就本文中的计划，在理论的工业落地中仍然存在以下亟待解决的问题。
数据可靠性问题。对于数据库系统，数据可靠性处于极其重要的地位。PM 尽管可能提供长久化的字节寻址能力，但其仍然存在设施写入磨损、硬件生效等影响数据可靠性的问题。云上数据库实例中，传统的长久化存储层通过多正本及分布式共识协定等形式实现高可靠性的数据存储，因而将 PM 作为长久化存储时仍然须要解决该问题。一种可冀望的解决方案是构建基于 PM 的高牢靠的分布式长久化内存池，但分布式化的 PM 内存池如何设计，可能具备何种 I / O 个性等仍须要进一步摸索。面对工业化落地时，在 OLTP 存储引擎设计中针对单机 PM 硬件优化长久化索引意义可能不是很大。
PM 内存应用效率问题。在该论文中，PM 的内存能够用于长久化目标以及非长久化目标，但在固定 PM 容量下，如何确定多少内存空间调配给长久化应用，多少空间用于非长久化目标等是一个值得进一步摸索的问题。例如，依据负载主动调节空间的分配比例，在写密集的负载中调配更多的 PM 内存用于长久化存储，在读密集型负载调配更多的内存用于 cache 等非长久化目标。
性能抖动问题。对于基于 LSM-tree 的存储引擎，一个让人头疼的问题就是性能抖动问题，而产生抖动的一个重要起因是后盾 compaction 导致的 cache 批量激烈的生效。在分布式场景中能够通过 smart cache[5]等形式缓解该问题，在单机状况下，是否能够通过在 PM 中调配独自的缓存空间用于长期缓存 compaction 的旧数据，之后迟缓的执行 cache 的替换？
延长浏览
[1] J. Yang, J. Kim, M. Hoseinzadeh, J. Izraelevitz, and S. Swanson,“An empirical guide to the behavior and use of scalable persistent memory,”in Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST’20), 2020, pp. 169–182.
[2] B. Daase, L. J. Bollmeier, L. Benson, and T. Rabl,“Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads,”Sigmod, no. 1, p. 13, 2021.
[3] G. Huang et al.,“X-Engine: An optimized storage engine for large-scale e-commerce transaction processing,”in Proceedings of the ACM SIGMOD International Conference on Management of Data, Jun. 2019, pp. 651–665.
[4] D. Waddington, M. Kunitomi, C. Dickey, S. Rao, A. Abboud, and J. Tran,“Evaluation of intel 3D-Xpoint NVDIMM technology for memory-intensive genomic workloads,”in ACM International Conference Proceeding Series, Sep. 2019, pp. 277–287.
[5] M. Y. Ahmad and B. Kemme,“Compaction management in distributed keyvalue datastores,”Proc. VLDB Endow., vol. 8, no. 8, pp. 850–861, 2015.
原文链接
本文为阿里云原创内容，未经容许不得转载。