Java高并发系统限流算法的实现

目录
  • 1 概述
  • 2 计数器限流
    • 2.1 概述
    • 2.2 实现
    • 2.3 结果分析
    • 2.4 优缺点
    • 2.5 应用
  • 3 漏桶算法
    • 3.1 概述
    • 3.2 实现
    • 3.3 结果分析
    • 3.4 优缺点
  • 4 令牌桶算法
    • 4.1 概述
    • 4.2 实现
    • 4.3 结果分析
    • 4.4 应用
  • 5 滑动窗口
    • 5.1 概述
    • 5.2 实现
    • 5.3 结果分析
    • 5.4 应用

1 概述

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。限流可以认为服务降级的一种,限流是对系统的一种保护措施。即限制流量请求的频率(每秒处理多少个请求)。一般来说,当请求流量超过系统的瓶颈,则丢弃掉多余的请求流量,保证系统的可用性。即要么不放进来,放进来的就保证提供服务。比如:延迟处理,拒绝处理,或者部分拒绝处理等等。

2 计数器限流

2.1 概述

计数器采用简单的计数操作,到一段时间节点后自动清零

2.2 实现

package com.oldlu.limit;
import java.util.concurrent.*;
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() {
                semaphore.release(3);
            }
        },3000,3000,TimeUnit.MILLISECONDS);
        //模拟无数个请求从天而降
        while (true) {
            try {
                //判断计数器
                semaphore.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //如果准许响应,打印一个ok
            System.out.println("ok");
        }
    }
}

2.3 结果分析

3个ok一组呈现,到下一个计数周期之前被阻断

2.4 优缺点

实现起来非常简单。
控制力度太过于简略,假如1s内限制3次,那么如果3次在前100ms内已经用完,后面的900ms将只能处于阻塞状态,白白浪费掉

2.5 应用

使用计数器限流的场景较少,因为它的处理逻辑不够灵活。最常见的可能在web的登录密码验证,输入错误次数冻结一段时间的场景。如果网站请求使用计数器,那么恶意攻击者前100ms吃掉流量计数,使得后续正常的请求被全部阻断,整个服务很容易被搞垮。

3 漏桶算法

3.1 概述

漏桶算法将请求缓存在桶中,服务流程匀速处理。超出桶容量的部分丢弃。漏桶算法主要用于保护内部的处理业务,保障其稳定有节奏的处理请求,但是无法根据流量的波动弹性调整响应能力。现实中,类似容纳人数有限的服务大厅开启了固定的服务窗口。

3.2 实现

package com.oldlu.limit;
import java.util.concurrent.*;
public class Barrel {
    public static void main(String[] args) {
        //桶,用阻塞队列实现,容量为3
        final LinkedBlockingQueue<Integer> que = new LinkedBlockingQueue(3);
        //定时器,相当于服务的窗口,2s处理一个
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                int v = que.poll();
                System.out.println("处理:"+v);
            }
        },2000,2000,TimeUnit.MILLISECONDS);
        //无数个请求,i 可以理解为请求的编号
        int i=0;
        while (true) {
            i++;
            try {
                System.out.println("put:"+i);
                //如果是put,会一直等待桶中有空闲位置,不会丢弃
//                que.put(i);
                //等待1s如果进不了桶,就溢出丢弃
                que.offer(i,1000,TimeUnit.MILLISECONDS);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}

3.3 结果分析

put任务号按照顺序入桶
执行任务匀速的1s一个被处理
因为桶的容量只有3,所以1-3完美执行,4被溢出丢弃,5正常执行

3.4 优缺点

有效的挡住了外部的请求,保护了内部的服务不会过载
内部服务匀速执行,无法应对流量洪峰,无法做到弹性处理突发任务
任务超时溢出时被丢弃。现实中可能需要缓存队列辅助保持一段时间
5)应用
nginx中的限流是漏桶算法的典型应用,配置案例如下:

http {
    #$binary_remote_addr 表示通过remote_addr这个标识来做key,也就是限制同一客户端ip地址。
#zone=one:10m 表示生成一个大小为10M,名字为one的内存区域,用来存储访问的频次信息。
#rate=1r/s 表示允许相同标识的客户端每秒1次访问
    limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;
    server {
        location /limited/ {
        #zone=one 与上面limit_req_zone 里的name对应。
#burst=5 缓冲区,超过了访问频次限制的请求可以先放到这个缓冲区内,类似代码中的队列长度。
#nodelay 如果设置,超过访问频次而且缓冲区也满了的时候就会直接返回503,如果没有设置,则所有请求
会等待排队,类似代码中的put还是offer。  

        limit_req zone=one burst=5 nodelay;
    }
}

4 令牌桶算法

4.1 概述

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

4.2 实现

package com.oldlu.limit;
import java.util.concurrent.*;
public class Token {
    public static void main(String[] args) throws InterruptedException {
        //令牌桶,信号量实现,容量为3
        final Semaphore semaphore = new Semaphore(3);
        //定时器,1s一个,匀速颁发令牌
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        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(5);
        //模拟洪峰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(1000);
            semaphore.acquire();
            System.out.println("日常:"+i);
            Thread.sleep(1000);
        }
        //再次洪峰
        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());
        }
    }
}

