令牌桶限流算法應(yīng)用

前言

今天原本是要出一個(gè)令牌桶限流算法的web應(yīng)用demo的，但是實(shí)際在搜索和實(shí)現(xiàn)相關(guān)算法的時(shí)候，發(fā)現(xiàn)似乎實(shí)現(xiàn)都不理想，于是我就花費(fèi)了大量的實(shí)踐用來尋找合適的限流算法，所以也就沒有足夠的時(shí)間來完成相關(guān)demo了，我不過我這里可以分享下思路，結(jié)合我們昨天和前天分享的內(nèi)容，我想各位小伙伴應(yīng)該能夠自己做出來：

令牌桶限流依然是在攔截器層實(shí)現(xiàn)，定義一個(gè)令牌桶限流注解，注解中定義速率和令牌桶容量，然后在攔截中獲取接口方法注解，實(shí)例化限流算法示例，調(diào)用限流算法acquire方法獲取token，如果token獲取失敗，則表示目前沒有可用令牌（觸發(fā)限流機(jī)制），直接返回錯(cuò)誤信息，如果獲取到token，直接進(jìn)入到接口中。

下面我們看下今天我這邊搜集到額令牌算法：

令牌桶限流算法

首先我們先回憶下令牌桶算法的原理：在令牌桶算法中，令牌生產(chǎn)算法以恒定速率不斷生成新的令牌放進(jìn)令牌桶中，當(dāng)數(shù)量達(dá)到令牌桶的上線時(shí)，生成的新令牌會(huì)被丟棄掉。對(duì)客戶端請(qǐng)求來說，每次請(qǐng)求處理前，先要從令牌桶中獲取令牌，如果獲取到令牌，則進(jìn)出接口服務(wù)處理相關(guān)請(qǐng)求，否則請(qǐng)求被拒絕。

在令牌桶限流算法中，最核心的點(diǎn)有以下幾個(gè)：

• 令牌的生成速率控制
• 令牌的補(bǔ)充
• 令牌的消耗
• 令牌的獲取

我測(cè)試了網(wǎng)上絕大多數(shù)算法實(shí)現(xiàn)，最后只找到一種完全滿足需求的算法：

public?class?TokenBucket5?{
????private?ArrayBlockingQueue?blockingQueue;
????private?int?limit;
????private?TimeUnit?unit;
????private?int?rate;
????private?ScheduledExecutorService?scheduledExecutorService?=?Executors.newScheduledThreadPool(1);

????public?TokenBucket5(int?capacity,?TimeUnit?unit,?int?rate)?{
????????//?存放令牌的隊(duì)列
????????this.blockingQueue?=?new?ArrayBlockingQueue<>(capacity);
????????//?令牌桶容量
????????this.capacity?=?capacity;
????????//?限流的時(shí)間單位
????????this.unit?=?unit;
????????//?限流的時(shí)間限制（速度），用于控制令牌生成速度
????????this.rate?=?rate;
????????init();
????????start();
????}

????//?初始化令牌桶
????private?void?init()?{
????????for?(int?i?=?0;?i?????????????blockingQueue.add(i);
????????}
????}

????//?創(chuàng)建令牌
????private?void?createToken()?{
????????blockingQueue.offer(1);
????}

????//?啟動(dòng)令牌創(chuàng)建定時(shí)線程池
????private?void?start()?{
????????scheduledExecutorService.scheduleAtFixedRate(this::createToken,?rate,?rate,?unit);
????}

????//?獲取令牌資源
????public?boolean?acquire()?{
????????return?blockingQueue.poll()?==?null???false?:?true;
????}

????//?釋放線程池資源
????public?void?release()?{
????????scheduledExecutorService.shutdown();
????}
}

在這個(gè)算法實(shí)現(xiàn)中，令牌的生成采用了定時(shí)線程池，生成的線程池被放進(jìn)固定尺寸的令牌隊(duì)列中，獲取令牌時(shí)令牌從隊(duì)列中刪除掉（當(dāng)隊(duì)列的count為0時(shí)，返回為null，所以如果poll方法不為空時(shí)表示仍然有令牌），生成令牌時(shí)會(huì)將令牌插入隊(duì)列。

測(cè)試

下面我們進(jìn)行一些簡單測(cè)試：

public?static?void?main(String[]?args)?{
????TokenBucket5?tokenBucket5?=?new?TokenBucket5(5,?TimeUnit.MILLISECONDS,?100);
????try?{
????????for?(int?i?=?0;?i?100;?i++)?{
????????????boolean?acquire?=?tokenBucket5.acquire();
????????????System.out.printf("timestamp:%s,?hello，result:?%s\n",?System.currentTimeMillis(),?acquire);
????????????Thread.sleep(5L);
????????}
????}?catch?(InterruptedException?e)?{
????????e.printStackTrace();
????}?finally?{
????????tokenBucket5.release();
????}

}

運(yùn)行結(jié)果如下：

當(dāng)我們的業(yè)務(wù)處理時(shí)間很短，而令牌生成很慢時(shí)，絕大多數(shù)請(qǐng)求都獲取令牌失敗（每隔100ms生成一個(gè)，業(yè)務(wù)只需要5ms），如果將業(yè)務(wù)處理時(shí)間增加或者將令牌生成時(shí)間減小，這時(shí)候就可以發(fā)現(xiàn)，絕大多數(shù)的業(yè)務(wù)都會(huì)處理成功，偶爾會(huì)有個(gè)別獲取令牌失敗：

至此，我們的限流目的也基本上達(dá)到了。

總結(jié)

關(guān)于令牌桶限流這塊沒有什么好總結(jié)的，但是在整個(gè)檢索算法的過程中，感觸倒是不少，特別是越發(fā)地意識(shí)到自己對(duì)多線程這塊地認(rèn)知真的是太淺薄了，所以后面會(huì)加強(qiáng)這塊地學(xué)習(xí)。好了，今天就先到在這里吧，各位小伙伴，晚安吧！