1. 论文基本信息

1.1. 标题

AnyKey: A Key-Value SSD for All Workload Types (AnyKey: 一种适用于所有工作负载类型的键值对固态硬盘)

1.2. 作者

• Chanyoung Park (汉阳大学)
• Jungho Lee (汉阳大学)
• Chun-Yi Liu (美光科技公司)
• Kyungtae Kang (汉阳大学)
• Mahmut Taylan Kandemir (宾夕法尼亚州立大学)
• Wonil Choi (汉阳大学) - 通讯作者

1.3. 发表期刊/会议

未明确提供，但从 ACM Reference Format 和提供的 CCS Concepts、Keywords 推断为 ACM 旗下的会议或期刊。

1.4. 发表年份

2025年 (根据 Published at (UTC): 2025-02-06T00:00:00.000Z 判断)

1.5. 摘要

键值对固态硬盘 (Key-Value Solid-State Drives, KV-SSDs) 被认为是大型 键值存储 (Key-Value, KV) 应用程序 的潜在存储解决方案。然而，现有的 KV-SSD 设计通常只针对特定类型的工作负载进行优化，即那些 值 (values) 的大小远大于 键 (keys) 的工作负载。有趣的是，在实际应用中也存在另一种 键 (keys) 大小相对较大的工作负载类型。

本文重新评估了当前 KV-SSD 设计在这些未被充分探索的工作负载下的性能，并发现它们的性能显著下降。通过观察到性能问题源于 元数据 (metadata) 大小的增加，本文提出了一种新颖的 KV-SSD 设计，名为 AnyKey。AnyKey 的核心思想是防止 元数据 大小在 键 大小变化时无限制地增长。

通过对各种真实工作负载的详细评估，结果表明 AnyKey 在不同类型、不同 键 和 值 大小的工作负载下，均优于 最先进的 (state-of-the-art) KV-SSD 设计。

1.6. 原文链接

/files/papers/6916de05110b75dcc59adfbc/paper.pdf (该链接指向论文的 PDF 文件，状态为已发布。)

2. 整体概括

2.1. 研究背景与动机

• 核心问题: 传统的 块存储 (block-based) 固态硬盘 (SSDs) 在处理 键值存储 (KV store) 应用时，需要复杂的软件栈，导致 延迟 (latency) 高、主机 (host) 系统 CPU 和内存开销大。为了解决这些问题，键值对固态硬盘 (KV-SSDs) 应运而生，它将 KV存储 功能直接集成到 SSD 设备内部，旨在提供更低的 延迟、更好的可伸缩性以及更高效的 SSD 管理。

• 当前挑战与空白: 尽管 KV-SSDs 潜力巨大，但其普及和商业化应用仍面临挑战，主要原因是其性能通常仍落后于依赖 主机 丰富资源的 主机 (host-based) KV存储。现有 KV-SSD 设计，特别是主流的基于 日志结构合并树 (LSM-tree) 的设计（例如 PinK），主要针对 高值键比 (high value-to-key ratio, high-v/k) 的工作负载进行优化，即 值 (value) 远大于 键 (key) 的场景。这些设计在 键 相对较小的假设下，能够将 元数据 (metadata) 保存在 设备内部动态随机存取存储器 (device-internal DRAM) 中，从而实现高性能。

• 未探索的工作负载: 然而，在实际应用中，存在大量 低值键比 (low value-to-key ratio, low-v/k) 的工作负载，其中 键 (key) 的大小相对较大。例如，社交图 (social graph) 的 对象元数据 (object metadata) 或 去重引擎 (deduplication engine) 的 数据库 (DB) 等。这些 low-v/k 工作负载的特性导致 元数据 的总大小急剧增加，超出了 SSD 内部 DRAM 的容量限制，迫使 元数据 溢出到速度较慢的 闪存 (flash) 中。一旦 元数据 需要从 闪存 读取，每次 键值对 查找都会产生额外的 闪存访问 (flash accesses)，导致 尾延迟 (tail latency) 显著增加和 输入输出操作每秒 (IOPS) 急剧下降。

• 论文切入点与创新思路: 论文的切入点正是揭示现有 KV-SSD 设计在 low-v/k 工作负载下的性能瓶颈，并提出一种通用设计来解决这个问题。其创新思路在于重新设计 KV-SSD 的 元数据 管理机制，使其在 键 大小变化时，元数据 大小不会无限增长，确保 元数据 能够始终驻留在 DRAM 中，从而提升所有类型工作负载下的性能。

2.2. 核心贡献/主要发现

本文的主要贡献体现在以下几个方面：

1. 揭示 低值键比 (low-v/k) 工作负载的挑战: 首次全面揭示了一系列真实世界中 低值键比 的 键值对 (KV) 工作负载，并发现现有 KV-SSD 设计（以 PinK 为代表）在这种工作负载下性能显著下降。这些性能退化主要是由于 元数据 大小随着 键 相对大小的增加而急剧膨胀，无法完全驻留在 SSD 内部 DRAM 中，导致额外的 闪存访问。

2. 提出 AnyKey 设计优化 low-v/k 工作负载: 针对 low-v/k 工作负载的性能问题，提出了名为 AnyKey 的新型 KV-SSD 设计。AnyKey 的核心思想是最小化 元数据 的大小，使其能够适应 SSD 内部 DRAM。这通过以下方式实现：

   • 将 KV对 以排序组的形式存储在 数据段组 (data segment group) 中，元数据 只需为每个组而非每个 KV对 维护一个 键。
   • 引入 哈希列表 (hash lists) 作为新的 元数据 类型，在 DRAM 中存储键的哈希值，从而在实际读取 闪存 页面之前快速检查 键值对 是否存在。
   • 通过这些优化，AnyKey 在 low-v/k 工作负载下，95th百分位尾延迟 (95th percentile tail latencies) 平均提升 56%，输入输出操作每秒 (IOPS) 提升 299%，并且显著延长了设备寿命。

3. 提出 $AnyKey+$ 增强版以支持所有工作负载: 进一步提出了 AnyKey 的增强版本 $AnyKey+$，通过改进 日志触发压缩 (log-triggered compaction) 机制，避免了在 高值键比 (high-v/k) 工作负载下可能出现的 压缩链 (compaction chain) 问题，从而提高了 日志结构合并树 (LSM-tree) 的管理效率。

   • $AnyKey+$ 能够为 high-v/k 工作负载提供显著的 IOPS 提升，平均比 PinK 高 15%。
   • 综合来看，$AnyKey+$ 在所有类型的工作负载下（无论是 low-v/k 还是 high-v/k）都优于 最先进的 (state-of-the-art) 设计 PinK，实现了对 low-v/k 工作负载 315% 的 IOPS 提升和对 high-v/k 工作负载 15% 的 IOPS 提升，展现了其普适性。

3. 预备知识与相关工作

3.1. 基础概念

• 键值对固态硬盘 (Key-Value Solid-State Drives, KV-SSDs)：一种新型的 固态硬盘 (SSD) 设备，它将 键值存储 (Key-Value store, KV store) 的功能直接集成到 SSD 内部，允许应用程序直接向设备发出 键值对 请求。与传统的 块设备 (block device) SSD 相比，KV-SSDs 旨在简化软件栈、降低 主机 (host) 系统开销、提高 吞吐量 (throughput) 和 设备寿命 (device lifetime)。

• 键值存储 (Key-Value store, KV store)：一种非关系型数据库，其中数据以 键 (key) 和 值 (value) 的形式存储。每个 键 都是唯一的，并用于检索关联的 值。KV store 广泛应用于大型分布式系统和 云服务 (cloud services) 中。

• 日志结构合并树 (Log-Structured Merge-tree, LSM-tree)：一种为 写密集 (write-intensive) 工作负载优化的磁盘数据结构。它的核心思想是所有写入操作都是 非原地更新 (out-of-place update)，即新的数据总是写入到新的位置。LSM-tree 将数据组织成多个层级（Level），从内存中的 C0 (MemTable) 开始，数据会周期性地刷写到磁盘上的 L1 层，然后通过 压缩 (compaction) 操作将数据从较低层级合并到较高层级，从而保持数据排序并删除旧版本数据，减少 写放大 (write amplification)。

• 元数据 (Metadata)：关于数据的数据。在 KV-SSD 中，元数据 主要指用于定位 闪存 (flash) 中 键值对 物理位置的信息，例如 键 及其对应的 物理页面地址 (Physical Page Address, PPA)。元数据 通常存储在 SSD 内部的 动态随机存取存储器 (DRAM) 中以加快访问速度。

• 尾延迟 (Tail Latency)：衡量系统响应时间分布高端的性能指标，例如 95th百分位延迟 (95th percentile latency) 或 99th百分位延迟 (99th percentile latency)。它表示 95% 或 99% 的请求在规定时间内完成。尾延迟 对于许多交互式应用程序至关重要，因为它直接影响用户体验。

• 输入输出操作每秒 (IOPS)：每秒可以完成的输入/输出操作（读取或写入）的数量。它是衡量存储设备性能的关键指标，反映了设备处理请求的能力。

• 写放大 (Write Amplification, WA)：在 固态硬盘 (SSD) 中，由于 闪存 (flash) 的 擦除 (erase) 单元 (块 (block)) 大于 写入 (write) 单元 (页 (page))，以及 LSM-tree 等数据结构的 压缩 (compaction) 操作，实际写入 闪存 的数据量可能远大于 主机 (host) 发出的逻辑写入数据量。写放大 会缩短 SSD 的 设备寿命 并降低性能。

• 垃圾回收 (Garbage Collection, GC)：固态硬盘 (SSD) 为了回收包含 无效数据 (invalid data) 的 块 (block) 而执行的内部操作。闪存 (flash) 无法 原地更新 (in-place update)，当数据被修改或删除时，旧的数据会变成 无效数据。GC 会将 有效数据 (valid data) 从 受害者块 (victim block) 移动到新的 块，然后 擦除 整个 受害者块。

• 压缩 (Compaction)：在 LSM-tree 中，压缩 是将数据从一个或多个层级读取，合并排序，并写入到下一个层级的过程。它旨在维持 LSM-tree 的结构、删除重复或 无效数据、并释放空间。

