聊聊leaky bucket算法的实现

序
本文主要研究一下 leaky bucket 算法的实现
leaky bucket 算法

bucket 以一定速率滴水，相当于增加桶容量
bucket 有其容量限制，请求过来时 bucket 满，则直接被抛弃
请求到来时，如果 bucket 不满，则放入 bucket，相当于放行

简单实现
public class LeakyBucket {

private final long capacity;
private final long leaksIntervalInMillis;

private double used;
private long lastLeakTimestamp;

public LeakyBucket(long capacity, long leaksIntervalInMillis) {
this.capacity = capacity;
this.leaksIntervalInMillis = leaksIntervalInMillis;

this.used = 0;
this.lastLeakTimestamp = System.currentTimeMillis();
}

synchronized public boolean tryConsume(int drop) {
leak();

if (used + drop > capacity) {
return false;
}

used = used + drop;
return true;
}

private void leak() {
long currentTimeMillis = System.currentTimeMillis();
if (currentTimeMillis > lastLeakTimestamp) {
long millisSinceLastLeak = currentTimeMillis – lastLeakTimestamp;
long leaks = millisSinceLastLeak / leaksIntervalInMillis;
if(leaks > 0){
if(used <= leaks){
used = 0;
}else{
used -= (int)leaks;
}
this.lastLeakTimestamp = currentTimeMillis;
}
}
}
}

这个实现设计了 lastLeakTimestamp 字段，用于计算时间差，以及在这个时间段内需要漏水的数量
每次 tryConsume 的时候，方法内部首先调用 leak，根据设定的速度以及时间差计算这个时间段需要漏水的数量，更新桶的当前使用量以及 lastLeakTimestamp
之后限流判断，就是判断 used 与请求的 drop 是否会超过桶容量，超出则限流，否则放入桶中，更新桶容量

小结

leaky bucket 与 token bucket 算法相反，前者是漏水，后者是添加 token
leaky bucket 由于是漏水算法，所以不能像 token bucket 添加 token 那种可以累积，因此 leaky bucket 不能支持 burst 突发流量

doc

Leaky Bucket Algorithm
Leaky bucket algorithm for flow control
Computer Network | Leaky bucket algorithm