一加Ace2 Pro官宣：普及16G內(nèi)存 引領(lǐng)24G
一加官方今天繼續(xù)為本月發(fā)布的新機(jī)一加Ace2 Pro帶來(lái)預(yù)熱，公布了內(nèi)存方面的信息。“淘汰 8GB ，12GB 起步，16GB 普及，24GB 引領(lǐng)，還有呢？#一加Ace2Pro#，2023 年 8 月，敬請(qǐng)期待。”同時(shí)
大家好,我是田螺。
最近一位朋友去拼夕夕面試,被問(wèn)了這么一道題:限流算法有哪些?用代碼實(shí)現(xiàn)令牌桶算法。跟星球好友討論了一波,發(fā)現(xiàn)大家都忘記得差不多了.所以田螺哥再整理一波，常見(jiàn)的四種限流算法,以及簡(jiǎn)單代碼實(shí)現(xiàn),相信大家看完,會(huì)茅塞頓開(kāi)的。
圖片
固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一種最簡(jiǎn)單的限流算法，其原理是在固定時(shí)間窗口(單位時(shí)間)內(nèi)限制請(qǐng)求的數(shù)量。該算法將時(shí)間分成固定的窗口，并在每個(gè)窗口內(nèi)限制請(qǐng)求的數(shù)量。具體來(lái)說(shuō)，算法將請(qǐng)求按照時(shí)間順序放入時(shí)間窗口中，并計(jì)算該時(shí)間窗口內(nèi)的請(qǐng)求數(shù)量，如果請(qǐng)求數(shù)量超出了限制，則拒絕該請(qǐng)求。
假設(shè)單位時(shí)間(固定時(shí)間窗口)是1秒，限流閥值為3。在單位時(shí)間1秒內(nèi)，每來(lái)一個(gè)請(qǐng)求,計(jì)數(shù)器就加1，如果計(jì)數(shù)器累加的次數(shù)超過(guò)限流閥值3，后續(xù)的請(qǐng)求全部拒絕。等到1s結(jié)束后，計(jì)數(shù)器清0，重新開(kāi)始計(jì)數(shù)。如下圖：
圖片
public static Integer counter = 0; //統(tǒng)計(jì)請(qǐng)求數(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)注公眾號(hào)：撿田螺的小男孩 * @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; //開(kāi)啟新的時(shí)間窗口 } if (counter < threshold) { // 小于閥值 counter++; //計(jì)數(shù)統(tǒng)計(jì)器加1 return true; } return false; }
圖片
滑動(dòng)窗口限流算法是一種常用的限流算法，用于控制系統(tǒng)對(duì)外提供服務(wù)的速率，防止系統(tǒng)被過(guò)多的請(qǐng)求壓垮。它將單位時(shí)間周期分為n個(gè)小周期，分別記錄每個(gè)小周期內(nèi)接口的訪問(wèn)次數(shù)，并且根據(jù)時(shí)間滑動(dòng)刪除過(guò)期的小周期。它可以解決固定窗口臨界值的問(wèn)題。
用一張圖解釋滑動(dòng)窗口算法，如下：
圖片
假設(shè)單位時(shí)間還是1s，滑動(dòng)窗口算法把它劃分為5個(gè)小周期，也就是滑動(dòng)窗口（單位時(shí)間）被劃分為5個(gè)小格子。每格表示0.2s。每過(guò)0.2s，時(shí)間窗口就會(huì)往右滑動(dòng)一格。然后呢，每個(gè)小周期，都有自己獨(dú)立的計(jì)數(shù)器，如果請(qǐng)求是0.83s到達(dá)的，0.8~1.0s對(duì)應(yīng)的計(jì)數(shù)器就會(huì)加1。
我們來(lái)看下，滑動(dòng)窗口,去解決固定窗口限流算法的臨界問(wèn)題，思想是怎樣
假設(shè)我們1s內(nèi)的限流閥值還是5個(gè)請(qǐng)求，0.8~1.0s內(nèi)（比如0.9s的時(shí)候）來(lái)了5個(gè)請(qǐng)求，落在黃色格子里。時(shí)間過(guò)了1.0s這個(gè)點(diǎn)之后，又來(lái)5個(gè)請(qǐng)求，落在紫色格子里。如果是固定窗口算法，是不會(huì)被限流的，但是滑動(dòng)窗口的話，每過(guò)一個(gè)小周期，它會(huì)右移一個(gè)小格。過(guò)了1.0s這個(gè)點(diǎn)后，會(huì)右移一小格，當(dāng)前的單位時(shí)間段是0.2~1.2s，這個(gè)區(qū)域的請(qǐng)求已經(jīng)超過(guò)限定的5了，已觸發(fā)限流啦，實(shí)際上，紫色格子的請(qǐng)求都被拒絕啦。
當(dāng)滑動(dòng)窗口的格子周期劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會(huì)越精確。
/** * 單位時(shí)間劃分的小周期（單位時(shí)間是1分鐘，10s一個(gè)小格子窗口，一共6個(gè)格子） */ private int SUB_CYCLE = 10; /** * 每分鐘限流請(qǐng)求數(shù) */ private int thresholdPerMin = 100; /** * 計(jì)數(shù)器, k-為當(dāng)前窗口的開(kāi)始時(shí)間值秒，value為當(dāng)前窗口的計(jì)數(shù) */ private final TreeMap<Long, Integer> counters = new TreeMap<>(); /** * 滑動(dòng)窗口時(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)前窗口總請(qǐng)求數(shù) //超過(guò)閥值限流 if (currentWindowNum >= thresholdPerMin) { return false; } //計(jì)數(shù)器+1 counters.get(currentWindowTime)++; return true; } /** * 統(tǒng)計(jì)當(dāng)前窗口的請(qǐng)求數(shù) */ private int countCurrentWindow(long currentWindowTime) { //計(jì)算窗口開(kāi)始位置 long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1); int count = 0; //遍歷存儲(chǔ)的計(jì)數(shù)器 Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Long, Integer> entry = iterator.next(); // 刪除無(wú)效過(guò)期的子窗口計(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ù)包像水滴一樣從桶的頂部流入桶中，并通過(guò)桶底的一個(gè)小孔以一定的速度流出，從而限制了數(shù)據(jù)包的流量。
漏桶限流算法的基本工作原理是：對(duì)于每個(gè)到來(lái)的數(shù)據(jù)包，都將其加入到漏桶中，并檢查漏桶中當(dāng)前的水量是否超過(guò)了漏桶的容量。如果超過(guò)了容量，就將多余的數(shù)據(jù)包丟棄。如果漏桶中還有水，就以一定的速率從桶底輸出數(shù)據(jù)包，保證輸出的速率不超過(guò)預(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)請(qǐng)求的數(shù)量。該算法維護(hù)一個(gè)固定容量的令牌桶，每秒鐘會(huì)向令牌桶中放入一定數(shù)量的令牌。當(dāng)有請(qǐng)求到來(lái)時(shí)，如果令牌桶中有足夠的令牌，則請(qǐng)求被允許通過(guò)并從令牌桶中消耗一個(gè)令牌，否則請(qǐng)求被拒絕。
/** * 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è)請(qǐng)求是否允許通過(guò)，該方法使用 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)：
總體來(lái)說(shuō)，令牌桶算法具有較高的穩(wěn)定性和精度，但實(shí)現(xiàn)相對(duì)復(fù)雜，適用于對(duì)穩(wěn)定性和精度要求較高的場(chǎng)景。
本文鏈接：http://m.www897cc.com/showinfo-26-75311-0.html面試必備：四種經(jīng)典限流算法講解
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)