README.md

fifo — 通用匹配引擎

fifo 是一个面向游戏场景的通用匹配引擎，核心职责是：将不断涌入的匹配请求（Ticket），按照可配置的规则，分组成若干队伍（Team），再将队伍两两/多方对阵后输出匹配结果。

---

目录

• 设计总览
• 核心概念
• 配置详解
• 使用方法
• 内置 FIFO 算法
• 过滤器系统
• 注意事项

---

设计总览

为什么要这样设计？

匹配系统在游戏服务器中面临几个核心矛盾：

1. 并发写入 vs. 单线程匹配：玩家请求在任意时刻从多个 goroutine 进入，但匹配算法本身涉及大量有状态的遍历和标记，多线程做匹配需要极其复杂的同步逻辑。
2. 多样的匹配规则 vs. 统一的引擎：不同的玩法（如不同赛季、不同战力段）需要不同的筛选条件，但匹配框架应保持一致。
3. 队内组队 vs. 队间对阵：匹配不仅要把散人凑成一队，还要把已组好的队伍配对对阵。

fifo 的设计针对以上矛盾做了如下选择：

输入队列与匹配缓存分离

              ┌─────────────────────────────────────────────────┐
              │                   Matcher                       │
              │                                                 │
  Submit() ──►│  inputQ (mutex)  ──mergeQ──►  Cache (串行)       │
  Cancel() ──►│                                     │           │
              │                            ┌────────┼────────┐  │
              │                         Pool A   Pool B  ... │  │
              │                            │        │        │  │
              │                         match()  match()     │  │
              │                            │        │        │  │
              │                            ▼        ▼        │  │
              │                      ResultSubmitter callback   │
              └─────────────────────────────────────────────────┘

• inputQ 是一个 sync.Mutex 保护的 map，任意 goroutine 可以随时调用 Submit() / Cancel() 往里写。
• 每个 Tick，匹配主循环调用 mergeQ() 把 inputQ 中的所有待处理项 一次性批量取出 合并到 Cache 中，之后 inputQ 清空，不再持有对这些 Ticket 的引用。
• 匹配算法只操作 Cache，是完全单线程的，无需加锁。

为什么？ 这样做把"并发安全"的边界收窄到 inputQ 一个点上。匹配算法可以随意修改 Ticket 的 used 标记等内部状态，不用担心并发问题。mergeQ() 每次是全量快照，语义清晰且不会丢数据。

多 Pool 分流

一个 Matcher 实例包含多个 Pool。每个 Pool 有自己的过滤器（Filter），每次 Tick 时，每张 Ticket 会被分发到所有满足条件的 Pool 中。

为什么？ 实际场景中，同一批玩家可能同时满足多个匹配规则。例如，一个战力 9,000,000 的玩家既属于"低段位"Pool（范围 0～10,000,000）又属于"中段位"Pool（范围 8,000,000～25,000,000）。让 Pool 之间有重叠，可以增大匹配成功率，避免卡在边界的玩家长时间等待。另外，可以利用 $wait 过滤器实现"先尝试精确匹配，等待超时后放宽条件"的渐进式策略。

算法可插拔

匹配算法通过 RegisterMatchFunction(name, func) 注册，MatchProfile.Algorithm 字段指定使用哪个。内置了 fifo 算法，业务可以注册自定义算法。

为什么？ 不同玩法对匹配质量/速度的权衡不同。有的场景需要 ELO 平衡，有的只需 FIFO 快速凑人。算法可插拔让框架和策略解耦。

---

核心概念

Ticket（匹配票据）

type Ticket struct {
    TicketId   string      // 整个匹配场里全局唯一 ID
    Members    []Member    // 这张票包含的玩家列表（至少 1 人）
    StringArgs []StringArg // 字符串类型的匹配参数
    IntArgs    []IntArg    // 整数类型的匹配参数
    FloatArgs  []FloatArg  // 浮点类型的匹配参数
    BlackList  []int64     // 黑名单，不会跟指定 member 匹配到同 team
}

一张 Ticket 代表一次匹配请求，可以是单人也可以是已组队的多人。例如：3 个人一起组队进入匹配，提交一张包含 3 个 Member 的 Ticket。

Member（成员）

type Member struct {
    MemberId string // 全局唯一的玩家 ID
    BlackId  int64  // 用于黑名单匹配的标识（必须为正数，0 值不合法）
    Extra    []byte // 额外数据，随匹配结果透传
    Sort     int    // >0 表示可选成员，匹配不成功时可被裁剪
}

Sort 字段的设计意图：当一个 Ticket 里有 4 人但队伍只需 3 人时，Sort > 0 的成员会被优先裁掉（Sort 值越大越优先裁掉）。Sort == 0 表示该成员是必选的。

MatchProfile（匹配场配置）

