流量管制-令牌桶與漏桶-有解無憂

Principle of token bucket

隨著互聯網的發展，在處理流量的方法也不僅僅為 first-come，first-served，而在共享網路中實作流量管理的基本機制就是排隊，而公平演算法則是實作在優先級佇列中基于哪些策略來排隊的”公平佇列“，Token Bucket 則是為公平排隊提供了替代方案，Fair Queue 與 Token Bucket的區別主要在，對于Fair Queue來講，如果請求者目前空閑，Queue會將該請求者的帶寬分配給其他請求者；而 Token Bucket 則是分配給請求者的帶寬是帶寬的上限，

通過例子了解演算法原理

假設出站帶寬是 4個資料包/ms，此時有一個需求為，為一個特定的發送端 A 來分配 1個資料包/ms的帶寬，此時可以使用公平排隊的方法分給發送 A 25%的帶寬，

此時存在的問題是我們希望可以靈活地允許 A 的資料包以無規則的時間間隔發送，例如假設 A 在每個資料包發送后等待1毫秒后再開始下一個資料包的發送，

sence1：此時假設 A 以 1ms 的間隔去發送資料包，而由于某種原因導致應該在 t=6 到達的資料包卻在 t=6.5 到達，隨后的資料包在 t=7 準時到達，在這種情況下是否應該保留到t=7.5？
sence2：或者是否允許在 t=6.5 發送一個遲到的資料包，在 t=7 發送下一個資料包，此時理論上平均速率仍然還是 1 個資料包/ms？

顯然sence2是合理的，這個場景的解決方法就是令牌桶演算法，規定 A 的配額，允許指定平均速率和突發容量，當資料包不符合令牌桶規范，那么就認為其不合理，此時會做出一下相應：

delay，直到桶準備好
drop
mark，標記為不合規的資料包

delay 被稱為整形 shaping , shaping 是指在某個時間間隔內發送超過 Bc（Committed Burst）的大小，Bc 在這里指桶的尺寸，由于資料流量是突發性的，當在一段時間內不活動后，再次激活后的在一個間隔內發送的數量大于 Bc ，那么額外的流量被稱為Be （burst excess），

將流量丟棄或標記超額流量，保持在一個流量速率限制稱為管制 policing，

Definition

令牌桶的定義是指，有一個桶，以穩定的速度填充令牌；桶中的任何一個溢位都會被丟棄，當要發送一個資料包，需要能夠從桶中取出一個令牌；如果桶是空的那么此時資料包是不合規的資料包，必須進行 delay , drop , mark 操作，如果桶是滿的，則會發送與桶容量相對應的突發（短時間內的高帶寬傳輸），這是桶是空的，

令牌桶的規范：\(TB(r,B_{max})\)

\(r\) ：r個token每秒的令牌填充率，表示桶填充令牌的速率
\(B\) ：桶容量，\(B_{mac} > 0\)

那么公式則表示，桶以指定的速率填充令牌，最大為 \(B_{max}\) ，這就說明了為了使大小為 S 的資料包合規，桶內必須至少有 S 個令牌，即 \(B \ge S\)，否則資料包不合規，在發送時，桶為 \(B=B-S\)

Examples

場景1：假設令牌桶規范為 \(TB(\frac{1}{3}\ packet/ms, 4\ packet)\)，桶最初是滿的，資料包在以下時間到達 [0, 0, 0, 2, 3, 6, 9, 12]

在處理完所有 T=0 的資料包后，桶中還剩 1 個令牌，到第四個資料包 T=2 到達時，桶內已經有1個令牌 + \(\frac{2}{3}\) 個令牌；當發送完第四個資料包時，桶內令牌數為 \(\frac{2}{3}\) ，到 T=3 資料包時，桶內令牌為1，滿足發送第 5 個資料包，萬松完成后桶是空的，在后面 6 9 12時，都滿足3/ms 一個資料包，都可以發送成功

場景2：另外一個實體，在同樣的令牌桶規范下 \(TB(\frac{1}{3}, 4)\)，資料包到達時間為 [0, 0, 0, 0, 12, 12, 12, 12, 24, 24, 24, 24] ，可以看到在這個場景下，資料到達為3個突發，每個突發4個資料包，此時每次發送完成后桶被清空，當再次填滿時需要12ms，此時另外一組突發達，故這組資料是合規的，、

場景3：在同樣的令牌桶規范下 \(TB(\frac{1}{3}, 4)\)，資料包到達時間為 [0, 1, 2, 3, 4, 5] , 這組資料是不合規的

用表格形式表示如下：

資料包到達時間	0	1	2	3	4	5
發送前桶內令牌	4	3 \(\frac{1}{3}\)	2 \(\frac{2}{3}\)	2	1 \(\frac{1}{3}\)	\(\frac{2}{3}\)
發送后桶內令牌	3	2 \(\frac{1}{3}\)	1 \(\frac{2}{3}\)	1	\(\frac{1}{3}\)	\(\frac{2}{3}\)

如果一個資料包在桶中沒有足夠的令牌來發送它時到達，可以進行整形或管制，整形使資料包等到足夠的令牌積累，管制會丟棄資料包，或者發送方可以立即發送資料包，但將其標記為不合規，

