Talking about the Implementation of leaky bucket Algorithm

  arch

Order

This paper mainly studies the implementation of leaky bucket algorithm

Leaky bucket algorithm

  • Bucket drips water at a certain rate, which is equivalent to increasing the bucket capacity.
  • Bucket has its capacity limit, when the request comes, bucket is full, and it will be discarded directly.
  • When the request arrives, if bucket is not satisfied, put bucket in, which is equivalent to release

Simple implementation

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;
            }
        }
    }
}
  • This implementation has designed the lastLeakTimestamp field to calculate the time difference and the amount of water leakage required during this time period.
  • When trying tryConsume each time, the inside of the method calls leak first, calculates the amount of water leakage required in this time period according to the set speed and time difference, and updates the current usage of the bucket and lastLeakTimestamp.
  • After that, the current limit judgment is to judge whether the used and the requested drop will exceed the barrel capacity, and if so, the current limit is imposed, otherwise, the used and the requested drop are put into the barrel to update the barrel capacity

Summary

  • Leaky bucket algorithm is opposite to token bucket algorithm, the former is leaking water, the latter is adding token
  • Leaky bucket is a leakage algorithm, so it cannot accumulate as token bucket adds token, so leaky bucket cannot support burst burst traffic.

doc