隨著微服務(wù)的流行，服務(wù)之間的依賴性和調(diào)用關(guān)系變得越來越復(fù)雜，服務(wù)的穩(wěn)定性變得尤為重要。業(yè)務(wù)場(chǎng)景中經(jīng)常會(huì)涉及到瞬時(shí)流量沖擊，可能會(huì)導(dǎo)致請(qǐng)求響應(yīng)超時(shí)，甚至服務(wù)器被壓垮、宕機(jī)不可用。出于對(duì)系統(tǒng)本身和上下游服務(wù)的保護(hù)，我們通常會(huì)對(duì)請(qǐng)求進(jìn)行限流處理，快速拒絕超出配置上限的請(qǐng)求，保證系統(tǒng)或上下游服務(wù)系統(tǒng)的穩(wěn)定。合理策略能有效應(yīng)對(duì)流量沖擊，確保系統(tǒng)可用性和性能。本文詳細(xì)介紹了幾種限流算法，比較各個(gè)算法的優(yōu)缺點(diǎn)，給出了限流算法選型的一些建議，同時(shí)對(duì)業(yè)務(wù)上常用的分布式限流也提出一些解決方案。

一、背景

保護(hù)高并發(fā)服務(wù)穩(wěn)定主要有三把利器：緩存、降級(jí)和限流。

• 緩存：緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，通過在內(nèi)存中存儲(chǔ)經(jīng)常訪問的數(shù)據(jù)，可以減少對(duì)數(shù)據(jù)庫或者其他存儲(chǔ)系統(tǒng)的訪問，從而提高系統(tǒng)的響應(yīng)速度。緩存可以應(yīng)用在多個(gè)層次，例如瀏覽器緩存、CDN 緩存、反向代理緩存、應(yīng)用緩存等。
• 降級(jí)：降級(jí)是在系統(tǒng)壓力過大或者部分服務(wù)不可用的情況下，暫時(shí)關(guān)閉一些非核心的服務(wù)，以保證核心服務(wù)的正常運(yùn)行。降級(jí)可以在多個(gè)層次進(jìn)行，例如頁面降級(jí)、功能降級(jí)、服務(wù)降級(jí)等。
• 限流：限流是一種控制系統(tǒng)處理請(qǐng)求的速率的技術(shù)，以防止系統(tǒng)過載。限流可以通過多種算法實(shí)現(xiàn)，例如令牌桶算法、漏桶算法等。

這三把"利器"各有其特點(diǎn)，通常會(huì)結(jié)合使用，以達(dá)到最佳的效果。例如，可以通過緩存來減少數(shù)據(jù)庫的訪問，通過降級(jí)來應(yīng)對(duì)系統(tǒng)故障，通過限流來防止系統(tǒng)過載。在設(shè)計(jì)高并發(fā)系統(tǒng)時(shí)，需要根據(jù)系統(tǒng)的具體需求和特點(diǎn)，合理地使用這些技術(shù)。接下來本文會(huì)主要介紹一些業(yè)界常用的限流方法。

二、限流知識(shí)概述

限流是一種對(duì)請(qǐng)求或并發(fā)數(shù)進(jìn)行限制的關(guān)鍵技術(shù)手段，旨在保障系統(tǒng)的正常運(yùn)行。當(dāng)服務(wù)資源有限、處理能力有限時(shí)，限流可以對(duì)調(diào)用服務(wù)的上游請(qǐng)求進(jìn)行限制，以防止自身服務(wù)因資源耗盡而停止服務(wù)。

在限流中，有兩個(gè)重要的概念需要了解：

• 閾值：指在單位時(shí)間內(nèi)允許的請(qǐng)求量。例如，將 QPS（每秒請(qǐng)求數(shù)）限制為500，表示在1秒內(nèi)最多接受500次請(qǐng)求。通過設(shè)置合適的閾值，可以控制系統(tǒng)的負(fù)載，避免過多的請(qǐng)求導(dǎo)致系統(tǒng)崩潰或性能下降。
• 拒絕策略：用于處理超過閾值的請(qǐng)求的策略。常見的拒絕策略包括直接拒絕、排隊(duì)等待等。直接拒絕會(huì)立即拒絕超過閾值的請(qǐng)求，而排隊(duì)等待則將請(qǐng)求放入隊(duì)列中，按照一定的規(guī)則進(jìn)行處理。選擇合適的拒絕策略可以平衡系統(tǒng)的穩(wěn)定性和用戶體驗(yàn)。

通過合理設(shè)置閾值和選擇適當(dāng)?shù)木芙^策略，限流技術(shù)可以幫助系統(tǒng)應(yīng)對(duì)突發(fā)的請(qǐng)求量激增、惡意用戶訪問或請(qǐng)求頻率過高的情況，保障系統(tǒng)的穩(wěn)定性和可用性。限流方案根據(jù)限流范圍，可分為 單機(jī)限流和分布式限流 ；其中單機(jī)限流依據(jù)算法，又可分為 固定窗口、滑動(dòng)窗口、漏桶和令牌桶限流等常見四種 。本文將對(duì)上述限流方案進(jìn)行詳細(xì)介紹。

三、限流基本算法

1.固定窗口限流

(1) 算法介紹

