本文实现了一种基本的令牌桶算法

令牌桶算法思想：以固定速率产生令牌，放入令牌桶，每次用户请求都得申请令牌，令牌不足则拒绝请求或等待。

代码逻辑：线程池每0.5s发送随机数量的请求，每次请求计算当前的令牌数量，请求令牌数量超出当前令牌数量，则产生限流。

@Slf4j
public class TokensLimiter {

    private ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5);

    // 最后一次令牌发放时间
    public long timeStamp = System.currentTimeMillis();
    // 桶的容量
    public int capacity = 10;
    // 令牌生成速度10/s
    public int rate = 10;
    // 当前令牌数量
    public int tokens;

    public void acquire() {
        scheduledExecutorService.scheduleWithFixedDelay(() -> {
            long now = System.currentTimeMillis();
            // 当前令牌数
            tokens = Math.min(capacity, (int) (tokens + (now - timeStamp) * rate / 1000));
            //每隔0.5秒发送随机数量的请求
            int permits = (int) (Math.random() * 9) + 1;
            log.info("请求令牌数：" + permits + "，当前令牌数：" + tokens);
            timeStamp = now;
            if (tokens < permits) {
                // 若不到令牌,则拒绝
                log.info("限流了");
            } else {
                // 还有令牌，领取令牌
                tokens -= permits;
                log.info("剩余令牌=" + tokens);
            }
        }, 1000, 500, TimeUnit.MILLISECONDS);
    }

    public static void main(String[] args) {
        TokensLimiter tokensLimiter = new TokensLimiter();
        tokensLimiter.acquire();
    }

}

输出结果：

16:13:20.042 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：1，当前令牌数：10

16:13:20.045 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=9

16:13:20.549 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：7，当前令牌数：10

16:13:20.549 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=3

16:13:21.054 [pool-1-thread-2] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：5，当前令牌数：8

16:13:21.054 [pool-1-thread-2] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=3

16:13:21.559 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：1，当前令牌数：8

16:13:21.559 [pool-1-thread-1] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=7

16:13:22.063 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：7，当前令牌数：10

16:13:22.063 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=3

16:13:22.568 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：7，当前令牌数：8

16:13:22.568 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 剩余令牌=1

16:13:23.072 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 请求令牌数：7，当前令牌数：6

16:13:23.072 [pool-1-thread-3] INFO com.example.demo.limit.TokensLimiter - 限流了

目录

一、漏桶和令牌桶介绍

二、Redis+ lua脚本 + 令牌桶算法 实现限流控制

1、自定义一个注解，用来给限流的方法标注

2、编写lua脚本

3、读取lua脚本

4、创建拦截器拦截带有该注解的方法

5、在WebConfig中注册这个这个拦截器

6、注解使用

一、漏桶和令牌桶介绍


漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于：l 漏桶算法能够强行限制数据的传输速率。l 令牌桶算法能够在限制数据的平均传输速率的同

时还允许某种程度的突发传输。需要说明的是：在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的

流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。



常用的限流算法有两种：漏桶算法和令牌桶算法。

      漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。


漏桶算法示意图




对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图2所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处

理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。


令牌桶算法示意图




并不能说明令牌桶一定比漏洞好，她们使用场景不一样。令牌桶可以用来保护自己，主要用来对调用者频率进行限流，为的是让自己不被打垮。所以如果自己本身有处理能力的时候，如果流量突发（实际消费能力强于配置的流量限制），那么实际处理速率可

以超过配置的限制。而漏桶算法，这是用来保护他人，也就是保护他所调用的系统。主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。

这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。

总结起来：如果要让自己的系统不被打垮，用令牌桶。如果保证被别人的系统不被打垮，用漏桶算法。


二、Redis+ lua脚本 + 令牌桶算法 实现限流控制

1、自定义一个注解，用来给限流的方法标注

