1.简介</br>
倒排索引在工程实践中也比较常见，特别是广告投放场景，在广告投放场景中，会经常说到某某广告只投指定流量，比如：限定国家、限定省份、限定性别之类的，而这些条件就实现了对请求流量的筛选。</br>
对于广告的指定投放，简单的处理方法就是遍历每个投放维度、逐个执行查找操作，比如：广告在国家和性别上设置了投放条件，当一条请求到来时，要先看国家维度上是否满足投放条件，如果满足则继续看性别维度，都满足则表示该广告可以投放，否则，不能投放要被过滤；在广告很多、投放维度较多的情况下，对每个广告按照投放维度逐个查找、判断哪些广告可以投放的方式是比较费时的，为了提高效率，下面就该倒排索引出场了。</br>
2.实现</br>
本部分就是针对广告的常见投放方式，建立倒排、实现广告的快速筛选。</br>
2.1术语</br>
在具体实现中，涉及的术语有：</br>
1）定向维度：为广告投放提供的定向字段、用于设置投放条件，比如，上面提到的国家、性别，就是定向维度；</br>
2）定向值：广告在定向维度上设置的投放条件，以定向维度"国家"为例，广告设置的定向值就是在哪些国家投、哪些国家不投；</br>
3）定向类型：根据定向实现方式不同，有不同的定向类型个，常见的有单值定向、多值定向、线段定向，后面会细谈；</br>
4）请求值类型：根据请求字段中取值分类，可以分为单值和多值，单值表示只能有一个取值，如：国家，请求中它取值唯一，而多值表示可以有多个取值，如：广告位支持尺寸，请求中它的取值可以是多个；</br>
5）黑、白名单：根据广告默认投放情况的配置决定，白名单的特点是默认不投，黑名单就是反之；</br>
基于上述概念，下面就是具体实现了，主要是针对广告定向中常见的三种场景讲解。</br>
2.2单值定向</br>
单值定向的特点是在请求上，定向维度的取值唯一，其倒排建立和定向的步骤是：</br>
1）解析广告文件，根据定向维度、定向值生成定向条件，每个定向值都有个位图对象；</br>
2）解析每个广告在每个定向条件上设置的投放条件，如果投则对应位设置为1，否则为0；</br>
3）根据请求中定向维度的取值，生成定向条件、查找位图，各定向条件的位图执行&操作后，位上取值为1的广告可以投放；</br>
除了上述处理，在对单值定向建立倒排时，还需要考虑默认情况处理，即存在两个回溯，下面举例说明，假设有两个广告，第一个广告要求只投中国，不投女性；另一个广告要求只投美国、不投男性，如：</br>
</br>
先说下正常情况，在country和sex两个定位维度上结合定向值得到两个定向条件，分别是country_CN和sex_F，对于广告1001，如果一个请求过来，传的country是CN、sex是F，则广告不投放；在看下要回溯的情况，如果请求传的country是CN、sex是M，而定向条件sex_M是没有的，那该怎么处理呢？根据上图配置可知，1001广告在sex为M的流量上设置的是不投放，因此，对于定向条件sex_M，要执行回溯情况，即看sex_*的情况，这里是针对请求定向的回溯，同样，在对广告建立倒排时，同样存在回溯处理，比如，1001广告没有在country_US上设置投放条件，根据默认配置可知其不投US，所以在country_US上的设置需要回溯到默认设置。</br>
总结来说，对于单值定向，除了根据定向设置建立倒排，还要考虑默认情况，请求定向时要考虑、建议倒排时也要考虑，综合上述分析，对于上图中的广告设置，其倒排索引的建立过程是：</br>
</br>
上图最后一部分显示了各广告在各定向条件上的设置，结合请求在举例说下定向过程，当请求的country是CN时，由此得到定向条件country_CN，根据上述结果、进而得知1001广告可以投放、1002广告不可以投放；当请求的country是IN时，由于定向条件country_IN不存在，故只能回溯查看定向条件country_*的情况，由上可知，1001和1002都过滤。</br>
2.2多值定向</br>
多值定向的特点是在请求上，定向维度的取值有多个，这是其与单值定向的最大区别，这也导致其倒排实现也略有差异——建立倒排时，多值定向取消针对默认情况的回溯处理，其处理思路是：对于一个定向维度，首先记录各广告在定向条件上的是否有设置，如果有设置则将位置为1；然后记录每个广告在定向维度上设置的黑白名单情况，如果广告在设置条件上有设置且设的是白名单，则表示广告投该条件，如果是黑名单，则就是不投该条件；由此可见，多值定向是根据黑白名单完成广告定向的，这与单值定向差异很大，为了方便理解，还是举例说下，如：有八个广告，在尺寸上的设置条件如下，当请求中广告位支持的尺寸是100x100和100x150时，对应的广告定向流程是：</br>
</br>
根据上图，举例说明下上面八个广告在"100x100和100x150"请求中广告的定向过程：</br>
1）解析广告配置，得到定向条件slotsize_100x100、slotsize_100x150，并为slotsize生成黑、白名单位图；</br>
2）设置位值，对于定向条件slotsize_100x100、slotsize_100x150，就看广告在该定向条件上是否有设置投放，如果有设置，不管是设置的0还是1，都将位设置为1；然后是为黑白名单设置位值，白名单就设置为1，黑名单就是0；</br>
3）根据请求尺寸得到本次定向条件是slotsize_100x100、slotsize_100x150，将slotsize_100x100、slotsize_100x150位图或在一起得到hitbit；</br>
4）最后通过黑白名单设置，执行 whitebit & hitbit | blackbit - hitbit，即最终满足投放条件的广告位图——bits_rst；</br>
2.3线段定向</br>
线段定向是针对区间定向而言，如：年龄段定向，IP段定向，线段定向是参考多值定向实现的，与多值定向的主要区别是，线段定向在建立倒排时，是单独处理实现的，没有专门生成定向条件、分配定向索引，这是因为线段定向中的每个定向条件也是个线段，所以将这块拎出单独处理，就建立倒排而言，线段定向的主要处理思路就是：</br>
1）遍历所有广告、记录每个广告上设置的定向线段；</br>
2）遍历的同时按照从小到大的顺序，记录每个广告上的设置的定向线段；</br>
3）当遍历到的线段与记录中线段存在交集，则执行拆分操作；</br>
举例说明下，线段定向的倒排索引的建立过程：</br>
</br>
完成倒排建立后，当请求过来时，后续定向过程就和多值定向一样了。</br>
3.代码</br>
针对上面谈到的三种定向，因为没想好动态位图在Go的实现方式，先用C++实现相关源码，git地址：</br>
https://github.com/JackBelief/inverted_module.git</br>
留两个问题，一个是能否以单值定向方式实现线段定向？二个是如何构建倒排集群，将倒排作为一个与业务无关的、独立集群存在？感兴趣的大佬，可以留言讨论！</br>
4.拓展</br>
在实现刀倒排前有个调研，想使用ES来做，不过由于项目引入改动较大，最终没有采用，有感兴趣的大佬可以尝试下、分享下；下面就举个简单样例，如何使用ES实现广告定向。</br>
假设有1001和1002两个广告，1001要求国家只投CN和US，性别只投M；1002要求国家只投JP和US，性别只投F，首先要将广告数据放入ES中，广告对定向维度设置的投与不投以黑白名单的形式存储，而请求定向就是对ES执行query查询操作，如：</br>
```json
PUT /adinfo/direct/1
{
"id":1001,
"sex_white":["M"],
"country_white":["CN", "US"]
}
PUT /adinfo/direct/2
{
"id":1002,
"sex_black":["F"],
"country_black":["US", "JP"]
}
POST /adinfo/direct/_search
{
"query":{
"bool":{
"should":[
{
"bool":{
"must":[
{
"term":{
"sex_white.keyword":{
"value":"M"
}
}
},
{
"term":{
"country_white.keyword":{
"value":"CN"
}
}
}
]
}
},
{
"bool":{
"must_not":[
{
"term":{
"sex_black.keyword":{
"value":"M"
}
}
},
{
"term":{
"country_black.keyword":{
"value":"CN"
}
}
}
]
}
}
]
}
}
}
```
有疑问加站长微信联系（非本文作者）
