常用的限流算法有哪些?你听说过几种?

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 限流,就是指限制流量请求的频次。在高并发情况下,它是一种保护系统的策略,避免了在流量高峰时系统崩溃,造成系统的不可用。

限流,就是指限制流量请求的频次。

在高并发情况下,它是一种保护系统的策略,避免了在流量高峰时系统崩溃,造成系统的不可用。

常见的限流算法有:

计数器限流算法

滑动窗口限流算法

漏桶限流算法

令牌桶限流算法

1. 计数器限流算法

计数器限流算法,是一种简单且直观的限流方法。它通过维护一个计数器变量来限制在特定时间间隔内的请求数量。这种算法的实现原理是在一段时间间隔内(如1分钟)对请求进行计数,并将计数结果与设置的最大请求数进行比较。如果请求数超过了最大值,则进行限流处理。当达到时间间隔的终点时,计数器会被清零,重新开始计数。计数器算法也被称为固定窗口算法。

比如限流100次/分钟可以这样实现:给定一个变量counter来记录处理的请求数量,当1分钟之内处理一个请求之后counter+1,1分钟之内的如果counter=100的话,后续的请求就会被全部拒绝。等到 1分钟结束后,将counter回归成0,重新开始计数。

计数器限流算法的实现可以非常简单,只需要一个计数器变量即可,每来一个请求就进行计数操作,无需复杂的逻辑设计。它直观易懂,设置明确的阈值,比如规定每秒允许的请求数,易于理解和配置。

计数器算法也有其局限性——窗口切换时的突增问题,在固定窗口算法中,当达到时间窗口切换点时,如果请求数突然增加,可能会导致短时间内大量请求通过限流检查,这被称为“突增问题”。

计数器算法还可以通过使用原子变量和循环数组等数据结构来优化实现,以支持分布式环境下的限流需求。

2. 滑动窗口限流算法

滑动窗口限流算法,本质上也是一种计数器。

它通过对时间窗口的滑动来管理请求的计数,从而实现对请求速率的限制。

与固定窗口算法相比,滑动窗口算法将时间窗口分为多个小周期,每个小周期都有自己的计数器。随着时间的滑动,过期的小周期数据被删除,这样可以更精确地控制流量。

比如,我们的接口限流每分钟处理60个请求,我们可以把 1 分钟分为60个窗口。每隔1秒移动一次,每个窗口一秒只能处理 不大于 60(请求数)/60(窗口数) 的请求, 如果当前窗口的请求计数总和超过了限制的数量的话就不再处理其他请求。

滑动窗口限流算法的实现原理可以概括为:

定义时间窗口:首先,需要定义一个时间窗口的大小,例如1分钟。

记录请求:每次有请求时,使用某种数据结构(如Redis中的zset)将这条请求记录下来。

滑动窗口操作:随着时间轴向右移动,滑动窗口的思想是只保留当前时间窗口内的请求记录,而丢弃当前窗口之外的记录。当下次有请求进来时,我们只需要判断当前窗口内的请求是否超过阈值即可。

限流策略:如果当前窗口内的请求数量超过了设定的阈值,则进行限流,不允许继续进行请求。否则,允许请求通过。

滑动窗口限流算法的优势在于其能够更精确地控制流量,尤其是在处理短时间内突发的高请求量时。通过动态调整时间窗口的起始点和结束点,可以有效地平滑流量波动,避免系统因瞬间高负载而崩溃。此外,滑动窗口限流算法还适用于需要精细控制访问频率的场景,如API接口访问限制、防止恶意攻击等。

在实际应用中,滑动窗口限流算法可以通过Redis等缓存系统实现,利用其提供的数据结构(如有序集合zset)来高效地管理请求记录和执行滑动窗口操作。这种实现方式不仅性能高效,还能够利用Redis的持久化和分布式特性,提高系统的可用性和可扩展性。

Spring Cloud 中的熔断框架 Hystrix,以及 Spring Cloud Alibaba中的Sentinel 都采用滑动窗口来做数据统计。

