美团广告实时索引的设计与实现

背景

在线广告是互联网行业常见的商业变现方式。从工程角度看，广告索引的结构和实现方式直接决定了整个系统的服务性能。本文以美团的搜索广告系统为蓝本，与读者一起探讨广告系统的工程奥秘。

领域问题

广告索引需具备以下基本特性：

1. 层次化的索引结构。

2. 实时化的索引更新。

层次投放模型

一般地，广告系统可抽象为如下投放模型，并实现检索、过滤等处理逻辑。

广告投放模型

该层次结构的上下层之间是一对多的关系。一个广告主通常创建若干个推广计划，每个计划对应一个较长周期的 KPI，比如一个月的预算和投放地域。一个推广计划中的多个推广单元分别用于更精细的投放控制，比如一次点击的最高出价、每日预算、定向条件等。广告创意是广告曝光使用的素材，根据业务特点，它可以从属于广告主或推广计划层级。

实时更新机制

层次结构可以更准确、更及时地反应广告主的投放控制需求。投放模型的每一层都会定义若干字段，用于实现各类投放控制。广告系统的大部分字段需要支持实时更新，比如审核状态、预算上下线状态等。例如，当一个推广单元由可投放状态变为暂停状态时，若该变更没有在索引中及时生效，就会造成大量的无效投放。

业界调研

目前，生产化的开源索引系统大部分为通用搜索引擎设计，基本无法同时满足上述条件。

• Apache Lucene

• 全文检索、支持动态脚本；实现为一个 Library。

• 支持实时索引，但不支持层次结构。

• Sphinx

• 全文检索；实现为一个完整的 Binary，二次开发难度大。

• 支持实时索引，但不支持层次结构。

因此，广告业界要么基于开源方案进行定制，要么从头开发自己的闭源系统。在经过再三考虑成本收益后，我们决定自行设计广告系统的索引系统。

索引设计

工程实践重点关注稳定性、扩展性、高性能等指标。

设计分解

设计阶段可分解为以下子需求。

实时索引

广告场景的更新流，涉及索引字段和各类属性的实时更新。特别是与上下线状态相关的属性字段，需要在若干毫秒内完成更新，对实时性有较高要求。

用于召回条件的索引字段，其更新可以滞后一些，如在几秒钟之内完成更新。采用分而治之的策略，可极大降低系统复杂度。

* 属性字段的更新：直接修改正排表的字段值，可以保证毫秒级完成。* 索引字段的更新：涉及更新流实时计算、倒排索引等的处理过程，只需保证秒级完成。

此外，通过定期切换全量索引并追加增量索引，由索引快照确保数据的正确性。

层次结构

投放模型的主要实体是广告主（Advertiser）、推广计划（Campaign）、广告组（Adgroup）、创意（Creative）等。其中：

* 广告主和推广计划：定义用于控制广告投放的各类状态字段。* 广告组：描述广告相关属性，例如竞价关键词、最高出价等。* 创意：与广告的呈现、点击等相关的字段，如标题、创意地址、点击地址等。

一般地，广告检索、排序等均基于广告组粒度，广告的倒排索引也是建立在广告组层面。借鉴关系数据库的概念，可以把广告组作为正排主表（即一个 Adgroup 是一个 doc），并对其建立倒排索引；把广告主、推广计划等作为辅表。主表与辅表之间通过外键关联。

广告检索流程

1. 通过查询条件，从倒排索引中查找相关 docID 列表。

2. 对每个 docID，可从主表获取相关字段信息。

3. 使用外键字段，分别获取对应辅表的字段信息。

检索流程中实现对各类字段值的同步过滤。

可靠高效

广告索引结构相对稳定且与具体业务场景耦合较弱，为避免 Java 虚拟机由于动态内存管理和垃圾回收机制带来的性能抖动，最终采用 C++11 作为开发语言。虽然 Java 可使用堆外内存，但是堆外堆内的数据拷贝对高并发访问仍是较大开销。项目严格遵循《Google C++ Style》，大幅降低了编程门槛。

在“读多写少”的业务场景，需要优先保证“读”的性能。检索是内存查找过程，属于计算密集型服务，为保证 CPU 的高并发，一般设计为无锁结构。可采用“一写多读”和延迟删除等技术，确保系统高效稳定运转。此外，巧妙利用数组结构，也进一步优化了读取性能。

