限速器

限速器類型

• Leaky Bucket：漏桶算法(和令牌桶(token bucket)非常相似)是一種非常簡(jiǎn)單，使用隊(duì)列來(lái)進(jìn)行限流的算法。當(dāng)接收到一個(gè)請(qǐng)求時(shí)，會(huì)將其追加到隊(duì)列的末尾，系統(tǒng)會(huì)按照先進(jìn)先出的順序處理請(qǐng)求，一旦隊(duì)列滿，則會(huì)丟棄額外的請(qǐng)求。隊(duì)列中的請(qǐng)求數(shù)目受限于隊(duì)列的大小。

  這種方式可以緩解突發(fā)流量對(duì)系統(tǒng)的影響，缺點(diǎn)是在流量突發(fā)時(shí)，由于隊(duì)列中緩存了舊的請(qǐng)求，導(dǎo)致無(wú)法處理新的請(qǐng)求。而且也無(wú)法保證請(qǐng)求能夠在一定時(shí)間內(nèi)處理完畢。

  令牌桶不會(huì)緩存請(qǐng)求，它通過(guò)頒發(fā)令牌的方式來(lái)允許請(qǐng)求，因此它存在和漏桶算法一樣的問(wèn)題。

• Fixed Window：該系統(tǒng)使用n秒的窗口大小(通常使用人類友好的值，例如60或3600秒)來(lái)跟蹤固定窗口下的請(qǐng)求速率。每接收到一個(gè)請(qǐng)求都會(huì)增加計(jì)算器，當(dāng)計(jì)數(shù)器超過(guò)閾值后，則會(huì)丟棄請(qǐng)求。通常當(dāng)前時(shí)間戳的下限來(lái)定義定義窗口，如12:00:03(窗口長(zhǎng)度為60秒)將位于12:00:00的窗口中。

  該算法可以保證最新的請(qǐng)求不受舊請(qǐng)求的影響。但如果在窗口邊界出現(xiàn)突發(fā)流量，由于短時(shí)間內(nèi)產(chǎn)生的流量可能會(huì)同時(shí)被計(jì)入當(dāng)前和下一個(gè)窗口，因此可能會(huì)導(dǎo)致請(qǐng)求速率翻倍。如果有多個(gè)消費(fèi)者等待窗口重置，則在窗口重置后的一開(kāi)始會(huì)出現(xiàn)踩踏效應(yīng)。跟漏桶算法一樣，固定窗口算法是針對(duì)所有消費(fèi)者而非單個(gè)消費(fèi)者進(jìn)行限制的。

• Sliding Log：滑動(dòng)日志會(huì)跟蹤每個(gè)消費(fèi)者的請(qǐng)求對(duì)應(yīng)的時(shí)間戳日志。系統(tǒng)會(huì)將這些日志保存在按時(shí)間排序的哈希集或表中，并丟棄時(shí)間戳超過(guò)閾值的日志。當(dāng)接收到一個(gè)請(qǐng)求后，會(huì)通過(guò)計(jì)算日志的總數(shù)來(lái)決定請(qǐng)求速率。如果請(qǐng)求超過(guò)速率閾值，則暫停處理該請(qǐng)求。
  

  這種算法的優(yōu)點(diǎn)在于它不存在固定窗口中的邊界限制，因此在限速上更加精確。由于系統(tǒng)會(huì)跟蹤每個(gè)消費(fèi)者的滑動(dòng)日志，因此也不存在固定窗口算法中的踩踏效應(yīng)。

  但保存無(wú)限量的請(qǐng)求會(huì)帶來(lái)存儲(chǔ)成本，且該算法在接收到請(qǐng)求時(shí)都需要計(jì)算消費(fèi)者先前的請(qǐng)求總和(有可能需要跨服務(wù)器集群進(jìn)行運(yùn)算)，因此計(jì)算成本也很高。基于上述原因，該算法在處理突發(fā)流量或DDos攻擊等問(wèn)題上存在擴(kuò)展性問(wèn)題。

