データベース101: 100万プレイヤーのゲームのリーダーボードをどうモデル化するか

リーグ・オブ・レジェンド、フォートナイト、あるいはロックバンドのようなゲームがリーダーボードをどうやって形にしてるのか気になったことありますか？この記事では、1Mプレイヤーのゲームでリーダーボードを適切にモデル化して、もの凄く高いパフォーマンスで扱う方法を一緒に見ていきましょう！

もしあなたが初心者でデータベースについてこれから学びたいなら、私が最初に書いた記事「データベース101: 初心者のためのデータ整合性」から読み始めることをおすすめします。その記事では私がこれまでのSQLとMySQLの経験を超えて、どれだけ多くのデータベースのパラダイムがあるかを探求しています。この「データベース101」シリーズで自分の学んだことを記録しています。

このシリーズで最初の記事を投稿してからもう1年近くになります！一緒に勉強してくれてありがとうございます。いつも皆さんのコメントや考えがとても役立ちます！

1. プロローグ

子供の頃から、ほとんどの開発者と同じように、ゲームの作り方に魅了されてきました。そこで、私のお気に入りの子供時代のゲーム、「ギターヒーロー3: レジェンズ・オブ・ロック」を紹介しましょう。

そして十数年後、私はオープンソースプロジェクトのゲーム開発に協力しようと決心しました。例えば rust-ro (Rust Ragnarok Emulator) や、この記事のメインキャラクター、YARG (Yet Another Rhythm Game) です。

YARGはまさに別のリズムゲームですが、このプロジェクトの違いは、完全にオープンソースであり、ゲーム開発とデザインの伝説的なコントリビューターたちが集まり、このプロジェクトを成立させたことです。

突然、Twitchでギターヒーロー/ロックバンドのストリーマー達が主にプレイするようになり、私は思いました。これはオープンソースプロジェクトだから、データベーススキルを何かに使えるかもしれない、例えばもの凄く高速なリーダーボードを作るとか、過去のゲームの記録を保存するとかにね。

これは彼らのDiscordでのシンプルなチャットから始まり、プロジェクトをより速く成長させる方法についての長い議論に発展しました。

その後、私はボスに相談し、私がYARGチームと一緒に仕事をする条件として、ScyllaDB (NoSQL Wide-column Database) を使って何かクールなものを作ることにしました。なぜなら私はそこでデベロッパーアドボケイトとして働いていたからです。ScyllaDBによるシンプルさとスケーラビリティがYARGにぴったりだったのは信じられないほどです！

とにかく、話は安い。いくつかのコードとコンセプトを見せてあげましょう！

2. QDD - クエリ駆動型データモデリング

NoSQLに関して開発を進める時、主に理解すべきことは、パラダイム（ドキュメント、グラフ、ワイドカラムなど）によって、最初にどのクエリを実行したいか理解することです。

MySQLでは一貫性を理解するのが主な目的ですが、Scyllaではクエリに焦点を合わせ、そのクエリに基づいてスキーマを作成するべきです。

このプロジェクトでは、次の2つのタイプのパラダイムを扱います。

キーバリュー
ワイドカラム（クラスタリゼーション）

それでは、モデリングのクエリ/機能について語りましょう。

2.1 機能: マッチの保存

YARGのゲームプレイを終えるたびに、最も興味深いのは着点と他の多くのゲーム内メトリクスを提出することです。

基本的に、これは主にインデックスに基づいた単一のクエリです。

SELECT score, stars, missed_notes, instrument, ...
FROM leaderboard.submisisons
WHERE submission_id = 'some-uuid-here-omg'

2.2 機能: リーダーボード

そして今、私たちの主な目標です。良いデータモデリングをした後は気にする必要のないすごくクールなリーダーボード！リーダーボードは曲ごとになっていて、特定の曲をプレイするたびに、最高スコアが保存され、ランク付けされます。

しかし、このインターフェースには大きなポイントがあります。それはフィルターを持っていて、正確に「どの」リーダーボードを持ってくるかを知る必要があります。

song_id: 必須
instrument: 必須
modifiers: 必須
difficulty: 必須
player_id: 任意
score: 任意

ですから、私たちのクエリはこのように見えます。それはスコアで降順にソートされた結果を返します。

SELECT
    player_id, score, ...
FROM
    leaderboard.song_leaderboard
WHERE
    instrument = 'guitar' AND
    difficulty = 'expert' AND
    modifiers = {'none'} AND
    track_id = 'dani-california'
LIMIT
    100;

--   player_id  | score
----------------+-------
--        tzach | 12000
--  danielhe4rt | 10000
--     kadoodle |  9999
----------------+-------

これで、ここで取り組む機能を知りましたが、最終のスキーマがどうなるかすでに想像できますか？

いいえ？大丈夫、それをお手伝いしましょう！

3. データモデリングの時間です！

ScyllaDBでのデータモデリングを深く掘り下げて、どうやってスケールするかをもっとよく理解する時間です。

3.1 - マッチのモデリング

まず、ゲーム自体についてもう少し理解しましょう。

