Posted inデータベース

Redis Sorted Setsを活用し、1,000万人以上のユーザーに対応するリアルタイム・リーダーボードのスケーリング

Database tutorial - IT technology blog
Database tutorial - IT technology blog

大規模環境におけるリアルタイム・ランキング

私たちのMySQLデータベースは、ユーザー数が100万人に達した瞬間に限界を迎えました。私たちは、プレイヤーがポイントを獲得した瞬間にグローバルランクが変動することを期待する、競争の激しいゲーム機能を構築していました。リレーショナルデータベースは多くの用途に優れていますが、ユーザーがプロフィールを確認するたびに100万行のテーブルに対して ORDER BY score DESC を実行するのは、破綻への近道です。

レイテンシは顕著でした。APIのレスポンスタイムは2,000ミリ秒を超えて急上昇し、データベースのCPU使用率は90%に張り付いたままでした。秒間数千件の同時スコア更新を処理しながら,瞬時にランクを検索できるソリューションが必要でした。そこで行き着いたのが Redis Sorted Sets（ZSET）です。本番環境で6ヶ月運用した現在、私たちのランキングエンジンはピーク時の負荷も余裕で処理しています。その構築方法をここで紹介します。

クイックスタート：5分で構築するリーダーボード

Redis Sorted Setsは、まさにこの目的のために作られています。Sorted Setの各要素はスコアとペアになっています。Redisはこれらのスコアを使用して、すべてを自動的に整列させます。標準的なリストとは異なり、特定のユーザーの順位を見つけたり、上位プレイヤーの範囲を取得したりする操作を対数時間（logarithmic time）で行うことができます。

基本コマンド

高性能なリーダーボードを管理するために必要なコアコマンドは4つだけです。

# ユーザーを追加、またはスコアを更新
ZADD game_leaderboard 1500 "user_88"

# スコアを加算（リアルタイムのポイント獲得に最適）
ZINCRBY game_leaderboard 50 "user_88"

# 上位10名のプレイヤーを取得（降順）
ZREVRANGE game_leaderboard 0 9 WITHSCORES

# 特定のユーザーの正確な順位を取得
ZREVRANK game_leaderboard "user_88"

Pythonでの実装

redis-py ライブラリを使用すると、これらのコマンドをシンプルなサービスにラップできます。このアプローチにより、アプリケーションロジックをクリーンに保、データベースクエリを高速に維持できます。

import redis

r = redis.Redis(host='localhost', port=6379, db=0)

def update_score(user_id, points):
    # ZINCRBYは既存のスコアにポイントを加算、または新規作成する
    r.zincrby("global_leaderboard", points, user_id)

def get_top_players(n=10):
    # (user_id, score) のタプルのリストを返す
    return r.zrevrange("global_leaderboard", 0, n-1, withscores=True)

def get_user_rank(user_id):
    # ZREVRANKは0から始まるため、人間が読みやすい順位にするために1を加算する
    rank = r.zrevrank("global_leaderboard", user_id)
    return rank + 1 if rank is not None else None

# 使用例
update_score("player_alpha", 100)
print(f"トップ10: {get_top_players()}")
print(f"あなたの順位: {get_user_rank('player_alpha')}")

アーキテクチャ：なぜスケールするのか

内部的には、Redisはスキップリスト（Skip List）とハッシュテーブル（Hash Table）を組み合わせています。この二重構造のアプローチにより、ユーザーの追加や順位の取得を含むほとんどの操作が O(log(N)) の計算量を維持します。1,000万人のユーザーがいるリーダーボードでも、順位を見つけるのに必要な比較は約24回だけです。

標準的なSQLデータベースが苦戦するのは、順序を維持するために大規模なインデックスをスキャンしたり、重いディスクI/Oを処理したりする必要があるためです。Redisは構造全体をメモリ上に保持します。スコアを更新すると、スキップリストによって、テーブル全体の再構築なしにユーザーをほぼ瞬時に再配置できます。

ピーク時には、毎秒5,000件のスコア更新を処理していますが、RedisのCPU使用率が15%を超えることは滅多にありません。以前のPostgreSQLの構成と比較すると、Redisによるミリ秒未満のレスポンスタイムは、ユーザーにとって魔法のように感じられるでしょう。

