分布式系统频次限制实现

频次限制（rate limiting）是Web系统比较常见的功能，防止用户频繁访问接口，导致系统负载增加而影响服务的质量。这里来介绍在分布式系统中实现一个共享的频次限制服务，且保证接口低时延高访问量。

系统要求

• 针对线上的功能，实现对指定对象有访问频次的限制
• 支持多个客户端访问
• 低延迟
• 承受较大的访问量
• 易于拓展

流程

1. 设置服务频次限制，如针对某个消耗资源很高的API设置1QPS的访问限制，并为单一用户生成访问该API的唯一key，如userA_APIX就是表示userA访问APIX的情况
2. 根据指定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

    // 提示用户操作超过限制
}

设计思路

1. 频次限制应该统一存储
   webserver是任意可拓展个数的服务，一开始，我将ratelimiter的存储放在了各自服务中，导致明明我限制的是整个集群这个API的访问单人不可超过1QPS，如果N个服务，实际上是NQPS。所以这个频次限制需要集中存储，统一整个系统的访问频次。

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

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

实现

最终选择了redis的lua脚本实现了频限功能，既统一了存储，又可以利用redis cluster实现了可拓展的频限服务，以最小的成本实现功能。
我司技术栈是Golang，所以实现了Golang的简单库，逻辑是初始化redis client并将lua脚本上传，在判断是否超过频率限制的时候，使用EVALSHA命令执行。由于逻辑都在redis端，所以客户端实际上代码极少，只要注意redis挂了不影响服务的响应，并且redis重启后保证lua脚本上传等。

lua脚本是来自Stripe公司的一位工程师：

local tokens_key = KEYS[1]
local timestamp_key = KEYS[2]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
local fill_time = capacity/rate
local ttl = math.floor(fill_time*2)
local last_tokens = tonumber(redis.call("get", tokens_key))
if last_tokens == nil then
    last_tokens = capacity
end
local last_refreshed = tonumber(redis.call("get", timestamp_key))
if last_refreshed == nil then
    last_refreshed = 0
end
local delta = math.max(0, now-last_refreshed)
local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
local allowed = filled_tokens >= requested
local new_tokens = filled_tokens
if allowed then
    new_tokens = filled_tokens - requested
end
redis.call("setex", tokens_key, ttl, new_tokens)
redis.call("setex", timestamp_key, ttl, now)
return { allowed, new_tokens }

通过SCRIPT LOAD上传该脚本获得hash，使用EVALSHA <hash> 2 userA_APIX_token userA_APIX_ts 1 1 <now_time> 1调用该脚本，根据返回的allowed决定此次操作是否进行。

benchmark

经过测试，MacBook Pro (Retina, 13-inch, Late 2013), CPU 2.4 GHz Intel Core i5, Memory 8 GB 1600 MHz DDR3上能达到**1w+**QPS。

项目地址

ratelimiter的golang实现，目前该版本暂时支持redis client，为了拓展性，可以将其升级为redis cluster，满足大并发系统的需求。

Recommended Posts(Driven byHexo Recommended Posts plugin)

• Practice datacenter failover in production
• Mit分布式系统课程-Lab2-PartB