腾讯技术 | 新一代搜索引擎项目 ZeroSearch 设计探索

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

背景

写这篇文章很大的原因在于不论是内网还是外网,分享内存检索引擎设计的资料都非常稀少,且存量的资料大多侧重于功能性的介绍。

另一方面,在磁盘检索引擎方面,由于开源搜索引擎 ES 的盛行,对于其使用的索引库 lucence 的分析资料反而较为丰富。

本文意在通过分享对于内存检索引擎的认识,核心的解决方案,和一些优化方向的思考等等,略微填补一下关于内存检索引擎设计的资料空缺。

需要说明的是本人进入搜索领域的时间并不长,尽管之前搭建过一些垂类搜索系统,但只是站在应用层面进行使用,真正从事引擎设计的工作也是通过今年 4 月份左右组内重新设计新一代搜索引擎的项目 ZeroSearch 开始,恰巧承担了在线检索的设计与开发。因此这并不是一份多么标准的答案,而是我们对于引擎设计的探索,其质量还需时间检验和调整。

本文属于 ZeroSearch 系列分享中的在线检索设计分享。在本文中假定读者已经对搜索引擎有了基本的了解,至少对倒排求交,打分排序有基本的概念。

系统认知

对于系统的认知深度,会决定我们怎么去看待内存检索这样一个问题,以及由此而产生的的设计方案。尽管本文要讲的是内存检索引擎设计,然而我们还是得从对磁盘搜索引擎的认识开始。

由于 ES 的盛行,以及网页搜索(搜索领域的大 boss)体验的存在,大多数人对检索引擎的认识可能都是基于磁盘检索引擎来理解的,即系统的倒排,正排数据都位于磁盘中,只有在执行检索时,才会将相关的数据 load 到内存中。

其整体的流程大概如图所示:

image.png

磁盘搜索引擎在设计的过程中面临的主要问题为:

  • 同时兼具计算密集型与 IO 密集型任务
  • 磁盘与内存及 CPU 存在数量级差距的性能 GAP,磁盘资源属于瓶颈,而计算量富余。

因此其在设计过程中考虑的核心要素为两点:

  • 任务调度的设计,即管理 IO 任务与计算任务
  • IO 优化 如异步 IO 设计,IOCache 优化,索引压缩等等

尽管 IO 优化也是非常重要的一环,但我们认为磁盘搜索引擎的核心,本质上是一个任务调度的问题。

现在回到内存搜索引擎的讨论上来。很明显,内存检索引擎在去除磁盘 IO 后,其要解决的核心问题是计算量的分配问题,即如何合理的分配计算量,能尽可能的让优质结果展现给用户。

下面是我们给内存检索引擎制定的核心流程:

可以看到我们对于计算量的分配,抽象出了求交,L1 打分,L2 打分等 3 个逻辑阶段。

求交
即根据查询串取出对应的倒排链进行求交,得到结果文档

L1打分
求交出来的文档均会送入L1打分

L2打分
L1得分Top的文档才能进入L2打分

这里为何要将打分分为两个阶段呢?

1 满足高求交数的需要

由于倒排数据处在内存中,因此单篇文档的求交消耗较少,限制引擎召回量的瓶颈往往不在求交,而在打分。轻量级的打分配合高求交数,可以避免求交截断导致的文档无法召回问题的出现

2 满足轻量级业务的打分需求

对于一些排序较简单的业务,不需要单独的精排服务,可以在引擎的 L2 打分过程中满足它的需求。

需要注意的是对于一些高消耗的模型,我们会放在更高层次的排序中,并对其进行抽离,放在独立的 tf 服务上执行,并不会放在引擎的 L1、L2 阶段来执行。

L0 打分在离线索引过程中我们会提供接口用于计算文档的质量分,因此全量文档计算都会进行质量分的计算,建立倒排索引过程中,质量分越高的文档,排序越靠前,以保证被优先查找到

核心设计

设计背景

在讲述核心设计之前,需要先了解以下几点背景

1 索引分片分库

索引会先进行分片,多个分片再合并为一个索引库。分片数一旦指定后便不可更改,但是索引库的库数是可以灵活调整的,可以满足业务数据增长,索引数据多集群划分的需求。在检索过程中,索引库是检索的基本单位。这一点与 ES 可做一个简单的对比,ES 为库-> 分片(多个库)-> 实例(多个分片)的设计,而我们的设计为分片-> 库(多个分片)-> 实例(多个库),即我们将数据分片放到了更底层,打开了它的数量限制,同时对库的数量进行了收敛,原因在于库数越多,引擎性能将越差。关于索引分片分库的详细背景和设计后续组内会另有同学来进行介绍。

2 无 RPC 框架设计

引擎自身不携带 RPC 框架,我们以组件化的思想来进行设计。通俗来说,就是封装成了一个库,提供了初始化函数和唯一的检索入口函数来给到外部进行使用。这种方式有优有劣,优势为无须考虑上层的协议头,可灵活适配于各种 RPC 框架中,并复用已有的运维体系。劣势为对线程的控制能力较弱,理想情况下引擎自身的工作线程与 RPC 工作线程应当资源隔离,通过亲缘性各自分配和独占 CPU,这一点在组件化里难以实现。

事实上我们是面向 Controller-Proxy-Work 这一类 RPC 框架进行设计的,典型的如 SPP,Svrkit 等,并且在我们的实现过程中,将预处理和回包处理的逻辑均放到了 RPC-Work 线程中进行。

3 以易用性为第一优先级

组内上一代的内存搜索引擎由于基础配置项过多,引擎细节暴露过多,且欠缺配套的 debug 工具/能力,导致它的学习和维护成本都非常高。在新引擎的设计过程中,我们将易用性列为了第一优先级,本质上也是以服务业务为第一优先级,即便是性能方面也需要为易用性让步。易用性方面主要会体现在以下几点:

3.1 引擎的学习成本应具备梯度,满足快速入门使用的需求;

3.2 配置项尽可能少,尽可能避免暴露引擎细节,尽可能以通俗语言表达,如内存大小,线程数量等;

3.3 需要有全面的问题定位能力,根据经验,维护垂搜业务时,最常做的事情就是查文档为什么召不回,如果引擎具备问题一键定位的能力,那么可以有效的减少运维成本。

需要说明的是,尽管这里提到了易用性,但是下面的内容不会涉及到我们为了提升引擎易用性采取的具体做法。这里之所以单独拎出来进行强调,在于根据我过往的业务开发经验,部门内上一代内存搜索引擎的学习和维护成本过高,与业务的快速发展已经不匹配,我认为作为一个基础平台,性能 100 分,还是 80 分,甚至是 70 分,只要可以通过加机器来解决,对于增长型业务来说基本就不太 care 了,而易用性(含可维护性)才是最优先被考量的因素,其对团队的整体效率有很大的影响。

