總結(jié)
本文主要寫(xiě)了常見(jiàn)的兩種限流算法漏桶算法與令牌桶算法民傻，并且演示了Guava中RateLimiter的實(shí)現(xiàn)称诗。
令牌桶算法是最常用的限流算法奢赂，它最大的特點(diǎn)就是容許一定程度的突發(fā)流量铛绰。
漏桶算法同樣也有自己的應(yīng)用之處舞吭，例如Nginx的限流模塊就是基于漏桶算法的绰上，它最大的特點(diǎn)就是強(qiáng)行限制流量按照指定的比例下發(fā)旨怠，適合那種對(duì)流量有絕對(duì)要求的場(chǎng)景，就是流量可以容許在我指定的值之下蜈块，可以被多次打回鉴腻，但是無(wú)論如何決不能超過(guò)指定的。
雖然令牌桶算法相對(duì)更好但是使用哪種完全就看大家各自的場(chǎng)景百揭，適合的才是最好的爽哎。
前言
分布式環(huán)境下應(yīng)對(duì)高并發(fā)保證服務(wù)穩(wěn)定幾招，按照個(gè)人理解器一，優(yōu)先級(jí)從高到低分別為緩存课锌、限流、降級(jí)祈秕、熔斷渺贤，每招都有它的作用，本文重點(diǎn)就講講限流這部分请毛。
坦白講志鞍，其實(shí)上面的說(shuō)法也不準(zhǔn)確，因?yàn)?strong>服務(wù)降級(jí)方仿、熔斷本身也是限流的一種固棚，因?yàn)樗鼈儽举|(zhì)上也是阻斷了流量進(jìn)來(lái)，但是本文希望大家可以把限流當(dāng)做一個(gè)單純的名詞來(lái)理解仙蚜，看一下對(duì)請(qǐng)求做流控的幾種算法及具體實(shí)現(xiàn)方式此洲。
為什么要限流
其實(shí)很好理解的一個(gè)問(wèn)題，為什么要限流委粉，自然就流量過(guò)大了唄呜师，一個(gè)對(duì)外服務(wù)有很多場(chǎng)景都會(huì)流量增大：
- 業(yè)務(wù)用戶量不斷攀升
- 各種促銷
- 網(wǎng)絡(luò)爬蟲(chóng)
- 惡意刷單
注意這個(gè)"大"，1000QPS大嗎艳丛？5000QPS大嗎匣掸？10000QPS大么？沒(méi)有答案氮双，因?yàn)闆](méi)有標(biāo)準(zhǔn)，因此霎匈，"大"一定是和正常流量相比的大戴差。流量一大，服務(wù)器扛不住铛嘱，扛不住就掛了暖释，掛了沒(méi)法提供對(duì)外服務(wù)導(dǎo)致業(yè)務(wù)直接熔斷袭厂。怎么辦，最直接的辦法就是從源頭把流量限制下來(lái)球匕，例如服務(wù)器只有支撐1000QPS的處理能力纹磺，那就每秒放1000個(gè)請(qǐng)求，自然保證了服務(wù)器的穩(wěn)定亮曹，這就是限流橄杨。
下面看一下常見(jiàn)的兩種限流算法。
漏桶算法
漏桶算法的原理比較簡(jiǎn)單照卦，水（請(qǐng)求）先進(jìn)入到漏桶里式矫，人為設(shè)置一個(gè)最大出水速率，漏桶以<=出水速率的速度出水役耕，當(dāng)水流入速度過(guò)大會(huì)直接溢出（拒絕服務(wù)）：
因此采转，這個(gè)算法的核心為：
- 存下請(qǐng)求
- 勻速處理
- 多于丟棄
因此這是一種強(qiáng)行限制請(qǐng)求速率的方式，但是缺點(diǎn)非常明顯瞬痘，主要有兩點(diǎn)：
無(wú)法面對(duì)突發(fā)的大流量----比如請(qǐng)求處理速率為1000故慈，容量為5000，來(lái)了一波2000/s的請(qǐng)求持續(xù)10s框全，那么后5s的請(qǐng)求將全部直接被丟棄惯悠，服務(wù)器拒絕服務(wù)，但是實(shí)際上網(wǎng)絡(luò)中突發(fā)一波大流量尤其是短時(shí)間的大流量是非常正常的竣况，超過(guò)容量就拒絕克婶，非常簡(jiǎn)單粗暴
無(wú)法有效利用網(wǎng)絡(luò)資源----比如雖然服務(wù)器的處理能力是1000/s，但這不是絕對(duì)的丹泉，這個(gè)1000只是一個(gè)宏觀服務(wù)器處理能力的數(shù)字情萤，實(shí)際上一共5秒，每秒請(qǐng)求量分別為1200摹恨、1300筋岛、1200、500晒哄、800睁宰，平均下來(lái)qps也是1000/s，但是這個(gè)量對(duì)服務(wù)器來(lái)說(shuō)完全是可以接受的寝凌，但是因?yàn)橄拗屏怂俾适?000/s柒傻，因此前面的三秒，每秒只能處理掉1000個(gè)請(qǐng)求而一共打回了700個(gè)請(qǐng)求较木，白白浪費(fèi)了服務(wù)器資源
所以红符，通常來(lái)說(shuō)利用漏桶算法來(lái)限流，實(shí)際場(chǎng)景下用得不多。
令牌桶算法
令牌桶算法是網(wǎng)絡(luò)流量整形（Traffic Shaping）和限流（Rate Limiting）中最常使用的一種算法预侯，它可用于控制發(fā)送到網(wǎng)絡(luò)上數(shù)據(jù)的數(shù)量并允許突發(fā)數(shù)據(jù)的發(fā)送致开。
從某種意義上來(lái)說(shuō)，令牌桶算法是對(duì)漏桶算法的一種改進(jìn)萎馅，主要在于令牌桶算法能夠在限制調(diào)用的平均速率的同時(shí)還允許一定程度的突發(fā)調(diào)用双戳，來(lái)看下令牌桶算法的實(shí)現(xiàn)原理：
整個(gè)的過(guò)程是這樣的：
- 系統(tǒng)以恒定的速率產(chǎn)生令牌，然后將令牌放入令牌桶中
- 令牌桶有一個(gè)容量糜芳，當(dāng)令牌桶滿了的時(shí)候飒货，再向其中放入的令牌就會(huì)被丟棄
- 每次一個(gè)請(qǐng)求過(guò)來(lái)，需要從令牌桶中獲取一個(gè)令牌耍目，假設(shè)有令牌膏斤，那么提供服務(wù)；假設(shè)沒(méi)有令牌邪驮，那么拒絕服務(wù)
那么莫辨，我們?cè)倏匆幌拢瑸槭裁戳钆仆八惴梢苑乐挂欢ǔ潭鹊耐话l(fā)流量呢毅访？可以這么理解沮榜，假設(shè)我們想要的速率是1000QPS，那么往桶中放令牌的速度就是1000個(gè)/s喻粹，假設(shè)第1秒只有800個(gè)請(qǐng)求蟆融，那意味著第2秒可以容許1200個(gè)請(qǐng)求，這就是一定程度突發(fā)流量的意思守呜，反之我們看漏桶算法型酥，第一秒只有800個(gè)請(qǐng)求，那么全部放過(guò)查乒，第二秒這1200個(gè)請(qǐng)求將會(huì)被打回200個(gè)弥喉。
注意上面多次提到一定程度這四個(gè)字，這也是我認(rèn)為令牌桶算法最需要注意的一個(gè)點(diǎn)玛迄。假設(shè)還是1000QPS的速率由境，那么5秒鐘放1000個(gè)令牌，第1秒鐘800個(gè)請(qǐng)求過(guò)來(lái)蓖议，第2~4秒沒(méi)有請(qǐng)求虏杰，那么按照令牌桶算法，第5秒鐘可以接受4200個(gè)請(qǐng)求勒虾，但是實(shí)際上這已經(jīng)遠(yuǎn)遠(yuǎn)超出了系統(tǒng)的承載能力纺阔，因此使用令牌桶算法特別注意設(shè)置桶中令牌的上限即可。
總而言之从撼，作為對(duì)漏桶算法的改進(jìn)州弟，令牌桶算法在限流場(chǎng)景下被使用更加廣泛钧栖。
RateLimiter使用
上面說(shuō)了令牌桶算法在限流場(chǎng)景下被使用更加廣泛低零，接下來(lái)我們看一下代碼示例婆翔，模擬一下每秒最多過(guò)五個(gè)請(qǐng)求：
public class RateLimiterTest {
private static final SimpleDateFormat FORMATTER = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
private static final int THREAD_COUNT = 25;
@Test
public void testRateLimiter1() {
RateLimiter rateLimiter = RateLimiter.create(5);
Thread[] ts = new Thread[THREAD_COUNT];
for (int i = 0; i < THREAD_COUNT; i++) {
ts[i] = new Thread(new RateLimiterThread(rateLimiter), "RateLimiterThread-" + i);
}
for (int i = 0; i < THREAD_COUNT; i++) {
ts[i].start();
}
for (;;);
}
public class RateLimiterThread implements Runnable {
private RateLimiter rateLimiter;
public RateLimiterThread(RateLimiter rateLimiter) {
this.rateLimiter = rateLimiter;
}
@Override
public void run() {
rateLimiter.acquire(1);
System.out.println(Thread.currentThread().getName() + "獲取到了令牌，時(shí)間 = " + FORMATTER.format(new Date()));
}
}
}
利用RateLimiter.create這個(gè)構(gòu)造方法可以指定每秒向桶中放幾個(gè)令牌掏婶，比方說(shuō)上面的代碼create(5)啃奴，那么每秒放置5個(gè)令牌，即200ms會(huì)向令牌桶中放置一個(gè)令牌雄妥。這邊代碼寫(xiě)了一條線程模擬實(shí)際場(chǎng)景最蕾，拿到令牌那么就能執(zhí)行下面邏輯，看一下代碼執(zhí)行結(jié)果：
RateLimiterThread-0獲取到了令牌老厌，時(shí)間 = 2019-08-25 20:58:53
RateLimiterThread-23獲取到了令牌瘟则，時(shí)間 = 2019-08-25 20:58:54
RateLimiterThread-21獲取到了令牌，時(shí)間 = 2019-08-25 20:58:54
RateLimiterThread-19獲取到了令牌枝秤，時(shí)間 = 2019-08-25 20:58:54
RateLimiterThread-17獲取到了令牌醋拧，時(shí)間 = 2019-08-25 20:58:54
RateLimiterThread-13獲取到了令牌，時(shí)間 = 2019-08-25 20:58:54
RateLimiterThread-9獲取到了令牌淀弹，時(shí)間 = 2019-08-25 20:58:55
RateLimiterThread-15獲取到了令牌丹壕，時(shí)間 = 2019-08-25 20:58:55
RateLimiterThread-5獲取到了令牌，時(shí)間 = 2019-08-25 20:58:55
RateLimiterThread-1獲取到了令牌薇溃，時(shí)間 = 2019-08-25 20:58:55
RateLimiterThread-11獲取到了令牌菌赖，時(shí)間 = 2019-08-25 20:58:55
RateLimiterThread-7獲取到了令牌，時(shí)間 = 2019-08-25 20:58:56
RateLimiterThread-3獲取到了令牌沐序，時(shí)間 = 2019-08-25 20:58:56
RateLimiterThread-4獲取到了令牌琉用，時(shí)間 = 2019-08-25 20:58:56
RateLimiterThread-8獲取到了令牌，時(shí)間 = 2019-08-25 20:58:56
RateLimiterThread-12獲取到了令牌策幼，時(shí)間 = 2019-08-25 20:58:56
RateLimiterThread-16獲取到了令牌邑时，時(shí)間 = 2019-08-25 20:58:57
RateLimiterThread-20獲取到了令牌，時(shí)間 = 2019-08-25 20:58:57
RateLimiterThread-24獲取到了令牌垄惧，時(shí)間 = 2019-08-25 20:58:57
RateLimiterThread-2獲取到了令牌刁愿，時(shí)間 = 2019-08-25 20:58:57
RateLimiterThread-6獲取到了令牌，時(shí)間 = 2019-08-25 20:58:57
RateLimiterThread-10獲取到了令牌到逊，時(shí)間 = 2019-08-25 20:58:58
RateLimiterThread-14獲取到了令牌铣口，時(shí)間 = 2019-08-25 20:58:58
RateLimiterThread-18獲取到了令牌，時(shí)間 = 2019-08-25 20:58:58
RateLimiterThread-22獲取到了令牌觉壶，時(shí)間 = 2019-08-25 20:58:58
看到脑题，非常標(biāo)準(zhǔn)，在每次消耗一個(gè)令牌的情況下铜靶，RateLimiter可以保證每一秒內(nèi)最多只有5個(gè)線程獲取到令牌叔遂，使用這種方式可以很好的做單機(jī)對(duì)請(qǐng)求的QPS數(shù)控制他炊。
至于為什么2019-08-25 20:58:53這個(gè)時(shí)間點(diǎn)只有1條線程獲取到了令牌而不是有5條線程獲取到令牌，因?yàn)镽ateLimiter是按照秒計(jì)數(shù)的已艰，可能第一個(gè)線程是2019-08-25 20:58:53.999秒來(lái)的痊末，算在2019-08-25 20:58:53這一秒內(nèi)，下一個(gè)線程2019-08-25 20:58:54.001秒來(lái)哩掺，自然就算到2019-08-25 20:58:54這一秒去了凿叠。
上面的寫(xiě)法是RateLimiter最常用的寫(xiě)法，注意：
- acquire是阻塞的且會(huì)一直等待到獲取令牌為止嚼吞，它有一個(gè)返回值為double型盒件，意思是從阻塞開(kāi)始到獲取到令牌的等待時(shí)間，單位為秒
- tryAcquire是另外一個(gè)方法舱禽，它可以指定超時(shí)時(shí)間炒刁，返回值為boolean型，即假設(shè)線程等待了指定時(shí)間后仍然沒(méi)有獲取到令牌誊稚，那么就會(huì)返回給客戶端false翔始，客戶端根據(jù)自身情況是打回給前臺(tái)錯(cuò)誤還是定時(shí)重試
RateLimiter預(yù)消費(fèi)
處理請(qǐng)求，每次來(lái)一個(gè)請(qǐng)求就acquire一把是RateLimiter最常見(jiàn)的用法片吊，但是我們看acquire還有個(gè)acquire(int permits)的重載方法绽昏，即允許每次獲取多個(gè)令牌數(shù)。這也是有可能的俏脊，請(qǐng)求數(shù)是一個(gè)大維度每次扣減1全谤，有可能服務(wù)器按照字節(jié)數(shù)來(lái)進(jìn)行限流，例如每秒最多處理10000字節(jié)的數(shù)據(jù)爷贫，那每次扣減的就不止1了认然。
接著我們?cè)倏匆欢未a示例：
@Test
public void testRateLimiter2() {
RateLimiter rateLimiter = RateLimiter.create(1);
System.out.println("獲取1個(gè)令牌開(kāi)始，時(shí)間為" + FORMATTER.format(new Date()));
double cost = rateLimiter.acquire(1);
System.out.println("獲取1個(gè)令牌結(jié)束漫萄，時(shí)間為" + FORMATTER.format(new Date()) + ", 耗時(shí)" + cost + "ms");
System.out.println("獲取5個(gè)令牌開(kāi)始卷员，時(shí)間為" + FORMATTER.format(new Date()));
cost = rateLimiter.acquire(5);
System.out.println("獲取5個(gè)令牌結(jié)束，時(shí)間為" + FORMATTER.format(new Date()) + ", 耗時(shí)" + cost + "ms");
System.out.println("獲取3個(gè)令牌開(kāi)始腾务，時(shí)間為" + FORMATTER.format(new Date()));
cost = rateLimiter.acquire(3);
System.out.println("獲取3個(gè)令牌結(jié)束毕骡，時(shí)間為" + FORMATTER.format(new Date()) + ", 耗時(shí)" + cost + "ms");
}
代碼運(yùn)行結(jié)果為：
獲取1個(gè)令牌開(kāi)始，時(shí)間為2019-08-25 21:21:09.973
獲取1個(gè)令牌結(jié)束岩瘦，時(shí)間為2019-08-25 21:21:09.976, 耗時(shí)0.0ms
獲取5個(gè)令牌開(kāi)始未巫，時(shí)間為2019-08-25 21:21:09.976
獲取5個(gè)令牌結(jié)束，時(shí)間為2019-08-25 21:21:10.974, 耗時(shí)0.997237ms
獲取3個(gè)令牌開(kāi)始启昧，時(shí)間為2019-08-25 21:21:10.976
獲取3個(gè)令牌結(jié)束叙凡，時(shí)間為2019-08-25 21:21:15.974, 耗時(shí)4.996529ms
看到這就是標(biāo)題所說(shuō)的預(yù)消費(fèi)能力，也是RateLimiter中允許一定程度突發(fā)流量的實(shí)現(xiàn)方式密末。第二次需要獲取5個(gè)令牌握爷，指定的是每秒放1個(gè)令牌到桶中跛璧，我們發(fā)現(xiàn)實(shí)際上并沒(méi)有等5秒鐘等桶中積累了5個(gè)令牌才能讓第二次acquire成功，而是直接等了1秒鐘就成功了新啼。我們可以捋一捋這個(gè)邏輯：
- 第一次請(qǐng)求過(guò)來(lái)需要獲取1個(gè)令牌追城，直接拿到
- RateLimiter在1秒鐘后放一個(gè)令牌，第一次請(qǐng)求預(yù)支的1個(gè)令牌還上了
- 1秒鐘之后第二次請(qǐng)求過(guò)來(lái)需要獲得5個(gè)令牌师抄，直接拿到
- RateLimiter在花了5秒鐘放了5個(gè)令牌漓柑，還上了第二次請(qǐng)求預(yù)支的5個(gè)令牌
- 第三個(gè)請(qǐng)求在5秒鐘之后拿到3個(gè)令牌
也就是說(shuō)教硫，前面的請(qǐng)求如果流量大于每秒放置令牌的數(shù)量叨吮，那么允許處理，但是帶來(lái)的結(jié)果就是后面的請(qǐng)求延后處理瞬矩，從而在整體上達(dá)到一個(gè)平衡整體處理速率的效果茶鉴。
突發(fā)流量的處理，在令牌桶算法中有兩種方式景用，一種是有足夠的令牌才能消費(fèi)涵叮，一種是先消費(fèi)后還令牌。后者就像我們0首付買車似的伞插，30萬(wàn)的車很少有等攢到30萬(wàn)才全款買的割粮，先簽了相關(guān)合同把車子給你，然后貸款慢慢還媚污，這樣就爽了舀瓢。RateLimiter也是同樣的道理，先讓請(qǐng)求得到處理耗美，再慢慢還上預(yù)支的令牌京髓，客戶端同樣也爽了，否則我假設(shè)預(yù)支60個(gè)令牌商架，1分鐘之后才能處理我的請(qǐng)求堰怨，不合理也不人性化。
RateLimiter的限制
特別注意RateLimiter是單機(jī)的蛇摸，也就是說(shuō)它無(wú)法跨JVM使用备图，設(shè)置的1000QPS，那也在單機(jī)中保證平均1000QPS的流量赶袄。
假設(shè)集群中部署了10臺(tái)服務(wù)器揽涮，想要保證集群1000QPS的接口調(diào)用量，那么RateLimiter就不適用了弃鸦。
分布式限流
集群流控最常見(jiàn)的方法是使用強(qiáng)大的Redis：
- 一種是固定窗口的計(jì)數(shù)绞吁，例如當(dāng)前是2019/8/26 20:05:00，就往這個(gè)"2019/8/26 20:05:00"這個(gè)key進(jìn)行incr唬格，當(dāng)前是2019/8/26 20:05:01家破，就往"2019/8/26 20:05:01"這個(gè)key進(jìn)行incr颜说，incr后的結(jié)果只要大于我們?cè)O(shè)定的值，那么就打回去汰聋，小于就相當(dāng)于獲取到了執(zhí)行權(quán)限
- 一種是結(jié)合lua腳本门粪，實(shí)現(xiàn)分布式的令牌桶算法。通過(guò)使用 SpringDataRedis 來(lái)進(jìn)行 Redis 腳本的調(diào)用烹困。
網(wǎng)上實(shí)現(xiàn)還是比較多的玄妈，可以參考https://blog.csdn.net/sunlihuo/article/details/79700225和https://www.infoq.cn/article/Qg2tX8fyw5Vt-f3HH673
這兩篇文章。
- 使用分布式限流的框架髓梅。如 Springboot的Hystrix拟蜻、resilience4j、Sentinel(阿里) 等框架枯饿。
基于Redis和lua的分布式限流
總得來(lái)說(shuō)酝锅，集群限流的實(shí)現(xiàn)也比較簡(jiǎn)單。