応用編：実世界の課題を解決する

1. 同点時の公平な処理

Redisは、スコアが同一のユーザーに対してデフォルトでアルファベット順のソートを適用します。競争環境では、通常、先にそのスコアに到達したプレイヤーが高い順位を得るべきです。これは「複合スコア」を作成することで解決できます。

ベーススコアにタイムスタンプの端数を付加することで、時系列でタイブレークを行うことができます。*早い*タイムスタンプを優先させたいため、将来の特定の日付定数から現在の時刻を差し引きます。

import time

# 未来の定数（例：2050年）
MAX_TIMESTAMP = 2524608000 

def update_score_with_tie_break(user_id, base_score):
    # タイムスタンプが早いほど、小数部分が大きくなる
    time_fraction = (MAX_TIMESTAMP - int(time.time())) / MAX_TIMESTAMP
    final_score = base_score + time_fraction
    r.zadd("leaderboard_with_ties", {user_id: final_score})

2. 日次および週次の期間設定

プレイヤーは、新たに勝利するチャンスがあるときに、より意欲的に参加します。私たちは leaderboard:2023-10-27 のような動的なキーを使用して、期間限定のリーダーボードを管理しています。また、これらのキーに有効期限（TTL）を設定しています。これにより、古い日次データが自動的に消去され、メモリコストを低く抑えることができます。

3. 「ソーシャル」ビュー：自分の周辺

グローバルランクも素晴らしいですが、自分のすぐ上と下にいる3人のプレイヤーを表示する方が、モチベーション維持に繋がることがよくあります。これは、ユーザーの順位を取得し、その周囲の狭い範囲を計算して取得することで実装できます。

def get_around_me(user_id, radius=3):
    rank = r.zrevrank("global_leaderboard", user_id)
    if rank is None: return []
    
    # 指定された範囲内のプレイヤーを取得
    start = max(0, rank - radius)
    end = rank + radius
    return r.zrevrange("global_leaderboard", start, end, withscores=True)

本番運用6ヶ月で得られた教訓

メモリ管理

Redisにおいて、RAMは最も高価なリソースです。キーにUUIDを使用し、1,000万人のユーザーを持つリーダーボードの場合、約1.2GBから1.5GBのメモリ使用を見込んでください。maxmemory ポリシーを設定することをお勧めします。私たちはクラッシュを防ぐために volatile-lru を使用していますが、制限に達する前に垂直スケーリング（スペックアップ）を行えるよう、綿密に監視しています。

永続化戦略

リーダーボードのデータは再起動後も保持される必要があります。私たちは everysec ポリシーを適用した AOF (Append Only File) を使用しています。これにより、パフォーマンスと安全性のバランスをとっています。万が一クラッシュした場合、1秒分のスコア更新が失われる可能性がありますが、通常の運用で得られる圧倒的なスピード向上を考えれば、妥当なトレードオフです。

Luaによるアトミックなロジック

新しいスコアが古いスコアよりも高い場合のみ更新したいことがあります。複数のコマンドをやり取りするとネットワークの遅延が発生します。小さなLuaスクリプトを使用すれば、このロジックをRedisサーバー上で直接、単一のアトミックなステップとして実行できます。

-- 新しいスコア（ARGV[1]）が現在のスコアより高い場合のみ更新
local current_score = redis.call('ZSCORE', KEYS[1], ARGV[2])
if not current_score or tonumber(ARGV[1]) > tonumber(current_score) then
    return redis.call('ZADD', KEYS[1], ARGV[1], ARGV[2])
end
return 0

結論

ユーザープロフィールや支払い履歴には引き続きPostgreSQLを使用していますが、ランキングロジックをRedisに移行したことは大きな転換点となりました。これにより、高頻度の書き込みがプライマリデータベースから切り離され、レイテンシが大幅に削減されました。もしあなたのアプリケーションが数百万行のリアルタイムなソートに苦労しているなら、Redis Sorted Setsは最も効果的なツールとなるでしょう。

Share:
Tags: