アプリボット制作の Legend of Cryptids は、2012 年 10 月にアップル社の北米
App Store ゲーム部門ランキング#1を記録

このケースでのランキング処理の要件は、以下の通りシンプルです。

• ゲームには数 10 万のプレイヤーが参加している
• プレイヤーが敵を倒すたびにスコアが増える。ピークで毎秒 300 件程度の更新が発生する
• トップページ上に常に最新のプレイヤーランキングを表示したい

スケーラビリティやレスポンスの速さが求められないのであれば、ランキングの取得は難しくはありません。たとえば Cloud Datastore 上で以下のようなクエリを実行します。

SELECT count(*) FROM Players WHERE Score > プレイヤーのスコア

このクエリは、特定のプレイヤーよりスコアの高いプレイヤーをすべてカウントします。しかし、プレイヤーが数 10 万人を超える規模のゲームで、プレイヤーがトップページにアクセスするたびにこのようなクエリを毎回実行するのは現実的でしょうか？　鈴木氏はまずこの方法を試しましたが、レスポンスを得るのに数秒かかってしまいました。これでは遅すぎる上、実行コストも高く、プレイヤー数が増えるほど性能が落ちてしまいます。

もっとも簡単な方法は、全プレイヤーをスキャンすること

鈴木氏は Google App Engine の Memcache サービス（メモリ キャッシュ）でランキングデータを保持する方法も検討しました。しかし Memcache サービスはレスポンスはきわめて速いものの、あくまでキャッシュである以上データの永続性がなく、万が一の障害時やメンテナンス時にはデータが失われる可能性がつきまといます。

結局、鈴木氏はすべてのプレイヤーのスコアをスキャンしてランキングを算出するバッチ処理を 1 時間に 1 回実行する方法を選択しました。この方法では、表示されるランキングは最大で 1 時間前の内容となってしまいます。

O(log n) アルゴリズムを探す
上述のような単純なクエリを使う方法では、プレイヤーより高いスコアを持つすべてのプレイヤーをスキャンしなければなりません。このアルゴリズムの計算量は O(n) です。すなわち、クエリの実行時間はプレイヤー数の増加に比例して増加するため、スケーラビリティの高い方法とは言えません。今回の要件を満たすには、計算量が O(log n) になるような、プレイヤー数の増加が処理時間にあまり影響を及ぼさないアルゴリズムを探す必要があります。

コンピュータサイエンスの授業を受けたことがある方なら、二分木、赤黒木、B 木などのツリー アルゴリズムを用いることでデータの探索を O(log n) 時間で実行できること覚えているでしょう。ツリー アルゴリズムは、集約した値を個々のブランチ ノードに置くことにより、ノードの数や最大値／最小値、平均値などの様々な集計にも応用できます。

この特性を利用して Google のエンジニアが Cloud Datastore 向けに実装したオープンソースのランキング処理ライブラリが、Google Code Jam Ranking Library です。Google Cloud Platform が提供する プラチナサポートプログラム に基づいて鈴木氏からの相談を受けた筆者は、鈴木氏のランキング問題を解決する手段としてこのライブラリの評価を行いました。

Google Code Jam Ranking Library を活用し、探索木でスコアランキングを取得

整合性確保と更新スループットのトレードオフ
しかし負荷テストを行う中で、筆者は Google Code Jam Ranking Library の問題点を発見しました。同ライブラリは、ツリーからランキング情報を取得する処理のレスポンスはたいへん速いものの、ツリーに対する更新処理のスループットがかなり低いことがわかったのです。負荷テストによる更新処理を毎秒 3 件より上げると、ライブラリはリトライ エラーを返すようになりました。この状況では、アプリボットの要件である毎秒 300 件の更新をこのライブラリで実現できないことは明らかでした。

