目录
为什么要限速?
速率限制策略速率限制可应用于以下参数:
1、漏桶算法
2、令牌桶算法
3、固定时间窗⼝算法
4、滑动时间窗⼝算法
总结
首页 科技周边 人工智能 四种常用限流算法掌握一身,面试必过

四种常用限流算法掌握一身,面试必过

Nov 15, 2023 am 11:22 AM
漏桶算法 限流算法 令牌桶算法

四种常用限流算法掌握一身,面试必过

在高并发访问下,比如电商大促活动,流量持续不断的涌入,服务之间的相互调用频率突然增加,引发系统负载过高,这时系统所依赖的服务的稳定性对系统的影响非常大,而且还有很多不确定因素引起雪崩,如网络连接中断,服务宕机等。一般微服务容错组件提供了限流、隔离、降级、熔断等手段,可以有效保护我们的微服务系统。本文主要说说限流。

限流,就是限制最大流量,防止操作频率超过定义的限制。系统能提供的最大并发有限,同时请求又太多,这就就需要限流,比如秒杀、大促活动业务,瞬时大量请求涌入,服务器服务不过来,就只好限流了。速率限制通过限制在给定时间段内可以到达 API 的请求数量来保护服务免受意外或恶意过度使用。在没有速率限制的情况下,任何用户都可以用请求轰炸您的服务器,从而导致其他用户饿死的情况。

为什么要限速?

  • 防止资源匮乏:速率限制的最常见原因是通过避免资源匮乏来提高基于 API 的服务的可用性。如果应用速率限制,则可以防止基于负载的拒绝服务 (doS) 攻击。即使一个用户用大量请求轰炸 API,其他用户也不会挨饿。
  • 安全性:速率限制可防止暴力破解登录、促销代码等安全密集型功能。对这些功能的请求数量在用户级别受到限制,因此暴力破解算法在这些场景中不起作用。
  • 防止运营成本:在按使用付费模式自动扩展资源的情况下,速率限制通过对资源扩展设置虚拟上限来帮助控制运营成本。如果不采用速率限制,资源可能会不成比例地扩展,从而导致指数级的账单。

速率限制策略速率限制可应用于以下参数:

  • 用户:限制在给定时间段内允许用户的请求数。基于用户的速率限制是最常见和最直观的速率限制形式之一。
  • 并发性:这里限制了在给定时间范围内用户可以允许的并行会话数。并行连接数量的限制也有助于缓解 DDOS 攻击。
  • 位置/ID:这有助于运行基于位置或以人口统计为中心的活动。可以限制不是来自目标人口统计的请求,以提高目标区域的可用性
  • 服务器:基于服务器的速率限制是一种利基策略。这通常在特定服务器需要大部分请求时使用,即服务器与特定功能强耦合

接下来,我们将介绍四种常见的限流算法

1、漏桶算法

漏桶算法的思路,是一种简单直观的算法,就是⼀个固定容量的漏桶,按照常量固定速率流出⽔滴。如果桶是空的,则不需流出水滴。可以以任意速率流入水滴到漏桶。如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。

这种算法的优点是它可以平滑请求的突发并以恒定的速率处理它们。它也很容易在负载均衡器上实现,并且对每个用户来说都是高效的内存。无论请求的数量如何,都保持到服务器的恒定接近均匀的流量。

缺点是请求的爆发可能会填满存储桶,导致新请求的匮乏。它也不能保证请求在给定的时间内完成。

四种常用限流算法掌握一身,面试必过

优点:

  • 平滑流量。由于漏桶算法以固定的速率处理请求,可以有效地平滑和整形流量,避免流量的突发和波动(类似于消息队列的削峰填谷的作用)。
  • 防止过载。当流入的请求超过桶的容量时,可以直接丢弃请求,防止系统过载。

缺点:

  • 无法处理突发流量:由于漏桶的出口速度是固定的,无法处理突发流量。例如,即使在流量较小的时候,也无法以更快的速度处理请求。
  • 可能会丢失数据:如果入口流量过大,超过了桶的容量,那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中,这可能是一个问题。

2、令牌桶算法