Principle of leaky bucket

漏桶（leaky bucket）是一種臨時存盤可變數量的請求并將它們組織成設定速率輸出的資料包的方法，漏桶的概念與令牌桶比起是相反的，漏桶可以理解為是一個具有恒定服務時間的佇列，

由下圖可以看出，漏桶的概念是一個底部有孔的桶，無論水進入桶的速度是多少，它都會以恒定的速度通過孔從桶中泄漏出來，如果桶中沒有水，則流速為零，如果桶已滿，則多余的水溢位并丟失，

和令牌桶一樣，漏桶用于流量整形和流量管制

Difference between Token and Leaky

Leaky	Token
桶中存放的是所有到達的資料包，必須入桶	桶中存放的是定期生成的令牌
桶以恒定速率泄漏	桶有最大容量 \(B_{max}\)
突發流量入桶轉換為恒定流量發送	發送資料包需要小號對應的token

token較leaky的優勢：

在令牌桶中，如果桶已滿，處理的方式有 shaping和policing兩種模型三種方式（延遲、丟棄、標記），而漏桶中的流量僅為shaping，
- 通俗來說，就是令牌桶已滿，丟棄的是令牌，漏桶中丟棄的則是資料包
令牌桶可以更快的速率發送大突發流量，而漏桶僅是恒定速率

Implementation with go

Token

在golang中，內置的 rate 包實作了一個令牌桶演算法，通過 rate.NewLimiter(r,B) 進行構造，與公式\(TB(r,B_{max})\) 意思相同，

type Limiter struct {
	limit Limit // 向桶中放置令牌的速率
	burst int // 桶的容量
	mu     sync.Mutex
	tokens float64 // 可用令牌容量
	last time.Time // 上次放入token的時間
	lastEvent time.Time
}

Limiter中帶有三種方法， Allow、Reserve、Wait 分別表示Token Bucket中的 shaping 和 policing：

Allow：丟棄超過速率的事件，類似 drop
Wait：等待，直到獲取到令牌或者取消或deadline/timeout
Reserve：等待或減速，不丟棄事件，類似于 delay

Reserve/ReserveN

Reserve() 回傳了 ReserveN(time.Now(), 1)
ReserveN() 無論如何都會回傳一個 Reservation，指定了呼叫者在 n 個事件發生之前必須等待多長時間，
Reservation 是一個令牌桶事件資訊
Reservation 中的 Delay() 方法回傳了需要等待的時間，如果時間為0則不需要等待
Reservation 中的 Cancel() 將取消等待

wait/waitN

Allow/AllowN

在獲取不到令牌是丟棄對應的事件
回傳的是一個 reserveN() 拿到token是合規的，并消耗掉token

AllowN 為截止到某一時刻，當前桶內桶中數目是否至少為 n 個，滿足則回傳 true，同時從桶中消費 n 個 token，反之不消費 Token，false，

func (lim *Limiter) AllowN(now time.Time, n int) bool {
	return lim.reserveN(now, n, 0).ok // 由于僅需要一個合規否，顧合規的通過，不合規的丟棄
}

reserveN() 是三個行為的核心，AllowN中指定的為 0 ，因為 maxFutureReserve 是最大的等待時間，AllowN給定的是0，即如果突發大的情況下丟棄額外的 Bc，

func (lim *Limiter) reserveN(now time.Time, n int, maxFutureReserve time.Duration) Reservation {
	lim.mu.Lock()

	if lim.limit == Inf {
		lim.mu.Unlock()
		return Reservation{
			ok:        true,
			lim:       lim,
			tokens:    n,
			timeToAct: now,
		}
	}
	// 這里拿到的是now，上次更新token時間和桶內token數量
	now, last, tokens := lim.advance(now)
	// 計算剩余的token
	tokens -= float64(n)

	// Calculate the wait duration
	var waitDuration time.Duration
	if tokens < 0 {
		waitDuration = lim.limit.durationFromTokens(-tokens)
	}

	// 確定是否合規，n是token
    // token 的數量要小于桶的容量，并且 等待時間小于最大等待時間
	ok := n <= lim.burst && waitDuration <= maxFutureReserve

	// Prepare reservation
	r := Reservation{
		ok:    ok,
		lim:   lim,
		limit: lim.limit,
	}
	if ok {
		r.tokens = n
		r.timeToAct = now.Add(waitDuration)
	}

	// Update state
	if ok {
		lim.last = now
		lim.tokens = tokens
		lim.lastEvent = r.timeToAct
	} else {
		lim.last = last
	}

	lim.mu.Unlock()
	return r
}

在reserveN中呼叫了一個 advance() 函式，