在清楚了大概的设计背景之后,可以开始真正考虑该如何设计我们的检索引擎了。

线程模型设计

下图是我们的检索组件目前使用的线程模型:
image.png

每个检索请求到达时,会生成一系列的求交与打分任务,在召回完成之后,会生成一个资源清理任务进行提交,请求完成。

下面对图中的主要元素做下简单的介绍

1 主线程
即RPC框架的Work线程,在Work线程中,会完成请求的预处理和回包处理的逻辑,并且处理求交或者打分任务完成后的回调逻辑。

2 JoinThreadPool
负责处理求交任务的线程池,在上面已经提到过,索引会分片分库,索引库是检索的基本单位,而一个求交任务至少会处理一个索引库(由于数据实时更新,系统中会存在一些小库,多个小库可能会被放到一个求交任务里进行处理),每个求交任务一旦分配到线程,就会将任务完整的执行完(或者超时)。

3 ScoreThreadPool
负责处理打分任务的线程池,打分任务分为L1打分任务和L2打分任务,但是线程池是共用的一个。对于L1打分任务,当一个求交任务完成的求交文档数量达到一定程度时,便会生成一个L1打分任务Push到打分队列中。L2打分任务同理,也是等到L1打分文档达到一定数量才会生产。

4 CleanThreadPool
负责处理资源清理任务的线程池,即资源的清理是异步进行的

5 求交资源池
负责管理求交时需要的一些数据结构,以资源池的形式来完成复用

可以看到整个线程模型是以 Task 为调度粒度的,这种模型有个比较大的缺陷,每个 Task 的消耗其实是不一致的。对于求交任务而言,每个任务会将一个索引库给求交完(达到限制或者超时),而随之产生的 L1 打分任务和 L2 打分任务,每个任务其实都只是求交出来的部分文档,因此求交任务的消耗是非常高的,并且求交任务在入队时是在一个 for 循环里集中式的入队(直到所有的索引库都分配完),为了防止打分任务饿死,这里划分了 3 个线程池以避免这个问题。

然而划分多个线程池本身就是问题所在,至少存在以下 3 个方面的问题:1 增加了配置项,降低了易用性。

2 其实业务并不知道该如何去对各个线程池的线程数量进行配置(尽管引擎会简单的根据 CPU 逻辑核数量进行默认设置),只能不断去调整测试来达到一个合适值。

3 多个线程池的方式不论怎么去配置数量,都不太可能把所有线程都高效利用起来,必然会有计算资源不能充分利用的线程池存在。

尽管存在这么多很容易预见的问题,我们还是先这样做了,一方面是目前开发人力非常少,在线检索这块的开发只有我一个人在兼职,需要弥补完善的东西还有很多,整体确实还比较粗糙,另一方面主要也是目前我们还没有建立一个用于质量标准评测的系统,因此一些优化类的工作优先级都排的比较低。

关于有没有饿死情况的出现,我们的评判标准并不是针对个例的发现,而是通过统计p99,p995,p999等指标来进行评判。因此严格意义上来说,也并不是真正的饿死,毕竟FIFO队列只要入队了迟早会被执行,只是等待时间长和短的问题。

正如标题是对于引擎设计的探索,这里简单分享一下后续计划要尝试的几个线程模型的方向,当然下面所有的方向都是只使用一个线程池。

1 继续维持 FIFO 的模式这个很好理解,也就是所有的 Task 都入同一个先进先出的队列,其实这个改动起来非常简单,只是质量标准评测系统还没搭起来,就暂时没去做对比测试了。

2 逻辑越轻量,优先级越高同样很好理解,即创建一个特殊的优先级队列,对各类 Task 根据逻辑的繁重设定一个优先级,设想的情况是这样的,优先级从高到低为:

清理Task > L1Task > L2Task > 求交Task

在 Push 任务时,优先级越高的直接插入到队首,但是同类 Task 之间依然保持先进先出的关系。最终是一个这样的队列:

image.png

为什么要这样做呢?

可以有效解决由于求交任务的高消耗和集中入队导致其它任务饿死的问题。通俗一点理解,那就是只有当所有的打分任务都完成了才会去执行求交任务。

从过程上看,似乎会有一个新的问题,即便系统有多个逻辑核,索引库之间的求交打分变成了线性的模式(串行),而非并发的模式?

但是从结果上进行分析,这种调度模式是否改变了处理请求时所需要的计算量?很明显,并没有。同样的,单位时间内机器的算力也并没有浪费,因为除非请求已经完成,否则一旦有空闲线程出现,那么必定会被分配给求交任务。那么至少从结果上来分析,这种模式应该是有效的,当然具体效果优劣,数据表现如何,还需实验验证。

以逻辑越轻量,优先级越高的优先级队列管理任务似乎会引入一个新的问题,即求交任务可能被'饿死' ? 这一点很难评判,原因在于两点
    1 打分任务其实是由求交任务产生,如果求交任务得不到执行,那么也就不会有打分任务了。
    2 单个打分任务的文档数较少,逻辑相对较轻,影响较小。
    具体还是需要实验验证后才能得出明确结论。

3 以时间片为调度粒度彻底改变 Task 为调度粒度的模式,换为时间片的模式,同时继续保持 FIFO 的模式,每个 Task 消耗完时间片后就被丢入队尾,直至超时或完成。

以时间片为调度粒度时,此时众生平等,也就不需要关注 Task 之间的消耗程度孰轻孰重带来的饿死情况轻重的问题了。  时间片调度这种模式其实还有一个好处,对于一些召回数过低的请求,大概率在一个时间片内就能被执行完,那么它总体的等待时间就会少很多,从它要入队时开始分析,等待时间由:

sum(队列Task-处理完成所需耗时之和)

降低到 sum(队列 Task-时间片之和),但这种模式有没有被引入的问题?

同样有的,对于高召回的请求需要多个时间片才能执行完,由于每次时间片执行完需要重新入队,那么它的等待时间相比 Task 的模式大概率是会增加的。不过这个问题相对来说还比较好解决,至少我们可以从以下两点来缓解和解决。

1 增大时间片的粒度即将时间片粒度变大,如由原先的 500us,增大为 1ms。从而可变相减少高召回请求的入队次数。当然这里也需要控制力度,极端情况下会退化为 Task 模式。

