[Java知识库] Java 常用限流算法解析

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Java知识库 -> Java 常用限流算法解析 -> 正文阅读

[Java知识库]Java 常用限流算法解析

前言

限流作为高并发场景下抵挡流量洪峰，保护后端服务不被冲垮的一种有效手段，比如大家熟知的限流组件guawa，springcloud中的Hystrix，以及springcloud-alibaba生态中的Sentinel，甚至是基于网关的限流，比如在nginx中配置限流策略，在gateway中配置限流策略等

限流无处不在，既然限流的作用如此强大，那么其底层的实现原理如何呢，说到底，限流的核心是由一系列不同的算法完成，本篇将通过实例来说明下常用的几种限流算法的用法和原理

1、计数器算法

计数器算法限流是采用简单的计数操作，到一段时间之后自动清零，通俗来说，就是系统允许的最大流量是固定的，每过来一个请求分发一个数量的资源处理请求，一旦某个时间段，这批用于处理请求的资源达到了最大值，后续再过来的请求就直接没法处理了

为了模拟计数器的效果，这里我们使用Java中的Semaphore，对Semaphore有过了解的同学应该直到，这个组件可以搭配线程一起使用，可以对并发线程进行处理，

可以理解Semaphore就是一个令牌发放的人员，所有过来的请求都必须从Semaphore中拿到一个资源(线程)，拿到资源的请求才能被处理

/**
 * 计数器限流算法
 */
public class Counter {

    public static void main(String[] args) {
        final Semaphore semaphore = new Semaphore(3);
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                //模拟每隔3秒钟，将计数器清零，在此期间过来的请求可以获取到了其中一个计数器的资源后，处理自己的请求业务
                semaphore.release(3);
                System.out.println();
            }
        }, 3000, 4000, TimeUnit.MILLISECONDS);

        //模拟源源不断的请求
        while (true) {
            try {
                semaphore.acquire();
                System.out.println("获取到计数器，开始处理自己的业务");
            } catch (Exception e) {
                e.printStackTrace();
            }
            System.out.println("finished ~");
        }
    }

}

本段代码的思路就是，模拟使用一个定时调度的线程池，每隔几秒钟重置Semaphore的计数器初始值，Semaphore这里模拟限流中的令牌发放员，持有一定数量的令牌，源源不断的请求过来之后，拿到了令牌的请求就能进行后续处理，否则被丢弃（或者放到队列等待处理）

运行下这段代码，看下效果
在这里插入图片描述
可以发现，由于请求那里使用了while(true)模拟源源不断的请求，但实际上Semaphore手头只有3个，不管过来多少，3个计数器发完了，只能等待下一个轮回

计数器算法优缺点总结

实现非常简单
控制力度太粗，假如1s内限制3次，假如有3次在前100ms内已经用完，那么后面的900ms将只能处于阻塞状态，其他的请求就进不来了，造成服务器资源浪费
实际应用场景较少

2、漏桶算法

可以按照下图理解漏桶算法，如图所示，有一个桶，桶里面源源不断的有一定数量的水滴，以某种速度漏出去，漏出去的水滴可以理解为一个个请求的令牌

漏桶算法是将请求缓存在桶中，使得服务能够匀速处理。超出桶容量的请求将部分丢弃，漏桶算法主要用于保护内部业务处理时，能够稳定有节奏的运行，但缺点是无法根据流量的波动进行动态调整（扩缩容)，可以想象现实中银行的服务窗口办理业务的情况

在这里插入图片描述

编码实现思路

既然请求到来之后，是被匀速处理的，可以考虑使用阻塞队列，而且阻塞队列的容量是固定的
服务端处理请求的能力是有限的，比如每秒只能处理一个请求，那么过来的请求可能有一部分被丢弃而无法处理

下面看具体的代码，参考注释进行理解

/**
 * 漏桶算法模拟
 */
public class LoseBarrel {

    public static void main(String[] args) {
        //相当于是一个容量固定大小的桶，用于存放源源不断过来的请求
        final LinkedBlockingQueue<String> que = new LinkedBlockingQueue(3);
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        //模拟请求的处理，后台每2秒从桶中取一个请求进行处理
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                String v = que.poll();
                System.out.println("当前处理：" + v);
            }
        }, 2000, 2000, TimeUnit.MILLISECONDS);

        //无数个请求不断涌过来，i可以理解为请求的编号
        int taskNum=0;

        while (true){
            taskNum++;
            try {
                System.out.println("put:任务"+taskNum);
                //等待1s如果进不了桶，就溢出丢弃
                que.offer("任务" + taskNum,1000,TimeUnit.MILLISECONDS);
            }catch (Exception e){
                e.printStackTrace();
            }
        }

    }
}

