自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

一篇帶給你 Sentinel 和常用流控算法

作者：開(kāi)發(fā)者老鄭
開(kāi)發(fā) 前端 算法
本文主要講述常見(jiàn)的幾種限流算法：計(jì)數(shù)器算法、漏桶算法、令牌桶算法。然后結(jié)合我對(duì) Sentinel 1.8.0 的理解，給大家分享 Sentinel 在源碼中如何使用這些算法進(jìn)行流控判斷。

[[401361]]

本文主要講述常見(jiàn)的幾種限流算法：計(jì)數(shù)器算法、漏桶算法、令牌桶算法。然后結(jié)合我對(duì) Sentinel 1.8.0 的理解，給大家分享 Sentinel 在源碼中如何使用這些算法進(jìn)行流控判斷。

計(jì)數(shù)器限流算法

我們可以直接通過(guò)一個(gè)計(jì)數(shù)器，限制每一秒鐘能夠接收的請(qǐng)求數(shù)。比如說(shuō) qps定為 1000，那么實(shí)現(xiàn)思路就是從第一個(gè)請(qǐng)求進(jìn)來(lái)開(kāi)始計(jì)時(shí)，在接下去的 1s 內(nèi)，每來(lái)一個(gè)請(qǐng)求，就把計(jì)數(shù)加 1，如果累加的數(shù)字達(dá)到了 1000，那么后續(xù)的請(qǐng)求就會(huì)被全部拒絕。等到 1s 結(jié)束后，把計(jì)數(shù)恢復(fù)成 0 ，重新開(kāi)始計(jì)數(shù)。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單

缺點(diǎn)：如果1s 內(nèi)的前半秒，已經(jīng)通過(guò)了 1000 個(gè)請(qǐng)求，那后面的半秒只能請(qǐng)求拒絕，我們把這種現(xiàn)象稱(chēng)為“突刺現(xiàn)象”。

實(shí)現(xiàn)代碼案例：

  1. public class Counter { 
  2.     public long timeStamp = getNowTime(); 
  3.     public int reqCount = 0; 
  4.     public final int limit = 100; // 時(shí)間窗口內(nèi)最大請(qǐng)求數(shù) 
  5.     public final long interval = 1000; // 時(shí)間窗口ms 
  6.  
  7.     public boolean limit() { 
  8.         long now = getNowTime(); 
  9.         if (now < timeStamp + interval) { 
  10.             // 在時(shí)間窗口內(nèi) 
  11.             reqCount++; 
  12.             // 判斷當(dāng)前時(shí)間窗口內(nèi)是否超過(guò)最大請(qǐng)求控制數(shù) 
  13.             return reqCount <= limit; 
  14.         } else { 
  15.             timeStamp = now; 
  16.             // 超時(shí)后重置 
  17.             reqCount = 1; 
  18.             return true; 
  19.         } 
  20.     } 
  21.  
  22.     public long getNowTime() { 
  23.         return System.currentTimeMillis(); 
  24.     } 
  25. } 

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

滑動(dòng)窗口，又稱(chēng) Rolling Window。為了解決計(jì)數(shù)器算法的缺陷，我們引入了滑動(dòng)窗口算法。下面這張圖，很好地解釋了滑動(dòng)窗口算法：

在上圖中，整個(gè)紅色的矩形框表示一個(gè)時(shí)間窗口，在我們的例子中，一個(gè)時(shí)間窗口就是一分鐘。然后我們將時(shí)間窗口進(jìn)行劃分，比如圖中，我們就將滑動(dòng)窗口 劃成了6格，所以每格代表的是10秒鐘。每過(guò)10秒鐘，我們的時(shí)間窗口就會(huì)往右滑動(dòng)一格。每一個(gè)格子都有自己獨(dú)立的計(jì)數(shù)器counter，比如當(dāng)一個(gè)請(qǐng)求 在0:35秒的時(shí)候到達(dá)，那么0:30~0:39對(duì)應(yīng)的counter就會(huì)加1。

