webサイトとかで、重いSQLを使ったページを快適に表示するために、重いSQLの結果をキャッシュするためにmemcachedとかをよく使います。
キャッシュの有効期限が切れた後に、大量のリクエストに対応して大量の重いSQLが走ると困るので、どうしよう。
これをthundering herd 問題といったり、cache stampede, database stampedeというそうです。
キャッシュ切れた後にががっとくるやつ、です。

1. キャッシュの有効期限が切れる
2. SQL発行
3. SQLの結果を受け取る
4. キャッシュにつっこむ

A-D.の間に大量のリクエストが来ると、重いSQLが走るので困ります。

Kazuhookuさんが書いています。
キャッシュシステムの Thundering Herd 問題

　対策としては、以下の２種類の手段があります。

• バックエンドへの同一リクエストを束ねるような仕組みを実装する
• エクスパイヤ以前の残存時間が一定以下となった段階で、キャッシュエントリのアップデートを開始する

昨日memcachedの勉強をしている時のFAQの資料にもいろいろ書いてあったのですが、
いくつか対策方法があるようです。

How to prevent clobbering updates, stampeding requests

The easiest answer is to avoid the problem. Don’t set caches to expire, and update them via cron, or as data is updated. This does not eliminate the possibility of a stampede, but removes it from becoming the norm.

最も簡単なのは、cronでキャッシュを更新してキャッシュに有効期限をもうけないこと。stampedeの可能性はなくならないが、標準的に起こる現象ではなくなる。

なくならないっていうのはどういうときに起こりえるんだろう？

他に、

If you want to avoid a stampede if key A expires for its common case (a timeout, for example). Since this is caused by a race condition between the cache miss, and the amount of time it takes to re-fetch and update the cache, you can try shortening the window.

First, set the cache item expire time way out in the future. Then, you embed the “real” timeout serialized with the value. For example you would set the item to timeout in 24 hours, but the embedded timeout might be five minutes in the future.

Then, when you get from the cache and examine the timeout and find it expired, immediately edit the embedded timeout to a time in the future and re-store the data as is. Finally, fetch from the DB and update the cache with the latest value. This does not eliminate, but drastically reduces the amount of time where a stampede can occur.

意訳すると、

1. キャッシュには長めの有効期限を設定しておく
2. キャッシュにつっこむ中身に、自前でつけるほんとの有効期限をいれておく

1

$cache->set( $key, { content => $content, expires => $real\_expire\_time }, $longer_expiry );

1. キャッシュからデータをとってきて、自前でつけるほんとの有効期限をみて、
   　有効期限切れだったら、すぐさまちょっとだけ有効期限を長くして（重いSQLをこなすのにかかる時間くらい）、
   　キャッシュにつっこむ

1
2
3
4

my $dat = $cache->get( $key );
if ( $dat->{expires} < time() ) {
$cache->set( $key, { content => $dat->{content}, expires => time() + 5 }, $longer_expiry );
}

1. 突っ込んだ後、重いSQLを発行
2. 重いSQLの結果をキャッシュにつっこむ

これにより、最初の例ではA-D.の間が問題となっていたのに対して、
2.の中の、cache->getしてからexpiresを更新してcache->setするまでの間の時間だけが、問題になります。
この時間が十分に短いかは、環境によるでしょう。
自分の開発環境では0.01sec程度でした。

この仕組みは、Catalyst::Plugin::PageCacheにbusy_lockというオプションを設定することで使用可能です。

バックエンドへの同一リクエストを束ねるような仕組みを実装する

このやり方も、BradがGearmanでできるよ、的なことを書いています。深追いはしていません。

さらに、他のやり方として、
probabilistic timeout
というのもあるようです。
基本的にはキャッシュからとってくるんだけれど、キャッシュが切れそうになったら、
リクエストに対して確率的に、SQLを発行するリクエストを選択して、キャッシュを更新する。
有効期限に近づくほど確率が100%に増すようにする。

さらにkazuhookuさんがつくったKeyedMutexでは
ウェブサービスのためのMutex – KeyedMutex

1
2
3
4
5
6
7
8

until ($value = $cache->get($key)) {
if (my $lock = $km->lock($key, 1)) {
#locked read from DB  
$value = get\_from\_db($key);
$cache->set($key, $value);
last;
}
}

ロック機構を使うことでDBへのアクセスを排他できます。
でもこのサンプル例だと、cache stampedesは解消できる代わり、get_from_dbの間のリクエストは全部待たされますね。

これとbusy_lockの仕組みを併用するのがいいかもしれない、とか今思った。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

my $dat = $cache->get( $key );
if ( $dat->{expires} < time() ) {
$cache->set( $key, { content => $dat->{content}, expires => time() + 5 }, $longer_expiry );
if (my $lock = $km->lock($key, 1)) {
#locked read from DB  
$value = get\_from\_db($key);
$cache->set($key, { content => $value, expires => $real\_expire\_time }, $longer_expiry );
return $value;
}
else {
return $value;
}
}
return $dat->{content};

有効期限切れのデータを絶対返したくないのか、数秒ならいいのか、get_from_dbにはどれくらい時間がかかるのか、
状況によりそうです。

自分がやりたかったのは、
busy_lockのあるPageCacheもいいけどユーザー毎に違う内容を表示する場合に、scriptタグとかでもう1httpリクエスト増えるのもあれだなぁと思ったので
テンプレの一部のレンダリング結果をキャッシュする仕組みがほしくて
http://github.com/mash/catalyst-plugin-blockcache/tree/master
ここまで書いたけどそれってなんでCatalystプラグインなの？TTプラグインでは？
Template::Plugin::Cache？？何それ今知った！
でもT::P:：Cacheはbusy_lock無いもん！
Cache::なんとかにしてbusy_lockだけ共通化したい
うーん←今ここ