之家广告索引系统设计

在处理海量广告库中的数据时，广告index索引系统需要快速筛选出几个或几十个符合条件的广告，以满足实时性要求。本文将对车智投index索引系统的设计进行简要介绍，以帮助大家更好地了解广告索引召回的处理过程。

广告客户通常会创建多个广告计划，每个计划对应一个较长周期的KPI，例如预算和投放地域。每个广告计划包含多个广告组，用于实现更精细的投放控制，并设置不同的定向条件。广告素材是广告曝光所展示的文字、图片或视频等，一般由广告客户提供，可以属于不同的广告组。广告检索、排序等都是基于广告组粒度进行的，而广告的倒排索引也是基于广告组层级建立。

index索引系统是广告投放引擎的子系统，为广告投放提供定向检索服务。它从众多的投放计划中快速筛选出符合当前页面浏览量（PV）的计划组，并提供实时化的索引更新功能。在广告系统中，大部分字段需要支持实时更新，例如计划/广告组状态和预算上下线状态等。举个例子，当一个广告组由可投放状态变为暂停状态时，如果该变更没有及时在索引中生效，就会导致大量无效的广告被投放出来。

系统采用多线程模型，主要包括主线程、Kafka线程、MySQL线程和Dump线程。

主线程负责接收广告服务器的请求并进行处理，并回应服务请求；

Kafka线程负责处理投放计划的实时更新消息，确保索引数据及时更新；

MySQL线程负责从MySQL中读取最新的全量投放计划数据，以保持索引的准确性和完整性。

Dump线程定期将内存中的索引数据导出到文件中，以便在需要时进行恢复和备份。

了解Index索引系统的基本架构后，下面将介绍底层索引结构的组成，包括索引的创建、更新和查找等操作的实现原理。

索引逻辑结构总体包含4部分，以下为结构的详细介绍。

1、广告组到docid映射

每个广告组都会被分配一个数值型的docid，并且生成规则采用自增量的方式。例如，如果有100个广告组，则它们的docid分别为0、1、2、…、97、98、99。系统中的索引操作，包括新建、更新和查找等，都是基于这些docid来进行的。为了存储广告组的docid和其对应的索引关系，系统使用了hash表作为内存结构。这样可以快速地进行索引映射和查找操作。

2、正排表

正排表是一种数组结构，用于存储广告数据并支持主键到文档的随机访问。它按照顺序依次存储每个docid对应的详细广告数据，包括广告组id、广告客户id、计划id、预算、计费方式、用途、投放方式、优先级、广告类型、订单类型和广告素材等信息。在检索过程中，先根据广告组id从映射表中取得对应的docid后，再通过该docid从正排表数组中获取详细的广告数据，正排表采用数组结构进行内存存储，使得可以快速地根据主键进行随机访问。

3、倒排hash表

倒排表用于存储索引及索引对应的广告状态数据，它由hash表和bitmap位图组成。

hash表：提供了快速的插入和查找操作，可以将存储和查找索引数据的时间消耗大大降低，并且几乎可以看作是常数时间。hash表采用数组加链表的实现方式，通过哈希函数将索引映射到对应的位置，以实现快速的索引存储和检索。

bitmap位图：将广告文档ID（docid）映射到位图中的相应位置，使用一个bit位（0或1）来表示广告是否存在。在拥有数以万级广告数据的情况下，使用位图标识广告状态非常节省存储空间。同时，利用位运算（如AND、OR、XOR、NOT）可以高效处理多个位图数据，例如查找同时满足多个定向条件的广告组数据，只需对对应的位图进行AND运算即可。

CHstr类通过传入的最大哈希值、哈希函数和比较函数来初始化，并提供了添加、删除、匹配和遍历等功能。其中，m_tables是一个指向哈希表的指针，用于存储倒排索引的数据。

在车智投广告系统的业务上，倒排索引大致可以分为以下几类：

广告位属性：包括广告位ID、轮播数、广告位尺寸（宽度*高度）、广告位素材类型和计费类型等属性。

页面属性：包括页面所在省份、城市、品牌、车系和级别等属性。

人群属性：包括用户所在省份、城市、投放时段、偏好品牌、偏好车系和偏好级别等属性。

移动属性：包括设备平台属性，用于区分不同的移动设备平台。

搜索属性：包括关键词，用于匹配用户搜索的关键词与广告内容的相关性。

状态属性：包括业务状态和计费状态。业务状态表示产品或运营通过业务系统变更计划或广告组的状态；计费状态是后端引擎根据计划到量情况判断的上下线状态。

4、docid状态位图

docid状态位图用于标识每个docid的有效性，其中0表示无效，1表示有效。通过位图的方式，可以快速判断一个docid是否存在，从而避免对无效的广告进行不必要的处理。这种状态位图的设计在索引系统中起到了关键作用，能够提高广告投放的效率和准确性。通过位运算等高效操作，可以方便地对多个位图数据进行处理，例如查找同时满足多个条件的广告组数据。

add：将新的文档添加到正排表和倒排索引中

update：修改已存在的文档内容，涉及正排表和倒排索引的变更

search：根据查询列表查询符合条件的文档集合并返回结果

假设有一个广告组T，投放地域：北京、上海，关键词：宝马，投放设备：移动端，计划id：2305，CPC计费，单次点击价格2元，预算1万，底层的索引结构构建过程步骤如下：

1、建立docid映射关系：将广告组T分配给docid=3

索引词的存储使用了hash分桶方式，根据索引词的哈希值确定其所属的存储桶，并在该存储桶中保存对应的索引项。这样一来，在查询某个索引词时，可以直接定位到对应的存储桶，而无需遍历整个索引结构，从而提高查询效率和速度。同时，使用hash分桶还可以平衡索引的负载，使得不同的索引词均匀地分布在各个存储桶中，提高整体性能和扩展性。

索引词hash生成规则如下：

hash的基本原理是将任意长度的输入通过hash算法转换成固定长度的输出，也称为哈希值。由于哈希值的长度是有限的，而输入数据的长度是无限的，因此必然会存在不同的输入数据经过哈希算法后得到相同的哈希值，这就是所谓的哈希冲突。当遇到哈希冲突时，常用的解决方法是采用链地址法（Chaining）。链地址法使用一个链表数组来存储相应的数据，当发生冲突时，将冲突的数据添加到对应位置的链表中。

链地址在处理的流程如下：

添加一个元素的时候，首先计算元素key的hash值，确定插入数组中的位置。如果当前位置下没有重复数据，则直接添加到当前位置。当遇到冲突的时候，添加到同一个hash值的元素后面，行成一个链表。这个链表的特点是同一个链表上的Hash值相同。

在索引构建时，若索引词hash值冲突，需要追加到链表后面：

这样的实时更新操作能够确保索引与业务数据的一致性，同时提供了灵活性和准确性。通过禁用旧索引的方式，可以避免脏数据的影响，而重新遍历新的索引词并设置对应的bitmap，则保证了新的索引能够正确地映射到相应的存储位置。最后，开启状态bitmap的操作则使得广告组的新索引生效，确保了查询结果的准确性。

部分代码实现如下：

假设一个北京的用户在之家app搜索宝马，index检索的过程如下：

1、确定待检索的定向条件：

地域#北京、地域#不限

设备#移动、设备#不限

词#宝马

2、根据定向条件进行倒排检索：