2 增大高召回请求的时间片粒度即给高召回请求的分配的时间片为基础的时间片 2,或者 3 等等,这是一种有效解决高召回请求入队次数过多的方法。但是难点在于我们如何识别出高召回请求?这是一件很有挑战性的事情,不过这里先不介绍我们在筹划的做法,下文中会提到。事实上,它不止对于线程模型调度的设计有直接影响,对于稍后介绍的任务模型同样有影响。

细心的读者可能已经想到了,高召回请求是从结果上来看的,当我们从过程上来看时,问题就简单很多了,即回到了问题本身,它是入队次数过多的请求。那么我们只需要增加每次重新入队时被分配的时间片即可,一种最简单的方式是参考 vector 的内存增长的方式,更高级的方式这里就不展开了,索引数据和求交进度也是分配的参考项。从而有效解决高召回请求入队次数过多的问题。不过同样,这里的增长也需要控制力度,极端情况下会退化为 Task 模式。

线程模型的介绍暂时就到这里了,下面我们看一下任务模型的设计。

任务模型设计

任务模型与线程模型有什么区别呢?

线程模型更专注于计算量(任务)的执行,而任务模型更专注于计算量(任务)的分配。对于执行者来说,它是任务无关的,而对于分配者来说,它本身就是任务的创建者,与任务是强相关的。在介绍线程模型时,其实我们已经大概清楚了,引擎中有以下 4 类任务,分别为清理任务,求交任务,L1 打分任务,L2 打分任务。其中清理任务较为独立,就不多花笔墨介绍了。

下面直接看我们的求交打分任务模型:

任务模型的核心要素为以下 3 点:

1 求交依然维持单库单线程求交(小库例外,多个小库合并一个求交任务)

2 求交文档达到阈值时生成一个L1打分任务

3 L1打分文档达到一定阈值时生成一个L2打分任务

从而可以实现求交、L1 打分、L2 打分并行执行的效果,整体达到一个流水线的设计,就如上图所示一样。组内的上一代内存搜索引擎对于求交打分是一个阶段一个阶段的执行,整体是一个串行的模式

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

在实际的实现里,上一代引擎对于每一个索引库其实是单线程边求交边 L1 打分的(因此本质上属于串行),等全部求交文档 L1 打分执行完毕后,再进行一次快速选择排序选出 TopK 得分的文档,然后把这部分文档送入 L2 打分,L2 打分结束后,进行最终的 TopK 排序,然后进入回包处理阶段。

在新引擎中,我们将求交与 L1 打分进行了拆分,并对打分任务以 Task 为粒度进行调度。为什么要这样做呢?当然是因为这是一种 CPU 利用率更高的做法。下面我们进行一个讨论,在这个讨论里我们先假定引擎的工作线程池只有一个,这样的话更利于分析。

假设索引库数 = CPU逻辑核数

1 在一个线程处理一个库内文档的求交与L1打分的形式下,各个线程耗时计算方式是固定的
| ------------------|-------------------|
           求交耗时 +  l1打分耗时
最终耗时为: max(各个库的求交耗时+l1打分耗时)

2 如果我们将求交与打分拆开,每次求交部分后,再将这部分送出去进行打分,让打分
独立出来,从而达到流水线化:
| ------------------|
       求交耗时
      |-------------------|
            打分耗时
|-------------------------|
         总耗时
理想情况下,最终耗时为:
sum(各个库的求交耗时+l1打分耗时) / 引擎工作线程数 = avg(各个库的求交耗时+l1打分耗时)
原因是计算总量虽然并未减少,但是被打散得更均匀了。很明显这种模式能更好的利用CPU资源

假设索引库数 > CPU逻辑核数

3 将会出现一个线程处理多个索引库,我们可以理解为这多个索引库只是一个更大的索引库,从而问题回归到讨论1与讨论2中。

假设索引库数 < CPU逻辑核数

4 老模式下其最终耗时依然为:max(各个库的求交耗时+l1打分耗时)
    新模式下其最终耗时为:
(sum(各个库的求交耗时+l1打分耗时) - 非求交线程承担的L1打分耗时 ) / 求交线程数
该值比avg(各个库的求交耗时+l1打分耗时)会更小。

尽管拆分后的方式 CPU 利用率更高,但是很明显,新的方式在总吞吐方面并不会提高。

计算基础
1 单位时间内机器的算力是固定的

2 每个请求需要消耗的算力并没用变

因此在极限情况下,吞吐方面确实没有提升。不过实际上,在正常情况下,我们都会保证机器的负载在一个较低的水平,以此来保证服务的安全,而当机器负载未满时,新模式下长尾求交任务通过把l1打分逻辑分发出去可以更充分利用总的CPU资源,从而减少请求的耗时。

我们可以得出以下两个结论:

  • 新模式在极限情况下的总吞吐没有提升
  • 相同吞吐情况下,新模式 CPU 利用率更高,因此请求处理平均耗时会更少

另外一个问题,为什么我们要维持单库单线程求交?简单来说,求交不是召回瓶颈,当然如果真的发生了这种事情,求交成为了召回瓶颈时,我们的建议是减少每个索引库包含的分片数。

最后,细心的读者可能早早就发现了,求交出来的文档是需要都送入 L1 打分的,但是只有 L1 得分 Top 的文档才能进入 L2 打分,整个任务模型里的求交-L1 打分-L2 打分的流水线处理应该无法实现才对。的确是的,求交结果进入 L1 打分是一个确定的行为,而 L1 打分结果是否进入 L2 打分是一个待定的行为。为了满足流水线的计算,我们需要将待定行为转为确定行为。

1 文档预估

如果我们能够知道一个请求能求交得到多少篇文档,那么当求交文档数 < L1 结果限制数(TopK 里的 k 值),那么很明显,所有完成了 L1 打分的文档都可以直接进入 L2 打分。

1.1 根据文档频率预估这是一种简单粗暴的方式,例如用户搜索[苹果手机],它的分词结果得[苹果 | 手机],两者的关系为求交,那么这个 query 的预估召回文档数就为:

min(Term(苹果)倒排链长度,Term(手机)倒排链长度)

如果考虑到苹果手机整体与 iPhone 同义,那么其预估召回文档数就为:

max(Term(iphone)倒排链长度,min(Term(苹果)倒排链长度,Term(手机)倒排链长度))

即根据各个 Term 的文档频率和其逻辑关系来进行简单的推导。很明显,实际求交文档数,一定会小于等于该推导值。

1.2 缓存查表由于一定时间内的索引数据是相对稳定的,我们可以通过缓存检索 query 和求交数的映射关系,每个请求到达时进行一次查表来完成预估。可能有读者会质疑,那为什么不直接缓存求交结果呢?

