干货：广告引擎索引的设计与实现

1.背景

在线广告是互联网企业常见的商业变现模式。广告占企业收入份额比重很大，业务的重要性不言而喻。

广告召回速度会直接影响企业收入。从技术的角度看，广告引擎中的索引结构与设计实现方式，决定整个广告系统检索的性能水平。

如下图所示，广告索引位于广告系统的位置。

1.1业务领域需求

需要支持高性能检索；
索引占用内存不能太大，空间尽可能小；
索引更新需要支持的实时更新；
易于自主维护与开发，便于开发团队上手，首选JAVA语言；

1.2 索引

什么是索引？举个具体的例子，假如给你一首诗的标题，你就能马上背出其内容。

这个其实就是一个典型的键值查询场景。在数据系统中大多将ID作为键（Key），把内容作为值（Value）。这样我们就能在O(1)的时间复杂度完成对Key的检索，这样对象唯一ID为Key的索引结构，就是正排索引。

如果我们想查询指定词语出现在哪些诗中，一般来说我们需要遍历所有的数据。查询时间复杂度是O(n)，如果每首诗平均长度是k，那遍历整个诗词的检索时间代价是非常高的，时间复杂度大多是O(k * n)。

根据诗的内容词语查诗的题目我们可以尝试”反向“建立哈希表，这样我们就可以根据关键词查询这个哈希表，在O(1)的时间复杂度就能查到包含关键词的诗的题目。这种根据内容或者字段属性反过来索引主键Key的结构，就是倒排索引。

1.3 行业调研

目前开源索引大部分为通用搜索引擎，很难满足业务领域的系统需求，基于开源的搜索引擎通常需要大量的二次开发，而且性能并不一定能达到预期的水平。

Apache Lucene

是全文检索引擎工具包，不支持分布式索引；
在高并发查询（磁盘IO）与同时再更新索引，对性能会有影响的；

Sphinx

由C++语言开发，支持实时索引的全文检索引擎，二次开发上成本会非常高；
目前大多作为MySQL查询全文检索引擎来使用；

考虑到需要开发人员完全能自主掌控系统的开发与维护，且满足高性能的领域需求，自研是比较好的选择。

2.索引设计

2.1 业务模型

2.1.1 模型层次设计

广告主（Advertiser）：在这个实体下面可以创建推广计划与推广单元以及广告创意；
推广计划（Campaign）：这个实体属于广告主实体，用于将推广的广告统一管理；
推广单元（Slice）：这个实体用于广告具体投放规则，关联到某一广告创意；
广告创意（Creative）：用户具体看到的广告内容；

广告索引建立、广告的检索、排序都是基于推广单元粒度，其中对广告建立倒排索引也是基于推广单元来进行的。

2.1.2 模型逻辑结构

通过用户与媒体属性与广告倒排索引进行匹配。
得到Top N的索引数据主表的ID。
通过数据主表ID可以关联获取到其他数据辅表数据。

2.2 索引结构

2.2.1 字典搜索树（Trie）

Trie树，也叫做”字典树“或者”前缀树”。它是一个树形结构，它与二分搜索树（Binary Search Tree）、红黑树（Red Black Tree）不同，Trie树是一种多叉树，即每个节点可以有m个子节点。它是一种专门处理字符串的数据结构，用来解决一组字符串中快速查找的问题。

字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但利用字符串的共同前缀（Common Prefix）作为存储依据，以此来节省存储空间并加速搜索时间。其在搜索字符串表现出高效，特别适用于文本搜索和词频统计等。

2.2.1.1 Trie树的性质

根节点不包含字符，除根节点外每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。

2.2.1.2 复杂度分析

一个线性表的顺序查找的时间复杂度为O(n)，二分搜索树的查找的时间复杂度为O(log n)，它们时间复杂度都与数据结构中的元素个数相关。字典树查询的时间复杂度与元素多少无关，只与查询的单词长度有关。

时间复杂度：

