紅魔電競平板評測：大屏幕硬實(shí)力
前言：三年的疫情因?yàn)橐暇W(wǎng)課的原因激活了平板市場，如今網(wǎng)課的時(shí)代已經(jīng)過去，大家的生活都恢復(fù)到了正軌，這也就意味著，真正考驗(yàn)平板電腦生存的環(huán)境來了。也就是面對著這種殘酷的
大家好,我是田螺。
最近一位朋友去拼夕夕面試,被問了這么一道題:限流算法有哪些?用代碼實(shí)現(xiàn)令牌桶算法。跟星球好友討論了一波,發(fā)現(xiàn)大家都忘記得差不多了.所以田螺哥再整理一波，常見的四種限流算法,以及簡單代碼實(shí)現(xiàn),相信大家看完,會茅塞頓開的。
圖片
固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一種最簡單的限流算法，其原理是在固定時(shí)間窗口(單位時(shí)間)內(nèi)限制請求的數(shù)量。該算法將時(shí)間分成固定的窗口，并在每個(gè)窗口內(nèi)限制請求的數(shù)量。具體來說，算法將請求按照時(shí)間順序放入時(shí)間窗口中，并計(jì)算該時(shí)間窗口內(nèi)的請求數(shù)量，如果請求數(shù)量超出了限制，則拒絕該請求。
假設(shè)單位時(shí)間(固定時(shí)間窗口)是1秒，限流閥值為3。在單位時(shí)間1秒內(nèi)，每來一個(gè)請求,計(jì)數(shù)器就加1，如果計(jì)數(shù)器累加的次數(shù)超過限流閥值3，后續(xù)的請求全部拒絕。等到1s結(jié)束后，計(jì)數(shù)器清0，重新開始計(jì)數(shù)。如下圖：
圖片
public static Integer counter = 0; //統(tǒng)計(jì)請求數(shù) public static long lastAcquireTime = 0L; public static final Long windowUnit = 1000L ; //假設(shè)固定時(shí)間窗口是1000ms public static final Integer threshold = 10; // 窗口閥值是10 /** * 固定窗口時(shí)間算法 * 關(guān)注公眾號：撿田螺的小男孩 * @return */ public synchronized boolean fixedWindowsTryAcquire() { long currentTime = System.currentTimeMillis(); //獲取系統(tǒng)當(dāng)前時(shí)間 if (currentTime - lastAcquireTime > windowUnit) { //檢查是否在時(shí)間窗口內(nèi) counter = 0; // 計(jì)數(shù)器清0 lastAcquireTime = currentTime; //開啟新的時(shí)間窗口 } if (counter < threshold) { // 小于閥值 counter++; //計(jì)數(shù)統(tǒng)計(jì)器加1 return true; } return false; }
圖片
滑動窗口限流算法是一種常用的限流算法，用于控制系統(tǒng)對外提供服務(wù)的速率，防止系統(tǒng)被過多的請求壓垮。它將單位時(shí)間周期分為n個(gè)小周期，分別記錄每個(gè)小周期內(nèi)接口的訪問次數(shù)，并且根據(jù)時(shí)間滑動刪除過期的小周期。它可以解決固定窗口臨界值的問題。
用一張圖解釋滑動窗口算法，如下：
圖片
假設(shè)單位時(shí)間還是1s，滑動窗口算法把它劃分為5個(gè)小周期，也就是滑動窗口（單位時(shí)間）被劃分為5個(gè)小格子。每格表示0.2s。每過0.2s，時(shí)間窗口就會往右滑動一格。然后呢，每個(gè)小周期，都有自己獨(dú)立的計(jì)數(shù)器，如果請求是0.83s到達(dá)的，0.8~1.0s對應(yīng)的計(jì)數(shù)器就會加1。
我們來看下，滑動窗口,去解決固定窗口限流算法的臨界問題，思想是怎樣
假設(shè)我們1s內(nèi)的限流閥值還是5個(gè)請求，0.8~1.0s內(nèi)（比如0.9s的時(shí)候）來了5個(gè)請求，落在黃色格子里。時(shí)間過了1.0s這個(gè)點(diǎn)之后，又來5個(gè)請求，落在紫色格子里。如果是固定窗口算法，是不會被限流的，但是滑動窗口的話，每過一個(gè)小周期，它會右移一個(gè)小格。過了1.0s這個(gè)點(diǎn)后，會右移一小格，當(dāng)前的單位時(shí)間段是0.2~1.2s，這個(gè)區(qū)域的請求已經(jīng)超過限定的5了，已觸發(fā)限流啦，實(shí)際上，紫色格子的請求都被拒絕啦。
當(dāng)滑動窗口的格子周期劃分的越多，那么滑動窗口的滾動就越平滑，限流的統(tǒng)計(jì)就會越精確。
/** * 單位時(shí)間劃分的小周期（單位時(shí)間是1分鐘，10s一個(gè)小格子窗口，一共6個(gè)格子） */ private int SUB_CYCLE = 10; /** * 每分鐘限流請求數(shù) */ private int thresholdPerMin = 100; /** * 計(jì)數(shù)器, k-為當(dāng)前窗口的開始時(shí)間值秒，value為當(dāng)前窗口的計(jì)數(shù) */ private final TreeMap<Long, Integer> counters = new TreeMap<>(); /** * 滑動窗口時(shí)間算法實(shí)現(xiàn) */ public synchronized boolean slidingWindowsTryAcquire() { long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //獲取當(dāng)前時(shí)間在哪個(gè)小周期窗口 int currentWindowNum = countCurrentWindow(currentWindowTime); //當(dāng)前窗口總請求數(shù) //超過閥值限流 if (currentWindowNum >= thresholdPerMin) { return false; } //計(jì)數(shù)器+1 counters.get(currentWindowTime)++; return true; } /** * 統(tǒng)計(jì)當(dāng)前窗口的請求數(shù) */ private int countCurrentWindow(long currentWindowTime) { //計(jì)算窗口開始位置 long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1); int count = 0; //遍歷存儲的計(jì)數(shù)器 Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Long, Integer> entry = iterator.next(); // 刪除無效過期的子窗口計(jì)數(shù)器 if (entry.getKey() < startTime) { iterator.remove(); } else { //累加當(dāng)前窗口的所有計(jì)數(shù)器之和 count =count + entry.getValue(); } } return count; }優(yōu)點(diǎn)：
缺點(diǎn)：
漏桶限流算法（Leaky Bucket Algorithm）是一種流量控制算法，用于控制流入網(wǎng)絡(luò)的數(shù)據(jù)速率，以防止網(wǎng)絡(luò)擁塞。它的思想是將數(shù)據(jù)包看作是水滴，漏桶看作是一個(gè)固定容量的水桶，數(shù)據(jù)包像水滴一樣從桶的頂部流入桶中，并通過桶底的一個(gè)小孔以一定的速度流出，從而限制了數(shù)據(jù)包的流量。
漏桶限流算法的基本工作原理是：對于每個(gè)到來的數(shù)據(jù)包，都將其加入到漏桶中，并檢查漏桶中當(dāng)前的水量是否超過了漏桶的容量。如果超過了容量，就將多余的數(shù)據(jù)包丟棄。如果漏桶中還有水，就以一定的速率從桶底輸出數(shù)據(jù)包，保證輸出的速率不超過預(yù)設(shè)的速率，從而達(dá)到限流的目的。
圖片
/** * LeakyBucket 類表示一個(gè)漏桶, * 包含了桶的容量和漏桶出水速率等參數(shù)， * 以及當(dāng)前桶中的水量和上次漏水時(shí)間戳等狀態(tài)。 */public class LeakyBucket { private final long capacity; // 桶的容量 private final long rate; // 漏桶出水速率 private long water; // 當(dāng)前桶中的水量 private long lastLeakTimestamp; // 上次漏水時(shí)間戳 public LeakyBucket(long capacity, long rate) { this.capacity = capacity; this.rate = rate; this.water = 0; this.lastLeakTimestamp = System.currentTimeMillis(); } /** * tryConsume() 方法用于嘗試向桶中放入一定量的水，如果桶中還有足夠的空間，則返回 true，否則返回 false。 * @param waterRequested * @return */ public synchronized boolean tryConsume(long waterRequested) { leak(); if (water + waterRequested <= capacity) { water += waterRequested; return true; } else { return false; } } /** * 。leak() 方法用于漏水，根據(jù)當(dāng)前時(shí)間和上次漏水時(shí)間戳計(jì)算出應(yīng)該漏出的水量，然后更新桶中的水量和漏水時(shí)間戳等狀態(tài)。 */ private void leak() { long now = System.currentTimeMillis(); long elapsedTime = now - lastLeakTimestamp; long leakedWater = elapsedTime * rate / 1000; if (leakedWater > 0) { water = Math.max(0, water - leakedWater); lastLeakTimestamp = now; } }}優(yōu)點(diǎn)
缺點(diǎn)
令牌桶算法是一種常用的限流算法，可以用于限制單位時(shí)間內(nèi)請求的數(shù)量。該算法維護(hù)一個(gè)固定容量的令牌桶，每秒鐘會向令牌桶中放入一定數(shù)量的令牌。當(dāng)有請求到來時(shí)，如果令牌桶中有足夠的令牌，則請求被允許通過并從令牌桶中消耗一個(gè)令牌，否則請求被拒絕。
/** * TokenBucket 類表示一個(gè)令牌桶 */public class TokenBucket { private final int capacity; // 令牌桶容量 private final int rate; // 令牌生成速率，單位：令牌/秒 private int tokens; // 當(dāng)前令牌數(shù)量 private long lastRefillTimestamp; // 上次令牌生成時(shí)間戳 /** * 構(gòu)造函數(shù)中傳入令牌桶的容量和令牌生成速率。 * @param capacity * @param rate */ public TokenBucket(int capacity, int rate) { this.capacity = capacity; this.rate = rate; this.tokens = capacity; this.lastRefillTimestamp = System.currentTimeMillis(); } /** * allowRequest() 方法表示一個(gè)請求是否允許通過，該方法使用 synchronized 關(guān)鍵字進(jìn)行同步，以保證線程安全。 * @return */ public synchronized boolean allowRequest() { refill(); if (tokens > 0) { tokens--; return true; } else { return false; } } /** * refill() 方法用于生成令牌，其中計(jì)算令牌數(shù)量的邏輯是按照令牌生成速率每秒鐘生成一定數(shù)量的令牌， * tokens 變量表示當(dāng)前令牌數(shù)量， * lastRefillTimestamp 變量表示上次令牌生成的時(shí)間戳。 */ private void refill() { long now = System.currentTimeMillis(); if (now > lastRefillTimestamp) { int generatedTokens = (int) ((now - lastRefillTimestamp) / 1000 * rate); tokens = Math.min(tokens + generatedTokens, capacity); lastRefillTimestamp = now; } }}優(yōu)點(diǎn)：
Guava的RateLimiter限流組件，就是基于令牌桶算法實(shí)現(xiàn)的。
缺點(diǎn)：
總體來說，令牌桶算法具有較高的穩(wěn)定性和精度，但實(shí)現(xiàn)相對復(fù)雜，適用于對穩(wěn)定性和精度要求較高的場景。
本文鏈接：http://www.www897cc.com/showinfo-26-75311-0.html面試必備：四種經(jīng)典限流算法講解
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： Vue2問題：分享一個(gè)通用多文件類型預(yù)覽庫
下一篇： 淺談鏈路聚合，你學(xué)會了嗎？
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號