文章目录：

1. 前言 2. 算法介绍 - 计数器法 3. 算法介绍 - 滑动窗口 4. 算法介绍 - 漏桶算法 5. 算法介 绍 - 令牌桶算法

前言

在一个高并发零碎中对流量的把控是十分重要的，当微小的流量间接申请到咱们的服务器上没多久就可能造成接口不可用，不解决的话甚至会造成整个利用不可用。

所以什么是限流呢？顾名思义，限流就是限度流量，打个比方，你宽带包了 1 个 G 的流量，流量耗尽了，就没有了。通过限流，咱们能够很好地控制系统的 qps，从而达到爱护零碎的目标。本篇文章将会介绍一下罕用的限流算法以及他们各自的特点。

算法介绍

计数器法

计数器法是限流算法里最简略也是最容易实现的一种算法。比方咱们规定，对于 A 接口来说，咱们 1 分钟的拜访次数不能超过 100 个。那么咱们能够这么做：在一开始的时候，咱们能够设置一个计数器 counter，每当一个申请过去的时候，counter 就加 1，如果 counter 的值大于 100 并且该申请与第一个申请的间隔时间还在 1 分钟之内，那么阐明申请数过多；如果该申请与第一个申请的间隔时间大于 1 分钟，且 counter 的值还在限流范畴内，那么就重置 counter，具体算法的示意图如下：

面试官问起 Spring Boot 接口应该怎么去限流，该如何作答？

具体的伪代码如下：

这个算法尽管简略，然而有一个非常致命的问题，那就是临界问题，咱们看下图：

从上图中咱们能够看到，假如有一个歹意用户，他在 0:59 时，霎时发送了 100 个申请，并且 1:00 又霎时发送了 100 个申请，那么其实这个用户在 1 秒外面，霎时发送了 200 个申请。咱们方才规定的是 1 分钟最多 100 个申请，也就是每秒钟最多 1.7 个申请，用户通过在工夫窗口的重置节点处突发申请，能够霎时超过咱们的速率限度。用户有可能通过算法的这个破绽，霎时压垮咱们的利用。

聪慧的敌人可能曾经看进去了，方才的问题其实是因为咱们统计的精度太低。那么如何很好地解决这个问题呢？或者说，如何将临界问题的影响升高呢？咱们能够看上面的滑动窗口算法。

滑动窗口

滑动窗口，又称 rolling window。为了解决这个问题，咱们引入了滑动窗口算法。如果学过 TCP 网络协议的话，那么肯定对滑动窗口这个名词不会生疏。上面这张图，很好地解释了滑动窗口算法：

Spring Boot 接口如何做限流？面试官问起如何作答

在上图中，整个红色的矩形框示意一个工夫窗口，在咱们的例子中，一个工夫窗口就是一分钟。而后咱们将工夫窗口进行划分，比方图中，咱们就将滑动窗口划成了 6 格，所以每格代表的是 10 秒钟。每过 10 秒钟，咱们的工夫窗口就会往右滑动一格。每一个格子都有本人独立的计数器 counter，比方当一个申请在 0:35 秒的时候达到，那么 0:30~0:39 对应的 counter 就会加 1。

那么滑动窗口怎么解决方才的临界问题的呢？咱们能够看上图，0:59 达到的 100 个申请会落在灰色的格子中，而 1:00 达到的申请会落在橘黄色的格子中。当工夫达到 1:00 时，咱们的窗口会往右挪动一格，那么此时工夫窗口内的总申请数量一共是 200 个，超过了限定的 100 个，所以此时可能检测进去触发了限流。

我再来回顾一下方才的计数器算法，咱们能够发现，计数器算法其实就是滑动窗口算法。只是它没有对工夫窗口做进一步地划分，为 60s。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越准确。

image.png

漏桶算法

漏桶算法，又叫 leaky bucket。为了不便了解漏桶算法，咱们看一下对于该算法的示意图：

image.png

从图中咱们能够看到，整个算法其实非常简略。首先，咱们有一个固定容量的桶，有水流进来，也有水流进来。对于流进来的水来说，咱们无奈预计一共有多少水会流进来，也无奈预计水流的速度。然而对于流出去的水来说，这个桶能够固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

咱们将算法中的水换成理论利用中的申请，咱们能够看到漏桶算法天生就限度了申请的速度。当应用了漏桶算法，咱们能够保障接口会以一个常速速率来解决申请。所以漏桶算法天生不会呈现临界问题。具体的伪代码实现如下：

令牌桶算法

令牌桶算法，又称 token bucket。为了了解该算法，咱们再来看一下算法的示意图：

image.png

从图中咱们能够看到，令牌桶算法比漏桶算法稍显简单。首先，咱们有一个固定容量的桶，桶里寄存着令牌（token）。桶一开始是空的，token 以一个固定的速率 r 往桶里填充，直到达到桶的容量，多余的令牌将会被抛弃。每当一个申请过去时，就会尝试从桶里移除一个令牌，如果没有令牌的话，申请无奈通过。

具体的伪代码实现如下：

Spring Boot 接口如何做限流？面试官问起如何作答

RateLimiter 实现

对于令牌桶的代码实现，能够间接应用 Guava 包中的 RateLimiter。

Spring Boot 接口如何做限流？面试官问起如何作答

相干变种

若认真钻研算法，咱们会发现咱们默认从桶里移除令牌是不须要消耗工夫的。如果给移除令牌设置一个延时工夫，那么实际上又采纳了漏桶算法的思路。Google 的 guava 库下的 SmoothWarmingUp 类就采纳了这个思路。

临界问题

咱们再来考虑一下临界问题的场景。在 0:59 秒的时候，因为桶内积满了 100 个 token，所以这 100 个申请能够霎时通过。然而因为 token 是以较低的速率填充的，所以在 1:00 的时候，桶内的 token 数量不可能达到 100 个，那么此时不可能再有 100 个申请通过。所以令牌桶算法能够很好地解决临界问题。下图比拟了计数器（左）和令牌桶算法（右）在临界点的速率变动。咱们能够看到尽管令牌桶算法容许突发速率，然而下一个突发速率必须要等桶内有足够的 token 后能力产生：

总结

计数器 VS 滑动窗口

计数器算法是最简略的算法，能够看成是滑动窗口的低精度实现。滑动窗口因为须要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上须要更多的存储空间。也就是说，如果滑动窗口的精度越高，须要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最显著的区别是令牌桶算法容许流量肯定水平的突发。因为默认的令牌桶算法，取走 token 是不须要消耗工夫的，也就是说，假如桶内有 100 个 token 时，那么能够霎时容许 100 个申请通过。

令牌桶算法因为实现简略，且容许某些流量的突发，对用户敌对，所以被业界采纳地较多。当然咱们须要具体情况具体分析，只有最合适的算法，没有最优的算法。

如果文章对你有帮忙的话，点个赞再走吧