目录
11.2 担保式投送系统
11.2.1 流量预测
11.2.2 频次控制
11.3 在线分配
11.3.1 在线分配问题
11.3.2 在线分配问题举例
11.3.3 极限性能研究
11.3.4 实用优化算法
总结
11.2 担保式投送系统
担保式投送（Guaranteed Delivery， GD）是合约广告的现代形式。与固定排期不同，它不再要求广告在特定时间、特定广告位上展示，而是承诺在约定的时间段内向特定目标人群展示一定数量的广告。例如，承诺“在未来一周内，向北京地区对汽车感兴趣的女性用户展示100万次某品牌汽车广告”。这种灵活性极大地提高了流量利用效率和广告效果，但同时也带来了巨大的技术挑战：系统必须实时决策每一次曝光是否分配给某个担保合约，并确保在合约到期时精准完成承诺的展示量。
担保式投送系统由两个核心组件构成：流量预测和频次控制。前者是“知天时”，后者是“明规矩”。两者结合，才能在复杂多变的流量环境中，优雅地履行每一个承诺。
11.2.1 流量预测
流量预测是担保式投送系统的“眼睛”和“导航仪”。它的任务是准确估计未来一段时间内，符合各种定向条件的可用的用户流量。预测的准确性直接决定了系统能否制定可行的投放计划、避免过度承诺（under-delivery）或库存浪费（over-delivery），以及进行高效的在线分配。
1. 预测问题的层次与粒度
担保式投送所需的流量预测是高度多维和细粒度的。我们需要预测的不再是简单的“首页Banner明天有多少PV”，而是类似“明天上午9点到10点，来自北京使用iOS设备、对旅游感兴趣的女性用户，在新闻频道体育板块的PV是多少”这样的组合条件。这构成了一个巨大的组合空间。
通常，预测任务被分解为两个层次：
基础流量预测：预测未来一段时间内（如未来24小时），媒体各个入口（如网站首页、频道页、文章页）或广告位（如Banner、插屏）的总曝光量。这主要是一个时间序列预测问题，考虑趋势、季节、工作日/周末、节假日等因素。
定向流量预测：在基础流量的基础上，预测符合各种定向标签组合的流量比例。这需要基于历史数据，统计或建模不同标签组合（如地域、性别、兴趣）在总流量中的分布，并考虑其随时间的变化。
2. 核心技术方法
经典时间序列模型：对于基础流量预测，ARIMA、SARIMA（季节性ARIMA）等模型可以捕捉时间序列的自相关性和季节性。但这些模型对突发新闻事件等外部冲击不敏感。
机器学习回归模型：将预测问题转化为回归问题。特征可以包括：历史同期流量、近期流量趋势、星期几、是否节假日、天气、是否有重大活动等。使用GBDT、随机森林或线性回归进行训练。这类模型能更好地融入外部特征。
深度学习序列模型：对于更复杂的流量模式，可以使用LSTM、GRU或Transformer来建模长期依赖和非线性关系。特别是当流量序列存在多种周期（日周期、周周期、月周期）和突变时，深度学习模型表现更优。
组合定向流量的估计：由于标签组合爆炸，不可能为每一种组合都独立训练一个预测模型。常用的方法是层次化估计或因子分解。
层次化估计：利用流量标签的层次结构（如：总流量 → 地域分布 → 某地域下的性别分布 → 某地域某性别下的兴趣分布）。先预测父节点的流量，再基于历史比例或动态模型预测子节点的比例。
因子分解法：将流量视为一个高维张量（维度包括时间、地域、性别、兴趣等）。使用张量分解（如CANDECOMP/PARAFAC）或低秩模型来学习各个维度的隐含因子，从而用较少的参数估计整个组合空间。现代方法可能会使用神经网络来学习这种复杂的联合分布。
3. 在线学习与实时校准
互联网流量瞬息万变，基于离线历史数据的预测模型可能很快过时。因此，担保式投送系统必须包含在线学习和实时校准模块。
在线学习：模型采用增量更新，每来一批新的流量数据（如每5分钟），就对模型参数进行微调，快速适应流量模式的变化。
实时校准：更常用的是一种轻量级的校准方法。系统持续监控实际流量与预测流量的比例（称为Pacing Rate或Delivery Rate）。例如，某定向流量在上午10点的预测是100万次，但到10点时实际只发生了80万次。那么系统会动态调低后续时间段的预测值（乘以一个校准系数如0.8），并用这个校准后的预测来指导后续的分配决策。这种反馈控制机制对保证整体投放进度至关重要。
4. 不确定性量化
预测不可能100%准确，因此必须量化预测的不确定性。这通常通过预测置信区间或给出概率分布来实现。例如，不仅预测期望流量是100万，还预测有90%的可能性在[90万, 110万]之间。这种不确定性信息对于风险敏感的合约分配决策（如是否承接一个新合约）极为重要。贝叶斯方法或分位数回归可用于此类任务。
5. 实践中的挑战
数据稀疏与冷启动：对于长尾的定向组合，历史数据极少。需要使用层次平滑、迁移学习或基于内容的方法来估计。
外部事件影响：突发新闻、社交热点、竞品活动等会剧烈改变流量。系统需要实时监控舆情或接入外部事件信号，作为预测特征。
服务器日志延迟与丢失：流量数据的收集和汇总可能存在延迟（如几分钟到几小时）和丢失。预测系统需要能够处理不完整的数据，并具有鲁棒性。
流量预测是担保式投送系统中一个持续迭代和优化的模块。它没有一劳永逸的解决方案，需要数据工程师、算法工程师和领域专家的紧密协作，不断融合新的数据源和算法，以应对日益复杂的媒体环境。
11.2.2 频次控制
频次控制是担保式投送系统中的“交通警察”。它的核心任务是：确保同一个广告在合约期内，向同一个用户展示的次数不超过约定的上限。这既是广告主的要求（避免过度打扰用户、提高投放效率），也是用户体验的保障。
1. 为什么需要频次控制？
广告主视角：广告的边际效用递减。对一个用户展示第一次广告可能效果显著，展示第五次可能就无效甚至产生反感。控制频次有助于在预算有限的情况下覆盖更广泛的受众，提高触达率（Reach）。
用户视角：避免被同一广告“刷屏”，减少侵扰感，提升对媒体平台的满意度。
媒体平台视角：合理分配流量，避免少数合约过度消耗优质用户资源，从而服务更多广告主。
2. 频次控制的技术挑战
在一个大型广告平台上，频次控制面临三大挑战：
高并发：每秒处理数百万次曝光请求，每次请求都需要查询并更新用户的历史频次记录。
低延迟：频次检查是广告决策流程中的一环，必须在几十毫秒内完成。
强一致性与高可用：频次数据必须准确，不能因为分布式系统的延迟或故障导致超投（超过频次上限）或少投。同时，服务必须7x24小时可用。
3. 实现方案演进
方案一：基于Cookie/Device ID的计数器（单机/分布式缓存）
思路：为每个（用户，广告活动）对维护一个计数器，存储在Redis或Memcached这样的高性能键值存储中。每次广告请求时，查询该计数器，若小于频次上限，则允许展示并递增计数器。
优点：简单、直接、精度高。
缺点：
存储成本高：用户数（数亿）乘以活动数（数千）可能达到百亿级键值对，内存消耗巨大。
写入压力大：每次允许展示都需要进行一次“读取-判断-递增-写入”的操作，对缓存集群的写入吞吐量是巨大考验。
持久化与恢复困难：缓存数据易失，需要定期持久化到数据库，故障恢复时间长。
方案二：概率性频次控制（基于Bloom Filter或其变种）
思路：使用布隆过滤器（Bloom Filter）这种空间效率极高的概率数据结构来记录用户是否看过某广告。布隆过滤器可以回答“用户可能看过”或“用户肯定没看过”。当过滤器回答“可能看过”时，可以结合一个宽松的策略（如按一定概率拒绝）来控制频次。
优点：空间效率极高，节省内存；查询速度快，只有O(k)次哈希计算。
缺点：
有误判率：存在将新用户误判为已看过广告的概率，导致少投。
无法支持精确计数：标准Bloom Filter只支持存在性检查，不支持“第N次”这样的精确计数。改进版如Counting Bloom Filter可以支持删除和有限计数，但空间消耗会增加。
难以重置：合约到期后，需要清空对应的过滤器。对于海量过滤器，管理复杂度高。
方案三：分层抽样与用户分桶（工业界主流）
思路：这是对“精确计数”的一种巧妙近似，旨在保证系统层面频次达标的同时，大幅降低存储和计算压力。核心思想是：不对全部用户进行频次控制，而是对每个广告活动，只对其抽样用户群进行严格计数，并假设这个抽样群体的行为可以代表全体用户。
具体实现（以一天内频次上限为N为例）：
用户分桶：将所有用户通过一个哈希函数（以广告活动ID为盐）均匀分配到M个桶中（例如M=1000）。每个用户属于且仅属于一个桶。
选择控制桶：指定其中K个桶（K<M，例如K=10）为“控制桶”。只有落入控制桶的用户，系统才会为其严格记录和检查对该广告的观看次数。
投放逻辑：当一个用户请求广告时：
计算其属于哪个桶。
如果该桶是控制桶，则进行精确的频次检查（如用方案一的计数器）。如果未超频，则展示广告。
如果该桶是非控制桶，则直接展示广告，不进行频次检查。
总量控制：由于用户是均匀随机分桶的，控制桶中用户的展示次数占全体用户展示次数的比例期望值为 K/M。因此，只需确保控制桶内的用户平均频次不超过N，即可推断全体用户的平均频次不超过N。系统可以通过调节控制桶内的投放概率来间接控制整体频次。
优点：
存储和计算开销降低：只需要为K/M比例的用户维护计数器，开销降低为原来的K/M（如1%）。
保持了统计意义上的准确性：在流量足够大的情况下，可以保证合约的整体频次目标。
易于扩展和管理：增加新的广告活动只需增加一组新的分桶和计数器。
缺点：
个体不公平：非控制桶的用户可能看到超频的广告。
需要谨慎调参：K和M的选择需要在精度和开销之间权衡。对于流量很小的定向，控制桶的样本可能不足，导致统计波动大。
方案四：基于时间窗口的近似计数（如滑动窗口 HyperLogLog）
思路：使用HyperLogLog（HLL）等基数估计数据结构来估计在最近一个时间窗口（如过去7天）内，看过某广告的独立用户数（去重计数）。结合总的展示次数，可以估算出平均频次。但这种方法无法控制单个用户的频次，只能控制整体的平均频次，更适用于“触达（Reach）”优化场景。
4. 智能频次控制
随着技术的发展，简单的固定频次上限（如“每人每天不超过3次”）正在向智能频次控制演进。其思想是：最优的频次不是固定的，它应取决于用户、广告和上下文。
个性化频次：对于高价值用户或高相关性广告，可以适当提高频次上限；对于已经表现出反感（如频繁跳过、关闭）的用户，则应降低频次甚至停止投放。这需要建立用户疲劳度模型，实时预测用户对下一次广告展示的负反馈概率。
跨广告活动频次控制：一个广告主可能有多个并行的广告活动。需要从广告主层面控制用户接收该品牌广告的总频次，避免跨campaign的过度打扰。
频次与效果建模：将频次作为特征纳入点击率/转化率预测模型。模型会自动学习频次与效果之间的关系（通常是倒U型曲线），从而在排序阶段就隐式地实现智能频次控制——对已经看过多次该广告的用户，其CTR预估值自然下降，排名靠后，被展示的概率降低。
5. 总结
频次控制是担保式投送系统中保证广告效果和用户体验的关键闸门。从简单的计数器到精巧的分层抽样，再到基于模型的智能控制，其技术演进体现了计算广告系统在追求规模、效率和智能化方面的不懈努力。在实际系统中，往往会采用混合方案，例如对头部核心合约使用精确控制，对长尾合约使用抽样控制，以达到整体最优。
11.3 在线分配
在线分配是担保式投送系统的“决策大脑”。当一次广告请求到来时，系统可能有多个担保合约都符合展示条件（定向匹配，且未完成展示量，且未达到频次上限）。在线分配算法必须实时决定：将这次曝光机会分配给哪一个合约（或者选择不分配，留给竞价广告）？其目标是：在流量随机到达、未来不确定的情况下，做出系列决策，使得所有合约都能在到期时刚好完成，同时最大化整体收入或其他目标（如预留更多流量给高优先级合约）。
11.3.1 在线分配问题
在线分配问题可以抽象为：有一系列订单（担保合约），每个订单 ii 要求 didi 单位的资源（展示量）。资源在时间线上以随机顺序到来，每次到达一个单位资源（一次曝光），并且带有特征标签（如用户属性、上下文）。当一个单位资源到达时，我们必须立即且不可撤销地将其分配给一个能“接受”该资源的订单（即定向匹配），或者丢弃（分配给竞价市场）。目标是尽可能满足所有订单的需求，或者最大化满足订单的总价值。
关键特性：
在线性：决策必须在看到所有未来资源请求之前做出。这是与离线排期的本质区别。
随机性：资源请求的序列不是敌意的，而是来自一个已知或部分已知的概率分布（即流量预测）。
目标：通常不是简单地满足所有需求，因为那可能导致低价值订单消耗了本可用于高价值订单的稀缺流量。目标往往是最大化所有被满足订单的总价值（每个订单可能有不同的优先级或单价），或者在满足所有订单的前提下最小化资源消耗（将更多流量留给利润更高的竞价广告）。
11.3.2 在线分配问题举例
为了更具体，我们引入一个高度简化的例子：
假设一个媒体只有一种类型的用户流量（无定向区分）。它有两个担保合约：
合约A：需要展示 50次；优先级高，单位展示价值为 $10（如果完成）。
合约B：需要展示 100次；优先级低，单位展示价值为 $5。
媒体预测在合约期内总共有 120次流量到达。
问题：如何分配这120次流量，以最大化完成合约的总价值？
分析：
如果我们将所有流量都给合约A，可以完成50次，价值 $500，但浪费了70次流量（合约B未完成）。
如果先尽量满足合约B，分配100次给B，价值 $500，然后剩下的20次给A，价值 $200，总价值 $700。
显然，最优策略是先分配足够流量给高价值合约A，确保其完成，再将剩余流量分配给B。即：分配50次给A，70次给B。总价值 = $10*50 + $5*70 = $850。
这个简单例子揭示了在线分配的核心原则：根据单位资源的价值（或称为“机会成本”）来分配资源。在高维定向、流量随机到达的现实场景中，我们需要一个系统化的方法来计算这个“机会成本”。
11.3.3 极限性能研究
理论计算机科学领域对在线分配问题有深入研究，其核心是衡量在线算法的性能。通常用竞争比来衡量：一个在线算法的竞争比是 cc，如果对于任何输入序列，该算法获得的收益至少是最优离线算法（能预知未来）所获收益的 cc 倍。cc 越接近1，算法越好。
对于在线分配，一个里程碑式的结果是双匹配问题及其算法。研究发现，如果资源请求是依概率分布独立同分布地到来，并且我们已知该分布，那么存在一种基于对偶变量的在线算法，其期望收益可以接近最优离线收益。这为实践中的算法设计提供了理论依据。
11.3.4 实用优化算法
在实践中，最常用的在线分配算法是基于对偶的贪婪算法，也称为HWM（High Water Mark）算法或Shadow Price算法。其核心思想源于线性规划的对偶理论。
1. 线性规划模型
首先，我们将问题建模为一个离线的线性规划（假设我们知道所有未来的请求）：
变量：xijxij —— 将第 jj 次曝光分配给合约 ii 的比例。
目标：最大化总价值 ∑i,jvijxij∑i,jvijxij，其中 vijvij 是将曝光 jj 分配给合约 ii 的价值（可能与CTR等相关）。
约束：
∑jxij≤di∀i(需求约束)j∑xij≤di∀i(需求约束)∑ixij≤1∀j(供给约束)i∑xij≤1∀j(供给约束)xij≥0xij≥0
这个线性规划的最优解给出了最优分配方案。
2. 对偶变量与影子价格
上述线性规划的对偶问题引入一组变量：
αi≥0αi≥0：对应每个合约 ii 的需求约束，可以理解为该合约的影子价格或单位资源价值。
βj≥0βj≥0：对应每次曝光 jj 的供给约束。
对偶理论告诉我们，在最优解处，互补松弛条件成立。特别地，对于一次曝光 jj，如果它被分配给合约 ii，那么有 vij=αi+βjvij=αi+βj。直观上，αiαi 可以解释为合约 ii 为获得一次曝光愿意支付的“内部价格”。
3. 在线算法设计
我们无法预知所有曝光 jj，但可以预先计算每个合约的影子价格 αiαi（通过求解一个基于预测流量的规划问题）。然后，当一个真实的曝光 jj 到达时：
找出所有有资格（定向匹配）且仍有剩余需求的合约集合 IjIj。
对于每个合约 i∈Iji∈Ij，计算其“收益” vij−αivij−αi（可以理解为扣除内部成本后的净收益）。
选择净收益最大的合约，即 i∗=argmaxi∈Ij(vij−αi)i∗=argmaxi∈Ij(vij−αi)。
如果这个最大净收益大于0（或者大于将该曝光留给竞价广告的收益），则将这次曝光分配给合约 i∗i∗，并减少其剩余需求 didi；否则，将曝光分配给竞价广告。
影子价格 αiαi的物理意义：它反映了合约 ii 所需流量的稀缺程度。如果一种定向流量很充足，其对应的合约影子价格 αiαi 会较低，容易赢得曝光；反之，如果流量稀缺，αiαi 会很高，只有对它价值极高的曝光（vijvij 很高）才能赢得分配。
4. 工程实现与动态调整
在实践中，流量预测会有误差，合约的消耗进度也会波动。因此，影子价格 αiαi 不能一次性计算后固定不变。系统需要周期性地（例如每小时）重新求解线性规划，根据最新的预测和消耗情况，更新所有合约的影子价格。这个过程称为“规划求解”。在线分配模块则使用最新的影子价格进行实时决策。
此外，在线分配还需要与** pacing **（投放节奏控制）紧密配合。Pacing 控制单个合约的消耗速度，确保其平稳消耗，避免前期过快耗尽预算（导致后期无广告可投）或后期突击消费（导致流量争夺激烈，成本上升）。通常，Pacing 通过调整每次曝光分配给该合约的概率来实现，而在线分配算法则决定了在“允许参与竞争”的合约中谁最终胜出。
总结
在线分配是担保式投送系统中最具理论深度和工程挑战的环节。它将运筹学、随机过程和在线算法的最新理论成果，转化为每天处理千亿次决策的工业系统。从HWM算法到基于实时对偶的优化，其核心思想始终是通过计算资源的“内部价格”来指导分配，在满足合约的同时，最大化整体资源利用效率。理解在线分配，是理解现代广告平台如何像精密的金融市场一样，对注意力资源进行高效、动态配置的关键。
