ToB企服应用市场:ToB评测及商务社交产业平台

标题: SplitDB: Closing the Performance Gap for LSM-Tree-Based Key-Value Stor [打印本页]
作者: 李优秀    时间: 2024-8-16 17:48
标题: SplitDB: Closing the Performance Gap for LSM-Tree-Based Key-Value Stor
泉源

IEEE TRANSACTIONS ON COMPUTERS, VOL. 73, NO. 1, JANUARY 2024
主要内容：计划了NVM存储层用于在LSM压缩过程中衔接内存和SSD/HDD
Abstract

日志布局化合并树 (LSM 树) 是现代键值存储的核心数据存储引擎。随着云计算和数据中心的发展，它的接纳速率迅速加快。尽管 LSM 树得到了广泛的应用，但它仍然面临严峻的性能问题，比方写入停顿、写入放大和读取效率低下。
本文先容了使用新兴的非易失性存储器 (NVM) 技术提高基于 LSM 树的键值存储性能的研究。我们的性能诊断表明，上述问题主要来自麋集的热键值数据处理，而慢速存储设备又加剧了这一问题。为了解决热点瓶颈，**我们提出了一种基于混合存储的拆分日志布局化合并树，**使用 LSM 树固有的热数据和冷数据分离属性。我们的方法将频繁访问的小型高级别提升到快速 NVM 上，并将剩余的冷的大型低级别卸载到慢速设备中，从而有用地缩小了基于 DRAMdisk 的 LSM 树的性能差距。此外，我们通过提出各种新颖的技术来优化拆分 LSM 树的读写性能。我们构建了一个名为 SplitDB 的热点感知键值数据库并进行了大量实验。实验结果表明，与开始进的键值数据库相比，SplitDB 有用防止了写入停滞，实现了 6 倍的写入减少，并将读取吞吐量提高了 3.5 倍。
1. Introduction

