java限流算法详细

目录
  • 1、场景
  • 2、算法详解
    • 2.1 计数算法
      • 2.1.1 说明
      • 2.1.2 适用场景
      • 2.1.3 代码
    • 2.2 漏桶算法
      • 2.2.1 说明
      • 2.2.2 漏桶算法图示
      • 2.2.3 适用场景
      • 2.2.4 代码
    • 2.3 令牌桶算法
      • 2.3.1 说明
      • 2.3.2 令牌桶算法图示
      • 2.3.3 适用场景
      • 2.3.4 代码
      • 2.3.5 第三方工具类

1、场景

程序中经常需要对接口进行限流,防止访问量太大,导致程序崩溃。

常用的算法有:计数算法、漏桶算法令牌桶算法,最常用的算法是后面两种。

2、算法详解

2.1 计数算法

2.1.1 说明

技术算法,为最简单的限流算法。

核心思想是,每隔一段时间,为计数器设定最大值,请求一次,计数器数量减一,如果计数器为0则拒绝请求

计数器算法图示:

2.1.2 适用场景

虽然此算法是大多数人第一个想到可以限流的算法,但是不推荐使用此算法

因为,此算法有个致命性的问题,如果1秒允许的访问次数为100,前0.99秒内没有任何请求,在最后0.01秒内,出现了200个请求,则这200个请求,都会获取调用许可,给程序带来一次请求的高峰。

如下图所示:计数器算法缺点

2.1.3 代码

import java.time.LocalDateTime;
import java.util.concurrent.TimeUnit;

/**
 * 计数器限流器
 */
public class CountLimiter {
    /**
     * 执行区间(毫秒)
     */
    private int secondMill;

    /**
     * 区间内计数多少次
     */
    private int maxCount;

    /**
     * 当前计数
     */
    private int currentCount;

    /**
     * 上次更新时间(毫秒)
     */
    private long lastUpdateTime;

    public CountLimiter(int second, int count) {
        if (second <= 0 || count <= 0) {
            throw new IllegalArgumentException("second and time must by positive");
        }
        this.secondMill = second * 1000;
        this.maxCount = count;
        this.currentCount = this.maxCount;
        this.lastUpdateTime = System.currentTimeMillis();
    }

    /**
     * 刷新计数器
     */
    private void refreshCount() {
        long now = System.currentTimeMillis();
        if ((now - this.lastUpdateTime) >= secondMill) {
            this.currentCount = maxCount;
            this.lastUpdateTime = now;
        }
    }

    /**
     * 获取授权
     * @return
     */
    public synchronized boolean tryAcquire() {
        // 刷新计数器
        this.refreshCount();
        if ((this.currentCount - 1) >= 0) {
            this.currentCount--;
            return true;
        } else {
            return false;
        }
    }
}

测试方法:

public static void main(String[] args) throws Exception {
    // 1秒限制执行2次
    CountLimiter countLimiter = new CountLimiter(1, 2);
    for (int i = 0; i < 10; i++) {
        System.out.println(LocalDateTime.now() + " " + countLimiter.tryAcquire());
        TimeUnit.MILLISECONDS.sleep(200);
    }
}

执行结果:

2021-05-31T22:01:08.660 true
2021-05-31T22:01:08.868 true
2021-05-31T22:01:09.074 false
2021-05-31T22:01:09.275 false
2021-05-31T22:01:09.485 false
2021-05-31T22:01:09.698 true
2021-05-31T22:01:09.901 true
2021-05-31T22:01:10.104 false
2021-05-31T22:01:10.316 false
2021-05-31T22:01:10.520 false

2.2 漏桶算法

2.2.1 说明

漏桶算法称为leaky bucket,可限制指定时间内的最大流量,如限制60秒内,最多允许100个请求。

其中接受请求的速度是不恒定的(水滴入桶),处理请求的速度是恒定的(水滴出桶)。