灵活扩展

正排表、主辅表间的关系等是相对稳定的，而表内的字段类型需要支持扩展，比如用户自定义数据类型。甚至，倒排表类型也需要支持扩展，例如地理位置索引、关键词索引、携带负载信息的倒排索引等。通过继承接口，实现更多的定制化功能。

逻辑结构

广告检索流程

从功能角度，索引由 Table 和 Index 两部分组成。如上图所示，Index 实现由 Term 到主表 docID 的转换；Table 实现正排数据的存储，并通过 docID 实现主表与辅表的关联。

分层架构

索引库分为三层：

1. 接口层：以 API 方式对外提供索引的构建、更新、检索、过滤等功能。

2. 能力层：实现基于倒排表和正排表的索引功能，是系统的核心。

3. 存储层：索引数据的内存布局和到文件的持久化存储。

索引实现

本节将自底向上，从存储层开始，逐一描述各层的设计细节和挑战点。

存储层

存储层负责内存分配以及数据的持久化，可使用 mmap 实现到虚拟内存空间的映射，由操作系统实现内存与文件的同步。此外，mmap 也便于外部工具访问或校验数据的正确性。

将存储层抽象为分配器（Allocator）。针对不同的内存使用场景，如对内存连续性的要求、内存是否需要回收等，可定制实现不同的分配器。

内存分配器

以下均为基于 mmap 的各类分配器，这里的“内存”是指调用进程的虚拟地址空间。实际的代码逻辑还涉及复杂的 Metadata 管理，下文并未提及。

简单的分配策略

• LinearAllocator

• 分配连续地址空间的内存，即一整块大内存；当空间需要扩展时，会采用新的 mmap 文件映射，并延迟卸载旧的文件映射。

• 新映射会导致页表重新装载，大块内存映射会导致由物理内存装载带来的性能抖动。

• 一般用于空间需求相对固定的场景，如 HashMap 的 bucket 数组。

• SegmentAllocator

• 为解决 LinearAllocator 在扩展时的性能抖动问题，可将内存区分段存储，即每次扩展只涉及一段，保证性能稳定。* 分段导致内存空间不连续，但一般应用场景，如倒排索引的存储，很适合此法。

• 默认的段大小为 64MB。

集约的分配策略

频繁的增加、删除、修改等数据操作将导致大量的外部碎片。采用压缩操作，可以使占用的内存更紧凑，但带来的对象移动成本却很难在性能和复杂度之间找到平衡点。在工程实践中，借鉴 Linux 物理内存的分配策略，自主实现了更适于业务场景的多个分配器。

• PageAllocator

• 页的大小为 4KB，使用伙伴系统（Buddy System）的思想实现页的分配和回收。

• 页的分配基于 SegmentAllocator，即先分段再分页。

在此简要阐述伙伴分配器的处理过程，为有效管理空闲块，每一级 order 持有一个空闲块的 FreeList。设定最大级别 order=4，即从 order=0 开始，由低到高，每级 order 块内页数分别为 1、2、4、8、16 等。分配时先找满足条件的最小块；若找不到则在上一级查找更大的块，并将该块分为两个“伙伴”，其中一个分配使用，另一个置于低一级的 FreeList。

下图呈现了分配一个页大小的内存块前后的状态变化，分配前，分配器由 order=0 开始查找 FreeList，直到 order=4 才找到空闲块。

伙伴分配器策略

将该空闲块分为页数为 8 的 2 个伙伴，使用前一半，并将后一半挂载到 order=3 的 FreeList；逐级重复此过程，直到返回所需的内存块，并将页数为 1 的空闲块挂在到 order=0 的 FreeList。

当块释放时，会及时查看其伙伴是否空闲，并尽可能将两个空闲伙伴合并为更大的空闲块。这是分配过程的逆过程，不再赘述。

虽然 PageAllocator 有效地避免了外部碎片，却无法解决内部碎片的问题。为解决这类小对象的分配问题，实现了对象缓存分配器（SlabAllocator）。

• SlabAllocator

• 基于 PageAllocator 分配对象缓存，slab 大小以页为单位。

• 空闲对象按内存大小定义为多个 SlabManager，每个 SlabManager 持有一个 PartialFreeList，用于放置含有空闲对象的 slab。

