What is 限流？

限流顧名思義,限制流量或者說(shuō)叫流量管制。

很形象的比喻如老式電閘都安裝了保險(xiǎn)絲，一旦有人使用超大功率的設(shè)備，保險(xiǎn)絲就會(huì)燒斷以保護(hù)各個(gè)電器不被強(qiáng)電流給燒壞。

Why use 限流？

理論上一個(gè)完整的對(duì)外提供服務(wù)的系統(tǒng)架構(gòu)在設(shè)計(jì)初期，就要基于上游流量，流速，高峰期時(shí)間點(diǎn)，峰值 qps，還有自身系統(tǒng)的負(fù)載能力，評(píng)估系統(tǒng)的吞吐量，并且進(jìn)行入口流量的管制。

當(dāng)超出限流閾值時(shí)，系統(tǒng)可以采取拒絕服務(wù),排隊(duì)或者引流等機(jī)制, 保證自身一直在健康的負(fù)載下。

如果系統(tǒng)沒(méi)有限流策略,對(duì)于突發(fā)性的超自身負(fù)載的流量，系統(tǒng)只能被動(dòng)的無(wú)奈接受,系統(tǒng)內(nèi)各個(gè)子服務(wù)逐漸解體，最后服務(wù)整體雪崩。

小概念 Review

QPS

Queries Per Second （每秒查詢率），每秒查詢率 QPS 是對(duì)一個(gè)特定的查詢服務(wù)器在規(guī)定時(shí)間內(nèi)所處理流量多少的衡量標(biāo)準(zhǔn)，在因特網(wǎng)上，作為域名系統(tǒng)服務(wù)器的機(jī)器的性能經(jīng)常用每秒查詢率來(lái)衡量。

RPS

Requests Per Second （每秒發(fā)送請(qǐng)求數(shù) /吞吐率），指客戶端每秒發(fā)出的請(qǐng)求數(shù)。阿里云 PTS 對(duì)于這個(gè)詞的解釋為 RPS 有些地方也叫做 QPS，在不單獨(dú)討論“事務(wù)”的情況下可以近似對(duì)應(yīng)到 Loadrunner/jmeter 的 TPS （ Transaction Per Second, 每秒事務(wù)數(shù)）。

TPS

Transactions Per Second （每秒傳輸?shù)氖挛锾幚韨€(gè)數(shù)），即服務(wù)器每秒處理的事務(wù)數(shù)。TPS 一般包括一條消息入和一條消息出，加上一次用戶數(shù)據(jù)庫(kù)訪問(wèn)。（業(yè)務(wù) TPS = CAPS × 每個(gè)呼叫平均 TPS ）

限流粒度

• 集群限流
• 單機(jī)限流

集群限流

集群限流方式可以歸納為兩種

• 網(wǎng)關(guān)層
• 應(yīng)用層

網(wǎng)關(guān)層

網(wǎng)關(guān)層常見設(shè)計(jì)，基于 Nginx lua module 實(shí)現(xiàn)整體管控。下面是簡(jiǎn)單 lua demo 。

local locks = require "resty.lock"
 
local function limiter()
    -- ngx dict
    local limiter = ngx.shared.limiter
    -- limiter lock
    local lock = locks:new("limiter_lock")
    local key = gx.var.host..ngx.var.uri
 
    -- add lock
    local elapsed, err =lock:lock("ngx_limiter:"..key)
    if not elapsed then
        return fail("failed to acquire the lock: ", err)
    end
    -- limit max value
    local limit = 5
    -- current value
    local current =limiter:get(key)
 
    -- 限流
    if current ~= nil and current + 1> limit then
       lock:unlock()
       return 0
    end
     
    if current == nil then
       limiter:set(key, 1, 1) -- 初始化
    else
        limiter:incr(key, 1)  -- +1
    end
    lock:unlock()
    return 1
end
ngx.print(limiter())

了解 lua-resty-lock：
https://github.com/openresty/lua-resty-lock

Nginx.conf

http {
 
    ……
    lua_shared_dict limiter_lock 10m;
    lua_shared_dict limiter 10m;
}

應(yīng)用層