固定窗口算法是一種簡(jiǎn)單直觀的限流算法，其原理是將時(shí)間劃分為固定大小的窗口，在每個(gè)窗口內(nèi)限制請(qǐng)求的數(shù)量或速率。具體實(shí)現(xiàn)時(shí)，可以使用一個(gè)計(jì)數(shù)器來記錄當(dāng)前窗口內(nèi)的請(qǐng)求數(shù)，并與預(yù)設(shè)的閾值進(jìn)行比較。固定窗口算法的原理如下：

• 將時(shí)間劃分固定大小窗口，例如每秒一個(gè)窗口。
• 在每個(gè)窗口內(nèi)，記錄請(qǐng)求的數(shù)量。
• 當(dāng)有請(qǐng)求到達(dá)時(shí)，將請(qǐng)求計(jì)數(shù)加一。
• 如果請(qǐng)求計(jì)數(shù)超過了預(yù)設(shè)的閾值（比如3個(gè)請(qǐng)求），拒絕該請(qǐng)求。
• 窗口結(jié)束后，重置請(qǐng)求計(jì)數(shù)。

(2) 代碼實(shí)現(xiàn)

type FixedWindowLimiter struct {
   windowSize  time.Duration // 窗口大小
   maxRequests int           // 最大請(qǐng)求數(shù)
   requests    int           // 當(dāng)前窗口內(nèi)的請(qǐng)求數(shù)
   lastReset   int64         // 上次窗口重置時(shí)間（秒級(jí)時(shí)間戳）
   resetMutex  sync.Mutex    // 重置鎖
}

func NewFixedWindowLimiter(windowSize time.Duration, maxRequests int) *FixedWindowLimiter {
   return &FixedWindowLimiter{
      windowSize:  windowSize,
      maxRequests: maxRequests,
      lastReset:   time.Now().Unix(),
   }
}

func (limiter *FixedWindowLimiter) AllowRequest() bool {
   limiter.resetMutex.Lock()
   defer limiter.resetMutex.Unlock()

   // 檢查是否需要重置窗口
   if time.Now().Unix()-limiter.lastReset >= int64(limiter.windowSize.Seconds()) {
      limiter.requests = 0
      limiter.lastReset = time.Now().Unix()
   }

   // 檢查請(qǐng)求數(shù)是否超過閾值
   if limiter.requests >= limiter.maxRequests {
      return false
   }

   limiter.requests++
   return true
}

func main() {
   limiter := NewFixedWindowLimiter(1*time.Second, 3) // 每秒最多允許3個(gè)請(qǐng)求
   for i := 0; i < 15; i++ {
      now := time.Now().Format("15:04:05")
      if limiter.AllowRequest() {
         fmt.Println(now + " 請(qǐng)求通過")
      } else {
         fmt.Println(now + " 請(qǐng)求被限流")
      }
      time.Sleep(100 * time.Millisecond)
   }
}

執(zhí)行結(jié)果：

(3) 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 實(shí)現(xiàn)簡(jiǎn)單：固定窗口算法的實(shí)現(xiàn)相對(duì)簡(jiǎn)單，易于理解和部署。
• 穩(wěn)定性較高：對(duì)于突發(fā)請(qǐng)求能夠較好地限制和控制，穩(wěn)定性較高。
• 易于實(shí)現(xiàn)速率控制：固定窗口算法可以很容易地限制請(qǐng)求的速率，例如每秒最多允許多少個(gè)請(qǐng)求。

缺點(diǎn)：

• 請(qǐng)求分布不均勻：固定窗口算法中，窗口內(nèi)的請(qǐng)求分布可能不均勻，導(dǎo)致某些窗口內(nèi)的請(qǐng)求數(shù)量超過閾值，而其他窗口內(nèi)的請(qǐng)求較少。
• 無法應(yīng)對(duì)突發(fā)流量：固定窗口算法的窗口大小是固定的，無法靈活地應(yīng)對(duì)突發(fā)流量。
• 請(qǐng)求的不公平性：窗口結(jié)束時(shí)的請(qǐng)求計(jì)數(shù)重置可能導(dǎo)致請(qǐng)求的不公平性。例如，在窗口結(jié)束前的最后一秒內(nèi)，請(qǐng)求計(jì)數(shù)已滿，而在窗口開始時(shí)的第一秒內(nèi)，請(qǐng)求計(jì)數(shù)為零。

固定窗口算法適用于對(duì)請(qǐng)求速率有明確要求且流量相對(duì)穩(wěn)定的場(chǎng)景，但對(duì)于突發(fā)流量和請(qǐng)求分布不均勻的情況，可能需要考慮其他更靈活的限流算法。

2. 滑動(dòng)窗口限流

(1) 算法介紹

上文已經(jīng)說明當(dāng)遇到時(shí)間窗口的臨界突變時(shí)，固定窗口算法可能無法靈活地應(yīng)對(duì)流量的變化。例如，在一個(gè)時(shí)間窗口結(jié)束時(shí)，如果突然出現(xiàn)大量請(qǐng)求，固定窗口算法可能會(huì)導(dǎo)致請(qǐng)求被拒絕，即使在下一個(gè)時(shí)間窗口內(nèi)的請(qǐng)求并不多。這種情況下，我們需要一種更靈活的算法來應(yīng)對(duì)突發(fā)流量和請(qǐng)求分布不均勻的情況—滑動(dòng)窗口算法。該算法是對(duì)固定窗口算法的一種改進(jìn)，它通過動(dòng)態(tài)調(diào)整窗口的大小來更好地適應(yīng)流量的變化。與固定窗口算法不同，滑動(dòng)窗口算法可以在遇到下一個(gè)時(shí)間窗口之前調(diào)整窗口的大小，以便更好地控制請(qǐng)求的速率。算法的原理如下：

