关于后端:常见的限流算法有哪些各自的区别和使用场景

3次阅读

共计 2191 个字符，预计需要花费 6 分钟才能阅读完成。

缓存、降级和限流是高并发零碎中应用的爱护零碎的形式。

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

代码实现：

public class Counter {public long timeStamp = System.currentTimeMillis(); // 以后工夫
    public int reqCount = 0; // 初始化计数器
    public final int limit = 100; // 工夫窗口内最大申请数
    public final long interval = 1000 * 60; // 工夫窗口 ms


    public boolean limit() {long now = System.currentTimeMillis();
        if (now < timeStamp + interval) {
            // 在工夫窗口内
            reqCount++;
            // 判断以后工夫窗口内是否超过最大申请管制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
}

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

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

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

我再来回顾一下方才的计数器算法，咱们能够发现，滑动工夫窗口限流法其实就是计数器算法的一个变种，仍然存在临界值的问题。只是计数器没有对工夫窗口做进一步地划分，所以只有 1 格。由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越准确。

代码实现：

public class SlidingWindow {
    // 工夫窗口大小，单位秒
    private static final int WINDOW_SIZE = 60;
    // 数组长度
    private static final int ARRAY_SIZE = 10;
    // 工夫粒度 单位毫秒
    private static final int TIME_UNIT = WINDOW_SIZE * 1000 / ARRAY_SIZE;
    // 申请阈值
    private static final int LIMIT = 100;
    // 申请计数器
    private static final int[] WINDOW = new int[ARRAY_SIZE];

    public static boolean isAllowed() {synchronized (WINDOW) {
            // 获取以后工夫的数组下标
            int index = (int) ((System.currentTimeMillis() / TIME_UNIT) % ARRAY_SIZE);
            // 如果以后工夫曾经在最初一个时间段内，则把数组左移一位
            if (index == 0) {System.arraycopy(WINDOW, 1, WINDOW, 0, ARRAY_SIZE - 1);
                WINDOW[ARRAY_SIZE - 1] = 0;
            }
            // 记录申请数量
            WINDOW[index]++;
            // 统计申请数量
            int count = 0;
            for (int i = 0; i < ARRAY_SIZE; i++) {count += WINDOW[i];
            }
            // 如果申请数量大于阈值，则拒绝请求
            if (count > LIMIT) {return false;}
            return true;
        }
    }
}

令牌桶算法的原理是零碎会以一个恒定的速度往桶里放入令牌，而如果申请须要被解决，则须要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

能够反对突发流量。

申请先进入到漏桶里，漏桶以肯定的速度放出申请，当申请速度过大会间接溢出，能够看出漏桶算法能强行限度数据的传输速率。因为桶容量是不变的，保障了整体的速率。

存在的问题：
因为漏桶算法的流出速率是固定的，所以漏桶算法不反对呈现突发流出流量。然而在理论状况下，流量往往是突发的。

正文完