电商课题I：集群环境下业务限流

@郑昀汇总 

创建日期：20120925

关键词索引：

令牌桶算法，漏桶算法

背景：

防注册机、秒杀器或扫号等常见电商流量过滤技术，一般具有如下要求：

1) 高性能。算法简单高效，能对HTTP Requests进行实时在线处理。

2) 分类错误率低。尤其是尽量保证不误杀正常顾客访问。

3) 鲁棒性强。由于双方攻防的对抗性很强，所以算法必须适应各种类型的攻击情形（包括DDoS攻击）。

 

课题1：

对网站某一个URL/表单提交/Ajax请求的访问进行实时检测，找出过于频繁请求的ip，对这些ip的访问频率进行限制。

 

课题2：

对网站开放平台访问，对某一个开放接口的调用，有频次约束，即针对单一App Key不得超过每小时150次调用。

 

翻译一下：

郑昀认为，我们希望限制住的是，在用M度量的任何时间周期内，某一个动作（action）的发生次数N。

 

英文关键词：

rate limiter

rate limiting

throttle limiter

 

要控制的是 Average Rate ：

　　

 

解决思路：

推荐采用令牌桶算法的简易实现。

 

参考资料：

一）

Leaky Bucket，漏桶算法。

     图1.1 漏桶算法示意图

如图1所示，桶本身具有一个恒定的速率往下漏水，而上方时快时慢地会有水进入桶中。当桶还未满时，上方的水可以加入。一旦水满，上方的水就无法加入了。桶满正是算法中的一个的关键触发条件（即流量异常判断成立的条件）。

在桶满水之后，常见的两种处理方式为：

1）暂时拦截住上方水的向下流动，等待桶中的一部分水漏走后，再放行上方水。

2）溢出的上方水直接抛弃。

将水看作网络通信中数据包的抽象，则

方式1起到的效果称为Traffic Shaping，

方式2起到的效果称为Traffic Policing（流量策略）。

由此可见，Traffic Shaping 的核心理念是“等待”，Traffic Policing 的核心理念是“丢弃”。它们是两种常见的流速控制方法。

 

再回顾一下上面的图，可以看出算法只需要两个参数：

1）桶漏水的速率

2）桶的大小

 

算法核心：

利用桶模型判断何时的流量达到异常了

 

外延：

1）流量异常时的处理方法：traffic policing v.s. traffic shaping

2）处理的数据包是否定长：定长 v.s. 变长

3）桶的大小是否等同于每个tick放行的水量：as a queue v.s. as a meter

 

二）

Token Bucket，令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。

漏桶算法不够灵活，因此加入令牌机制。 

基本思想：

令牌桶在 traffic shaping 中的应用思想如下图2.1所示。

    图2.1 CAR和CTS进行流量控制示意图

我们主要关注约定访问速率(CAR)模式，即：

a. 按特定的速率向令牌桶投放令牌；

b.根据预设的匹配规则先对报文进行分类，不符合匹配规则的报文不需要经过令牌桶的处理，直接发送；

c.符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌量按报文的长度做相应的减少；

d.当令牌桶中的令牌不足时，报文将不能被发送（即丢弃），只有等到桶中生成了新的令牌，报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度，达到限制流量的目的。

 

实现：

在数据结构上，没有必要真的实现一个令牌桶。

基于时间的流逝生成受控制数量的令牌即可——以时间的流逝来洗涤旧迹，也就是将两次发包或者收包的间隔和令牌数量联系起来。

 

辅助理解的图形：

 

令牌桶和漏桶算法最主要的差别在于：漏桶算法能够强行限制数据的传输速率，而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。  

在令牌桶算法中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。 

 

三）http://developer.linkedin.com/documents/throttle-limits  这是常见的开放平台限制请求速率的方式。

LinkedIn 比较好的一点就是把Application throttles和Developer throttles分开了。后者是方便联调测试的。

 

四）Better Rate Limiting in .NET [Penned Objects]

 

五）郑昀推荐阅读，Leaky Bucket算法和Token Bucket算法学习笔记，令牌桶算法的应用，QoS令牌桶工作原理，用Netfilter模块实现基于令牌桶的每IP地址流量控制

 

六）Token Bucket 算法的 Python 实现一：kombu.utils.limits.py

代码：https://github.com/celery/kombu/blob/master/kombu/utils/limits.py

对此实现一个较为早期的解释：http://code.activestate.com/recipes/511490/

即，每次外界调用 _get_tokens 方法时，才会查一下需要追加多少token。

class TokenBucket(object):

    def _get_tokens(self):

        if self._tokens < self.capacity:

            now = time.time()

            delta = self.fill_rate * (now - self.timestamp)

            self._tokens = min(self.capacity, self._tokens + delta)

            self.timestamp = now

        return self._tokens

消耗令牌则是通过 consume 函数，指明本次消耗多少张令牌：

    def consume(self, tokens):
        """Consume tokens from the bucket. Returns True if there were
        sufficient tokens otherwise False."""
        if tokens <= self.tokens:
            self._tokens -= tokens
        else:
            return False
        return True

 

七）Rate Limiting 的 memcache-based django decorator 实现：Rate limiting with memcached

代码实现：https://github.com/simonw/ratelimitcache/blob/master/ratelimitcache.py

 

八）Preventing login hacks: Rate limiting using memcachedPython 实现。

它明确提出了防字典攻击防扫号的目的。

既可限制住ip，也可限制住其他字段如 username 。

 

八）Token Bucket 算法的node.js实现

jhurliman/node-rate-limiter 给出了一个非常便于理解的 Token 消耗方式：

下面是 150次请求/次 范例，每1次请求消耗1个token：

var RateLimiter = require('limiter').RateLimiter;
// Allow 150 requests per hour (the Twitter search limit). Also understands
// 'second', 'minute', 'day', or a number of milliseconds
var limiter = new RateLimiter(150, 'hour');

// Throttle requests
limiter.removeTokens(1, function(err, remainingRequests) {
  // err will only be set if we request more than the maximum number of
  // requests we set in the constructor

  // remainingRequests tells us how many additional requests could be sent
  // right this moment
  callMyRequestSendingFunction(...);
});

下面是150KB/sec 范例，每1个字节的传输就消耗1个token：

var BURST_RATE = 1024 * 1024 * 150; // 150KB/sec burst rate
var FILL_RATE = 1024 * 1024 * 50; // 50KB/sec sustained rate
var TokenBucket = require('limiter').TokenBucket;
// We could also pass a parent token bucket in as the last parameter to
// create a hierarchical token bucket
var bucket = new TokenBucket(BURST_RATE, FILL_RATE, 'second', null);

bucket.removeTokens(myData.byteLength, function() {
  sendMyData(myData);
});

 

九）StackOverflow 上的相关讨论：

Throttling method calls to M requests in N seconds

What’s a good rate limiting algorithm?

Best way to implement request throttling in ASP.NET MVC?