3. 漏桶限流算法

漏桶算法通过一个带有恒定流出速度的漏桶来模拟数据流量的处理过程。无论数据流入的速度如何变化,漏桶的流出速度始终保持不变。

基于MQ实现的 生产者-消费者 模型,就是一种漏桶限流算法。

漏桶限流算法的工作机制:

数据流入:当数据包到达时,它们被放入漏桶中。如果漏桶未满,数据包将被接受并排队等待处理;如果漏桶已满,则根据算法策略处理(如丢弃数据包)。

数据流出:漏桶中的数据以恒定的速率(r字节/秒)流出,注入网络。这个过程模拟了网络流量的平滑处理。

限流策略:

当请求速度大于漏桶的流出速度时,即请求量大于当前服务所能处理的最大极限值时,触发限流策略。此时,如果漏桶已满,新到达的数据包将被丢弃。

当请求速度小于或等于漏桶的漏出速度时,即服务的处理能力大于或等于请求量时,正常执行。

漏桶算法能够提供一个稳定的流量输出,有效避免突发流量对系统的冲击。所有请求都按照相同的速率被处理,保证了公平性。

漏桶算法的漏出速率是固定的,无法应对需要突发传输的场景。在网络未发生拥塞时,漏桶算法可能无法充分利用网络资源。

4. 令牌桶限流算法

令牌桶算法使用一个固定容量的桶来存放令牌,这些令牌以恒定的速率被添加到桶中。当数据包需要发送到网络时,它们会消耗桶中的令牌。如果桶中有足够的令牌,数据包将被允许发送;否则,数据包可能需要等待或被丢弃。

相对于漏桶限流算法来说,令牌桶限流算法可以处理突发流量的问题。

只要桶中有足够的令牌,就可以以峰值速率发送流量。

通过调整令牌桶的容量和令牌生成速率,可以灵活地控制流量的平滑程度和突发程度。

令牌桶限流算法工作机制:

令牌生成:令牌桶以恒定的速率(CIR/EIR)生成令牌,并将它们添加到桶中。如果桶已经满了,新生成的令牌将被丢弃。

令牌消耗:当数据包需要发送到网络时,它们会根据自身的大小从桶中消耗相应数量的令牌。不同大小的数据包消耗的令牌数量不同。

流量控制:

如果桶中有足够的令牌,数据包将被允许发送。

如果桶中令牌不足,数据包可能需要等待直到桶中积累了足够的令牌,或者根据配置的策略被处理(如丢弃、排队或特殊标记)。

网关层面的限流或者接口调用的限流,都可以使用令牌桶算法。

在视频、音频等多媒体数据的传输中,使用令牌桶算法来确保数据的流畅传输,同时允许一定程度的突发传输以适应网络波动。

Google的Guava和 Redisson的限流,都用到了令牌桶算法。

限流的本质是实现系统的保护,最终选择什么样的算法,一方面取决于统计的精准度要求,另外一方面要考虑限流维度和场景的要求。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
3月前
|
算法 NoSQL Java
spring cloud的限流算法有哪些?
【8月更文挑战第18天】spring cloud的限流算法有哪些?
83 3
|
4月前
|
存储 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
|
4月前
|
算法 Java 调度
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
|
4月前
|
缓存 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
|
4月前
|
算法 UED 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
|
4月前
|
存储 算法 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
|
4月前
|
算法 API 缓存
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
|
4月前
|
监控 算法 Java
详解 Java 限流接口实现问题之避免令牌桶限流算法可能导致的过载问题如何解决
详解 Java 限流接口实现问题之避免令牌桶限流算法可能导致的过载问题如何解决
|
4月前
|
算法 Java
详解 Java 限流接口实现问题之漏桶限流算法的缺点问题如何解决
详解 Java 限流接口实现问题之漏桶限流算法的缺点问题如何解决
|
4月前
|
算法 Java UED
详解 Java 限流接口实现问题之滑动窗口限流算法的缺点如何解决
详解 Java 限流接口实现问题之滑动窗口限流算法的缺点如何解决