« MySQL の高速化プチBK | メイン | ウェブサービスのためのMutex - KeyedMutex »

2007年09月26日

キャッシュシステムの Thundering Herd 問題

 サーバにおける Thundering Herd 問題注1は良く知られていると思いますが、類似の現象はキャッシュシステムでも発生することがあります注2

 通常、キャッシュに格納されるデータは、それぞれ単一の生存時間をもっています。問題は、頻繁にアクセスされるキャッシュデータがエクスパイアした際に発生します。データがエクスパイヤした瞬間から、並行に走る複数のアプリケーションロジックがミスヒットを検知し、いずれかのプロセスがキャッシュデータを格納するまでの間、同一のリクエストが多数、バックエンドに飛んでしまうのです。

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

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

 これらの手法には、それぞれメリットとデメリットがあり、アプリケーションによって最適な方法は異なります。Pathtraq では、最終的に両者を併用する形になると思います。後者については、本日公開した Swifty 0.05 で実装しましたので、よろしければご覧ください。

注1: naoyaのはてなダイアリー - prefork サーバーと thundering herd 問題が参考になると思います。ただ、私の記憶が正しければ、1プロセスしか accept に成功しないにもかかわらず全プロセスがwakeされる (=全ての accept がなんらかの結果 (ほとんどの場合 EAGAIN) を返す) というのが、Thundering Herd の最大の問題だったはずです (だから1プロセスしかwakeされない flock で順列化するのは立派な Thundering Herd 対策です)。その点については、naoya さんの修正が間違っていると思います。
注2: どの程度速度が低下するかは、バックエンドとキャッシュシステムの速度の比率によります (だから memcached で軽いSQLクエリをキャッシュしている場合は大きな問題じゃないかも)

投稿者 kazuho : 2007年09月26日 10:11 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1543

コメント

いつもどもども。

いま手元に本がないのであれなんですけど、Stevens 本によると flock(2) でブロックされてたプロセス群がロックを獲得しにいくときも thundering herd が起こる、とのことでした。あとでまた確認してみます。

(flock(2) はロック獲得待ちにいる一つのプロセスだけが wake されることを保証してたりするんでしょうか。)

投稿者 naoya : 2007年09月26日 10:32

> flock(2) はロック獲得待ちにいる一つのプロセスだけが wake されることを保証してたりするんでしょうか

保証していると思います (apache の flock_mutex も EINTR しか見ていない) 。

もちろんカーネル内部の実装がブロックしているプロセスの数に対して O(1) かどうか、という問題はあるのですが、ユーザープロセスが一斉に起動するというかなりイヤな状況が当時は発生した、という風に記憶しています。
#今でも複数ソケットを listen していて poll -> accept だと楽しい状況が観測できるはず

投稿者 kazuho : 2007年09月26日 10:44