token bucketアルゴリズムの実現について話します

シーケンス
本文は主にtoken bucketアルゴリズムの実現を研究する.
ストリーム制限アルゴリズムの概要
主に次のようなものがあります.

信号量Semaphore

に基づく
数量次元のみ、時間次元なし

fixed window

に基づく
時間次元を持っていますが、2つのウィンドウの臨界点で制限フローを超えた場合が発生しやすいです.たとえば、1分に10個のリクエストを制限し、00:59に10回、01:01に10回、00:30-01:30というウィンドウでは、この分に20回リクエストしましたが、コントロールできませんでした.

rolling window

に基づく
fixed windowで解決されていないウィンドウの臨界問題を解決するには、主にtoken bucketベースのアルゴリズムとleaky bucketベースのアルゴリズムがある.
token bucketアルゴリズム

token bucketに指定されたレートで

に追加

一つのbucketはその容量制限があり、その容量を超えると余分なtokenは

に破棄される.

要求が来ると、まずtokenを取得しようとするが、残りのtokenが十分であれば放行し、足りなければ放行( token )

は許されない.
単純な実装

/**
 * The minimalistic token-bucket implementation
 */
public class MinimalisticTokenBucket {

    private final long capacity;
    private final double refillTokensPerOneMillis;

    private double availableTokens;
    private long lastRefillTimestamp;

    /**
     * Creates token-bucket with specified capacity and refill rate equals to refillTokens/refillPeriodMillis
     */
    public MinimalisticTokenBucket(long capacity, long refillTokens, long refillPeriodMillis) {
        this.capacity = capacity;
        this.refillTokensPerOneMillis = (double) refillTokens / (double) refillPeriodMillis;

        this.availableTokens = capacity;
        this.lastRefillTimestamp = System.currentTimeMillis();
    }

    synchronized public boolean tryConsume(int numberTokens) {
        refill();
        if (availableTokens < numberTokens) {
            return false;
        } else {
            availableTokens -= numberTokens;
            return true;
        }
    }

    private void refill() {
        long currentTimeMillis = System.currentTimeMillis();
        if (currentTimeMillis > lastRefillTimestamp) {
            long millisSinceLastRefill = currentTimeMillis - lastRefillTimestamp;
            double refill = millisSinceLastRefill * refillTokensPerOneMillis;
            this.availableTokens = Math.min(capacity, availableTokens + refill);
            this.lastRefillTimestamp = currentTimeMillis;
        }
    }

    private static final class Selftest {

        public static void main(String[] args) {
            // 100 tokens per 1 second
            MinimalisticTokenBucket limiter = new MinimalisticTokenBucket(100, 100, 1000);

            long startMillis = System.currentTimeMillis();
            long consumed = 0;
            while (System.currentTimeMillis() - startMillis < 10000) {
                if (limiter.tryConsume(1)) {
                    consumed++;
                }
            }
            System.out.println(consumed);
        }

    }

}

以上はbucket 4 jが与える簡単な実装であり、token bucketアルゴリズム

を理解するために使用される.

このアルゴリズムはスレッドを採用してrefill tokenに行かなかった.bucketが多すぎると、スレッドが多すぎて、cpu

を消費するからだ.

このアルゴリズムはperiodごとに使用されるtokenを格納せず、充填が必要なtoken

を計算するためにlastRefillTimestampフィールドを設計した.

tryConsumerのたびにメソッド内部でまずrefillが呼び出され、設定された速度および時間差からこの時間帯に補足が必要なtokenを計算し、availableTokensおよびlastRefillTimestamp

を更新する

以降のストリーム制限判定は、availableTokensと要求numberTokens

とを判定する.
小結
token bucketアルゴリズムは、qpsに基づいてストリームを制限し、その簡単な実現は、単位時間でtokenのレートを補充し、tryConsumerのたびにレートに基づいてavailableTokensを修正することである.
doc

Brief overview of token-bucket algorithm