Abstract

• 我们的大量实验表明，现有的键值存储 (KVSs) 以巨大的内存占用为代价实现了高性能，而这通常是不切实际或不可接受的。即使使用新兴的超快速字节可寻址持久内存 (PM)， KVS 也远远不能提供 PM 优越的 I/O 带宽所承诺的高性能。为了找到根本原因并弥合巨大的性能/内存占用差距，我们重新审视了两种代表性索引机制 (单阶段和多阶段) 的体系结构特征，并提出了一种称为 FluidKV 的三阶段 KVS。FluidKV 通过快速无缝地将传入的键值请求流从写并发前端阶段运行到跨中间阶段的内存高效后端阶段，有效地整合了这些索引。FluidKV 还设计了重要的启用 enabling 技术，如线程独占日志记录、PM 友好的 KV-block 结构和双粒度索引，以充分利用超高速存储硬件的并行处理和高带宽功能，同时减少开销。我们实现了一个 FluidKV 原型，并在各种工作负载下对其进行了评估。结果表明，FluidKV 优于最先进的 PM-aware KV，包括具有不同索引的 ListDB 和 FlatStore，在写入和读取吞吐量方面分别高出 9x 和 3.9x，同时减少了高达 90% 的 DRAM 占用。

Introduction

• 作者提出了一个分类方法：单阶段索引 KVS 和多阶段索引 KVS
• 单阶段是指有个专门的索引来索引所有的键值对，可能在内存中也可能是内存存储混合。
• 多阶段则是动态和周期性地把写入的键值对从一个小的内存集合迁移到大的盘上集合，每一个都有自己的索引

• 现有的基于 PM 的 KVS 不管是单阶段还是多阶段，在不严重依赖于巨大的DRAM容量的情况下，远远达不到超高速存储(例如PM)所承诺的高性能，正如我们在 2 中深入的实验分析所阐述的那样，并通过以下 5 个关键观察结果进行总结。
1. 只在 DRAM 中维护的单阶段索引表现出很好的并发和读写性能
2. 但这是以很高的 DRAM 开销为代价的，很难扩展到更大的数据量
3. 多阶段索引比如 LSM，只为少量的无需数据构建比较小的粗粒度的索引让内存开销可控
4. 但是也引入了被人诟病的写停顿和读写放大，因为多个阶段之间的 Compaction。即便有一些针对 PM 的优化，但是由于写入并发性有限，这种多阶段索引的读写性能仍然远远低于内存的单阶段索引
5. 单阶段和多阶段索引都没有充分利用 PM 带宽。

• 本文的核心思想就是组合单阶段索引的高并发 + 多阶段索引的可控内存开销，快速高效地从前合并到后。该方案由三个阶段组成：FastStore, BufferStore, StableStore。
• FastStore 采用了一个并发的键粒度的索引，以及线程独立的日志，从而快速吸收前台的写入但是无序，实现高写性能
• BufferStore 动态刷回 FastStore 数据到一组持久化的且有序的 KV 数据集，并且将其归并排序到后端的 StableStore，从而及时控制内存开销；
• StableStore 存储了一个全局的键范围粒度的索引，从而最小化内存开销的同时保证读性能。

• 本文提出了一个 PM 友好的索引结构和数据块结构。

Background and Analysis

Key-value Store Indexing

单阶段索引

• 单级索引 KVS 维护一个单一的 KV 粒度索引，以精确地记录每个 KV 在持久数据中的位置，如图 1a 所示。包括范围索引和哈希索引；
• 大部分针对快速存储设计的索引结构，比如 KVell，在内存中维护了整个索引来避免索引成为瓶颈，FlatStore 则是在 PM 上构建一个高效的多日志结构并且采用一个易失索引；

• 图 2 证明了观察 1，只在 DRAM 中维护的单阶段索引表现出很好的并发和读写性能

• 图 3 证明了观察 2，单阶段索引 KVS 的内存占用随着数据集大小呈陡坡线性增长
• 虽然在可字节寻址的 PM 中容纳全部或部分 KVS 索引[35,36,41]可以减少DRAM消耗，但由于两个原因，它会带来非常明显的性能下降的高成本。
• 首先，它会导致索引更新和 KV 数据访问之间的 I/O 争用。
• 其次，对 PM 的小 I/O 访问比对 DRAM 的低效得多 [54,56]。如图 2 所示，Flatstore with Fast&Fair B+-tree，FF 是一个基于 PM 的持久化 B+Tree
• 图 3 还显示 FFTree 用读/写性能换取内存占用，内存占用仍然与数据大小成正比。
• 总而言之，给定单阶段索引 KVS 的性能由其索引结构主导，它需要在性能和 DRAM 占用之间取得谨慎的平衡，以适应不断增长的数据量

