计数器限流

最原始的代码

public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }

    public long getNowTime() {
        return System.currentTimeMillis();
    }
}

但是计数器限流无法对相邻两秒都是高qps进行限流，比如1:29:29.999有100qps，1:30:30.001也有100qps，其实一秒内qps已经超过100qps，但是无法触发限流。

计数器+时间窗口结合

可以对1s进行拆分10个小格，一格允许10qps，每次请求进来，都只统计当前时间所在小格和往前推9个小格的qps统计，超过100则促发限流，否则请求可以通过

漏桶算法

有一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。
这个可以看作是一个生产者消费者模型，消费者以恒定速率消费。

缺点：无法应对突发流量，突发高qps流量会被拦截

令牌桶算法

我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以 一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。可以应对突发流量
具体实现代码 guava RateLimiter

RateLimiter源码解析

变量解析

• storedPermits 目前存储的可用的令牌
• maxPermits 可以存储的最多令牌数
• stableIntervalMicros 请求的间隔，5permits 1s，该值就是200ms
• nextFreeTicketMicros 下一个请求可以授权通过的时间，不管该请求需要多少permits，但是请求的permits越多，请求通过后，nextFreeTicketMicros值越大

RateLimiter创建

static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
  }

默认创建SmoothBursty方式的rateLimiter，它支持某一刻的突发流量，stopwatch封装了读取当前时间(毫秒)的函数

public double acquire(int permits) {
    long microsToWait = reserve(permits);
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
  }

final long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
  }

计算应该需要等待的毫秒，在sleep，最后返回等待的秒数

void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    if (nowMicros > nextFreeTicketMicros) {
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();//如果now比nextFreeTicketMicros大，计算到now时间应该新生成多少newPermits
      storedPermits = min(maxPermits, storedPermits + newPermits);//求最小值，因为如果now比nextFreeTicketMicros大很多，新生成的newPermits必然也会很多，需要有一个maxPermits限制最大值，maxPermits默认就是你设置的速率（比如1s5个permits，maxPermits就是5）
      nextFreeTicketMicros = nowMicros;//更新nextFreeTicketMicros为nowMicros
    }
  }

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros); //精髓所在，每次请求才更新storedPermits和nextFreeTicketMicros
    long returnValue = nextFreeTicketMicros; //直接返回上面计算出来的nextFreeTicketMicros，这也是能应对突发高qps的原因，只会把nextFreeTicketMicros延后，影响下一次请求
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros); //请求超过存储的permits，计算nextFreeTicketMicros延后的时间

    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    this.storedPermits -= storedPermitsToSpend;  //storedPermits减去当前请求消耗的permits，如果当前请求的permits大于storedPermits也不管，减到0为止，同时延后nextFreeTicketMicros即可
    return returnValue;
  }

tryAcquire原理

private boolean canAcquire(long nowMicros, long timeoutMicros) {
    return nextFreeTicketMicros - timeoutMicros <= nowMicros;
  }

public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
    long timeoutMicros = max(unit.toMicros(timeout), 0);
    checkPermits(permits);
    long microsToWait;
    synchronized (mutex()) {
      long nowMicros = stopwatch.readMicros();
    //只是计算nextFreeTicketMicro和timeoutMicros的差值，如果大于nowMicros直接返回false;否则计算出
      if (!canAcquire(nowMicros, timeoutMicros)) {
        return false;
      } else {
//调用reserveEarliestAvailable(设置新的nextFreeTicketMicros和storedPermits)，返回nextFreeTicketMicros，计算需要等待的时间
        microsToWait = reserveAndGetWaitLength(permits, nowMicros);
      }
    }
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return true;
  }

下面我们看看SmoothWarmingUp创建的ratelimiter，它是带有预热期的平滑限流，它启动后会有一段预热期，逐步将分发频率提升到配置的速率，

创建一个平均分发令牌速率为5，预热期为3秒。由于设置了预热时间是3秒，令牌桶一开始并不会0.2秒发一个令牌，而是形成一个平滑线性下降的坡度，频率越来越高，在3秒钟之内达到原本设置的频率，以后就以固定的频率输出。这种功能适合系统刚启动需要一点时间来“热身”的场景。