17.1 匹配算法与公平性
组队、排位、战场，只要一局需要「凑够 N 个人才能开」，服务端就得有一张匹配器。听起来它只是把玩家从队列里两两取出来，但真正上线后你会发现，匹配器的每一个决定都在两个互相矛盾的目标之间拉扯：要么等得久一点、配得准一点，要么配得快一点、实力悬殊一点。
把这件事做对很难，难在三点。第一，评分必须是可复现的纯函数——同一个玩家、同一时刻、同样的对手，评分结果必须逐位相同，否则线上对不齐、测试也写不了断言。第二，窗口必须随等待时长放宽，否则高分段玩家凌晨三点永远配不上，只能一直干等。第三，rating 到底准不准，不能靠「感觉」，得有一个能跑出来的收敛实验：跑几百轮之后，rating 的排序是不是真的和真实实力的排序一致。
本节从零实现 internal/match 包的前半部分：Elo 期望胜率、随等待时长放宽的窗口、确定性的评分函数，以及一个 128 人 400 轮的仿真。全部代码是 L1，go test ./internal/match/ 可以直接跑。
本章与站内既有内容的分工
站内已有几篇文章讲过匹配服务的整体架构、房间生命周期与实例调度，它们负责「架构方案与取舍」。本章不复述结论，只做一件事：把匹配、大厅、实例池从零写出来并跑出真实数字。分工如下。
| 既有文章 | 它负责什么 | 本节只做什么 |
|---|---|---|
/game-server-matchmaking-architecture-design/ | 匹配服务的分层与整体方案 | 只写「评分与窗口」这一层的可跑实现 |
/matchmaking-service-is-more-than-filling-a-room/ | 为什么匹配不只是「凑满一个房间」 | 只量化评分函数的可复现性与收敛性 |
/game-server-match-lobby-lifecycle-architecture/ | 大厅房间的生命周期 | 只产出「成局」这一事件，生命周期见 17.2 |
/game-server-instance-scheduler-architecture/ | 实例调度的架构 | 只做单服实例池的分配与回收，见 17.3 |
/game-server-battle-instance-allocation-broker-architecture/ | 战斗实例分配代理 | 只写池内 best-fit 与冷却，跨服调度留到卷三 |
评分函数：把公平性写成可复现的公式
匹配器的输入是一张票据 Ticket：玩家、当前 rating、延迟、队伍人数、进队时刻。匹配的入口命令号是 CmdMatchJoinReq 0x0C01，成局后服务端用 CmdMatchFoundNotify 0x0C02 把房间与实例 ID 推给客户端——命令号来自卷一定稿的报文头，本节只负责「队列内部」的算法。
第一件事是 rating 与期望胜率。Elo 公式只有一个 math.Pow，但它的价值在于纯函数：同样的两个分，永远得到同样的期望胜率，匹配与结算才能对得上账。下面这段是 L1，go test ./internal/match/ 可以直接跑：
// file: internal/match/rating.go
// tier: L1
// verify: go test ./internal/match/
package match
import "math"
// ExpectedScore 返回 A 对 B 的期望胜率（Elo 公式），值域 (0,1)。
// 纯函数：同样的两个分永远得到同样的期望值，这是匹配与结算可复现的前提。
func ExpectedScore(ratingA, ratingB float64) float64 {
return 1.0 / (1.0 + math.Pow(10, (ratingB-ratingA)/400.0))
}
// UpdateRating 按实际结果 actual（1 胜 / 0 负 / 0.5 平）把 rating 朝对手方向修正。
// k 越大对新结果越敏感；K=32 是「一局大约动 16 分」的常用口径。
func UpdateRating(rating, oppRating, actual, k float64) float64 {
return rating + k*(actual-ExpectedScore(rating, oppRating))
}
// RankCorrelation 用 Kendall tau-b 衡量两个序列的排序一致性，值域 [-1,1]。
// 我们用它验证「匹配收敛后 rating 是否真的排出了真实实力的次序」。
func RankCorrelation(a, b []float64) float64 {
n := len(a)
if n != len(b) || n < 2 {
return 0
}
var concordant, discordant, tiesA, tiesB float64
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
da := a[i] - a[j]
db := b[i] - b[j]
switch {
case da == 0 && db == 0:
tiesA++
tiesB++
case da == 0:
tiesA++
case db == 0:
tiesB++
case (da > 0) == (db > 0):
concordant++
default:
discordant++
}
}
}
denom := math.Sqrt((concordant + discordant + tiesA) * (concordant + discordant + tiesB))
if denom == 0 {
return 0
}
return (concordant - discordant) / denom
}
ExpectedScore 里 400 是 Elo 的经典尺度：分差 400 意味着强者约 10 倍胜率。RankCorrelation 是本节自己的验收工具——它比较「rating 排序」与「真实实力排序」，0 表示毫无关系、1 表示完全一致。有了它，「收敛」这个模糊的词就变成了一个能断言的数字。
队列与窗口：等待越久，越愿意将就
有了 rating，匹配器要决定「谁和谁配」。核心是窗口：刚进队的玩家只接受评分差很小的对手，等得越久窗口越大，直到封顶。窗口函数必须是时间差的分段线性函数，这样才能精确算出「拐点」。
评分函数 PairScore 同样必须是纯函数：不读时钟、不掷骰子，只吃两张票据。下面这段是 L1，和上一段同一个包：
// file: internal/match/matcher.go
// tier: L1
// verify: go test ./internal/match/
package match
import (
"math"
"sort"
)
// PlayerID 是全服唯一角色 ID（卷二共享类型，uint64）。
type PlayerID uint64
// Ticket 是一张排位请求票据。JoinedAt 用毫秒时间戳，决定等待时长与窗口放宽幅度。
type Ticket struct {
Player PlayerID
Rating float64
LatencyMS int
PartySize int
JoinedAt int64
}
// Config 是匹配器的全部可调参数。评分函数只读它，不做任何随机化。
type Config struct {
BaseWindow float64 // 刚进队列时可接受的评分差
GrowthPerSec float64 // 每多等 1 秒，窗口放宽多少评分差
MaxWindow float64 // 窗口上限，防止久等者配到任意对手
RatingScale float64 // 评分差的归一化尺度
LatencyScale float64 // 延迟差的归一化尺度
PartyScale float64 // 队伍人数差的归一化尺度
WeightRating float64
WeightLatency float64
WeightParty float64
}
// DefaultConfig 是《晨曦大陆》1v1 排位用的默认参数。
func DefaultConfig() Config {
return Config{
BaseWindow: 100,
GrowthPerSec: 50,
MaxWindow: 800,
RatingScale: 200,
LatencyScale: 60,
PartyScale: 1,
WeightRating: 1.0,
WeightLatency: 0.3,
WeightParty: 0.2,
}
}
// WindowAt 返回等待 waitMS 毫秒后允许的评分差上限。
func (c Config) WindowAt(waitMS int64) float64 {
if waitMS < 0 {
waitMS = 0
}
w := c.BaseWindow + c.GrowthPerSec*float64(waitMS)/1000.0
if w > c.MaxWindow {
w = c.MaxWindow
}
return w
}
// PairScore 给一对候选打分，越小越合适。纯函数：不读时间、不掷骰子，
// 因此同一个 (a,b) 在任何时候都得到同一个分，测试可以逐位比对。
func (c Config) PairScore(a, b Ticket, nowMS int64) float64 {
dr := math.Abs(a.Rating-b.Rating) / c.RatingScale
dl := math.Abs(float64(a.LatencyMS-b.LatencyMS)) / c.LatencyScale
dp := float64(absInt(a.PartySize-b.PartySize)) / c.PartyScale
return c.WeightRating*dr + c.WeightLatency*dl + c.WeightParty*dp
}
func absInt(x int) int {
if x < 0 {
return -x
}
return x
}
// Pair 是一次成局的产物：两名玩家与他们的匹配分。
type Pair struct {
A Ticket
B Ticket
Score float64
}
// Match 从等待队列里配出一批对局，返回成局的 pairs 与仍未匹配的 waiting。
// 策略：按等待时长升序（等最久的先挑），每个候选在窗口内找评分最小的对手；
// 窗口取双方中较严的一个——久等者的宽窗口不能把新玩家拉进悬殊对局。
func (c Config) Match(queue []Ticket, nowMS int64) (pairs []Pair, waiting []Ticket) {
remaining := append([]Ticket(nil), queue...)
sort.SliceStable(remaining, func(i, j int) bool {
if remaining[i].JoinedAt != remaining[j].JoinedAt {
return remaining[i].JoinedAt < remaining[j].JoinedAt
}
return remaining[i].Player < remaining[j].Player
})
used := make([]bool, len(remaining))
for i := 0; i < len(remaining); i++ {
if used[i] {
continue
}
best := -1
bestScore := math.Inf(1)
for j := i + 1; j < len(remaining); j++ {
if used[j] {
continue
}
w := math.Min(c.WindowAt(nowMS-remaining[i].JoinedAt), c.WindowAt(nowMS-remaining[j].JoinedAt))
if math.Abs(remaining[i].Rating-remaining[j].Rating) > w {
continue
}
if s := c.PairScore(remaining[i], remaining[j], nowMS); s < bestScore {
bestScore, best = s, j
}
}
if best >= 0 {
pairs = append(pairs, Pair{A: remaining[i], B: remaining[best], Score: bestScore})
used[i], used[best] = true, true
}
}
for i := range remaining {
if !used[i] {
waiting = append(waiting, remaining[i])
}
}
return pairs, waiting
}
两个刻意的选择值得说清楚。其一，排序键是等待时长而不是评分——「等最久的先挑」是公平性的一部分：如果按评分排序，高分段永远优先，低分段会被无限期饿死。其二，窗口取 math.Min 而不是 Max：久等者的宽窗口只对自己有效，不能强行把刚进队的新玩家拉进一场实力悬殊的对局，否则「放宽窗口」就变成了「牺牲新人」。
Match 的时间复杂度是 O(n²)，看起来朴素，但在单服队列（通常几十到几百人）下完全够用，而且它没有任何随机性——这正是可复现的基础。
收敛验证：rating 真的排出了实力次序吗
前两节给了算法，但「公平」还不能只说在嘴上。真正的验收是：让一批同分玩家互相打几百轮，看 rating 最终能不能把真实实力排出正确次序。测试里每个玩家有一个隐藏的 trueSkill，对局结果按 Elo 期望胜率用固定种子的 PRNG 掷出，再回写 rating。下面是 internal/match/matcher_test.go 里两段关键测试的摘录，属于同一个已跑通的 L1 包：
// snippet: internal/match/matcher_test.go（摘录）
// 同一个 (a,b) 在任何时刻都必须得到同一个分——可复现匹配的底线。
func TestPairScoreIsReproducible(t *testing.T) {
cfg := DefaultConfig()
a := Ticket{Player: 1, Rating: 1500, LatencyMS: 40, PartySize: 1}
b := Ticket{Player: 2, Rating: 1640, LatencyMS: 55, PartySize: 2}
first := cfg.PairScore(a, b, 1000)
for i := 0; i < 1000; i++ {
if got := cfg.PairScore(a, b, 1000); got != first {
t.Fatalf("第 %d 次评分 = %v，与首次 %v 不一致", i, got, first)
}
}
if cfg.PairScore(b, a, 1000) != first { // 评分必须对称
t.Fatalf("PairScore 不对称")
}
}
// 收敛验证：128 人同初始分，跑 400 轮后 rating 必须排出真实实力的次序。
func TestRatingConvergenceTracksSkill(t *testing.T) {
const (
n = 128
round = 400
k = 32.0
)
rng := rand.New(rand.NewPCG(7, 11))
trueSkill := make([]float64, n)
rating := make([]float64, n)
for i := range trueSkill {
trueSkill[i] = 1200 + rng.NormFloat64()*200
rating[i] = 1500 // 所有人同分：匹配器开局没有任何先验
}
cfg := DefaultConfig()
cfg.BaseWindow = 500 // 冷启动先放宽，让分差还没拉开时也能成局
cfg.GrowthPerSec = 200
before := RankCorrelation(rating, trueSkill)
for r := 0; r < round; r++ {
queue := make([]Ticket, 0, n)
for i := 0; i < n; i++ {
queue = append(queue, Ticket{Player: PlayerID(i + 1), Rating: rating[i],
LatencyMS: 30, PartySize: 1, JoinedAt: int64(r)})
}
pairs, _ := cfg.Match(queue, int64(r))
for _, p := range pairs {
ia, ib := int(p.A.Player)-1, int(p.B.Player)-1
pa := ExpectedScore(trueSkill[ia], trueSkill[ib])
actual := 0.0
if rng.Float64() < pa {
actual = 1.0
}
ra, rb := rating[ia], rating[ib]
rating[ia] = UpdateRating(ra, rb, actual, k)
rating[ib] = UpdateRating(rb, ra, 1-actual, k)
}
}
after := RankCorrelation(rating, trueSkill)
t.Logf("Kendall tau: 开局 %.3f -> 400 轮后 %.3f", before, after)
if after < 0.6 {
t.Fatalf("收敛后排序一致性 %.3f < 0.6，rating 没有排出实力次序", after)
}
}
TestPairScoreIsReproducible 把「可复现」钉死：同一个 (a,b) 跑 1000 次，分值必须逐位相同，而且交换两人不改变分值（对称性）。TestRatingConvergenceTracksSkill 则回答「准不准」：开局所有人都是 1500 分、排序一致性必然为 0，400 轮后如果 RankCorrelation 仍然很低，说明匹配与更新没能把实力差异「学」出来。
还有一条容易被忽略的验收：同一实验跑两次必须得到逐位相同的结果。TestConvergenceReproducible 用同一种子跑两遍 100 轮，逐位比对最终 rating——只要有一步用了全局 rand 或遍历 map 的顺序，这条就会红。
本节小结 / 实测结论
本机（Go 1.26.0，darwin/arm64）实跑结果：
$ go test ./internal/match/
ok aegis/internal/match 0.627s （19 个 test 全绿）
$ go test ./internal/match/ -run TestRatingConvergenceTracksSkill -v
matcher_test.go:142: Kendall tau: 开局 0.000 -> 400 轮后 0.861
128 人从完全同分出发，400 轮后 rating 与真实实力的 Kendall tau 达到 0.861——排序已经高度一致，剩下的偏差来自「同分冷启动阶段打了太多随机局」。窗口放宽的拐点也验证过：评分差 600 的一对，BaseWindow=100 / GrowthPerSec=50 下要等到 10000ms 窗口才覆盖得住，测试在 9000ms 断言「配不上」、10000ms 断言「配得上」。以上数字是同机相对量级，绝对数值不可移植，换一套 Config 会得到不同的 tau 与拐点。
匹配器只产出了「成局」这一个事件。成局之后房间怎么建、怎么在全员掉线时被回收，才是线上最容易出幽灵的地方——下一节看大厅生命周期。
阅读导航：上一节：目录 · 下一节：17.2 大厅生命周期：防幽灵房间 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。