5種限流算法，7種限流方式，擋住突發(fā)流量？
點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)??
前言
最近幾年，隨著微服務(wù)的流行，服務(wù)和服務(wù)之間的依賴越來(lái)越強(qiáng)，調(diào)用關(guān)系越來(lái)越復(fù)雜，服務(wù)和服務(wù)之間的穩(wěn)定性越來(lái)越重要。在遇到突發(fā)的請(qǐng)求量激增，惡意的用戶訪問，亦或請(qǐng)求頻率過高給下游服務(wù)帶來(lái)較大壓力時(shí)，我們常常需要通過緩存、限流、熔斷降級(jí)、負(fù)載均衡等多種方式保證服務(wù)的穩(wěn)定性。其中限流是不可或缺的一環(huán)，這篇文章介紹限流相關(guān)知識(shí)。
1. 限流
限流顧名思義，就是對(duì)請(qǐng)求或并發(fā)數(shù)進(jìn)行限制；通過對(duì)一個(gè)時(shí)間窗口內(nèi)的請(qǐng)求量進(jìn)行限制來(lái)保障系統(tǒng)的正常運(yùn)行。如果我們的服務(wù)資源有限、處理能力有限，就需要對(duì)調(diào)用我們服務(wù)的上游請(qǐng)求進(jìn)行限制，以防止自身服務(wù)由于資源耗盡而停止服務(wù)。
在限流中有兩個(gè)概念需要了解。
閾值：在一個(gè)單位時(shí)間內(nèi)允許的請(qǐng)求量。如 QPS 限制為10，說(shuō)明 1 秒內(nèi)最多接受 10 次請(qǐng)求。 拒絕策略：超過閾值的請(qǐng)求的拒絕策略，常見的拒絕策略有直接拒絕、排隊(duì)等待等。
2. 固定窗口算法
固定窗口算法又叫計(jì)數(shù)器算法，是一種簡(jiǎn)單方便的限流算法。主要通過一個(gè)支持原子操作的計(jì)數(shù)器來(lái)累計(jì) 1 秒內(nèi)的請(qǐng)求次數(shù)，當(dāng) 1 秒內(nèi)計(jì)數(shù)達(dá)到限流閾值時(shí)觸發(fā)拒絕策略。每過 1 秒，計(jì)數(shù)器重置為 0 開始重新計(jì)數(shù)。
2.1. 代碼實(shí)現(xiàn)
下面是簡(jiǎn)單的代碼實(shí)現(xiàn)，QPS 限制為 2，這里的代碼做了一些優(yōu)化，并沒有單獨(dú)開一個(gè)線程去每隔 1 秒重置計(jì)數(shù)器，而是在每次調(diào)用時(shí)進(jìn)行時(shí)間間隔計(jì)算來(lái)確定是否先重置計(jì)數(shù)器。
/**
?*?@author?https://www.wdbyte.com
?*/
public?class?RateLimiterSimpleWindow?{
????//?閾值
????private?static?Integer?QPS?=?2;
????//?時(shí)間窗口（毫秒）
????private?static?long?TIME_WINDOWS?=?1000;
????//?計(jì)數(shù)器
????private?static?AtomicInteger?REQ_COUNT?=?new?AtomicInteger();
????
????private?static?long?START_TIME?=?System.currentTimeMillis();
????public?synchronized?static?boolean?tryAcquire()?{
????????if?((System.currentTimeMillis()?-?START_TIME)?>?TIME_WINDOWS)?{
????????????REQ_COUNT.set(0);
????????????START_TIME?=?System.currentTimeMillis();
????????}
????????return?REQ_COUNT.incrementAndGet()?<=?QPS;
????}
????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????for?(int?i?=?0;?i?10;?i++)?{
????????????Thread.sleep(250);
????????????LocalTime?now?=?LocalTime.now();
????????????if?(!tryAcquire())?{
????????????????System.out.println(now?+?"?被限流");
????????????}?else?{
????????????????System.out.println(now?+?"?做點(diǎn)什么");
????????????}
????????}
????}
}
運(yùn)行結(jié)果：
20:53:43.038922 做點(diǎn)什么
20:53:43.291435 做點(diǎn)什么
20:53:43.543087 被限流
20:53:43.796666 做點(diǎn)什么
20:53:44.050855 做點(diǎn)什么
20:53:44.303547 被限流
20:53:44.555008 被限流
20:53:44.809083 做點(diǎn)什么
20:53:45.063828 做點(diǎn)什么
20:53:45.314433 被限流
從輸出結(jié)果中可以看到大概每秒操作 3 次，由于限制 QPS 為 2，所以平均會(huì)有一次被限流?？雌饋?lái)可以了，不過我們思考一下就會(huì)發(fā)現(xiàn)這種簡(jiǎn)單的限流方式是有問題的，雖然我們限制了 QPS 為 2，但是當(dāng)遇到時(shí)間窗口的臨界突變時(shí)，如 1s 中的后 500 ms 和第 2s 的前 500ms 時(shí)，雖然是加起來(lái)是 1s 時(shí)間，卻可以被請(qǐng)求 4 次。
簡(jiǎn)單修改測(cè)試代碼，可以進(jìn)行驗(yàn)證：
//?先休眠 400ms，可以更快的到達(dá)時(shí)間窗口。
Thread.sleep(400);
for?(int?i?=?0;?i?10;?i++)?{
????Thread.sleep(250);
????if?(!tryAcquire())?{
????????System.out.println("被限流");
????}?else?{
????????System.out.println("做點(diǎn)什么");
????}
}
得到輸出中可以看到連續(xù) 4 次請(qǐng)求，間隔 250 ms 沒有卻被限制。：
20:51:17.395087?做點(diǎn)什么
20:51:17.653114?做點(diǎn)什么
20:51:17.903543?做點(diǎn)什么
20:51:18.154104?被限流
20:51:18.405497?做點(diǎn)什么
20:51:18.655885?做點(diǎn)什么
20:51:18.906177?做點(diǎn)什么
20:51:19.158113?被限流
20:51:19.410512?做點(diǎn)什么
20:51:19.661629?做點(diǎn)什么
3. 滑動(dòng)窗口算法
我們已經(jīng)知道固定窗口算法的實(shí)現(xiàn)方式以及它所存在的問題，而滑動(dòng)窗口算法是對(duì)固定窗口算法的改進(jìn)。既然固定窗口算法在遇到時(shí)間窗口的臨界突變時(shí)會(huì)有問題，那么我們?cè)谟龅较乱粋€(gè)時(shí)間窗口前也調(diào)整時(shí)間窗口不就可以了嗎？
下面是滑動(dòng)窗口的示意圖。
上圖的示例中，每 500ms 滑動(dòng)一次窗口，可以發(fā)現(xiàn)窗口滑動(dòng)的間隔越短，時(shí)間窗口的臨界突變問題發(fā)生的概率也就越小，不過只要有時(shí)間窗口的存在，還是有可能發(fā)生時(shí)間窗口的臨界突變問題。
3.1. 代碼實(shí)現(xiàn)
下面是基于以上滑動(dòng)窗口思路實(shí)現(xiàn)的簡(jiǎn)單的滑動(dòng)窗口限流工具類。
package?com.wdbyte.rate.limiter;
import?java.time.LocalTime;
import?java.util.concurrent.atomic.AtomicInteger;
/**
?*?滑動(dòng)窗口限流工具類
?*
?*?@author?https://www.wdbyte.com
?*/
public?class?RateLimiterSlidingWindow?{
????/**
?????*?閾值
?????*/
????private?int?qps?=?2;
????/**
?????*?時(shí)間窗口總大?。ê撩耄?br>?????*/
????private?long?windowSize?=?1000;
????/**
?????*?多少個(gè)子窗口
?????*/
????private?Integer?windowCount?=?10;
????/**
?????*?窗口列表
?????*/
????private?WindowInfo[]?windowArray?=?new?WindowInfo[windowCount];
????public?RateLimiterSlidingWindow(int?qps)?{
????????this.qps?=?qps;
????????long?currentTimeMillis?=?System.currentTimeMillis();
????????for?(int?i?=?0;?i?????????????windowArray[i]?=?new?WindowInfo(currentTimeMillis,?new?AtomicInteger(0));
????????}
????}
????/**
?????*?1.?計(jì)算當(dāng)前時(shí)間窗口
?????*?2.?更新當(dāng)前窗口計(jì)數(shù)?&?重置過期窗口計(jì)數(shù)
?????*?3.?當(dāng)前?QPS?是否超過限制
?????*
?????*?@return
?????*/
????public?synchronized?boolean?tryAcquire()?{
????????long?currentTimeMillis?=?System.currentTimeMillis();
????????//?1.?計(jì)算當(dāng)前時(shí)間窗口
????????int?currentIndex?=?(int)(currentTimeMillis?%?windowSize?/?(windowSize?/?windowCount));
????????//?2.??更新當(dāng)前窗口計(jì)數(shù)?&?重置過期窗口計(jì)數(shù)
????????int?sum?=?0;
????????for?(int?i?=?0;?i?????????????WindowInfo?windowInfo?=?windowArray[i];
????????????if?((currentTimeMillis?-?windowInfo.getTime())?>?windowSize)?{
????????????????windowInfo.getNumber().set(0);
????????????????windowInfo.setTime(currentTimeMillis);
????????????}
????????????if?(currentIndex?==?i?&&?windowInfo.getNumber().get()?????????????????windowInfo.getNumber().incrementAndGet();
????????????}
????????????sum?=?sum?+?windowInfo.getNumber().get();
????????}
????????//?3.?當(dāng)前?QPS?是否超過限制
????????return?sum?<=?qps;
????}
????private?class?WindowInfo?{
????????//?窗口開始時(shí)間
????????private?Long?time;
????????//?計(jì)數(shù)器
????????private?AtomicInteger?number;
????????public?WindowInfo(long?time,?AtomicInteger?number)?{
????????????this.time?=?time;
????????????this.number?=?number;
????????}
????????//?get...set...
????}
}
下面是測(cè)試用例，設(shè)置 QPS 為 2,測(cè)試次數(shù) 20 次，每次間隔 300 毫秒，預(yù)計(jì)成功次數(shù)在 12 次左右。
public?static?void?main(String[]?args)?throws?InterruptedException?{
????int?qps?=?2,?count?=?20,?sleep?=?300,?success?=?count?*?sleep?/?1000?*?qps;
????System.out.println(String.format("當(dāng)前QPS限制為:%d,當(dāng)前測(cè)試次數(shù):%d,間隔:%dms,預(yù)計(jì)成功次數(shù):%d",?qps,?count,?sleep,?success));
????success?=?0;
????RateLimiterSlidingWindow?myRateLimiter?=?new?RateLimiterSlidingWindow(qps);
????for?(int?i?=?0;?i?????????Thread.sleep(sleep);
????????if?(myRateLimiter.tryAcquire())?{
????????????success++;
????????????if?(success?%?qps?==?0)?{
????????????????System.out.println(LocalTime.now()?+?":?success,?");
????????????}?else?{
????????????????System.out.print(LocalTime.now()?+?":?success,?");
????????????}
????????}?else?{
????????????System.out.println(LocalTime.now()?+?":?fail");
????????}
????}
????System.out.println();
????System.out.println("實(shí)際測(cè)試成功次數(shù):"?+?success);
}
下面是測(cè)試的結(jié)果。
當(dāng)前QPS限制為:2,當(dāng)前測(cè)試次數(shù):20,間隔:300ms,預(yù)計(jì)成功次數(shù):12
16:04:27.077782:?success,?16:04:27.380715:?success,?
16:04:27.684244:?fail
16:04:27.989579:?success,?16:04:28.293347:?success,?
16:04:28.597658:?fail
16:04:28.901688:?fail
16:04:29.205262:?success,?16:04:29.507117:?success,?
16:04:29.812188:?fail
16:04:30.115316:?fail
16:04:30.420596:?success,?16:04:30.725897:?success,?
16:04:31.028599:?fail
16:04:31.331047:?fail
16:04:31.634127:?success,?16:04:31.939411:?success,?
16:04:32.242380:?fail
16:04:32.547626:?fail
16:04:32.847965:?success,?
實(shí)際測(cè)試成功次數(shù):11
4. 滑動(dòng)日志算法
滑動(dòng)日志算法是實(shí)現(xiàn)限流的另一種方法，這種方法比較簡(jiǎn)單?；具壿嬀褪怯涗浵滤械恼?qǐng)求時(shí)間點(diǎn)，新請(qǐng)求到來(lái)時(shí)先判斷最近指定時(shí)間范圍內(nèi)的請(qǐng)求數(shù)量是否超過指定閾值，由此來(lái)確定是否達(dá)到限流，這種方式?jīng)]有了時(shí)間窗口突變的問題，限流比較準(zhǔn)確，但是因?yàn)橐涗浵旅看握?qǐng)求的時(shí)間點(diǎn)，所以占用的內(nèi)存較多。
4.1. 代碼實(shí)現(xiàn)
下面是簡(jiǎn)單實(shí)現(xiàn)的 一個(gè)滑動(dòng)日志算法，因?yàn)榛瑒?dòng)日志要每次請(qǐng)求單獨(dú)存儲(chǔ)一條記錄，可能占用內(nèi)存過多。所以下面這個(gè)實(shí)現(xiàn)其實(shí)不算嚴(yán)謹(jǐn)?shù)幕瑒?dòng)日志，更像一個(gè)把 1 秒時(shí)間切分成 1000 個(gè)時(shí)間窗口的滑動(dòng)窗口算法。
package?com.wdbyte.rate.limiter;
import?java.time.LocalTime;
import?java.util.HashSet;
import?java.util.Set;
import?java.util.TreeMap;
/**
?*?滑動(dòng)日志方式限流
?*?設(shè)置?QPS?為?2.
?*
?*?@author?https://www.wdbyte.com
?*/
public?class?RateLimiterSildingLog?{
????/**
?????*?閾值
?????*/
????private?Integer?qps?=?2;
????/**
?????*?記錄請(qǐng)求的時(shí)間戳,和數(shù)量
?????*/
????private?TreeMap?treeMap?=?new?TreeMap<>();
????/**
?????*?清理請(qǐng)求記錄間隔,?60?秒
?????*/
????private?long?claerTime?=?60?*?1000;
????public?RateLimiterSildingLog(Integer?qps)?{
????????this.qps?=?qps;
????}
????public?synchronized?boolean?tryAcquire()?{
????????long?now?=?System.currentTimeMillis();
????????//?清理過期的數(shù)據(jù)老數(shù)據(jù)，最長(zhǎng)?60?秒清理一次
????????if?(!treeMap.isEmpty()?&&?(treeMap.firstKey()?-?now)?>?claerTime)?{
????????????Set?keySet?=?new?HashSet<>(treeMap.subMap(0L,?now?-?1000).keySet());
????????????for?(Long?key?:?keySet)?{
????????????????treeMap.remove(key);
????????????}
????????}
????????//?計(jì)算當(dāng)前請(qǐng)求次數(shù)
????????int?sum?=?0;
????????for?(Long?value?:?treeMap.subMap(now?-?1000,?now).values())?{
????????????sum?+=?value;
????????}
????????//?超過QPS限制，直接返回?false
????????if?(sum?+?1?>?qps)?{
????????????return?false;
????????}
????????//?記錄本次請(qǐng)求
????????if?(treeMap.containsKey(now))?{
????????????treeMap.compute(now,?(k,?v)?->?v?+?1);
????????}?else?{
????????????treeMap.put(now,?1L);
????????}
????????return?sum?<=?qps;
????}
????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????RateLimiterSildingLog?rateLimiterSildingLog?=?new?RateLimiterSildingLog(3);
????????for?(int?i?=?0;?i?10;?i++)?{
????????????Thread.sleep(250);
????????????LocalTime?now?=?LocalTime.now();
????????????if?(rateLimiterSildingLog.tryAcquire())?{
????????????????System.out.println(now?+?"?做點(diǎn)什么");
????????????}?else?{
????????????????System.out.println(now?+?"?被限流");
????????????}
????????}
????}
}
代碼中把閾值 QPS 設(shè)定為 3，運(yùn)行可以得到如下日志：
20:51:17.395087?做點(diǎn)什么
20:51:17.653114?做點(diǎn)什么
20:51:17.903543?做點(diǎn)什么
20:51:18.154104?被限流
20:51:18.405497?做點(diǎn)什么
20:51:18.655885?做點(diǎn)什么
20:51:18.906177?做點(diǎn)什么
20:51:19.158113?被限流
20:51:19.410512?做點(diǎn)什么
20:51:19.661629?做點(diǎn)什么
5. 漏桶算法
漏桶算法中的漏桶是一個(gè)形象的比喻，這里可以用生產(chǎn)者消費(fèi)者模式進(jìn)行說(shuō)明，請(qǐng)求是一個(gè)生產(chǎn)者，每一個(gè)請(qǐng)求都如一滴水，請(qǐng)求到來(lái)后放到一個(gè)隊(duì)列（漏桶）中，而桶底有一個(gè)孔，不斷的漏出水滴，就如消費(fèi)者不斷的在消費(fèi)隊(duì)列中的內(nèi)容，消費(fèi)的速率（漏出的速度）等于限流閾值。即假如 QPS ?為 2，則每 1s / 2= 500ms 消費(fèi)一次。漏桶的桶有大小，就如隊(duì)列的容量，當(dāng)請(qǐng)求堆積超過指定容量時(shí)，會(huì)觸發(fā)拒絕策略。
下面是漏桶算法的示意圖。
由介紹可以知道，漏桶模式中的消費(fèi)處理總是能以恒定的速度進(jìn)行，可以很好的保護(hù)自身系統(tǒng)不被突如其來(lái)的流量沖垮；但是這也是漏桶模式的缺點(diǎn)，假設(shè) QPS 為 2，同時(shí) 2 個(gè)請(qǐng)求進(jìn)來(lái)，2 個(gè)請(qǐng)求并不能同時(shí)進(jìn)行處理響應(yīng)，因?yàn)槊?1s / 2= 500ms 只能處理一個(gè)請(qǐng)求。
6. 令牌桶算法
令牌桶算法同樣是實(shí)現(xiàn)限流是一種常見的思路，最為常用的 Google 的 Java 開發(fā)工具包 Guava 中的限流工具類 RateLimiter 就是令牌桶的一個(gè)實(shí)現(xiàn)。令牌桶的實(shí)現(xiàn)思路類似于生產(chǎn)者和消費(fèi)之間的關(guān)系。
系統(tǒng)服務(wù)作為生產(chǎn)者，按照指定頻率向桶（容器）中添加令牌，如 QPS 為 2，每 500ms 向桶中添加一個(gè)令牌，如果桶中令牌數(shù)量達(dá)到閾值，則不再添加。
請(qǐng)求執(zhí)行作為消費(fèi)者，每個(gè)請(qǐng)求都需要去桶中拿取一個(gè)令牌，取到令牌則繼續(xù)執(zhí)行；如果桶中無(wú)令牌可取，就觸發(fā)拒絕策略，可以是超時(shí)等待，也可以是直接拒絕本次請(qǐng)求，由此達(dá)到限流目的。
下面是令牌桶限流算法示意圖。
思考令牌桶的實(shí)現(xiàn)可以以下特點(diǎn)。
1s / 閾值（QPS） ?= 令牌添加時(shí)間間隔。 桶的容量等于限流的閾值，令牌數(shù)量達(dá)到閾值時(shí)，不再添加。 可以適應(yīng)流量突發(fā)，N 個(gè)請(qǐng)求到來(lái)只需要從桶中獲取 N 個(gè)令牌就可以繼續(xù)處理。 有啟動(dòng)過程，令牌桶啟動(dòng)時(shí)桶中無(wú)令牌，然后按照令牌添加時(shí)間間隔添加令牌，若啟動(dòng)時(shí)就有閾值數(shù)量的請(qǐng)求過來(lái)，會(huì)因?yàn)橥爸袥]有足夠的令牌而觸發(fā)拒絕策略，不過如 RateLimiter 限流工具已經(jīng)優(yōu)化了這類問題。
6.1. 代碼實(shí)現(xiàn)
Google 的 Java 開發(fā)工具包 Guava 中的限流工具類 RateLimiter 就是令牌桶的一個(gè)實(shí)現(xiàn)，日常開發(fā)中我們也不會(huì)手動(dòng)實(shí)現(xiàn)了，這里直接使用 RateLimiter 進(jìn)行測(cè)試。
引入依賴：
<exclusion>
???<groupId>com.google.guavagroupId>
????<artifactId>guavaartifactId>
???<version>31.0.1-jreversion>
exclusion>
RateLimiter 限流體驗(yàn)：
//?qps?2
RateLimiter?rateLimiter?=?RateLimiter.create(2);
for?(int?i?=?0;?i?10;?i++)?{
????String?time?=?LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
????System.out.println(time?+?":"?+?rateLimiter.tryAcquire());
????Thread.sleep(250);
}
代碼中限制 QPS 為 2，也就是每隔 500ms 生成一個(gè)令牌，但是程序每隔 250ms 獲取一次令牌，所以兩次獲取中只有一次會(huì)成功。
17:19:06.797557:true
17:19:07.061419:false
17:19:07.316283:true
17:19:07.566746:false
17:19:07.817035:true
17:19:08.072483:false
17:19:08.326347:true
17:19:08.577661:false
17:19:08.830252:true
17:19:09.085327:false
6.2. 思考
雖然演示了 Google Guava 工具包中的 RateLimiter 的實(shí)現(xiàn)，但是我們需要思考一個(gè)問題，就是令牌的添加方式，如果按照指定間隔添加令牌，那么需要開一個(gè)線程去定時(shí)添加，如果有很多個(gè)接口很多個(gè) RateLimiter 實(shí)例，線程數(shù)會(huì)隨之增加，這顯然不是一個(gè)好的辦法。顯然 Google 也考慮到了這個(gè)問題，在 RateLimiter 中，是在每次令牌獲取時(shí)才進(jìn)行計(jì)算令牌是否足夠的。它通過存儲(chǔ)的下一個(gè)令牌生成的時(shí)間，和當(dāng)前獲取令牌的時(shí)間差，再結(jié)合閾值，去計(jì)算令牌是否足夠，同時(shí)再記錄下一個(gè)令牌的生成時(shí)間以便下一次調(diào)用。
下面是 Guava 中 RateLimiter 類的子類 SmoothRateLimiter 的 resync() 方法的代碼分析，可以看到其中的令牌計(jì)算邏輯。
void?resync(long?nowMicros)?{?//?當(dāng)前微秒時(shí)間
????//?當(dāng)前時(shí)間是否大于下一個(gè)令牌生成時(shí)間
????if?(nowMicros?>?this.nextFreeTicketMicros)?{?
???????//?可生成的令牌數(shù) newPermits =?（當(dāng)前時(shí)間?-?下一個(gè)令牌生成時(shí)間）/?令牌生成時(shí)間間隔。
???????//?如果?QPS?為2，這里的?coolDownIntervalMicros?就是?500000.0?微秒(500ms)
????????double?newPermits?=?(double)(nowMicros?-?this.nextFreeTicketMicros)?/?this.coolDownIntervalMicros();
????//?更新令牌庫(kù)存 storedPermits。
???????this.storedPermits?=?Math.min(this.maxPermits,?this.storedPermits?+?newPermits);
????//?更新下一個(gè)令牌生成時(shí)間?nextFreeTicketMicros
???????this.nextFreeTicketMicros?=?nowMicros;
????}
}
7. Redis 分布式限流
Redis 是一個(gè)開源的內(nèi)存數(shù)據(jù)庫(kù)，可以用來(lái)作為數(shù)據(jù)庫(kù)、緩存、消息中間件等。Redis 是單線程的，又在內(nèi)存中操作，所以速度極快，得益于 Redis 的各種特性，所以使用 Redis 實(shí)現(xiàn)一個(gè)限流工具是十分方便的。
下面的演示都基于Spring Boot 項(xiàng)目，并需要以下依賴。
org.springframework.boot
spring-boot-starter-data-redis
配置 Redis 信息。
spring:
??redis:
????database:?0
????password:?
????port:?6379
????host:?127.0.0.1
????lettuce:
??????shutdown-timeout:?100ms
??????pool:
????????min-idle:?5
????????max-idle:?10
????????max-active:?8
????????max-wait:?1ms
7.1. 固定窗口限流
Redis 中的固定窗口限流是使用 incr 命令實(shí)現(xiàn)的，incr 命令通常用來(lái)自增計(jì)數(shù)；如果我們使用時(shí)間戳信息作為 key，自然就可以統(tǒng)計(jì)每秒的請(qǐng)求量了，以此達(dá)到限流目的。
這里有兩點(diǎn)要注意。
對(duì)于不存在的 key，第一次新增時(shí)，value 始終為 1。 INCR 和 EXPIRE 命令操作應(yīng)該在一個(gè)原子操作中提交，以保證每個(gè) key 都正確設(shè)置了過期時(shí)間，不然會(huì)有 key 值無(wú)法自動(dòng)刪除而導(dǎo)致的內(nèi)存溢出。
由于 Redis 中實(shí)現(xiàn)事務(wù)的復(fù)雜性，所以這里直接只用 lua 腳本來(lái)實(shí)現(xiàn)原子操作。下面是 lua 腳本內(nèi)容。
local?count?=?redis.call("incr",KEYS[1])
if?count?==?1?then
??redis.call('expire',KEYS[1],ARGV[2])
end
if?count?>?tonumber(ARGV[1])?then
??return?0
end
return?1
下面是使用 Spring Boot 中 RedisTemplate 來(lái)實(shí)現(xiàn)的 lua 腳本調(diào)用測(cè)試代碼。
/**
?*?@author?https://www.wdbyte.com
?*/
@SpringBootTest
class?RedisLuaLimiterByIncr?{
????private?static?String?KEY_PREFIX?=?"limiter_";
????private?static?String?QPS?=?"4";
????private?static?String?EXPIRE_TIME?=?"1";
????@Autowired
????private?StringRedisTemplate?stringRedisTemplate;
????@Test
????public?void?redisLuaLimiterTests()?throws?InterruptedException,?IOException?{
????????for?(int?i?=?0;?i?15;?i++)?{
????????????Thread.sleep(200);
????????????System.out.println(LocalTime.now()?+?"?"?+?acquire("user1"));
????????}
????}
????/**
?????*?計(jì)數(shù)器限流
?????*
?????*?@param?key
?????*?@return
?????*/
????public?boolean?acquire(String?key)?{
????????//?當(dāng)前秒數(shù)作為?key
????????key?=?KEY_PREFIX?+?key?+?System.currentTimeMillis()?/?1000;
????????DefaultRedisScript?redisScript?=?new?DefaultRedisScript<>();
????????redisScript.setResultType(Long.class);
????????//lua文件存放在resources目錄下
????????redisScript.setScriptSource(new?ResourceScriptSource(new?ClassPathResource("limiter.lua")));
????????return?stringRedisTemplate.execute(redisScript,?Arrays.asList(key),?QPS,?EXPIRE_TIME)?==?1;
????}
}
代碼中雖然限制了 QPS 為 4，但是因?yàn)檫@種限流實(shí)現(xiàn)是把毫秒時(shí)間戳作為 key 的，所以會(huì)有臨界窗口突變的問題，下面是運(yùn)行結(jié)果，可以看到因?yàn)闀r(shí)間窗口的變化，導(dǎo)致了 QPS 超過了限制值 4。
17:38:23.122044?true
17:38:23.695124?true
17:38:23.903220?true
#?此處有時(shí)間窗口變化，所以下面繼續(xù)?true
17:38:24.106206?true
17:38:24.313458?true
17:38:24.519431?true
17:38:24.724446?true
17:38:24.932387?false
17:38:25.137912?true
17:38:25.355595?true
17:38:25.558219?true
17:38:25.765801?true
17:38:25.969426?false
17:38:26.176220?true
17:38:26.381918?true
7.3. 滑動(dòng)窗口限流
通過對(duì)上面的基于 incr 命令實(shí)現(xiàn)的 Redis 限流方式的測(cè)試，我們已經(jīng)發(fā)現(xiàn)了固定窗口限流所帶來(lái)的問題，在這篇文章的第三部分已經(jīng)介紹了滑動(dòng)窗口限流的優(yōu)勢(shì)，它可以大幅度降低因?yàn)榇翱谂R界突變帶來(lái)的問題，那么如何使用 Redis 來(lái)實(shí)現(xiàn)滑動(dòng)窗口限流呢？
這里主要使用 ZSET 有序集合來(lái)實(shí)現(xiàn)滑動(dòng)窗口限流，ZSET 集合有下面幾個(gè)特點(diǎn)：
ZSET 集合中的 ?key 值可以自動(dòng)排序。 ZSET 集合中的 value 不能有重復(fù)值。 ZSET 集合可以方便的使用 ZCARD 命令獲取元素個(gè)數(shù)。 ZSET 集合可以方便的使用 ZREMRANGEBYLEX 命令移除指定范圍的 key 值。
基于上面的四點(diǎn)特性，可以編寫出基于 ZSET 的滑動(dòng)窗口限流 lua 腳本。
--KEYS[1]:?限流?key
--ARGV[1]:?時(shí)間戳?-?時(shí)間窗口
--ARGV[2]:?當(dāng)前時(shí)間戳（作為score）
--ARGV[3]:?閾值
--ARGV[4]:?score?對(duì)應(yīng)的唯一value
--?1.?移除時(shí)間窗口之前的數(shù)據(jù)
redis.call('zremrangeByScore',?KEYS[1],?0,?ARGV[1])
--?2.?統(tǒng)計(jì)當(dāng)前元素?cái)?shù)量
local?res?=?redis.call('zcard',?KEYS[1])
--?3.?是否超過閾值
if?(res?==?nil)?or?(res?tonumber(ARGV[3]))?then
????redis.call('zadd',?KEYS[1],?ARGV[2],?ARGV[4])
????return?1
else
????return?0
end
下面是使用 Spring Boot 中 RedisTemplate 來(lái)實(shí)現(xiàn)的 lua 腳本調(diào)用測(cè)試代碼。
@SpringBootTest
class?RedisLuaLimiterByZset?{
????private?String?KEY_PREFIX?=?"limiter_";
????private?String?QPS?=?"4";
????@Autowired
????private?StringRedisTemplate?stringRedisTemplate;
????@Test
????public?void?redisLuaLimiterTests()?throws?InterruptedException,?IOException?{
????????for?(int?i?=?0;?i?15;?i++)?{
????????????Thread.sleep(200);
????????????System.out.println(LocalTime.now()?+?"?"?+?acquire("user1"));
????????}
????}
????/**
?????*?計(jì)數(shù)器限流
?????*
?????*?@param?key
?????*?@return
?????*/
????public?boolean?acquire(String?key)?{
????????long?now?=?System.currentTimeMillis();
????????key?=?KEY_PREFIX?+?key;
????????String?oldest?=?String.valueOf(now?-?1_000);
????????String?score?=?String.valueOf(now);
????????String?scoreValue?=?score;
????????DefaultRedisScript?redisScript?=?new?DefaultRedisScript<>();
????????redisScript.setResultType(Long.class);
????????//lua文件存放在resources目錄下
????????redisScript.setScriptSource(new?ResourceScriptSource(new?ClassPathResource("limiter2.lua")));
????????return?stringRedisTemplate.execute(redisScript,?Arrays.asList(key),?oldest,?score,?QPS,?scoreValue)?==?1;
????}
}
代碼中限制 QPS 為 4，運(yùn)行結(jié)果信息與之一致。
17:36:37.150370?true
17:36:37.716341?true
17:36:37.922577?true
17:36:38.127497?true
17:36:38.335879?true
17:36:38.539225?false
17:36:38.745903?true
17:36:38.952491?true
17:36:39.159497?true
17:36:39.365239?true
17:36:39.570572?false
17:36:39.776635?true
17:36:39.982022?true
17:36:40.185614?true
17:36:40.389469?true
這里介紹了 Redis 實(shí)現(xiàn)限流的兩種方式，當(dāng)然使用 Redis 也可以實(shí)現(xiàn)漏桶和令牌桶兩種限流算法，這里就不做演示了，感興趣的可以自己研究下。
8. 總結(jié)
這篇文章介紹實(shí)現(xiàn)限流的幾種方式，主要是窗口算法和桶算法，兩者各有優(yōu)勢(shì)。
窗口算法實(shí)現(xiàn)簡(jiǎn)單，邏輯清晰，可以很直觀的得到當(dāng)前的 QPS 情況，但是會(huì)有時(shí)間窗口的臨界突變問題，而且不像桶一樣有隊(duì)列可以緩沖。 桶算法雖然稍微復(fù)雜，不好統(tǒng)計(jì) QPS 情況，但是桶算法也有優(yōu)勢(shì)所在。 漏桶模式消費(fèi)速率恒定，可以很好的保護(hù)自身系統(tǒng)，可以對(duì)流量進(jìn)行整形，但是面對(duì)突發(fā)流量不能快速響應(yīng)。 令牌桶模式可以面對(duì)突發(fā)流量，但是啟動(dòng)時(shí)會(huì)有緩慢加速的過程，不過常見的開源工具中已經(jīng)對(duì)此優(yōu)化。
單機(jī)限流與分布式限流
上面演示的基于代碼形式的窗口算法和桶算法限流都適用于單機(jī)限流，如果需要分布式限流可以結(jié)合注冊(cè)中心、負(fù)載均衡計(jì)算每個(gè)服務(wù)的限流閾值，但這樣會(huì)降低一定精度，如果對(duì)精度要求不是太高，可以使用。
而 Redis 的限流，由于 Redis 的單機(jī)性，本身就可以用于分布式限流。使用 Redis 可以實(shí)現(xiàn)各種可以用于限流算法，如果覺得麻煩也可以使用開源工具如 redisson，已經(jīng)封裝了基于 Redis 的限流。
其他限流工具
文中已經(jīng)提到了 Guava 的限流工具包，不過它畢竟是單機(jī)的，開源社區(qū)中也有很多分布式限流工具，如阿里開源的 Sentinel 就是不錯(cuò)的工具，Sentinel 以流量為切入點(diǎn)，從流量控制、熔斷降級(jí)、系統(tǒng)負(fù)載保護(hù)等多個(gè)維度保護(hù)服務(wù)的穩(wěn)定性。
一如既往，文章中的代碼存放在：github.com/niumoo/JavaNotes
參考
Redis INCR:https://redis.io/commands/incr
Rate Limiting Wikipedia：https://en.wikipedia.org/wiki/Rate_limiting
SpringBoot Redis:https://www.cnblogs.com/lenve/p/10965667.html
2.?優(yōu)雅地處理重復(fù)請(qǐng)求（并發(fā)請(qǐng)求）
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
PS：因公眾號(hào)平臺(tái)更改了推送規(guī)則，如果不想錯(cuò)過內(nèi)容，記得讀完點(diǎn)一下“在看”，加個(gè)“星標(biāo)”，這樣每次新文章推送才會(huì)第一時(shí)間出現(xiàn)在你的訂閱列表里。
點(diǎn)“在看”支持小哈呀，謝謝啦??
