这篇“Java常见的限流算法怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“Java常见的限流算法怎么实现”文章吧。
在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩。
限流算法很多,常见的有三类,分别是 计数器算法 、漏桶算法、令牌桶算法 。
(1)计数器:
在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理。
(2)漏桶:
漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时,会丢弃过多的请求)。
(3)令牌桶:
令牌桶的大小固定,令牌的产生速度固定,但是消耗令牌(即请求)速度不固定(可以应对一些某些时间请求过多的情况);每个请求都会从令牌桶中取出令牌,如果没有令牌则丢弃该次请求。
在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理。
举个例子,比如我们规定对于A接口,我们1分钟的访问次数不能超过100次。
那么我们可以这么做:
在一开 始的时候,我们可以设置一个计数器counter,每当一个请求过来的时候,counter就加1,如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内,那么说明请求数过多,拒绝访问;
如果该请求与第一个请求的间隔时间大于1分钟,且counter的值还在限流范围内,那么就重置 counter,就是这么简单粗暴。
代码实现:
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //计数器 限流 public class CounterLimiter { //起始时间 private static long startTime = System.currentTimeMillis(); //时间间隔1000ms private static long interval = 1000; //每个时间间隔内,限制数量 private static long limit = 3; //累加器 private static AtomicLong accumulator = new AtomicLong(); /** * true 代表放行,请求可已通过 * false 代表限制,不让请求通过 */ public static boolean tryAcquire() { long nowTime = System.currentTimeMillis(); //判断是否在上一个时间间隔内 if (nowTime < startTime + interval) { //如果还在上个时间间隔内 long count = accumulator.incrementAndGet(); if (count <= limit) { return true; } else { return false; } } else { //如果不在上一个时间间隔内 synchronized (CounterLimiter.class) { //防止重复初始化 if (nowTime > startTime + interval) { startTime = nowTime; accumulator.set(0); } } //再次进行判断 long count = accumulator.incrementAndGet(); if (count <= limit) { return true; } else { return false; } } } // 测试 public static void main(String[] args) { //线程池,用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为:" + limited.get() + ",通过的次数为:" + (threads * turns - limited.get())); System.out.println("限制的比例为:" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为:" + time + "s"); } }
计数器限流的不足:
这个算法虽然简单,但是存在临界问题,我们看下图:
从上图中我们可以看到,假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么其实这个用户在 1秒里面,瞬间发送了200个请求。
我们刚才规定的是1分钟最多100个请求(规划的吞吐量),也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求, 可以瞬间超过我们的速率限制。
用户有可能通过算法的这个漏洞,瞬间压垮我们的应用。
漏桶算法限流的基本原理为:水(对应请求)从进水口进入到漏桶里,漏桶以一定的速度出水(请求放行),当水流入速度过大,桶内的总水量大于桶容量会直接溢出,请求被拒绝。
大致的漏桶限流规则如下:
(1)进水口(对应客户端请求)以任意速率流入进入漏桶。
(2)漏桶的容量是固定的,出水(放行)速率也是固定的。
(3)漏桶容量是不变的,如果处理速度太慢,桶内水量会超出了桶的容量,则后面流入的水滴会溢出,表示请求拒绝。
⭐漏桶算法其实很简单,可以粗略的认为就是注水漏水过程,往桶中以任意速率流入水,以一定速率流出水,当水超过桶容量(capacity)则丢弃,因为桶容量是不变的,保证了整体的速率。
以一定速率流出水,
削峰: 有大量流量进入时,会发生溢出,从而限流保护服务可用
缓冲: 不至于直接请求到服务器, 缓冲压力
代码实现:
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //漏斗限流 public class LeakBucketLimiter { //桶的大小 private static long capacity = 10; //流出速率,每秒两个 private static long rate = 2; //开始时间 private static long startTime = System.currentTimeMillis(); //桶中剩余的水 private static AtomicLong water = new AtomicLong(); /** * true 代表放行,请求可已通过 * false 代表限制,不让请求通过 */ public synchronized static boolean tryAcquire() { //如果桶的余量问0,直接放行 if (water.get() == 0) { startTime = System.currentTimeMillis(); water.set(1); return true; } //计算从当前时间到开始时间流出的水,和现在桶中剩余的水 //桶中剩余的水 water.set(water.get() - (System.currentTimeMillis() - startTime) / 1000 * rate); //防止出现<0的情况 water.set(Math.max(0, water.get())); //设置新的开始时间 startTime += (System.currentTimeMillis() - startTime) / 1000 * 1000; //如果当前水小于容量,表示可以放行 if (water.get() < capacity) { water.incrementAndGet(); return true; } else { return false; } } // 测试 public static void main(String[] args) { //线程池,用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为:" + limited.get() + ",通过的次数为:" + (threads * turns - limited.get())); System.out.println("限制的比例为:" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为:" + time + "s"); } }
漏桶的不足:
漏桶的出水速度固定,也就是请求放行速度是固定的。
漏桶出口的速度固定,不能灵活的应对后端能力提升。比如,通过动态扩容,后端流量从1000QPS提升到1WQPS,漏桶没有办法。
令牌桶算法中新请求到来时会从桶里拿走一个令牌,如果桶内没有令牌可拿,就拒绝服务。 当然,令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关,时间流逝的时间越长,会不断往桶里加入越多的令牌,如果令牌发放的速度比申请速度快,令牌桶会放满令牌,直到令牌占满整个令牌桶。
令牌桶限流大致的规则如下:
(1)进水口按照某个速度,向桶中放入令牌。
(2)令牌的容量是固定的,但是放行的速度不是固定的,只要桶中还有剩余令牌,一旦请求过来就能申请成功,然后放行。
(3)如果令牌的发放速度,慢于请求到来速度,桶内就无牌可领,请求就会被拒绝。
总之,令牌的发送速率可以设置,从而可以对突发的出口流量进行有效的应对。
代码实现:
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //令牌桶 public class TokenBucketLimiter { //桶的容量 private static long capacity = 10; //放入令牌的速率,每秒2个 private static long rate = 2; //上次放置令牌的时间 private static long lastTime = System.currentTimeMillis(); //桶中令牌的余量 private static AtomicLong tokenNum = new AtomicLong(); /** * true 代表放行,请求可已通过 * false 代表限制,不让请求通过 */ public synchronized static boolean tryAcquire() { //更新桶中剩余令牌的数量 long now = System.currentTimeMillis(); tokenNum.addAndGet((now - lastTime) / 1000 * rate); tokenNum.set(Math.min(capacity, tokenNum.get())); //更新时间 lastTime += (now - lastTime) / 1000 * 1000; //桶中还有令牌就放行 if (tokenNum.get() > 0) { tokenNum.decrementAndGet(); return true; } else { return false; } } //测试 public static void main(String[] args) { //线程池,用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为:" + limited.get() + ",通过的次数为:" + (threads * turns - limited.get())); System.out.println("限制的比例为:" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为:" + time + "s"); } }
令牌桶的好处:
令牌桶的好处之一就是可以方便地应对 突发出口流量(后端能力的提升)。
比如,可以改变令牌的发放速度,算法能按照新的发送速率调大令牌的发放数量,使得出口突发流量能被处理。
以上就是关于“Java常见的限流算法怎么实现”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。