應(yīng)用層常見通過(guò)業(yè)務(wù)代碼實(shí)現(xiàn)，基于 redis 計(jì)數(shù), 通過(guò) lua script 保證 redis 執(zhí)行原子性

local key = "limiter:" .. KEYS[1]
local limit = tonumber(ARGV[1])
local expire_time = tonumber(ARGV[2])
local is_exists = redis.call("EXISTS", key)
if is_exists == 1 then
    if redis.call("INCR", key) > limit then
        return 0
    else
        return 1
    end
else
    redis.call("SET", key, 1)
    redis.call("EXPIRE", key, expire_time)
    return 1
end

單機(jī)限流

單兵作戰(zhàn)，自生自滅，我不倒集群不倒。不依賴存儲(chǔ)中間件，基于 local cache 就可以實(shí)現(xiàn)簡(jiǎn)單的本地計(jì)數(shù)限流，宏觀角度觀察，只要網(wǎng)關(guān)層負(fù)載均衡服務(wù)高可用，每個(gè)節(jié)點(diǎn)流量差別不大，只需要關(guān)心單個(gè)節(jié)點(diǎn)的流量管控就可以。

以上是限流粒度分類，下面說(shuō)說(shuō)具體的限流算法模型。

限流模型

以上 Demo 都是基于簡(jiǎn)單的固定時(shí)間窗口模型實(shí)現(xiàn)限流，但是當(dāng)出現(xiàn)臨界點(diǎn)瞬間大流量沖擊，。

常用的模型分類有兩種：

• 時(shí)間模型
• 桶模型

時(shí)間模型

時(shí)間模型分兩種:

• 固定窗口模型
• 滑動(dòng)窗口模型

固定時(shí)間模型

上面聊到的各粒度限流模式的 code demo 都是這種方式。

如圖(圖片來(lái)源網(wǎng)絡(luò))，拉長(zhǎng) timeline，以 QPS 為例，限流 1000QPS，我們會(huì)講 timeline 按照固定間隔分窗口，每個(gè)窗口有一個(gè)獨(dú)立計(jì)數(shù)器，每個(gè)計(jì)數(shù)器統(tǒng)計(jì)窗口內(nèi)的 qps，如果達(dá)到閾值則拒絕服務(wù)，這是一種最簡(jiǎn)單的限流模型，但是缺點(diǎn)比較明顯，當(dāng)在臨界點(diǎn)出現(xiàn)大流量沖擊，就無(wú)法滿足流量控制。

如圖(圖片來(lái)源網(wǎng)絡(luò))，在 900ms 和 1100ms 都出現(xiàn) 1000QPS 并發(fā)，雖然單個(gè)窗口內(nèi)是符合限流要求，但是實(shí)際上臨界點(diǎn)處的 QPS 已經(jīng)打到 2000，服務(wù)過(guò)載。

滑動(dòng)時(shí)間模型

如圖(圖片來(lái)源網(wǎng)絡(luò))，為了規(guī)避臨界點(diǎn)大流量沖擊，滑動(dòng)時(shí)間模型會(huì)將每個(gè)窗口切分成 N 個(gè)子窗口，每個(gè)子窗口獨(dú)立計(jì)數(shù)。這樣用w1+w2計(jì)數(shù)之和來(lái)做限流閾值校驗(yàn)，就可以解決此問(wèn)題。

桶模型

桶模型也分兩種:

• 令牌桶
• 漏桶

令牌桶模型

令牌桶算法的原理是系統(tǒng)會(huì)以一個(gè)恒定的速度往桶里放入令牌，而如果請(qǐng)求需要被處理，則需要先從桶里獲取一個(gè)令牌，當(dāng)桶里沒(méi)有令牌可取時(shí)，則拒絕服務(wù)。不過(guò)令牌桶還是允許一定程度的突發(fā)傳輸,這樣解決了在實(shí)際上的互聯(lián)網(wǎng)應(yīng)用中，流量經(jīng)常是突發(fā)性的問(wèn)題。

Ref: https://en.wikipedia.org/wiki/Token_bucket

如圖：

算法實(shí)現(xiàn)方式有兩種：

