Posted inデータベース

Redisのキャッシュスタンピード対策：分散Mutexロック vs 確率的早期有効期限切れ（XFetch）

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

クイックスタート：キャッシュスタンピードの再現

秒間15,000リクエストを処理するWebサービスを運用しているとします。トップページでは商品のメトリクスを集計し、TTLを10分に設定してRedisにキャッシュしています。12:00:00、そのキーの有効期限が切れます。そのわずか1秒後、1,500本ものワーカースレッドが一斉にRedisへ問い合わせを行い、キャッシュミスを検知して、負荷の高い同一の集計クエリをデータベースに集中投下します。

エンジニアはこれをキャッシュスタンピード（cache stampede）やドッグパイル（dogpiling）現象と呼びます。コネクションプールはミリ秒単位で枯渇し、データベースのCPU使用率は100%に張り付き、後続のサービスでタイムアウトが連鎖します。

一般的なPythonのキャッシュ処理コードにおいて、この脆弱性は次のように現れます：

import redis
import time

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

def get_expensive_product_data(product_id):
    cache_key = f"product:{product_id}"
    cached_val = r.get(cache_key)
    
    if cached_val is not None:
        return cached_val
    
    # 危険地帯: TTL失効時、何百ものスレッドが同時にこの行に到達する
    computed_data = execute_heavy_database_query(product_id)
    r.setex(cache_key, 600, computed_data)
    return computed_data

def execute_heavy_database_query(product_id):
    time.sleep(0.3)  # 300msの負荷の高いDB集計処理をシミュレート
    return f"data_for_{product_id}"

k6やLocustを使用して2,000仮想ユーザーでこれをシミュレートすると、キーの失効と同時に、PostgreSQLのコネクションプール上限（デフォルトのmax_connections=100など）がFATAL: remaining connection slots are reservedエラーを吐いて崩壊します。この問題を解決するには、再生成処理を実行するワーカーを1つに絞り込むか、キーが完全に失効する前にデータを更新する必要があります。

根本原因と解決策のアーキテクチャ

PostgreSQL、MySQL、MongoDBのいずれを使用していても、何千ものスレッドが同一の集計処理を一斉に実行すれば、リレーショナルエンジンは悲鳴を上げます。従来のキャッシュパターンは読み取りと更新ルーチンを疎結合にしているため、キャッシュ失効から再設定までの間に危険な空白期間が生じてしまいます。

ドッグパイル現象を防ぐための実戦的なアーキテクチャは主に2つあります：

  1. 分散Mutexロック： 再生成処理を直列化します。1つのワーカーのみがロックを取得してデータベースに問い合わせを行い、残りのスレッドは待機、ポーリング、または古いデータを返却します。
  2. 確率的早期有効期限切れ（XFetch）： エントリをプロアクティブ（事前）に更新します。有効期限が近づくにつれて、読み取り処理が確率計算を行い、バックグラウンドでの再計算を段階的にトリガーします。

戦略1：Redisによる分散Mutexロック

分散ロックは、単一ワーカーによるキャッシュ再生成を保証します。キャッシュミスが発生すると、スレッドはRedisの不可分（アトミック）操作であるSET key value NX PXを使用して排他ロックの獲得を試みます。

import uuid
import time

def get_with_mutex(product_id):
    cache_key = f"product:{product_id}"
    lock_key = f"lock:{cache_key}"
    
    val = r.get(cache_key)
    if val is not None:
        return val
    
    # 5秒間の分散ロックを取得
    lock_token = str(uuid.uuid4())
    acquired = r.set(lock_key, lock_token, nx=True, px=5000)
    
    if acquired:
        try:
            # ロックを取得したスレッドがデータを計算してキャッシュに設定
            data = execute_heavy_database_query(product_id)
            r.setex(cache_key, 600, data)
            return data
        finally:
            # 新しいロックを誤って削除しないよう、Luaスクリプトで安全に解放
            lua_release = """
            if redis.call('get', KEYS[1]) == ARGV[1] then
                return redis.call('del', KEYS[1])
            else
                return 0
            end
            """
            r.eval(lua_release, 1, lock_key, lock_token)
    else:
        # 50ms待機してキャッシュの読み取りを再試行
        time.sleep(0.05)
        return get_with_mutex(product_id)

