Elixir Advent Calendar 2016 の22日目です。
mixiグループ Advent Calendar 2016 の22日目も記載しているのでよければそちらもどうぞ
マッチングとは
ゲームにおいて、プレイヤーとプレイヤーを何らかの条件で（同程度の強さなど）によって結びつけることです。プレイヤーにとって面白いと考えられる対戦を作るのが目標になります。
良い対戦相手を見つけるには待ち時間が必要になります。キューに入ってきた順ではなく、同じ条件のユーザが揃うまで待つ必要があるからです。
そのため、クライアントには非同期で結果を返す必要があります。
Phoenix Channels
クライアントへ非同期に結果を返すために、Phoenix の Channels を活用します。WebSocket を抽象化しており、アプリケーション側から容易にメッセージパッシングを行えます。
また、Phoenix では WebSocket を扱うのに十分速いため実用として利用できます。
Phoenix Channels vs Rails Action Cable
Matching Server
Game Server はクライアントと WebSocket を繋いだあと、Matching Server に登録します。
Matching Server では、Matching Board に書き込むまでを行い、Game Server にはすぐにレスポンスを返してしまいます。
Game Server と Matching Server は別の Phoenix Application となってます。
Matching Worker
Workerは、Matching Board から、古いレコードを探してきて、別のマッチングポイントと結びつけます。結びつけが成功した場合、アプリケーション登録時に指定した Callback URL へ結果をPOSTします。結果が返ってきた Game Server は、さらに結果を WebSocket を通してクライアントへ通知します。
複数台の Game Server がある場合は、どのサーバに結果を POST しても問題無いように、Pub/Sub サーバを別途用意する必要があります。
Elixirを使うと、このWorkerもプロセスとして容易に実装できます。
多段 Worker
Worker は複数並べることができ、性格の異なる Worker を持てます。
今回の実装にあたっては、 Matching Board に登録したけど、なかなか相手が見つからないような場合、条件を緩和してマッチングを行うような Worker を追加しています。
スケールアウト戦略
一番難しい問題は、このシステムをどのようにスケールアウトさせるかです。
大量のユーザがマッチングを行うことを考えるとスケールアウトできる設計であることが重要です。
今回実際にマッチングを行う Worker は容易に横に並べることが可能です。
そのため、データベースである Matching Board をどのように横に並べるか、横に並べても問題ないように実装するかを考える必要があります。
DB を横に分割する
DB を横に分割する場合、競合が問題となります。今回のシステムで問題となる競合は2点あります。
* マッチングさせるべき起点ユーザを取得する
* 起点ユーザと結びつけるユーザを取得する
複数の DB に Transaction をかけることは（スケールアウトの観点から）できないため、レコード自体に State (Lock/Unlock) をもたせる必要があります。
今回説明は省きますが、マッチングの解除などユーザに対しての操作などがあるため、Transactionをかけやすいように DB はユーザのID単位でシャーディングしています
マッチングさせるべき起点ユーザを取得する
マッチング時間をなるべく減らしたいため、 Worker に触られていない時間が長いレコードを探してきます。
State が Unlock かつ、updated_at が一番古いレコードを見つけ、State を Lock に変更します。
複数の DB から一番古いレコードを見つけるのは難しいため、複数の DB からランダムに1台選び、単一DBの Transaction で上記の操作を行います。
厳密には一番触られていないレコードではないですが、複数の Worker でバランスされ実用上問題ないため許容しています。
起点ユーザと結びつけるユーザを取得する
複数の DB を触る必要があるため、単純に Transaction をかけることは出来ません。しかしながら、一番古いユーザを探す場合と比較して、競合自体は少ないと思われます。
レコードに lock_version を導入し楽観的ロックで実装します。（レコードの更新時に lock_version の値を調べ、他から更新が行われていないことを保証する)
Worker が死んだ場合
StateをLockにしたまま、Workerが死んでしまう可能性があります。その場合、このレコードは他から永遠に見つけられることがなくなります。
そのためZombieとなってしまうレコードを救う、Exorcist Workerを追加します。
Lockのまま、update_atが更新されないレコードはworkerが死んで放置されたと判断し、UnlockしていくWorkerです。
まとめ
以上の設計でマッチングシステムの実装を行いました。
Phoenix Channels や、 Elixir のプロセスを用いて容易に実装が行えます。
皆さん Phoenix 使っていきましょう！