酷应用

ESearch：58集团基于C++语言自主研发的搜索内核

百家作者：InfoQ 2018-06-10 03:02:03

作者｜杨逸

出处｜58架构师公众号

58 同城作为中国最大的分类信息网站，提供了房产、招聘、黄页和二手交易等多方面的生活服务信息，信息数据量和访问量逐年增长，列表页排序需求也时常变化。在这样的背景下，58 搜索技术部使用 C++ 语言自主研发了 ESearch 搜索内核，取代之前使用的 Solr，大幅提高了性能和可定制性。

经过多年的实践和优化，ESearch 已发展成为一个功能完善、性能优异、运行稳定的搜索内核，如今作为一个核心组件，承担了 58 集团（包括 58 同城、赶集、安居客等）所有搜索业务，承载每天几十亿的查询流量。ESearch 的主要特性包括：

秒级实时索引：从文档发布到能检索出该文档，可以做到平均一秒的时间延迟。
大数据量、高并发、低延迟：基于本地缓存、自定义内存池、自动 Query 改写等多种性能优化措施，可达到单机千万级文档、8000 QPS、毫秒级平均延迟。
功能丰富：支持复合条件查询、空间查询、Facet 查询、分组查询、结果去重等功能。
业务可定制：支持 SKU 查询、一一抽取、在线用户实时过滤等个性化功能。
可扩展、易复用的排序框架：支持简单的线性加权、自定义的打分表达式、基于机器学习的逻辑回归、多决策树等模型，以及多模型融合等多种排序方式。

本文将介绍 ESearch 的整体架构，并重点说明其中实时索引的设计和实现细节。

一、整体架构

上图是 58 搜索系统的整体架构，分为应用层和内核层两大部分，应用层包括 Proxy 和 Builder 两个模块，负责与业务相关的逻辑，内核层就是本文重点介绍的 ESearch，包括 Merger 和 Searcher 两个模块，负责通用的检索功能。各个模块的具体功能如下：

Proxy：查询代理，接收前端查询请求，进行意图识别和查询改写等工作，然后发送请求到 Merger，获取检索结果。
Merger：基于一致性哈希算法将请求分发到多个 Searcher，然后合并结果，并进行一些排序调整。
Searcher：包含索引数据和排序模型，负责实时建索引并执行召回、打分、排序等检索流程。
Builder：接收外部请求进行进行文档构建，并将文档发给 Searcher。

二、实时索引

实时索引的设计主要需要考虑两个需求：

文档更新能在秒级时间内生效：用户信息发布或者修改更新之后，需要能尽快被检索到。
文档更新时不影响查询效率：在大数据量大更新量的情况下，不能影响查询延时。

从查询效率出发，业界通常采用读写分离的设计，即索引不提供更新功能，避免更新操作阻塞查询线程。接收到新文档之后，先与原索引数据合并为新索引，然后替换掉旧索引，从而使新文档生效。但在文档更新量比较大，并且索引量随时间逐渐增大的情况下，合并时间会变得很长，导致新文档长时间无法生效。此外还有一些搜索引擎采用了无锁数据结构，支持索引的高并发读写，但实现相对复杂。

ESearch 也采用了读写分离设计，为了克服合并时间过长的问题，对合并机制做了改进设计：对每个检索节点的索引数据按生命周期分为多段，每段是一份完整的小索引，包含独立的倒排和正排索引等数据。新增的文档数据只和最小的索引段合并，确保了索引的更新速度。

在实际的应用层面，根据自身数据量和业务特点，我们采取了以下方案：每个节点上索引按生命周期分为 3 秒、15 分钟、6 小时、1 天、1 个月、1 个月以前等 6 级。

实时索引每 3 秒接收一批新文档数据，然后建成一个生命周期为 3 秒的小段，此时这批文档立即生效，能被查询线程召回。3 秒后，该段到达生命周期终点，由一个专门负责索引段合并的线程将其与 15 分钟生命周期的段合并。由于 15 分钟索引段最多只包含了 15 分钟内的新增文档，数据量较少，所以合并速度非常快，可以达到毫秒级。同理，15 分钟、6 小时等其他周期的段，到达各自的生命周期终点后，都会向上一级索引段合并。

生命周期在 1 天以上的段，数据量较多，合并时间较长，但其合并频率较低，每天最多一次，可以指定其在每天凌晨进行，这是一天中访问量和数据更新最少的时间段，因此对系统性能影响不大。若 1 个月周期的数据量太大，可以在线下定期将其与 1 个月以前的索引合并，合并好后推送到检索节点，避免影响系统性能。

在这种分段设计下，查询处理器可以为每个查询分配多个线程，每个线程检索一个段，最终将结果合并。因此分段设计也便于利用并发能力降低查询延时。

如果文档的更新和查询的召回条件或排序均遵循时间序（例如日志索引），那么可以只检索与查询中的时间段相关的索引段，提升检索效率，因此这种设计很适合以时间序为主要排序需求的搜索系统。

三、索引结构

上一节介绍了实时索引整体的设计，本节介绍索引段内的具体结构。

在 ESearch 中，每个索引段包含四种索引结构：主键索引、删除表、倒排索引和正排索引。

3.1、主键索引

为了便于高效计算，索引内部为整个文档集分配了从 0 开始递增的 doc id，倒排和正排索引均基于 doc id 来组织，而不使用文档的原始主键。为了能从文档的原始主键查找到对应的索引数据，必须先将主键映射为 doc id，主键索引就是为此而存在的，它本质上是一个从主键映射到 doc id 的哈希表。