@Target({ElementType.TYPE, ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
public @interface RateLimit {
    //限流唯一标示
    String key() default "";
 
    //限流单位时间（单位为s）
    int time() default 1;
 
    //单位时间内限制的访问次数
    int count();
 
    //是否限制ip
    boolean ipLimit() default false;
}

2、编写lua脚本

根据key（参数） 查询 对应的 value（令牌数）
	如果为null 说明该key 是第一次进入 
	{
		初始化 令牌桶（参数）数量;记录初始化时间 ->返回 剩余令牌数
	} 
	
	如果不为null
	{
		判断 value 是否大于1 
		{
			大于1  ->value - 1  -> 返回 剩余令牌数
			小于1  -> 判断  补充令牌时间间隔是否足够
			{
				足够 -> 补充令牌；更新补充令牌时间-> 返回 剩余令牌数
				不足够	-> 返回 -1 (说明超过限流访问次数)
			}
		}
	}
	

redis.replicate_commands();
-- 参数中传递的key
local key = KEYS[1]
-- 令牌桶填充 最小时间间隔
local update_len = tonumber(ARGV[1])
-- 记录 当前key上次更新令牌桶的时间的 key
local key_time = 'ratetokenprefix'..key
-- 获取当前时间(这里的curr_time_arr 中第一个是 秒数，第二个是 秒数后毫秒数)，由于我是按秒计算的，这里只要curr_time_arr[1](注意：redis数组下标是从1开始的)
--如果需要获得毫秒数 则为 tonumber(arr[1]*1000 + arr[2])
local curr_time_arr = redis.call('TIME')
-- 当前时间秒数
local nowTime = tonumber(curr_time_arr[1])
-- 从redis中获取当前key 对应的上次更新令牌桶的key 对应的value
local curr_key_time = tonumber(redis.call('get',KEYS[1]) or 0)
-- 获取当前key对应令牌桶中的令牌数
local token_count = tonumber(redis.call('get',KEYS[1]) or -1)
-- 当前令牌桶的容量
local token_size = tonumber(ARGV[2])
-- 令牌桶数量小于0 说明令牌桶没有初始化
if token_count < 0 then
	redis.call('set',key_time,nowTime)
	redis.call('set',key,token_size -1)
	return token_size -1
else
	if token_count > 0 then --当前令牌桶中令牌数够用
		redis.call('set',key,token_count - 1)
		return token_count -1   --返回剩余令牌数
	else    --当前令牌桶中令牌数已清空
		if curr_key_time + update_len < nowTime then    --判断一下，当前时间秒数 与上次更新时间秒数  的间隔，是否大于规定时间间隔数 （update_len）
			redis.call('set',key,token_size -1)
			return token_size - 1
		else
			return -1
		end
	end
end

3、读取lua脚本

@Component
public class CommonConfig {
    /**
     * 读取限流脚本
     */
    @Bean
    public DefaultRedisScript<Number> redisluaScript() {
        DefaultRedisScript<Number> redisScript = new DefaultRedisScript<>();
        //这里脚本的路径为path for source root 路径
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("myLua.lua"))); 
        redisScript.setResultType(Number.class);
        return redisScript;
    }
    /**
     * RedisTemplate
     */
    @Bean
    public RedisTemplate<String, Serializable> limitRedisTemplate(LettuceConnectionFactory redisConnectionFactory) {
        RedisTemplate<String, Serializable> template = new RedisTemplate<String, Serializable>();
        template.setKeySerializer(new StringRedisSerializer());
        template.setValueSerializer(new GenericJackson2JsonRedisSerializer());
        template.setConnectionFactory(redisConnectionFactory);
        return template;
    }
}

4、创建拦截器拦截带有该注解的方法

@Component
public class RateLimitInterceptor implements HandlerInterceptor {
    private final Logger LOG = LoggerFactory.getLogger(this.getClass());
    
    @Autowired
    private RedisTemplate<String, Serializable> limitRedisTemplate;
 
