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フィールドを設計し、この時間帯に水漏れが必要な数

を設計する.

tryConsumerのたびにメソッド内部で最初に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