3.2、删除表

倒排索引是为查询优化的，不利于原地更新和删除，因此当文档被删除时，我们需要一个删除表来标记文档的删除状态，它本质上是一个 bitmap。

3.3、倒排索引

倒排索引用于根据 term 快速查找包含该 term 的所有文档。由于采用了读写分离设计，ESearch 的倒排索引数据结构不需要支持更新，每个 term 对应的 doc id 集合以有序数组的形式存储即可。对于文本域，倒排数据还包含词频、词权、位置等信息。

58 的关键词查询通常需要在多个文本域中查询，比如“title: 租房 OR content: 租房”，需要召回 title 或者 content 这两个域中包含租房的文档。为了优化这类常见查询的性能，同时也让文本相关性计算更方便，ESearch 支持倒排域打包功能（或称联合域），即自动把同一个 term 在多个文本域中的文档集合并到同一个倒排链（Posting List）中，此功能只需在 schema 中稍作配置即可启用。如此，相当于在索引中对每个 term 预计算了多个域的并集。另外，由于不同文本域的权重不同，进行文本相关性打分时需要识别出一个 term 命中了哪些文本域，因此联合域倒排链中的每个 doc id 还必须附带一个微型 bitmap 来标记其所命中的域。

下图为把 Title 域和 Content 域合并为 Fulltext 域的例子：

3.4、正排索引

正排索引是从 doc id 到文档属性值的映射。在 58 的搜索系统中，正排索引除了存储必要的文档属性以外，也存储用于打分的文档特征。在检索过程中，也有可能读取某些正排域来进行文档过滤。

ESearch 的正排索引采用列存储设计，即不同正排域的数据分开存储。

针对 58 文档的特性，ESearch 提供了正排域的多种存储形式。58 是一个分类信息网站，所有类目的信息都存在同一个数据库中。类目不同，信息的字段差异也很大，譬如房产信息包含楼层、户型等字段，二手交易信息包含品牌、型号等字段。这些差异化的字段按统一格式合并存储在同一个数据库字段，在建索引的时候，仍会分别建到各自的倒排、正排域中。但同时各类目信息也有不少通用字段，例如标题、城市 ID、类目 ID 等。

这意味着有些域的值分布是稀疏的，例如在所有信息中，包含“手机品牌”这个字段的信息的占比可能远低于 50%，而有些域的值分布是紧密的，例如几乎 100% 的信息都包含“类目 ID”这个字段。

针对紧密型的正排域，我们使用数组作为存储形式，而针对稀疏型正排域，使用哈希表作为存储形式，这样能够避免浪费空间，也都保证了 O(1) 的平均查找时间复杂度。

此外，对于布尔型的正排域，我们直接采用 Bitmap 作为存储形式。

列存储的一个缺陷是缺乏空间局部性，可能影响 CPU 缓存命中率。例如在给一个文档打分时，通常会从正排索引读取多个特征值进行计算，因此需要进行多次查找和多处内存访问。针对此问题，可以考虑使用联合正排域，将经常需要同时访问的多个字段合并建到一个正排域中。

四、缓存与二次排序

为了降低检索服务响应时间，对检索结果进行缓存是必需的，但缓存也会导致文档字段和排序特征的更新无法立刻生效，影响实时性。本节介绍 ESearch 在使用了缓存的情况下如何保证召回结果和排序结果得到实时更新。

4.1、召回结果

在实时索引中，如前文所述，文档更新时会被建入新的小索引段中。如果旧的索引段也包含此文档，那么此文档在旧段中会被标记删除。

ESearch 为每一个段分配了独立的缓存，每个段各自将检索结果从缓存中取出后，会用删除表过滤掉已删除的文档，从而确保只有更新后的文档能被检索出来。

4.2、排序结果

为了便于打分排序，我们会把一些文档特征值存储在索引中。这些特征值不会作为召回条件，因此只建在正排索引中。对这类文档属性的更新可以不走前文所述的生成新段 - 段合并的更新流程，而是直接在正排索引中原地刷新，因此特征值刷新的性能远高于正常文档更新，从而允许我们实时调整排序结果。

为了使特征值的改变能够实时影响排序结果，我们在从缓存中取出检索结果后，对检索结果会做第二次打分排序。由于缓存中的结果一般只包含 Top 几百的文档，因此第二次排序耗时有限，不影响整体性能。

除了保证实时性以外，这种两阶段排序也便于我们在 58 主站大规模应用复杂的机器学习排序模型。

复杂的排序策略通常比较耗时，因此业界在处理海量数据的排序时，通常用“粗排 - 精排”两阶段排序的方式，在效果和性能之间做一个合理折中，即先对海量数据进行低代价的粗排，然后对粗排的 TopN 结果进行代价较大的精排，最终整个处理过程耗时不会太大。

58 分类信息的特点也很适合这种模式，很多类目（例如租房）的信息注重时效性，时间序是主要排序因素。在信息发布时间相近的前提下，需要根据信息质量、转化率等其他因素进行更精细的排序。二次排序恰好可以用来实现这样的流程：第一次排序对全量文档按时间序求出 TopN 结果集保存在缓存中，第二次排序使用复杂的机器学习模型来对 TopN 结果打分重排。

五、总结

本文介绍了在 58 搜索内核 ESearch 中，如何根据 58 的数据和搜索特点来设计实时索引以及进行索引存储和查询流程方面的优化。随着业务的不断发展，我们也将继续在检索性能、资源利用率、排序等方面持续优化，也欢迎感兴趣的同学和我们一起交流。