Press "Enter" to skip to content

微信搜一搜在线检索技术演进复盘

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

 

作者:kaelhua,腾讯 WXG 后台开发工程师

 

背景

 

2020 年下半年我们(搜一搜工程团队
)开发了一个新的内存检索引擎 ZeroSearch,并开始对搜一搜背后的大量垂直搜索系统进行升级,随着升级过程中遇到的各种问题和新的需求,以及半年多来我们自身认识的提高,在线检索引擎在各个方面都取得了长足的进步。在本文中,我会对我们团队
做过的一些主要事件进行经验的分享,全文较长,约 2 万 2 千字,内容涵盖评测体系介绍,倒排查找算法优化,线程模型优化,索引压缩原则,wand 检索实践,向量融合方案,以及性能优化方面的工作。

 

本文与前文(ZeroSearch 在线检索设计)的目的一致,并不是因为觉得自己做得比较好,而是因为网络上关于搜索领域的工程技术文章实在太少了,几乎都是从大的方案架构上进行介绍,然而从目前了解到的信息来看大家其实都大同小异,而稍微细化一点介绍具体实现的资料却几乎没有。本文意图略微填补一下关于检索引擎详细设计的资料空缺,搜一搜正在招聘后台开发和运营开发工程同学,如果阁下对搜索引擎或者搜索系统感兴趣,也欢迎联系我们。下面开始正文。

 

在线检索评测体系

 

工欲善其事必先利其器,为了能够在版本迭代以及特性开发过程中,确保每次变更的质量以及量化其收益,我们先建立了一套在线检索评测体系,该体系主要由以下几方面构成:

 

1 评测 Query 集

 

2 评测文档集

 

3 评测工具

 

4 评测指标

 

我们先从搜一搜的搜索日志里随机筛选出了一批 Query,并经过一定的加工筛选后,得到了我们的评测 Query 集,同时从长文本业务中,随机抽取了一批文档,作为我们的评测文档集。评测工具主要是通过设定 Query 集,并发数,评测时间,以及收集引擎返回的 kpi 信息(下文会介绍)进行统计,并输出相关报告。评测指标主要分为以下几个方面。

 

引擎 kpi

 

每次 Query 检索过程中其召回篇数信息,耗时信息,以及打分信息引擎都会进行记录,并随检索结果一起返回给上游,便于上游进行统计,上游通过统计 Query 集的信息后,得到我们最终的引擎 kpi,目前引擎 kpi 主要由以下指标构成:

 

全局指标

 

统计成功总数,失败总数,空结果率,QPS 等指标。

 

召回结果指标

 

统计各个环节的篇数信息,如平均召回篇数,平均求交篇数,平均 L1 打分篇数,平均 L2 打分篇数等指标。

 

耗时指标

 

统计各个环节的耗时信息,如平均总耗时,平均求交耗时,平均 L1 耗时,平均 Join&L1 耗时,平均 L2 耗时,平均打分耗时,平均 Join&Score 耗时等指标。

 

耗时分布指标

 

统计最终耗时和各个环节耗时的耗时水位信息,如 99 分位耗时,99.9 分位耗时等指标。

 

打分指标

 

统计文档的打分信息,如平均 L1 得分,平均 L2 得分等指标。

 

程序热点

 

通过 perf 及其配套工具生成程序火焰图,用于热点分析,另外火焰图也能方便我们了解程序全局的算力分配情况。

 

细粒度程序性能指标

 

perf stat 中的软硬件统计指标,如 CPU 利用率,内存利用率,IPC(insns per cycle),cache 命中率,分支预测失败率, context 上下文切换次数和 CPU 迁移次数等等细粒度指标。

 

得益于 BG 完备的运维体系,上面很多指标都有现成的运维监控系统可以统计到,包括程序的火焰图也可以一键抓取。评测体系建立完成后,我们每次有重要特性合入时,都会进行一轮评测,获取引擎的全面信息,除了上面说的质量保证和收益量化,该评价体系对我们的工作方向同样具有指导作用。

 

细粒度统计指标中,实际上真正对我们的工作产生指导性作用的,只有 IPC,cache 命中率,分支预测失败率。

 

关于倒排查找

 

在最初的设计里,我们的倒排查找实现非常简单,由于每个 term 的倒排链都位于连续内存中,并且当时的索引结构也未进行压缩,可以简单理解为每条倒排链就是一个 uint32 类型的有序数组,因此我们是直接通过二分查找来定位某个文档 id 的。

 

=注:经过半年多的迭代,目前索引结构已经发生了很大变化,不过并不影响本节内容。

 

这里其实是有个先入为主的问题,谈到倒排查找的时候,我们(包括笔者)往往都会联想到跳表,这可能是因为谈到搜索引擎的时候,大家接触过的或者想到的都是磁盘搜索引擎。基于这种刻板的认知,我们直接使用了二分搜索,因为在我们看来,跳表本质上实现的是一个在不连续内存上进行二分搜索的方式(这种认知也是有偏差的,实际上在磁盘检索上其更多是从磁盘 IO 的角度来考虑的,且其比二分更能利用局部性优势)。

 

稍作细想,我们可以想到,除了二分查找的方式,还有顺序遍历,Galloping Search 等方式。为了明确各种查找方式的一个性能对比,我们比较了以下四种倒排查找算法(基于 k-way 求交算法下,详细见 ZeroSearch 在线检索设计一文)的性能数据,结果出乎意料,这是部分数据的一个对比:

表格中的结论为:顺序遍历 > Galloping Search(区间内顺序遍历) > 大于 Galloping Search(区间内二分查找) > 二分查找。

 

注:检索过程中会有多个库并发进行求交,这里的求交耗时是把所有库求交完所花耗时的累加值。根据不同的测试数据集和测试 Query 集,各个查找算法的消耗会有不同的表现,以上和以下数据均是以我们的测试数据集为准进行测试的,该测试数据集来源为搜一搜中较大的一个长文本搜索业务,测试数据集的文档规模与真实的线上环境基本一致。

 

倒排查找统计

 

目前我们的倒排查找过程,分为以下两个阶段:

 

1 块间查找

 

2 块内查找

 

我们首先通过火焰图观察到块间查找的消耗仅占 0.05%,几乎可以忽略不计,因此对上面的结论造成影响的因素基本全部来自块内查找。为了进一步明确块内查找的消耗情况,我们对倒排查找函数内部的执行状况进行了统计,以下为 Block Size 固定为 1024 时,需要向后查找 PageId 时的统计数据。

 

为什幺我们之前 block size 采用了固定 1024 呢?主要是当时还未考虑索引压缩,block size 太小的话,内存占用会变多(事实上这个考虑是多余的),而最终选用 1024,其实是因为 1024 是一个比较程序员的数字,一开始打算先用它试试,后面没再花精力调整了。

 

1 Block Gap 统计

 

统计下一个目标 PageId 所在 Block 与当前 Block 的在倒排链上的距离:

表格中的结论为:1 100%的查找落在本 Block 和邻接 1 Block 内,说明 k-way 求交算法下由于求交连续性,目标文档几乎都在近邻 Block 内查找。2 解释了火焰图中块间查找函数占比极低的原由。

 

2 目标 PageId 位置 Gap 统计

 

统计下一个目标 PageId 与当前游标指向的 PageId 在倒排链上的距离。

 

