广告投放场景中倒排索引的构建与实现

tianqy · 2020-10-27 12:27:21 · 3388 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2020-10-27 12:27:21 的主题,其中的信息可能已经有所发展或是发生改变。

1.简介
    倒排索引在工程实践中也比较常见,特别是广告投放场景,在广告投放场景中,会经常说到某某广告只投指定流量,比如:限定国家、限定省份、限定性别之类的,而这些条件就实现了对请求流量的筛选。
    对于广告的指定投放,简单的处理方法就是遍历每个投放维度、逐个执行查找操作,比如:广告在国家和性别上设置了投放条件,当一条请求到来时,要先看国家维度上是否满足投放条件,如果满足则继续看性别维度,都满足则表示该广告可以投放,否则,不能投放要被过滤;在广告很多、投放维度较多的情况下,对每个广告按照投放维度逐个查找、判断哪些广告可以投放的方式是比较费时的,为了提高效率,下面就该倒排索引出场了。
2.实现
    本部分就是针对广告的常见投放方式,建立倒排、实现广告的快速筛选。
2.1术语
    在具体实现中,涉及的术语有:
     1)定向维度:为广告投放提供的定向字段、用于设置投放条件,比如,上面提到的国家、性别,就是定向维度;
    2)定向值:广告在定向维度上设置的投放条件,以定向维度"国家"为例,广告设置的定向值就是在哪些国家投、哪些国家不投;
    3)定向类型:根据定向实现方式不同,有不同的定向类型个,常见的有单值定向、多值定向、线段定向,后面会细谈;
    4)请求值类型:根据请求字段中取值分类,可以分为单值和多值,单值表示只能有一个取值,如:国家,请求中它取值唯一,而多值表示可以有多个取值,如:广告位支持尺寸,请求中它的取值可以是多个;
    5)黑、白名单:根据广告默认投放情况的配置决定,白名单的特点是默认不投,黑名单就是反之;
    基于上述概念,下面就是具体实现了,主要是针对广告定向中常见的三种场景讲解。
2.2单值定向
    单值定向的特点是在请求上,定向维度的取值唯一,其倒排建立和定向的步骤是:
    1)解析广告文件,根据定向维度、定向值生成定向条件,每个定向值都有个位图对象;
    2)解析每个广告在每个定向条件上设置的投放条件,如果投则对应位设置为1,否则为0;
    3)根据请求中定向维度的取值,生成定向条件、查找位图,各定向条件的位图执行&操作后,位上取值为1的广告可以投放;
    除了上述处理,在对单值定向建立倒排时,还需要考虑默认情况处理,即存在两个回溯,下面举例说明,假设有两个广告,第一个广告要求只投中国,不投女性;另一个广告要求只投美国、不投男性,如:
    image.png
    先说下正常情况,在country和sex两个定位维度上结合定向值得到两个定向条件,分别是country_CN和sex_F,对于广告1001,如果一个请求过来,传的country是CN、sex是F,则广告不投放;在看下要回溯的情况,如果请求传的country是CN、sex是M,而定向条件sex_M是没有的,那该怎么处理呢?根据上图配置可知,1001广告在sex为M的流量上设置的是不投放,因此,对于定向条件sexM,要执行回溯情况,即看sex的情况,这里是针对请求定向的回溯,同样,在对广告建立倒排时,同样存在回溯处理,比如,1001广告没有在country_US上设置投放条件,根据默认配置可知其不投US,所以在country_US上的设置需要回溯到默认设置。
    总结来说,对于单值定向,除了根据定向设置建立倒排,还要考虑默认情况,请求定向时要考虑、建议倒排时也要考虑,综合上述分析,对于上图中的广告设置,其倒排索引的建立过程是:
    image.png
    上图最后一部分显示了各广告在各定向条件上的设置,结合请求在举例说下定向过程,当请求的country是CN时,由此得到定向条件country_CN,根据上述结果、进而得知1001广告可以投放、1002广告不可以投放;当请求的country是IN时,由于定向条件countryIN不存在,故只能回溯查看定向条件country