3.2. 前人工作

论文在 KV存储 (KV store) 的执行模型和 KV-SSD 的设计方面介绍了相关工作。

3.2.1. KV存储 的三种执行模型

KV存储 在目标系统中有三种不同的托管模型，取决于存储的使用方式：

1. 主机 (Host) + 块设备 (Block device)： (如 Figure 3(a) 所示)

   • 描述: 这是最传统的模型，KV存储 软件（如 RocksDB [22] 和 LevelDB [27]）运行在 主机 系统中，并通过标准的 块输入输出 (block I/O) 接口访问一个或多个传统 块设备 固态硬盘 (SSDs)。
   • 优点: 不需要对系统进行任何修改，兼容性好。
   • 缺点: 性能受限于复杂的 软件栈 (software stack)，每次访问底层存储都需要经过 操作系统内核 (OS kernel) 和 文件系统 (file system) 等层级，导致 延迟 (latency) 高。
   • 相关工作: 许多工作 [7, 11, 18-20, 44, 46-49, 61] 致力于通过优化 主机 端的 KV存储 软件来提高性能。另一些工作 [12, 16, 23, 35, 37, 54, 56, 60] 引入了 字节可寻址持久内存 (byte-addressable persistent memory) 来减少 块输入输出 (block I/O) 流量。

2. 主机 + SSD 支持： (如 Figure 3(b) 所示)

   • 描述: 为了解决传统模型中 软件栈 笨重以及将 SSD 视为“黑盒”的问题，这种模型尝试利用 SSD 独特的特性或内部结构/行为来提升性能。
   • 优点: 允许 主机 软件更深入地与 SSD 交互，例如利用 SSD 内部的并行性或 事务持久性 (transactional persistence)。
   • 缺点: 仍然需要 主机 端一定程度的软件参与，且对 SSD 接口有特定要求。
   • 相关工作: 例如，有研究定义了新的 SSD 接口以利用 设备内部并行性 (device-internal parallelism) 或 闪存 (flash) 命令的 事务持久性 [50]。另有工作针对 开放通道 SSD (Open-Channel SSD) 修改 内核驱动 (kernel driver) 以优化 缓存 (caching) 和 调度 (scheduling) 机制 [63]。

3. 键值对固态硬盘 (KV-SSD)： (如 Figure 3(c) 所示)

   • 描述: 最新的方法是将整个 KV存储 引擎直接集成到 SSD 设备本身，由 SSD 自身管理 KV存储。

   • 优点: 相比前两种方法，它能提供更高的性能、更好的可伸缩性和更高效的设备管理 [4, 36, 38]。应用程序可以直接向 KV-SSD 发出 键值对 (KV pair) 请求，无需经过复杂的 软件栈。

   • 缺点: SSD 内部资源（如 CPU、DRAM）有限，需要精巧的设计来克服这些限制。

   • 相关工作: 存在各种具有不同内部结构、行为和接口的 KV-SSD 设计 [8, 13, 24, 30-32, 36, 43, 51, 64]。本文提出的 AnyKey 就属于这一类。

     下图（原文 Figure 3）对比了三种 KV存储 执行模型，并展示了 KV-SSD 的内部架构：

     该图像是一个柱状图，展示了不同工作负载下的页面写入总数。各个工作负载的页面写入数量（以百万计）通过三种不同的设计（Pink、AnyKey 和 AnyKey+）进行比较，显示出在转换条件下 AnyKey 的优势。

3.2.2. 现有 KV-SSD 设计

KV-SSD 的硬件架构与传统 块存储 SSD 相同（如 Figure 3(d) 所示），包括 闪存芯片 (flash chips)、块 (blocks)（擦除 (erase) 单元）和 页 (pages)（读/写 (read/write) 单元）。KV对 (KV pairs) 直接存储在 页 中，因此 KV-SSD 需要 元数据 (metadata) 来定位目标 KV对，这些 元数据 通常保存在 设备内部动态随机存取存储器 (device-internal DRAM) 中。管理 元数据 的数据结构主要有 哈希表 (hash tables) 和 日志结构合并树 (LSM-trees)。

1. 基于 哈希表 的 KV-SSD：

   • 描述: KV-SSD 早期设计主要基于 哈希表 [8, 24, 32, 36, 64]，因其简单性而受到青睐。
   • 问题:
     • 原地更新 (in-place update) 机制: 哈希表 的 原地更新 会在写入时产生 局部页更新 (partial page updates)，频繁触发 垃圾回收 (GC) 操作，从而浪费 带宽 (bandwidth) 和 设备寿命 (device lifetime)。
     • 哈希冲突 (hash collision): 为了将 哈希表 放入有限的 DRAM，需要减小其大小，但这会增加 哈希冲突 的频率，导致 读取 (read) 操作时 尾延迟 (tail latencies) 增加。
   • 局限性: 其他排序索引结构，如 B树 (B-trees) [15] 和 学习索引 (learned indexes) [18, 40]，也可能不适用，因为它们也需要 原地更新，在 写密集 (write-heavy) 工作负载下会导致 SSD 的设备管理问题。

2. 基于 LSM-tree 的 KV-SSD：

   • 描述: LSM-tree 因其 闪存友好 (flash-friendly) 的 非原地更新 (out-of-place update) 机制而日益流行。它通过多级索引结构来确保有界的 尾延迟。
   • 优势: 避免了 原地更新 带来的 GC 问题，更适合 SSD 特性。
   • 当前主流: 近期提出的 KV-SSD 设计都基于 LSM-tree [13, 30, 31, 43, 51]，本文提出的 AnyKey 也采用了 LSM-tree。

3.2.3. PinK 的结构和操作

论文选择 PinK [30, 31] 作为 最先进的 (state-of-the-art) LSM-tree-based KV-SSD 的代表进行重新评估和比较。尽管 PinK 是为通用 KV-SSD 设计的，但其核心设计理念与其他当代 LSM-tree-based KV-SSDs 相似。

KV-SSD 的内部结构与通用 LSM-tree-based KV store 有所不同。通用 LSM-tree 将 KV对 (KV pairs) 排序并维护在 排序字符串表 (Sorted String Tables, SSTables) 文件中。而 KV-SSD 中，文件物理上分散在 闪存 (flash) 中，需要新的数据结构来协同功能，类似 SSTables。

下图（原文 Figure 4）展示了 PinK 的内部结构以及如何定位目标 KV对：

PinK 的内部结构:

• 数据段 (Data segment)： 实际的 KV对 存储在 闪存 中，并作为 数据段 进行管理。简单来说，每个 闪存页 (flash page) 可以是一个 数据段，其中包含多个 KV对。
• 元段 (Meta segment)： 一个 元段 可以适应一个 闪存页，它维护着排序的 键 (keys) 以及指向相应 KV对 的物理 闪存地址 (Physical Flash Address, PPA)。由于 DRAM 容量有限，PinK 将 LSM-tree 上层（如 L1, L2）的 元段 保存在 设备内部动态随机存取存储器 (device-internal DRAM) 中，而下层（如 L3 到 Ln）的 元段 则存储在 闪存页 (flash pages) 中。
• 层级列表 (Level list)： 每个 元段 都有一个对应的 层级列表 条目，其中包含该 元段 的第一个（或最小的）键 以及 元段 的位置（DRAM 地址或 闪存地址）。这些 层级列表 条目被分组到多个层级 $L_1$ 到 $L_n$，每个 层级列表 内的条目都是排序的。

PinK 的操作流程:

• 定位 KV对（读取 (read) 操作）： 如 Figure 4 所示，以键 “PP” 为例。

  1. 给定 键，首先从 $L_1$ 开始，依次搜索 层级列表。如果当前 层级列表 中未找到，则检查下一个 层级列表。
  2. 一旦找到 “PP” 可能落入的 层级列表 条目，其对应的 元段 会被读取到 DRAM 地址 0x10。
  3. 然而，“PP” 可能不存在于该 元段 中，因为 层级列表 的 键 范围可能跨不同层级重叠。在这种情况下，会搜索下一个层级。
  4. 如果在 $L_2$ 中找到另一个 层级列表 条目，并且其对应的 DRAM 地址 0x20 中的 元段 确实包含 “PP”，则可以获取目标 KV对 所在 数据段 的位置。
  5. 最后，从 闪存地址 901 读取 数据段，并提取目标 值。

• 更新现有 键 或添加新 键（写入 (write) 操作）：

  1. 写入请求 (write request) 首先缓冲在 设备内部动态随机存取存储器 (device-internal DRAM) 中。
  2. 当 缓冲区 (buffer) 满时，其中的 KV对 会被合并到 $L_1$ 中（即 L0-L1 压缩）。
  3. 这个创建新 $L_1$ 的过程包括为相应 键 在 DRAM 中生成新的 层级列表 条目和 元段，同时 值 被写入到 闪存 中的 数据段。简而言之，每个 写入请求 首先从 缓冲区 立即响应，然后成为 LSM-tree 的一部分。

3.3. 技术演进与差异化分析

3.3.1. 技术演进

KV存储 技术从最初在 主机 (host) 系统上运行并使用传统 块设备 (block-based) 固态硬盘 (SSDs) 发展而来。这种传统方式通过标准 I/O 栈 (I/O stack) 导致性能瓶颈。为了解决此问题，研究者们尝试利用 SSD 内部特性或提供新的 SSD 接口来优化 KV存储，但 主机 端仍需承担部分管理职责。

最终，KV-SSD 概念应运而生，将 KV存储 功能直接移入 SSD 设备内部，实现了 KV存储 与底层 闪存 (flash) 的深度融合。在 KV-SSD 内部数据结构的选择上，经历了从早期基于 哈希表 (hash tables) 的简单设计到如今主流的基于 日志结构合并树 (LSM-trees) 的演进。LSM-trees 因其 非原地更新 (out-of-place update) 特性，天然地对 闪存 友好，能有效减少 写放大 (write amplification)，并提供可控的 尾延迟 (tail latencies)。PinK 就是 LSM-tree 在 KV-SSD 领域的一个 最先进 (state-of-the-art) 实现。