物联网和呆板学习等现实应用中的数据呈指数级增长，对当今的云计算和数据中心供应商提出了重大挑战[1]。键值数据库，包罗LevelDB [2]、RocksDB [3]和Cassandra [4]，由于其易于明白的存储范例、快速检索和对非布局化数据的有用支持，为管理、存储和索引大量数据提供了有用的解决方案。键值数据库已成为当前云和数据中心折务提供商不可或缺的构建块，比方亚马逊[5]、Meta [3]和阿里巴巴[6]。
这些键值存储中的核心数据存储引擎是Log-Structured Merge树。LSM树是一种接纳异地写入计谋的写优化数据布局。LSM树将数据缓冲在内存组件中，并将它们惰性地写入磁盘。磁盘空间由组织为树布局的多个组件构成。**新版本数据会先到达高级别的磁盘组件，之后再迁移到低级别的组件，这个过程叫做 LSM 树压缩。由于旋转磁盘有利于顺序写入，因此内存组件刷新和数据压缩都充分使用了硬件的这一特性。**另一方面，数据读取会先搜刮内存组件。如果没有找到数据，它会按照从上到下的顺序搜刮磁盘上的每一级。这种 LSM 树计划主要会导致三个性能问题。
两个闻名的问题降低LSM-Tree的写入效率
同时，LSM tree 同样遭受低速读取。对于 DRAM 组件查找未掷中，必须逐级搜刮深层 LSM 树。逐级搜刮涉及昂贵的 I/O 传输，用于定位磁盘组件和密钥比较。长读取路径成为基于 LSM 树的键值存储的一个严峻缺点影响
作者 [10] 分析认为写停顿是由于 MemTable 刷新和数据压缩之间的性醒目扰造成的，并提出了一种调度方法来减少这种干扰。
MatrixKV [8] 使用 NVM 加快 L0-L1 压缩，从而减轻数据压缩对写停顿的影响。许多研究工作致力于通过从多个方面改造 LSM 树压缩来减少写放大，比方消除值数据写入 [7]、避免低级 SSTable 重写 [11], [12] 和跳过相邻级别合并 [13]。
为了减少长 LSM 树读取延迟，先前的研究提出了高效的辅助索引布局 [9], [14], [15]（我们也是提出一种辅助索引布局）。比方，ChameleonDB [14] 引入了 DRAM 内哈希表以避免长时间逐级 LSM 树查找。ElasticBF [9] 提出了热点感知布隆过滤器计划来提高热 SSTable 读取性能。
从前的文章提出了各种方法来独立解决这些问题。与它们差别，本文提出了一个团体解决方案来同时应对这三个挑战。我们的解决方案源于一个新发现：对于倾斜的工作负载，LSM 树性能问题主要是由迟钝、麋集的热数据处理引起的。我们在这里简要形貌这一发现。第二节具体先容了它
LSM 树包含多个级别，形成一个条理布局来满足数据请求。现实应用程序表现出倾斜的数据访问模式 [1]，[16]：一小部分热数据吸引了更高的关注。频繁的热数据更新会生成大量集中在高层的键值记录。我们在第二部分中的 YCSB 工作负载实验报告称，L0-L1 压缩中超过 54% 的数据写入涉及热键值记录（本方法实现的LSM-tree不涉及热数据，且数据不可变）。大量的热数据写入是写入放大的决定因素。此外，在慢速设备上运行的长而昂贵的高级热数据压缩无法实时清空高级空间，导致客户端写入不测停顿。末了，热数据比冷数据读取麋集得多。但是，压缩将热数据分散到多个树层上。查找分散的热数据会带来不可预测的长延迟，从而降低团体读取性能。
基于这些发现，本文计划并实现了一种新型热点感知键值数据库 SplitDB。它将新兴的 NVM 存储技术无缝融入 LSM 树计划中，以解决与热点相关的挑战，从而有用提高现代键值存储的性能。
非易失性存储器Non-volatile memories（如英特尔傲腾 DC 长期内存）提供靠近 DRAM 的访问延迟、优于 SSD 的速率、类似磁盘的数据长期性和字节寻址能力 [17]。这些设备特性使 NVM 成为基于 DRAM-SSD/HDD 条理布局的中间层。此外，LSM 树原生支持热数据和冷数据分离。高层麋集添补了大量更新的热键值记录，冷数据徐徐减少。使用这种特性，我们计划了一种基于混合存储的新型拆分 LSM 树。它将频繁访问的高层树提升到快速 NVM 上，并将较大的低层卸载到相对较慢的基于块的存储设备（本文中为 SSD）中。这种拆分 LSM 树架构包管了热数据处理事件（比方键值读取和数据压缩）大概发生在高速 NVM 中，从而缩小了内存存储条理布局中的性能差距。
我们充分使用 NVM 特性计划了分割 LSM 树。我们提出了多种有用的技术来优化分割 LSM 树的写入和读取路径。简而言之，==我们使用 NVM 字节寻址能力计划了一种新颖的基于链表的键值数据存储格式。==它有助于计划轻量级 DRAM 组件刷新和写入最佳 LSM 树压缩。此外，我们计划了一个级联跳表索引布局。它支持高效的跨级 LSM 树查找，从而减少了较长的 LSM 树搜刮路径。末了，我们提出了有用的数据提升和降级机制来保留 NVM 中的热数据。
基于拆分的 LSM 树，我们构建了 SplitDB，一个基于异构 NVM-SSD 存储的高性能键值数据库。SplitDB 同时满足了热点感知、写入效率和崩溃容忍度。在实验中，我们将 SplitDB 与商用 LevelDB [2]、RocksDB [18]、NVM 优化的 NoveLSM [19] 和 MatrixKV [8] 进行了比较，并使用了一系列微基准测试和 YCSB 工作负载 [20]。实验结果表明，与开始进的基于 LSM 树的键值存储相比，SplitDB 最多可提高 3.5 倍/2.9 倍的读写吞吐量，最多可降低 6 倍的写入放大，并有用防止写入停顿。
总结：我们做了以下贡献
2. Background and motivation

2.3 Closing the Performance Gap

先驱者计划使用快速 NVM 来弥补商品键值存储中存储硬件的迟钝问题。
两个代表性作品（NoveLSM [19] 和 MatrixKV [8]）接纳了差别的方法，如图 2 所示。NoveLSM 将 MemTable 和 ImmuTable 放在 NVM 中。它为键值写入提供了快速且长期的数据写入
MatrixKV 发现，较小且较慢的 L0 级别轻易导致写入停顿和写入放大问题。因此，MatrixKV 配置了一个较大的 L0 级别并将其存储在 NVM 中。
与它们相反，SplitDB 将高 k 级别放在 NVM 中。我们的动机有两个方面。起首，像英特尔 DCPMM 如许的可扩展 NVM 设备提供了很大的容量（128-512GB）。它与 512GB 到 2TB 的贸易 SSD 相当 [17]。NVM 有足够的空间来保留多个 LSM 树级别。其次，我们的动机实验表明，高级热数据 R/W 事件（比方数据压缩、MemTable 刷新和 SSTable 查找）会导致性能问题。仅仅提高 L0 性能不敷以完全解决这些问题

3. Split Log-Structure Merge Tree

3.1 Overview

由于现有的 LSM 树性能问题主要是由热数据处理速率慢引起的，我们的主要思想是使用超快的 NVM 来弥补慢速存储设备的缺点，从而提高 LSM 树热点性能。图 3 展示了所提出的拆分日志布局合并树。
LSM 树本身具有多级布局，可提供热/冷数据分离。我们使用这一固有属性来计划一种新型的拆分日志布局合并树，该树超过 NVM 和 SSD 的混合存储。拆分 LSM 树由两棵子树构成。其频繁访问的高层（即 H-LSM 树）被上传到快速 NVM 上，而较低层（即 L-LSM 树）驻留在慢速 SSD 上。L-LSM 树驻留在 SSD 存储中。它的键值布局、数据压缩和其他计划方面直接借鉴了现有的基于 SSD 的键值数据库（本文中的 LevelDB [2]）。此外，H-LSM 树保存在快速 NVM 中，以确保快速满足热数据请求。具体来说，我们从两个方面提出了多种技术来提高 H-LSM 树的性能：
（1）我们使用 NVM 硬件特性来广泛优化其键值存储布局以及数据读写路径（第 III-B 至 III-E 节）
（2）我们提出了有用的数据升级和降级机制，以将热数据在很大程度上保留在 NVM 内部（第 III-F 节)。
3.2 NVTable Data Storage

我们为 H-LSM 树计划了一种称为 NVTable 的新型数据存储布局（这个数据布局只存放在NVM中）。LevelDB 中的 SSTable 将键值对组织为有序线性数组。NVTable 使用 NVM 字节寻址能力将键值对组织在一个未排序的双向链表（称为 KV 列表）中，如图 4 所示。

NVTable 插入是一个简朴的 KV 列表附加，没有任何额外的数据移动。这种基于列表的未排序 KV 数据存储格式对于写入最佳的 H-LSM 树压缩计划非常重要。（这里在第四节有重要应用）
使用双向列表是因为硬件布局的缘故原由
NVTable 后续必要作为类日志布局来实现容错规复，所以此处必要存储数据的内存位置
虽然 KV 列表答应快速写入数据，但未排序的键值对组织会降低数据查找性能。键值对查找必要遍历整个 KV 列表并访问每个 KV 列表元素。我们引入了一个偏移数组来解决这个缺点。具体而言，NVTable 中的键值对顺序是偏移数组索引，而相关的内存地点偏移是偏移数组元素。使用偏移数组，NVTable 查找可以执行二进制搜刮以确定目的数据内存地点。然后，它使用内存地点来获取键值项。偏移量数组和其他 NVTable 元数据（如最大键）存储在一连的内存区域中，而 KV 对存储在外部。偏移量数组是在 ImmuTable Flush 期间构建的，稍后将对此进行形貌。
除了 L0 级之外，其他每个 H-LSM 树级都有一个具有非重叠键范围的 NVTable 集合。L0 级的 NVTable 是通过从 DRAM 中刷新 ImmuTable 生成的。L0 NVTable 无需进一步的数据合并或排序。它们的键范围大概会重叠。
3.3 Cascading Skiplist Index

H-LSM 树使用级联 NVMskiplist 来管理和索引除 L0 之外的每个 H-LSM 树级别的 NVTable。
L0 中的 NVTable 被组织为按创建时间戳排序的有序双向链表。它包管在 L0 中搜刮 NVTable 遵循严格的时间顺序。
我们选择 skiplist 作为我们的 NVTable 索引布局（此处才是NVM硬件中索引NVTable的数据布局），因为它具有可证实的无锁查找和对多版本数据管理的有用支持。我们的 skiplist 是一个混合 DRAM-NVM 索引。它将 skiplist 底层存储在耐用的 NVM 中。Skiplist 上层位于快速 DRAM 中。每个 NVTable 都由其最大键索引。H-LSM 树级中的键值对查找包罗两个阶段。起首，它遍历 skiplist 以找到 NVTable，其次，它在 NVTable 中搜刮目的对。
传统的 LSM 树经常因其冗长的多级查找而因其读取效率低下而受到批评 [9]，[14]。LSM 树查找本钱高昂。它包罗从当前树级的大量 SSTable 中定位目的 SSTable 并在 SSTable 中搜刮键值对。我们提出了级联跳跃列表计划来减少 H-LSM 树查找延迟。
我们起首简要先容现有的跳跃列表查找（skiplist ）过程，然后形貌我们的跨层查找优化。
   具体来说，跳跃列表查找从最高级别开始并遍历列表以查找键大于或即是目的键的第一个节点(为什么要找这一个点？)。如果有匹配的键，则查找竣事。否则，它向下重复此过程，直到到达最底层。
  为了减少跳跃列表搜刮中的查找范围，我们引入了一个称为级联指针的跨层指针。由于差别级别的 NVTable 具有重叠的键范围，级联指针可充当从上层跳跃列表的节点 1 到下层跳跃列表的节点 2 的快捷方式。节点 1 的键必须小于节点 2 的键才能包管正确的查找结果（这里的级联指针是为了快速找到低层级和高层于该键值相近（低于）的节点）。此外，节点 1 的键应尽大概靠近节点 2 的键以最小化搜刮范围。传统的跳跃列表搜刮总是从最左边的节点开始。使用级联指针，上层跳跃列表搜刮可以资助减少低层跳跃列表搜刮中的查找范围并有利于后续查找。
  如图 5 所示，

在第一次查找键时，线程在 Lk 处执行通例跳跃列表搜刮。它在底层找到目的跳跃列表节点并搜刮 NVTable。如果未掷中，它将搜刮 Lk+1 处的跳跃列表。到达目的节点并在 NVTable 中找到目的键后，它会在 Lk 处创建一个级联指针，指向 Lk+1 处的目的节点。在第二次查找中，线程不是从 Lk+1 处的最左边的节点遍历，而是使用级联指针直接跳转到中间跳跃列表节点。这个中间节点非常靠近目的节点，剩下的 Lk+1 搜刮从这个中间节点开始。它有用地减少了 Lk+1 处的查找范围。
每个跳跃列表都提供无锁插入/删除/查找，并使用风险指针 [27] 进行安全内存回收。此外，每个跳跃表节点都包含一个自旋锁和一个引用计数器。当线程将一个级联指针从节点1设置到节点2时，它起首获取这两个节点的两个锁，然后增长节点2的计数器。只有当节点2的计数器达到零时，才能回收节点2。由于级联指针很少被修改，因此这种基于锁的方法险些没有性能本钱。
3.4 LightWeight（轻量级） ImmuTable Flush（完备过程在这里报告，解释了图四的使用方法）

