简介： 随着非易失内存产品的商业化推广，咱们对于其在云原生数据库中大规模推广的后劲越来越有趣味。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.
原文链接
本文为阿里云原创内容，未经容许不得转载。