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

tianqy · · 2646 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

2646 次点击  
加入收藏 微博
1 回复  |  直到 2020-11-02 18:37:39
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传