在传统的 LSM 树计划中，键值对起首长期化在 WAL 文件中，然后插入到 MemTable 中。当 MemTable 切换到 ImmuTable 时，ImmuTable 中的键值对将刷新到长期 SSTable。为了减少 ImmuTable 刷新延迟，我们提出了无日志键值数据插入，并消除了 ImmuTable 刷新路径中昂贵的数据长期化操作。
   这里要明白：
    如图 6 所示，

在线程将新的键值对插入 MemTable 之前
它起首创建一个长期键值对并在步骤 ❶ 中附加一个 KV 列表节点。KV 列表是一个双向链表。在当前的硬件架构上，原子地修改两个不一连的八字节字是不大概的。我们只使用 cmpxchg 指令原子地设置一个八字节后向指针（这里先容了为什么使用双向链表），并通过 clwb 指令和 sfence 指令将其长期化。前向指针将在稍后的 ImmuTable 刷新期间创建。对于并发写入，我们使用链接和长期技术 [28] 来实现正确的长期顺序。
在步骤 ❷ 中，线程将键值对插入易失性 MemTable。此放入操作完成，无需任何额外的日志写入。当 MemTable 已满时，它将更改为 ImmuTable。背景线程将 ImmuTable 刷新到存储设备。荣幸的是，ImmuTable 中的键值数据在放入期间已长期保存在 NVTable 中（这里NVTable的功能代替了日志）。在步骤 ❸ 中，我们扫描 ImmuTable 跳表的底层。底层是已排序的键值对的链接列表。我们按顺序读取每一对，在 NVTable 中找到其内存地点，并创建偏移数组元素。构建偏移数组后，我们向后遍历 KV 列表以在步骤 ❹ 中创建前向指针。之后，生成一个完备的 NVTable，而且可以释放此 ImmuTable。
3.5 Write-Optimal List Compaction（写入最佳列表压缩）

传统的 LSM 树压缩选择一个或多个捐躯 SSTable，将数据加载到 DRAM 中（数据合并在内存中执行），并在合并和排序键值记录后将新的 SSTable 写入磁盘。（合并数据）
压缩期间重复的数据写入是写入放大的根本缘故原由。使用 NVTable 数据组织，我们计划了写入优化的 NVTable 压缩，称为列表压缩。（根据NVTable实现的写入优化）它通过避免在压缩期间进行任何现实数据复制来减轻写入放大。
假设 H-LSM 树级别 Lk 的大小超过了预界说的阈值。列表压缩以循环方式选择捐躯 NVTable，并在 Lk+1 级别中找到键范围与捐躯 NVTable 的键范围重叠的 NVTable（压缩到                                                   L                                           k                                  +                                  1                                                       L_{k+1}                     Lk+1​层）。这些 NVTable 一起作为输入文件。

如图 7 所示，在第一步中，多个工作线程对所有键值记录执行并行就地样本排序。对于每个 NVTable，工作线程使用偏移量数组来收集一定数量的等距样本。然后，主线程对所有采样的 KV 对进行排序，并在排序数据上收集 k − 1（k 是工作线程编号）个等距样本（论文最开始好像是根据基数排序的方式）。
两个相邻样本的键的间隔表示工作线程的键范围。所有工作线程的键范围均不重叠。每个工作线程从每个 NVTable 中获取键范围内的关联数据，独立执行本地合并排序，并生成新的偏移数组。使用偏移数组元数据，每个工作线程执行就地排序而不会干扰 KV 数据位置。
在第二步中，每个工作线程使用偏移数组扫描键值对并执行数据重复数据删除。每个键值对都有一个序列号，该序列号是在 put/del 中创建的单调递增时间戳。如果它检测到具有相同键的多个键值记录，则使用序列号保留具有最新值的记录（哪个时间戳新保留哪一个，也是类似于增量查询的方式）。对于过时的 KV 对，在关联的偏移数组条目中设置删除标记。
所有 worker 完成排序后，主节点将 worker 的结果连接起来以生成全局偏移数组。
在第三步中，它将全局偏移数组划分为 m 个部分，其中 m 是输出 NVTable 的数量（此时实现了新低层级的NVTable生成）。它将分区数组分配给 worker。对于输出 NVTable，worker 将偏移数组复制到 NVTable 中，找到关联的 KV 列表节点并重新链接这些节点。
列表压缩会调整前后列表节点指针以移动键值对，而不是像传统 LSM 树压缩那样复制现实数据。由于写入放大主要是由键值数据写入引起的，因此列表压缩使用基于列表的数据组织来避免大量键值数据复制，并只需修改四个八字节指针即可进行列表节点调整。
键值数据排序不会影响就地排序的体系状态同等性。在第二步中，我们使用全局偏移数组进行数据重复数据删除（这里实现了对NVM最高层L0数据的排序）。旧版本的键值对在偏移数组条目中被标记为已删除。与第一步类似，此步骤对输入数据也没有副作用。在第三步中，我们使用原子 cmpxchg 和 clwb 指令来修改和长期化 KV 列表指针。它包管了 KV 列表节点链接期间的崩溃同等性。如果发生崩溃，规复例程将使用偏移量数组重修不完备的 KV 列表。
3.6 Data Promotion and Demotion Mechanism