多阶段索引

• 如图 1b 所示，阶段 0 由一个名为 memtable 的内存索引和一个持久的预写日志(WAL)组成，用于通过顺序 I/O 快速持久化用户写操作。其他阶段使用小的粗粒度持久索引(例如，每个4KB块的索引项)存储排序的 KV。后台线程异步地、周期性地将一个阶段中的 KV 合并到下一个阶段，并更新持久索引。

• 我们测量了 RocksDB 在不同数据量下的 DRAM 占用。如图 3 所示，它的 DRAM 消耗始终在1GB以内，并且主要来自 memtable。因此，我们得出
• 观察 3 (OB3)的结论: 多阶段索引 KVS 可以将 DRAM 占用从数据量中解耦。

• LSM-tree 的另一个问题是读写放大，ListDB 尝试使用持久性跳表来替代原本的有序结构，因此通过只修改指针来避免数据的重写拷贝；如下测试表明
• 观察 4：多阶段 KVS 的读写性能表现一般，不如单阶段 KVS，写并发十分有限。

• 写并发受限的原因：日志和索引的同步开销；读写放大之间的冲突。

快速存储上的索引

• 如图 5 测试了不同 KVS 加载 3G KVS 数据的带宽，单线程使用的读写带宽不足 1GB/s 和 0.2G/s，即便是 32 线程，写带宽也只花了 30%，读带宽 70%。其中 FFTree 和 ListDB 因为构建了持久化的索引所以用了更多的带宽，而 Masstree 则是纯内存索引，RocksDB 并行度差，所以 PM 带宽利用不够充分。得到了结论 5
• 观察 5：对于无论是单阶段还是多阶段索引，PM 带宽都不是瓶颈。

动机

• 目标 1：好的写扩展性。需要高效索引来减小因为多线程竞争导致的开销。

• 目标 2：可控内存开销；避免随着数据量增长无限制的内存开销，需要高效索引来存储大部分键值对的索引在 PM 中，减小实际的 DRAM 开销；

• 目标 3：低读延迟；LSM-tree 的读延迟由查询索引和 PM 访问组成，因为 PM 延迟是 DRAM 的五倍，所以需要减少 PM 访问。

Design

Overview

• FastStore 维护一个 KV 粒度的易失范围索引，同时包含了多个线程独立的日志。

• StableStore 使用 PM 上的数据块和索引节点有序存储，数据块和索引节点都是 PM 友好的。最终维护一个读友好的索引结构，DRAM 开销低，保证查询性能

• BufferStore 是介于 FastStore 和 StableStore 之间的可调节阶段，实现了 FluidKV 的无缝流动。它将 FastStore 的 KV 粒度索引转换为较小的 SortedBlock 粒度索引，以快速减少内存开销，同时将这些排序块索引合并到 StableStore 中以减少读取放大

FastStore

• 小且定长的 value 存双份 PM 和索引都存，类似于 LSM 的 Memtable 和 WAL，避免查询 PM 太慢。变长使用 KV 分离，索引存的是 PM 地址。

• 日志记录包含一个有效标志位，表明是否删除，31bit 的 LSN 记录写入顺序，所有记录按照 64B 对齐。小于 32B 的记录会被打包。

• 索引采用了一个全内存的范围索引，因为 PM 访问的延迟太大，很容易成为瓶颈。同时要求高并发和高范围查询，所以需要细粒度锁或者乐观并发控制。

• 线程独立的日志：为每个用户线程分配一个日志来消除 I/O 争用，从而充分利用 PM 带宽。

• 粗粒度分配器：粗粒度的 PM 分配器来为每个线程分配和回收日志空间，将 PM 分区成多个固定大小的 chunk 4M，并且为每个 chunk 维护分配状态。单独为每个线程分配可用的 PM chunk，避免多线程写争用。

StableStore

• 期望以较低的内存开销实现好的读性能。易失索引 B+Tree 和持久化的有序块，小规模的上层 B 树提供了足够的并行性，大规模的排序块有效地减少了具有数据局部性的上层索引的内存占用。同时，StableStore 根据 I/O 亲和性调整持久块的大小，进一步优化读性能。

