Amazon ElastiCache for Redis でリアルタイムゲームリーダーボードを構築する

ゲームリーダーボードを使用すると、プレイヤーは互いのパフォーマンスを比較できます。この重要なソーシャル機能により、プレイヤーの関わり合いが高められ、競争が促進されます。リーダーボードのデータは、同様のスキルレベルの競争相手とプレイヤーをマッチングさせるゲーム内のアルゴリズムに活かすこともできます。

この記事では、伝統的なリレーショナルデータベースを使用してゲームリーダーボードを構築および拡張することに関する課題を探ります。また、Redis などの最新のインメモリデータストアを活用して、非常に効率的でスケーラブルなソリューションを提供する方法についても検討します。

この提案されたソリューションは、リーダーボードストレージとクエリをリレーショナルデータベースからより汎用性の高い Amazon ElastiCache for Redis に向かうことを後押しします。ここで概説したアプローチは、ゲームリーダーボードだけでなく、一般にアプリケーション内でランキングを生成するあらゆる状況に適用されます。

背景

従来のリレーショナルデータベースを使用して基本的なリーダーボードを構築する手順はシンプルです。通常、以下の手順が含まれます。

テーブルを作成します。
スコアが変更されたときにスコアを挿入または更新します。
テーブルをクエリして、スコアの降順でランキングを取得します。

以下が基本的なリレーショナルデータベースのリーダーボードの実装です。

+---------+---------+------+-----+---------+-------+
| Field   | Type    | Null | Key | Default | Extra |
+---------+---------+------+-----+---------+-------+
| user_id | int(11) | NO   | MUL | NULL    |       |
| score   | int(11) | NO   | MUL | NULL    |       |
+---------+---------+------+-----+---------+-------+

このテーブルは最も基本的なリーダーボードスキーマを例示したものです。実装によっては、別のゲームを参照するための game_id 値、または同点のスコアの順位付けをするためのタイムスタンプなど、より多くの情報を追加することがあります。けれども、リーダーボードをクエリおよび更新する方法の基本的なコンセプトは変わりません。

以下、基本的なリーダーボードを実行するための create table スクリプトを示します。