NVM 的访问速率比 SSD/HDD 更快。因此，在 NVM 中保留热数据对于分割 LSM 树的性能尤为重要。为了实现这一点，我们提出了数据升级和降级机制，旨在将热键值记录从慢速 SSD 迁移到快速 NVM，并从 NVM 中逐出冷键值记录。
Data promotion
为了计划一个高效的数据提升机制，我们必要答复两个问题：
（1）怎样精准识别热门键值对？
（2）何时将热门键值对提升到 H-LSM 树上？
为了答复第一个问题，我们使用 count-min sketch 方法 [29] 来检测 SSTable 中的热门键值数据。具体来说，我们为每个 SSTable 创建一个具有 m 行和 n 列的二维 sketch 数组。m 是哈希函数的数量。当线程读取一个键值对时，它会增长关联的 m 个 sketch 数组单元中的计数器。如果这 m 个单元中的最小计数器大于预界说的阈值，则表示该键值对是热门的，我们将其添加到易失性缓冲区中以供将来提升。
由于 SSTable 中的键值对是经过排序的，因此插入新的 KV 对会导致昂贵的数据移动。为了避免这种开销，我们将数据提升集成到 L-LSM 树压缩中。具体来说，假设压缩是将键值对从 Lk 迁移到 Lk+1。我们选择那些键位于输入 SSTables 的键范围内的热门 KV 对，并将它们添加到压缩输入中。此压缩将输出新的 SSTables 到 Lk+1（这里不应该是将热门KV对输出到Lk-1层吗）。因此，热门键值对从 Lk+2 提升到 Lk+1。在热门数据被提升到 SSD 中最高的 L-LSM 树级别后，我们必要将它们迁移到 NVM 中的 H-LSMtree。类似地，当压缩发生在末了两个 H-LSM 级别之间时，我们选择最高 L-LSM 树级别中的那些热门 KV 对并将它们添加到此压缩输入中。
此外，当前的 LSM 树压缩是热点无意识的。压缩大概会将热数据移至低级别。为了避免不测的数据沉降，我们计划了一个热点意识的 L-LSM 树压缩。对于 Lk-Lk+1 压缩，我们将输出键值对分为热集和冷集。在压缩输出期间，热的键值对保留在Lk，而冷的键值对移动到Lk+1。
Data Demotion
除了热数据提升之外，我们还将冷键值数据从 NVM 降级到 SSD。**我们接纳基于 LRU 的粗粒度数据驱逐计谋来降级 H-LSM 树数据，**而不是为 L-LSM 树使用细粒度的热数据草图。我们的动机是 LSM 树工作负载通常是写入麋集型的。因此，更新频率最低的 NVTable 包含最冷的数据，应该被驱逐到 SSD。具体来说，我们为存储在 H-LSM 树级别的 NVTable 构建一个全局 LRU 列表。新创建的 NVTable 被插入到 LRU 列表头中，因为它是最热的。当压缩发生在 H-LSM 树的最低级别时，它会选择位于 LRU 列表尾部的 NVTable，并将 NVTable 数据压缩到底层 L-LSM 树。
4 SplitDB：Design and Implementation