对象的内存分配过程，即从对应的 PartialFreeList 获取含有空闲对象的 slab，并从该 slab 分配对象。反之，释放过程为分配的逆过程。

对象缓存分配器

综上，实时索引存储结合了 PageAllocator 和 SlabAllocator，有效地解决了内存管理的外部碎片和内部碎片问题，可确保系统高效稳定地长期运行。

能力层

能力层实现了正排表、倒排表等基础的存储能力，并支持索引能力的灵活扩展。

正向索引

也称为正排索引（Forward Index），即通过主键（Key）检索到文档（Doc）内容，以下简称正排表或 Table。不同于搜索引擎的正排表数据结构，Table 也可以单独用于 NoSQL 场景，类似于 Kyoto Cabinet 的哈希表。

Table 不仅提供按主键的增加、删除、修改、查询等操作，也配合倒排表实现检索、过滤、读取等功能。作为核心数据结构，Table 必须支持频繁的字段读取和各类型的正排过滤，需要高效和紧凑的实现。

正排存储结构

为支持按 docID 的随机访问，把 Table 设计为一个大数组结构（data 区）。每个 doc 是数组的一个元素且长度固定。变长字段存储在扩展区（ext 区），仅在 doc 中存储其在扩展区的偏移量和长度。与大部分搜索引擎的列存储不同，将 data 区按行存储，这样可针对业务场景，尽可能利用 CPU 与内存之间的缓存来提高访问效率。

此外，针对 NoSQL 场景，可通过 HashMap 实现主键到 docID 的映射（idx 文件），这样就可支持主键到文档的随机访问。由于倒排索引的 docID 列表可以直接访问正排表，因此倒排检索并不会使用该 idx。

反向索引

也称作倒排索引（Inverted Index），即通过关键词（Keyword）检索到文档内容。为支持复杂的业务场景，如遍历索引表时的算法粗排逻辑，在此抽象了索引器接口 Indexer。

索引器接口定义

具体的 Indexer 仅需实现各接口方法，并将该类型注册到 IndexerFactory，可通过工厂的 NewIndexer 方法获取 Indexer 实例，类图如下：

索引器接口类图

当前实现了三种常用的索引器：

• NoPayloadIndexer：最简单的倒排索引，倒排表为单纯的 docID 列表。

• DefaultPayloadIndexer：除 docID 外，倒排表还存储 keyword 在每个 doc 的负载信息。针对业务场景，可存储 POI 在每个 Node 粒度的静态质量分或最高出价。这样在访问正排表之前，就可完成一定的倒排优选过滤。

• GEOHashIndexer：即基于地理位置的 Hash 索引。

上述索引器的设计思路类似，仅阐述其共性的两个特征：

• 词典文件 term：存储关键词、签名哈希、posting 文件的偏移量和长度等。与 Lucene 采用的前缀压缩的树结构不同，在此实现为哈希表，虽然空间有所浪费，但可保证稳定的访问性能。

• 倒排表文件 posting：存储 docID 列表、Payload 等信息。检索操作是顺序扫描倒排列表，并在扫描过程中做一些基于 Payload 的过滤或倒排链间的布尔运算，如何充分利用高速缓存实现高性能的索引读取是设计和实现需要考虑的重要因素。在此基于 segmentAllocator 实现分段的内存分配，达到了效率和复杂度之间的微妙平衡。

倒排存储结构

出于业务考虑，没有采用 Lucene 的 Skip list 结构，因为广告场景的 doc 数量没有搜索引擎多，且通常为单个倒排列表的操作。此外，若后续 doc 数量增长过快且索引变更频繁，可考虑对倒排列表的元素构建 B+树结构，实现倒排元素的快速定位和修改。

接口层

接口层通过 API 与外界交互，并屏蔽内部的处理细节，其核心功能是提供检索和更新服务。

配置文件

配置文件用于描述整套索引的 Schema，包括 Metadata、Table、Index 的定义，格式和内容如下：

索引配置文件

可见，Index 是构建在 Table 中的，但不是必选项；Table 中各个字段的定义是 Schema 的核心。当 Schema 变化时，如增加字段、增加索引等，需要重新构建索引。篇幅有限，此处不展开定义的细节。

检索接口

检索由查找和过滤组成，前者产出查找到的 docID 集合，后者逐个对 doc 做各类基础过滤和业务过滤。