func (lim *Limiter) advance(now time.Time) (newNow time.Time, newLast time.Time, newTokens float64) {
   last := lim.last
   if now.Before(last) { // 計算上次放入token是否在傳入now之前
      last = now
   }

   // 當 last 很舊時，避免在下面進行 delta 溢位，
   // maxElapsed 計算裝滿需要多少時間
   maxElapsed := lim.limit.durationFromTokens(float64(lim.burst) - lim.tokens)
   elapsed := now.Sub(last) // 上次裝入到現在的時差
   if elapsed > maxElapsed { // 上次如果放入token時間超長，就讓他與裝滿時間相等
      elapsed = maxElapsed // 即，讓桶為滿的
   }

   // 裝桶的動作，下面函式表示，elapsed時間內可以生成多少個token
   delta := lim.limit.tokensFromDuration(elapsed)
   tokens := lim.tokens + delta // 當前的token
   if burst := float64(lim.burst); tokens > burst {
      tokens = burst // 這里表示token溢位，讓他裝滿就好
   }

   return now, last, tokens
}

wait/waitN

桶內令牌可以>N時，回傳，在獲取不到令牌是阻塞，等待context取消或者超時
回傳的是一個 reserveN() 拿到token是合規的，并消耗掉token

func (lim *Limiter) WaitN(ctx context.Context, n int) (err error) {
	if n > lim.burst && lim.limit != Inf {
		return fmt.Errorf("rate: Wait(n=%d) exceeds limiter's burst %d", n, lim.burst)
	}
	// 外部已取消
	select {
	case <-ctx.Done():
		return ctx.Err()
	default:
	}
	// Determine wait limit
	now := time.Now()
	waitLimit := InfDuration
	if deadline, ok := ctx.Deadline(); ok {
		waitLimit = deadline.Sub(now)
	}
	// 三個方法的核心，這里給定了deatline
	r := lim.reserveN(now, n, waitLimit)
	if !r.ok {
		return fmt.Errorf("rate: Wait(n=%d) would exceed context deadline", n)
	}
	// Wait if necessary
	delay := r.DelayFrom(now)
	if delay == 0 {
		return nil
	}
	t := time.NewTimer(delay)
	defer t.Stop()
	select {
	case <-t.C:
		// We can proceed.
		return nil
	case <-ctx.Done():
		// Context was canceled before we could proceed.  Cancel the
		// reservation, which may permit other events to proceed sooner.
		r.Cancel()
		return ctx.Err()
	}
}

Dynamic Adjustment

在 rate.limiter 中，支持調整速率和桶大小，這樣就可以根據現有環境和條件，來動態的改變 Token生成速率和桶容量

SetLimit(Limit) 更改生成 Token 的速率
SetBurst(int) 改變桶容量

Example

一個流量整形的場景

package main

import (
	"log"
	"strconv"
	"time"

	"golang.org/x/time/rate"
)

func main() {
	timeLayout := "2006-01-02:15:04:05.0000"
	limiter := rate.NewLimiter(1, 5) // BT(1,5)
	log.Println("bucket current capacity: " + strconv.Itoa(limiter.Burst()))
	length := 20 // 一共請求20次
	chs := make([]chan string, length)
	for i := 0; i < length; i++ {
		chs[i] = make(chan string, 1)
		go func(taskId string, ch chan string, r *rate.Limiter) {
			err := limiter.Allow()
			if !err {
				ch <- "Task-" + taskId + " unallow " + time.Now().Format(timeLayout)
			}

			time.Sleep(time.Duration(5) * time.Millisecond)
			ch <- "Task-" + taskId + " run success  " + time.Now().Format(timeLayout)
			return

		}(strconv.FormatInt(int64(i), 10), chs[i], limiter)
	}
	for _, ch := range chs {
		log.Println("task start at " + <-ch)
	}
}

通過執行結果可以看出，在突發為20的情況下，allow僅允許了獲得token的事件執行，，這種場景下實作了流量整形的特性，

一個流量管制的場景

package main

import (
	"context"
	"log"
	"strconv"
	"time"

	"golang.org/x/time/rate"
)

func main() {
	timeLayout := "2006-01-02:15:04:05.0000"
	limiter := rate.NewLimiter(1, 5) // BT(1,5)
	log.Println("bucket current capacity: " + strconv.Itoa(limiter.Burst()))
	length := 20 // 一共請求20次
	chs := make([]chan string, length)
	for i := 0; i < length; i++ {
		chs[i] = make(chan string, 1)
		go func(taskId string, ch chan string, r *rate.Limiter) {
			err := limiter.Wait(context.TODO())
			if err != nil {
				ch <- "Task-" + taskId + " unallow " + time.Now().Format(timeLayout)
			}
			ch <- "Task-" + taskId + " run success  " + time.Now().Format(timeLayout)
			return

		}(strconv.FormatInt(int64(i), 10), chs[i], limiter)
	}
	for _, ch := range chs {
		log.Println("task start at " + <-ch)
	}
}

結果可以看出，在大突發的情況下，在拿到token的任務會立即執行，沒有拿到token的會等待拿到token后繼續執行，這種場景下實作了流量管制的特性

Reference

tokenbucket
QoS Policing

作者：鋼閘門
出處：http://lc161616.cnblogs.com/ 本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利， 阿里云優惠：點擊力享低價 墨墨學英語：幫忙點一下

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/491773.html

標籤：Go

上一篇：JqueryinArray為不存在的物件回傳true

下一篇：fastJson如何將json與物件、集合、陣列相互轉換呢？