<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
Java 常見的限流演演算法詳細分析並實現
2022-04-07 19:00:15
為什麼要限流
在保證可用的情況下儘可能多增加進入的人數,其餘的人在排隊等待,或者返回友好提示,保證裡面的進行系統的使用者可以正常使用，防止系統雪崩。
限流演演算法
限流演演算法很多,常見的有三類,分別是 計數器演演算法 、漏桶演演算法、令牌桶演演算法 。
（1）計數器：
在一段時間間隔內，處理請求的最大數量固定，超過部分不做處理。
（2）漏桶：
漏桶大小固定，處理速度固定，但請求進入速度不固定（在突發情況請求過多時，會丟棄過多的請求）。
（3）令牌桶：
令牌桶的大小固定，令牌的產生速度固定，但是消耗令牌（即請求）速度不固定（可以應對一些某些時間請求過多的情況）；每個請求都會從令牌桶中取出令牌，如果沒有令牌則丟棄該次請求。
計數器限流
在一段時間間隔內，處理請求的最大數量固定，超過部分不做處理。
舉個例子,比如我們規定對於A介面，我們1分鐘的存取次數不能超過100次。
那麼我們可以這麼做：
在一開 始的時候，我們可以設定一個計數器counter，每當一個請求過來的時候，counter就加1，如果counter的值大於100並且該請求與第一個請求的間隔時間還在1分鐘之內，那麼說明請求數過多,拒絕存取；
如果該請求與第一個請求的間隔時間大於1分鐘，且counter的值還在限流範圍內，那麼就重置 counter,就是這麼簡單粗暴。
程式碼實現：
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
//計數器 限流
public class CounterLimiter {
//起始時間
private static long startTime = System.currentTimeMillis();
//時間間隔1000ms
private static long interval = 1000;
//每個時間間隔內，限制數量
private static long limit = 3;
//累加器
private static AtomicLong accumulator = new AtomicLong();
/**
* true 代表放行，請求可已通過
* false 代表限制，不讓請求通過
*/
public static boolean tryAcquire() {
long nowTime = System.currentTimeMillis();
//判斷是否在上一個時間間隔內
if (nowTime < startTime + interval) {
//如果還在上個時間間隔內
long count = accumulator.incrementAndGet();
if (count <= limit) {
return true;
} else {
return false;
}
} else {
//如果不在上一個時間間隔內
synchronized (CounterLimiter.class) {
//防止重複初始化
if (nowTime > startTime + interval) {
startTime = nowTime;
accumulator.set(0);
}
}
//再次進行判斷
long count = accumulator.incrementAndGet();
if (count <= limit) {
return true;
} else {
return false;
}
}
}
// 測試
public static void main(String[] args) {
//執行緒池，用於多執行緒模擬測試
ExecutorService pool = Executors.newFixedThreadPool(10);
// 被限制的次數
AtomicInteger limited = new AtomicInteger(0);
// 執行緒數
final int threads = 2;
// 每條執行緒的執行輪數
final int turns = 20;
// 同步器
CountDownLatch countDownLatch = new CountDownLatch(threads);
long start = System.currentTimeMillis();
for (int i = 0; i < threads; i++) {
pool.submit(() ->
{
try {
for (int j = 0; j < turns; j++) {
boolean flag = tryAcquire();
if (!flag) {
// 被限制的次數累積
limited.getAndIncrement();
}
Thread.sleep(200);
}
} catch (Exception e) {
e.printStackTrace();
}
//等待所有執行緒結束
countDownLatch.countDown();
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
float time = (System.currentTimeMillis() - start) / 1000F;
//輸出統計結果
System.out.println("限制的次數為：" + limited.get() +
",通過的次數為：" + (threads * turns - limited.get()));
System.out.println("限制的比例為：" + (float) limited.get() / (float) (threads * turns));
System.out.println("執行的時長為：" + time + "s");
}
}
計數器限流的不足：
這個演演算法雖然簡單，但是存在臨界問題，我們看下圖：
從上圖中我們可以看到，假設有一個惡意使用者，他在0:59時，瞬間傳送了100個請求，並且1:00又瞬間傳送了100個請求，那麼其實這個使用者在 1秒裡面，瞬間傳送了200個請求。
我們剛才規定的是1分鐘最多100個請求（規劃的吞吐量），也就是每秒鐘最多1.7個請求，使用者通過在時間視窗的重置節點處突發請求， 可以瞬間超過我們的速率限制。
使用者有可能通過演演算法的這個漏洞，瞬間壓垮我們的應用。
漏桶限流
漏桶演演算法限流的基本原理為：水（對應請求）從進水口進入到漏桶裡，漏桶以一定的速度出水（請求放行），當水流入速度過大，桶內的總水量大於桶容量會直接溢位，請求被拒絕。
大致的漏桶限流規則如下：
（1）進水口（對應使用者端請求）以任意速率流入進入漏桶。
（2）漏桶的容量是固定的，出水（放行）速率也是固定的。
（3）漏桶容量是不變的，如果處理速度太慢，桶內水量會超出了桶的容量，則後面流入的水滴會溢位，表示請求拒絕。
⭐漏桶演演算法其實很簡單，可以粗略的認為就是注水漏水過程，往桶中以任意速率流入水，以一定速率流出水，當水超過桶容量（capacity）則丟棄，因為桶容量是不變的，保證了整體的速率。
以一定速率流出水，
削峰： 有大量流量進入時,會發生溢位,從而限流保護服務可用
緩衝： 不至於直接請求到伺服器, 緩衝壓力
程式碼實現：
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
//漏斗限流
public class LeakBucketLimiter {
//桶的大小
private static long capacity = 10;
//流出速率,每秒兩個
private static long rate = 2;
//開始時間
private static long startTime = System.currentTimeMillis();
//桶中剩餘的水
private static AtomicLong water = new AtomicLong();
/**
* true 代表放行，請求可已通過
* false 代表限制，不讓請求通過
*/
public synchronized static boolean tryAcquire() {
//如果桶的餘量問0，直接放行
if (water.get() == 0) {
startTime = System.currentTimeMillis();
water.set(1);
return true;
}
//計算從當前時間到開始時間流出的水，和現在桶中剩餘的水
//桶中剩餘的水
water.set(water.get() - (System.currentTimeMillis() - startTime) / 1000 * rate);
//防止出現<0的情況
water.set(Math.max(0, water.get()));
//設定新的開始時間
startTime += (System.currentTimeMillis() - startTime) / 1000 * 1000;
//如果當前水小於容量，表示可以放行
if (water.get() < capacity) {
water.incrementAndGet();
return true;
} else {
return false;
}
}
// 測試
public static void main(String[] args) {
//執行緒池，用於多執行緒模擬測試
ExecutorService pool = Executors.newFixedThreadPool(10);
// 被限制的次數
AtomicInteger limited = new AtomicInteger(0);
// 執行緒數
final int threads = 2;
// 每條執行緒的執行輪數
final int turns = 20;
// 同步器
CountDownLatch countDownLatch = new CountDownLatch(threads);
long start = System.currentTimeMillis();
for (int i = 0; i < threads; i++) {
pool.submit(() ->
{
try {
for (int j = 0; j < turns; j++) {
boolean flag = tryAcquire();
if (!flag) {
// 被限制的次數累積
limited.getAndIncrement();
}
Thread.sleep(200);
}
} catch (Exception e) {
e.printStackTrace();
}
//等待所有執行緒結束
countDownLatch.countDown();
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
float time = (System.currentTimeMillis() - start) / 1000F;
//輸出統計結果
System.out.println("限制的次數為：" + limited.get() +
",通過的次數為：" + (threads * turns - limited.get()));
System.out.println("限制的比例為：" + (float) limited.get() / (float) (threads * turns));
System.out.println("執行的時長為：" + time + "s");
}
}
漏桶的不足：
漏桶的出水速度固定，也就是請求放行速度是固定的。
漏桶出口的速度固定，不能靈活的應對後端能力提升。比如，通過動態擴容，後端流量從1000QPS提升到1WQPS，漏桶沒有辦法。
令牌桶限流
令牌桶演演算法中新請求到來時會從桶裡拿走一個令牌，如果桶內沒有令牌可拿，就拒絕服務。 當然，令牌的數量也是有上限的。令牌的數量與時間和發放速率強相關，時間流逝的時間越長，會不斷往桶裡加入越多的令牌，如果令牌發放的速度比申請速度快，令牌桶會放滿令牌，直到令牌佔滿整個令牌桶。
令牌桶限流大致的規則如下：
（1）進水口按照某個速度，向桶中放入令牌。
（2）令牌的容量是固定的，但是放行的速度不是固定的，只要桶中還有剩餘令牌，一旦請求過來就能申請成功，然後放行。
（3）如果令牌的發放速度，慢於請求到來速度，桶內就無牌可領，請求就會被拒絕。
總之，令牌的傳送速率可以設定，從而可以對突發的出口流量進行有效的應對。
程式碼實現：
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
//令牌桶
public class TokenBucketLimiter {
//桶的容量
private static long capacity = 10;
//放入令牌的速率,每秒2個
private static long rate = 2;
//上次放置令牌的時間
private static long lastTime = System.currentTimeMillis();
//桶中令牌的餘量
private static AtomicLong tokenNum = new AtomicLong();
/**
* true 代表放行，請求可已通過
* false 代表限制，不讓請求通過
*/
public synchronized static boolean tryAcquire() {
//更新桶中剩餘令牌的數量
long now = System.currentTimeMillis();
tokenNum.addAndGet((now - lastTime) / 1000 * rate);
tokenNum.set(Math.min(capacity, tokenNum.get()));
//更新時間
lastTime += (now - lastTime) / 1000 * 1000;
//桶中還有令牌就放行
if (tokenNum.get() > 0) {
tokenNum.decrementAndGet();
return true;
} else {
return false;
}
}
//測試
public static void main(String[] args) {
//執行緒池，用於多執行緒模擬測試
ExecutorService pool = Executors.newFixedThreadPool(10);
// 被限制的次數
AtomicInteger limited = new AtomicInteger(0);
// 執行緒數
final int threads = 2;
// 每條執行緒的執行輪數
final int turns = 20;
// 同步器
CountDownLatch countDownLatch = new CountDownLatch(threads);
long start = System.currentTimeMillis();
for (int i = 0; i < threads; i++) {
pool.submit(() ->
{
try {
for (int j = 0; j < turns; j++) {
boolean flag = tryAcquire();
if (!flag) {
// 被限制的次數累積
limited.getAndIncrement();
}
Thread.sleep(200);
}
} catch (Exception e) {
e.printStackTrace();
}
//等待所有執行緒結束
countDownLatch.countDown();
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
float time = (System.currentTimeMillis() - start) / 1000F;
//輸出統計結果
System.out.println("限制的次數為：" + limited.get() +
",通過的次數為：" + (threads * turns - limited.get()));
System.out.println("限制的比例為：" + (float) limited.get() / (float) (threads * turns));
System.out.println("執行的時長為：" + time + "s");
}
}
令牌桶的好處：
令牌桶的好處之一就是可以方便地應對 突發出口流量（後端能力的提升）。
比如，可以改變令牌的發放速度，演演算法能按照新的傳送速率調大令牌的發放數量，使得出口突發流量能被處理。
到此這篇關於Java 常見的限流演演算法詳細分析並實現的文章就介紹到這了,更多相關Java 限流演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45