こんにちは、こんばんわ、正統派近代小説感覚2D対戦アクションUNDER NIGHT IN-BIRTHではオリエを使っていますが、最近はミカに浮気中です。谷脇です。
この記事はTech KAYAC Advent Calendar 2020の7日目の記事です。長くなってしまったので8日目もお借りして前後編でお送りします。
昨日は@commojunさんの6年続いているサービスのPerlのバージョンを5.16から5.30へと今にもアップデートさせようとしているでした。この話で上がっているサービスのリリース時から私は携わっていたので、残してきた負債を回収してくれて、申し訳なさとありがたいと感慨深いが同時に来る感じで読ませていただきました。
さて、私は最近、ゲーム大会のエントリーから大会進行、トーナメント表構築に至るまで誰でも！かんたんに！開ける！参加できる！Tonamelというサービスのサーバサイド開発に携わっております。
先日、ダブルエリミネーション形式に対応したので、その時の苦労やら、やってよかったこととかを話します。
この記事を読んでほしいなと思う方
- Go言語で複雑な実用アプリケーションを作るときの設計手法が知りたい方
- のっぴきならない事情により何らかの大会のトーナメント表を作りたいなと思う方
- しかしできればTonamelを使ってほしい！最近はゲーム大会だけではなくスポーツチャンバラの大会でも使われています
- Tonamelを使っていて裏側どうなっているんだろうという興味がある奇特な方
ダブルエリミネーション形式とは
普段、我々が"トーナメント"と書いて思い浮かぶ表があるとします。Tonamelの画面だとこれですね。
目にするときは反時計回りに90度回転させた状態なときもあれば、左右に1回戦があって真ん中に決勝戦があるタイプのものもありますが、トポロジーとしては同じです。勝てば次のラウンドに進めるが、負ければそこでおしまいという方式ですね。これは16人シングルエリミネーションの例です。
この大会形式を"シングルエリミネーション"と呼びます。勝ち抜き戦と呼ぶこともあります。日本語では"トーナメント"と言えばこれですが、英語のTournamentが指す範囲はもっと広く、大会自体を指します。
では、"ダブルエリミネーション"とはどういう形式でしょうか。今回実装したものを紹介します。どん！
シングルエリミネーションの例で示した16人だと縦幅がでかくなるので、半分の8人にしております。
シングルエリミネーションとパッと見て違う点として、2つのトーナメント表ができていますね？ 上はシングルエリミネーションに近い形ですが、下はよくわからない。
この2つの表は実はつながっています。というのも、シングルエリミネーションは「1回負けると終わり」という形式でしたが、ダブルエリミネーションは「1回までなら負けてもOK、2回負けると終わり」という形式です。よく見ると、上の"勝者サイド"の対戦カードには敗者は"敗者サイドの#◯◯に行く"と書かれたアンカーがくっついており、下の"敗者サイド"には"勝者サイドの#◯◯の敗者がここに入る"と対戦カードに書かれています。
最後まで進行してみるとこんな感じ。
よく見ると勝者サイド1回戦で負けた人が敗者サイド1回戦に配置され、その人達の中で戦っています。2回戦で負けた人も、敗者サイド2回戦に行きます。これをその後も似たような形で続けることで、「1回までなら負けてもOK」な形式を実現します。そして、敗者サイドの決勝で勝った人が、勝者サイド決勝で勝った人と組み合わされてグランドファイナルを戦います。
ここで、おや？と思う方もいると思うんですが、上記の例だとグランドファイナルが2回あります。2つ目のグランドファイナルはリセットと呼ばれていて、グランドファイナルで敗者サイドの人が勝利した場合に、勝者サイド優勝の人にも「1回までなら負けたらOK」という権利を適用するために存在します。勝者サイド優勝の人はグランドファイナルが始まる時点では負けてませんからね。大会開催の流派(?)にもより、リセットがない場合の大会もあります。今のところTonamelはリセットありのダブルエリミネーションしか作れません。
今回何を実装したの？
リリースが告知されたときの公式アカウントのツイートがこちら。
主催者の皆様、大変お待たせいたしました！本日、ダブルエリミネーション形式を正式にリリース致しました！ダブルエリミネーションを心待ちにされていた方も、これまでシングル/スイス形式がメインで運営されてきた方もこれを機に是非お試しください。https://t.co/3ZjCp3ea5h pic.twitter.com/cdQY0EQNRn
— 【公式】Tonamel（トナメル） (@TonamelJP) 2020年11月26日
このツイートのスレッドにもくっついているんですが、従来から存在していたシングルエリミネーション形式もリニューアルしています。もう一つ、Tonamelにはスイスドロー形式もあるんですが、これはそのままです。
従来のものと比べると、フロントエンド側はかなり別物なんですが、サーバサイドも別物で、以下の項目を実装しました。一部実装し直し(再実装)もあります。
再実装したもの
- シングルエリミネーションのトーナメント表構築
- シングルエリミネーションの進行管理
- シングルエリミネーションの順位付け
- 実は結果のCSV出力という機能もあり、順位はそこで使われています。そちらもまるっきり別物になっています
- 抗議や10分間未アクセスアラートなどの主催者向けアラート類
新規実装したもの
- ダブルエリミネーションのトーナメント表構築
- ダブルエリミネーションの進行管理
- ダブルエリミネーションの順位付け
なぜ再実装したの？
実はTonamelは前の名前のLobi Tournament時代も含めると歴史が長く、2017年ごろから運用されています。
そして、当初からあるトーナメント表はPerlのモノリシックアプリケーションで実装されていました。今回はそれをGoで実装し直しています。Goで実装した理由としては、
- PerlでGraphQLを捌く際のCPU負荷に困っていた
- フロントエンドとの通信はGraphQLを使用している。一部サーバサイドでテンプレート生成していた
- だいたい型解決にCPU使っていたのはわかっていたので、大部分を静的に解決できるGoでなら性能が向上する見込みがあった
- バックエンドデータストアにAmazon DynamoDBを使用したかった
- Perl側はAmazon Aurora MySQLを使用していた
- Tonamelは平日日中など大会がない時間はほとんど負荷がないが、大きな大会が集中する週末にドカンと負荷がかかる特性がある
- 週末に合わせて今まではDBのインスタンスサイズを設定していたが、平日日中は暇しててほぼ無駄だったので、負荷に合わせて自由にスケールするデータベースをNoSQL含めて検討した結果DynamoDBを選択した
- PerlでDynamoDBは社内でも実績がなく、ライブラリもあまりないようなので選択しづらかった
- ダブルエリミネーション形式みたいな複雑なアプリケーションを型がゆるい環境で実装仕切る自信がなかった
- Goで複雑なアルゴリズムを伴うアプリケーションを作る経験は昨年していた 新マスタデータ管理システムakashicの開発 - KAYAC engineers' blog
というわけで、既存実装を流用するのは言語が違うので出来ないので、参考にしつつ今のユースケースに合わせて仕様自体を変えている箇所もあります。そのへんを以下では紹介していきます。
シングルエリミネーションをキレイに組む手法
キレイに組むのは本質的に難しい
私は、だいたいの世の中のWebアプリケーションはブラウザから値を受け取って、やばい値だったら弾いて、OKだったらDBに保存し、別のタイミングでDBから取り出していい感じに加工してブラウザに返す、という単純な流れの繰り返しであって、難しいアルゴリズムを実装するぞ！となることはあまりありません。そうなった場合、設計が変に難しくないか、仕様が無駄に難しくなってないかを疑い、実装しやすく、かつやりたいことを実現できる形に曲げることが多々あります。
しかし、シングルエリミネーションの実装というは"本質的に難しい"側に入ります。本質的に難しいというのは、「難しいことやってるんだから実装も難しくなる」ということを言っていて、それでいて「難しいことをやりたいんだからこのシステムに価値があるんだよ」ということでもあります。Tonamelはトーナメント表を簡単に作れて、それを実際に動かせるからみんな使ってくれているという理解です。なので、難しい実装をやることは避けられません。
以前と以後
何が難しいのか。ずばりいうと人ではないトーナメント表を、キレイに組むのが難しい。先程の例で見せた16人や8人は
でした。また、Tonamelの前のシングルエリミネーションでは、参加人数よりも大きい[tex: 2n]のトーナメント表を作成し、人が足りない部分にはBYEと表記し不戦勝とすることで対応していました。
このやり方は実装の観点で、比較的考慮することを少なく出来、理にかなっています。しかし見づらいという意見もあり、難しい方を実装するのにチャレンジする、つまりいわゆるシードを含んだ形のトーナメントをわかりやすく構築したいと私は考えました。
というわけで実装した結果はこうなります。
このデータはもともと冗長なBYE入りのトーナメント表をクライアントサイドで切り捨てているのではなく、サーバサイドで初めからこの結果を生成しています。
設計戦略と実装
複雑なアプリケーションを組むために以下の図に示すような設計を採用しました。
いわゆるレイヤードアーキテクチャです。左端がGraphQL処理部で、ブラウザに対して一番近い部分で、右端のCombinationモジュールが設計上もっとも奥に位置します。なぜレイヤーを分けるかというと、レイヤーごとに出来ることを限定させたいからです。出来ることを限定すると、責務が分割され、レイヤーごとに考えることが狭まり、コードの見通しが良くなります。
抽象化によって得られる考えることが少なくなる例: 順番付け
具体例を示します。左端のCombinationはトーナメント表構築を司ります。最もコアなモジュールであると言えますが、ここでは参加者の情報や、どうやってフロントエンドで表示すべきかの情報は持っていません。また、内部的には表示順を持っておらず、Matchmakerに渡すときに初めて決定するようになっています。表示順を持たないことは、Combination内部での操作時にトーナメント表操作時に、順番の再計算を行うことを省略できます。
ただし、当初は毎回順番を計算すると、変換のたびに順番が変わってしまって動作の一貫性がないことがありました。というわけで今は以下の図のような、"右"と"左"の概念を与えています。
左右とは、親の対戦ノードから見た相対位置です。相対位置なので、親の更に隣のノードを見て順序付けを見る必要はなく、自分が親から見て右にいるのか左にいるかだけで判断ができます。
そして、対戦の順番付けを行う際に、決勝戦から見て右、左、さらにその子供の対戦ノードを右から右、左...と見ることで一貫した順序付けが出来ます。
ちなみに、Combinationの中ではこのトーナメント表の管理をgonumのgraphパッケージの有向グラフで表現しています。本来は数学のグラフ理論で使われるパッケージで、A*で経路探索なんかも出来るものです。機能的にはtoo matchなのですが、ノードの追加削除の速度的には本番アプリケーションで使用できるので、グラフを操作するために採用しています。
偏りのないトーナメント表を組むアルゴリズム
ここまで抽象度を上げると、あとはトーナメント表の形(具体的な順番や参加者が入っていないこの段階をトポロジーと私は呼んでいます)にのみ意識を集中して取り組むことが出来ます。人ではない参加者であっても、偏りのない綺麗なトーナメント表を組むアルゴリズムを考えてみます。
決勝戦のノードに参加者ノードを放り込むと、形に応じて勝手に子供の対戦ノードを生やしていくインターフェイスを考えます。これで参加者を投入する側は、対戦ノードの状態を考えなくて済みます。
各対戦ノードには、自分にぶら下がる参加者が何人いるかを記録しておきます。
根本の対戦ノード(=決勝戦)に、参加者が放り込まれたときに、自分の子供の対戦ノードのうち人数が低い方に、参加者をパスします。これを下まで再起で繰り返し、1人以下のときに自分の子ノードとして参加者を入れます。また、2人のときは、子供の対戦ノードを作成し、もともといた2人をそちらに移した上で、放り込まれた新しい参加者を自分の子ノードにします。さらに、自分の持っている参加者が3人かつ、対戦ノードが1つの場合は、新しく子供の対戦ノードを作成し、もともといた1人と新しい参加者をその子ノードにします。
これを繰り返すと勝手にバランスが取れた木が出来上がります。難点として、イチから作成ではなく、すでにあるトーナメントのデータをgonum/graphの形式に変えるときですが...それはあまり工夫無く力技でノードを貼っつけていってます...ときには力も必要...やはり腕力は大事...。
今日はここまで
明日は「圧縮と展開」という特徴的な機能についての話と、本丸のダブルエリミネーション敗者サイドの話についてお話します。お楽しみに。