假设要查询的字符串长度为 k，查询的查询的时间复杂度为：O(k)。
假设所有字符串长度之和为 n，构建字典树的时间复杂度为 O(n)。

有的人可能会问题，为什么不选择HashMap，HashMap的时间复杂度是O(1)不是更快吗？

哈希表的搜索取决于hash函数的好坏以及数据的离散分布，频繁的出现hash冲突效率不一定比Trie树高。
由于广告定向条件是有多重情况组合而成，使用哈希表至少需要较Trie树10倍的内存空间。

空间复杂度：

字典树每一个节点都需要用一个数组来存储子节点的指针，即便实际只有两三个子节点，但依然需要完整大小的数组。所以字典树比较消耗内存，空间复杂度较高。

2.2.1.3 Trie的优缺点

优点：

插入和查询效率都非常高效，假如插入和查询的字符串的长度都为 k，时间复杂度都为O(k)。
相同前缀的字符串相对哈希表能有不错压缩表现。
不需要求hash值，对短字符串有更快的速度。

缺点：

字符集不能过大，否则存储空间会过于浪费。
在字符串前缀重合较多的情况，才能有较好的表现。
没有现成的字典树代码库可以用，需要手动编写。

2.2.2 有限状态转化（FST）

Finite State Transducers简称FST，有限状态转化传感器。FST的功能类似于字典，Lucene4.0在查找Term时使用了FST算法，来快速定位Term的位置。lucene-fst.png

Lucene采用FST的结构来构建词典，这个结构保证了时间和空间复杂度的均衡，是Lucene的核心功能之一。

2.2.2.1 FST

结构如图，我们知道把一堆字符串放在一堆，把它们共同的前缀进行压缩就会变成Brust-Trie。如果把后缀变成一个个的节点，那么它就是Trie结构。如果将后缀也进行压缩的话，那边你就会发现它变成一张图结构。

那边FST是压缩字典树后缀的图结构，它拥有Trie高效搜索能力，同时还非常小，比Trie树结构占用更小。查询时间复杂度为：O(k)， k表示查询字符串长度。

2.3 索引数据存储

我们知道了倒排索引原理，以及对比了解了相对效率较高的索引数据结构，那么倒排索引上的数据Postings List如何存储？为了加快检索的速度，我们必须要设计占用的越少空间，索引数据存储采用的压缩算法也十分重要。

2.3.1 FOR算法

FOR算法（Frame Of Reference）的核心思想是用减法来削减数值大小，从而大多降低空间存储。在Apache Lucene，从4.1版本开始通过增量编码的方式进行压缩。

数据经过增量拆解、分块，然后根据最后分好组的组内最大值计算二进制最大所需位数。

数组元素值和与前一位的差值：V(n) = V(n) – V(n-1)， n=2,3,4…..。
计算数组最大值所需占用的大小。
计算数组是否需要拆分，计算拆分后每组的最大值所需占用的大小并记录。

缺点：

FOR算法的核心是用减法来缩减数值的大小，但在数值比较离散，或者数值很大时，FOR算法达到的效果是不明显的。比如 100W、200W、300W，相减依然很大。

2.3.2 RBM算法（RoaringBitmaps）

对于有序整数ID集合（比如通过定向条件查询到命中的广告ID），在Apache Lucene从5版本开始使用了Roaring BitMaps进行索引压缩。RBM算法核心是通过除法来缩减数值大小，但并不是直接相除的。

比如数组：1000,62101,131382,191173,196658，其中196658的二进制表示为：
0000 0000 0000 0011 0000 0000 0011 0010
然后将其高16位和低16位分布转换成10进制：
0000 0000 0000 0011 -> 3
0000 0000 0011 0010 -> 50

那么196658转换成了(3,50)的表示形式，其效果相对除以2^16，商3余50。因为商和余数都不超过16位，那么我们最大用16bit来存储足够了。也就是short类型因此商和余数都可以用一个short存储。

