Golang 隨機公平庫 satmihir-fair

FAIR 是一個 Go 庫, 旨在確保資源受限環境中的公平性。它有助於在資源短缺時將有限的資源 (例如數據庫 / blob 存儲吞吐量、作業執行資源等) 均勻分配給多個客戶端, 防止基於客戶端行爲的過度分配和飢餓。

簡介

FAIR 的核心算法基於 隨機公平 BLUE[1] , 這種算法通常用於網絡擁塞控制, 但做了一些修改。FAIR 的理念是隻在真正資源短缺時進行限制, 而不是像令牌桶或漏桶等方法那樣, 即使資源仍然可用也可能拒絕請求 (FAIR 的創造性配置可以實現這種類型的行爲, 但我們不鼓勵這樣做)。由於狀態存儲在多級  Bloom Filter[2]  風格的數據結構中, 所需的內存是恆定的, 不會隨客戶端數量的增加而擴展。在正確配置時, FAIR 可以擴展到非常大數量的客戶端, 具有較低的誤報概率和接近零的持續誤報概率, 這要歸功於哈希輪換機制, 該機制定期重新哈希客戶端以避免任何相關行爲持續超過幾分鐘。

主要特性

評估

在這個例子中, 20 個客戶端競爭一個以 20/s 的速率再生的資源 (圖中每個數據點間隔 5 秒)。20 個客戶端中有 18 個是 "表現良好" 的, 因爲它們每秒請求一次資源, 而剩下的兩個客戶端則試圖每 100 毫秒獲取一次資源, 這是一個 "不公平" 的速率。在左側, 我們看到當不受限制時, 兩個不公平的客戶端搶佔了不成比例的大量資源, 而常規工作負載則處於飢餓狀態, 獲得的資源遠低於 1/s 的速率。在右側, 當使用 fair 進行限制時, 常規工作負載幾乎不受影響, 而不公平的工作負載則受到限制。平均而言, 即使是不公平的工作負載, 在較長時間段內也能獲得公平份額。

安裝

要安裝 FAIR 庫, 請使用 go get:

go get github.com/satmihir/fair

然後, 在你的 Go 代碼中導入它:

import "github.com/satmihir/fair"

使用方法

使用默認配置 (在大多數情況下應該能很好地工作):

trkB := tracker.NewFairnessTrackerBuilder()

trk, err := trkB.BuildWithDefaultConfig()
defer trk.Close()

如果你想對配置進行一些更改, 可以使用構建器上的 setter:

trkB := tracker.NewFairnessTrackerBuilder()
// 每分鐘輪換一次底層哈希,以避免相關的誤報
trkB.SetRotationFrequency(1 * time.Minute)

trk, err := trkB.Build()
defer trk.Close()

對於每個傳入的請求, 你必須將流標識符 (你想要維護公平性的 ID) 傳遞給跟蹤器, 以查看是否需要限制它。例如, 客戶端 ID 可以作爲這樣的 ID 來維護客戶端之間的資源公平性。

ctx := context.Background()
id := []byte("client_id")

resp, _ := trk.RegisterRequest(ctx, id)
if resp.ShouldThrottle {
    throttleRequest()
}

對於任何表示資源短缺的失敗 (這是我們開始限制的觸發器), 你要將結果報告爲失敗。對於在你的業務邏輯中被視爲失敗但不表示資源短缺的任何其他結果, 不要報告任何結果。

ctx := context.Background()
id := []byte("client_id")

trk.ReportOutcome(ctx, id, request.OutcomeFailure)

另一方面, 當你能夠獲得資源時, 你要報告成功。

ctx := context.Background()
id := []byte("client_id")

trk.ReportOutcome(ctx, id, request.OutcomeSuccess)

調優

你可以使用 GenerateTunedStructureConfig 來調優跟蹤器, 而無需直接接觸算法參數。它提供了一個簡單的接口, 你需要根據你的應用邏輯和擴展需求傳遞以下內容:

conf := config.GenerateTunedStructureConfig(1000, 1000, 25)
trkB := tracker.NewFairnessTrackerBuilder()

trk, err := trkB.BuildWithConfig(config)
defer trk.Close()

參考鏈接

  1. 隨機公平 BLUE: https://rtcl.eecs.umich.edu/rtclweb/assets/publications/2001/feng2001fair.pdf
  2. Bloom Filter: https://medium.com/p/e25942ab6093
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ITRMicqEGCG4r5-cm2Kzfw

猜你喜歡