CREATE TABLE `leaderboard` (
  `user_id` int(11) NOT NULL,
  `score` int(11) NOT NULL,
  KEY `idx_score` (`score`),
  KEY `user_id` (`user_id`),
  CONSTRAINT `leaderboard_ibfk_1` FOREIGN KEY (`user_id`) REFERENCES `users` (`id`) ON DELETE CASCADE

この例では、より速い集計と順位付けのために user_id にインデックスを追加し、スコアを付けました。スコアは、次のようなアトミック SQL ステートメントを使用して増減されます。

update leaderboard set score=score+1 where user_id=<user_id>;

同時ゲームユーザーの数が少～中程度の人数のままである限り、この設計により十分なリーダーボード機能が提供されます。ただし、同時ゲームアクセスが増加すると、次のスキーマは拡張が困難になります。

ランク計算は、大きなテーブルでは計算コストが高くなります。
特定のプレイヤーのランキングは、すべての相対的なリーダーボードの順位の計算を必要とします。
リーダーボードのバッチモード生成と結果のキャッシュは、繰り返し発生する計算の影響を軽減しますが、全体的なユーザーエクスペリエンスには影響します。

特定のプレイヤーのランク計算は、特に大きなテーブルの場合は、コストがかかる可能性があります。たとえば、次のようなクエリを検討します。

SELECT *,(SELECT COUNT(*) FROM leaderboard l2 WHERE l2.score>=l1.score) RANK FROM leaderboard l1 WHERE l1.user_id=<user_id>;

ユーザーのランキングを計算するためのネストしたクエリを考えると、時間の複雑さは二次的です。インデックスがあっても 5000 万件のレコードを持つテーブルに対してクエリを実行するのに平均 35 秒かかります。スコアとランキングは常に変化しているため、結果を簡単にキャッシュすることはできません。

理想的なソリューションは、ユーザー数が増えていっても予測可能なパフォーマンスを提供することです。また、そのようなソリューションは、遅くて複雑なクエリに頼る必要なしに、一般的なリーダーボード関連の操作 (たとえば、最低スコアの検索、またはスコアによる類似のプレイヤーの検索) を容易に行えるようにします。

Redis は、非常に効率的でスケーラブルなソリューションを提供します。Redis は、基本的なキーと値の機能をサポートするインメモリデータストアです。ハッシュ、リスト、セット、ソートセット、範囲クエリ、地理空間インデックスなど、さまざまなデータ構造もサポートしています。これは、リレーショナルデータベースを介さずに、ElastiCache for Redis を介してストレージとクエリを行うことに潜在的な利点があることを示唆しています。

ElastiCache for Redis アプローチには、以下の利点があります。

他の種類のリクエストのためにデータベースリソースを解放します。
簡単にはキャッシュされないデータに適した高いリクエスト率を実現します。
リーダーボードのユースケースを処理するために最適化されたデータ構造をサポートします。

ElastiCache の紹介

ElastiCache は、Memcached または Redis のいずれかをサポートする、低レイテンシーの完全マネージド型インメモリデータストアです。ElastiCache を使用すると、プロビジョニング、セットアップ、パッチ適用、設定、監視、バックアップ、および障害回復などの管理タスクの面倒を見てくれるので、アプリケーション開発に集中できます。

Redis に固有の ElastiCache では、読み取りと書き込みの両方を「拡大」または「縮小」できます。クラスターモードでは、シャードのサポートが追加され、書き込みのスケーリングが可能になります。最大 250 のシャードをサポートし、最大 170.6 TB のインメモリデータを提供します。オンラインクラスターサイズを変更することにより、シャードの内外でゼロダウンタイムスケーリングが可能になります。Amazon CloudWatch アラームに応じてスケーリングを自動化することもできます。読み取りをスケーリングするには、読み取りレプリカを追加するだけです。

ソートセットの紹介

ソートセットには、関連スコアを持つメンバーのリストが含まれています。セットメンバーは一意ですが、スコア値は繰り返すことができます。スコアは、リストを昇順にランク付けするために使用します。

ソートセットとリレーショナルデータベースの大きな違いの 1 つは、ツールがリストをソートするときです。挿入または更新操作中に、ソートセットは自動的にアイテムを正しい順序に配置します。この事前ソートのため、クエリの実行はかなり高速化されます。迅速かつ効率的にリストの中身をクエリしたり、特定のメンバーのランクを取得したりすることができます。ソートセットは、メンバーの数に比例して、対数的に特定のランキングを見つけます。

対照的に、リレーショナルデータベースはクエリ中にアイテムを順序付けし、データベースに計算上の負担をかけます。特定のプレイヤーのランクを取得するには、二次的な時間上の複雑さが伴います。

以下は、リーダーボードを構築するためにソートセットで実行できる主なコマンドです。

ZADD – 新しいメンバーをソートセットに追加するか、リストに既に存在するメンバーのスコアを更新します。
ZRANGE – 昇順でソートされ、ランク範囲 (インデックス付けなし) を使用してフィルタ処理されたメンバーの範囲を取得します。逆順にするには、ZREVRANGE を使用します。
ZRANK – メンバーのランク (インデックス付けなし) を取得します。このランクは昇順です。降順にするには、ZREVRANK を使用します。
ZRANGEBYSCORE – ZRANGE のように機能しますが、スコアをフィルタリングします。逆順にするには、ZREVRANGEBYSCORE を使用します。
ZSCORE – メンバーのスコアを取得します。
ZREM – リーダーボードからメンバーを削除します。

単語「rev」を含むソートセットコマンドは、逆順または降順を意味します。

すべてをまとめる

これらの機能がどのように相互作用するかを示すために、次のデモアプリケーションを作成しました。次の図に上位アーキテクチャを示します。

これらすべての要素がどのように連携するのかをテストするには、AWS CloudFormation スタックを起動します。スタックは以下のリソースを作成します。

AWS Lambda 関数
Amazon API Gateway API アクション
パラメータ:

ラムダ関数

次の表は、デモアプリケーション用に AWS CloudFormation スタックが作成した関数の一覧です。

関数	説明
LeaderboardRetrievePlayerInfo	プレイヤーのランクとスコアを Redis から取得します。
LeaderboardUpsertScore	Redis の既存のプレイヤーのスコアを更新または挿入します。
LeaderboardSearchUser	MySQL データベースのユーザーテーブルに対して検索します。
LeaderboardRetrieveTop10	Redis からトップ 10 ユーザーを取得し、その結果を MySQL データベースからのユーザーの詳細情報とマージします。
LeaderboardLoadFrontend	フロントエンドをホストするために使用される S3 バケットを正しく初期化するためのカスタムリソースとして AWS CloudFormation テンプレートを使用します。

API Gateway API のアクション

AWS CloudFormation テンプレートは、Lambda 関数へのプロキシとして機能する API も作成します。API の構造は次のとおりです。

/leaderboard
  /player-info
    GET
  /top10
    GET
/users
  /score
    POST
  /search
    GET

パラメータ:

次の表に、デモアプリケーション用に AWS CloudFormation スタックが作成したパラメータを示します。

パス	使用方法
/leaderboard/player-info	ランクとスコアの情報を取得するユーザーを示すために、クエリ文字列に user_id パラメータを渡します。
/users/score	次の JSON をリクエストボディに渡します。 `{score: "<score>", user_id: "<user_id>"}`
/users/search	既存のユーザーを検索するには、クエリ文字列に username パラメータを渡します。ユーザー名は、ワイルドカード検索を実行するのに不完全な場合があります。

Redis と MySQL

両方のデータベースに 100 万ユーザー/スコアをプリロードしました。MySQL の場合、データベースには 2 つのテーブルがあります。ユーザーとリーダーボードです。Redis の場合、ソートセットキーはリーダーボードです。MySQL と Redis の両方のデータは似ているため、クエリの応答時間をすばやく比較できます。

フロントエンドとバックエンドへのアクセス

AWS CloudFormation がスタックの構築を終了すると、スタックの [出力] タブに 2 つの URL が見つかります。次のスクリーンショットは例を示しています。

APIGatewayInvokeURL は、REST API バックエンドの URL です。返される実際のペイロードを確認するには、このエンドポイントに直接 API 呼び出しを行います。詳細については、先の API Gateway セクションを参照してください。

FrontendURL は、ブラウザで直接開いてデモアプリケーションを見ることができます。次のスクリーンショットは例を示しています。

ユーザー名を検索したり、現在のランクとスコアを確認したり、現在のスコアを変更したりできます。スコアを更新すると、トップ 10 リストが更新されます。

Redis とのインタラクション

デモアプリケーションが Redis インスタンスにコマンドを送信する前に、次のタスクを完了する必要があります。

node_redis をインストールする
クライアントオブジェクトを初期化します。

node_redis ライブラリをインストールする

デモアプリケーションは Node.js を使用するため、次のコマンドを実行してライブラリをインストールします。

npm install --save redis

クライアントオブジェクトを初期化する

ライブラリがインストールされたら、次のコマンドでクライアントオブジェクトを作成することで Redis インスタンスに接続できます。

var redis = require("redis");

var redisClient = redis.createClient(<port>, <endpoint url>);

Redis コマンドによる一般的なリーダーボード操作

以下は一般的なリーダーボード操作とそれに対応する Redis コマンドです。

ユーザースコアの挿入/更新

プレイヤーのスコアを挿入または更新するには、次のコマンドを使用します。

redisClient.zadd([key, score, userId], callback);

ユーザースコアを取得する

次のコマンドは、特定のユーザー ID のスコアを取得します。zadd コマンドを使用してスコアと一緒にメンバーを挿入するときに、メンバー ID として user_id を使用しました。

redisClient.zscore([key, userId], callback);

ユーザーのリストを取得する

ユーザーの範囲を取得するために zrange と zrevrange という 2 つのコマンドがあります。デモアプリケーションでは、zrevrange を使用します。ハイスコアのプレイヤーがランク上位に来るようにするためです。

redisClient.zrevrange([key, min, max, “WITHSCORES”], callback);

ソートセットは、0 から始まる最小値がランク #1 になるような、ゼロインデックスの配列に基づいて最小値または最大値パラメータを設定します。パラメータ「WITHSCORES」は、結果に各プレイヤーのスコアが含まれることを意味します。このパラメータは、たとえば[<user1>, <score>, <user2>, <score>, <user3>, <score>…] といった結果の配列に影響を与えます。「 WITHSCORES」パラメータがなければ、それは単なるユーザーの配列になります。

ユーザーのランクを取得する

ユーザーのリストを取得する場合と同様に、ユーザーのランクを取得するためのコマンドが 2 つあります。zrank と zrevrank です。このデモアプリケーションでは、ハイスコアのプレイヤーがランク上位に来るため、zrevrank を使用します。

redisClient.zrevrank([key, userId], callback);

スケーリング

ElastiCache はオンライン上でクラスターサイズを変更することをサポートしています。これにより、シャードの内外でゼロダウンタイムのスケーリングが可能になります。ピークトラフィックと非ピークトラフィックに対応するために、CloudWatch アラームに応じてサイズを変更することができます。

サイズの変更を行う API は ModifyReplicationGroupShardConfiguration です。これにより、シャードの追加、シャードの削除、または既存のシャード間のキースペースの再調整が行えます。

結論

適切なユースケースに適切なデータストレージを使用し、データアクセスパターンを考慮することで、パフォーマンスが大幅に向上するだけでなく、費用対効果の高いソリューションも提供します。

ソートセットとは別に、Redis はゲーム業界で役立つ他のデータ構造を提供します。Redis のドキュメントには各コマンドの時間の複雑さも記載されているので、ユーザーが増えるにつれてパフォーマンスがどのように向上または下落するかがわかります。

著者について

Jan Michael Go Tan は、Global Financial Services Team のソリューションアーキテクトです。

Amazon Web Services ブログ