SharK：通过Vlog动态分片实现键值存储高性能范围查询的新方法

《IEEE Access》：SharK: Enabling High-Performance Range Queries in Key-Value Store Through Vlog Resharding

本文针对键值分离设计中更新与范围查询性能难以兼顾的问题，提出了一种名为SharK的新型键值存储架构。该研究通过将值日志（vLog）按键范围进行分片（Sharding），并结合垃圾回收（GC）过程实施动态再分片（Resharding）机制，有效解决了因键分布不均导致的性能下降。实验表明，SharK在保持优异更新吞吐量的同时，显著提升了范围查询效率，相比RocksDB、FenceKV等现有方案，范围查询性能提升最高达6.43倍，为未来键值存储引擎的设计提供了新思路。

　　

在现代数据基础设施中，键值（Key-Value, KV）存储扮演着核心角色，广泛应用于从缓存系统到在线事务处理（OLTP）等各种场景。然而，随着混合事务/分析处理（HTAP）等新型工作负载的出现，对KV存储同时具备高效更新和快速查询能力的需求日益迫切。目前主流的存储引擎架构——日志结构合并树（Log-Structured Merge Tree, LSM-tree）——虽然能提供高写入吞吐量，但其固有的读写放大（Read/Write Amplification）问题严重制约了性能，尤其是在处理大规模数据时。为了缓解这一问题，键值分离（Key-Value Separation）技术应运而生，它将占用空间较大的值（Value）从LSM-tree中分离出来，单独存储在一个称为值日志（Value Log, vLog）的追加写入日志中，从而减小LSM-tree的体积，降低 compaction 带来的写放大和读放大。Wisckey 是这一思想的先驱，但它也引入了新的挑战：vLog 的垃圾回收（Garbage Collection, GC）效率低下，以及由于值在vLog中无序存放而导致的范围查询（Range Query）性能急剧下降。

后续的研究试图解决这些新问题。HashKV 通过哈希（Hashing）将vLog分成多个段（Segment），实现了无需查询LSM-tree的高效GC，但其哈希分组方式破坏了数据的局部性，对范围查询不友好。FenceKV 则转向基于键范围（Range-based）的分组，通过在GC过程中对值进行排序来优化范围查询。然而，FenceKV 采用静态的“围栏”（Fence）来划分键范围，这些围栏在初始化后便固定不变。当实际键的分布与初始假设不符或随时间变化时，极易导致不同分组间数据量严重失衡。某些分组可能因写入过多而频繁触发GC，且GC时需要读写大量数据，拖累更新性能；同时，组内数据的分散也加剧了范围查询时的随机访问，使其优势荡折扣，甚至在某些情况下性能退化至接近Wisckey的水平。

针对这一核心痛点，来自日本庆应义塾大学和东京科学研究所的研究人员 Naoto Sugiura 和 Daichi Fujiki 在《IEEE Access》上提出了 SharK。SharK 的核心思想是借鉴分布式数据库中常用的分片（Sharding）和再分片（Resharding）技术，将vLog划分为基于键范围的、大小固定的分片（Shard），并通过与GC过程紧密结合的动态再分片机制，自适应地调整分片的键范围，从而在保持范围查询高效性的同时，有效解决分组失衡问题。其巧妙之处在于，将数据迁移这一再分片的主要开销，巧妙地融合进了GC必须进行的读取和写回操作中，从而实现了近乎零成本的动态负载均衡。

为了开展研究，作者团队基于HashKV和LevelDB使用C++实现了SharK原型系统。研究主要采用了基于YCSB（Yahoo! Cloud Serving Benchmark）的基准测试来评估性能，并使用了SOSD（Suite of Learned Index Benchmarks）基准测试中的真实数据集（如books, wiki, osm）来验证分片预生成（Shard Pre-generation）策略的有效性。关键的技术方法包括：1） 设计了基于范围表（Range Table）的分片管理机制，用于快速定位键所属的分片；2） 将垃圾回收（GC）与再分片（Resharding）操作耦合，根据分片内有效数据比例动态触发分片分裂（Split）或合并（Merge）；3） 提出了被动和主动（基于专用HotShard）的冷热数据分离策略，以减少GC时的数据写回量；4） 引入了基于线性样条回归的采样预测方法，用于初始分片预生成，以降低数据库加载阶段的再分片开销。

SharK架构概述