那么滑動(dòng)窗口怎么解決剛才的臨界問(wèn)題的呢?我們可以看上圖，0:59到達(dá)的100個(gè)請(qǐng)求會(huì)落在灰色的格子中，而1:00到達(dá)的請(qǐng)求會(huì)落在橘黃色的格子中。當(dāng)時(shí)間到達(dá)1:00時(shí)，我們的窗口會(huì)往右移動(dòng)一格，那么此時(shí)時(shí)間窗口內(nèi)的總請(qǐng)求數(shù)量一共是200個(gè)，超過(guò)了限定的100個(gè)，所以此時(shí)能夠檢測(cè)出來(lái)觸發(fā)了限流。

我再來(lái)回顧一下剛才的計(jì)數(shù)器算法，我們可以發(fā)現(xiàn)，計(jì)數(shù)器算法其實(shí)就是滑動(dòng)窗口算法。只是它沒(méi)有對(duì)時(shí)間窗口做進(jìn)一步地劃分，所以只有1格。

由此可見(jiàn)，當(dāng)滑動(dòng)窗口的格子劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會(huì)越精確。

實(shí)現(xiàn)代碼案例：

  1. public class SlideWindow { 
  2.  
  3.     /** 隊(duì)列id和隊(duì)列的映射關(guān)系，隊(duì)列里面存儲(chǔ)的是每一次通過(guò)時(shí)候的時(shí)間戳，這樣可以使得程序里有多個(gè)限流隊(duì)列 */ 
  4.     private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>(); 
  5.  
  6.     private SlideWindow() {} 
  7.  
  8.     public static void main(String[] args) throws InterruptedException { 
  9.         while (true) { 
  10.             // 任意10秒內(nèi)，只允許2次通過(guò) 
  11.             System.out.println(LocalTime.now().toString() + SlideWindow.isGo("ListId", 2, 10000L)); 
  12.             // 睡眠0-10秒 
  13.             Thread.sleep(1000 * new Random().nextInt(10)); 
  14.         } 
  15.     } 
  16.  
  17.     /** 
  18.      * 滑動(dòng)時(shí)間窗口限流算法 
  19.      * 在指定時(shí)間窗口，指定限制次數(shù)內(nèi)，是否允許通過(guò) 
  20.      * 
  21.      * @param listId     隊(duì)列id 
  22.      * @param count      限制次數(shù) 
  23.      * @param timeWindow 時(shí)間窗口大小 
  24.      * @return 是否允許通過(guò) 
  25.      */ 
  26.     public static synchronized boolean isGo(String listId, int count, long timeWindow) { 
  27.         // 獲取當(dāng)前時(shí)間 
  28.         long nowTime = System.currentTimeMillis(); 
  29.         // 根據(jù)隊(duì)列id，取出對(duì)應(yīng)的限流隊(duì)列，若沒(méi)有則創(chuàng)建 
  30.         List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>()); 
  31.         // 如果隊(duì)列還沒(méi)滿，則允許通過(guò)，并添加當(dāng)前時(shí)間戳到隊(duì)列開(kāi)始位置 
  32.         if (list.size() < count) { 
  33.             list.add(0, nowTime); 
  34.             return true; 
  35.         } 
  36.  
  37.         // 隊(duì)列已滿（達(dá)到限制次數(shù)），則獲取隊(duì)列中最早添加的時(shí)間戳 
  38.         Long farTime = list.get(count - 1); 
  39.         // 用當(dāng)前時(shí)間戳 減去 最早添加的時(shí)間戳 
  40.         if (nowTime - farTime <= timeWindow) { 
  41.             // 若結(jié)果小于等于timeWindow，則說(shuō)明在timeWindow內(nèi)，通過(guò)的次數(shù)大于count 
  42.             // 不允許通過(guò) 
  43.             return false; 
  44.         } else { 
  45.             // 若結(jié)果大于timeWindow，則說(shuō)明在timeWindow內(nèi)，通過(guò)的次數(shù)小于等于count 
  46.             // 允許通過(guò)，并刪除最早添加的時(shí)間戳，將當(dāng)前時(shí)間添加到隊(duì)列開(kāi)始位置 
  47.             list.remove(count - 1); 
  48.             list.add(0, nowTime); 
  49.             return true; 
  50.         } 
  51.     } 
  52.  
  53. } 

