计数器限流
最原始的代码
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秒钟之内达到原本设置的频率，以后就以固定的频率输出。这种功能适合系统刚启动需要一点时间来“热身”的场景。