3.3.2. 差异化分析

AnyKey 与 PinK 等现有 LSM-tree-based KV-SSD 设计的核心区别在于它们对 元数据 (metadata) 的处理方式以及对不同工作负载的适应性：

• 元数据 粒度和存储位置:

  • PinK (及现有设计): 元数据（主要是 元段 (meta segments)）中包含每个 键值对 (KV pair) 的完整 键 (key) 信息，以及指向其在 闪存 (flash) 中 数据段 (data segment) 的指针。在 高值键比 (high-v/k) 工作负载（键 小）下，这些 元数据 可以完全驻留在 设备内部动态随机存取存储器 (device-internal DRAM) 中。然而，在 低值键比 (low-v/k) 工作负载（键 相对大）下，元数据 的总大小会急剧膨胀，超出 DRAM 容量，导致部分 元段 被迫存储在 闪存 中。这使得 读取 (read) 请求需要额外的 闪存访问 来获取 元数据，从而显著增加 尾延迟。
  • AnyKey: 采取“以组为单位”的 元数据 管理策略。它将多个 KV对 排序并组织成 数据段组 (data segment group)。DRAM 中的 层级列表 (level list) 条目只存储每个 数据段组 的最小 键、数据段组 的起始 物理页面地址 (PPA) 以及每个页面内第一个 键 的 哈希值 (hash values) 列表。通过这种方式，AnyKey 显著减少了 元数据 的总体大小，确保其能够完全驻留在 DRAM 中，即使在 low-v/k 工作负载下也是如此。此外，AnyKey 还引入了 哈希列表 (hash lists) 来在 闪存 访问前进行快速存在性检查，进一步减少不必要的 闪存 读取。

• 值 (value) 的管理:

  • PinK: KV对 的 键 和 值 通常存储在一起，或者 元数据 直接指向包含 键 和 值 的 数据段。在 LSM-tree 压缩 (compaction) 过程中，如果 KV对 需要移动，则整个 值 也必须被读取和重写，尤其是在 值 很大的情况下，会消耗大量 带宽 (bandwidth) 和 设备寿命。
  • AnyKey: 为了提高 LSM-tree 管理效率，AnyKey 引入了 值日志 (value log)。它将 值 与 键 分离存储。新的 KV对 的 值 首先写入 值日志。数据段组 中的 KV实体 (KV entity) 可能只存储指向 值日志 中 值 位置的指针，而不是 值 本身。这使得 压缩 过程主要处理 键 和 元数据 的移动，而大部分 值 可以原地不动，显著减少了 闪存 写入量。

• 压缩链 (compaction chain) 的处理:

  • AnyKey (基础版): 尽管 AnyKey 优化了 元数据 和 值 的管理，但在某些 高值键比 或 值 相对较大的 low-v/k 工作负载下，日志触发压缩 (log-triggered compaction) 仍可能导致大量 值 被合并到 数据段组 中，从而触发 目标层级 (destination level) 达到阈值，进而引发连续的 树触发压缩 (tree-triggered compaction)，形成 压缩链，影响性能。

  • $AnyKey+$ (增强版): $AnyKey+$ 通过修改 日志触发压缩 机制来解决 压缩链 问题。它在 压缩 过程中监控目标层级的大小。一旦目标层级达到某个阈值，剩余的 值 将被写回 值日志，而不是强制合并到 数据段组 中，从而避免 压缩链 的产生。此外，$AnyKey+$ 在选择 日志触发压缩 的 源层级 (source level) 时，会优先选择包含最多 无效值 (invalid values) 的层级，进一步提高 值日志 的空间回收效率。

    通过这些关键差异，AnyKey 能够有效解决 现有KV-SSD 在 low-v/k 工作负载下的性能瓶颈，而 $AnyKey+$ 则通过优化 LSM-tree 的管理效率，使其成为一个在所有 KV 工作负载类型下都表现优异的通用 KV-SSD 解决方案。

4. 方法论

4.1. 方法原理

AnyKey 的核心方法原理是：针对现有 KV-SSD 设计在 低值键比 (low-v/k) 工作负载下 元数据 (metadata) 大小急剧膨胀，导致 尾延迟 (tail latency) 增加和 输入输出操作每秒 (IOPS) 下降的问题，通过最小化 元数据 的粒度，并将 值 (value) 从 键 (key) 中分离，从而确保 元数据 能够完全驻留在 设备内部动态随机存取存储器 (device-internal DRAM) 中，并优化 日志结构合并树 (LSM-tree) 的管理效率，最终实现对所有工作负载类型的通用高性能支持。

其直觉是，如果 键 很大，那么为每个 键值对 (KV pair) 存储完整 键 的 元数据 会很快耗尽 DRAM。但如果将 KV对 分组，并只为每个组存储少量 元数据（例如，组的起始 键 和一些 哈希值 (hash values)），就可以显著减少 DRAM 的需求。同时，将 值 分离到单独的 值日志 (value log) 中，可以避免在 LSM-tree 压缩 (compaction) 过程中频繁移动大 值，从而节省 闪存 (flash) 带宽和延长 设备寿命 (device lifetime)。

4.2. 核心方法详解

4.2.1. 重新评估当前设计 (PinK) 的结构性限制

本文首先重新评估了 最先进的 (state-of-the-art) LSM-tree-based KV-SSD 设计 PinK [30]，特别是在 低值键比 (low-v/k) 工作负载下的行为，从而揭示了其结构性限制。

PinK 的内部结构如 Figure 4 所示，它将实际的 KV对 存储在 数据段 (data segments) 中，而它们的 键 (keys) 和指向 KV对 的指针则排序后存储在 元段 (meta segments) 和 层级列表 (level lists) 中。这些 元数据 结构主要保存在 设备内部动态随机存取存储器 (device-internal DRAM) 中。

作者通过假设一个 64GB SSD 包含 64MB DRAM 并已填满 KV对 的情况，分析了 PinK 在不同工作负载下的行为。下图（原文 Figure 5）展示了 PinK 在 高值键比 (high-v/k) 和 低值键比 (low-v/k) 工作负载下的对比行为：

该图像是图表，展示了在不同 DRAM 大小下的读延迟的累积分布函数（CDF）。图中包含三种不同负载的比较，分别是 Crypto1、ETC 和 W-Pink，横轴为延迟（ms），纵轴为 CDF。各负载使用不同的 DRAM 大小（32MB、64MB、96MB）进行标识，提供了延迟性能的直观对比。

从 Figure 5 中可以观察到两种截然不同的行为：

• 在 高值键比 (high-v/k) 工作负载下 (Figure 5a): 由于 键 的大小很小，层级列表 和 元段（包含 键）的总体大小非常小，大部分可以驻留在 DRAM 中。因此，定位 键 大部分可以在 DRAM 内部完成，每个请求的 闪存访问 (flash accesses) 次数被限制在最多 3 次 (Figure 5b)。

• 在 低值键比 (low-v/k) 工作负载下 (Figure 5a): 随着 值键比 (value-to-key ratio) 的降低（即 键 的相对大小增加），层级列表 和 元段 的累计大小显著增加。由于 DRAM 容量固定，它们无法完全容纳在 DRAM 中，部分 元数据 必须存储在 闪存 中。

  • 对于 值键比 相对较高的 low-v/k 工作负载（例如 UDB, ETC, Xbox），只有 元段 被存储在 闪存 中。这可能导致每次 读取 (read) 请求需要额外的一两次 闪存访问 来获取这些 元段 以定位 KV对。

  • 对于 值键比 相对较低的 low-v/k 工作负载（例如 Crypto1, ZippyDB, Cache15），除了整个 元段 外，一些 层级列表 也被存储在 闪存 中。在这种情况下，搜索请求的 键 将涉及多次额外的 闪存读取 来获取 闪存 中的 层级列表，这会严重损害整体性能。

    这些观察表明，现有 LSM-tree-based KV-SSD 设计在 low-v/k 工作负载下的性能瓶颈在于 元数据 大小随着 键 的相对增大而迅速膨胀，超出了 DRAM 容量，导致频繁的 闪存访问。

4.2.2. AnyKey 设计原则与整体结构

为了解决上述问题，AnyKey 提出了以下设计原则和相应的结构。下图（原文 Figure 6）展示了 AnyKey 的内部结构：

该图像是图表，显示了在不同工作负载下，Crypto1、ETC 和 W-Pink 三种情形下的读取延迟的累积分布函数（CDF）。图中包含了4KB、8KB和16KB三种页面大小的延迟比较，横坐标为延迟（毫秒），纵坐标为CDF值。不同颜色和线型表示不同的页面大小。

4.2.2.1. 最小化 元数据 大小

为了减少 元数据 (metadata) 的大小，AnyKey 建议以组的形式管理 KV对 (KV pairs)，其中 KV对 自身是排序的。传统的 KV-SSD 设计要求每个 KV对 都有自己的 元数据 来直接定位它。而 AnyKey 的方法是，如果许多 KV对 被排序并作为一个组进行管理，那么组内的目标 KV对 就可以仅使用组的 元数据 来定位。

