面向推荐系统参数服务器的稀疏哈希表:设计空间与训练、推理场景下的取舍分析

#摘要

推荐模型的 sparse 参数以 FID -> embedding 的形式存放在参数服务器(Parameter Server,PS)的哈希表中,大模型的 key 数达数百亿至数千亿。已有讨论往往把"哪种哈希表最好"当作与场景无关的问题,但训练 PS 与推理 PS 的负载几乎相反:前者写密集、key 集合持续变化,后者读密集、对尾延迟敏感且数据按副本复制。本文首先刻画两类场景的负载差异;随后提出一组八个评价维度,并据此对九类哈希表结构及十余个常用 C++ 库进行归类;接着给出索引内存占比、批量查找延迟与指纹误命中率三个简单的分析模型;最后分别对训练 PS 与推理 PS 给出候选方案与选型建议。分析表明:训练侧的首要约束是并发原地更新、不停服扩容与 dump,索引内存仅占总内存的约 1%~3%;推理侧的首要约束是 P99 延迟与跨分片版本一致,且由于 payload 量化与副本复制,压缩索引的收益显著高于训练侧。

关键词:参数服务器;embedding 表;哈希表;推荐系统;并发数据结构

#1 引言

在工业推荐系统中,sparse 特征(用户 ID、物品 ID、交叉特征等)经哈希后得到 64 位特征 ID(FID),每个 FID 对应一个 embedding 向量。大模型的 key 数达数百亿至数千亿,参数总量可达数 TB 至数十 TB,存放在参数服务器中,由哈希表完成从 FID 到参数的映射。哈希表的内存开销、查找延迟和并发能力因此直接决定了 PS 的成本与性能。

通用哈希表的研究与工程实现已相当成熟,例如 Swiss Table [4]、F14 [5]、Cuckoo 哈希 [6][7] 和最小完美哈希 [9][10][11]。然而,这些结构的评测通常基于通用负载,其结论不能直接迁移到 PS:PS 的 value 远大于 key,写入模式与一致性要求也与通用 KV 场景不同。更重要的是,训练 PS 与推理 PS 对同一张表提出了几乎相反的要求,脱离场景讨论"最优哈希表"容易得出误导性的结论。

本文的贡献如下:

  1. 负载刻画:从读写比例、key 集合动态性、value 构成、更新方式、延迟、一致性、内存与持久化八个方面,对比训练 PS 与推理 PS 的负载特征(第 3 节)。
  2. 设计空间:提出八个评价维度,并将常见哈希表结构归为九类,同时给出主流 C++ 库的归类(第 4 节与附录 A)。
  3. 分析模型:给出索引内存占比、批量查找延迟和指纹误命中率的简单模型,用于定量说明不同场景下的取舍(第 5 节)。
  4. 选型建议:分别对训练 PS 与推理 PS 给出候选方案与选型建议,并以 Monolith [1] 和 NeighborHash [2] 作为两个场景的案例(第 6、7、8 节)。

需要说明的是,本文是基于公开文献与开源实现的分析性综述,未进行系统性实验评测;文中数字均为量级估计,实际选型应结合具体负载实测。

#2 背景与问题定义

#2.1 参数服务器中的 sparse 参数

PS 通常按 FID 的哈希值将参数分片到多台服务器上。训练时,worker 按 mini-batch 向 PS 拉取(pull)所需的 embedding,完成前向和反向计算后推送(push)梯度,由 PS 端的 optimizer 原地更新参数。推理时,在线服务按请求从推理 PS 批量查询 embedding;推理 PS 的数据来自训练 PS 的增量同步或全量快照。

#2.2 问题定义

设某分片上的 key 集合为KK,∣K∣=N|K| = N。每个 key 对应的参数占PP 字节,索引结构为每个 key 平均分摊II 字节(包括空槽开销)。哈希表需要支持以下操作:

  • Find(k)\mathrm{Find}(k):查找 keykk,返回参数或 miss;
  • Upsert(k,v)\mathrm{Upsert}(k, v):插入或覆盖;
  • Update(k,f)\mathrm{Update}(k, f):在互斥保护下对参数原地执行读改写ff,例如 optimizer 更新;
  • Erase(k)\mathrm{Erase}(k):删除,用于淘汰;
  • Scan()\mathrm{Scan}():遍历全部条目,用于 dump 与迁移。

对于一次包含BB 个 key 的批量查询,我们关注其总延迟,尤其是尾延迟。

#3 负载刻画:训练 PS 与推理 PS

两类场景共有的约束是:大模型的 key 数达数百亿至数千亿(单个分片上也有数亿至数十亿);value 远大于 key,总内存以 payload 为主;查询以批量点查为主;miss 必须有明确语义,误把一个 key 当作另一个会读到错误的参数。在此之上,两者的差异见表 1。

表 1 训练 PS 与推理 PS 的负载特征对比

维度训练 PS推理 PS
读写比例每个 step 都有 pull 和 push,写和读一样多读远多于写,写只来自训练侧的同步
key 集合新 key 持续出现,要准入过滤;不活跃的 key 要淘汰跟随训练侧变化;冷冻模型的 key 集合完全固定
value 内容embedding + optimizer 状态(如 Adagrad、Adam 的累积量)只有 embedding,常做量化(FP16、INT8)
更新方式optimizer 原地读改写,同一个 key 可能被并发写分钟级增量原地写入,或者小时级、天级整版切换
延迟要求看吞吐,单次 pull 的延迟可被流水线掩盖看 P99,直接影响线上请求
一致性异步训练本身容忍一定的陈旧和不一致同一请求最好读到同一代数据,否则效果下降
内存每个 key 只存一份,optimizer 状态使 payload 更大每份数据要乘上副本数;payload 小,索引占比反而更高
持久化要定期 dump checkpoint,最好不停训练从 checkpoint 或增量流加载,扩副本要快

由表 1 可以得到两个观察:

  • 观察 1:索引内存在两类场景中的分量不同。训练侧 payload 包含 optimizer 状态,索引占比很小;推理侧 payload 经量化后变小,且总内存随副本数线性增长,压缩索引的绝对收益更大(定量分析见第 5.1 节)。
  • 观察 2:"写"在两类场景中的含义不同。训练侧是高频、细粒度、可能并发的原地更新;推理侧的写可以批量化,甚至可以不在原表上写,而以整表替换的方式完成。后者使只读结构成为可行选项。

#4 设计空间

#4.1 评价维度

我们用以下八个维度评价一种哈希表结构或实现:

  • C1 索引内存:每个 key 分摊的索引开销II,包括空槽。
  • C2 查找跳数:一次查找所需的相互依赖的随机访存次数hh。
  • C3 并发模型:不支持并发、分段加锁、细粒度锁,或读者无锁。
  • C4 原地修改:能否在互斥保护下直接修改 value。有的并发表只允许整体替换 value,对大 value 不友好。
  • C5 指针稳定:插入或扩容后,已取得的 value 指针是否仍然有效。
  • C6 扩容方式:整表重建、按分片重建或渐进迁移。
  • C7 erase 与遍历:是否支持并发 erase,以及能否在并发写入下稳定遍历。
  • C8 key 判定:存储完整 key,或只存储指纹。后者存在误命中。

#4.2 结构分类

表 2 按结构将常见方案归为九类。

表 2 哈希表结构分类