我们使用发起的分割 LSM 树构建 SplitDB。SplitDB 将新兴的 NVM 技术集成到现代键值数据库中，以实现热点优化、写入效率和崩溃同等性。
4.1 Parallelizing KV Data Insert

SplitDB 并行化键值数据插入以提高用户写入性能。LevelDB 序列化 MemTable 插入。当多个并行线程执行 MemTable 插入时，委托线程会收集所有线程的请求。它会逐个将键值对记录到 WAL 文件中。在 WAL 文件长期化后，委托线程将键值对插入 MemTable。WAL 文件写入和 MemTable 插入都是序列化的。RocksDB 通过并发 MeTable 插入缓解了这个可伸缩性问题。但是，其 WAL 文件写入仍然是序列化的。
与 RocksDB 类似，SplitDB 也答应并行 MemTable 插入。此外，SplitDB 中没有 WAL。**它使用崩溃同等性 KV 列表来确保数据放入/删除的原子长期性。KV 列表插入是无锁的。**多个线程使用 cmpxchg 指令以原子方式将数据附加到 KV 列表。之后，乐成的 KV 列表附加使用 clwb 来包管数据的长期性。
4.2 Multi-Version Data Management

键值数据库应提供多版本数据管理，以实现正确的范围查询。我们使用与 LevelDB 相同的版本界说，即版本**是两个相邻压缩之间的 SSTables/NVTables 集**。压缩将生成许多新的 SSTables，但它们对于在压缩之前启动的读取器是不可见的。每次压缩完成时，LevelDB 都会创建一个具有 L 行和 k 列的二维版本数组。L 和 k 分别是 LSM 树的高度和所有级别的最大 SSTable 数量（并不完全是是一个矩形）。版本数组跟踪 SSTables，数组条目是 SSTable 文件名。在 SplitDB 中，其 L-LSM 树接纳与 LevelDB 相同的管理方案。对于其 H-LSM，我们提出了一种基于时间戳的轻量级多版本数据管理计谋。

具体来说，图 8 表现 SplitDB 维护一个全局时间戳 T，它是一个单调递增的整数。
每次 SplitDB 完成压缩或 ImmuTable 刷新时，它都会将 T 增长一。每个全局时间戳都有一个关联的引用计数器（图中的Ref）。读取器（比方，读取或扫描 NVTable）在开始/完成 NVTable 读取时会增长/减少计数器。每个 NVTable 都有两个本地时间戳：创建时间戳                                              T                            c                                       T_c                  Tc​和逻辑删除时间戳                                              T                            l                                       T_l                  Tl​（NVTable 自身的记录）。
压缩会删除旧的 NVTable 并生成新的 NVTable。假设当前全局时间戳为 T。已删除 NVTable 的逻辑删除时间戳设置为 T，而新创建的 NVTable 的创建时间戳设置为 T + 1。
在 SplitDB 中，NVTable 使用元组 [max_key, Tc] (key的最大值，创建时的时间戳)进行跳跃列表索引。max_key 是主键。对于具有相同 max_key 的 NVTable，它们按 Tc 降序排序。
如图 8 所示，假设读取器从 T8 开始。只有在 T8 之前创建的 NVTable 集对读取器可见（因为之前的NVTable失效了）。读取器在 ① 中增长相应的计数器。然后，它使用请求的键 10 和时间戳 T8 遍历跳跃列表。它找到第一个元组大于或即是 [10, T8] 的节点 (②)。
元组比较规则界说如下。对于两个元组 t1：[key1，T1] 和 t2：[key2，T2]，(1) 如果 key1 < key2，则 t1 < t2。(2) 如果 key1 = key2 且 T1 > T2，则 t1 > t2。对于 (1)，我们通过将 T8 与 NVTable 的创建和逻辑删除时间戳进行比较来进一步检查 NVTable 的有用性 (③)。
如果 Tc ≤ T8 ≤ Tl，则此 NVTable 可见。否则，如果 Tl <T8，则表示此 NVTable 在 T8 之前发生的压缩期间已被删除。因此，它对读取器不可见。
对于 (2)，我们还验证了关联的 NVTable 的逻辑删除时间戳。
无论哪种情况，如果 NVTable 验证失败，读取器都会继续遍历底层列表 (④)，访问 NVTable 的最大键大于或即是情况 (1) 或 (2) 中的键的后续节点，并验证时间戳 (⑤)。
4.3 SplitDB KV operation