• 数据段组 (Data segment group) (在 闪存 中):

  • 概念: AnyKey 将多个 闪存页 (flash pages) 组合成一个 数据段组，其中存储的多个 KV对 是排序的。这样做可以显著减少 元数据 的总大小，因为它只需要为每个 数据段组 而非每个 KV对 维护 元数据。
  • 定位机制: 由于每个组内的 KV对 是排序的，因此仍然可以使用组的 元数据 来定位目标 KV对。AnyKey 当前的实现中，将一个 闪存块 (flash block) 内相邻的物理页组合成一个 数据段组。由于一个 块 内的 物理页面地址 (PPAs) 是连续的，因此只需知道组中第一个页面的 PPA 就可以访问 数据段组 内的任何 闪存页。
  • 组内 KV对 定位: 一旦确定了目标 数据段组，高效定位存储目标 KV对 的 闪存页 至关重要，否则可能需要读取 数据段组 中的所有 闪存页。
    • 挑战: 如果简单地在组 元数据 中保留每个 闪存页 的第一个 键 (key)，当 键 较大时（即在 low-v/k 工作负载下），元数据 大小会再次显著增加。
    • 解决方案：哈希值 (hash values) 排序: AnyKey 引入了 小尺寸哈希值 (small-sized hash values) 来表示 大尺寸键，并使用这些 哈希值 对 数据段组 内的 KV对 进行排序。
    • KV实体 (KV entity) 结构: 每个 数据段组 中的 KV对 以 {(i) 键, (ii) 键的哈希值, (iii) 值} 的形式存储，称之为 KV实体。
      • 对于 (ii) 哈希值：分析表明，使用 32位哈希值 (32-bit hash values) 足以在包含数千个 KV对 的 数据段组 中唯一标识 键。与基于 哈希 的 KV-SSD 不同，AnyKey 中需要维护在 DRAM 中的 哈希值 数量非常少。
      • 对于 (iii) 值：KV实体 中可以直接存储 值，或者，如果 值 存储在单独的 值日志 (value log) 中，则存储一个指向 值 所在 值日志 位置的 PPA。
    • 哈希冲突位 (Hash collision bits): 如果 数据段组 中不同的 键 偶然具有相同的 哈希值，这些 KV实体 将连续存储。为了处理这种情况，AnyKey 为每个 闪存页 预留 2位，称为 哈希冲突位。如果需要读取下一页才能找到具有相同 哈希值 的 KV实体，则设置为 01；如果需要读取上一页，则设置为 10。论文分析指出，这种情况发生率仅为 0.075%，对整体性能影响可忽略。
  • 当前实现细节: 当前实现将 32个 8KB 闪存页 组合成一个 数据段组，可容纳 100-5,000个 KV对。数据段组 的大小选择平衡了 元数据 减少量和潜在的 哈希冲突 带来的额外读取。

• 层级列表 (Level lists) (在 DRAM 中):

  • 概念: AnyKey 也使用 层级列表 来容纳组 元数据。每个 层级列表 条目被重新设计以包含对应 数据段组 的 元数据。
  • 层级列表 条目结构 (在 DRAM 中): {(i) 最小键, (ii) 第一页的PPA, (iii) 页面中第一个键的哈希值列表}。
    • (i) 最小键 (smallest key)：用于在 层级列表 中识别目标 数据段组，因为 层级列表 条目在每个层级都是排序的。
    • (ii) 第一页的PPA (PPA of the first page)：一旦目标 数据段组 被识别，可以使用此 PPA 访问组内的所有 闪存页。
    • (iii) 页面中第一个键的哈希值列表 (list of the hash values of the first keys in the pages)：由于 数据段组 中的所有 KV对 都根据 键 的 哈希值 进行排序，通过在 哈希值列表 中搜索目标 键 的 哈希值，可以轻松找到目标 闪存页。
  • 当前实现细节: 为了进一步减少 层级列表 条目的大小，当前实现只使用 哈希值 的前 16位 (Hash[0:15])。

4.2.2.2. 进一步减少 闪存访问

上述 数据段组 和 层级列表 的组合可能仍需额外的 闪存访问。原因在于：(i) 层级列表 仅提供 键 的范围；(ii) 键 的范围可能跨不同层级重叠，即使 键 落入某个 层级列表 条目，对应的 数据段组 也可能不包含目标 KV对。这个问题也存在于其他 LSM-tree-based 设计中。AnyKey 引入了一个机制来检查目标 KV对 是否确实存在于一个 数据段组 中。

• 哈希列表 (Hash lists) (在 DRAM 中):
  • 概念: AnyKey 在 LSM-tree 中引入了一种新的 元数据 类型，称为 哈希列表。每个 层级列表 条目都有一个 哈希列表，其中维护了实际存在于对应 数据段组 中的所有 键 的 哈希值。
  • 作用: 如果目标 键 的 哈希值 未在 哈希列表 中找到，则表明目标 KV对 不存在于该 数据段组 中，从而继续在下一个 层级列表 中搜索，避免了不必要的 闪存读取。
  • 存储与优先级: 哈希列表 利用剩余的 DRAM 空间来存储。如果 DRAM 空间不足，则不对较低层级的 层级列表 维护 哈希列表。在这种情况下，AnyKey 也无法避免额外的 闪存访问。然而，由于 AnyKey 将大量 KV对 分组，显著减少了 层级列表 元数据 的大小，因此在可用 DRAM 空间中引入 哈希列表 可以进一步提升性能。
  • 实现细节: 当前实现使用整数数组作为 哈希列表，并采用 二分查找 (binary search) 来搜索 哈希值。论文指出，使用 Bloom Filter 或 Cuckoo Filter 虽然可以节省 DRAM 空间，但生成这些 过滤器 (filters) 需要密集的计算，对 SSD 内部资源造成显著负担，因此 PinK [31] 也未采用此类 过滤器。

4.2.2.3. 提高 LSM-tree 管理效率

上述 AnyKey 设计虽然可以改善 读取延迟 (read latency)，但也可能增加 LSM-tree 管理的开销。具体来说，由于 层级列表 直接指示存储 键 和 值 的 数据段组，在 压缩 (compaction) 过程中，如果 KV对 需要移动，则目标 数据段组 中所有 KV对 的 值 都将被读取和写入，从而大量浪费 设备带宽 (device bandwidth) 和 设备寿命 (device lifetime)。

• 值日志 (Value log) (在 闪存 中):
  • 概念: 为了防止在 压缩 过程中移动 数据段组 中的所有 值，AnyKey 将 值 从 数据段组 中分离出来，并单独管理。为此，AnyKey 引入了一个新的数据结构，称为 值日志，它位于 闪存 的一个单独区域中，专门用于存储 值。
  • 存储策略: AnyKey 中的 闪存 空间被划分为两个区域：一个用于 数据段组，另一个用于 值日志。每个 KV对 的 值 可以存储在这两个区域之一：要么直接在 数据段组 的 KV实体 (KV entity) 中，要么在 值日志 中。在后一种情况下，KV实体 将包含一个指向 值日志 中 值 存储位置的指针。
  • 写入流程: 最初，所有 写入 (writes) 操作的 值 都被写入 值日志。随后，其中一些 值 会被合并到 数据段组 中，以确保 值日志 有可用空间继续服务新的写入。
  • 值 迁移: 值 从 值日志 移动到 数据段组 的过程在 压缩 过程中执行（详见 4.2.3.2 压缩 部分）。
  • 值日志 大小: AnyKey 将 SSD 剩余容量的一半用于 值日志 区域。这是因为 LSM-tree 会随着新的 KV对 加入而增长。即使 值日志 中所有 值 都属于新 KV对，AnyKey 仍然可以利用另一半剩余容量将它们合并到 数据段组 中。如果 SSD 容量已满，AnyKey 可以利用 预留空间 (over-provisioned, OP) 容量的一半作为 值日志。论文分析指出，即使是小的 值日志 仍然有益，因为 OP 通常用于容纳更新的 值。

4.2.3. 详细操作

4.2.3.1. 读取 (Read) 操作

给定一个 键 (key) 请求，AnyKey 使用 层级列表 (level lists) 和 哈希列表 (hash lists) 来查找目标 数据段组 (data segment group)，进而找到其中的 KV实体 (KV entity) 和目标 值 (value)。如果 KV实体 存储的是目标 值 的位置信息，AnyKey 则从 值日志 (value log) 中读取 值。

以下是 Figure 6 中读取 键 “PP”（其 哈希值 为 “4791”）的示例：

1. AnyKey 从 $L_1$ 到 $L_n$ 依次搜索 层级列表。
2. 如果在某个 层级列表 中检测到一个 条目 (entry)，键 “PP” 落入其 键 范围，AnyKey 会检查 “PP” 的 哈希值 (“4791”) 是否存在于对应的 哈希列表 中。
3. 如果 哈希值 未找到，则表明目标 KV实体 不存在于该 层级列表 条目所指示的 数据段组 中，AnyKey 会继续在下一个层级搜索。
4. 如果另一个 层级列表 条目被选为候选，并且其 哈希值 也在对应的 哈希列表 中找到，那么目标 数据段组 就被识别。
5. 在组内的 闪存页 (flash pages) 中，PPA 300 中的第一页被选中并读取，因为 哈希值 的前 16位 (“47”) 介于 层级列表 条目中前两个 16位哈希值 (“12” 和 “66”) 之间。
6. 如果目标 KV实体 直接包含 值，则读取完成。
7. 否则，从 KV实体 中提取 值 的实际位置，并从 值日志 中读取该页面（PPA 901）。

4.2.3.2. 写入 (Write) 操作

与大多数 KV-SSD 设计 [13, 30, 31, 43, 51] 类似，写入请求 (write request)（对现有 键 的更新或新添加的 键）首先缓冲在 设备内部动态随机存取存储器 (device-internal DRAM) 中。当 缓冲区 (buffer) 满时，其中的 KV对 (KV pairs) 会合并到 L1 层（即 L0-L1 压缩 (compaction)）。具体来说，新的 数据段组 (data segment groups) 和 L1 的 层级列表 (level list) 条目被构建（所有 值 (values) 被写入 值日志 (value log)）。简单来说，加入 LSM-tree 的新 值 都写入 值日志。

4.2.3.3. 压缩 (Compaction) 操作

与传统的 LSM-tree-based KV-SSD 采用的 压缩 过程相似，AnyKey 中的 $L_{n-1}$ 到 $L_n$ 压缩 也包括：(i) 读取来自两个层级的所有 KV对，(ii) 根据 键 对它们进行排序，以及 (iii) 顺序地构建新的 数据段组 和 $L_n$ 的对应 层级列表 条目。然而，AnyKey 的 压缩 过程具有两个显著特点：

1. 在 (i) 阶段（即读取目标层级的 KV对 时），每个 KV对 的 值 都从其当前存储位置读取，这可以是 数据段组 或 值日志。

