本文會(huì)對(duì)這4個(gè)限流算法進(jìn)行詳細(xì)說(shuō)明，并輸出實(shí)現(xiàn)限流算法的代碼示例。
代碼是按照自己的理解寫(xiě)的，很簡(jiǎn)單的實(shí)現(xiàn)了功能，還請(qǐng)大佬們多多交流找bug。
下面還有投票，幫忙投個(gè)票👍

前言

什么是限流？限流 限流 就是限制流量。在高并發(fā)、高流量的場(chǎng)景中我們需要把限流做好，防止突發(fā)的流量、惡意的攻擊等大量請(qǐng)求的沖擊帶來(lái)不必要的影響，保證業(yè)務(wù)系統(tǒng)的正常運(yùn)行。

如何限流？首先我們需要知道限流的基本思路，其次需要知道限流的幾種實(shí)現(xiàn)方式（這里我們叫限流算法）。

限流的基本思路就是在一個(gè)單位時(shí)間內(nèi)流量超過(guò)某個(gè)閾值后被拒絕或限制。

目前常見(jiàn)的限流算法有計(jì)數(shù)器（固定時(shí)間窗口）算法、滑動(dòng)時(shí)間窗口算法、漏斗算法、令牌算法。

1、計(jì)數(shù)器（固定時(shí)間窗口）算法

計(jì)數(shù)器（固定時(shí)間窗口）算法是最簡(jiǎn)單的限流算法，實(shí)現(xiàn)方式也比較簡(jiǎn)單。

原理

其原理是：通過(guò)維護(hù)一個(gè)單位時(shí)間內(nèi)的計(jì)數(shù)值，每當(dāng)一個(gè)請(qǐng)求通過(guò)時(shí)，就將計(jì)數(shù)值加1，當(dāng)計(jì)數(shù)值超過(guò)預(yù)先設(shè)定的閾值時(shí)，就拒絕單位時(shí)間內(nèi)的其他請(qǐng)求。如果單位時(shí)間已經(jīng)結(jié)束，則將計(jì)數(shù)器清零，開(kāi)啟下一輪的計(jì)數(shù)。

代碼實(shí)現(xiàn)

import java.util.Random;public class Counter {//時(shí)間窗口private final int interval = 1000;//時(shí)間窗口內(nèi)的閾值private final int limit = 5;private long lastTime = System.currentTimeMillis();private int counter = 0;public boolean tryAcquire() {if (System.currentTimeMillis() < lastTime + interval) {// 在時(shí)間窗口內(nèi)counter++;} else {//超過(guò)時(shí)間窗口充值重置counterlastTime = System.currentTimeMillis();counter = 1;}return counter <= limit;}public static void main(String[] args) throws InterruptedException {Counter counter = new Counter();while (true) {if (counter.tryAcquire()) {System.out.println("進(jìn)行請(qǐng)求");} else {System.out.println("限流了。。。。");}Thread.sleep(100 * new Random().nextInt(5));}}
}

存在的問(wèn)題

但是這種實(shí)現(xiàn)會(huì)有一個(gè)問(wèn)題，舉個(gè)例子:

假設(shè)我們?cè)O(shè)定1s內(nèi)允許通過(guò)的請(qǐng)求閾值是100，如果在時(shí)間窗口的最后幾毫秒發(fā)送了99個(gè)請(qǐng)求，緊接著又在下一個(gè)時(shí)間窗口開(kāi)始時(shí)發(fā)送了99個(gè)請(qǐng)求，那么這個(gè)用戶其實(shí)在一秒顯然超過(guò)了閾值但并不會(huì)被限流。其實(shí)這就是臨界值問(wèn)題，那么臨界值問(wèn)題要怎么解決呢？

2、滑動(dòng)時(shí)間窗口算法

原理

