为什么要限流
秒杀时特别热卖的商品，会有很多人来抢(不排除黄牛)，不进行限流，有可能把缓存和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的从库，写入主库，这样有可能存在主从延时导致多放请求进来。