• 窗口大小：確定一個(gè)固定的窗口大小，例如1秒。
• 請(qǐng)求計(jì)數(shù)：在窗口內(nèi)，每次有請(qǐng)求到達(dá)時(shí)，將請(qǐng)求計(jì)數(shù)加1。
• 限制條件：如果窗口內(nèi)的請(qǐng)求計(jì)數(shù)超過了設(shè)定的閾值，即超過了允許的最大請(qǐng)求數(shù)，就拒絕該請(qǐng)求。
• 窗口滑動(dòng)：隨著時(shí)間的推移，窗口會(huì)不斷滑動(dòng)，移除過期的請(qǐng)求計(jì)數(shù)，以保持窗口內(nèi)的請(qǐng)求數(shù)在限制范圍內(nèi)。

動(dòng)態(tài)調(diào)整：在滑動(dòng)窗口算法中，我們可以根據(jù)實(shí)際情況調(diào)整窗口的大小。當(dāng)遇到下一個(gè)時(shí)間窗口之前，我們可以根據(jù)當(dāng)前的流量情況來調(diào)整窗口的大小，以適應(yīng)流量的變化。

(2) 代碼實(shí)現(xiàn)

package main

import (
   "fmt"
   "sync"
   "time"
)

type SlidingWindowLimiter struct {
   windowSize   time.Duration // 窗口大小
   maxRequests  int           // 最大請(qǐng)求數(shù)
   requests     []time.Time   // 窗口內(nèi)的請(qǐng)求時(shí)間
   requestsLock sync.Mutex    // 請(qǐng)求鎖
}

func NewSlidingWindowLimiter(windowSize time.Duration, maxRequests int) *SlidingWindowLimiter {
   return &SlidingWindowLimiter{
      windowSize:  windowSize,
      maxRequests: maxRequests,
      requests:    make([]time.Time, 0),
   }
}

func (limiter *SlidingWindowLimiter) AllowRequest() bool {
   limiter.requestsLock.Lock()
   defer limiter.requestsLock.Unlock()

   // 移除過期的請(qǐng)求
   currentTime := time.Now()
   for len(limiter.requests) > 0 && currentTime.Sub(limiter.requests[0]) > limiter.windowSize {
      limiter.requests = limiter.requests[1:]
   }

   // 檢查請(qǐng)求數(shù)是否超過閾值
   if len(limiter.requests) >= limiter.maxRequests {
      return false
   }

   limiter.requests = append(limiter.requests, currentTime)
   return true
}

func main() {
   limiter := NewSlidingWindowLimiter(500*time.Millisecond, 2) // 每秒最多允許4個(gè)請(qǐng)求
   for i := 0; i < 15; i++ {
      now := time.Now().Format("15:04:05")
      if limiter.AllowRequest() {
         fmt.Println(now + " 請(qǐng)求通過")
      } else {
         fmt.Println(now + " 請(qǐng)求被限流")
      }
      time.Sleep(100 * time.Millisecond)
   }
}

執(zhí)行結(jié)果：

(3) 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 靈活性：滑動(dòng)窗口算法可以根據(jù)實(shí)際情況動(dòng)態(tài)調(diào)整窗口的大小，以適應(yīng)流量的變化。這種靈活性使得算法能夠更好地應(yīng)對(duì)突發(fā)流量和請(qǐng)求分布不均勻的情況。
• 實(shí)時(shí)性：由于滑動(dòng)窗口算法在每個(gè)時(shí)間窗口結(jié)束時(shí)都會(huì)進(jìn)行窗口滑動(dòng)，它能夠更及時(shí)地響應(yīng)流量的變化，提供更實(shí)時(shí)的限流效果。
• 精度：相比于固定窗口算法，滑動(dòng)窗口算法的顆粒度更小，可以提供更精確的限流控制。

缺點(diǎn)：

• 內(nèi)存消耗：滑動(dòng)窗口算法需要維護(hù)一個(gè)窗口內(nèi)的請(qǐng)求時(shí)間列表，隨著時(shí)間的推移，列表的長(zhǎng)度會(huì)增長(zhǎng)。這可能會(huì)導(dǎo)致較大的內(nèi)存消耗，特別是在窗口大小較大或請(qǐng)求頻率較高的情況下。
• 算法復(fù)雜性：相比于簡(jiǎn)單的固定窗口算法，滑動(dòng)窗口算法的實(shí)現(xiàn)較為復(fù)雜。它需要處理窗口滑動(dòng)、請(qǐng)求計(jì)數(shù)和過期請(qǐng)求的移除等邏輯，可能需要更多的代碼和計(jì)算開銷。