结构代表实现C1 索引内存C2 查找跳数写入与扩容
链式桶std::unordered_map、tbb::concurrent_hash_map高,每个元素一个节点2~3 跳,cache 不友好插入简单,指针稳定
扁平开放寻址absl Swiss Table、folly F14、Boost flat、tsl::robin_map中,空槽按整个槽计通常 1 次 cache miss扩容整表搬迁,指针不稳定
稀疏分组Google sparsehash、tsl::sparse_map低,空槽约 1~3 bit组头 → 元素,约 2 跳插入需在组内搬移元素,难以并发
Cuckoolibcuckoo [6]、Monolith [1]负载可达 90% 以上最多 2 个位置,延迟稳定踢出链带来插入尾延迟,表满时重建
数组内链接NeighborHash [2]、ska::bytell_hash_map [20]、emhash7 [21]无独立节点;NeighborHash 为 16 B 槽,负载 80% 以上沿数组内的链跳转;NeighborHash 约 1.1 条 cache line不支持并发写(NeighborHash 开源版支持单写者,容量固定)
邻域哈希Hopscotch [23]、tsl::hopscotch_map [22]每个桶附带一个邻域 bitmap只扫描 home 桶附近的一个邻域,通常 1 条 cache line插入时可能要把空位"跳"进邻域;跳不进时扩容
路由与数据分离两级表一级每槽数字节,只存指纹路由 → 数据 → 向量,最多 3 跳追加写;扩容只重建路由
静态完美哈希CHD [9]、PTHash [10]、RecSplit [11]每个 key 2~4 bit1~2 次访存不能插入,只能整体重建
GPU 表HierarchicalKV [12]受显存限制warp 并行,吞吐极高批量插入,内建淘汰

下面简述其中四类在推荐场景下特点鲜明的结构。

扁平开放寻址。 Swiss Table [4]、F14 [5] 与 Boost 的 unordered_flat_map 采用相同的思路:槽位分组,每组附带一小块元数据,每个槽存 1 字节的哈希片段;查找时以 SIMD 一次比较整组,仅对片段匹配的槽比较完整 key。该类结构通常只需 1 次 cache miss。其节点变体(absl::node_hash_map、F14NodeMap)以多一次分配和一跳为代价换取指针稳定;数组变体(F14VectorMap、ankerl::unordered_dense)将 value 连续存放,遍历效率高,适合 dump。该类结构本身不支持并发,在 PS 中通常以分片加锁的形式使用,或作为推理侧的只读表。

稀疏分组。 底层数组被划分为若干组,每组以一个 64 位 bitmap 标记被占用的槽,仅为存在的元素分配紧凑数组;第ii 个槽在紧凑数组中的偏移为popcount(bitmap∧(2i−1))\mathrm{popcount}(\mathit{bitmap} \land (2^i - 1))。空槽几乎不占内存,因而可以在低负载下运行以缩短探测链;代价是插入与删除需要在组内搬移元素,迭代器和引用随之失效,难以支持并发原地更新。

数组内链接。 这一类把冲突的元素串成链,但链节点就是表数组里的槽,而不是单独分配的节点,因此兼有链式桶"只沿链查找"和开放寻址"无额外分配"的优点。ska::bytell_hash_map [20] 每个槽配 1 字节元数据,其中记录到链上下一个元素的跳转距离(取自一张预设的距离表);emhash7 [21] 在槽内存储链上下一个元素的下标,无需墓碑,删除频繁时性能也稳定,并支持很高的负载因子;NeighborHash [2] 采用 coalesced chaining,并通过把占用他人 home 桶的记录迁走、在 cache line 内双向探测,让一条链尽量落在同一条 cache line 内(第 7.3 节)。与之相近的还有 Hopscotch 哈希 [23]:它不维护链,而是保证每个 key 都位于其 home 桶附近HH 个槽的"邻域"内,每个桶用一个 bitmap 标记邻域中哪些槽属于自己,查找只需扫描一个邻域。这几种结构的出发点都是把一次查找限制在很少的 cache line 内,但都不支持并发写。

路由与数据分离。 两级表将热路径上的路由信息压缩到极小:一级表按 key 的哈希做开放寻址,只存短指纹与二级位置,每槽仅数字节;二级表按 block 追加写入,参数内联,大向量再经指针指向内存池或 SSD。扩容时只需重建一级路由,二级数据不动;为此完整 key 需另行保存,可置于更廉价的存储中。该结构的优点是索引极省、插入路径稳定、扩容几乎不中断服务;代价是指纹误命中(第 5.3 节)和更多的依赖访存(第 5.2 节)。

#5 分析模型

#5.1 索引内存占比

