在程序化广告投放系统中 (即实时竞价方式采买曝光机会), 广告主的投放, 通常会有每日金额消耗限制. 此外, 在不超预算的前提下, 也希望消耗更加均匀, 全日都能够出量, 不要在每天一开始就把预算全部消耗光了, 丧失了在其他潜在效果更好的时间段出量机会. 从我们投放者的角度来说, 希望尽可能的将每日预算消耗殆尽.

基于以上3个预算消耗约束 (消耗上限, 尽可能平均, 尽可能消耗完), 我们探讨下实现的方案.

方案一: 按照时间槽分隔预算

一般的做法, 如rtbkit, 是将预算分到更小的时间槽内, 如每分钟消耗上限. 实践起来非常简单, 将取整的时间作为redis的存储键值记录消耗即可.

为了应对中途预算调整, 存储中应记录消耗值, 剩余值由程序计算得到.

在高频的竞价过程中, 这种方式会导致消耗集中在每个时间槽开始时几秒. 如果每个竞价者都采用此种方式, 会显著推高成本.

此外, 在实践过程中, 绝大部分情况下, 每个时间槽的预算是消耗不完的, 这就导致实际跑下来的消耗远低于预算. 为了充分消耗预算, 应将之前时间段未消耗的余额纳入当前进行计算, 这个在实现上引入了一些复杂度.

方案二:

理想情况下, 在没有预算调整的情况下, 消耗和时间应是线性关系. 为了尽可能地”丝滑”, 方案二的思路是实时计算预期消耗和实际消耗的差值, 并作为该时刻可以消耗的上限:

t时刻预期消耗值 E(t) = 总预算 / 总时间段 * 已经经过的时长
t时刻实际消耗值 C(t),
t时刻可以竞价的金额 R(t) = E(t) - C(t).

R(t) <= 0 表示已经超预算了, 不能够继续竞价. 由于实现事务问题, R(t) < 0 是可能出现的. 导致持续一段时间不出价, R(t)增长为正值, 从而在一定程度上补偿了事务问题导致的短时间内的超预期预算.

TODO 这里画个图例更容易说明问题

事务问题

任何先读, 条件判断, 然后再写的操作, 在并发数高, 单个请求耗时较长的情况下, 会有严重的事务问题, 导致限不住.

如果预算判断放在竞价逻辑最后一步处理 (即如果满足预算要求则一定出价), 可以通过事务性的读+条件写解决, 实现使用redis lua脚本的方式, 保证事务性. 实测发现, 使用redis lua脚本保证逻辑事务, 性能远远不能满足要求, 弃之.

如果预算判断逻辑后面还有一些决定是否竞价逻辑, 一种”悲观锁”的想法是, 先提前扣掉, 最后决定不出价时, 再补偿回来. 在竞价率非常低的情况下, 这种方式会产生大量的写请求, 是一种非常糟糕的实现. 换个角度, “乐观锁”的思路, 读时不做任何处理, 写提交的时候进行条件判断, 如果写入时发现预算依然超过, 则放弃此次竞价. 这种方式最好避免多个写入, 否则又有恶心的业务逻辑多个更新然后回滚的操作.

另外一种思路, 通过限制竞价频次, 或者竞价消耗速率的手段, 来保证即便超出预期, 超出额度也是预期可控. 这个也是常见的退化保障机制, 即逻辑本身不能够保证时刻满足约束的情况下, 通过外部约束, 保证偏离上限可控.

未确认消耗的处理

程序化交易过程中, 先决定是否竞价, 如果决定竞价, 如果竞价成功, 交易平台(即ADX)会回调通知我们, 并确认金额. 这之间有一定的时间间隔. 此外, 由于竞价规则, 导致实际结算价格, 和我们出价价格, 会有一定的价差, 这个在实际设计中也需要考虑到.

如果投放系统只在收到回调时候才更新消耗, 那么竞价时候看到的剩余消耗会不实时, 导致潜在的超预算的情况. 为此, 我们对于这些未确认(inflight)的竞价金额需要处理.

一些比较专业的ADX, 会约定回调延迟保证, 即竞价成功回调, 一定会在竞价的T时间段内, 没有的话, 一定是竞价失败. 对于没有约定保证的ADX, 我们可以通过历史回调延迟统计, 来估出一个相对安全的T值.

解决思路是:

消耗金额分为已确认和未确认两部分.
竞价时候的金额先计在未确认消耗中;
如果T时间内, 没有收到通知, 从未确认消耗中释放;
否则, 累计到已确认中, 为了避免重复计算, 还应从未确认中及时扣除掉.
当前消耗 = 未确认消耗 * 权值 + 已确认消耗, 这里权值保守点用1就好, 激进点, 用预估的竞价成功率替换

未确认部分的消耗金额统计的实现方式可以采用redis的sorted set结构, key通过时间戳+定长唯一ID来做. 每次计算的时候将T时间段前的记录清除掉, 并将最近T时间段的汇总得到未确认消耗. 实践中这种方式是O(n)的, 性能不好, 可以退化成按照时间槽分配的淘汰机制.

多预算计划管理

实际项目中预算管理可能非常复杂, 设置在不同的维度上面. 所以并不是一次预算条件判断, 而是多个预算设定的只读检查后, 确保在没有任何一个检查违背时, 才能够确认出价. 这种涉及多个外部读写, 时延会上去, 也带来了更加严重的事务问题. 实践中通过上述空频次的方式缓解问题.

在其他业务场景中的应用