为什么要限流

限流场景：1）系统处理能力有限，阻止计划外的请求继续对系统造成压力 2）针对某个用户的行为进行控制，避免非法垃圾请求

算法

1）固定窗口
对一个固定时间窗口内的请求进行计数，如果请求超过阈值则丢弃，如果没有达到阈值则接受该请求，并将请求数加1，当时间窗结束置为0，重新开始下一个窗口。

固定窗口

优点：实现简单
缺点：无法控制流量平滑，容易造成流量突变
2）滑动窗口
滑动窗口是在固定窗口的基础上，将一个计时窗口分成若干小窗口，平滑移动小窗口并统计大窗口内计数。就是在一个时间范围内，允许多少请求通过。计算时间窗口内，当前请求数是否达到最大允许值。
优点：解决了固定窗口算法产生两倍流量问题，使得流量比较平滑
缺点：当限流的容量比较大时，比较浪费空间（基于Redis实现）。

基于redis有序集合实现，score分值用时间戳（zset）:
boolean isAllowd(String userId, String actionKey, int peroid, int maxCount) {
    String key = String.format("hist:%s:%s", userId, actionKey);
    // 1.zadd添加请求
    // 2.zremrangeByScore移除时间外计数
    // 3.zcard统计当前计数curCount
    // 4.比较curCount和允许的maxCount的大小
}

3）漏斗算法
漏斗容量是有限的，漏斗以一定的流速往下流，当流入的速率小于等于流出的速率，则允许通过。
优点：流速是恒定的，避免了大流量波动对系统造成的影响。
缺点：无法解决流量突增的情况，突增流量需要在队列中排队等待处理。

public Funnel(int capacity, float leakingRate) {
    this.capacity = capacity;
    this.leakingRate = leakIngRate;
    this.leftQuota = capacity;
    this.leakingTs = System.currentTimeMillis();
}
void makeSpace() {
    long nowTs = System.currentTimeMills();
    long deltaTs = nowTs - leakingTs;
    int deltaQuota = (int)(deltaTs * leakingRate);
    // 防止溢出
    if (deltaQuota  < 0) {
        // TODO
    }
    // 腾出空间不够
    if (deltaQuota < 1) {
        return;
    }
    this.leftQuota += deltaQuota;
    this.leakingTs = nowTs;
    if (this.leftQuota > this.capacity) {
        this.leftQuota = this.capacity;
    }
}

boolean watering(int quota) {
    // 腾出空间
    makeSpace();
    // 判断空间是否足够容纳新的数据
    if (this.leftQuota >= quota) {
        this.leftQuota -= quota;
        return true;
    }
    return false;
}

令牌桶

令牌桶算法有一个令牌桶，以一种恒定的速率向桶中放入令牌，令牌桶有容量限制，当超过容量时不允许放入新令牌。当请求过来的时候，先到令牌桶去拿令牌，能拿到令牌则处理该请求，并消耗令牌。当令牌桶为空时，则请求被拒绝。
优点：令牌桶是对漏斗算法的改进，除了能够起到限流作用，还能够一定程度上解决流量突发情况。

令牌桶

限流算法

限流算法

为什么要限流

算法

令牌桶