LSM-tree

• ICDE‘2024 LSM-tree 相关论文选读。

• 具体技术方面，主要涉及到 KV 分离、NVM、学习索引、FPGA、特定负载（范围查询、RMW/Merge）等。

Scavenger: Better Space-Time Trade-Offs for Key-Value Separated LSM-trees

TL;DR/Abstract

• KV 分离的 LSM-tree 有效减小了 LSM-tree 的写放大，提升了前台写性能，但是空间放大严峻。

• 空间放大严峻的两大原因：
• 低效的垃圾回收操作，缺乏对负载特征的全面考虑；
• 索引 LSM-tree 中延迟的合并（Compaction）操作，导致部分垃圾被隐藏，GC 无法感知

• 针对 KV 分离的 LSM-tree 的空间放大问题，我们基于 TerarkDB/LavaKV 提出了本文的方案 Scavenger：
• I/O 高效的 GC 针对 GC 的三个关键步骤（读、反查、写）分别进行了优化；
• 空间感知的 Compaction 策略，通过补偿及时调度 Compaction，有效提升系统垃圾率，从而提升 GC 效率

• 在相同存储空间配额下显著提高了写性能，不限制存储空间时实现了更低的空间放大。

Motivation

• 传统的 LSM-tree 总结：
• LSM-tree 通过将随机写转换为顺序写来充分利用存储设备的特征，提升写性能；
• LSM-tree 因为异地更新的策略以及有序性的要求，频繁执行 Compaction 导致高写入放大；
• LSM-tree 的层级结构以及 Dynamic Level 机制有效控制了空间放大。

• KV 分离的 LSM-tree: KV 分离的 LSM-tree 通过在独立的日志中存储值数据，在 LSM-tree 中只保留索引数据来减小 LSM-tree 的大小。这种方法最小化了 LSM-tree 合并操作所涉及的数据量，减少了写放大。然而，这增加了空间成本。为此 KV 分离的 LSM-tree 引入了 GC 操作来回收空间。

• 空间放大建模分析
• 在优化空间放大之前，我们对 KV 分离的 LSM-tree 的空间放大做了建模分析。

• 对于传统的 LSM-tree，在开启 Dynamic Level 且达到一个相对稳定的状态之后，其最后一层的数据可以近似地看做该 LSM-tree 中存储的唯一数据集的大小，而上层的数据则是对最后一层数据的更新，所以我们可以将传统的 LSM-tree 的空间放大可以表示为
• 表示除最后一层以外上面所有层的数据大小
• 表示最后一层的数据大小

• 对于 KV 分离的 LSM-tree，因为分离以后索引 LSM-tree 相比于整个 value data 而言较小，其空间放大可以近似用 value data 的空间放大来做估计。但在表示之前我们尝试对 value data 中的数据进行分类：
• 有效数据 D 表示与索引 LSM-tree 的最后一层相关联的值数据，对应表示了唯一数据集的总大小；
• 隐藏垃圾 对应于与索引 LSM-tree 的最后一层中仍在等待合并的键相关的值数据。即使它已经过时，系统也不能将其识别为垃圾数据，因为合并尚未发生。
• 暴露垃圾 是指在索引 LSM-tree 合并过程中被合并的键对应的值数据。它会被计入到系统的垃圾率，该垃圾率将用于触发后续的GC操作进行空间回收。

• 考虑到LSM-tree本质上默认容忍了上层数据对应的空间放大，这就导致了垃圾数据被隐藏。因此，隐藏垃圾与有效数据的比率可以近似为索引LSM-tree中上层数据与底层数据的比例，可以表示为：

• 至此我们可以将 KV 分离的空间放大表示出来：

• 至此我们可以确定 KV 分离的 LSM-tree 的空间放大的两个来源：
• Value Data 中的暴露垃圾比例，主要受 GC 影响；
• 索引 LSM-tree 中的空间放大$$S_{index}$$，主要受 Compaction 影响

• 空间放大原因一：I/O 低效的 GC
• 展示了不同工作负载下每个步骤的延迟分解，表明GC操作性能高度依赖于工作负载。具体来说，
• Read：大部分负载的开销主要瓶颈，尤其是大 value 负载
• GC-Lookup：在小 value 负载和变长负载下更显著
• Write：在大 value 负载下也不容忽视
• Write-Index：对于 Titan 等需要回写的引擎来说开销很大，该步骤被 TerarkDB 消除

• 空间放大原因二：延迟执行的 Compaction
• 索引 LSM-tree 展现出相比于传统 LSM-tree 更严峻的空间放大，进一步分析发现：
• 分离以后更小的 key SST 文件大小（211K for Fixed-8K vs 64M SSTable size）
• 分离以后更少的 Compaction 执行次数（分离以后执行次数是不分离的次数的 27.8%）

Design

• 引入几种新的结构：
• Value SST 采用 RecordBasedTable 优化 GC-Read
• Key SST 采用 IndexDecoupledTable 优化 GC-Lookup
• 内存中引入 DropCache 便于冷热识别，实现冷热数据分流

• 引入了基于补偿大小的 Compaction 策略来及时调度 Compaction 执行

• 引入了空间感知的限流策略确保存储空间可控，以及测试比较的公平性~

• I/O 高效的 GC
• RecordBasedTable - Lazy Read of GC
• 为 Value SST 提出了基于 Record 的表结构，每个 KV 对作为一个数据块，将键数据聚集在索引块中，GC-Read 只需要先读取索引块就可以获取所有的键数据，在执行 GC-Lookup 以后发现数据有效之后再去读取对应的 value。
• IndexDecoupledTable - Index-Record Separation
• 为 Key SST 提出了新的表结构 DTable，分离索引和记录，并赋予 index key blocks 更高的缓存优先级
• DropCache - Hotness-aware write
• 通过引入了缓存 DropCache 进行热点检测，记录了 Compaction 过程中发生了 Drop 的键数据来作为热数据集用于指导后续数据写入的分流。

