devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

高并发限流之令牌桶

作者：繁依Fanyi0 | 2024-06-15 23:47:06

赞

踩

令牌桶

什么是限流？

限流可以认为服务降级的一种，限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

简单点来说就是：一定时间内把请求量限制在一定范围内，保证系统不被冲垮，同时尽可能提升系统的吞吐量。

为什么要限流？

保护服务，防止系统被瞬间的高并发请求冲垮，导致服务瘫痪。

怎么做到限流？

①限流算法：令牌桶、漏桶、计数器。

②应用层方面解决限流：Nginx
有了对高并发限流的简单认识后，下面我们来认识一下什么是令牌桶？

令牌桶算法

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

优点：

  • 放过的流量比较均匀，有利于保护系统。

  • 存量令牌能应对突发流量，很多时候，我们希望能放过脉冲流量。而对于持续的高流量，后面又能均匀地放过不超过限流值的请求数。

缺点：

  • 存量令牌没有过期时间，突发流量时第一个周期会多放过一些请求，可解释性差。即在突发流量的第一个周期，默认最多会放过 2 倍限流值的请求数。

  • 实际限流数难以预知，跟请求数和流量分布有关。

令牌桶动作分解

1 固定速录往桶里面存入令牌

2 客户端如果想访问请求，要从桶里面获取令牌

注意：

  • 客户端只有拿到令牌，才可以成功访问请求（关键）

  • 桶有固定容量，不能无限存入，满了就不再装了

  • 成功拿到了一个令牌就会从桶里删除一个令牌，当桶里有空余，继续往桶里存入令牌

搭建Demo

生成令牌桶​

  1.    /**
  2.     * 单列模式</br>
  3.     * 1、在内存中维护一个工厂实例，用于生成令牌桶</br>
  4.     * 2、客户端则调用TokenBucket.getToken()方法抢令牌，并根据是否抢到令牌来决定下一步的操作，从而达到限流的目的。</br>
  5.     * 3、发放速率控制：</br>
  6.     *   a、build("t1",3,RateUnit.SECOND)，表示创建名字为"t1"的令牌桶，且每秒发放3个令牌</br>
  7.     *   b、build("t2",3,RateUnit.MINUTE)，表示创建名字为"t2"的令牌桶，且每分钟发放3个令牌</br>
  8.     *   c、build("t3",3,RateUnit.HOUR)，     表示创建名字为"t3"的令牌桶，且每小时发放3个令牌</br>
  9.     *
  10.     * @param tokenName 令牌桶名称
  11.     * @param tokens 令牌个数
  12.     * @param rateUnit 速率类型：秒，分钟，小时
  13.     * @return
  14.     */
  15. public static TokenBucket build(String tokenName, int tokenNum, RateUnit rateUnit) {
  16.       if (instance == null) {
  17.          //"令牌桶工厂"单列模式
  18.          synchronized (TokenBucketFactory.class) {
  19.             if (instance == null) {
  20.                instance = new TokenBucketFactory();
  21.             }
  22.          }
  23.       }
  24.                  //调用令牌桶初始化方法
  25.       return initTokenBucket(tokenName, tokenNum, rateUnit);
  26.    }

令牌桶初始化

  

  1.  private static TokenBucket initTokenBucket(String tokenName, int tokenNum, RateUnit rateUnit) {
  2.       //1、查询令牌桶
  3.       TokenBucket bucket = tokenBuckets.get(tokenName);
  4.       if (bucket == null) {
  5.          try {
  6.             //2、如果令牌桶不存在，则获取写锁，开始初始化令牌桶，那些得不到锁的，则排队等待
  7.             rwl.writeLock().lock();
  8.             //3、因存在排队情况，判断名称为"tokenName"的令牌桶是否已经存在，只有不存在的场景下，才会执行初始化的动作。
  9.             bucket = tokenBuckets.get(tokenName);
  10.             if (bucket == null) {
  11.                //4、初始化令牌桶并放入tokenBuckets中保存
  12.                    //在new TokenBucketImpl()时执行了init方法进行令牌桶初始化
  13.                bucket = new TokenBucketImpl(tokenName, tokenNum, rateUnit);//
  14.                tokenBuckets.put(tokenName, bucket);
  15.             }
  16.          } catch (Exception e) {
  17.             log.error("令牌桶初始化失败:" + e.getMessage());
  18.             log.error(e);
  19.          } finally {
  20.             //5、释放写锁
  21.             rwl.writeLock().unlock();
  22.          }
  23.       }
  24.       return bucket;
  25.    }