饼状图中的数字 2,4,8,16 等等是指统计区间的上限,如 2 指的是距离位于[0,2),4 指的是[2,4),8 指的是[4,8)

饼状图中的结论为:1 求交的连续性带来了查找的局部性,离游标当前位置越接近的文档,其作为下一个目标文档 id 的可能性就越高。

 

2 解释了二分查找性能最差的原因,由于二分查找的查找次数固定,其只适合目标文档 id 均匀分布的情况,无法利用局部性优势。

 

3 倒排链长度分布统计

 

我们对索引库中倒排链长度的分布同样进行过统计,结论为绝大多数倒排链都是短链,长链占比极低(但是与之相反的是,长链的累加长度远高于短链,即倒排链的内存消耗反而主要是长链带来的),这是最基础的数据分布特征,我们认为这也是查找行为的局部性特征的重要原因之一,该统计数据对索引结构设计,索引压缩方案同样具备指导性价值。在 ZeroSearch 设计一文中,我们提到过索引数据会进行分片分库,即数据是被稀疏过多次的,一般最终到一个索引库内的文档数已经降低到百万级别了,这是造成倒排链长度的数据分布特征的一个原因。

 

不过这里还是得再强调一遍,本文中所有的统计数据都是基于我们选取的一个长文本业务(业务量较大)的数据统计得到,不同的数据源,是完全可能具有不同的数据结论的。

 

k-way 求交算法与倒排查找

 

通过上述的多个倒排查找算法的性能数据以及倒排查找中的 Gap 统计数据,可能会直接得出结论:顺序遍历在我们的评测体系中具有最佳的性能表现。但深入思考一下,我们会发现存在以下问题:

 

1 尽管 Gap 越大的位置,其占比越低,但是其要花费的查找代价也是成倍上涨的。

 

2 记第 i 条倒排链为 Pi,在倒排求交中一种常见的查询优化手段是让短链优先查找,即在初始阶段,我们会对查询语法树进行处理,最终会存在这样一个关系:

 

Len( P(n+1) ) >= Len( P(n) )

 

由于短链节点查找消耗更低,单次查找更快,因此短链节点优先查找,可快速更新求交基准,有利于提前结束求交行为。在 k-way 求交算法下,第 n+1 条倒排链,其进行第 x 次查找时,其要查找的位置,是前 n 条倒排链已经查找到的第 x 个交集元素, 即:

 

P(n+1)x = ( P(1)  ∩  P(2)  ∩  P(3)  .....  P(n) )x

 

即长链查找的次数一定是小于短链的(我们认为这也是局部性特征的重要原因之一)。如果数据分布均匀的话,那幺毫无疑问,对长链而言,大概率前后要查找的两个位置的 Gap 较大,这在一定程度上帮助我们分析了 Gap 统计数据中高 Gap 值的来源的问题。需要说明的是,这一点只是猜想,我们并没有去进行精确测量。

 

动态调整

 

通过上面的分析,可以推测没有最优的倒排查找算法,只有针对具体的场景最合适的倒排查找算法。因此在应对不同的语法树时,我们会对语法树中每一个 term 节点,通过该 term 节点在优化后的语法树中的位置,该 term 节点对应的倒排链长度,该 term 节点的起始文档和结束文档的覆盖范围,以及其它 term 节点的相关信息等特征,我们可以从全局的角度进行考虑,来为每个 term 节点选取最佳的查找算法,以逼近理论最优值。

 

在我们的评测体系下,与其它的单一的查找算法相比,动态选取方式生效的查找行为比统一的查找算法速度提升了25%
,但由于并不是所有的查询语法树都需要动态调整,因此其生效比例并不高,在评测集最终整体的平均查找耗时的优化效果上大打折扣。

 

在动态调整的应用过程中,我们曾一度预期 Galloping Search+循环查找的方式性能可能最好,因为我们做过 Gap 统计,k-way 求交算法下,查找是具有局部性特征的,那幺 Galloping Search 会比二分搜索更适合。但通过大量的测试,在我们的测试集下,测试数据又一次证明预期是错误的,结论为二分搜索是比 Galloping Search 更合适的大 Gap 下的查找算法。我们曾试图过去寻找一些原因,不过浅尝辄止,一种简单的数学上的印象是这样的:在大 Gap 下,如果我们新打开了一个 Block,那幺查找位置,落在该 Block 中的所有位置的概率是均匀 的(尽管局部性的存在导致并不是这样的),那幺通过计算查找消耗的数学期望可以知道,二分的数学期望是最小的。即在 BlockSize 为 1024 的倒排查找中,我们完全弃用了 Galloping Search。

 

多级倒排表设计

 

通过上面的数据分析已经知道,在一定的索引特征和 k-way 求交算法下,求交行为具有局部性特征。其实倒排链分块(一级索引)本身就已经充分利用了局部性了(保证了我们能够在近邻块内进行查找,而不是整条链查找),这里存在一个设计问题,即倒排表应该分多少级?例如一级索引,二级索引,三级索引等等。这个问题其实也显而易见了,由局部性特征及其统计数据可以知道,一级索引已经足够了,继续增加只会徒增 IO 和计算逻辑,这点我们认为不论是对磁盘搜索引擎还是内存搜索引擎都没有区别,不过这条结论是由我们的测试数据集和测试 Query 集得到,且只是单纯的文本检索,我们只能确保目前在搜一搜内该结论有效。

 

算力分配问题

 

正如之前在 ZeroSearch 设计一文中提到过的,我们认为内存搜索引擎要解决的核心问题是计算量的分配问题,即如何合理的分配计算量,能尽可能的让优质结果展现给用户。解决量与分配的关系关键在于对检索流程进行标准化,而标准化的意图在于量化算力
。为此我们抽象出了求交任务,L1 打分任务,L2 打分任务,资源清理任务等四个逻辑任务,并设计了任务的流水线模式。在 ZeroSearch 里,每一个逻辑任务就是对于计算量的一个抽象
,而量化的尺度为各任务的文档篇数与超时时间。

 

我们会发现量化似乎是资源类应用设计的通用准则,例如从硬件层面看,其对于算力的量化标准为 CPU 频率,功能单元容量,延迟,发射周期等性能指标,从机器运维的角度看,其量化标准为机器的 CPU 使用率,而我们要做的事情(CPU 密集型服务)其实就是将 CPU 使用率合理的转化为我们的量化标准,我们希望每一分 CPU(在篇数与超时时间不变的情况下)都可以对应到具体的 QPS。

 

在我们最初的设计里,每个任务一旦被调度到,就会运行到结束或者超时。考虑到不同任务的计算量消耗是不一样的,以及单库单线程求交设计中,求交任务消耗最严重,为了避免饿死其它线程,我们进行了拆分多个线程池,即整体如下图所示:

按照最初我们的预期,假设求交线程数为 x,打分线程数为 y,会存在一组参数(x,y),且 x + y = CPU 逻辑核数时,其性能最佳,引擎吞吐量最大。但是经过大量测试,出现了反预期的现象:

 

各线程池的线程数均较多时(超越核数),吞吐量反而更高。

 

为了找到线程数与吞吐量的关系,我们先固定了 x:y=1:1,通过调整引擎的线程总数**(线程总数=线程系数*CPU 逻辑核数量**),对多组参数进行测试和统计,得到了下图:

说明:在达到最大吞吐时,各组测试参数下的服务 CPU 均已达到 90%多,快接近 100%,图中的吞吐能力可以简单理解为最大 QPS。

 

