Spring Cloud RedisRateLimit限频存在的几个问题

发表于

本文主要讨论Spring Cloud Gateway的基于Redis分布式限频存在的失效/不准确的可能性及解决方法，同时适用于所有参考request_rate_limiter.lua实现的基于redis限频组件.

阅读本文不需要了解Spring Cloud Gateway（下简称SCG）怎么使用或具体实现，本文只是基于限频角度讨论下常规的组件使用问题。
主要讨论SCG提供的基于Redis分布式限频存在的失效/不准确的可能性及解决方法，同时适用于所有参考request_rate_limiter.lua实现的基于redis限频组件，其次也讨论该方案其他不足。如果你对SCG RedisRateLimit有所了解或已知道其存在的几个问题或觉得TLDR;，可以直接跳到本文最后。

SCG RedisRateLimit如何实现

Spring Cloud Gateway定义了RateLimiter接口来达到限频效果，通过RedisRateLimiterFactory生成这个bean，借助于基于spring的各种扩展，我们可以通过诸如：

  • spring 配置/Configuation

  • GatewayRedisAutoConfiguration

    1
    2
    3
    4
    5
    name: RequestRateLimiter
      args:
        key-resolver: "#{@remoteAddrKeyResolver}"
        redis-rate-limiter.replenishRate: 1
        redis-rate-limiter.burstCapacity: 5

  • 注解
    @RateLimiter(base = RateLimiter.Base.IP, path=”/xxx”, permits = 4, timeUnit = TimeUnit.MINUTES)

上面不需要理解，总之，通过上述等，最后生成RedisRateLimiter类型的bean，而限频最终就是通过该bean调用一段 Redis的Lua脚本来实现，该lua脚本基于令牌桶（Token Bucket）算法实现限频限流，支持从服务、用户、IP或自定义等维度限流。
我们来看下基于redis的限频逻辑和SCG的调用逻辑。

简要介绍下脚本的内容

这里lua脚本是本文主要讨论的内容，它位于SCG的spring-cloud-gateway-core模块的META-INF/scripts/request_rate_limiter.lua下面:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
local tokens_key = KEYS[1]
local timestamp_key = KEYS[2]
redis.log(redis.LOG_WARNING, "tokens_key " .. tokens_key)
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)
--redis.log(redis.LOG_WARNING, "rate " .. ARGV[1])
--redis.log(redis.LOG_WARNING, "capacity " .. ARGV[2])
--redis.log(redis.LOG_WARNING, "now " .. ARGV[3])
--redis.log(redis.LOG_WARNING, "requested " .. ARGV[4])
--redis.log(redis.LOG_WARNING, "filltime " .. fill_time)
--redis.log(redis.LOG_WARNING, "ttl " .. ttl)
local last_tokens = tonumber(redis.call("get", tokens_key))
if last_tokens == nil then
  last_tokens = capacity
end
redis.log(redis.LOG_WARNING, "last_tokens " .. last_tokens)
local last_refreshed = tonumber(redis.call("get", timestamp_key))
if last_refreshed == nil then
  last_refreshed = 0
end
redis.log(redis.LOG_WARNING, "last_refreshed " .. last_refreshed)
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
local allowed_num = 0
if allowed then
  new_tokens = filled_tokens - requested
  allowed_num = 1
end
redis.log(redis.LOG_WARNING, "delta " .. delta)
redis.log(redis.LOG_WARNING, "filled_tokens " .. filled_tokens)
redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
--redis.log(redis.LOG_WARNING, "allowed_num " .. allowed_num)
--redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
redis.log(redis.LOG_WARNING, "--------")
redis.call("setex", tokens_key, ttl, new_tokens)
redis.call("setex", timestamp_key, ttl, now)
return { allowed_num, new_tokens }