TokenBucketImpl (String tokenName, int tokenNum, RateUnit rateUnit)构造方法 

  1.   /**
  2.     *
  3.     * @param tokenName 令牌桶名称
  4.     * @param tokens 令牌个数
  5.     * @param rateUnit 速率类型：秒，分钟，小时
  6.     */
  7.    protected TokenBucketImpl (String tokenName, int tokenNum, RateUnit rateUnit) {
  8.       System.out.println("-----------------令牌桶对象创建");
  9.       this.tokenName = tokenName;
  10.        //执行令牌桶初始化方法init
  11.       init(tokenNum, rateUnit);
  12.    }
  13.  
  14. /**
  15. * 令牌桶的初始化
  16. * @param tokenNum 令牌个数
  17. * @param rateType 令牌发放的时间
  18. */
  19. private void init(int tokenNum, RateUnit rateUnit) {
  20.    
  21.    //检查参数
  22.    if (tokenNum <= 0) {
  23.       throw new LimitedException("TokenBucket初始化失敗：tokenNum 参数必须为正整数 !!!!!!");
  24.    }
  25. ​
  26.    if (rateUnit == null) {
  27.       throw new LimitedException("TokenBucket初始化失敗：rateUnit 参数赋值范围：RateUnit.SECOND、RateUnit.MINUTE、RateUnit.HOUR");
  28.    }
  29.    type = rateUnit;
  30.    MAX_TOKENS = tokenNum;
  31.    log.info("58line==========="+MAX_TOKENS);
  32.    //创建保存令牌的队列
  33.    tokenQueue = new LinkedBlockingQueue<String>(MAX_TOKENS); //LinkedBlockingQueue：基于链表的阻塞队列
  34.    //创建定时任务处理服务，单线程即可
  35.    scheduExec = Executors.newScheduledThreadPool(1);
  36.    //初始化定时器，每XX毫秒执行一次task，task往令牌队列中放入一个令牌
  37.    //scheduExec.scheduleWithFixedDelay(new TokenTask(), 0, getDelay(), TimeUnit.MILLISECONDS);
  38.    //当TokenTask任务的执行时长超过getDelay()的时长，后续的任务会暂缓执行，在JVM发生性能问题的时候，可以避免加重JVM负担。
  39.    scheduExec.scheduleAtFixedRate(new TokenTask(), 0, getDelay(), TimeUnit.MILLISECONDS);
  40. }

上面初始化init过程中，创建了单线程定时任务，每隔100毫秒往桶里放一个令牌。

  1.  //具体的任务：判断令牌桶是否满容，如果不满则往里放入令牌；如果满则停止放入令牌，一直等待至有请求从桶里拿令牌
  2.   
  3.  private class TokenTask implements Runnable {
  4.       public TokenTask () {
  5.       }
  6.       public void run() {
  7.          //为了避免放入令牌的任务被中断，这里需要捕获任何可能发生的异常
  8.          try {
  9.             if (tokenQueue != null) {
  10.                if (tokenQueue.size() < MAX_TOKENS) {
  11.                   tokenQueue.offer(""); //offer操作：往桶里放入一个""               
  12.                   System.out.println("我放进去了一个东西");
  13.                }
  14.             }
  15.          } catch (Exception e) {
  16. //          log.warn("令牌发放发生异常:" + e.getMessage());
  17. //          log.warn(e);
  18.          }
  19.       }
  20.    }

