RateLimiter限流

一、常见的限流算法

1.漏桶算法

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

image

2.令牌桶算法

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

image

在 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文件代码

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

• java代码

package com.infinite.controller;

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);
    }

}