2. 在 (iii) 阶段（即创建每个 数据段组 并写入 闪存 (flash) 时），KV实体 (KV entities) 会根据 键 的 哈希值 (hash values) 再次排序。

   压缩 操作在以下两种情况下触发：(i) 当一个层级的大小超过其阈值时（称为 树触发压缩 (tree-triggered compaction)），以及 (ii) 当 值日志 变满时（称为 日志触发压缩 (log-triggered compaction)）。下图（原文 Figure 8）展示了 AnyKey 中采用的 压缩 操作：

   该图像是图表，展示了在不同 heta 值下，AnyKey、AnyKey+ 和 PinK 的延迟分布曲线（CDF）。从图中可以看出，随着 heta 值的变化，AnyKey 的延迟表现优于其他方案。

• 树触发压缩 (Tree-triggered compaction):

  • 当 LSM-tree 的 $L_n-1$ 层（即其 数据段组 和 值日志 中引用的 值 的总大小）达到其阈值时，会触发一个 $L_{n-1}$ 到 $L_n$ 的 压缩。这是维护 LSM-tree 非原地更新 (out-of-place update) 机制所需的常规 压缩 操作。

• 日志触发压缩 (Log-triggered compaction):

  • AnyKey 还会为确保 值日志 中的可用空间而触发 压缩。当 值日志 变满时，会选择一个目标（源）层级 $L_{n-1}$，并触发一个 $L_{n-1}$ 到 $L_n$ 的 压缩。
  • 在 压缩 过程中，$L_n-1$ 和 $L_n$ 中 值日志 内的所有 值 都将被重新定位到新创建的 $L_n$ 的 数据段组 中，从而在 值日志 中创建可用空间。
  • 对于目标层级 $L_{n-1}$，AnyKey 会选择 值日志 中其 值 大小最大的层级，因为这样做在回收 值日志 的空闲空间方面最有利。

• 哈希列表 更新: 值得注意的是，当两种类型的 压缩 操作都被触发且 层级列表 被修改时，AnyKey 会检查可用的 DRAM 空间并相应地更新顶层 哈希列表。由于 压缩 操作涉及大量的 闪存读取 和 写入，在 DRAM 中更新 哈希列表 只会产生很小的开销，并且可以有效地隐藏。

4.2.3.4. 垃圾回收 (GC) 操作

传统 垃圾回收 (GC) 操作会重新定位 受害者块 (victim block) 中所有 有效数据 (valid data)（以 页 (page) 为单位），然后擦除该 块。而在 AnyKey 中，GC 操作的特点是：(i) 它重新定位 受害者块 中每个 数据段组（以多个 页 为单位），并且在 组 重新定位后，(ii) 其新的 物理页面地址 (PPA) 会在对应的 层级列表 (level list) 条目中更新。

根据观察，AnyKey 中的大多数 受害者块 不包含任何 有效数据，因此 GC 操作可以直接擦除它们，无需耗时的 有效数据 重新定位过程，从而使得整体 GC 开销非常低。这是因为一个层级的 数据段组 往往存储在同一个 块 中，并且这些 块 中的 组 在 压缩 (compaction) 操作（两种类型）期间会一起重新定位。此外，值日志 (value log) 中不会触发 GC 操作，因为 值日志 中 闪存块 的回收在 日志触发压缩 (log-triggered compaction) 期间执行。

4.2.3.5. 范围查询 (Range query) 操作

由于 KV对 (KV pairs) 在每个 数据段组 (data segment group) 内部是根据其 哈希值 (hash values) 排序的，因此对于 范围查询，如果需要根据 键 (keys) 重新排序，将需要大量的计算。为了解决这个问题，AnyKey 维护额外的定位信息 {目标页 (target page), 页偏移量 (page offset)} 来定位 数据段组 中的每个 KV对。这些信息根据 键 进行排序，并存储在 数据段组 的第一个页面中。利用这些信息，范围查询 请求的 KV对 可以快速定位，无需任何排序过程。

值得强调的是，随着 范围查询 长度的增加，AnyKey 的 范围查询 性能会提高。这是因为 范围查询 的性能取决于需要读取的 闪存页 (flash pages) 数量，而 AnyKey 对于较长的 范围查询 需要读取的页数更少。具体来说，范围查询 请求的 KV对 存储在 数据段组 的 闪存页 中是聚簇的，因此读取它们只需访问少数 闪存页。相比之下，在 PinK 中，尽管 键 和指向其 值 (values) 的指针在 元段 (meta segments) 中是排序的，但 数据段 中的相应 KV对 却分散在不同的 闪存页 中。因此，PinK 中的 范围查询 需要读取大量的 闪存页。对于小型 范围查询，AnyKey 也能表现出与 PinK 相当的性能，因为它可以直接使用存储在第一个页面中的位置信息来定位目标 KV对，而无需对 KV对 进行排序。

4.2.4. 元数据 大小分析

本文对 元数据 (metadata) 的大小进行了定量分析，以了解 AnyKey 相对于 PinK 能减少多少。下表（原文 Table 1）比较了 PinK 和 AnyKey 在不同 值键比 (value-to-key ratios) 下的 元数据 数据结构大小，假设 64GB SSD 已填满 KV对：

观察结果:

• 当 值键比 相对较低时，AnyKey 中 元数据 的总大小远小于 PinK。
• 这是因为 AnyKey 中 层级列表 的大小显著减小，并且其 哈希列表 仅使用剩余的 DRAM 空间生成，将两个数据结构的总大小限制在 DRAM 容量内。
• 因此，即使 值键比 极度下降，AnyKey 也能阻止 元数据 总大小的增加。 AnyKey 减少 元数据 大小的关键机制是为多个 KV对 组成的 组（即 数据段组）生成 元数据。

4.2.5. 设计开销

4.2.5.1. 存储容量开销 (Storage Capacity Overhead)

在 AnyKey 中，数据段组 (data segment group) 中的每个 KV实体 (KV entity) 包含其 键 (key) 的 32位哈希值 (32-bit hash value)。如果一个 64GB SSD 中有 一千万 (ten million) KV对 (KV pairs)，那么这些 32位哈希值 的总大小为 38MB，仅占整个 SSD 容量的 0.05%。此外，每个 数据段组 需要维护组内所有 KV对 的位置信息（即 {目标页 (target page), 页偏移量 (page offset)}）以实现快速 范围查询 (range query) 处理。假设一个包含 32个 8KB 页 的组中有 1,000个 KV对，这些信息的总大小为 2KB，不到整个 组 大小的 1%。

这种集体开销相对于 PinK 来说极小。在 PinK 中，如果 元段 (meta segments) 无法容纳在 DRAM 中，它可能需要在 闪存 (flash) 中存储每个 键 的两个不同副本（一个来自 元段，另一个来自 数据段），从而导致更高的存储开销。

4.2.5.2. 计算开销 (Computation Overhead)

在 KV-SSD 设计中采用 哈希值 (hash values) 会引入相关的计算任务：

1. 哈希值 生成: 当 KV对 首次写入 日志结构合并树 (LSM-tree) 时，以及在给定 读取请求 (read request) 时，AnyKey 需要为 键 生成 32位哈希值。在当前实现中，采用了 xxHash [14] 算法。在 1.2 GHz ARM Cortex-A53 核心（现代 SSD 中常用的计算资源 [5]）上，从一个 40字节键 生成 32位哈希值 需要 79纳秒 (79ns)。与典型的 闪存读取 或 写入延迟 相比，这是一个边际开销。

2. KV实体 排序: 在 压缩 (compaction) 过程中构建 数据段组 时，AnyKey 需要根据 键 的 哈希值 对一组 KV实体 进行排序。由于每个要合并的 组 已经包含排序的 KV实体，因此排序时间非常短。合并两个包含 8,192个 排序 KV实体 的 数据段组，在 ARM Cortex-A53 核心上大约需要 118微秒 (118us)。与耗时的 压缩 操作相比，这个开销可以忽略不计。

   论文强调，第 5 节中提供的所有实验数据都已包含了上述计算开销。

4.2.6. 压缩 过程的增强 ($AnyKey+$)

4.2.6.1. 动机观察 (Motivational Observations)

作者观察到，虽然 AnyKey 在 低值键比 (low-v/k) 工作负载下 输入输出操作每秒 (IOPS) 显著提高，但在 高值键比 (high-v/k) 工作负载下，以及在 low-v/k 工作负载中 值 (values) 相对较大的情况下，IOPS 会下降。分析表明，在这些工作负载中，在 日志触发压缩 (log-triggered compaction) 期间，大量的 值 被合并到 数据段组 (data segment groups) 中。这反过来导致目标（目的地）层级达到其阈值，并连续触发 树触发压缩 (tree-triggered compaction)。作者将这种连续的 压缩 调用称为 压缩链 (compaction chain)。下图（原文 Figure 9a）描述了发生 压缩链 的情况：

该图像是图表，展示了不同扫描长度下UDB的延迟CDF曲线，包括长度为100、150和200的三个子图。可以看出，AnyKey设计在多种工作负载下的延迟表现优于其他设计。

1. 当 值日志 (value log) 的大小达到其阈值时，会触发一个 日志触发 (L_{n-1} – to – L_n) 压缩（$L_{n-1}$ 被选为目标源层级，因为其 值 的总大小最大），因此大量 值 被合并到目的地层级 $L_n$。
2. 在 压缩 过程中，目的地层级 $L_n$ 达到其阈值，并连续触发一个 树触发 (L_n – to – L_{n+1}) 压缩。

4.2.6.2. 修改后的 日志触发压缩 (Modified Log-Triggered Compaction)

为了避免 压缩链，AnyKey 添加了一个简单而有效的增强功能，其中 日志触发压缩 操作略作修改。具体来说，如 Figure 9b 所示，在 日志触发 (L_{n-1} – to – L_n) 压缩 期间：

1. AnyKey 监控目标目的地层级 ($L_n$) 的大小是否达到其阈值（同时将 值日志 中的 值 合并到 数据段组 中）。

