为什么要限流

  秒杀时特别热卖的商品，会有很多人来抢(不排除黄牛)，不进行限流，有可能把缓存和DB全部拖垮从而造成雪崩。
  微博上的热搜，那流量可想而知。
  比如业务方发布了一个活动，拼团支付一分钱，抽百万大奖，这是拼团支付流量很大，影响了其他业务的正常支付，这个时候需要对各个业务方做单独限流。
  业务方提出需求，用户在单位时间内访问某个页面的次数不能超过多少，这时也需要限流。
  限流应用场景很多，就不一一列举了,这些应用场景应该单独抽取出来，做成一个流控服务。

常见的限流有 : 单机限流，分布式限流，计数器限流。

单机限流

  单机限流的常见算法 漏桶算法、令牌桶算法、计数器算法

漏桶算法

  由图片可知，桶的漏出速率是一定的，请求达到桶的容量之后就会拒绝请求。漏桶算法有一定的缺点，就是当系统可以承受这么大的压力时，请求放过的量还是这么多，不能有效的利用系统资源。

漏桶算法

令牌桶算法

  如下图所示,请求过来以后先去桶里拿令牌，拿不到令牌之后则拒绝请求。令牌桶允许一定量的突发流量，请求空闲时预热一部分令牌，新请求无需等待

令牌桶算法

  guava 的RateLimiter默认就是令牌桶实现，提供了SmoothWarmingUp（预热限流），SmoothWarmingUp(突发限流)两种实现。
几个关键的成员变量

  // 当前桶里存放多少个令牌
  double storedPermits;
  // 最大可以存放多少令牌
  double maxPermits;
  // 获取一个令牌需要的时间，比如限流qps是5，那此值就是 1/5 = 200ms
  double stableIntervalMicros;
  // 记录最近一个可以获取令牌的时间。
  long nextFreeTicketMicros = 0L;

public double acquire(int permits) {
    // 拿 permits 个令牌要等待多长时间
    long microsToWait = reserve(permits);
    // 其实就是sleep
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
  }

接下来看一下reserve方法的实现

final long reserve(int permits) {
    checkPermits(permits);
    // mutex方法使用了double check，这在多线程编程里是很常见的
    synchronized (mutex()) {
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
  }

reserveAndGetWaitLength 调用了reserveEarliestAvailable方法，最主要的实现就是在这个方法里了。没看源码之前总以为是有一个后台线程在不断的往桶里面放令牌，其实是每次拿令牌的时候才去更新桶里的令牌数量，这个实现很精髓。

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
   // 这个方法的作用是，假如有很长时间都没有线程来拿令牌了，则更新令牌桶里的令牌数量
    resync(nowMicros);
    long returnValue = nextFreeTicketMicros;
    // 取要求拿几个令牌 和 现有存储令牌的 最小值
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;
    // 计算等待时间，storedPermitsToWaitTime 在SmoothBursty实现里返回0
    // 当拿的令牌数量小于桶中剩余令牌数量时，等待时间为0。
    long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
        + (long) (freshPermits * stableIntervalMicros);
    // 更新剩余令牌数量和最近一个可用令牌的时间
    this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
  }

返回的这个returnValue 大于0的话，当前线程就sleep多长时间。

private void resync(long nowMicros) {
    // 当前时间大于最后一个令牌可用时间，说明有一段时间没有线程来拿令牌了
    if (nowMicros > nextFreeTicketMicros) {
      // 更新存储令牌的数量，计算方式如下
      storedPermits = min(maxPermits,
          storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
      nextFreeTicketMicros = nowMicros;
    }
  }

acquire方法介绍完了，接下来在看一下 tryAcquire 方法的实现。

public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
    long timeoutMicros = max(unit.toMicros(timeout), 0);
    checkPermits(permits);
    long microsToWait;
    // acquire 和 tryAcquire 方法在此处都是加锁线程安全的。
    synchronized (mutex()) {
      long nowMicros = stopwatch.readMicros();
      // 看能否获取锁
      if (!canAcquire(nowMicros, timeoutMicros)) {
        return false;
      } else {
        // 接下来就是调用 reserveEarliestAvailable方法，上面已经介绍过了
        microsToWait = reserveAndGetWaitLength(permits, nowMicros);
      }
    }
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return true;
  }

// timeoutMicros 参数就是最长等待多长时间
private boolean canAcquire(long nowMicros, long timeoutMicros) {
    // queryEarliestAvailable 返回的是 nextFreeTicketMicros
    // 最近一次可以获取令牌的时间 - 等待时间 < 当前时间
    return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;
 }

guava的RateLimiter源码就大致解析到这里

计数器算法

这个实现比较简单，demo如下

// 设置1秒钟过期
LoadingCache<String, AtomicLong> cache = CacheBuilder.newBuilder().expireAfterWrite(1, TimeUnit.SECONDS).build(new CacheLoader<String, AtomicLong>() {
            @Override
            public AtomicLong load(String key) throws Exception {
                // load 方法内部加了 synchorized 代码块修饰，在高并发下key失效，也只有一个线程调用此方法去加载初始值放到cache，其余线程从cache获取
                return new AtomicLong(0);
            }
        });
 if (cache.get("key").incrementAndGet() < 限流大小) {
      // pass
  } else {
      // reject
  }

单机限流还可以根据 线程池，每个限流方法配置不同的线程池，做到很好的线程隔离。也可以使用信号量，hystrix实现。

分布式限流

原因

  现在服务部署都是集群方式，使用比如dubbo等RPC框架，还有使用nginx做反向代理，有可能流量请求到物理机上不均匀，还有就是机器的性能不相同，如果使用单机限流的话，性能好的物理机资源会大大的浪费。

应用

• 支付服务是核心服务，会有多个业务方来调，这时候要多各个业务方做限流，防止由于某个业务方支付量激增时影响其他业务方支付。
• 限制 百分之多少的用户请求时直接降级。
• 限制用户一天访问多少次，等等。

实现

• 分布式限流可以基于redis，对限流的key做incr操作，并设置过期值，当incr的值大于限流值之后，直接reject调。
• 可以单独部署一个令牌服务，每次请求时客户端去令牌服务端拿对应的令牌，令牌服务做成HA高可用，这样就不强依赖redis。(阿里开源的sentinel分布式限流就是这么做的)
• 也可以使用nginx做限流，nginx+lua脚本实现。

  下面简单画了一下基于redis的集群限流图片

redis限流

高效率与高可用

• 集群限流强依赖于第三方(比如redis)，当网络放生抖动时，会使一个请求的时间大大加长，这对于业务方来说是不可忍受的。可以对请求redis的时间做熔断降级(异步写redis)，当redis不可用时，集群限流降级为单机限流(集群限流值/机器总数)。
• 客户端也可以一次拿多个令牌，这样就不会频繁请求redis了。
• 读取redis的从库，写入主库，这样有可能存在主从延时导致多放请求进来。