要点

• 广告索引系统介绍。
• 广告索引系统的关键技术点。

概述

广告业务是互联网企业最重要的变现方式，计算广告系统也就是大多数互联网企业的标配。索引系统是计算广告系统中较为重要的部分，它的主要功能是，从海量的广告候选集中筛选一批广告进行投放。

索引系统在计算广告系统中的位置如下图所示：

计算广告系统

本文将对索引系统的整体架构及各模块的关键技术实现进行介绍。

索引系统架构

索引系统的主要功能是：索引构建和广告请求处理两大部分。具体的流程结构如下图：

索引系统结构

索引构建：索引系统收到业务平台推送的广告信息后，在系统中存储广告信息，并创建广告索引。

广告请求处理：索引系统接收到广告请求后，依次经历：初始化请求、检索广告、生成候选、策略模块，最后将候选结果返回给业务逻辑层。

索引系统中，广告的存储结构由广告信息表(正排表)和广告索引两部分构成。广告信息表是以广告id为关键字进行存储，广告索引则是根据规则建立的。将广告信息表和索引分开存储的好处是：

• 能避免广告信息的冗余：对索引而言，它仅需要小部分的广告信息，保存全量广告信息并无必要。
• 方便广告信息维护：广告信息与业务规则密切相关，随时有可能增加/删除字段，属于易“变”部分。而索引规则相对固定，属于“不变”部分。将“变”与“不变”部分进行隔离，对系统的维护比较友好。比如，广告信息中增加或删除一个字段，只需要对广告基本信息的结构进行修改即可，不需要每个索引都变动。

索引构建

索引的构建有实时和离线两部分，其中实时部分是指，在业务平台创建广告后，将其实时地推送到索引系统中进行投放。离线部分是指，当索引系统重启时，需要将在投的广告加载到系统中。

实时推送的实现方式，一般是使用消息队列来实现。由业务平台将广告写入消息队列中，索引系统则从消息队列中实时消费，并更新广告信息表和索引模块。

离线消息实现方式：

• 记录全量的广告信息变更日志，当系统重启时，重做全量日志。这种方式的问题是，当日志量较大时，重做全量日志的时间较长，因此，不太适合用在日志量较大的场景中。
• 定时dump内存+实时消息日志，定时从索引系统中，将在线的广告信息dump到磁盘，同时记录下当前消费到的日志序号。当系统重启时，先从最近的dump文件中恢复，然后，从dump时记录的日志序号开始重做。该方式避免了重放时间较长的问题，但是，若系统中在投广告量较大时，定时从内存中dump广告信息，可能会影响索引系统的整体性能。

在线广告数量较多，单机内存无法存储全量广告时，解决方案：

• 分库：即每一台机器，只存储一部分地广告，为了提高可用性，可以将线上机器分组，每组机器分别存储不同的广告。分库的规则可以是按广告的id进行hash后拆分，也可以是按照业务规则进行拆分。
• 按优先级加载广告：一段时间内，只投放部分广告。比如，在广告创建时，根据广告的投放时长、素材内容、历史投放情况等，建立一个广告投放优先级。索引系统根据优先级高低，按顺序投放，没有达到投放级别的广告，暂时不加载到内存。

广告信息更新，可能会影响性能，解决方案：

广告的上下线、查询和更新操作，会对广告信息表频繁访问，并且这是一个多线程处理过程。因此，广告信息表需要使用“锁”来保护。考虑到对广告信息表的访问，是一个读多写少的场景。所以，通常会使用“读写锁”来实现。但是，当广告规模较大时，加锁粒度较大，一次更新操作，会阻塞住大量的读请求，对系统资源不友好。变通的解决办法有：

1、广告信息表在内存中按id拆分，分成N个小组，每个小组创建一个锁。对其中一个组的写操作，不会阻塞其他组的读写，从而，达到降低锁粒度的目的。

2、采用双buffer的形式，内存中维护两份广告信息表，一份用于只读，一份用于只写。当写操作完成后，原来的只写用于只读，原来的只读变为只写。这种方式，可以最大限度地避免锁的竞争。但是，如果广告信息更新比较频繁时，会频繁地进行读写切换，对系统性能也有一定的消耗。

初始化请求

该阶段主要是为检索广告，初始化一些资源，并准备好相关参数。

在广告规模较大，算力紧张的情况下，该阶段也可以做一些算力分配的工作。通过计算流量的价值，决定召回队列的长度。对于高价值的流量，可以召回更多地广告候选，以利于Rank排序时更充分地竞争。也可以根据流量价值的高低，来决定是否调用大算力召回通路。同时，在流量尖峰时，也可以起到一定的降级作用。