• 空间感知的合并策略
• KV 分离以后，索引 LSM-tree 的 Compaction 没能考虑到实际的空间占用。
• 我们通过补偿索引 LSM-tree，将其填充成未分离的 LSM-tree，就可以重新感知到整体的空间使用。通过记录对应的 value 大小，并在计算 Compaction Score 过程中使用补偿大小来计算，从而及时调度 Compaction。

Evaluations

• 大量实验表明，本文方案 Scavenger 在相同存储空间配额下显著提高了写入性能，在不限制存储空间下实现了比其他 KV 分离 LSM 树（包括 BlobDB、Titan 和 TerarkDB）更低的空间放大，从而实现了更好的时空权衡。

• 限制存储空间大小为 1.5x 数据集下的 YCSB 吞吐测试，对应了 Mixed-8K 负载和 Pareto-1K 负载
• Mixed-8K: 1:1 ratio of small (uniformly distributed from 100B to 512B) to large (16KB) values
• Pareto-1K: value sizes that conform to a generalized Pareto distribution

• 不限制空间下 YCSB-A 的吞吐和空间放大

STEM: Streaming-based FPGA Acceleration for Large-Scale Compactions in LSM KV

Abstract

• 日志结构合并树(LSM-tree) 以其优异的写效率和较高的空间利用率而被广泛采用。在基于 LSM 树的键值(LSM KV)系统中，定期调用 Compaction 以保持良好的系统性能。随着 LSM-KV 规模的增大，大规模 Compaction 现象频繁出现。Compaction 吞吐量随着输入的增加而显著降低，导致频繁的写停顿和总体写吞吐量的下降。本文提出了一种基于流的 FPGA Compaction 框架 STEM 来解决这个问题。引入了一种简洁的算法来实现基于流的大规模数据 Compaction。通过多单元流水线和动态流水线调度，STEM 可以有效地处理大规模的 Compaction 任务。实验结果表明，STEM 的 Compaction 吞吐量比现有的 RocksDB Compaction 吞吐量提高了 35 倍，比最先3进的 FPGA 加速器提高了 2.09 ~ 2.27倍。

Motivation

• 现有软件方法优化 Compaction 策略往往伴随着别的开销，如读放大；而基于 FPGA 的硬件方法在处理大规模 Compaction 任务时受限于硬件资源（尤其是 DRAM 和 LUT，FPGA 中一个用于实现逻辑功能的存储单元）。

• Compaction 规模变大意味着更多的写停顿，
• FPGA 的 DRAM 容纳不下这么大的数据来做 Compaction
• 输入文件越多，LUT 消耗越大，以前的方案在输入超过了 9 就只能由 host 端接管，无法 offload 给 FPGA

Design

• Clean Cutter 把文件拆分成多个数据块
• 大规模文件被分割成大小有限的不重叠块。该算法首先获取每个SST文件的密钥范围。每个文件的最大键由一个最小堆 k 来选择和维护。clean-cut boundary 的值被设置为堆 k kmin 的顶部元素，并选择边界内的块作为压缩输入。使用 clean-cut，压缩结果将不会与输入的其余部分有重叠的键范围，从而保证压缩的正确性。

• 多单元流水线
• Clean Cutter 把文件拆成多个数据流。它还为并行处理输入提供了机会。多单元流水线设计协调了CPU上的Clean Cut、数据传输和FPGA上的计算单元，整个工作流程从CPU上的Clean Cut开始，CPU选择一部分压缩输入。由一个Clean Cut选择的块形成一个块集，它将通过缓冲区读取传输到FPGA DRAM上的缓冲区。然后FPGA上的计算单元开始合并这些选定的块。对于并行执行，每个块集在FPGA上都有自己的缓冲区，并且不同块集的压缩是独立处理的。对于合并步骤，每个FPGA计算单元处理一个Block Set，多个FPGA计算单元并行执行，进一步提高了效率。压缩吞吐量随着计算单元的增加而增加

• 动态流水线调度
• 为了进一步提高STEM的压实效率，在调度过程中尽量减少流水线气泡是至关重要的。这是我们想要的完全流水线化的合并循环。最大限度地提高压缩效率，提高硬件资源利用率。
• 然而，由于每个阶段的时间消耗不同，大规模压实的流水线设计具有挑战性。当系统处理可变长度的输入时，静态流水线调度可能导致管道气泡。这是一个管道气泡，当新的块被转移到缓冲区 1 时，它仍然被前面块的写操作所占用。主机与 FPGA 之间的数据传输受阻。这可以归因于缓冲区的数量有限。
• 当新的块分配给 FPGA 计算单元 1 时，当它仍在处理以前的块时，会发生流水线气泡。FPGA 计算单元的数量有限，导致流水线气泡。
• 为了最大限度地减少流水线气泡，我们引入了一种新的流水线计划。我们的分析将缓冲区大小确定为流水线性能的关键因素。确定了减少流水线气泡的数学条件，并建立了最佳缓冲大小公式。使用这些公式动态调整每次Compaction 的缓冲区大小

 

Evaluation

Enhancing LSM-tree Key-Value Stores for Read-Modify-Writes via Key-Delta Separation

Abstract