    @Autowired
    private DefaultRedisScript<Number> redisLuaScript;
    
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
        assert handler instanceof HandlerMethod;
        HandlerMethod method = (HandlerMethod) handler;
        RateLimit rateLimit = method.getMethodAnnotation(RateLimit.class);
        //当前方法上有我们自定义的注解
        if (rateLimit != null) {
            //获得单位时间内限制的访问次数
            int count = rateLimit.count();
            String key = rateLimit.key();
            //获得限流单位时间（单位为s）
            int time = rateLimit.time();
            boolean ipLimit = rateLimit.ipLimit();
            //拼接 redis中的key
            StringBuilder sb = new StringBuilder();
            sb.append(Constants.RATE_LIMIT_KEY).append(key).append(":");
            //如果需要限制ip的话
            if(ipLimit){
                sb.append(getIpAddress(request)).append(":");
            }
            List<String> keys = Collections.singletonList(sb.toString());
           //执行lua脚本
            Number execute = limitRedisTemplate.execute(redisLuaScript, keys, time, count);
            assert execute != null;
            if (-1 == execute.intValue()) {
                ResultModel resultModel = ResultModel.error_900("接口调用超过限流次数");
                response.setStatus(901);
                response.setCharacterEncoding("utf-8");
                response.setContentType("application/json");
                response.getWriter().write(JSONObject.toJSONString(resultModel));
                response.getWriter().flush();
                response.getWriter().close();
                LOG.info("当前接口调用超过时间段内限流,key:{}", sb.toString());
                return false;
            } else {
                LOG.info("当前访问时间段内剩余{}次访问次数", execute.toString());
            }
        }
        return true;
    }
 
    @Override
    public void postHandle(HttpServletRequest request, HttpServletResponse response, Object handler, ModelAndView modelAndView) throws Exception {
 
    }
 
    @Override
    public void afterCompletion(HttpServletRequest request, HttpServletResponse response, Object handler, Exception ex) throws Exception {
 
    }
    
    public static String getIpAddr(HttpServletRequest request) {
        String ipAddress = null;
        try {
            ipAddress = request.getHeader("x-forwarded-for");
            if (ipAddress == null || ipAddress.length() == 0 || "unknown".equalsIgnoreCase(ipAddress)) {
                ipAddress = request.getHeader("Proxy-Client-IP");
            }
            if (ipAddress == null || ipAddress.length() == 0 || "unknown".equalsIgnoreCase(ipAddress)) {
                ipAddress = request.getHeader("WL-Proxy-Client-IP");
            }
            if (ipAddress == null || ipAddress.length() == 0 || "unknown".equalsIgnoreCase(ipAddress)) {
                ipAddress = request.getRemoteAddr();
            }
            // 对于通过多个代理的情况，第一个IP为客户端真实IP,多个IP按照','分割
            // "***.***.***.***".length()
            if (ipAddress != null && ipAddress.length() > 15) { 
                // = 15
                if (ipAddress.indexOf(",") > 0) {
                    ipAddress = ipAddress.substring(0, ipAddress.indexOf(","));
                }
            }
        } catch (Exception e) {
            ipAddress = "";
        }
        return ipAddress;
    }
 
}

一个自定义的常量用作redis前缀

public class Constants {
    public static final String RATE_LIMIT_KEY = "rateLimit:";
}

5、在WebConfig中注册这个这个拦截器

@Configuration
@EnableWebMvc
public class WebConfig extends WebMvcConfigurerAdapter {
 
    @Autowired
    private RateLimitInterceptor rateLimitInterceptor;
 
    @Override
    public void addInterceptors(InterceptorRegistry registry) {
        registry.addInterceptor(rateLimitInterceptor);
        super.addInterceptors(registry);
    }
}

6、注解使用

@RestController
@RequestMapping(value = "/test")
public class TestController {
 
    //限流规则为 1秒内只允许同一个ip发送5次请求
    @RateLimit(key = "testGet",time = 1,count = 5,ipLimit = true)
    @RequestMapping(value = "/get")
    public ResultModel testGet(){
        return ResultModel.ok_200();
    }
 
}

 

漏桶算法与令牌桶算法
漏桶算法
令牌桶算法
区别
RateLimiter
信号量


转载：本文转载自 linkedkeeper.com (文／张松然)

