流量调整和限流技术
copy from http://blog.****.net/glory1234work2115/article/details/51674985
在早期的计算机领域,限流技术(time limiting)被用作控制网络接口收发通信数据的速率。 可以用来优化性能,减少延迟和提高带宽等。 现在在互联网领域,也借鉴了这个概念, 用来为服务控制请求的速率, 如果双十一的限流, 12306的抢票等。 即使在细粒度的软件架构中,也有类似的概念。
两种常用算法
令牌桶(Token Bucket)和漏桶(leaky bucket)是 最常用的两种限流的算法。
漏桶算法
它的主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏桶算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量。 漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶(包缓存)溢出,那么数据包会被丢弃。 用说人话的讲:
漏桶算法思路很简单,水(数据或者请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。
在某些情况下,漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使某一个单独的流突发到端口速率。因此,漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常,漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。
令牌桶算法
令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。 令牌桶的另外一个好处是可以方便的改变速度。 一旦需要提高速率,则按需提高放入桶中的令牌的速率。 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量, 比如华为的专利"采用令牌漏桶进行报文限流的方法"(CN 1536815 A),提供了一种动态计算可用令牌数的方法, 相比其它定时增加令牌的方法, 它只在收到一个报文后,计算该报文与前一报文到来的时间间隔内向令牌漏桶内注入的令牌数, 并计算判断桶内的令牌数是否满足传送该报文的要求。
从最终用户访问安全的角度看,设想有人想暴力碰撞网站的用户密码;或者有人攻击某个很耗费资源的接口;或者有人想从某个接口大量抓取数据。大部分人都知道应该增加 Rate limiting,做请求频率限制。从安全角度,这个可能也是大部分能想到,但不一定去做的薄弱环节。
从整个架构的稳定性角度看,一般 SOA 架构的每个接口的有限资源的情况下,所能提供的单位时间服务能力是有限的。假如超过服务能力,一般会造成整个接口服务停顿,或者应用 Crash,或者带来连锁反应,将延迟传递给服务调用方造成整个系统的服务能力丧失。有必要在服务能力超限的情况下 Fail Fast。
另外,根据排队论,由于 API 接口服务具有延迟随着请求量提升迅速提升的特点,为了保证 SLA 的低延迟,需要控制单位时间的请求量。这也是 Little’s law 所说的。
还有,公开 API 接口服务,Rate limiting 应该是一个必备的功能,否则公开的接口不知道哪一天就会被服务调用方有意无意的打垮。
所以,提供资源能够支撑的服务,将过载请求快速抛弃对整个系统架构的稳定性非常重要。这就要求在应用层实现 Rate limiting 限制。
常见的 Rate limiting 的实现方式
Proxy 层的实现,针对部分 URL 或者 API 接口进行访问频率限制
Nginx 模块
limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s; server { location /search/ { limit_req zone=one burst=5; }
详细参见: ngx_http_limit_req_module
Haproxy 提供的功能
详细参见: Haproxy Rate limit 模块
RateLimiters是令牌桶和漏桶在.NET 中实现。这些策略可用于速率限制请求不同的网站中,后端或 API 调用等场景。
ASP.NET Web API rate limiter for IIS and Owin hosting
基于 Redis 功能的实现
这个在 Redis 官方文档有非常详细的实现。一般适用于所有类型的应用,比如 PHP、Python 等等。Redis 的实现方式可以支持分布式服务的访问频率的集中控制。Redis 的频率限制实现方式还适用于在应用中无法状态保存状态的场景。
网上有众多关于这方面的文章,这里列出了本文参考的一些文档。
- http://en.wikipedia.org/wiki/Token_bucket
- http://en.wikipedia.org/wiki/Leaky_bucket
- http://www.cnblogs.com/LBSer/p/4083131.html
- http://www.cnblogs.com/mushroom/p/4659200.html
- 电商课题I:集群环境下业务限流