每日算法-限流算法

令牌桶算法#

public class TokenBucket {
    private final double rate;//生成令牌的速率
    private  double currentToken;//当前令牌的数量
    private final long maxToken;//桶最大容量
    private final long lastTime;//上次补充令牌的时间戳
    private final ReentrantLock lock=new ReentrantLock();
    public TokenBucket(double rate,long maxToken){
        this.maxToken=maxToken;
        this.rate=rate;
        this.lastTime=System.currentTimeMillis();
    }
    private boolean tryAcquire(){
        return tryAcquire(1);
    }
    private boolean tryAcquire(int need){
        lock.lock();
        try {
            long now=System.currentTimeMillis();
            this.currentToken=Math.min((now-lastTime)*this.rate+this.currentToken,this.maxToken);
            if (this.currentToken>=need){
                return true;
            }
            return false;
        }finally {
            lock.unlock();
        }
    }
}

漏桶算法#

public class LeakyBucket {
    private final double leakRate;
    private final int capacity;
    private  double water;
    private long lastLeakTime;
    private final ReentrantLock lock=new ReentrantLock();
    public LeakyBucket(double leakRate,int capacity){
        this.capacity=capacity;
        this.leakRate=leakRate;
        this.lastLeakTime=System.currentTimeMillis();
        this.water=0;
    }
    private boolean tryAcquire(){
        lock.lock();
        try{
            long now =System.currentTimeMillis();
            double del=(now-lastLeakTime)*leakRate;
            water=Math.max(0,water-del);
            lastLeakTime=now;
            if (water<capacity){
                water++;
                return true;
            }
            return false;
        }finally {
            lock.unlock();
        }
    }
}

滑动时间窗口#

public class SlidingWindow {
    private final int limit;
    private final long windowMs;
    private final Queue<Long>queue=new LinkedList<>();
    private final ReentrantLock lock=new ReentrantLock();
    public SlidingWindow(int limit,int windowMs){
        this.limit=limit;
        this.windowMs=windowMs;
    }
    private boolean tryAcquire(){
        lock.lock();
        try{
            long now=System.currentTimeMillis();
            long expireTime=now-windowMs;
            while (!queue.isEmpty() && queue.peek() < expireTime) {
                queue.poll();
            }
            if (queue.size() < limit) {
                queue.offer(now);
                return true;
            }
            return false;
        }
        finally {
            lock.unlock();
        }
    }
}

三种算法的对比#

令牌算法#

平时没有人使用的时候会积攒满令牌，所以可以抗一波突击流量

漏桶算法#

水流出的速度的固定的，处理请求的速度是固定的。流量均匀，保护脆弱下游

滑动窗口#

qps精准统计，但是在临界值方面容易出现问题