漏桶算法
漏桶算法：水（请求）先进入到漏桶里，漏桶以一定速度出水，当水流（请求）过大时会直接溢出，可以强行限制数据的传输速率。


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


区别
漏桶和令牌桶的区别：令牌桶常用于控制并发，无论何时，令牌的总数是固定的，每次调用开始都需要申请，调用结束都需要释放；而漏桶适用于控制QPS，漏桶可以在每秒生成m个令牌，每次调用开始都需要申请，但调用结束不需要释放，不过问题就是如果上一秒的调用没有结束，实际调用会大于当前生成的m个令牌控制的调用量。
RateLimiter
Google 开源工具包 Guava 提供了限流工具类 RateLimiter，该类基于令牌桶算法实现流量限制，使用十分方便，而且十分高效。
首先简单介绍下 RateLimiter 的使用：
public void testAcquire() {
  RateLimiter limiter = RateLimiter.create(1);

  for(int i = 1; i < 10; i = i + 2 ) {
    double waitTime = limiter.acquire(i);
    System.out.println("cutTime=" + System.currentTimeMillis() 
        + " acq:" + i 
        + " waitTime:" + waitTime);
  }
}

输出结果：
cutTime=1535439657427 acq:1 waitTime:0.0
cutTime=1535439658431 acq:3 waitTime:0.997045
cutTime=1535439661429 acq:5 waitTime:2.993028
cutTime=1535439666426 acq:7 waitTime:4.995625
cutTime=1535439673426 acq:9 waitTime:6.999223

