图解高并发限流
图解高并发限流
背景
在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流
- 缓存：缓存的目的是提升系统访问速度和增大系统处理容量
- 降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行
- 限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理
我们经常在调别人的接口的时候会发现有限制，比如微信公众平台接口、高等API等等，对方会限制每天最多调多少次或者每分钟最多调多少次
限流算法
计数器
在指定周期内累加访问次数，当访问次数达到设定的阈值时，出发限流策略，当进入下一个时间周期时会将访问次数清零
优缺点：实现起来比较简单，但会出现「临界问题」，如上图，短时间内的访问量超过1000，大于了规定的10s内的访问量不超过500的限定
滑动窗口
将固定窗口中分割出多个小时间窗口，分别在每个小的时间窗口中记录访问次数，然后根据时间将窗口往前滑动并删除过期的小时间窗口
优缺点：实现简单，但存在突刺现象(如果在单位时间10秒内的前100ms，通过了500个请求，则后面的990ms都无法接受任何请求，也就无法应对短时间高并发)
漏桶
水流速度不定， 漏桶水滴的流出速度始终保持不变
优缺点：起到削峰的作用，可以应对突发流量，不足之处是无法应对突发的并发流量
令牌桶
令牌桶是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法
- 当请求速度大于令牌的生成速度，令牌会被拿完后限流
- 当请求速度等于令牌的生成速度，流量正常稳定处理
- 当请求速度小于令牌的生成速度，请求可以被正常处理，且多余的令牌被丢弃
令牌桶和漏桶对比
- 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
- 令牌桶限制的是平均流入速率，允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌；漏桶限制的是常量流出速率，即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2，从而平滑突发流入速率；
- 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流出速率；
RateLimiter源码赏析
Guava有两种限流模式，一种为稳定模式(SmoothBursty:令牌生成速度恒定)，一种为渐进模式(SmoothWarmingUp:令牌生成速度缓慢提升直到维持在一个稳定值)
RateLimiter构造方法
public static RateLimiter create(double permitsPerSecond) {return create(RateLimiter.SleepingStopwatch.createFromSystemTimer(), permitsPerSecond);}@VisibleForTestingstatic RateLimiter create(RateLimiter.SleepingStopwatch stopwatch, double permitsPerSecond) {RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0D);rateLimiter.setRate(permitsPerSecond);return rateLimiter;}
其它是一些接口方法,常用到的是acquire()和tryAcquire()：
public double acquire() {}
public double acquire(int permits) {}public boolean tryAcquire() {}
public boolean tryAcquire(int permits) {}
public boolean tryAcquire(long timeout, TimeUnit unit) {}
public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {}public final double getRate() {}
public final void setRate(double permitsPerSecond) {}
两个属性:
//计时，以后的时间都是相对时间
private final RateLimiter.SleepingStopwatch stopwatch;
//锁，RateLimiter依赖synchronized来控制并发
private volatile Object mutexDoNotUseDirectly;
SmoothRateLimiter
属性
// 当前还有多少permits没有被使用，被存下来的 permits 数量
double storedPermits;
// 最大允许缓存的 permits 数量，也就是 storedPermits 能达到的最大值
double maxPermits;
// 每隔多少时间产生一个 permit， 假如构造方法中设置每秒5个，也就是每隔 200ms 一个，这里单位是微秒，也就是 200,000
double stableIntervalMicros;
// 下一次可以获取 permits 的时间，这个时间是相对 RateLimiter 的构造时间的，是一个相对时间
private long nextFreeTicketMicros
SmoothBursty
构造方法
- 1.0的参数传进去，赋值给变量maxBurstSeconds，也就是说最多会缓存1秒钟，会有1.0 * permitsPerSecond这么多的permits到候选池中，会带来如下的影响：
0 <= storedPermits <= maxPermits = permitsPerSecond
static RateLimiter create(RateLimiter.SleepingStopwatch stopwatch, double permitsPerSecond) {RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0D);rateLimiter.setRate(permitsPerSecond);return rateLimiter;}SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {super(stopwatch, null);this.maxBurstSeconds = maxBurstSeconds;
}
setRate
//调整速率
public final void setRate(double permitsPerSecond) {Preconditions.checkArgument(permitsPerSecond > 0.0D && !Double.isNaN(permitsPerSecond), "rate must be positive");//synchronized关键字修饰控制并发synchronized(this.mutex()) {this.doSetRate(permitsPerSecond, this.stopwatch.readMicros());}
}
doSetRate & resync
final void doSetRate(double permitsPerSecond, long nowMicros) {this.resync(nowMicros);//同步调整参数//计算stableIntervalMicros属性// 每隔多少时间产生一个 permit， 假如构造方法中设置每秒5个，也就是每隔 200ms 一个，这里单位是微秒，也就是 200,000double stableIntervalMicros = (double)TimeUnit.SECONDS.toMicros(1L) / permitsPerSecond;this.stableIntervalMicros = stableIntervalMicros;this.doSetRate(permitsPerSecond, stableIntervalMicros);
}//调整storedPermits和nextFreeTicketMicros的值void resync(long nowMicros) {//如果nextFreeTicket已经过期了需要重新rebase nextFreeTicket 到当前的时间if (nowMicros > this.nextFreeTicketMicros) {this.storedPermits = Math.min(this.maxPermits, this.storedPermits + (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros());this.nextFreeTicketMicros = nowMicros;}}
doSetRate
- resync方法后，进入到doSetRate方法，计算storedPermits的值
- 这个方法，原来的 RateLimiter 是用某个 permitsPerSecond 值初始化的，现在要调整这个频率。对于 maxPermits 来说，是重新计算，而对于 storedPermits 来说，是做等比例的缩放
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {double oldMaxPermits = this.maxPermits;this.maxPermits = this.maxBurstSeconds * permitsPerSecond;if (oldMaxPermits == 1.0D / 0.0) {this.storedPermits = this.maxPermits;} else {this.storedPermits = oldMaxPermits == 0.0D ? 0.0D : this.storedPermits * this.maxPermits / oldMaxPermits;}}
acquire
public double acquire() {return this.acquire(1);}public double acquire(int permits) {//如果当前不能获取到permits，需要返回需要等到的时间长度microsToWaitlong microsToWait = this.reserve(permits);this.stopwatch.sleepMicrosUninterruptibly(microsToWait);//返回等待的时长return 1.0D * (double)microsToWait / (double)TimeUnit.SECONDS.toMicros(1L);}final long reserve(int permits) {checkPermits(permits);synchronized(this.mutex()) {return this.reserveAndGetWaitLength(permits, this.stopwatch.readMicros());}}final long reserveAndGetWaitLength(int permits, long nowMicros) {//返回nextFreeTicketMicroslong momentAvailable = this.reserveEarliestAvailable(permits, nowMicros);//计算时长return Math.max(momentAvailable - nowMicros, 0L);}
reserveEarliestAvailable
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {// 同步，更新 storedPermits 和 nextFreeTicketMicros resync(nowMicros);// 返回值 nextFreeTicketMicros，刚刚已经做了 resync 了，此时它是最新的正确的值long returnValue = nextFreeTicketMicros;// storedPermits 中可以使用多少个 permitsdouble storedPermitsToSpend = min(requiredPermits, this.storedPermits);// storedPermits 中不够的部分double freshPermits = requiredPermits - storedPermitsToSpend;// 为了这个不够的部分，需要等待多久时间long waitMicros =storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) // 这部分固定返回 0+ (long) (freshPermits * stableIntervalMicros);// 将 nextFreeTicketMicros 往前推try {this.nextFreeTicketMicros = LongMath.checkedAdd(this.nextFreeTicketMicros, waitMicros);} catch (ArithmeticException var13) {this.nextFreeTicketMicros = 9223372036854775807L;}// storedPermits 减去被拿走的部分this.storedPermits -= storedPermitsToSpend;return returnValue;
}
- 获取 permits 的时候，其实是获取了两部分，一部分来自于存量 storedPermits，存量不够的话，另一部分来自于预占未来的 freshPermits,返回值是 nextFreeTicketMicros 的旧值，因为只要到这个时间点，就说明当次 acquire 可以成功返回了，而不管 storedPermits 够不够。如果 storedPermits 不够，会将 nextFreeTicketMicros 往前推一定的时间，预占了一定的量
Reference
- 四种限流算法图解
- Java架构师之高并发限流
- 令牌桶算法限流
- 超详细的Guava RateLimiter限流原理解析
- RateLimiter 源码分析(Guava 和 Sentinel 实现)
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！