在这里插入图片描述

从运行代码的效果来看，由于请求的速度非常快，是不间断的过来的，但是过来的请求要先放入队列，等待调度器从队列中取出请求进行处理，事实上，处理请求的能力比请求的速度要慢，因此有一部分的请求将会被丢弃，正如图中，处理了1，2，3任务之后，中间跳过了4和5，直接从6开始处理

漏桶算法优缺点小结

可以有效抵挡外部的请求洪峰，保护内部服务不会过载
内部服务匀速执行，但无法应对流量洪峰，无法做到弹性处理突发任务
任务超时溢出时被丢弃，粒度较粗，事实上可能更需要缓存队列辅助保持一段时间

关于漏桶算法的实际使用，在Nginx中可以通过相关的配置实现限流，由于Nginx属于网关层，在某些场景下，利用Nginx配置限流策略具有较好的效果，具体配置可以参考：Nginx限流

在这里插入图片描述

3、令牌桶算法

令牌桶算法可认为是漏桶算法的一种升级，它不但可以将流量做一步限制，还能解决漏桶中无法弹性伸缩处理请求的问题，即请求突然的洪峰和低谷。在现实中，类似服务大厅的门口设置门禁卡发放。发放是匀速的，请求较少时，令牌可以缓存起来，供流量爆发时一次性批量获取使用。而内部服务窗口不再设限

令牌桶算法可以参考下图进行理解
在这里插入图片描述

从这个图中可以抽取几点关键信息

有一个不断产生令牌的工厂，用于生产令牌
生成的令牌放到一个令牌桶中，令牌桶容量有限，超出容量的令牌将会被丢弃
后续过来的请求，需要先从令牌中获取令牌，只有那些获取到令牌的请求才能被处理

从这不难发现，令牌桶的好处就是，可以暂存令牌，假如某段时间，密集性的请求涌过来，如果令牌桶中的令牌比较充足，就可以及时应对这段洪峰的请求处理，而不是像漏桶那样直接丢弃

实现思路

1、一个可以存储请求的容器
2、恒速产生令牌
3、模拟正常的速度的请求和洪峰的请求

了解了原理之后，直接上代码，参考注释进行理解

/**
 * 令牌桶算法模拟
 */
public class TokenBarrel {

    public static void main(String[] args) throws Exception {
        //模拟令牌桶，里面可以存储3个请求
        final Semaphore semaphore = new Semaphore(3);
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        //模拟每隔2秒中，向令牌桶中放一个令牌
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                if (semaphore.availablePermits() < 3) {
                    semaphore.release();
                }
                System.out.println("令牌数：" + semaphore.availablePermits());
            }
        }, 1000, 1000, TimeUnit.MILLISECONDS);

        Thread.sleep(50);

        //模拟洪峰5个请求，前3个迅速响应，后两个由于产生令牌的速度是固定的，只能排队等待
        for (int i = 0; i < 5; i++) {
            semaphore.acquire();
            System.out.println("洪峰请求：" + i);
        }

        //模拟日常请求，2s一个
        for (int i = 0; i < 3; i++) {
            Thread.sleep(1200);
            semaphore.acquire();
            System.out.println("日常请求：" + i);
            Thread.sleep(1200);
        }
        //再次洪峰请求
        for (int i = 0; i < 5; i++) {
            semaphore.acquire();
            System.out.println("洪峰请求：" + i);
        }

        //检查令牌桶的数量
        for (int i = 0; i < 5; i++) {
            Thread.sleep(2000);
            System.out.println("令牌剩余：" + semaphore.availablePermits());
        }
    }
}

在这里插入图片描述
下面来分析下执行结果

洪峰0-2迅速被执行，说明桶中暂存了3个令牌，有效应对了洪峰
洪峰3，4被间隔性执行，得到了有效的限流
日常请求被匀速执行，间隔均匀（这里设置了日常请求业务处理需要1.2秒，令牌产生的速度能够满足）
第二波洪峰来临，和第一次一样
所有请求过去后，令牌最终被均匀颁发，积累到3个后不再继续增加

令牌桶由于其优秀的特性，使用的场景较多，比如springcloud中的gateway限流，就有着实际的运用场景，具体使用可以参考小编之前的文章：gateway限流使用

4、滑动窗口算法

滑动窗口可理解为更加细分的计数器算法。前面了解到计数器算法比较粗暴，比如限定了1分钟内的访问次数。

而滑动窗口限流是将1分钟拆分成多个段，不但要求整个1分钟内请求数小于上限，而且要求每个细分的片段内请求数也要小于上限值。相当于将原来的计数周期做了多个片段拆分，更为精细。

在这里插入图片描述
以上图为例进行说明，其核心思想如下所述

