广告超投动态控制系统设计
j5land
背景
在广告系统中，高并发环境下的广告投放管理是一个复杂而关键的问题。广告主通常会设定特定的预算，用于控制其广告的投放量和投放时长。在高并发环境下，如果系统无法在广告主的预算耗尽时及时停止广告投放，便会导致“超投”现象。即使广告主的预算已经用完，系统仍然继续为其投放广告，这样就可能会对广告平台的收入造成损失。
超投控制算法（目前）
降速触发机制
以下条件达成其一，触发降速检查机制（优先判定今日预算）：
- 今日预算设置了，今日费用消耗达到今日预算的90%
- 今日预算没设置，总预算设置了，总费用消耗达到总预算的90%
降速检查机制
查询当前广告分钟级消耗，即查询广告当前时间的上一分钟的费用消耗。
计算剩余投放时间 = 广告剩余费用 / 广告当前时间消耗
若是消耗费用达到上述触发机制条件，并判断剩余投放时间是否小于30分钟，当 广告剩余投放时间 <= 30分钟时，通过广告剩余投放时间占比变化调整广告命中概率，从而达到降速的目的。
降速算法
降速系数 = (剩余分钟数+3)/33，也可称之为Miss概率，保留下限约0.1，防止未真正投放达到预算却迟迟没有量。
由于当前的广告命中概率，通过权重 1 ～ 10000来设置，并且 命中概率 =[10000-某条广告权重]/sum[(10000-ad1)+(10000-ad2)+(10000-ad3)+(10000-ad..)]。
结合降速系数（Miss概率），假如 A、B、C三条广告，有不同的权重，随机选中了A，但是由于A触发了降速，因此需要再次根据Miss概率随机一次，如果是Miss的话，从B和C中再随机选中，依次类推。
让 t 表示预估剩余分钟数，降速系数（也称为Miss概率）可以定义为函数 D(t)。函数的形式如下：
- 当 t > 30 分钟时，降速系数 D(t)=1。
- 当 t ≤ 30 分钟时，降速系数 D(t)= (t+3) / 33，但要保留一个下限约为 0.1。
可以将降速系数定义为以下分段函数： $$ D(t) = \begin{cases} 1 & \text{如果 } t > 30 \ \max\left(0.1, \frac{t + 3}{33}\right) & \text{如果 } t \leq 30 \end{cases} $$ 这里使用了 max 函数来确保当 t ≤30 分钟时，降速系数不会低于0.1。
其中，t 是预估剩余分钟数， (t+3) / 33 是在 t ≤ 30 时的降速系数计算方式，并且确保其不会低于0.1。
当t <= 30时，函数曲线：
$$
D(t)=\frac{t+3}{33}
$$
目前弊端
延迟反应
降速触发机制基于费用消耗达到预算的90%时才启动
这意味着在达到90%之前，广告投放速度是全速的。如果广告的消耗速度非常快，在高峰期可能会在短时间内从90%消耗到100%甚至超过预算，导致短时间内出现超投现象。
降速系数下限
设定降速系数下限为0.1，虽然防止了广告完全停止投放的情况，但在预算即将耗尽的情况下，仍然会有一定量的广告投放。
这种情况在预算非常紧张时，可能会导致轻微的超投。
基于分钟级消耗
当前算法仅查询广告的分钟级消耗来判断剩余时间，但实际消耗速度可能会在分钟内波动
在秒级消耗较高的情况下，单分钟消耗数据可能不足以精确反映实际情况，可能导致降速反应不及时或不准确。
超投动态控制算法
总体思路：
- 获取目前广告当前时段的投放速度，使用秒级消耗计算，为保证数据相对准确使用最近10秒加权平均数计算；
- 获得所属目标广告的剩余投放时间，即 广告预算余额 / 广告当前消耗速度，剩余投放时间秒；
- 根据广告投放速度限制系数函数，根据广告剩余投放时间，来计算广告投放速度限制系数；
- 计算当前时间段的投放速度限制系数，通过广告限制系数，从而来调节广告速度；（其限制系数其值在0~1之间）
秒级广告消耗速度
当前广告的投放速度
目前广告当前时段的投放消耗速度：
使用秒级消耗来计算，时间范围使用最近10秒滑动窗口的加权平均来计算，可以更平滑和稳定地估计当前的广告投放速度。
步骤：
- 维护一个包含最近10秒广告消耗数据的滑动窗口。
- 对这些数据应用加权平均计算，其中较新的数据权重更大，反映出最新的消耗趋势。
广告秒级消耗公式（最近10秒加权平均）
$$ \bar{C} = \sum_{i=1}^{10} w_i’ \cdot c_i $$
权重公式
使用指数衰减系数 α 来计算权重： $$ w_i = (1 - \alpha)^{10 - i} $$
标准化权重
权重标准化，使其和为1： $$ w_i’ = \frac{w_i}{\sum_{i=1}^{10} w_i} $$
计算案例
假设最近10秒的广告消耗数据分别为 c1，c2，…，c10 对应的权重为 w1，w2，…，w10。
最近10秒的广告消耗数据为： $$ c_1 = 0, \quad c_2 = 0, \quad c_3 = 0, \quad c_4 = 0, \quad c_5 = 0, \quad c_6 = 17, \quad c_7 = 18, \quad c_8 = 19, \quad c_9 = 16, \quad c_{10} = 20 $$ 指数衰减系数： a = 0.1
初始权重：
$$
w_1 = 0.9^9 \approx 0.38742,
w_2 = 0.9^8 \approx 0.43047,
w_3 = 0.9^7 \approx 0.4783,
w_4 = 0.9^6 \approx 0.53144,
w_5 = 0.9^5 \approx 0.59049,
w_6 = 0.9^4 \approx 0.6561,
w_7 = 0.9^3 \approx 0.729,
w_8 = 0.9^2 \approx 0.81,
w_9 = 0.9^1 \approx 0.9,
w_{10} = 0.9^0 = 1
$$
标准化权重：
$$
w_i’ = \frac{w_i}{6.51322}
$$
$$ w_1’ \approx \frac{0.38742}{6.51322} \approx 0.0595 , w_2’ \approx \frac{0.43047}{6.51322} \approx 0.0661 , w_3’ \approx \frac{0.4783}{6.51322} \approx 0.0734 , w_4’ \approx \frac{0.53144}{6.51322} \approx 0.0816 , w_5’ \approx \frac{0.59049}{6.51322} \approx 0.0906 , w_6’ \approx \frac{0.6561}{6.51322} \approx 0.1007 , w_7’ \approx \frac{0.729}{6.51322} \approx 0.1119 , w_8’ \approx \frac{0.81}{6.51322} \approx 0.1244 , w_9’ \approx \frac{0.9}{6.51322} \approx 0.1382 , w_{10}’ \approx \frac{1}{6.51322} \approx 0.1535 $$ 计算加权平均广告消耗： $$ \bar{C} \approx 0.0595 \cdot 0 + 0.0661 \cdot 0 + 0.0734 \cdot 0 + 0.0816 \cdot 0 + 0.0906 \cdot 0 + 0.1007 \cdot 17 + 0.1119 \cdot 18 + 0.1244 \cdot 19 + 0.1382 \cdot 16 + 0.1535 \cdot 20 $$
$$ \bar{C} \approx 11.3709 $$
得到最近10秒的加权平均广告消耗大约为：11.37
剩余投放时间
根据当前投放速度获得所属目标广告的剩余投放时间，即 t = 广告预算余额 / 广告投放速度， 单位为秒；
当前投放速度限制系数
计算当前时间段的投放速度限制系数，获取当前限制系数公式：
D(t)标识下一时段对所述广告的投放速度限制系数，其值在0~1之间，t表示所述广告的剩余投放时间。 $$ D(t)=\frac{1-e^{-0.0083t}}{1+16e^{-0.0083t}} $$
函数曲线
调节广告命中率
通过该广告速度限制系数调节广告命中率
超投控制模块设计
