玖叶教程网

前端编程开发入门

2024年09月06日

图解常见的限流算法(计数器、滑动窗口计数、漏桶、令牌桶)

哈喽，大家好呀，我是呼噜噜，好久没有更新文章了，今天我们来聊聊在企业级项目中，常见的几种限流手段的原理及其实现

什么场景需要限流

随着互联网的业务发展，比如秒杀、双十一、618等这些我们耳熟能详，也有被人恶意攻击的场景下，系统往往经受被高并发流量冲垮的风险，这个时候可以采用限流的方式，来保护自身的系统以及下游系统，当然还有其他各种方式手段，比如熔断、降级、隔离等，本文将重点来讲讲限流

限流就是就是对请求或并发数进行限制，通过在一定时间内对请求量进行限制，来达到保护系统正常运行的目的。常见的限流算法，有计数器算法、滑动窗口计数算法、漏桶算法、令牌桶算法

计数器算法

计数器算法，通过计数器在周期内累加访问次数，并规定一个周期(时间窗口)内的系统处理的请求数量(阈值)，当在一个周期内，计数的值达到限流阈值时触发拒绝策略；到下一周期计数器就重置为0，重新开始计数，它是一种简单方便的限流算法

比如我们设置系统的阈值1s中最多请求100次，在计数器算法中，我们需要把时间划分固定大小窗口(所以计数器算法又叫固定窗口算法Fixed Window)，这里我们将1s划分为一个时间窗口；然后用计数器来记录在每个时间窗口的处理的请求数量，如果请求数量超过100次，后续的请求会被直接拒绝，直到1s结束后，重新开始计数

计数器算法优点实现简单, 占用内存小，性能较高，但是有一个缺点，就是临界问题，因为在一个时间窗口中，请求或者流量并不是均匀分布的，比如，在1.9s和2.1s的时间点，分别被人恶意并发请求了100次，也就是说从1.9s开始后的1s时间窗口期间，被瞬间请求了200次已经超过系统的阈值了，即使窗口2和窗口3还是正常的，这样可能会导致系统直接挂掉

这里提供一个简单的demo(Java版，其他语言大家自行改写):

public class MyFixedWindowRateLimiterDemo {
    // 阈值
    private static Integer QPS = 2;
    // 时间窗口（毫秒）
    private static long TIME_WINDOWS = 1000;
    // 计数器
    private static AtomicInteger counter = new AtomicInteger();

    //上一个窗口的开始时间
    private static long START_TIME = System.currentTimeMillis();

    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            counter.set(0);
            START_TIME = System.currentTimeMillis();
        }
        return counter.incrementAndGet() <= QPS;
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

滑动窗口计数算法

滑动窗口算法(Sliding Window)出现于网络协议中传输层，是一种流量控制技术。我们这里对计数器(固定窗口)算法的临界问题，滑动窗口算法进行了改进，不再固定窗口大小，而是将把固定窗口近一步划分成多个小周期，每个周期都记录自己的请求访问次数，随着时间流逝，滑动时间窗口(每次向后移动一周期)，同时删除过期的小周期。每次判断限流时，需要将一个窗口的所有小周期合起来，再与阈值进行比较

举个例子，上图我们将1s时间窗口，划分成5个200ms的小周期，记录每个周期的请求访问次数，这里沿用上一小节的情形在1.9s和2.1s的时间点，分别被人恶意并发请求了100次，当滑动到第5个小周期时，访问量为100次，未达到阈值；而当窗口滑动到第6个小周期时，访问数量变为：200，这个时候会超过阈值，触发拒绝访问的限制

这样就能限制住瞬时流量爆发。如果滑动窗口的单位区间划分越细的话，滑动窗口的滚动就越平滑，限流统计也会越精准。但随着而来的是实现滑动窗口算法，需要更多的存储空间。另外计数器算法实现起来比较简单，滑动窗口则更复杂

这里提供一个笔者感觉非常简单明了的demo，参考于简单的java实现滑动时间窗口限流算法，在此感谢

public class MySlidingWindowRateLimiterDemo {

    /** 队列id和队列的映射关系，队列里面存储的是每一次通过时候的时间戳，这样可以使得程序里有多个限流队列 */
    private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();
    
    //阈值
    private static int QPS = 2;
    //时间窗口总大小（毫秒）
    private static long WindowSize = 10 * 1000;


    /**
     * 滑动时间窗口限流算法
     * 在指定时间窗口，指定限制次数内，是否允许通过
     *
     * @param listId     队列id
     * @param count      限制次数
     * @param timeWindow 时间窗口大小
     * @return 是否允许通过
     */
    public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
        // 获取当前时间
        long nowTime = System.currentTimeMillis();
        // 根据队列id，取出对应的限流队列，若没有则创建
        List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
        // 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
        if (list.size() < count) {
            list.add(0, nowTime);
            return true;
        }

