分布式系统频次限制实现

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

系统要求

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

流程

  1. 设置服务频次限制,如针对某个消耗资源很高的API设置1QPS的访问限制,并为单一用户生成访问该API的唯一key,如userA_APIX就是表示userA访问APIX的情况
  2. 根据指定key,服务向ratelimiter询问是否允许此次访问

基于令牌桶算法的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 初始换状态
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,并且使用了一些redisWATCH命令实现了CAS(Compare And Set),redis里存了keytokenslastTime,算法逻辑仍然放在client端(也就是那些web server)。
    经过压测,QPS比较低,主要是因为CAS的重试率随着并发量上升不断升高,况且重试过程不断访问redis增加了网络开销,于是考虑如何将逻辑和数据放到一起。

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

实现

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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,满足大并发系统的需求。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×