從代碼的角度可以發(fā)現(xiàn)，滑動(dòng)窗口算法實(shí)際上是顆粒度更小的固定窗口算法，它可以在一定程度上提高限流的精度和實(shí)時(shí)性，并不能從根本上解決請(qǐng)求分布不均勻的問題。算法受限于窗口的大小和時(shí)間間隔，特別是在極端情況下，如突發(fā)流量過大或請(qǐng)求分布極不均勻的情況下，仍然可能導(dǎo)致限流不準(zhǔn)確。因此，在實(shí)際應(yīng)用中，要采用更復(fù)雜的算法或策略來進(jìn)一步優(yōu)化限流效果。

3. 漏桶限流

(1) 算法介紹

盡管滑動(dòng)窗口算法可以提供一定的限流效果，但它仍然受限于窗口的大小和時(shí)間間隔。在某些情況下，突發(fā)流量可能會(huì)導(dǎo)致窗口內(nèi)的請(qǐng)求數(shù)超過限制。為了更好地平滑請(qǐng)求的流量，漏桶限流算法可以作為滑動(dòng)窗口算法的改進(jìn)。算法的原理很簡(jiǎn)單：它維護(hù)一個(gè)固定容量的漏桶，請(qǐng)求以不定的速率流入漏桶，而漏桶以固定的速率流出。如果請(qǐng)求到達(dá)時(shí)，漏桶已滿，則會(huì)觸發(fā)拒絕策略。可以從生產(chǎn)者-消費(fèi)者模式去理解這個(gè)算法，請(qǐng)求充當(dāng)生產(chǎn)者，每個(gè)請(qǐng)求就像一滴水，當(dāng)請(qǐng)求到達(dá)時(shí)，它被放入一個(gè)隊(duì)列（漏桶）中。而漏桶則充當(dāng)消費(fèi)者，以固定的速率從隊(duì)列中消費(fèi)請(qǐng)求，就像從桶底的孔洞中不斷漏出水滴。消費(fèi)的速率等于限流閾值，例如每秒處理2個(gè)請(qǐng)求，即500毫秒消費(fèi)一個(gè)請(qǐng)求。漏桶的容量就像隊(duì)列的容量，當(dāng)請(qǐng)求堆積超過指定容量時(shí)，會(huì)觸發(fā)拒絕策略，即新到達(dá)的請(qǐng)求將被丟棄或延遲處理。算法的實(shí)現(xiàn)如下：

• 漏桶容量：確定一個(gè)固定的漏桶容量，表示漏桶可以存儲(chǔ)的最大請(qǐng)求數(shù)。
• 漏桶速率：確定一個(gè)固定的漏桶速率，表示漏桶每秒可以處理的請(qǐng)求數(shù)。
• 請(qǐng)求處理：當(dāng)請(qǐng)求到達(dá)時(shí)，生產(chǎn)者將請(qǐng)求放入漏桶中。
• 漏桶流出：漏桶以固定的速率從漏桶中消費(fèi)請(qǐng)求，并處理這些請(qǐng)求。如果漏桶中有請(qǐng)求，則處理一個(gè)請(qǐng)求；如果漏桶為空，則不處理請(qǐng)求。
• 請(qǐng)求丟棄或延遲：如果漏桶已滿，即漏桶中的請(qǐng)求數(shù)達(dá)到了容量上限，新到達(dá)的請(qǐng)求將被丟棄或延遲處理。

(2) 代碼實(shí)現(xiàn)

package main

import (
   "fmt"
   "time"
)

type LeakyBucket struct {
   rate       float64 // 漏桶速率，單位請(qǐng)求數(shù)/秒
   capacity   int     // 漏桶容量，最多可存儲(chǔ)請(qǐng)求數(shù)
   water      int     // 當(dāng)前水量，表示當(dāng)前漏桶中的請(qǐng)求數(shù)
   lastLeakMs int64   // 上次漏水的時(shí)間戳，單位秒
}

func NewLeakyBucket(rate float64, capacity int) *LeakyBucket {
   return &LeakyBucket{
      rate:       rate,
      capacity:   capacity,
      water:      0,
      lastLeakMs: time.Now().Unix(),
   }
}

func (lb *LeakyBucket) Allow() bool {
   now := time.Now().Unix()
   elapsed := now - lb.lastLeakMs

   // 漏水，根據(jù)時(shí)間間隔計(jì)算漏掉的水量
   leakAmount := int(float64(elapsed) / 1000 * lb.rate)
   if leakAmount > 0 {
      if leakAmount > lb.water {
         lb.water = 0
      } else {
         lb.water -= leakAmount
      }
   }

   // 判斷當(dāng)前水量是否超過容量
   if lb.water > lb.capacity {
      lb.water-- // 如果超過容量，減去剛剛增加的水量
      return false
   }

   // 增加水量
   lb.water++

   lb.lastLeakMs = now
   return true
}

func main() {
   // 創(chuàng)建一個(gè)漏桶，速率為每秒處理3個(gè)請(qǐng)求，容量為4個(gè)請(qǐng)求
   leakyBucket := NewLeakyBucket(3, 4)

   // 模擬請(qǐng)求
   for i := 1; i <= 15; i++ {
      now := time.Now().Format("15:04:05")
      if leakyBucket.Allow() {
         fmt.Printf(now+"  第 %d 個(gè)請(qǐng)求通過\n", i)
      } else {
         fmt.Printf(now+"  第 %d 個(gè)請(qǐng)求被限流\n", i)
      }
      time.Sleep(200 * time.Millisecond) // 模擬請(qǐng)求間隔
   }
}