SharK的整体架构与传统的键值分离设计类似，值存储在vLog区域，而键与值的地址信息存储在LSM-tree中。其创新点在于vLog的管理方式。SharK将vLog划分为多个固定大小的分片（默认2 MiB），每个分片负责一个连续的键范围。写入时，根据键值在范围表中的查找结果，将值追加到对应的分片末尾。初始时只有一个分片，随着数据写入和分片变满，GC被触发。在GC过程中，SharK会读取分片内的数据，识别出有效的键值对（依靠追加写入的特性，无需查询LSM-tree），并进行排序。然后，根据有效数据比例（R = S_valid/S_shard）决定是否进行再分片。若R超过分裂阈值（默认0.8），则执行分片分裂：创建一个新分片，并将排序后的有效数据后半部分写入新分片，前半部分写回原分片。若R低于合并阈值（默认0.2），则执行分片合并，将当前分片数据合并到相邻分片中。这种设计确保了分片间的负载均衡，并使得每个分片内的数据保持有序，从而优化范围查询。

分片管理与再分片

SharK在内存中维护了两个关键元数据表：分片表（Shard Table）和范围表（Range Table）。分片表记录每个分片的当前写入位置等状态。范围表是一个有序哈希映射，存储每个分片的最小键和分片ID，用于快速定位键所属的分片。再分片操作（分裂或合并）会更新范围表。通过将再分片与GC紧密结合，SharK避免了单独进行数据迁移的巨大开销，实现了动态自适应的数据分组。

冷热数据分离

SharK的GC策略天然地带来了一种被动的冷热数据分离效果：写入频繁的“热”分片会更早变满并触发GC，而写入稀少的“冷”分片则较少被GC打扰，从而减少了冷数据的写回。此外，SharK还提供了一种积极的冷热分离策略：维护一个LRU（Least Recently Used）列表来识别热键，并将热键对应的值写入一个专门的、容量更大的HotShard中。这进一步将热数据集中管理，避免了热数据在普通分片中“污染”冷数据，从而显著降低了GC时写回的数据量。

分片预生成

在数据库初始加载阶段，如果只有一个分片，会经历频繁的再分片，影响加载性能。为此，SharK提出了分片预生成技术。它利用工作负载初始的一小部分键样本（如2048个键），通过线性样条回归来预测键的累积分布函数（CDF），然后根据预测的CDF将整个键范围均匀划分为多个分片，并预先创建这些分片。这种方法仅需极少的样本（0.0065%的数据量）就能达到甚至超过FenceKV使用大量样本（0.40%数据量）进行随机采样分组的加载性能，有效减少了初始再分片次数。

性能评估结果

研究团队对SharK与RocksDB、WiscKey、HashKV、FenceKV进行了全面的性能对比评估。在加载30 GiB数据后执行范围查询的测试中，SharK的范围查询吞吐量比WiscKey高4.71倍，比HashKV高4.97倍，比FenceKV高4.38倍，比RocksDB高2.13倍。在后续进行90 GiB更新操作后，SharK的更新吞吐量比WiscKey高2.60倍，比FenceKV高1.29倍，与HashKV相当。尤为重要的是，更新后的范围查询性能，SharK比WiscKey高6.43倍，比HashKV高6.21倍，比FenceKV高2.13倍，比RocksDB高2.78倍。这些结果充分证明了SharK在同时优化更新和范围查询性能方面的有效性。

在针对不同键值对大小（256 B 至 64 KiB）的测试中，SharK 在较大值（如 64 KiB）时表现出显著优势，其范围查询吞吐量是 RocksDB 的 3.52 倍，凸显了键值分离对大值处理的优势。在 YCSB 核心工作负载（A-F）的测试中，SharK 在写密集型负载（A, F）中表现最佳，在读密集型负载（B, C）中与其他键值分离方案性能相近，在涉及插入的负载（D）和短范围扫描负载（E）中也保持了竞争力。此外，评估还显示，SharK 的 GC 写回数据量比 WiscKey 少 1.40 倍，比 HashKV 少 1.33 倍，比 FenceKV 少 1.56 倍，比 RocksDB 的 compaction 写回量少 5.60 倍，证明了其高效的资源利用率和较低的写放大。

研究结论与意义

本研究表明，通过引入动态范围分片和与GC协同的再分片机制，SharK成功地解决了现有键值分离设计在范围查询和更新性能之间的权衡难题。SharK 的关键贡献在于其自适应数据分组能力，确保了即使在键分布倾斜或变化的负载下，也能维持稳定的高性能。其隐式和显式的冷热数据分离策略进一步提升了GC效率。此外，分片预生成等优化措施降低了初始开销。综合来看，SharK 为键值存储引擎的设计提供了一种新范式，它不仅在多项性能指标上超越了现有先进方案，还具备了弹性存储管理的灵活性，无需像一些先前工作那样预先分配固定容量，为应对未来多样化的数据存储需求奠定了坚实的基础。这项工作有力地证明了动态再平衡是构建高性能、自适应键值存储系统的关键，具有重要的理论和实践意义。