每个 key 的总内存为I+PI + P,索引占比为

ρ=II+P.\rho = \frac{I}{I + P}.

训练侧的 payload 为P=d⋅b⋅(1+s)P = d \cdot b \cdot (1 + s),其中dd 为向量维度,bb 为每个元素的字节数,ss 为 optimizer 状态的倍数(Adagrad 取s=1s = 1,Adam 取s=2s = 2)。取d=64d = 64、FP32、Adagrad,得P=512P = 512 字节。此时I=16I = 16 字节对应ρ≈3.0%\rho \approx 3.0\%,I=3I = 3 字节对应ρ≈0.6%\rho \approx 0.6\%。即使把索引压缩到原来的五分之一,总内存也只减少约 2.4%。

推理侧去掉 optimizer 状态并量化到 FP16,同样d=64d = 64 时P=128P = 128 字节,I=16I = 16 字节对应ρ≈11%\rho \approx 11\%。此外,推理侧总内存为R⋅N⋅(I+P)R \cdot N \cdot (I + P),其中RR 为副本数。以 key 数N=1011N = 10^{11}(一千亿)的大模型为例,把II 从 16 字节降到 3 字节,每份完整数据可节省13×101113 \times 10^{11} 字节,约 1.3 TB;若R=10R = 10,总计约 13 TB。这与观察 1 一致:压缩索引在推理侧的收益显著高于训练侧。

#5.2 批量查找延迟

设一次批量查询包含BB 个 key,每个 key 需要hh 次相互依赖的随机访存,单次访存延迟为tmt_m。若逐个 key 串行查找,总延迟约为

Tserial≈B⋅h⋅tm.T_{\text{serial}} \approx B \cdot h \cdot t_m.

若采用 AMAC [3] 或协程方式交错执行多个 key 的查找,使至多WW 个访存同时在途,则总延迟受限于内存级并行度(memory-level parallelism,MLP):

Toverlap≈B⋅h⋅tmmin⁡(W,MLP).T_{\text{overlap}} \approx \frac{B \cdot h \cdot t_m}{\min(W, \mathrm{MLP})}.

由此可见:(1) 在不做交错的情况下,延迟与hh 成正比,多跳结构(如两级表的h=3h = 3)显著慢于单跳结构;(2) 交错可以按min⁡(W,MLP)\min(W, \mathrm{MLP}) 的倍数掩盖延迟,但总访存次数B⋅hB \cdot h 不变,因此hh 仍决定了吞吐上限。仅对下一个 key 的首跳做预取,只能掩盖依赖链的第一跳;对多跳结构,需要为每一跳都发出预取。

#5.3 指纹误命中率

设内存中只存储ff 位指纹,一次查询需要与cc 个候选条目比较指纹。假设指纹均匀分布,一次查询中出现误命中的概率约为

pfp≈c⋅2−f.p_{\text{fp}} \approx c \cdot 2^{-f}.

若每天有QQ 次查询的目标 key 不在表中,期望误命中次数约为Q⋅c⋅2−fQ \cdot c \cdot 2^{-f}。以f=31f = 31、c=1c = 1、Q=1011Q = 10^{11} 为例,期望约为1011/231≈4710^{11} / 2^{31} \approx 47 次。也就是说,在数百亿至数千亿 key、高查询量的条件下,31 位指纹每天仍可能产生数十次误命中。误命中会使查询返回另一个 key 的参数,若下游按 key 的配置解释该参数(例如向量长度不同),还可能引发更严重的错误。存储完整 key 可以使pfp=0p_{\text{fp}} = 0;若坚持只存指纹,至少应选择足够大的ff,并在读取 payload 时增加校验。

#6 训练 PS 的分析

