图1 NetDSH 框架
Fig. 1 Framework of NetDSH
北京大学学报(自然科学版) 第62卷 第1期 2026年1月
Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 62, No. 1 (Jan. 2026)
doi: 10.13209/j.0479-8023.2025.091
国家自然科学基金(62302281)和山西省基础研究计划(202303021212016)资助
收稿日期: 2024–11–18;
修回日期: 2025–04–21
摘要 为提高分布式应用系统的网络性能, 提出一种基于可编程数据面的加速分布式检索系统 NetDSH。该系统能够优化可编程数据面的存储和数据处理能力, 通过自定义协议、Top-K 插入方法和 T 更新策略, 高效准确地剔除潜在的低质量候选答案, 从而提高网络传输性能。在搭建的测试平台上, 基于 4 种类型的数据集(SIF1M, SIF1B, SPACE1B 和 Random)对NetDSH进行评估。结果表明, 与传统的基于局部敏感哈希的分布式检索系统 TLSH 和 NetSHa 相比, NetDSH 可以将传输的数据包数目减少至原来的 1/3, 同时, 系统检索性能得到 3.2 倍的提升。
关键词 可编程数据面; 分布式系统; 近似最近邻检索; 局部敏感哈希算法
最近邻搜索(nearest neighbour search, NNS)是一种检索算法, 其目的在于从众多向量中识别出与特定查询向量距离最近的向量。该算法已被众多应用领域采纳, 用于优化查询处理流程。例如, 在网络搜索引擎[1]、模式识别[2]、计算机视觉[3]、推荐系 统[4]以及序列匹配[5]等领域, 对搜索速度和响应效率有极高的要求, 因此均采用近似 NNS 来提升搜索框架中查询处理的速度。在 NNS 中, 数据和查询均为多维向量, 在大规模数据集中寻找最近向量时, NNS 会消耗较多的时间, 从而影响系统的响应时间。为了在高维和大规模数据集中提升搜索效率, 近似最近邻搜索(approximate nearest neighbour sea-rch, ANNS)算法[6–7]应运而生。ANNS 与 NNS 的主要区别在于 ANNS 旨在寻找近似最近距离的向量。
局部敏感哈希(locality sensitive Hashing, LSH)算法[8–9]是一种应用广泛且有效的 ANNS 方法。LSH 通过设计一系列哈希函数, 能够以较高的概率, 将相似向量映射到同一个哈希桶中, ANNS 算法在处理查询时, 仅需检查少量的桶, 即可高效地定位相似向量。为进一步提升 ANNS 算法性能, 工业界和学术界开发了多种基于 LSH 算法的新方法, 例如, MinHash 使用杰卡德距离实现向量的哈希处 理[10], E2LSH 实现基于欧几里得距离的哈希函数[11], SimHash 用角度距离计算哈希函数值[12]。研究人员还提出三元局部敏感哈希(ternary LSH, TLSH)方 法[13], 利用硬件技术加速向量到哈希桶的映射计算, 旨在进一步提高 ANNS 的效率。
云计算时代, 分布式应用快速发展, 数据规模持续扩大, 数据向量维度增加, 分布式系统应用局部敏感哈希(LSH)算法来应对查询显得尤为必要。近年来的研究多集中于构建高性能分布式 LSH 检索系统[14–18]。分布式 LSH 系统进一步提升了近似最近邻搜索(ANNS)的效率, 但也增加了网络中的数据传输任务, 导致显著的通信延迟。具体而言, 系统处理查询时, 每个服务器会在其存储的哈希桶中搜索多个近似向量作为候选答案, 随后候选答案通过网络传输至“代理服务器(agent server)”进行过滤, 以便确定 Top-K 个最优答案, 作为查询结果。由于所有答案都需要通过网络传输至代理服务器, 因此会造成网络拥塞和高延迟。有些研究者注意到分布式系统的网络性能问题, 并尝试优化服务器间的负载分配[15,19–20], 这些方法通过平衡服务器间发送的答案数量来减轻网络负担, 但并未减少答案的总量, 因此网络性能的提升相对有限。Zhang 等[16]提出一种基于 LSH 的分布式搜索系统, 该系统利用可编程交换机[21]的计算能力, 实现“尽力而为”的答案过滤方法, 降低分布式系统的网络成本并提升性能。但是, 该系统处理大规模并发查询时, 由于网络过滤效率低, 大部分答案依旧被转发到代理服务器进行过滤。
上述研究均是通过尝试降低网络负载来减少网络数据包的传输。为进一步提高分布式系统网络数据传输能力, 本文提出一种基于可编程数据面优化的 LSH 分布式检索系统 NetDSH。将系统处理查询产生的答案传输和答案过滤任务卸载到网络数据面执行, 在可编程交换机的高性能数据面优化答案存储和过滤过程。为实现 NetDSH, 我们还提出一项互联网协议(IP)扩展方案, 用数据面解析携带答案的数据包, 并执行存储和过滤方法, 在可编程数据面设计了一种新的基于距离的答案排序算法。此外, NetDSH 实现 Top-K 插入方法和 T 更新策略, 从而保证在可编程交换机上能够有效地剔除非 Top-K的候选答案, 同时确保搜索质量不受损害。最后, 在 4 种不同类型的数据集上对 NetDSH 进行评估, 验证本文方法的有效性。
局部敏感哈希(LSH)算法是高维空间中解决相似最近向量检索问题的高效哈希技术之一。LSH 的定义如下: 设 Dist(x, y)为向量 x与 y之间的欧几里得距离, LSH 算法通过生成一系列哈希函数{fh : fh (Rd)→C}, 将 d维向量 R映射为一个常数 C。对于任意两个向量 x, y∈Rd, 若满足式(1), 它们被哈希为相同值的概率至少为 P1; 若满足式(2), 则被哈希为相同值的概率最多为 P2。LSH 函数的设计目标是确保 r1 < r2且 P1 > P2。若 Dist (x, y) ≤ r1, 则
Pr[fh(p)=fh(q)]≥P1, (1)
若 Dist (x, y) ≥ r2, 则
Pr[fh(p)=fh(q)]≤P2。 (2)
在 LSH 算法中, k个 LSH 函数可以将一个 d维向量 x哈希为 k个不同的常数, 这 k个常数连接起来构成 k维向量, 代表向量 x的签名, 记为 Sign(x)= (fh1(x), ..., fhk(x))。LSH 算法构建了 L个哈希表, 每个哈希表包含 k个 LSH 函数, 向量 x在每个哈希表内被映射成 k 维向量签名, 最终 LSH 为向量 x生成L个签名, 在每个哈希表内, 具有相似签名的向量会放入同一个哈希桶中。
LSH 算法的计算过程分为两个阶段。第一阶段, 将向量数据集哈希至不同的签名, 并将数据及其签名插入不同哈希表的哈希桶中。例如, 向量x通过第 i个哈希表的 k个 LSH 函数处理后, 形成 k维签名, 记为 Sign_i(x), 然后将 Sign_i(x)插入第 i个哈希表的对应桶中。第二阶段, 处理查询, LSH同样使用哈希表内的 k个 LSH 函数对查询 q进行哈希处理, 得到其签名。然后, LSH 在哈希表中定位相应的桶, 并根据 q的签名找到相似的向量, 计算相似向量与 q的欧几里得距离值, 记为候选答案。最终, LSH 算法将候选答案按距离值从小到大排序, 获得 Top-K 的答案。
云计算时代, 分布式系统通常基于 MapReduce框架构建。MapReduce 框架包括 Map 和 Reduce 两个阶段, 简化了复杂的计算任务。该框架将数据转换为(Key, Value)的形式, 处理查询时, 在 Map 阶段检索与查询具有相似 key 值的向量, 在 Reduce 阶段, 通过比较相似度, 过滤较差的向量值, 保留 Top-K的向量, 发送给用户。本研究阐述一种基于 Map-Reduce 框架的分布式 LSH 搜索系统。我们定义分布式系统包括一个代理服务器和 N 个检索服务器, 代理服务器存储数据的索引 ID 和数据向量, 每个检索服务器上部署 LSH 算法, LSH 哈希表内存储每个被映射的向量, 以(key=数据向量签名, value =数据索引 ID)的形式存储, 其中 key 由哈希函数生成, value 则唯一地对应代理服务器上的具体数据向量。分布式系统将所有的(key, value)键值对存储在检索服务器上, 且保证具有相同或相似的 key 的键值对位于同一服务器的哈希表内。当系统处理查询时, 首先计算查询的签名, 然后将查询发送到检索服务器, 找到具有相似签名的哈希表, 如果查询签名与表内的向量签名距离值在误差范围内, 则将其记为候选答案, 以(Qid, Did, Dist)的形式存储, 其中 Qid 代表查询的索引 ID, Did 代表数据向量的索引 ID, Dist 代表查询与数据签名的欧几里得距离。所有的候选答案通过网络传输到代理服务器。代理服务器选出距离最小的 Top-K 个答案发送给用户。
为提升分布式 LSH 系统的网络数据传输性能, 可以考虑多种方法。一种朴素的策略是检索服务器只发送单一数据包, 将所有候选答案封装在该数据包中。但是, 当系统需要检索的答案数 K 比较大, 且答案分散在多个服务器时, 这种策略的效果会大打折扣。因此, 本研究考虑在网络数据面优化候选答案的选取。近年来, 网络数据面的能力得到显著提升, 可编程交换机和智能网卡等设备的出现, 为网络数据面提供了较大的存储资源以及较高的计算和编程能力, 使得服务器端侧的一些算法可以卸载至网络侧进行加速。其中, Barefoot Networks Tofino交换机(亦称 P4 交换机)[21]是微软提供的高性能网络硬件设备, 可以灵活地对交换机的数据面进行编程。P4 交换机具有灵活的解析器与匹配–动作指令转发, 支持自定义协议解析数据包, 并通过编程执行一系列简单的算术运算和存储读写功能, 通过硬件实现数据的高速处理。P4 交换机支持高达 25M TCAM与 480M SRAM 的存储容量, 具备使用运算器(ALU)执行布尔与算术运算的能力。
本研究设计一种基于可编程数据面的加速分布式检索系统 NetDSH, 可降低分布式 LSH 系统的检索处理时间, 同时不降低系统的查询质量。NetDSH 沿袭了分布式 LSH 检索系统的基本架构, 并在此基础上设计两项核心数据面优化策略: Top-K 插入方法和 T 更新策略。图 1 展示 NetDSH 的系统框架。
在逻辑架构上, NetDSH 将可编程交换机作为系统网络数据传输通道, 实现系统内多个服务器之间的互连, 每个检索服务器负责检索查询的多个候选答案, 这些候选答案被封装于 IP 数据包中, 并通过可编程交换机数据面转发至代理服务器, 数据面通过一系列计算以及匹配操作来转发候选答案。Net-DSH 利用交换机数据面的计算资源来执行数据包分析、过滤和聚合候选答案等, 从而优化网络流量传输过程。
图1 NetDSH 框架
Fig. 1 Framework of NetDSH
具体流程上如下: NetDSH 对于来自检索服务器传入网络的每个数据包, 由交换机解析协议, 并获取候选答案(Qid, Did, Dist); 数据面识别查询 Qid, 属于同一个 Qid 的候选答案, 被存储在交换机的同一寄存器; NetDSH 执行 Top-K 插入方法和 T 更新 策略, 过滤同一 Qid 下的候选答案, 仅保留 Top-K的答案, 当前 Qid 的答案处理结束后, 交换机构造数据包, 携带寄存器内 Top-K 的答案发送到代理服务器。
简而言之, NetDSH 接收到查询请求后, 选择相应的检索服务器处理查询, 检索服务器会在哈希表内匹配与查询相似的数据签名, 并生成候选答案; 随后服务器产生的所有候选答案传送至交换机统一解析存储, 交换机执行 Top-K 插入和 T 更新策略, 获取属于该查询的 Top-K 答案, 并发送至代理服务器。通过上述方式, NetDSH 将答案过滤任务卸载至可编程数据面, 利用硬件性能加速查询处理, 降低端侧的答案数量, 从而有效地降低通信成本, 提升系统的检索效率。
NetDSH 能够为分布式 LSH 检索系统带来显著的网络性能提升, 但也面临如下 5 个方面的挑战。
1)可编程交换机最初是为网络数据包转发任务设计的, 同时支撑协议解析以及基本运算和存储操作。NetDSH 需要在不影响交换机常规网络功能的前提下, 优化分布式系统的特定数据通信, 实现分布式系统检索服务器与代理服务器之间的高性能数据传输, 构建高可用、高扩展性的分布式 LSH 检索系统。
2)分布式系统产生的每个候选答案都与一个距离值相关联, 用来表示答案与查询的相似度, 但需要考虑如何定义候选答案的排序, 以便实现数据面 Top-K 的插入和存储, 保证 NetDSH 能高效率排序答案, 且实现正确的过滤功能。
3)交换机内存有限, 但候选答案数目众多, NetDSH 在可编程数据面需要对比大量答案, 决定丢弃答案还是存储至寄存器中。因此必须设定一个衡量标准, 过滤掉所有不符合标准的候选答案, 并将优于标准的答案更新至寄存器中。随后, 交换机可将所有寄存器内的答案传输至代理服务器。
4)可能存在某些查询的答案全部符合标准, 则NetDSH 需要考虑使用交换机将答案全部存储并发送至代理服务器的可能性, 最坏的情况是无法过滤掉任何答案, 这会影响系统性能。
5)当系统处理过多查询时, 交换机需要同时为每个查询开辟一块内存来存储答案, 受内存限制, 交换机数据面无法有效地存储每个查询的所有答案, 若大部分答案在交换机队列中等待, 会延长系统的响应时间, 降低系统吞吐量, 因此, NetDSH 必须在交换机存储、答案队列等待与系统响应时间之间找到一个平衡点。
为解决挑战 1 提及的不影响常规网络功能, 且为支撑 NetDSH 的 Top-K 插入方法与 T 更新策略操作的支持, 本研究充分调研了交换机可编程数据面特性, 对传统 IP 网络协议进行扩展, 并在交换机部署相应的解析程序, 提升可编程交换机在处理候选答案数据包的效率。我们将此扩展简称为 NetDSH协议。图 2 展示符合 NetDSH 协议的数据包的结构。NetDSH 协议利用 IP 字段中的保留位(ToS)来标识 NetDSH 数据包(即包含候选答案的数据包)。
数据包的构造如下: 当 IPToS 保留位设置为 1时, 标识该包被封装为 NetDSH 包。该协议扩展方法在数据中心网络中广泛使用, 用来实现自定义协议[22], 同时不影响传统网络功能运作。
NetDSH 数据包由以下 3 个部分组成: 标准 IP头部、NetDSH 头部和 NetDSH 负载。标准 IP 头部通过 IPToS 字段区分该协议数据包; NetDSH 头部包含 4 字节 Qid, 指示答案所属的查询 ID, 4 字节的Num 表示候选答案数量; NetDSH 负载包含 Num 个数据对 D, 每个数据对由 4 字节的 Did 和 4 字节的Dist 构成, 分别表示数据索引 ID 和距离值, 距离值用于评估候选答案与查询之间的距离。
在可编程交换机数据面配置相关程序后, 可编程交换机数据面仅会拦截并解析 NetDSH 协议的数据包, 其他数据包则直接转发。因此, NetDSH 系统不会对常规网络功能产生影响。
分布式系统的代理服务器的主要功能是接收来自一个或多个检索服务器的候选答案, 随后对这些答案进行排序, 并选取前 K 个最优答案作为查询结果。这一过程称为答案归约, 该过程给代理服务器带来显著的计算压力。随着分布式搜索系统规模的扩大、数据规模增加和并发查询数量增多, 网络答案传输和代理服务器的答案归约过程逐渐成为系统性能的限制因素。
图2 NetDSH 协议
Fig. 2 Protocol of NetDSH
为解决分布式系统的性能瓶颈, NetDSH 将答案归约任务从代理服务器卸载至网络交换机, 在交换机数据面存储候选答案, 筛选掉质量较低的答案, 并获取 Top-K 的答案, 发送到代理服务器。这种卸载之所以可行, 是因为可编程数据面可以通过程序获取所有候选答案, 并利用与每个答案相关的距离值评估答案的质量。相比之下, 检索服务器仅能获取自身检索的候选答案; 尽管代理服务器可以获取全部答案, 但处理全部答案的效率低, 从而制约系统性能。然而, 在可编程数据面识别并筛选掉质量较差的候选答案是一项困难的任务(挑战 2～4), 例如存在候选答案(Did, Dist), 其中 Dist 是交换机内存储的局部最大值, 但不能直接丢弃这个答案, 因为它可能是全局的 Top-K 候选答案之一。
为应对上述挑战, 一种直观的方法是在交换机数据面为每个查询设定一个阈值 T, 所有距离值大于 T的候选答案被直接丢弃, 其他答案被转发至代理服务器。在该方法中, 阈值 T的设定至关重要。为此, Zhang 等[16]提出一种改进方法, 交换机数据面开辟存储区域, 存储同一查询的 K个答案, 记录存储够 K个答案后的最大距离值, 将其作为阈值 T(K是代理服务器应返回给用户的答案数量(即 Top-K个)。然后, 根据记录好的阈值 T决定是否丢弃后续答案。然而, 该方法的局限性是, 如果提前记录了最大的距离值作为阈值, 则无法过滤掉任何答案。
NetDSH 提出一种改进的 K插入方法, 可以在保留候选答案的同时保持搜索质量。该方法通过使用数据面的寄存器来实现, 每个寄存器类似一个 C语言的数组。NetDSH 为每个寄存器分配 K+3 个槽位, 其中 K个槽位用于存储对应的候选答案, 其余3 个为功能槽位。如图 3 所示, 功能槽位包括存储查询 ID(Qid)、存储阈值(T)和存储计数值(Count)。当一批候选答案抵达交换机后, NetDSH 将根据答案的距离值, 将其插入相应的寄存器中, 并将功能槽的阈值 T更新为已存储答案的最大距离值。由于Top-K 插入方法仅插入最开始的 K个候选答案, 并依次填入寄存器槽位, 所以其时间和空间复杂度均为 O(K)。
在同一个查询的 K个槽位被占用情况下, 将寄存器功能槽计数值记为 K, 标志 NetDSH 将转入第二阶段, 即 T 更新策略阶段。在此阶段, NetDSH 主要过滤较差的候选答案, 距离值超过 T的答案将被舍弃, 因为它们相较于已记录的 K个答案质量较差; 距离值小于等于 T的答案, 会纳入对应查询的寄存器。图 4 展示候选答案 Dt(Did, Dist)的距离值不大于 T时执行的 T 更新策略, NetDSH 首先遍历寄存器中的所有答案, 额外记录寄存器内的两个信息: 距离值最大(Dm)和次大(Dn)的候选答案, 随后 Net-DSH 将 Dt 替换至 Dm 位置的答案, 然后更新寄存器功能槽的 T(T取 Dt.Dist 和 Dn.Dist 中的较大值)。上述插入操作的时间复杂度为 O(K)。
图3 Top-K 插入方法
Fig. 3 Top-K insertion method
可编程数据面实现的 T 更新策略通过 T 替换算法(算法 1)来实现。
算法 1 T 替换算法
当 NetDSH 处理大规模查询时, 需要为每一个查询安排一个寄存器存储相应的候选答案, 当数据包抵达交换机时, 将选择一个寄存器插入其候选答案。本研究采用线性搜索来确定寄存器, 寄存器替换算法(算法 2)描述交换机为新查询确定寄存器的过程。
图4 T 更新策略
Fig. 4 T Updating Strategy
算法 2 寄存器替换算法
具体来讲, 若交换机通过线性查找的方式确定一个寄存器已包含相同的查询 ID(算法 2 第 2～6 行), 则将候选答案追加至寄存器末尾, 直至寄存器的 K个槽填满为止, 若填满则依据 T 更新策略更新候选答案。若是一个新的查询, 则交换机首先定位一个“空”寄存器, 并将数据包中候选答案追加入寄存器, 并设置寄存器的功能槽状态, 包括相应的查询 ID、T和计数值(算法 2 第 7～11 行)。
当 NetDSH 的检索服务器完成当前查询 ID 的检索, 将发送一个带 fin 标志的 NetDSH 数据包(NUM = 0)。对于每个查询, 所有检索服务器均需发送带fin 标志的数据包, 即便未执行搜索。交换机接收到带 fin 标志的数据包时, 会将寄存器功能槽的计数值增加 1, 寄存器随后向代理服务器发送候选答案, 且在计数器记录了每个检索服务器到达的标志后, 清空寄存器内容。
NetDSH 方法主要依靠交换机中寄存器实现相应功能, 寄存器数量决定并行执行的查询数量。然而, 由于经济成本和内存的限制, 交换机数据面可开辟的寄存器数量是有限的, 如果所有寄存器均被占用, 带有新查询 ID 的 NetDSH 数据包将无法得到处理。
我们设计一种启发式策略, 以便快速获取一个合适的寄存器。该启发式策略体现一种基于时间和结束标志的优先选择机制。若所有寄存器均被占用, 数据包将被放入队列中, 等待一个寄存器完成当前的查询 ID 并清空内存。在 T 更新策略中, Net-DSH 需要等到寄存器接收到所有检索服务器的 fin标志时, 才允许交换机构造数据包, 并将寄存器的答案发送至代理服务器, 然后清空寄存器。然而, 该操作必须与响应时间相平衡。因此, 我们的启发式策略为每个寄存器配备时间触发器, 当队列有数据包等待时, 检查寄存器是否接收到任何 fin 标志或达到时间触发器要求(根据寄存器计数值, 当寄存器收到 fin 标志, 计数值会增加 1, 此时计数值大于 K), 一旦满足任一条件, 寄存器必须构造 Net-DSH 数据包并清空其内存(算法 2 第 12～16 行)。该策略能够保证 NetDSH 的响应时间与搜索质量之间的平衡性。在关于寄存器替换算法的描述中, 本研究通过 3 次循环定位, 就可以插入查询的寄存器, 但在实际过程中, 只需通过一次循环记录可插入寄存器的位置信息, 即可实现替换算法的优化。该算法的时间复杂度为 O(T), 其中, T 为寄存器的数目。
可编程交换机通过解析并识别 NetDSH 协议数据包来剔除低质量候选答案, 对其他类型数据包则直接转发。在完成优质答案筛选后, 交换机会将其聚合为新的 NetDSH 数据包并发送至代理服务器。这意味着交换机的输入和输出均为 NetDSH 数据包, 该方法可以有效快速地扩展到多交换机上部署。一种初步扩展方案是为每台交换机独立部署 NetDSH策略, 通过查询分片, 将高并发查询划分为多个子集, 由不同交换机并行处理。然而, 此方案需预先静态地分配查询任务, 且难以动态地平衡交换机之间的负载差异, 导致资源利用率不均衡。
本文提出多交换机层次化协同过滤架构(图 5), 通过边缘和核心交换机的分工协作, 突破单交换机内存和算力瓶颈。核心机制如下: 边缘交换机执行第一级答案过滤; 每台交换机执行 NetDSH 策略, 负责部分检索服务器, 并过滤检索服务器收到的每份答案; 边缘交换机不负责存储所有答案, 而是存储阈值, 用于及时过滤低质量候选答案, 并将优质答案转至核心交换机; 核心交换机汇聚多边缘交换机的过滤结果, 执行精细化二次过滤(保留全局Top-K 答案)。
例如, 边缘交换机 Sw1 负责对服务器 s1 和 s2上的候选答案进行过滤, 仅保留优质结果转发至核心交换机 Sw-core, 其他边缘交换机负责相应服务器上的候选答案。核心交换机负责接收所有来自边缘交换机的优质候选答案, 并执行 NetDSH 策略执行二次过滤。边缘交换机负责过滤的服务器越多, 核心交换机的压力越小, 越容易应对大规模的并发查询。
该策略具有以下优势。首先是动态负载均衡, 通过分布式查询处理与实时结果聚合, 可以避免强制路由带来的性能开销, 支持候选答案在传输路径上按需过滤。其次是资源协同优化, 层级化存储与计算资源的高效协同可有效地降低核心交换机 40%以上的负载。最后是弹性扩展能力, 通过增加边缘交换机数量或引入多级核心交换机, 可以线性地扩展系统的处理能力, 适配超大规模数据中心网络拓扑。
图5 NetDSH 多交换机协同过滤
Fig. 5 Multi-switch cooperative filtering of NetDSH
可编程交换机在云计算平台、分布式应用以及数据中心广泛部署, 使得网络侧具备灵活的数据面和客观的计算存储资源。在 NetDSH 系统中, 通过运用交换机可编程数据面相关技术, 可以实现候选答案的插入、过滤、聚合及转发过程的优化。
目前, 可编程数据面普遍采用多管道模型处理数据包。以 P4 交换机为例, 用户需要通过定制数据面的管道配置文件来满足特定情况下数据包进入管道, 并提取相应信息进行操作。NetDSH 协议正是利用上述特性, 当携带候选答案的数据包通过交换机数据面管道时, 交换机依据 NetDSH 协议和配置文件预设好状态自动机, 通过状态跳转, 解析头部字段, 利用 IPToS 字段的状态, 将 NetDSH 协议包与常规数据包区分开。常规数据包的 IPTos 字段设置为 0, 在管道状态机内被识别后, 自动匹配的目的地址等信息被转发出去。NetDSH 数据包则进入寄存器, 交换机对包内数据执行 Top-K 插入、过滤和聚合等操作。
NetDSH 主要在可编程数据面实现复杂的插入和过滤功能, 未改变网络基础转发功能, 且不破坏分布式 LSH 系统的基本架构, LSH 算法也正常部署在分布式检索系统的检索服务器上。NetDSH 充分利用标准的 LSH 函数生成的数据签名和距离值, 在数据面进行 Top-K 插入和 T 更新策略。因此, Net-DSH 保持了 LSH 函数在搜索质量方面的优势, 确保与传统的基于 LSH 的搜索方法具备同等的性能。
NetDSH 的运行并不干扰交换机的常规网络功能, 它与常规网络功能并行运行, 且仅占用部分内存和计算资源, NetDSH 依据特定的 IPToS 字段识别并处理 NetDSH 数据包, 其他常规数据包则正常转发, 无任何中断。此外, NetDSH 具备在数据面调整其寄存器资源分配的灵活性, 可以轻松地扩展到多个交换机, 实现多个交换机协同过滤的策略。基于内存叠加和数据面资源的优势, 可有效地应对复杂网络下大规模并发查询, 提高分布式系统的检索 性能。
本研究构建了一个测试平台, 包括一台 Bare-foot Tofino 交换机(吞吐率 3.2Tb/s)和 8 台商用服务器, 所有服务器均与交换机直连, 每台服务器配备Intel®Xeon®8171M CPU(3.5GHz 频率, 128 个 CPU核心, 256GB 运行内存)。在服务器上利用 kuberne-tes 搭建分布式框架, 每台服务器运行 25 个虚拟机, 每个虚拟机独占 4 个 CPU 核心和 8GB 运行内存。虚拟机之间通过 OpenvSwitch(OVS)进行通信。在测试平台, 设置一个虚拟机作为代理虚拟机, 并且给代理虚拟机配置 20 个 CPU 核心和 40GB 运行内存, 负责存储所有数据向量和索引 ID, 并负责筛选Top-K 答案, 其他虚拟机则存储由 LSH 算法处理的数据。
本研究采用如下 4 种类型的数据集。
1) SIF1M 数据集[23]。从图像中生成, 用于评估近邻搜索算法的性能, 本研究获取 10 亿个 128 维的浮点向量作为基础数据集。
2) SIF1B 数据集[23]。从文本中生成, 是一个评估大规模向量搜索中 ANNS 算法性能的经典数据集, 本研究获取 10 亿个 128 维的字节向量作为基础数据集。
3) SPACE1B 数据集[24]。源自一个商业搜索引擎的生产数据。本研究获取 10 亿个 100 维的字节向量作为基础数据集。
4) Random 数据集[16]。通过从正态分布 Nd(0, 1)中的采样点构建, 其中 d =128。查询是通过对正态分布 Nd(0, r)添加一个小扰动生成, r = 0.25。本研究生成 10 亿个 128 维的字节向量作为测试数据集。
本研究将 NetDSH 与其他两种分布式方案进行对比: 服务器端实现的分布式 LSH 算法(TLSH)[13]和基于在网计算实现答案部分过滤的分布式 LSH系统(NetSHa)[16]。测试平台预先通过 LSH 算法将所有数据加载到不同的虚拟机, 通过代理虚拟机用单 CPU 核发送查询, 定义单核发送查询为标准化发送方式(ConRate=1.0)。
对于每种类型的数据集, 运行 20 次, 并尽可能记录不同方案的结果平均值以及 95%的置信区间值。在每次实验中, 平台从数据集中随机发出 1000万个查询, 记录从代理虚拟机发送查询到候选答案返回代理虚拟机并取得 Top-K 答案的时间。可编程交换机的 SRAM 支持最大 480×4096 个 64 位寄存器。我们使用 10000 个 64 位寄存器, K设置为 50, 每个寄存器有 K+3=53 个槽位, 默认代理虚拟机将向用户返回前 50个答案。
我们对 NetDSH 与方案 TLSH 和 Netsha 的查询效率进行评估。图 6 展示 20 次实验的平均查询耗时(包括 95%置信区间), 可以看出, Net-DSH 处理查询的性能显著提升, 其原因在于可编程数据面能充分减少低质量答案, 并在寄存器中保留单个查询的Top-K 答案, 从而减轻分布式系统的网络拥塞, 降低代理虚拟机的工作负载。性能提升可归因于以下3 个方面。
首先, 系统在网络数据面的排队延迟大幅度降低。由于数据包数量减少, 多数低质量答案被提前丢弃, 交换机内数据包队列长度缩短, 交换机的网络负载和代理虚拟机的工作负载显著减轻。其次, 代理虚拟机的读写开销得到优化。因为代理虚拟机需要接收来自网络的数据包, 且通过中断进行读写调用, 仅接收处理Top-K 答案的数据包, 减少了不必要的读写调用且获取到正确的答案。最后, 代理虚拟机的处理效率大幅提高。由于代理接收的数据包中基本上只包含 Top-K 的答案, 其处理过程仅需根据答案的索引 ID 获取数据, 省略了原分布式系统的排序和过滤操作, 降低了 CPU 的工作负载。
本研究设计的 Top-K 插入方法和 T 更新策略有助于优化系统的网络通信效率, 也能对终端主机性能产生正面影响。为了更明确地展示 NetDSH 对代理虚拟机工作负载的优化, 我们在执行 1000 万次查询时, 统计代理虚拟机接收到的数据包数量, 结果如图 7 所示。以 TLSH 接收到的数据包数量作为基线(记为 100%), NetSHa和NetDSH的数据包接收比例(百分比)分别为其接收数量与 TLSH 接收数量的比值。从图 7 可以看出, 与 TLSH 和 NetSHa 相比, NetDSH 的数据包数量显著减少, 与 TLSH 相比减少约 94%数据包, 与 NetSHa 相比进一步减少 12 个百分点, 并且搜索效率至少提高 3.2 倍。
图6 三种方法的性能评估
Fig. 6 Performance of three methods
图 8 展示 NetDSH 在不同查询工作负载(即不同的网络利用率水平)下的性能表现。在实验配置中, 基准线并发查询速率(ConRate=1.0)指 NetDSH 仅使用一个 CPU 核发送查询请求的速率。为了提高并发查询速率, 我们通过增加代理虚拟机的 CPU 核数来增加同一时间的可发送的查询数目。提高查询速率后, 可以进一步提高分布式系统的检索性能, 但更高的查询速率会导致性能提升略有下降, 原因是更高的查询速率会引发更多的可编程数据面缓存未命中, 导致更多的答案需要排队等待数据面寄存器资源的释放。当 ConRate>10.0 时, 交换机处理寄存器上的答案的耗时增加, 更多的候选答案在交换机队列中等待, 导致系统在网络侧传输的效率效率降低。为避免此问题, 一种有效的解决方案是增加交换机寄存器的数量。然而, 目前可编程交换机的SRAM 内存有限, 在保持 K=50 的情况下, 最多只支持 40000 个 64 位的寄存器。即使在交换机内存受限的情况下, 提高系统的并发查询速率, NetDSH 的性能改进依然显著。
图7 3 种方法的代理虚拟机收到的数据包数目
Fig. 7 Received packets of agent VM of three methods
并发查询速率以ConRate=1.0为基准
图8 NetDSH 在不同的并发查询速率下的性能对比
Fig. 8 Performance of NetDSH in different ConRate
通过对比 3 种方案的召回率和 F1 分数来衡量 3种解决方案的搜索质量, 结果如图 9 所示。实验中, 固定 K值为 50。假设返回的 K个答案中包含 n个正确答案, 则应有正确答案 Kt个, 本实验中 K=Kt, 则正确率=n/K×100%, 召回率=n/Kt×100%, F1 分数= 2×正确率×召回率/(正确率+召回率)。
从实验结果可以看出, NetDSH 完全在交换机中实现答案过滤策略, 且能够保证其检索质量与传统的分布式检索框架基本上一致。原因是在大规模并发查询下, 为及时将已过滤的答案传输给代理, NetDSH设置了定时策略, 在超过时限后 NetDSH 会清空寄存器并发送存储的答案到代理虚拟机。在最坏的情况下, 极小部分的答案可能会被丢弃, 检索质量会略有降低。
图9 3 种不同方法的搜索质量
Fig. 9 Search qualities of three methods
NetDSH 在不同的系统参数设置下会表现出不同的性能, 寄存器的槽位数量 K是影响 NetDSH 性能的主要参数。K值决定交换机可以同时处理多少个答案, 在交换机内存容量固定的情况下, K值越大, 交换机可同时存储的查询数量越少, 但可为单个查询存储更多的候选答案, 从而实现更优的搜索质量。
本实验中, 交换机的限制为 10000 个 32 位寄存器, 每个寄存器可配置 203 个槽位, 通过改变每个寄存器的槽位数量(K值从 50 变化到 200), 测试NetDSH 处理查询的性能, 结果如图 10 所示。可以看出, 寄存器的槽位越多, NetDSH 获取 Top-K 个答案所需的时间越长。原因是在 Top-K 插入方法中, 若候选答案小于等于阈值 T, 则交换机需要进行 K次比较才能保留该答案, 剔除寄存器内最差答案, 并且根据 T更新策略重新生成最差答案和次差答案, 因此 NetDSH 处理查询的耗时会增加。
图 11 展示不同的 K值对应 NetDSH 的搜索质量。可以看出, 随着 K值增大, NetDSH 处理查询的性能会降低, 但搜索质量会提高, 所以在大规模查询下, NetDSH 可以实现更好的检索质量。从实验结果还可以看出, NetDSH 并不破坏传统的分布式检索方法, 保持交换机寄存器个数不变, 增大 K值后, 交换机内存储的单一查询的候选答案增多, 在保证性能的情况下可以有效地提高搜索质量。
图10 NetDSH 在不同 K值下的性能对比
Fig. 10 Performance of NetDSH with different K
图11 NetDSH 在不同 K值下的搜索质量
Fig. 11 Search quality of NetDSH with different K
本研究提出一种基于可编程数据面加速的分布式检索系统 NetDSH 系统的设计理念与实现路径, NetDSH 旨在通过可编程数据面提升分布式 LSH 检索系统的效率, 核心设计理念是在不降低搜索质量的前提下, 能够保持现有分布式搜索系统的完整性, 并且通过利用可编程交换机的计算资源来最小化通信开销。NetDSH 引入定制化的网络协议, 并在可编程数据面实现 Top-K 插入和 T 更新策略, 过滤低质量答案, 降低系统通信成本。NetDSH 充分利用可编程数据面的加速能力, 创新性地设计出完全卸载到网络侧加速的答案过滤功能。由于单交换机内存资源优先, NetDSH 在高效处理大规模并发查询方面依然面临挑战。本文讨论了关于多交换机协同过滤 NetDSH 系统方案的可行性, 通过边缘交换机和核心交换机实现层次化过滤, 充分利用多交换机的寄存器完成复杂网络下的答案过滤, 缓解高并发查询带来的效率问题。下一步工作中, 我们将致力于实现多交换机协同过滤方案, 并聚合来自不同查询的候选答案, 进一步提高系统的性能。
参考文献
[1] Das A, Datar M, Garg A, et al. Google news personali-zation: scalable online collaborative filtering // Proce-edings of the 16th International Conference on World Wide Web. New York, 2007: 271–280
[2] Azzopardi G, Azzopardi N. Trainable COSFIRE filters for keypoint detection and pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelli-gence, 2013, 35(2): 490–503
[3] Charleen, Angelica C, Purnama H, et al. Impact of computer vision with deep learning approach in medi-cal imaging diagnosis // The 1st International Confer-ence on Computer Science and Artificial Intelligence (ICCSAI). Jakarta, 2021: 37–41
[4] Das A. S, Datar M, Garg A, et al. Google news persona-lization: scalable online collaborative filtering // The 16th International Conference on World Wide Web (WWW). New York, 2007: 271–280
[5] Berlin K, Koren S, Chin C. S, et al. Assembling large genomes with single-molecule sequencing and loca-lity-sensitive hashing. Nature Biotechnology, 2015, 33 (6): 623–630
[6] Huang Q, Feng J, Zhang Y, et al. Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proceedings of the VLDB Endowment, 2015, 9(1): 1–12
[7] Li J, Yan X, Zhang J, et al. A general and efficient querying method for learning to hash // The 2018 In-ternational Conference on Management of Data (SIG-MOD). New York, 2018: 1333–1347
[8] Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // The Thirtieth Annual ACM Symposium on Theory of Com-puting (STOC). New York, 1998: 604–613
[9] Tao Y, Yi K, Sheng C, et al. Quality and efficiency in high dimensional nearest neighbor search // The 2009 International Conference on Management of Data (SIGMOD). New York, 2009: 563–576
[10] Broder A Z, Charikar M, Frieze A M, et al. Min-wise independent permutations. Journal of Computer and System Sciences, 2000, 60(3): 630–659
[11] Datar M, Immorlica N, Indyk P, et al. Locality-sensiti-ve hashing scheme based on p-stable distributions // The Twentieth Annual Symposium on Computational Geometry (SCG). New York: 2004: 253–262
[12] Charikar M. S. Similarity estimation techniques from rounding algorithms // The Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC). New York, 2002: 380–388
[13] Shinde R, Goel A, Gupta P, et al. Similarity search and locality sensitive hashing using ternary content addres-sable memories // The 2010 International Conference on Management of Data (SIGMOD). New York, 2010: 375–386
[14] Bahmani B, Goel A, Shinde R. Efficient distributed lo-cality sensitive hashing // The 21st ACM International Conference on Information and Knowledge Manage-ment (CIKM). New York, 2012: 2174–2178
[15] Li J, Cheng J, Yang F, et al. Losha: A general frame-work for scalable locality sensitive hashing // The 40th International Conference on Research and Develop-ment in Information Retrieval (SIGIR). New York, 2017: 635–644
[16] Zhang P, Pan H, Li Z, et al. Accelerating LSH-based distributed search with in-network computation // IEEE Conference on Computer Communications (IN-FOCOM). Vancouver, 2021: 1–10
[17] Zhang P, Pan H, Li Z, et al. Netanns: a high-performance distributed search framework based on in-network computing //2021 IEEE Intl Conf on Parallel Distributed Processing with Applications (ISPA). New York, 2021: 271–278
[18] Zhang P, Pan H, Li Z, et al. Netsha: in-network acce-leration of LSH-based distributed search. IEEE Tran-sactions on Parallel and Distributed Systems, 2022, 33(9): 2213–2229
[19] Li H, Nutanong S, Xu H, et al. C2Net: a network-efficient approach to collision counting LSH similarity join. IEEE Transactions on Knowledge and Data En-gineering, 2018, 31(3): 423–436
[20] Kim Y, Callan J, Culpepper J. S, et al. Load-balancing in distributed selective search // The 39th International Conference on Research and Development in Informa-tion Retrieval (SIGIR). New York, 2016: 905–908
[21] Bosshart P, Daly D, Gibb G, et al. P4: programming protocol-independent packet processors. ACM SIG-COMM Computer Communication Review, 2014, 44 (3): 87–95
[22] Li Y, Liu I, Yuan Y, et al. Accelerating distributed reinforcement learning with in-switch computing // The 46th Annual International Symposium on Compu-ter Architecture (ISCA). Phoenix, 2019: 279–291
[23] Amsaleg L. Datasets for approximate nearest neighbor search [EB/OL]. (2010-01)[2024–07–01]. http://corpus- texmex.irisa.fr/
[24] Microsoft. A billion-scale vector dataset for text de-scriptors [EB/OL]. (2010–09)[2024–07–01]. https://gi thub.com/microsoft/SPTAG/tree/master/datasets/
Accelerating Distributed Search Systems Based on Programmable Data Plane Technology
Abstract To enhance the network performance of distributed application systems, we propose an acceleration framework NetDSH for distributed search based on a programmable data plane. NetDSH optimizes the storage and data processing capabilities of the programmable data plane by leveraging a custom protocol, a Top-K insertion method, and a T-update strategy to efficiently and accurately filter out low-quality candidate answers, thereby improving network transmission efficiency. We evaluate NetDSH on the testbed using four benchmark datasets inclouding SIF1M, SIF1B, SPACE1B, and Random. Experimental results demonstrate that compared with conventional distributed search systems, namely TLSH and NetSHa, NetDSH reduces the number of transmitted packets to 1/3 of the original volume while achieving a 3.2× improvement in system retrieval performance.
Key words programmable data plane; distributed system; approximate nearest neighbour search; local sensitive hashing