[FAST'20] HotRing: A Hotspot-Aware In-Memory Key-Value Store 论文阅读

发表于 2026-03-29 分类于 database-system 阅读次数：本文字数： 13k 阅读时长 ≈ 48 分钟

#摘要

内存键值存储 (KVS) 被广泛用于缓存热点数据, 以解决基于磁盘的存储系统或分布式系统中的热点问题. 然而, 内存 KVS 内部的热点问题却一直被忽视. 随着近年来热点问题愈发严重, 现有 KVS 由于缺乏热点感知能力, 在高度偏斜的工作负载上往往表现不佳, 且可靠性不足.

本文探索了面向内存 KVS 索引结构的热点感知设计. 我们首先分析理想热点感知索引的潜在收益, 并讨论在有效利用热点感知时所面临的挑战 (即热点迁移与并发访问). 基于这些认识, 我们提出了一种新的热点感知 KVS - HotRing, 其针对“大量并发访问集中于少量条目”的场景进行了优化.

HotRing 基于一种有序环 (ordered-ring) 哈希索引结构, 该结构通过将头指针移动到更靠近热点项的位置来加速对热点项的访问. 同时, HotRing 采用了一种轻量级策略来在运行时检测热点迁移. HotRing 在整体设计中系统性地采用了无锁结构, 不仅覆盖常规操作 (即读, 更新), 也覆盖 HotRing 特有操作 (即热点迁移检测, 头指针移动以及有序环 rehash), 从而使海量并发请求能够更好地利用多核架构. 大量实验表明, 在高度偏斜的工作负载下, 我们的方法相较于其他内存 KVS 最多可实现 2.58× 的性能提升.

#1 引言

内存键值存储 (KVS) 是存储基础设施 (例如数据库, 文件系统) 中的一个关键组成部分, 其通过将频繁访问的数据缓存在内存中来提供更快的访问. KVS 有助于提升这些系统的性能与可扩展性, 因为这些系统往往需要在单秒内处理数十亿次请求. 许多最先进的 KVS, 例如 Memcached, Redis 及其变体, 已经在 Facebook, Amazon, Twitter 和 LinkedIn 等企业的生产环境中得到广泛开发和部署.

热点问题 (即在高度偏斜的工作负载中, 只有一小部分条目被频繁访问) 是现实场景中的常见问题, 并已在文献中得到广泛研究. 已有大量方案用于解决集群范围的热点问题, 例如 一致性哈希, 数据迁移 以及 前端数据缓存. 此外, 单节点层面的热点问题也已被较好地解决. 例如, 计算机体系结构通过分层存储布局 (如磁盘, RAM, CPU cache) 将频繁访问的数据块缓存到低延迟存储介质中. 许多存储系统, 如 LevelDB 和 RocksDB, 也使用内存 KVS 来管理热点项.

然而, 内存 KVS 内部的热点问题通常被忽视. 我们从阿里巴巴的生产环境中收集了内存 KVS 的访问分布, 如论文图 1 所示. 我们观察到, 在日常场景下有 50% 的访问, 在极端场景下有 90% 的访问, 仅触及总条目数的 1%. 这表明, 在互联网时代, 热点问题已经变得前所未有地严重.

这一现象背后有若干原因. 首先, 在线应用中的活跃用户规模持续增长. 一个实时事件 (例如线上促销, 突发新闻) 能够在短时间内吸引数十亿次访问集中于少量条目, 而对这些热点进行快速访问至关重要. 已有报道指出: Amazon 页面加载每延迟 0.1 秒, 会造成 1% 的销售损失; Google 搜索结果每额外增加 0.5 秒的加载延迟, 会导致 20% 的流量下降. 其次, 这类应用下方的基础设施日趋复杂. 流水线中任何一个位置的轻微错误 (例如软件 bug 或配置失误) 都可能导致某个条目被不可预测地重复访问 (例如不断读取某一项并无限返回错误消息). 理想情况下, 这类不可预测的热点不应导致整个系统崩溃或被阻塞. 因此, 在热点存在时保持 KVS 的高性能与高可靠性, 具有重要意义.

多种索引结构都可用于实现 KVS, 例如跳表, 平衡树 / Trie 树 (如 Masstree) , 以及哈希 (如 Memcached, MemC3, MICA, FASTER), 其中哈希由于查找更快而最为流行. 然而, 我们观察到, 大多数方案都 不感知热点, 即它们以统一策略管理所有条目. 在这种情况下, 读取一个热点项与读取其他条目需要相同数量的内存访问. 从理论分析 (详见第 2.2 节) 可知, 在当前哈希索引中查找热点项, 相比理想的热点感知策略, 需要付出更多代价. 尽管已有一些机制能减少内存访问次数, 但其效果有限. 例如, CPU cache 能加速热点访问, 但容量通常仅为 32MB; rehash 能缩短冲突链长度, 但会显著增加内存占用. 这一现状为我们在高度偏斜工作负载下进一步优化热点访问提供了机会.

在本文中, 我们提出 HotRing, 一种热点感知的内存 KVS, 其使用经过专门优化的哈希索引, 以支持 “大量并发访问集中于少量条目 (即热点)” 的场景. 其基本思想是: 查找某一条目所需的内存访问次数应与该条目的热度负相关, 即越热的条目应当越快被访问到. 为实现这一目标, 需要解决两个挑战:

热点迁移 (hotspot shift): 热点集合会持续变化, 因此系统需要及时检测并适配这些变化;
并发访问 (concurrent access): 热点天然会被海量并发请求访问, 因此需要在这些热点上维持高并发能力.

对于热点迁移问题, 我们用一种 有序环结构 替代哈希索引中的冲突链, 使得桶头可以在热点迁移时直接重新指向热点项, 而不破坏正确性. 此外, 我们还使用一种轻量级机制来在运行时检测热点迁移. 对于并发访问问题, 我们采用一种受现有无锁结构启发的无锁设计, 并将其扩展为支持 HotRing 所需的全部操作, 包括热点迁移检测, 头指针移动以及有序环 rehash.

我们基于模拟真实工作负载的基准测试进行了大量实验, 并将 HotRing 与无锁链式哈希及其他基线系统进行了比较. 结果表明, 在极度偏斜的工作负载下, HotRing 每秒最多可处理 565M 次读请求, 相比其他系统可获得 2.58× 的提升. 对于原地更新与读复制更新 (RCU), HotRing 分别实现了 2.17× 和 1.32× 的性能提升. 这验证了 HotRing 是一种能够提升单节点热点处理能力, 从而使内存 KVS 更高性能且更可靠的有效结构.

#主要贡献

本文的主要贡献可概括如下:

我们识别了现有内存索引中的热点问题, 并证明热点感知设计在提升热点项性能方面具有巨大潜力.
我们提出了 HotRing - 一种有序环哈希结构, 作为利用热点感知设计的首次尝试. 它通过将头指针移动到更靠近热点项的位置来加速访问, 并采用轻量级策略在运行时检测热点迁移.
我们将 HotRing 设计为无锁结构, 以支持海量并发访问. 特别地, 我们从头设计了 HotRing 特有操作, 包括热点迁移检测, 头指针移动和有序环 rehash.
我们在基于真实工作负载特征的基准测试中对该方法进行了评估. 结果显示, 当访问高度偏斜时, HotRing 明显优于其他 KVS.

本文余下部分组织如下: 第 2 节介绍哈希索引与热点问题, 并讨论热点感知哈希的机会与挑战; 第 3 节详细说明 HotRing 的设计; 第 4 节对其性能进行评估; 第 5 节回顾相关工作; 第 6 节给出结论.

#2 背景与动机

本节首先介绍现有 KVS 中的哈希索引以及其中存在的热点问题; 随后从理论上说明理想热点感知哈希所能带来的潜在收益; 最后讨论在实际索引中有效利用热点感知所面临的挑战, 以及我们的设计原则.

#2.1 哈希索引与热点问题

哈希索引是 KVS 中最常见的内存结构, 尤其适用于上层应用不需要范围查询的场景. 论文图 2 展示了典型的哈希索引结构: 它包含一个全局哈希表, 以及哈希表中每个槽位所对应的一条冲突链. 访问某个 key 时, 首先计算其哈希值 h 以定位对应桶头, 然后沿冲突链逐项检查, 直到找到该 key 或到达链尾 (即 key 不存在).

一个 n 位哈希值还可进一步拆分为两部分: 哈希表部分 (例如 $k$ 位) 与 tag 部分 (例如 $n-k$ 位). tag 可存放在每个条目中, 以避免直接比较较长的 key. 正如论文图 2 所示, 哈希索引并不感知热点, 即热点项可能均匀分布在冲突链中. 对于一个位于冲突链尾部附近的热点项 (例如图中的 Item3), 访问它所需的内存访问次数将高于前部的其他条目. 然而, 在高度偏斜的工作负载下, 热点项访问成本即便只是轻微增加, 也可能导致整体性能的严重下降.

存在若干方法可以降低热点项的访问成本, 但其效果都较为有限. 首先, CPU cache 可加速对热点数据块 (即以 64 字节 cacheline 为单位) 的访问. 然而, 对于大多数商用服务器而言, CPU cache 容量通常约为 32MB, 而整个内存容量往往超过 256GB, 因此可缓存的内存仅占 0.012%, 远低于论文图 1 中所观察到的热点比例. 为了更好地利用 CPU cache, 人们提出了许多 cache-friendly 的索引结构. 其次, 可以通过扩张哈希表 (即 rehash) 来缩短冲突链长度, 从而减少定位热点项所需的内存访问次数. 但当哈希表本身已经很大时, rehash 不再划算. 例如, 连续两次 rehash 中, 第二次需要额外两倍的内存空间, 却只能带来前一次一半的收益 (以链长缩短为衡量标准).

总之, 现有方法都只能在有限程度上缓解热点问题.

#2.2 热点感知的潜在收益

随着热点问题日益严重 (如图 1 所示), 热点感知哈希索引的设计机会也在不断增长. 首先, 我们希望对 “通过热点感知设计究竟能够获得多大收益” 进行一个粗略估计与分析.

在传统基于冲突链的哈希索引中, 热点项是随机放置在链上的, 因此热点项与冷项在访问成本上没有区别. 假设有 N 个条目 (键值对) 存放在具有 B 个桶的哈希表中, 则每个桶链的平均长度为:

L = N / B

则在链式结构中检索一个条目所需的期望内存访问次数 E_chain 为:

E_chain = 1 + L/2 = 1 + N/(2B)

其中前导的 1 表示对哈希表本身的一次访问.

在理想的热点感知哈希索引中, 检索一个条目所需的内存访问次数应与其热度负相关, 即最热的条目需要最少的内存访问. 我们使用 Zipfian 分布来建模条目热度, 其中第 x 个最热条目的访问频率 f(x) 表示为:

f(x) = (1 / x^q) / Σ_{n=1..N}(1 / n^q)

其中 q 为偏斜因子.

为简化分析, 我们假设热点在 B 个桶中均匀分布, 即每个桶恰好包含一个来自前 B 个最热点的条目, 一个来自第 B+1 到 2B 个最热点区间的条目, 以此类推. 在这种情况下, 如果能够按访问频率降序对每条链中的条目进行排序, 则检索一个条目所需的期望内存访问次数 E_ideal 可表示为:

E_ideal = 1 + Σ_{k=1..L} F(k) * k

其中 F(k) 表示各链中第 k 个位置上的条目所累积的访问频率.

为了估计热点感知设计的潜在收益, 我们分别计算了传统哈希与理想热点感知哈希的期望内存访问次数, 如论文图 3 所示. 可以观察到, 随着冲突链长度不断增加, 热点感知哈希能够显著提升访问效率. 这一结果验证了: 在哈希索引中引入热点感知, 是一个极具前景的性能优化方向.

#2.3 挑战与设计原则

我们已经表明, 使索引具备热点感知能力是有益的. 然而, 要在实际设计中利用这一思想, 仍面临若干挑战:

热点迁移 (Hotspot Shift): 在真实应用中, 访问模式会随时间不断变化. 始终按照最新热度对所有条目进行理想排序在代价上是不可接受的. 因此, 我们需要一种轻量级方法来追踪热度迁移.
并发访问 (Concurrent Access): 每个热点都会天然地受到海量并发请求访问. 因此, 为了维持令人满意的性能, 必须为读 / 写操作都提供高并发支持.

对于热点迁移问题, 我们的设计原则是: 不重新对链中条目排序, 而是移动头指针, 例如使其指向最热点项, 或者一个全局更优的位置. 为保证无论头指针如何移动, 桶中的所有条目始终可达, 我们用一种称为 HotRing 的有序环结构 (第 3.1 节) 取代传统冲突链. 尽管这种设计无法达到第 2.2 节所讨论的理想热点感知最优状态, 但实验表明它已足够有效且足够快. 此外, 我们还采用两种轻量级策略在运行时检测热点迁移 (第 3.2 节).

对于并发访问问题, 无锁结构是一类经典解决方案, 因为它消除了昂贵的锁与同步操作. 已有许多工作证明, 无锁设计可显著提升系统吞吐量. 我们的无锁设计借鉴了既有工作, 并将其扩展为支持 HotRing 所需的全部基本操作, 包括热点迁移检测, 头指针移动以及 rehash (第 3.4 节).

#3 HotRing 的设计

本节详细阐述 HotRing 的设计, 包括采用热点感知思想的索引结构, 热点迁移检测策略, 以及一系列无锁操作 (读 / 写, 插入 / 删除, 头指针移动和 rehash).

#3.1 有序环哈希索引

论文图 4 展示了 HotRing 的索引结构. 它对传统哈希索引中的冲突链结构进行了改造: 链中的最后一个条目会重新链接到第一个条目, 从而形成一个冲突环. 以这种方式, 哈希表中的头指针可以指向对应环中的任意条目, 而不再固定指向链首. 若环中只有单个条目, 则其 next 指针直接指向自身.

基于这种冲突环设计, HotRing 能够根据数据热度移动头指针, 并从任意起始位置扫描整个环. 需要注意的是, 如果只存在一个条目, 则 next 指针指回自身.

然而, 环结构带来一个严重问题: 如果目标条目不存在, 则可能在环中发生无限遍历. 因此, 必须确定何时能够安全终止查找过程. 仅仅把头指针所指的第一个条目标记为终止信号是不够的, 因为该条目可能会被并发请求修改 (例如被标记条目被删除). 为解决这一问题, 我们提出一种有序环结构来辅助判断查找何时终止.

其直观思想是: 按 key 对环中条目进行排序. 在这种情况下, 如果在遍历过程中已经遇到一对相邻条目, 其中前者小于目标条目, 后者大于目标条目, 那么就可以判定“目标条目不存在”. 进一步地, 由于直接比较长 key 的代价可能较高, 我们先利用第 2.1 节引入的 tag 字段. 也就是说, 条目 k 的排序依据是其 (tag_k, key_k) 二元组, 即:

order_k = (tag_k, key_k)

在查找条目 k 的过程中, 设当前访问到条目 i, 则在满足以下任一条件时可以立即终止:

**命中 (Hit) 条件: **

order_i = order_k

**未命中 (Miss) 条件: **

order_{i-1} < order_k < order_i
或 order_k < order_i < order_{i-1}
或 order_i < order_{i-1} < order_k

论文图 5 展示了在 HotRing 中查找一个条目时的所有可能情况. 图中给出了每个条目的字典序 (tag, key). 例如, 条目 C 位于条目 A 之后, 是因为 tag_A < tag_C; 条目 D 位于条目 C 之后 (tag 相同), 是因为 key_C < key_D. 当比较到条目 C 时, 可以判定条目 B 为 miss, 因为 tag_A < tag_B < tag_C; 条目 G 和 H 在比较到条目 I 时也可被判定为 miss, 因为分别满足 tag_G < tag_I < tag_F 与 tag_I < tag_F < tag_H.

与传统链式哈希不同, 在 HotRing 中并不需要访问环中的全部条目才能得出 miss 结论. 假设一个环含有 n 个条目, 则平均只需比较约 (n/2)+1 个条目即可完成查找.

#3.2 热点迁移识别

在有序环哈希索引中, 查找过程已经能够容易地判断 hit 或 miss. 接下来需要解决的问题是: 如何识别热点, 并在热点迁移时调整头指针.

由于哈希值通常服从强均匀分布, 热点项会均匀分布在各个桶中. 这里我们把注意力聚焦于每个桶内部独立地识别热点. 在实践中, 每个桶中的冲突条目数通常较少 (例如 5 到 10 个), 因此在热点比例为 10%～20% 时, 每个冲突环中通常只有一个热点. 我们可以通过将头指针直接指向这一热点来提升访问性能, 而无需重组数据, 也不会增加额外内存开销.

为获得良好性能, 需要关注两个指标:

识别准确率: 被识别为热点的条目中, 真正热点所占比例;
反应延迟: 从新热点出现到系统成功检测它之间的时间跨度.

考虑这两个指标, 我们首先介绍一种随机移动策略, 它具有极低的反应延迟; 随后提出一种统计采样策略, 其识别准确率更高, 但反应延迟也相对稍高.

在本节中, 我们首先定义几个术语. 由头指针所指向的第一个条目称为热项 (hot item), 其余条目称为冷项 (cold items); 对这两类条目的访问分别称为热访问 (hot access)与冷访问 (cold access).

#3.2.1 随机移动策略

这里我们引入一种直接的随机移动策略. 该策略保持较低反应延迟, 但识别准确率相对较低. 其基本思想是: 头指针周期性地根据某次即时访问作出决策, 并移动到一个潜在热点, 而无需记录历史元数据.

具体而言, 每个线程都维护一个线程本地参数, 用于记录该线程已执行的请求数. 在每经过 R 次请求之后, 该线程决定是否执行一次头指针移动操作:

若第 R 次访问是一次热访问, 则头指针位置保持不变;
否则, 若第 R 次访问是一次冷访问, 则将头指针移动到此次冷访问所访问的条目, 该条目成为新的热项.

参数 R 会影响反应延迟与识别准确率. 若 R 较小, 则系统达到稳定性能所需的反应时间较低; 但与此同时, 也可能导致头指针移动过于频繁且往往无效. 在我们的场景中, 访问高度偏斜, 因此头指针移动本身通常并不频繁. 实验中默认将 R 经验性地设为 5, 结果表明这一选择能够在反应延迟与性能影响之间取得较好平衡.

需要指出的是, 当工作负载偏斜性不明显时, 随机移动策略会变得低效. 更重要的是, 该策略无法处理一个冲突环中存在多个热点的情况. 在这种情况下, 头指针会频繁移动, 但这并不能加速热点访问, 反而会对正常操作造成不利影响.

#3.2.2 统计采样策略

为了获得更高性能, 我们设计了一种统计采样策略, 其目标是在稍高反应延迟的代价下提供更高的热点识别准确率. 下面我们首先介绍 HotRing 中条目与指针的具体格式, 并说明如何利用现有格式在不增加额外空间开销的情况下维护统计信息; 随后详细说明采样策略如何估计访问频率; 最后, 在考虑一个环中可能存在多个热点的情况下, 给出如何推导最优头指针移动的方法.

#索引格式

我们希望记录每个冲突环中所有条目的访问频率. 现代机器的物理地址通常只占用 48 位 (但可以通过 64 位原子 CAS 操作更新), 因此剩余的 16 位可用于记录元数据.

在 HotRing 中, 每个头指针由三部分组成 (如论文图 6(a) 所示) :

一个 Active bit: 用于控制统计采样;
一个 Total Counter (15 位) : 记录对应环上的访问次数;
一个 Address (48 位) : 记录条目地址.

其中, Active bit 是一个标志位, 用于控制热点识别过程中的统计采样; Total Counter 用于记录对应冲突环被访问的总次数.

此外, 条目的结构如论文图 6(b) 所示. 其中:

Rehash 是一个用于控制 rehash 过程的标志位 (第 3.4 节讨论) ;
Occupied 用于保证并发正确性 (本节稍后讨论) ;
HotRing 还利用 next-item 地址中的剩余 14 位来记录每个条目的访问计数.

基于环级别与条目级别的统计信息, 访问频率的计算是直接的.

#统计采样

如何以低开销动态识别热点, 是一个具有挑战性的问题. 哈希表通常非常大, 例如包含 2^27 到 2^30 个桶. 若对海量冲突环持续, 同步地更新统计信息, 会导致严重性能下降. 因此, 关键在于尽可能降低统计开销, 同时保留识别准确率, 而这正是 HotRing 中周期性采样的目标.

具体来说, 每个线程维护一个线程本地计数器, 用于记录其已处理的请求数. 每完成 R 次请求后, 系统判断是否开启新一轮采样 (即将图 6(a) 中的 Active 位置为 1). 若第 R 次访问是热访问, 说明当前热点识别仍然准确, 因此无需触发采样; 否则, 说明热点已经发生迁移, 于是启动采样过程.

一旦 Active bit 被设置, 后续对该环的访问就会同时记录到:

环级别的 Total Counter;
对应条目的访问计数器.

采样过程需要额外的 CAS 操作, 因此会导致短暂的访问性能下降. 为缩短这一时期, 我们将采样数设置为“环中条目数”这一数量级, 因为我们认为这一规模已经足以推导新的热点位置.

#热点调整

基于收集到的统计信息, 我们可以确定新的热项, 并根据各条目的访问频率来移动头指针. 采样结束后, 最后一个访问该环的线程负责执行频率计算与热点调整.

首先, 该线程使用 CAS 原子地重置 Active bit, 以保证只有一个线程能够执行后续任务. 然后, 该线程计算环中每个条目的访问频率. 设环的总访问数为 N, 第 k 个条目的计数为 n_k, 则其访问频率为 n_k / N.

接着, 我们计算头指针指向每个候选条目时的“收益 (income)” . 设头指针指向第 t 个条目 (0 < t < k), 则对应收益 W_t 计算如下:

W_t = Σ_{i=1..k} (n_i / N) * ((i - t) mod k)

这里, W_t 衡量的是: 当头指针选择指向第 t 个条目时, 该冲突环的平均内存访问次数. 因此, 选择 min(W_t) 对应的条目作为热项, 可以保证热点访问尽可能更快. 若计算得到的新位置与原头指针位置不同, 则应通过 CAS 原子地移动头指针.

需要注意的是, 该策略不仅适用于“单热点”情形, 也适用于“多热点”情形. 它能够找出一个最优位置 (该位置不一定就是最热点项本身), 从而避免头指针在多个热点之间频繁来回移动. 在完成热点调整之后, 负责该过程的线程会重置所有计数器, 为下一轮采样做准备.

#RCU 场景下的写热点

对于更新操作, HotRing 对于不超过 8 字节的值提供原地更新方法. 在这种情况下, 读一个条目与更新一个条目在“热度”上可视为等价.

然而, 对于更大的值, 情况则完全不同, 如论文图 7 所示. 为了获得较高性能, 必须使用 read-copy-update (RCU) 协议. 在这种情况下, 更新一个条目时, 需要修改其前驱条目的指针, 使之指向新条目. 若位于头部的写热点被修改, 则整个冲突环必须被遍历, 以找到其前驱条目. 换言之, 一个写密集型热点条目, 也会使其前驱条目变热.

基于这一洞察, 我们对统计采样策略作了轻微修改: 对于一次 RCU 更新, 不再增加目标条目的计数, 而是增加其前驱条目的计数. 这样有助于将头指针移动到写热点的前驱位置, 从而使整个 RCU 更新操作更快.

#3.2.3 热点继承

当对头项执行 RCU 更新或删除时, 我们需要将头指针移动到另一个条目. 如果头指针被随机地移动, 它很可能指向一个冷项, 从而导致热点识别策略频繁触发. 此外, 由于这些策略被频繁触发, 系统性能也会显著下降.

首先, 如果冲突环中只有一个条目 (即 next-item address 与头指针位置相同), 那么只需通过 CAS 修改头指针即可完成更新或删除. 若环中包含多个条目, HotRing 将利用现有热点信息 (即头指针位置) 来进行热度继承.

我们针对 RCU 更新与删除操作分别设计了不同的头指针移动策略, 以保证热点调整的有效性:

对于头项的 RCU 更新, 由于访问具有时间局部性, 最近更新过的条目有较高概率会被立即再次访问. 因此, 头指针会被移动到该头项的新版本上.
对于头项的删除, 则直接将头指针移动到其下一个条目, 这是一个简单且有效的方案.

#3.3 并发操作

头指针移动使得无锁设计更加复杂, 其主要体现在以下几个方面:

一方面, 头指针移动可能与其他线程并发发生, 因此必须处理头指针移动与其他修改操作之间的并发关系, 避免头指针指向无效条目. 另一方面, 当删除或更新某个条目时, 还需要检查头指针是否正指向该条目; 若是, 则必须正确地, 智能地移动头指针.

本节主要介绍 HotRing 中用于解决并发访问问题的控制方法. 为实现高并发访问并保证高吞吐量, 我们实现了一整套无锁设计, 这些设计已在先前工作中被严格讨论. 其核心是使用原子 CAS 操作来保证: 两个线程不会同时修改同一个 next-item address. 若多个线程尝试同时更新同一个 next-item address, 则只有一个线程成功, 其余线程必须重新执行自己的操作.

#读 (Read)

HotRing 按照第 3.1 节所述, 在冲突环中扫描查找具有目标 key 的条目. 为了保证读操作的正确性, 不需要额外的同步操作. 因此, 读操作是完全无锁的.

#插入 (Insertion)

插入操作会创建一个新条目 (例如图 8(a) 中的条目 C), 并修改其前驱条目的 next-item address. 两个并发插入可能竞争同一个 next-item address. CAS 能保证只有一个线程成功, 另一个线程失败并重试.

#更新 (Update)

我们为不同大小的值设计了两种更新策略. 原地更新 (用于 8 字节值) 不会影响其他操作, 其正确性由 CAS 保证. 然而, RCU 更新 (用于更长的值) 需要创建一个新条目, 因此会对其他操作的并发性提出挑战.

以图 8(a) 中的 “RCU update & Insert” 为例: 一个线程试图通过修改条目 B 的 next-item address 插入条目 C; 另一个线程同时试图将 B 更新为 B’. 由于两个线程修改的是不同指针, 因此它们的操作都可能成功. 但这会带来问题: 如果原条目 B 已经从逻辑环中不可见, 即使插入操作在局部上成功了, 条目 C 也无法在后续被访问, 从而导致错误. 同样的问题也存在于图 8(b) 所示场景中.

为解决这一问题, HotRing 使用 Occupied 位 (见图 6(b)) 来保证并发正确性. 更新操作分两步执行. 以 “Update & Insert” 为例:

首先, 将待更新条目 B 的 next-item address 原子地标记为 occupied; 一旦 Occupied 位被设置, 对条目 C 的插入就会失败并必须重试.
然后, 将条目 A 的 next-item address 原子地修改为指向新条目 B’, 并清除 B’ 的 Occupied 位.

#删除 (Deletion)

删除操作通过将“指向待删条目的指针”改为“指向待删条目的后继”来完成. 因此, 必须保证在删除过程中, 待删条目的 next-item address 不会发生变化. 类似地, 我们也利用 Occupied 位来保证并发正确性.

以图 8© 中的 “RCU update & Delete” 为例: 对条目 D 的更新需要通过修改其前驱条目 B 的指针来完成, 而此时条目 B 正在被删除. 这样, 更新得到的新条目 D’ 将无法被正确遍历, 导致数据丢失. 若删除操作预先设置了条目 B 的 Occupied 位, 则对 D 的更新将无法修改 B 的 next-item address, 只能失败并重试. 一旦删除完成, 更新操作便可正确执行.

#头指针移动 (Head Pointer Movement)

头指针移动是 HotRing 中的一种特殊动作. 为了保证头指针移动与其他操作 (尤其是更新与删除) 之间的正确性, 我们需要额外控制. 这里主要有两个问题需要解决:

如何处理由热点识别策略触发的头指针移动, 与普通操作之间的并发？
如何处理由于更新或删除头项而引发的头指针移动？

对于第一类, 即由热点识别策略触发的头指针移动, 我们同样使用 Occupied 位来保证正确性. 当将头指针移动到一个新条目时, 我们先设置该条目的 Occupied 位, 以保证在移动过程中, 该条目不会被更新或删除.

对于头项更新, HotRing 会把头指针移动到该条目的新版本. 在移动头指针之前, 必须确保这个新版本不会被其他线程进一步修改 (即更新或删除). 因此, 在更新过程中, HotRing 会先设置新版本条目的 Occupied 位, 直到头指针移动完成.

对于头项删除, HotRing 不仅需要占住待删条目本身, 还需要占住其后继条目. 因为如果删除过程中后继条目未被占住, 则它可能已被其他线程改变, 从而使头指针最终指向一个无效条目.

#3.4 无锁 Rehash

随着插入不断发生, 一个环中的冲突条目数会持续增加, 导致每次访问都需要遍历更多条目. 在这种情况下, KVS 性能会显著下降. 为此, 我们在 HotRing 中提出了一种无锁 rehash 策略, 使得随着数据规模增长, 可以灵活执行 rehash.

传统 rehash 通常由哈希表的装载因子 (即平均链长) 触发. 然而, 这种方式没有考虑热点影响, 因此并不适用于 HotRing. 为了使索引能够适应热点项数量的增长, HotRing 使用访问开销 (即检索一个条目所需的平均内存访问次数) 来触发 rehash.

我们的无锁 rehash 策略包括三个步骤:

#初始化 (Initialization)

首先, HotRing 创建一个后台 rehash 线程. 该线程初始化一个新的哈希表, 其大小是旧表的两倍, 并通过共享 tag 的最高位来划分数据. 如论文图 9(a) 所示: 旧表的一个桶对应旧头指针, 而新表中对应有两个新头指针. 哈希位数从 k 位扩展到 k+1 位. HotRing 依据 tag 范围划分数据. 假设哈希值共有 n 位, tag 范围为 [0, T) (其中 T = 2^(n-k)), 则两个新头指针分别管理 [0, T/2) 与 [T/2, T) 两段数据.

同时, rehash 线程会创建一个 rehash node, 其中包含两个子 rehash 条目, 分别对应两个新头指针. 每个 rehash 条目的格式与普通数据条目相同, 只是不存储有效的键值对. HotRing 通过条目中的 Rehash 位来区分 rehash 条目. 在初始化阶段, 两个子 rehash 条目的 tag 分别设置为不同值, 如图 9(b) 所示, 其值分别为 0 与 T/2.

#拆分 (Split)

在拆分阶段, rehash 线程通过把两个 rehash 条目插入原环, 实现对该环的逻辑切分. 如图 9© 所示, rehash 条目分别插入在条目 B 与条目 E 之前, 成为划分 tag 范围的边界.

当这两个插入完成后, 新哈希表被激活. 此后, 新的访问请求从 New Table 出发, 需要通过比较 tag 来选择对应的新头指针; 而原来已经在执行中的访问仍然可以从 Old Table 出发, 并通过识别 rehash node 的方式继续正确访问数据. 因此, 在不影响并发读写的情况下, 所有数据依然可达.

到这一阶段为止, 访问路径已经在逻辑上被分裂成两条, 因此一次查找至多只需扫描原来约一半的环. 例如, 若访问条目 F, 则遍历路径可以是: Head1 → E → F.

#删除 (Deletion)

在这一阶段, rehash 线程删除 rehash node (如图 9(d) 所示). 在此之前, rehash 线程必须维护一个过渡期, 以确保所有从旧表发起的访问都已经结束; 这类似于 RCU 同步原语中的 grace period. 待所有访问结束后, rehash 线程就可以安全地删除旧表以及 rehash 节点.

需要指出的是, 这一过渡期只会阻塞 rehash 线程本身, 而不会阻塞访问线程.

#4 评估

本节使用基于真实工作负载特征的基准测试来评估 HotRing 的性能. 具体而言, 我们比较了 HotRing 与无锁链式哈希以及其他基线系统在吞吐量和可扩展性方面的表现, 并通过更细粒度的实验来说明 HotRing 中关键设计的有效性.

#4.1 实验设置

#环境

实验运行在一台由两颗 Intel® Xeon® CPU E5-2682 v4 (2.50GHz) 构成的机器上. 该机器具有:

2 个 socket;
每个 socket 16 个核心;
共 64 个超线程;
256GB RAM;
操作系统为 CentOS 7.4, Linux 3.10 内核.

为了获得更好的性能, 我们将每个线程绑定到对应核心. 论文表 1 总结了该机器的硬件配置.

#工作负载

我们使用 YCSB core workloads 进行实验, 但不包含涉及 scan 操作的 workload E. 对于每个条目 (即键值对), 我们将 key 大小设为 8 字节; value 大小分别设为 8 字节与 100 字节, 对应原地更新和读复制更新 (RCU) 两种场景.

在每轮测试中, 载入的 key 数量固定为 2.5 亿. 通过调整 key-bucket ratio (即 key 数除以 bucket 数), 来控制冲突链的平均长度. 此外, 我们调节 YCSB 中 Zipfian 分布参数 q, 生成模拟“日常热点场景”和“极端热点场景”的工作负载. 论文表 2 给出了不同热点定义 (即最热前 a 比例条目) 与不同 Zipf 参数下的热点访问比例.

回顾图 1 中生产环境的访问分布, 我们观察到:

对于日常场景, q 大致落在 [0.9, 0.99];
对于极端场景, q 大致落在 [1, 1.22].

因此, 我们选取 q = 0.99 和 q = 1.22 作为代表值.

#基线系统

为了更好地展示 HotRing 中热点感知设计的优势, 我们实现了一个无锁链式哈希索引作为基线 (Chaining Hash). 该结构修改自 Memcached 的哈希结构, 并使用 CAS 原语将新条目插入到冲突链头部.

我们还与以下系统进行比较:

FASTER 的 C++ 版本 (并确保所有数据均驻留内存) ;
Masstree, 一种高性能内存范围索引, 代表非哈希型 KVS;
此外, 作为参考, 我们也纳入了基于锁的 Memcached.

需要注意的是, 索引结构的内存占用会显著影响性能. 为了保证公平性, 我们严格使各方案的索引内存开销保持一致.

除非特别说明, 在每个测试中我们使用如下默认设置:

64 线程;
8 字节 value;
YCSB workload B;
q = 1.22;
key-bucket ratio = 8 (针对 HotRing).

#4.2 与现有系统的比较

#整体性能

论文图 10 展示了所有方案在不同 YCSB 工作负载上的系统整体吞吐量. 我们运行了 HotRing 的两个变体:

HotRing-r: 采用随机移动策略;
HotRing-s: 采用统计采样策略.

与其他系统相比, HotRing 在所有工作负载上的吞吐量都更高, 尤其是在 workload B 和 C 上优势明显. HotRing-s 相比其他方案可实现 2.10× 到 7.75× 的提升. 其在单线程下达到 12.90M ops/sec, 在 64 线程下达到 565.36M ops/sec, 这说明它具有良好的可扩展性.

此外, HotRing 在插入操作上也保持优势. 对于包含大量插入的 YCSB workload D 与 F, HotRing-s 相比其他方案可实现 1.81× 到 6.46× 的提升. 这是因为, 有序环结构通过提前终止加速了条目定位, 而 tag 字段降低了排序带来的成本. 虽然 HotRing-r 的热点识别准确率低于 HotRing-s (约差 7%), 但其整体性能仍显著优于其他系统.

#冲突链长度

论文图 11(a) 给出了在改变冲突链长度时, 不同方案的吞吐量变化. 我们将 key-bucket ratio 从 2 调整到 16, 这意味着哈希表中的冲突越来越严重.

可以看到, 当 key-bucket ratio 为 2 时, Chaining Hash 和 FASTER 具有较好的性能. 这是因为当冲突链较短时, 热点项的额外内存访问开销相对较小, 此时 cache 的作用 (特别是对 FASTER) 更加明显. 然而, 随着冲突链增长, 频繁访问热点项会严重拉低 Chaining Hash 和 FASTER 的性能. 相较之下, HotRing 即便在链较长时仍能保持较高性能.

具体而言:

当 key-bucket ratio = 2 时, HotRing 的读吞吐量分别达到 Chaining Hash 与 FASTER 的 1.93× 和 1.31×;
当该比值增至 16 时, 这一性能差距扩大为 4.02× 和 3.91×.

其原因在于, HotRing 把热点项放在更靠近头部的位置, 从而减少所需的内存访问次数. 这种设计也更具 cache-friendly 特性: 只需缓存头指针和热点项即可, 从而获得更高性能. 因此, 我们得出结论: HotRing 由于其热点感知设计, 在性能与可扩展性上都更优.

#访问偏斜度

论文图 11(b) 展示了当 Zipfian 参数 q 变化时, 各方案的吞吐量表现. 我们将 q 从 0.5 调整到 1.22, 这意味着工作负载中的热点问题变得越来越严重.

可以看到, 由于缺乏热点感知设计, Chaining Hash 和 FASTER 的性能随着 q 增大并没有显著提升. 相反, HotRing 的性能随着 q 的增加而显著提升, 尤其是在 q 大于 0.8 时更为明显. 即便当 q 落在 [0.5, 0.8] 这一热点问题相对较弱的区间时, HotRing-s 仍然优于其他方案. 这是因为 HotRing-s 能够处理“一个冲突环中存在多个热点”的情形. 当多个条目具有相近的访问频率时, HotRing-s 能够找到最佳头指针位置, 以获得最优性能 (第 3.2.2 节) ; 而在这种情形下, HotRing-r 则无法选择最优位置, 导致头指针移动被频繁触发.

#RCU 操作

为了更突出地展示 RCU 的性能, 我们使用 YCSB 生成写密集工作负载, 并将 value 大小设为 100 字节 (包括 50% 写和纯写两种情况). 论文图 12 给出了在涉及 RCU 操作时各方案的吞吐量.

在该实验中, 我们进一步说明了 HotRing 对 RCU 操作进行特殊处理的必要性 (第 3.2.2 节). 其中:

HotRing-s 表示统计采样策略在 RCU 更新时会增加前驱条目的计数;
HotRing-s(w/o) 表示不区分 RCU 的普通策略.

首先, HotRing-s(w/o) 在所有情况下都表现较差, 甚至比 Chaining Hash 和 FASTER 更差. 这是因为 HotRing-s(w/o) 在执行热点条目的 RCU 操作时, 必须遍历整个冲突环以找到前驱条目.

而在 HotRing-s 中, 经优化的热点计数策略显著提升了 RCU 性能. 需要注意的是, 当 key-bucket ratio = 2 时, HotRing-s 的性能略慢于 FASTER. 这是因为热点条目在头指针指向位置之后的第二个槽位, 访问时需要额外一次内存访问; 此外, 完成 RCU 还需要额外一次 CAS (设置 Occupied 位). 但随着冲突条目数持续增加, 这些问题会被明显缓解. 例如, 当 key-bucket ratio = 8 时, HotRing-s 的吞吐量比 Chaining Hash 和 FASTER 高 1.32×.

#4.3 对关键设计的细致分析

本节将 HotRing 与传统链式哈希进行比较, 以分析热点感知设计所带来的优势.

#开销分解

我们收集了工作负载执行过程中不同函数的开销分解. 论文图 13 给出了在 key-bucket ratio = 8 时, 一次读访问在 HotRing 与 Chaining Hash 中的平均开销分布. 图中的开销项包括:

HeadPointer: 定位对应冲突环 / 链头指针的开销;
HeadItem: 访问头项的开销;
Non-HeadItem: 访问非头项的开销;
HashValue: 计算哈希值的开销;
Benchmark: 读取并解释工作负载命令的开销;
Other: 内核等其他系统开销.

可以看到, 在 Chaining Hash 中, 主要开销来自 Non-HeadItem 访问: 当 q = 1.22 / 0.99 时, 这部分开销约为 193ns / 660ns. 这说明在链式哈希中, 热点项往往均匀分布在冲突链中, 从而显著提高了访问成本. 相比之下, HotRing-r 和 HotRing-s 都显著降低了 Non-HeadItem 开销. 尤其是 HotRing-s, 在 q = 1.22 / 0.99 时, 该开销约为 10ns / 136ns. 由于 Non-HeadItem 的比例与热点识别准确率负相关, 这说明 HotRing-s 的热点识别精度更高, 能够将更多热点项放置到头部附近.

#反应延迟

反应延迟是衡量热点识别策略的重要指标之一. 论文图 14 展示了热点发生迁移后, 系统吞吐量随时间的变化趋势 (使用 workload C). 可以观察到, HotRing-r 的反应速度快于 HotRing-s, 它通常在不到 2 秒内就达到稳定状态; 然而, 由于其热点检测不够准确, 其峰值吞吐量低于 HotRing-s. Chaining Hash 则不受影响, 因为它不具备热点感知能力.

#读 miss

我们进一步评估两种方案处理读 miss 的吞吐量, 如论文图 15(a) 所示. 可以看到, 随着链长增加, HotRing 与 Chaining Hash 的性能差距逐渐扩大. 具体而言:

当 key-bucket ratio = 2 时, HotRing 提升约 1.17×;
当 key-bucket ratio = 16 时, 提升达到 1.80×.

其原因在于: HotRing 平均只需比较约一半条目即可完成查找 (如图 5 所示), 而 Chaining Hash 需要访问链中的全部条目.

#参数 `R`

回顾第 3.2 节, 参数 R 的选取会影响头指针移动频率. 若 R 过小, 则热点识别反应快, 但会引入更多频繁且无效的头指针移动; 若 R 过大, 则对热点迁移的响应过慢. 论文图 15(b) 展示了不同场景下 R 对整体吞吐量的影响. 实验表明, 当 R 过小或过大时, 性能都会略有下降; 在实践中, 作者将 R 设为 5, 作为吞吐量与反应速度之间的平衡点.

#尾延迟

HotRing-s 需要进行统计采样, 而在采样过程中, 最后一个线程还需计算访问频率以确定最佳头指针位置. 因此, 可能会存在额外计算导致的长尾访问. 论文图 16 展示了 10 万次访问的延迟分布.

当 q = 1.22 时, 99 百分位响应时间约为 2µs, 但最长尾部访问可达 8.8µs;
当 q = 0.99 时, 99 百分位响应时间约为 3µs, 长尾可达 9.6µs.

需要指出的是, 这种长尾访问部分来源于实现中的简化选择; 若将额外计算迁移到专门的后台线程中, 长尾现象仍有进一步缓解空间.

#无锁 Rehash

Rehash 是保证不断增长的哈希表保持稳定性能的重要机制. 我们构造如下场景来评估 HotRing 的无锁 rehash: 初始状态下加载 2.5 亿 个 key, key-bucket ratio = 8; 随后使用一个包含 50% 读 (q=1.22) 和 50% 插入 的 YCSB 工作负载, 模拟哈希表持续增长. 论文图 17 展示了在发生 rehash 时 HotRing 随时间变化的性能.

在图中, I, T 和 S 分别表示 rehash 的初始化 (Initialization) , 过渡期 (Transition) 和拆分 (Split) 阶段. 可以看到, 连续两次 rehash 能够在数据规模持续增长时保持吞吐量稳定. rehash 期间的短暂下降, 主要归因于新哈希表刚开始工作时暂时缺乏充分的热点感知状态.

#5 相关工作

大量已有工作关注 KVS 索引结构的设计. Memcached 是最广泛使用的分布式键值存储之一, 被许多公司使用. 然而, 由于频繁的锁竞争, 其多线程性能并不理想. 围绕 Memcached, 文献中已有大量工作作出重要改进. 通过实现无锁设计和 cache-friendly 优化, 它们达到了更高的并发性与吞吐量. 其中, FASTER 是当时最先进的无锁实现之一.

在热点感知方面, Splay Tree 是一项具有启发性的经典工作. 它通过根据最近访问情况调整结构, 以优化对近期访问条目的访问. 然而, Splay Tree 基于锁的设计使其不适合高度并发的场景.

此外, 还有许多工作探索如何将系统设计更好地与新型硬件结合, 例如 FPGA, 支持 RDMA 的网卡, GPU, 低开销用户态 TCP 实现, 以及带有硬件级可靠数据报能力的 InfiniBand. 与此同时, 为了支持快速内存分配 (特别是服务于插入和删除), 还有许多协议采用了无锁内存管理方法, 这些方法也可用于避免 ABA 问题.

需要指出的是, 这些面向硬件和内存管理的优化与索引结构设计本身是正交的, 因此我们也可以将这些思想引入 HotRing, 以进一步提升其性能.

#6 结论与未来工作

在现实部署中, KVS 中的热点问题非常常见, 而且近年来愈发严重. 例如, 为了提供高可用服务, 阿里巴巴的 NoSQL 产品 Tair 不得不部署多于正常需要的机器, 以应对热点的突然出现. 因此, 我们探索了设计热点感知内存 KVS的机会与挑战.

基于上述洞察, 我们提出了一种名为 HotRing 的哈希索引, 其针对“大量并发访问集中于少量条目”的场景进行了优化. 它通过将桶头指向频繁访问的条目, 来动态适应热点迁移. 在大多数情况下, 热点项可以在两次内存访问内被检索到. HotRing 在设计中系统性地采用了无锁结构, 不仅覆盖常规哈希操作, 也覆盖 HotRing 特有操作.

大量实验表明, 在高度偏斜的工作负载下, 我们的方法相较于其他内存 KVS 可实现 2.58× 的吞吐量提升. 目前, HotRing 已成为 Tair 的一个子组件, 并在阿里巴巴集团内被广泛使用.

目前, HotRing-r 主要面向每条链只有单一热点的情形, 而 HotRing-s 还能够处理多个热点. 在大多数情况下, 可以通过 rehash 缩短链长来缓解多热点问题; 而对于某些该方法难以处理的极端情形, 作者将寻找更合适的解决方案留作未来工作.

#文件说明

本次生成的精译版文件路径:

/home/frezcirno/.openclaw/workspace/papers/HotRing-A-Hotspot-Aware-In-Memory-Key-Value-Store-中文精译版.md

同目录下还包括:

原始 PDF: /home/frezcirno/.openclaw/workspace/papers/hotring-fast20.pdf
提取文本: /home/frezcirno/.openclaw/workspace/papers/hotring-fast20.txt
通顺整理版翻译: /home/frezcirno/.openclaw/workspace/papers/HotRing-A-Hotspot-Aware-In-Memory-Key-Value-Store-中文翻译.md

#摘要

#1 引言

#主要贡献

#2 背景与动机

#2.1 哈希索引与热点问题

#2.2 热点感知的潜在收益

#2.3 挑战与设计原则

#3 HotRing 的设计

#3.1 有序环哈希索引

#3.2 热点迁移识别

#3.2.1 随机移动策略

#3.2.2 统计采样策略

#索引格式

#统计采样

#热点调整

#RCU 场景下的写热点

#3.2.3 热点继承

#3.3 并发操作

#读 (Read)

#插入 (Insertion)

#更新 (Update)

#删除 (Deletion)

#头指针移动 (Head Pointer Movement)

#3.4 无锁 Rehash

#初始化 (Initialization)

#拆分 (Split)

#删除 (Deletion)

#4 评估

#4.1 实验设置

#环境

#工作负载

#基线系统

#4.2 与现有系统的比较

#整体性能

#冲突链长度

#访问偏斜度

#RCU 操作

#4.3 对关键设计的细致分析

#开销分解

#反应延迟

#读 miss

#参数 R

#尾延迟

#无锁 Rehash

#5 相关工作

#6 结论与未来工作

#文件说明

#参数 `R`