令牌桶算法:假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌。桶中最多存放b个令牌,当桶满时,新添加的令牌被丢弃或拒绝。当一个n个字节大小的数据包到达,将从桶中删除n个令牌,接着数据包被发送到网络上。如果桶中的令牌不足n个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么缓冲区等待)。令牌桶限流原理,如图所示。


四种常用限流算法掌握一身,面试必过

限流服务器端的令牌桶可以根据实际服务性能和时间段来调整生成令牌的速度和桶的容量。当需要提高速率时,可以按需增加放入桶中的令牌速率

生成令牌的速度是恒定的,而请求获取令牌的速度没有限制。这意味着当面对瞬时大流量时,该算法可以在短时间内获取大量令牌,而且获取令牌的过程并不会消耗很多资源

当每次新的请求到达服务器时,会执行两个操作:

  • 获取令牌:获取该用户的当前令牌数。如果它大于定义的限制,则丢弃请求。
  • 更新令牌:如果获取的令牌小于持续时间 d 的限制,则接受请求并附加令牌。

该算法具有内存效率,因为我们为我们的应用程序为每个用户节省了更少的数据量。这里的问题是它可能导致分布式环境中的竞争条件。当来自两个不同应用程序服务器的两个请求同时尝试获取令牌时,就会发生这种情况。

优点:

  • 可以处理突发流量:令牌桶算法可以处理突发流量。当桶满时,能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
  • 限制平均速率:在长期运行中,数据的传输率会被限制在预定义的平均速率(即生成令牌的速率)。
  • 灵活性:与漏桶算法相比,令牌桶算法提供了更大的灵活性。例如,可以动态地调整生成令牌的速率。

缺点:

  • 可能导致过载:如果令牌产生的速度过快,可能会导致大量的突发流量,这可能会使网络或服务过载。
  • 需要存储空间:令牌桶需要一定的存储空间来保存令牌,可能会导致内存资源的浪费。
  • 实现稍复杂:相比于计数器算法,令牌桶算法的实现稍微复杂一些。

3、固定时间窗⼝算法

在固定的时间窗口内,允许一定数量的请求进入。超过数量则拒绝或排队等待下一个时间段。这种计数器限流的实现方式是在时间间隔内进行限制。如果用户在上一个时间间隔结束前发送请求(但未超过限制),同时在当前时间间隔开始时也发送请求(同样未超过限制),那么在各自的时间间隔内,这些请求都是正常的。然而,当请求在时间间隔的临界时间段内超过系统限制时,可能会导致系统过载

四种常用限流算法掌握一身,面试必过

由于计数器算法存在时间临界点缺陷,因此在时间临界点左右的极短时间段内容易遭到攻击。比如设定每分钟最多可以请求100次某个接口,如12:00:00-12:00:59时间段内没有数据请求,而12:00:59-12:01:00时间段内突然并发100次请求,而紧接着跨入下一个计数周期,计数器清零,在12:01:00-12:01:01内又有100次请求。那么也就是说在时间临界点左右可能同时有2倍的阀值进行请求,从而造成后台处理请求过载的情况,导致系统运营能力不足,甚至导致系统崩溃。

缺点:

  • 限流不够平滑。例如:限流是每秒3个,在第一毫秒发送了3个请求,达到限流,窗口剩余时间的请求都将会被拒绝,体验不好。
  • 无法处理窗口边界问题。因为是在某个时间窗口内进行流量控制,所以可能会出现窗口边界效应,即在时间窗口的边界处可能会有大量的请求被允许通过,从而导致突发流量。

例如:限流是每秒3个,在第一秒的最后一毫秒发送了3个请求,在第二秒的第一毫秒又发送了3个请求。在这两毫米内处理了6个请求,但是并没有触发限流。如果出现突发流量,可能会压垮服务器。

4、滑动时间窗⼝算法

滑动窗⼝算法是把固定时间间进行划分,并且随着时间移动,移动方式为开始时间点变为时间列表中的第二时间点,结束时间点增加一个时间点,不断重复,通过这种方式可以巧妙的避开计数器的临界点的问题。

滑动窗口算法可以有效的规避计数器算法中时间临界点的问题,但是仍然存在时间片段的概念。同时滑动窗口算法计数运算也相对固定时间窗口算法比较耗时。