的情况,由上可知,1001和1002都过滤。
2.2多值定向
    多值定向的特点是在请求上,定向维度的取值有多个,这是其与单值定向的最大区别,这也导致其倒排实现也略有差异——建立倒排时,多值定向取消针对默认情况的回溯处理,其处理思路是:对于一个定向维度,首先记录各广告在定向条件上的是否有设置,如果有设置则将位置为1;然后记录每个广告在定向维度上设置的黑白名单情况,如果广告在设置条件上有设置且设的是白名单,则表示广告投该条件,如果是黑名单,则就是不投该条件;由此可见,多值定向是根据黑白名单完成广告定向的,这与单值定向差异很大,为了方便理解,还是举例说下,如:有八个广告,在尺寸上的设置条件如下,当请求中广告位支持的尺寸是100x100和100x150时,对应的广告定向流程是:
    image.png
    根据上图,举例说明下上面八个广告在"100x100和100x150"请求中广告的定向过程:
    1)解析广告配置,得到定向条件slotsize_100x100、slotsize_100x150,并为slotsize生成黑、白名单位图;
    2)设置位值,对于定向条件slotsize_100x100、slotsize_100x150,就看广告在该定向条件上是否有设置投放,如果有设置,不管是设置的0还是1,都将位设置为1;然后是为黑白名单设置位值,白名单就设置为1,黑名单就是0;
    3)根据请求尺寸得到本次定向条件是slotsize_100x100、slotsize_100x150,将slotsize_100x100、slotsize_100x150位图或在一起得到hitbit;
    4)最后通过黑白名单设置,执行 whitebit & hitbit | blackbit - hitbit,即最终满足投放条件的广告位图——bits_rst;
2.3线段定向
    线段定向是针对区间定向而言,如:年龄段定向,IP段定向,线段定向是参考多值定向实现的,与多值定向的主要区别是,线段定向在建立倒排时,是单独处理实现的,没有专门生成定向条件、分配定向索引,这是因为线段定向中的每个定向条件也是个线段,所以将这块拎出单独处理,就建立倒排而言,线段定向的主要处理思路就是:
    1)遍历所有广告、记录每个广告上设置的定向线段;
    2)遍历的同时按照从小到大的顺序,记录每个广告上的设置的定向线段;
    3)当遍历到的线段与记录中线段存在交集,则执行拆分操作;
    举例说明下,线段定向的倒排索引的建立过程:
    image.png
    完成倒排建立后,当请求过来时,后续定向过程就和多值定向一样了。

3.代码
    针对上面谈到的三种定向,因为没想好动态位图在Go的实现方式,先用C++实现相关源码,git地址:
    https://github.com/JackBelief/inverted_module.git
    留两个问题,一个是能否以单值定向方式实现线段定向?二个是如何构建倒排集群,将倒排作为一个与业务无关的、独立集群存在?感兴趣的大佬,可以留言讨论!

4.拓展
    在实现刀倒排前有个调研,想使用ES来做,不过由于项目引入改动较大,最终没有采用,有感兴趣的大佬可以尝试下、分享下;下面就举个简单样例,如何使用ES实现广告定向。
    假设有1001和1002两个广告,1001要求国家只投CN和US,性别只投M;1002要求国家只投JP和US,性别只投F,首先要将广告数据放入ES中,广告对定向维度设置的投与不投以黑白名单的形式存储,而请求定向就是对ES执行query查询操作,如:

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"
                                    }
                                }
                            }
                        ]
                    }
                }
            ]
        }
    }
}

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3388 次点击  
加入收藏 微博
1 回复  |  直到 2020-11-02 18:37:39
tianqy
tianqy · #1 · 4年之前

C++代码移入了环境变量,有空控制调试日志,如果不想使用的话,可以修改下;也可以引入临时环境变量,如: export InvertedTest=true

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传