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

前言

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

考察点

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

回答  

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

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

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

图片

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

图片

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

图片

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

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