算力分配具体操作可参考论文：DCAF: A Dynamic Computation Allocation Framework for Online Serving System。

检索广告

该阶段是索引系统的核心功能，也称为召回阶段，它负责从大量的广告候选中，挑选出满足定向要求的广告。

1、常用的定向召回实现方式：

• 兴趣定向：按照兴趣定向投放。构建索引的方式：位图、倒排等。
• 地域定向：基于地理位置定向投放，如指定省、城市、商圈、附近的人等进行投放。构建索引的方式：位图、GeoHash、kd-tree等。
• 关键词定向：在某些场景下进行投放，如投放给搜索了某些关键词的人。构建索引的方式：倒排等。
• 投放时间段：在指定时段内进行投放。构建索引的方式：倒排、线段树等。
• 基于营销目标投放：广告主指定营销目标，广告系统该目标的优化进行建模，筛选出合适的流量进行投放。这里的建模与精排阶段不同的是，这里的模型精度要求不高，起到粗筛作用即可，但是对计算时延要求较高，在线计算时长一般会要求在几十毫秒以内。较常用的召回模型有：DSSM、lookalike、深度树模型等。

2、在检索广告时，由于存在多个召回方式，因此，在发起召回调用时，一般会设计成并行请求多个召回通路。并行请求的实现方式：

• 异步：当召回模块设计为独立的rpc服务时，偏于IO型，采用异步调用，能效地提高cpu的利用率。
• 并行：当召回模块在同一个服务内执行时，偏于计算型，可以采用多线程并行执行的方式实现。

无论是异步还是并行，为了充分利用CPU，工作线程数的设定可以参考公式：

其中，N为CPU核数，x为单线程执行时本地计算时长，y为单线程执行时等待时长。

生成候选

该阶段，主要是根据上一阶段检索出来的候选id，进行去重，然后查询正排表，生成候选集。

策略模块

这一阶段主要是对广告候选集，执行一些业务策略，优化用户体验，提高投放效率。常见的策略：

频次、负反馈

频次和负反馈主要是用于优化用户体验。众所周知，广告系统要在平台收入、用户体验和广告主收益三者之间找到平衡点。因此，每个广告系统都会针对用户体验做一些业务策略。比如：一段时间内，不给同一个人曝光同一个广告等。

平滑

对于品牌广告来说，平滑的作用是，曝光给更大范围的受众，同时尽可能地保证投放效果。对于效果广告来说，平滑的作用是，更好地完成广告的投放效果，如CPC不高于某个值。

平滑控制的方式主要有：

• 调整参竞率：根据流量分布，通过控制参竞率，达到平滑效果。其特点是，模型简单，但无投放效果上的优化。
• 调整出价：根据流量情况，动态地调整出价，通过控制预算的消耗，将预算花在更有可能产生效果的流量上，从而，达到效果优化的目的。

进行平滑控制时，需要考虑的问题：

• 控制参数更新频率

参数的更新频率决定了平滑控制的灵敏度。

• 预测每个广告的流量分布

该问题的难点是：广告系统中定向类型有很多，且每个广告的定向也有差异，因此，预测每个广告，在定向条件下的流量分布比较难。常见做法是，抽样一部分流量，统计其定向条件下的分布情况。

• 控制参数预估

控制参数预估是平滑的核心部分，由于效果数据较稀疏，且回传延时大，因此，给实时计算调整控制参数带来一定的困难。常用的有：

1、论文"Budget Pacing for Targeted Online Advertisements at LinkedIn"中的做法是，设置固定值0.1。

2、论文“Smart Pacing for Effective Online Ad Campaign Optimization”中的做法是，根据广告效果将请求分层，每层的参竞率不同，点击率越高的层，参竞率越高，点击率低的层，参竞率越低。也就是说，当流量过来之后，根据预测的效果指标(如点击率)，找到对应层的参竞率。

• 慢启动问题

慢启动时，投放门槛设定得过低，则会很快投完，失去平滑的意义。设定得过高，则在慢启动阶段无法完成特征学习。因此，针对每个广告，都需要有一个合理的慢启动参数。

• 平滑控制失效

为了最大限度地避免投不完或者超投情况，可以将一天预算只按22个小时分配，剩余2个小时，用于平滑控制自我补救。

后记：本文主要围绕广告系统中索引服务及其周边系统进行了介绍，由于篇辐问题，将在后续文章中，分别从基本索引、区间索引、空间索引和向量索引等方面介绍具体地实现技术。