• Ticker
  定義一個(gè) Ticker，持續(xù)生成令牌并導(dǎo)入桶中。這樣問(wèn)題是會(huì)極大的消耗系統(tǒng)資源。如果基于某一維度進(jìn)行限流，會(huì)創(chuàng)建多桶，對(duì)應(yīng)多 Ticker，資源消耗很可怕。
• Inert Fill
  惰性填充，定義一個(gè) inert fill 函數(shù)。該函數(shù)會(huì)在每次獲取令牌之前調(diào)用，其實(shí)現(xiàn)思路為，若當(dāng)前時(shí)間晚于 lastAccessTime，則計(jì)算該段時(shí)間內(nèi)可以生成多少令牌，將生成的令牌加入令牌桶中并更新數(shù)據(jù)。這樣一來(lái)，只需要在獲取令牌時(shí)計(jì)算一次即可。

桶內(nèi)令牌數(shù)計(jì)數(shù)方式

桶內(nèi)令牌數(shù) = 剩余的令牌數(shù) + (本次取令牌的時(shí)刻-上一次取令牌的時(shí)刻)/放置令牌的時(shí)間間隔 * 每次放置的令牌數(shù)

常用令牌桶如: github.com/juju/ratelimit 2K Star

多種填充令牌方式:

func NewBucket(fillInterval time.Duration, capacity int64) *Bucket

默認(rèn)令牌桶，fillInterval 每過(guò)多?時(shí)間向桶?放?個(gè)令牌，capacity 是桶的容量，超過(guò)桶容量的部分會(huì)被直接丟棄。

func NewBucketWithQuantum(fillInterval time.Duration, capacity, quantum int64) *Bucket

和默認(rèn)方式一樣，唯一不同是每次填充的令牌數(shù)是 quantum,而不是 1 個(gè)。

func NewBucketWithRate(rate float64, capacity int64) *Bucket

按照使用方定義的?例，每秒鐘填充令牌數(shù)。比如 capacity 是 100，? rate 是 0.1，那么每秒會(huì)填充 10 個(gè)令牌。

多種領(lǐng)取令牌方式:

func (tb *Bucket) Take(count int64) time.Duration {}
func (tb *Bucket) TakeAvailable(count int64) int64 {}
func (tb *Bucket) TakeMaxDuration(count int64, maxWait time.Duration) (
    time.Duration, bool,
) {}
func (tb *Bucket) Wait(count int64) {}
func (tb *Bucket) WaitMaxDuration(count int64, maxWait time.Duration) bool {}

如下,我簡(jiǎn)單實(shí)現(xiàn)了一個(gè)極簡(jiǎn)的令牌桶, 速率默認(rèn)為 QPS 。

TokenBucket Demo

Struct 結(jié)構(gòu)

// object
type TbConfig struct {
  QPS    int64 	// 限制 qps e.g 200
  MaxCap int64	// 桶最大容量 e.g:1000
}
type TokenBucket struct {
	*TbConfig
	m         sync.Mutex		// 讀寫鎖
	available int64					// 可用令牌
	lastTime  time.Time			// 最后一次獲取令牌時(shí)間
}

Inert Fill

func (tb *TokenBucket) fill() error {
   n := time.Now()
   timeUnit := n.Sub(tb.latestTime).Seconds()
   fillCnt := int64(timeUnit) * tb.QPS // 見文下描述
   if fillCnt <= 0 {
      return nil
   }
   tb.available += fillCnt
   // 防止過(guò)大溢出
   if tb.MaxCap > 0 && tb.available > tb.MaxCap {
      tb.available = tb.MaxCap
   }
   tb.latestTime = n
   return nil
}

桶內(nèi)令牌數(shù) = 剩余的令牌數(shù)**tb.available** + (本次取令牌的時(shí)刻**n** - 上一次取令牌的時(shí)刻**tb.latestTime) / 放置令牌的時(shí)間間隔速率為 qps,所以此處是1** * 每次放置的令牌數(shù)**tb.QPS**

漏桶模型

漏桶算法思路很簡(jiǎn)單，如下圖(圖片來(lái)源網(wǎng)絡(luò)),水（請(qǐng)求）先進(jìn)入到漏桶里，漏桶以一定的速度出水，當(dāng)水流入速度過(guò)大會(huì)直接溢出，可以看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率。