• Sliding Window：滑動(dòng)窗口算法結(jié)合了固定窗口算法中的低成本處理以及滑動(dòng)日志中對(duì)邊界條件的改進(jìn)。像固定窗口算法一樣，該算法會(huì)為每個(gè)固定窗口設(shè)置一個(gè)計(jì)數(shù)器，并根據(jù)當(dāng)前時(shí)間戳來(lái)考慮前一窗口中的請(qǐng)求速率的加權(quán)值，用來(lái)平滑突發(fā)流量。

  例如，假設(shè)有一個(gè)每分鐘允許100個(gè)事件的限速器，此時(shí)當(dāng)前時(shí)間到了75s點(diǎn)，那么內(nèi)部窗口如下：

此時(shí)限速器在15秒前開(kāi)始的當(dāng)前窗口期間(15s~75s)內(nèi)已經(jīng)允許了12個(gè)事件，而在前一個(gè)完整窗口期間允許了86個(gè)事件。滑動(dòng)窗口內(nèi)的計(jì)數(shù)近似值可以這樣計(jì)算：

count = 86 * ((60-15)/60) + 12
      = 86 * 0.75 + 12
      = 76.5 events

86 * ((60-15)/60)為與上一個(gè)窗口重疊的計(jì)數(shù)，12為當(dāng)前窗口的計(jì)數(shù)

由于每個(gè)關(guān)鍵點(diǎn)需要跟蹤的數(shù)據(jù)量相對(duì)較少，因此能夠在大型集群中進(jìn)行擴(kuò)展和分布。

推薦使用滑動(dòng)窗口算法，它在提供靈活擴(kuò)展性的同時(shí)，保證了算法的性能。此外它還避免了漏桶算法中的饑餓問(wèn)題以及固定窗口算法中的踩踏效應(yīng)。

分布式系統(tǒng)中的限速

可以采用*數(shù)據(jù)存儲(chǔ)(如redis或Cassandra)的方式來(lái)實(shí)現(xiàn)多節(jié)點(diǎn)集群的全局限速。*存儲(chǔ)會(huì)為每個(gè)窗口和消費(fèi)者收集請(qǐng)求次數(shù)。但這種方式會(huì)給請(qǐng)求帶來(lái)延遲，且存儲(chǔ)可能會(huì)存在競(jìng)爭(zhēng)。

在采用get-then-set(即獲取當(dāng)前的限速器計(jì)數(shù)，然后增加計(jì)數(shù)，最后將計(jì)數(shù)保存到數(shù)據(jù)庫(kù))模式時(shí)可能會(huì)產(chǎn)生競(jìng)爭(zhēng)，導(dǎo)致數(shù)據(jù)庫(kù)計(jì)數(shù)不一致。

解決該問(wèn)題的一種方式是使用鎖，但鎖會(huì)帶來(lái)嚴(yán)重的性能問(wèn)題。更好的方式是使用set-then-get模式，并依賴原子操作來(lái)提升性能。

性能優(yōu)化

即使是Redis這種快速存儲(chǔ)也會(huì)給每個(gè)請(qǐng)求帶來(lái)毫秒級(jí)的延遲。可以采用本地內(nèi)存檢查的方式來(lái)最小化延遲。

為了使用本地檢查，需要放寬速率檢查條件，并使用最終一致性模型。例如，每個(gè)節(jié)點(diǎn)都可以創(chuàng)建一個(gè)數(shù)據(jù)同步周期，用來(lái)與*數(shù)據(jù)存儲(chǔ)同步。每個(gè)節(jié)點(diǎn)周期性地將每個(gè)消費(fèi)者和窗口的計(jì)數(shù)器增量推送到數(shù)據(jù)庫(kù)，并原子方式更新數(shù)據(jù)庫(kù)值。然后，節(jié)點(diǎn)可以檢索更新后的值并更新其內(nèi)存版本。在集中→發(fā)散→再集中的周期中達(dá)到最終一致。

