on
由浅入深的聊聊广告检索
互联网广告与传统媒体广告，一个最大的差别就是，互联网广告支持精准投放。广告主在媒体方投放广告时，可以指定，这条广告的目标人群。 当媒体方的流量符合该目标人群时，才能够展示该广告。 在广告引擎召回广告的过程中，第一步就是广告检索：根据当前的流量条件，在广告库中检索出所有符合的广告，然后再对这些广告进行CTR、CVR预测以及控量等一系列操作。 所以广告检索是广告引擎的基础。
假设广告引擎支持的定向条件有以下4种：
- geo：地理位置定向，如：中国、印度、北京市、河北省
- sex：性别，男、女
- age：年龄，如：20，35
- APPlist：设备的APP列表，如：微信、支付宝
广告库中有5条广告，每条的定向条件分别是：
[geo(北京||上海) && age(20) && APPlist(微信)] || [geo(印度) && age(25) && sex(男)]这条广告的目标人群是：北京或上海的20岁的装了微信的人群，或者印度的25岁男性。这里，我们给定几个术语，这两组定向条件，我们称之为dnf； 单个的一组条件，我们称之为conjunction；单个维度的条件，我们称之为predicate；单个维度条件的单个值，我们称之为value。[geo(北京||上海) && age(20) && APPlist(微信)][geo(北京||上海) && APPlist(!微信)]这里注意，微信前有个!号，这表示取反，即定向人群是北京或上海的没有装微信的人群。[geo(中国) && APPlist(!微信)][geo(印度) && age(25)&&sex(男)]
广告检索具体如何实现呢？
方案一 逐条匹配
最简单的办法就是逐条匹配：遍历每一条广告，将每个广告的dnf依次与当前流量进行匹配，如果完全满足广告设定的某一个conjunction，则可以召回该广告。 这种方案非常简单，但缺点也很明显：效率低下，当广告库中的广告非常多时（比如电商广告的千万级别数据场景），那么这种全表遍历的方式就不可取了。
方案二 倒排索引
上面我们介绍了，每个广告都可以设置一个dnf，一个dnf包含多个conjunction，当前流量只要符合任意一个conjunction，即可召回该广告。
在实际生产环境下，有大量广告，他们的conjunction其实是相同的，举个例子，有一万条口红广告这样的广告，但是它们的设置的定向条件都是20-30岁的女性。
即：count(distinct conjunction) << count(ad)。所以在这可以引入倒排索引，key存储conjunction id，value存储广告id列表。
我们根据上面的5条广告，来实际的构建下这个倒排索引：
conjunction列表:
conjunction 1: [geo(北京||上海)&&age(20)&&APPlist(微信)]
conjunction 2: [geo(印度)&&age(25)&&sex(男)]
conjunction 3: [geo(北京||上海)&&APPlist(!微信)]
conjunction 4: [geo(中国)&&APPlist(!微信)]
倒排索引1:
conjunction 1 -> [ad 1, ad 2]
conjunction 2 -> [ad 1, ad 5]
conjunction 3 -> [ad 3]
conjunction 4 -> [ad 4]
这样我们只需要遍历conjunction列表，而不需要遍历所有的广告，即可检索出所有符合条件的广告了。
方案三 两层倒排索引
我们继续对方案二进行优化。方案二中，我们仍需要遍历所有的conjunction，然后使用当前流量的条件依次和conjunction中的每个条件进行比较。 这个匹配仍旧是可以优化的，在这里，可以再引入一层倒排索引，key是value id，value是conjunction id。下面实际构建下这个倒排索引：
conjunction列表，hit_count表示该conjunction的predicate的个数:
conjunction 1: [geo(北京||上海)&&age(20)&&APPlist(微信)], hit_count=3
conjunction 2: [geo(印度)&&age(25)&&sex(男)], hit_count=3
conjunction 3: [geo(北京||上海)&&APPlist(!微信)], hit_count=1 //取反条件hit_count不+1
conjunction 4: [geo(中国)&&APPlist(!微信)], hit_count=1
value列表:
value 1: geo(北京)
value 2: geo(上海)
value 3: geo(印度)
value 4: age(20)
value 5: age(25)
value 6: geo(中国)
value 7: APPlist(微信)
value 8: sex(男)
倒排索引2:
value 1 -> [conjunction 1, conjunction 3]
value 2 -> [conjunction 1, conjunction 3]
value 3 -> [conjunction 2]
value 4 -> [conjunction 1]
value 5 -> [conjunction 2]
value 6 -> [conjunction 4]
value 7 -> [conjunction 1, !conjunction 3] //这里conjunction 3前面有个!，表示当前流量符合value 7时，不能召回conjunction 3
value 8 -> [conjunction 2]
假设当前流量为：geo(北京) && age(20) && APPlist(微信) && sex(男)，那么检索过程如下：
1. 遍历value列表，与当前流量相匹配，找到符合当前流量的每个value对应的conjunction：
a. value 1 -> [conjunction 1, conjunction 3]
b. value 4 -> [conjunction 1]
c. value 7 -> [conjunction 1, !conjunction 3]
d. value 8 -> [conjunction 2]
2. 每命中一次conjunction i，就给conjunction i的hit_count + 1，计算所有conjunction的hit_count数：
a. conjunction 1 hit_count=3
b. conjunction 2 hit_count=1
c. conjunction 3 应该删除
3. 过滤掉步骤2中计算得到hit_count与conjunction列表中hit_count不相等的conjunction，此时只剩下conjunction 1
4. 使用倒排索引1，通过conjunction 1找到ad 1和ad 2，完成检索
方案四 区间树 + 两层倒排索引
方案三中，我们已经将匹配的粒度降到最小了，即value级别，但value列表可能会很大，比如单单APPlist这个条件，理论上就可能有几十甚至上百万个。 所以我们仍需要对方案三进行优化，优化点就在于，如何不用遍历value列表，就能拿到符合当前流量的所有value。有人可能会说，倒排索引2中的key， 不要存储value id，直接存储value的值，这样我们直接通过当前流量中的值可以就使用倒排索引2查到conjunction了。这种方式实际上是不行的， 对于一些范围查询，比如地理信息、年龄，就无法使用这种匹配方式。
我们可以考虑，将value由二维信息（条件类型 + 条件值），转化成一维信息（targeting id），具体转化过程如下：
给四种定向条件划分不相交的targeting id范围：
1. geo: [1000000, 2000000]
2. sex: [1, 9]
3. age: [1000, 2000]
4. APPlist: [10000000, 20000000]
将所有value映射到targeting id范围上，同一维度的value有可能相交
value 1: geo(北京) -> [1011001, 1012000] 要在geo(中国)范围之内
value 2: geo(上海) -> [1012001, 1013000] 要在geo(中国)范围之内
value 3: geo(印度) -> [1020001, 1030000] 要在geo范围之内
value 4: age(20) -> [1020, 1020] 要在age范围之内
value 5: age(25) -> [1025, 1025] 要在age范围之内
value 6: geo(中国) -> [1010001, 1020000] 要在geo范围之内
value 7: APPlist(微信) -> [10000001, 10000001] 要在APPlist范围之内
value 8: sex(男) -> [1, 1] 要在sex范围之内
当我们把二维的value转化成一维的targeting id后，匹配value的问题就抽象为：
给定若干个可能有重叠的区间，再给定一组点，找出这些点落在哪些区间里。我们可以使用区间树解这个问题。
区间树是一颗高度平衡二叉树，每个节点都是一个区间。
节点除了记录区间的左右边界外，还要记录以当前节点为根节点的子树的所有节点右区间的最大值。
使用区间树进行查询，时间复杂度为：m*log(n)，m为解的个数，n为区间的个数。下面给出构建好的区间树：
([1010001, 1020000] max:10000001)
/ \
([1020, 1020] max:1025) ([1020001, 1030000] max:10000001)
/ \ / \
([1, 1] max:1) ([1025, 1025] max:1025) ([1011001, 1012000] max:1030000) ([10000001, 10000001] max:10000001)
\
([1012001, 1013000] max:1030000)
假设当前流量为：geo(北京) && age(20) && APPlist(支付宝) && sex(男)，那么检索过程如下：
1. 将流量的值转换成targeting id范围，并只取左边界当做targeting id即可
a. geo(北京) -> [1011001, 1012000] -> 1011001
b. age(20) -> [1020, 1020] -> 1020
c. APPlist(支付宝) -> [10000002, 10000002] -> 10000002 //这里假设支付宝的范围是[10000002, 10000002]
d. sex(男) -> [1, 1] -> 1
2. 上面四个targeting id，通过区间树，查询到符合的value
a. 1011001 ->geo(中国), geo(北京)
b. 1020 -> age(20)
c. 10000002 -> null
d. 1 -> sex(男)
3. 通过倒排索引2，拿到所有的conjunction，并计算hit_count
a. conjunction 1 hit_count=1
b. conjunction 2 hit_count=1
c. conjunction 4 hit_count=1
d. conjunction 3 hit_count=1
4. 过滤掉hit_count不符的conjunction，只剩下：conjunction 4
5. 通过倒排索引1，拿到符合的ad 4，检索完成
关于区间树，可以阅读这篇文章：《区间树》
总结
我们上面分别介绍了四种广告检索的方案，从最简单的逐条遍历开始，一步一步的优化，直到最后的方案四：区间树 + 两层倒排索引。
下面我们再逐一的分析下，四种方案的时间复杂度，这里认为一条流量的流量标签是常数级别：
- 方案一：遍历了所有广告、每个广告的所有conjunction、每个conjunction的所有predicate、每个predicate的所有value，不过每个广告的定向条件数都是有限的， 所以这里可以认为conjunction、predicate、value的数量是常数，所以时间复杂度是：N，N是广告数量。
- 方案二：遍历了所有不相同的conjunction、每个conjunction的所有predicate、每个predicate的所有value，所以时间复杂度是：N，N是不相同的conjunction的数量。
- 方案三：遍历了所有不相同的value，然后又遍历了命中的conjunction，后者可以认为是常数，所以时间复杂度是：N，N是不相同的value数量。
- 方案四：通过区间树查找了命中的value，然后又遍历了命中的conjunction，后者认为是常数，所以时间复杂度是：k*log(N)，k是命中的value数量，N是不相同的value数量。
那么关于广告检索的讨论，到这里就告一段落了。