在 Sentinel 中 通過(guò) LeapArray 結(jié)構(gòu)來(lái)實(shí)現(xiàn)時(shí)間窗算法, 它的核心代碼如下(只列舉獲取時(shí)間窗方法)：

  1. /** 
  2.      * 獲取當(dāng)前的時(shí)間窗 
  3.      * 
  4.      * Get bucket item at provided timestamp. 
  5.      * 
  6.      * @param timeMillis a valid timestamp in milliseconds 
  7.      * @return current bucket item at provided timestamp if the time is valid; null if time is invalid 
  8.      */ 
  9. public WindowWrap<T> currentWindow(long timeMillis) { 
  10.   if (timeMillis < 0) { 
  11.     return null; 
  12.   } 
  13.  
  14.   int idx = calculateTimeIdx(timeMillis); 
  15.   // Calculate current bucket start time. 
  16.   // 計(jì)算窗口的開(kāi)始時(shí)間，計(jì)算每個(gè)格子的開(kāi)始時(shí)間 
  17.   long windowStart = calculateWindowStart(timeMillis); 
  18.  
  19.   /* 
  20.          * Get bucket item at given time from the array. 
  21.          * 
  22.          * (1) Bucket is absent, then just create a new bucket and CAS update to circular array. 
  23.          * (2) Bucket is up-to-date, then just return the bucket. 
  24.          * (3) Bucket is deprecated, then reset current bucket and clean all deprecated buckets. 
  25.          */ 
  26.   while (true) { 
  27.     WindowWrap<T> old = array.get(idx); 
  28.     // 如果沒(méi)有窗格，創(chuàng)建窗格 
  29.     if (old == null) { 
  30.       /* 
  31.                  *     B0       B1      B2    NULL      B4 
  32.                  * ||_______|_______|_______|_______|_______||___ 
  33.                  * 200     400     600     800     1000    1200  timestamp 
  34.                  *                             ^ 
  35.                  *                          time=888 
  36.                  *            bucket is empty, so create new and update 
  37.                  * 
  38.                  * If the old bucket is absent, then we create a new bucket at {@code windowStart}, 
  39.                  * then try to update circular array via a CAS operation. Only one thread can 
  40.                  * succeed to update, while other threads yield its time slice. 
  41.                  */ 
  42.       WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); 
  43.       if (array.compareAndSet(idx, null, window)) { 
  44.         // Successfully updated, return the created bucket. 
  45.         return window; 
  46.       } else { 
  47.         // Contention failed, the thread will yield its time slice to wait for bucket available. 
  48.         Thread.yield(); 
  49.       } 
  50.       // 當(dāng)前窗格存在，返回歷史窗格 
  51.     } else if (windowStart == old.windowStart()) { 
  52.       /* 
  53.                  *     B0       B1      B2     B3      B4 
  54.                  * ||_______|_______|_______|_______|_______||___ 
  55.                  * 200     400     600     800     1000    1200  timestamp 
  56.                  *                             ^ 
  57.                  *                          time=888 
  58.                  *            startTime of Bucket 3: 800, so it's up-to-date 
  59.                  * 
  60.                  * If current {@code windowStart} is equal to the start timestamp of old bucket, 
  61.                  * that means the time is within the bucket, so directly return the bucket. 
  62.                  */ 
  63.       return old; 
  64.       // 
  65.     } else if (windowStart > old.windowStart()) { 
  66.       /* 
  67.                  *   (old) 
  68.                  *             B0       B1      B2    NULL      B4 
  69.                  * |_______||_______|_______|_______|_______|_______||___ 
  70.                  * ...    1200     1400    1600    1800    2000    2200  timestamp 
  71.                  *                              ^ 
  72.                  *                           time=1676 
  73.                  *          startTime of Bucket 2: 400, deprecated, should be reset 
  74.                  * 
  75.                  * If the start timestamp of old bucket is behind provided time, that means 
  76.                  * the bucket is deprecated. We have to reset the bucket to current {@code windowStart}. 
  77.                  * Note that the reset and clean-up operations are hard to be atomic, 
  78.                  * so we need a update lock to guarantee the correctness of bucket update. 
  79.                  * 
  80.                  * The update lock is conditional (tiny scope) and will take effect only when 
  81.                  * bucket is deprecated, so in most cases it won't lead to performance loss. 
  82.                  */ 
  83.       if (updateLock.tryLock()) { 
  84.         try { 
  85.           // Successfully get the update lock, now we reset the bucket. 
  86.           // 清空所有的窗格數(shù)據(jù) 
  87.           return resetWindowTo(old, windowStart); 
  88.         } finally { 
  89.           updateLock.unlock(); 
  90.         } 
  91.       } else { 
  92.         // Contention failed, the thread will yield its time slice to wait for bucket available. 
  93.         Thread.yield(); 
  94.       } 
  95.       // 如果時(shí)鐘回?fù)?，重新?chuàng)建時(shí)間格 
  96.     } else if (windowStart < old.windowStart()) { 
  97.       // Should not go through here, as the provided time is already behind. 
  98.       return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); 
  99.     } 
  100.   } 
  101. } 