其实这是两个维度的东西,它们本身也并不冲突,如果在引擎内对结果缓存会占用较多的内存,我们期望的做法是在更上层对分页后的结果进行缓存,因为可以明确的一点是首页的缓存命中率一定会显著高于后续的结果页。另外引擎内进行缓存的话还会影响系统的时效性,这一点并不合适。

1.3 模型预估通过模型来对一个 query 的召回文档数进行预估。由于每个业务的数据量是相对稳定的,可以通过在线收集 query 和查 询语法树的特征以及倒排链相关的特征,离线训练,在线接入,来完成预估。

2 预计算即选出一部分 L1 打分完成的文档,先进行 L2 打分计算。目前我们实现的方式有以下几种:

2.1 固定篇数模式取固定的 l1 结果数进行预计算,原则为先完成 l1 打分的文档将会被送入,这是因为由于 l0 得分的存在,通常我们认为越先被求交出来的文档,其质量越高

2.2 得分阈值模式 l1 得分大于得分阈值的进行预计算

2.3 得分比例模式 l1 得分大于 (已完成 l1 打分的文档的平均分 * rate) 的文档进行预计算,因此其实这是一种特殊的得分阈值模式,只是它的阈值在不断调整。

由于我们目前只有一些较简单的离线业务接入了新引擎,上面几种方案的具体效果如何还没有得到一个可信的数据。另外后续也会考虑不断加入新的预计算方式,例如将固定篇数模式与得分阈值模式组合起来使用。

事实上,预计算几乎肯定会有浪费计算量的情况出现,即本不能进入 L2 打分的文档却被执行了 L2 打分。其浪费率以及耗时降低的收益需要根据各个业务自己的需求而定。

需要特别说明的是,新引擎在 L1 打分阶段完成之后(求交阶段已完成,且 L1 打分任务全部完成),依然会整体进入 L2 打分阶段,对 L1 结果集取 TopK,然后分配 L2 打分任务,只是每个 L2 打分任务对分配到的文档进行打分时会先判断是否已经被预计算过了,如果是的话则直接跳过。因此预计算的存在并不会导致结果不稳定的问题出现。

求交设计

求交设计分为两块,一块是语法树求交设计,主要是查询语法树的设计和求交算法。另一块是查找算法设计,主要介绍倒排查找的做法。

语法树求交设计

对于求交而言,基本的理解其实就是取出几条倒排链,然后计算出倒排链中公共的文档。不过实际情况比这个要复杂很多。对于求交设计而言,第一步要考虑的是查询语法树的设计,我们从同义词开始,在新引擎的设计里,我们采用的 3 层结构语法树。假设 [苹果手机] 存在同义词 [iphone],那么对于 query [苹果手机回收] 的最终的检索语法树为下图所示:

这里以宽度优先的方式给每个节点进行了编号。可以看到这是一颗 and-or-and 的语法树,可以支持多对多的同义词表达形式,例如这里的节点 2 下面的两个同义词词组,就是一个 2 对 1 的同义词组。

现在我们要需要考虑一下这样的一颗语法树如何做召回。一种很直观的做法是这样的:

1 节点6与节点7的倒排链进行求交,得到的pageid作为节点4的pageid

2 节点2的pageid = min(节点4 pageid,节点5 pageid)

3 比较节点2的pageid与节点3的pageid

3.1 节点2 pageid = 节点3 pageid
则弹出该节点作为求交结果,所有节点对应的倒排链后移一位

3.2 节点2 pageid < 节点3 pageid
节点2先内部求交得到一个大于等于节点3 pageid的文档

3.3 节点2 pageid > 节点3 pageid
节点3对应的倒排链查找第一个大于等于节点2 pageid的文档

上述过程一直持续有节点2或者节点3有节点到达了末尾为止。其中节点2由于是一颗子树,它是否到达末尾,由其子节点节点4与节点5到达了末尾为止,节点4同理。

关于pageid
在建索引库时我们会对进入到该索引库的文档按L0得分排序,从0开始重新编号,当然库内会有一片区域保存库内pageid到原docid的映射关系。这一点的主要目的是为了保证倒排链中的文档按L0得分排列后依然有序,次要目的是为了对倒排链进行压缩。但是对于内存搜索引擎而言,我们暂时还没有尝试对倒排链进行压缩,一方面是因为CPU同样是紧张资源,另一方面团队也还没有精力投入到这一块。因此目前其最大的作用只是保证了倒排链中的文档id有序,以及库内文档id的连续(从而可以根据库内文档id直接下标访问文档数据),另外把8字节的文档id,转成了4字节的库内pageid,省了一半内存。

本人之前听到过多次这样的说法:语法树的层级越高,求交的性能就会越差。如果是按照我上面所述的求交方式的话,那么的确是的,层级越高,求交性能就会越差。原因是什么呢?

原因在于高层级的语法树进行求交时可能会存在一些不必要的求交行为。以上面的那颗 3 层语法树为例,假如节点 6[苹果]和节点 7[手机]这两条倒排链中的 pageid 都非常小,而节点 3 的 pageid 比较大时,那么有可能节点 2 所有的求交结果都来自节点 5。



那为什么会存在一些不必要的求交行为呢?其本质在于上面所述的求交方式是一种逻辑先验的求交算法。下面介绍一种逻辑后验的算法。

定义求交基准为一个可能的求交结果

1 计算求交基准N = max( min( max(节点6 pageid, 节点7 pageid), 节点5 pageid), 节点3 pageid)

2 所以倒排链全部往N靠拢,找到第一个>=N的位置

3 判断所有倒排链当前的结果是否符合求交逻辑关系,若符合则弹出结果且相关节点后移一位。

4 判断是否求交结束,如果未结束则流程回到1,否则退出

求交损耗的本质为各条倒排链的跳跃查找次数,and/or 等语法只是建立在倒排链的跳跃查找之上的逻辑关系,跳跃查找次数越少的,性能也就越好。在逻辑后验求交算法里,每次选出的求交基准 N 都是一个可能的求交结果,也就是说除非我们能找到新的算法可以再次排除一些可能的求交结果位置,否则不会有比它性能更好的语法树求交算法。

现在尝试一下将语法树打平,看一下打平后的语法树具备哪些方面的优势。这里要介绍的是我们上一代内存搜索引擎中将 3 层结构语法树转化为 2 层结构语法树进行求交的做法。

笛卡尔积语法树

通过将 3 层语法树结构里的同义词节点做笛卡尔积,可得到与其等效的 2 层结构语法树,还是以 query [苹果手机回收] 为例,其中 [苹果手机][iphone] 互为同义词,将其转换为笛卡尔积语法树后,其结构如下图所示

其原理为
(A && B) || (C && D)
= (A || (C && D)) && (B || (C && D))
= (A || C) && (A || D) && (B || C) && (B || D)

