广告筛选及广告排序的一些想法

 

转自：http://www.csyangchen.com/ads-filter-and-search.html

广告筛选及广告排序的一些想法

 

广告投放系统中, 对于一个展示机会, 能投什么广告, 投哪个广告效果比较好, 和吃饭睡觉一样, 是广告系统要解决的基本需求.

能投什么广告, 是广告筛选的问题: 在根据流量属性, 以及一定的定向条件, 筛选出匹配的广告库存. 这个属于硬性条件, 比如说Android手机, 投放iOS应用的广告, 显然是不合适的.

投哪个广告效果比较好, 就是说, 同样一个展示机会, 是投A应用获得的潜在回报高, 还是投B应用高? 这个属于软性条件. 在算法层面来说, 需要对效果正确预估, 这里不展开讨论. 落地系统实现层面, 需要有效地实现广告排序: 选择出在满足广告筛选的前提下, 优先级最高的广告进行投放.

广告筛选, 以及广告排序, 在系统实践中, 觉得有一些相关之处. 这里斗胆讨论一下.

这里的广告系统可以理解为DSP, 也适用于ADN场景.

广告筛选

广告筛选需求: 给定流量属性, 以及广告投放规则, 有效地筛选出满足流量条件的广告.

从流量的属性以及广告的静态属性的关系来看, 分为一下几种情况:

• 1 v M: e.g. 如投放地区地区, 操作系统, 网络链接方式等信息, 对于流量而言是单一属性, 但是广告定向可能是一个或者多种选择, 这种属于最常见的定向要求
• N v 1: e.g. 流量对于广告会有黑/白名单要求, 如禁止投放的广告类别等
• 范围筛选等其他筛选逻辑: 如, 指定年龄段投放, 等, 本文不涉及到这些筛选逻辑讨论, 只是想说业务上有各种的筛选逻辑

从动态的广告投放规则的来看:

• 各个维度的投放频次控制
• 预算控制以及消耗速率控制
• 以及其他各种业务上的广告筛选逻辑

这里把频次控制, 预算控制概念上划归到广告筛选里面, 因为从执行过程上来看, 都是属于决定一个广告是否要投的这一环.

为了优化查询性能, 需要在投放程序内存中加载全部广告信息, 并设计合理的数据结构.

单个筛选逻辑的优化

类似 1 v M 的黑/白名单定向的筛选逻辑, 在代码最底层的筛选层面, 需要视情况采用 ordered map, hash map, trie 等数据结构. 列表遍历从列表上看似乎是很差的选择, 但其实考虑到 其他数据结构实现上的复杂性, 在 M 较小时也不见得差. 总而言之, 根据 profile 结果说话.

另外, 对于流量的列表属性, 如黑/白名单之类, 可以对表示流量属性的数据结构进行预处理, 如将列表结构转换为字典结构, 从而避免不必要的遍历匹配操作.

对于动态筛选逻辑, 会用到redis读取, 一个常见的办法是使用批量读取进行优化, 但是使用批量请求会导致逻辑严重耦合. 并且, 假设前一个从redis的读取操作已经决定了不匹配, 那么后续的批量读操作都是浪费的. 如果必要的话, 可以使用lua逻辑实现了这种条件读的批量操作, 不过这种redis里面用lua写逻辑, 对于redis吞吐不是很好, 另外在做redis集群化时会比较麻烦.

单个广告定向筛选

看到有些实现, 将广告过滤的业务逻辑堆砌在代码中, 导致整个代码随着业务需求变化频繁更新, 味道不好. 其实, 稍微重构一下, 就可以用一种可扩展的方式实现:

type Filter func(ctx *BidContext) bool

type Campaign struct {
    filters []Filter
}

// 获取流量属性信息
ctx := getBidContext(...)
...
// 决定单个广告是否匹配
for f := range c.filters {
    if !f(ctx) {
        break
    }
}

这里每个filter关联到一个筛选逻辑, 在加载广告配置时注册到Campaign下. 值得一提的一点, 如果广告没有相关的定向条件, 则不用注册, 执行时也省去了相关筛选的判断逻辑.

另外, filter的顺序是可以调整的, 我们可以很方便地通过调整filter的顺序来优化广告筛选的效率.

filter 顺序的优化

对于每个 filter， 有

• 检查开销, 这里开销可以理解为延时, CPU消耗等.
• 通过概率

如果假定每个 filter 的检查开销相同, 那么问题简化为, 按照 通过概率 升序排列 即可.