漏桶算法

漏桶算法(Leaky Bucket)是網(wǎng)絡(luò)世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)時(shí)經(jīng)常使用的一種算法，它的主要目的是控制數(shù)據(jù)注入到網(wǎng)絡(luò)的速率，平滑網(wǎng)絡(luò)上的突發(fā)流量。漏桶算法提供了一種機(jī)制，通過(guò)它，突發(fā)流量可以被整形以便為網(wǎng)絡(luò)提供一個(gè)穩(wěn)定的流量, 執(zhí)行過(guò)程如下圖所示。

實(shí)現(xiàn)代碼案例：

  1. public class LeakyBucket { 
  2.   public long timeStamp = System.currentTimeMillis();  // 當(dāng)前時(shí)間 
  3.   public long capacity; // 桶的容量 
  4.   public long rate; // 水漏出的速度 
  5.   public long water; // 當(dāng)前水量(當(dāng)前累積請(qǐng)求數(shù)) 
  6.  
  7.   public boolean grant() { 
  8.     long now = System.currentTimeMillis(); 
  9.     // 先執(zhí)行漏水，計(jì)算剩余水量 
  10.     water = Math.max(0, water - (now - timeStamp) * rate);  
  11.  
  12.     timeStamp = now; 
  13.     if ((water + 1) < capacity) { 
  14.       // 嘗試加水,并且水還未滿 
  15.       water += 1; 
  16.       return true; 
  17.     } else { 
  18.       // 水滿，拒絕加水 
  19.       return false; 
  20.     } 
  21.   } 
  22. } 

說(shuō)明：

(1)未滿加水：通過(guò)代碼 water +=1進(jìn)行不停加水的動(dòng)作。

(2)漏水：通過(guò)時(shí)間差來(lái)計(jì)算漏水量。

(3)剩余水量：總水量-漏水量。