算法总体描述如下:

  • 有个固定容量的桶B(指定时间区间X,允许的的最大流量B),如60秒内最多允许100个请求,则B为100,X为60。
  • 有水滴流进来(有请求进来),桶里的水+1。
  • 有水滴流出去(执行请求对应的业务),桶里的水-1(业务方法,真正开始执行=>这是保证漏桶匀速处理业务的根本),水滴流出去的速度是匀速的,流速为B/X(1毫秒100/60次,约1毫秒0.00167次,精度可根据实际情况自己控制)
  • 水桶满了后(60秒内请求达到了100次),水滴无法进入水桶,请求被拒绝

2.2.2 漏桶算法图示

实际开发中,漏桶的使用方式可参考下图:

注意:水滴滴落的时候,才开始执行业务代码,而不是水滴进桶的时候,去执行业务代码。

业务代码的执行方式,个人认为有如下两种:

同步执行:

  • 调用方请求时,如水滴可以放入桶中,调用方所在的线程“阻塞”
  • 水滴漏出时,唤醒调用方线程,调用方线程,执行具体业务

异步执行:

  • 调用方请求时,如水滴可以放入桶中,调用方所在的线程收到响应,方法将异步执行
  • 水滴漏出时,水桶代理执行具体业务

网上很多滴桶的实现代码,在水滴进桶的时候,就去执行业务代码了。这样会导致业务代码,无法匀速地执行,仍然对被调用的接口有一瞬间流量的冲击(和令牌桶算法的最终实现效果一样)。

2.2.3 适用场景

水桶的进水速度是不可控的,有可能一瞬间有大量的请求进入水桶。处理请求的速度是恒定的(滴水的时候处理请求)。

此算法,主要应用于自己的服务,调用外部接口。以均匀的速度调用外部接口,防止对外部接口的压力过大,而影响外部系统的稳定性。如果影响了别人的系统,接口所在公司会来找你喝茶。

漏桶算法,主要用来保护别人的接口。

2.2.4 代码

本实例代码的实现,在水滴滴下,执行具体业务代码时,采用同步执行的方式。即唤醒调用方的线程,让"调用者"所属的线程去执行具体业务代码,去调用接口

import java.net.SocketTimeoutException;
import java.time.LocalDateTime;
import java.util.Queue;
import java.util.UUID;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;

/**
 * 漏桶算法
 */
public class LeakyBucketLimiterUtil {

    /**
     * 漏桶流出速率(多少纳秒执行一次)
     */
    private long outflowRateNanos;

    /**
     * 漏桶容器
     */
    private volatile BlockingQueue<Drip> queue;

    /**
     * 滴水线程
     */
    private Thread outflowThread;

    /**
     * 水滴
     */
    private static class Drip {
        /**
         * 业务主键
         */
        private String busId;

        /**
         * 水滴对应的调用者线程
         */
        private Thread thread;

        public Drip(String busId, Thread thread) {
            this.thread = thread;
        }

        public String getBusId() {
            return this.busId;
        }

        public Thread getThread() {
            return this.thread;
        }
    }

