Golang 随机公平库 satmihir/fair

FAIR 是一个 Go 库，旨在确保资源受限环境中的公平性。它帮助在资源短缺的情况下将有限的资源（如数据库/Blob 存储吞吐量、作业执行资源等）均匀分配给多个客户端，防止因客户端行为引起的过度分配和资源饥饿问题。

简介

FAIR 的核心算法基于随机公平的 BLUE[1] 算法，该算法通常用于网络拥塞控制，经过了一些修改。FAIR 的理念是在真正资源短缺时才进行限制，而不是像令牌桶或漏桶等方法一样，即使资源可用也可能拒绝请求。FAIR 采用了多级 Bloom Filter[2] 风格的数据结构，使所需的内存保持恒定，不会随客户端数量增加而扩展。在正确配置下，FAIR 可以扩展到大量客户端，具有较低的误报概率，并且得益于哈希轮换机制，误报持续时间接近于零。

主要特性

框架和协议无关，易于集成到任何 HTTP/GRPC 服务中。
自动调优，开箱即用，配置最少，但也可以进行全面调优。
可扩展到大量客户端，内存需求恒定。
简单的资源和错误跟踪模型，适用于多种类型的资源限制场景。

评估

在一个评估例子中，20 个客户端竞争一个以 20/s 的速率再生的资源。20 个客户端中有 18 个表现良好，它们每秒请求一次资源，剩下的两个客户端则每 100 毫秒请求一次。在不受限制的情况下，不公平的客户端抢占了大量资源，而常规工作负载处于饥饿状态，资源获取速率远低于 1/s。使用 FAIR 限制后，常规工作负载几乎不受影响，不公平的工作负载则受到限制，且长时间内也能获得公平份额。

安装

使用 go get 安装 FAIR 库：

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）来判断是否需要限制：

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(conf)
defer trk.Close()