在 Sentine 中RateLimiterController 實(shí)現(xiàn)了了漏桶算法 , 核心代碼如下

  1. @Override 
  2. public boolean canPass(Node node, int acquireCount, boolean prioritized) { 
  3.   // Pass when acquire count is less or equal than 0. 
  4.   if (acquireCount <= 0) { 
  5.     return true; 
  6.   } 
  7.   // Reject when count is less or equal than 0. 
  8.   // Otherwise,the costTime will be max of long and waitTime will overflow in some cases. 
  9.   if (count <= 0) { 
  10.     return false; 
  11.   } 
  12.  
  13.   long currentTime = TimeUtil.currentTimeMillis(); 
  14.   // Calculate the interval between every two requests. 
  15.   // 計(jì)算時(shí)間間隔 
  16.   long costTime = Math.round(1.0 * (acquireCount) / count * 1000); 
  17.  
  18.   // Expected pass time of this request. 
  19.   // 期望的執(zhí)行時(shí)間 
  20.   long expectedTime = costTime + latestPassedTime.get(); 
  21.  
  22.   // 當(dāng)前時(shí)間 > 期望時(shí)間 
  23.   if (expectedTime <= currentTime) { 
  24.     // Contention may exist here, but it's okay. 
  25.     // 可以通過(guò)，并且設(shè)置最后通過(guò)時(shí)間 
  26.     latestPassedTime.set(currentTime); 
  27.     return true; 
  28.   } else { 
  29.     // Calculate the time to wait. 
  30.     // 等待時(shí)間 = 期望時(shí)間 - 最后時(shí)間 - 當(dāng)前時(shí)間 
  31.     long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis(); 
  32.     // 等待時(shí)間 > 最大排隊(duì)時(shí)間 
  33.     if (waitTime > maxQueueingTimeMs) { 
  34.       return false; 
  35.     } else { 
  36.       // 上次時(shí)間 + 間隔時(shí)間 
  37.       long oldTime = latestPassedTime.addAndGet(costTime); 
  38.       try { 
  39.         // 等待時(shí)間 
  40.         waitTime = oldTime - TimeUtil.currentTimeMillis(); 
  41.         // 等待時(shí)間 > 最大排隊(duì)時(shí)間 
  42.         if (waitTime > maxQueueingTimeMs) { 
  43.           latestPassedTime.addAndGet(-costTime); 
  44.           return false; 
  45.         } 
  46.         // in race condition waitTime may <= 0 
  47.         // 休眠等待 
  48.         if (waitTime > 0) { 
  49.           Thread.sleep(waitTime); 
  50.         } 
  51.         // 等待完了，就放行 
  52.         return true; 
  53.       } catch (InterruptedException e) { 
  54.       } 
  55.     } 
  56.   } 
  57.   return false; 
  58. } 

令牌桶算法

令牌桶算法是網(wǎng)絡(luò)流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一種算法。典型情況下，令牌桶算法用來(lái)控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。如下圖所示：

簡(jiǎn)單的說(shuō)就是，一邊請(qǐng)求時(shí)會(huì)消耗桶內(nèi)的令牌，另一邊會(huì)以固定速率往桶內(nèi)放令牌。當(dāng)消耗的請(qǐng)求大于放入的速率時(shí)，進(jìn)行相應(yīng)的措施，比如等待，或者拒絕等。

實(shí)現(xiàn)代碼案例：

  1. public class TokenBucket { 
  2.   public long timeStamp = System.currentTimeMillis();  // 當(dāng)前時(shí)間 
  3.   public long capacity; // 桶的容量 
  4.   public long rate; // 令牌放入速度 
  5.   public long tokens; // 當(dāng)前令牌數(shù)量 
  6.  
  7.   public boolean grant() { 
  8.     long now = System.currentTimeMillis(); 
  9.     // 先添加令牌 
  10.     tokens = Math.min(capacity, tokens + (now - timeStamp) * rate); 
  11.     timeStamp = now; 
  12.     if (tokens < 1) { 
  13.       // 若不到1個(gè)令牌,則拒絕 
  14.       return false; 
  15.     } else { 
  16.       // 還有令牌，領(lǐng)取令牌 
  17.       tokens -= 1; 
  18.       return true; 
  19.     } 
  20.   } 
  21. } 

