精华内容
下载资源
问答
  • 如何实现漏桶算法与令牌桶算法
    2020-12-29 00:34:50

    作者:大数据孟小鹏(Java架构沉思录做了部分修改) 原文:https://blog.csdn.net/mengxpFighting/article/details/79117934

    Java中对于生产者消费者模型,或者小米手机营销(1分钟卖多少台手机)等都存在限流的思想在里面。

    关于限流目前存在两大类:从线程并发数角度(jdk1.5 Semaphore)限流和从速率限流(guava)。

    Semaphore:从线程并发数限流。

    RateLimiter:从速率限流。目前常见的算法是漏桶算法和令牌算法。

    令牌桶算法。相比漏桶算法而言区别在于,令牌桶是会去匀速的生成令牌,拿到令牌才能够进行处理,类似于匀速往桶里放令牌。

    漏桶算法是:生产者消费者模型,生产者往木桶里生产数据,消费者按照预先定义的速度去消费数据。

    应用场景:

    漏桶算法:必须读写分离的情况下,限制读取的速度。

    令牌桶算法:必须读写分离的情况下,限制写的速率。

    实现的方法都是一样的,通过RateLimiter来实现。

    对于多线程场景下,很多时候使用的类都是原子性的,但是由于代码逻辑的原因,也可能发生线程安全问题。

    1. 关于RateLimter和Semphore简单用法

    packageconcurrent;importcom.google.common.util.concurrent.RateLimiter;import java.util.concurrent.*;importjava.util.stream.IntStream;import staticjava.lang.Thread.currentThread;/*** ${DESCRIPTION}

    * 关于限流 目前存在两大类,从线程个数(jdk1.5 Semaphore)和RateLimiter速率(guava)

    * Semaphore:从线程个数限流

    * RateLimiter:从速率限流 目前常见的算法是漏桶算法和令牌算法,下面会具体介绍

    *

    *@authormengxp

    *@version1.0

    * @create 2018-01-15 22:44

    **/

    public classRateLimiterExample {//Guava 0.5的意思是 1秒中0.5次的操作,2秒1次的操作 从速度来限流,从每秒中能够执行的次数来

    private final static RateLimiter limiter=RateLimiter.create(0.5d);//同时只能有三个线程工作 Java1.5 从同时处理的线程个数来限流

    private final static Semaphore sem=new Semaphore(3);private static voidtestSemaphore(){try{

    sem.acquire();

    System.out.println(currentThread().getName()' is doing work...');

    TimeUnit.MILLISECONDS.sleep(ThreadLocalRandom.current().nextInt(10));

    }catch(InterruptedException e) {

    e.printStackTrace();

    }finally{

    sem.release();

    System.out.println(currentThread().getName()' release the semephore..other thread can get and do job');

    }

    }public static voidrunTestSemaphore(){

    ExecutorService service= Executors.newFixedThreadPool(10);

    IntStream.range(0,10).forEach((i)->{//RateLimiterExample::testLimiter 这种写法是创建一个线程

    service.submit(RateLimiterExample::testSemaphore);

    });

    }/*** Guava的RateLimiter*/

    private static voidtestLimiter(){

    System.out.println(currentThread().getName()' waiting 'limiter.acquire());

    }//Guava的RateLimiter

    public static voidrunTestLimiter(){

    ExecutorService service= Executors.newFixedThreadPool(10);

    IntStream.range(0,10).forEach((i)->{//RateLimiterExample::testLimiter 这种写法是创建一个线程

    service.submit(RateLimiterExample::testLimiter);

    });

    }public static voidmain(String[] args) {

    IntStream.range(0,10).forEach((a)-> System.out.println(a));//从0-9//runTestLimiter();

    runTestSemaphore();

    }

    }

    2. 实现漏桶算法

    packageconcurrent.BucketAl;importcom.google.common.util.concurrent.Monitor;importcom.google.common.util.concurrent.RateLimiter;importjava.util.concurrent.ConcurrentLinkedQueue;importjava.util.concurrent.TimeUnit;importjava.util.function.Consumer;import staticjava.lang.Thread.currentThread;/*** ${DESCRIPTION}

    *

    *@authormengxp

    *@version1.0

    * @create 2018-01-20 22:42

    * 实现漏桶算法 实现多线程生产者消费者模型 限流

    **/

    public classBucket {//定义桶的大小

    private final ConcurrentLinkedQueue container=new ConcurrentLinkedQueue<>();private final static int BUCKET_LIMIT=1000;//消费者 不论多少个线程,每秒最大的处理能力是1秒中执行10次

    private final RateLimiter consumerRate=RateLimiter.create(10d);//往桶里面放数据时,确认没有超过桶的最大的容量

    private Monitor offerMonitor=newMonitor();//从桶里消费数据时,桶里必须存在数据

    private Monitor consumerMonitor=newMonitor();/*** 往桶里面写数据

    *@paramdata*/

    public voidsubmit(Integer data){if (offerMonitor.enterIf(offerMonitor.newGuard(()->container.size()

    container.offer(data);

    System.out.println(currentThread()' submit..' data ' container size is :[' container.size() ']');

    }finally{

    offerMonitor.leave();

    }

    }else{//这里时候采用降级策略了。消费速度跟不上产生速度时,而且桶满了,抛出异常//或者存入MQ DB等后续处理

    throw new IllegalStateException(currentThread().getName() 'The bucket is ful..Pls latter can try...');

    }

    }/*** 从桶里面消费数据

    *@paramconsumer*/

    public void takeThenConsumer(Consumerconsumer){if (consumerMonitor.enterIf(consumerMonitor.newGuard(()->!container.isEmpty()))){try{//不打印时 写 consumerRate.acquire();

    System.out.println(currentThread() ' waiting'consumerRate.acquire());

    Integer data=container.poll();//container.peek() 只是去取出来不会删掉

    consumer.accept(data);

    }finally{

    consumerMonitor.leave();

    }

    }else{//当木桶的消费完后,可以消费那些降级存入MQ或者DB里面的数据

    System.out.println('will consumer Data from MQ...');try{

    TimeUnit.SECONDS.sleep(10);

    }catch(InterruptedException e) {

    e.printStackTrace();

    }

    }

    }

    }

    2.1 漏桶算法测试类

    packageconcurrent.BucketAl;importjava.util.concurrent.TimeUnit;importjava.util.concurrent.atomic.AtomicInteger;importjava.util.stream.IntStream;import staticjava.lang.Thread.currentThread;/*** ${DESCRIPTION}

    *

    *@authormengxp

    *@version1.0

    * @create 2018-01-20 23:11

    * 漏桶算法测试

    * 实现漏桶算法 实现多线程生产者消费者模型 限流

    **/

    public classBuckerTest {public static voidmain(String[] args) {final Bucket bucket = newBucket();final AtomicInteger DATA_CREATOR = new AtomicInteger(0);//生产线程 10个线程 每秒提交 50个数据 1/0.2s*10=50个

    IntStream.range(0, 10).forEach(i ->{new Thread(() ->{for(; ; ) {int data =DATA_CREATOR.incrementAndGet();try{

    bucket.submit(data);

    TimeUnit.MILLISECONDS.sleep(200);

    }catch(Exception e) {//对submit时,如果桶满了可能会抛出异常

    if (e instanceofIllegalStateException) {

    System.out.println(e.getMessage());//当满了后,生产线程就休眠1分钟

    try{

    TimeUnit.SECONDS.sleep(60);

    }catch(InterruptedException e1) {

    e1.printStackTrace();

    }

    }

    }

    }

    }).start();

    });//消费线程 采用RateLimiter每秒处理10个 综合的比率是5:1

    IntStream.range(0, 10).forEach(i ->{newThread(

    ()->{for(; ; ) {

    bucket.takeThenConsumer(x->{

    System.out.println(currentThread()'C..'x);

    });

    }

    }

    ).start();

    });

    }

    }

    3. 令牌桶算法

    packageconcurrent.TokenBucket;importcom.google.common.util.concurrent.RateLimiter;importjava.util.concurrent.TimeUnit;importjava.util.concurrent.atomic.AtomicInteger;import staticjava.lang.Thread.currentThread;import staticjava.lang.Thread.interrupted;/*** ${DESCRIPTION}

    *

    *@authormengxp

    *@version1.0

    * @create 2018-01-21 0:18

    * 令牌桶算法。相比漏桶算法而言区别在于,令牌桶是会去匀速的生成令牌,拿到令牌才能够进行处理,类似于匀速往桶里放令牌

    * 漏桶算法是:生产者消费者模型,生产者往木桶里生产数据,消费者按照定义的速度去消费数据

    *

    * 应用场景:

    * 漏桶算法:必须读写分流的情况下,限制读取的速度

    * 令牌桶算法:必须读写分离的情况下,限制写的速率或者小米手机饥饿营销的场景 只卖1分种抢购1000

    *

    * 实现的方法都是一样。RateLimiter来实现

    * 对于多线程问题查找时,很多时候可能使用的类都是原子性的,但是由于代码逻辑的问题,也可能发生线程安全问题

    **/

    public classTokenBuck {//可以使用 AtomicInteger 容量 可以不用Queue实现

    private AtomicInteger phoneNumbers=new AtomicInteger(0);private RateLimiter rateLimiter=RateLimiter.create(20d);//一秒只能执行五次//默认销售500台

    private final static int DEFALUT_LIMIT=500;private final intsaleLimit;public TokenBuck(intsaleLimit) {this.saleLimit =saleLimit;

    }publicTokenBuck() {this(DEFALUT_LIMIT);

    }public intbuy(){//这个check 必须放在success里面做判断,不然会产生线程安全问题(业务引起)//原因当phoneNumbers=99 时 同时存在三个线程进来。虽然phoneNumbers原子性,但是也会发生。如果必须写在这里,在success//里面也需要加上double check

    /*if (phoneNumbers.get()>=saleLimit){

    throw new IllegalStateException('Phone has been sale ' saleLimit ' can not buy more...')

    }*/

    //目前设置超时时间,10秒内没有抢到就抛出异常//这里的TimeOut*Ratelimiter=总数 这里的超时就是让别人抢几秒,所以设置总数也可以由这里的超时和RateLimiter来计算

    boolean success = rateLimiter.tryAcquire(10, TimeUnit.SECONDS);if(success){if (phoneNumbers.get()>=saleLimit){throw new IllegalStateException('Phone has been sale ' saleLimit ' can not buy more...');

    }int phoneNo =phoneNumbers.getAndIncrement();

    System.out.println(currentThread()' user has get :[' phoneNo ']');returnphoneNo;

    }else{//超时后 同一时间,很大的流量来强时,超时快速失败。

    throw new RuntimeException(currentThread() 'has timeOut can try again...');

    }

    }

    }

    3.1 令牌桶算法的测试类

    packageconcurrent.TokenBucket;importjava.util.stream.IntStream;/*** ${DESCRIPTION}

    *

    *@authormengxp

    *@version1.0

    * @create 2018-01-21 0:40

    **/

    public classTokenBuckTest {public static voidmain(String[] args) {final TokenBuck tokenBuck=new TokenBuck(200);

    IntStream.range(0,300).forEach(i->{//目前测试时,让一个线程抢一次,不用循环抢//tokenBuck::buy 这种方式 产生一个Runnable

    newThread(tokenBuck::buy).start();

    });

    }

    }

    更多相关内容
  • ratelimit 基于令牌桶算法和漏桶算法来实现的限速限流,Golang实现
  • 漏桶算法思路很简单,请求先进入到漏桶里,漏桶以固定的速度出水,也就是处理请求,当水加的过快,则会直接溢出,也就是拒绝请求,可以看出漏桶算法能强行限制数据的传输速率。 漏桶算法示意图 但是对于很多场景...

    目录

    1、漏桶算法

    2、令牌桶算法

    3、两种算法的区别

    4、限流工具类RateLimiter

    4.1 RateLimiter demo

    4.2 主要接口


    常用的限流算法有两种:漏桶算法和令牌桶算法。

    1、漏桶算法

    漏桶算法思路很简单,请求先进入到漏桶里,漏桶以固定的速度出水,也就是处理请求,当水加的过快,则会直接溢出,也就是拒绝请求,可以看出漏桶算法能强行限制数据的传输速率

    漏桶算法示意图

    但是对于很多场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。

    2、令牌桶算法

    令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务

    令牌桶算法示意图

    为了更好的理解令牌桶算法,自己造了一个限流算法的简略代码,方便理解。

    创建一个需要执行的任务,使用线程池执行。

    public class TaskRunnable implements Runnable {
        private Integer reqCount;//已使用令牌数量
        public TaskRunnable(int reqCount) {
            this.reqCount = reqCount;
        }
        @Override
        public void run() {
            System.out.println(Thread.currentThread().getName() + "已经执行...,目前已使用令牌数:" + reqCount);
        }
    }

    具体执行逻辑和限流逻辑,//自己造轮子

    public class TokenTask {
        //关键:时间控制周期+令牌桶容量
        static volatile long timeStamp = getNowTime();//令牌桶计时开始
        static AtomicInteger reqCount = new AtomicInteger(0);//统计调用数
        static final int maxReqCount = 5;//时间周期内最大请求数
        static final long effectiveDuration = 1000;//时间控制周期(秒)
        /**
         * 限流逻辑
         * @return
         */
        public static boolean passControl() {
            long now = getNowTime();//程序执行时间
            if (now < (timeStamp + effectiveDuration)) {//在时间控制范围内
                reqCount.getAndIncrement();
                return reqCount.get() <= maxReqCount;//当前时间范围内超过最大请求控制数
            } else {
                timeStamp = now;//超时后重置
                reqCount = new AtomicInteger(1);//占用一个令牌
                return true;
            }
        }
        //获取执行时间
        public static long getNowTime() {
            return System.currentTimeMillis();
        }
    
        public static void main(String[] args) throws InterruptedException {
            ExecutorService executor = Executors.newFixedThreadPool(10);
            for (int i = 0; i < 10; i++) {
                //Thread.sleep(200); //用来模拟令牌周期
                if (passControl()) {//放行
                    executor.execute(new TaskRunnable(reqCount.get()));
                } else {
                    System.out.println("被限流,请稍后访问!");
                }
            }
        }
    }

    限流效果

     注:本算法只是简单模拟了一下限流流程,不能用于生产。

    3、两种算法的区别

    漏桶算法输入的时候请求不固定,但都会在漏桶里边先保存起来(小于漏桶的容量),然后输出的时候采用的是恒定的速率执行请求,有点像队列的先进先出,只是队列中的元素出队的时间间隔一致。

    //有点类似于使用线程池 new SingleThreadExecutor()-单线程串行,newFixedThreadPool() 固定线程

    令牌桶算法跟漏桶算法刚好相反,令牌桶的大小就是接口所能承载的最大访问量,令牌的发放是恒速的,而最终能在某一时间处理的请求数不是恒定的,这取决于单位时间内令牌桶中的令牌数量。

    4、限流工具类RateLimiter

    Google开源工具包Guava提供了限流工具类RateLimiter,该类基于“令牌桶算法”,非常方便使用。RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率。它支持两种获取Permits接口,一种是如果拿不到立刻返回false,一种会阻塞等待一段时间看能不能拿到。

    4.1 RateLimiter demo

    //多任务执行,但每秒执行不超过2个任务
    final RateLimiter rateLimiter = RateLimiter.create(2.0);
    void submitTasks(List<Runnable> tasks, Executor executor) {
        for (Runnable task : tasks) {
            rateLimiter.acquire(); //默认获取1个令牌
            executor.execute(task);
        }
    }
    //以每秒5kb内的速度发送-限制数据包大小
    final RateLimiter rateLimiter = RateLimiter.create(5000.0);
    void submitPacket(byte[] packet) {
        rateLimiter.acquire(packet.length);//获取指定数量的令牌
        networkService.send(packet);
    }
    //以非阻塞的形式达到降级
    if(limiter.tryAcquire()) { //未请求到limiter则立即返回false
        doSomething();
    }else{
        doSomethingElse();
    }

    4.2 主要接口

    RateLimiter其实是一个abstract类,但是它提供了几个static方法用于创建RateLimiter:

    /**
    * 创建一个稳定输出令牌的RateLimiter,保证了平均每秒不超过permitsPerSecond个请求
    * 当请求到来的速度超过了permitsPerSecond,保证每秒只处理permitsPerSecond个请求
    * 当这个RateLimiter使用不足(即请求到来速度小于permitsPerSecond),会囤积最多permitsPerSecond个请求
    */
    public static RateLimiter create(double permitsPerSecond);
    
    /**
    * 创建一个稳定输出令牌的RateLimiter,保证了平均每秒不超过permitsPerSecond个请求
    * 还包含一个热身期(warmup period),热身期内,RateLimiter会平滑的将其释放令牌的速率加大,直到起达到最大速率
    * 同样,如果RateLimiter在热身期没有足够的请求(unused),则起速率会逐渐降低到冷却状态
    *
    * 设计这个的意图是为了满足那种资源提供方需要热身时间,而不是每次访问都能提供稳定速率的服务的情况(比如带缓存服务,需要定期刷新缓存的)
    * 参数warmupPeriod和unit决定了其从冷却状态到达最大速率的时间
    */
    public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit);

    提供了两个获取令牌的方法,不带参数表示获取一个令牌。如果没有令牌则一直等待,返回等待的时间(单位为秒),没有被限流则直接返回0.0

    public double acquire();//默认获取一个令牌
    public double acquire(int permits);//获取指定令牌数

    尝试获取令牌,分为待超时时间和不带超时时间两种:

    //尝试获取一个令牌,立即返回
    public boolean tryAcquire();
    public boolean tryAcquire(int permits);
    //尝试获取permits个令牌,带超时时间
    public boolean tryAcquire(long timeout, TimeUnit unit);
    public boolean tryAcquire(int permits, long timeout, TimeUnit unit);

    下篇这篇文章一点要看:

    https://zhuanlan.zhihu.com/p/60979444

    参考阅读:

    流量控制算法——漏桶算法和令牌桶算法 - 知乎

    展开全文
  • Go rate limiter:漏桶算法速率限制的一个Golang实现
  • 标准令牌漏桶算法

    2014-04-12 11:25:40
    漏桶算法 Leaky Bucket 是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经常使用的一种算法 它的主要目的是控制数据注入到网络的速率 平滑网络上的突发流量 漏桶算法提供了一种机制 通过它 ...
  • 漏桶算法(有点像Kafka,大批量的数据吞吐) 漏桶算法的主要思路为: 在nginx层与controller层加一层(即漏桶层), 用于接收nginx收到的大批量的请求,接收的请求的速度是没有控制的,但是如果超过了漏桶层的最大容量则...

    序言

    此两种算法是服务降级的一种实现.

    常用于限制我们的对外服务的QPS,即控制对外服务在单位时间内所能处理的请求数量.保护我们的服务不会被海量请求给崩盘cuiyaonan2000@163.com

    漏桶算法

    漏桶算法的主要思路为: 

    1. 在nginx层与controller层加一层(即漏桶层),
    2. 用于接收nginx收到的大批量的请求,接收的请求的速度是没有控制的,但是如果超过了漏桶层的最大容量则直接抛弃该请求.
    3. 漏桶层将大批量的请求以特定的速度转发给controller层.(当然漏桶层可以放置在需要的任何位置cuiyaonan2000@163.com)

    更直观的理解可以参考百度百科的截图如下:

    java实现用例

    package nan.yao.cui.others.aboutbuckets;
    
    import java.util.concurrent.atomic.AtomicInteger;
    
    /**
     * @author 崔耀男
     * @des: TODO
     * @date 2021年6月22日 上午11:10:30
     * @package nan.yao.cui.others.aboutbuckets
     */
    public class BucketTest {
    
        // 桶的容量
        private int capacity = 100;
    
        // 木桶剩余的水滴的量(初始化的时候的空的桶)
        private AtomicInteger water = new AtomicInteger(0);
    
        // 水滴的流出的速率,这个可以在 构造方法种设置,比如每秒10个请求.
        private int outRate;
    
        // 记录上次成功接收到请求的时间
        // 用于计算当前系统时间减去上次请求时间 乘以outrate 所处理的请求数.
        private long receivedTime;
    
        // 判断该controller是否能继续接收请求
        // true:表示可以处理该请求
        // false:表示不能处理该请求,漏桶已经满了
        public boolean acquire() {
    
    	// 如果是空桶,则直接将
    	if (water.get() == 0) {
    
    	    receivedTime = System.currentTimeMillis();
    	    water.addAndGet(1);
    	    return true;
    
    	}
    
    	// 先计算下上成功接受到当前时间已经流出的记录数
    	int outNum = ((int) ((System.currentTimeMillis() - receivedTime) / 1000)) * outRate;
    	int waterLeft = water.get() - outNum;
    	water.set(Math.max(0, waterLeft));
    	// 重新更新leakTimeStamp
    	// outNum是否大于0---cuiyaonan2000@163.com
    	if (outNum > 0) {
    	    receivedTime = System.currentTimeMillis();
    	}
    
    	// 尝试加水,并且水还未满
    	if ((water.get()) < capacity) {
    	    water.addAndGet(1);
    	    return true;
    	} else {
    	    // 水满,拒绝加水
    	    return false;
    	}
        }
    
        public static void main(String[] args) {
    	System.out.println((((System.currentTimeMillis() - 100) / 1000) * 2));
    	System.out.println(System.currentTimeMillis() - 100);
    	System.out.println((System.currentTimeMillis() - 100) / 1000);
    
        }
    
    }
    

    令牌桶算法

    令牌桶的算法中心逻辑是: 

    1. 以恒定的速度向令牌桶种添加令牌.当令牌桶满时则放弃向令牌桶中添加令牌
    2. 请求到达controller层时,需要去令牌桶中获取令牌,如果存在令牌,则继续执行,不存在这放弃这次请求cuiyaonan2000@163.com

    更直观的流程图参考百度:

    java实现用例

    package nan.yao.cui.others.aboutbuckets;
    
    import java.util.concurrent.atomic.AtomicInteger;
    
    /**
     * @author 崔耀男
     * @des: TODO
     * @date 2021年6月22日 上午11:14:29
     * @package nan.yao.cui.others.aboutbuckets
     */
    public class TokenBucketTest {
        
        // 令牌桶的容量----同时表示该controller的同一时间的并发量
        private int capacity = 10;
    
        // 令牌桶
        private AtomicInteger tokenBucket = new AtomicInteger(0);
    
        // 每秒钟产生的令牌数量
        private int tokenNum;
    
        public void doWhile() throws InterruptedException {
    	// 多少毫秒产生一个令牌
    	int forNum = 1000 / tokenNum;
    	while (true) {
    	    tokenBucket.set(0);
    	    while (forNum < 1000) {
    		Thread.sleep(forNum);
    		forNum += forNum;
    		tokenBucket.getAndAdd(1);
    	    }
    	}
        }
    
        public synchronized boolean getToken() {
    	if (tokenBucket.get() <= 0) {
    	    return false;
    	}
    
    	tokenBucket.decrementAndGet();
    
    	return true;
        }
    
        public static void main(String[] args) {
    	System.out.println((((System.currentTimeMillis() - 100) / 1000) * 2));
    	System.out.println(System.currentTimeMillis() - 100);
    	System.out.println((System.currentTimeMillis() - 100) / 1000);
    
        }
    
    }
    

    展开全文
  • 漏桶算法

    千次阅读 2019-03-12 21:06:36
    近期在研究Jaeger,Jaeger中有一种采集策略是速率限制类型,内部使用的是漏桶算法,在这里研究了下Jaeger漏桶算法的实现原理,自己仿照其实现了一个rateLimiter,并进行了相关测试,下面是主要实现。 lck:lck是...

    近期在研究Jaeger,Jaeger中有一种采集策略是速率限制类型,内部使用的是漏桶算法,在这里研究了下Jaeger漏桶算法的实现原理,自己仿照其实现了一个rateLimiter,并进行了相关测试,下面是主要实现。

    • lck:lck是互斥锁,主要用来防止并发情况下产生错误。
    • rate:速率,即接口每秒限制多少个请求。在这里也就是水滴从漏桶中流出的速度,同时也是余量增加的速度。
    • balance:漏桶的空闲余量,会随着漏桶滴水逐渐变大;如果将请求添加到漏桶中,会逐渐变小。当请求到来时,如果余量不足1,那么表明不能容下当前的请求,当前的请求会被拒绝。
    • limit:漏桶的最大容量。
    • lastTime:上次调用Check函数的时间。用于计算时间差dur,然后计算这段时间漏桶流出的水w,增加的余量=流出的水量w=时间*速率=dur*rate。

    rateLimiter实现代码:

    package ratelimiter
    
    import (
    	"sync"
    	"time"
    )
    
    type rateLimiter struct {
    	lck      *sync.Mutex
    	rate     float64   //最大速率限制
    	balance  float64   //漏桶的余量
    	limit    float64   //漏桶的最大容量限制
    	lastTime time.Time //上次检查的时间
    }
    
    func NewRateLimiter(limitPerSecond int, balance int) *rateLimiter {
    	return &rateLimiter{
    		lck:      new(sync.Mutex),
    		rate:     float64(limitPerSecond),
    		balance:  float64(balance),
    		limit:    float64(balance),
    		lastTime: time.Now(),
    	}
    }
    
    func (r *rateLimiter) Check() bool {
    	ok := false
    	r.lck.Lock()
    	now := time.Now()
    	dur := now.Sub(r.lastTime).Seconds()
    	r.lastTime = now
    	water := dur * r.rate //计算这段时间内漏桶流出水的流量water
    	r.balance += water    //漏桶流出water容量的水,自然漏桶的余量多出water
    	if r.balance > r.limit {
    		r.balance = r.limit
    	}
    	if r.balance >= 1 { //漏桶余量足够容下当前的请求
    		r.balance -= 1
    		ok = true
    	}
    	r.lck.Unlock()
    	return ok
    }
    

    单元测试代码:

    package ratelimiter
    
    import (
    	"fmt"
    	"testing"
    	"time"
    )
    
    func TestRateLimiter_Check(t *testing.T) {
    	limiter := NewRateLimiter(10, 1)
    	start := time.Now()
    	count := 0
    	for i := 0; i < 1e3; i++ {
    		if limiter.Check() {
    			fmt.Println(i)
    			count++
    		}
    		time.Sleep(time.Millisecond)
    	}
    	fmt.Println("count:", count)
    	fmt.Println(time.Now().Sub(start).Seconds())
    }
    

    测试结果:每秒限制10个,1.3秒接受了13个请求,加上一开始填满桶的一个,共14个。

    展开全文
  • 限流之漏桶算法

    千次阅读 2021-11-15 16:55:29
    现在,微服务大行其道,好多项目都是拆分,再拆分,美其名曰:解耦!这个不多说,适合自己的实际项目就好,反正项目都是会逐渐... 今天,就来说一个中间件常用的限流算法,木桶算法! 简单描述一下,其实也就是类...
  • redis 漏桶算法—Lua

    2021-04-22 20:06:22
    漏桶算法 import java.io.IOException;import java.nio.charset.Charset;import org.springframework.core.io.ClassPathResource;import com.google.common.io.Files;import redis.clients.jedis.Jedis;/****@author...
  • 关于限流 目前存在两大类,从线程个数(jdk1.5 Semaphore)和RateLimiter速率(guava)Semaphore:从线程个数限流RateLimiter:从速率限流 目前常见的算法是漏桶算法和令牌算法令牌桶算法。相比漏桶算法而言区别在于,...
  • 令牌桶算法和漏桶算法

    千次阅读 2020-03-01 22:42:51
    常用的限流算法有令牌桶和和漏桶,而Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。 在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存:缓存的目的是提升系统访问速度和增大系统...
  • 背景 每一个对外提供的API接口都是需要做流量控制的,不然会导致系统直接崩溃。很简单的例子,和保险丝的原理一样...漏桶算法(Leaky Bucket)是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经
  • 令牌桶算法三、限流工具类RateLimiter四、适用场景五、服务治理---限流(令牌桶算法)六、高并发系统限流中的漏桶算法和令牌桶算法,通过流量整形和速率限制提升稳定性七、聊聊高并发系统之限流特技**限流算法****...
  • 两个比较常用的算法有令牌桶算法、漏桶算法,是目前最常用的流量限制的方法。 2、漏桶算法 如上图所示,我们假设系统是一个漏桶,当请求到达时,就是往漏桶里“加水”,而当请求被处理掉,就是水从漏桶的底部...
  • 漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。 图1 漏桶算法示意图 对于很多应用场景来说,除了要求能够...
  • 二者区别l 漏桶算法能够强行限制数据的传输速率。l 令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。需要说明的是:在某些情况下,漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是...
  • 限流算法-令牌桶、漏桶算法之java实现
  • 限流 在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存:缓存的目的是提升系统访问速度和增大系统处理能力 降级:当服务流量剧增,影响到核心流程的性能,需要...漏桶算法 漏桶(Leaky Bucket) 算
  • 漏桶算法 把请求比作是水,水来了都先放进桶里,并以限定的速度出水,当水来得过猛而出水不够快时就会导致水直接溢出,即拒绝服务。 漏斗有一个进水口 和 一个出水口,出水口以一定速率出水,并且有一个最大出水...
  • 限流算法:滑动窗口、漏桶算法、令牌桶算法
  • 文章目录漏桶算法、令牌桶算法思路及使用场景RateLimiter实现原理SmoothBurstySmoothWarmingUp 漏桶算法、令牌桶算法思路及使用场景 在介绍RateLimiter之前我们先看下常说的漏桶算法和令牌桶算法,看下两种算法的...
  • 滑动窗口与固定窗口的关系 滑动窗口只有一个窗口就是固定窗口 漏桶算法(Leaky Bucket) 漏桶算法由流量容器、流量入口和出口组成。其中流量出口流速即为我们期望的限速值,比如 100 QPS。漏桶算法除了具备限流能力,...
  • 漏桶算法:水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出(拒绝服务),可以看出漏桶算法能强行限制数据的传输速率 流入:以任意速率往桶中放入水滴。 流出:以固定速率从桶中流出...
  • 漏桶算法详解

    千次阅读 2020-07-21 17:18:26
    本篇介绍漏桶算法,具体的漏桶算法概念如下: 漏桶算法跟令牌桶比较类似,但实际上是两种策略。想了解令牌桶算法的可以看之前的文章。 下面我们看一下维基百科的图片: 如图所示,我们可以看到,整个算法其实十分...
  • 1,漏桶算法漏桶作为计量工具(The Leaky Bucket Algorithm as a Meter)时,可以用于流量整形(Traffic Shaping)和流量控制(TrafficPolicing),漏桶算法的描述如下:一个固定容量的漏桶,按照常量固定速率流出水滴;...
  • 一、前言 在高并发场景,为了保证服务高可用,...为了规避上述问题,常用的更平滑的限流算法有漏桶算法和令牌桶算法。 二、漏桶算法(Leaky Bucket) 2.1、漏桶算法的思路 水(请求)先进入到漏桶里,漏桶以一定的速
  • 漏桶算法-php实现 1,概览 最近研究nginx的限流,limit_req_zone。 其功能就是限制大访问量下的请求数量,防止服务器故障。 核心逻辑就是: ...比较感兴趣它的实现,查阅资料发现利用了漏桶算法。就顺便带
  • 今天的主角跟其有密切关系,他被称之为漏桶算法漏桶算法要解决的一个核心问题,便是如何将不断变化的访问量,变成相对稳定的一个访问量。这么说可能太过抽象,举一个实际的例子,NGINX 接收到互联网上的请求,速率...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,124
精华内容 3,649
关键字:

漏桶算法