• 越来越多的人在实际的键值(KV)存储工作负载中观察到读-修改-写(RMW)，以支持细粒度的更新。为了使 RMW 高效，一种方法是将增量(即对当前值的更改)写入日志结构的合并树(LSM-tree)，但是它增加了由检索和组合增量链引起的读取开销。我们提出了一个称为 key-delta (KD) 分离的概念，以支持 RMW 密集型工作负载下 LSM 树 KV 存储中的高效读取和 RMW。KD 分离的目的是将增量存储在单独的存储区域中，并将增量分组到称为 bucket的存储单元中，这样一个键的所有增量都保存在同一个 bucket 中，并且可以在随后的读取中一起访问。为此，我们构建了 KDSep，这是一个中间件层，实现 KD 分离，并将 KDSep 集成到最先进的 LSM 树 KV 存储(例如RocksDB 和 BlobDB)中。我们表明，KDSep 在 RMW-intensive 工作负载下实现了显着的 I/O 吞吐量增益和读取延迟降低，同时保持了一般工作负载的效率。

Motivation

• 有研究表明 RMW 也是常见的一种负载。
• 有研究表明在 AI/ML 领域中的 RocksDB 实例上大约 92.5% 的请求都是读修改写；
• 在事务性数据库 benchmarks 中也有大约 90% 的负载是 RMW
• YCSB-F 也有 50% 的请求是 RMW
• NoSQL、实时数据处理、社交图数据库中也如此

• RocksDB 为了支持 RMW 使用了 Merge 语义来代替传统的读修改写，即把 delta 写入，而不需要读，从而实现快速的 RMW，但是引入了读开销。因为读取操作不仅需要读取出当前的 value，还要读取出整个 delta 链，从而重建出 value 的最新的版本；这样的 delta 可能横跨多个 levels。

• 作者测试发现 Merge 操作可以减少 RMW 延迟 96.9%，但是增加读延迟 74.1%。一种可能的解决方案是 KV 分离，通过减小 LSM 的大小来减小读延迟，但是当前的实现还是将 delta 存储在 LSM-tree 中，虽然一定程度上减小了读延迟，但是延迟还是很高。
• 图 3 的细节：
• 1. 作者认为 KV 分离能减小读延迟；
• 2. Get-Put 方式中大部分读出现在 low level，而 Merge 主要在 high level；且 Merge 读更多

Design

• 设计的几个挑战：
• 减少对于 LSM-tree 元数据的读取：即 KV 分离以后如果还是存储了元数据在 LSM-tree 中读开销还是很大
• 减少对于 KD 数据的读取：需要遍历所有的 KD 数据，可能造成大量的随机访问，需要做聚合
• 需要对 KD 数据做 GC：如果在 LSM-tree 中记录元数据，可能导致查询开销变大
• 崩溃恢复：添加了额外的单独存储组件，需要小心处理崩溃一致性

• 设计：
• 引入了三个新的结构：基于跳表的索引来索引 delta 中的 range；KD Cache；Bucket Table 管理 Bucket
• KV/KD 分离的逻辑：value 分离存储在 vLog 中，delta 写在 BucektTable 中，持久化存储在 DeltaStore 中，value 的元数据存储在 LSM-tree。Commit Log 来保证 Bucket Table 的崩溃一致性。读则是并行读取。

• 按 range 分 Bucket 存储 delta，每个 Bucket 大小 256K，Bucket 是一个连续的空间，有自己的起始地址；
• Bucket 内部无序，Bucket 因为分区使得分区间有序；维护跳表索引 Bucket，记录其最小键；
• 分区是按照 write buffer 写回的 delta 数据按照 256K*5% 大小的粒度做初始分区，然后构建索引
• 分区变大以后会在 GC 过程中被拆分；分区中不仅存储了 delta 还存储了表示删除的 anchor；
• 追加写入使得没有顺序保证，影响读，所以加一个有序层；GC 之后有序，有序层只存储 delta
• 读取的最大 I/O 开销为 256KB，即 Bucket 大小；作者一个 insight 是 256K I/O 延迟只是 4K 的 4x。
• 每个 Bucket 在内存中维护了一个索引，两个 BF，一个写 Buffer；索引是一个稀疏索引，确保两个索引项之间的数据只比 4K 略大，不超过 8K。每个 Bukcet 索引的大小控制在 1.75K 左右。写 Buffer 大约就是 SSD page 大小 4K。
• 全局的 KDCache 缓存最新读写的数据。（所有 Bucekt 共享）

• GC 承担着回收空间、排序、以及拆分合并 Bucket 的任务
• GC 在 Bucket 满了之后执行，合并其中的 delta；有效 delta 达到阈值拆分 Bucket；
• 如果达到了拆分阈值且 Bucket 数量达到了 N-2 就执行合并，因为无法分配更多的 Bucket
• 拆分合并后需要更新对应的索引信息 Skiplist

Evaluations

Range Cache: An Efficient Cache Component for Accelerating Range Queries on LSM-Based Key-Value Stores

Abstract

• LSM-tree 已广泛用于键值存储，以提供高写吞吐量。但是，LSM-tree 存在周期性 Compaction 操作导致的块缓存无效问题，这会降低块缓存的效率，导致读取性能差，特别是对于 range 查询。为了解决这个问题，我们提出了一个新的缓存组件，称为范围缓存，以加速基于 LSM 的键值存储的范围查询。RangeCache 与传统块缓存的区别在于两个方面。首先，范围缓存缓存查询结果，即键值对，而不是数据块。其次，与传统的块缓存利用哈希表来索引数据相比，范围缓存包含一个有序索引，这对范围查询更有效。此外，我们将 RangeCache 集成到基于LSM 的键值存储中，而不会干扰其他组件。使用范围缓存，我们可以消除 Compaction 操作对块缓存的影响，避免块缓存无效问题，并减少点/范围查询的磁盘 I/O。我们在 RocksDB 上实现了 Range Cache，并在不同的设置下，与 LevelDB、RocksDB、LSbM-tree 和 remixdb 进行了比较。实验结果表明，RangeCache 可以显著提高缓存效率和吞吐量，特别是对于范围查询。

