キャッシュの殺到

キャッシュスタンピードは、キャッシュメカニズムを備えた超並列コンピューティングシステムに非常に高い負荷がかかったときに発生する可能性のある連鎖障害の一種です。この動作はドッグパイリングとも呼ばれます。^{[1] [2]}

キャッシュ スタンピードがどのように発生するかを理解するには、システム負荷を軽減するために、レンダリングされたページを一定期間キャッシュするためにmemcached を使用するWeb サーバーを検討してください。単一の URL への負荷が特に高い場合、リソースがキャッシュされている限り、システムは応答性を維持し、リクエストはキャッシュされたコピーにアクセスすることで処理されます。これにより、コストのかかるレンダリング操作が最小限に抑えられます。

負荷が低い場合、キャッシュ ミスによりレンダリング操作が 1 回再計算されます。システムは以前と同じように動作し、キャッシュ ヒット率が高いため平均負荷は非常に低く抑えられます。

ただし、非常に重い負荷がかかっている場合、そのページのキャッシュされたバージョンの有効期限が切れると、サーバー ファームで十分な同時実行性が得られ、複数の実行スレッドがすべて同時にそのページのコンテンツをレンダリングしようとする可能性があります。システム的には、同時実行サーバーはいずれも、他のサーバーが同時に同じレンダリングを実行していることを認識していません。十分に高い負荷が存在する場合、これだけで共有リソースを使い果たしてシステムの輻輳崩壊を引き起こすのに十分である可能性があります。輻輳崩壊により、すべての試行がタイムアウトになるため、ページが完全に再レンダリングおよび再キャッシュされることができなくなります。したがって、キャッシュ スタンピードによりキャッシュ ヒット率がゼロになり、負荷が非常に重い限り、システムはリソースの再生成を試行するため、輻輳崩壊状態が継続します。

具体的な例を挙げると、検討中のページのレンダリングに 3 秒かかり、トラフィックが 1 秒あたり 10 件のリクエストであるとします。その後、キャッシュされたページの有効期限が切れると、30 個のプロセスが同時にページのレンダリングを再計算し、レンダリングされたページでキャッシュを更新します。

以下は、 ttl単位の時間ごとに更新する必要があるアイテムの一般的なキャッシュ使用パターンです。

関数fetch( key , ttl ) {
     value ← cache_read( key )
     if (! value ) {
         value ← recompute_value()
        cache_write(キー、値、TTL )
    }
    戻り 値
}

関数recompute_value() の実行に時間がかかり、キーが頻繁にアクセスされる場合、キャッシュ値の有効期限が切れると、 多くのプロセスが同時にrecompute_value()を呼び出します。

一般的な Web アプリケーションでは、関数recompute_value() はデータベースをクエリしたり、他のサービスにアクセスしたり、複雑な操作を実行したりすることがあります (これが、この特定の計算がそもそもキャッシュされる理由です)。要求レートが高い場合、データベース (またはその他の共有リソース) は要求/クエリの過負荷に悩まされ、その結果、システムがクラッシュする可能性があります。

キャッシュの暴走 (ドッグパイル防止とも呼ばれる) を軽減するためのアプローチがいくつか提案されています。それらは、おおよそ 3 つの主なカテゴリに分類できます。

同じ値が同時に複数回再計算されるのを防ぐため、キャッシュ ミスが発生すると、プロセスはそのキャッシュ キーのロック取得を試み、取得できた場合にのみ再計算を行います。

ロックが取得されない場合は、さまざまな実装オプションがあります。

• 値が再計算されるまで待つ
• 「見つからない」を返し、クライアントが値の欠如を適切に処理するようにします。
• 新しい値が再計算される間、古いアイテムをキャッシュに保持して使用します。

ロックが適切に実装されていれば、暴走を完全に防ぐことができますが、ロック機構のために追加の書き込みが必要になります。書き込み回数が倍増すること以外に、主な欠点は、ロックを取得するプロセスの失敗、ロックの有効期間の調整、競合状態などのエッジケースも処理するロック機構の正しい実装です。

このソリューションは、キャッシュ値の再計算を、それを必要とするプロセスから外部プロセスに移動します。外部プロセスの再計算は、さまざまな方法でトリガーできます。

• キャッシュ値の有効期限が近づくと
• 定期的に
• 値を必要とするプロセスがキャッシュミスに遭遇した場合

このアプローチには、外部プロセスというもう 1 つの可動部分が必要であり、これを保守および監視する必要があります。さらに、このソリューションでは不自然なコードの分離/複製が必要であり、静的キャッシュ キー (つまり、ID によってインデックス付けされたキーの場合のように動的に生成されないもの) に主に適しています。

このアプローチでは、各プロセスは独立した確率的決定を行うことで、有効期限が切れる前にキャッシュ値を再計算できます。この場合、値の有効期限が近づくにつれて、早期の再計算を実行する確率が高くなります。確率的決定は各プロセスによって独立して行われるため、同時に有効期限が切れるプロセスが少なくなり、スタンピードの影響が緩和されます。

指数分布に基づく以下の実装は、群衆の暴走を防ぐ効果と早期の再計算の実現可能性の点で最適であることが示されています。^[3]

関数x-fetch( key , ttl , beta =1) {
     value , delta , expiry ← cache_read( key )
     if (! value || (time() - delta * beta * log(rand(0,1))) ≥ expiry ) {
         start ← time()
         value ← recompute_value()
         delta ← time() – start
        cache_write(キー、(値、デルタ)、TTL )
    }
    戻り 値
}

パラメータbeta を1 より大きい値に設定すると、再計算が早くなり、さらに暴走を減らすことができますが、著者らは、beta =1 に設定すると実際にはうまく機能することを示しています。変数delta は値を再計算する時間を表し、確率分布を適切にスケーリングするために使用されます。

このアプローチは実装が簡単で、トラフィック レートが上昇したときに自動的に早期の再計算を優先することで、キャッシュの集中的な処理を効果的に削減します。1 つの欠点は、値の差分をキャッシュ項目とバンドルする必要があるため、キャッシュでより多くのメモリが必要になることです。キャッシュ システムがキーの有効期限の取得をサポートしていない場合は、有効期限(つまり、time() + ttl ) もバンドルに保存する必要があります。

• キャッシュ スタンピードの最小化、Joshua Thijssen、2010 年
• 典型的な Perl キャッシュ使用に関する問題と解決策、Jonathan Swartz、2008