• 逻辑有序表：易失的 B+tree 为逻辑有序表 LST 构建索引，每个 LST 由一个索引块和多个数据块组成，每个数据块存储一组经过排序的 KV，索引块中索引项的键和值分别是其索引数据块的最小键和数据块的地址。当启用键值分离功能时，数据块中每个键的值是指向相应 PM-log 记录的指针。索引块末尾的空条目用块中最后一个有效条目填充，以方便二分搜索(对于数据块也是如此)。存储在每个 LST 中的最大 KV 数是索引块中的条目数与数据块中的条目数的乘积。例如，如果我们使用 512 字节大小的块，即一个块存储 32 个条目(8+8字节)。然后StableStore 的易失性索引的 DRAM 消耗减少到像 FastStore 这样的 KV 粒度索引的 1/1024

• I/O 友好的 PM 块：正如 2.2.1 中提到的，虽然大多数持久索引利用 PM 的字节可寻址性来执行细粒度(例如，8 字节指针)访问，但 StableStore 选择 512 字节作为索引和数据块的大小，因为 PM 的 I/O 亲和力。如表 1 所示，在 I/O 大小为 64B 到 512B 的范围内，PM 的随机访问延迟大致保持不变，然后随着 I/O 大小的增加而显著上升，这是由于 PM 内部有 256byte 的XPBuffer[23,50]。因此，在查询 StableStore 的索引时，在关键路径上最多需要两次具有最小读延迟的 PM 访问

• 除了稳定的读取延迟和低内存占用外，StableStore 的混合结构还简化了崩溃恢复。StableStore 不需要重建一个巨大的 KV 粒度索引，只需要恢复 volatile B -tree，其中 LST 元数据持久化在 Manifest 中(详见5.5)，而 LST 持久化存储在 PM 上，不需要恢复。

BufferStore: Dynamic Data Migration

• FastStore 和 StableStore 之间的 BufferStore 负责将 KV 数据从内存密集型的 FastStore 无缝快速迁移到内存高效的 StableStore，使 FluidKV 能够同时实现高并发写入、稳定读取延迟和低内存占用的优势。

• 在 BufferStore 中，键值数据由与 StableStore 结构相同的多个缓冲树索引。当 FastStore 达到其容量(由内存约束决定)时，volatile 索引将被转换为缓冲树，以便通过刷新操作快速释放内存资源。然后，当缓冲树的数量达到一定阈值时，通过 Compaction 操作对一个或多个缓冲树进行排序并合并到 StableStore 中，这是一个耗时的过程。Flush 和 Compaction 的详细工作流程见 5.4。flush 和 compaction 操作是并发执行的，不会阻塞用户请求的前端处理，充分利用多核 CPU 的并行性和超高速存储来加速数据从 FastStore 到 StableStore 的流动。

• 动态负载感知：BufferStore 不像 LSM-tree 那样将 KV 数据分布在多个级别，数据容量呈指数级增长，这有助于减少写放大，而是在运行时采用不同的数据迁移策略，以适应工作负载的动态变化。FluidKV 通过分析来自用户线程的请求来计算工作负载的读/写比率(R:W)。如图 10 所示，在读取密集型工作负载(例如，R:W > 1)， FluidKV 更积极地触发刷新和合并，以减少索引的数量，从而减轻读取放大。BufferStore 中的任何缓冲树都将通过合并(即 threshold=1) 机会性地合并到 StableStore 中。此外，在只读工作负载下，FluidKV 甚至忽略 FastStore 容量的阈值，以触发将 FastStore 数据合并到后期阶段的刷新。相反，在写密集型工作负载下，FluidKV 暂时在 BufferStore 中容忍更多的缓冲树以提高写性能，并在缓冲树数量达到较高阈值 (例如 4) 时触发压缩。这是因为合并的写放大是由 BufferStore 和 StableStore 的容量比决定的。因此，增加 BufferStore 容量可以减少写放大，但代价是读放大。综上所述，FluidKV通过调整其三个阶段的相对空间和处理能力来动态平衡读写性能。

实现

索引

• 基于 Masstree 的修改，析构函数中修改实现了快速地内存回收。因为 FluidKV 在 Flush 和 Compaction 中频繁删除整个索引。

• 同时也测试了 Bw-tree，一个无锁的 B+tree，以及测试了 HOT，一个并发的 trie，但是没使用。Bwtree 在读写性能方面都比 Masstree 差，HOT 的读性能最好但是写性能和 scan 性能稍差。但是，由于它在删除操作期间不回收内存，因此对于由于 Compaction 而频繁删除索引项的 StableStore 来说，它的效率不高。

写