滑動(dòng)時(shí)間窗口算法就是為了解決上述固定時(shí)間窗口存在的臨界值問(wèn)題而誕生。要解決這種臨界值問(wèn)題，顯然只用一個(gè)窗口是解決不了問(wèn)題的。假設(shè)我們?nèi)匀辉O(shè)定1秒內(nèi)允許通過(guò)的請(qǐng)求是200個(gè)，但是在這里我們需要把1秒的時(shí)間分成多格，假設(shè)分成5格（格數(shù)越多，流量過(guò)渡越平滑），每格窗口的時(shí)間大小是200毫秒，每過(guò)200毫秒，就將窗口向前移動(dòng)一格。為了便于理解，可以看下圖

圖中將窗口劃為5份，每個(gè)小窗口中的數(shù)字表示在這個(gè)窗口中請(qǐng)求數(shù)，所以通過(guò)觀察上圖，可知在當(dāng)前窗口（200毫秒）只要超過(guò)110就會(huì)被限流。

代碼實(shí)現(xiàn)

這里我用了 LinkedList 作為分割窗口，可以快速的實(shí)現(xiàn)功能。

import java.util.LinkedList;
import java.util.Random;public class MovingWindow {//時(shí)間窗口/msprivate final int interval = 1000;//時(shí)間窗口內(nèi)的閾值private final int limit = 5;//分割窗口個(gè)數(shù)private int slotCount = 5;private LinkedList<Node> slot = new LinkedList<Node>();public MovingWindow() {new Thread(() -> {while (true) {// 每過(guò)200毫秒，就將窗口向前移動(dòng)一格if (slot.size() == slotCount) {slot.poll();}slot.offer(new Node(System.currentTimeMillis()));try {Thread.sleep(interval / slotCount);} catch (InterruptedException e) {e.printStackTrace();}}}).start();}public boolean tryAcquire() {Node currWindow = getCurrWindow();currWindow.setCount(currWindow.getCount() + 1);return getCounter() <= limit;}private int getCounter() {return slot.stream().mapToInt(Node::getCount).sum();}private Node getCurrWindow() {if (slot.isEmpty()) {while (true) {if (slot.isEmpty()) {try {Thread.sleep(10);} catch (InterruptedException e) {e.printStackTrace();}} else break;}}return slot.getLast();}private class Node {private int count;private long time;public Node(long time) {this.time = time;}public int getCount() {return count;}public void setCount(int count) {this.count = count;}public long getTime() {return time;}public void setTime(long time) {this.time = time;}}public static void main(String[] args) throws InterruptedException {MovingWindow counter = new MovingWindow();while (true) {counter.slot.stream().forEach(node -> System.out.print(node.getTime() + ":" + node.getCount() + "|"));if (counter.tryAcquire()) {System.out.println("進(jìn)行請(qǐng)求");} else {System.out.println("限流了。。。。");}Thread.sleep(100 * new Random().nextInt(5));}}}

存在的問(wèn)題

那么滑動(dòng)窗口限流法是完美的嗎？細(xì)心觀察我們應(yīng)該能馬上發(fā)現(xiàn)問(wèn)題，如下圖：

0ms-1000ms、200ms-1200ms的請(qǐng)求在我們?cè)O(shè)置的閾值內(nèi)，但是100ms-1100ms的請(qǐng)求一共是220，超過(guò)了我們所設(shè)置的閾值。

滑動(dòng)時(shí)間窗口限流法其實(shí)就是計(jì)數(shù)器算法的一個(gè)變種，依然存在臨界值的問(wèn)題。并且流量的過(guò)渡是否平滑依賴于我們?cè)O(shè)置的窗口格數(shù)，格數(shù)越多，統(tǒng)計(jì)越精確，但是具體要分多少格呢？

3、漏桶算法

上面所介紹的兩種算法存在流量不能平滑的過(guò)渡，下面介紹下漏桶算法。

原理

漏桶算法以一個(gè)常量限制了出口流量速率，因此漏桶算法可以平滑突發(fā)的流量。其中漏桶作為流量容器我們可以看做一個(gè)FIFO的隊(duì)列，當(dāng)入口流量速率大于出口流量速率時(shí)，因?yàn)榱髁咳萜魇怯邢薜?#xff0c;超出的流量會(huì)被丟棄。