type MatchProfile struct {
    Name      string        // 匹配场名字，唯一标识
    Algorithm string        // 使用的算法名（如 "fifo"）
    Tick      string        // 匹配频率（如 "0.5s", "500ms", "2s"）
    Pools     []PoolProfile // 匹配池列表
}

PoolProfile（匹配池配置）

type PoolProfile struct {
    Name                    string         // 池名
    BetweenTeamAntiAffinity string         // 队间反亲和性（按 StringArg 的 key 来区分）
    StringFilters           []StringFilter // 字符串过滤器
    IntFilters              []IntFilter    // 整数过滤器
    FloatFilters            []FloatFilter  // 浮点过滤器
    Teams                   []string       // 需要匹配出多少支队伍（每个元素是队伍名）
    TeamMembers             int            // 每队人数
    MaxMatchPerRound        int            // 每轮最多匹配出多少组（必须 > 0）
    AllowCut                bool           // 是否允许裁剪队伍（丢弃可选成员）
    AllowHate               bool           // 是否考虑玩家黑名单
}

Teams 的含义：如果 Teams = ["blue", "red"]，表示每次匹配需要组出 2 支队伍对阵。如果 Teams = ["1"]，表示只需凑满一支队伍即为成功（如 PvE 场景）。

BetweenTeamAntiAffinity：指定一个 StringArg 的 key，拥有相同 value 的 Ticket 不会被分配到对阵的不同队伍中。典型场景：同服玩家不对阵。

MatchResult（匹配结果）

type MatchResult struct {
    PoolName string       // 来源于哪个池子
    Teams    []TeamResult // 匹配出的队伍
}

type TeamResult struct {
    TeamName   string         // 对应 PoolProfile.Teams 中的名字
    TicketId   []string       // 由哪些 Ticket 组成
    Members    []MemberResult // 最终成员
    CutMembers []MemberResult // 被裁剪掉的成员
}

---

配置详解

Tick 格式

Tick 支持以下时间单位后缀：

格式	含义	示例
ms	毫秒	"500ms" → 500 毫秒
s	秒	"0.5s" → 500 毫秒
m	分钟	"0.5m" → 30 秒
h	小时	"1h" → 1 小时

支持浮点数。解析失败时默认为 1 秒。

过滤器配置

StringFilter

{"arg": "season", "op": "=", "value": "s1"}

• op 支持 "=" 和 "!="
• 当 Ticket 缺少对应的 StringArg 时："=" 返回 false，"!=" 返回 true

IntFilter

{"arg": "power", "min": 8000000, "max": 25000000, "excludes": []}

• min 和 max 均为可选字段（指针类型 *int64）：
  • 同时设置：Ticket 的参数必须满足 min ≤ value ≤ max
  • 仅设置 min：只检查下界 value ≥ min
  • 仅设置 max：只检查上界 value ≤ max
  • 均不设置：不做范围检查（仅检查参数存在性和 excludes）
• excludes：参数值不能在该列表中
• 特殊内置参数：
  • "$wait"：当前时间 - Ticket 开始匹配时间（毫秒），用于实现"等待一段时间后才进入某个更宽松的 Pool"
  • "$member"：Ticket 的成员数量，用于按组队人数过滤

FloatFilter

{"arg": "score", "min": 1.0, "max": 100.0}

• 与 IntFilter 类似，min 和 max 均为可选字段（指针类型 *float64），支持单边过滤，无 excludes

---

使用方法

1. 创建 Matcher

int64Ptr := func(v int64) *int64 { return &v }

m, err := fifo.NewMatcher("my-game", fifo.MatchProfile{
    Name:      "ranked-5v5",
    Algorithm: "fifo",
    Tick:      "0.5s",
    Pools: []fifo.PoolProfile{
        {
            Name:             "normal",
            Teams:            []string{"blue", "red"},
            TeamMembers:      5,
            MaxMatchPerRound: 100,
            StringFilters: []fifo.StringFilter{
                {Arg: "season", Op: fifo.EqualOp, Value: "s1"},
            },
            IntFilters: []fifo.IntFilter{
                {Arg: "power", Min: int64Ptr(0), Max: int64Ptr(50_000_000)},
            },
            BetweenTeamAntiAffinity: "alliance",
        },
        {
            Name:             "relaxed",
            Teams:            []string{"blue", "red"},
            TeamMembers:      5,
            MaxMatchPerRound: 100,
            IntFilters: []fifo.IntFilter{
                {Arg: "$wait", Min: int64Ptr(5000), Max: int64Ptr(3_600_000)},
            },
            AllowCut: true,
        },
    },
}, func(result fifo.MatchResult) {
    // 处理匹配结果
    // 注意：回调在匹配主循环中同步执行，不应进行阻塞操作（如网络 IO、数据库写入等）
    fmt.Printf("匹配成功: pool=%s, teams=%d\n", result.PoolName, len(result.Teams))
    for _, team := range result.Teams {
        fmt.Printf("  队伍 %s: %v\n", team.TeamName, team.TicketId)
    }
}, func(ticket fifo.Ticket) {
    // 可选：匹配超时失败回调，当 Ticket 因超时被移除时触发
    // 注意：回调在匹配主循环中同步执行，不应进行阻塞操作
    fmt.Printf("匹配超时: ticket=%s\n", ticket.TicketId)
})
if err != nil {
    log.Fatal(err)
}