Motivation

• Compaction 导致的缓存失效问题影响了缓存效率，从而影响查询性能。

• 现有的 LSM 可以很好处理长范围查询，但短范围查询表现不好，所以短范围查询是很多研究优化重点，但都没解决缓存失效问题。而解决缓存失效问题的方案大多采用了 rowcache，不能服务范围查询，而且在 block cache 和 row cache 之间的数据移动会带来额外开销。

Design

• 新的键值对缓存：RangeCache。可以同时服务点查和范围查
• 数据管理
• 跳表做有序索引，代替传统的 Hash。（作者解释不采用 tree 是因为频繁的分裂合并导致缓存性能差）
• LRU 管理数据淘汰：一个 LRU List 记录 Key 和 Vptr
• 点查缓存单个 entry，范围查就缓存多个 entry
• 数据结构中一个 next_key 如果为 1 则表示是一个范围查询的 cache entry，即该键和下一个键连续，中间再无其他键。如果是点查询的 cache entry，且没有直接插入到已有的 range cache entry 中，则为 0。

• 操作：
• 写操作会插入数据到 range cache，需要判断是否属于已有 range 来设置 next_key
• 读操作首先使用范围索引查询目标键，然后读取 value 并更新 LRU List
• PutRange：插入一个起始键 S 和一个键值对数组到 cache，键值对数组来源于对 LSM-tree 的范围查询
• 起始键 S 可能小于数组的第一个键，但是也记录该信息，S 即为 Guard 键，next_key 为 true
• 数组中逐条更新，如图 3 所示，当碰到 20 大于了 14 的时候，14 一定是个 Guard，此时把 14 添加到删除列表中，然后创建一个新的缓存项 p，并将其添加到 added_list 和 temp_list 中。然后后续的 23 24 都加到 added_list 中，删除 deleted_list 中的 14，然后使用 temp_list 更新 LRU List，added_list 都加到 range index
• GetRange：针对起始键执行 Seek，然后一路 Next，直到数据无效或者达到 scan length。访问到的数据加到 temp_list，最后用 temp_list 更新 LRU List
• Update：将 Cache 数据更新到最新。

• LRU 优化：批量更新 LRU，避免频繁的链表更新。

• Range Cache 的不足：无法像 block cache 那样利用存储的局部性。

Evaluations

LeaderKV: Improving Read Performance of KV Stores via Learned Index and Decoupled KV Table

Abstract

• 日志结构合并树(LSM-tree)是一种广泛应用于键值存储的存储体系结构。为了提高 LSM-tree 的读取效率，最近的研究利用 learned-index 来学习键和位置之间的映射关系。然而，在现有的学习索引辅助 KV 存储中，低效的学习索引设计和磁盘访问严重影响了读取性能。如何设计一种可学习的 KV 存储以提高索引效率和减少磁盘访问仍然是一个关键问题。本文提出了读优化的基于 LSM 树的 KV 存储 LeaderKV。LeaderKV 采用解耦 KV 表 (DKTable)和高效的学习索引进行数据检索。DKTables 是 LeaderKV 中的存储文件，因为它们避免在查询期间读取与学习索引无关的数据。提出了一种名为 Leader 的学习索引来加速 DKTable 内的数据检索。Leader 由精确模型和近似模型组成。重定向机制旨在减少 Leader 中错误预测的成本。我们将 DKTable 和 Leader 集成到 LeaderKV 中，并使用各种数据集和工作负载证明其有效性。实验结果表明，与代表性方案相比，LeaderKV 的读取性能得到了显著提高。

Motivation

• 低效索引导致的性能瓶颈。SeekKey 包括 Seek IB and DB，发现 RocksDB 和 Bourbon 各自占据 28% 和 48%
• Bourbon 的学习索引由一组线性模型组成，需要多次二分来定位目标模型。
• TridentKV 学习索引的预测粒度是数据块，需要在预测的数据块内多次二分。测试使用了 RocksDB 替代

• 盘上访问导致的性能瓶颈。加载不相关的数据增大盘读取开销。RocksDB 和 Bourbon 各自占据 54% 和 26%
• Bourbon 因为预测错误导致加载了大量数据块，性能降级
• TridentKV 加载整个预测的数据块，导致开销。

• 学习索引面临的挑战：
• LSM-tree 的键值对大小不固定，使得键到位置的映射变得复杂
• 读密集负载中，需要同时支持点查和范围查
• 如何设计学习索引以平衡查询效率、训练开销和空间占用

Design

• 使用 DKTable 代替 SSTable。DKTable 实现了 Table 级的 KV 分离。
• Key Area 和 Value Area 还是按照 Block 组织，作为最小写入单元。
• Value 存储信息 vinfo 记录了 value 的起始位置以及 value 大小，和 Key 关联存储
• 通过保证 key-vinfo 对定长来简化学习索引的设计（vinfo-8B，offset 和 size 各自占据 4B）
• DKTable 没有存储索引块，而是将学习索引存储到单独的索引文件。
• 解耦有助于学习索引的训练和持久化对于前台的影响。
• 读流程：1. 加载 meta 数据和索引文件中的学习索引；2. 学习索引计算键在键区的物理位置。（pos = F(key) × N，即根据 CDF 和数据个数 N 计算）；3. 根据计算的位置和键区的起始位置计算预测的键所在位置；4. 根据预测的偏移查询对应的 BF，如果显示不命中则终止查询，否则读取对应位置上的数据；5. 如果预测 Key 与读取的目标 Key 匹配则读取对应的 value。