執(zhí)行結(jié)果：

(3) 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 平滑流量：漏桶算法可以平滑突發(fā)流量，使得輸出流量變得更加平穩(wěn)，避免了流量的突然增大對(duì)系統(tǒng)的沖擊。
• 簡(jiǎn)單易實(shí)現(xiàn)：漏桶算法的原理簡(jiǎn)單，實(shí)現(xiàn)起來也相對(duì)容易。
• 有效防止過載：通過控制流出的流量，漏桶算法可以有效地防止系統(tǒng)過載。

缺點(diǎn)：

• 對(duì)突發(fā)流量的處理不夠靈活：雖然漏桶算法可以平滑突發(fā)流量，但是在某些情況下，我們可能希望能夠快速處理突發(fā)流量。在這種情況下，漏桶算法可能就不夠靈活了。
• 無法動(dòng)態(tài)調(diào)整流量：漏桶算法的流出速率是固定的，無法根據(jù)系統(tǒng)的實(shí)際情況動(dòng)態(tài)調(diào)整。
• 可能會(huì)導(dǎo)致流量浪費(fèi)：如果輸入流量小于漏桶的流出速率，那么漏桶的流出速率就會(huì)被浪費(fèi)。
• 如果輸入流量持續(xù)大于漏桶的流出速率，那么漏桶會(huì)一直滿，新的請(qǐng)求會(huì)被丟棄，可能會(huì)導(dǎo)致服務(wù)質(zhì)量下降。

4. 令牌桶限流

(1) 算法介紹

令牌桶算法是實(shí)現(xiàn)限流是一種常見的思路，用于限制請(qǐng)求的速率。它可以確保系統(tǒng)在高負(fù)載情況下仍能提供穩(wěn)定的服務(wù)，并防止突發(fā)流量對(duì)系統(tǒng)造成過載。最為常用的 Google 的 Java 開發(fā)工具包 Guava 中的限流工具類 RateLimiter 就是令牌桶的一個(gè)實(shí)現(xiàn)。令牌桶算法基于一個(gè)令牌桶的概念，其中令牌以固定的速率產(chǎn)生，并放入桶中。每個(gè)令牌代表一個(gè)請(qǐng)求的許可。當(dāng)請(qǐng)求到達(dá)時(shí)，需要從令牌桶中獲取一個(gè)令牌才能通過。如果令牌桶中沒有足夠的令牌，則請(qǐng)求被限制或丟棄。 令牌桶算法的實(shí)現(xiàn)步驟如下：

• 初始化一個(gè)令牌桶，包括桶的容量和令牌產(chǎn)生的速率。
• 持續(xù)以固定速率產(chǎn)生令牌，并放入令牌桶中，直到桶滿為止。
• 當(dāng)請(qǐng)求到達(dá)時(shí)，嘗試從令牌桶中獲取一個(gè)令牌。
• 如果令牌桶中有足夠的令牌，則請(qǐng)求通過，并從令牌桶中移除一個(gè)令牌。
• 如果令牌桶中沒有足夠的令牌，則請(qǐng)求被限制或丟棄。

(2) 代碼實(shí)現(xiàn)

package main

import (
   "fmt"
   "sync"
   "time"
)

// TokenBucket 表示一個(gè)令牌桶。
type TokenBucket struct {
   rate       float64    // 令牌添加到桶中的速率。
   capacity   float64    // 桶的最大容量。
   tokens     float64    // 當(dāng)前桶中的令牌數(shù)量。
   lastUpdate time.Time  // 上次更新令牌數(shù)量的時(shí)間。
   mu         sync.Mutex // 互斥鎖，確保線程安全。
}

// NewTokenBucket 創(chuàng)建一個(gè)新的令牌桶，給定令牌添加速率和桶的容量。
func NewTokenBucket(rate float64, capacity float64) *TokenBucket {
   return &TokenBucket{
      rate:       rate,
      capacity:   capacity,
      tokens:     capacity, // 初始時(shí)，桶是滿的。
      lastUpdate: time.Now(),
   }
}

// Allow 檢查是否可以從桶中移除一個(gè)令牌。如果可以，它移除一個(gè)令牌并返回 true。
// 如果不可以，它返回 false。
func (tb *TokenBucket) Allow() bool {
   tb.mu.Lock()
   defer tb.mu.Unlock()

   // 根據(jù)經(jīng)過的時(shí)間計(jì)算要添加的令牌數(shù)量。
   now := time.Now()
   elapsed := now.Sub(tb.lastUpdate).Seconds() 
   tokensToAdd := elapsed * tb.rate            

   tb.tokens += tokensToAdd
   if tb.tokens > tb.capacity {
      tb.tokens = tb.capacity // 確保令牌數(shù)量不超過桶的容量。
   }

   if tb.tokens >= 1.0 {
      tb.tokens--
      tb.lastUpdate = now
      return true
   }

   return false
}

func main() {
   tokenBucket := NewTokenBucket(2.0, 3.0)

   for i := 1; i <= 10; i++ {
      now := time.Now().Format("15:04:05")
      if tokenBucket.Allow() {
         fmt.Printf(now+"  第 %d 個(gè)請(qǐng)求通過\n", i)
      } else { // 如果不能移除一個(gè)令牌，請(qǐng)求被拒絕。
         fmt.Printf(now+"  第 %d 個(gè)請(qǐng)求被限流\n", i)
      }
      time.Sleep(200 * time.Millisecond)
   }
}