なぜ毎秒 3 件程度の更新でリトライ エラーが発生するのでしょうか？ その理由は、ツリーの整合性を維持するためにあります。Datastore では、複数行を更新するトランザクションにおいて強整合性（Strong Consistency）を確保する仕組みとして、エンティティ グループとよばれるメカニズムを提供しています（エンティティ グループについて詳しくはドキュメント「Balancing Strong and Eventual Consistency with Google Cloud Datastore」を参照してください）。Code Jam Ranking Library ではツリー全体を 1 つのエンティティ グループに収めることで、ツリーの整合性を確保する設計になっています。

しかし、エンティティ グループには性能に限界があります。Datastore ではすべてのデータを必ず 3 台以上のサーバーに同期書き込みして高い可用性と永続性を提供するため、加えて強整合性も保証するエンティティ グループについては、1 つにつき毎秒 1 件のトランザクションしか処理できません。もしこの 1 秒の間に同じエンティティ グループに対して他のトランザクションによる書き込みの競合が発生すると、後者の処理はキャンセルされてリトライエラーが発生します。この楽観的排他制御（optimistic concurrency）により、整合性を確保する仕組みです。

つまり Code Jam Ranking Library は、Datastore 上でツリーアルゴリズムを実装することで優れたレスポンスと高い整合性、可用性、永続性を提供するものの、更新処理のスループットはあまり高くないライブラリであることがわかりました。

Datastore チームの解決法：ジョブ アグリゲーション
こうした課題を背景に筆者が米国本社の Datastore チームに問題の解決方法についてアドバイスを求めたところ、同 チームからは「ジョブ アグリゲーション」パターン利用の提案がありました。

ジョブ アグリゲーションでは、多数の更新処理をひとつのトランザクションに集約し、単一のバッチ処理スレッドで実行します。エンティティ グループに同時アクセスするスレッドが 1 つしかないため、トランザクションの同時実行にともなうリトライ エラーやロック待ちは発生しません。そのため、データ構造の整合性を確保しながら高い更新スループットが得られます。ただしトレードオフとしてスレッド数が 1 つに制限されるため、スケーラビリティを際限なく高めることはできません。これと同様のアイデアは VoltDb や Redis のような他のストレージ製品にも見られます。

Datastore チームからのアドバイスに基づき、筆者はジョブ アグリゲーション パターンと Code Jam Ranking Library を組み合わせたサンプル コードを作成しました。App Engine の分散キューサービスである Task Queue を使用して複数の更新処理をタスクとしてキューに保存します。一方、バックエンドでは単一のスレッドで一回あたり最大 1000 件までのタスクをキューから取り出すバッチ処理を実行します。この複数の更新内容を Code Jam Ranking Library にまとめて渡し、全体を 1 つのトランザクションとして実行します。この仕組みにより、上述のようなリトライエラーは一切発生せずに、毎秒 1 件をケタ違いに上回る更新処理が可能になります。

下記のグラフは、サンプルコードを用いた負荷テストの結果です。今回はキューのスループットの変動を最小限に抑えるため、キューのシャーディング（分散化）も組み込みました。最終的にアプリボットに提案したソリューションでは、数時間にわたり毎秒 300 件の更新を処理できることを確認しました。個々の更新内容は、リクエストを受けてから 5 秒程度で Datastore に反映されます。

サンプルコードの性能グラフ

結果的にこのソリューションでは、数 10 万人のプレイヤーを有するゲームサイト上で、毎秒 300 件ほどのスコア更新処理を扱いながら、高い整合性と可用性、永続性を備えたランキング処理を 5 秒ほどの遅延で実行するという要件に応える実装を提案できました。またここで紹介したジョブ アグリゲーション パターン以外にも、線形補間等のアプローチによるいくつかのソリューションも合わせて提案しています。その詳細については「Fast and Reliable Ranking in Datastore」をご覧ください。

注記
本記事で公開されている性能数値は参考用のサンプル値であり、App Engine、Datastore、または他のサービスの絶対性能を保証するものではありません。