#6.1 核心约束

  1. 并发原地更新:同一 key 可能被多个 worker 同时 push,optimizer 需在互斥保护下原地读改写(C3、C4)。由于写与读一样频繁,RCU、双 buffer 等读者无锁方案的收益有限。
  2. 不停服扩容:新 key 持续进入,扩容不可避免(C6)。可选做法包括:分片后逐片扩容;渐进式 rehash,新旧两表同时查询,后台迁移;或者将索引与数据分离,扩容只重建索引。
  3. erase 与遍历:淘汰需要 erase,checkpoint 需要在训练进行中 dump(C7)。常见做法包括:fork 进程利用写时复制获取快照;逐分片加锁 dump;或者为条目附带版本号,只取不晚于快照版本的值。
  4. 索引内存为次要因素:由第 5.1 节,ρ\rho 仅约 1%~3%;准入过滤、淘汰、下沉 SSD 对总内存的影响要大一个数量级。

#6.2 候选方案

表 3 训练 PS 的候选方案

方案并发与原地修改扩容评价
phmap::parallel_flat_hash_map [15]每片一把锁,modify_if 等接口在锁内修改每片单独扩容推荐:将"分片 + 锁"实现为现成组件
boost::concurrent_flat_map [16]每组一把读写锁,只能用 visit 传 lambda 在锁内访问整表扩容推荐:visit 接口契合 optimizer 更新
libcuckoo [6] / Monolith [1]桶级细粒度锁,update_fn 在锁内修改表满时扩容推荐:成熟,存完整 key;高负载时有插入尾延迟
两级表1 bit 锁嵌在槽与条目中,锁粒度到单个 key只重建路由,几乎不停内存紧张、扩容频繁时适用;需处理指纹误命中
tbb::concurrent_hash_map [17]accessor 获取元素级写锁,语义合适按桶渐进分裂可用,但每个元素一个节点加一把锁,数百亿至数千亿 key 时内存开销过大
HierarchicalKV [12](GPU)批量插入与更新内建淘汰GPU 训练的首选
folly::ConcurrentHashMap [5]更新为整体替换 value,不能原地修改分段扩容不适用:大 value 每次更新都需复制
folly::AtomicHashMap、tbb::concurrent_unordered_map插入与查找无锁,value 的线程安全需自行保证—不适用:erase 不回收空间或不是并发安全的,难以淘汰
sparse_map、NeighborHash、静态完美哈希不支持并发写,或不支持插入—不适用

#6.3 案例:Monolith 的无冲突 embedding 表

Monolith [1] 指出,许多早期系统先将 ID 哈希到固定大小的表中,使不同 ID 共享同一 embedding,这种冲突会损害模型质量,在热门 ID 与长尾 ID 混杂时尤为明显。为此,Monolith 为每个 ID 分配独立的 embedding,并采用以下设计:

  • Cuckoo HashMap:两张子表T0T_0、T1T_1,各对应一个哈希函数;插入时若目标位置被占用,则将原 key 踢到其在另一张表中的位置,直至放下为止;查找最多访问 2 个位置。
  • 准入过滤:ID 出现足够多次后才分配 embedding,以概率过滤器计数,过滤只出现一两次的长尾 ID。
  • 过期淘汰:记录每个 embedding 的最近更新时间,删除长期不活跃的 ID。
  • 训练与推理同步:训练 PS 周期性地把有变化的 sparse 参数增量同步到推理 PS,可实现分钟级更新。

后两项设计对应训练侧 key 集合持续变化的需求。Monolith 的重点在于证明"无冲突加实时训练"对模型效果的收益,哈希表本身采用成熟的 Cuckoo 结构,并未在内存上做极致优化。与两级表相比,Cuckoo 存完整 key、判定精确、跳数少,但表满时需重建,插入存在尾延迟;两级表索引更省、扩容只需重建路由,但只存指纹且多一跳。

#7 推理 PS 的分析