但实际上不能简化, 一些频次控制的 filter 涉及到外部数据的读取, 比内存中一次哈希表查找要高很多. 一个简单的做法就是将部内在内存中完成的 filter 永远排在后面, 从而减少不必要的外部读取.

通过概率, 则是和流量分布情况相关, 在较短时间内看, 应当是比较稳定的.

此外, 对于某些类型的 filter, 如频次 / 预算控制等, 其 通过概率 不是固定的, 随着自身状态改变而不断变化.

在实现时, 可以通过统计单个广告每个 filter 的检查开销和通过概率, 对 filter 的顺序进行动态调整, 从而减少单个广告匹配的开销.

多广告筛选定向

以上讨论的是单个广告匹配的问题, 实际上我们有很大的广告池, 需要从中筛选出一批符合条件的广告.

充分使用索引

使用索引来减少需要检视的广告列表长度.

索引维度的选择: 使用流量唯一属性, 如操作系统, 国家信息, 展示位尺寸等. 从而保证一次查询就能获取备选广告列表.

对于不限定操作系统或者国家信息的投放计划, 需要枚举所有的国家/操作系统, 从而保证索引的正确性.

另一种方式是将存在于索引中但没有定向的属性标记为ALL, 但对于每一个可能有ALL的属性, 需要再额外查找一次. 这种方式, 对于属性值无法枚举的情况, 如渠道ID定向, 也许更加适合.

索引选择以优化流量匹配为先, 一个广告, 可能会有相关的多个索引. 在广告更新时, 对应的索引关系也需要正确更新.

正常来说, 如果搞定了最常见的索引属性, 广告筛选简化为O(1)的查找. 一次投放决策的响应时间也就不会太慢.

但是在极端情况下, 如果我们再投的广告实在太多了, 怎么办呢?

调整广告顺序

同一索引下, 也会有相同的广告候选, 需要再进一步检查. 那么如何决定遍历的顺序?

从公平起见考虑, 为了保证每个广告都有相同的机会, 应当以随机的方式遍历.

从优化效率的角度考虑, 和单个广告调整 filter 顺序思路相同, 对于筛选概率较低的广告, 降低其优先级. 顺序的调整可以主动, 比如说一个广告触发了投放的整体频次控制后, 或者说 throttle 后, 在最近T时间内绝对不会再投, 则可以主动暂停一段时间, 从而避免无效的筛选.

广告暂停时间(或者说, 广告下次潜在可投时间), 可以作为一个排序依据, 按照暂停结束时间排序, 从而在遍历时, 遇到第一个尚未恢复的广告后, 结束遍历. (想一下, 真正实现时根本不需要排序, 只要记录下次可投的时间戳, 遍历时在单个广告筛选之前检查下即可, 其实应该算单个广告筛选优化策略)

降级服务, 浅尝辄止

另外, 如果对于广告筛选过程有硬性的响应指标, 在筛选过程中, 发现超时, 即刻放弃. 此外遍历过程中适当加入随机, 从而保证 “雨露均沾”, 也提高广告筛选的成功率. 此外, 降低单个请求的遍历深度, 提高单个请求响应时间, 也有助于提高并发处理能力.

流量匹配情况监控

在我们实际项目中, 需要统计流量和投放计划的不匹配情况, 以指导流量定向采买的优化.

实现中, 我们对于每种投放定向不匹配标记了一个NBR码 (No Bid Reason). 在遍历备选广告, 没有发生匹配的时候, 按照最后一个不匹配的NBR统计.

这种统计方式导致了最后统计上的偏差. 举例来说, 美国地区的展示机会, 先是匹配到了有定向美国的广告, 但是由于其它原因, 如预算不足, 导致放弃出价, 最后查询到了一个不投美国的广告, 并以国家定向不匹配统计此次竞价不出价原因. 这种统计方式, 理解上不合理, 因为我明明是有投放美国的广告, 就不应该有美国地区流量出现国家不匹配的情况.

为了解决这种统计偏差, 我们将这些需要关心的维度放到索引里面来做, 并且在索引查询不匹配时, 需要知道第一个不匹配的维度, 从而统计NBR. 索引实现上, 使用简单的类似trie的嵌套结构可以比较好扩展的满足需求.