• 混合模型学习索引 Leader 加速 DKTable 的查询，内部节点使用精确模型，叶子结点使用近似模型。在 Compaction 过程中收集 DKTable 中的新键，提交到后台学习队列来训练，将模型持久化到单独的索引文件
• Bucket：是一个存储了冲突模型节点的数组，即当多个模型被预测到了同个位置，则基于键范围升序存储。
• 每个 AM 节点是一个由斜率和截距组成的近似模型。AM nodes 使用分段线性回归 (PLR) 构建。预测位置与实际位置之间的差距在误差范围内。
• PM 模型是一个 entry 数组和 entry type 的 bit vector，在 node 构建之前训练。在构建过程中，PM 节点利用模型将子指针存储在预测条目处。

• 四种 Entry 类型：Node Pointer；Bucket Pointer；Duplicate Pointer；Null
• Node Pointer：指向一个 AM 节点，存储模型节点的地址
• Bucket Pointer：指向 Bucket，

• 学习索引 Leader 自下往上构建：PM 节点的模型基于从子节点中解析出的最小 keys 来训练。
• 首先收集节点 1-5 的最小键 key 1-5，形成一个有序的最小键序列。
• 随后，将 普通最小二乘(OLS) 回归 应用于该序列，训练 PM 节点的线性模型。

• 为了减小查询过程中因为预测误差导致的开销，提出一个重定向机制。即重复指针和重定向指针。
• 重复指针和重定向指针旨在将预测的位置重定向到正确的位置。
• 预测失败将直接获取重定向节点，如果 Key 不在重定向节点的范围中，表明 Key 不存在于索引中，查询终止
• 确保每个 PM 节点只会有一次线性计算，然后最多一次重定向找到子节点，从而减小预测失败开销
• 图 6b 展示了一个重定向机制，回归结果表明 key1 和 key2 预测在 p1 和 p2（向下取整），和实际的位置匹配。而最小 key3, key4, key5 预测到了位置 p2, p3, p4（向下取整），此时发现 key2 key3 预测到了同一个位置，那么 Node2 Node3 包含在了同一个 Bucket。
• 如果一个 key 落在了 key1 和 key2 之间，且离 key2 更近（即图 6b 中虚线表示的位置），那么这个 key 实际上需要搜索 Node1，但是根据回归结果却是 Node2。所以父节点在预测的位置的数据项中存储了一个额外的重定向到 Node1 的指针。（即需要在 PM Node2 中存储一个重定向指针指向 Node1）
• 图 5 中的灰色虚线表示重定向指针。对于 Node 或桶 类型的条目，它们存储子指针 (即节点指针和桶指针)和重定向指针。重定向指针指向 redirect child 节点。假设 prep 表示由前一个节点指针或桶指针索引的子节点。
• 如果 prep 是 AM 节点或 PM 节点，则重定向指针包含 prep 的地址
• 如果 prep 是桶，则重定向指针包含 prep 中最后一个模型节点的地址
• 重复指针是重定向指针的特殊类型。对于重复的项，它们最初没有子指针，因为在这些位置上没有最小键预测到这个位置。因此，重复条目将重定向指针存储为子指针。





• 根据这一原理，我们以图 5 中的根节点为例进行研究，其子指针和重定向指针如表 1 所示。
• 假设第二层的PM 节点从左到右依次为 PM node1、PM node2、PM node3。PM node1 的最小键值预测在第二个条目（Node Pointer），并且在 PM node1 之前没有模型节点。因此，第一个和第二个条目的重定向指针为空（因为前面没有无需重定向）。
• PM node2 和 PM node3 的最小键值都预测第四个条目中（重复位置，形成了 Bucket）。
• 因此，第三个条目将重定向指针存储为指向 PM node1 的子指针（因为只会落在前面的节点里）。
• 第四个条目还存储指向 PM node1 的 redirect pointer（因为可能第四个条目也可能预测失败）。
• 最后，第五个条目将重定向指针存储为子指针，指向桶中的最后一个模型节点，即 PM node3。

• 查询流程：查询根节点，然后获取第二层的节点 node，然后获取叶子节点 seg，最后线性模型预测位置
• Node 内查询过程：node 模型预测 entry 位置，获取对应 entry 的子指针。
• 如果键没有落在 child 的范围中 而且 child 是个 bucket，那么 bucket 内二分选择模型
• 如果键落在了 child 的范围中切 child 是个 node model，直接返回该 node
• 如果键不在 child 的范围内，使用预测项的重定向指针对应的 model node
• 如果键也在重定向的 node range 内，那表明不存在

• Node 构建过程：
• 首先解析出 children 中每个节点的最小键，使用 OLR 回归来训练一个线性回归模型。
• 然后算法使用模型计算每个键的存储位置
• 初始的 entry type 都设置为 NULL。
• 如果预测的 entry 类型是 null，则存储 model node 地址，标记为 node pointer 类型
• 如果多个模型节点映射到了同一个位置，那么 entry 索引的 child 更新为一个 bucket。然后按顺序存储多个 model 到 Bucket 中。
• 至此，如果没被标记为 node pointer，则都是 null type
• 如果 entry 类型是 node pointer 或者 bucket pointer，对应的 redirect pointer 设置为前一个 model node
• 如果条目的类型为空，则条目将重定向指针存储为子指针，并将其类型更新为节点指针(第22-23行)。最后，返回构造的模型节点