2. 一旦目标目的地层级的大小达到某个点（即 阈值 × α，$0 \leq \alpha \leq 1$；$α$ 可以根据目标工作负载的 键/值 大小而变化），剩余的（要合并到 数据段组 的）值 将被写回 值日志。这样做可以防止 压缩链 的产生。

   然而，这可能会降低 日志触发压缩 的效益（即 值日志 中回收的干净空间可能会减少），因为 值 在某个点后会被写回 值日志。为此，AnyKey 也改变了选择目标层级的方式。不再选择 值日志 中其 值 大小最大的层级，而是选择 值日志 中拥有最多“无效”值的层级。在 LSM-tree 中，由于其 非原地更新 (out-of-place update) 机制，通常一个 键 存在多个不同版本的 值，显然 值日志 也包含大量的 无效值。通过选择这样的目标层级，可以在避免 压缩链 的同时，进一步确保 值日志 中的可用空间。

5. 实验设置

5.1. 数据集

实验使用了 14 种 键值对 (KV) 工作负载，这些工作负载来自不同领域，具有不同的 键 (key) 和 值 (value) 大小，从而代表了 高值键比 (high value-to-key ratio, high-v/k) 和 低值键比 (low value-to-key ratio, low-v/k) 两种类型。

下表（原文 Table 2）列出了所有测试的 KV 工作负载（大小以字节为单位）：

数据集选择原因: 这些数据集的选择旨在覆盖广泛的实际应用场景，特别是为了揭示 低值键比 (low-v/k) 工作负载的挑战，这些工作负载在现有研究中未被充分探索。它们涵盖了从传统的大 值 小 键 (high-v/k)（如 KVSSD、YCSB、W-PinK）到大 键 小 值 (low-v/k)（如 Crypto1、RTDATA、ZippyDB）的不同 值键比 类型。通过这些多样化的工作负载，可以全面评估 AnyKey 设计的普适性和有效性。

5.2. 评估指标

论文使用了以下评估指标来衡量 KV-SSD 设计的性能和效率：

1. 95th百分位尾延迟 (95th percentile tail latency)：

   • 概念定义: 衡量请求响应时间的稳定性。它表示 95% 的请求其响应时间都低于这个特定的值。这个指标对于衡量用户体验和系统在重负载下的表现至关重要，因为它可以反映少数极端慢速请求对整体用户感知的影响。
   • 数学公式: $L_{95} = \text{percentile}(T, 0.95)$
   • 符号解释:
     • $L_{95}$：95th百分位尾延迟。
     • $T$：所有请求响应时间的集合。
     • $\text{percentile}(T, p)$：一个函数，返回集合 $T$ 中第 $p$ 个百分位的值。

2. 输入输出操作每秒 (IOPS)：

   • 概念定义: 衡量存储设备每秒能够处理的输入（读取）和输出（写入）操作的数量。IOPS 是评估存储系统 吞吐量 (throughput) 的一个核心指标，反映了设备处理并发请求的能力。
   • 数学公式: $\text{IOPS} = \frac{\text{总操作数}}{\text{总时间 (秒)}}$
   • 符号解释:
     • $\text{IOPS}$：每秒输入输出操作数。
     • $\text{总操作数}$：在测试期间完成的读取和写入操作的总和。
     • $\text{总时间 (秒)}$：进行这些操作所花费的总时间（以秒为单位）。

3. 存储利用率 (Storage Utilization)：

   • 概念定义: 衡量存储设备中有效、独特的数据所占的比例，相对于其总容量。这个指标反映了存储效率，高利用率意味着更少的冗余或未使用的空间。
   • 数学公式: $\text{Utilization} = \frac{\text{独特KV对的总大小}}{\text{总存储容量}}$
   • 符号解释:
     • $\text{Utilization}$：存储利用率。
     • $\text{独特KV对的总大小}$：存储在设备中所有唯一的 键值对 的总数据量。
     • $\text{总存储容量}$：固态硬盘 (SSD) 的总物理存储容量。

4. 页面写入总数 (Total Number of Page Writes)：

   • 概念定义: 记录 固态硬盘 (SSD) 在操作过程中实际写入 闪存 (flash) 的页面总数。这个指标与 写放大 (write amplification) 直接相关，并影响 SSD 的 设备寿命 (device lifetime)。较低的页面写入总数意味着更长的 SSD 寿命。
   • 数学公式: $\text{Total Writes} = \sum_{i=1}^{N} \text{writes}_i$
   • 符号解释:
     • $\text{Total Writes}$：在整个执行阶段产生的页面写入总数。
     • $N$：所有写入操作的计数。
     • $\text{writes}_i$：第 $i$ 次写入操作写入的页面数。

5.3. 对比基线

论文将 AnyKey 的两个版本（基础版 AnyKey 和增强版 $AnyKey+$）与 PinK [30, 31] 进行了比较。

• PinK： 被认为是 最先进的 (state-of-the-art) 基于 日志结构合并树 (LSM-tree) 的 键值对固态硬盘 (KV-SSD) 设计。它在 高值键比 (high value-to-key ratio) 工作负载下表现良好，但在 低值键比 (low value-to-key ratio) 工作负载下存在性能瓶颈。

5.4. 实验环境与配置

• 测试平台 (Testbed):

  • 基于广泛使用的 闪存模拟器 (flash emulator) FEMU [45] 构建。
  • 利用 uNVMe 驱动 [2] 的 FIO 插件引擎 (FIO plugin engine) 在用户空间生成目标工作负载请求，并使其直接发送到模拟 SSD，绕过传统的 软件栈 (software stack)。
  • 将 PinK [31] 的公开源代码移植到此测试平台，并修改其数据结构以实现 AnyKey。
  • 源代码可访问性: 实现的源代码可在 https://github.com/chanyoung/kvemu 获得。

• 设备配置 (Device configuration):

  • 固态硬盘 (SSD) 容量: 模拟一个 64GB SSD。
  • 通道和芯片: 包含 8个通道 (channels)，每个通道包含 8个闪存芯片 (flash chips)，与 PinK [31] 的配置相同。
  • 页面大小 (Page size): 默认为 8KB。
  • 动态随机存取存储器 (DRAM) 容量: 默认为 64MB（通常设置为 SSD 总容量的 0.1% [25, 39]）。
  • 闪存 (flash) 类型和时序: 假设为现代 TLC 闪存 (TLC flash)，读取 (read)、写入 (write) 和 擦除 (erase) 时间分别设置为 $(56.5, 77.5, 106) µs$、$(0.8, 2.2, 5.7) ms$ 和 3ms，如 [34] 中所述。
  • 可伸缩性研究: 尽管主要模拟小型 SSD，但论文也指出 AnyKey 适用于大型 SSD，并在第 5.9 节评估了 4TB SSD 与 4GB DRAM 的场景。

• 工作负载配置 (Workload configuration):

  • 写入比例 (Write ratios): 所有工作负载的 写入比例 均设置为 20%。
  • 键 (key) 分布 (Key distribution): 默认使用 Zipfian 分布 (Zipfian distribution)，$\theta$ 值为 0.99，表示 键 访问模式是偏斜的。也进行了不同 $\theta$ 值的敏感性分析。
  • 输入输出 (I/O) 队列深度 (I/O queue depth): 设置为 64，理论上允许所有 64个 底层 闪存芯片 同时处理 I/O 请求。
  • KV 应用程序: 由于没有公开可用的 KV 应用程序用于评估 KV-SSD 设计（它们通过传统 I/O 栈 生成 块 I/O 追踪），KV-SSD 研究通常依赖于 KV 生成器（例如基于 FIO 引擎），通过调整 键/值 大小、读/写比例和访问分布等属性来生成工作负载。

• 执行步骤 (Execution procedure):

  1. 预热阶段 (Warm-up stage): 插入所有 KV对，并频繁触发 垃圾回收 (GC) 和 压缩 (compaction) 操作，直到系统性能稳定。
  2. 执行阶段 (Execution stage): 收集性能数据。此阶段持续到总请求大小达到 SSD 总容量 (64GB) 的两倍。对于测试的工作负载，此过程总计 413小时。

5.5. 图像与公式文本摘要（已包含在分析框架的引导说明中，此处不再重复列出）

6. 实验结果与分析

6.1. 核心结果分析

本节详细分析了 AnyKey 及其增强版 $AnyKey+$ 相对于 PinK 在各种工作负载和设备配置下的性能表现。

6.1.1. 尾延迟和 IOPS 性能

下图（原文 Figure 10）比较了在 5种低值键比 (low-v/k) 和 2种高值键比 (high-v/k) 工作负载下，三种系统（PinK、AnyKey、$AnyKey+$）的 95th百分位读取尾延迟 (95th percentile read tail latencies) 的 累积分布函数 (CDF)：

该图像是图表，展示了不同日志大小对 ZippyDB、UDB 和 ETC 的 IOPS 及页面写入总数的影响。图（a）显示了在不同日志大小下的 IOPS，而图（b）则展示了页面写入的总数。

• 针对 low-v/k 工作负载 (Figure 10(a)-(e)): PinK 的 尾延迟 相当长，而 AnyKey 和 $AnyKey+$ 显著缩短了 尾延迟。这证实了 AnyKey 设计通过最小化 元数据 大小并使其驻留在 设备内部动态随机存取存储器 (device-internal DRAM) 中的有效性。

• 针对 high-v/k 工作负载 (Figure 10(f)-(g)): AnyKey 表现出与 PinK 相当的短 延迟，表明 AnyKey 也适用于这些工作负载。$AnyKey+$ 的结构设计与 AnyKey 相同，因此观察到相似的 延迟 分析结果。

  下图（原文 Figure 12）展示了三种系统在所有测试工作负载下实现的 输入输出操作每秒 (IOPS)：

  该图像是图表，展示了KV存储的三种执行模型的比较（a-c），以及KV-SSD的内部架构（d）。其中，图(d)显示了用于定位KV对的元数据结构，包括哈希表和LSM树等。

• 针对 low-v/k 工作负载: AnyKey 相较于 PinK，IOPS 平均提升了 3.15倍。这一显著提升主要归因于两个关键因素：(i) 读取请求 (read requests) 的 闪存访问 (flash access) 次数减少（如 Figure 11b 所示），以及 (ii) 压缩 (compaction) 开销的降低（详见下一节）。