首先通过 RateLimiter.create(1); 创建一个限流器，参数代表每秒生成的令牌数，通过 limiter.acquire(i); 来以阻塞的方式获取令牌，当然也可以通过 tryAcquire(int permits, long timeout, TimeUnit unit) 来设置等待超时时间的方式获取令牌，如果超 timeout 为0，则代表非阻塞，获取不到立即返回。
从输出来看，RateLimiter 支持预消费，比如在 acquire(5) 时，等待时间是3秒，是上一个获取令牌时预消费了3个两排，固需要等待 3*1 秒，然后又预消费了5个令牌，以此类推。
RateLimiter 通过限制后面请求的等待时间，来支持一定程度的突发请求（预消费），在使用过程中需要注意这一点，具体实现原理后面再分析。
信号量
操作系统的信号量是个很重要的概念，Java 并发库 的Semaphore 可以很轻松完成信号量控制，Semaphore 可以控制某个资源可被同时访问的个数，通过 acquire() 获取一个许可，如果没有就等待，而 release() 释放一个许可。
信号量的本质是控制某个资源可被同时访问的个数，在一定程度上可以控制某资源的访问频率，但不能精确控制。
public static void main(String[] args) {

  ExecutorService executorService = Executors.newCachedThreadPool();
  // 信号量，只允许 3个线程同时访问
  Semaphore semaphore = new Semaphore(3);
  for (int i=0;i<10;i++){
    final long num = i;
    executorService.submit(new Runnable() {
      @Override
      public void run() {
        try {
          // 获取许可
          semaphore.acquire();
          // 执行
          System.out.println("Accessing: " + num);
          Thread.sleep(new Random().nextInt(5000)); // 模拟随机执行时长
          // 释放
          semaphore.release();
          System.out.println("Release..." + num);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
      }
    });
  }
  executorService.shutdown();
}

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
令牌桶算法的基本过程如下：

假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；

假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；

当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络；

如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外；

算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理：

它们可以被丢弃；

它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；

它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。

注意：令牌桶算法不能与另外一种常见算法“漏桶算法（Leaky Bucket）”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。
令牌桶工作参数

工作过程包括3个阶段：产生令牌、消耗令牌和判断数据包是否通过。其中涉及到2个参数：令牌产生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用图形简要概括一下这3个阶段与2个参数的关系。 [1]
产生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达CBS/EBS，则丢弃多余令牌。

消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。

判断是否通过：输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃。
基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有IN/OUT公平标记器（FM）和三色标记器（TCM），扩展的算法主要有单速率三色标记器（srTCM）和双速率三色标记器（trTCM）。其中单速率标记器和双速率标记器已分别称为IETF的标准建议。
令牌桶限流

限流

限流是对某一时间窗口内的请求数进行限制，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。常用的限流算法有令牌桶和和漏桶，而Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。
在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流

缓存：缓存的目的是提升系统访问速度和增大系统处理容量

降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行

限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

我们经常在调别人的接口的时候会发现有限制，比如微信公众平台接口、百度API Store、聚合API等等这样的，对方会限制每天最多调多少次或者每分钟最多调多少次
我们自己在开发系统的时候也需要考虑到这些，比如我们公司在上传商品的时候就做了限流，因为用户每一次上传商品，我们需要将商品数据同到到美团、饿了么、京东、百度、自营等第三方平台，这个工作量是巨大，频繁操作会拖慢系统，故做限流。
以上都是题外话，接下来我们重点看一下令牌桶算法

令牌桶算法



RateLimiter

https://github.com/google/guava
RateLimiter的代码不长，注释加代码432行，看一下RateLimiter怎么用

package com.cjs.example;
import com.google.common.util.concurrent.RateLimiter;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.text.SimpleDateFormat;
import java.util.Date;

@RestController
public class HelloController {

    private static final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    private static final RateLimiter rateLimiter = RateLimiter.create(2);

    /**
     * tryAcquire尝试获取permit，默认超时时间是0，意思是拿不到就立即返回false
     */
    @RequestMapping("/sayHello")
    public String sayHello() {
        if (rateLimiter.tryAcquire()) { //  一次拿1个
            System.out.println(sdf.format(new Date()));
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }else {
            System.out.println("limit");
        }
        return "hello";
    }

    /**
     * acquire拿不到就等待，拿到为止
     */
    @RequestMapping("/sayHi")
    public String sayHi() {
        rateLimiter.acquire(5); //  一次拿5个
        System.out.println(sdf.format(new Date()));
        return "hi";
    }

}









关于RateLimiter：

A rate limiter。每个acquire()方法如果必要的话会阻塞直到一个permit可用，然后消费它。获得permit以后不需要释放。

RateLimiter在并发环境下使用是安全的：它将限制所有线程调用的总速率。注意，它不保证公平调用。

RateLimiter在并发环境下使用是安全的：它将限制所有线程调用的总速率。注意，它不保证公平调用。Rate limiter（直译为：速度限制器）经常被用来限制一些物理或者逻辑资源的访问速率。这和java.util.concurrent.Semaphore正好形成对照。

一个RateLimiter主要定义了发放permits的速率。如果没有额外的配置，permits将以固定的速度分配，单位是每秒多少permits。默认情况下，Permits将会被稳定的平缓的发放。

可以配置一个RateLimiter有一个预热期，在此期间permits的发放速度每秒稳步增长直到到达稳定的速率

基本用法：
final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is "2 permits per second"
void submitTasks(List<Runnable> tasks, Executor executor) {
    for (Runnable task : tasks) {
        rateLimiter.acquire(); // may wait
        executor.execute(task);
    }
}

实现



SmoothBursty以稳定的速度生成permit
SmoothWarmingUp是渐进式的生成，最终达到最大值趋于稳定



源码片段解读：
public abstract class RateLimiter {

    /**
     * 用给定的吞吐量（“permits per second”）创建一个RateLimiter。
     * 通常是QPS
     */
    public static RateLimiter create(double permitsPerSecond) {
        return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
    }
    
    static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
        RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
        rateLimiter.setRate(permitsPerSecond);
        return rateLimiter;
    }
    
    /**
     * 用给定的吞吐量(QPS)和一个预热期创建一个RateLimiter
     */
    public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
        checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
        return create(permitsPerSecond, warmupPeriod, unit, 3.0, SleepingStopwatch.createFromSystemTimer());
    }

    static RateLimiter create(
            double permitsPerSecond,
            long warmupPeriod,
            TimeUnit unit,
            double coldFactor,
            SleepingStopwatch stopwatch) {
        RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit, coldFactor);
        rateLimiter.setRate(permitsPerSecond);
        return rateLimiter;
    }

    private final SleepingStopwatch stopwatch;

    //    锁
    private volatile Object mutexDoNotUseDirectly;

    private Object mutex() {
        Object mutex = mutexDoNotUseDirectly;
        if (mutex == null) {
            synchronized (this) {
                mutex = mutexDoNotUseDirectly;
                if (mutex == null) {
                    mutexDoNotUseDirectly = mutex = new Object();
                }
            }
        }
        return mutex;
    }
    
    /**
     * 从RateLimiter中获取一个permit，阻塞直到请求可以获得为止
     * @return 休眠的时间，单位是秒，如果没有被限制则是0.0
     */
    public double acquire() {
        return acquire(1);
    }
  
    /**
     * 从RateLimiter中获取指定数量的permits，阻塞直到请求可以获得为止
     */
    public double acquire(int permits) {
        long microsToWait = reserve(permits);
        stopwatch.sleepMicrosUninterruptibly(microsToWait);
        return 1.0 * microsToWait / SECONDS.toMicros(1L);
    }
    
    /**
     * 预定给定数量的permits以备将来使用
     * 直到这些预定数量的permits可以被消费则返回逝去的微秒数
     */
    final long reserve(int permits) {
        checkPermits(permits);
        synchronized (mutex()) {
            return reserveAndGetWaitLength(permits, stopwatch.readMicros());
        }
    }
    
    private static void checkPermits(int permits) {
        checkArgument(permits > 0, "Requested permits (%s) must be positive", permits);
    }
    
    final long reserveAndGetWaitLength(int permits, long nowMicros) {
        long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
        return max(momentAvailable - nowMicros, 0);
    }
}


