API 限流器（二）史上最优秀的访问频率控制器的算法设计详解

项目代码地址： https://github.com/tangaiyun/RedisRateLimiter

算法的核心思想是用redis中的有序集合来记录访问痕迹，集合的key与时间段序号强相关，集合中加入访问痕迹元素时，score值和member都来自于redis的当前精确到微秒的时间。

举例如果限制的时间单位为分钟，限制前缀为一个IP（128.9.9.23）访问频率，则当前有序集合的key的运算规则如下：

求出当前时间所处的分钟序号： long index = Long.parseLong(jedis.time().get(0)) / 60;

当前有序集合的key为：“128.9.9.23”+“：”+index

API 限流器（二）史上最优秀的访问频率控制器的算法设计详解

对于任意一次访问，设当前时间为T，如上图所示，我们要分别统计A、B 集合中一个统计区间的元素之和，则对于B集合来说，我们需要统计B集合中到目前为止所有的访问记录，其实就是B中的所有元素，简单一点的做法就是 redis.zcount(keyB, Long.MIN_VALUE,Long.MAX_VALUE)。对于A集合，统计的时间起始点为当前时间-单位时间, 命名为Ta，则Ta = T - 单位时间（微秒）

则A中满足条件的元素个数为 redis.zcount(keyA, Ta, Long.MAX_VALUE).

如果redis.zcount(keyB, Long.MIN_VALUE,Long.MAX_VALUE) + redis.zcount(keyA, Ta, Long.MAX_VALUE) 小于限制次数，则访问允许通过，并且在当前的集合中调用redis.zadd(key, score, member)。

在调用redis.zadd方法时，key、score、member的参数取值逻辑如下：

1. key的取值上述已有说明。

2. Score的取值为当前时间，精度到微秒，算法为：

private long getRedisTime(Jedis jedis) {
       List<String> jedisTime = jedis.time();
       Long currentSecond = Long.parseLong(jedisTime.get(0));
       Long microSecondsElapseInCurrentSecond = Long.parseLong(jedisTime.get(1));
       Long currentTimeInMicroSecond = currentSecond * 1000000 + microSecondsElapseInCurrentSecond;
       return currentTimeInMicroSecond;

}

因为redis time命令会返回一个包含两个字符串的列表：第一个字符串是当前时间(以 UNIX 时间戳格式表示，是从1970年1月1日（UTC/GMT的午夜）开始所经过的秒数，不考虑闰秒)，而第二个字符串是当前这一秒钟已经逝去的微秒数。

3. member呢？我们如何给member参数传值？我们说了这个是redis管理的有序集合，集合的意思很明确，就是元素不能重复，如果2次访问时间一致，则访问次数会被漏记一次。

这里有个简单可行的方案，就是把member的值设为score的字符串化的表示，为什么可以这么做？因为redis访问实际上是单线程执行的，而且jedis.time()方法返回的时间精度为微秒级，每一个jedis.time()调用耗时应该会超过1微秒，因此我们可以认为每次jedis.time()返回的时间都是唯一且递增的。

代码还有部分逻辑是控制有序集合的TTL的，简单讲TTL = 2 * 单位时间段 + K。

这个频率访问控制器经过笔者多次改善，希望大家多多使用，多提意见。

如第一次读此文章，请参考上篇： https://blog.****.net/suncold/article/details/52278788

联系方式：

email: [email protected]
weixin: 13851932401

API 限流器（二）史上最优秀的访问频率控制器的算法设计详解

相关推荐