Evaluations

BushStore: Efficient B+Tree Group Indexing for LSM-Tree in Non-Volatile Memory

Abstract

• 非易失性内存(NVM) 提供低延迟、非易失性和字节寻址能力，使其成为一种非常有前途的数据库性能增强设备。目前的研究主要集中在利用 LSM-Tree 与 NVM 结合来减少写放大和缓解写停顿问题。然而，NVM 同时提高读写性能的综合潜力仍未得到充分开发。而且之前的 NVM 增强的 LSM-Tree 也忽略了 NVM 对小粒度随机读写的敏感性，我们认为这是进一步提高读写性能的关键。

• 为了解决这些问题，我们提出了 BushStore，这是一个创新的为 NVM 优化的 lsm-tree 变体。BushStore 采用三层架构设计，其中较高层的 BushStore 包含一组不可变的、非集群的 B 树，取代了传统的 SSTable。通过将非叶节点存储在 DRAM 中，而将叶节点存储在 NVM 中，并将数据页与索引分离，这些 B 树能够在各种读写操作中表现出出色的性能。我们的方法包括四项关键技术来显著提高系统效率：
• 首先，我们开发了新的数据结构，将读/写操作本地化到受限的 NVM 区域，提高了访问速度。
• 其次，我们优化了在刷新和 Compaction 阶段的键值数据处理，利用 B 树优越的扫描和顺序写入功能来加快写入和 Compaction 过程。
• 第三，我们动态调整 B 树的大小，实现平衡和优化的刷新和 Compaction 过程，从而提高整体写性能。
• 第四，我们实现了延迟删除 Cuckoo filtering 和延迟持久分配策略，以加快查询和 Compaction 过程。

• 评估表明，与最先进的 MioDB 系统相比，BushStore 在合成和实际工作负载下表现出高性能和可扩展性，并且实现了 3.3 倍随机写入吞吐量和 4.3 倍随机读取吞吐量的平均性能提升

Motivation

• 现有方案 NoveLSM 和 MioDB 虽然消除了序列化和反序列化开销，但是导致了在查询和 Compaction 过程中对于 NVM 的大量随机访问，导致读写放大。SLM-DB 和 FAST&FAIR 采用一个 B+Tree 索引来加速读，但是依然会在 flush 过程中产生大量的随机读写。所以本文目标是减小对于 NVM 的细粒度的随机访问

• 减少随机访问的思路是使用局部性（缓存利用率）更好的结构。然后对 LSM 减少层数导致单层变大，读复杂度变大，所以用 Cuckoo Filter 来加速；此外为了减小写放大尝试在 B+Tree 中用 KV 分离。

Design

• 层级结构：
• Memtable：只存储键和 value pointer，写入之前就 KV 分离到了 NVM 的数据页，同时作为 WAL
• L0-L1 采用 B+Tree 来组织，其叶子节点存储在 NVM 上，上层索引存储在 DRAM 中。L1 一整层是个 B+Tree
• NVM 同时管理 L0 和 L1 是为了同时支持只使用 NVM 的存储，两层才能做 Compaction 来平衡读写
• B+Tree 的叶子在 NVM 上持久化，包含一组 KP，指向对应的数据页，非叶子节点存储在 DRAM
• L0-L1 合并多个 L0 的 B+Trees 到 L1 的一个 B+Tree，只合并索引，不合并 pages
• L2 采用类似于 SST 的形式存储，放置在 L2 上
• 合并 L1 的 B+Tree 和 L2 的 SSTs，生成新的 SST，按 L1 B+Tree 划分键范围，并行执行

• Page 结构：内部键值分离减小写放大
• 索引页中：Index 存储在数据页中的位置，Pointer 存储对应数据页的起始地址
• 数据页中：Bitmap 表明对应的 value 是否有效，Compaction 过程中被 Clear，Nums 代表当前页面有效数据的个数，如果 Num 为 0 将删除该页。Next 用于数据恢复，Capacity 代表当前页中的原始个数，Offset 代表每个键值对在当前页的偏移

 

• Compaction：
• 只重写整个 L0 和相应 L1 范围之间重叠的数据。这只会重写索引页和部分数据页。该过程主要包括以下步骤
• 根据 L0 的 B+Tree 范围，从 L1 中选择相应的子树范围；如果整个 L1 范围都重叠，将选择整个 B+Tree
• 合并然后生成新的 B+Tree：合并生成新的索引页和中间节点，删除重复 value 并释放 Nums 为 0 的页；
• 组合且删除：如果老的 L1 B+Tree 是新生成的 B+Tree 范围的子集，将直接被新的树替代。如果新的 B+Tree 和老的 B+Tree 有很大的范围差距，那么只会选择第二步的 B+Tree 子树。子树将被删除替代。我们将执行范围替换操作，将对 L1 的 B+Tree 加一个写锁，把老的 B+Tree 和新的 B+Tree 合并，释放老的部分。
• 最后释放 L0 中的 B+Tree 和 L1 中遍历的数据。因为 L0 中的数据是一个只读的 B+Tree，所以在分配的时候我们可以明确知道精确的内存大小。因此在 Flush 时分配一整块内存，此时可以直接释放。
• 当总体空间利用率低于预定义的阈值时，将触发 GC。我们将 GC 过程集成到 Compaction 中，并采用基于轮询的回收模式。为了确保稳定性，每个 Compaction 周期只回收特定数量的数据页。此外，在随后的 Compaction 循环中，回收过程在先前停止的地方恢复。但是，当整个 NVM 的总体空间利用率超过阈值时，GC 将被暂时挂起。由于NVM 中有限的两级结构，回收确保指定范围内的值是有序的。这种方法增强了相应范围内范围查询的性能。