在介绍下该脚本之前，我们先看下SCG怎么调用的，这里简单贴下代码：

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
32
33
34
35
36
37
38
@ConfigurationProperties("spring.cloud.gateway.redis-rate-limiter")
public class RedisRateLimiter extends AbstractRateLimiter<RedisRateLimiter.Config> implements ApplicationContextAware {
    //......
    /**
     * This uses a basic token bucket algorithm and relies on the fact that Redis scripts
     * execute atomically. No other operations can run between fetching the count and
     * writing the new count.
     */
    @Override
    @SuppressWarnings("unchecked")
    public Mono<Response> isAllowed(String routeId, String id) {
        //...
        // How many requests per second do you want a user to be allowed to do?
        int replenishRate = routeConfig.getReplenishRate();
        // How much bursting do you want to allow?
        int burstCapacity = routeConfig.getBurstCapacity();
        try {
            List<String> keys = getKeys(id);
            // The arguments to the LUA script. time() returns unixtime in seconds.
            List<String> scriptArgs = Arrays.asList(replenishRate + "", burstCapacity + "",
                    Instant.now().getEpochSecond() + "", "1");
            // allowed, tokens_left = redis.eval(SCRIPT, keys, args)
            Flux<List<Long>> flux = this.redisTemplate.execute(this.script, keys, scriptArgs);
            ...
        }
    }
    static List<String> getKeys(String id) {
        // use `{}` around keys to use Redis Key hash tags
        // this allows for using redis cluster
        // Make a unique key per user.
        String prefix = "request_rate_limiter.{" + id;
        // You need two Redis keys for Token Bucket.
        String tokenKey = prefix + "}.tokens";
        String timestampKey = prefix + "}.timestamp";
        return Arrays.asList(tokenKey, timestampKey);
    }
    //......
}

为便于理解，我把大部分代码都省略了，只保留调用部分，如上可看到，isAllowed方法判断是否限频时，通过6个参数调用上文的redis lua脚本，分别是：

  • tokenKey ：限频的key，如 request_rate_limiter.{userId123}
  • timestampKey：限频ke对应的时间戳，request_rate_limiter.{userId123}.timestamp
  • rate：限频的频率，为次每秒
  • capacity：令牌桶算法支持的突发量(burst)
  • now：当前时间（unix Epoch）
  • requested：请求量，(代码写死)统一为一次

其中 tokenKey 就是限频的维度，即是限频是针对用户还是服务等，SCG默认支持的有：General（统一控制，通常是request path）,IP（用户IP）,User（按用户控制），此外也可自定义，诸如上文配置里的 key-resolver。

几个小问题讨论

上面介绍SCG redis限频实现，不过不是必须理解的，上述归纳起来只是要说明一点：SCG redis限频就是通过 Redis Lua脚本实现，上文代码贴出，并且，这段代码也是国内一些公司自研的基于redis Lua实现限频功能的组件常参考的代码。
一段题外话，如果读者可能已经知道限频常用算法分为漏桶(Leaky Bucket)和令牌桶(Token Bucket)，Spring Cloud 定义是该Lua脚本是基于 Token bucket算法实现，这里可以简单了解下，不过笔者认为没必要纠结Leaky Bucket和Token Bucket的区别，事实上guava官方doc/代码没有说自己是Token Bucket实现甚至没有提及，Nginx认为自己是基于Leaky Bucket实现，但核心代码类似上述，Ali Sentinel还认为Guava的实现更接近Leaky，如果你用guava和toekn bucket搜索得到的是中文结果或英文但作者中文名，不过不是本文重点，笔者会在自己的下一篇博客讨论下这个问题，总之不要认为leaky和token是不同的限频/限流算法即可。
好了，看几个小问题：

  • 基于用户维度
    显然这是比较耗费Redis内存的，每个用户都需要一点redis存储和redis TTL数据，这个级别是基于TTl时长的活跃用户级别的，并且如果多个接口都使用限频，那么redis的数据量就是是 M*N 量级了。
    并且，这个限频是基于用户级别限频，不是针对服务限频的，即该维护无法提供系统服务级别本身的限频能力
  • 基于General（path、接口）维度
    该维度限频，可以提供服务级别的限频能力，也是笔者认为大多数微服务里的限频限流模块以及各类容器里的限频限流模块所指代的对象。
    但该脚本实现存在这 热点 数据问题，即无论redis以何种方式部署，最终都会读写tokenKey这个热点数据，也就是最终操作都会聚集到一台redis机器上，其实无论你使用何种实现：Guava的RateLimiter、Bucket4j、Zuul、Ali的Sentinel，或者无论何后端存储（Bucket4j-Jcache、Caffeine、Hazelcast、Redis、RocksDB等，都存在热点问题，而高性能的redis get/set一般在10几万每秒级别，笔者没有测试过，但理论上QPS在10万以内，也就是说无论如何扩容，该接口性能不会超过10万每秒，当然，如果你认为接口限频一定小于这个数值，那么可以忽略。
    我们可以将一个lua function分解成多个的方式避免此问题，笔者在下一篇文章再讨论。
  • 基于IP维度
    这个维度没有服务/业务意义，但是一个适中的力度，当然，如果有人特别需求ip到区域的，笔者推荐 IP2Location Nginx Module，lua可参考。
  • 时间回退问题
    读者是否注意到，计算可用token时，依赖时间，因为token bucket算法就是把时间等价成一段段token均匀放入的。上述lua脚本now参数就是java的unix Epoch time，如果对应机器时间发生校正了（前置/回退），那么上述计算结果就是不准确的。
    事实上，像Nginx实现的leaky bucket限频算法，阿里的Sentinel实现的Token bucket算法，都存在时间回退问题，而Guava的SmoothRatelimiter实现最终用的是nanoTime就不存在这个问题。