散点图的纵轴表示吞吐能力,横轴表示线程系数,可以看到在剔除了线程系数为 1 的数据后,整体的波动就比较明确了,大体上呈抛物线,先缓慢上升,后缓慢下降,整体上还是稳定的。我们通过对比测试过程中得到的统计数据对此进行了分析。

 

上升阶段

 

线程系数由 1.5 递增到 3.5 时,整体上升,上升趋势逐步收敛。

 

分析:大多数请求召回篇数较低,甚至空召回,增加各线程池的线程数量,本质上是增加了各任务阶段并发度。低(空)召回请求可以更快得到处理,请求平均等待耗时下降,最终检索平均耗时下降

 

下降阶段

 

继续增大线程系数,当线程系数超过 3.5 后,吞吐开始下降,下降趋势逐步收敛。

 

分析:通过统计数据我们观测到 sys 部分 CPU 在上升,推测是内损消耗变大(如线程上下文切换,线程之间的竞争等),带来的收益小于增加的成本

 

同时我们对性能最优的这组线程数据(线程系数 3.5),以递增的压力进行压测,并统计不同压力下的吞吐,得到了以下数据:

当压测系数超过一定阈值时,其吞吐能力直接下降了一截,可以知道这种模式的稳定性较差,并且当我们继续增大并发压力时,其吞吐还在缓慢下降。

 

新的方案

 

多线程池任务粒度调度模式的设计存在以下两方面的问题

 

1 业务很难配置出一个得到最佳性能的参数
2 服务的稳定性较差,压力过大时可能导致雪崩

 

因此新的方案中我们舍弃了多线程池的设计,因为我们认为这是导致服务稳定性较差的重要原因。

 

另一方面,任务为粒度的调度单位太大了,长尾请求容易持续占用 CPU,最终导致算力分配不够均衡,因此我们重新实现了调度机制,不再以任务为粒度,而是以时间片为粒度,最终方案采用了单线程池设计 + 时间片粒度调度设计。程序被分配了多少个核,我们就创建多少个引擎工作线程,并分别绑定 CPU 核。

 

但需要强调的是,时间片粒度调度方案的设计初衷是为了保障在低线程数的情况下,依然保持较低的任务平均队列等待耗时,而不是最大吞吐量和服务稳定性。但是该项收益在我们的测试集中并不明显,因此在下文中我们依然是以最大吞吐和稳定性两个维度进行对比和分析。

 

关于任务平均队列等待耗时
假设我们有3个任务A,B,C, A 需要执行3个时间单位,B和C分别需要执行1个时间单位,现在我们有一个CPU核,在任务粒度调度里,假设我们按A,B,C的顺序进行执行,各个任务从入队到执行完毕所花的时间如下:
A任务 3 时间单位
B任务 4 时间单位(队列等待3时间单位)
C任务 5 时间单位(队列等待4时间单位)
任务平均耗时(3 + 4 + 5) / 3 = 4 时间单位
假设我们按C,B,A的顺序进行执行,则各个任务所花时间为:
C任务 1 时间单位
B任务 2 时间单位(队列等待1时间单位)
A任务 5 时间单位(队列等待2时间单位)
任务平均耗时(1 + 2 + 5) / 3 ~= 2.67 时间单位
即时间片调度的一个直观收益在于,其可以减少平均队列等待耗时。但这点如何验证呢?以下两种方式都可以验证得到
1 通过固定QPS请求服务,统计平均耗时相关的指标
2 通过固定并发数请求服务,统计服务的QPS指标
不过在我们的测试数据集中,我们对测试集本身卡了空结果率,保证测试集的空结果率在1.5%以下,实际上线上业务的空结果率远高于此值,而在空结果率高的情况下,时间片轮转调度的收益才会更高

 

同样的,在我们实现完该方案后,我们对多组参数进行了测试和统计,得到了以下数据。

通过多组测试,在最大吞吐量方面,时间片调度方案与任务粒度调度方案几乎相等。在引入时间片调度后,会增加以下成本:

 

1 增加了各任务的入队出队次数
2 由于业务相关性的一些需要,相关性库在每个任务的开始函数和结束函数的调用会变为多次(任务粒度的调度则只有一次)

 

如果将上述第 2 点也改为一次的话,在测试数据集中,最大吞吐量的收益稳定在 1-2%,不显着。

 

由于时间片调度会增加一些成本,因此我们最初预期是最大吞吐会有所下降,但测试结果是基本持平,甚至略有提高。

 

理论上,除非我们减少了长尾请求的算力占用,否则时间片调度方案不应该有最大吞吐量的收益。这是因为一个请求在没有超时的情况下,其消耗的算力是固定的。而单位时间下,机器拥有的算力也是固定的,两者相除即得到服务的最大吞吐量。我们通过统计数据观察到,不论是在时间片调度还是任务粒度调度方案里,有任意环节超时的请求数均为0,即每个请求的算力消耗是一致的。时间片调度方案相比任务调度方案的最大吞吐收益来源其实分为两部分,一部分来自sys部分(该部分占用恒定且非常低),另一部分是时间片调度是唯一一个可以完全榨干算力,CPU占用一直保持100%的方案。

 

虽然在最大吞吐量上的收益不明显,但是服务的稳定性大大增强,当吞吐达到最大值后,即便我们继续增加压测压力,服务也只是各阶段的平均耗时在上升,但是吞吐保持了稳定。

 

同时,单线程池的设计也可以简化引擎的参数配置,业务不再需要理解和配置各个线程池的线程数量,降低了使用门槛。

 

  当以时间片粒度调度时,如果时间片足够大,将退化为任务粒度调度,我们同样测试过这种情况,在我们的测试数据集中,其稳定性,以及最大吞吐量都比小粒度时间片要差。即小粒度时间片方案在输入差异的情况下,还可以保证在一个周期内具备比较恒定的输出。
  另一方面,我们还未对任务调度进行过多优化,目前整体为一个简单的优先级队列。改为时间片粒度调度后,由于任务重复入队,如果服务的并发压力过高的话,那幺服务同样会面临雪崩的问题,这也是后续我们计划优化的一个方向。不过某种程度上这其实是一个伪命题,由于组件化的设计,我们的在线检索服务 = 在线检索组件 + 任意支持线程模式的RPC框架,即检索服务中存在两个线程池,一个是RPC框架的工作线程池,一个是在线检索组件的工作线程池,即最大并发压力=RPC框架的工作线程数量。因此RPC框架的工作线程数量帮我们限制住了服务的最大并发压力,在达到最大并发压力之前,CPU早早就达到100%,触发扩容机制了。另一方面通过优化任务调度的策略,我们也可以进一步减少平均任务队列等待耗时。

 

对于算力分配问题,其实我们的完整解决思路是从分配高效和分配均衡两点下手,对应的解决方案分别为任务流水线设计以及单线程池时间片调度,由于任务流水线设计已经在 ZeroSearch 设计一文中提过了,因此本文就不再重复了。

 

关于索引压缩

 

索引压缩部分主要由我们团队的 agan 负责,后续将有独立的分享,本文中只谈一下我们对于索引压缩的粗浅认识。

 

空间与性能的权衡

 