        // 队列已满（达到限制次数），则获取队列中最早添加的时间戳
        Long farTime = list.get(count - 1);
        // 用当前时间戳 减去 最早添加的时间戳
        if (nowTime - farTime <= timeWindow) {
            // 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于count
            // 不允许通过
            return false;
        } else {
            // 若结果大于timeWindow，则说明在timeWindow内，通过的次数小于等于count
            // 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
            list.remove(count - 1);
            list.add(0, nowTime);
            return true;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 20; i++) {
            Thread.sleep(1000);
            LocalTime now = LocalTime.now();
            if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒内，只允许2次通过;自定义限流规则“ip”
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

美中不足的是，在滑动窗口算法，窗口中流量到达阈值时，流量会瞬间切断，而现实中我们还是更希望，让流量跟平滑地放行到系统中，而不是简单粗暴地将其掐断

漏桶算法

我们再来看看漏桶算法Leaky Bucket，是一个非常贴切的比喻，意思是，水(就是请求/流量)从进水口(生产端)进入桶(队列)中，这个桶是漏的(比方说桶底有一个孔)，以一定的速度漏水(消费端不断的在消费队列中的请求)，当水进入桶的速度过大(大于漏水的速度)，会导致桶里的水堆积，当超过桶容量时会溢出来(请求被拒绝)。从而实现网络流量整形和限流的功能

这里漏水的速度其实就是限流的阈值，所谓的阈值，表示在一个单位时间内允许的请求量，比如如QPS为100，说明1秒内系统最多可以消费100个请求。如果生产端的速率超过阈值的话，请求会慢慢堆积，又因为漏桶的容量是固定的，最后会触发拒绝策略(溢出)

漏桶算法它的优点是，实现起来简单，很容易理解。它可以严格限制请求的处理速度，一旦超过该速度就拒绝服务，从而避免网络拥塞和系统过载

但它也有缺点：

  1. 即使没有大流量，也求需要等待漏桶处理完成(流量限制过于严格)，这样就会导致请求处理延迟，不适用于实时性要求很高的场景
  2. 由于它请求的处理速度是固定的，哪怕网络没有发生拥塞时，也不能使某一个单独的数据流达到生产端的速率，也无法很好地应对突发特性的流量，不能充分利用系统资源

这里提供一个简单的demo(不完整，生产慎用，仅用来演示):

public class MyLeakyBucketRateLimiterDemo {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int rate;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public MyLeakyBucketRateLimiterDemo(int rate, int capacity) {
        this.capacity = capacity;
        this.rate = rate;
    }

    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * rate);
        timeStamp = now;

        // 如果未满，则放行；否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }


    public static void main(String[] args) throws InterruptedException {
        MyLeakyBucketRateLimiterDemo limiterDemo = new MyLeakyBucketRateLimiterDemo(2,5);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(500);
            LocalTime now = LocalTime.now();
            if (!limiterDemo.tryAcquire()) {
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

令牌桶算法

令牌桶算法是漏桶算法的改进版，是网络流量整形(Traffic Shaping)和限流(Rate Limiting)中最常使用的一种算法，它也有一个桶，现在用来存放固定数量的令牌(token)，该算法会以一定的速率(阈值)往桶中发放令牌。每次请求都需要先获取到桶中的一个令牌才能继续执行，请求处理完毕之后将这个令牌丢弃，否则执行拒绝策略(一般有直接拒绝、排队等待 等)；另外放令牌的动作是持续不断进行的，如果桶装满了，则丢弃令牌

表面上看，令牌桶算法和漏桶算法是相反的，一个"进水"，一个是"漏水"。但与漏桶算法实际不同的是，令牌桶不仅能够在限制客户端请求流量速率的同时还能允许一定程度的突发流量。限流和允许瞬时流量其实并不矛盾，在大多数场景中，小批量的突发流量系统是完全可以接受的

因为令牌桶算法中，发放令牌是持续不间断的，当流量一直比较缓和时，桶能够一直持有冗余的令牌，以应对突发流量。如果这时突发大流量，形成流量尖峰，这些请求进来可以直接拿到令牌去执行。只有超越系统阈值的流量，由于未获得桶中的令牌，请求只能等待或者被拒绝，从而维护系统的稳定。

当然相较于漏桶算法，令牌桶算法，实现更为复杂，需要维护令牌的生成和消耗，还需要精确的时间控制(不然会影响限流的效果)，需要消耗更多的内存来储存令牌

这里也提供一下代码实现，单机下推荐使用(或者仿写)Google Guava自带的限流工具类RateLimiter

先引入依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.0-jre</version>
</dependency>

设置发放令牌的速率，然后直接调用tryAcquire，大家感兴趣地可以看看其源码实现

public class MyTokenBucketRateLimiterDemo {
    public static void main(String[] args) throws InterruptedException {
        // 每1s发放5个令牌到桶里
        RateLimiter rateLimiter = RateLimiter.create(5);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(100L);
            if(rateLimiter.tryAcquire()) {
                System.out.println("get one token");
            }else {
                System.out.println("no token");
            }
        }
    }
}

补充：分布式限流

本文上述提供的例子，仅适用于单机，如果是多机部署(分布式)场景下，算法还是可以采用上述算法，需要通过中间件将限流算法的参数信息(比如令牌桶、计数器等)改成存储全局化，比如采用redis+lua的方式实现，或者使用开源工具比如redisson(内部封装了基于Redis的限流)、Sentinel(带有监控监控平台)等

或者我们也可以利用nginx来从上层流量入口进行限流，它提供2个限流模块ngx_http_limit_req_module，ngx_http_limit_conn_module

上述几种限流算法都是业内常见的，各有优劣，我们需要理解每种方案的工作原理和特性，这样可以能更好地根据项目具体的情况和多种因素，选择合适的方案

全文完，感谢您的阅读，点赞收藏在看就是对笔者最好的催更！

我们下期再见~


作者：小牛呼噜噜 ，关注公众号「小牛呼噜噜」，更多高质量好文等你！

标签：luamath 

作者:gojiuye , 分类:技术精选 , 浏览:7 , 评论:0

发表评论:

控制面板
您好，欢迎到访网站！
  查看权限
网站分类
最新留言