检索接口定义

• Search：返回正排过滤后的 ResultSet，内部组合了对 DoSearch 和 DoFilter 的调用。

• DoSearch：查询 doc，返回原始的 ResultSet，但并未对结果进行正排过滤。

• DoFilter：对 DoSearch 返回的 ResultSet 做正排过滤。

一般仅需调用 Search 就可实现全部功能；DoSearch 和 DoFilter 可用于实现更复杂的业务逻辑。

以下为检索的语法描述：

/{table}/{indexer|keyfield}?query=xxxxxx&filter=xxxxx

第一部分为路径，用于指定表和索引。第二部分为参数，多个参数由 &分隔，与 URI 参数格式一致，支持 query、filter、Payload_filter、index_filter 等。

由 query 参数定义对倒排索引的检索规则。目前仅支持单类型索引的检索，可通过 index_filter 实现组合索引的检索。可支持 AND、OR、NOT 等布尔运算，如下所示：

query=(A&B|C|D)!E

查询语法树基于 Bison 生成代码。针对业务场景常用的多个 term 求 docID 并集操作，通过修改 Bison 文法规则，消除了用于存储相邻两个 term 的 doc 合并结果的临时存储，直接将前一个 term 的 doc 并入当前结果集。该优化极大地减少了临时对象开销。

由 filter 参数定义各类正排表字段值过滤，多个键值对由“;”分割，支持单值字段的关系运算和多值字段的集合运算。

由 Payload_filter 参数定义 Payload 索引的过滤，目前仅支持单值字段的关系运算，多个键值对由“;”分割。

详细的过滤语法如下：

过滤语法格式

此外，由 index_filter 参数定义的索引过滤将直接操作倒排链。由于构造检索数据结构比正排过滤更复杂，此参数仅适用于召回的 docList 特别长但通过索引过滤的 docList 很短的场景。

结果集

结果集 ResultSet 的实现，参考了 java.sql.ResultSet 接口。通过 cursor 遍历结果集，采用 inline 函数频繁调用的开销。

实现为 C++模板类，主要接口定义如下：

结果集接口定义

• Next：移动 cursor 到下一个 doc，成功返回 true，否则返回 false。若已经是集合的最后一条记录，则返回 false。

• GetValue：读取单值字段的值，字段类型由泛型参数 T 指定。如果获取失败返回默认值 def_value。

• GetMultiValue：读取多值字段的值，返回指向值数组的指针，数组大小由 size 参数返回。读取失败返回 null，size 等于 0。

更新接口

更新包括对 doc 的增加、修改、删除等操作。参数类型 Document，表示一条 doc 记录，内容为待更新的 doc 的字段内容，key 为字段名，value 为对应的字段值。操作成功返回 0，失败返回非 0，可通过 GetErrorString 接口获取错误信息。

更新接口定义

• 增加接口 Add：将新的 doc 添加到 Table 和 Index 中。

• 修改接口 Update：修改已存在的 doc 内容，涉及 Table 和 Index 的变更。

• 删除接口 Delete：删除已存在的 doc，涉及从 Table 和 Index 删除数据。

更新服务对接实时更新流，实现真正的广告实时索引。

更新系统

除以上描述的索引实现机制，生产系统还需要打通在线投放引擎与商家端、预算控制、反作弊等的更新流。

挑战与目标

数据更新系统的主要工作是将原始多个维度的信息进行聚合、平铺、计算后，最终输出线上检索引擎需要的维度和内容。

业务场景导致上游触发可能极不规律。为避免更新流出现的抖动，必须对实时更新的吞吐量做优化，留出充足的性能余量来应对触发的尖峰。此外，更新系统涉及多对多的维度转换，保持计算、更新触发等逻辑的可维护性是系统面临的主要挑战。

吞吐设计

虽然更新系统需要大量的计算资源，但由于需要对几十种外部数据源进行查询，因此仍属于 IO 密集型应用。优化外部数据源访问机制，是吞吐量优化的主要目标。

在此，采取经典的批量化方法，即集群内部，对于可以批量查询的一类数据源，全部收拢到一类特定的 worker 上来处理。在短时间内，worker 聚合数据源并逐次返回给各个需要数据的数据流。处理一种数据源的 worker 可以有多个，根据同类型的查询汇集到同一个 worker 批量查询后返回。在这个划分后，就可以做一系列的逻辑优化来提升吞吐量。

