キャッシュの Stampede 問題をセマフォで解決する #Cache

Cache Stampede

キャッシュが有効期限切れによってオリジン（データベースなど）へのアクセスが殺到することで負荷が高まってしまう問題を Cache Stampede (キャッシュ・スタンピード）と呼びます。Stampede は日本語にすると「殺到」というような意味合いの単語です。

※他にも Cache miss storm だったり Thundering Herd だったり、Dog pile だったり、いろいろ呼び方はあるようです。

本記事ではこの Cache Stampede 問題への対策として memcached の機能をセマフォとして使い、オリジンへのアクセスを制御する方法について記します。

問題の整理のため、キャッシュを使う場合の典型的な処理を振り返りながら見ていきます。

単純なキャッシュ

キャッシュには通常では有効期限があり、有効期限が切れるとキャッシュを使用せずに、オリジン（データベースなど）にアクセスして新しい結果を取得し、キャッシュに保存しつつレスポンスを返すことになります。

実装としてはおおむね以下のようになるでしょう。

# キャッシュからデータを取得する
data = get_cache(key)

if not data:
  # キャッシュがなければデータベースから取得する
  data = get_data_from_database(...)

  # 新しいデータをキャッシュに保存する
  set_cache(key, data, ttl=60)

# ユーザーにレスポンスを返す
send_response(data)

アクセスが少ない場合

アクセスが少ない場合は、問題になりません。以下のように、オリジンへ到達するアクセスが少ないためです。

アクセスが多い場合

アクセスが大量にある場合、キャッシュが有効期限切れになると、複数のアクセスがデータベースに行くことになります。これは、キャッシュの有効期限切れと、新しいキャッシュが保存されるまでのタイムラグが存在するためです。データベースの処理が重かったりすると、キャッシュ切れのタイミングで負荷が高まってしまいます。

対策

対策にはいくつかの方法があります。

ロック
別プロセスでの更新
確率的な早期の期限切れ

本記事ではロックの一種であるセマフォを使った解決方法について記します。

ひとりだけ更新

キャッシュ切れ時のデータベースへのアクセスは、ひとりのユーザーが実施し、新しいキャッシュを作成すればよく、他のユーザーは新しいキャッシュを待てば、オリジンへの負荷は軽減できます。

セマフォ

このような場合、セマフォを使ってアクセスを制御すれば実現できそうです。

セマフォとは？

複数の実行単位が「共有する資源」にアクセスするのを制御するもの。ある資源が「何個使用可能かを示す記録」で、使用や解放の際に記録を「安全に書き換え」て、資源が使用可能になるまで「待つ」操作が結びついている。
※ https://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%9E%E3%83%95%E3%82%A9 より要約

ところが、Webサービスにおいては、複数のサーバでアプリケーションが動作しています。同一サーバにおいても複数プロセスで動作していたりします。このため、各アクセスが同一のOSプロセス上ではないので、OSの（プログラミング言語上の）セマフォを使うことができません。

ではどうするかというと、各アクセスから共有して使うことができるのは「キャッシュのシステム」なので、ここにセマフォを実装してしまいます。

add

memcached の add コマンドは「アイテムが存在しない場合だけ、保存」します。つまり、そのキーに対してデータを保存できるのは、単一のクライアントだけです。

よって add に成功したことを「セマフォを獲得した」と見なすことで、単一のクライアントにキャッシュ更新をさせることができるようになります。

例

# キャッシュからデータを取得する
data = memcache.get(key_for_data)

if data:
  # キャッシュがある場合はセマフォの獲得を試みる
  ret = memcache.add(key_for_semaphore, 1, ttl=60)

  if ret:
    # セマフォを獲得した場合は新しいキャッシュを作る
    data = get_data_from_database(...)
    memcache.set(key_for_data, data, ttl=120)

else:
  # 本当にキャッシュ切れしてしまった場合は、どうしようもないのでオリジンへアクセスします
  memcache.add(key_for_semaphore, 1, ttl=60)
  data = get_data_from_database(...)
  memcache.set(key_for_data, data, ttl=120)

return data

add できるのはひとりなので、オリジンへのアクセスは、おおむね、ひとりに限られます。

有効期限

memcache にはアイテムの有効期限を設定できます。よって、セマフォの解放を有効期限切れによって行うことができます。Webサービスにおいては、HTTPリクエストの処理は即座に返ってしまい、セマフォを明示的に解放することはできません。ところがアイテムの有効期限切れがあるので、自動的に解放されるし、解放忘れがありません。

また、セマフォの有効期限は データ側の有効期限より短く しておく必要があります。こうすることで、キャッシュのデータが残っているうちにオリジンへのアクセスと新しいキャッシュの作成が発生し、セマフォを獲得しなかったクライアントはキャッシュのデータをそのまま利用できます。

上記の例だと key_for_semaphore がデータより先に有効期限切れします（ttl=60）。memcache.get から data が得られつつも、最初に memcache.add できたクライアントがオリジンにアクセスし memcache.set で新しいデータを保存します（ttl=120）。もちろん、キャッシュが有効期限以外の理由で消えてしまうこともあるので else 側に入ることもありますが、おおむね問題なく動作すると思います。

その他

各ソフトウェアの Stampede 対策の機能
- Rails ActiveSupport::Cache::Store race_condition_ttl
- nginx proxy_cache_lock
- Varnish Grace mode
- Fastly

参考
- http://techblog.yahoo.co.jp/infrastructure/cache-reducing-origin-request/
- https://en.wikipedia.org/wiki/Cache_stampede