四种常用限流算法掌握一身,面试必过

缺点: 还是存在限流不够平滑的问题。例如:限流是每秒3个,在第一毫秒发送了3个请求,达到限流,剩余窗口时间的请求都将会被拒绝,体验不好。

总结

介绍了四种常用的限流算法:固定窗口算法、滑动窗口算法、漏桶算法和令牌桶算法。每种算法都有其特点和适用场景,下面我们来对它们进行简单的总结和比较。

  • 令牌桶算法既能平滑流量,又能处理突发流量,适用于需要处理突发流量的场景。
  • 漏桶算法的优点是流量处理更平滑,但是无法应对突发流量,适用于需要平滑流量的场景。
  • 固定窗口算法 实现简单,但是限流不够平滑,存在窗口边界问题,适用于需要简单实现限流的场景。
  • 滑动窗口算法解决了窗口边界问题,但是还是存在限流不够平滑的问题,适用于需要控制平均请求速率的场景。

以上是四种常用限流算法掌握一身,面试必过的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

我尝试了使用光标AI编码的Vibe编码,这太神奇了! 我尝试了使用光标AI编码的Vibe编码,这太神奇了! Mar 20, 2025 pm 03:34 PM

Vibe编码通过让我们使用自然语言而不是无尽的代码行创建应用程序来重塑软件开发的世界。受Andrej Karpathy等有远见的人的启发,这种创新的方法使Dev

2025年2月的Genai推出前5名:GPT-4.5,Grok-3等! 2025年2月的Genai推出前5名:GPT-4.5,Grok-3等! Mar 22, 2025 am 10:58 AM

2025年2月,Generative AI又是一个改变游戏规则的月份,为我们带来了一些最令人期待的模型升级和开创性的新功能。从Xai的Grok 3和Anthropic的Claude 3.7十四行诗到Openai的G

如何使用Yolo V12进行对象检测? 如何使用Yolo V12进行对象检测? Mar 22, 2025 am 11:07 AM

Yolo(您只看一次)一直是领先的实时对象检测框架,每次迭代都在以前的版本上改善。最新版本Yolo V12引入了进步,可显着提高准确性

Sora vs veo 2:哪个创建更现实的视频? Sora vs veo 2:哪个创建更现实的视频? Mar 10, 2025 pm 12:22 PM

Google的VEO 2和Openai的Sora:哪个AI视频发电机占据了至尊? 这两个平台都产生了令人印象深刻的AI视频,但它们的优势在于不同的领域。 使用各种提示,这种比较揭示了哪种工具最适合您的需求。 t

Google的Gencast:Gencast Mini Demo的天气预报 Google的Gencast:Gencast Mini Demo的天气预报 Mar 16, 2025 pm 01:46 PM

Google DeepMind的Gencast:天气预报的革命性AI 天气预报经历了巨大的转变,从基本观察到复杂的AI驱动预测。 Google DeepMind的Gencast,开创性

Chatgpt 4 o可用吗? Chatgpt 4 o可用吗? Mar 28, 2025 pm 05:29 PM

Chatgpt 4当前可用并广泛使用,与诸如ChatGpt 3.5(例如ChatGpt 3.5)相比,在理解上下文和产生连贯的响应方面取得了重大改进。未来的发展可能包括更多个性化的间

哪个AI比Chatgpt更好? 哪个AI比Chatgpt更好? Mar 18, 2025 pm 06:05 PM

本文讨论了AI模型超过Chatgpt,例如Lamda,Llama和Grok,突出了它们在准确性,理解和行业影响方面的优势。(159个字符)

O1 vs GPT-4O:OpenAI的新型号比GPT-4O好吗? O1 vs GPT-4O:OpenAI的新型号比GPT-4O好吗? Mar 16, 2025 am 11:47 AM

Openai的O1:为期12天的礼物狂欢始于他们迄今为止最强大的模型 12月的到来带来了全球放缓,世界某些地区的雪花放缓,但Openai才刚刚开始。 山姆·奥特曼(Sam Altman)和他的团队正在推出12天的礼物前

See all articles