リズムゲームです。
一度に特定の曲をプレイします。
ゲーム前に「モディファイヤー」を有効にして、生活を楽にしたり難しくしたりできます。
楽器を選ぶ必要があります（例：ギター、ドラム、ベース、マイクなど）。
ゲームプレイのあらゆる側面が追跡されます。例えば：
- スコア；
- ミスノート；
- オーバードライブの回数；
- プレイ速度（1.5x〜1.0x）；
- ゲームプレイの日付/時刻；
- その他のクールなもの。

それを踏まえると、私たちは以下のようなデータモデリングを簡単に開始することができます。

CREATE TABLE IF NOT EXISTS leaderboard.submissions (
    submission_id uuid,
    track_id text,
    player_id text,
    modifiers frozen<set<text>>,
    score int,
    difficulty text,
    instrument text,
    stars int,
    accuracy_percentage float,
    missed_count int,
    ghost_notes_count int,
    max_combo_count int,
    overdrive_count int,
    speed int,
    played_at timestamp,
    PRIMARY KEY (submission_id, played_at)
);

int/textの値を飛ばして、set<text>に飛び込みましょう。

set型を使うと、特定の型のアイテムのリストを保存することができます。クエリが実行される方法を見て、なぜこのリストをモディファイヤで保存することに決めたのか理解するために、このリストを使うことにしました。

INSERT INTO leaderboard.submissions (
    submission_id,
    track_id,
    modifiers,
    played_at
) VALUES (
    some-cool-uuid-here,
    'starlight-muse'
    {'all-taps', 'hell-mode', 'no-hopos'},
    '2024-01-01 00:00:00'
);

この型では、後で取得するためにアイテムのリストを簡単に保存することができます。

もう一つの面白い情報は、このクエリがキーバリューのようなものだということです。これはどういうことかと言うと？

あなたが常にsubmission_idだけでクエリするのであれば、それはキーバリューとして分類されるわけです。

3.2 リーダーボードのモデリング

この記事の部分では、いくつかのクールなワイドカラムデータベースの概念を学びます。

先に述べたように、リーダーボードのクエリでは、WHERE句に常に動的な値が必要になります。これはそれらの値がパーティションキーに属することを意味し、クラスタリングキーは「任意」の値を持つことができます。

パーティションキーは、特定の値を識別するために追加した異なるフィールドの組み合わせに基づいているハッシュです。わかりましたか？いえ？私もそれを理解するのにしばらく時間がかかりましたが、何かを見せてあげましょう：

100回Starlight - Museを演奏したと想像してみてください。この情報をクエリすると、scoreやplayer_idのようなクラスタリングキーで違う結果が100回出るでしょう。

SELECT
    player_id, score ---
FROM
    leaderboard.song_leaderboard
WHERE
    track_id = 'starlight-muse'
LIMIT
    100;

もし100万人のプレイヤーがこの曲をプレイしたら、クエリは遅くなり、将来の問題になるでしょう。なぜならあなたのパーティションキーはtrack_idだけの一つのフィールドで構成されているからです。

しかしながら、もしあなたがゲームをプレイする前に必須のもの、たとえば楽器、難易度、モディファイヤーなどのフィールドをパーティションキーに追加するなら、ある特定のトラックに関する情報をより早いクエリのために均等に分割することができるでしょう。今のビッグピクチャーが見えましたか？いくつかの単純な数字で想像してみましょう：


-- クエリパーティションID: '1'
SELECT
    player_id, score, ...
FROM
    leaderboard.song_leaderboard
WHERE
    instrument = 'guitar' AND
    difficulty = 'expert' AND
    modifiers = {'none'} AND -- モディファイヤー変更
    track_id = 'starlight-muse'
LIMIT
    100;

-- クエリパーティションID: '2'
SELECT
    player_id, score, ...
FROM
    leaderboard.song_leaderboard
WHERE
    instrument = 'guitar' AND
    difficulty = 'expert' AND
    modifiers = {'all-hopos'} AND -- モディファイヤー変更
    track_id = 'starlight-muse'
LIMIT
    100;

ですので、特定の形でクエリを構築すれば、常に特定のトークンを探し、それら特定のパーティションキーに基づいてデータを取得することになります。

最終的なモデリングを見て、クラスタリングキーとアプリケーション層について話しましょう：

CREATE TABLE IF NOT EXISTS leaderboard.song_leaderboard (
    submission_id uuid,
    track_id text,
    player_id text,
    modifiers frozen<set<text>>,
    score int,
    difficulty text,
    instrument text,
    stars int,
    accuracy_percentage float,
    missed_count int,
    ghost_notes_count int,
    max_combo_count int,
    overdrive_count int,
    speed int,
    played_at timestamp,
    PRIMARY KEY ((track_id, modifiers, difficulty, instrument), score, player_id)
) WITH CLUSTERING ORDER BY (score DESC, player_id ASC);

上述した通り、パーティションキーはトラック_id、モディファイヤー、難易度、楽器といった必須パラメーターで定義されています。そして、クラスタリングキーにはスコアとプレイヤーIDを加えました。

注意してほしいのは、デフォルトではクラスタリングフィールドはscore DESCで並び、プレイヤーが同じスコアだった場合の勝者の基準はalphabeticalです ¯\(ツ)/¯。

最初に知っておくべきことは、我々はプレイヤーごとに一つのスコアしか持たないということですが、このようなモデリングではプレイヤーが同じトラックを異

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/danielhe4rt/database-101-how-to-model-leaderboards-for-1m-players-game-2pfa