聊聊系统保护机制-限流

卢利如
背景

限流是保护应用系统的机制之一。它可以防止瞬间的流量爆发,大量的请求进来冲垮我们的应用,比如电商大促一类的场景。

常见算法

目前主要有以下几种限流方式:

  1. 信号量
  2. 计数器
  3. 滑动窗口
  4. 令牌桶算法
  5. 漏桶算法
信号量

信号量实际上就是限制系统的并发量,来达到限流的目的。

JDK从1.5开始,已经内置了信号量的实现类Semaphore

Semaphore需要在创建时,指定permit的数量。

常见的用法是:在方法开始时,调用Semaphore.acquire()或者Semaphore.tryAcquire()来获取permit;并在方法返回前,调用Semaphore.release()来返还permit;

信号量主要存在以下问题:

  1. 在达到permit上限前,系统的qps上升是毫无阻力的,瞬间的qps可以达到极大值。
计数器

计数器的方案比较简单。比如要求限制qps为1000,我们每秒存放一个计数,每当进来一个请求,则计数器+1。当计数器达到上限时,则触发限流。

存在这么一种情况,在第1秒的后半时间内,涌入了大量流量,然后到了第2秒前半时间,又涌入了大量流量。由于从第1秒到第2秒,请求计数是清零的,所以在这瞬间的qps有可能就超过系统的承载。

滑动窗口

滑动窗口本质上也是一种计数器,只不过它的粒度更细。比如限制qps为1000,设定窗口大小为10,则每个窗口的时间间隔为100ms。每次窗口滑动时,重置的是前1s至前900ms之间内的计数,而不是完整的1s。

它仍然没有解决计数器的问题。

漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率。

令牌桶算法

令牌桶算法的原理是,系统以固定的速率往令牌桶中放入令牌;当请求进来时,则从桶中取走令牌;当桶中令牌为空时,触发限流。

令牌桶与漏桶相比,好处在于它支持突发流量。

Guava中的实现

Guava的RateLimiter是基于令牌桶的一种实现。

RateLimiter目前有2种实现:SmoothBurstySmoothWarmingUpSmoothBursty是一种令牌桶的设计,桶的容量为一秒的QPS;SmoothWarmingUp则可看做是一种漏桶设计。

SmoothBursty为例,它最核心的属性有两个:nextFreeTicketMicrosstoredPermitsnextFreeTicketMicros记录下一次能够请求成功的微秒时间错,而storedPermits就是桶中的令牌数。当每次请求时,SmoothBursty会将当前时间与nextFreeTicketMicros作比较,计算在这两个请求时间内积蓄的令牌数,并更新storedPermits,然后将nextFreeTicketMicros的值更新。

SmoothWarmingUp则有些不同,它所允许的最大QPS为实例初始化时指定的QPS,并不允许突发流量,且还有一个特性,可以指定QPS缓慢上升的时间。比如说我们创建这样一个对象:

RateLimiter limiter = RateLimiter.create(10, 2000, TimeUnit.MILLISECONDS);  

这是一个限定QPS为10,预热时间为2秒的SmoothWarmingUp。则QPS会在2秒之内,从冷却期1/3的QPS缓慢上升到1倍QPS。

集群限流

Guava只是作了单机的限流方案,并不支持集群的限流。当然,我们可以根据总体QPS/机器数来做临时方案。不过该方案取决于前端负载均衡的平衡情况,而且当应用增减机器时,需要动态调整该参数,并不十分方便。

我们可以借助于memcache、redis之类的分布式,并参考Guava的实现原理来实现一个分布式限流方案。

以redis为例,需要考虑以下几个问题:

1、我们需要根据redis里的共享数据作一些计算,所以要借助lua脚本来实现。
2、为了实现方案的高可用,所以redis本身需要作高可用。
3、lua脚本要能够支持redis分片。
4、考虑降级方案。在redis master节点宕机,slave节点接替master这段期间内,会导致应用的不可用,所以需要降级。有两种思路,一种是直接放行,基于理由是redis master概率比较低,恰巧这段时间又爆发流量的可能性就更低了;还有一种思路是从集群限流降级为单机限流,比如根据机器的规模,设定降级后单机允许的QPS为集权的1/10、1/100。

lua脚本实现如下(要求redis版本3.2+):

local required_permits = tonumber(ARGV[2]);

local next_free_micros = redis.call('hget',KEYS[1],'next_free_micros');  
if(next_free_micros == false) then  
    next_free_micros = 0;
else  
    next_free_micros = tonumber(next_free_micros);
end;

local time = redis.call('time');  
local now_micros = tonumber(time[1])*1000000 + tonumber(time[2]);

--[[
try aquire  
--]]
if(ARGV[3] ~= nil) then  
    local micros_to_wait = next_free_micros - now_micros;
    if(micros_to_wait > tonumber(ARGV[3])) then
        return micros_to_wait;
    end
end

local stored_permits = redis.call('hget',KEYS[1],'stored_permits');  
if(stored_permits == false) then  
    stored_permits = 0;
else  
    stored_permits = tonumber(stored_permits);
end

local stable_interval_micros = 1000000/tonumber(ARGV[1]);  
local max_stored_permits = tonumber(ARGV[1]);

if(now_micros > next_free_micros) then  
    local new_stored_permits = stored_permits + (now_micros - next_free_micros) / stable_interval_micros;
    if(max_stored_permits < new_stored_permits) then
        stored_permits = max_stored_permits;
    else
        stored_permits = new_stored_permits;
    end
    next_free_micros = now_micros;
end

local moment_available = next_free_micros;  
local stored_permits_to_spend = 0;  
if(stored_permits < required_permits) then  
    stored_permits_to_spend = stored_permits;
else  
    stored_permits_to_spend = required_permits;
end  
local fresh_permits = required_permits - stored_permits_to_spend;  
local wait_micros = fresh_permits * stable_interval_micros;

redis.replicate_commands();  
redis.call('hset',KEYS[1],'stored_permits',stored_permits - stored_permits_to_spend);  
redis.call('hset',KEYS[1],'next_free_micros',next_free_micros + wait_micros);  
redis.call('expire',KEYS[1],10);

return moment_available - now_micros;  

比如QPS为10,则执行:

eval 'lua脚本' 1 '自定义key' 'qps' '请求的令牌数'  

redis将返回获取请求成功后,线程需要等待的微秒数

如果是tryAcquire,则执行:

eval 'lua脚本' 1 '自定义key' 'qps' '请求的令牌数' '最大等待微秒数'  

redis同样返回需要等待的微秒数,将该返回值与最大等待微秒数做比较,如果redis返回的值较大,则说明失败;反之,则是成功,并根据返回值让线程等待。

参考资料
  1. http://blog.csdn.net/zheng0518/article/details/51685895