就这么几个限流算法，总是记了又忘！！！

什么是限流？

限流，限流，就是限制流量。

在日常生活中，我们经常能看到一些限流场景，比如旅游景点限流、餐厅排队等号、交通限流等，目的就是为了确保可以正常运转。

同样，在我们进行应用开发时，也需要把应用系统的限流做好，避免突发流量、恶意攻击等大量请求的冲击带来不必要的影响，确保业务系统的正常运行。

如何限流？

首先我们需要知道限流的基本思路，其次需要知道限流的几种实现方式（这里我们叫限流算法）。

限流的基本思路就是：在一个单位时间内流量超过某个阈值后被拒绝或限制。

目前常见的限流算法有4个：

1. 计数器，也叫固定时间窗口算法。
2. 滑动时间窗口算法。
3. 漏斗算法。
4. 令牌算法。

下面分别对这4种限流算法进行介绍，并通过Java代码实现简单的限流功能。

计数器（固定时间窗口）算法

原理

计数器（固定时间窗口）算法是最简单的限流算法。简单来讲就是：在固定时间内累计访问次数，当次数达到阈值后，触发限流（拒绝访问或者排队等待）。

如下图，在0～1s内，如果counter>=100，那么在这个时间内就不会再接受新的请求，一直到1s后将counter进行重置。

代码实现

代码实现也相对简单：

通过维护一个单位时间内的计数值，每当一个请求通过时，就将计数值加1，当计数值超过预先设定的阈值时，就拒绝单位时间内的其他请求。如果单位时间已经结束，则将计数器清零，开启下一轮的计数。

临界值问题

但是固定时间窗口算法会存在一个问题，举个例子:

假设设定1s内允许通过的请求阈值是100，如果在时间窗口的最后几毫秒发送了99个请求，紧接着又在下一个时间窗口开始时发送了99个请求，这样显然在一秒超过了阈值。如下图

但又因为时间窗口原因，这99个请求不会被限流，就可能会对系统造成影响。

这就是临界值问题，那么临界值问题要怎么解决呢？

很简单：当请求来临时，往前推1s的时间范围内，如请求数超过100，就进行限流。

于是就有了滑动时间窗口算法。

滑动时间窗口算法

原理

滑动时间窗口算法是这样的：将一个大的时间窗口分割成多个小的时间窗口，当请求到达当前的时间窗口时，聚合前面的时间窗口的计数值是否超过设定的阈值。

假设设定1秒内允许通过的请求是200个，这里把1秒的时间分成多格，假设分成5格（格数越多，流量过渡越平滑），每格窗口的时间大小是200毫秒，每过200毫秒，就将窗口向前移动一格。通过观察下图，可以得知在当前窗口只要超过110就会被限流。

代码实现

代码实现要关注几个点：

1. 要存储每个小窗口的计数值。
2. 超出时间范围的窗口要被移除，同时添加新的窗口。

这里我用了 LinkedList 作为分割窗口，可以快速的实现功能。

临界值问题

那么滑动窗口限流法是完美的吗？细心观察应该能马上发现问题，如下图：

没错，滑动时间窗口限流法依然存在临界值的问题。流量的过渡是否平滑依赖于我们设置的窗口格数，格数越多，统计越精确。但是具体要分多少格呢？

于是乎，就有了漏桶算法。

漏桶算法

原理

漏桶算法就是一个拥有固定容量的容器，用以承载流量。

当流量超出桶的容量时，多余的流量就会被丢弃，确保不会过载。而在桶内的流量，则以恒定的速率平稳流出，从而实现了对流量访问的平滑控制。这样，漏桶不仅有效地限制了流量的突发，还保证了流量的稳定输出。

image.png

代码实现

在进行漏桶算法实现时，要关注几个点：

1. 需要一个容器作为漏桶。
2. 以固定速率对容器进行移除。

这里我用了 ArrayBlockingQueue 作为漏桶，可以快速的实现功能。

不支持突发流量

因为漏桶算法的流出速率是固定的，所以漏桶算法不支持突发流量。但是在实际情况下，流量往往是突发的。

那如何改进呢？

于是乎，就有了令牌桶算法。

令牌桶算法

原理

令牌桶算法是如何支持突发流量的呢？

与漏桶算法不同，令牌桶的漏桶中存放的是令牌而不是流量。

最开始，令牌桶是空的，我们以恒定速率往令牌桶里加入令牌，当桶被装满时，多余的令牌会被丢弃。

当请求到来时，会从令牌桶获取令牌，获取成功则请求被放行，获取失败则阻塞或拒绝请求。那么当突发流量来临时，只要令牌桶有足够的令牌，就不会被限流。

代码实现

令牌桶算法的实现与漏桶算法类似

限流算法应用场景

无论哪个限流算法，都有各自的适用场景和优缺点，具体选择哪种算法需要根据实际的业务需求和系统环境进行考虑。

例如，对于需要平滑处理流量的场景，可以选择滑动窗口算法或漏桶算法。而对于需要应对突发大流量的场景，令牌桶算法可能更合适。

总结

在工作中，我们可能会使用现成的限流组件，如Spring Cloud的Hystrix、Spring Cloud Alibaba的Sentinel，或者是Google的Guava限流器。

但是，无论哪个组件，背后的实现原理都离不开这四种限流算法。作为开发人员，我们不仅要会用这些工具，还要做到知其然，知其所以然。

我正在参与2024腾讯技术创作特训营最新征文，快来和我瓜分大奖！