当谈到索引压缩时,按照思维的惯性,我们可能会想到倒排链的各种压缩算法。依瓢画葫芦的确是一件比较轻松的事情,但如果深入思考的话,我们会发现倒排链的压缩对内存搜索引擎来说,其收益是比较局限的。

 

压缩的本质是时间换空间,但是在内存搜索引擎里,CPU 与内存都是紧缺资源,导致倒排链的压缩变成了性能与空间的一项权衡,即我们会倾向于访问频率越高的数据,其压缩的必要性越低,或者是解压效率越重要(当然不压缩的时候解压效率是最高的),很遗憾倒排链恰恰是访问频率最高的。不过在磁盘搜索引擎里这点是毋庸置疑的,由于磁盘 IO 的存在,其不止换到了空间,还省了时间,一本万利。(注:这里的磁盘 IO 特指 hdd,非 ssd)。

 

事实上,在我们开启索引压缩工作前,我们先选取了一个文档量较大的核心业务的索引库,对引擎内的各部分索引结构的空间占用进行了精确测量和统计,我们希望能够对我们要做的事情先有一个全局的认识和掌控,并尽可能提前量化好工作收益,再以此为指导进行工作的展开。

 

在得出具体的统计数据之后,我们做的第一件事不是索引的压缩,而是索引结构的重新设计,在我们的收益预估中,索引结构的重新设计,其性价比(空间优化幅度 / 性能降低幅度)比倒排压缩更高。

 

另一方面,我们通过对已有业务进行统计,真正占用了内存消耗大头的,反而是文档的正排数据(含文档的 Pos 数据)。因此对于倒排链的压缩,我们只采用了一些非常轻量的压缩方式,一方面倒排数据是检索过程中访问最频繁的索引数据,另一方面倒排数据在索引数据中的占比并不高,没有必要为了倒排的内存空间收益而放弃 CPU 和性能。

 

关于 weakand 的落地应用

 

长期以来,在文本检索这块,搜一搜使用的都是严格的布尔检索形式。例如用户输入 Query:[广州机场附近有啥玩的地方],我们通过分词环节,可能会得到[广州,机场,附近,有,啥,玩,的,地方]这样一个 term 列表,一种理所当然的做法是将各个 term 对应的倒排链取出来,求其交集,得到我们的召回结果,即语法表达形式如下:

 

(广州 and 机场 and 附近 and 有 and 啥 and 玩 and 的 and 地方)

 

在 Query 处理过程中,分词之后,还有很关键的一步,就是对这个 term 列表中的 term 设置必留(必须命中)或者丢弃(可选命中)属性。例如我们可能会对[有,啥]两个 term 设置丢弃词属性,就算文档没命中这两个 term 也可以进行召回,即语法表达形式如下:

 

(广州 and 机场 and 附近 maybe 有 maybe 啥 and 玩 and 的 and 地方)

 

当然,在这个例子中我描述的很简单,但实际上在长 Query 下,必留或者丢弃属性的设置要做到比较精确是非常困难的,这里一部分原因是语言自身的复杂度,另一部分原因是搜一搜背后存在大量的垂直搜索引擎,各个垂类搜索引擎的必留/丢弃属性的设置标准是不一样的,Query 处理环节中,不可能满足所有需求。

 

正如 ZeroSearch 设计一文中提到的,我们对 weakand 的认识在于这种求交方式可以缓解对于 Query 处理能力的依赖,这恰好是搜一搜所需要的。通过相关论文对 wand 有一定了解后,我们最终在引擎内采用了 block-max-weakand 的实现方式,并对其性能,召回效果方面有了一定的应用经验。

 

block-max-weakand 实现的主要参考论文:[Efficient_query_evaluation_using_a_two-level_retrieval_process
][7]

 

wand召回方式是以召回相关性得分TopK的文档作为召回目标,假设我们存在一个Query:ABCD,其分词结果为A,B,C,D,
在布尔检索中,其召回集的size为:
A ∩ B ∩ C ∩ D
在动态非必留中,其召回集的size为下面的区间:
[ A ∩ B ∩ C ∩ D,    (A ∪ B ∪ C ∪ D ) / N ] , N 为要求的最低命中term数
在weakand中,其召回集的size为:
A ∪ B ∪ C ∪ D
很明显,weakand的召回集的size是最大的,为所有相关的倒排链的并集,我们记为S。weakand的召回方式为从S中选取出相关性评分TopK的文档出来,然后进行召回,这种召回方式与布尔检索或者动态非必留是完全不同的。在布尔检索和动态非必留中,本质上召回的文档是满足命中关系的L0得分TopK的文档。

 

量化单位

 

(我们认为)搜索引擎的设计标准之一:让算力变得透明,可量化。因此引入 wand 第一个要考虑的问题是如何去量化 wand 召回行为,篇数与超时依然是我们的量化尺度
。在超时上,wand 属于召回环节里的不同召回方式,因此超时机制可以直接复用。在篇数上,wand 的召回方式为选取相关性评估得分 TopK 的文档进行召回,不过这是在满求交下才能得到的理想结果,为了与原有篇数配置兼容,我们新增了一个求交膨胀系数。即在 wand 召回中,其求交篇数为原有的求交篇数配置*求交膨胀系数,然后再从这些文档中,选出相关性 TopK 的文档进行召回。

 

在召回篇数未达到 K 时,文档将按 did 从小到大顺序依次入堆,当堆满之后才开始裁剪逻辑,因此减小求交篇数配置值可以更快速的开始裁剪。而增加求交膨胀系数后引擎将求交出更多的文档,即在更多的文档中选出 bm25 得分 TopK 的文档,从而得到一个更优质的召回结果集,但其代价为消耗更多的算力。

 

在固定求交篇数的条件下,假设引擎固定求交 10W 篇,即:

 

求交篇数配置 * ( 1 + 求交膨胀系数 ) = 10W

 

我们对多组参数进行过测试,求交膨胀系数越大,求交篇数越小,召回过程就越快,原因在于其能更快速的进入到裁剪过程,且裁剪过程将得到加速。

 

另一方面,理论上求交膨胀系数越大,求交篇数配置越小,最终召回结果将会越优质,原因在于其裁剪规模将越大(未满求交的前提下)。使用者可以根据自身需求,综合考虑召回篇数,召回效果以及性能损耗。

 

内存 or 算力

 

在我们的 wand 实现里,采用了各个字段的 bm25 得分加权求和来作为文档的相关性评分。bm25 得分的计算项主要是两部分,一部分是计算 Term 权重,另一部分是计算 Term 与文档的相关性评分。

 

其中 Term 权重是固定的,一个索引库内的每个 term 只需要计算一次,其空间占用较小,因此我们放在了离线索引阶段来计算。还有一部分原因是搜一搜中大多数业务的倒排链目前不是按 field 粒度来建的,而是按文档粒度建的,在线计算的话无法分 field 来计算。

 

但是 Term 与文档的相关性评分,属于 Term-Doc 维度的得分,如果在检索阶段,对每篇求交出来的文档都计算一遍,这部分的 CPU 消耗不可忽略。因此其实现方式有两种,分别为在线计算或者离线计算 Term 与文档的相关性评分。采用离线计算时,依据业务的不同,内存大概增长 20-30%,适用于业务体量较小的业务,例如帐号搜索系统。而采用在线计算时,CPU 大概增长 10%,适用于业务体量较大的业务,例如长文本搜索系统。

 

初始阈值

 

