CIKM'24 : 更快的批量KV查询系统

在现代推荐系统中，需要以尽可能低的延迟在海量的数据中快速计算出与用户最相关的top-N。而其中能够管理海量数据并支持高速批量查询的存储系统是最重要的组件之一。如下图所示，无论是在召回、排序阶段，还是在离线模型训练期间，更多的特征和更快的计算通常会带来更好的推荐结果。

基于深度学习的推荐系统需要大量的特征来准确描述复杂的用户的行为、属性、偏好。与电商的商品推荐相比 B 站主要分发视频内容，关键帧图像嵌入、视频情感、作者的态度以及观点等特征对内容的推荐至关重要。且对于 B 站这样的大型平台，在拥有数亿用户和数十亿内容的推荐系统中，用户和内容的属性，以及从属性中挖掘的特征，以及特征训练出来的Embedding都会对KV存储系统有巨大的挑战：

• 高吞吐量批量读取：在模型训练和预测期间有效读取大型特征集。

• 批量查询一致性：在并发操作中保持准确的结果。

• 大容量存储：在确保性能的同时扩展以管理海量数据。

为应对上述挑战，团队设计并实现了一种用于批量查询的分布式查询架构，显著提高了推荐系统的性能。其中包含对传统哈希表的一些优化，后文称NeighborHash，它最大限度的减少了每个查询对缓存行的访问次数，从而在有限的内存宽带约束下实现更大的查询吞吐量。且在 NeighborHash 的基础上，引入了一种基于NVMe的分布式键值存储服务，该服务支持功能和模型大小的水平扩展，同时保持较低的资源消耗。同时，因为数据更新过程中会存在多个版本，为了确保批量查询过程中的一致性，优化了更新与查询协议。

本文介绍的分布式查询架构、NeighborHash相关优化及其详细实验数据已发表于：An Enhanced Batch Query Architecture in Real-time Recommendation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM ’24), October 21–25, 2024, Boise, ID, USA. ACM, New York, NY, USA, 8 pages.https://doi.org/10.1145/3627673.3680034。

与传统KV缓存在线事务处理服务不同 ，我们的场景只有导入没有commit，过程中没有一致性要求，只需要最终一致性，也就是一个在线分析处理 (OLAP) 系统。我们应用场景的特点是批量点查、无范围查询需求且查询命中率高（~90%）。所以相比于Skip-list 、 B+ Tree等KV数据结构，hash-map是最快的。

在传统哈希表中，通常使用Separate Chaining 和 Open Addressing来解决哈系统冲突 。如下图所示：

• Separate Chaining：在哈希表的每个 bucket 上建立一个链表，将所有哈希值相同的元素都存储在这个链表中。典型实现：std::unordered_map

• 优势：pointer stability，比较次数可控，冲突容忍高

• 劣势：high cache miss，查询性能比较差，内存利用率低

• Open Addressing：当发生冲突时，通过线性探查的方式在哈希表中寻找其他空闲的位置来存储冲突的元素典型实现：google::dense_hash_map

• 优势：cache命中率好，查询性能高（low load-factor）

• 劣势：pointer instability，high load-factor性能变差，内存利用率低

在我们核心关注的OLAP场景中，查询性能是最重要的，而主要衡量其性能的有两个指标Cacheline Access 和 Comparsion。以下对两种解hash冲突方式进行比较，我们控制影响hashMap查询性能的各个维度在以下约束上，以满足对比需要。

1. 数据分布：数据在哈希表中均匀分布。

2. 负载因子：80%。

3. 数据集大小：使用巨页可寻址的大型数据集，减少L1、L2 catch对于Cacheline Access指标的影响以及降低大数据量情况下TLB Catch Miss对查询性能的影响。

4. 读写比例：强调OLAP场景中常见的静态工作负载，其中读取操作占主导地位。

5. 成功查找率：90% 。

6. 哈希函数：absl::Hash。

结果如下图所示，在负载因子为 0.8 且数据均匀分布的情况下，线性探测平均需要访问 1.36 次 CPU 缓存行，并且平均比较次数为 2.37 次。相比之下，链式哈希需要大约 1.37 次比较，但需要访问 2.46 个缓存行。

由于现代体系结构下，CPU性能的增速远大于内存访问延迟的增速，a.k.a memory wall，因此更快的hashmap实现往往都是基于Linear Probing进行优化，例如google::dense_hash_map，cuckoohash，Robinhood，Swiss Table等。