4.3 结果分析

注意结果出现的节奏!
洪峰0-2迅速被执行,说明桶中暂存了3个令牌,有效应对了洪峰
洪峰3,4被间隔性执行,得到了有效的限流
日常请求被匀速执行,间隔均匀
第二波洪峰来临,和第一次一样
请求过去后,令牌最终被均匀颁发,积累到3个后不再上升

4.4 应用

springcloud中gateway可以配置令牌桶实现限流控制,案例如下:

cloud:
    gateway:
      routes:
      ‐ id: limit_route
        uri: http://localhost:8080/test
        filters:
        ‐ name: RequestRateLimiter
          args:
           #限流的key,ipKeyResolver为spring中托管的Bean,需要扩展KeyResolver接口
            key‐resolver: '#{@ipResolver}'
            #令牌桶每秒填充平均速率,相当于代码中的发放频率
            redis‐rate‐limiter.replenishRate: 1
            #令牌桶总容量,相当于代码中,信号量的容量
            redis‐rate‐limiter.burstCapacity: 3

5 滑动窗口

5.1 概述

滑动窗口可以理解为细分之后的计数器,计数器粗暴的限定1分钟内的访问次数,而滑动窗口限流将1分钟拆为多个段,不但要求整个1分钟内请求数小于上限,而且要求每个片段请求数也要小于上限。相当于将原来的计数周期做了多个片段拆分。更为精细。

5.2 实现

package com.oldlu.limit;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
public class Window {
    //整个窗口的流量上限,超出会被限流
    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 Window(){
        //初始化窗口,当前时间指向的是最末端,前两片其实是过去的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+"=ok:"+map);
        }else {
            System.out.println(key+"=reject:"+map);
        }
    }
    public static void main(String[] args) throws InterruptedException {
        Window window = new Window();
        //模拟10个离散的请求,相对之间有200ms间隔。会造成总数达到上限而被限流
        for (int i = 0; i < 10; i++) {
            Thread.sleep(200);
            window.req();
        }
        //等待一下窗口滑动,让各个片的计数器都置零
        Thread.sleep(3000);
        //模拟突发请求,单个片的计数器达到上限而被限流
        System.out.println("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐");
        for (int i = 0; i < 10; i++) {
        window.req();
        }
    }
}

5.3 结果分析

模拟零零散散的请求,会造成每个片里均有计数,总数达到上限后,不再响应,限流生效:

再模拟突发的流量请求,会造成单片流量计数达到上限,不再响应而被限流

5.4 应用

滑动窗口算法,在tcp协议发包过程中被使用。在web现实场景中,可以将流量控制做更细化处理,解决计数器模型控制力度太粗暴的问题。

