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

作者|杨毅

来源| 58建筑师微信官方账号

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

经过多年的实践和优化，Search已经发展成为功能完善、性能卓越、运行稳定的搜索内核。现在作为核心组件，承担了58集团的所有搜索服务。)并每天承载数十亿的查询流量。电子搜索的主要功能包括:

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

本文将介绍电子搜索的总体架构，并重点介绍实时索引的设计和实现细节。

一.总体结构

上图是58搜索系统的整体架构，分为应用层和内核层两部分。应用层包括两个模块，代理和构建器，负责业务相关的逻辑。核心层是本文主要介绍的搜索，包括合并和搜索两个模块，负责一般的检索功能。每个模块的具体功能如下:

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

第二，实时指数

实时指标的设计主要需要考虑两个要求:

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

从查询效率来看，业界通常采用读写分离的设计，即索引不提供更新功能，以避免更新操作阻塞查询线程。收到新文档后，与原索引数据合并形成新索引，然后替换旧索引，使新文档生效。但是当文档更新量比较大，索引量随着时间逐渐增加时，合并时间会变得很长，导致新文档很长时间都不会生效。此外，一些搜索引擎采用无锁数据结构，支持索引的高并发读写，但实现相对复杂。

ESearch也采用读写分离的设计。为了克服合并时间长的问题，对合并机制进行了改进:将每个检索节点的索引数据按照其生命周期分为若干段，每段为一个完整的小索引，包括独立的倒排索引和前向索引。新添加的文档数据只与最小的索引段合并，保证了索引的更新速度。

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

实时索引每3秒接收一批新的文档数据，然后构建一个生命周期为3秒的短节。此时，这批单据立即生效，可以被查询线程召回。3秒钟后，该段到达其生命周期的终点，并通过专门合并索引段的线程与具有15分钟生命周期的段合并。由于15分钟索引段最多只包含15分钟内新增的文档，而且数据量小，合并速度非常快，可以达到毫秒级。同样，其他时段的索引段将在到达各自生命周期的末尾后与下一级的索引段合并。

生命周期超过一天的段，数据量大，合并时间长，但合并频率低，可以指定每天凌晨进行，是一天中访问量和数据更新最少的时间段，对系统性能影响不大。如果一个月期间的数据量过大，可以定期离线与一个月前的索引合并，然后推送到检索节点，避免影响系统性能。

在这种分段设计下，查询处理器可以为每个查询分配多个线程，每个线程检索一个段，最后合并结果。因此，分段设计也便于使用并发来减少查询延迟。

如果文档的更新和查询的召回条件或排序遵循时间顺序，那么只能检索到查询中与时间段相关的索引段，提高了检索效率。因此，本设计适用于以时序为主要排序要求的搜索系统。

第三，指数结构

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

在电子搜索中，每个索引段包含四种索引结构:主键索引、删除表、倒排索引和前向索引。

3.1.主键索引

为了便于高效计算，整个文档集在索引中被分配了从0开始递增的文档id。反向和正向索引是基于文档id而不是文档的原始主键来组织的。为了从文档的原始主键中找到相应的索引数据，必须首先将主键映射到文档id。主键索引是为此目的而存在的，它本质上是一个从主键映射到文档id的哈希表。

3.2.删除表格

倒排索引针对查询进行了优化，不利于就地更新和删除。因此，当一个文档被删除时，我们需要一个删除表来标记文档的删除状态，这本质上是一个位图。

3.3.倒排索引

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

58的关键字查询通常需要在多个文本字段中查询，如“标题:出租或内容:出租”，需要召回标题或内容字段中包含出租的单据。为了优化这类常见查询的性能，使文本相关性的计算更加方便，ESearch支持倒域打包功能，即多个文本域中相同词条的文档自动合并到同一个过帐列表中，只需在模式中稍加配置即可启用。这样，就相当于预先计算了索引中每个项的多个字段的并集。此外，由于不同文本字段的权重不同，因此在对文本相关性进行评分时，有必要识别一个术语击中了哪些文本字段。因此，反向连接字段链中的每个文档id必须附有一个迷你位图，以标记它所命中的字段。