    /**
     * @param second 秒
     * @param time   调用次数
     */
    public LeakyBucketLimiterUtil(int second, int time) {
        if (second <= 0 || time <= 0) {
            throw new IllegalArgumentException("second and time must by positive");
        }

        outflowRateNanos = TimeUnit.SECONDS.toNanos(second) / time;
        queue = new LinkedBlockingQueue<>(time);

        outflowThread = new Thread(() -> {
            while (true) {
                Drip drip = null;
                try {
                    // 阻塞,直到从桶里拿到水滴
                    drip = queue.take();
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (drip != null && drip.getThread() != null) {
                    // 唤醒阻塞的水滴里面的线程
                    LockSupport.unpark(drip.getThread());
                }
                // 休息一段时间,开始下一次滴水
                LockSupport.parkNanos(this, outflowRateNanos);
            }
        }, "漏水线程");
        outflowThread.start();
    }

    /**
     * 业务请求
     *
     * @return
     */
    public boolean acquire(String busId) {
        Thread thread = Thread.currentThread();
        Drip drip = new Drip(busId, thread);
        if (this.queue.offer(drip)) {
            LockSupport.park();
            return true;
        } else {
            return false;
        }
    }
}

测试代码如下:

public static void main(String[] args) throws Exception {
    // 1秒限制执行1次
    LeakyBucketLimiterUtil leakyBucketLimiter = new LeakyBucketLimiterUtil(5, 2);
    for (int i = 0; i < 10; i++) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                String busId = "[业务ID:" + LocalDateTime.now().toString() + "]";
                if (leakyBucketLimiter.acquire(busId)) {
                    System.out.println(LocalDateTime.now() + " " + Thread.currentThread().getName() + ":调用外部接口...成功:" + busId);
                } else {
                    System.out.println(LocalDateTime.now() + " " + Thread.currentThread().getName() + ":调用外部接口...失败:" + busId);
                }
            }
        }, "测试线程-" + i).start();
        TimeUnit.MILLISECONDS.sleep(500);
    }
}

执行结果如下:

2021-05-31T20:52:52.297 测试线程-0:调用外部接口...成功:[业务ID:2021-05-31T20:52:52.295]
2021-05-31T20:52:53.782 测试线程-3:调用外部接口...失败:[业务ID:2021-05-31T20:52:53.782]
2021-05-31T20:52:54.286 测试线程-4:调用外部接口...失败:[业务ID:2021-05-31T20:52:54.286]
2021-05-31T20:52:54.799 测试线程-1:调用外部接口...成功:[业务ID:2021-05-31T20:52:52.761]
2021-05-31T20:52:55.300 测试线程-6:调用外部接口...失败:[业务ID:2021-05-31T20:52:55.300]
2021-05-31T20:52:55.806 测试线程-7:调用外部接口...失败:[业务ID:2021-05-31T20:52:55.806]
2021-05-31T20:52:56.307 测试线程-8:调用外部接口...失败:[业务ID:2021-05-31T20:52:56.307]
2021-05-31T20:52:56.822 测试线程-9:调用外部接口...失败:[业务ID:2021-05-31T20:52:56.822]
2021-05-31T20:52:57.304 测试线程-2:调用外部接口...成功:[业务ID:2021-05-31T20:52:53.271]
2021-05-31T20:52:59.817 测试线程-5:调用外部接口...成功:[业务ID:2021-05-31T20:52:54.799]

2.3 令牌桶算法

2.3.1 说明

令牌桶算法,主要是匀速地增加可用令牌,令牌数因为桶的限制有数量上限。

请求拿到令牌,相当于拿到授权,即可进行相应的业务操作。

2.3.2 令牌桶算法图示

2.3.3 适用场景

和漏桶算法比,有可能导致短时间内的请求数上升(因为拿到令牌后,就可以访问接口,有可能一瞬间将所有令牌拿走),但是不会有计数算法那样高的峰值(因为令牌数量是匀速增加的)。

一般自己调用自己的接口,接口会有一定的伸缩性,令牌桶算法,主要用来保护自己的服务器接口

2.3.4 代码

代码实现如下:

import java.time.LocalDateTime;
import java.util.concurrent.TimeUnit;

/**
 * 令牌桶限流算法
 */
public class TokenBucketLimiter {

    /**
     * 桶的大小
     */
    private double bucketSize;

    /**
     * 桶里的令牌数
     */
    private double tokenCount;

    /**
     * 令牌增加速度(每毫秒)
     */
    private double tokenAddRateMillSecond;

    /**
     * 上次更新时间(毫秒)
     */
    private long lastUpdateTime;

    /**
     * @param second 秒
     * @param time   调用次数
     */
    public TokenBucketLimiter(double second, double time) {
        if (second <= 0 || time <= 0) {
            throw new IllegalArgumentException("second and time must by positive");
        }
        // 桶的大小
        this.bucketSize = time;
        // 桶里的令牌数
        this.tokenCount = this.bucketSize;
        // 令牌增加速度(每毫秒)
        this.tokenAddRateMillSecond = time / second / 1000;
        // 上次更新时间(毫秒)
        this.lastUpdateTime = System.currentTimeMillis();
    }