Mutexロックは改札口のように機能します。データベースを確実に保護できる反面、待機中のスレッドにはレイテンシのスパイクが発生します。また、ロックを保持しているワーカーがクエリ実行中にダウンした場合、他のスレッドはロックのタイムアウト上限まで待たされることになります。

戦略2：確率的早期有効期限切れ（XFetch）

50,000 QPS規模の高トラフィックでは、テールレイテンシの抑制が極めて重要です。ロックのポーリングに50ms待機することは、クライアントのレスポンスタイムの大きな浪費となります。2015年、研究者のVattani、Chierichetti、Lowensteinらは、より洗練された解決策であるXFetchアルゴリズムを提唱しました。

完全な失効を待つのではなく、読み取り側が早期に再計算すべきかどうかを確率的に判断します。この判定は、残りのTTLと前回のデータベースクエリ所要時間とのバランスによって行われます。残り時間が短くなるにつれて、プロアクティブなバックグラウンド更新の発生確率は100%へと近づいていきます。

判定条件の数式は以下のとおりです：

-(compute_time * beta * ln(random())) > remaining_ttl

  • compute_time (delta)： キャッシュ対象のレコードを前回生成するのにかかった秒数。
  • beta： 積極性を調整する乗数。1.0を設定すると理論上最適な確率になります。1.0より大きい値を設定すると、より早い段階で更新がトリガーされます。
  • random()： 0.0から1.0（0を除く）の一様乱数浮動小数点数。

Pythonによる実装例は以下のようになります：

import math
import random
import time
import json

def xfetch_read(key, beta=1.0):
    raw = r.get(key)
    if not raw:
        return None, True  # コールドスタートによるキャッシュミス
        
    entry = json.loads(raw)
    value = entry["value"]
    delta = entry["delta"]         # 計算にかかった秒数（例: 0.28）
    ttl = r.ttl(key)              # Redisでキーが失効するまでの残り秒数
    
    if ttl <= 0:
        return value, True
    
    # XFetchのコアとなる確率判定トリガー
    should_refresh = -(delta * beta * math.log(random.random())) > ttl
    return value, should_refresh

def get_product_data_xfetch(product_id):
    key = f"product:{product_id}"
    value, needs_refresh = xfetch_read(key, beta=1.0)
    
    if value is not None and not needs_refresh:
        return value
        
    # 再計算: コールドミスまたは確率判定によってトリガーされる
    start_time = time.time()
    fresh_data = execute_heavy_database_query(product_id)
    compute_duration = time.time() - start_time
    
    payload = json.dumps({
        "value": fresh_data,
        "delta": compute_duration
    })
    
    # TTLを600秒に設定して保存
    r.setex(key, 600, payload)
    return fresh_data

安定したトラフィック下では、キーが完全に失効することは実質的になくなります。読み取り側はロックのオーバーヘッドを完全に回避でき、プライマリデータベースに対するバックグラウンド更新もTTLウィンドウの終盤で滑らかに分散されます。

本番環境運用のポイント

  • 固定TTLにジッター（揺らぎ）を加える： 通常の有効期限方式を維持する場合、ttl = 600 + random.randint(-45, 45)のように疑似ランダムなオフセットを持たせます。これにより、一括デプロイ時などに同時に作成されたキーが一斉に失効するのを防げます。
  • XFetchをバックグラウンドワーカーで非同期化する： needs_refreshがtrueと判定された際、HTTPリクエストのスレッドをブロックしてはいけません。現在のキャッシュ値を即座に返しつつ、CeleryやRQなどに非同期タスクを投入して新しいデータを書き込ませます。
  • ロックTTLはp99レイテンシより長めに設定する： Mutexを使用する場合、ロックの有効期限はデータベースのp99所要時間の少なくとも3倍以上に設定してください。クエリに400msかかるのにロックが300msで切れてしまうと、重複したワーカーが次々と流れ込んでしまいます。
  • Betaパラメータを適切に調整する： 急激なスパイクアクセスによって更新が追いつかない場合は、betaを1.3や1.5に引き上げます。データベースのキャパシティが逼迫している場合は、不要なバックグラウンド更新を防ぐために1.0に固定します。
Share:
Tags: