Open MatchのBackfill機能

マッチメイキング実装のOSSであるOpen Match に Backfill という機能が追加された。 Backfill 機能の概要については公式ドキュメントに解説がある が、文章だけ読んでも実装が想像つかず結構苦戦したので Backfill 機能が作られた背景と自分なりの実装の解釈を解説する。

Backfill 機能が生まれた背景

Open Matchではプレイヤーのマッチ要求を Ticket という形で作り、他の Ticket とマッチするとそれぞれに接続情報が入る仕組みを持つ。

どのような条件のチケット同士がマッチするかは、 Match Function という独自実装可能な部分で決まる。 チケットの属性(Search Fields)を見て近い実力同士を優先的にマッチさせることができる。 そして、マッチングの人数も Match Function で自由に指定できる。 4人対戦のゲームであれば4つのチケットが見つかったら初めてマッチ成立するといったコードを書けばよい。

ここまででOpen Matchのマッチ機能を大まかに説明した。Match Functionの自由度が高いので様々なゲームに使えそうである。 しかし、3人以上のマッチを作るときに問題があった。 それは 人数が完全にそろうまでマッチ成立しないこと だ。 チケットの状態は「マッチしてない」か「マッチした」の2つだけで、進捗状況は外からは取得できない。 4人対戦のゲームだとしたら4人揃うまでプレイヤーはずっと「マッチ検索中」ということしかわからない。

こういった問題を解決するために Backfill という機能が追加された。

Feature Request: Backfill Support · Issue #1240 · googleforgames/open-match · GitHub

Backfill とは

Backfillは前述の問題を解決する機能だ。 チケットとは別に「空いた枠の埋め合わせを募集中」という意思の Backfill Object をOpen Matchに作り 多人数マッチ中の途中経過状態としても使えるし、離脱したプレイヤーの再募集枠としても使える。

f:id:castaneai:20210826142815p:plain

Backfill の作り方

Match構造体を作るときにBackfillフィールドに入れると同時にBackfillもOpen Match内部に作成できる。

backfill := &pb.Backfill{
    SearchFields: ...,
}

Backfillが持つフィールドは現時点では次の5つ。

Field Name
ID ID（Open Matchが自動的に入れてくれる）
CreationTime 作成時間（Open Matchが自動的に入れてくれる）
Generation Backfillの世代（Open Matchが自動的に入れてくれる）
SearchFields Backfillの検索条件
Extensions 拡張フィールド（ゲーム仕様に応じて自由な値を入れてよい）

Open Matchが自動的に入れてくれるフィールドは無視でいいとして、重要なのはSearch Fields（検索条件）だ。 新たに入ってきたチケットとBackfillをマッチさせるための判断に使う。

何人補充したいか という情報はどこに入れるべきか？ これはBackfillが進行するにつれて変化していくし、検索条件とは異なる扱いにしたい。 Open Matchのissueで質問してみると、 Extensions（拡張フィールド）に入れると良いよ、と助言をもらった。

https://github.com/googleforgames/open-match/issues/1240#issuecomment-746384697

Extensions はprotobufのAny型で何でもありなフィールドなので、ここに open-slots といった名前で入れると良さそう。

Backfillを作るタイミング

Bacfkillを作るタイミングの違いによってOpen Matchで実装する場所が変わる。

  • Match Functionでマッチ成立と同時にBackfillを作る
  • Game Serverがすでにある状態で、Game Serverからの要求でBackfillを作る

前者は部屋作成と同時補充を開始したい場合、 後者は人数がある程度揃ったあと、余った枠だけを補充したいとか、誰かが抜けた分だけあとから補充したい場合に使える。

Match FunctionからBackfillを作る

まず、マッチ成立（≒部屋を作る）と同時にBackfillを作る場合のパターンを解説する。 これはMatch構造体を作るときに中にBackfillを入れておくだけでよい。

match := &pb.Match{
    MatchId:       "...",
    MatchProfile:  "...",
    MatchFunction: "...",
    Tickets:       tickets,
    Backfill:      backfill,
}
match.AllocateGameServer = true

ひとつ注目なのが AllocateGameServer というフィールドがMatchに新しく増えたことだ。 true の場合だけ、Directorによる新しいサーバー割り当てが発生する。 Backfill中は すでにGameServerが存在していることが多いため、その場合は false にして新しくGameServerが作られないようにする。 使い方は後のDirectorの実装の項目で解説する。

GameServerからBackfillを作る

Backfill構造体を作るところは同じで、Open Match Frontend の CreateBackfill 関数を呼び出すとよい。

backfill, err := omFrontend.CreateBackfill(ctx, &pb.CreateBackfillRequest{Backfill: &pb.Backfill{
    SearchFields: ...,
}})
if err != nil {
    return err
}

Match Functionの実装

Backfillがない時代のMatch Functionは Ticket を入力として受け取り、成立したMatchを返すという実装だった。

f:id:castaneai:20201207143932p:plain

しかし、Backfillを実現するためにはTicketだけでなくBackfillも入力として受け取る必要がある。 従来は QueryPools という関数で入力チケットを受け取っていたが、 これに加えて QueryBackfillPools という関数も呼び出して入力Backfillを受け取る必要がある。

f:id:castaneai:20210826163722p:plain

そして、メインのマッチ成立判定部分ではチケットの属性を見てマッチ候補を探すだけでなく、 現在募集中のBackfill があればそこに入れる といった処理を追加しなければならない。

open-match公式のexamplesにそのようなMatch Functionの例 があり、簡易的に流れをかくと次のようになる。

var matches []*pb.Match