• 其他优化：
• L0 中 B+Tree 大小可变：L0 中的 B+Tree 个数和总大小显著影响 Compaction 时间。所以动态调整下一个刷回的 B+Tree 大小来平衡 Flush 和 Compaction 速度。如果 L0 的 B+Tree 大小较小，那么 Flush 比 Compaction 快，可能导致因 L0 填充满造成写停顿，引发性能下降。如果大小较大，Compaction 比 Flush 更快，Compaction 空闲，没有充分发挥盘带宽，影响写性能。假设最近写入的一个 Memtable 刷回的时间为 t0，而 Compaction 消费 K 个 B+Tree 的时间为 t1。如果 t1/t0 > K，意味着 Compaction 较慢，所以适当增大 Memtable，以调大 B+Tree。
• Cuckoo Filter 的惰性删除：当 flush 生成一个新的B树时，它会给 B+树分配一个增量ID。在 Compaction 过程中，L0 中会有一批 B+树被删除，最小的树 ID 会被更新，过滤器中任何低于这个最小树 ID 的数据都是过时的。如果查询到的值小于最小的树 ID，则表示查询的值不在 L0，可以跳过 L0 处的查询。延迟删除意味着在Compaction 过程中不修改过滤器中的 TreeID，只是在下一次写入时覆盖最小 TreeID 下面的槽。与布隆过滤器相比，Cuckoo 过滤器最多只需要读取一次。与 Cuckoo filter 相比，它减少了 Compaction 过程中的随机读写，提高了 BushStore 的写性能。
• 惰性分配持久化：当在 NVM 中分配和释放页面时，BushStore选择在恢复时遍历 B+ 树的页面来恢复 Bitmap 等元数据，而不是持久化修改后的元数据(例如 Bitmap)。由于在 Compaction 过程中会有大量的页面被分配和释放，惰性持久化可以显著减少页面分配的时间消耗，从而提高写性能。

Evaluations

Boosting Write Performance of KV Stores: An NVM-Enabled Storage Collaboration Approach

Abstract

• 日志结构合并树 (Log-Structured Merge Tree, LSM-tree) 是键值存储中最常用的数据结构，它可以消除随机写操作，并保持良好的读性能。但是，LSM-tree 的 Leveled Compaction 带来的写延迟和写放大会显著降低系统性能。新兴的非易失性内存(NVM)提供了字节可寻址访问和低延迟数据持久性。由于 NVM 的访问速度比硬盘驱动器或基于闪存的固态驱动器快几个数量级，因此在 LSM 树的设计中集成 DIMM 接口 NVM 可以潜在地缓解写 Stall 和写放大问题。应该仔细设计这种混合存储，需要新的体系结构和键值结构支持。

• 本文介绍了 ZigZagDB，一种支持 NVM 的数据管理方案，用于基于 LSM 树的键值存储。zigzagdb 增加了额外的键值存储层，并使用非易失性存储器作为存储介质来保存这些额外的数据层。新设计的键值存储交替地从 SSD 或 NVM 访问数据。这种锯齿形的存储协作和同步可以提高写效率和空间利用率。通过利用容量非常有限的 NVM，重新设计的 LSM 树组织可以有效地解决写延迟和写放大问题。我们使用一组广泛的实验来证明所提议的 ZigZagDB 的可行性。实验结果表明，与代表性方案相比，zigzagdb 可以显著降低写入放大，提高吞吐量

Motivation

• MatrixKV 通过细粒度 Compaction 缓解了写停顿，但是只是为 L0-L1 设计，没有考虑到其它层对写停顿的影响。作者做了下面这个实验来测试不同读写比例负载下每一层对写的贡献：
• （这个实验有点奇怪，只是在讲每一层对于写的贡献，没讲到和写停顿之间的联系）

• 写放大导致性能瓶颈（这个实验也很怪，尤其是图 b）

Design

• 组件：
• 内存组件不变，多了一个 Event Trigger Scheduler
• 记录 WSTable 的参数和访问状态，容量、键值对个数、访问次数，采用两个选择策略 NVM -> SSD：
• 容量感知的选择策略：NVM 中某一层总的 WSTable 大小超过阈值，选择部分 WSTable 迁移。选择时按照对于该层数据总大小的贡献以及读次数进行加权。使用 argmax 算子得到一个集合用于迁移。
• Read-Miss 感知的选择策略：考虑 WSTable 的 Read-miss 个数，以及键值对总个数。
• 盘上组件多了一个 Additional NVM Tree，所对应的每一层有 Writable Sorted Table，根据 NVM 容量和 AF 计算层数，AF 越小，每一层 WSTables 个数越少。
• 本质是一个持久性跳表，和传统跳表区别在于区分了数据区和映射区，利用字节寻址+偏移访问数据
• 在此基础上做读优化：布隆过滤器+索引跳表。BF 减少对于 NVM 的随机读，索引跳表本质是二级索引
• Additional NVM Tree
• WSTables 有两种：一种是键范围和 SSD 上的下一层完全一样的 Shadow WSTable；另一种是和 SSD 上的下一层完全不重叠的 Non-overlapped WSTable。当 WSTable 从 NVM 迁移到 SSD，确保最多只会和一个 SSTable 合并，从而控制每次迁移的开销。
• WSTable 的键范围在内存中维护

