常见限流算法与使用redis实现简单的计数限流算法

本文参考资源:

QPS、TPS是什么 - 春眠觉晓 - 博客园

常用限流算法 - 香芋牛奶面包 - 博客园

几种常见的限流算法 - 知乎

Spring Cloud Gateway中的令牌桶限流浅析 | KL博客

《Redis深度历险:核心原理与应用实践》

网站吞吐量指标

网站吞吐量指单位时间内系统处理的请求数量,体现系统的整体处理能力。 可以用请求数/秒,或者页面数/每秒来衡量,也可以用访问人数/天,或者处理的业务数/小时等来衡量。

QPS(Queries Per Second,每秒查询数)是吞吐量的一个常用量化指标,此外还有TPS(Transaction Per Second,每秒事务数)、HPS(每秒 HTTP 请求数)等。

通常就将QPS理解为请求数,强调服务器的处理能力。

常见限流算法

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。限流就是通过限制网站吞吐量,防止系统不被瞬时大流量冲垮。

常见的限流算法有三种:
+ 计数算法(也称时间窗口限流)
+ 漏桶算法
+ 令牌桶算法

计数算法

这种限流算法最简单,也是最容易实现的,通过在单位时间内设置最大访问数就可以达到限流的目的。这个单位时间我们也称作时间窗口,在一个时间窗口内,限制最大的请求数。例如想要限制系统的QPS为60,就可以限制接口在一秒内只能被访问60次即可(设置一个计数器用于计数)。这种算法有一个缺陷,假如在时间窗口的前1%的时间内流量就达到顶峰了,那么在时间窗口内即使还有99%的时间系统能够继续提供服务,还是会被限流算法的这种缺陷阻断在门外,这种缺陷也被称为 “突刺效应”

还有一个临界值问题:假设我们设定1秒内允许通过的请求阈值是200,如果有用户在时间窗口的最后几毫秒发送了200个请求,紧接着又在下一个时间窗口开始时发送了200个请求,那么这个用户其实在一秒内成功请求了400次,显然超过了阈值但并不会被限流。

漏桶算法

关于漏桶算法有一张很经典的图:

常见限流算法与使用redis实现简单的计数限流算法

这张图形象地描述了漏桶算法的原理,活塞流出的水为流入流量,漏桶有一个固定大小,所有请求在这个漏桶中进行排队,而底部匀速流出一定的水,代表放行的流量。如果漏桶已满,还有流量流入,则会拒绝(即溢出)。

因为没有时间窗口的概念,限流较为平滑,它有效的避免了计数器法的“突刺效应”和临界值问题。实现也不复杂,通过固定大小的队列+定时取队列元素的方式即可实现。不过因为漏桶算法限制了流出速率是一个固定常量值,所以漏桶算法不支持出现突发流出流量。但是在实际情况下,流量往往是突发的。 例如漏桶的容积是100,出水速率是10/s,则漏桶为空的时候能承载的最大QPS是100/s,但因为流量通过的速率始终是10/s,无法很快地将这些流量放行,于是QPS很快就又下来了。

常见限流算法与使用redis实现简单的计数限流算法

令牌桶算法

常见限流算法与使用redis实现简单的计数限流算法

令牌桶法也是基于桶的原型,但是和漏桶算法截然不同的是,没有出水口。令牌桶通过令牌的产生速率+令牌桶的容积来控制流量,有效的解决了漏桶效率不高的问题。

在令牌桶算法中,有一个令牌流会向桶中匀速放置令牌,当一个请求过来的时候,可以从令牌桶中取走令牌,拿到令牌的请求即可通行,若桶中没有令牌,则请求需要排队等待,直到取到令牌。 由于令牌桶的令牌是源源不断生成的,当访问量小时,可以留存令牌达到令牌桶的上限,这样当短时间的突发访问量来时,积累的令牌数可以处理这个问题。当访问量持续大量流入时,由于生成令牌的速率是固定的,最后也就变成了类似漏斗算法的固定流量处理。