#7.1 核心约束

  1. P99 延迟:一次请求需查询数百至上千个 key。由第 5.2 节,可通过减少hh(单层扁平表加完整 key,每个 key 约 1 条 cache line 加 1 次 value 解引用)或通过交错执行掩盖延迟;对多跳结构,后者几乎是必需的。
  2. 更新模式决定表的形态:
    • 分钟级原地增量:表需支持边读边写,可采用读者无锁的动态表,或"只读基础表 + 小的动态增量表"的分层结构,查询时先查增量再查基础。
    • 小时级或天级整版切换:表可完全只读,按副本滚动切换,读路径无锁且内存最省。
  3. 跨分片版本一致:一次请求的 key 分布在多个分片上,若各分片不是同一代数据,请求会混用新旧 embedding。整版切换只需在查询协议中携带版本号;原地增量则需要额外的版本机制。
  4. 索引内存随副本数放大:由第 5.1 节,推理侧压缩索引的收益更大;但正确性优先,只存指纹的方案需要按第 5.3 节选择足够长的指纹并增加校验。

#7.2 候选方案

表 4 推理 PS 的候选方案

方案读路径更新方式评价
absl::flat_hash_map、F14、Boost flat、unordered_dense、bytell、emhash7、hopscotch无锁(只读)整版构建后原子切换指针推荐用于整版切换:实现简单、查找快
NeighborHash [2]无锁,配合 AMAC 与 SIMD整版切换;开源版支持单写者推荐用于批量只读点查
folly::ConcurrentHashMap [5]无锁(hazard pointer)原地增量,整体替换 value推荐用于读多写少的分钟级增量;value 较小时复制代价可接受
静态完美哈希 + 指纹无锁只能整体重建适用于冷冻模型、内存极紧的场景
sparse_map / sparsehash无锁(只读)单线程加载适用于 value 很小、内存极紧的场景
folly::AtomicUnorderedInsertMap [5]无锁只能插入,不能 erase适用于一次性构建后只读的表
libcuckoo、phmap、两级表有轻量锁原地增量可用;两级表需补充多跳预取与更长的校验
HierarchicalKV [12](GPU)warp 并行批量更新GPU 推理

#7.3 案例:NeighborHash 的批量只读查询

NeighborHash [2] 将索引置于单层扁平数组中,采用 coalesced chaining,并将占用他人 home bucket 的记录迁走,使一个 key 的探测尽量落在同一条 cache line 内。查询侧结合 AMAC [3](为每个 key 维护一个状态机,发出预取后切换到下一个 key)与 SIMD 多 key 并行,以掩盖随机访存延迟。

其开源实现的 benchmark 将 NeighborHash 与 std::unordered_map、absl::flat_hash_map、ankerl::unordered_dense、ska::bytell_hash_map、emhash7、tsl::hopscotch_map,以及作者实现的线性探测与 SIMD 分桶(16×16)两个基线进行了对比,覆盖标量、向量化与多线程几类场景。

该系统完全按推理侧设计:训练 PS 与推理 PS 分离,查询集群不承担训练时的 push 与 optimizer 计算。更新以按副本滚动切换整个版本的方式完成(论文实验中的更新间隔为 15 分钟至 4 小时),查询协议携带分片与版本信息,保证同一请求读到同一代数据。论文报告,不施加一致性约束时约 3% 的结果混用了多个版本的 embedding。这一设计以部分新鲜度为代价,换取了读路径无锁、读写隔离与版本一致。

#8 讨论

#8.1 选型建议

表 5 不同场景下的选型建议

场景建议
训练 PS(CPU)phmap::parallel_flat_hash_map、boost::concurrent_flat_map 或 libcuckoo,存完整 key;内存紧张时用两级表
训练 PS(GPU)HierarchicalKV 一类的 GPU 表
推理 PS,分钟级增量folly::ConcurrentHashMap 等读者无锁的动态表,或"只读基础表 + 动态增量表",配合批量预取
推理 PS,小时级或天级整版切换absl::flat_hash_map、F14 或 NeighborHash 作为只读表,按副本滚动切换,查询携带版本号
推理 PS,冷冻模型、内存极紧静态完美哈希 + 指纹,或稀疏分组结构