    /**
     * 刷新桶内令牌数(令牌数不得超过桶的大小)
     * 计算“上次刷新时间”到“当前刷新时间”中间,增加的令牌数
     */
    private void refreshTokenCount() {
        long now = System.currentTimeMillis();
        this.tokenCount = Math.min(this.bucketSize, this.tokenCount + ((now - this.lastUpdateTime) * this.tokenAddRateMillSecond));
        this.lastUpdateTime = now;
    }

    /**
     * 尝试拿到权限
     *
     * @return
     */
    public synchronized boolean tryAcquire() {
        // 刷新桶内令牌数
        this.refreshTokenCount();
        if ((this.tokenCount - 1) >= 0) {
            // 如果桶中有令牌,令牌数-1
            this.tokenCount--;
            return true;
        } else {
            // 桶中已无令牌
            return false;
        }
    }
}

测试代码:

public static void main(String[] args) throws Exception{
    // 2秒执行1次
    TokenBucketLimiter leakyBucketLimiter = new TokenBucketLimiter(2, 1);
    for (int i = 0; i < 10; i++) {
        System.out.println(LocalDateTime.now() + " " + leakyBucketLimiter.tryAcquire());
        TimeUnit.SECONDS.sleep(1);
    }
}

执行结果如下:

2021-05-31T21:38:34.560 true
2021-05-31T21:38:35.582 false
2021-05-31T21:38:36.588 true
2021-05-31T21:38:37.596 false
2021-05-31T21:38:38.608 true
2021-05-31T21:38:39.610 false
2021-05-31T21:38:40.615 true
2021-05-31T21:38:41.627 false
2021-05-31T21:38:42.641 true
2021-05-31T21:38:43.649 false

2.3.5 第三方工具类

可以使用Guava中的RateLimiter来实现令牌桶的限流功能。

maven依赖如下:

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

直接获取令牌(true为获取到令牌,false为获取失败):

RateLimiter rateLimiter = RateLimiter.create(2);
boolean acquireResule = rateLimiter.tryAcquire();
if (acquireResule) {
    System.out.println("获取令牌:成功");
} else {
    System.out.println("获取令牌:失败");
}

等待尝试获取令牌(阻塞当前线程,直到获取到令牌):

RateLimiter rateLimiter = RateLimiter.create(2);
// 阻塞获取令牌
double waitCount = rateLimiter.acquire();
System.out.println("阻塞等待时间:" + waitCount);

以上就是java限流算法详细的详细内容,更多关于java限流算法的资料请关注我们其它相关文章!希望大家以后多多支持我们!

(0)