tokenQueue底层用了阻塞队列BlockingQueue

 private BlockingQueue<String> tokenQueue;

阻塞队列 BlockingQueue的了解可看博客： https://www.cnblogs.com/tjudzj/p/4454490.html

创建令牌桶并初始化方法调用过程

获取令牌

  1.    public boolean getToken() {
  2.       try {
  3.          log.info("tokenQueue1============"+tokenQueue.size());
  4.          if (tokenQueue != null) {
  5.             //为了避免阻塞客户端的调用，设置超时的时长为30毫秒：代表这次请求允许的最大等待时间为30毫秒
  6.             String token = tokenQueue.poll(30, TimeUnit.MILLISECONDS);
  7.             if (token != null) {
  8.                return true;
  9.             }
  10.          }
  11.       } catch (Throwable e) {
  12.          log.warn("获取令牌发生异常：" + e);
  13.       }
  14. ​
  15.       return false;
  16.    }

tokenQueue.poll(3, TimeUnit.MILLISECONDS)方法是获取令牌，允许最长等待时间为3毫秒

枚举类RateUnit定义了三种时间单位：秒、分、时

  1. public enum RateUnit {
  2.       SECOND, MINUTE, HOUR
  3.    }

测试类

  1. public class test {
  2.    public static void main(String[] args) {
  3.       //创建令牌桶并初始化：生成一个名叫“huyijun”的令牌桶，每秒往桶内放入10个令牌，也就是说每100毫秒往桶内放入1个令牌
  4.       TokenBucket tokenBucket = TokenBucketFactory.build("huyijun", 10, RateUnit.SECOND);
  5.       //for循环模拟发送请求
  6.        for(int i=1;i<10;i++) {
  7.            //获取当前时间
  8.          long t1 = new Date().getTime();
  9.            //获取令牌，如果拿到了立刻返回true；如果没拿到等待完最大可等待的时间后返回false
  10.            //获取令牌中涉及到了一个允许等待多久时间的参数设置，上面设置的是30毫秒
  11.            //就是说，在上一个请求成功拿到令牌后，需要等候100毫秒的时间才有下一个令牌的放入
  12.            //但在没放入令牌前，服务还是会一直被请求，每个请求最大可等待的时间为30毫秒，30毫秒内如果还没有成功拿到，则返回false；如果30毫秒内拿到令牌则立即返回true
  13.          if(tokenBucket.getToken()) {
  14.                //(new Date().getTime()-t1)是为了计算每次拿令牌的时间，有误差，但是最大值在30毫秒左右
  15.             System.out.println(i+":拿到了令牌，耗费时间"+(new Date().getTime()-t1));
  16.          }else {
  17.             System.out.println(i+":没拿到令牌，等待时间"+(new Date().getTime()-t1));
  18.          }
  19.       }
  20.    }
  21. }

运行结果：

思考：

1、为什么9次for循环中，有些拿到令牌了，有些没拿到？
答：在生成令牌桶时设定的参数：令牌桶容量为10，每100毫秒生成1个令牌；
在令牌桶初始化时设定的参数：每个请求允许的最大等待时间为30毫秒；
在一开始令牌桶初始化的时候，令牌桶就放入了一个令牌，所以请求1能拿到令牌，
但是在下一个请求2进来的时候，令牌桶这时候是空的，请求2等待30毫秒后还没有到达下一次令牌放置的时间100毫秒，就返回了false，所以请求2不能拿到令牌，
请求3、4同理；
到请求5进来的时候，只需要等待几毫秒就刚好到了令牌桶第二个令牌放入的时间，所以请求5能拿到令牌；
循环反复……
2、为什么到后面只是放进去，没有拿令牌的操作？
答：因为for循环执行完了，就没有了取令牌的操作，但此时令牌桶中的令牌还没到达容量，所以定时任务会一直往里添加令牌。
3、怎么才能保证每个请求都能拿到令牌？
答：当每个请求允许最大等待时间的设定大于令牌生成的时间，则可以保证每个请求都能拿到令牌。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/724281
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号