在 wand 召回里,当召回篇数小于 K 篇时,文档将直接入堆,原因在于我们需要先求交出 K 篇文档,才能选举出裁剪阈值,然后执行裁剪逻辑,并在随后的过程中不断更新阈值,而阈值越高时,裁剪规模也会越大,整个求交过程会处于不断加速的过程中,类似于滚雪球,越滚越快。

 

根据统计得到,直接入堆的文档得分一般都较低,在后续的求交过程中也会被丢掉,从而浪费了算力。因此我们提供了让业务设置初始阈值的能力,提前开启裁剪逻辑,确保初始入堆的文档质量。另外一方面,业务也可以通过给与一个较高的初始阈值,从而加速整个求交过程,在固定求交篇数下,较高的初始阈值可以保证遍历到更多的文档(即满求交率更高),进而提升最终的召回文档的质量。但是阈值给的过高时,可能导致欠召回问题产生。

 

出于性能的考虑,我们也会根据文档频率,以及查询 term 列表的特征信息,提供一个默认的保守计算初始阈值的选项。

 

计算规模裁剪

 

在布尔检索中,检索串越长其召回集越低(召回集为 term list 的交集),但是在 wand 求交方式里,检索串越长,其召回集就越大(召回集为 term list 的并集),参与到 wand 计算的 term 就越多,其性能损耗也将越大。

 

但是 wand 召回方式本身就天然适用于解决长串的召回问题,为了加速 wand 召回方式里长串的检索速度。我们支持布尔检索与 wand 召回结合的检索方式,即可以从长串中抽离出核心词或丢弃词,对于核心词采用严格 and-or 语义求交,对于丢弃词则直接不参与求交。最后剩下的 term 才参与到 weakand 的计算中来,最终达到减少 wand 计算规模的效果。

 

初始阈值是一种通过加速裁剪过程来完成加速召回的方式。而抽离核心词做布尔检索则是通过减小计算规模(召回集大小,wand 计算的 term 数量)来完成加速召回的方式。

 

适用场景与效果

 

wand 召回方式可缓解搜索系统对于 NLP 能力的依赖,因此其天然适用于长串的检索召回。在搜索系统中,长串的检索召回相比短串要困难很多,一方面是 Query 处理过程中很难精确设置必留/丢弃词,即容易出现召回偏移和欠召回问题。另一方面,相关性计算方面也容易出现结果漂移。我们这边有独立的相关性计算流程,因此对于 wand 主要用于解决召回偏移和欠召回的问题。我们对长文本业务做过一个召回覆盖率的评测,评测结论为:增加一路 wand 召回队列,大约可以提升 12%绝对值的召回覆盖率。

 

关于向量融合

 

向量检索及其优化主要由我们团队的 willen 和 jingwen 负责,后续将有独立的分享。本文中主要介绍我们处理向量检索结果和文本检索结果的多队列结果融合方案的实现。

 

问题背景

 

引擎进行文本召回时,本质上是对多个有序列表求其交集,同时整个过程是流式的,因此随着求交不断进行,弹出来的 did 是有序的,整体是 did 从小到大进行召回。由于 L0 得分越高,did 越小,因此文本召回的结果集一方面是 did 有序,另一方面它是质量分从高到低的一个结果列表。

 

注意:此处的 did 特指引擎内部给文档赋予的 id,与业务层面的文档 id 不一样。引擎内部对文档进行 id 赋值时,标准为 L0 得分(离线计算得到的文档质量分)越高,则其 id 越小,保证在倒排链的前面,能被优先求交出来。

 

引擎进行向量召回时,将搜索与检索条件中的向量距离最接近的文档,即向量得分越高的文档进行返回,其整个过程其实也是流式的。向量召回的结果集,为向量距离从小到大的结果列表,或者说是向量得分从高到低的结果列表。但 did 是无序的。

 

在相关性特征输入信息方面,文本队列的只有文本命中信息,而向量队列的只有向量得分信息。由于我们希望将结果的融合放在引擎内部实现,因此不论文档是从文本队列召回还是向量队列召回,我们在给到相关性库打分时,其相关性特征输入信息应该保持一致,否则相关性库无法以一个统一的标准来对文档进行相关性评分。

 

当文本召回和向量召回同时进行时会面临一个问题,即在什幺时候进行结果融合?一种方案是召回过程中进行融合,但是文本召回需要保证 did 有序,否则倒排求交就没法进行下去了,而向量召回结果为 did 无序,因此我们需要将其转化为有序。

 

另一种方案是召回阶段结束后融合,首先两个队列出来的结果集几乎可以肯定是不一致的,两者的结果集没法完美合并掉,那幺我们还需要将其特征进行对齐。

 

引擎底层融合,比让业务自己在上层融合具备更多优势,其一是更低的开发成本,其二是融合排序会更加容易且自然。如果文本检索和向量检索是独立系统的话,那幺引擎底层融合与之相比,还可以减少维护成本,同时规避掉多套检索系统带来的数据冗余和一致性的问题。

 

召回队列与召回比例

 

遵循算力可量化的标准,我们先对引擎的检索输入信息做了多队列召回支持的改造,支持使用者设置多条队列的检索条件,并给每条队列设置一个召回比例。各个队列的召回篇数=求交篇数配置项 * 队列召回比例的百分比。

 

融合召回方案

 

在 ZeroSearch 中,一次检索行为,会经历三个阶段:

 

求交阶段 ---> L1打分阶段 ---> L2打分阶段

 

对于融合召回,我们最初采取的解决方案是在求交阶段通过控制各条召回队列的召回比例来进行混合召回完成的。那幺我们需要解决的是向量队列 did 无序返回的问题,我们的思路也很简单,直接让向量队列先完成召回,然后再 sort 一遍后与文本队列融合。整体设计如下图所示:

整体流程为:

 

1 求交任务先进行向量召回
2 对向量召回结果进行sort,按did从小到大排列
3 求交任务进行文本召回,并与向量召回结果融合
4 求交结束,进入打分阶段

 

该方案的优势为:

 

1 结果融合时可保证文本队列的召回结果与向量队列的召回结果不重复
由于求交任务中的向量召回队列先进行,引擎给与了向量召回结果更高的召回优先级,因此可保证文本召回与向量召回结果不重复,但是向量召回队列之间还是可能存在结果重复
2 向量召回结果可获取到文本命中特征
倒排链的组织形式为按did从小到大排列,因此文本召回过程中,可通过将查询串的各条倒排链的游标移动到向量召回结果的did位置处,来获取向量召回结果的文本命中信息

 

该方案同时具备以下缺陷:

 

1 文本召回和向量召回实际上是在同一个求交任务下串行进行,导致最终耗时和召回耗时下限都比较高
2 文本召回的结果获取不到向量特征(向量得分),这是因为实际业务场景中,文本队列的召回比例往往非常高,一方面我们需要寻址和读取该文档的向量信息,另一方面高维向量的一次欧拉距离或者内积计算的消耗同样不可忽略,由于可能存在多条向量队列同时召回,如果对每个文本队列的结果单独计算多次向量分,但进入L2打分阶段却只有L1得分TopK的结果,这里会存在较多的算力浪费的现象。

 

独立召回方案

 