当然这里的同义词组更简单,为(A && B) || C 的模式。下面我们分析一下笛卡尔积语法树与原语法树的差别。

求交性能分析

为了能够更具体一点的了解不同语法树之间的性能差异。我们需要对求交性能做一个定量的分析。下面对 3 层结构的原语法树和其对应的笛卡尔积语法树各自的求交过程来进行性能分析,依然以苹果手机回收这个 case 为例。

1 原语法树求交基准的计算公式:(此处直接以Term值来表示对应Term节点)
max ( min(苹果 && 手机  , iphone)  , 回收)
  笛卡尔积语法树求交基准的计算公式:
max( min(苹果,iphone) , min(手机,iphone) ,  回收)

2 给定一个基准的前提下:
  源语法树需要操作的语法节点为4个,对应为4条倒排链
  笛卡尔积语法树需要操作的语法树节点为5个,对应为5条倒排链

3 两种类型的语法树结束条件较为相似,都是某一颗子树到达末尾
源语法树结束条件:
(End(苹果 || 手机)  &&  End(iphone))  ||  End(回收)
笛卡尔积语法树结束条件:
(End(苹果 || iphone) || End(手机 || iphone)) || End(回收)
由于
End(苹果 || 手机)  &&  End(iphone) = End(苹果 || iphone) || End(手机 || iphone)
因此结束条件的位置其实是一致的。

为了简化性能评估,我们假定每次语法节点的操作损耗相同,则性能评估的大致公式为:

image.png

从公式上来看,决定性能的因素主要有以下 4 点:

  • 求交基准总数
  • 语法节点个数
  • 求交基准选取损耗
  • 语法树节点操作个数

现在我们来对比下打平后的笛卡尔积语法树和原语法树之间的差异。

1 求交基准总数由于(A && B) || C = (A || C) && ( B || C),因此两颗语法树的最终逻辑肯定是一致的,只是表现形式不一样而已,那么仅从公式上,可以知道这两颗语法树的求交基准个数肯定是一样多的(这句话其实是有一些问题的,不过可以先这么理解)。

2 语法树节点个数很明显,笛卡尔积语法树的语法节点数会大于原语法树的节点个数,(A && B) || C ==> (A || C) && ( B || C)的转换,其实是析取范式到合取范式的一个转换,并且恰好属于转换后会导致子句指数型暴涨的情况,即同义词组的个数越多,每个同义词的叶子节点越多,那么转换后的语法树节点就越多,并呈指数型增长。语法树节点越多,求交时的逻辑也就越重。

3 求交基准选取损耗对于求交基准的选取损耗很明显是跟语法树节点个数强相关的,由于笛卡尔积语法树的语法树节点远超原语法树,因此笛卡尔积语法树每次的求交基准选取损耗都会大于原语法树。

4 语法树节点操作个数笛卡尔积语法树层数降低为了 2 层,并且消除了第 3 层的 and 逻辑,整颗语法树只剩下最顶层的 and 逻辑。这一点有什么优势呢?我们在对 and 节点下的子节点进行求交的时候,往往都是一个节点一个节点的操作,因此如果只剩下最顶层的 and 节点的时候,一旦发现有节点经过跳跃查找后,跟求交基准的值不一致,可以很方便的提前就结束掉对于该求交基准 N 的查找,即可以很方便的提前排除掉求交基准 N。

这一点对于笛卡尔积语法树来说是一个优势,可以减少排除一个基准的需要操作的节点个数。但是其只是降低了提前结束求交基准 N 的查找的代码实现的复杂度,对逻辑后验求交算法进行改进后同样可以实现。

改进的逻辑后验求交算法当我们得出一个求交基准时,各条倒排链都需要进行跳跃查找第一个大于等于求交基准 N 的值,我们可以通过在查找过程中就更新求交基准 N 的值,从而减少后续每条倒排链的查找次数

经过对比后可以发现,语法树打平之后其实并没有什么优势,并且会导致语法节点数指数型增长,因此我们目前认为使用原语法树配合逻辑后验求交算法就是内存检索引擎最佳的求交方式。这种想法当然有点坐井观天了,如果有读者有更好的方式,欢迎指点一二。

在了解完同义词,以及 3 层结构语法树的逻辑后验求交算法后,可以再简单了解一下其余的查询语法。

1 丢弃词可设置 and 节点下的 term 节点为丢弃词,这样的话,它不会参与求交。为什么不在 query 处理环节就把它丢弃掉呢?这里存在一些差别,一个 term 节点即便被设置丢弃词,我们依然会为它设置文档的命中信息,这对于相关性库(文档打分库)来说是有必要的。其实现方式为不参与逻辑后验以及求交基准的计算,但是会参与对于求交基准的倒排链跳跃查找。

2 动态非必留与必留词动态非必留是一种动态求交方式,例如一个 and 节点下挂了 3 个 term 节点 A,B,C(均不是丢弃词),动态非必留设置为 2 个 term 命中即可召回,那么一个文档只要 A,B 或者 A,C,或者 B,C 命中即可。

必留词是指在进行动态非必留求交时,该词必须是求交元素,一般我们会设置在一些核心词上面。例如 A 设置为了必留词的话,那么一个文档只要 A,B 或者 A,C 命中即可召回。动态非必留适用于一些召回不足的场景。其实现方式为对 and 节点下的 term 进行快速选择排序,在选取求交基准时,不再对所有 term 节点取 max,而是取倒数第[必留个数]大的 term 的 pageid 弹出去。

3 位置约束可对一个 and 节点下的 term 设置位置约束。例如一个 and 节点下挂了 3 个 term 节点 A,B,C(均不是丢弃词),我们可以设置 B 存在 Pos=OneOfPos(A)+1,设置 C 存在 Pos=OneOfPos(B) + 2。在我们的引擎里,如果是相邻 term 也设置了位置约束,那么它们会作为一个整体来进行位置约束判断,有点类似于多槽位的模板匹配。其实现方式为取出相关 term 的 pos 列表做二分查找。

and-or语法,配合丢弃词的求交方式,特别依赖于Query处理能力,丢弃词设置的好与坏会决定求交结果准确与否。例如对于Query:[深圳有哪些景点],如果深圳或者景点被设置了丢弃词,那么召回结果可能会完全偏移,这种属于在召回侧结果集就已经偏移,在相关性上面进行排序调整也十分吃力。
WeakAnd求交方式是我们目前处于计划中,但还未实现的一个功能,主要原因在于其标准实现方式与新引擎当前的任务模型有冲突,我们还未能找到方法将其良好的融合进去。对于WeakAnd的实现方式网上的资料很多,这里不想赘述。我们对它的认识在于这种求交方式可以缓解对于Query处理能力的依赖。