簡(jiǎn)單的說(shuō)： 調(diào)用方只能嚴(yán)格按照預(yù)定的間隔順序進(jìn)行消費(fèi)調(diào)用。

Ref: https://en.wikipedia.org/wiki/Leaky_bucket

常用漏桶:
https://github.com/uber-go/ratelimit 2.4k Star

對(duì)于很多應(yīng)用場(chǎng)景來(lái)說(shuō)，除了要求能夠限制流量的平均傳輸速率外，還要求允許某種程度的突發(fā)傳輸。

傳統(tǒng)的 Leaky Bucket，關(guān)鍵點(diǎn)在于漏桶始終按照固定的速率運(yùn)行，但是它并不能很好的處理有大量突發(fā)請(qǐng)求的場(chǎng)景。

對(duì)于這種情況，uber-go 對(duì) Leaky Bucket 做了一些改良，引入了最大松弛量 (maxSlack) 的概念。

當(dāng)請(qǐng)求間隔時(shí)間小于固定的速率時(shí)，可以把間隔比較長(zhǎng)的請(qǐng)求多余出來(lái)的時(shí)間 buffer，勻給后面的使用，保證每秒請(qǐng)求數(shù)。如果間隔時(shí)間遠(yuǎn)遠(yuǎn)超出固定速率,那會(huì)給后續(xù)請(qǐng)求增加超大的 buffer，以至于即使后面大量請(qǐng)求瞬時(shí)到達(dá)，也無(wú)法抵消完這個(gè)時(shí)間，那這樣就失去了限流的意義。所以 maxSlack 會(huì)限制這個(gè) buffer 上限。

LeakyBucket Demo

如下,實(shí)現(xiàn)了一個(gè)極簡(jiǎn)的非阻塞漏桶。

Struct 結(jié)構(gòu)

// object
type LbConfig struct {
  Rate     float64 // 速率 e.g 200: 每秒 200 次請(qǐng)求
  MaxSlack int64   // 最大松弛量,可以理解 buffer 時(shí)間內(nèi)最大放行的 qps 。默認(rèn)為 0 表示不開啟松弛量 e.g 10: 如果松弛量大于 10，則松弛量強(qiáng)制為 10
}
type LeakyBucket struct {
	*LbConfig
	m          sync.Mutex			// 讀寫鎖    			
	perRequest time.Duration		// 速率
	bufferTime time.Duration		// 多余時(shí)間
	slackTime  time.Duration		// 最大松弛時(shí)間
	lastTime   time.Time			// 最后一次獲取令牌時(shí)間
}

無(wú)松弛量實(shí)現(xiàn)

即嚴(yán)格按照預(yù)定時(shí)間間隔獲取令牌。

func (lb *LeakyBucket) withoutSlack() error {
	n := time.Now()
	lb.bufferTime = lb.perRequest - n.Sub(lb.lastTime)
	// 多余時(shí)間如果為正數(shù)： 證明前后時(shí)間間隔超過(guò)預(yù)期速率，需要拒絕服務(wù)
	if lb.bufferTime > 0 {
		return ErrNoTEnoughToken
	} else {
		lb.lastTime = n
	}
	return nil
}

有松弛量實(shí)現(xiàn)

即多余時(shí)間勻給后面獲取令牌使用。

func (lb *LeakyBucket) withSlack() error{
	n := time.Now()
  // 此處為+= 表示要累計(jì)多余時(shí)間
	lb.bufferTime += lb.perRequest - n.Sub(lb.lastTime)
	// 多余時(shí)間如果為正數(shù)： 證明前后時(shí)間間隔超過(guò)預(yù)期速率，需要拒絕服務(wù)
	if lb.bufferTime > 0 {
		return ErrNoTEnoughToken
	} else {
		lb.lastTime = n
	}
	// 允許抵消的最長(zhǎng)時(shí)間
	if lb.bufferTime < lb.slackTime {
		lb.bufferTime = lb.slackTime
	}
	return nil
}

Demo 源碼

源碼可見
github.com/xiaoxuz/limiter

感謝閱讀，三連是最大的支持！