相关推荐

  • java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • Javaweb应用使用限流处理大量的并发请求详解

    在web应用中,同一时间有大量的客户端请求同时发送到服务器,例如抢购.秒杀等.这个时候如何避免将大量的请求同时发送到业务系统. 第一种方法:在容器中配置最大请求数,如果大于改请求数,则客户端阻塞.该方法有效的阻止了大量的请求同时访问业务系统,但对用户不友好. 第二种方法:使用过滤器,保证一定数量的请求能够正常访问系统,多余的请求先跳转到排队页面,由排队页面定时发起请求.过滤器实现如下: public class ServiceFilter implements Filter { private

  • java 排序算法之冒泡排序

    目录 基本介绍 图解冒泡排序算法的过程 代码实现 演变过程 优化 封装算法 大量数据耗时测试 基本介绍 冒泡排序(Bubble Sorting)(时间复杂度为 O(n²))的基本思想:通过对待排序序列 从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的旗袍一样逐渐向上冒. 优化点:因为排序过程中,个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志判断元素是否进行过交换.从而减

  • Java RPC框架如何实现客户端限流配置

    关键资源 关键资源总是有限的,也就意味着处理能力也有限,所以当面对大量业务时,为了保障自己能够有序的提供服务最经济的做法就是限制同一时间处理的事务数.比如银行的工作人员,一个工作人员同时只能为一个客户服务,来多了根本处理不了,不光是一种浪费而且有可以造成混乱的局面导致工作人员无法工作. 网络请求漏斗 越上层的服务器处理的事务越轻,应付请求的能力也越强,也就意味着同一请求越上层处理时间越短.为了有效的保护下层服务器,就需要对发送给下层的请求量做限流,在下层服务器可接受的范围内.否则就可能会出现下层

  • java限流算法详细

    目录 1.场景 2.算法详解 2.1 计数算法 2.1.1 说明 2.1.2 适用场景 2.1.3 代码 2.2 漏桶算法 2.2.1 说明 2.2.2 漏桶算法图示 2.2.3 适用场景 2.2.4 代码 2.3 令牌桶算法 2.3.1 说明 2.3.2 令牌桶算法图示 2.3.3 适用场景 2.3.4 代码 2.3.5 第三方工具类 1.场景 程序中经常需要对接口进行限流,防止访问量太大,导致程序崩溃. 常用的算法有:计数算法.漏桶算法.令牌桶算法,最常用的算法是后面两种. 2.算法详解 2

  • Java中字符串根据宽度(像素)换行的问题

    目录 Java 字符串根据宽度(像素)换行 根据像素宽度进行换行 Java字符串根据宽度(像素)进行换行及Pdf合并 1.工具类最终版前奏 2.工具类最终版 3.项目中具体使用 3.1 controller层 3.2 serviceImpl层 4.工具类补充 Java 字符串根据宽度(像素)换行 在一些场景下,我们经常会通过判断字符串的长度,比如个数来实现换行,但是中文.英文.数字.其实在展示的时候同样长度的字符串,其实它的宽度是不一样的,这也是们我通俗意义上说的宽度(像素) 根据像素宽度进行换

  • Java实现上传Excel文件并导入数据库

    目录 Java实现上传Excel文件并导出到数据库 1.导入依赖 2.domain 3.utils 4.Controller 5.xml Java实现上传Excel文件并导出到数据库 1.导入依赖 <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi-ooxml</artifactId> <version>4.1.2</version> </de

  • Java 实现滑动时间窗口限流算法的代码

    在网上搜滑动时间窗口限流算法,大多都太复杂了,本人实现了个简单的,先上代码: package cn.dijia478.util; import java.time.LocalTime; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Random; import java.util.concurrent.ConcurrentHashMap; /** * 滑动时间窗

  • Java使用Semaphore对单接口进行限流

    目录 一.实战说明 1.1 效果说明 1.2 核心知识点 二. 环境搭建 三.限流演示 3.1 并发请求工具 3.2 效果示例图 一.实战说明 1.1 效果说明 本篇主要讲如何使用Semaphore对单接口进行限流,例如有如下场景 a. A系统的有a接口主要给B系统调用,现在希望对B系统进行限流,例如处理峰值在100,超过100的请求快速失败 b. 接口作为总闸入口,希望限制所有外来访问,例如某个房间只能同时100个玩家在线,只有前面的处理完后面的才能继续请求 c. 其他类型场景,也就是资源固定

  • 详解Java分布式IP限流和防止恶意IP攻击方案

    前言 限流是分布式系统设计中经常提到的概念,在某些要求不严格的场景下,使用Guava RateLimiter就可以满足.但是Guava RateLimiter只能应用于单进程,多进程间协同控制便无能为力.本文介绍一种简单的处理方式,用于分布式环境下接口调用频次管控. 如何防止恶意IP攻击某些暴露的接口呢(比如某些场景下短信验证码服务)?本文介绍一种本地缓存和分布式缓存集成方式判断远程IP是否为恶意调用接口的IP. 分布式IP限流 思路是使用redis incr命令,完成一段时间内接口请求次数的统

随机推荐