为了解决融合召回方案中的缺陷,我们重新思考了结果融合这个问题,总体思路为忽略非必要的缺陷,解决核心需求点。通过结合实际场景分析,向量召回的结果一般用于补充文本召回的结果,且其召回量相对较低,向量召回结果与文本召回结果存在适量重复是可以接受的。而召回耗时增加,以及多条队列的召回结果,其文本/向量特征不完全统一的情况对于打分阶段是难以接受的,基于此我们提出了新的多队列独立召回方案,新方案的整体设计如下图所示:

其整体流程为:

 

1 文本召回由独立的求交任务和L1打分任务进行
2 向量召回由独立的求交任务和L1打分任务进行
3 两条召回队列的结果在L1打分结束后进行融合,统一文档特征
4 将特征统一后的最终L1打分结果送入L2打分结果

 

其核心设计点为:

 

1 特征统一放在了L2打分阶段之前
进入L2之前如果在L1打分阶段进行特征统一,对一篇文档的特征进行统一的消耗较大,而求交阶段的召回结果较多,性能消耗较大,因此该方案被舍弃
2 向量队列结果可直接进入L2打分
向量队列召回的结果本身就是向量得分TopK的结果,没有必要再进行L1打分筛选一遍TopK,从而规避掉了与文本队列结果一起进入L1筛选TopK的问题

 

该方案其实依赖于双打分流程(L1Score —> L2Score)的设计。但在 ZeroSearch 设计之初,其实我们也没有意识到双打分流程在多队列召回中也能起到关键性作用。

 

这里想说点题外话,虽然我们让引擎支持了 wand 召回方式,也支持了引擎同时进行文本和向量检索,且寻找到了一条至少看似合理的路径实现了结果的融合。但是于个人来说,做这些事情的过程和结果并不是最重要的,重要的是做完这些事情后,它们本身给我们带来了新的思考,即:作为一名成熟的搜索工程同学,其职业成长的方向会在哪里?一种显而易见的想法当然是引擎平台化,技术产品化,那幺围绕这两点进行工作方向的展开即可。

 

尽管要做到这两点已经非常困难,事实上能做到的公司凤毛麟角,但这只是我们的次要目标,因为我们还有更重要的业务目标。长久以来我们对信息检索的认识就是分词,索引,倒排求交,打分,排序这样一套模板,即便平台化后,也不过是模板通用化了,可以批量生产了,但实际上我们并没有在这个领域取得进步,搜索最终依然是 NLP 能力的体现,这有点类似于三体中基础科学被智子锁死后地球科技的发展。而 wand 和向量检索与融合则不同,它们重构了信息检索过程,并分别在一定程度上减轻了对 NLP 能力的依赖,最终却能在一些 case 下达到一个更好的检索效果,这也会是我们后续的一个思考方向。

 

关于性能优化

 

性能优化是一个非必须,但是又避不开的话题,一方面引擎性能不能太拉垮,但是比性能更值得去建设的事情又太多了,其重要性也就大打折扣了,另一方面,性能优化是一个长期持续的事情,从我们开始这部分工作以来,引擎的召回性能相比最初的版本已经提升了近 50%(最大吞吐能力)
。由于搜索引擎是一个比较特殊的 CPU 密集型的服务,其性能优化的思路与一般的业务场景会有所差异,毕竟对大多数业务场景而言,再多的优化方法可能都没有一次缓存命中的效果好,下面简要介绍我们在搜索引擎上应用过的优化方法。

 

搜索引擎进行召回时,需要召回多篇文档,因此本身就处在一个大的循环的场景中,存在部分代码段调用时机极为频繁,即自身存在优化基础,另一方面,在短平快开发模式下,无法写出具备较优性能的代码,也因此引擎在代码性能方面存在优化空间。

 

首先是优化位置的定位,引擎本身的代码大概分为以下几个场景:

 

1 程序生命周期级别
2 请求级别
3 请求-文档级别
4 请求-文档-字段级别
5 请求-文档-语法节点级别

 

原则上我们只关注高频调用的逻辑,即大循环体内,文档级别以下的场景,另外火焰图也可以帮助我们定位到热点函数。

 

榨取算力

 

simd 应用的优化效果一般,建议参考。

 

simd 应用

 

simd 是通过扩宽单条指令处理的数据流来实现算力的榨取。目前公司的生产环境基本都支持 sse 和 avx256 指令集,倒排查找过程中,Galloping Search 及其变体实现
(与 simd 结合后,我们的做法是通过一次 simd 比较就确定查找区间),以及顺序遍历
的查找方式与 simd 的使用刚好是匹配的。通过对倒排查找函数进行 simd 改造,使得整体的查找效率得到了一定幅度的提升。关于 simd 在倒排查找算法上的应用,网上已经有非常多的资料,这里就不再展开讲解了,附上在我们的引擎中以及对应的评测数据下,不同倒排查找算法,经 simd 改造后的耗时对比数据,该数据为 block size 为 1024,且索引未压缩的数据,仅供参考:

遍历:指顺序遍历查找方式

 

SSE:指顺序遍历查找方式,使用128bit寄存器及相关的指令集实现版本

 

AVX:指顺序遍历查找方式,使用256bit寄存器及相关的指令集实现版本

 

GP: 标准的Galloping Search查找方式(非simd实现方式)

 

GP + xx:先通过GP确定查找区间,区间内使用xx查找方式

 

可以看到遍历是 simd 应用前最佳的查找方式。另外 AVX 相比二分,倒排查找耗时降低了约 26%,由于对于召回模块而言,倒排查找的消耗只占其中一部分,因此对最终的性能提升的贡献一般。

 

不过值得一提的是,由于索引压缩的需求,我们后续的索引结构里,block size 调整到了 128 附近浮动,这里出现过一个反预期的现象:

 

在索引不压缩的情况下,SSE,AVX 等指令集反而是负优化,速度最快的是顺序遍历。

 

通过分析,我们认为整个倒排查找过程的性能消耗主要由以下两方面决定:

 

1 CPU计算
2 Memory Load(L1Cache与寄存器)

 

我们推测,由于在局部性特征的存在,在我们的评测数据下:

 

1 block size在1024时,引入了太多无效的CPU计算,因此simd指令集应用可以加速整个过程。
2 block size在128附近浮动时,simd指令集引入了太多无效的Memory Load操作,从而导致在不压缩情况下,反而成为了负优化。

 

指令并发

 

与 simd 不同,另一种算力榨取的方式为增加单个时间周期里 CPU 处理的指令条数,对应到我们评测体系中的 IPC 指标。深入理解计算机系统一书中对指令并发进行过介绍,其最常见的手段就是循环展开,以及解除指令流中的数据依赖。我们曾经试图过对此进行应用,场景集中在索引数据的解析中,但最终基本没什幺效果,或者说处在误差范围之内。这里很大部分原因在于我们当时的索引结构还未进行过压缩,没有找到较合适的应用场景,在解压操作中该优化方式的优化空间应该会比较大,不过对于新版的索引结构我们还没有投入时间去针对性优化(目前索引层接口设计归属在离线工作中),因此这方面的最新数据暂时还欠缺。

 

引擎一直采用的 02 的优化等级,我们也用过 O3 的优化等级去编译,例如循环展开,函数内联优化等手段,在 O3 等级中编译器就会开启,但是经测试,02 和 03 优化的二进制在性能上没有差异。原因可能是多方面的,例如引擎内部逻辑比较复杂,在代码编写过程中已经很注重使用 inline 了,编译器的循环展开,内联优化等手段可能影响很小,也可能是代码段的膨胀抵销了收益。

 