執(zhí)行結(jié)果：

(3) 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 平滑流量：令牌桶算法可以平滑突發(fā)流量，使得突發(fā)流量在一段時(shí)間內(nèi)均勻地分布，避免了流量的突然高峰對(duì)系統(tǒng)的沖擊。
• 靈活性：令牌桶算法可以通過調(diào)整令牌生成速率和桶的大小來靈活地控制流量。
• 允許突發(fā)流量：由于令牌桶可以積累一定數(shù)量的令牌，因此在流量突然增大時(shí)，如果桶中有足夠的令牌，可以應(yīng)對(duì)這種突發(fā)流量。

缺點(diǎn)：

• 實(shí)現(xiàn)復(fù)雜：相比于其他一些限流算法（如漏桶算法），令牌桶算法的實(shí)現(xiàn)稍微復(fù)雜一些，需要維護(hù)令牌的生成和消耗。
• 需要精確的時(shí)間控制：令牌桶算法需要根據(jù)時(shí)間來生成令牌，因此需要有精確的時(shí)間控制。如果系統(tǒng)的時(shí)間控制不精確，可能會(huì)影響限流的效果。
• 可能會(huì)有資源浪費(fèi)：如果系統(tǒng)的流量持續(xù)低于令牌生成的速率，那么桶中的令牌可能會(huì)一直積累，造成資源的浪費(fèi)。

5. 四種基本算法的對(duì)比

四、分布式限流

單機(jī)限流指針對(duì)單一服務(wù)器的情況，通過限制單臺(tái)服務(wù)器在單位時(shí)間內(nèi)處理的請(qǐng)求數(shù)量，防止服務(wù)器過載。常見的限流算法上文已介紹，其優(yōu)點(diǎn)在于實(shí)現(xiàn)簡(jiǎn)單，效率高，效果明顯。隨著微服務(wù)架構(gòu)的普及，系統(tǒng)的服務(wù)通常會(huì)部署在多臺(tái)服務(wù)器上，此時(shí)就需要分布式限流來保證整個(gè)系統(tǒng)的穩(wěn)定性。接下本文會(huì)介紹幾種常見的分布式限流技術(shù)方案：

1. 基于中心化的限流方案

(1) 方案原理

通過一個(gè)中心化的限流器來控制所有服務(wù)器的請(qǐng)求。實(shí)現(xiàn)方式：

• 選擇一個(gè)中心化的組件，例如—Redis。
• 定義限流規(guī)則，例如：可以設(shè)置每秒鐘允許的最大請(qǐng)求數(shù)（QPS），并將這個(gè)值存儲(chǔ)在Redis中。
• 對(duì)于每個(gè)請(qǐng)求，服務(wù)器需要先向Redis請(qǐng)求令牌。
• 如果獲取到令牌，說明請(qǐng)求可以被處理；如果沒有獲取到令牌，說明請(qǐng)求被限流，可以返回一個(gè)錯(cuò)誤信息或者稍后重試。

(2) 代碼實(shí)現(xiàn)

package main

import (
   "context"
   "fmt"
   "go.uber.org/atomic"
   "sync"

   "git.code.oa.com/pcg-csd/trpc-ext/redis"
)

type RedisClient interface {
   Do(ctx context.Context, cmd string, args ...interface{}) (interface{}, error)
}

// Client 數(shù)據(jù)庫
type Client struct {
   client RedisClient // redis 操作
   script string      // lua腳本
}

// NewBucketClient 創(chuàng)建redis令牌桶
func NewBucketClient(redis RedisClient) *Client {
   helper := redis
   return &Client{
      client: helper,
      script: `
         -- 令牌桶限流腳本
         -- KEYS[1]: 桶的名稱
         -- ARGV[1]: 桶的容量
         -- ARGV[2]: 令牌產(chǎn)生速率
         
         local bucket = KEYS[1]
         local capacity = tonumber(ARGV[1])
         local tokenRate = tonumber(ARGV[2])
         
         local redisTime = redis.call('TIME')
         local now = tonumber(redisTime[1])
         
         local tokens, lastRefill = unpack(redis.call('hmget', bucket, 'tokens', 'lastRefill'))
         tokens = tonumber(tokens)
         lastRefill = tonumber(lastRefill)
         
         if not tokens or not lastRefill then
            tokens = capacity
            lastRefill = now
         else
            local intervalsSinceLast = (now - lastRefill) * tokenRate
            tokens = math.min(capacity, tokens + intervalsSinceLast)
         end
         
         if tokens < 1 then
            return 0
         else
            redis.call('hmset', bucket, 'tokens', tokens - 1, 'lastRefill', now)
            return 1
         end
      `,
   }
}

// 獲取令牌，獲取成功則立即返回true，否則返回false
func (c *Client) isAllowed(ctx context.Context, key string, capacity int64, tokenRate int64) (bool, error) {
   result, err := redis.Int(c.client.Do(ctx, "eval", c.script, 1, key, capacity, tokenRate))
   if err != nil {
      fmt.Println("Redis 執(zhí)行錯(cuò)誤:", err)
      return false, err
   }
   return result == 1, nil
}

