常见的限流算法

本是古典何须时尚 2021-12-05 15:07 297阅读 0赞

### 1.漏桶算法 ###

漏桶算法的原理比较简单，请求进入到漏桶中，漏桶以一定的速率漏水。当请求过多时，水直接溢出。可以看出，漏桶算法可以强制限制数据的传输速度。

### 2.令牌桶算法 ###

令牌桶算法的原理是系统以一定速率向桶中放入令牌，如果有请求时，请求会从桶中取出令牌，如果能取到令牌，则可以继续完成请求，否则等待或者拒绝服务。这种算法可以应对突发程度的请求，因此比漏桶算法好。

在 Wikipedia 上，令牌桶算法是这么描述的：

*  每秒会有 r 个令牌放入桶中，或者说，每过 1/r 秒桶中增加一个令牌
 *  桶中最多存放 b 个令牌，如果桶满了，新放入的令牌会被丢弃
 *  当一个 n 字节的数据包到达时，消耗 n 个令牌，然后发送该数据包
 *  如果桶中可用令牌小于 n，则该数据包将被缓存或丢弃

### 二、RateLimiter ###

Guava中开源出来一个令牌桶算法的工具类RateLimiter，可以轻松实现限流的工作。RateLimiter 对简单的令牌桶算法做了一些工程上的优化，具体的实现是 SmoothBursty。需要注意的是，RateLimiter 的另一个实现 SmoothWarmingUp，就不是令牌桶了，而是漏桶算法。也许是出于简单起见，RateLimiter 中的时间窗口能且仅能为 1s，如果想搞其他时间单位的限流，只能另外造轮子。

RateLimiter 有一个有趣的特性是「前人挖坑后人跳」，也就是说 RateLimiter 允许某次请求拿走超出剩余令牌数的令牌，但是下一次请求将为此付出代价，一直等到令牌亏空补上，并且桶中有足够本次请求使用的令牌为止。这里面就涉及到一个权衡，是让前一次请求干等到令牌够用才走掉呢，还是让它先走掉后面的请求等一等呢？Guava 的设计者选择的是后者，先把眼前的活干了，后面的事后面再说。

测试代码：

public class RateLimiterMain {
        public static void main(String[] args) {
            RateLimiter rateLimiter = RateLimiter.create(2);
            System.out.println(rateLimiter.acquire(5));
            System.out.println(rateLimiter.acquire(2));
            System.out.println(rateLimiter.acquire(1));
        }
    }

2.496889
    0.992149

可以看出，令牌桶每秒只能产生2个令牌，我们可以第一次取出5个，但是第二个再去取令牌的时候，需要等2.5s，也就是第一次令牌取完后，需要等2.5s才能取到令牌。同样的，第三次取1个令牌的时候，也需要等待第二次的1s的时间。也就是，取的速率可以超过令牌产生的速率，但是下一次再次去取的时候，需要阻塞等待。  
当然也可以使用tryAcquire来非阻塞的获取，可以实时返回结果。另外tryAcquire也可以传入参数，也就是等待的时间，规定时间内没获取到令牌直接返回false。这点等同于常见的lock，tryLock。

### 三、RateLimiter对API接口的限流实例 ###

pom文件

<dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>16.0.1</version>
            </dependency>

java代码

import java.util.concurrent.TimeUnit;
    
    import org.springframework.web.bind.annotation.RequestMapping;
    import org.springframework.web.bind.annotation.RestController;
    
    import com.google.common.util.concurrent.RateLimiter;
    import com.infinite.controller.vo.ResultBean;
    
    /**
     * 
    * @ClassName: RateLimiterTestController
    * @Description: RateLimiter限流（单应用，分布式考虑redis实现）
    * @author chenliqiao
    * @date 2018年5月11日 下午4:19:35
    *
     */
    @RestController
    public class RateLimiterTestController {
        
        /**令牌桶容量，一秒生成5个令牌**/
        private static final double PERMITS=5;
        
        RateLimiter rateLimiter=RateLimiter.create(PERMITS);
        
        @RequestMapping(value="/rateLimiter/getOrderNO")
        public ResultBean<String> getOrderNO(){
            /** 
             * tryAcquire(long timeout, TimeUnit unit) 
             * 从RateLimiter 获取许可如果该许可可以在不超过timeout的时间内获取得到的话， 
             * 或者如果无法在timeout 过期之前获取得到许可的话，那么立即返回false（无需等待） 
             */  
            if(!rateLimiter.tryAcquire(1000, TimeUnit.MILLISECONDS)){
                System.out.println("获取失败!");
                return new ResultBean<>("error!");
            }
            
            String orderNo="NO"+System.currentTimeMillis();
            System.out.println("获取成功："+orderNo);
            return new ResultBean<String>(orderNo);
        }
    
    }