FAIR 是一个 Go 库,旨在确保资源受限环境中的公平性。它有助于在资源短缺时将有限的资源(例如数据库/blob 存储吞吐量、作业执行资源等)均匀分配给多个客户端,防止基于客户端行为的过度分配和饥饿。
简介
FAIR 的核心算法基于 随机公平 BLUE[1] ,这种算法通常用于网络拥塞控制,但做了一些修改。FAIR 的理念是只在真正资源短缺时进行限制,而不是像令牌桶或漏桶等方法那样,即使资源仍然可用也可能拒绝请求(FAIR 的创造性配置可以实现这种类型的行为,但我们不鼓励这样做)。由于状态存储在多级 Bloom Filter[2] 风格的数据结构中,所需的内存是恒定的,不会随客户端数量的增加而扩展。在正确配置时,FAIR 可以扩展到非常大数量的客户端,具有较低的误报概率和接近零的持续误报概率,这要归功于哈希轮换机制,该机制定期重新哈希客户端以避免任何相关行为持续超过几分钟。
主要特性
- 框架和协议无关,易于集成到任何 HTTP/GRPC 服务中。
- 开箱即用的自动调优,配置最少,但需要时可以完全调优。
- 可扩展到大量客户端,内存需求恒定。
- 简单的资源和错误跟踪模型,可以轻松转化为多种类型的限制场景。
评估
在这个例子中,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 来调优跟踪器,而无需直接接触算法参数。它提供了一个简单的接口,你需要根据你的应用逻辑和扩展需求传递以下内容:
expectedClientFlows- 你预期的应用并发客户端数量bucketsPerLevel- 核心结构中每级的桶数tolerableBadRequestsPerBadFlow- 在完全关闭一个流之前我们可以容忍的请求数量
conf := config.GenerateTunedStructureConfig(1000, 1000, 25) trkB := tracker.NewFairnessTrackerBuilder() trk, err := trkB.BuildWithConfig(config) defer trk.Close()
参考链接
- 随机公平 BLUE: https://rtcl.eecs.umich.edu/rtclweb/assets/publications/2001/feng2001fair.pdf
- Bloom Filter: https://medium.com/p/e25942ab6093
