3.1　物料检索系统

正如上文所述，物料检索系统的职责在于快速地从海量候选集中筛选出与业务目标具有较高匹配度的候选集，而这个候选集也框定了后续所有模块的优化范围，因此该模块具有举足轻重的地位。此模块被广泛地应用于广告、推荐和搜索等信息检索领域中，虽然在不同场景下它所承载的物料不同，但是检索技术是较为通用的。举例来说，在搜索场景下，物料集合是网页链接；在信息流推荐场景下，物料集合是用户博文；在广告场景下，物料集合是广告计划。如图 3-2 所示，倒排检索、相似检索和模型粗排是该系统中最主流的技术。

3.1.1　倒排检索

倒排检索是一项历史悠久且最为经典的物料检索技术，它的核心思想是建立从检索关键词到物料的映射关系。这项技术最初被使用在搜索引擎中，随后它也在诸如推荐系统和计算广告等领域里得到了广泛应用。倒排检索的架构如图 3-3 所示，它包含了关键字词典、倒排索引文件和正排集合这几个主要部分，其中关键字词典是物料中的关键词集合，正排集合通常是物料本身，而倒排索引文件则是从关键字到正排集合的映射关系。

● 关键字词典：它通常利用哈希表或者 B+ 树这两种数据结构来实现。哈希表的实现较为直观，系统把每个关键词经过哈希函数映射到某个存储空间，该空间包含了关键字对应的倒排列表及其附属信息。哈希函数的选择和哈希表的设计是非常重要的，通常来说，我们需要以减小哈希冲突和提高内存利用率为目标。B+ 树是一种平衡多叉树，它的每个节点都可以有多于两个的分支，并且绝大部分信息都只存储于叶节点中。图 3-4 展示了一个基于字母序的 B+ 树词典，其中第一层将所有关键词按照首字母排序分为三个分支；第二层继续以首字母顺序进行细分；第三层为叶节点，它存储着关键字以及对应的附属信息。

● 倒排索引文件：它存储着关键字所对应的倒排列表。倒排列表是一种较为直观的数据结构，它通常为一块连续的空间并存储着某个关键词对应的物料标识集合。为了提高检索效率和内存利用率，系统可以应用如下一些常见的技术。

● 差值存储和变长编码：通常来说，物料标识是一个较大的正整数，系统可以通过存储前后两个物料标识的差值把需要存储的元素转化为较小的整数，然后系统就可以利用变长编码来进一步压缩数据存储空间。Gamma 编码就是该领域内十分常见的一种编码格式，它的编解码都是基于位操作的，因此它具有较高的运行性能。

● PForDelta 编码：这种编码是在变长编码基础上的一种改进方案，它将索引块作为解压缩的基本单位，以便提升整体的运行性能。此外，PForDelta 算法还可以通过阈值设定的方式将数据划分成两部分，前一部分存储数值较小但是占比较大的数据，后一部分则存储那些具有较大值的数据。借助整体解压缩和阈值设定这两个特点，该编码格式可以在压缩率和运行速度之间寻求良好的平衡。

● 介质优化：系统可以把冷热数据存储在不同的存储介质中，以便取得性能和成本的平衡。通常来说，冷数据可以被存储到本地磁盘或者分布式文件系统中，而热数据可以被存储到内存和固态硬盘中。

3.1.2　倒排索引实例

Lucene 是一个广为使用的开源全文检索库，它利用许多经典的倒排索引技术构建了一套较为完善的查询引擎和索引引擎。Lucene 倒排索引的核心结构如图 3-5 所示，其主要包含词索引、词典和倒排列表三个部分。与上文介绍的通用结构相比，Lucene 也利用了一些独特的技术来提升系统性能，其中词索引和倒排索引段是比较具有代表性的。

● 词索引：它的核心思想是快速定位到关键词的大体位置，然后进行精确搜索，以便找到该关键词及其对应的倒排列表。特别地，Lucene 采用了 FST（Finite State Transducers）这种比 Trie 树更为强大的数据结构来实现词索引。FST 是一种特殊的有限状态机，它在结构上和 Trie 树具有相似之处，但是它除了可以让关键词共享词的前缀，还能让它们共享词的后缀，因此 FST 拥有更高的空间利用率。

● 倒排索引段：它是一种典型的 LSM（Log-Structured Merge-Tree）数据存储结构，在读/写性能上均比较高效和均衡。如图 3-6 所示，倒排索引被分成了若干个具有不变特性的数据段，并且每个数据段都是一个独立的索引。当系统向倒排索引中添加新的文档时，新的文档信息会首先写入内存中，随后系统会异步地把内存中的新增数据批量落盘到磁盘上，并形成新的倒排索引段。此外，系统也会定期地进行索引段的合并与清理来减少文件碎片和冗余数据。熟悉 RocksDB 的读者可以发现，Lucene 在倒排索引上的设计思路和 RocksDB 是非常类似的，它们都具有较为均衡的读/写性能，并且这样的数据存储方案在固态硬盘上的表现远远优于其他方式。

3.1.3　相似检索

倒排检索在文本或者标签层面进行物料匹配，而相似检索则在语义层面进行匹配，因此它常常具备更为强大的泛化能力。在相似检索悠久的发展历程中，诸如 TF-IDF 等许多优秀的技术都在不同阶段发挥了重要作用。近年来，由于机器学习特别是深度学习的发展，基于向量空间的相似检索彰显了强大的生命力，它被广泛地应用在各类互联网业务中。