abstract class SmoothRateLimiter extends RateLimiter {
    
    /** The currently stored permits. */
    double storedPermits;

    /** The maximum number of stored permits. */
    double maxPermits;

    /**
     * The interval between two unit requests, at our stable rate. E.g., a stable rate of 5 permits
     * per second has a stable interval of 200ms.
     */
    double stableIntervalMicros;
    
    /**
     * The time when the next request (no matter its size) will be granted. After granting a request,
     * this is pushed further in the future. Large requests push this further than small requests.
     */
    private long nextFreeTicketMicros = 0L; // could be either in the past or future
    
    final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
        resync(nowMicros);
        long returnValue = nextFreeTicketMicros;
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits);    //    本次可以获取到的permit数量
        double freshPermits = requiredPermits - storedPermitsToSpend;    //    差值，如果存储的permit大于本次需要的permit数量则此处是0，否则是一个正数
        long waitMicros =
            storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
                + (long) (freshPermits * stableIntervalMicros);    //    计算需要等待的时间（微秒）

        this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
        this.storedPermits -= storedPermitsToSpend;    //    减去本次消费的permit数
        return returnValue;
    }
    
    void resync(long nowMicros) {
        // if nextFreeTicket is in the past, resync to now
        if (nowMicros > nextFreeTicketMicros) {    //    表示当前可以获得permit
            double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();    //    计算这段时间可以生成多少个permit
            storedPermits = min(maxPermits, storedPermits + newPermits);    //    如果超过maxPermit，则取maxPermit，否则取存储的permit+新生成的permit
            nextFreeTicketMicros = nowMicros;    //    设置下一次可以获得permit的时间点为当前时间
        }
    }
}

RateLimiter实现的令牌桶算法，不仅可以应对正常流量的限速，而且可以处理突发暴增的请求，实现平滑限流。
通过代码，我们可以看到它可以预消费，怎么讲呢
nextFreeTicketMicros表示下一次请求获得permits的最早时间。每次授权一个请求以后，这个值会向后推移（PS：想象一下时间轴）即向未来推移。因此，大的请求会比小的请求推得更。这里的大小指的是获取permit的数量。这个应该很好理解，因为上一次请求获取的permit数越多，那么下一次再获取授权时更待的时候会更长，反之，如果上一次获取的少，那么时间向后推移的就少，下一次获得许可的时间更短。可见，都是有代价的。正所谓：要浪漫就要付出代价。
还要注意到一点，就是获取令牌和处理请求是两个动作，而且，并不是每一次都获取一个，也不要想当然的认为一个请求获取一个permit（或者叫令牌），可以再看看前面那幅图
Stopwatch

