<返回更多

聊聊常见的限流算法有哪些?

2023-11-28  微信公众号  程序员的故事
加入收藏

前言

今天来分享一道比较好的面试题,“常见的限流算法有哪些?”对于这个问题,我们一起看看考察点和比较好的回答吧!

 

 

考察点

限流算法是一种用于限制流量请求的频率或速率的算法,其目的是在高并发或大流量请求的情况下,保护系统服务的安全性和可用性。限流算法可以应对热点业务带来的突发请求、调用方bug导致的突发请求以及恶意攻击请求等情况。这个问题就是面试官想考察我们是不是平日里善于积累,仔细思考这方面的知识!

回答  

首先,限流算法是一种系统保护策略,主要是避免在流量高峰导致系统被压垮,造成系统不可用的问题。常考的算法有以下几种。

1. (如图)计数器限流,一般用在单一维度的访问频率限制上,比如短信验证码每隔60s 只能发送一次,或者接口调用次数等。它的实现方法很简单,每调用一次就加 1,处理结束以后减一。

 计数器限流算法的实现原理是在一个时间窗口内,每调用一次就增加计数器,当时间窗口到达设定的时间后,计数器归零。如果在时间窗口内再次调用,则计数器再次增加。这种算法的优点是实现简单,但是存在临界问题。如果在一个时间窗口内的最后一次调用正好在时间窗口结束的瞬间,那么这个请求会被拒绝,因为计数器已经归零。为了解决这个问题,可以采用滑动窗口限流算法。该算法将时间窗口划分为多个小的时间段,每个时间段都有一个独立的计数器。当一个时间段结束时,该时间段的计数器归零,而其他时间段的计数器保持不变。这样就可以避免在时间窗口结束的瞬间出现请求被拒绝的情况。

 

聊聊常见的限流算法有哪些?图片

2. (如图)滑动窗口限流,本质上也是一种计数器,只是通过以时间为维度的可滑动窗口设计,来减少了临界值带来的并发超过阈值的问题。每次进行数据统计的时候,只需要统计这个窗口内每个时间刻度的访问量就可以了。Spring Cloud里面的熔断框架Hystrix ,以及Spring Cloud Alibaba里面的Sentinel都采用了滑动窗口来做数据统计。

聊聊常见的限流算法有哪些?图片

3. (如图)漏桶算法,它是一种恒定速率的限流算法,不管请求量是多少,服务端的处理效率是恒定的。基于 MQ 来实现的生产者消费者模型,其实算是一种漏桶限流算法。

聊聊常见的限流算法有哪些?图片

4. (如图)令牌桶算法,相对漏桶算法来说,它可以处理突发流量的问题。它的核心思想是,令牌桶以恒定速率去生成令牌保存到令牌桶里面,桶的大小是固定的,令牌桶满了以后就不再生成令牌。每个客户端请求进来的时候,必须要从令牌桶获得一个令牌才能访问,否则排队等待。在流量低峰的时候,令牌桶会出现堆积,因此当出现瞬时高峰的时候,有足够多的令牌可以获取,因此令牌桶能够允许瞬时流量的处理。网关层面的限流、或者接口调用的限流,都可以使用令牌桶算法,像 google 的 Guava,和 redisson 的限流,都用到了令牌桶算法在我看来,限流的本质是实现系统保护,最终选择什么样的算法,一方面取决于统计的精准度,另一方面考虑限流维度和场景的需求。

以上就是我对于这个问题的理解。

关键词:算法      点击(6)
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多算法相关>>>