2. 启动匹配循环

ctx, cancel := context.WithCancel(context.Background())
go m.Start(ctx)

// 需要停止时
cancel()

Start() 是一个阻塞方法，会在独立的 goroutine 中持续运行，直到 ctx 被取消。

3. 提交 / 取消 Ticket

// 单人匹配
m.Submit(fifo.Ticket{
    TicketId: "ticket-001",
    Members:  []fifo.Member{{MemberId: "player-A"}},
    StringArgs: []fifo.StringArg{{Key: "season", Value: "s1"}},
    IntArgs:    []fifo.IntArg{{Key: "power", Value: 15_000_000}},
})

// 多人组队匹配（3 人组队，其中 1 人为可选）
m.Submit(fifo.Ticket{
    TicketId: "ticket-002",
    Members: []fifo.Member{
        {MemberId: "player-B", Sort: 0},  // 必选
        {MemberId: "player-C", Sort: 0},  // 必选
        {MemberId: "player-D", Sort: 1},  // 可选，可被裁剪
    },
})

// 带延迟和超时的匹配
m.SubmitWithTime(ticket, 2000, 30000) // 延迟 2 秒开始匹配，最多匹配 30 秒

// 取消匹配
m.Cancel("ticket-001")

4. 注册自定义算法

fifo.RegisterMatchFunction("my-elo", func(
    profile fifo.PoolProfile,
    teams map[string]*fifo.Ticket,
    now int64,
    r fifo.ResultSubmitter,
) {
    // 你的自定义匹配逻辑
    // 通过调用 r(result) 提交每一组匹配结果
})

// 在 MatchProfile 中引用
profile := fifo.MatchProfile{
    Algorithm: "my-elo",
    // ...
}

---

内置 FIFO 算法

fifo 是内置的先到先服务匹配算法。它的核心思路是贪心：优先从大组队开始凑人，尽可能快速匹配。

算法流程

第一阶段：队内组人 (search)
━━━━━━━━━━━━━━━━━━━━━━━━━━
1. 将 Pool 中所有 Ticket 按成员数量分桶：
   bucket[1] = [单人票据...]
   bucket[2] = [双人票据...]
   ...
   bucket[N] = [N人票据...]
   每个桶内按 startMatch（进入时间）升序排列

2. 从最大桶（N人）开始遍历到最小桶（1人）：
   - 取一个未使用的 Ticket 作为种子
   - 贪心搜索：从剩余空位数量对应的桶开始，寻找能填满队伍的 Ticket
   - 如果启用 AllowHate，检查黑名单
   - 如果启用 AllowCut，只要必选成员数 ≥ 需求人数即可成队
   - 凑满 → 生成一个 candidate（候选队伍）
   - 每轮结束清理已使用的 Ticket

第二阶段：队间对阵 (searchTeam)
━━━━━━━━━━━━━━━━━━━━━━━━━━━
（仅当 Teams 数量 > 1 时执行）

1. 如果配置了 BetweenTeamAntiAffinity，提取每个 candidate 的反亲和标签
2. 遍历 candidate 列表，尝试找到 N 个互不冲突的队伍
3. 冲突判定：如果两个 candidate 存在相同的 anti 标签，则不能对阵
4. 成功配对 → 通过 ResultSubmitter 输出结果

关键设计细节

为什么从大桶开始？ 大组队的 Ticket 更难匹配（可选组合更少），优先处理可以避免它们被后面的小票据"挤掉"空位。

AllowCut 的工作原理： 每个 Ticket 的成员分为两类：

• Sort == 0：必选成员，贡献 low 和 high 计数
• Sort > 0：可选成员，只贡献 high 计数

当 AllowCut = true 时，搜索空位的算法使用 need - low（还需要多少必选成员）来决定要找多大的票据；最终只要 low ≤ need ≤ high 即可成队。被裁剪的成员按 Sort 升序排序后截断，出现在结果的 CutMembers 中。

黑名单机制： 当 AllowHate = true 时：

• Ticket A 加入 candidate 后，记录自己所有成员的 BlackId 以及自己的 BlackList
• 新 Ticket B 要加入时，检查 B 的成员 BlackId 不在 candidate 已有的 hates 中，且 B 的 BlackList 不包含 candidate 中已有成员的 BlackId