到此这篇关于Java高并发系统限流算法的应用的文章就介绍到这了,更多相关Java高并发限流算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 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限流算法详细

    目录 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 常见的限流算法详细分析并实现

    目录 为什么要限流 限流算法 计数器限流 漏桶限流 令牌桶限流 为什么要限流 在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩. 限流算法 限流算法很多,常见的有三类,分别是 计数器算法 .漏桶算法.令牌桶算法 . (1)计数器:           在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理. (2)漏桶:           漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时

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

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

  • Java高并发系统限流算法的实现

    目录 1 概述 2 计数器限流 2.1 概述 2.2 实现 2.3 结果分析 2.4 优缺点 2.5 应用 3 漏桶算法 3.1 概述 3.2 实现 3.3 结果分析 3.4 优缺点 4 令牌桶算法 4.1 概述 4.2 实现 4.3 结果分析 4.4 应用 5 滑动窗口 5.1 概述 5.2 实现 5.3 结果分析 5.4 应用 1 概述 在开发高并发系统时有三把利器用来保护系统:缓存.降级和限流.限流可以认为服务降级的一种,限流是对系统的一种保护措施.即限制流量请求的频率(每秒处理多少个请求

  • golang高并发系统限流策略漏桶和令牌桶算法源码剖析

    目录 前言 漏桶算法 样例 源码实现 令牌桶算法 样例 源码剖析 Limit类型 Limiter结构体 Reservation结构体 Limiter消费token limiter归还Token 总结 前言 今天与大家聊一聊高并发系统中的限流技术,限流又称为流量控制,是指限制到达系统的并发请求数,当达到限制条件则可以拒绝请求,可以起到保护下游服务,防止服务过载等作用.常用的限流策略有漏桶算法.令牌桶算法.滑动窗口:下文主要与大家一起分析一下漏桶算法和令牌桶算法,滑动窗口就不在这里这介绍了.好啦,废

  • java分布式面试系统限流最佳实践

    目录 引言 1.面试官: 哪些场景系统使用了限流?为什么要使用限流? 2.面试官: 那你了解哪些常用限流算法? 1.计数器方法: 2.漏斗算法: 3.令牌桶算法: 3.面试官: 那具体这值该如何评估,说到现在我还是不知道限流到底要怎么设置,可以给我一点经验方法吗? 深入分析 使用线程池实现: 借助Guava实现: 总结 引言 前面讲了系统中的降级熔断设计和对 Hystrix 组件的功能了解,关于限流降级还有一个比较重要的知识点就是限流算法. 如果你面试的是电商相关公司,这一块就显得更加重要了,秒

  • Python+redis通过限流保护高并发系统

    保护高并发系统的三大利器:缓存.降级和限流.那什么是限流呢?用我没读过太多书的话来讲,限流就是限制流量.我们都知道服务器的处理能力是有上限的,如果超过了上限继续放任请求进来的话,可能会发生不可控的后果.而通过限流,在请求数量超出阈值的时候就排队等待甚至拒绝服务,就可以使系统在扛不住过高并发的情况下做到有损服务而不是不服务. 举个例子,如各地都出现口罩紧缺的情况,广州政府为了缓解市民买不到口罩的状况,上线了预约服务,只有预约到的市民才能到指定的药店购买少量口罩.这就是生活中限流的情况,说这个也是希

  • 高并发系统的限流详解及实现

    在开发高并发系统时有三把利器用来保护系统:缓存.降级和限流.本文结合作者的一些经验介绍限流的相关概念.算法和常规的实现方式. 缓存 缓存比较好理解,在大型高并发系统中,如果没有缓存数据库将分分钟被爆,系统也会瞬间瘫痪.使用缓存不单单能够提升系统访问速度.提高并发访问量,也是保护数据库.保护系统的有效方式.大型网站一般主要是"读",缓存的使用很容易被想到.在大型"写"系统中,缓存也常常扮演者非常重要的角色.比如累积一些数据批量写入,内存里面的缓存队列(生产消费),以及

  • Java实现5种限流算法及7种限流方式

    目录 前言 1. 限流 2. 固定窗口算法 2.1. 代码实现 3. 滑动窗口算法 3.1. 代码实现 4. 滑动日志算法 4.1. 代码实现 5. 漏桶算法 6. 令牌桶算法 6.1. 代码实现 6.2. 思考 7. Redis 分布式限流 7.1. 固定窗口限流 7.3. 滑动窗口限流 8. 总结 参考 前言 最近几年,随着微服务的流行,服务和服务之间的依赖越来越强,调用关系越来越复杂,服务和服务之间的稳定性越来越重要.在遇到突发的请求量激增,恶意的用户访问,亦或请求频率过高给下游服务带来较

  • java高并发情况下高效的随机数生成器

    前言 在代码中生成随机数,是一个非常常用的功能,并且JDK已经提供了一个现成的Random类来实现它,并且Random类是线程安全的. 下面是Random.next()生成一个随机整数的实现: protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend)

  • java 高并发中volatile的实现原理

    java 高并发中volatile的实现原理 摘要: 在多线程并发编程中synchronized和Volatile都扮演着重要的角色,Volatile是轻量级的synchronized,它在多处理器开发中保证了共享变量的"可见性".可见性的意思是当一个线程修改一个共享变量时,另外一个线程能读到这个修改的值.它在某些情况下比synchronized的开销更小 1. 定义: java编程语言允许线程访问共享变量,为了确保共享变量能被准确和一致的更新,线程应该确保通过排他锁单独获得这个变量.

  • Java高并发BlockingQueue重要的实现类详解

    ArrayBlockingQueue 有界的阻塞队列,内部是一个数组,有边界的意思是:容量是有限的,必须进行初始化,指定它的容量大小,以先进先出的方式存储数据,最新插入的在对尾,最先移除的对象在头部. public class ArrayBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable { /** 队列元素 */ final Object

  • 详解Java高并发编程之AtomicReference

    目录 一.AtomicReference 基本使用 1.1.使用 synchronized 保证线程安全性 二.了解 AtomicReference 2.1.使用 AtomicReference 保证线程安全性 2.2.AtomicReference 源码解析 2.2.1.get and set 2.2.2.lazySet 方法 2.2.3.getAndSet 方法 2.2.4.compareAndSet 方法 2.2.5.weakCompareAndSet 方法 一.AtomicReferen

随机推荐