Get[key]：Get[key] 大概导致涉及 DRAM MemTable、ImmuTable、NVM H-LSM 树甚至 SSD L-LSM 树的多层查找。假设 get 请求从 T 开始。
它起首探测 MemTable 和 ImmuTable。如果未掷中，它将搜刮 NVM H-LSM 树。对于每个 H-LSM 树级别，它会在级联跳跃列表中搜刮第一个键大于 key 的节点。接下来，它通过验证创建和逻辑删除时间戳来找到有用的 NVTable。**如果验证乐成，它会在有用的 NVTable 中搜刮请求的键。**如果在 H-LSM 树中查找未掷中，它将继续在 SSD 中搜刮 L-LSM 树。查找过程与 LevelDB 相同。唯一的区别是它起首检查提升缓冲区，然后再搜刮 SSTable。
Put[key, val]/Del[key]：Put 或 Del 会创建新的键值记录。 Del 为值创建墓碑标记。如第 III-D 节所述，此键值记录长期保存在长期性 NVTable 中，然后以严格的顺序插入易失性 MemTable 中。
Scan[min, max]：扫描操作创建一个迭代器。此迭代器遍历所有拆分 LSM 树级别以收集键值对。假设 Scan[min, max] 从 T 开始。起首，它在每个拆分 LSM 树级别定位起始遍历位置。在 H-LSM 树中，它使用 min 搜刮跳跃列表以找到当前级别上第一个最大键大于或即是 min 的 NVTable。如果有多个匹配的 NVTable，类似于 get，它会检查它们的有用性。按照与 LevelDB 相同的方法，它在每个 L-LSM 树级别定位起始 SSTable。然后，迭代器开始在 NVTable/SSTable 中读取给定范围 [min, max] 内的键值对。如果读取到多个差别树层级的相同key的KV对，则返回序号最大的对，且序号应该小于T，该对包含最新的数据版本，迭代器持续扫描，直到当前读取的key超过[min,max]。
4.4 SplitDB Recovery and Implementation

体系突然崩溃后，SplitDB 规复例程开始将数据库规复到同等状态。起首，它在 NVM 中规复 H-LSM 树。规复例程扫描每个 H-LSM （高层级树）树级别中的每个跳跃列表底层，以在 DRAM 中重修上层。接下来，它规复在 ImmuTable 刷新之前创建的这些不完备的 NVTable。它添加 KV 列表节点的缺失后向指针并生成偏移数组。之后，它将规复的 NVTable 插入到 H-LSM 树 L0 级。对于压缩期间生成的不完备 KV 列表，规复例程使用全局偏移数组重新链接剩余的 KV 列表节点。接下来，LevelDB 规复例程规复 L-LSM 树。末了，SplitDB 还运行 PMDK 规复例程来规复 NVM 内存池状态。
SplitDB 是基于 LevelDB [2] 开辟的。与 RocksDB 类似，我们为 SplitDB 添加了并发压缩支持。我们添加了约莫 5700 行 C++ 代码来实现 NVM 中的 H-LSM 树。此外，我们还修改了 1200 行 LevelDB 代码，以实现数据升级和降级机制以及热点感知并发压缩。我们使用 Intel PMDK 库 [30] 来管理 NVM 空间。
footnote


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4