• 首先，LSN 由全局增量计数器(第2行)生成，用于在崩溃恢复期间区分多个单线程日志中日志记录的全局顺序。由于共享单个全局计数器会导致并发用户线程的大量同步开销，因此每个Put 请求通过散列其键来使用多个 (例如，256个) 单独计数器中的一个。因此，同一键的日志记录顺序仍然可以通过 LSN 来区分。其次，FluidKV 用键值对和 LSN 构建一个日志记录，并将其持久化到每线程日志(第 3 行)。最后，使用日志记录地址和 LSN 作为值更新易失性索引(第4行)。

• 由于日志写入和索引更新没有被锁定，因此对同一键的多线程更新可能导致索引中的值与最新日志中的值不一致。为了在不添加低效率的粗粒度锁的情况下解决这个问题，我们在 mastree 的写操作中添加了一个验证机制。mastree 的写入过程包括首先搜索需要更新的目标节点，然后锁定该节点(第 7 行)并更新它(第 13 行)，最后解锁它(第14行)。当mastree在第一步中找到目标键时，提议的验证将读取目标键的值以获得其 LSN，并将其与要写入的记录的 LSN 进行比较。如果值较新，则不会更新节点并返回(第8~12行)。这种验证适用于大多数并发索引，因为它们的更新过程相似，而且在索引中不存在目标键时不会产生开销。因此，FastStore 确保了 volatile 索引和持久日志之间的一致性，同时保证了高并发性下的线性性。

读

• 在 get 操作中(如算法2所示)，用户线程可以依次访问活动的 FastStore、正在刷新的不可变的 FastStore、BufferStore 中的缓冲树(从最新的到最旧的)和 StableStore。在 FastStore 中，目标键的存在只能通过索引来确定。在缓冲树或 StableStore 中，FluidKV 首先扫描内存索引中的 LST，然后检查目标键是否在 LST 中。只有在某个阶段找到目标键才能完成搜索。此时，如果找到的键是有效的，FluidKV 读取其对应值的地址以返回值数据;如果无效，则 FluidKV 通知该密钥不存在

• FluidKV的扫描操作以类似于合并的方式实现，即在目标键范围的所有阶段上迭代具有优先级队列的最小元素。在当前的实现中，我们使用 LSN 和 seq_no (在5.5中引入) 作为时间戳，为扫描构建一致的快照。过时的刷新和压缩索引删除步骤被推迟，以保留正在扫描的快照。

Flush and Compaction

• 为了避免刷新和前端写入之间的争用，FluidKV 允许在刷新操作期间同时使用两个 FastStore (不可变的 Flatstore 用于刷新，活动的 FlatStore 用于写入)。FluidKV 首先创建一个新的活动FastStore 结构，包括易失性索引和线程独占日志，用于后续写操作(第2~4行)。后台 Flush 线程通过修改指示活动 FastStore 的全局原子信号量来切换 FastStore。用户线程在每次写入前检查信号量，以获取要写入的索引和 PM 日志。在等待超时(例如100毫秒)之后，Flush 线程扫描不可变 FastStore 的索引，以获取其所有 KV 数据以生成 LST 并构建一个新的相应的缓冲树。最后，当缓冲树准备好并可以被用户线程读取时，FluidKV 删除旧 FastStore 的索引以释放其占用的内存空间。启用键值分离后，PM 日志将继续存储可变长度的值。

• 压实操作包括三个连续的步骤，即选择压实、运行压实和清除压实。
• 在选择压缩步骤(第19~22行)中，FluidKV 首先扫描所有缓冲树以读取其关联 lst 的元数据，然后扫描 StableStore 索引以确定与 BufferStore 的 lst 有重叠键范围的 lst。
• 然后在运行压缩步骤(第24~25行)中，FluidKV将所有输入的 lst 合并到新的 lst 中，并构建相应的元数据。具体来说，在我们的实现中，我们使用优先级队列作为最小堆来执行合并排序。值得一提的是，当 FluidKV 在 merge-sorting 步骤中发现 lst 与其他输入 lst 没有重叠时，不需要修改 lst，直接插入 StableStore 中，以减少写放大[49]。由于当 StableStore 变大时，压缩的效率将低于 flush，因此我们采用并行压缩机制来充分利用 PM 带宽和 CPU 核来加速压缩。FluidKV 根据键范围对输入 lst 进行分区，并为每个分区分配一个线程以并行执行合并排序。在我们的原型中，分区的默认数目是 8。
• 最后，清理压缩步骤(第27~33行)首先将输出 LST 在 Manifest 中持久化后插入到 StableStore 索引中，然后从 StabeStore 中删除过时的 LST 数据和元数据，最后删除 BufferStore 并释放其 DRAM/PM 空间。因为我们使用并发 B 树(例如，masstree)作为 StableStore 索引，所以索引更新过程也不需要锁定

测试