查找算法设计

正如上面提过的一样,求交损耗的本质为各条倒排链的跳跃查找次数,跳跃查找次数越少的,性能也就越好。语法树求交设计解决的问题是尽可能减少跳跃查找次数,而查找算法设计解决的问题是尽可能减少每次跳跃查找的消耗。

由于新引擎的倒排索引结构细节较多,为了方便阐述这块的内容,这里看一下我们组内上一代内存检索引擎的倒排索引结构,由于其相对简单,适合拿来介绍查找算法。

image.png

倒排结构整体是先分块(Block,BLK),每个块内再保存具体的 page 信息,page 信息主要分为两部分,一部分自然是 pageid 列表,另一块是 page info 结构,保存的各个文档的 term 级别的信息,这里就不对其进行介绍了,直接忽略它即可。

关于分块设计的背景
1 继承自磁盘检索系统,磁盘分块读取

2 内存分块,有助于实时索引构建。相当于是说对于实时索引数据是以块为单位进行加载的,不过我们的系统并不是这样实现的,我们的实时索引数据依然是以库为粒度进行加载的,因此在我们的系统中索引数据都是分布在连续内存中。

以库粒度进行加载,其索引时效性如何保障?这个问题暂且搁置,在后续的ZeroSearch系列文章中会有解答。

上一代引擎在查找某个 pageid 时(连续内存中),采取的做法是先二分查找到对应块,然后再在块内进行二分查找。

有问题么?表面上看,似乎并没有什么问题。我们对它简单分析一下,假设某个 term 的倒排链长度为 L,块长为 T(即每个 BLK 内至多保存 T 个文档信息),则块数为 N=L/T,则查找次数为:logN + logT = logN*T = logL 而不分块直接对整条倒排链二分查找的查找次数显然也是 logL。

因此上一代引擎的索引设计以及查找算法其实并没有带来查找效率的提升。从一个有序列表中,找到第一个大于等于 N 值的位置,二分查找就是最快速的查找方式了,似乎并没有优化空间了?如果从结果出发,站在宏观的角度来思考优化,那几乎不可能能得出答案,我们需要以微观的角度,深入到过程来寻找优化空间。

对于倒排查找过程的思考

1 过程的连续性事实上倒排查找并不是只查找一个 N 值,而是随着求交过程,需要不断的去查找新的 N 值,且 N 值之间满足严格递增关系。即整个过程是具备连续性的。

2 数据分布特征索引分片分库时文档已经被打散过一次(稀疏),这对倒排链(聚集)中的 pageid 分布是否会有影响,它们的值分布稠密或者稀疏对于求交是否又有影响。即倒排链 pageid 是否可能具备数据分布特征。

3 长链与短链长链与短链对于求交的影响如何,是否应该区别处理,长链与短链该如何去定义。通过对求交过程进行分析和思考,得出了这 3 个点。下面我们以一个特殊的实例来看一下求交过程。

假设存在这样的一条短链 L1 和一条长链 L2,它们的 pageid 范围相近,且前后 pageid 的间距都是固定的(数据分布均匀),其中短链的前后 pageid 固定为 d1,长链的前后 pageid 固定为 d2:

现在分析一下存在的求交组合情况,主要从查找消耗和求交基准两点进行分析。

1 短链与短链求交
查找消耗:由于本身链路短,因此二分查找时,总的查找范围较小,查找消耗较低。
求交基准:求交基准的数目上限为短链长度L1。
特殊:由于短链的间距d1过大,单个Block内的pageid跨度(范围)会更大。下一个求交基准落在本block内的可能性较高。

2 短链与长链求交
查找消耗:由于短链的间距d1过大,因此长链在查找过程中依然适用于二分查找,但是长链查找范围会偏大,查找消耗一般
求交基准:求交基准的数目上限为短链长度L1

3 长链与长链求交
查找消耗:长链与长链求交时,由于长链的间距d2较小,下一个求交基准N大概率出现在上一个基准附近,因此长链在二分查找时,查找范围过大,资源消耗较高
求交基准:求交基准数目上限由长链长度L2决定

现在泛化到多条链之间的求交情况分析,即短链变为多条,或者长链变为多条,或者两者都变为多条。由于我们采用的是多哨兵位的求交算法,是从整体进行求交,那么在多条倒排链(大于 2 条)求交时,只有以下 3 种情况。

1 全部都为短链
问题回归到短链与短链求交的讨论

2 同时存在短链与长链
问题回归到短链与长链求交的讨论

3 全部都为长链
问题回归到长链与长链求交的讨论

现在考虑数据分布不均匀情况下的求交特点。数据分布不均匀时,将存在稠密区域与非稠密区域,稠密区域内 pageid 的值分布集中,间距较小,而非稠密区域 pageid 的值分布较为分散,间距较大。同样存在以下 3 种组合情况

1 非稠密区域与非稠密区域的查找,与短链与短链的查找特点相似

2 非稠密区域与稠密区域的查找,与短链与长链的查找特点相似

3 稠密区域与稠密区域的查找,与长链与长链的查找特点相似

尽管问题又得到了回归,但是数据分布均匀与否依然有着显著的差异,即数据分布均匀的情况下,它的求交特点是稳定的,而数据分布不均匀时,求交特点是变化的,可能上一次查找属于非稠密区域与非稠密区域的查找,下一次查找时就落入了稠密区域与稠密区域的查找了,甚至随着求交过程,长链与短链的相对关系也在变化。

关于如何去评判一条倒排链的数据分布情况,计划采用的方式是通过计算间距的平均值和方差来进行评判,因此实际上当前我们对于这一点也还属于还未开工的探索阶段,暂且无法得到数据分布特征的一些数据。

不管怎样,问题总算是得到了回归,至少我们可以得到以下两点结论和一个猜想:1 多条倒排链求交时,其耗时主要由短链的长度决定,原因是求交基准的数目上限由短链决定。

2 多条长链求交时,长链每次查找范围过大,因此查找消耗较大。

3 猜想:不论是对于长链还是短链,下一个求交基准大概率落在近邻 Block 内

以这 3 点为基础,可以给我们的查找算法带来一些新的思路。下面介绍求交优化的做法。

1 倒排链查找优化根据猜想:下一个求交基准大概率落在近邻 Block 内。我们将先使用步长增长查找的方式对近邻 Block 进行查找,未找到再二分查找剩余 Block,Block 内依然使用二分查找。

步长增长查找:每次向后查找的 Block 数量为 2^(n-1),确定目标位置后,再在该 2^(n-1)个 Block 内进行二分查找。