下图显示了将标题字段和内容字段合并为全文字段的示例:

3.4、正指数

正向索引是从文档id到文档属性值的映射。在58的搜索系统中，前向索引不仅存储必要的文档属性，还存储用于评分的文档特征。在检索过程中，还可以读取一些转发字段进行文档过滤。

ESearch的前向行索引采用列存储的设计，即不同前向行的数据分开存储。

根据58个文档的特点，ESearch提供了多种正排域的存储形式。58是一个分类信息网站，所有类别的信息都存储在同一个数据库中。不同的类别有不同的信息领域。比如房产信息包括楼层、户型等字段，二手交易信息包括品牌、型号等字段。这些区分出来的字段按照统一的格式合并存储在同一个数据库字段中，在建立索引时仍然会内置到各自的反向和正向字段中。但同时各种物品信息中又有很多通用字段，如标题、城市ID、类别ID等等。

这意味着某些字段的值分布是稀疏的。比如，在所有的信息中，包含“手机品牌”这一领域的信息可能远远占不到50%，而一些领域的价值分布比较紧张。例如，几乎100%的信息包含“类别标识”字段。

我们使用数组作为紧凑前向秩域的存储形式，哈希表作为稀疏前向秩域的存储形式，可以避免浪费空并保证O的平均搜索时间复杂度。

此外，我们直接使用位图作为布尔正域的存储形式。

列存储的一个缺陷是空之间缺乏局部性，这可能会影响CPU缓存命中率。比如给一个文档打分时，通常从前排索引中读取多个特征值进行计算，因此需要多次搜索和多次内存访问。为了解决这个问题，可以考虑使用联合前向秩字段，将几个需要同时访问的字段合并成一个前向秩字段。

第四，缓存和二次排序

为了减少检索服务的响应时间，需要缓存检索结果，但缓存也会导致文档字段和排序特征的更新无法立即生效，影响实时性。本节介绍了当电子搜索使用缓存时，如何确保召回结果和排序结果实时更新。

4.1.回忆结果

在实时索引中，如上所述，当文档更新时，它将被构建到新的小索引段中。如果旧的索引段也包含此文档，此文档将在旧的段中标记为删除。

电子搜索为每个段分配一个独立的缓存。每个片段从缓存中检索到检索结果后，会用删除表过滤掉被删除的文档，从而保证只有更新后的文档才能被检索到。

4.2.排序结果

为了便于评分和排序，我们将在索引中存储一些文档特征值。这些特征值不会被用作召回条件，因此它们只构建在正向索引中。这类文档属性的更新不能遵循上述生成新的段-段合并的更新过程，而是直接在前排索引中进行刷新，因此特征值刷新的性能远高于正常的文档更新，这使得我们可以实时调整排序结果。

为了使特征值的变化实时影响排序结果，我们将在从缓存中检索到检索结果后，对检索结果进行第二次评分和排序。因为缓存中的结果通常只包含数百个顶级文档，所以第二次排序花费的时间有限，并且不会影响整体性能。

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

复杂的排序策略通常很耗时。因此，在对海量数据进行排序时，业界通常采用“粗排序-细排序”的两阶段排序方法，在效果和性能之间做出合理的折中，即先对海量数据进行低成本的粗排序，再对TopN结果进行高成本的细排序，最后整个处理过程不会花费太多时间。

涉密信息的特点也适合这种模式。很多类别讲究时效性，时间顺序是主要的排序因素。在信息发布时间相近的前提下，需要根据信息质量、转化率等其他因素进行更精细的排序。第二次排序可以用来实现这样一个过程:第一次排序按时间顺序计算完整文档的TopN结果集并存储在缓存中，第二次排序使用复杂的机器学习模型对TopN结果进行分级和重排。

动词 （verb的缩写）总结

介绍了如何根据58的数据和搜索特点设计实时索引，以及如何在58搜索内核search中优化索引存储和查询流程。随着业务的不断发展，我们将在检索性能、资源利用、排序等方面不断优化，欢迎有兴趣的同学与我们交流。

作者简介

杨毅，58集团TEG搜索R&D部，后端架构师，专注于高度并发的搜索引擎技术。本文转载自58建筑师微信官方账号。