有偿问答
面经分享
技术探讨
资料领取
登录
面试官问起Spring Boot 接口应该怎么去限流，该如何作答？
社长
1年前
⋅ 481 阅读
> https://juejin.cn/post/7039237026599665678 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 个请求通过。 令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。 如果文章对你有帮助的话，点个赞再走吧 
阅读全部
全部评论:
0
条
我有话说:
@
发送
-- 目录 --
关注官方公众号：
Java问答社
接收最新有赏问答推送！
最新发布
1.
SpringBoot 接口数据加解密技巧，so easy!
2.
一个依赖搞定 Spring Boot 反爬虫，防止接口盗刷！
3.
Java8 Stream 极大简化了代码，它是如何实现的？
4.
马上大四了，秋招还是春招好？先找工作还是找实习？
5.
万字详解 Linux 常用指令（值得收藏）
6.
4年工作经验，多线程间的5种通信方式都说不出来，你敢信？
最新评论
部署文档没有了,您能提供下吗
部署文档没有了,能提供下吗
我测你的🐎
源码从哪里获取请问
想学
那篇石墨文档 没有权限查看哇