如,容积为100的桶,令牌产生速率为50/s,那么就代表当桶中令牌已满的时候,最大能够承载100的流量,后面如果流量一直居高不下,也会以每秒50个流量的速度恒速处理请求。令牌桶的这种特性有效的处理了洪峰流量也能做到不被洪峰压垮,是目前限流比较常见的实现方法。比较著名的实现有谷歌guava中的RateLimiter

使用Redis实现简单的计数算法

主要思想是使用Sorted Set的score维护一个滑动时间窗口,每一个请求到来的时候将一个时间窗口之前的请求全部丢弃,看set里面元素的个数。

代码来源:《Redis深度历险:核心原理与应用实践》,我做了一点修改。

import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.jedis.Response;

import java.util.UUID;

public class SimpleRateLimiter {
    private Jedis jedis;

    public SimpleRateLimiter(Jedis jedis) {
        this.jedis = jedis;
    }

    /**
     * @param userId 标识用户
     * @param actionKey 标识处理请求的方法(或服务)
     * @param period 时间窗口的大小,单位为秒
     * @param maxCount 时间窗口内允许的最大请求
     * @return 请求是否放行
     */
    public boolean isActionAllowed(String userId,String actionKey,int period,int maxCount){
        String key = String.format("hist:%s:%s", userId,actionKey);
        //当前毫秒时间戳,作为插入元素的score
        long nowTs = System.currentTimeMillis();
        //使用Pipeline管道化进行Redis请求
        Pipeline pipe = jedis.pipelined();
        pipe.multi();
        //插入元素,score为当前时间戳,value并无具体含义,但注意每次请求必须唯一
        pipe.zadd(key, nowTs, UUID.randomUUID().toString());
        //移除距当前时间一个时间窗口之前的所有元素
        pipe.zremrangeByScore(key, 0, nowTs-period*1000);
        //获取集合中元素数量
        Response<Long> count = pipe.zcard(key);
        //若时间窗口的有效期没有续上,则会从内存中移除,节省存储空间
        pipe.expire(key, period+1);
        pipe.exec();
        pipe.close();
        //获取集合中元素数量是否小于等于允许的最大请求数
        return count.get()<=maxCount;
    }

    public static void main(String[] args) {
        Jedis jedis = new Jedis("192.168.176.128");
        SimpleRateLimiter limiter = new SimpleRateLimiter(jedis);
        //短时间处理20个请求
        for(int i = 0;i<20;i++){
            boolean isAllowed = limiter.isActionAllowed("123","reply" , 1, 10);
            System.out.println("第"+(i+1)+"个请求:"+isAllowed);
        }
    }
}

注意这是一种滑动时间窗口,和我们一开始介绍的时间窗口算法又有一些不同,应当说是计数算法的改进。它的时间窗口不是固定在两个时间点之间的,而是每次请求的时间点向前推了一个时间窗口,避免了临界值问题。

查看输出:

第1个请求:true
第2个请求:true
第3个请求:true
第4个请求:true
第5个请求:true
第6个请求:true
第7个请求:true
第8个请求:true
第9个请求:true
第10个请求:true
第11个请求:false
第12个请求:false
第13个请求:false
第14个请求:false
第15个请求:false
第16个请求:false
第17个请求:false
第18个请求:false
第19个请求:false
第20个请求:false

这里提一下,原书中的代码是将每次请求的时间戳作为插入元素的value,然而由于是Set,元素的值不能重复,很有可能在一毫秒内处理几个请求,这样的话插入的元素会覆盖同一时间戳的元素,导致集合内元素的个数没有增加,最后运行的结果通过的请求数也是大于或等于5的。使用这个实现方式应当避免value重复,我这里使用的UUID,可能有点长了,还可以使用其他方式例如时间戳加随机数,通常来说小概率value重复也是可以忍受的。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%b8%b8%e8%a7%81%e9%99%90%e6%b5%81%e7%ae%97%e6%b3%95%e4%b8%8e%e4%bd%bf%e7%94%a8redis%e5%ae%9e%e7%8e%b0%e7%ae%80%e5%8d%95%e7%9a%84%e8%ae%a1%e6%95%b0%e9%99%90%e6%b5%81%e7%ae%97%e6%b3%95/