Sentinel 在 WarmUpController 中運(yùn)用到了令牌桶算法，在這里可以實(shí)現(xiàn)對(duì)系統(tǒng)的預(yù)熱，設(shè)定預(yù)熱時(shí)間和水位線，對(duì)于預(yù)熱期間多余的請(qǐng)求直接拒絕掉。

  1. public boolean canPass(Node node, int acquireCount, boolean prioritized) { 
  2.   long passQps = (long) node.passQps(); 
  3.  
  4.   long previousQps = (long) node.previousPassQps(); 
  5.   syncToken(previousQps); 
  6.  
  7.   // 開(kāi)始計(jì)算它的斜率 
  8.   // 如果進(jìn)入了警戒線，開(kāi)始調(diào)整他的qps 
  9.   long restToken = storedTokens.get(); 
  10.   if (restToken >= warningToken) { 
  11.     long aboveToken = restToken - warningToken; 
  12.     // 消耗的速度要比warning快，但是要比慢 
  13.     // current interval = restToken*slope+1/count 
  14.     double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); 
  15.     if (passQps + acquireCount <= warningQps) { 
  16.       return true; 
  17.     } 
  18.   } else { 
  19.     if (passQps + acquireCount <= count) { 
  20.       return true; 
  21.     } 
  22.   } 
  23.  
  24.   return false; 
  25. } 

限流算法總結(jié)

計(jì)數(shù)器 VS 時(shí)間窗

時(shí)間窗算法的本質(zhì)也是通過(guò)計(jì)數(shù)器算法實(shí)現(xiàn)的。

時(shí)間窗算法格子劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會(huì)越精確，但是也會(huì)占用更多的內(nèi)存存儲(chǔ)。

漏桶 VS 令牌桶

漏桶算法和令牌桶算法本質(zhì)上是為了做流量整形或速率限制，避免系統(tǒng)因?yàn)榇罅髁慷淮虮?，但是兩者的核心差異在于限流的方向是相反?/p>

漏桶：限制的是流量的流出速率，是相對(duì)固定的。

令牌桶 ：限制的是流量的平均流入速率，并且允許一定程度的突然性流量，最大速率為桶的容量和生成token的速率。

在某些場(chǎng)景中，漏桶算法并不能有效的使用網(wǎng)絡(luò)資源，因?yàn)槁┩暗穆┏鏊俾适窍鄬?duì)固定的，所以在網(wǎng)絡(luò)情況比較好并且沒(méi)有擁塞的狀態(tài)下，漏桶依然是會(huì)有限制的，并不能放開(kāi)量，因此并不能有效的利用網(wǎng)絡(luò)資源。而令牌桶算法則不同，其在限制平均速率的同時(shí)，支持一定程度的突發(fā)流量。

參考文檔

https://www.cnblogs.com/linjiqin/p/9707713.html

https://www.cnblogs.com/dijia478/p/13807826.html

 

責(zé)任編輯：姜華 來(lái)源： 運(yùn)維開(kāi)發(fā)故事
SentinelRedis 流控算法
相關(guān)推薦

2021-05-24 08:09:21

SentinelRedis 流控原理

2021-07-12 06:11:14

SkyWalking 儀表板UI篇

2023-03-09 07:47:56

BeanFactorSpring框架

2022-04-27 09:09:57

架構(gòu)師術(shù)語(yǔ)技術(shù)語(yǔ)言

2022-05-08 19:36:35

Web前端時(shí)間復(fù)雜度

2021-07-21 09:48:20

etcd-wal模塊解析數(shù)據(jù)庫(kù)

2021-06-21 14:36:46

Vite 前端工程化工具

2021-01-28 08:55:48

Elasticsear數(shù)據(jù)庫(kù)數(shù)據(jù)存儲(chǔ)

2021-04-01 10:51:55

MySQL鎖機(jī)制數(shù)據(jù)庫(kù)

2021-04-14 14:16:58

HttpHttp協(xié)議網(wǎng)絡(luò)協(xié)議

2022-04-29 14:38:49

class文件結(jié)構(gòu)分析

2023-03-29 07:45:58

VS編輯區(qū)編程工具

2021-03-12 09:21:31

MySQL數(shù)據(jù)庫(kù)邏輯架構(gòu)

2024-06-13 08:34:48

2022-03-22 09:09:17

HookReact前端

2022-02-17 08:53:38

ElasticSea集群部署

2021-04-08 11:00:56

CountDownLaJava進(jìn)階開(kāi)發(fā)

2022-11-24 06:58:44

Ansible

2021-04-14 07:55:45

Swift 協(xié)議Protocol

2022-02-25 15:50:05

OpenHarmonToggle組件鴻蒙
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)