在开发高并发系统时, 有三把利器用来保护系统: 缓存, 降级和限流. 那么何为限流呢? 顾名思义, 限流就是限制流量, 就像你宽带包了 1 个 G 的流量, 用完了就没了. 通过限流, 我们可以很好地控制系统的 qps, 从而达到保护系统的目的. 本篇文章将会介绍一下常用的限流算法以及他们各自的特点.
Node.JS 接口可以采用下面的几种方法进行限流:
1, 计数器算法
计数器算法是限流算法里最简单也是最容易实现的一种算法.
比如我们规定, 对于 A 接口来说, 我们 1 分钟的访问次数不能超过 100 个. 那么我们可以这么做: 在一开 始的时候, 我们可以设置一个计数器 counter, 每当一个请求过来的时候, counter 就加 1, 如果 counter 的值大于 100 并且该请求与第一个 请求的间隔时间还在 1 分钟之内, 那么说明请求数过多; 如果该请求与第一个请求的间隔时间大于 1 分钟, 且 counter 的值还在限流范围内, 那么就重置 counter, 具体算法的示意图如下:
具体的伪代码如下:
- public class CounterTest {
- public long timeStamp = getNowTime();
- public int reqCount = 0;
- public final int limit = 100; // 时间窗口内最大请求数
- public final long interval = 1000; // 时间窗口 ms
- public boolean grant() {
- long now = getNowTime();
- if (now < timeStamp + interval) {
- // 在时间窗口内
- reqCount++;
- // 判断当前时间窗口内是否超过最大请求控制数
- return reqCount <= limit;
- } else {
- timeStamp = now;
- // 超时后重置
- reqCount = 1;
- return true;
- }
- }
- public long getNowTime() {
- return System.currentTimeMillis();
- }
- }
这个算法虽然简单, 但是有一个十分致命的问题, 那就是临界问题, 我们看下图:
从上图中我们可以看到, 假设有一个恶意用户, 他在 0:59 时, 瞬间发送了 100 个请求, 并且 1:00 又瞬间发送了 100 个请求, 那么其实这个用户在 1 秒里面, 瞬间发送了 200 个请求. 我们刚才规定的是 1 分钟最多 100 个请求, 也就是每秒钟最多 1.7 个请求, 用户通过在时间窗口的重置节点处突发请求, 可以瞬间超过我们的速率限制. 用户有可能通过算法的这个漏洞, 瞬间压垮我们的应用.
聪明的朋友可能已经看出来了, 刚才的问题其实是因为我们统计的精度太低. 那么如何很好地处理这个问题呢? 或者说, 如何将临界问题的影响降低呢? 我们可以看下面的滑动窗口算法.
滑动窗口
滑动窗口, 又称 rolling Windows. 为了解决这个问题, 我们引入了滑动窗口算法. 如果学过 TCP 网络协议的话, 那么一定对滑动窗口这个名词不会陌生. 下面这张图, 很好地解释了滑动窗口算法:
在上图中, 整个红色的矩形框表示一个时间窗口, 在我们的例子中, 一个时间窗口就是一分钟. 然后我们将时间窗口进行划分, 比如图中, 我们就将滑动窗口 划成了 6 格, 所以每格代表的是 10 秒钟. 每过 10 秒钟, 我们的时间窗口就会往右滑动一格. 每一个格子都有自己独立的计数器 counter, 比如当一个请求 在 0:35 秒的时候到达, 那么 0:30~0:39 对应的 counter 就会加 1.
那么滑动窗口怎么解决刚才的临界问题的呢? 我们可以看上图, 0:59 到达的 100 个请求会落在灰色的格子中, 而 1:00 到达的请求会落在橘黄色的格 子中. 当时间到达 1:00 时, 我们的窗口会往右移动一格, 那么此时时间窗口内的总请求数量一共是 200 个, 超过了限定的 100 个, 所以此时能够检测出来触发了限流.
我再来回顾一下刚才的计数器算法, 我们可以发现, 计数器算法其实就是滑动窗口算法. 只是它没有对时间窗口做进一步地划分, 所以只有 1 格.
由此可见, 当滑动窗口的格子划分的越多, 那么滑动窗口的滚动就越平滑, 限流的统计就会越精确.
2, 令牌桶算法
令牌桶算法是比较常见的限流算法之一, 大概描述如下:
1), 所有的请求在处理之前都需要拿到一个可用的令牌才会被处理;
2), 根据限流大小, 设置按照一定的速率往桶里添加令牌;
3), 桶设置最大的放置令牌限制, 当桶满时, 新添加的令牌就被丢弃或者拒绝;
4), 请求达到后首先要获取令牌桶中的令牌, 拿着令牌才可以进行其他的业务逻辑, 处理完业务逻辑之后, 将令牌直接删除;
5), 令牌桶有最低限额, 当桶中的令牌达到最低限额的时候, 请求处理完之后将不会删除令牌, 以此保证足够的限流;
3, 漏桶算法
漏桶算法其实很简单, 可以粗略的认为就是注水漏水过程, 往桶中以一定速率流出水, 以任意速率流入水, 当水超过桶流量则丢弃, 因为桶容量是不变的, 保证了整体的速率.
来源: http://www.css88.com/qa/node-js/10803.html