一个以纳秒为单位度量流逝时间的对象。它是一个相对时间，而不是绝对时间。
Stopwatch stopwatch = Stopwatch.createStarted();
System.out.println("hahah");
stopwatch.stop();
Duration duration = stopwatch.elapsed();
System.out.println(stopwatch);

Semaphore（信号量）

A counting semaphore. Conceptually, a semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.
一个信号量维护了一系列permits。
每次调用acquire()方法获取permit，如果必要的话会阻塞直到有一个permit可用为止。
调用release()方法则会释放自己持有的permit，即用完了再还回去。
信号量限制的是并发访问临界资源的线程数。
令牌桶算法 VS 漏桶算法

漏桶

漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。
令牌桶

生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。
最后，不论是对于令牌桶拿不到令牌被拒绝，还是漏桶的水满了溢出，都是为了保证大部分流量的正常使用，而牺牲掉了少部分流量，这是合理的，如果因为极少部分流量需要保证的话，那么就可能导致系统达到极限而挂掉，得不偿失。
小定律：排队理论

https://en.wikipedia.org/wiki/Little%27s_law
the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is：
在一个固定系统中，顾客的长期平均数量L等于顾客的长期平均到达速率λ乘以顾客在系统中平均花费的时间W。用公式表示为：
虽然这看起来很容易，但这是一个非常显著的举世瞩目的结果，因为这种关系“不受到达过程的分布，服务分布，服务顺序，或其他任何因素的影响”。这个结果适用于任何系统，特别是适用于系统内的系统。唯一的要求是系统必须是稳定的非抢占式的。
例子

例1：找响应时间

假设有一个应用程序没有简单的方法来度量响应时间。如果系统的平均数量和吞吐量是已知的，那么平均响应时间就是：
mean response time = mean number in system / mean throughput
平均响应时间 = 系统的平均数量 / 平均吞吐量.
例2：顾客在店里

想象一下，一家小商店只有一个柜台和一个可供浏览的区域，每次只能有一个人在柜台，并且没有人不买东西就离开。
所以这个系统大致是：进入 --> 浏览 --> 柜台结账 --> 离开
在一个稳定的系统中，人们进入商店的速度就是他们到达商店的速度（我们叫做到达速度），它们离开的速度叫做离开速度。
相比之下，到达速度超过离开速度代表是一个不稳定的系统，这就会造成等待的顾客数量将逐渐增加到无穷大。
前面的小定律告诉我们，商店的平均顾客数量L等于有效的到达速度λ乘以顾客在商店的平均停留时间W。用公式表示为：
假设，顾客以每小时10个的速度到达，并且平均停留时间是0.5小时。那么这就意味着，任意时间商店的平均顾客数量是5
现在假设商店正在考虑做更多的广告，把到达率提高到每小时20。商店必须准备好容纳平均10人，或者必须将每个顾客在商店中的时间减少到0.25小时。商店可以通过更快地结帐或者增加更多的柜台来达到后者的目的。
我们可以把前面的小定律应用到商店系统中。例如，考虑柜台和在柜台前排的队。假设平均有2个人在柜台前排队，我们知道顾客到达速度是每小时10，所以顾客平均必须停留时间为0.2小时。
最后

这是单机（单进程）的限流，是JVM级别的的限流，所有的令牌生成都是在内存中，在分布式环境下不能直接这么用。
如果我们能把permit放到Redis中就可以在分布式环境中用了。
参考

https://blog.csdn.net/jek123456/article/details/77152571
https://blog.csdn.net/syc001/article/details/72841951
https://segmentfault.com/a/1190000012875897
https://blog.csdn.net/charleslei/article/details/53152883
https://www.jianshu.com/p/8f548e469bbe
https://www.cnblogs.com/f-zhao/p/7210158.html
https://m.jb51.net/article/127996.htm