// 調(diào)用檢測(cè)
func main() {
   c := NewBucketClient(redis.GetPoolByName("redis://127.0.0.1:6379"))
   gw := sync.WaitGroup{}
   gw.Add(120)
   count := atomic.Int64{}
   for i := 0; i < 120; i++ {
      go func(i int) {
         defer gw.Done()
         status, err := c.isAllowed(context.Background(), "test", 100, 10)
         if status {
            count.Add(1)
         }
         fmt.Printf("go %d status:%v error: %v\n", i, status, err)
      }(i)
   }
   gw.Wait()
   fmt.Printf("allow %d\n\n", count.Load())
}

執(zhí)行結(jié)果：

(3) 存在的問題

• 性能瓶頸：由于所有的請(qǐng)求都需要經(jīng)過Redis，因此Redis可能成為整個(gè)系統(tǒng)的性能瓶頸。為了解決這個(gè)問題，可以考慮使用Redis集群來提高性能，或者使用更高性能的硬件。
• 單點(diǎn)故障：如果Redis出現(xiàn)故障，整個(gè)系統(tǒng)的限流功能將受到影響。為了解決這個(gè)問題，可以考慮使用Redis的主從復(fù)制或者哨兵模式來實(shí)現(xiàn)高可用。
• 網(wǎng)絡(luò)帶寬：Redis是一個(gè)基于網(wǎng)絡(luò)通信的內(nèi)存數(shù)據(jù)庫，因此網(wǎng)絡(luò)帶寬是其性能的一個(gè)關(guān)鍵因素。如果網(wǎng)絡(luò)帶寬有限，可能會(huì)導(dǎo)致請(qǐng)求的傳輸速度變慢，從而影響Redis的性能。

redis官方性能測(cè)試圖

2. 基于負(fù)載均衡的分布式限流方案

(1) 方案原理

可以看到中心化限流方案的存在較高的單點(diǎn)故障風(fēng)險(xiǎn)，且?guī)捚款i比較嚴(yán)重。在這個(gè)基礎(chǔ)上本文結(jié)合本地緩存單機(jī)限流和負(fù)載均衡設(shè)計(jì)了一個(gè)新的分布式限流方案。具體方案如下：

• 使用負(fù)載均衡器或分布式服務(wù)發(fā)現(xiàn)（北極星即可做到），將請(qǐng)求均勻地分發(fā)到每個(gè)機(jī)器上。這確保了每個(gè)機(jī)器都能處理一部分請(qǐng)求。
• 在每個(gè)機(jī)器上維護(hù)本機(jī)的限流狀態(tài)，實(shí)現(xiàn)本地緩存單機(jī)限流的邏輯。使用令牌桶限流算法，在每個(gè)機(jī)器上獨(dú)立地進(jìn)行限流控制。每秒鐘處理的請(qǐng)求數(shù)、令牌桶的令牌數(shù)量等。根據(jù)本地限流狀態(tài)，對(duì)到達(dá)的請(qǐng)求進(jìn)行限流判斷。
• 準(zhǔn)備相應(yīng)的動(dòng)態(tài)調(diào)整方案，可以根據(jù)每個(gè)機(jī)器的實(shí)際負(fù)載情況，動(dòng)態(tài)地調(diào)整限流參數(shù)。例如，如果一個(gè)機(jī)器的CPU或內(nèi)存使用率過高，你可以降低這個(gè)機(jī)器的限流閾值，減少這個(gè)機(jī)器的請(qǐng)求處理量。反之，如果一個(gè)機(jī)器的資源使用率較低，提高這個(gè)機(jī)器的限流閾值，增加這個(gè)機(jī)器的請(qǐng)求處理量。

(2) 存在的問題

• 本地緩存：這個(gè)方案對(duì)本地緩存的要求較高，需要自己根據(jù)業(yè)務(wù)邏輯抉擇本地緩存的淘汰策略和緩存容量限制等風(fēng)險(xiǎn)點(diǎn)。
• 限流精度：本地緩存單機(jī)限流的精度受限于每個(gè)服務(wù)實(shí)例的資源和配置。這可能導(dǎo)致限流策略無法精確地適應(yīng)整個(gè)系統(tǒng)的流量變化，無法靈活地調(diào)整限流規(guī)則。
• 請(qǐng)求負(fù)載均衡器的單點(diǎn)故障。
• 動(dòng)態(tài)擴(kuò)縮容的適應(yīng)性：當(dāng)系統(tǒng)需要?jiǎng)討B(tài)擴(kuò)展或縮容時(shí)，該方案可能需要額外的配置和和調(diào)整，以確保新加入或移除的服務(wù)實(shí)例能夠正確地參與限流和請(qǐng)求均衡。

3. 基于分布式協(xié)調(diào)服務(wù)的限流

(1) 方案原理

使用ZooKeeper或者etcd等分布式協(xié)調(diào)服務(wù)來實(shí)現(xiàn)限流。每臺(tái)服務(wù)器都會(huì)向分布式協(xié)調(diào)服務(wù)申請(qǐng)令牌，只有獲取到令牌的請(qǐng)求才能被處理。基本方案：