同步周期應(yīng)該是可配置的，當(dāng)在集群中的多個(gè)節(jié)點(diǎn)間分發(fā)流量時(shí)，較短的同步間隔會(huì)降低數(shù)據(jù)點(diǎn)的差異。而較長(zhǎng)的同步間隔會(huì)減少數(shù)據(jù)存儲(chǔ)的讀/寫(xiě)壓力，并減少每個(gè)節(jié)點(diǎn)獲取新同步值所帶來(lái)的開(kāi)銷。

Golang中的滑動(dòng)窗口

Golang的滑動(dòng)窗口實(shí)現(xiàn)比較好的實(shí)現(xiàn)有mennanov/limiters和RussellLuo/slidingwindow，個(gè)人更推薦后者。下面看下RussellLuo/slidingwindow的用法和實(shí)現(xiàn)。

簡(jiǎn)單用法

下面例子中，創(chuàng)建了一個(gè)每秒限制10個(gè)事件的限速器。lim.Allow()會(huì)增加當(dāng)前窗口的計(jì)數(shù)，當(dāng)計(jì)數(shù)達(dá)到閾值(10)，則會(huì)返回false。

package main

import (
	"fmt"
	sw "github.com/RussellLuo/slidingwindow"
	"time"
)

func main() {
	lim, _ := sw.NewLimiter(time.Second, 10, func() (sw.Window, sw.StopFunc) {
		return sw.NewLocalWindow()
	})

	for i := 1; i < 12; i++ {
		ok := lim.Allow()
		fmt.Printf("ok: %v\n", ok)
	}
}

對(duì)外接口如下：

• lim.SetLimit(newLimit int64)：設(shè)置窗口大小
• lim.Allow()：就是AllowN(time.Now(), 1)
• lim.AllowN(now time.Time, n int64)：判斷當(dāng)前窗口是否允許n個(gè)事件，如果允許，則當(dāng)前窗口計(jì)數(shù)器+n，并返回true，反之則返回false
• lim.Limit()：獲取限速值
• lim.Size()：獲取窗口大小

實(shí)現(xiàn)

首先初始化一個(gè)限速器，NewLimiter的函數(shù)簽名如下：

func NewLimiter(size time.Duration, limit int64, newWindow NewWindow) (*Limiter, StopFunc) 

• size：窗口大小
• limit：窗口限速
• newWindow：用于指定窗口類型。本實(shí)現(xiàn)中分為L(zhǎng)ocalWindow和SyncWindow兩種。前者用于設(shè)置單個(gè)節(jié)點(diǎn)的限速，后者用于和*存儲(chǔ)聯(lián)動(dòng)，可以實(shí)現(xiàn)全局限速。

下面看下核心函數(shù)AllowN和advance的實(shí)現(xiàn)：

實(shí)現(xiàn)中涉及到了3個(gè)窗口：當(dāng)前窗口、當(dāng)前窗口的前一個(gè)窗口以及滑動(dòng)窗口。每個(gè)窗口都有計(jì)數(shù)，且計(jì)數(shù)不能超過(guò)限速器設(shè)置的閾值。當(dāng)前窗口和當(dāng)前窗口的前一個(gè)窗口中保存了計(jì)數(shù)變量，而滑動(dòng)窗口的計(jì)數(shù)是通過(guò)計(jì)算獲得的。

// AllowN reports whether n events may happen at time now.
func (lim *Limiter) AllowN(now time.Time, n int64) bool {
	lim.mu.Lock()
	defer lim.mu.Unlock()

	lim.advance(now)//調(diào)整窗口

	elapsed := now.Sub(lim.curr.Start())
	weight := float64(lim.size-elapsed) / float64(lim.size)
	count := int64(weight*float64(lim.prev.Count())) + lim.curr.Count() //計(jì)算出滑動(dòng)窗口的計(jì)數(shù)值

	// Trigger the possible sync behaviour.
	defer lim.curr.Sync(now)

	if count+n > lim.limit { //如果滑動(dòng)窗口計(jì)數(shù)值+n大于閾值，則說(shuō)明如果運(yùn)行n個(gè)事件，會(huì)超過(guò)限速器的閾值，此時(shí)拒絕即可。
		return false
	}

	lim.curr.AddCount(n) //如果沒(méi)有超過(guò)閾值，則更新當(dāng)前窗口的計(jì)數(shù)即可。
	return true
}