// 1. まず募集中のBackfillがあれば、チケットをそこに入れる
newMatches, remainingTickets, err := handleBackfills(profile, tickets, backfills)
if err != nil {
    return nil, err
}
matches = append(matches, newMatches...)

// 2. 次にTicket同士だけでマッチが成立しそうなら、そのままチケット同士をマッチさせる
newMatches, remainingTickets = makeFullMatches(profile, remainingTickets)
matches = append(matches, newMatches...)

// 3. それもダメなら、新しくBackfillを作る
if len(remainingTickets) > 0 {
    remainingMatch, err := makeMatchWithBackfill(profile, remainingTickets)
    if err != nil {
        return nil, err
    }
    matches = append(matches, remainingMatch)
}

もちろん必ずこうしなければならない、というわけではないので ゲームの仕様によってこの部分は自由に変えるとよい。

Directorの実装

Directorは成立したマッチを取得して新しいAssignmentを作る（＋GameServerを割り当てる）役割を持っていて、 ゲーム開発者が独自で実装する部分である。

従来のDirectorは、 FetchMatches 関数でマッチを取得して、AssignTickets 関数でマッチしたチケットにAssignmentを付けるという実装でよかった。

f:id:castaneai:20210826174535p:plain

しかし、Backfillを考慮するとDirectorの処理も少し変わってくる。 取得したMatchにBackfillが付属している可能性があるからだ。 Backfillがある場合は基本 新しいAssignmentを作らない1。

f:id:castaneai:20210826174559p:plain

ここの分岐がけっこう難しくて、3通りのパターンが生まれる。

  • Backfillがない場合（従来どおり）
  • 新しく作られたBackfillの場合（GameServerは新しく作るが、Assignmentは作らない）
  • すでに募集中のBackfillの場合（GameServerもAssignmentも作らない）

この3つの分岐をDirectorで実装してあげる必要がある。Backfillのissue内で擬似コード例が示されていた ので、この通りに書くとよさそう。 ここでMatch作成時の項目で説明した AllocateGameServer フィールドが使用される。

if match.Backfill == nil { 
         do the same actions as before.
} else if {
    if match.AllocateGameServer == true{
        AllocateGameServer as before but propagate match.Backfill.Id to the GameServer, 
                do not assign resulting tickets to the GameServer, they would be assigned by AcknowledgeBackfill
        } else {
            do not allocate and do not assign tickets
            some other regular logic like gather metrics and log
    }
}

GameServerの実装

GameServerはBackfillに対して新たに2つの処理が必要になる。

  • 新しくマッチしたプレイヤーにGameServerの接続先を教える
  • 現在のBackfillの状況を取得する

この2つの処理は AcknowledgeBackfill というAPIで実現できる。 図にすると以下のような流れになる。

f:id:castaneai:20210826141329p:plain

Backfillが続く限り、GameServerは ポーリングで定期的に AcknowledgeBackfill を呼び続ける。 これでほぼリアルタイムに新しくマッチしたプレイヤー（チケット）に接続先の情報が渡り、 同時にGameServerはBackfillの最新状況を取得できる。上で触れたExtensionsフィールドの状況がわかるので残り人数を把握できる。

そして補充が完了したら StopBackfill APIを呼んで募集を停止する。

具体的な実装例

こうやって振り返ると、あちこちで追加の実装が必要となり結構大変。

実際にBackfillを作ってGameServerにプレイヤーを補充していく様子を ローカルKubernetes環境でテストできるexampleを作ったので、具体的な実装が見たい方は参考にしてただければと思います。

github.com

READMEに沿ってテストを実行すると次のようにBackfillが次々と行われて3人のプレイヤーが揃い、 その後1人だけ切断し、足りない分をさらにBackfillで1人補充して再び3人揃う、という流れのログが出る。

=== RUN   TestCreateTicketWithBackfill
[GS: ...] 2021/08/26 11:34:41 start polling with acknowledge backfill
[GS: ...] 2021/08/26 11:34:41 acknowledge backfill (openSlots: 2)
[GS: ...] 2021/08/26 11:34:41 player connected (ticketID: c4jfrg0t9qe8h7ktv0q0) (1 players in room)
[GS: ...] 2021/08/26 11:34:43 acknowledge backfill (openSlots: 1)
[GS: ...] 2021/08/26 11:34:43 player connected (ticketID: c4jfrg8t9qe8h7ktv0qg) (2 players in room)
[GS: ...] 2021/08/26 11:34:44 acknowledge backfill (openSlots: 0)
[GS: ...] 2021/08/26 11:34:44 player connected (ticketID: c4jfrgot9qe8h7ktv0r0) (3 players in room)
[GS: ...] 2021/08/26 11:34:44 backfill stopped (backfillID: c4jfrgfvlk4o0ha88al0)
[GS: ...] 2021/08/26 11:34:44 player disconnected (ticketID: c4jfrg0t9qe8h7ktv0q0) (2 players in room)
[GS: ...] 2021/08/26 11:34:44 backfill created (backfillID: c4jfrh0t9qe8h7ktv0rg, openSlots: 1)
[GS: ...] 2021/08/26 11:34:44 start polling with acknowledge backfill
[GS: ...] 2021/08/26 11:34:44 acknowledge backfill (openSlots: 1)
[GS: ...] 2021/08/26 11:34:45 player connected (ticketID: c4jfrh0t9qe8h7ktv0s0) (3 players in room)
--- PASS: TestCreateTicketWithBackfill (4.72s)
PASS
ok      github.com/castaneai/openmatch-local-dev/tests  5.064s

  1. 「GameServerの実装」で登場した AcknowledgeBackfill APIが内部で AssignTickets と同じ処理をやっているのでDirectorから呼ぶ必要がない↩