了解到这种查找方式其实有个专有名词叫:Galloping Search,其实是很轻松就能想到的方式。

需要注意的是,在这里我们需要对长链和短链区分处理,简单来说就是短链查找的近邻 Block 较少,长链查找的近邻 Block 较多。具体下文会分析。

2 bitmap 对于超长链,其倒排结构使用 bitmap 进行存储,bitmap 具备快速求交、快速求并、快速查找等特性,然而 bitmap 在 bit 位稀疏时的顺序迭代访问性能较差,而求交基准在选取时是需要获取每个节点当前指向的 pageid 的,对于 bitmap 来说,需要通过顺序迭代访问来找到第一个非零 bit 位。因此超长链的定义将主要由 bitmap 带来的收益和迭代性能来决定,仅从空间使用率上来看,未压缩的情况下其实一条倒排链只需要满足长度大于等于索引库文档总数/32(pageid 采用 4 字节存储)即可,当然这个标准在性能上肯定是不行的。

3 语法树查询优化

3.1 短链优先查找由于短链节点查找消耗更低,单次查找更快,因此短链节点优先查找,用于快速更新求交基准,减少后续倒排链的查找次数,同时 pageid 值的间距更大的可能性较高,利于快速增长求交基准 N。

需要注意的是,随着求交过程的不断执行,长链,短链的相对关系可能会发生变化,这里的短链优先查找是在求交开始之前就对查询节点的查询顺序进行调整,后续不会再进行调整。

3.2 同义词子树置后查找与短链节点优先查找对应,由于同义词子树一次查找需要对多个 Term 节点进行倒排查找,因此在评估单次查找消耗时,需要以整颗子树进行考虑,其查找消耗是该子树下所有 Term 节点之和。最终的效果会导致同义词子树被置后查找。同样的,这里的调整是在求交开始之前就完成,后续不会再进行调整。

3.3 bitmap 合并 bitmap 语法节点合并,对于有多个 bitmap 子节点的父节点,可对其新增一个虚拟语法节点,对 or 节点下的 bitmap 节点进行求并,对 and 节点下的 bitmap 节点进行求交。

3.4 重复词节点合并对于语法树中的每个 Term 节点,我们只会创建一个倒排访问对象,简称游标(Cursor)。在逻辑后验算法里,所有倒排链都在往求交基准 N 查找,因此对于相同的 Term 节点,它们可以共享同一个游标。

4 指令集优化经组内同事 sen 指点,在求交过程中可以利用 SSE 指令集(需要硬件支持)中的 XMM(128bit)、YMM(256bit)等大长度寄存器,使用单指令多数据流的方法一次比较多个整形元素,来达到求交加速的效果。这类寄存器的使用跟步长增长查找的方式恰好十分匹配,这一点属于我们后续打算尝试的一个方向。

那么遗留下来的问题就是如何定义短链,长链,以及超长链了。

短链长链与超长链

其中超长链的定义相对简单一些,设定一个阈值 X,当且仅当:倒排链长度 / max(倒排链的 pageid) >= X 则倒排链使用 bitmap 进行存储。X 的考虑主要是 bitmap 收益与顺序迭代访问损耗的一个折中,这一点需要通过业务数据来实际验证后才能明确。

那么短链和长链又该如何定义。短链与长链的区别对待体现在近邻查找时的 Block 数量上,在这里我们需要先简单分析一下步长增长查找方式与二分查找在性能上的差异。

条件:假设倒排链总长度为 n,块长为 T,块数为 N。二分查找的时间复杂度为:

logN + logT = logn

需要注意的是由于倒排查找过程中要找的是第一个大于等于求教基准 N 值的位置,因此每一次二分查找,其查找次数不多不少,都是 logn(n 为还未查找过的文档数量)。如果以倒排链长度为 X 轴,时间复杂度为 Y 轴,那么二分查找的时间复杂度就是一条直线。

当使用步长增长查找方式时,假设第 X 次确定了目标位置,那么其时间复杂度为

X + log2^(X-1) * T = 2X + logT - 1,其中1 <= X <= log(N+1)

其最小值约等于 logT,最大值约等于 logN + logn,如果以倒排链长度为 X 轴,时间复杂度为 Y 轴,那么很明显,步长增长查找方式的时间复杂度为一条曲线。

从步长增长查找的复杂度公式里的最小值和最大值可以知道,越在前面找到下一个求交基准的位置,那么步长增长查找带来的提升就越大,再往后,其性能就开始落后于二分查找了。现在可以开始考虑短链与长链了。假设存在阈值 K,Block 数目大于 K 的就是长链,小于 K 的就是短链,我们希望的最理想的效果是使用步长增长查找时的平均复杂度小于等于使用二分查找的平均时间复杂度。

由于二分查找的时间复杂度固定为 logn,因此其平均复杂度也就是 logn 了。而步长增长查找的平均时间复杂度的计算要麻烦许多,假定求交基准落在每一个 Block 的概率是相等的话,那么其平均时间复杂度为:


乍一看好像挺复杂的,完全误会了,本人数学底子非常渣。这里其实就是对于每一个 X,都乘了一下[当前 X 所覆盖的 Block 数量 / 总 Block 数量]的比例值,得到的平均时间复杂度的公式。

总之,由于本人的数学底子非常渣的原因,我这里就直接给出我们这边计划尝试的 K 值了,K=15。怎么得出来的呢?通过计算 k=3,7,15,31,63 等等情况下的两者的平均时间复杂度,发现 k 值越大,步长增长查找的平均时间复杂度就越高(但其实算法实现的时候会发现,当我们限定了只查找多少个 Block 时,步长增长查找方式的逻辑会轻很多,尽管查找次数上并不占优)。最后因为如下 2 点原因选择了 15:

1 越靠近的Block,命中下一个求交基准的概率就越高(仅仅是猜想,还未有实际业务验证),虽然k=15时平均复杂度已经比二分高了,但如果越靠前的Block命中概率越高的话,靠前的Block区域加权因子变大,靠后的Block区域加权因子变小,那么其平均复杂度可能并不会比二分高。

2 XMM寄存器一次可比较4个32bit的整数,与步长增长查找15个Block刚好对应。如果XMM的使用确实带来了优化,那么我们后续也会对YMM进行测试。这一点才是主要考虑的原因,为后续指令集优化埋下伏笔。

即在我们的引擎里,Block 数量大于等于 15 的则为长链,小于 15 的则为短链。对于长链,在近邻搜索时最多查找 15 个 Blcok(含当前 Block),对于短链,我们只与当前 Block 的最大值进行比较一次。

