泽民博客 ☰ Menu

分布式系统频次限制实现

频次限制（rate limiting）是Web系统比较常见的功能，防止用户频繁访问接口，导致系统负载增加而影响服务的质量。



系统要求
针对线上的功能，实现对指定对象有访问频次的限制
支持多个客户端访问
低延迟
承受较大的访问量
易于拓展
流程
设置服务频次限制，如针对某key10QPS
根据指定key，服务请求ratelimiter，获得是否允许此次访问
伪代码
// 初始换状态
rate := 1 // 设置频率为1ops
needed := 1 // 设置访问1次API需要的令牌数量为1
key := “userA_APIX” // userA访问APIX的场景
tokens := 0 // 当前可用令牌数
lastTime := time.Now() // 上次令牌更新时间



// 时间过去1s
time.Sleep(time.Second)



// userA请求访问APIX
nowTime := time.Now()



// 计算这段时间新生成的令牌数量
newTokens := (nowTime-lastTime)*rate



// 判断是否允许访问
allow := (newTokens+tokens)>needed



// 更新数据
if allow {
tokens = newTokens+tokens-needed
lastTime = nowTime



// 响应用户操作 } else {

tokens = tokens+newTokens

lastTime = nowTime

 

// 提示用户操作超过限制 } <!-- more --> 设计思路 频次限制应该统一存储 webserver是任意可拓展个数的服务，一开始，我将rate limiter的存储放在了各自服务中，导致明明我限制的是整个集群这个API的访问单人不可超过5QPS，实际上却是5nQPS。所以这个频次限制需要统一存储，统一整个系统的访问频次。


频次限制本质是一个服务
我试着把存储挪到了redis，并且使用了一些redis的命令实现了CAS，redis里存了key，tokens，lastTime，实现令牌桶算法，可是算法逻辑仍然放在client端（也就是那些web server）。
经过压测，QPS比较低，主要是因为CAS的重试率随着并发量上升不断升高，况且访问redis增加了网络开销，于是考虑将逻辑如何和数据放到一起。



控制成本
重新开发一个频限服务，需要考虑多节点数据同步，请求转发，failover等功能，我希望以最小的开支实现这个系统。



实现
最终选择了redis的lua脚本实现了频限功能，既统一了存储，又可以利用redis cluster实现了可拓展的频限服务，以最小的成本实现功能。



benchmark
经过测试，MacBook Pro (Retina, 13-inch, Late 2013), CPU 2.4 GHz Intel Core i5, Memory 8 GB 1600 MHz DDR3上能达到1w+QPS。
https://github.com/wallstreetcn/rate



1.频率控制措施
弹图片验证码
一段时间内禁止登陆（封号一段时间）
2.要求
设置某段时间内的最多访问次数（两个参数：时间+次数）
区分不同业务的频率控制服务（业务类型）
并发控制（访问次数存储在何处，如何修改，如何判断是否超过限制，如何加锁或使用原子操作）
3.实现
某段时间+最多访问次数+业务类型，可以配置到数据库或配置文件
访问次数存储，由于写的频率很高，采用缓存的方式存储
控制并发—在何处加锁（访问次数的修改处）



接口频次控制主要包括两方面：



（1）业务ID对某一个接口某时间间隔（如一分钟）内访问的次数 限制



（2）业务ID在某个时间周期（如一天）内访问的次数 限制



对于存储并进行频次计数的服务来说，要具备以下的特点：



（1）自更新能力，在某个约定的时间点对所有的node（节点）进行自更新操作，也就是常说的出厂设置



（2）协议轻型能力，协议必须尽可能简单，才能达到高效的目的



（3）增删查改能力，允许业务调用方对某个节点的数据增删查改



以上所提节点，如node，大体包含了如下分支



node.bizid,业务id,给某个客户分配的业务id,是客户在频次计数系统里的唯一标识



node.m_count,某分钟周期内访问次数



node.count,某计数周期内访问次数，如一天。



node.starttime，计数开始周期



node.endtime,计数结束周期，记录客户最后一次接口访问的时间，也用于频次计数系统的自更新



node.m_starttime,分钟计数开始时间



node.m_endtime,分钟计数结束时间，当（node.m_endtime-node.m_starttime）<60 && node.m_count>M_MAX_COUNT，接口访问被拒绝，当（node.m_endtime- node.m_starttime）> 60,同时更新node.m_endtime，node.m_starttime为当前时间，重置node.m_count



同样，天计数周期的原理也如此。



  为防止开放系统的公共接口被过度调用，本文提出一种面向系统内部的访问频率限制服务轻型模型，并给出泛型键值索引、频率约束算法等关键技术实现。该服务模 型抽象了各种业务的访问频率限制逻辑，记录各个键值对特定业务的访问间隔和访问时间，通过频率约束算法，为系统公共接口提供访问频率约束依据，使得公共接 口可以对外界请求做出拒绝，消除了因接口过调用而带来的系统安全隐患，提高了系统的服务质量以及接口调用的有效性。


关键字：访问频率限制； MMAP集群；泛型键值索引



1.引言
对于大型开放平台，其公开的服务接口会被外界频繁调用，在不加任何访问频率的控制策略，这些接口甚至可能会被过度调用。给系统带来额外的负担。
过度调用，会导致两方面的后果：接口调用者通过对服务接口的多次调用间接获取系统安全信息，对系统造成隐患，常见的有：短时间内对登陆服务接口，通过枚举 组合，破解用户系统密码。另一方面，因为用户个体数量庞大，单个用户对接口大量的调用，会影响其他用户的服务质量，降低系统的有效负荷。



    用户访问数达到一定量级的系统平台均会遇到上述问题，并各自都有相应的解决方法。但现成的方法是，把访问限制功能作为独立的模块，系统内部需要使用此功能 的业务，就把该模块的拷贝纳入作为业务的子模块。这种系统组织方式既不利于维护，也不利于管理。而且访问约束所适用的类型往往是固定的，不易于扩展。用户 访问数据的存储方面，已有的方式主要分两种：客户端记录，或在服务端用数据库存储。前者的访问数据可能被篡改，有安全隐患；作为一种基础功能模块，后者的 做法代价较为昂贵，可能会占用大量的数据库连接，降低业务处理能力。



    针对上述问题，本文提出一种轻型的访问频率限制服务模型(Access Frequency Restrict Service Model, AFRSM)。此模型本身是一种面向平台内部的私有服务接口。系统边界以内的一切需要进行访问频率限制的模块和对外服务接口均可通过简单的协议共同使用此 服务(Frequency Restrict Service, FRS)。最终达到统一管理和使用访问频率限制服务的目的。


2.FRSM概述
2.1 架构
频率限制服务(Frequency Restrict Service, FRS)作为CGI、Web-Service等公共服务接口的依赖服务，自身对性能有较高的要求。在设计模型时我们偏重其并发处理能力以及轻型的数据存储。
FRS由三大块组成：微服务器框架、MMAP文件群以及一组配置文件。其中服务器我们采用了并发度较高的epoll模型，除守护进程外还可配置n个子进程 进一步增加其并发性能。服务只处理两种类型的请求:Query和Update，分别对应FRS的查询接口和更新接口。公共服务(记为PS)通过FRS的查 询接口可以获知：当前用户/当前IP是否仍对于该服务(PS)有使用权，如有权使用则表示该用户在服务(PS)中没有被限制；反之，则表示该用户在服务 (PS)中已被约束。



在FRS的核心处理模块中，包含了一些核心算法，用以访问和更新MMAP文件群。
Config-Cache是FRS的重要组成部分之一，在守护进程启动时，指定配置文件内容机会被缓存在中，之后每次访问配置文件实际上都会在内存中命中 需获取的配置项。配置文件在此分两种类型：(1)服务器相关的配置(srv.xml)，用于指定服务器的子进程数，所绑定的主机端口等；(2)业务配置 (map.xml)，用于注册各个业务的频率限制细则：业务标识、时间间隔、间隔内最大访问次数。



2.2协议
FRS采用TCP协议，并在此基础之上构建应用层协议。由于FRS是内部服务，不对外公开，因此不存在数据包的保密问题；同时FRS属于轻型服务，在一次服务请求过程中不会传输过多数据，因此不需要考虑数据包压缩的问题。应用层协议的构建原则是:简单并易于扩展。
HTTP-XML协议是我们所采用的应用层协议。即，使用HTTP头描述数据包体的长度、请求命令类型等信息。具体请求/响应数据则采用XML协议描述，以便在此基础上进行扩展修改。



2.3 部署与使用
FRS作为一种内部服务，其使用者是位于系统最外层的CGI、Web-Service、其他Server等公开服务接口。通用的HTTP-XML协议使得其它服务的逻辑中可以很方便实现对FRS的调用。
FRS的客户端使用模式相对固定，主要分=两个步骤: a. Query, b. Update.
当且仅当key在服务(BizID)中没有被约束，调用者key才能继续使用该业务，并在使用完毕后，必须更新记录key对这次业务的使用情况
4 FRS使用模式
由于从步骤(02)开始需要依赖步骤(01)的结果，步骤(01)必须使用同步模式请求FRS。如该业务采用异步I/O模型[3]的可能在此进行特殊处理，采取局部的同步请求。



3.关键问题分析
3.1 泛型的键值索引
FRS中的访问记录我们采用轻型的MMAP存储，使用时只需把文件数据映射到内存中即可。然而遍历文件找到真正需要的数据是一项耗时的操作，尤其在文件较 大的情况下。为此，本文采用泛型的键值索引，将MMAP文件平均划分为m块存储区域(称为关键节点，key-node)，在目标数据存储或检索之前，预先 为其估算出一个关键节点，使MMAP可以快速定位到该区域。键值不同的数据有可能会被安排在同一个关键节点中，称为估算冲突。冲突的数据会被安排在该关键 节点的一条冲突链上，进行小区域遍历检索。



上侧描述的是单个MMAP文件存储。垂直排布示意的是关键节点，与其紧连的是该节点的冲突链。冲突链是有长度限制的，因为m=1的极端情况下，冲突 链将占满整个文件，检索算法会退化为文件遍历检索。较为理想的情况是尽量减少冲突链的长度，尽可能一次命中。当某条冲突链用尽的时候，我们需要考虑采用淘 汰算法，将过期的节点抹掉/复用。假定允许的冲突长度为Length conflict (包含关键节点本身)，每个节点存储大小为size node，则可计算出MMAP文件的大小：
size MMAP = size node * Length conflict * m



上述的泛型是指FRS的扩展性。在FRS中通过编程扩展可以支持：以不同数据类型作为索引主键，只要实现该种数据类型的索引估算接口，和比较接口即可。其 中，索引估算接口在知道关键节点总量m的前提下，用来计算关键节点。如：Integer类型的键值可以采用求模运算得到关键节点索引，而String类型 则可以使用现成的Bob Hash算法[5]；而比较接口则是在冲突链上用来进行键值比较，最终定位到目标数据。



MMAP集群由多个同构的MMAP文件构成。它适用于更大数据量存储。假定一个MMAP群当中有n个存储文件。即相当于将数据存储容量扩展了n倍。根据上述说明，可得出总的数据存储大小为
size MMAP = size node * Length conflict * m* n。



总体看来，使用MMAP群模式对数据进行存储检索，实际上使用了2级检索：第一级，索引到文件；第二级，索引到关键节点。
为了使用方便，我们把上述对MMAP的访问步骤封装成一组操作：Init-MMAP、Find-Node、Erase-Node、Update-Node。由于MMAP是多进程共享访问的，因此这些操作（尤其是修改文件数据的操作）都需要使用信号量互斥处理。
Init-MMAP：在守护进程启动时，根据配置文件初始化MMAP/MMAP群的规模。
Create-Node：创建新节点。
Find-Node：找到目标数据节点。
Erase-Node：删除目标节点。通常在淘汰处理时调用。
Update-Node：更新目标数据节点。



3.2 频率限制
频率限制是FRS的核心模块之一。在保证它的有效性的前提下，我们尽量简化了它的实现逻辑。它基于以下简单的数据结构和算法(图6)：
其中Interval和Max分别是某业务ID所对应的时间间隔和限制次数（于配置文件中设定）。这两个参数控制了个体在一个时间段内访问业务的次数。
由算法可知，在Interval时间段内：
第1次访问一个业务时，会通过FRS创建一个新的记录节点（记为node），并把node.Start和node.End更新为当前时间戳，node.Count记为1图6 频率限制算法示意
第n次（n<=Max）访问该业务，则保持node.Start不变，node.End更新为当前时间戳，node.Count记为n；
第n次（n> Max）访问该业务，仍然继续保持node.Start的值不变，node.End更新为当前时间戳，但由于node.Count已到达极限值，访问被拒绝。
当且仅当，在下次访问时满足：解除时间间隔约束(node.end-node.start>=Interval)条件，node.start才会重 置为当前时间戳。回到处理第1次访问逻辑的状态。有两种情况会促使FRS调用Create-Node去创建一个新节点：(1)第一次访问；(2)因为节点 过旧而被淘汰，需要新建。



4.结束语
通过简单的协议和高并发的服务器模型，我们在本文中把访问频率限制功能抽象成一种内部服务接口，并在实现中使用MMAP集群确保了其数据访问存储的轻型 性。在实际应用运营过程中，该服务模型可胜任10,000,000级别日访问量的开放平台，保证了有效的服务质量以及系统安全。实践表明，将平台内部功能 抽象为服务，能提高其应用服用程度，明显降低了功能的维护和扩展成本，具有一定的推广意义。



系统API接口日均调用次数预计1亿次，提供5台服务器。



需要做两种层面的控制：




单IP、单应用每小时调用次数不超过10000次





单应用、单用户、单接口每小时调用次数不超过1000次




要求每次对频控系统的调用的平均响应时间在1ms内。



此外，应用开发者和开放平台所属公司关心调用次数统计数据，如当天某应用所有接口被调用总次数、当天某应用某接口被调用次数、当天某应用用户使用数等。



根据上面，我们可以直接得到系统响应度要求和计算得到系统吞吐量要求，计算公式如下：


频控系统吞吐量（系统每秒能够处理的请求数）
= 80% * 1亿 / (24小时 * 60分钟 * 60秒 * 40% * 5) = 4630tps
80%、40%是指一天中有80%的请求发生在40%的时间内，是粗略的估算值。5是服务器数量。所以得到吞吐量要求为4630tps。前期设计系统时必须参考这些性能指标，后期压测系统时必须根据这些指标设计测试计划。



总结下系统设计需要达成的目标：


请求的响应足够快



能支撑4630tps



占用的CPU、内存等硬件资源不能太夸张（隐性设计目标）



A、数据结构设计初步尝试



计数是典型的key-value数据结构。



可能想到的最简单最自然的方式是下面这样的：


K(app_id, ip) => V(count, startTime, lastTime)
K(app_id, uid, interface_id) => V(count, startTime, lastTime)
startTime记录的是第一次调用的发生时刻，lastTime记录的是最近一次调用的发生时刻，它们用来判断是否应该重置计数值count和是否该拒绝调用。startTime和lastTime都只精确到秒级。



为了节省内存，有必要对key和value做特殊设计，最次的方案当然是直接拼接上面各个字段。但这是非常不合理的，我们来简单估算下：


假设应用有10,000个，平均每个应用的用户数为100,000，接口数为50，独立访问IP地址为1,000,000，那么数据项总共为：



10,000 * 1,000,000 + 10,000 * 100,000 * 50 = 600亿



那么如果每个数据项节省1个字节，能够节省的总数据存储是600G，这是非常可观的。



对于Key，一种更优方案是先拼接Key的字符串，然后MD5得到16位定长字符串作为Key，Key定长的话或许对性能提升也会有一定帮助。



对于Value，count、startTime、lastTime信息不能丢失，那么或许可以考虑下面两种优化方案：


无损压缩Value字符串，比如使用Snappy字符串压缩算法，但压缩和解压缩会带来额外的CPU计算消耗，需要权衡



计数不需要太精确，所以可以牺牲一定精确度换取空间节省。或许我们可以利用CountingBloomFilter？Key需要重新设计为：MD5(app_id, interface_id, 现在距离1970年1月1号的小时数)，Value就是CountingBloomFilter数据结构了，每个调用先根据“app_id、interface_id和现在距离1970年1月1号的小时数”计算16位MD5值，然后得到所属的CountingBloomFilter（如果没有就创建），然后每次先检查是否已达到最大插入次数，如果是则直接返回，如果不是才插入。但是我们别忘了一点：CountingBloomFilter支持最大重复插入次数为15，远小于这里的1000次和10000次。所以很遗憾，CountingBloomFilter不适合这种方案。但这是一个很好的起点，Value的数据结构虽然不能用CountingBloomFilter，但或许可以用其他的优化数据结构，可以参考：



http://blog.csdn.net/hguisu/article/details/7856239



还有一篇文章标题大概是用1k内存来排序亿级数组，找不到了。另外频率控制数据结构模型还可以参考“令牌桶算法”，这里不再深入，详情看：http://en.wikipedia.org/wiki/Token_bucket



B、进一步的数据存储和数据结构设计



考虑到性能要求，肯定需要用到Cache，这里打算选用Redis做Cache。再根据上面的估算，数据项总共有600亿，所以不可能把所有数据项全部放到Redis Cache中（假设每个Cache项占100个字节，估算下需要多少内存，嘿嘿）。



所以我这里采用冷热数据分离方案。有这么三类数据：


冷数据存放在MySQL数据库，按照app_id、uid进行水平Shard



不冷不热数据采用Redis Hash结构存储（这种内存结构更加紧凑）



热数据放在另外的Redis库中，并且“展开式”存储以改善访问性能



先简单说下不冷不热数据的Redis Hash结构，Key是app_id，Field是MD5(ip, interface_id, uid, 现在距离1970年1月1号的小时数)，Value包括两个计数值，即单IP、单应用已调用次数和单应用、单接口、单用户已调用次数。这样设计相当于把本来应该存成两项的数据合并到了一个缓存数据项中。



热数据的所谓“展开式”结构是指将上面两个维度的计数分开，即存成类似下面这两种结构：


K：MD5(app_id, ip, 现在距离1970年1月1号的小时数)，V：count
K：MD5(app_id, interface_id, uid, 现在距离1970年1月1号的小时数)，V：count
这种方案有一个小缺陷，那就是小时区间的划分不太符合用户的直觉。用户的直觉是认为真正第一次调用的时刻才是计时起点。为了满足这个需求，可以回归到A节的数据结构上，变成如下：



K：MD5(app_id, ip)，V：count、startTime、endTime的优化数据结构
K：MD5(app_id, interface_id, uid)，V：count、startTime、endTime的优化数据结构
另外，我后面仔细思考过，不冷不热数据采用Redis Hash和热数据展开存储，是否真的会像我推断的那样展开存储更快？



答案是不一定。因为Redis Hash存储的话，只需要一次Redis访问外加一些解析计算开销，而展开存储需要两次Redis访问。应该不是绝对的，需实际进行测量后才能下结论。



Redis Cache失效时间：



如果采用的数据结构是：


K：MD5(app_id, ip, 现在距离1970年1月1号的小时数)，V：count
K：MD5(app_id, interface_id, uid, 现在距离1970年1月1号的小时数)，V：count
设置缓存失效时间为1小时。



如果采用的数据结构是：


K：MD5(app_id, ip)，V：count、startTime、endTime的优化数据结构
K：MD5(app_id, interface_id, uid)，V：count、startTime、endTime的优化数据结构
那么建议设置缓存永不失效。



冷热数据迁移过程：



数据的冷热一直在发生着改变，所以冷热数据之间需要进行迁移。包括下面四种：


热数据中符合不冷不热数据标准的数据移动到不冷不热数据缓存



将不冷不热数据中符合热数据标准的数据迁移到热数据缓存



将不冷不热数据中符合冷数据标准的数据迁移到MySQL数据库



将MySQL数据库中符合不冷不热数据标准的数据迁移到不冷不热数据缓存



判断冷热的标准可以基于下面一种或者几种：


每天计算一次的历史平均每小时调用次数：单应用、单IP和单应用、单接口、单用户



根据应用的用户量级来区分冷热，也就是区分热应用、不热不冷应用和冷应用。比如某个用户量级超过20万，则该应用下的接口调用数据存为热数据。然后用户量级在5万到20万之间的应用的接口调用数据存为不热不冷数据。至于用户量级低于5万的应用的接口调用数据就存为冷数据了。这种是我比较推荐的方案，因为简单科学，并且只需要控制到应用粒度



基于最近50次调用的平均时间间隔来判断数据冷热，也就是对于每一个数据项还要存储一个它最近50次调用的平均时间间隔（可以借鉴下文提到的滑动窗口算法）



比如我采用第二种划分标准。每天跑一次后台脚本将热应用、不热不冷应用和冷应用区分出来，然后缓存到Redis Cache中（应用数不会太多，百万级就了不起了，所以甚至可以存为Local Cache），类似这样：


app_id => 1或者2或者3 # 1表示是热应用，2表示是不热不冷应用，3表示是冷应用
然后API接口调用时，先根据app_id去这个Cache里找出应用的热度级别，然后就知道该访问前面哪一种存储了。当然可能出现访问未命中的情况，在那种情况需要依次访问热缓存数据 => 不冷不热缓存数据 => 冷数据来确定是因为数据存储中还没有相应的Key或者是还没有及时迁移数据到正确的存储，但那种情况毕竟是很少的。



C、借债机制



比如限制某应用某个接口单用户每小时调用次数不能超过1000次，那么是否严格按照1000次的标准来哪？



答案是否。因为用户调用接口的频率可能并不均匀，比如像下面这样：


第1小时 第2小时 第3小时
1200 700 950
如果严格按照1000次标准来的话，那么第1小时内就有200次调用被拒绝。而如果采用简单的借债机制，即如允许超出1000次往上300次，那么在第一小时内的1200次调用都能成功，但欠下200的债，需要在第2小时偿还，第2小时的调用额度就变成800了，以此类推



D、RPC框架选择



频率控制系统是作为一个独立的系统供其他系统调用，所以需要一个高性能的RPC框架来保证能满足并发要求。选择Thrift，并且采用TNonblockingServer非阻塞模式。


E、滑动窗口算法



我最早听到滑动窗口算法是在大学的计算机网络课程上，它是TCP协议用来保证数据帧顺序和限制流量的一个算法。Storm中貌似也用到了滑动窗口算法来限制调用频率。所以或许可以迁移应用到这个系统的设计中。



滑动窗口算法可以参考：http://blog.csdn.net/thisispan/article/details/7545785


F、服务降级



虽然调用频率控制系统是开放平台中的一个重要系统，但我们也不希望在调用频率控制系统不可用的情况下正常的数据API调用都不可用。所以频控系统应该增加一个服务开关，以实现服务降级。


2014年11月04日22:59更新：另外API接口调用频率控制比较适合用Storm这种实时事件处理框架来处理。



2015年03月10日22:14更新：



数据结构可以用位运算优化，用一个长整数同时包含count、startTime、endTime信息。



此外如果用Redis等带缓存自动失效的系统可以省略“现在距离1970年1月1日的小时数”字段，每次调用都只需要GET-COMPARE-SET。



广告中的频次控制是指控制一个用户最多在指定时间内看到一个广告（或相似广告）的次数，比如广告主可以限制一个用户最多只能一天看到一个广告3次（频次控制也可以让publisher来指定，但本文不考虑publisher）。



本文所说的频次控制不是硬性的，也就是说展示的次数多只会降低相同广告出现的概率，而不是达到一定次数后彻底不出。两者的区别是：前者广告主需要自己去试到底多长的时间段最多出几次合适，比较麻烦，但如果他得到了接近事实的次数，会对他有利。后者是广告主省事了，代价是广告平台只会去优化eCPM，不会去考虑广告主的利益。



引入频次控制有以下优点：





  1. 增加触达受众数量。频次控制可以让更多的受众看到广告。因为频次控制消除了广告主有限的预算总是消耗在了不断地向同一群人展示广告上。




  2. 提高CTR。频次控制是提高广告CTR的有效手段之一。CTR大约在相同广告展示4次之后就很低了，因为用户已经开始对这个广告无视了。




  3. 提高CVR（转化率），与CTR相似，在第一次展示时转化率最高，在展示4-6次后基本无转化。





频次控制原理



技术分享



     见上图，横坐标是展示次数，纵坐标是CPM，曲线是不同的广告（是的，我知道图和我说的不是一回事，但道理和数据真的差不多，因为我没法把公司的数据拿出来讲）。需要注意的是：




  1. 所有的广告都是随着展示次数的增加，CPM减小。




  2. 以蓝线和红线为例，蓝色的广告展示1次的CPM是高于红色的展示一次的CPM，但蓝色展示两次后CPM是低于红色展示一次的CPM。




  3. 每个折线下降的速度是有差异的。





回忆一下公式：CPM = CTR * Bid，eCPM = pCTR * Bid。公式中的Bid是已知且固定的，那么也就是eCPM因为展示次数的变化是因为展示次数影响了pCTR，那么如果基于展示次数对pCTR进行了调整，那么eCPM就更加合理了。



考虑了已经展示的次数对pCTR进行调整，理想情况我们会收获更高的CPM，也就是公司能赚到更多的钱了。（请问你能想象我打这句话时的心情吗？）



技术分享



     实现频次控制后的图应该是这样，紫色的线就是优化后的效果，如果你看不明白，最左边其实少了一根黑化的竖线（我再强调一下，图里的Ad Network把它想成广告，如果你是SSP，那就不要想了）。可以看到紫色的线明显高于蓝线。


频次控制实现



技术分享



     首先基于展示次数对pCTR进行调整是否本身就是pCTR自己的问题，这个我一直有点疑问，展示次数明显可以作为一个特征加入到pCTR的模型中去，但我自己没有试过。但无论展示次数是否作为特征加入，做法都差不多，重要的是如何得到数据。



     数据分两部分，一部分实时数据，另一部分离线数据。需要storm收集实时数据的原因是写hive数据库一般有小时级的延时。KV DB中保存的是聚合了实时数据和离线数据的结果，Key是user，value是[ad_n, count_n]的列表。



     如果是展示次数作为特征放到pCTR学习中，那一切OK了，如果不这样做，那就麻烦了，首先，要得到前面图中的折线，得到展示次数对每个广告pCTR的影响。这里就有问题了，广告曝光不足怎么办？点击就几十个，怎么统计？是维度向上计算推广计划？曝光还不够怎么办？再向上到广告类别？广告主维度？还是更直接点，假装没看到这些数据，直接忽略，目标只去解决有统计意义的广告。



 



想多一点还有更多的问题，人群A可能看过一次不点就不会再点了，人群B看过一次点击的概率并和从未看过点击概率差不多。人群的定义可以是无限多种。另外一个广告被展示到了顶部广告位，和底部广告位，难道都认为被展示了一次？所以我虽然没试过，但我认为展示次数放到pCTR模型里作为一个特征应该是最简单合理的。

Category algorithm