精华内容
下载资源
问答
  • 令牌桶算法谷歌实现
    2022-01-24 21:25:32

    令牌桶算法


    小序


    The token bucketis an algorithm used in packet-switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth) and burstiness (a measure of the unevenness or variations in the traffic flow). 
    令牌桶是一种用于分组交换和电信网络的算法。它可用于检查数据包形式的数据传输是否符合定义的带宽和突发性限制(流量不均匀或变化的度量)
    

    谷歌实现


    添加maven依赖

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

    测试用例

    import com.google.common.util.concurrent.ListeningExecutorService;
    import com.google.common.util.concurrent.MoreExecutors;
    import com.google.common.util.concurrent.RateLimiter;
    
    import java.text.SimpleDateFormat;
    import java.util.Date;
    import java.util.concurrent.Executors;
    
    public class LimitTest {
    
    	public static void main(String[] args) {
    		ListeningExecutorService executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(100));
             
    		RateLimiter limiter = RateLimiter.create(1);
    		for (int i = 1; i < 50; i++) {
    			Double acquire = limiter.acquire(i);
    			executorService.submit(new PrintTask(String.format("get token,token:%s consumer:%s, taskId:%s",acquire, acquire, i)));
    		}
    	}
    	static class PrintTask implements Runnable {
    		String out;
    		public PrintTask(String out) {
    			this.out = out;
    		}
    		@Override
    		public void run() {
    			SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
    			System.out.println(sdf.format(new Date()) + " -> " + Thread.currentThread().getName() + out);
    		}
    	}
    }
    
    

    核心方法

    //实例化处理器 每秒允许一个请求通过
    RateLimiter limiter = RateLimiter.create(1); 
    //获取令牌
    Double acquire = limiter.acquire(i);
    

    源码

    /**
    创建具有指定稳定吞吐量的RateLimiter ,以“每秒允许数”(通常称为QPS ,每秒查询数)的形式给出。
    返回的RateLimiter确保在任何给定的秒内平均发出不超过permitsPerSecond ,持续的请求在每一秒内顺利传播。 当传入请求速率超过permitsPerSecond时,速率限制器将每(1.0 / permitsPerSecond)秒释放一个许可。 当速率限制器未使用时,将允许最多permitsPerSecond许可的突发,随后的请求以permitsPerSecond的稳定速率平滑限制。
    
    参数:
    permitPerSecond – 返回的RateLimiter的速率,以每秒可用的许可数量衡量
    抛出:
    IllegalArgumentException – 如果permitsPerSecond为负数或零
    推断注释:
    @org.jetbrains.annotations.NotNull @org.jetbrains.annotations.Contract("_->new")
    
    */
    public static RateLimiter create(double permitsPerSecond) {
        /*
         * The default RateLimiter configuration can save the unused permits of up to one second. This
         * is to avoid unnecessary stalls in situations like this: A RateLimiter of 1qps, and 4 threads,
         * all calling acquire() at these moments:
         *
         * T0 at 0 seconds
         * T1 at 1.05 seconds
         * T2 at 2 seconds
         * T3 at 3 seconds
         *
         * Due to the slight delay of T1, T2 would have to sleep till 2.05 seconds, and T3 would also
         * have to sleep till 3.05 seconds.
        默认的 RateLimiter 配置最多可以保存一秒钟的未使用许可。这是为了避免在以下情况下出现不必要的停顿: 1qps 的 RateLimiter 和 4 个线程,在这些时刻都调用 acquire(): T0 在 0 秒 T1 在 1.05 秒 T2 在 2 秒 T3 在 3 秒 由于轻微延迟在 T1 中,T2 必须睡到 2.05 秒,T3 也必须睡到 3.05 秒。
         */
        return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
      }
    
    

    从源码中我们可以看到,除了传入的速率值,还需要初始化一个SleepingStopwatch.createFromSystemTimer()定时处理器,我们看看这个里面到底有什么。

    SleepingStopwatch

     public static SleepingStopwatch createFromSystemTimer() {
          return new SleepingStopwatch() {
    		//初始化Stopwatch 并启动
            final Stopwatch stopwatch = Stopwatch.createStarted();
    		
              /**
              读取秒表
              */
            @Override
            protected long readMicros() {
              return stopwatch.elapsed(MICROSECONDS);
            }
    		
            /**
              睡眠
             */
            @Override
            protected void sleepMicrosUninterruptibly(long micros) {
              if (micros > 0) {
                Uninterruptibles.sleepUninterruptibly(micros, MICROSECONDS);
              }
            }
          };
        }
    //stopwatch.elapsed(MICROSECONDS) 获取当前时间 
     public long elapsed(TimeUnit desiredUnit) {
        //获取时间并转换为纳秒
        return desiredUnit.convert(elapsedNanos(), NANOSECONDS);
     }
    //elapsedNanos() 获取时间
    private long elapsedNanos() {
        // 如果当前处于运行状态 则从ticker中读取时间-开始计时的时间+elapsedNanos时间, 否则返回elapsedNanos 过去时间
        return isRunning ? ticker.read() - startTick + elapsedNanos : elapsedNanos;
    }
    //追踪ticker 初始化对象中Stopwatch.createStarted();
      Stopwatch() {
        this.ticker = Ticker.systemTicker();
      }
    // Ticker 源码 其实就是去读取系统的纳秒时间
    public abstract class Ticker {
      protected Ticker() {}
      public abstract long read();
      public static Ticker systemTicker() {
        return SYSTEM_TICKER;
      }
      private static final Ticker SYSTEM_TICKER =
          new Ticker() {
            @Override
            public long read() {
              return Platform.systemNanoTime();
            }
          };
    }
    //Platform.systemNanoTime 读取系统时间
     static long systemNanoTime() {
        return System.nanoTime();
      }
    
    

    可以看到createFromSystemTimer 方法返回了一个只有读取秒表时间和睡眠的方法的实例。可以看到这个方法主要是获取系统的纳秒时间

    我们继续跟踪主线代码create方法

      @VisibleForTesting
      static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
        RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
        rateLimiter.setRate(permitsPerSecond);
        return rateLimiter;
      }
    ----->创建对象
      SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
          super(stopwatch);
          this.maxBurstSeconds = maxBurstSeconds;
        }
    
    

    到这里我们可以看到,ReteLimiter真正的实现是SmoothBursty,然后设置下流速,就返回了。到此对象的实例算是完成了,我们这条线暂时到这。接下来看看acquire获取令牌的方法。

    acquire 获取令牌

    /**
    从此RateLimiter获取给定数量的许可,阻塞直到可以授予请求。 告知睡眠时间(如果有)
    */
      @CanIgnoreReturnValue
      public double acquire(int permits) {
        //获取需要等待的时间
        long microsToWait = reserve(permits);
        //阻塞等待
        stopwatch.sleepMicrosUninterruptibly(microsToWait);
    	//返回一个值,其实这个值是多少没什么太大作用
        return 1.0 * microsToWait / SECONDS.toMicros(1L);
      }
    

    可以看到,申请token的方法中,主要实现三个功能:

    1. 计算等待时间
    2. 阻塞等待
    3. 返回一个值

    可以看到核心是reserve计算等待时间这个方法,我们可以继续跟进去。

    /**
       * Reserves the given number of permits from this {@code RateLimiter} for future use, returning
       * the number of microseconds until the reservation can be consumed.
       * 从此RateLimiter保留给定数量的许可以供将来使用,返回微秒数,直到可以使用保留
       * @return time in microseconds to wait until the resource can be acquired, never negative
       */
      final long reserve(int permits) {
    	//校验permits是否大于0,负责抛出异常
        checkPermits(permits);
         // mutex 设置上锁点
        synchronized (mutex()) {
          //核心 保留并计算等待时间长度
          return reserveAndGetWaitLength(permits, stopwatch.readMicros());
        }
      }
    

    可以看到reserveAndGetWaitLength才是我们算法的核心所在,这个方法需要的参数,除了我们传入的速率之外,还有一个从stopwatch中读取的秒表,我们继续跟踪查看:

    /**
       * Reserves next ticket and returns the wait time that the caller must wait for.
       * 保留下一张票并返回调用者必须等待的等待时间
       * @return the required wait time, never negative
       */
      final long reserveAndGetWaitLength(int permits, long nowMicros) {
        //获取最早可用的时间
        long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
        //返回需要等待时间值
        return max(momentAvailable - nowMicros, 0);
      }
    

    这里reserveEarliestAvailable 就是我们的主要目标了,怼吧。

      @Override
      final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
        //1.重新同步时间
        resync(nowMicros);
        //2.将下次可以获取获取令牌的时间作为返回值
        long returnValue = nextFreeTicketMicros;
        //3.存储消费许可, 取要求token个数和已有token个数的最小值
        /*
        3.存储消费许可, 取要求token个数和已有token个数的最小值
        4.去除要求的token之外,剩余token个数
        这两步要合起来看
        需求toke个数: requiredPermits
        已有token: storedPermits
        如果requiredPermits > storedPermits,则需要新令牌的个数为
         requiredPermits - storedPermits
        如果requiredPermits <= storedPermits,则需要新令牌的个数为
         requiredPermits - storedPermits
         这两行代码写的真是厉害
        */  
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
        // 4.去除要求的token之外,需要重新刷的token个数
        double freshPermits = requiredPermits - storedPermitsToSpend;
        //5.令牌消费之后,剩余令牌可以使用的时间
        long waitMicros =
            storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
                + (long) (freshPermits * stableIntervalMicros);
    	//6.刷新下个允许获取令牌的时间  
        this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
        //7.更新消费许可
        this.storedPermits -= storedPermitsToSpend;
        return returnValue;
      }
    
    //-----------------------------resync 代码------------------------------
    void resync(long nowMicros) {
        // if nextFreeTicket is in the past, resync to now
        //如果允许获取下一个令牌的时间小于当前时间,则更新nextFreeTicketMicros为当前时间
        if (nowMicros > nextFreeTicketMicros) {
          //计算当前时间和next的时间差内可以产生的token个数
          double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
          //更新存储的可用token的个数
          storedPermits = min(maxPermits, storedPermits + newPermits);
          //更新允许可以获取下一个token的时间
          nextFreeTicketMicros = nowMicros;
        }
      }
    
    

    可以看到这里就是我们的索要追踪的核心所在了,

    1. 重新同步时间的逻辑

      1.2.1. 计算当前时间和上一个next的时间差内可以产生的token个数

      1.2.2. 更新当前可存储的token个数

      1.2.3. 更新允许获取下一个token的时间next

    2. 将下次可以获取获取令牌的时间作为返回值

    3. 存储消费许可, 取要求token个数和已有token个数的最小值,具体原因可以看代码注释

    4. 去除要求的token之外,需要重新刷的token个数

    5. 令牌消费之后,剩余令牌可以使用的时间

    6. 计算下个允许获取令牌的时间

    7. 更新剩下的消费许可

    获取到需要等待的时间之后,我们就可以返回方法处了

    /**
    从此RateLimiter获取给定数量的许可,阻塞直到可以授予请求。 告知睡眠时间(如果有)
    */
      @CanIgnoreReturnValue
      public double acquire(int permits) {
        //获取需要等待的时间
        long microsToWait = reserve(permits);
        //阻塞等待
        stopwatch.sleepMicrosUninterruptibly(microsToWait);
    	//返回一个值,其实这个值是多少没什么太大作用
        return 1.0 * microsToWait / SECONDS.toMicros(1L);
      }
    

    这个拿到需要阻塞的时间之后,直接阻塞,时间到了,返回值。 到此算是整个过程处理完毕。

    总结

    从源码看这个令牌桶算法是先拿的人是无限制,拿到之后,下次可以获取令牌的时间,就要等到这些令牌的制造所需时间过后才能重新获取。
    
    更多相关内容
  • 基于令牌桶算法的Java限流实现。 项目需要使用限流措施,查阅后主要使用令牌桶算法实现,为了更灵活的实现限流,就自己实现了一个简单的基于令牌桶算法的限流实现。
  • 主要介绍了15行Python代码带你轻松理解令牌桶算法,需要的朋友可以参考下
  • 利用Redis和Golang实现分布式令牌桶算法令牌桶算法对速率限制和网络拥塞控制非常有用
  • 令牌桶算法c实现

    2017-11-29 23:23:04
    Token Bucket Emulation in C using Multithreading This project involved emulation of the Token Bucket algorithm using POSIX threads in C. The aim was to simulate a traffic shaper that receives and ...
  • 系统在运行过程中,如遇上某些活动,访问的人数会在一瞬间内爆增,导致服务器瞬间压力飙升,使系统超...本文介绍php基于redis,使用令牌桶算法,实现访问流量的控制,提供完整算法说明及演示实例,方便大家学习使用。
  • ratelimit 基于令牌桶算法和漏桶算法来实现的限速限流,Golang实现
  • 基于令牌桶算法实现的SpringBoot无锁限流插件,支持方法级别、系统级别的限流,提供快速失败与CAS阻塞两种方案,开箱即用!
  • 令牌桶算法

    2021-08-22 21:55:32
    使用了那种算法?为什么要这样实现?可能就不大理解了。在这之前,我也是这样,只知其然不知其所然。 1. 为什么要限流 一个系统,面临大数据量,高并发的访问时,将出现无法提供服务,或请求响应超时等情况,严重的...

    最近,某个项目需要上线一个功能,需要对请求进来的流量进行控制,也就是我们常说的限流。“限流”,通过字面意思也能猜到是要干什么的,但是,它是怎么实现的?使用了那种算法?为什么要这样实现?可能就不大理解了。在这之前,我也是这样,只知其然不知其所然。

    1. 为什么要限流

    一个系统,面临大数据量,高并发的访问时,将出现无法提供服务,或请求响应超时等情况,严重的,在连锁反应下导致系统崩溃。这时候,对请求进行限流就很有必要了。通过限流,当请求达到一定的并发数或速率,就进行让请求等待、排队、降级、拒绝服务等,平缓进入系统的请求数峰值。

    2. 常用的限流算法

    常用的限流算法有两种,分别是漏桶算法,令牌桶算法。

    1. 漏桶算法
      漏桶算法图例
      漏桶算法是将请求放入到漏桶中,桶中的请求按照一定的速率出去。突发大流量请求,经过漏桶算法控制后,将以恒定的速率进入网络。

    2. 令牌桶算法
      令牌桶算法图例
      固定容量的令牌桶可自行以恒定的速率产生令牌。如果令牌不被消耗,或者被消耗的速度小于产生的速度,桶内的令牌累积,直到把桶填满。后面再产生的令牌就会从桶中溢出抛弃。请求进来时,需要先从令牌桶中获取到令牌,方能被系统处理及响应。否则,被直接拒绝服务。

    总结:
    漏桶算法直接强制限制了请求的速率,无论多大的并发请求数,都会以恒定的速率出现。当一个系统的请求处理速率大于漏桶算法的限制速率时,面对突发的大流量,将会出现大量请求被拒绝,而系统利用率低的情况,在这个时候,漏桶算法就不合适了。此时,就要用令牌桶算法。令牌桶在容量固定,在请求量平缓且低于令牌生成速率(令牌生成速率及令牌桶容量要根据系统的处理能力设置)时,令牌桶是满的,面对突发的大流量,令牌桶容量大小的请求数能获取到令牌,降低流量峰值的同时,避免大量请求被丢弃。请求流量平缓进入系统,直到与令牌生成速率持平。
    两种算法原理是不同的,但都能达到限流的目的,我们可以结合实际场景使用。比如,当调用的第三方系统处理能力有限,且没有相应的限流机制,这个时候,有突发大流量,为了第三方系统的稳定,就必须抛弃掉多余的流量。使用漏桶算法,刚好可以达到这个目的。相反,作为被调用方,在无法预测有多大的流量进入己方系统时,就可以使用令牌桶算法限流,即使在大流量请求到来,也能平缓过渡。

    3. 限流实例

    Google开源工具包Guava提供了限流工具类RateLimiter,该类基于令牌桶算法来完成限流,我们可以导入相应的包进行使用。

    <dependency>
           <groupId>com.google.guava</groupId>
           <artifactId>guava</artifactId>
           <version>20.0</version>
    </dependency>
    
    3.1 调用代码:

    在这里插入图片描述

    3.2 限流工具类RateLimiter:
    /**
         * Acquires the given number of permits from this {@code RateLimiter} if it can be obtained
         * without exceeding the specified {@code timeout}, or returns {@code false} immediately (without
         * waiting) if the permits would not have been granted before the timeout expired.
         * 如果没有超过延时时间,能够从令牌桶获取到指定数量的令牌就返回true;
         * 或者在延时结束时还没有获取到令牌,就返回false(没有指定延时时间 timeout,就马上返回false)
         * @param permits the number of permits to acquire
         * @param timeout the maximum time to wait for the permits. Negative values are treated as zero.
         * @param unit the time unit of the timeout argument
         * @return {@code true} if the permits were acquired, {@code false} otherwise
         * @throws IllegalArgumentException if the requested number of permits is negative or zero
         */
        public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
            long timeoutMicros = max(unit.toMicros(timeout), 0);
            // 入参校验
            checkPermits(permits);
            long microsToWait;
            // 同步块,解决并发获取令牌的情况
            synchronized (mutex()) {
                long nowMicros = stopwatch.readMicros();
                // 马上能获取到令牌或者在延时时间内能获取到令牌 canAcquire(nowMicros, timeoutMicros)
                if (!canAcquire(nowMicros, timeoutMicros)) {
                    return false;
                } else {
                    // 预定下一张令牌,返回下一张令牌生成需等待的时间
                    microsToWait = reserveAndGetWaitLength(permits, nowMicros);
                }
            }
            stopwatch.sleepMicrosUninterruptibly(microsToWait);
            return true;
        }
    
    3.3 令牌桶限流效果

    在这里插入图片描述

    展开全文
  • 2、令牌桶算法 3、两种算法的区别 4、限流工具类RateLimiter 4.1 RateLimiter demo 4.2 主要接口 常用的限流算法有两种:漏桶算法和令牌桶算法。 1、漏桶算法 漏桶算法思路很简单,请求先进入到漏桶里,漏桶...

    目录

    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

    参考阅读:

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

    展开全文
  • 本文章是关于令牌桶算法的应用。
  • 在网络中传输数据的时候时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。

    文章目录

    简介

    在网络中传输数据的时候时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。

    令牌桶算法是网络流量整形和速率限制中最常使用的一种算法。大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗,或者被消耗的速度小于产生的速度,令牌就会不断地增多,直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。
    ipt-1
    传送到令牌桶的数据包需要消耗令牌。不同大小的数据包,消耗的令牌数量不一样。

    令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌,则允许发送流量;而如果令牌桶中不存在令牌,则不允许发送流量。因此,如果突发门限被合理地配置并且令牌桶中有足够的令牌,那么流量就可以以峰值速率发送。

    lpt-2
    与“令牌桶算法”类似的算法还有“漏桶算法”,这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

    在本文中,我们使用 Golong 语言实现一个简单的“令牌桶算法”,或者说是“漏桶算法”更为合适。

    实现

    首先,我们假设令牌桶的放入令牌的速率是恒定的,不考虑流量速率突变的情况。

    package awesomeProject
    
    import (
    	"sync"
    	"time"
    )
    
    // 定义令牌桶结构
    type tokenBucket struct {
    	limitRate int           // 限制频率,即每分钟加入多少个令牌
    	tokenChan chan struct{} // 令牌通道,可以理解为桶
    	cap       int           // 令牌桶的容量
    	muLock    *sync.Mutex   // 令牌桶锁,保证线程安全
    	stop      bool          // 停止标记,结束令牌桶
    }
    
    // NewTokenBucket 创建令牌桶
    func NewTokenBucket(limitRate, cap int) *tokenBucket {
    	if cap < 1 {
    		panic("token bucket cap must be large 1")
    	}
    	return &tokenBucket{
    		tokenChan: make(chan struct{}, cap),
    		limitRate: limitRate,
    		muLock:    new(sync.Mutex),
    		cap:       cap,
    	}
    }
    
    // Start 开启令牌桶
    func (b *tokenBucket) Start() {
    	go b.produce()
    }
    
    // 生产令牌
    func (b *tokenBucket) produce() {
    	for {
    		b.muLock.Lock()
    		if b.stop {
    			close(b.tokenChan)
    			b.muLock.Unlock()
    			return
    		}
    		b.tokenChan <- struct{}{}
    		d := time.Minute / time.Duration(b.limitRate)
    		b.muLock.Unlock()
    		time.Sleep(d)
    	}
    }
    
    // Consume 消费令牌
    func (b *tokenBucket) Consume() {
    	<-b.tokenChan
    }
    
    // Stop 停止令牌桶
    func (b *tokenBucket) Stop() {
    	b.muLock.Lock()
    	defer b.muLock.Unlock()
    	b.stop = true
    }
    

    其中,

    • tokenBucket为令牌桶的结构,包括限制频率、令牌桶容量和通道等;
    • NewTokenBucket为对外提供的创建令牌桶的方法;
    • Start为开启令牌桶的方法;
    • produce为以恒定速率生成令牌的方法,以协程的方式启动;
    • Consume为消费令牌的方法;
    • Stop为停止令牌桶的方法。

    如上述所示,即为令牌桶的简易实现。

    轮子

    实际上,在 Go 语言中已经提供了对令牌桶的支持了,因此不需要我们重复造轮子。
    lpt-3
    更详细的内容,大家可以点击「limiter」进行查看,祝好!


    参考资料

    展开全文
  • 提出一种基于令牌桶算法的抵御Flood攻击的通信量整形模型和过滤规则,从硬件线路的改进着手对Flood攻击行为进行瓦解。
  • 令牌桶算法原理

    2021-10-27 16:33:40
    token_bucket令牌桶算法原理 讲在原理之前 我们今天主要是分析令牌桶算法,分析之前我们先介绍一下使用该算法的背景。 限流 每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限...
  • bucket4j, 基于令牌桶算法的Java速率限制库 Bucket4j - 基于令牌桶算法的Java速率限制库。 的优点在已经知算法的基础上实现,它是in行业的速率限制的实际标准。有效的锁自由实现,Bucket4j可以用于多线程处理。绝对...
  • 桶算法(有点像Kafka,大批量的数据吞吐) 漏桶算法的主要思路为: 在nginx层与controller层加一层(即漏桶层), 用于接收nginx收到的大批量的请求,接收的请求的速度是没有控制的,但是如果超过了漏桶层的最大容量则...
  • 令牌桶算法实现

    千次阅读 2022-04-01 22:19:37
    #define MYTBF_MAX 1024 //能够支持1024个不同速率的令牌桶 typedef void mytbf_t; mytbf_t *mytbf_init(int, int); int mytbf_fetchtoken(mytbf_t *, int); int mytbf_returntoken(mytbf_t *, int); int mytbf...
  • 关于限流 目前存在两大类,从线程个数(jdk1.5 Semaphore)和RateLimiter速率(guava)Semaphore:从线程个数限流RateLimiter:从速率限流 目前常见的算法是漏桶算法和令牌算法令牌桶算法。相比漏桶算法而言区别在于,...
  • 令牌桶算法。相比漏桶算法而言区别在于,令牌桶是会去匀速的生成令牌,拿到令牌才能够进行处理,类似于匀速往桶里放令牌。 漏桶算法是:生产者消费者模型,生产者往木桶里生产数据,消费者按照预先定义的速度去消费...
  • 算法思想是: 令牌以固定速率产生,并缓存到令牌桶中; 令牌桶放满时,多余的令牌被... 相比漏桶算法,令牌桶算法不同之处在于它不但有一只“桶”,还有个队列,这个桶是用来存放令牌的,队列才是用来存放请求的...
  • 如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。 三、限流工具类RateLimiter Google开源工具包...
  • 令牌桶算法及其应用

    千次阅读 2020-05-29 07:47:44
    令牌桶算法简介 在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。 [1]  ...
  • 令牌桶算法的使用

    2021-05-23 04:41:31
    令牌桶算法 简介 令牌桶(token bucket)算法是 Nginx 进行流量限制的一种常用算法。常用于控制发送到网络上的数据的数量,并允许突发数据的发送。 基础流程图 当数据请求来临时,算法通过检查当前桶的令牌量,如果...
  • 限流算法:滑动窗口、漏桶算法、令牌桶算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,682
精华内容 4,272
关键字:

令牌桶算法

友情链接: STM32 USART.zip