但是, 索引维度的先后顺序对于统计结果也是有偏差的. 举例来说: 流量单从os看, 匹配度50%; 单从country看, 匹配度也是50%. 如果索引顺序是: os, country, 最终统计结果是, os不匹配的流量比country不匹配的多了一倍; 再进一步, 如果从os, country组合维度看没有匹配的广告 (比如说只有美国IOS流量, 印度Android流量, 但是我库存只投美国Anrdoid, 印度IOS), 统计结果上只有country不匹配的统计, 不能看出这种不匹配的原因.

因此, 这种根据线上投放报告的不匹配维度来统计流量匹配, 得到的结果是片面的, 也没有考虑到维度组合因素的影响. 为了真是统计流量匹配情况, 还是需要将看到的流量维度统计下来, 然后去和库存情况做离线的匹配, 从而得到更精准的匹配报告.

广告排序

常见权重因素包括:

• 预估的展示期望回报, 如ECPM, ECPC, 这些数据一般由广告优化算法离线或半实时给出
• 业务上的一些设定, 如测试新单子, 优先跑量小的广告等
• 广告是否在投, 也可以简化为优先级最高的权重因素, 因为排序后, 遇到第一个不在投的广告, 查询就可以结束了, 避免了对于下线广告的无谓访问. 也可以做一次截断就可以把下线的广告一次性剔除.

优先级不一定是一个数值, 可以是多维的信息组成, 只要满足排序关系即可, 这样为广告投放规则留下了不少发挥的空间.

优先级的权重设计应当是不敏感的, 保证在一段时间内的稳定性. 比如说, 以展示的量级, 而不是具体的展示数作为权重因素.

排序优先级的数据来源, 一般是从外部数据库读取, 半实时更新, 并触发内存中数据结构的重排序.

排序如何影响投放选择

方式一: 高权重广告一定优先投放, 只有在频次控制等广告筛选规则不能通过的情况下, 才投较低优先级的广告; 对于相同优先级广告, 有同等投放机会.

同优先级广告有相同机会, 实现上的一些方式: 一种办法是在排序时, 对于相同优先级元素时, 随机返回一个顺序关系, 从而保证顺序同优先级广告的遍历顺序是比较随机, 缺点是需要定时进行重新排序. 另外一种办法是自己设计数据结构, 遍历相同优先级元素时, 按照一个随机顺序访问, 这种实现起来不难.

这种投放方式导致一个时间段内则集中在某些广告, 尽快出量, 而其他低优先级广告没有投放试错机会. 如果从观察效果数据的角度, 还是需要做到”雨露均沾”, 低优先级广告也有投放的机会.

方式二: 高权重广告有更高的投放机会, 而不是一定优先投放

实现上: 每个优先级单独一个队列, 访问每个队列的顺序按照权重决定. 这种带权的随机, 需要我们知道整个队列的权和, 对于非数值型的优先级设计, 处理起来会比较麻烦了. 可以在排序时, 不相等的元素间加差标记位, 从而解决问题.

上述这里两种方式, 不一定哪个更好, 需要结合实际情况来看, 甚至是可以组合在一起来用的. 比如说: 优先投放有转化的广告, 按照转化率作为权重, 按照方式二投放; 对于转化率太低还未有统计意义的广告, 按照展示数量级作为权重, 从而尽快拉近每个广告的展示量级.

优先级和流量属性有关

我们之前的讨论, 全部建立在优先级和流量属性无关的假设下讨论的. 实际上每个广告的效果, 适合流量属性相关的.

简单的例子: 同一广告, 在不同的渠道的表现不一样, 如果渠道总数不多, 简单做法, 每个渠道一个维护一个优先队列; 更加深挖一点: 效果可能是由渠道的各种流量属性标签导致的, 或者是使用者的偏好习惯决定, 如应用类型, 广告位属性, 等等. 这里首先要确定的决定投放效果的 feature 集合.

如果 feature 集合已经确定, 可以根据各个 feature 的组合, 创建广告排序的索引. 这块儿可以和多广告筛选的索引类似.

在维度组合确定的情况下, 这种是可行的, 但是如果选择的 feature 是不能预先枚举的, 可以通过懒初始化的方式来做.

总结

不好意思, 写得有点混乱, 总结几点:

• 一种灵活的插件式的广告筛选结构
• 基于这种插件式的广告筛选结构, 我们可以在单个广告的 筛选逻辑 执行顺序, 以及多个广告的检视顺序上, 进行类似的排序优化, 以提高 广告筛选 效率
• 广告排序, 由广告优化算法提供权重指标, 其目的是为了效果优化, 讨论了在落地到具体实现上时, 会遇到的几种情况和解决思路