其中 Swiss Table 是在2017年 Google的工程师在CPPCON上首次披露的。其经典实现abseil查询性能是最好的，首先其通过open-address解决哈希冲突，然后在open-address的基础上加入了meta-data。如下面左图所示，把每个key的hash_value，也就是一个uint64，拆分成两部分，H1和H2。分别是57个bit和7个bit，把7个bit的部分，也就是H2，拿出来再加一个bit作为标记位，作为这个bucket的meta-data，如下面右图所示，这个标记位用来标识这个bucket是空的，被占用，还是被删除。

这样就形成了一个两层的结构，如下图所示，meta-data一层，Element bucket一层，用H1也就是hash-value中剩余的57个bit来寻址Bucket。有了meta-data，有很多好处，首先meta-data很小，只有元素的1/16大小，可以把更多的数据放入缓存，由于其中有一部分hash-value也可以快速进行比较，来过滤掉不匹配的位置。包括open-address很难解决的empty、delete标记位问题，甚至clear，遍历都会加速。

除此之外，Swiss Table 还引入了SIMD（单指令多数据）来加速查询过程。Swiss Table会把bucket按照16个一组进行分组，16个meta-data就是128位，在进行比较的时候，就可以用SSE指令进行并行比较。首先，先用H1来定位到bucket-group，然后用key的H2构造一个128位的mask，比如下图所示，H1已经定位到group的Metadata ，H2是0x43，就会构造一个0x43这样一个128位的mask。然后跟这个group的meta-data用sse进行比较，一个sse指令就可以比较16个元素，非常高效，sse的比较指令会返回一个bitmap来标记那一个位置有匹配。有匹配的，再去取对应的bucket的完整的key来比较，如果没有找到，并且这个group里还有空位，就说明所要查找的key不在表里，如果这个group已经满了，那就需要探测下一个位置。这部分跟传统的open-address是相同的，用的是quadratic的probing。这个设计还是非常高效的，尤其对于大量miss的查询，大部分只需要读一次meta-data就可以结束了。但是对于高命中的查找，最少需要两次内存访问以及两次比较，两次比较还好说，因为第一次成功了第二次大概率也是成功的，故建立在多发射指令流水线上cpu的分支预测还是比较高效的，最麻烦的是两次内存访问，这个在大数据量下的开销还是非常大的。另外一个问题是对hash函数的要求会比较高，因为H2只有7个bit，要保证尽可能随机才能有比较好的效果。

Linear probing在低负载下可以保持很好的cache locality和查询性能，但是高负载下会急速退化，而Separate chaining虽然有确定性的跳转，但是cache locality差。NeighborHash在设计上除了尝试结合前述两种方案的优势，还借鉴了Swiss-Table 在 SIMD（单指令多数据）上的使用，来加速比较过程。NeighborHash的开源版本地址为：https://github.com/slow-steppers/NeighborHash/commits/main/。

与CoalescedHash类似，NeighborHash在一个Flat Array中建立sperated chaining，但是不同于CoalescedHash通过Cellar Region处理冲突，NeighborHash采用了Lodger Relocation的方式来处理冲突，并采用Bidirectional Cacheline-aware的方法来进行probing，为了进一步优化内存访问，采用inline-chaining来表示冲突链表，后文会详细解释这三个设计点。

2.2.1.1 Lodger Relocation

在传统的 CoalescedHash 中，哈希表 bucket 被编号为1-N，其中前 M 个 bucke t用于哈希函数的可寻址区域，剩余的 N-M 个 bucket 专门用于存放冲突记录（后称为Cellar Region）。当 Cellar Region 被占满时，后续的冲突记录必须占用前 M 个可寻址区域的空 bucket，这就导致可能与后续插入的记录进一步冲突。PSL（探测序列长度）对于 Cellar Region 的大小很敏感，为了最小化 PSL，我们去掉了 CoalescedHash底部，将冲突元素直接放到了可寻址区域。方法如下：对于bucket i 中的记录x，如果Hash（x.key）为 i，则称为 host 记录；否则，它被称为 lodger 记录。当插入一条新记录 y 时，哈希（y.key）会产生 bucket j，如果 bucket j被一个 lodger 记录占用，在将记录 y 存储在 bucket j 中之前，会寻找一个空 bucket 来重新放置 lodger 记录。如果 bucket j 由 host 记录占用，会寻找空位来存储记录y，并将其附加到链的末尾。如下图样例所示，最初有三个键：3、4和11，键3和11都哈希到 bucket 3，为了解决这个冲突，键11暂时占据 bucket 2，然后插入键2（哈希到 bucket 2），系统首先将键11迁移到附近可用位置——在本例中是 bucket 1，移动键11后，键2成功插入 bucket 2，此过程最大限度地减少了探测次数，并保持了对元素的高效访问。

Lodger Relocation可以看作一种动态的 Cellar Region 策略，确保PSL最小化（与 Separate chaining 相同）。其缺点是插入过程变得更加复杂。考虑查询请求是推荐系统的主要负载，所以我们忍者这种权衡取舍是值得的。

