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

限流算法

1、计数器算法

计数器算法是限流算法里最简略也是最容易实现的一种算法。
比方咱们规定,对于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个申请,用户通过在工夫窗口的重置节点处突发申请, 能够霎时超过咱们的速率限度。用户有可能通过算法的这个破绽,霎时压垮咱们的利用。

2. 滑动窗口算法

在上图中,整个红色的矩形框示意一个工夫窗口,在咱们的例子中,一个工夫窗口就是一分钟。而后咱们将工夫窗口进行划分,比方图中,咱们就将滑动窗口 划成了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;        }    }}

3. 令牌桶算法

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

能够反对突发流量。

4. 漏桶算法

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

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