#8.2 开放问题

  • 分层结构:将不可变的基础表(完美哈希或 NeighborHash)与小型动态增量表组合,有望同时获得只读表的内存与延迟优势和动态表的新鲜度,但增量表的合并策略与一致性语义仍需设计。
  • 多跳结构的批量预取:路由与数据分离的结构在扩容与内存上有优势,其查找延迟能否通过 AMAC 式多跳预取逼近单层扁平表,有待实测。
  • 正确性与内存的权衡:第 5.3 节表明短指纹在大规模下会产生可观的误命中。如何以最小的内存代价获得可接受的误命中率(例如只在推理侧加长指纹),值得进一步研究。

#8.3 局限性

本文未进行系统性实验,第 5 节的模型忽略了 cache 命中、TLB、NUMA 与内存带宽等因素;各库的特性基于其公开文档与源码的一般描述,可能随版本变化。实际选型应以目标负载下的实测为准。

#9 相关工作

通用哈希表。 Cuckoo 哈希 [7] 以多个候选位置换取最坏情况下常数次的查找,libcuckoo [6] 在其基础上实现了高并发写入。Robin Hood 哈希 [8] 通过平衡探测距离降低查找方差;Hopscotch 哈希 [23] 将每个 key 限制在 home 桶附近的邻域内,使查找只需扫描固定范围。Swiss Table [4] 与 F14 [5] 以分组元数据和 SIMD 比较大幅提升了开放寻址的查找速度。最小完美哈希方面,CHD [9]、RecSplit [11] 与 PTHash [10] 在每个 key 仅数 bit 的空间下支持常数时间查找,但只适用于静态 key 集合。

推荐系统的 embedding 存储。 Monolith [1] 采用无冲突的 Cuckoo 表并结合准入与淘汰,支持实时训练;TFRA [19] 在 TensorFlow 中提供了基于哈希表的动态 embedding;HierarchicalKV [12] 面向 GPU 提供带淘汰的多级哈希表;NeighborHash [2] 针对推理侧的批量只读查询优化了 cache 局部性与访存并行。

访存延迟掩盖。 AMAC [3] 通过为每个查询维护状态机并交错执行,掩盖指针追逐类操作的访存延迟,适用于哈希表探测与链表遍历等场景。

#10 结论

本文从训练 PS 与推理 PS 的负载差异出发,分析了推荐系统 embedding 哈希表的设计空间。结论是:训练侧应优先解决并发原地更新、不停服扩容与 dump,索引内存是次要因素;推理侧应优先解决 P99 延迟与跨分片版本一致,且由于 payload 量化与副本复制,索引内存比训练侧更值得压缩。无论哪一侧,在数百亿至数千亿 key 的规模下,只存短指纹带来的误命中都不可忽视。

#附录 A 常见库速查

表 A1 常见 C++ 哈希表库

库 / 类型结构类别并发原地修改指针稳定备注
std::unordered_map链式桶无是是基线
absl::flat_hash_map扁平开放寻址无是否最大负载 7/8
absl::node_hash_map扁平开放寻址(存指针)无是是每个元素多一次分配
folly::F14ValueMap / F14NodeMap扁平开放寻址无是Node 是每个 chunk 14 个槽
folly::F14VectorMap扁平索引 + 连续数组无是否遍历快;erase 用最后一个元素填洞
boost::unordered_flat_map扁平开放寻址无是否15 槽一组
ankerl::unordered_denseRobin Hood 索引 + 连续数组无是否遍历快,代码量小
tsl::robin_mapRobin Hood 开放寻址无是否
tsl::sparse_map、sparsehash稀疏分组无是否空槽约 1 bit
phmap::parallel_flat_hash_map分片扁平开放寻址每片一把锁是(modify_if 等)否可插入自定义 mutex
boost::concurrent_flat_map扁平开放寻址每组读写锁是(visit)—无迭代器,用 visit_all 遍历
tbb::concurrent_hash_map链式桶元素级读写锁是(accessor)是支持并发 erase;内存开销大
tbb::concurrent_unordered_mapsplit-ordered list插入与查找无锁自行保证是erase 不是并发安全的
folly::ConcurrentHashMap分段读者无锁,写者每段加锁否,整体替换—迭代器在并发修改下安全
folly::AtomicHashMap开放寻址插入与查找无锁自行用原子操作是key 只能是整数;erase 不回收空间
folly::AtomicUnorderedInsertMap开放寻址插入与查找无锁自行用原子操作是固定容量,不能 erase
libcuckoo cuckoohash_mapCuckoo桶级细粒度锁是(update_fn)否lock_table 后遍历
ska::bytell_hash_map数组内链接无是否1 字节元数据记录跳转距离
emhash7::HashMap数组内链接无是否无墓碑,支持高负载因子
tsl::hopscotch_map邻域哈希(Hopscotch)无是否每桶一个邻域 bitmap

