前言:
失踪人口回归,哈哈哈,最近项目比较忙,然后还要学习前端的知识,后端性能治理也比较有挑战性,还是没有太多时间沉下心来写文章,等之后好好补上。
今天1024,在此奉上本人在掘金上面的一篇文章,虽然是在其他平台发布过的文章,但还是很值得学习的。
好了话不多说,下面进入正文。
什么是限流?
限流可以认为服务降级的一种,限流就是限制系统的输入和输出流量已达到保护系统 的目的。一般来说系统的吞吐量是可以被测算的,为了保证系统的稳定运行,一旦达到的需要限制的阈值,就需要限制流量并采取一些措施以完成限制流量的目的。比如:延迟处理,拒绝处理,或者部分拒绝处理等等。接下来我们来讲解一下常见的限流算法。
1.计数器(也可称为固定窗口)
固定窗口,相比其他的限流算法,这应该是最简单的一种。
它简单地对一个固定的时间窗口内的请求数量进行计数,如果超过请求数量的阈值,将被直接丢弃。
比如我们下图中的黄色区域就是固定时间窗口,默认时间范围是60s,限流数量是100。
如图中括号内所示:
- 第一个黄色框(也就是第一个60s),前面一段时间都没有流量,刚好最后面20秒内来了100个请求,为没有超过限流阈值,所以请求全部通过,
- 第二个黄色框(也就是第二个60s),刚开始的20秒内来了100个请求,此时因为按照的是第二个黄色框来计算的,所以这个时候认为刚好达到限流数量,所以通过了100个请求。
此时我们结合第一个黄色框的后20s和第二个黄色框的前20s,这个时候在40s内,是有200个请求通过了,超过了我们限流的阈值,这很有可能让我们的服务崩溃。
这种方式既可以称为计算机,也就是60s内限制计数100个,下个60s内又重新限制100个,这种方式也可以抽象的理解成固定窗口。
2.滑动窗口
刚才我们提到了固定窗口有严重的弊端,所以为了优化这个问题,于是有了滑动窗口算法,顾名思义,滑动窗口就是时间窗口在随着时间推移不停地移动。
如果还是60s,限流数量是100那么就变成如下:
窗口不在固定,以当前时间为窗口末端,往前推60s为一个窗口,计算窗口内的流量是否超过100,超过则执行拒绝策略(可以加入等待队列,可以直接拒绝请求),没超过则放行。
大家可以去看一下滑动窗口的算法,leetcode里面有很多题目都用到了这个,大致差不多。
临界问题:
假设我们1s内的限流阀值是5个请求,0.8~1.0s内(比如0.9s的时候)来了5个请求,落在黄色格子里。时间过了1.0s这个点之后,又来5个请求,落在紫色格子里。如果是固定窗口算法,是不会被限流的,但是滑动窗口的话,每过一个小周期,它会右移一个小格。过了1.0s这个点后,会右移一小格,当前的单位时间段是0.2~1.2s,这个区域的请求已经超过限定的5了,已触发限流啦,实际上,紫色格子的请求都被拒绝啦。
TIPS: 当滑动窗口的格子周期划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。
3.漏桶Leaky bucket
漏桶算法,人如其名,他就是一个漏的桶,不管请求的数量有多少,最终都会以固定的出口流量大小匀速流出,如果请求的流量超过漏桶大小,那么超出的流量将会被丢弃。
也就是说流量流入的速度是不定的,但是流出的速度是恒定的。
漏桶算法的优势是匀速,匀速是优点也是缺点,很多人说漏桶不能处理突增流量,这个说法并不准确。
漏桶本来就应该是为了处理间歇性的突增流量,流量一下起来了,然后系统处理不过来,可以在空闲的时候去处理,防止了突增流量导致系统崩溃,保护了系统的稳定性。
但是,换一个思路来想,其实这些突增的流量对于系统来说完全没有压力,你还在慢慢地匀速排队,其实是对系统性能的浪费。
所以,对于这种有场景来说,令牌桶算法比漏桶就更有优势。
4.令牌桶token bucket
令牌桶算法是指系统以一定地速度往令牌桶里丢令牌,当一个请求过来的时候,会去令牌桶里申请一个令牌,如果能够获取到令牌,那么请求就可以正常进行,反之被丢弃。
- a. 按特定的速率向令牌桶投放令牌,这个速率可以慢慢增减,也可以减少,也可以恒定速率。
- b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;
- c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;
- d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。
现在的令牌桶算法,像Guava和Sentinel的实现都有冷启动/预热的方式,为了避免在流量激增的同时把系统打挂,令牌桶算法会在最开始一段时间内冷启动(可类比JVM中的热机与冷机),随着流量的增加,系统会根据流量大小动态地调整生成令牌的速度,最终直到请求达到系统的阈值。
5.滑动日志
滑动日志是一个比较“冷门”,但是确实好用的限流算法。滑动日志限速算法需要记录请求的时间戳,通常使用有序集合来存储,我们可以在单个有序集合中跟踪用户在一个时间段内所有的请求。
假设我们要限制给定T时间内的请求不超过N,我们只需要存储最近T时间之内的请求日志,每当请求到来时判断最近T时间内的请求总数是否超过阈值。
实现如下:
Copypublic class SlidingLogRateLimiter extends MyRateLimiter {
/**
* 每分钟限制请求数
*/
private static final long PERMITS_PER_MINUTE = 60;
/**
* 请求日志计数器, k-为请求的时间(秒),value当前时间的请求数量
*/
private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();
@Override
public synchronized boolean tryAcquire() {
// 最小时间粒度为s
long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
// 获取当前窗口的请求总数
int currentWindowCount = getCurrentWindowCount(currentTimestamp);
if (currentWindowCount >= PERMITS_PER_MINUTE) {
return false;
}
// 请求成功,将当前请求日志加入到日志中
requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
return true;
}
/**
* 统计当前时间窗口内的请求数
*
* @param currentTime 当前时间
* @return -
*/
private int getCurrentWindowCount(long currentTime) {
// 计算出窗口的开始位置时间
long startTime = currentTime - 59;
// 遍历当前存储的计数器,删除无效的子窗口计数器,并累加当前窗口中的所有计数器之和
return requestLogCountMap.entrySet()
.stream()
.filter(entry -> entry.getKey() >= startTime)
.mapToInt(Map.Entry::getValue)
.sum();
}
}
滑动日志能够避免突发流量,实现较为精准的限流;同样更加灵活,能够支持更加复杂的限流策略,如多级限流,每分钟不超过100次,每小时不超过300次,每天不超过1000次,我们只需要保存最近24小时所有的请求日志即可实现。
灵活并不是没有代价的,带来的缺点就是占用存储空间要高于其他限流算法。
6.总结
-
固定窗口算法实现简单,性能高,但是会有临界突发流量问题,瞬时流量最大可以达到阈值的2倍。
-
为了解决临界突发流量,可以将窗口划分为多个更细粒度的单元,每次窗口向右移动一个单元,于是便有了滑动窗口算法。
滑动窗口当流量到达阈值时会瞬间掐断流量,所以导致流量不够平滑。
-
想要达到限流的目的,又不会掐断流量,使得流量更加平滑?可以考虑漏桶算法!需要注意的是,漏桶算法通常配置一个FIFO的队列使用以达到允许限流的作用。
由于速率固定,即使在某个时刻下游处理能力过剩,也不能得到很好的利用,这是漏桶算法的一个短板。
-
限流和瞬时流量其实并不矛盾,在大多数场景中,短时间突发流量系统是完全可以接受的。令牌桶算法就是不二之选了,令牌桶以固定的速率v产生令牌放入一个固定容量为n的桶中,当请求到达时尝试从桶中获取令牌。
当桶满时,允许最大瞬时流量为n;当桶中没有剩余流量时则限流速率最低,为令牌生成的速率v。
-
如何实现更加灵活的多级限流呢?滑动日志限流算法了解一下!这里的日志则是请求的时间戳,通过计算制定时间段内请求总数来实现灵活的限流。
当然,由于需要存储时间戳信息,其占用的存储空间要比其他限流算法要大得多。
以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的,但是由于机器性能,流量分布不均以及计算数量动态变化等问题,单机限流在分布式场景中的效果总是差强人意。
分布式限流最简单的实现就是利用中心化存储,即将单机限流存储在本地的数据存储到同一个存储空间中,如常见的Redis等。
当然也可以从上层流量入口进行限流,Nginx代理服务就提供了限流模块,同样能够实现高性能,精准的限流,其底层是漏桶算法。
不管黑猫白猫,能抓到老鼠的就是好猫。限流算法并没有绝对的好劣之分,如何选择合适的限流算法呢?不妨从性能,是否允许超出阈值,落地成本,流量平滑度,是否允许突发流量以及系统资源大小限制多方面考虑。文章来源:https://www.toymoban.com/news/detail-442461.html
当然,市面上也有比较成熟的限流工具和框架。如Google出品的Guava中基于令牌桶实现的限流组件,拿来即用;以及alibaba开源的面向分布式服务架构的流量控制框架Sentinel更会让你爱不释手,它是基于滑动窗口实现的。文章来源地址https://www.toymoban.com/news/detail-442461.html
到了这里,关于常见的几种限流算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!