• 针对 high-v/k 工作负载: AnyKey 和 PinK 在不同工作负载下互有胜负。然而，$AnyKey+$ 优于两者，因为它有效避免了 压缩链 (compaction chain) 的发生。

6.1.2. 元数据 大小及其对 闪存访问 的影响

为了解释 AnyKey 性能提升的原因，论文分析了 元数据 大小及其对 闪存访问 的影响。下图（原文 Figure 11）展示了 AnyKey 和 $AnyKey+$ 的 元数据 大小分析及其影响：

该图像是图表(a)和(b)，展示了不同值尺寸与键尺寸比率下，95th百分位尾延迟和IOPS的性能特征。其中(a)展示了延迟的CDF曲线，(b)展示了不同比率下的IOPS值。

• AnyKey 的 元数据 管理 (Figure 11a): 层级列表 (level lists) 由于其极小的尺寸，完全容纳在 DRAM 中。即使是大量的 哈希列表 (hash lists) 也在剩余的 DRAM 空间中生成和存储。
• 闪存访问 次数 (Figure 11b): 结果是，在大多数情况下，读取操作 (read operation) 的 闪存访问 次数可以限制在最多 2 次。这意味着，即使目标 值 (value) 存储在 值日志 (value log) 中，AnyKey 也只需要两次 闪存访问——一次用于 数据段组 (data segment group) 中的目标 KV实体 (KV entity)，另一次用于 值日志 中由 KV实体 指向的 值。

6.1.3. 压缩 和 垃圾回收 (GC) 分析

下表（原文 Table 3）列出了三种系统在 压缩 和 垃圾回收 (GC) 操作期间产生的页面读写次数：

• GC 操作: AnyKey 和 $AnyKey+$ 几乎没有 GC 读写操作。这是因为一个层级的 数据段组 倾向于存储在相同的 块 (blocks) 中，并且这些 块 中的 组 在 压缩 期间会一起重新定位。因此，受害者块 (victim blocks) 中很少发现 有效页 (valid pages)。
• low-v/k 工作负载下的 压缩: PinK 在 low-v/k 工作负载下，压缩 期间的读写计数显著增加。这主要是因为大量的 元段 (meta segments) 必须存储在 闪存 (flash) 中，在 压缩 过程中重新定位时会产生大量的页面读写。相比之下，AnyKey 消除了 元段，从而避免了由此产生的读写。
• high-v/k 工作负载下的 压缩: 如果 AnyKey 遇到 压缩链，其 压缩 开销可能会增加。相比之下，$AnyKey+$ 通过防止 压缩链 的形成，显著降低了开销。

6.1.4. 设备寿命 (Device Lifetime) 和 存储利用率 (Storage Utilization)

下图（原文 Figure 13）显示了每个系统经历的页面写入总数，这实际上反映了 压缩/GC 写入量：

该图像是示意图，展示了 AnyKey KV-SSD 的结构，包括 DRAM、层级列表、元段和数据段。图中标示了不同的键和地址映射，突出显示了键值对在存储中的布局。关键公式如 PPA 代表物理页面地址。

$AnyKey+$ 平均比 PinK 减少了 50% 的写入次数。这直接延长了 固态硬盘 (SSD) 的 设备寿命。

下图（原文 Figure 14）显示了当存储已满时，三种系统的 存储利用率（独特 KV对 (KV pairs) 的总大小对整个存储容量的贡献）：

该图像是图表，展示了不同元数据类型的大小及其在DRAM或Flash中的位置。图的左侧部分（a）比较了高v/k和低v/k工作负载下数据结构的大小，标出了64MB DRAM的参考线。右侧部分（b）显示了不同请求下Flash的访问次数比例，揭示了在不同工作负载下的性能差异。这些信息有助于理解KV-SSD设计在不同场景下的表现。

• 针对 low-v/k 工作负载: PinK 需要在 闪存 (flash) 中维护大量的 元段 (meta segments)，这意味着它在 闪存 中为每个 键 (key) 存储了两个不同的副本（一个来自 元段，另一个来自 数据段 (data segment)）。
• 针对 AnyKey 和 $AnyKey+$: 通过移除 元段，它们始终在 闪存 中为每个 键 只保留一个副本，因此在 low-v/k 工作负载下具有更高的 存储利用率。

6.2. 敏感性分析

6.2.1. 不同 DRAM 大小下的读取延迟

下图（原文 Figure 15）展示了在 3种代表性工作负载 下，当 设备内部动态随机存取存储器 (DRAM) 容量从 32MB 变化到 96MB 时，AnyKey 经历的 尾延迟 (tail latencies)：

该图像是示意图，展示了 AnyKey 设计中的关键-值 SSD 结构。图中包含了 DRAM、Flash 存储的层次结构，以及如何在不同层次中搜索给定关键字的过程。图示强调了级别列表和哈希列表的组合，以及数据段组的排序机制。

• low-v/k 工作负载 (如 Crypto1, ETC): 在 元数据 较大时，如果 DRAM 大小从 96MB 减少到 32MB，尾延迟 会增加。这是因为即使少量 元数据 也无法容纳在 DRAM 中。
• high-v/k 工作负载 (如 W-PinK): 元数据 通常较小，因此微小的 DRAM (32MB) 也足以容纳它，延迟 变化不明显。

6.2.2. 不同 闪存页 (Flash Page) 大小下的读取延迟

下图（原文 Figure 16）展示了在 3种代表性工作负载 下，当 闪存页 大小从 4KB 变化到 16KB 时，AnyKey 经历的 尾延迟：

该图像是示意图，展示了两种类型的压缩操作：树触发压缩和日志触发压缩。在树触发压缩中，当目标源达到其阈值时，数据段组和价值日志发生合并；而在日志触发压缩中，若日志满则进行合并和回收操作。

• 观察结果: 页面大小 (page size) 越大，尾延迟 越短。
• 原因: 假设总 固态硬盘 (SSD) 容量固定，随着 页面大小 的增加（意味着 闪存页 总数减少），AnyKey 中的 数据段组 (data segment group) 数量减少，这反过来意味着 层级列表 (level list) 条目（元数据 大小）减少。更少的 元数据 使得 DRAM 能容纳更多，减少 闪存访问。

6.2.3. 不同 键分布 (Key Distributions) 下的延迟

在默认 $Zipfian \text{分布} ($\theta=0.99) 之外，论文还评估了 AnyKey、$AnyKey+$ 和 PinK 在不同 $\theta$ 值下的表现（$\theta$ 值越低，键 分布越均匀）。下图（原文 Figure 17）展示了 ETC 工作负载在不同 键分布 下的 延迟 (latencies)：

该图像是一个示意图，展示了 AnyKey 中的日志触发压实过程中的问题情况（a）和修改后的日志触发压实方案（b）。图中说明了在源目标满时的处理步骤，以及阈值监控机制的变化。

• PinK: 随着 键分布 变得更均匀，PinK 的 尾延迟 变长。这是因为在更均匀的分布中，许多请求会流向 日志结构合并树 (LSM-tree) 的较低层级，而这些层级的 元数据 (metadata) 通常存储在 闪存 (flash) 中。
• AnyKey 和 $AnyKey+$: 它们通过减小 元数据 大小，能够在 DRAM 中找到这些较低层级 键 的 元数据，因此在不同的 键分布 下提供了更一致的性能。

6.2.4. 范围查询 (Range Queries) 性能

为了评估 扫描请求 (scan requests) 的性能，论文基于 UDB 工作负载设计了一个 扫描中心 (scan-centric) 工作负载。下图（原文 Figure 18）比较了三种系统在不同 扫描请求 长度下的 尾延迟：

该图像是图表，展示了不同系统下 $95^{th}$ 百分位延迟的累积分布函数（CDF）。包含七个子图，分别为RTDATA、Crypto1、ZippyDB、Cache15、Cache、W-PinK及KVSSD，展示了它们在不同延迟下的表现。

• 观察结果: 扫描请求 包含的子请求越多，AnyKey 和 $AnyKey+$ 带来的效益越显著。
• 原因: AnyKey 和 $AnyKey+$ 以 数据段组 (data segment group) 为单位管理一组连续的 键，这有助于 扫描 的许多子请求从相同的 闪存页 (flash pages) 和 数据段组 中得到服务。
• 对比 PinK: PinK 中的 KV对 (KV pairs) 并非排序聚簇在 闪存 中，而是分散在不同的 闪存页 中，导致每个子请求可能访问不同的 闪存页，性能受限。
• 小型 范围查询: 对于小型 范围查询，AnyKey 也能表现出与 PinK 相当的性能，因为它可以使用存储在 数据段组 第一个页面中的位置信息直接定位目标 KV对。

6.2.5. 值日志 (Value Log) 大小对性能的影响

为了评估 值日志 (value log) 大小的影响，论文进行了敏感性分析，将其大小从 3.2GB 变化到 9.6GB（占 64GB SSD 的 5% 到 15%）。下图（原文 Figure 19）展示了不同 值日志 大小对 ZippyDB、UDB 和 ETC 的 输入输出操作每秒 (IOPS) 和 页面写入总数 (total page writes) 的影响：

该图像是图表，展示了不同数据结构的大小及其在元数据中的位置（DRAM或Flash）。图(a)分析各数据结构的大小，图(b)则展示了读取时所需的Flash访问次数，能够反映出AnyKey和AnyKey+在元数据处理上的表现与影响。

• IOPS (Figure 19a):
  • 当 值 (value) 大小相对较小 (ZippyDB) 时，即使是小的 值日志（如 3.2GB）也能实现高 IOPS，且随着 值日志 大小增加 IOPS 不再显著提升。
  • 随着 值 大小增加 (UDB 和 ETC)，值日志 大小的增加可以略微提高 IOPS。
  • 分析: 如果工作负载的 值 大小较小（例如 低值键比 (low-v/k) 工作负载），即使是小的 值日志 也很少会变满，因此很少触发 日志触发压缩 (log-triggered compaction)。