将一个大的时间段拆分为多个小的时间段，比如计数器算法中限定1分钟，那么认为1分钟为一个大的滑动时间窗口
对于这个1分钟的时间窗口来说，该算法要求1分钟内请求数不超过100个，即1分钟内的请求总数不超过100个
为了更好的限制细分窗口流量，比如限定1秒或者5秒内的请求次数也不得超过一个数值，比如50个，那么就可以将1分钟划分为12个段，每个段为5秒中，这5秒中逻辑上为一个整体，进行流量数的限制
由于时间窗口是不断往前推进的，因此每个窗口当作一个整体向前推进

有了理论的基础之后，我们很容易想到，可以利用linkedList结合map去实现

在这里插入图片描述
关键实现思路

使用一个linkedlist用于保存每个具体的小分段的时间
每个小分段内，以当前时间为key，当前这一秒的时间内请求次数为value进行记录
需要一个定时任务调度器，不断的将时间窗口以秒为单位，向前推进
需要2个方法，一个是判断每个时间点的请求是否达到给定的上限，另一个判断这段时间内的总的请求数是否达到上限

下面来看具体的代码，结合注释进行理解

/**
 * 滑动时间窗口算法
 */
public class Windows {

    //整个窗口的流量上限，超出会被限流
    final int totalMax = 5;

    //每片的流量上限，超出同样会被拒绝，可设置不同的值，可以和整个窗口限流数不一样，但是不能大于
    final int sliceMax = 5;

    //分多少片，这里指代每个小的分段
    final int slice = 3;

    //窗口，分3段，每段1s，也就是总长度3s
    final LinkedList<Long> linkedList = new LinkedList<>();

    //计数器，每片一个key，可以使用HashMap，这里为控制保持有序性和可读性，采用TreeMap
    Map<Long, AtomicInteger> map = new TreeMap<>();

    //心跳，每1s跳动1次，滑动窗口向前滑动一步，实际业务中可能需要手动控制滑动窗口的时机。
    ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

    //获取key值，这里即是时间戳（秒）
    private Long getKey() {
        return System.currentTimeMillis() / 1000;
    }

    //滑动时间窗口初始化
    public Windows() {
        //初始化窗口，当前时间指向的是最末端，前两片其实是过去的2s
        Long key = getKey();
        for (int i = 0; i < slice; i++) {
            linkedList.addFirst(key - i);
            map.put(key - i, new AtomicInteger(0));
        }

        //启动心跳任务，窗口根据时间，自动向前滑动，每秒1步
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                //队尾添加最新的片
                Long key = getKey();
                linkedList.addLast(key);
                map.put(key, new AtomicInteger());
                //将最老的片移除
                map.remove(linkedList.getFirst());
                linkedList.removeFirst();
                System.out.println("step:" + key + ":" + map);
            }
        }, 1000, 1000, TimeUnit.MILLISECONDS);
    }

    //检查当前时间所在的片是否达到上限
    public boolean checkCurrentSlice() {
        long key = getKey();
        AtomicInteger integer = map.get(key);
        if (integer != null) {
            return integer.get() < sliceMax;
        }
        //默认允许访问
        return true;
    }

    //检查整个窗口所有片的计数之和是否达到上限
    public boolean checkAllCount() {
        return map.values().stream().mapToInt(value -> value.get()).sum() < totalMax;
    }

    //请求来临进行处理
    public void req() {
        Long key = getKey();
        //如果时间窗口未到达当前时间片，稍微等待一下
        // 其实是一个保护措施，放置心跳对滑动窗口的推动滞后于当前请求
        while (linkedList.getLast() < key) {
            try {
                Thread.sleep(200);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        //如果未达到上限，返回ok，计数器加1
        // 如果总的时间窗口或者分段窗口数量任意一项达到上限，拒绝，以达到限流的目的
        // 这里是直接拒绝。也将请求放入缓冲队列暂存
        if (checkCurrentSlice() && checkAllCount()) {
            map.get(key).incrementAndGet();
            System.out.println(key + " = get ok:" + map);
        } else {
            System.out.println(key + " = is rejected:" + map);
        }
    }

    public static void main(String[] args) throws Exception {
        Windows window = new Windows();
        //10个随机的请求，之间有200ms间隔。会造成总数达到上限而被限流
        for (int i = 0; i < 10; i++) {
            Thread.sleep(200);
            window.req();
        }
        Thread.sleep(3000);
        System.out.println();
        System.out.println();
        //模拟突发请求，单个时间分片计数器达到上限被限流
        for (int i = 0; i < 10; i++) {
            window.req();
        }
    }

}

在这里插入图片描述
结合控制台输出结果，下面简单分析下执行的过程