token bucket令牌桶限流算法原理及代碼（上）

1 概述

限流算法主要有如下幾種：

• 基于信号量Semaphore

  隻有數量次元，沒有時間次元

• 基于fixed window

  帶上了時間次元，不過在兩個視窗的臨界點容易出現超出限流的情況，比如限制每分鐘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足夠再繼續)

2 簡單實作

2.1 Java版

/**
 * 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);
        }

    }

}      

以上是bucket4j給出的一個簡單實作，用于了解token bucket算法。

這個算法沒有采用線程去refill token，因為bucket太多的話，線程太多，耗cpu

這個算法沒有存儲每個period使用的token，設計了lastRefillTimestamp字段，用于計算需要填充的token

每次tryConsume的時候，方法内部首先調用refill，根據設定的速度以及時間差計算這個時間段需要補充的token，更新availableTokens以及lastRefillTimestamp

之後限流判斷，就是判斷availableTokens與請求的numberTokens