• 操作：
• ZigZag Data Migration：
• 分成两步，一个是从 SSD 迁移到 NVM 没有任何合并操作；一个是 NVM 迁移到 SSD 最多一次合并。减少了 Li 到 Li+1 的合并粒度。
• 通过在 NVM 中也维护 sorted run 来提升读性能：当 SSD 中 Level i 达到阈值，选择一个最早生成的 SST 执行迁移，从 NVM 中对应层中找到重叠的 WSTable，按顺序将数据插入到 WSTable。减小了传统的合并
• NVM 到 SSD：选择一个 WSTable 之后，触发 “Upto one merge” SST 生成算法。
• 读取 SSD Level 中的 SST 数据到内存；合并 WSTable 和 SST；刷回新的 SST。（Shadow WSTable）
• 读取 WSTable，然后转换成 SST，直接写回到 SSD Level （non-overlap WSTable）
• Updating WSTable：生成 WSTable 时确保属于上面两种类型，本质是做范围划分。

Evaluations

IndeXY: A Framework for Constructing Indexes Larger than Memory

Abstract

• 数据库系统中的索引可能会消耗大量内存。当索引变得太大而不能完全保存在内存中时，索引的选定部分必须卸载到二级存储中。在设计跨内存和磁盘的可扩展索引时，存在许多挑战。首先，索引的内存部分和磁盘部分的设计必须解耦，以便可以独立地为每个设备做出最佳选择。其次，必须仔细设计有选择地将内存部分卸载到磁盘，以最大化内存访问的机会，并产生最适合磁盘的 I/O 访问。第三，必须优化从磁盘重新加载索引并保留在内存中的策略，以获得最高的内存效率。

• 在本文中，我们提出了一个跨内存磁盘的索引设计，命名为 IndeXY，以有效地解决这些挑战。IndeXY 的区别在于，它是一个框架，允许单独采用内存索引设计和磁盘上的数据组织和访问方案，这被认为是对其工作负载最有效的。框架不是跨内存和磁盘的又一个通用索引，而是提供了精心设计的机制和策略，将选定的内存索引(index X)和磁盘索引(Index Y)集成到一个可扩展索引(Index XY)中。我们已经用可选的内存索引( ART树 或 B树) 和可选的磁盘索引(LSM 树或 B 树)实现了IndexXY。作为一个示例，实验表明，在框架中集成 ART tree 和 LSM 树可以导致 TPC-C 工作负载在使用内存和磁盘中的 B 树索引的 Leanstore 上的性能提高 8.6 倍，并且可以提高几乎所有 YCSB 工作负载下的性能

Motivation

• 索引对内存的消耗很大，尤其是小键值对。一旦内存耗尽，OS 开始换出页面，但是没有索引使用的内部知识，而且按照 page 粒度替换，其中冷热数据可能混合在一起，不是合适的迁移载体。而叶子节点或者子树可能更合适。为了实现高效的存储和访问，对索引有几个要求：
• 它们需要组织在一个高度可访问的结构中。作为反例，它们在磁盘上作为日志文件的存储是不可接受的，因为它不支持直接访问。这意味着应该在更复杂的数据结构(如树变体)中对这两个位置的索引节点进行索引。
• 节点可以高效地 assembled 和 disassembled，从而在两个位置的索引之间移动。效率经常受到访问模式和存储粒度的影响。虽然节点可以在字节可寻址内存中灵活组织，但它们必须组装到块中(例如 4KB)，然后卸载 disassembled 到磁盘。当频繁访问(又称热)节点没有连续地放在内存索引上时，它们可能会被组装 assembled 到不同的块中，从而导致效率的损失。当节点从磁盘加载到内存索引中时，也会出现类似的问题。因此，为了获得更高的性能和更好的兼容性，当前的做法是必须共同设计索引的内存和磁盘结构。
• 第三，存在许多仅为内存或磁盘设计的高性能传统索引。新的、更有效的内存和磁盘数据索引不断出现。因为内存和磁盘具有非常不同的访问特性，所以不可能有同时适合这两个设备的索引设计。理想的设计是为内存和磁盘分别采用适合设备及其工作负载的最佳索引。

• 本文的目标是提供一个名为 IndeXY 的框架，支持跨内存和磁盘开发可扩展索引。它可以有效地解决上述问题。首先，它允许将一个选定的现有内存索引(Index X)和一个选定的现有磁盘上索引(Index Y)集成到一个索引结构中。IndeXY 可以从为其目标设备设计并为目标工作负载选择的每个组件索引中获益。其次，它以可适应的粒度在键空间中提供了高效的热度监控功能。第三，它根据内存可用性自动从磁盘卸载/加载 unloading/loading 索引节点

Design

• Index Pre-Cleaning：周期性 pre-cleaning 操作。它识别索引中的脏数据，然后在 unloading 之前将它们写回磁盘，希望将来的 unloading 操作可以简单地丢弃(几乎)完全干净的子树。具体细节涉及到一些状态转换和加锁。

• Selection of Subtrees for Release：当 IndexX 大小达到高水位，激活对应的 memory release 线程来选择子树进行驱逐。Pre-Cleaning 线程利用了写操作的局部性，release 线程则是利用读局部性来识别最近最少被访问的子树。同时也需要考虑子树的大小，提出了访问密度的概念，以及一个基于密度的节点排名算法。

• Moving Data between Indexes X and Y：于写缓冲区，预清理操作试图避免清理正在密集写入的子树。对一个键的重复更新可以被写入缓冲区吸收。对于读缓存，框架将从索引 Y 加载的键直接插入到索引 X。空间局部性对处理块设备的性能也至关重要。框架保留了用索引 Y 设计的写缓存和读缓存，以利用局部性。但是，它们的大小被配置为最小(例如，几兆字节)。

Evaluation

拓展链接