另外 inline 虽然是建议内联,但是经实践,O2 优化之下,编译器会将相关函数都内联掉。另外类的成员函数如果是 private 方法的话,即便声明和实现分别在.h 和.cc 文件中,也可以通过 inline 实现内联。这里强调 private 的原因是,非 private 方法一般会在别的 object 文件中被引用,如果声明和实现分离,内联后会导致找不到符号。

 

内存优化

 

内存优化的优化效果显着,强烈建议参考。

 

内存引用优化

 

引擎检索时会涉及到大量的索引数据操作,内部使用了较多的指针,所谓内存引用优化,指的是减少间接寻址的次数。其最简单的应用为将需要多次访问的地址(可能在不同函数中访问),使用临时变量将该地址下的值给保存起来,从而避免多次解指针。这一点经实践确实有效,不过借鉴经验不大,因为引擎这里还存在一些隐藏属性,首先索引数据不是内存对齐的,另一点是索引数据比较大,例如我们的评测体系中机器的内存空间占用几乎达到了 80%,在 NUMA 架构下,内存分为本地内存和非本地内存,如果索引数据处于非本地内存,其访问速度要慢很多。

 

我们甚至做过一些测试,将一些索引数据的读取直接改成了 memcpy,结果发现两者性能差距可忽略不计,内存访问对于性能的影响可见一斑。

 

内存分配优化

 

检索过程中会涉及到大量的复杂数据结构的使用,最突出的一点就是文档的相关性信息中命中信息的存储。文档相关性命中信息是一个非常复杂的结构,多层 struct 嵌套,且里面包含大量指针,涉及到堆内存的申请和释放。所谓的分配优化,并不是单纯指减少内存分配函数的调用次数(特别是程序在链接上 jemalloc 后,内存分配的开销已经被弱化过一次),而是指我们试图让一次检索行为涉及到的核心数据结构的内存都处于连续的内存空间。

 

注:由于 ZeroSearch 本身是多线程环境,且内部存在频繁的小内存申请和释放,因此我们目前先选用了 jemalloc 来负责内存管理

 

内存分配优化给引擎整体的性能带来了肉眼可见的提升。一种显而易见的优势是连续内存分配可以充分利用局部性原理,例如提高程序的 cache 命中率,但经测试这一点的收益占比非常小,其真正的收益在于加速了引擎的资源清理,内存块的释放是一种更彻底的析构调用

 

不过我们目前在连续内存分配上还没有做的非常彻底,当前索引层的接口设计里面还大量使用了智能指针来进行内存管理。即便合理运用智能指针和右值引用,当其使用量较大时,其性能损耗依然较高(主要消耗在析构),下一步我们计划将在线的内存管理机制渗透进去,预期这里还将带来可观的收益。

 

由于用户层使用的是虚拟内存空间,用户层的连续内存分配是无法保证物理上连续的,因此我们并未采取预申请大内存的方案,而是采用链表来管理。整个内存管理方案也非常简单,整体如下图所示:

默认情况下,单个 Memory Block 的大小为一个(一倍)页面大小,根据使用场景可自行调整倍数。如果单次申请超出了页面大小的话,则使用传入的参数值。释放的时候,遍历 Block 链表,逐块释放即可。但同样的,内存分配时依然需要注意保持内存对齐的原则,我们的做法也很简单,保证每次分配的内存块均为 8 字节的倍数即可。

 

分支优化

 

分支优化的优化效果不明显,略高于误差范围,不建议参考。

 

条件传送

 

现代 CPU 多级流水线的实现,一旦分支预测失败,将导致流水线冲刷,从而带来性能上的损耗,将一些简单的条件控制语句转为条件传送语句,可有效减少程序分支,从而规避掉该问题。与条件控制语句不同,条件传送语句将会同时计算两个分支的结果,最后根据控制条件的结果来选择计算结果,其最常应用的场景就是赋值运算的代码块。例如引擎中存在一些循环代码块,形式如下图所示的代码:

 

val_1 = x, val_2 = y;
for (auto it : list)
{
    loop_val = it->doSomeThing(args);
if (expr(loop_val))
    {
        val_1 = expr(loop_val);
        val_2 = expr(val_1);
    }
}

 

其优化实现为:

 

val_1 = x, val_2 = y;
flag = false;
for (auto it : list)
{
    loop_val = it->doSomeThing(args);
    flag = expr(loop_val);
    val_1 = flag ? expr(loop_val) : val_1;
    val_2 = flag ? expr(val_1) : val_2;
}

 

通过对这两种形式的代码块的汇编代码进行比较,我们可以发现其中蹊跷,经 O2 优化之后,三元操作符下,使用的是 cmov 类型的指令,根据 cmp 的计算结果选择传值,不会破坏流水线,而 if 分支下使用的是 je 类型的指令,即需要跳转,一旦预测失败将导致流水线冲刷。

 

分支预测

 

使用 likely,unlikely 等标记也是 coding 级别优化中的常见手段,其作用为将开发者认为更可能被预测为成功的分支的代码块移动到前面来,从而提升指令的 cache 命中率,给程序带来更高的性能。这点在程序的 cache-misses 和 L1-icache-load-misses 指标上会有明显的体现。但是最终带来的性能收益并不高。

 

谈到分支预测优化,可能很多人还会想到如何提高分支预测率,但是在不改变程序逻辑的前提下,分支预测率是无法提高的,其基本是由 CPU 自身的分支预测器决定,不过现代 CPU 的分支预测器已经做的足够好了,正常情况下其正确率都能达到 99%以上。

 

引擎的代码在经过多轮优化之后,在分支预测率方面的确也有提升,与最初的版本相比,下降了约 50%
(降幅,非绝对值),它的提升在于两点,一是整体减少了分支语句,二是编写了更符合场景规律的代码。

 

索引设计

 

背景:索引设计被划入在离线的工作中,原先对索引设计的认知是很粗浅的,停留在依葫芦画瓢阶段,我们先规划出了,索引数据分为哪些类型,然后针对每种类型的索引数据进行了结构的设计,并独立存储。

 

事实证明,当时的想法是稚嫩的,表面上看,索引设计似乎并不需要遵循什幺准则。但是从在线的性能角度去看,把一次操作需要读取的数据放在一片连续内存,一次性读出,会比分成多片索引区域,分开读取性能要好(这一点在磁盘检索引擎中应该是共识,因为能减少磁盘 IO 次数。但是内存的随机存取特性让我们最初设计内存检索引擎时忽略了这点)。

 

其收益来自于两方面,一方面是连续内存读取将带来局部性优势,另一方面是,在每片索引区域读取一篇文档的数据的时候,我们都需要一次索引读取操作以及对应的索引解析操作(虽然大多数时候都是可以直接根据 did 直接内存寻址的),而分成多片索引区域时需要执行多次这样的操作。

 

索引设计的另一准则为尽量保证定长数据的内存对齐,包括适当的内存 padding 的使用,正如内存优化小节提到的,非内存对齐数据的访问其开销比我们想像中要大很多。而根据我们的经验,对于内存搜索引擎来说,其消耗就是由 CPU 消耗和 Memory Load 消耗构成的。

 

提高缓存命中率其实在绝大部分时候都是一句正确的废话,其应用场景非常少,即便程序内存 IO 非常庞大时(内存检索引擎恰恰就是内存 IO 频繁且庞大的场景),这一点的收益经实践也非常小。就像上面内存优化里提的一样,连续内存最大的优势在于能够快速清理。

 

