キャッシュの殺到

キャッシュ・スタンピードとは、キャッシュ機構を備えた超並列コンピューティングシステムに非常に高い負荷がかかった場合に発生する連鎖的な障害の一種です。この動作はドッグ・パイリングとも呼ばれます。[ 1 ] [ 2 ]

キャッシュ・スタンピードがどのように発生するかを理解するために、システム負荷を軽減するために、レンダリングされたページを一定期間キャッシュするためにmemcachedを使用するウェブサーバーを例に考えてみましょう。単一の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()を呼び出します。

一般的なウェブアプリケーションでは、関数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は値の再計算にかかる時間を表し、確率分布を適切にスケーリングするために使用されます。

このアプローチは実装が簡単で、トラフィックレートの増加時に早期の再計算を自動的に優先することで、キャッシュの暴走を効果的に抑制します。ただし、値の差分をキャッシュアイテムにバンドルする必要があるため、キャッシュのメモリ消費量が増えるという欠点があります。キャッシュシステムがキーの有効期限の取得をサポートしていない場合、有効期限（つまり、time() + ttl）もバンドルに 保存する必要があります。

参考文献

  1. ^ Galbraith, Patrick (2009), Apache、MySQL、memcached、Perl による Web アプリケーションの開発、John Wiley & Sons、p. 353、ISBN 9780470538326。
  2. ^ Allspaw, John; Robbins, Jesse (2010), Web Operations: Keeping the Data On Time , O'Reilly Media, pp.  128– 132, ISBN 9781449394158。
  3. ^ Vattani, A.; Chierichetti, F.; Lowenstein, K. (2015)、「最適確率的キャッシュ・スタンピード防止法」（PDF）、VLDB基金紀要、8（8）、VLDB：886– 897、doi：10.14778/2757807.2757813、ISSN 2150-8097 。
「 https://en.wikipedia.org/w/index.php?title=Cache_stampede&oldid=1330515031」より取得