实战系列-Java实现限流算法

妖狐艹你老母 2023-01-14 05:56 135阅读 0赞

> **导语**  
>   在Java开发过程中，经常用到的限流算法有两种，一种是令牌桶算法，一种是漏斗桶算法，那么下面就来分别看看两种算法的Java实现方式。

### 文章目录 ###

*   *  限流算法之漏桶算法
     *   *  漏桶的实现
     *  限流算法之令牌桶法
     *   *  简单的令牌桶算法实现
     *  总结

## 限流算法之漏桶算法 ##

漏桶算法:首先保证请求先进入到漏桶中，漏桶再通过一定的速度将流量引出，这里需要注意的是当流量太大或者是漏桶已经满了之后会直接溢出，然后就开始拒绝请求，可以看出漏桶算法能强行限制数据传输的速率。如图所示，图来自网络

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]

### 漏桶的实现 ###

实现的关键点：

*  1、定义这个桶的最大容量；
 *  2、记录好上次操作完成后的时间以及桶的剩余量，用来记录后续计算当前桶的容量；
 *  3、定义好流速，速率越小，流控越大，流量越小；
 *  4、每次请求，需要先检查桶大小，如果超过最大值，则拒绝，如果没有超过最大值则继续进行操作；

public class LeakyBucket { 
    
        // 流出速率
        private double rate;
    
        // 桶大小
        private double burst;
    
        // 最后更新时间
        private long refreshTime;
    
        // 现有量
        private int water;
    
    
        public LeakyBucket(double rate,double burst){ 
            this.rate = rate;
            this.burst = burst;
        }
    
        /** * 用来刷新水量 */
        private void refreshWater(){ 
            long now = System.currentTimeMillis();
            water = (int) Math.max(0,water-(now-refreshTime)* rate);
            refreshTime = now;
        }
    
        public synchronized boolean tryAcquire(){ 
            refreshWater();
            if (water<burst) { 
                water++;
                return true;
            }else { 
                return false;
            }
        }
    
    
        private static LeakyBucket leakyBucket = new LeakyBucket(1,100);
        public static void main(String[] args) { 
            ExecutorService executorService = Executors.newCachedThreadPool();
            for (int i = 0; i < 1000; i++) { 
                executorService.execute(()->{ 
                    System.out.println(leakyBucket.tryAcquire());
                });
            }
            executorService.shutdown();
        }
    }

## 限流算法之令牌桶法 ##

系统通过一定的速率往桶里面添加令牌，处理请求之前，需要先从桶里获取一个令牌，当桶里没有令牌的时候则需要进行返回失败。  
  大概描述如下：

*  所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
 *  获取不到令牌，则请求返回失败；
 *  根据限流大小，设置按照一定的速率往桶里添加令牌；
 *  桶要设置最大放置令牌的限制，当桶满的时候、添加新的令牌就会被丢弃或者拒绝；

如图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center 1]

### 简单的令牌桶算法实现 ###

实现关键点

*  1、初始化固定数量的令牌放入令牌桶中
 *  2、初始化和开启一个定时任务，定时往令牌桶添加令牌
 *  3、提供一个获取令牌的方法，获取一个令牌，令牌桶中减一，如果令牌桶为空，则返回失败

public class TokenLimiter { 
    
        private ArrayBlockingQueue<String> blockingQueue;
        private int limit;
        private TimeUnit timeUnit;
        private int period;
    
    
        public TokenLimiter(int limit,int period,TimeUnit timeUnit){ 
            this.limit = limit;
            this.timeUnit = timeUnit;
            this.period = period;
            blockingQueue = new ArrayBlockingQueue<>(limit);
            init();
            start();
        }
    
    
    
        /** * 初始化令牌操作 */
        private void init() { 
            for (int i = 0; i < limit; i++) { 
                blockingQueue.add("1");
            }
        }
    
        /** * 获取令牌为空，返回false * @return */
        public boolean tryAcquire(){ 
            return blockingQueue.poll()==null?false:true;
        }
    
        private void addToken(){ 
            blockingQueue.offer("1");
        }
    
    
    
    
        private void start() { 
            Executors.newScheduledThreadPool(1).scheduleAtFixedRate(()->{ 
                addToken();
            },10,period,timeUnit);
        }
    }

## 总结 ##

上面通过简单的方式实现了两种限流算法，当然还是有很多的改进的地方，这里只是通过简单的代码对两种算法的核心内容进行演示，当然后续高级算法的演变也是基于核心思想来进行的变化。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/1c0c628af0164de5aff62b63c6be1c9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/c9dc630c17fd450db7e46969342dbeac.png