关于磁盘检索

 

尽管我们当前做的是内存检索引擎,但磁盘检索引擎的实现其实并不困难。随着硬件的升级,磁盘检索引擎的实现难度已经大大降低,例如使用 nvme 通信接口的 ssd 盘,其吞吐速率已经能接近内存的 1/10,每秒吞吐量能达到 GB 级别。由于在线召回架构已经对检索请求进行了任务粒度的拆分和调度,我们只需要给任务增加一个 IO 状态便可以完美嵌入到当前的召回架构中。当然,索引结构也需要进行一些细微调整,以进一步减少磁盘 IO 次数。

 

最后

 

通过半年多来的追赶,ZeroSearch 完成了从田间燕雀到雏鹰的转变,以前想过在公司内部开源,现在反而越觉得欠缺的还太多,半成品的东西没法开源。以前在乐问里看到一句话十分认同:我们总是高估技术的短期效应,而低估它们的长期影响力。我们做的事情其实不如多加一些词表,多写一些 if-else 策略的收益来得快,它的价值会由时间来证明,万丈高楼的搭建需要坚实的地基,在我看来我们做的就是这样一件事情。

 

对于引擎设计,其实还有一些想写的内容,例如 everything online 的设计理念,支持通过请求参数来控制引擎的全部检索行为,不论是篇数,耗时,还是召回方式的选取上,这样可以让业务在召回策略上面进行灵活组织,例如组件化设计,将检索内核与业务特性模块隔离,管理好引擎的复杂度,例如召回架构的双层语法树设计,支持任意索引类型数据的求交求并,例如引擎内部的问题诊断能力的建设,例如多文本同时检索等等,限于本文篇幅已经比较长了。

 

但话说回来,我们做的很多事情其实跟我们当前的索引规模也有很大的关系,由于相比网页搜索的索引规模少了一个数量级,因此很多事情我们都还不需要考虑,或者侧重点不一样,例如数据量到达一定程度后,索引压缩比,篇数截断限制下的倒排求交设计,结果多样性保障等等都需要提上议程。

 

本文的内容稍显杂乱,其实近一年来的时间,所有的工作的展开,我们基于对搜索领域挑战的认知,背后是有思考在里面的,整体分为 3 个阶段:

 

1 基础能力建设

 

搜索引擎首先是一个工程的问题,基础能力的夯实,将为后续各种基础设施和检索能力的建设打下坚实的基础.

 

1.1 迭代质量保障

 

建立了一套全面的评测体系来对引擎质量进行评估,确保持续迭代过程中的版本质量保障.

 

1.2 工程核心问题解决

 

算力分配是内存搜索引擎在工程方面的核心问题,我们采用了流水线设计(分配高效)+时间片调度(分配均衡)方案来解决.

 

1.3 复杂度管理

 

通过组件化设计,实现了清晰的软件分层架构,同时保证了检索内核的独立性和开放性.

 

1.4 性能优化专项

 

从倒排查找算法优化,算力榨取,内存优化,分支优化多个角度进行召回性能优化.

 

2 进阶能力建设

 

搜索系统的比拼最终会落在 NLP 能力的比拼上面,站在工程这个岗位上,我们的思路是对检索引擎扩展出丰富的检索特性,灵活的检索控制能力,高效的运营/调试能力,最终给与业务同学更大更灵活,以及更高效的操作空间.

 

2.1 召回架构设计

 

通过双层级语法树设计,兼容多索引类型检索,支持不同类型索引任意组合的求交求并。

 

通过原语法树求交实现,拒绝二项式变换,保留原始检索语义,进而实现多种召回方式。

 

2.2 诊断能力建设

 

衡量大型分布式系统的复杂度管理的标准之一:是否具备高效的运营效率。其最终影响的是整个团队的迭代效率

 

2.3 索引实验能力建设

 

提供灵活的数据评测手段,如召回实验,正排实验。

 

2.4 Everything Online 的设计理念

 

让检索引擎的一切行为都可以通过请求参数实时控制,让业务同学可灵活组织其召回策略。

 

3 团队效能建设

 

团队越大,业务分工越细,每位开发同学对于业务目标达成的边际效应将越明显,站在工程这个岗位上,我们的思路是建立必要的公共技术体系,例如将业务目标抽炼为一些公共且必要的技术框架,重新组织和聚合每位开发同学的开发成果,让其能发光至全部业务。

 

3.1 公共相关性库的建设

 

搭建了一套相关性开发框架,定义了标准开发流程,可灵活组装,应用范围能覆盖搜一搜内部的全部场景。我们希望能将各个小团队的相关性开发成果组织起来,聚集为大团队的开发成果,再转而服务全部业务。

 

整体来看目前我们比较欠缺的是在接入优化,引擎易用性等方面,这两块的投入和建设非常少,不过主要也是人力所限了,欢迎对在线召回感兴趣的同学加入我们一起建设。关于搜索引擎工程设计的分享文章就此为止,后续应该不会再写了。非常感谢老大能给到机会和时间,能脱离业务摸鱼一年,还好勉勉强强完成了预期目标,不然只能给拥堵的滨海大厦腾出工位了。最近一年,应该也是职业生涯里写出最多 BUG 的一年,非常感谢 jacky,sigma, sings,change,jaye,lie,yixiang,leol,levi … 等等搜索技术中心的同事,在引擎各方面建设还不足并且有坑的时候,就开始接入使用,严格来讲,搜一搜的技术演进是他们在推动进行的。

 

后话

 

回过头来看 ZeroSearch 第一版在线系统的设计还是比较稚嫩的,当时有幸在腾讯技术工程公众号上发表过,小编同学还起了个很唬人的标题:新一代搜索引擎设计… 当时看到这个标题时,心情真的十分复杂。

从项目立项开始,这一年来的工程实践,整个过程更像是一个不断”破圈”的过程,当我们在圈 A 时,我们看到了圈 B,而当我们到达圈 B 时,我们看到了更广大的圈 C。以前我们看山是山,认为检索引擎只是一个工程问题,专注在引擎工程架构的建设上,现在我们看山才是山,专注在业务长远价值的建设上。

 

但帮助我们快速实现破圈的其实是落地应用,当技术落地应用后,问题才会凸显出来,从而弥补我们自身的认知缺陷,最终也反向推动技术应用变得更加成熟,这是一个互相成就的过程。

 

总结下来是两句话:

 

1 做工程技术需要脚踏实地,心怀敬意,直面问题,解决问题。其实不需要什幺高端理念指导,也没有所谓方法论,或者说方法论就是找准问题,用心做事;

 

2 工程技术是很难实现自突破的,需要伴随着相应的应用场景,与其一起成长进化。

 

本人自认为分享过的所有文章都还是比较纯粹朴实的,不会有什幺空洞的字眼,唬人的概念,力求干货,正如我所在的团队的做事风格,纯粹务实。搜一搜正在招聘后台开发和运营开发工程同学,我们致力于通过技术能力将微信生态内的海量精品内容和服务精准触达到每一位用户。这是一件极具挑战但富有意义的事情,很多程序员都可能曾经拷问过自己当初来到互联网世界的初衷是什幺,我相信这件事情足够我们在回首往事时用来取悦自己。

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注