将源数组除以2^16得到：(0,1000),(0,62101),(2,313),(2,980),(2,60101),(3,50)

转化为二位数组：
0:1000,62101
2:313,980,60101
5:50

Roaring Bitmap将高位数值存储到一个有序数组中，这个有序数组中每一个值都是一个“桶”，对于低16位，Roaring Bitmap则将它存储在一个2^16的位图中，将其位置设置为1。这样每个桶都会对应一个2^16的位图。

如果我们要确认一个元素是否在Roaring Bitmap中存在，通过两次查询就能确认了。

第一步是以高16位在有序数组中二分查找，看对应桶是否存在。
如果存在，第二步是将桶中的位图取出，判断相应的位置是否为1。如果桶为数组时间复杂度是O(log n)，如果桶为位图，时间复杂度为O(1)。

如图所示，我们可以看出阈值是 8192btye / 2bytes = 4096 个文档，也就是说当文档数小于4096的时候，用Integer array比较合理，超出4096时选择BitMap存储性能更优。

3.系统设计

倒排索引设计

Field，存储定向条件关键字，通过顺序链接，单条广告的多个定向条件可以构建一条树的链路；
Term，存储定向条件关键字具体定向数值，若为链路点，则含有data字段；
Data Postings，包含该树形结构从根节点到当前节点的链路的数据；
Pointer，指向子节点的指针，若当前节点无任何指针指向，则当前节点为叶子节点；

4.性能测试

4.1测试方法

测试机器：MacBook Pro 2021 ，cpu Apple M1 Pro ，内存 16G。

通过10个定向维度进行测试，对以下内容进行基准测试：

索引建立时间
索引占用内存
单次检索耗时

4.2测试结果

4.2.1 索引建立时间（毫秒）

Lucene

Trie

广告数量	索引建立时间(Lucene)	索引建立时间(Trie)
1,000	1 ms	0.56 ms
10,000	14 ms	6 ms
100,000	147 ms	49 ms
1,000,000	3359 ms	853 ms

4.2.2 索引占用内存

广告数量	Lucene	Trie
1,000	0.053 MB	1.1 MB
10,000	0.36 MB	4.8 MB
100,000	3.5 MB	15.9 MB
1,000,000	36 MB	104.5 MB

4.2.3 单次检索耗时（微秒）

广告数量	单次检索(Lucene)	Trie
1,000	6.823 μs	0.194 μs
10,000	1.757 μs	0.199 μs
100,000	67.73 μs	0.198 μs
1,000,000	3789.99 μs	0.203 μs

4.3测试结论

Trie 检索的时间复杂度不随数据量变化，只与检索的Term 数量有关，检索性能优异。
随着数据量的增加，Trie 缺少一些数据压缩算法加持，内存占用相比Lucene没有很大的优势。
十万级数量广告使用简易的Trie 作为检索结构非常合适，在百万级别以上时需要考虑更优化的数据压缩算法，否则优先考虑Lucene。

5后续规划

本文对广告实时索引其背后的原理进行了分析，并对比自研索引与开源搜索引擎工具包进行对比及性能分析。

后续会一步一步开源自研的广告实时索引及广告引擎相关源码，共同学习。

另，转载请注明出处。

Github：https://github.com/j5land/adEngine，欢迎Star关注。

参考资料

美团广告实时索引的设计与实现：https://tech.meituan.com/2018/05/11/adp-rtidx-ls.html
Lucene ：https://lucene.apache.org/
Indexing Boolean Expressions ：http://theory.stanford.edu/~sergei/papers/vldb09-indexing.pdf
Indexing Boolean Expressions2：https://pdfs.semanticscholar.org/28d5/eae010074ea82a635e9c36d5a420dba949fa.pdf
基于布尔表达式的广告索引设计：https://zhuanlan.zhihu.com/p/59658727
FLA：https://cs.nyu.edu/~mohri/pub/fla.pdf
FST：http://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/