需要再次说明的是以上的讨论都是建立在猜想:越靠近的 Block,命中下一个求交基准的概率就越高。原因在于文档在索引分片分库时已经被打散(稀疏)过一次,同时一个 Block 内保存的是多个 pageid,被稀疏过后的文档又紧密存储(聚集)在一起。

如果猜想不成立呢?

计划用质量标准系统统计一下长链在求交过程中命中下一个求交基准的 Block 与上一个位置所处的 Block 的距离。例如如果有 90% 以上是落在 X 个 Block 内的话,那么依然还是有价值先对这 X 个 Block 进行查找的。

另外当我们确定要对 X 个 Block 进行查找时,是有多种查找方式可以使用的,例如从前往后查,或者从后往前查,恒定步长的查找方式,步长增长的查找方式等等。具体如何使用还是需要视数据分布特征而定。

关于近邻查找的篇幅显得有点啰嗦了,最后再简单总结一下:由于文档在索引分片分库的过程中被稀疏和聚集过一次,求交过程的连续性,以及索引数据相对稳定的特点,我们尝试去寻找一些特征来帮助我们加速整个倒排查找过程。

如果把两种查找方式的时间复杂度相减,即2X + logT - 1 - logn,由于T和n都是常数,因此它们的差值为
f(x) = 2x + logT - 1 - logn
当f(x)大于0时,表示对近邻Block进行搜索时,步长增长方式的查找消耗更高
当f(x)小于0时,表示对近邻Block进行搜索时,步长增长方式的查找消耗更低
很明显,在二元坐标轴里,f(x)是一根斜向上的直线,当f(x) = 0时
x = (1 + logn - logT) / 2
x = (1 + log(n/T)) / 2
x = (1 + logN) / 2
即只有当x < (1 + logN) / 2 时,步长增长查找方式性能才会比二分查找性能会好。需要注意的是这里的f(x)中x的定义,其定义为步长增长式查找时确认到了目标位置时的查找次数。

引擎组件化

在文章的开头提到过,我们以组件化的思想来进行设计,在线检索能力被封装成了一个库,相比于携带 RPC 框架的引擎,检索库的形式可较好的融入已有的开发体系和运维体系。既然是以库的形式存在,就需要有合适的接口暴露出来,让使用者能嵌入业务逻辑和业务数据。对于组件化设计,核心的设计点如下

1 在线检索过程中检索逻辑与数据需要进行分离,一个请求相关的所有数据都是通过检索 Session 来进行管理

2 业务数据的嵌入通过检索入口传入,之后交由检索 Session 管理,在这里可以简单看下我们提供的唯一检索入口:

int32_t Retrieve(const RetrieveOptions* retrieve_options,void* business_session)

@arg1 retrieve_options : 检索协议(pb格式)
@arg2 business_session : 业务session数据

3 对整个检索流程中的各个环节暴露出接口封装成类进行管理,业务逻辑的嵌入通过反射的形式来实现注入

4 相关性接口同样封装成类,业务通过反射的形式来实现注入

整体如下图所示:

image.png

在进行组件化设计之后,检索的细节都被封装在库里。这里对 SearcherStage 设计和相关性接口设计再简单介绍一下。

Searcher 是在线检索组件的名称,Stage 是我以我拙劣的英文水平选的一个词,意为阶段。在大环节上面,检索流程分为预处理,核心处理,回包 3 个环节,我们在每个大环节的开始和结束阶段都暴露了接口,并把所有接口放到了 SearcherStage 类中进行管理。对于任何想使用 Searcher 来作为部门内通用搜索引擎的用户来说,它必须通过继承并实现 SearcherStage 类的相关接口来实现自己的通用搜索引擎,一般来说,至少需要通过 SearcherStage 类完成以下 2 件事情。

1 在AfterHandleResponse中将索引数据转化为业务数据
2 在RetrieveKPIReport中对本次请求的检索情况进行上报,如检索状态,各个阶段的文档数量,耗时等等。

需要再次说明的是,每一个 SearcherStage 对象都是一个独立的通用搜索引擎,例如在搜一搜这边,也只是存在一个 S1SSearcherStage 类,并以它为基础封装为了搜一搜的检索库,其余的所有垂搜业务都是链接该检索库,而非 Searcher 组件。

下面再简单介绍一下相关性接口的设计。相关性接口设计的总体原则:控制复杂度。其体现为以下两点

  • 人性化的相关性输入信息
  • 合理的逻辑拆分

关于人性化的相关性输入信息,本文暂且不提,这里简单介绍下逻辑拆分的背景。相关性接口的执行场景分为全局初始化、请求级别初始化及各打分环节初始化、文档打分 3 个,在我们的上一代内存检索引擎中,所有的相关性接口都集中在了一个类中,该设计客观上导致了当前所有业务的打分主逻辑都集中了一个类的实现里,臃肿,多个场景/环节的变量和逻辑交织在一起,容易出错,另一方面所有的代码都集中了一个。h 和。cc 文件中,可读性差,难以管理和协作开发。也因此,在新引擎中,我们对各个过程进行了拆分,抽象为了独立的类,类之间以组合的形式进行访问。拆分之后还有一个好处在于,由于每个文档都有独立的打分对象,文档的打分从无状态变为了有状态。

末尾

大概的内容就是这样了,在引擎的整个设计过程中,很多关键的设计点都是跟组内同事 sen 进行探讨后得到,sen 给了我很多指导和把控。我们整体的设计原则其实非常简单:

1 充分考虑易用性以服务业务为第一优先级,易用性将决定业务的服务舒适度

2 还是要像一个内存搜索引擎设计方案上还是不能太糟糕,不能存在明显的设计问题

本文取名为关于内存检索引擎设计的探索,实则也是我之前想写的检索初阶系列中的第二篇:内存检索引擎设计。之前检索初阶(一)和(三)都早早就发出来了,但其实那会对检索引擎的理解还比较浅,这篇虽然是(二),不过是作为收官之作来写的。

组内这次开发的新引擎(ZeroSearch)后续也会准备对公司内部开源,时间点应该要到明年了,其实目前已经完成了一个比较粗糙的版本,目前正处于推动业务升级的阶段,但是还有大量的 TODO 和方向还没去尝试。不过在那之前,组内后续还会有同学分别介绍 ZeroSearch 的分布式索引系统设计,索引库构建流程设计,索引结构设计等等一系列的文章 ,让我们一起为内存检索引擎设计的资料空缺出把力吧。

最后打一个小广告,微信搜索诚招 C++ 后台开发,如有搜索开发经验或大厂工作经验者更佳,诚邀有志之士,共襄大业。有兴趣的同学可与本人邮件联系:scut_huajian@qq.com


本文地址:https://www.6aiq.com/article/1604358516545
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出