[SIGMOD'27] HierarchicalKV: A GPU Hash Table with Cache Semantics for Continuous Online Embedding Storage 阅读笔记

发表于 2026-08-09 分类于 hpc 阅读次数：本文字数： 17k 阅读时长 ≈ 1:01

作者：

NVIDIA: Haidong Rong, Jiashu Yao, Matthias Langer, Shijie Liu, Mengyao Xu, Fan Yu, Minseok Lee, Zehuan Wang, Even Oldridge
Tencent: Li Fan
Vipshop: Dongxin Wang
BOSS Zhipin: Jia He, Jinglin Chen
ByteDance: Jiaheng Rang
Snap: Julian Qian

#0. 摘要

传统 GPU 哈希表会保留所有插入的 Key – 这一 Dict 假设在 Embedding Table 经常超出单个 GPU 容量时会浪费稀缺的 HBM。我们打破了这一假设，采用了基于 Cache 语义的存储方式，其中策略驱动的淘汰成为了一等公民操作。我们提出了 HierarchicalKV（HKV） 这一通用 GPU 哈希表库，它的正常运行模式基于 Cache 语义：每次完整的更新或插入操作都会通过淘汰或拒绝操作就地解决，而不是通过 Rehash 处理或因容量不足而失败。 HKV 结合了四种核心机制：GPU Cache-Line 对齐的桶结构、基于分数的原地 Update/Insert 操作、基于分数的动态双桶选择，以及三角色组并发控制。此外，HKV 还采用了分层 Key-Value 分离的设计，从而能够在超出 HBM 容量的情况下实现扩展。

在一块 NVIDIA H100 NVL GPU 上，HKV 每秒能够处理高达 3.9 B 个 KV 对。在负载因子为 0.50–1.00 的情况下，性能表现仅有 5% 的波动。与 WarpCore 相比，HKV 在吞吐量上高出 1.4 倍；在基于间接处理的 GPU 基准测试中，性能提升可达 2.6–9.4 倍。

自 2022 年 10 月开源以来，HKV 已被集成到多个开源推荐系统中。

#1. 引言

现代的推荐、搜索和广告系统（Naumov 等人，2019 年）依赖于深度学习模型。这些模型中的 Embedding 表负责将稀疏特征映射到密集向量上，这一过程占据了大量的内存资源。通常，这些 Embedding 表占用的内存远远超过单颗 GPU 所能承受的最大内存容量。

例如，1B 个 64-dim float32 key 会占用 ~256GB 的内存，而一块 NVIDIA H100 NVL 卡上只有 96GB HBM。

持续的在线训练进一步增加了内存使用的压力，因为需要不断处理新增的 Embedding，而内存预算却始终有限。

所有被广泛使用的 GPU 哈希表 – 如 cuCollections（NVIDIA，2020 年）、WarpCore（Jünger 等人，2020 年）、BGHT（Awad 等人，2023 年）、WarpSpeed（McCoy 和 Pandey，2025 年）以及 Hive（Polak 等人，2025 年）-- 都采用 Dict 模型：每个插入的键都必须被保留下来。当负载因子接近 1.0 时，查询链会延长，吞吐量会下降，系统不得不进行 Rehash 处理，否则就会失败。这些限制是 Dict 模型固有的：只要要求保留每个 Key，那么在高负载情况下的性能下降以及外部维护工作就难以避免。我们的测量结果显示，当负载引子 $\lambda$ 接近 1.0 时，查找吞吐量会下降 31% 到 100%（参见第 5.2 节），这使得 Dict 语义的哈希表不适合用于需要持续填充的 Embedding 缓存系统。

我们注意到，将存储功能建模为 Cache 比建模为 Dict 更为合适：幂律访问模式意味着只需保留高价值的条目，而淘汰低价值的条目则有助于保持模型的稳定性。由于内存资源有限，淘汰低价值条目成为必然且频繁发生的操作。这种从 Dict 语义到 Cache 语义的转变，从根本上改变了设计约束：完整的表不再被视为错误状态，而是正常的运行状态。就像 B 树索引（Dict 语义）与缓冲池（Cache 语义）之间的区别导致了数据库系统中不同的并发控制与替换策略一样，同样的语义划分也导致了 GPU 哈希表设计的根本差异。采用 Cache 语义开辟了新的设计空间，但同时也带来了四个具体挑战（参见第 2.4 节）：

将每个 Key 的查找操作限制在固定的 GPU 内存事务数量之内。
在不重复处理的情况下完成全部更新操作（C2）
在有界相联结构的情况下保留高价值的数据条目（C3）
在混合工作负载环境下将结构化的写入操作与非结构化的写入操作分开处理（C4）。

为了应对这些挑战，我们提出了 HierarchicalKV (HKV) – 首个通用的 GPU 哈希表库。该库的满容量操作契约采用 Cache 语义：每次对满 Bucket 进行 Update/Insert 操作时，都会通过淘汰或拒绝来直接修改数据，而无需进行 Rehash 处理或外部维护。 HKV 将四种协同设计的机制整合为一套完整的架构体系。

单桶约束型 Cache-Line 对齐的桶结构（#3.2）：这种结构将每个 Key 的所有候选值压缩为 128 字节的 Digest，这些 Digest 仅占用一个 GPU 的 L1 Cache-Line 空间。这样一来，在单次内存事务中就能实现每个桶的完整检索，无论是在单桶模式下还是双桶模式下都是如此。
基于分数的原地 Update/Insert 操作语义（#3.3）：桶级局部分数比较、并发控制以及比较与交换（CAS）操作直接集成到插入路径中，因此整个表的插入操作可以在内部完成，无需额外的淘汰流程。
基于分数的动态双桶选择算法（#3.4）：该算法扩展了基于二选一策略的优化方法（Azar 等人，1994 年；Mitzenmacher，2001 年），将这种策略从负载均衡扩展到 GPU 哈希表中的淘汰策略优化。该算法能够解决在单桶模式下因生日悖论导致提前淘汰未使用的内存块的问题，同时能在 $\lambda = 1.0$ 情况下实现 99.4% 的最高分数保留率。
三角色组并发控制（#3.5）：将 Reader、Updater 和 Inserter 角色分离，并采用 CPU-GPU 双层锁机制。所有结构性的修改都集中在 Inserter Kernel 中完成，因此Reader 和 Updater Kernel 无需进行 CAS 操作或淘汰逻辑处理 – 这大大降低了每个 Kernel 的复杂性，并使得每种访问模式都能得到独立优化。

作为一种可扩展性的实现机制，分层 Key-Value 分离结构（#3.6）将容量扩展到了 HBM 之外：键、 Digest 和分值分别存储在 HBM 中，而值则通过基于位置的地址映射被存储到固定的Host内存（HMEM）中。这四种核心机制协同工作，共同实现了三种特性，而这些特性是之前所有 GPU 哈希表所不具备的：在每次加载时，每个桶的查找操作都会执行固定的操作；能够在不 Rehash 的情况下实现满容量原地 Update/Insert 操作；以及能够同时执行读取、更新和插入操作，并且这些操作由具有角色隔离功能的 Kernel 来完成。分层 Key-Value 分离结构还适用于混合 HBM 和 HMEM 的部署场景，同时仍然将键值处理任务保留在 GPU 上。

我们对 NVIDIA H100 NVL GPU 的评估表明，HKV 的 find() 吞吐量高达 3.9 B KV/s，其在负载因子为 0.50–1.00 的情况下表现稳定，波动仅为 5%。其查找吞吐量相当于 WarpCore 的 1.4×，而在基于间接寻址的设计中，吞吐量可达到 2.6–9.4×（即使用 (key, index) 对并结合单独的值收集方式：BP2HT、BGHT、cuCollections））。自 2022 年 10 月开源以来，HKV 已集成到 NVIDIA Merlin HugeCTR、TFRA（TensorFlow SIG Recommenders）以及 NVIDIA RecSys 示例中。本文介绍了 HKV Cache 语义架构的设计原理、正式特性以及全面的评估结果。

本文的贡献包括：

我们分析了 GPU Embedding 缓存工作负载，并识别出推动系统从 Dict 语义转向 Cache 语义的四项挑战 C1–C4（#2）。
我们设计了一种与 GPU Cache-Line 对齐的桶结构，只需一次固定的内存事务即可明确判定每桶 miss ：单桶约束将一个键的完整候选空间压缩为 128 个单字节 Digest，并恰好装入一条 GPU L1 Cache-Line。一次 Cache-Line 加载在这里构成完整的负向查找，而不仅是可变长度探测链中单个步骤的加速；这种对齐在 64 B CPU Cache-Line 上无法实现（#3.2）。
我们提出基于分数的原地 Update/Insert 路径，将分数比较、准入控制和 CAS 提交融合为一次 GPU 操作，在表内处理每次满桶插入，从而消除先前具备淘汰感知能力的设计所需的独立淘汰数据结构、多 Kernel 流水线以及 CPU 参与（#3.3）。
我们提出基于分数的动态双桶选择，将二选一范式从负载均衡扩展到 GPU 哈希表中的淘汰质量优化。在满容量时，两个桶同样满，基于负载的 P2C 会退化为随机选择；HKV 则比较候选桶的最低分数，恢复有意义的选择维度。该维度仅在 Cache 语义下成立，并回收生日悖论碰撞浪费的 ~34% HBM，在 $\lambda=1.0$ 时实现 99.4% 的 top- $N$ 分数保留率（#3.4）。
我们设计了区分结构性与非结构性 GPU 写入的三角色组并发控制，将 Reader、Updater 和Inserter 角色分离；这种分离平面在此前所有基于角色的设计中均不存在。该机制由 CPU–GPU 双层锁协调；据我们所知，这是首个跨越 CPU 与 GPU 执行域的哈希表并发协议，相比读写锁可实现最高 4.80× 的吞吐量（#3.5）。
我们实现分层 Key-Value 分离，以支持 HBM+HMEM 混合部署（#3.6）；在 H100 NVL 上与四种基线进行了评估（#5），并报告了 HKV 自 2022 年 10 月以来在 HugeCTR、TFRA 和 NVIDIA RecSys Examples 中的开源集成情况。

#2. 背景与动机

我们讨论了 Embedding 存储需求的问题（第 2.1 节）、GPU 哈希表的设计方案（第 2.2 节）、在高负载情况下字典与语义处理的性能问题（第 2.3 节），以及促使 HKV 采用 Cache 语义架构的四大挑战（第 2.4 节）。

#2.1 推荐系统中的 Embedding 存储

图 1. 将查找 Embedding 流程集成到推荐模型中。稀疏的分类特征通过 Embedding 表被映射为密集向量，而这些 Embedding 表正是模型中主要的内存消耗部分。在线训练过程中，新的 key 不断被引入，而内存预算却始终有限。

这些特征 ID 占据了一个稀疏的 uint64 键空间，且存在幂律访问现象（Naumov 等人，2019 年）。因此，将它们 Embedding 到存储中非常适合用于 Cache 语义处理（见图 1）。

#2.2 GPU 哈希表设计方案

GPU 哈希表充当了 Embedding 存储的索引基础结构。其设计涉及三个相互关联的决策：碰撞解决策略、探测距离限制，以及语义承诺（即 Dict 式存储与 Cache 式存储之间的选择）。

#2.2.1 开放地址 vs 分桶

开放地址 方案（如 WarpCore（Jünger 等人，2020 年）、WarpSpeed（McCoy 和 Pandey，2025 年）、cuCollections（NVIDIA 公司，2020 年））通过连续探测各个槽位来解决冲突问题，其探测距离不受限制。
分桶方案（如 Hive（Polak 等人，2025 年）、BP2HT（Awad 等人，2023 年））则将槽位分组到固定大小的桶中，探测时遵循一定的边界距离。

这两种方案都采用 Dict 语义：每个 Key 都必须被保留下来，如果整个表写满了，可能会导致 Rehash 或插入失败 - 这对于持续接收数据的 Embedding 缓存来说是不可接受的。表 1 总结了这两种设计方案的差异；目前现有的 GPU 哈希表并未提供内置的淘汰机制或相关的策略接口。

表 1. GPU 哈希表的设计空间。与以往的所有 GPU 哈希表不同，HKV 采用了基于 Cache 语义的满容量机制。它直接将基于分数的准入机制与淘汰操作整合到了插入操作的流程中。

系统	碰撞	探针	语义	特征淘汰	LF
WarpCore (Jünger 等人，2020 年)	开放地址法	无上界	`Dict`	无	<1.0
WarpSpeed (McCoy 和 Pandey，2025 年)	开放地址法	无上界	`Dict`	无	<1.0
cuCollections (NVIDIA 公司，2020 年)	开放地址法	无上界	`Dict`	无	<1.0
BGHT (Awad 等人，2023 年)	分桶	k×b	`Dict`	无	∼0.85B
P2HT (Awad 等人，2023 年)	分桶 P2C	2×16	`Dict`	无	∼0.90
Hive (Polak 等人，2025 年)	分桶 CuckooHash	2×32	`Dict`	无	∼0.95
HKV	分桶	128	`Cache`	支持	1.0

#2.3 Workload 分析：持续在线插入

图 2 总结了持续在线插入场景下的三个关键工作负载特性。

图 2. 连续在线 Embedding 处理的工作负载特性。(a) 随着新特征的不断引入，负载水平呈单调上升趋势；在没有淘汰机制的情况下，负载会达到上限。(b) 由于新出现的特征在探索阶段占据主导地位，因此 miss 率仍然很高。© 在开放地址方案中，当负载水平超过 0.8 时，探测距离会呈超线性增长，这会导致 GPU 上的 Warp Divergence。

在 Dict 语义哈希表中，吞吐量会逐渐下降。在持续插入数据的过程中，由于 $\lambda$ 的值增加，查询所需的探测距离也会延长。一旦哈希表达到满负荷状态，系统就需要 Rehash 数据，否则就会插入失败。当 $\lambda$ 从 0.25 上升到 1.00 时，WarpCore 系统的性能下降幅度为 90%，BGHT 为 31%，而 cuCollections 则下降了 100%（见图 6）。而 HKV 的性能下降幅度则保持在 <1% 范围内。

#2.4 挑战

上述分析引发了四个设计上的挑战：

C1：固定工作量查询（#3.2）：Dict 语义哈希表的性能会下降 31-100%，因为 $\lambda \rightarrow 1.0$ （见图 6）。而 Embedding Cache 必须持续以高 $\lambda$ 的情况下持续运行。因此，每个操作都必须通过固定数量的内存事务来完成，而这一过程与 $\lambda$ 无关。
C2：满容量原地 Update/Insert（#3.3）：不断有新的 Embedding 数据涌入，这就要求处理满容量桶的原地插入。而基于 Dict 语义的存储方式要么无法完成插入操作，要么会导致资源浪费 – 这会占用 GPU 资源，并暂时增加内存需求。在严格的 HBM 预算限制下，这种存储方式是不可接受的。因此，基于 Cache 语义的存储方式必须采用在线移除或拒绝插入的方式来处理满容量桶的原地插入。
C3：在有界相联结构的情况下进行留存操作（#3.4）：淘汰操作并不平等：淘汰一个受欢迎的 Embedding 对象会导致昂贵的重计算或远程获取操作。在单桶约束的情况下，生日悖论会导致浪费 ~34% 的资源；因此，需要使用双桶方案，并采用基于分数的桶选择策略，以最大化留存高价值条目的能力。
C4：混合工作负载的并发控制（#3.5）：在生产系统中，同时需要从重叠的推理和训练 Kernel 中进行读写操作（Wang 等人，2022 年）。由于最多可以有 270k 个驻留的 GPU 线程，因此粗粒度读写锁机制会成为瓶颈，因为这些锁会串行处理非结构化数据的更新操作。

在实际应用中，Embedding 表的容量往往仍然超过单 GPU 的 HBM 容量限制。因此，我们将分层 Key-Value 分离机制（参见第 3.6 节）视为一种扩展手段，它建立在核心缓存与语义契约的基础上，而不是作为上述四个核心挑战之一来处理的。

#2.4.1 Cache 语义哈希表

定义 2.1（Cache 语义哈希表）。如果一个哈希表满足以下条件，则称为 Cache 语义哈希表：

CS1： 每次完整的插入操作都会通过策略驱动的淘汰或拒绝来直接完成；
CS2： 没有任何操作会触发 Rehash 或外部容量管理；
CS3： 查找成本独立于插入总次数。

没有任何 Dict 语义哈希表能够满足这三个条件：CS1 要求哈希表具有满容量 Resolution，而 Dict 语义则禁止这种做法。本文其余部分介绍了一种 GPU 哈希表库的设计与评估过程，该哈希表库在正常满容量运行时满足 CS1-CS3。

#3. 系统设计

HKV 遵循的是 Cache 语义 (淘汰操作是一种由策略驱动的一等公民操作) 而非 Dict 语义 (所有插入都必须被保留，满表会触发 Rehash 或插入失败)。在持续在线插入的情况下，当负载因子达到 $\lambda = 1.0$ 时，每个满桶的 Update/Insert 操作都会通过基于分数的淘汰或拒绝来直接完成；不会出现因容量限制而导致的插入失败，关键路径上没有 Rehash，同时也不需要任何外部维护流程。

MemcachedGPU（Hetherington 等人，2015 年提出）在网络服务级别实现了 Cache 语义，采用单一的 LRU 策略，并且由 CPU 负责处理淘汰操作；而 HKV 则作为一个库级 GPU 哈希表原语来运行，它具有单一的 CAS 淘汰机制、五种可插件的评分策略，以及零成本的准入机制 – 所有操作都完全在 GPU 上完成。

#3.1. 架构概述

HKV 是一个 GPU 哈希表库，提供 17 个与标准模板库兼容的接口（如 find, insert_or_assign, find_or_insert, insert_and_evict, assign, contains 等），底层通过分批 Kernel 调用实现，每次启动处理百万级别的 KV 对。如图 3 所示，每个操作都会：

计算 Murmur3 哈希值
在 HBM 中定位目标桶
基于 Digest 执行查找操作

对于 insert_or_assign 操作桶，已满时，Kernel还会扫描分数，并通过准入控制及 CAS 提交机制完成原地 Update/Insert 操作 – 这样就能在单次Kernel执行中完成查找、目标选择以及插入操作。

图 3. HKV 架构。Key、Digest 和分数存储于 HBM 中；而溢出值则通过零拷贝映射指针存储在 Pin 住的Host内存（HMEM）中。SSD/GDS 层（虚线表示）是一个架构上的扩展点。

协同设计理念。 这四个核心机制 – 单桶约束机制（#3.2）、基于分数的原地 Update/Insert 机制（#3.3）、动态双桶选择机制（#3.4），以及三角色组并发控制（#3.5） – 共同构成了一个相互关联的体系。这些机制的相互作用产生了三种系统级特性（参见表 2），而这些特性是任何单一组件都无法实现的：单桶约束机制能确保固定的 miss 工作量；在线 Update/Insert 机制能够实现写满时的处理能力；双桶选择机制能够弥补“生日悖论”下的数据保留问题；而将结构性修改限制在 Update/Insert 路径上，则能够实现三角色组并发。分层 Key-Value 分离机制（#3.6）进一步扩展了这一设计，使其成为支持扩展能力的一种手段。

表 2 列出了第 3.2 节至第 3.5 节中四种协同设计的机制的核心特性。而分级 KV 分离机制（第 3.6 节）则是一种基于这些核心特性的扩展功能。

系统	Miss 时仅需要 1 次事务	原地满容量处理	读/更新/插入并发
SwissTable/F14/BBC	✗	✗	n/a
MemC3	✗	✓	n/a
MemcachedGPU	✗	✓	n/a
FBGEMM TBE	✗	✓	✗
WarpCore/BGHT/BP2HT	✗	✗	✗
HKV	✓	✓	✓

#3.2 单桶约束 Cache-Line 对齐设计

之前的 GPU 哈希表采用可变长度的探测链结构（Jünger 等人，2020 年；Awad 等人，2023 年；Polak 等人，2025 年），或者多桶设计（Fan 等人，2013 年；Hegeman 等人，2024 年；Herlihy 等人，2008 年）。而 HKV 则能够在单次 Cache-Line 访问中处理所有 128 个候选（见表 3）。

HKV 的桶结构的关键设计理念是将每个 Key 的所有候选数据压缩成一个单一的、与 GPU L1 Cache-Line 对齐的单元。这样，当某个桶中的某个位置出现 miss 时，可以通过一次固定的内存事务来明确确定其原因。（在双桶模式下（#3.4），两个固定长度的内存事务可以分别处理两个桶中的候选数据。）

#3.2.1 单桶约束

HKV 使用基于 Murmur3 的、针对 GPU 优化的哈希函数，将每个 Key 映射到一个 128 槽位的桶中 – 不使用二级哈希，不设置 Overflow Chain，也不进行布谷鸟重定位。这个桶就代表了该键的全部候选空间。不同于仍需二次探测的有界探测设计（Herlihy et al., 2008；Panigrahy, 2005；Breslow et al., 2016；Awad et al., 2023；Polak et al., 2025），单桶约束可确保扫描一个桶后即能明确判定 miss 。

Cache 语义使得这种方案可行：高负载情况下，采用 Dict 语义无法实现单桶约束桶：已满且不存在 Overflow Chain，插入操作就会失败。 Cache 语义解决了这一问题 – 基于分数的淘汰机制会确定性地替换分数最低的条目，从而消除 Overflow Chain、Rehash 以及容量不足导致的失败。正是这种语义转变，使单桶约束在 $\lambda = 1.0$ 下成为可行方案，并进一步实现了下文所述的明确 miss 特性。

Adas 等人（Friedman 和 Mozes，2022 年）指出，采用淘汰机制的有界相联结构可维持 O(1) 的最坏情况查找复杂度。在 GPU 上，单次哈希消除了三种由架构特性引发的开销：

由于需要判断 “哪个桶包含这个 Key” 而导致的 Warp Divergence；
每次启动 Kernel 时，为数百万个键计算第二个独立哈希函数所带来的计算开销；
探测两个不相邻的桶所产生的非连续内存访问，从而导致 L1/L2 缓存压力加倍。

#3.2.2 Cache-Line 对齐的 Digest 数组

HKV 将单桶约束与面向 GPU 内存层次结构的内联指纹机制相结合：每个槽位存储一个 8 位 Digest （GPU 优化版 Murmur3 的第 32–39 位）。 HKV 将 Digest 单独存放在专为 GPU 的 128 B L1 Cache-Line 设计的连续数组中： 128 个单字节 Digest = 一次 Cache-Line 加载，从而可在单次内存事务中处理 128 个候选项。

在相似的 CPU 哈希表中：

SwissTable（Benzaquen et al., 2017）（每组使用 7 位 H2，通过 SSE 扫描）和 F14（Bronson and Shi, 2019）（使用 7 位 tag，通过 SIMD 分块过滤） – 将 tag 嵌入到固定大小的分组中，每个 64 B CPU Cache-Line 最多容纳 16 个条目；
BBC（Böther et al., 2023）在每个桶头部放置一个连续的 16 个 fingerprint 子数组以进行 SIMD 扫描，但其桶会跨越多个 Cache-Line ，并且在高负载因子下仍需进行溢出探测。
MemcachedGPU（Hetherington et al., 2015）将 8 位 hash 值嵌入到 ≥ 20 Bytes 的 Per-Entry Header 中，每次 miss 时需要跨多次 Cache-Line 加载检查最多 16 个候选槽位。

与 CPU 及此前的 GPU 设计相比，HKV 实现了每次事务 8× 的候选项覆盖范围。一次查找会执行 32 次 __vcmpeq4 比较；只有 Digest 匹配的槽位才会触发完整 Key 比较（误报率为 1/256 ，每次 miss 会产生 ∼0.5 次不必要的 Key 读取）。

#3.2.3 单次内存事务即可确定桶级别 miss

三项协同设计将 miss 路径的开销压缩至每桶仅需要头条 Cache-Line Load（图 4）：

Key-Digest 分离，将 128 个 Digest 紧凑排列在一条 128 字节的 GPU L1 Cache-Line 中；
单桶约束使这 128 个槽位构成该键的全部候选空间；
一次加载即可覆盖所有候选项；

在单桶模式下，由于该桶就是完整的候选空间，因此可在表级别确定 miss；双桶模式（#3.4）将候选空间扩展到两个桶（两次固定长度事务），同时提升留存质量。

在每个桶包含 $S=128$ 个槽位的单桶模式下，对于任意不在 $T$ 中的键 $k$ ， $\text{Find}(k)$ （算法 1）在恰好检查一个桶、执行 $S$ 次 Digest 比较和至多 $S \times 2^{−8} = 0.5$ 次预期完整键比较后返回 $\text{NotFound}$ ，仅使用一次 128 字节内存事务。

算法 1 总结了单桶的 Digest 加速查找路径。

算法 1：基于 Digest 加速的查找过程

输入： Key (k)，哈希表 (T)，包含 (B) 个桶，每个桶有 (S=128) 个槽位
输出： (\mathrm{Found}(v)) 或 (\mathrm{NotFound})

$\begin{array}{r l} 1 & h \leftarrow \mathrm{Hash}(k) \\[2pt] 2 & b \leftarrow h \bmod B \qquad \text{// 计算桶索引} \\[2pt] 3 & d \leftarrow h[31:24] \qquad \text{// 提取 8-bit Digest } \\[2pt] 4 & D[0:S-1] \leftarrow T.\mathrm{digests}[b] \qquad \text{// 加载 128 B Digest } \\[2pt] 5 & \hat d \leftarrow d \times \mathtt{0x01010101} \qquad \text{// 广播到 4 个 byte lane} \\[4pt] 6 & \mathbf{for}\ i \leftarrow 0\ \mathbf{to}\ S/4-1\ \mathbf{do} \\[2pt] 7 & \qquad m \leftarrow \mathtt{\_\_vcmpeq4} \left(D[4i:4i+3],\,\hat d\right) \qquad \text{// SIMD 4-way compare} \\[2pt] 8 & \qquad \mathbf{for\ each}\ j \in \mathrm{Matches}(m)\ \mathbf{do} \\[2pt] 9 & \qquad\qquad p \leftarrow 4i+j \\[2pt] 10 & \qquad\qquad \mathbf{if}\ T.\mathrm{keys}[b][p] = k\ \mathbf{then} \\[2pt] 11 & \qquad\qquad\qquad \mathbf{return}\ \mathrm{Found}\!\left(T.\mathrm{values}[b][p]\right) \\[2pt] 12 & \qquad\qquad \mathbf{end\ if} \\[2pt] 13 & \qquad \mathbf{end\ for} \\[2pt] 14 & \mathbf{end\ for} \\[4pt] 15 & \mathbf{return}\ \mathrm{NotFound} \end{array}$

表 3 量化了这一区别。此前的所有设计的 miss 开销都会随负载因子增加，或在容量已满时需要 Rehash；HKV 在包括 $\lambda = 1.0$ 在内的每种负载因子下都能实现恒定开销的 miss 处理。

表 3. 代表性负载因子下的 miss 路径 I/O 开销（每次负向查找的内存加载次数）。“-” 表示无法达到该负载因子（需要 Rehash）。先前系统的各行数据是根据已发表的探测结构推导出的示意性结构计数，并非在同一平台上测得的基准测试结果。 HKV 是唯一一种 miss 开销不受负载因子影响的设计。

设计	负载因子: 0.50	0.875	1.00
CPU(SwissTable, F14, BBC)	~2 次加载	~8 次加载	-
MemC3	2 次桶加载	2 次桶加载	-
WarpCore	~2 次探测	~8 次探测	-
BGHT	2 × 16 个槽位	2 × 16 个槽位	-
BP2HT	2 × 16 个槽位	2 × 16 个槽位	-
Hive	2 × 32 个槽位	2 × 32 个槽位	-
HKV（单桶）	1 次 Cache-Line 加载	1 次 Cache-Line 加载	1 次 Cache-Line 加载
HKV（双桶）	2 次 Cache-Line 加载	2 次 Cache-Line 加载	2 次 Cache-Line 加载

图 4. 单个 HKV 桶（128 个槽位）的内存布局。 Digest 数组恰好占用一条 GPU L1 Cache-Line （128 B），因此仅需一次 Cache-Line 加载，即可完成单个桶内的 miss 判断。Value 通过桶和槽位索引寻址（基于位置的寻址，#3.6）；无需为每个条目存储指针。

单桶约束可保证 miss 的代价恒定；下一小节将讨论桶被填满时的处理方式。

#3.3 基于分数的淘汰机制

在 Cache 语义下，桶写满并非错误，而是稳定状态。据我们所知，HKV 是首个将淘汰机制直接融合到 Insert 路径中的 GPU 哈希表，因此完全不需要任何外部淘汰流程（导出、排序、压实）。

#3.3.1 与以往具备淘汰感知能力的设计在架构上的区别

在此前所有内置淘汰机制的哈希表中：

CPHash（Metreveli et al., 2012）（LRU 链表，每条目 16 Bytes 的指针开销）；
MemC3 的 CLOCK（Fan et al., 2013）（每条目的引用位，以及外部时钟指针扫描）；
CacheLib（Berg et al., 2020）（侵入式钩子链表，每条目 ∼24 Bytes）；
FBGEMM TBE（Meta Platforms, Inc., 2019）（Multi-Kernel 淘汰流水线）；

辅助淘汰的元数据都构成了第二种数据结构，拥有独立的内存布局、遍历逻辑和同步域。 HKV 完全消除了这一辅助结构：分数数组就是淘汰元数据，桶就是淘汰范围，而 CAS 就是淘汰锁 – 这种统一在此前所有 GPU 哈希表中都不存在。

HashPipe（Sivaraman et al., 2017）将基于计数的淘汰机制 Embedding 嵌入到 Switch ASIC 上的单条目哈希阶段管道中；

HKV 与之共享路径内淘汰这一原则，但运行于包含 128 个槽位的 GPU 桶之上，并支持可插拔的评分机制和通用 KV 语义。

与最接近的工业级系统 FBGEMM TBE 对比，可以清楚地看出二者的差异：

FBGEMM 需要 Multi-Kernel 流水线（分别使用不同的 Kernel 处理缓存 miss、逐集合淘汰对象选择以及替换），而 HKV 采用通过 CAS 提交的单一就地 Update/Insert 路径；
FBGEMM 支持 2 种固定淘汰策略（LRU、LFU），而 HKV 不仅内置多种分数方式，还提供由调用方指定的自定义评分路径；
FBGEMM 的相联度为 8–32 路（取决于版本），而 HKV 采用与 GPU L1 对齐的 128 槽位桶，并通过 Digest 加速淘汰对象搜索。

进一步的差异在于特征准入控制：当传入 Key 的分数低于桶内最低分数时，系统会拒绝插入 – 表中将保留价值更高的条目，从而在对抗性访问模式下维持缓存质量。与 TinyLFU（Einziger et al., 2017）基于 Frequency-Sketch 的准入门控不同，HKV 的特征准入检查嵌入到桶局部的 Update/Insert 路径中，无需任何额外的数据结构。

#3.3.2 评分策略

编译期 ScoreFunctor 抽象，通过同一套内联 Update/Insert 机制实现 LRU、LFU、epoch-aware 和自定义分数，无需第二套淘汰数据结构（#5）。

#3.3.3 内联式桶内准入与提交

桶写满时，Kernel 会扫描全部 128 个分数，找出分数最低的槽位，并通过对 Key 字段执行 CAS 将其原子替换。该扫描采用异步 Prefetch 和双缓冲共享内存来隐藏 HBM 的延迟（#4.3）。

算法 2 对完整的 Update/Insert 路径进行了形式化描述。

算法 2 采用桶局部准入与淘汰的 Update/Insert 操作。 存在空闲槽位时直接插入（第 8 行桶）。已写满时，执行带准入控制的淘汰（第 10–13 行）；CAS 同时充当锁和提交机制（第 14 行）。

$\begin{array}{r l} & \textbf{输入：}\quad \text{Key } k,\ \text{value } v,\ \text{分数 } s,\ \text{哈希表 } T \\[2pt] & \textbf{输出：}\quad \mathrm{Inserted},\ \mathrm{Updated},\ \mathrm{Rejected},\ \text{or}\ \mathrm{Evicted}(k_{\mathrm{old}}) \\[6pt] 1 & \text{在桶 } b \text{ 中对 } k \text{ 执行 Algorithm 1} \\[2pt] 2 & \mathbf{if}\ k \text{ 位于槽位 } j\ \mathbf{then} \\[2pt] 3 & \qquad T.\mathrm{values}[b][j] \leftarrow v \\[2pt] 4 & \qquad T.\mathrm{分数s}[b][j] \leftarrow s \\[2pt] 5 & \qquad \mathbf{return}\ \mathrm{Updated} \\[2pt] 6 & \mathbf{end\ if} \\[4pt] 7 & e \leftarrow \text{桶 } b \text{ 中的第一个空槽位} \\[2pt] 8 & \mathbf{if}\ e \neq \mathrm{Nil}\ \mathbf{then} \\[2pt] 9 & \qquad \mathrm{Write}(k,v,s,d)\ \text{至槽位 } e \\[2pt] 10 & \qquad \mathbf{return}\ \mathrm{Inserted} \\[2pt] 11 & \mathbf{end\ if} \qquad \text{/桶/已满：淘汰路径} \\[4pt] 12 & m \leftarrow \underset{i}{\arg\min}\; T.\mathrm{分数s}[b][i] \\[2pt] 13 & \mathbf{if}\ s < T.\mathrm{分数s}[b][m]\ \mathbf{then} \\[2pt] 14 & \qquad \mathbf{return}\ \mathrm{Rejected} \qquad \text{// Admission control} \\[2pt] 15 & \mathbf{end\ if} \\[4pt] 16 & \mathbf{if}\ \mathrm{CAS} \left( T.\mathrm{keys}[b][m], k_{\mathrm{old}}, \mathrm{Locked} \right) = k_{\mathrm{old}} \ \mathbf{then} \\[2pt] 17 & \qquad \mathrm{Write}(k,v,s,d)\ \text{至槽位 } m \\[2pt] 18 & \qquad \mathbf{return}\ \mathrm{Evicted}(k_{\mathrm{old}}) \\[2pt] 19 & \mathbf{else} \\[2pt] 20 & \qquad \mathbf{goto}\ 12 \qquad \text{// CAS 失败时重试} \\[2pt] 21 & \mathbf{end\ if} \end{array}$

命题 3.2（活性）。 如果桶 $b$ 已满，且插入线程持有独占锁，则算法 2 会在 $O(B)$ 时间内终止，其中 $B=128$ 为桶容量。如果还满足 $s \ge s_{\min}(b)$ ，则新条目会通过单次 CAS 替换分数最低的条目。在三角色组协议（#3.5）下，每个表最多只能有一个 Inserter Kernel 并发执行。由于每个 warp 恰好协同处理一个键及其对应的桶，因此不会有两个 warp 同时操作同一个桶；所以，CAS 竞争仅限于单个 warp 内的线程，从而将每个线程的重试次数限制为最多 $W-1=31$ 次（warp 宽度为 $W=32$ ）。

#3.4 基于分数的动态双桶选择

单桶约束（#3.2）带来了一个根本性的内存利用率问题：对于包含 128 个槽位的桶，由于生日悖论，首次淘汰会在 $\lambda \approx 0.66$ 时触发（Walzer, 2023），导致淘汰路径尚未启用，就已有 ∼34% 的已分配 HBM 未被使用。对于 HBM 容量直接制约模型规模的 GPU 而言，这种浪费是不可接受的。 HKV 通过动态双桶模式解决了这一问题，将 2 的幂次范式（Seznec, 1993；Azar et al., 1994；Mitzenmacher, 2001）从 基于负载 的选择扩展为 基于分数 的选择。每个 Key 通过独立的哈希函数映射到两个候选桶。与 BP2HT（Awad et al., 2023）及其他基于负载的二选一设计不同，HKV 引入了一种两阶段自适应策略，将选择标准从 负载均衡 转向 淘汰质量 – 选择最低分数的桶等于最佳淘汰决策。这两个阶段分别为：

D1：预热阶段，基于内存利用率决策。当至少一个候选桶存在空闲槽位时，将键插入负载较低的桶 – 这种经典的负载均衡二选一放置策略将首次淘汰从 $\lambda \approx 0.66$ 推迟至 $\lambda \gt 0.97$ （#5.5），从而回收几乎所有被浪费的 HBM。
D2：稳态阶段，基于分数决策。在 $\lambda \approx 1.0$ 时，两个桶均已满，因此基于负载的 P2C 退化为随机二选一。HKV 通过将决策维度从负载转移到分数，恢复了二选一的优势：Kernel 会在最低分数较低的桶中执行淘汰（算法 3）。在持续的 Zipfian 数据插入下，双桶模式的 top-N 分数保留率达到 99.4%，而单桶模式为 95.4%，提升了 4.05%（#5.5）。

查找成本分析。 双桶模式在 miss 路径上会发起两次 Cache-Line 事务，而不是一次 – 但仍为 $O(1)$ 级别，且与负载因子无关。尽管多了一次事务，双桶模式通过避免从 $\lambda \approx 0.66$ 开始的过早淘汰开销，实现了相当或更高的吞吐量（#5.5）。图 5 展示了这一两阶段策略。

图 5. 两阶段双桶选择。阶段 D1（左）为提高内存利用率，将数据插入负载较低的桶；阶段 D2（右， $\lambda \approx 1.0$ ）在最低分数较低的桶中执行淘汰，从而提高淘汰的正确性。

算法 3：基于分数的双桶 Update/Insert

输入： 键 $k$ 、值 $v$ 、分数 $s$

$\begin{array}{r l} 1 & b_1 \leftarrow h_1(k) \bmod B;\quad b_2 \leftarrow h_2(k) \bmod B \qquad \text{// 两个候选桶} \\ 2 & \mathbf{if}\ \mathrm{occupancy}(b_1)<128\ \mathbf{or}\ \mathrm{occupancy}(b_2)<128\ \mathbf{then} \qquad \text{// 阶段 D1} \\ 3 & \qquad \text{将 }(k,v,s)\text{ 插入占用率较低的桶} \\ 4 & \mathbf{else} \qquad \text{// 阶段 D2：基于分数（} \lambda=1.0 \text{）} \\ 5 & \qquad m_1 \leftarrow \mathrm{min\text{-}分数}(b_1);\quad m_2 \leftarrow \mathrm{min\text{-}分数}(b_2) \\ 6 & \qquad b^* \leftarrow \arg\min(m_1,m_2) \qquad \text{// 最低分数更低的桶} \\ 7 & \qquad \mathbf{if}\ s>\min(m_1,m_2)\ \mathbf{then} \qquad \text{// 准入控制} \\ 8 & \qquad\qquad \mathrm{Update/Insert\text{-}With\text{-}Eviction}(b^*,k,v,s) \qquad \text{// 算法 2} \\ 9 & \qquad \mathbf{else} \\ 10 & \qquad\qquad \text{拒绝插入} \qquad \text{// 传入分数过低} \\ 11 & \qquad \mathbf{end\ if} \\ 12 & \mathbf{end\ if} \end{array}$

命题 3.3（基于分数的选择优势）。 假设分数独立同分布地采样自累积分布函数 $F$ ，选择最低分数更低的桶，会将被淘汰分数的期望值从 $\mathbb{E}[X_{(1:n)}]$ 降低到 $\mathbb{E}[\min(X_{(1:n)},Y_{(1:n)})]$ 。对于定义在 $[0,1]$ 上的均匀分布 $F$ ，桶大小 $n=128$ 时，被淘汰分数的期望值减半：

$\mathbb{E}[\min]=\frac{1}{2n+1}\approx 0.0039 \quad\text{vs.}\quad \frac{1}{n+1}\approx 0.0078.$

标准次序统计量参考资料可见 David 和 Nagaraja（2003 年）。

在生产环境的 Zipfian 工作负载中，分数并非独立同分布的均匀变量；由于高价值条目会聚集在热桶中，经验提升（表 11）超过了独立同分布情况下的界限。

完成桶设计、淘汰与负载均衡后，余下的挑战是保证来自 GPU 和 CPU 的并发访问安全。

#3.5 三角色组并发控制

HKV 引入了一种三角色组并发协议，根据操作是否修改桶结构来加以区分；此前所有基于角色的哈希表设计都没有这种分离平面。无论是 读 vs 写 (RCU) 还是 mutation vs resize（Fatourou 等人）的既有角色设计，都不区分结构性写入和非结构性写入，也没有跨越 CPU–GPU 执行域的设计（#6）。 HKV 的三角色组方案将 Reader、Updater 和 Inserter 隔离到不同的 GPU Kernel 中，并增加 CPU–GPU 双层锁来协调Host与设备。三个组分别是：

Reader（find、contains、size）：多个 Reader 可以并发执行；每个 Reader Kernel 都假设桶结构稳定，因此不需要 CAS。
Updater（assign、assign_scores）：多个 Updater 可以并发执行；它们原地修改已有条目的值或分数，但绝不会改变桶结构，即不分配槽位、不更新 Digest，也不执行淘汰。
Inserter（insert_or_assign、find_or_insert、erase）：独占访问；Inserter 负责分配槽位、更新 Digest 并执行淘汰，这些结构性修改与并发读取或更新不兼容。

这种结构性/非结构性区分由基于分数的淘汰机制（#3.3）所支撑：由于淘汰、槽位分配和 Digest 更新都嵌入到 Insert 路径中，所有结构性修改都被限制在 Inserter 角色中。单桶约束（#3.2）保证插入不会触发跨多个桶的级联重定位；这一封闭性使表级 Reader/Updater/Inserter 角色隔离足以保证正确性，无需逐桶细粒度锁。

将淘汰融合到插入路径 同样至关重要：如果淘汰像 MemC3 的 CLOCK 扫描或 CacheLib 的 AccessContainer 一样由独立后台进程执行，就会在 Inserter 角色之外产生结构性修改，破坏所有结构变化都局限于单一 Kernel 类型的三角色组不变量。表 4 总结了最终的兼容矩阵。

表 4. 三角色组并发兼容性。✓ 表示允许并发执行；✗ 表示互斥。

	Reader	Updater	Inserter
Reader	✓	✗	✗
Updater	✗	✓	✗
Inserter	✗	✗	✗

#3.5.1 并发语义

表 4 的兼容矩阵遵循 Gray 的意向锁层次结构。相较读写锁，其主要优势是：允许多个 Updater 并发执行：读写锁会把所有值更新都作为写入而串行化，三角色组机制则允许 Updater 批次并行，吞吐量最高可提升 4.80×（#5.4）。

Reader 和 Updater 互斥，因为 GPU 值更新最大可达 256 Bytes，若不采用逐条目锁就无法保证原子可见；表级串行化避免了这项开销。

获取/释放协议使用原子组计数器，细节见 #4.4。

命题 3.4（Reader 安全性）。 在三角色组协议下，Reader Kernel 绝不会观察到某个桶处于 “旧 Key 已被淘汰、替代项尚未写入” 的状态。这直接源于表 4 的兼容矩阵：Reader 和 Inserter Kernel 不会并发执行，因此 Reader 不可能观察到任何淘汰中间状态。

#3.5.2 CPU–GPU 双层锁

GPU Kernel 无法直接观察 Host 端原子变量，而 Host 线程也不能控制正在运行的 Kernel 内各 warp 的执行顺序。这个跨域缺口要求使用显式的双层同步机制来桥接 Host 与 Device 边界。

Host 层通过 std::atomic 计数器宣布角色组转换，分别跟踪活跃的 Reader、Updater 和 Inserter；
轻量级同步 Kernel 将已提交的角色状态传播至 Device 内存，确保下一组启动前所有 GPU warp 都观察到新的角色分配。

该设计既避免了 GPU 端全局屏障和设备范围的原子竞争，又保证不兼容的角色组绝不会并发执行。实现细节见 #4.4。四项核心机制就位后，仍有一项容量约束：Embedding 表可能超出单 GPU 的 HBM。下一小节在保持 Key 端处理位于 GPU 的同时，将设计扩展到 HBM 之外。

#3.6 分层 Key-Value 分离

Embedding 表经常超出单 GPU 的 HBM 容量。作为扩展能力，HKV 实现了基于位置的分层 Key-Value 分离：Key、Digest 和 Score 始终驻留在 HBM 中，Value 则通过零拷贝映射指针溢出到 Pin 住的Host内存（Host Pinned Memory），CPU 不参与关键路径。

由于每个 Key 恰好映射到一个桶，Value 地址可以通过 桶索引 和 槽位索引 进行算术计算，无需存储逐条目指针，从而消除每条目 8 Bytes 的开销（容量为 128 M 时共 1 GB）。

由此产生的架构效果是，Key 端操作的吞吐量（find*、contains）基本不受 Value 放置位置影响：在 H100 NVL 上，混合模式中的 find* 和 contains 可保留纯 HBM 吞吐量的 96.0%。该架构还允许在 HMEM 下方增加其他存储层，例如通过 GPU Direct Storage 接入 SSD；本文聚焦覆盖主要部署场景的 HBM+HMEM 路径。实现细节见 #4.2。

第 5 节将通过实验验证这些主张。

#4. 实现

本节介绍将 HKV 的设计（#3）映射到 GPU 硬件时采用的工程方案，包括公开 API（#4.1）、实现 Key-Value 分离的分层存储引擎（#4.2）、GPU Kernel 工程（#4.3），以及三角色组锁的物理实现（#4.4）。

#4.1 API 设计与易用性

HKV 提供以模板类 HashTable<K,V,S> 为核心的 STL 风格接口，其中 K 是键类型（通常为 uint64_t），V 是值元素类型（如 float），S 是分数类型（uint64_t）。

HKV 保留了熟悉的 map 操作（find、erase、insert_or_assign），并增加缓存专用原语：

insert_and_evict 在单次 Kernel 启动中返回被淘汰条目；
find_or_insert 将查找与冷启动插入结合起来；
export_batch_if 则将满足谓词的条目流式传输到Host以供检查点保存。

每次调用都会获取相应的三角色组锁（#3.5），启动 CUDA Kernel，并在完成后释放锁。

#4.2 分层存储引擎

#3.6 所述的 Key-Value 分离通过基于切片的内存分配器实现。初始化时，HKV 根据用户配置的 HBM 水位线确定值存储可用的最大 HBM 预算。 Key、Digest 和 Scores 始终放在 HBM 中；水位线耗尽后，Value 切片通过 CUDA 映射分配溢出到 Pin 住的Host内存（HMEM）。 Pin 住的页面映射到 GPU 地址空间，因此 Kernel 通过同一种指针接口访问驻留Host的值，数据路径中没有 CPU 线程。

Value 存储按粗粒度切片组织，切片大小随表容量而变化，范围为 256 KB–16 GB，以摊销 Pin 内存分配开销。在每个切片中，Value 按桶连续布局； Value 地址由其桶索引和槽位索引推导，无需存储逐条目指针。

#4.3 自适应 Kernel 选择

最大化 Key 级别并行度（每个 Key 一个线程）可获得最高探测吞吐，但复制大 Value 和在高 $\lambda$ 下扫描淘汰对象分别需要不同程度的线程协作。 HKV 提供三种 Update/Insert Kernel 变体，并根据负载因子和 Value 大小在运行时选择。

TLPv1：SIMD Digest 探测。 每个线程独立处理一个 Key。包含 128 个槽位的 Digest 数组以 32 个向量化 4-byte word 的形式加载，每个字通过 __vcmpeq4 执行字节并行 SIMD 比较； 32 条指令即可覆盖全部 128 个槽位，每次 miss 的预期误报完整键比较约为 0.5 次（每槽位 $1/256$ ）。 Value 写入使用流式存储（__stcs）绕过 L1。该变体用于 Value 较小（ $\le 32$ Bytes）且 $\lambda\le 0.98$ 的情况。
TLPv2：两阶段并行度切换。 探测与 TLPv1 相同，但探测阶段结束后，线程会重新组成 8–16 个线程的 cooperative groups，通过双缓冲共享内存协同复制每个成员的值，即在 Kernel 中途从 Key 级别并行切换到带宽级并行。共享内存缓冲区在淘汰扫描和 Value 复制阶段之间复用。该变体用于中等大小的 Value（32–512 Bytes）且 $\lambda \le 0.95$ 的情况。
Pipeline：warp 协作的四阶段重叠。 一个完整的 32 线程 warp 依次处理 Key，并在连续 Key 之间重叠四个阶段：（1）通过 __pipeline_memcpy_async 异步预取 128 个 Digest ；（2）warp 范围的 SIMD Digest 比较；（3）使用 cg::reduce 的协作式分数归约和 CAS 提交；（4）warp 协作式值回写。三深度流水线提交隐藏了 HBM 延迟。该变体用于 $\lambda>0.95$ ，此时频繁的淘汰扫描使延迟隐藏变得关键。
运行时策略选择。 Value 大小决定协作策略（TLPv1 或 TLPv2）；当 $\lambda\approx 0.95$ 时，负载因子会触发切换到 Pipeline，因为此时延迟隐藏的收益超过逐 Key 串行化成本。Lookup Kernel 使用类似结构，但由于三角色组保证（#3.5）而省略锁定。

#4.4 三角色组锁与 Key 级别 CAS

三角色组锁由 Host 上的三个原子计数器和 Device 端镜像的原子变量实现；轻量级单线程传播 Kernel 使用线程局部缓存的 CUDA stream，在两层之间同步。两层采用 “store–launch–fence” 握手：Host 写入原子计数器，启动同步 Kernel，而 Kernel 完成则构成跨域栅栏。

细粒度槽位级别的互斥通过 CAS(Acquire) 将 Key 原子替换为 Sentinel Lock 值来实现；Value 写入完成后再恢复实际 Key。

#5. 评估

我们通过四组实验评估 HKV：

与四个基线比较负载因子敏感性（#5.2）；
评估包括 HBM+HMEM 混合模式在内的端到端吞吐量（#5.3）；
对 Digest 过滤、淘汰开销、缓存质量、准入控制与并发进行组件消融（#5.4）；
分析单桶与双桶模式（#5.5）。

#5.1 实验设置

硬件。 所有实验均在单块 NVIDIA H100 NVL GPU（94 GB HBM3、Hopper 架构、Compute Capability 9.0）上运行。 GPU 通过 PCIe Gen5 ×16 连接到一台服务器，服务器配备 AMD EPYC 7313P（16 核、32 线程、3.0 GHz）和 125 GB DDR4 Host DRAM。

软件。 Ubuntu 24.04、CUDA 12.9（驱动 580.105.08）、GCC 13.3，使用 nvcc -O3 -arch=sm_90 编译。受测 HKV 版本为 main@2026-02；基线版本分别为 WarpCore v1.3.1、BGHT v0.1、cuCollections v0.1.0-ea，以及 BP2HT（BGHT main@2026-02）。

Workload。 除非另有说明，键为 uint64_t，值为 float32 × dim，每次操作的批大小为 1 M 个键值对，淘汰策略为 LRU。实验改变 Embedding 维度 $dim \in \{8,32,64\}$ 和负载因子 $\lambda \in \{0.50,0.75,1.00\}$ 。

配置。 表 5 总结配置 A–C（纯 HBM）和 D（通过 cudaHostAllocMapped 实现 HBM+HMEM）。

表 5. 基准测试配置。所有配置均使用单块 NVIDIA H100 NVL GPU。容量单位为百万键值对（M-KV）。

配置	dim	容量(M-KV)	HBM	HMEM	模式
A	8	128 M	4 GB	—	纯 HBM
B	32	128 M	16 GB	—	纯 HBM
C	64	64 M	16 GB	—	纯 HBM
D	64	128 M	16 GB	16 GB	HBM+HMEM

内存开销。 每条目的元数据（8 B 键、1 B Digest 、8 B 分数）共 17 B；值根据维度占 32–256 B，因此元数据开销为 6%–35%。

统计方法。 每个数值取 5 次冷启动运行的中位数；读取的变异系数 CV < 3%，写入的 CV < 5%。误差条小于绘图标记，故省略。

基线。 我们在同一块 H100 NVL 上，以相同 CUDA/驱动编译四种 Dict 语义 GPU 哈希表作为对比：WarpCore、BGHT、cuCollections 和 BP2HT。

cuCollections、BGHT 和 BP2HT 使用 (key, index) 间接寻址；所有测量都包含端到端的值 gather/scatter。
WarpSpeed（仅支持标量）、FBGEMM TBE（融合算子）和 MemcachedGPU（网络服务）因 API 语义不兼容而排除。
Hive（2025 年 arXiv 版本，采用 bounded cuckoo relocation 的 Dict 语义）在评估时尚未公开源码，因此未纳入。

#5.2 实验 1：负载因子分析

Cache 语义在整个负载因子范围内都能提供稳定吞吐量，包括 $\lambda=1.0$ ；所有Dict 语义基线在这一状态下都会退化或失败。

跨系统比较。 图 6 绘制 HKV 与四个基线（WarpCore、BGHT、cuCollections、BP2HT）的插入和查找吞吐量随 $\lambda$ 的变化。所有测试均在同一块 H100 NVL 上运行， $dim=32$ ，批大小为 1 M。

图 6. 插入（a）与查找（b）吞吐量随负载因子变化（ $\lambda=0.25–1.00$ ， $dim=32$ ，批大小 1 M）。采用 LRU 淘汰和 Cache 语义的 HKV 在整个 $\lambda$ 范围内维持近乎恒定的查找吞吐量（~3.4 B-KV/s），包括 $\lambda=1.0$ ；同时，满桶插入均在原地处理，不会 Rehash 或因容量不足而失败。 Dict 语义基线单调退化；WarpCore、BGHT 和 cuCollections 在 $\lambda\approx0.95$ 以上的阴影区域崩溃。BP2HT 的插入吞吐量只统计成功插入；在 $\lambda=1.0$ 时仅 48% 的插入成功。注意 cuCollections、BGHT 和 BP2HT 使用 #5.1 所述的 (key, index) 间接寻址。所有数据点均运行 5 次且 CV < 3%；误差条小于标记，故省略。（实验 1）

HKV 的查找吞吐量在 $\lambda=0.25–1.00$ 之间变化不足 1.0%（3.37–3.40 B-KV/s），并且每次插入都原地处理，不 Rehash、也不失败。

所有基线均单调退化：WarpCore 的查找吞吐量下降 90%，BGHT 下降 31%，BP2HT 下降 4%，cuCollections 则降至零。
在 $\lambda\approx0.95$ 以上，WarpCore、BGHT 和 cuCollections 崩溃；这是能力缺口，而不只是性能差距。BP2HT 会静默丢弃插入： $\lambda=1.0$ 时只有 48% 成功，有效吞吐量为 0.38 B-KV/s。

表 6 量化了不断扩大的差距。负载因子扫描使用均匀随机键，以便把结构退化与访问模式影响隔离开；#5.4 的实验 3c 使用生产环境式 Zipfian 偏斜（ $\alpha=0.50–1.25$ ）评估缓存质量。

表 6. 代表性负载因子下的查找吞吐量（B-KV/s）。H100 NVL， $dim=32$ ，批大小 1 M。 $\approx0$ 表示系统停滞、吞吐量接近零。（实验 1）

系统	$\lambda=0.50$	$\lambda=0.75$	$\lambda=1.00$	淘汰	并发
HKV	3.37	3.38	3.40	是	R/U/I
WarpCore	2.45	2.12	0.25	否	LF
BGHT†	1.31	1.30	0.92	否	LF
cuCollections†	0.36	0.36	$\approx0$	否	LF
BP2HT†	1.09	1.09	1.07	否	LF

† cuCollections、BGHT 和 BP2HT 使用 (key, index) 间接寻址（#5.1）。R/U/I 表示Reader/Updater/Inserter；LF 表示无锁 CAS。

在 $\lambda=0.50$ 时，HKV 的查找速度比所有基线快 1.38–9.43×；在更高 $\lambda$ 下差距进一步扩大（表 6）。

逐 API 敏感性。 图 7 按 API 分解 HKV 的负载因子敏感性（配置 A–C）。

图 7. 纯 HBM 模式（配置 A–C）下吞吐量随负载因子变化， $\lambda\in\{0.50,0.75,1.00\}$ 。所有配置中 find 的变化最多为 4.7%（ $dim=8$ 时为 1.3%）；由于无法再利用空槽位提前终止，find* 在 $\lambda=1.00$ 时下降~38%；insert_or_assign 因淘汰扫描开销在 $\lambda=1.00$ 时出现有界的 32%–41% 降幅。（实验 1）

与跨系统数据一致，find 在所有配置中随 $\lambda$ 的变化最多为 4.7%（其中 $dim=8$ 时仅为 1.3%，吞吐量为 3.889–3.941 B-KV/s）。find* 在 $\lambda=1.0$ 时因失去空槽位提前终止而下降~38%；insert_or_assign 因淘汰开销下降 32%–41%；assign 的变化最多为 6.7%，说明非结构性更新基本不受占用率影响。

#5.3 实验 2：端到端吞吐量

纯 HBM 吞吐量。 在所有 Embedding 维度下，HKV 的 find 达到 3.61–3.89 B-KV/s，返回指针的 find* 达到~7.05 B-KV/s（图 8）。

图 8. 纯 HBM 模式下 HKV 所有核心 API 的端到端吞吐量（配置 A–C， $\lambda=0.50$ ，每次操作批大小 1 M KV）。find 从 $dim=64$ 时的 3.61 B-KV/s 到 $dim=8$ 时的 3.89 B-KV/s；返回指针的 find* 不受维度影响，约为 7.05 B-KV/s；contains 在所有配置中均维持~5.10 B-KV/s。（实验 2）

find 达到 3.61–3.89 B-KV/s； $dim=64$ 时因值复制成本下降 7.2%。返回指针的 find* 不受维度影响，达到~7.05 B-KV/s，证实瓶颈是值复制而非键端索引。写 API 仍处于 B-KV/s 量级：insert_or_assign 为 1.72–2.13 B-KV/s，insert_and_evict 额外增加 5%–21% 开销，assign 为 2.59–3.26 B-KV/s。

延迟与扩展性。 每批 find 延迟在不同负载因子下保持稳定：配置 B、1,000 个批次时， $\lambda=0.50$ 与 $1.00$ 的 P50 均约为 0.30 ms。容量从 16 M 变化到 512 M 时，吞吐量变化小于 3%。

混合存储影响。 基于位置的值寻址（#3.6）使 HBM+HMEM 混合模式下的键端吞吐量保持在纯 HBM 的 4% 以内：配置 D（ $dim=64$ ，容量 128 M）中，返回指针的 find* 保留 96.0% 的吞吐量，即 6.949 B-KV/s，而纯 HBM 为 7.242 B-KV/s。相比之下，复制值的 API 受 PCIe 限制：find 降至 0.172 B-KV/s（下降~95%）。

#5.4 实验 3：组件消融

我们分解 HKV 的吞吐量，以量化各设计组件的贡献。

实验 3a：Digest 贡献。 在编译时禁用 Digest 预过滤，并测量 find 吞吐量（表 7）。

表 7. Digest 消融：启用与禁用 Digest 预过滤时的 find 吞吐量（B-KV/s）。加速比 = 启用/禁用。（实验 3a）

配置	$\lambda$	有 Digest	无 Digest	加速比
A（dim=8）	0.50	3.376	2.052	1.65×
B（dim=32）	0.50	3.321	1.929	1.72×
C（dim=64）	0.50	3.157	1.685	1.87×
A（dim=8）	1.00	4.768	1.825	2.61×
B（dim=32）	1.00	4.769	1.828	2.61×
C（dim=64）	1.00	4.769	1.836	2.60×

在 $\lambda=0.50$ 时， Digest 过滤带来 1.65–1.87× 加速；在 $\lambda=1.00$ 时，优势增至 2.60–2.61×，因为没有 Digest 时每次 miss 都要比较全部 128 个键，吞吐量不论维度都收敛到~1.83 B-KV/s。

实验 3b：淘汰开销。 比较 $\lambda=0.50$ （无淘汰）和 $\lambda=1.00$ （每次插入都淘汰）时的 insert_or_assign，开销为 32%–41%： $dim=8$ 为 41%， $dim=32$ 为 39%， $dim=64$ 为 32%。该开销有界，因为淘汰扫描始终只处理一个包含 128 个槽位的桶。

实验 3c：生产环境式访问模式下的缓存质量。 缓存命中率衡量持续在线插入期间，查找在表中找到目标的比例；它是 top- $N$ 保留率（#5.5）的运行时补充指标，后者衡量最终表状态的质量。生产推荐模型的 Embedding 访问呈幂律分布，Zipfian 偏斜约为 $\alpha\approx0.99$ 。表 8 在全部五种随库提供的 分数Functor 特化上扫描 $\alpha$ （配置 B， $\lambda=1.0$ ）。在生产环境典型的 $\alpha=0.99$ 下，LFU 达到 88.3%，比 LRU 高 4.4 个百分点；在 $\alpha\ge1.25$ 时，由于热集缩小到容量以下，所有策略均收敛到~99.4%。所有策略的吞吐量相当（2.97–3.04 B-KV/s），说明贡献来自共享的内联 Update/Insert 机制，而非策略数量本身。

表 8. 不同评分策略和 Zipfian $\alpha$ 下的缓存命中率（%）。配置 B， $\lambda=1.0$ ，单桶，容量 128 M。 $\alpha$ 扫描用于研究生产环境式幂律偏斜附近的敏感性。（实验 3c）

策略	$\alpha=0.50$	$\alpha=0.75$	$\alpha=0.99$	$\alpha=1.25$
kLru	18.6	43.0	83.9	99.4
kLfu	31.4	55.7	88.3	99.7
kEpochLru	18.6	43.0	83.9	99.4
kEpochLfu	18.6	43.0	83.9	99.4
kCustomized	18.6	43.0	83.9	99.4

实验 3d：准入控制。 基于分数的准入门控（算法 2）会拒绝分数低于桶内最低分的键。突发实验向一个 $\lambda=0.96$ 、拥有 16 M 个槽位的表注入 4 M 个键，以隔离该门控的贡献（表 9）。

表 9. 准入控制消融：向 $\lambda=0.96$ 、16 M 槽位的表突发注入 4 M 个键后的命中率变化。（实验 3d）

突发分数	准入情况	命中率变化
低（ $s=1$ ）	0%（全部拒绝）	+0.00 个百分点
高（ $s=10^9$ ）	100%（替换原有条目）	−21.48 个百分点

实验 3e：并发消融。 我们用传统读写锁替换三角色组机制（#3.5），测量七种工作负载组合（ $\lambda=0.75$ 、 $dim=16$ 、每批 64 K 个键、每线程 200 批）。当Updater从 1 个增加到 10 个时，三角色组机制达到 2.569 B-KV/s，而读写锁反向扩展至 0.535 B-KV/s，差距为 4.80×。混合工作负载中的差距缩小但仍显著：更新密集型（4F/5U/1I）为 3.21×，插入密集型（4F/2U/4I）为 1.20×；读取密集型（8F/1U/1I）接近持平（1.03×），因为单个Updater很少发生竞争。

表 10 总结移除各组件造成的系统级影响，表明四项创新构成不可分解的设计：移除任何一项都会破坏下游涌现特性。

表 10. 协同设计消融：移除任一组件都会破坏一项系统级特性。H100 NVL（#5.3–#5.5）。

移除项	被破坏的特性	实测影响
淘汰	$\lambda>0.66$ 时插入失败	无法持续运行于 $\lambda=1.0$
双桶	过早淘汰、保留率降低	$\lambda_{\mathrm{1st}}:0.98\to0.63$ ；top- $N$ : 99.4%→95.4%
三角色组	更新被串行化	慢 4.80×
单桶	miss 需要 $\ge2$ 次加载	失去单事务明确 miss 特性

#5.5 实验 4：单桶与双桶

表 11. 持续 Zipfian 插入下的单桶与双桶模式（ $\alpha=0.99$ ，容量 128 M， $b=128$ ）。top- $N$ 保留率衡量在 $\lambda=1.0$ 下完成 $5\times\text{capacity}$ 次稳态插入后，理想的最高分 $N$ 个键（ $N=\text{capacity}$ ）中仍存在于表内的比例。（实验 4）

指标	单桶	双桶	$\Delta$
首次淘汰 $\lambda$	0.633	0.977	+54.3%
top- $N$ 分数保留率	95.39%	99.44%	+4.05 个百分点
缓存命中率	83.88%	84.02%	+0.14 个百分点

双桶选择将首次淘汰从 $\lambda=0.633$ 推迟到 $\lambda=0.977$ （+54.3%），并将 top- $N$ 分数保留率提高到 99.44%（表 11）。这些结果比较的是双桶 GPU Kernel（#3.4）与默认单桶模式。

吞吐量。 双桶模式在所有负载因子下都提供与单桶相当或更高的吞吐量。在 $\lambda=0.50$ 时，双桶 find 吞吐量比单桶高~5%：二选一放置使键在桶间分布更均匀，降低每桶占用率并缩短平均 Digest 扫描路径；insert_or_assign 吞吐量则相差不到 1%。在 $\lambda=1.0$ 时优势扩大：双桶 insert_or_assign 吞吐量是单桶的 1.64×，因为单桶从 $\lambda\approx0.66$ 起就承受过早淘汰开销，而双桶把淘汰起点推迟到 $\lambda\approx0.98$ 。结合首次淘汰负载因子提升 54.3% 和 top- $N$ 分数保留率增加 4.05 个百分点（表 11），双桶在没有吞吐量损失的情况下，为内存受限部署提供了严格更优的行为。

#6. 相关工作

Dict 语义下的 GPU 哈希表。 GPU 哈希表从基于布谷鸟的设计发展到 Stadium Hashing、warp 协作式 slab、WarpCore、cuCollections、BGHT 和 WarpSpeed。DyCuckoo 处理动态调整大小；DACHash 优化 GPU 硬件缓存效率；GPHash 面向字节粒度持久内存；Hegeman 等人将紧凑哈希适配到 GPU 桶，但仍需多桶探测。GPU 哈希技术的全面综述可参见 Lessley 和 Childs。这些系统在碰撞解决和硬件优化方面各不相同，却都保留 Dict 语义：必须保留每个插入的键，因此表写满时会触发 Rehash 或插入失败。

有界探测、二选一与指纹 miss 过滤。 二选一范式证明，从两个箱中选择负载较低者可指数级降低最大负载；Panigrahy、Walzer 等人和 BP2HT 将这一脉络延伸到分桶及 GPU 哈希表。BP2HT 使用静态的基于负载选择，两个桶都满时便失败。Hopscotch、分桶布谷鸟和 Horton Tables 等有界探测设计在 Dict 语义下仍依赖溢出机制。SwissTable、F14 和 BBC 等 CPU 哈希表使用内联指纹，但 miss 仍需遍历多个组。

具体到 miss 路径，MemC3 探测两个各含 4 个槽位的桶且不支持 GPU；MemcachedGPU 把 8 位哈希 Embedding 每条目至少 20 Bytes 的头部中，每次 miss 需跨多个 Cache-Line 检查最多 16 个候选槽位；BP2HT 和 Hive（2025 年 arXiv）使用不含 Digest 数组的多桶设计，每次 miss 需要至少读取两个桶。相比之下，HKV 将单桶约束与连续 Digest 数组结合，因此每次桶检查都是明确的，且只需固定的一次 Cache-Line 加载。

缓存替换与淘汰感知数据结构。 Belady 最优算法给出了离线下界；实用在线策略则以最优性换取 $O(1)$ 开销。RRIP 表明，硬件缓存中基于预测的替换优于仅使用新近性的策略；HKV 通过共享的分数计算接口，在哈希表库层面应用这一原则。CPHash 引入 LRU 感知哈希表；Friedman 和 Mozes 表明，有界相联结构可提高吞吐量且只轻微影响命中率；Cavast 在操作系统页面级优化布局以提高 CPU LLC 效率，而 HKV 在哈希表桶级针对 GPU L1 Cache-Line 对齐。

MemC3 将布谷鸟哈希、标签与 CLOCK 淘汰协同设计；CacheLib 通过与哈希索引解耦、基于链表的 MMContainer 提供生产级可插拔淘汰。TinyLFU 提出轻量级准入门控，HKV 将其适配为逐桶、基于分数的准入（#3.3）。HashPipe 将基于计数的淘汰 Embedding 由单条目哈希阶段构成的数据平面流水线；HKV 共享路径内淘汰原则，但运行在 128 槽位 GPU 桶上，支持可插拔分数和通用键值语义。与所有这些系统不同，HKV 把淘汰分数融合到插入 CAS 路径中，不使用独立淘汰队列、淘汰数据结构或准入过滤器；哈希表本身就是缓存。

并发哈希表。 Li 等人通过乐观锁实现细粒度并发谷鸟哈希；RCU 哈希表定义Reader/写入器/调整大小角色；Fatourou 等人把逐桶修改与目录调整大小分离。Fatourou 的更新角色通过逐桶 PSim 实例把插入、删除和值变化等所有修改绑定在一起，而 HKV 进一步拆分修改：非结构性的值/分数更新可与查找并发，只有可能触发淘汰的结构性插入需要独占访问；在混合工作负载中，这类操作约占 10%。Bw-tree 形式化了结构修改操作；oneTBB 的 concurrent_hash_map 提供逐桶读写访问器。Liu 等人提出三阶段“冻结–迁移”模式，实现非阻塞哈希表调整大小。此前没有 GPU 哈希表将值/分数更新与插入/淘汰结构变化分开。HKV 把结构性与非结构性分离应用于 GPU 哈希表，通过 CPU–GPU 双层锁和角色隔离 Kernel，将可并行的值/分数更新与独占的插入/淘汰分开；这是此前纯 CPU 设计所不具备的。

Key-Value 分离与分层存储。 Key-Value 分离最初由 SSD/LSM-tree 场景中的 WiscKey 和 HashKV 推广；FAWN-DS、SILT 和 FASTER 使用紧凑的内存哈希索引指向存储中的数据。MICA 开创了使用环形日志值存储和并行哈希索引分区的整体 KV 存储设计；MemcachedGPU 和 Mega-KV 是早期 GPU Key-Value 分离系统，但会存储逐条目值指针，并要求 CPU 线程参与关键路径：MemcachedGPU 从 CPU 驻留 slab 处理 SET，Mega-KV 则由 CPU 负责分配与淘汰调度。HKV 引入基于位置的值寻址：键、 Digest 和分数驻留 HBM，值通过 cudaHostAllocMapped 溢出到 HMEM；每个槽位的键和值共享同一数组索引，既消除逐条目值指针，又通过零拷贝映射指针让 CPU 脱离关键路径。

推荐系统的 Embedding 存储。 深度学习推荐模型推动了专用 Embedding 存储的发展。Meta 的 FBGEMM 是与 HKV 最接近的工业系统，它提供 8–32 路（取决于版本）GPU 组相联 LRU/LFU 缓存。两者最关键的架构差异是淘汰决策的位置：FBGEMM 将淘汰解耦为包含独立数据结构的多 Kernel 流水线，HKV 则把分数比较、准入控制和淘汰对象替换 Embedding 桶局部插入路径。NVIDIA 的 cuEmbed 和 nv-embedding-cache 分别以 8 路组相联设计处理同一问题，进一步验证 GPU Embedding 缓存的重要性。Fleche 和 UGACHE 分别提供近似 LRU 与静态放置的 GPU Embedding 缓存；Catalyst 使用学习式成本模型自动做出缓存决策；LCR 在框架层应用学习式替换。HKV 作为带 Kernel 内淘汰的底层 GPU 哈希表原语，高层系统可在其上叠加框架专用策略。

#7. 结论

本文提出 HKV，这是首个将 Cache 语义作为正常满容量运行契约的 GPU 哈希表库：淘汰是一种由策略驱动的一等操作，而不是错误或维护事件。四项协同设计机制带来三项核心系统级特性：包含连续 Digest 数组、Cache-Line 对齐的 128 槽位桶，仅用一次内存事务即可明确判定每桶 miss （#3.2）；内联分数驱动 Update/Insert 与基于分数的双桶选择相结合，通过淘汰或拒绝准入在原地处理满桶插入，并改善 $\lambda=1.0$ 时的保留质量（#3.3、#3.4）；三角色组并发协议通过分离结构性与非结构性 GPU 写入，维持混合工作负载吞吐量（#3.5）。作为扩展能力，分层 Key-Value 分离把同一设计扩展到 HBM 之外，同时保持键端处理位于 GPU（#3.6）。

这些特性共同使 HKV 能够在 NVIDIA H100 NVL GPU 上以负载因子 1.0 持续保持十亿量级的稳定吞吐量；此前任何单一组件都无法实现这一组合。NVIDIA Merlin HugeCTR、TFRA 和 NVIDIA RecSys Examples 中的开源集成为 GPU 加速 Embedding 存储提供了实用部署路径。

限制与未来工作。 Reader 与 Updater 互斥以原子性换取简洁性；对于单字原子值，可以放宽这一限制。双桶模式覆盖 insert_or_assign 和 find，完整 API 则由单桶路径支持。多 GPU 分片按设计交由应用代码负责。未来，更宽的 GPU Cache-Line 可支持更大的桶；SSD/GDS 分层与动态 Rehash 仍是开放扩展方向。更广泛地说，HKV 确立了 Cache 语义作为 GPU 驻留数据结构的一种实用设计范式：以放弃字典不变量为代价，换取持续插入下的满容量稳定运行。