最大的问题

以下讨论都是针对 同一个 tokenKey 的情况，即tokenkey为general/api/path时现象明显，uid时存在可能性但不明显。
任何参考上述SCG通过Redis Lua脚本实现的基于Redis分布式限频，最大问题就是限频功能可能会失效。
为什么这么说？
首先，Token Bucket计算依赖于时间，这个时间是脚本参数传入的，假设我们的分布式系统中服务器的时间不一样，比如有一台机器慢了一秒或任何秒数，我相信该现象时间可能极短，但是应该频繁发生。
其次，我们看下有一台时间慢一秒，该lua脚本会发生什么。
这里需要读懂上述lua脚本代码，不过也可只看下面推理即可

  • 假设某次请求时间正常，为21:00:09秒某秒段內，且已达限频临界条件。
  • 此时慢几秒的机器发送请求（21:00:06秒），按上述脚本，则该请求会被限频，但是 redis.call(“setex”, timestamp_key, ttl, now)这句，把当前时间更新为21:00:06秒了
  • 之后其他机器请求进来，时间为21:00:09秒，基于Token bucket算法，以秒为单位时，我们知道当前秒数大于上次秒数时，请求会立即放行，并且可用缓冲permits能达到capacity。

上面分析结论就是 21:00:09秒 限频临界后的请求本该被限频，但是却被放行了，即限频失效。

下面这个脚本可以验证上述想法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/bin/bash 
sleep 4;
date
snds=`date +"%s"`
for i in {1..4} 
do 
    redis-cli --eval ~/git/spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $snds 1;
done
redis-cli --eval ~/git/spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $snds 1;
echo "--reset---"
redis-cli --eval ~/git/spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $((snds-10)) 1
echo "--after reset---"
for i in {1..4} 
do 
    redis-cli --eval ~/git/spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $snds 1; 
done
redis-cli --eval ~/git/spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $snds 1;
date

上述 spc_ratelimit.lua uuid1 uuid1.tmp , 2 4 $snds 1;即是调用该脚本，uuid1即为tokenkey，2是频率，4是capacity，$snds是当前秒，1是请求量，redis ttl时间是4秒，所以开头sleep 4秒来清空历史数据。
开启redis-server，运行上述shell，本人机器输出：

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
➜  2019 sh test.sh
Wed Apr 22 23:59:57 CST 2020
1) (integer) 1
2) (integer) 3
1) (integer) 1
2) (integer) 2
1) (integer) 1
2) (integer) 1
1) (integer) 1
2) (integer) 0
1) (integer) 0
2) (integer) 0
--reset---
1) (integer) 0
2) (integer) 0
--after reset---
1) (integer) 1
2) (integer) 3
1) (integer) 1
2) (integer) 2
1) (integer) 1
2) (integer) 1
1) (integer) 1
2) (integer) 0
1) (integer) 0
2) (integer) 0
Wed Apr 22 23:59:57 CST 2020

可以看到，在调用四次被限频后，通过模拟一次慢10秒（$((snds-10))）的请求调用后，请求又被放行了，即 在 “Wed Apr 22 23:59:57 CST 2020至Wed Apr 22 23:59:57 CST 2020”这段时间內，接口被访问了8次(本该4次)。

解决办法

1，拆分
个人觉得比较好的办法是将一个热点数据拆分成16个或更多，可以提高性能，然后通过设置机器相关的key将同一台机器请求路由至同一台redis，但该方案需要些hash改进，且需要解决分布式调用均衡的问题。
2，改lua脚本
该方法是将 now 这个时间由服务传参方式，改为 lua脚本自己获取时间，lua本身有 os.time 可以获取时间，但是redis安全原因 禁止lua调用系统函数，所以想到了 redis本身有个 time 指令，所以将 request_rate_limiter.lua 脚本里的
local now = tonumber(ARGV[3])
改为
now = tonumber(redis.call(“time”)[1])
即可，上述改完后再次sh test.sh 就会发现限频生效，仅放行四次，但需要指出的是，该改动多了一次redis调用(但无需重新路由)。

需要指出的是，上述改进并非必要，正如 阿里 Sentinel的限频实现所说，只要求保证实现限频的效果，不要求准确性。

update: 关于redis低版本不支持set命令前含有副作用命令，见下一篇文章。

Ref

1.spring-cloud-gateway
2.Sentinel-限流冷启动