目錄
一、計數(shù)器固定窗口算法
二、計數(shù)器滑動窗口算法
三、漏斗算法
四、令牌桶算法
五、代碼
六、總結(jié)
概念
#1.為什么有限流算法
(1)系統(tǒng)面臨高并發(fā)、請求量大的情況下，為了保證系統(tǒng)服務的安全穩(wěn)定性,則需要對新的流量進行限制,也叫限流
(2)常用的限流算法有計數(shù)器固定窗口算法、滑動窗口算法、漏斗算法和令牌桶算法
#2.例子:比如web服務箕昭、對外API货抄，這種類型的服務有以下幾種可能導致機器被拖垮
(1)web服務
用戶增長過快（這是好事）
因為某個熱點事件（微博熱搜）
競爭對象爬蟲,惡意的刷單
無法預知的:不知道什么時候會有10倍甚至20倍的流量打進來，如果真碰上這種情況，擴容是根本來不及的（彈性擴容都是虛談窿吩，一秒鐘你給我擴一下試試）
(2)對外API
例子:BCDE --> A
一個服務A的接口可能被BCDE多個服務進行調(diào)用，在B服務發(fā)生突發(fā)流量時，直接把A服務給調(diào)用掛了，導致A服務對CDE也無法提供服務。
解決方案:
1、每個調(diào)用方采用線程池進行資源隔離
2、使用限流手段對每個調(diào)用方進行限流
一漓踢、計數(shù)器固定窗口算法
image-20211226102840809.png
#1.原理
(1)計數(shù)器固定窗口算法是最基礎和簡單的一種限流算法薯酝。
(2)算法核心:對一段固定時間窗口內(nèi)的請求進行計數(shù)
--如果請求數(shù)超過了閾值浩村，則舍棄該請求
--如果沒有達到設定的閾值酿矢，則接受該請求，且計數(shù)加1。
--當時間窗口結(jié)束時之众，重置計數(shù)器為0棺禾。
#2.結(jié)果分析
優(yōu)點：實現(xiàn)簡單膘婶，容易理解竣付。
缺點：流量曲線可能不夠平滑滞欠，有“突刺現(xiàn)象”(如下圖所示)
#3.該算法存在兩個問題
(1)一段時間內(nèi)(不超過時間窗口)系統(tǒng)服務不可用:比如窗口大小為1s，限流大小為100惹恃，然后恰好在某個窗口的第1ms來了100個請求，然后第2ms-999ms的請求就都會被拒絕参淹，這段時間用戶會感覺系統(tǒng)服務不可用浙值。
(2)窗口切換時可能會產(chǎn)生兩倍于閾值流量的請求(但是符合限流規(guī)則):比如窗口大小為1s开呐，限流大小為100筐付，然后恰好在某個窗口的第999ms來了100個請求瓦戚，窗口前期沒有請求冕茅，所以這100個請求都會通過姨伤。再恰好乍楚，下一個窗口的第1ms有來了100個請求徒溪，也全部通過了臊泌，那也就是在2ms之內(nèi)通過了200個請求渠概，而我們設定的閾值是100播揪，通過的請求達到了閾值的兩倍猪狈。
image-20211226103032199.png
image-20211226103238568.png
二谓形、計數(shù)器滑動窗口算法
image-20211226103324853.png
#1.原理
(1)計數(shù)器滑動窗口算法是計數(shù)器固定窗口算法的改進套耕，解決了固定窗口切換時可能會產(chǎn)生兩倍于閾值流量請求的缺點冯袍。
(2)算法核心:
--小計數(shù)器:在固定窗口的基礎上康愤，將計時窗口分成了若干個小窗口征冷，然后每個小窗口維護一個獨立的計數(shù)器检激。
--平移小窗口(頭丟棄,尾添加):當請求的時間大于當前窗口的最大時間時叔收，則將計時窗口向前平移一個小窗口饺律。平移時复濒，將第一個小窗口的數(shù)據(jù)丟棄乒省，然后將第二個小窗口設置為第一個小窗口袖扛，同時在最后面新增一個小窗口，將新的請求放在新增的小窗口中
--計數(shù)器總和小于閾值:同時要保證整個窗口中所有小窗口的請求數(shù)目之后不能超過設定的閾值妓雾。
#2.分析
(1)升級版本:滑動窗口算法就是固定窗口的升級版
(2)分割小窗口,細粒度越高,限流越精準:將計時窗口劃分成一個小窗口械姻，滑動窗口算法就退化成了固定窗口算法楷拳。而滑動窗口算法其實就是對請求數(shù)進行了更細粒度的限流欢揖，窗口劃分的越多她混，則限流越精準坤按。
#3.總結(jié)
(1)避免了計數(shù)器固定窗口算法固定窗口切換時可能會產(chǎn)生兩倍于閾值流量請求的問題臭脓；
(2)和漏斗算法相比来累，新來的請求也能夠被處理到嘹锁，避免了漏斗算法的饑餓問題兼耀。
三、漏斗算法
image-20211226104029262.png
#1.原理
(1)算法核心:
--漏斗空:請求來了先進到漏斗，漏斗以恒定的速率將請求流出處理韭山，從而起到平滑流量的作用钱磅。
--漏斗滿:當請求的流量過大時盖淡，漏斗達到最大容量時會溢出褪迟，此時請求被丟棄味赃。
(2)保護系統(tǒng),兜底:加了一層漏斗算法限流之后心俗，就能夠保證請求以恒定的速率流出城榛。在系統(tǒng)看來吠谢，請求永遠是以平滑的傳輸速率過來工坊，從而起到了保護系統(tǒng)的作用王污。因為我們不知道請求會以多大的速率來昭齐，這就給系統(tǒng)的安全性埋下了隱患
#2.分析
(1)可以看到1-5號請求被接受阱驾，而6-10號請求被拒絕里覆，說明此時漏斗已經(jīng)溢出了喧枷，符合我們的預期
(2)漏斗算法的特點:即雖然請求流量是瞬時產(chǎn)生的，但是請求以固定速率流出被處理车荔。
#3.產(chǎn)生問題
(1)漏桶的漏出速率是固定的渡冻，可以起到整流的作用:即雖然請求的流量可能具有隨機性,忽大忽小，但是經(jīng)過漏斗算法之后忧便，變成了有固定速率的穩(wěn)定流量族吻，從而對下游的系統(tǒng)起到保護作用。
(2)不能解決流量突發(fā)的問題:我們設定的漏斗速率是2個/秒茬腿，然后突然來了10個請求
--受限于漏斗的容量5呼奢，只有5個請求被接受切平，另外5個被拒絕握础。
--你可能會說，漏斗速率是2個/秒悴品，然后瞬間接受了5個請求禀综，這不就解決了流量突發(fā)的問題嗎？不苔严，這5個請求只是被接受但沒馬上處理定枷，處理速度仍是設定的2個/秒，所以沒有解決流量突發(fā)的問題(令牌桶算法能夠在一定程度上解決流量突發(fā)的問題)
四届氢、令牌桶算法
image-20211226104706688.png
#1.原理
(1)算法概念:令牌桶算法是對漏斗算法的一種改進欠窒，除了能夠起到限流的作用外，還允許一定程度的流量突發(fā)退子。
(2)算法核心
--存在一個令牌桶岖妄，算法中存在一種機制以恒定的速率向令牌桶中放入令牌,令牌桶也有一定的容量,如果滿了令牌就無法放進去了。
--當請求來時寂祥，會首先到令牌桶中去拿令牌荐虐，如果拿到了令牌，則該請求會被處理丸凭，并消耗掉拿到的令牌福扬；---如果令牌桶為空，則該請求會被丟棄惜犀。
#2.分析
(1)例子:同樣取令牌桶算法的容量是5铛碑，產(chǎn)生令牌的速度為2個/秒，然后模擬了連續(xù)的10個請求虽界，編號從1-10
(2)對于這10個請求,令牌桶和漏斗算法一樣接受了5個請求,拒絕了5個請求,但不同的是令牌桶是馬上處理了這5個請求,可以認為處理速度是5個/秒,
對于10個請求亚茬，令牌桶算法和漏斗算法一樣，都是接受了5個請求浓恳，拒絕了5個請求刹缝。與漏斗算法不同的是，令牌桶算法馬上處理了這5個請求颈将，處理速度可以認為是5個/秒梢夯，超過了我們設定的2個/秒的速率，即允許一定程度的流量突發(fā)晴圾。這一點也是和漏斗算法的主要區(qū)別
(3)限平均速率,允許一定流量突發(fā):令牌桶算法是對漏桶算法的一種改進颂砸，除了能夠在限制調(diào)用的平均速率的同時還允許一定程度的流量突發(fā)。
#3.other
(1)Guava的ratelimit實現(xiàn)思路:他的限流就是基于令牌桶算法,但是比較遺憾的是在單機下的限流
(2)合理設置間隔的時間,減小服務器壓力
--間隔如果過短的話,一次性向桶里添加的令牌數(shù)量則是桶的最大容量!那么某個時間的瞬間請求過來,服務器的壓力是非常大的.
--所以此處增加令牌數(shù)可以設置的稍微合理些,哪怕間隔時間再長!
五死姚、代碼
5.1 計數(shù)器固定窗口算法
package com.fong.CountLimiter;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author fong
* @date 2021/12/18 - 7:19:25
*/
public class CounterLimiter {
private int windowSize; // 窗口大小人乓，毫秒為單位(窗口寬度)
private int limit;// 窗口內(nèi)限流大小(窗口容量)
private AtomicInteger count;// 當前窗口的原子計數(shù)器(窗口計數(shù)器)
private CounterLimiter() {
}
public CounterLimiter(int windowSize, int limit) {
this.limit = limit;
this.windowSize = windowSize;
count = new AtomicInteger(0);
// 開啟一個線程，達到窗口結(jié)束時清空count(每隔一段時間刷新一次窗口的計數(shù)器)
// 相當于Redis的過期時間
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
count.set(0);
try {
Thread.sleep(windowSize);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
// 請求到達后先調(diào)用本方法都毒，若返回true色罚，則請求通過，否則限流
public boolean tryAcquire() {
int newCount = count.addAndGet(1);
return newCount <= limit;
}
public static void main(String[] args) throws InterruptedException {
// 1.構(gòu)造滑動窗口, 每秒允許20個請求
CounterLimiter counterLimiter = new CounterLimiter(1000, 20);
int count = 0;
// 2.模擬請求
// 2.1模擬50次請求账劲，看多少能通過
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
System.out.println("第一撥50次請求中通過：" + count + ",限流：" + (50 - count));
// 2.2過一秒再請求
Thread.sleep(1000);
// 2.3模擬50次請求戳护，看多少能通過
count = 0;
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
System.out.println("第二撥50次請求中通過：" + count + ",限流：" + (50 - count));
}
}
#分布式
// redis的ttl特性完美的滿足了這一需求,將時間窗口設置為key的失效時間,然后將key的值每次請求+1即可.偽代碼實現(xiàn)思路:
// 1.判斷是否存在該key
if(EXIT(key)){
// 1.1自增后判斷是否大于最大值,并返回結(jié)果
if(INCR(key) > maxPermit){
return false;
}
return true;
}
// 2.不存在key,則設置key初始值為1,失效時間為3秒
SET(KEY,1);
EXPIRE(KEY,3);
5.2 計數(shù)器滑動窗口算法
package com.fong.CountLimiter;
/**
* @author fong
* @date 2021/12/18 - 8:05:30
*/
public class CounterSlideWindowLimiter {
private int windowSize; // 窗口大小，毫秒為單位
private int limit;// 窗口內(nèi)限流大小
private int splitNum;// 切分小窗口的數(shù)目大小
private int[] counters;// 每個小窗口的計數(shù)數(shù)組
private int index;// 當前小窗口計數(shù)器的索引
private long startTime;// 窗口開始時間
private CounterSlideWindowLimiter() {
}
//
public CounterSlideWindowLimiter(int windowSize, int limit, int splitNum) {
this.limit = limit;
this.windowSize = windowSize;
this.splitNum = splitNum;
counters = new int[splitNum];
index = 0;
startTime = System.currentTimeMillis();
}
// 請求到達后先調(diào)用本方法瀑焦，若返回true腌且，則請求通過，否則限流
public synchronized boolean tryAcquire() {
long curTime = System.currentTimeMillis();
// 計算滑動小窗口的數(shù)量 = 第二個大窗口往后多出來的時間 / 小窗口時間
long windowsNum = Math.max(curTime - windowSize - startTime, 0) / (windowSize / splitNum);
slideWindow(windowsNum);// 滑動窗口
int count = 0;
for (int i = 0; i < splitNum; i++) {
count += counters[i];
}
if (count >= limit) {
return false;
} else {
counters[index]++;
return true;
}
}
private synchronized void slideWindow(long windowsNum) {
if (windowsNum == 0)
return;
// 新的滑動窗口的計算器置為0
long slideNum = Math.min(windowsNum, splitNum);
for (int i = 0; i < slideNum; i++) {
index = (index + 1) % splitNum;
counters[index] = 0;
}
// 更新滑動窗口時間
startTime = startTime + windowsNum * (windowSize / splitNum);
}
public static void main(String[] args) throws InterruptedException {
// 每秒20個請求
int limit = 20;
CounterSlideWindowLimiter counterSlideWindowLimiter = new CounterSlideWindowLimiter(1000, limit, 10);
int count = 0;
Thread.sleep(3000);
// 計數(shù)器滑動窗口算法模擬100組間隔30ms的50次請求
System.out.println("計數(shù)器滑動窗口算法測試開始");
System.out.println("開始模擬100組間隔150ms的50次請求");
int failCount = 0;
for (int j = 0; j < 100; j++) {
count = 0;
for (int i = 0; i < 50; i++) {
if (counterSlideWindowLimiter.tryAcquire()) {
count++;
}
}
Thread.sleep(150);
// 模擬50次請求榛瓮，看多少能通過
for (int i = 0; i < 50; i++) {
if (counterSlideWindowLimiter.tryAcquire()) {
count++;
}
}
if (count > limit) {
System.out.println("時間窗口內(nèi)放過的請求超過閾值铺董，放過的請求數(shù)" + count + ",限流：" + limit);
failCount++;
}
Thread.sleep((int) (Math.random() * 100));
}
System.out.println("計數(shù)器滑動窗口算法測試結(jié)束，100組間隔150ms的50次請求模擬完成禀晓，限流失敗組數(shù)：" + failCount);
System.out.println("===========================================================================================");
// 計數(shù)器固定窗口算法模擬100組間隔30ms的50次請求
System.out.println("計數(shù)器固定窗口算法測試開始");
// 模擬100組間隔30ms的50次請求
CounterLimiter counterLimiter = new CounterLimiter(1000, limit);
System.out.println("開始模擬100組間隔150ms的50次請求");
failCount = 0;
for (int j = 0; j < 100; j++) {
count = 0;
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
Thread.sleep(150);
// 模擬50次請求精续，看多少能通過
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
if (count > limit) {
System.out.println("時間窗口內(nèi)放過的請求超過閾值，放過的請求數(shù)" + count + ",限流：" + limit);
failCount++;
}
Thread.sleep((int) (Math.random() * 100));
}
System.out.println("計數(shù)器滑動窗口算法測試結(jié)束匆绣，100組間隔150ms的50次請求模擬完成驻右，限流失敗組數(shù)：" + failCount);
}
}
5.3 漏斗算法
package com.fong.CountLimiter;
import java.util.Date;
import java.util.LinkedList;
public class LeakyBucketLimiter {
private int capaticy;// 漏斗容量
private int rate;// 漏斗速率
private int left;// 剩余容量
private LinkedList<Request> requestList;
private LeakyBucketLimiter() {}
public LeakyBucketLimiter(int capaticy, int rate) {
this.capaticy = capaticy;
this.rate = rate;
this.left = capaticy;
requestList = new LinkedList<>();
// 開啟一個定時線程，以固定的速率將漏斗中的請求流出崎淳，進行處理
new Thread(new Runnable() {
@Override
public void run() {
while(true){
if(!requestList.isEmpty()){
Request request = requestList.removeFirst();
handleRequest(request);
}
try {
Thread.sleep(1000 / rate); //睡眠
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
/**
* 處理請求
* @param request
*/
private void handleRequest(Request request){
request.setHandleTime(new Date());
System.out.println(request.getCode() + "號請求被處理堪夭，請求發(fā)起時間："
+ request.getLaunchTime() + ",請求處理時間：" + request.getHandleTime() + ",處理耗時："
+ (request.getHandleTime().getTime() - request.getLaunchTime().getTime()) + "ms");
}
public synchronized boolean tryAcquire(Request request){
if(left <= 0){
return false;
}else{
left--;
requestList.addLast(request);
return true;
}
}
public static void main(String[] args) {
LeakyBucketLimiter leakyBucketLimiter = new LeakyBucketLimiter(5,2);
for(int i = 1;i <= 10;i ++){
Request request = new Request(i,new Date());
if(leakyBucketLimiter.tryAcquire(request)){
System.out.println(i + "號請求被接受");
}else{
System.out.println(i + "號請求被拒絕");
}
}
}
/**
* 請求類，屬性包含編號字符串拣凹、請求達到時間和請求處理時間
*/
static class Request{
private int code;
private Date launchTime;
private Date handleTime;
private Request() { }
public Request(int code,Date launchTime) {
this.launchTime = launchTime;
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public Date getLaunchTime() {
return launchTime;
}
public void setLaunchTime(Date launchTime) {
this.launchTime = launchTime;
}
public Date getHandleTime() {
return handleTime;
}
public void setHandleTime(Date handleTime) {
this.handleTime = handleTime;
}
}
}
5.4 令牌桶算法
package com.fong.CountLimiter;
import java.util.Date;
public class TokenBucketLimiter {
private int capaticy;// 令牌桶容量
private int rate;// 令牌產(chǎn)生速率
private int tokenAmount;// 令牌數(shù)量
public TokenBucketLimiter(int capaticy, int rate) {
this.capaticy = capaticy;
this.rate = rate;
tokenAmount = capaticy;
new Thread(new Runnable() {
@Override
public void run() {
// 以恒定速率放令牌
while (true) {
synchronized (this) {
tokenAmount++;
if (tokenAmount > capaticy) {
tokenAmount = capaticy;
}
}
try {
Thread.sleep(1000 / rate);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
public synchronized boolean tryAcquire(Request request) {
if (tokenAmount > 0) {
tokenAmount--;
handleRequest(request);
return true;
} else {
return false;
}
}
/**
* 處理請求
*
* @param request
*/
private void handleRequest(Request request) {
request.setHandleTime(new Date());
System.out.println(request.getCode() + "號請求被處理森爽，請求發(fā)起時間："
+ request.getLaunchTime() + ",請求處理時間：" + request.getHandleTime() + ",處理耗時："
+ (request.getHandleTime().getTime() - request.getLaunchTime().getTime()) + "ms");
}
/**
* 請求類，屬性只包含一個名字字符串
*/
static class Request {
private int code;
private Date launchTime;
private Date handleTime;
private Request() {
}
public Request(int code, Date launchTime) {
this.launchTime = launchTime;
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public Date getLaunchTime() {
return launchTime;
}
public void setLaunchTime(Date launchTime) {
this.launchTime = launchTime;
}
public Date getHandleTime() {
return handleTime;
}
public void setHandleTime(Date handleTime) {
this.handleTime = handleTime;
}
}
public static void main(String[] args) throws InterruptedException {
TokenBucketLimiter tokenBucketLimiter = new TokenBucketLimiter(5, 2);
for (int i = 1; i <= 10; i++) {
Request request = new Request(i, new Date());
if (tokenBucketLimiter.tryAcquire(request)) {
System.out.println(i + "號請求被接受");
} else {
System.out.println(i + "號請求被拒絕");
}
}
}
}
#pom.xml
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>18.0</version>
</dependency>
#java
package com.fong.other;
import com.google.common.util.concurrent.RateLimiter;
public class RateLimiterMain {
public static void main(String[] args) {
// 創(chuàng)建了一個每秒生成10個令牌的限流器嚣镜，即100ms生成一個爬迟，并最多保存10個令牌，多余的會被丟棄
RateLimiter rateLimiter = RateLimiter.create(10);
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
rateLimiter.acquire();
System.out.println("pass");
}
}).start();
}
}
}
六菊匿、總結(jié)
#1算法
計數(shù)器固定窗口算法:實現(xiàn)簡單付呕，容易理解计福。和漏斗算法相比，新來的請求也能夠被馬上處理到徽职。但是流量曲線可能不夠平滑象颖，有“突刺現(xiàn)象”，在窗口切換時可能會產(chǎn)生兩倍于閾值流量的請求姆钉。
計數(shù)器滑動窗口算法:計數(shù)器固定窗口算法的一種改進说订，有效解決了窗口切換時可能會產(chǎn)生兩倍于閾值流量請求的問題。
漏斗算法:能夠?qū)α髁科鸬秸鞯淖饔贸逼浚岆S機不穩(wěn)定的流量以固定的速率流出陶冷，但是不能解決流量突發(fā)的問題。
令牌桶算法:作為漏斗算法的一種改進毯辅，除了能夠起到平滑流量的作用埂伦，還允許一定程度的流量突發(fā)。
#2.沒有最好的算法悉罕，只有最合適的算法赤屋。
--令牌桶算法(自身的系統(tǒng)實際的處理能力強于配置的流量限制):一般用于保護自身的系統(tǒng)，對調(diào)用者進行限流壁袄，保護自身的系統(tǒng)不被突發(fā)的流量打垮类早。可以允許一定程度的流量突發(fā)嗜逻，使得實際的處理速率高于配置的速率涩僻，充分利用系統(tǒng)資源。
--而漏斗算法(保護第三方的系統(tǒng),支付系統(tǒng)...):比如自身的系統(tǒng)需要調(diào)用第三方的接口栈顷，為了保護第三方的系統(tǒng)不被自身的調(diào)用打垮逆日，便可以通過漏斗算法進行限流，保證自身的流量平穩(wěn)的打到第三方的接口上
image-20211226124621430.png
ref:
四種限流算法:
https://blog.csdn.net/weixin_41846320/article/details/95941361
https://blog.csdn.net/linhui258/article/details/81155622
https://segmentfault.com/a/1190000017078491
https://zhuanlan.zhihu.com/p/228412634
