限流算法总结

限流

限流是指在系统面临高并发，大流量请求的情况下。限制新的流量对系统的访问，从而保证系统服务的安全

常见限流算法

计数器限流算法

原理

创建一个计数器，保留计数器的值。处理了一个请求，计数器加一。一个请求处理完毕后计数器减一。单机中可用Atomic原子类实现，分布式集群中可用Redis的incr实现。

代码实现

//计数器限流算法 Code 实现
public class Case01 {
    //@TODO 如何使用Redis实现分布式集群下的计数器限流算法
    private static volatile int counter = 0;
    private static final int threshold = 100;
    public static boolean tryAcquire(){
        if (counter < threshold){
            counter++;
            return true;
        }
        return false;
    }
    public static boolean tryRelease(){
        if (counter > 0){
            counter--;
            return true;
        }
        return false;
    }
}

固定窗口限流算法

原理

在单位事件里面设定窗口阈值大小，比如 10个请求/1秒。在规定的1s里面流量最大阈值是10个。相隔的0.5s + 0.5s 加起来的流量突破阈值的时候如何处理是一个问题。

2. 代码实现

//固定窗口限流算法 Code 实现
public class Case02 {

    public static Integer counter = 0; //统计请求数
    public static long lastAcquireTime = 0L;
    public static final Long windowUnit = 1000l; //假设固定时间窗口是1000ms
    public static final Integer threshold = 10; //窗口阈值是10

    public static boolean tryAcquire(){
        long currentTime = System.currentTimeMillis();
        if (currentTime - lastAcquireTime > windowUnit){
            counter = 0;
            lastAcquireTime = currentTime;
        }
        if (counter < threshold){
            counter++;
            return true;
        }
        return false;
    }

}

滑动窗口限流

原理

它把单位时间周期划分成n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期，它可以解决固定窗口临界值的问题

代码实现

// 滑动窗口限流算法 Code 实现
public class Case03 {

    private int SUB_CYCLE = 10;
    private int thresholdPerMin = 100;
    private final TreeMap<Long, Integer> counters = new TreeMap<Long, Integer>();

    public synchronized  boolean slidingWindowsTryAcquire(){
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE;
        int currentWindowNum = countCurrentWindow(currentWindowTime);
        
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }
        Integer integer = counters.get(currentWindowTime);
        integer++;
        counters.put(currentWindowTime, integer);
        return true;
    }

    private synchronized int countCurrentWindow(long currentWindowTime) {
        long startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE - 1);
        int count = 0;
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Long, Integer> entry = iterator.next();
            if (entry.getKey() < startTime){
                iterator.remove();
            } else {
                count = count + entry.getValue();
            }
        }
        return count;
    }
}

漏桶限流算法

原理

对于每个到来的数据包，都将其加入到漏桶中，并检查漏桶中当前的水量是否超过了漏桶的容量，如果超过了容量，就将多余的数据包抛弃。如果漏桶中还有水，就以一定的速率流出数据包

代码实现

//漏桶限流算法 代码实现
public class Case04 {

    private final long capacity; //桶的容量
    private final long rate; //漏桶出水速率
    private long water; //当前桶中的水量
    private long lastLeakTimestamp; //上次漏水时间戳

    public Case04(long capacity, long rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = 0;
        this.lastLeakTimestamp = System.currentTimeMillis();
    }
    
    public synchronized boolean tryConsume(long waterRequested){
        leak();
        if (water + waterRequested <= capacity){
            water += waterRequested;
            return true;
        } else {
            return false;
        }
    }

    private void leak(){
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastLeakTimestamp;
        long leakedWater = elapsedTime * rate / 1000;
        if (leakedWater > 0){
            water = Math.max(0, water - leakedWater);
            lastLeakTimestamp = now;
        }
    }
}

令牌桶算法

原理

该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶放入一定数量的令牌，当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌

代码实现

//令牌桶限流算法 代码实现
public class Case05 {

    private final int capacity;
    private final int rate;
    private int tokens;
    private long lastRefillTimestamp;

    public Case05(int capacity, int rate){
        this.capacity = capacity;
        this.rate = rate;
        this.tokens = capacity;
        this.lastRefillTimestamp = System.currentTimeMillis();
    }

    public synchronized boolean allowRequest(){
        refill();
        if (tokens > 0){
            tokens--;
            return true;
        } else {
            return false;
        }
    }

    private void refill(){
        long now = System.currentTimeMillis();
        if(now > lastRefillTimestamp){
            int generatedTokens = (int) ((now - lastRefillTimestamp) / 1000 * rate);
            tokens = Math.min(tokens + generatedTokens, capacity);
            lastRefillTimestamp = now;
        }
    }
}