匹配失败时的回退： 如果一个种子 Ticket 开始的搜索无法凑满队伍：

• 若非黑名单原因失败：释放所有已标记的 Ticket（used = false），让它们参与后续轮次
• 若因黑名单导致失败：不释放，因为这些 Ticket 可能对其他种子也有冲突

---

过滤器系统

过滤器决定一张 Ticket 是否进入某个 Pool。每个 Tick 时，所有 Ticket 会被重新分发到各 Pool，因此 过滤条件是动态评估的（这对 $wait 这样的时间相关过滤器很重要）。

内置伪参数

参数名	类型	含义
$wait	IntFilter	now - ticket.startMatch，单位毫秒。用于渐进式放宽
$member	IntFilter	len(ticket.Members)，用于按组队人数筛选

渐进式匹配示例

利用多 Pool + $wait 实现"先精确后宽松"：

int64Ptr := func(v int64) *int64 { return &v }

Pools: []fifo.PoolProfile{
    {
        Name: "strict",
        IntFilters: []fifo.IntFilter{
            {Arg: "power", Min: int64Ptr(20_000_000), Max: int64Ptr(30_000_000)},
        },
        TeamMembers: 5,
        // ...
    },
    {
        Name: "relaxed",
        IntFilters: []fifo.IntFilter{
            {Arg: "power", Min: int64Ptr(10_000_000), Max: int64Ptr(50_000_000)},
            {Arg: "$wait", Min: int64Ptr(5000), Max: int64Ptr(3_600_000)},  // 等待 5 秒后进入
        },
        TeamMembers: 5,
        AllowCut:    true,  // 允许缺人
        // ...
    },
}

效果：前 5 秒只在精确段位匹配；5 秒后同时进入宽松池，增大匹配概率。

---

注意事项

线程安全

• Submit() 和 Cancel() 是并发安全的，可以从任意 goroutine 调用。
• Start() 必须在单独一个 goroutine 中运行，不要对同一个 Matcher 实例多次调用 Start()。
• Cache 字段虽然是导出的（大写），但不要在 Start() 运行期间从外部直接读写它，它没有锁保护。

TicketId 唯一性

• TicketId 必须在整个匹配场中全局唯一。重复的 TicketId 会导致后提交的覆盖先提交的。
• Cancel() 使用 TicketId 标识要取消的票据。

Ticket 提交后不可修改

• Submit() 会复制 Ticket 值（参数是值类型），提交后修改原始 Ticket 不会影响匹配。但 Members 中的 Extra 字段（[]byte）是切片，底层数组是共享的——如果需要在提交后修改 Extra，请提前 copy。

AllowCut 与 Sort

• 如果 AllowCut = false，Sort 字段无实际效果，所有成员都视为必选。
• 如果 AllowCut = true 但所有 Member 的 Sort 都是 0，则效果和 AllowCut = false 一样——因为所有人都是必选的，不会有人被裁。
• 被裁剪的成员会出现在 TeamResult.CutMembers 中，业务侧需要自行处理这些玩家（如通知他们匹配失败或重新排队）。

Pool 的顺序

• Pool 按配置中的顺序依次执行匹配。前面的 Pool 匹配成功的 Ticket 会从 Cache 中移除，不再参与后续 Pool 的匹配。
• 因此，越严格的 Pool 应该放在前面，越宽松的 Pool 放在后面，避免宽松规则"抢走"应该精确匹配的玩家。

MaxMatchPerRound

• 该值限制的是 FIFO 算法中第一阶段凑出的 candidate 数量，不是最终输出的 MatchResult 数量。
• 设置合理的值可以防止单次 Tick 消耗过多 CPU，在大量玩家涌入时尤为重要。

延迟与超时

• SubmitWithTime(ticket, delay, timeout) 中的 delay 和 timeout 单位均为毫秒。
• delay：Ticket 在 delay 毫秒后才会开始参与匹配（通过 startMatch 时间戳实现，Pool 的 Allow() 方法会检查 now >= startMatch——注意：$wait 过滤器的值为 now - startMatch，delay 期间该值为负数，不会通过 Min > 0 的过滤器）。
• timeout：从开始匹配算起超过 timeout 毫秒后，Ticket 会在 mergeQ() 时被自动移除。timeout = 0 表示永不超时。

自定义算法的约定

注册自定义 MatchFunction 时需遵守以下约定：

1. 通过调用 r(result) 提交每一组匹配成功的结果（可以调用多次）。
2. 框架会自动根据结果中的 TicketId 从 Cache 中移除已匹配的 Ticket，算法不需要自行清理。
3. tickets 参数是该 Pool 的 Ticket 视图，算法可以修改 Ticket 的 used 标记，但不要从 map 中删除元素。
4. 算法执行时已经过 recover 保护，panic 不会崩溃整个 Matcher，但会跳过当前 Pool 本轮的匹配。