下圖比較形象的說(shuō)明了漏桶算法的原理，其中水滴是入口流量，漏桶是流量容器，勻速流出的水是出口流量。

代碼實(shí)現(xiàn)

這里我用了 ArrayBlockingQueue 作為漏桶，可以快速的實(shí)現(xiàn)功能。

import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;public class Funnel {//出口流量速率 1s 10個(gè)private int rate = 10;//漏桶private ArrayBlockingQueue bucket;public Funnel(int rate, int capacity) {this.rate = rate;this.bucket = new ArrayBlockingQueue(capacity);int speed = 1000 / this.rate;//固定速率滴水new Thread(() -> {while (true) {bucket.poll();try {Thread.sleep(speed);} catch (InterruptedException e) {e.printStackTrace();}}}).start();}public boolean tryAcquire() {// 漏桶里面放水return bucket.offer(this);}public static void main(String[] args) throws InterruptedException {Funnel funnel = new Funnel(10, 100);while (true) {if (funnel.tryAcquire()) {System.out.println("進(jìn)行請(qǐng)求");} else {System.out.println("限流了。。。。");}Thread.sleep(20 * new Random().nextInt(5));}}}

存在的問(wèn)題

因?yàn)槁┩八惴ǖ牧鞒鏊俾适枪潭ǖ?#xff0c;所以漏桶算法不支持出現(xiàn)突發(fā)流出流量。但是在實(shí)際情況下，流量往往是突發(fā)的。

4、令牌桶算法

令牌桶算法是漏桶算法的改進(jìn)版，可以支持突發(fā)流量。不過(guò)與漏桶算法不同的是，令牌桶算法的漏桶中存放的是令牌而不是流量。

原理

令牌桶算法是如何支持突發(fā)流量的呢？最開(kāi)始，令牌桶是空的，我們以恒定速率往令牌桶里加入令牌，令牌桶被裝滿時(shí)，多余的令牌會(huì)被丟棄。當(dāng)請(qǐng)求到來(lái)時(shí)，會(huì)先嘗試從令牌桶獲取令牌（相當(dāng)于從令牌桶移除一個(gè)令牌），獲取成功則請(qǐng)求被放行，獲取失敗則阻塞或拒絕請(qǐng)求。那么當(dāng)突發(fā)流量來(lái)臨時(shí)，只要令牌桶有足夠的令牌，就不會(huì)被限流。

代碼實(shí)現(xiàn)

import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;public class Token {//添加令牌速率 1s 10個(gè)private int rate = 10;//漏桶private ArrayBlockingQueue bucket;public Token(int rate, int capacity) {this.rate = rate;this.bucket = new ArrayBlockingQueue(capacity);//恒定速率往漏桶里面添加令牌int speed = 1000 / this.rate;new Thread(() -> {while (true) {bucket.offer(this);try {Thread.sleep(speed);} catch (InterruptedException e) {e.printStackTrace();}}}).start();}public boolean tryAcquire() {// 漏桶里面取令牌return null != bucket.poll();}public static void main(String[] args) throws InterruptedException {Token funnel = new Token(10, 100);//8s后突發(fā)流量Thread.sleep(8000);while (true) {if (funnel.tryAcquire()) {System.out.println("進(jìn)行請(qǐng)求");} else {System.out.println("限流了。。。。");}Thread.sleep(20 * new Random().nextInt(5));}}}

最后

或許大家在工作中會(huì)用現(xiàn)成的一些限流組件比如：Spring Cloud 的 Hystrix 、Spring Cloud Alibaba 的 Sentinel 或者是 Google 的 Guava 限流器。其實(shí)現(xiàn)原理離不開(kāi)上述所說(shuō)的4種限流算法，我們開(kāi)發(fā)人員還是要知其然，知其所以然。