• 页面写入总数 (Figure 19b): 观察到与 IOPS 相似的模式。
• 与 AnyKey- 的比较: 论文还考虑了一个未引入 值日志 的系统 AnyKey-。观察发现：(i) 随着 写入比例 (write ratio) 的增加，AnyKey- 的 IOPS 显著下降，而 $AnyKey+$ 仍能保持高 IOPS；(ii) 尽管 $AnyKey+$ 相对于 AnyKey- 增加了 尾延迟 (tail latencies)，但它仍与 PinK 相当。

6.2.6. 设计可伸缩性 (Design Scalability)

尽管主要假设 64GB SSD 进行研究，但 AnyKey 提案适用于任何 SSD 容量。此外，SSD 容量越大（即 SSD 包含的 KV对 越多），在 低值键比 (low-v/k) 工作负载下，AnyKey 带来的效益就越大。例如，如果 Crypto1 在 4TB SSD 上执行，AnyKey 的 元数据 大小限制在 3.65GB，而 PinK 的 元数据 大小将增加到 25.2GB。这表明 AnyKey 的设计具有良好的可伸缩性。

6.2.7. 多工作负载执行场景 (Multi-Workload Execution Scenarios)

除了单工作负载场景，AnyKey 也适用于多工作负载场景。如果需要将两个工作负载 共置 (co-locate)，可以创建两个 分区 (partitions) [1, 29, 41]，使每个 分区 由独立的 固件 (firmware)（PinK 或 AnyKey）管理，并在其各自的 分区 中执行每个工作负载。论文进行了一个 2工作负载 场景（w-PinK + ZippyDB）的实验，通过创建两个均匀 分区 并用 PinK 或 AnyKey 管理。

• 结果: 相比 PinK，AnyKey 可以分别将 w-PinK 和 ZippyDB 的 99.9th百分位尾延迟 (99.9th percentile tail latencies) 提高 14% 和 216%。
• 结论: 这表明使用 分区机制 (partitioning mechanism) 进行多工作负载场景可以帮助每个工作负载在独立 分区 上从 AnyKey 中受益。

7. 总结与思考

7.1. 结论总结

本文提出了一个新颖的 键值对固态硬盘 (KV-SSD) 设计 AnyKey，其核心洞察力基于以下观察：(i) 现有 KV-SSD 的设计原则假设的是 值键比 (value-to-key ratios) 极高的有限工作负载范围；(ii) 实际上存在着其他 值键比 较低类型的工作负载。

AnyKey 旨在解决这些 低值键比 (low-v/k) 工作负载下的性能问题，它通过最小化 元数据 (metadata) 的大小，并确保其能够完全驻留在 固态硬盘 (SSD) 内部 动态随机存取存储器 (DRAM) 中，从而减少了额外的 闪存访问 (flash accesses)。其增强版 $AnyKey+$ 进一步提升了 日志结构合并树 (LSM-tree) 的管理效率，通过优化 日志触发压缩 (log-triggered compaction) 过程避免 压缩链 (compaction chain)，使得 $AnyKey+$ 在 低值键比 和 高值键比 (high-v/k) 两种工作负载下都优于 最先进的 (state-of-the-art) 设计 PinK。

通过广泛的真实工作负载评估，AnyKey 在 low-v/k 工作负载下显著改善了 尾延迟 (tail latencies) 和 输入输出操作每秒 (IOPS)，而 $AnyKey+$ 则在所有类型的工作负载下都表现出卓越的性能，证明了其通用性和高效性。

7.2. 局限性与未来工作

论文主要关注基于 日志结构合并树 (LSM-tree) 的 KV-SSD 设计，这本身是一种选择。以下是论文可能存在的局限性以及未来可能的研究方向：

• 对 LSM-tree 结构的依赖: AnyKey 是基于 LSM-tree 的，因此它继承了 LSM-tree 固有的 写放大 (write amplification) 和 压缩 (compaction) 相关的复杂性。尽管 AnyKey 和 $AnyKey+$ 优化了 压缩 效率，但 LSM-tree 结构本身仍然是其基础。对于某些不需要 LSM-tree 复杂性的特定工作负载，可能有更简单的优化方案。
• DRAM 容量的限制: 尽管 AnyKey 显著减少了 元数据 大小，但 SSD 内部 DRAM 容量仍然是有限的。对于未来可能出现的极端 low-v/k 工作负载（例如，键 变得极其大，而 值 变得极其小，导致 KV对 数量爆炸），即使是 AnyKey 优化后的 元数据 也可能再次面临溢出 DRAM 的风险。
• 值日志 (Value log) 的间接性: 引入 值日志 带来了 值 访问的间接性，即在 读取 (read) 操作时可能需要两次 闪存访问（一次访问 数据段组 (data segment group) 中的 KV实体 (KV entity) 获取 值 的指针，另一次访问 值日志 获取实际 值）。虽然论文认为这是一种可接受的权衡，并且 日志触发压缩 有助于将活跃 值 迁移到 数据段组，但对于某些纯 读密集 (read-intensive) 且 值 长期保留在 值日志 中的工作负载，这种间接性仍可能带来轻微的性能开销。
• 哈希冲突位 (Hash collision bits) 的开销: 尽管论文指出 哈希冲突 (hash collision) 发生率极低，但 哈希冲突位 的存在和处理逻辑增加了设计的复杂性，并在极少数情况下仍可能导致额外的 闪存访问。
• 模拟环境的局限性: 实验是在 FEMU 模拟器上进行的，而非真实 KV-SSD 硬件。尽管 FEMU 旨在提供准确的模拟，但实际硬件的复杂性（如更细致的 闪存 特性、控制器内部并行性、热管理等）可能带来模拟中未完全捕获的因素。
• 范围查询 的优化潜力: AnyKey 为 范围查询 引入了额外的定位信息，并存储在 数据段组 的第一个页面中。虽然这提高了 范围查询 的效率，但如何进一步优化或动态调整这种辅助信息的粒度，以适应不同 范围查询 模式的需求，仍有探索空间。

7.3. 个人启发与批判

7.3.1. 个人启发

• 工作负载特征化的重要性: 这篇论文最核心的启发在于强调了深入理解工作负载特征（特别是 键 和 值 的相对大小，即 值键比 (value-to-key ratio)）对于存储系统设计的重要性。许多 最先进的 (state-of-the-art) 设计可能在通用或特定假设下表现优异，但在未考虑到的工作负载（如 低值键比 (low-v/k)）下却会暴露出严重的性能瓶颈。这提醒研究者和工程师，设计通用系统需要更全面的工作负载建模。
• 元数据 优化的创造性: AnyKey 通过将 KV对 (KV pairs) 组织成 数据段组 (data segment groups)，并利用 哈希值 (hash values) 进行组内排序和 元数据 压缩，极大地减少了 DRAM 中 元数据 的存储需求。这种“以组为单位”的 元数据 策略非常巧妙，它在不牺牲 KV对 定位效率的前提下，解决了 DRAM 容量限制的问题，特别是在 键 较大的场景下。
• 键值分离 (Key-Value Separation) 的新视角: 值日志 (value log) 的引入是 键值分离 思想在 KV-SSD 和 LSM-tree 背景下的一个优秀实践。它不仅减少了 压缩 (compaction) 过程中的 闪存写入 (flash writes) 量，延长了 设备寿命 (device lifetime)，还通过将 活跃值 (active values) 保留在 值日志 中，避免了在 LSM-tree 各层级间 值 的频繁移动。这种分离和动态管理策略，对于 写密集 (write-intensive) 工作负载的 日志结构合并树 具有普遍的借鉴意义。
• 压缩链 (Compaction Chain) 问题的识别与解决: $AnyKey+$ 针对 LSM-tree 中可能发生的 压缩链 问题提供了实用的解决方案。在 日志触发压缩 (log-triggered compaction) 过程中通过监控目标层级大小并回写 值 的策略，有效地中断了 压缩链，维护了系统性能的稳定性。这表明在设计复杂的存储系统时，不仅要考虑理想情况下的效率，还要关注异常或连锁反应。

7.3.2. 批判与改进方向

• 值日志 动态管理策略的深入研究: AnyKey 简单地将 SSD 剩余容量的一半用于 值日志，并优先选择包含最多 无效值 (invalid values) 的层级进行 日志触发压缩。未来可以研究更智能、更动态的 值日志 大小分配和 值 迁移策略。例如，基于工作负载的 读写比例 (read/write ratios)、值 的访问模式（热点 值）、键 的生命周期等，动态调整 值日志 的大小或 值 迁移的阈值，以进一步优化性能和 存储利用率 (storage utilization)。
• 哈希值 长度与碰撞率的权衡: 论文指出 32位哈希值 足以在 数据段组 中唯一标识 键，且 哈希冲突 发生率低。但随着 SSD 容量和 数据段组 中 KV对 数量的增加，哈希值 长度的选择是一个关键的权衡点。未来可以探索自适应的 哈希值 长度，或者结合更复杂的 哈希 算法，在保证唯一性的同时，最小化 哈希值 的存储开销和计算开销。
• 更通用的 元数据 溢出管理: 尽管 AnyKey 努力将 元数据 保持在 DRAM 中，但在极端情况下（例如，DRAM 容量极其有限或 KV对 数量空前庞大），元数据 仍可能溢出到 闪存。在这种情况下，如何高效地管理 溢出元数据，例如采用多级 元数据 缓存、或者像 PinK 那样将部分 元段 存储到 闪存 但采用更优化的访问模式，将是值得研究的方向。
• 真实硬件验证: 尽管 FEMU 提供了准确的模拟，但最终的性能和效率仍需在真实 KV-SSD 硬件上进行验证。这将有助于发现模拟器可能未捕获的实际硬件行为和瓶颈，例如更复杂的 闪存 磨损机制、控制器固件的内部细节以及不同 NAND 技术的差异。
• 与新兴存储技术的结合: 随着 计算存储 (Computational Storage, CS) 和 区命名空间 (Zoned Namespace, ZNS) 等新兴 SSD 接口和技术的发展，AnyKey 的设计理念如何与这些技术结合，以实现更深层次的协同优化，也是一个潜在的未来研究方向。例如，ZNS 可以提供更严格的 写入 (write) 顺序性，可能进一步简化 值日志 的管理。