#参考文献

[1] Z. Liu, L. Zou, X. Zou, C. Wang, B. Zhang, D. Tang, B. Zhu, Y. Zhu, P. Wu, K. Wang, Y. Cheng. Monolith: Real Time Recommendation System With Collisionless Embedding Table. In ORSUM Workshop at ACM RecSys, 2022. arXiv:2209.07663.

[2] Q. Zhang, Z. Teng, D. Wu, J. Wang. An Enhanced Batch Query Architecture in Real-time Recommendation. In Proceedings of CIKM, pp. 5078–5085, 2024. doi:10.1145/3627673.3680034. arXiv:2409.00400. 开源实现:NeighborHash。

[3] O. Kocberber, B. Falsafi, B. Grot. Asynchronous Memory Access Chaining. Proceedings of the VLDB Endowment, 9(4): 252–263, 2015. doi:10.14778/2856318.2856321.

[4] Abseil. Swiss Tables Design Notes.

[5] Facebook. Folly: F14 Hash Table、ConcurrentHashMap、AtomicHashMap。

[6] X. Li, D. G. Andersen, M. Kaminsky, M. J. Freedman. Algorithmic Improvements for Fast Concurrent Cuckoo Hashing. In Proceedings of EuroSys, 2014. doi:10.1145/2592798.2592820. 开源实现:libcuckoo。

[7] R. Pagh, F. F. Rodler. Cuckoo Hashing. Journal of Algorithms, 51(2): 122–144, 2004. doi:10.1016/j.jalgor.2003.12.002.

[8] P. Celis, P.-Å. Larson, J. I. Munro. Robin Hood Hashing. In Proceedings of FOCS, pp. 281–288, 1985. doi:10.1109/SFCS.1985.48.

[9] D. Belazzougui, F. C. Botelho, M. Dietzfelbinger. Hash, Displace, and Compress. In Proceedings of ESA, LNCS, pp. 682–693, 2009. doi:10.1007/978-3-642-04128-0_61.

[10] G. E. Pibiri, R. Trani. PTHash: Revisiting FCH Minimal Perfect Hashing. In Proceedings of SIGIR, pp. 1339–1348, 2021. doi:10.1145/3404835.3462849.

[11] E. Esposito, T. Mueller Graf, S. Vigna. RecSplit: Minimal Perfect Hashing via Recursive Splitting. In Proceedings of ALENEX, pp. 175–185, 2020. doi:10.1137/1.9781611976007.14.

[12] NVIDIA. HierarchicalKV.

[13] Google. sparsehash.

[14] T. Goetghebuer-Planchon (Tessil). sparse-map.

[15] G. Popovitch (greg7mdp). parallel-hashmap.

[16] Boost.Unordered. unordered_flat_map / concurrent_flat_map.

[17] UXL Foundation. oneTBB.

[18] M. Leitner-Ankerl. unordered_dense.

[19] TensorFlow. Recommenders Addons (TFRA).

[20] M. Skarupke. flat_hash_map / bytell_hash_map;设计说明:A new fast hash table in response to Google’s new fast hash table, 2018.

[21] ktprime. emhash.

[22] T. Goetghebuer-Planchon (Tessil). hopscotch-map.

[23] M. Herlihy, N. Shavit, M. Tzafrir. Hopscotch Hashing. In Proceedings of DISC, LNCS, pp. 350–364, 2008. doi:10.1007/978-3-540-87779-0_24.