• 初始化令牌桶：在ZooKeeper中創(chuàng)建一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的數(shù)據(jù)代表令牌的數(shù)量。初始時(shí)，將數(shù)據(jù)設(shè)置為令牌桶的容量。
• 申請(qǐng)令牌：當(dāng)一個(gè)請(qǐng)求到達(dá)時(shí)，服務(wù)器首先向ZooKeeper申請(qǐng)一個(gè)令牌。這可以通過獲取節(jié)點(diǎn)的分布式鎖，然后將節(jié)點(diǎn)的數(shù)據(jù)減1實(shí)現(xiàn)。如果操作成功，說明申請(qǐng)到了令牌，請(qǐng)求可以被處理；如果操作失敗，說明令牌已經(jīng)用完，請(qǐng)求需要被拒絕或者等待。
• 釋放令牌：當(dāng)一個(gè)請(qǐng)求處理完畢時(shí)，服務(wù)器需要向ZooKeeper釋放一個(gè)令牌。這可以通過獲取節(jié)點(diǎn)的分布式鎖，然后將節(jié)點(diǎn)的數(shù)據(jù)加1實(shí)現(xiàn)。
• 補(bǔ)充令牌：可以設(shè)置一個(gè)定時(shí)任務(wù)，定期向ZooKeeper中的令牌桶補(bǔ)充令牌。補(bǔ)充的頻率和數(shù)量可以根據(jù)系統(tǒng)的負(fù)載情況動(dòng)態(tài)調(diào)整。

(2) 存在的問題

這個(gè)方案的優(yōu)點(diǎn)是可以實(shí)現(xiàn)精確的全局限流，并且可以避免單點(diǎn)故障。但是，這個(gè)方案的缺點(diǎn)是實(shí)現(xiàn)復(fù)雜，且對(duì)ZooKeeper的性能有較高的要求。如果ZooKeeper無法處理大量的令牌申請(qǐng)和釋放操作，可能會(huì)成為系統(tǒng)的瓶頸。

五、總結(jié)

總之，沒有最好的方案，只有合適的方案。在選擇合適的限流方案時(shí)，我們需要考慮多種因素，包括系統(tǒng)的需求、現(xiàn)有的技術(shù)棧、系統(tǒng)的負(fù)載情況以及底層系統(tǒng)的性能等。理解每種方案的工作原理和特性，以便在實(shí)際應(yīng)用中做出最佳的選擇。

一個(gè)好的限流設(shè)計(jì)必須要考慮到業(yè)務(wù)的特性和需求，同時(shí)具備以下六點(diǎn)：

• 多級(jí)限流：除了主備復(fù)制的限流服務(wù)，可以考慮實(shí)現(xiàn)多級(jí)限流策略。例如，可以在應(yīng)用層、服務(wù)層和數(shù)據(jù)層都設(shè)置限流，這樣可以更好地防止系統(tǒng)過載。
• 動(dòng)態(tài)閾值調(diào)整：我們可以根據(jù)系統(tǒng)的實(shí)時(shí)負(fù)載情況動(dòng)態(tài)調(diào)整限流策略。例如，當(dāng)系統(tǒng)負(fù)載較低時(shí)，我們可以放寬限流策略；當(dāng)系統(tǒng)負(fù)載較高時(shí)，我們可以收緊限流策略。
• 靈活維度：限流策略應(yīng)該能夠根據(jù)不同的業(yè)務(wù)場(chǎng)景進(jìn)行調(diào)整。除了接口，設(shè)備，ip，賬戶id等維度外，我們還可以考慮更細(xì)粒度的限流。例如，我們可以根據(jù)用戶的行為模式進(jìn)行限流，這樣可以更好地防止惡意用戶的攻擊。
• 解耦性：限流應(yīng)該作為一個(gè)基礎(chǔ)服務(wù)，與具體的業(yè)務(wù)邏輯分離。這樣，當(dāng)業(yè)務(wù)邏輯發(fā)生變化時(shí)，不需要修改限流服務(wù)的代碼，只需要調(diào)整限流策略即可。
• 容錯(cuò)性：限流服務(wù)應(yīng)該具有高可用性，但是如果出現(xiàn)問題，業(yè)務(wù)應(yīng)該有備選方案（熔斷、降級(jí)）。這可能包括使用備用的限流服務(wù)，或者根據(jù)業(yè)務(wù)的敏感性決定是否放行請(qǐng)求。
• 監(jiān)控和報(bào)警：對(duì)限流策略應(yīng)進(jìn)行實(shí)時(shí)監(jiān)控，并設(shè)置報(bào)警機(jī)制。當(dāng)限流策略觸發(fā)時(shí)，可立即收到報(bào)警，以便我們可以及時(shí)地處理問題。

限流是保證系統(tǒng)穩(wěn)定和高效運(yùn)行的重要手段，但它并不是唯一的解決方案。我們還需要考慮其他的系統(tǒng)設(shè)計(jì)和優(yōu)化手段，例如負(fù)載均衡、緩存、異步處理等（面對(duì)爆量，擴(kuò)容永遠(yuǎn)是最好的方式，除了貴！）。這些手段相互配合，才能構(gòu)建出一個(gè)既能應(yīng)對(duì)高并發(fā)請(qǐng)求，又能保證服務(wù)質(zhì)量的系統(tǒng)。