讨论的重点是展示量合约广告以及相应的担保式
把这个值传给服务器来决策创意。这一方案的好处是简单易行，而且服务成本低。缺点是扩展性不好，当同时跟踪多个广告的频次时，cookie可能会变得很重，从而影响广告响应时间。当然，在移动应用广告中利用SDK做前端投放控制的场景，客户端的方案是非常好的选择。服务器端的方案是在后台设置一个专门用于频次记录和更新的缓存，当广告请求到来时，在缓存中查询候选广告的频次，并根据最后实际投放的广告更新频次。
频次控制用到的缓存，同时存在高并发读和高并发写的要求。而且随着频次控制粒度要求的不同，需要记录的频次变量数目也可能很大。比如在创意级别控制频次就比在广告主级别控制频次需要更多的缓存容量。不过考虑到问题的实际情况，这一缓存实际上可以有很轻量级的方案。对我们有利的问题特性主要有以下两点。
（1）频次存储的规模是有上界的。如果我们在某个时间周期内控制频次，那么上述的频次变量总数一定不会超过这个时间周期内的展示总数，这会远远小于所有可能的（a，u）的组合数量。因此，缓存实际的存储规模没有我们想象的那么大。
（2）当用（a，u） 的组合生成缓存中对应的键时，实际上并不需要处理冲突，因为从业务角度来说，对极少比例的冲突组合上的频次控制不准是可以接受的。因此，我们用简单的MD5之类的散列方法生成键就可以，这会比哈希表的方案要简便高效一些。这实际上也反映了广告系统投放过程弱一致的设计原则。
由于频次控制有上述这些特点，并且存在高并发读写的要求，大多数通用型的 NoSQL存储方案并不能很好地用于频次控制的缓存服务，因此很可能需要自行实现一个非常轻量级的内存（key，value） 方案来满足需求。而且，就大多数广告产品的流量规模来看，此缓存完全可以放在广告投放机本机的内存中。
11.3 在线分配
本章中我们讨论的重点是展示量合约广告以及相应的担保式投送系统。展示量合约广告的优化问题与公式 2.2 表达的一般问题，主要区别在于合约量的要求引入了一些约束条件，这引出了在线分配问题。
在线分配问题指的是在通过对每一次广告展示进行实时在线决策，从而达到在满足某些量的约束的前提下，优化广告产品整体收益的过程。很容易理解，此问题计算上最困难的地方在于“在线”，也就是在信息尚不全面的时候作出决策；而系统上最困难的地方在于分配策略需要是弱状态的，同时各广告投放机之间耦合程度也要尽量低。
在线分配是计算广告中比较关键的算法框架之一，它适用于许多量约束下的效果优化问题，而这实际上是广告业务非常本质的需求。由于在线分配问题的重要性超越了担保式投送本身，我们先来介绍此问题的应用场景与算法。
11.3.1 在线分配问题
我们的出发点仍然是公式2.2的计算广告核心问题。此问题优化的是一组广告展示上的利润，而在线分配问题进一步引入了量的约束。为了讨论方便，需要先对公式2.2做一些变化，得到适合于描述在线分配问题的带约束优化问题。
1.供给与需求二部图
以担保式投送为代表，可以看出在线分配问题有两个主要的挑战：一是要在量的约束下优化效果；二是要实时对每一次展示作出决策。直接在这两个要求下优化，会使得求解过程相当困难。因此，在在线分配问题中，一般将此问题简化为一个二部图（bipartite graph）匹配的问题。这里的“二部”指的是代表广告库存的供给节点（集合记为 I，其中某个节点代表的是所有标签都相同的流量库存）和代表广告合约的需求节点（集合记为A）。
供给节点、需求节点和在线分配二部图的示例如图11-5 所示。在这个示例中，下方的6个节点为供给节点，而上面的三个节点为需求节点。如果某个供给节点的受众标签能够满足某个需求节点的要求，就在相应的两个节点间建立一条连接边。我们把这个二部图记为G=（I∪A，E ），其中 E 为 I 与 A之间边的集合，并用 Γ（a）表示所有与需求节点 a∈A相邻的供给节点的集合，而 Γ（i） 表示所有与供给节点 i∈I 相邻的需求节点的集合。我们的任务就是求解由i∈I 到a∈A的分配比例，使得满足供给方和需求方的约束的同时，某个与广告效果相关的目标函数达到最优。
图11-5 在线分配中的二部图匹配问题示意
二部图中的供给节点有时为一组标签约束下的流量集合，在这种情况下，用 si 表示供给节点i的总流量；有时也会用一个节点代表一次展示，这适用于不假设对流量有预测能力的场景或者需要精细区分每次展示的场景下。
请大家注意，与2.2的计算广告一般问题相比，这样的二部图结构实际上假设了在同样一组供给节点和需求节点之间发生的广告展示，其目标函数或回报r是没有差别的。这虽然不够准确，但却是更直接地研究在线分配算法的一种合理近似。在这一近似下，r由（a，u，c）组合的函数变成了供给节点 i和需求节点 a的函数，将其记为 ria。为了方便起见，从分配问题的物理意义出发，往往还假设整体的收益或目标函数是可分的[73]，这一目标函数表示为如下的形式：
其中 si 为供给节点 i的总供给量，而 x={xia}I×A 中的每个元素表示 si 分配给合约 a的比例，这就是在线分配问题