2.2.1.2 Bidirectional Cacheline-aware

NeighborHash努力将同一冲突链上的bucket放置在同一缓存行内，以尽量减少每个查询的内存带宽使用。在搜索可用存储桶的过程中，该算法首先检查同一缓存行中的存储桶。与仅在一个方向上进行探测的线性探测不同，NeighborProbing在缓存行内进行双向探测。如果没有找到，搜索将双向展开，以识别距离头部最近的可用 bucket。如图下图所示，这种方法最大限度地减少了查询过程中的跨缓存行探测。我们的实验结果表明，在负载因子为75%的1亿条记录的随机数据集上，每个查询的平均缓存行访问次数约为1.12，与线性探测的1.47次相比，通过 Bidirectional Cacheline-aware 后需要访问的缓存行更少。如果同一缓存行中没有可用的 bucket，则重新定位到附近的缓存行，其可以减轻TLB缓存未命中，并且与链中前一条记录的相对偏移较小，从而实现偏移压缩。

2.2.1.3 inline-chaining

与下面左图中传统Separate chaining通过冲突指针实现chaining不同，其每个bucket一般需要24B。而inline chaining利用高12位值字段表示相对偏移，实现冲突链表。具体实现如下面右图所示，缓存行大小一般为64B，我们设计每个缓存行包含四个bucket，每个bucket包含一个64bits的key、12bits的offset和52bits用于寻址的value。其中offset指向chaining中下一个元素的相对偏移，表示范围为-2047到2048，考虑到冲突分配策略的主要目的是在根节点附近找到合适的位置，12位相对偏移就足够了。在我们的实践中，12位偏移可以实现超过80%的负载系数。

针对上述优化，我们尝试通过benchmark来验证优化后的结果。如下两个折线图所示，其分别是在查找成功命中率90%及30%情况下的比对结果，参与比较的有以下结构：

RA：Random Access（表示内存随机访问的性能上限）

NB: Neighbor Hash

LP: Linear Probing

BT: bytell Hash

CH: coalesced hash

（一些性能表现不典型或者不及上述的结构未参与比较，如：ankerl::unordered_dense::map，tsl::hopscotch_map，Cuckoo hashing，std::unordered_map）

可以看到虽然NB比LP、BT、CH查询性能都要高，可是在大数据集下与 RA 的性能差距还是很大。但是NB按照平均访问的Cacheline个数(1.12)量化计算，理论分析性能应该与RA同一个量级，且其Memory load远未达到内存带宽上限。

RA为什么会这么快？我们尝试进行如下对比（左图：对比实现，右图：对比结果），当随机访问（RA）开启chasing（前后访问建立依赖）要比不开启chasing慢很多。这样比较的原因是，NB在CacheLine平均访问个数上与RA为同一量级，但是前后数据的访问却可能存在chasing。而存在chasing时慢的原因是，处理器指令流水线中的任何两条指令之间如果存在依赖关系，它们就不能在多发射指令流水线中并行执行。为了在存在chasing的情况下，实现并发执行访存指令，我们引入了AMAC。

前面说到，由于NeighborHash访问内存时CPU指令存在前后依赖，无法有效利用处理器多发射指令流水线来实现并发访存，故引入AMAC。我们在批量查询情况下，对每一次查找建立状态机，查找期间维护其状态。如图中所示需要批量查询四个Key时，第一个Key执行完Compute bucket及PreFetch bucket后不会阻塞等待结果返回，会执行下一个Key的指令，循环回第一个Key时大概率其需要读的数据已经加载到缓存中了。从而实现模拟在有chasing情况下的多发射指令流水线。

优化后如下图所示，我们比较NB、NB + amac-8以及NB + amac-32，可以看到大数据集时在amac-32的加持下要比裸NB快接近一倍。

除了应用了AMAC（异步内存访问链）来实现内存并发访问之外，我们参考了Swiss Table 引入了SIMD（单指令多数据）来加速查询过程。与Swiss table一条SSE指令通过比较 group Metadata 只查询比较一个key不同，我们通过一条SSE指令并行进行多个key的probing以提升查询吞吐。且由于不同key的probing sequence不同，我们参考IMV，设计了一个Residual Vector来临时存储未探测完的Key。下图为一个SIMD 查询的实例，在 Key-1 ~ Key-4 的 SIMD 指令查询中，Key-2 命中，Key-3 不存在。将 Key-1、Key-4 放至 Residual Vector 中等待 SIMD 向量填充满下一步执行。Key-5 ~ Key-8 的 SIMD 指令查询中，Key-5、Key-7 命中，而 Key-6、Key-8 未命中填充至前述 SIMD 向量中，执行下一步指令。