分层抽象

除生成商家端的投放模型数据，更新系统还需处理针对各种业务场景的过滤，以及广告呈现的各类专属信息。业务变更可能涉及多个数据源的逻辑调整，只有简洁清晰的分成抽象，才能应对业务迭代的复杂度。

工程实践中，将外部数据源抽象为统一的 Schema，既做到了数据源对业务逻辑透明，也可借助编译器和类型系统来实现完整的校验，将更多问题提前到编译期解决。

将数据定义为表（Table）、记录（Record）、字段（Field）、值（Value）等抽象类型，并将其定义为 Scala Path Dependent Type，方便编译器对程序内部的逻辑进行校验。

可复用设计

多对多维度的计算场景中，每个字段的处理函数（DFP）应该尽可能地简单、可复用。例如，每个输出字段（DF）的 DFP 只描述需要的源数据字段（SF）和该字段计算逻辑，并不描述所需的 SF(1)到 SF(n)之间的查询或路由关系。

此外，DFP 也不与最终输出的层级绑定。层级绑定在定义输出消息包含的字段时完成，即定义消息的时候需要定义这个消息的主键在哪一个层级上，同时绑定一系列的 DFP 到消息上。

这样，DFP 只需单纯地描述字段内容的生成逻辑。如果业务场景需要将同一个 DF 平铺到不同层级，只要在该层级的输出消息上引用同一个 DFP 即可。

触发机制

更新系统需要接收数据源的状态变动，判断是否触发更新，并需要更新哪些索引字段、最终生成更新消息。

为实现数据源变动的自动触发机制，需要描述以下信息：

• 数据间的关联关系：实现描述关联关系的语法，即在描述外部数据源的同时就描述关联关系，后续字段查询时的路由将由框架处理。

• DFP 依赖的 SF 信息：仅对单子段处理的简单 DFP，可通过配置化方式，将依赖的 SF 固化在编译期；对多种数据源的复杂 DFP，可通过源码分析来获取该 DFP 依赖的 SF，无需用户维护依赖关系。

生产实践

早期的搜索广告是基于自然搜索的系统架构建的，随着业务的发展，需要根据广告特点进行系统改造。新的广告索引实现了纯粹的实时更新和层次化结构，已经在美团搜索广告上线。该架构也适用于各类非搜索的业务场景。

系统架构

作为整个系统的核心，基于实时索引构建的广告检索过滤服务（RS），承担了广告检索和各类业务过滤功能。日常的业务迭代，均可通过升级索引配置完成。

系统架构

此外，为提升系统的吞吐量，多个模块已实现服务端异步化。

性能优化

以下为监控系统的性能曲线，索引中的 doc 数量为百万级别，时延的单位是毫秒。

索引查询性能

后续规划

为便于实时索引与其他生产系统的结合，除进一步的性能优化和功能扩展外，我们还计划完成多项功能支持。

JNI

通过 JNI，将 Table 作为单独的 NoSQL，为 Java 提供本地缓存。如广告系统的实时预估模块，可使用 Table 存储模型使用的广告特征。

索引库 JNI

SQL

提供 SQL 语法，提供简单的 SQL 支持，进一步降低使用门槛。提供 JDBC，进一步简化 Java 的调用。

参考资料

• Apache Lucene http://lucene.apache.org/
  

• Sphinx http://sphinxsearch.com/
  

• “Understanding the Linux Virtual Memory Manager” https://www.kernel.org/doc/gorman/html/understand/
  

• Kyoto Cabinet http://fallabs.com/kyotocabinet/
  

• GNU Bison https://www.gnu.org/software/bison/
  

作者简介

• 仓魁：广告平台搜索广告引擎组架构师，主导实时广告索引系统的设计与实现。擅长 C++、Java 等多种编程语言，对异步化系统、后台服务调优等有深入研究。

• 晓晖：广告平台搜索广告引擎组核心开发，负责实时更新流的设计与实现。在广告平台率先尝试 Scala 语言，并将其用于大规模工程实践。

• 刘铮：广告平台搜索广告引擎组负责人，具有多年互联网后台开发经验，曾领导多次系统重构。

• 蔡平：广告平台搜索广告引擎组点评侧负责人，全面负责点评侧系统的架构和优化。