// advance updates the current/previous windows resulting from the passage of time.
func (lim *Limiter) advance(now time.Time) {
	// Calculate the start boundary of the expected current-window.
	newCurrStart := now.Truncate(lim.size) //返回將當(dāng)前時(shí)間向下舍入為lim.size的倍數(shù)的結(jié)果，此為預(yù)期當(dāng)前窗口的開(kāi)始邊界

	diffSize := newCurrStart.Sub(lim.curr.Start()) / lim.size
	if diffSize >= 1 {
		// The current-window is at least one-window-size behind the expected one.

		newPrevCount := int64(0)
		if diffSize == 1 {
			// The new previous-window will overlap with the old current-window,
			// so it inherits the count.
			//
			// Note that the count here may be not accurate, since it is only a
			// SNAPSHOT of the current-window's count, which in itself tends to
			// be inaccurate due to the asynchronous nature of the sync behaviour.
			newPrevCount = lim.curr.Count()
		}
		lim.prev.Reset(newCurrStart.Add(-lim.size), newPrevCount)

		// The new current-window always has zero count.
		lim.curr.Reset(newCurrStart, 0)
	}
}

advance函數(shù)用于調(diào)整窗口大小，有如下幾種情況：

需要注意的是，newCurrStart 和lim.curr.Start()相差0或多個(gè)lim.size，如果相差0，則newCurrStart等于lim.curr.Start() ，此時(shí)滑動(dòng)窗口和當(dāng)前窗口有重疊部分。

• 如果diffSize == 1說(shuō)明記錄的當(dāng)前窗口和預(yù)期的當(dāng)前窗口是相鄰的(如下圖)。

  因此需要將記錄的當(dāng)前窗口作為前一個(gè)窗口(lim.prev)，并將預(yù)期的當(dāng)前窗口作為當(dāng)前窗口，設(shè)置計(jì)數(shù)為0。轉(zhuǎn)化后的窗口如下：

• 如果如果diffSize > 1說(shuō)明記錄的當(dāng)前窗口和預(yù)期的當(dāng)前窗口不相鄰，相差1個(gè)或多個(gè)窗口(如下圖)，說(shuō)明此時(shí)預(yù)期的當(dāng)前窗口的前一個(gè)窗口內(nèi)沒(méi)有接收到請(qǐng)求，因而沒(méi)有對(duì)窗口進(jìn)行調(diào)整。

  此時(shí)將前一個(gè)窗口的計(jì)數(shù)設(shè)置為0。并將預(yù)期的當(dāng)前窗口作為當(dāng)前窗口，設(shè)置計(jì)數(shù)為0。

此時(shí)AllowN中的運(yùn)算如下：

1. 計(jì)算出當(dāng)前時(shí)間距離當(dāng)前窗口開(kāi)始邊界的差值(elapsed)
2. 計(jì)算出滑動(dòng)窗口在前一個(gè)窗口中重疊部分所占的比重(百分比)
3. 使用滑動(dòng)窗口在前一個(gè)窗口中重疊部分所占的比重乘以前一個(gè)窗口內(nèi)的計(jì)數(shù)，再加上當(dāng)前窗口的計(jì)數(shù)，算出滑動(dòng)窗口的當(dāng)前計(jì)數(shù)
4. 如果要判斷滑動(dòng)窗口是否能夠允許n個(gè)事件，則使用滑動(dòng)窗口的當(dāng)前計(jì)數(shù)+n與計(jì)數(shù)閾值進(jìn)行比較。如果小于計(jì)數(shù)閾值，則允許事件，并讓滑動(dòng)窗口計(jì)數(shù)+n，否則返回false。

• 如果diffSize<1，說(shuō)明滑動(dòng)窗口和當(dāng)前窗口有重疊部分，此時(shí)不需要調(diào)整窗口。AllowN中的運(yùn)算與上述邏輯相同：

總結(jié)

以上是生活随笔為你收集整理的限速器算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。