针对上述优化，我们通过benchmark来对比不同实现的性能差异。如下图所示，BBC: 带有AMAC优化的Swiss Table，NB: Neighbor Hash，RA: Random Access。当数据集较小时（256KB）NB + VEC比 NB + AMAC性能要高，这是因为在小数据集下Cache命中率高，key值的比较是性能的瓶颈。当数据集达到256M后，NB + AMAC性能反超，这时数据访问是才是性能的瓶颈。且在大数据集情况下 NB + VEC + AMAC达到了 RA + VEC + AMAC 70%～80%的性能水平，这与我们计算的理论水平（平均访问1.12个Cacheline）相符。

除此之外，为了了解NeighborHash的各种设计对性能的影响，我们对NeighborHash的以下三个关键设计进行了消融分析：

• Lodger Relocation: 在Coalesced Hashing的基础上使用此策略，后称为 PerfectCellarHash。

• Cacheline-aware Neighbor Probing: 在PerfectCellarHash的基础上构建，优先搜索最后一个节点缓存行附近可用的 bucket ，并将相对偏移量存储在单独的数组中，后称为NeighborProbing 。

• Inline Chaining: 扩展NeighborProbing，将值的高位12位作为相对偏移量编码，完成NeighborHash的完整实现。

结果如下图所示，就每秒数百万次操作（MOPS）而言，上述三种关键的NeighborHash设计分别使吞吐量提高了20%、30%和30%。值得注意的是，这三种设计并非完全独立；Lodger Relocation和Cacheline-aware Neighbor Probing的联合作用实现了偏移压缩，当与特定的使用场景相结合时，可以将其实现整合。且测试结果中 APCL 从1.72下降到了1.14，表明优化节省了内存带宽，实现了提高吞吐量的目标。我们还评估了Lodger Relocation的线性探测的APCL，结果为1.24。可以推断，与单向探测相比，双向探测对内存带宽效率的贡献约为9%。

我们的架构借鉴了 Google Mesa 的思想，存储系统由两个主要组件组成：批量查询子系统和更新子系统，如图所示。更新子系统管理数据更新，包括来自持续模型训练的用户行为和参数调整，确保系统反映当前用户行为。批量查询子系统解决了海量数据和高并发性的挑战，采用分布式部署，包含多个分片和副本，以能够处理每秒数十万次查询的峰值请求量。

更新子系统通过Controllers 监听数据版本，将数据更新至在线实例中。其中主要包含以下worker角色：

Listener：对数据挖掘，模型训练等数据源版本进行监听，有新版本则触发 Index worker。

Index：对数据源进行格式转换，索引构建（Text -> Protobuf / Binary），并实时更新数据版本的状态，使其可以被Update worker更新。

Update：监听数据版本状态，发现可被部署的新版本则进行rolling-update，逐副本重启换库。

• 多分片并行，多分片一致性

• 全量，增量，实时

• 重启的好处：节约内存，无读写冲突，最大化查询吞吐

• Maintenance：可以监听词表状态以及是否修改quota等，执行新表建表、删表、内存扩缩容、分片扩缩

• 一个表对应k8s上一组stateful-set

• CPU/MEM/NVME资源弹性伸缩，混部友好

其上述数据状态、词表状态等Metadata存储在Etcd中。

实时推荐系统不能承受任何停机时间，因此我们采用了一种滚动更新方法，一次更新一个副本，只需要1/n的额外资源。然而，这带来了在表更新期间维护不同分片上不同版本之间一致性的挑战。对于某些模型嵌入表，只有来自同一训练批次的数值才是可比的；我们称之为强版本数据。为了保持强一致性，我们通过查询协议直接在客户端和服务器之间通信分片和版本元数据，而不是仅仅依赖命名服务。这种方法最大限度地减少了更新期间的不一致性，并确保系统在处理频繁的数据更新时保持运行。

在拥有数十亿用户和物品的工业场景中，存在着大量的冷数据。与将所有数据存储在内存中相比，将冷数据存储在 NVMe 中，热数据存储在内存中更具成本效益。通过 neighbor-hash 原理，我们将其扩展到支持 NVMe 后端，这对于键很少而值很长的场景非常理想，我们将键、值偏移量和值长度加载到内存中，使用 Neighbor-hash-map 进行存储，而 NVMe 只保留值字节。读写使用 io_uring 以提高效率。

就缓存设计而言，我们在内存中维护完整的键集，简化了缓存过程。与传统的 LRU 缓存不同，我们的方法以最小的成本更新频率统计信息，允许通过异步线程高效地进行缓存逐出。

-End-

作者丨Alonzo、末一、志胜、飞云