基于特征向量空间的相似检索是目前最流行的方案，它把用户、物料和查询语句等一切元素都投影到一个公共的语义向量空间内，不同元素之间的相似性可以用欧氏距离或者余弦相似度等指标来衡量。欧氏距离，即两个向量终点之间的直线距离，一般来说，距离越短的两个元素具有越高的相似性；余弦相似度，即两个向量之间的夹角，一般来说，夹角越小的两个元素具有越高的相似性。如何把元素投影到向量空间内，以及如何在空间中进行高效检索，都是充满技术挑战的难题，前者一般可以利用协同过滤或者深度学习模型来解决，而后者则可以借助最近邻搜索算法来解决。

● 基于协同过滤的传统模型：协同过滤（Collaborative-Filtering）是一种历史悠久的建模思想，它早已被广泛地应用于推荐系统中，其核心思想是通过对行为的观察来达到人以群分、物以类聚的目的。矩阵分解模型（Matrix Factorization Model）和因子分解机模型（Factorization Machine Model）是协同过滤里面最具有代表性的方案，前者把代表历史行为的高维稀疏矩阵分解为两个由特征向量组成的低维稠密矩阵，而后者在此基础上通过增加更多的特征来进行模型表达能力的升级改造。这两种方法都可以把元素投影到同一个语义向量空间中以便进行相似检索。

● 基于表示学习的深度模型：深度神经网络模型也可以把元素依照表示学习的建模思路抽象为特征向量。相比于传统模型，深度模型具有更好的特征自动组合能力和泛化能力，但它也对计算资源和算法建模能力提出了更高的要求。在文本检索领域中，微软的 DSSM 模型具有代表性意义，而双塔模型则在推荐、搜索和广告领域中发挥了重要作用。双塔模型的结构如图 3-7 所示，它将特征划分为请求侧和物料侧两部分，这两部分可以利用不同的网络结构来生产最终的顶层特征向量。双塔模型的一个重要优势在于它的灵活性，因为系统可以根据实际需要对顶层特征向量的生产时机和利用方式进行调整。通常来说，请求侧的特征向量可以通过实时计算得到，而物料侧的特征向量则可以采用离线和半实时的方式来生产，系统还可以利用诸如 Faiss 等高性能的检索库来提高在线匹配效率。

● 最近邻搜索算法（KNN）：它的核心目标是快速地找出与给定向量最相邻的 K 个向量。一般而言，KNN 检索系统可以借助 K-D 树或者局部敏感哈希（LSH）等技术来进行构造。K-D 树是一种可以进行精准相似检索的数据结构，但是它的检索性能在海量数据的情况下往往不能尽如人意。LSH 虽然只能进行近似检索，但是它可以利用前置的数据降维操作来极大地提升检索性能。该技术的核心思想是利用一些具备特别性质的哈希函数来使得哈希冲突最大化。具体而言，LSH 可以利用 Jaccard 指标来衡量两个向量之间的相似度，然后利用哈希函数把原始高维向量空间内相邻的元素映射到低维空间里的相邻位置上。

3.1.4　相似检索实例

Faiss 是由 Facebook 开发的一个高性能的相似性检索库和聚类库，它支持多种索引结构、硬件设备、编程语言和检索方案。在具体的使用过程中，系统可以利用 Faiss 对物料向量进行索引构建，随后再利用该索引为请求向量返回最佳的相似检索结果。Faiss 的一个重要特点在于它的灵活性，系统可以按照实际需要来进行设置，并找到内存占用量、检索性能和结果精确度之间的平衡方案。

● 精确搜索：针对请求量较小或者物料候选集较小的场景，Faiss 提供了 IndexFlatL2 和 IndexFlatIP 两种精确搜索的索引方案。前者使用欧氏距离来衡量相似度，而后者采用内积来衡量相似度，这两种索引也是其他高级索引的实现基础。一般来说，精确搜索这种暴力检索方式可以在 GPU 硬件加速器的帮助下达到令人满意的匹配效率。

● 相似检索：针对海量物料候选集的场景，Faiss 采用了主成分分析（PCA）和乘积量化（PQ）等技术来达到检索效率与内存占用量之间的平衡。在内存足够大的情况下，HNSW 索引是最佳选择，它能够提供几乎最优异的性能。在内存资源基本够用的情况下，系统可以先利用各类聚类算法进行向量空间的划分，然后在向量子空间内利用上文提到的精确检索方案。在内存资源不足的情况下，Faiss 则充分利用了 PCA 来进行向量降维压缩，并利用了 PQ 来进一步压缩存储空间。

总而言之，Faiss 提供了一套性能优异、配置灵活、部署方便的相似性检索解决方案，它被广泛地使用在物料召回、网页去重、图像检索、版权识别和指纹匹配等领域中。

3.1.5　模型粗排

如图 3-8 所示，在物料检索阶段，系统会依赖上文提到的倒排检索和相似检索等技术从多个不同的物料召回通路里获得候选物料，然后进行多路归并和物料去重操作，最后系统会得到一个规模较大的物料候选集。如果这个候选集的体量比较庞大，则会给后续的精准排序和策略机制环节造成较大的计算压力，因此检索系统通常会内置一个简单的模型粗排引擎来对物料进行初步的筛选。受限于计算规模，在进行目标值预估的过程中，模型粗排引擎通常只会利用诸如 FM 模型和表征向量等较为精简的结构。当然，随着模型量化压缩、模型蒸馏和模型剪枝等软件技术的进步，以及硬件加速器的进步，深度神经网络模型也在粗排环节中愈发常见。最后值得一提的是，在部分场景中，粗排模块也可能会结合多样性策略、负反馈策略以及运营策略来进行更为精细化的物料筛选。