搜索能够让用户直达目的，成熟的互联网产品基本上都会标配搜索能力。如何从海量数据中检索出符合用户预期的数据，需要依赖一系列工程和算法的手段。 其中召回模块作为检索的最下游，负责从亿级的文档中筛选出千级别的候选集。工程上会遇到性能、稳定性各方面的问题，本文根据历史经验、希望总结出一套行之有效的经验集。
导读
推荐本质上是”猜你喜欢“，根据用户特征猜用户感兴趣的内容，推荐给用户；相比推荐而言，用户通过query表达了自己的意图，搜索围绕输入query，挖掘用户意图；而广告，则是带价格的推荐、搜索场景。
搜索工程的整体架构，大的流程上与推荐、广告并没有太大的区别：核心都是召回、粗排、精排、重排。经过重重筛选，最终从海量资源池中，返回用户需要的资源，展示出来。
对于搜索场景，通常还会前置一个qu环节（query understanding)，从词法、语法、语义多个维度挖掘有效信息、识别用户意图。通常包括多个算子：分词、纠错、query扩展、query改写、意图识别、时效性识别等。
语言级优化
召回引擎核心的计算、存储节点大多都是采用C 语言。以下优化主要针对C 语言层面。
使用jemalloc
默认的C 程序是使用glibc内置的ptmalloc来进行内存管理的，ptmalloc相对稳定，但是会存在内存碎片、以及加锁导致的性能问题。尤其在SMP多线程的环境下，主分配区的锁竞争会比较激烈。
可选的有tcmalloc和jemalloc，jemalloc在静态线程（线程不会被频繁的创建和析构，比如协程场景，调度线程数是静态固定的）虽然内存占用更多，但是加锁大幅减少，在多线程场景性能表现最优。
开启protobuf arena
trpc默认采用protobuf协议，在我们之前的性能perf中，发现pb对象的析构耗费了较多的cpu时间。
默认情况下，每个消息对象和子对象，比如字符串、map等，都会在堆上进行分配，解析消息时，这个分配操作会大量发生；析构是，又要为每个子对象执行对应的析构操作。对象嵌套越深、子对象越多，内存分配和析构调用的次数会越多。
aren正好能解决这个问题。它的原理相对简单，pb对象构造时，预先分配一个内存块，后续构造内部的message都在这块内存上以placement new的形式创建出来；内存块不够的时候，会触发扩容（拷贝）。它维护的对象析构，都在arena析构时统一进行，一次释放整个arena。
虽然arena能够提供内存分配、对象析构的效率。但使用中，仍然需要注意一些问题：
- 初始对象大小：前文有提到，初始化内存块不够时、arena会进行扩容，合理的通过参数指定初始化内存大小，能进一步提高效率
- 涉及生命周期变更接口使用：set_allocated_xxx, release_xxx；swap操作等。在实现上都会发生变更。比如swap，实际会退化为copy
避免拷贝
对于非pod类型，以值拷贝形式传参时，需要特别注意：
- 是否可以使用Move语义
- 是否可以使用引用，或者指针传递：对于字符串类型，是否可以使用string_view
- shared_ptr对象：传参时通过引用传递
- protobuf对象：是否可以通过release_xxx转移对象生命周期；protbuf容器，是否可以swap
另外，不要滥用shared_ptr；在日常CR中，发现有很多同学即使生命周期非常明确、甚至是临时变量，也习惯用shared_ptr；当然用shared_ptr会省力。然而shared_ptr使用并不是无开销的，另外会带来false-sharing问题。
不做无用抽象
多态性是C 重要面向对象特性，利用继承is-a的关系，能够提高使用效率、简化代码编写和修改过程，代码也能体现良好的接口性。
但当一个接口表现出多态性的，是无法内联的。内联函数代码被放入符号表中，在使用时进行替换；大部分场景下，能够减少调用开销，间接提升性能。特别是在热点函数上，更是如此。
无锁化和RCU
多线程情况下，对数据进行读写，常见的是通过加锁的方式来解决。即便加锁的区间合理、冲突比较小，加锁也会引发cpu cache失效，只能从内存中读取。
使用cas指令，在多cpu场景下也并非是最优解。每一个cpu的cas操作，都会导致其他cpu的cache失效。
因此，我们常采用rcu(read copy update) 来实现无锁编程。比如单链表的插入（双链表不能采用）：
- 第一步：创建L5节点（新节点）
- 第二步：将L5->next 指向L2
- 第三部：将L1->next指向L5
删除时，除了修改前趋节点的next域，还要将被删除的节点置于延迟删除队列，避免该节点正在被其他线程持有，从而导致内存问题。
linux内核中就有rculist的实现：https://github.com/torvalds/linux/blob/master/include/linux/rculist.h
存储
分而治之
召回的集合是整个物品库，物品库的规模跟业务场景强相关：如大搜和垂搜的差别就很大。像一些视频搜索的场景，文档通常是数十亿级别。
在实现上，通常会对召回的文档进行分库。按不同的优先级：比如文档质量分、时间维度等划分成一个一个分库，每个库根据文档集合的大小又会分成不同的数据分片。召回整体的架构示意图如下：
其中：
- merge 层负责解析分词结果，并决定以何种方式（求交、求并）请求分库。最终归并各分库的结果返回给上游。归并的方式可以按硬quota、或者粗排分作为统一衡量标准
- 分库merge 是每个分库的入口服务。核心职责是归并下游各分片结果。
- 最下层是存储与计算的核心节点，其中存储包括倒排索引、正排存储等；计算包含相关性得分计算、过滤等
分库带来的好处是：
- 有利于优质资源的露出
- 减少扇出压力，实际上转化为二级扇出
- 为稳定性提供更多选项：如果上游压力过大时，可以摘掉不太重要的库种，减少上游的归并压力和下游的负载
分片带来的好处是：
- 打破单节点的容量限制
- 做到节点级并行，减少单节点存储、计算压力
字段数字化
业务侧统一数字化处理，能够极大简化存储、加速计算。
这里的数字化处理，包含文档的唯一id、以及文档相关的正排字段等。
如果业务侧不能处理，在索引离线构建时，引擎也通常会将文档id数字化处理，这里有两种做法：一种是存储数字化的签名；一种是对文档编号，并存储数字化id 与 真实文档id之间的映射关系。
对与正排字段，在垂搜场景下，也可以采用类似手段，对字符串进行编码。同一分片索引内同一个字符串只存储一份，也能极大化节约内存。加速计算。
倒排存储
索引的设计是存储引擎核心点，倒排索引结构的设计是搜索引擎的核心。召回模块从上亿文档中筛选符合条件的万级别文档，第一步就是倒排拉链的交、并处理。关于倒排索引的详细定义，可以参考：维基百科
搜索场景下，倒排索引存储的是【单词 -- 文档列表】的映射。
最容易想到的是：用hash map存储单词列表，用list存储每个单词下的倒排文档列表。如下图：
实际上在工程中，很少会这样简单的实现。这里面存在的问题是：
1. 词：本身有很多公共前缀（后缀）。如果要明文存储term，直接采用hash_map存储、存储效率和性能上都不是最优。
实际上除了kv，还有类似B 树、FST存储类型。在lucene中通常会实现为FST，可以共享前缀和后缀，而且能够实现范围查找：https://www.shenyanchao.cn/blog/2018/12/04/lucene-index-files/
即使是采用hash_map的形式，实现不同，性能和存储效率差异也会比较大。可供选择的有tsl::hopscotch_map、google::dense_hash_map等：https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html
2. 有序拉链：拉链会涉及到很多求交、求并的操作。比如用户要召回同时包含”搜索“和”召回“两个term的文档，需要将这两条拉链求交。如果直接用链表实现，求交操作效率比较低，需要从当前位置一个一个遍历查找（o(n)时间复杂度）。
工程实现中，跳表是常采用的结构。
跳表中，上一层是下一层的索引。只有最底层存储真正的数据。一般我们会把增量和全量索引分别存储（当成不同的分片，或者不同的内存块），所以全量索引只读不写。这里的指针会完全省掉，数据也会做一定的压缩。
比如我们采用三级索引，第2级实现为有序数组，存储真正的postling list以及payload信息；第1级映射term-block位置信息；第0级则存分域信息。
计算
通过倒排链交并处理后，可以拿到符合文本相关性阈值要求的初始列表。但是这个列表并不能直接展示给用户，通常业务层需要对这份数据做过滤：比如安全等级、标签筛选等。
这些过滤条件会抽象为一颗过滤语法树，可类比mysql检索条件的where部分。其中包括比较、范围查询。相比mysql而言，存储引擎支持多值类型，会使得计算更为复杂。
rbm存储
如前文所述，计算是召回逻辑的关键环节。拉链交并处理得到的每一个文档，都要经过过滤语法树的计算，通常是十万级别。同理，对这里性能热点的优化整体的召回性能都得到较大的提升。
以字符串比较为例：用户需要查找标签满足【玄幻、国漫】一个条件的短视频，每个视频文档上、该字段为一个多值字符串类型，例如：【玄幻、武侠、日漫、...】五到十个字符串。如果对每个文档进行匹配，即使对文档标签按字符串序排序、进行二分查找。也要经过多次字符串比对。而采用bitmap存储、将每个字符串匹配转化为bit查找，则会极大的加速计算性能。
单个文档的值，分散在不同的bitmap上。
在存储上，对于可读的全量副本、可用rbm进一步压缩bitmap的存储空间。
bitset 缓存
对于统一场景，一段时间内过滤条件基本是相对固定的（除了用户筛选的例外）。以mysql为例：where a = 's' and b in ('shenzhen', 'guangzhou', 'beijing')，如果where条件相对固定，可以将a / b对应的bitmap，合并为一个大的bitmap，并缓存起来。这次每次查询中，多个Bitmap的位check，可以转换为单次bit为比较。
通过bitset cache，能够提升50% 的性能。对于长尾部分query，提升效果更加明显。
需要注意的是，cache实际上是以空间换时间，业务场景不同，采取的策略可能不尽一致。如果过滤条件是用户筛选的结果，可能不能粗暴的做bitset cache。可以将头部（比较频繁出现的部分cache），提高cache命中率。
稳定性
任何系统的容量都有上限，我们不可能无限制的扩容应对用户行为带来的流量变更。且由于召回是带数据、有状态的服务，即便机器资源充足，从容器调度、进程拉起到数据加载完毕，也需要一定的时间，可能扩容完毕，流量尖峰已经把系统击垮。
而召回是系统的最底层，由于系统扇出，承受的QPS一般也远高于用户层实际触发的QPS。
因此，稳定性对于召回系统而言至关重要。
除了平常规范研发流程规范，对系统定期压测、做到对系统容量胸中有数外。应对各种突发情况，常用的手段就是缓存和降级。
缓存
缓存可以分为有损和无损的。通常的情况下，召回引擎开启10秒左右的数据有效时间cache，能有效起到消锋的作用；虽然会带来数据更新不实时，但是仍然可以认为无损的。
实际上，垂搜场景的用户top query比较集中。合理的设计缓存key，缓存命中率能够达到70% 的高水位值。
可以将用户请求分为以下几类：
- 高频query
- 长尾query
- 无结果query
高频query数量不大，但是能够涵盖大部分流量。即使不对这部分请求cache，也可以采用类似请求队列的机制，确保同一个时间维度（比如10ms）以内的多个请求，只会有一个穿透到下游。
长尾query数量不多，占比也不高。但是通常会由于query比较泛、遍历深度较深，底层召回和计算的压力反而更大。容易造成超时。对这部分query进行cache，能够有效消除系统失败率尖刺。
无结果query：不是所有的query一定会有结果，特别是垂搜场景。有可能是没有符合条件的倒排拉链，也有可能是对整个链交并、过滤后，没有符合条件的文档。对于第一种情况，即使不做cache、也能迅速返回结果，并不会消耗太多资源；对于第二种条件，将会产生大量的无效计算。
降级
当我们开启cache后，流量仍然超过了系统的负载。此时，只能对外提供有损的服务，即降级。降级的手段有很多种，各层的降级策略都可以选择。
对计算层而言，可以选择：
- 减少遍历深度：减少参与过滤和相关性计算的文档数
- 减少进入TopN候选集的文档数：减少topn分计算
- 如果粗排设计在计算层，还可以减少送粗排的文档数，减少粗排耗时、降低粗排负载
对分库merge层而言，可以选择：
- 分片缩召回：假设上游需要N个文档，正常情况下，每个分片都需要召回N个文档，分库归并层才能取到全局的topn。当系统压力过大，可以减少每个分片召回的文档数
- 延长cache数据的有效时长，降低穿透率
- 如果粗排在归并层，同样可以降低送粗排的文档数
对merge层而言，可以选择：
- 减少各分库的召回策略，以降低扇出压力
- 摘库：直接将下游优先级不高的库流量摘掉；将机器资源扩给更重要的库和策略
- 延长cache有效时长
