网站建设合同的注意事项,wordpress自定义末班,成都网站原创,asp网站程序限流是我们经常会碰到的东西#xff0c;顾名思义就是限制流量。它能保证我们的系统不会被突然的流量打爆#xff0c;保证系统的稳定运行。像我们生活中#xff0c;地铁就会有很多护栏#xff0c;弯弯绕绕的#xff0c;这个就是一种限流。像我们抢茅台#xff0c;肯定大部…限流是我们经常会碰到的东西顾名思义就是限制流量。它能保证我们的系统不会被突然的流量打爆保证系统的稳定运行。像我们生活中地铁就会有很多护栏弯弯绕绕的这个就是一种限流。像我们抢茅台肯定大部分流量也是会被限流的你的请求可能根本没进到下单等环节就被拦截了。
计数限流
最简单的限流算法就是计数限流了例如系统能同时处理 100 个请求保存一个计数器处理了一个请求计数器加一一个请求处理完毕之后计数器减一。
每次请求来的时候看看计数器的值如果超过阈值要么拒绝。
非常的简单粗暴计数器的值要是存内存中就算单机限流算法。存中心存储里例如 Redis 中集群机器访问就算分布式限流算法。
优点就是简单粗暴单机在 Java 中可用 Atomic 等原子类、分布式就 Redis incr。
缺点就是只有数量没有时间的概念。一秒处理100个请求和一分钟处理100个请求是不一样的。
固定窗口限流
它相比于计数限流主要是多了个时间窗口的概念。计数器每过一个时间窗口就重置。 规则是
在时间窗口内累加访问次数这个时间窗口过了之后计数器清零
缺点就是在临界时间如果出现突发流量的情况会超过阈值。
——|——|——
0 1 2
滑动窗口限流
滑动窗口限流解决固定窗口临界值的问题可以保证在任意时间窗口内都不会超过阈值。
相对于固定窗口滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点因此对内存的占用会比较多。
规则如下假设时间窗口为 1 秒 记录每次请求的时间 统计每次请求的时间 至 往前推 1 秒这个时间窗口内请求数并且 1 秒前的数据可以删除。 统计的请求数小于阈值就记录这个请求的时间并允许通过反之拒绝。 但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。
我们所想的限流场景例如每秒限制 100 个请求。希望请求每 10ms 来一个这样我们的流量处理就很平滑但是真实场景很难控制请求的频率。因此可能存在 5ms 内就打满了阈值的情况。
当然对于这种情况还是有变型处理的例如设置多条限流规则。不仅限制每秒 100 个请求再设置每 10ms 不超过 2 个。
漏桶算法
如下图所示水滴持续滴入漏桶中底部定速流出。如果水滴滴入的速率大于流出的速率当存水超过桶的大小的时候就会溢出。
规则如下 请求来了放入桶中 桶内请求量满了拒绝请求 服务定速从桶内拿请求处理 优点既是缺点流量处理太过平滑。面对突发请求服务的处理速度和平时是一样的这其实不是我们想要的在面对突发流量我们希望在系统平稳的同时提升用户体验即能更快的处理请求而不是和正常流量一样循规蹈矩的处理
令牌桶算法
令牌桶其实和漏桶的原理类似只不过漏桶是定速地流出而令牌桶是定速地往桶里塞入令牌然后请求只有拿到了令牌才能通过之后再被服务器处理。
当然令牌桶的大小也是有限制的假设桶里的令牌满了之后定速生成的令牌会丢弃。
规则 定速的往桶内放入令牌 令牌数量超过桶的限制丢弃 请求来了先向桶内索要令牌索要成功则通过被处理反之拒绝
一般而言我们不需要自己实现限流算法来达到限流的目的不管是接入层限流还是细粒度的接口限流其实都有现成的轮子使用其实现也是用了上述我们所说的限流算法。
比如Google Guava 提供的限流工具类 RateLimiter是基于令牌桶实现的并且扩展了算法支持预热功能。
阿里开源的限流框架 Sentinel 中的匀速排队限流策略就采用了滑动窗口。
Nginx 中的限流模块 limit_req_zone采用了漏桶算法还有 OpenResty 中的 resty.limit.req库等等。
Guava如何实现令牌桶算法
根据令牌桶的原理我们可能第一直觉会觉得使用生产者-消费者模式一个线程定时向阻塞队列添加令牌而请求作为消费线程去获取令牌。如果并发量不大的情况这个实现没有什么问题。但一般情况下使用限流都是高并发的场景而且系统压力已经临界极限了这个时候cpu忙碌放令牌的线程可能没法被及时唤醒造成放令牌延迟同时定时器会创建调度线程也会对系统性能产生影响。
所以Guava没有使用定时线程。它的办法很简单就是通过经过的时间来判断有多少令牌产生并保存下目前的令牌数。
举个例子假设限制1s一个请求。启动之后刚开始没有请求到10秒的时候来了个请求。因为过了10s所以就可以判断有10个令牌产生然后消耗一个剩9个令牌记录下来。又过了10s再来了一个请求。那么又有10个令牌产生消耗一个还剩18个令牌。
通过这种简单的方式就可以实现令牌桶了。 public double acquire(int permits) {long microsToWait reserve(permits); // sleep的时间stopwatch.sleepMicrosUninterruptibly(microsToWait);return 1.0 * microsToWait / SECONDS.toMicros(1L);}final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {resync(nowMicros);long returnValue nextFreeTicketMicros;// 需要消耗储存的令牌的数量double storedPermitsToSpend min(requiredPermits, this.storedPermits);// 需要等待新创建的令牌的数量double freshPermits requiredPermits - storedPermitsToSpend;// 需要等待的时间long waitMicros storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) (long) (freshPermits * stableIntervalMicros);// 下次令牌生成的时间this.nextFreeTicketMicros LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);this.storedPermits - storedPermitsToSpend;return returnValue;/*** Updates {code storedPermits} and {code nextFreeTicketMicros} based on the current time.*/void resync(long nowMicros) {// if nextFreeTicket is in the past, resync to nowif (nowMicros nextFreeTicketMicros) {double newPermits (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();// 存储新生成的令牌storedPermits min(maxPermits, storedPermits newPermits);nextFreeTicketMicros nowMicros;}}sentinel滑动窗口算法 Overridepublic void addPass(int count) {WindowWrapMetricBucket wrap data.currentWindow();wrap.value().addPass(count);}public WindowWrapT currentWindow(long timeMillis) {if (timeMillis 0) {return null;}int idx calculateTimeIdx(timeMillis);// Calculate current bucket start time.long windowStart calculateWindowStart(timeMillis);/** Get bucket item at given time from the array.** (1) Bucket is absent, then just create a new bucket and CAS update to circular array.* (2) Bucket is up-to-date, then just return the bucket.* (3) Bucket is deprecated, then reset current bucket.*/while (true) {WindowWrapT old array.get(idx);if (old null) {WindowWrapT window new WindowWrapT(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));if (array.compareAndSet(idx, null, window)) {// Successfully updated, return the created bucket.return window;} else {// Contention failed, the thread will yield its time slice to wait for bucket available.Thread.yield();}} else if (windowStart old.windowStart()) {return old;} else if (windowStart old.windowStart()) {if (updateLock.tryLock()) {try {// Successfully get the update lock, now we reset the bucket.return resetWindowTo(old, windowStart);} finally {updateLock.unlock();}} else {// Contention failed, the thread will yield its time slice to wait for bucket available.Thread.yield();}} else if (windowStart old.windowStart()) {// Should not go through here, as the provided time is already behind.return new WindowWrapT(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));}}}
