オトコのイメトレ2008

エンジニアたるもの想像力が必要だ。

複数のmemcachedサーバーを起動させてキャッシュを分散させるような運用では、各データをそれぞれどのサーバーにキャッシュするかを自動的に選択する必要がある。そのアルゴリズムとして、コンシステントハッシュ法というものがあるのだが、これがなんとも見事なアルゴリズムなのである。

コンシステントハッシュ法はハッシュの一種（注意！！オヤジギャグ！！突っ込むべし！！）なので、特定のキーに対して特定のmemcachedサーバーをつねに選択するためのアルゴリズムである。コンシステントハッシュ法ではない最も単純なハッシュ法としては、MD5などでキーからハッシュ値を算出し、memcachedサーバー台数で割り算をしてその余りを用いるというものがある。実際、このアルゴリズムは非常にシンプルであるし、うまく機能するだろう。ただしサーバー台数が一定であるという条件の下では。

しかし昨今では、サイトのトラフィック数が劇的に増減するというのはもはやオトコの常識である。ふとしたことがきっかけでトラフィックが一夜にして100倍になることも珍しくはない。するとサイト管理者はそれに合わせてサイトの処理能力を上げるため、システムのスケールアップ/アウトさせなければならないことになる。スケールアップはコストも手間もかかるので急激なトラフィック増加には対応できない。つまり必要なのはスケールアウト＝サーバー追加である。今は猫も杓子もとにかくサーバーの追加が必要な時代であるということである。しかしながら、上記のような単純なハッシュ法ではサーバーの追加に対応できないのである。

上記の単純なハッシュ法では、一台でもサーバーが増えればハッシュ値（割り算の余り）が変わってしまう。それはつまり、memcachedサーバーにキャッシュした内容を全て捨て去らなければならないという事態が発生することを意味する。所詮キャッシュなんだしオトコらしくズバッと捨てればイイじゃん！！と思うかも知れないが、それは早計というものである。捨てた瞬間、キャッシュヒット率は0%になるのでデータベースへの問い合わせが突如として増加することが容易に想像できる。そのような突発的な負荷にデータベースが耐えきれるとは思わない。データベースのサポートを生業とする俺にとって、そのような突発的な異常高負荷状態は何が何でも避けなければいけない事態であると言える。決してデータベースを無慈悲なまでの過負荷状態に陥れてはならない。そのようなことが原因でデータベースがトラブっても、そんなの仕様！以上！！本件即クローズ！！！である。（おぃっ＞俺）

しか〜〜〜っし！！コンシステントハッシュ法を使えばこのような事態をイッパツで解決することが出来る。ブラボー！！マーベラス！！エクセレント！！前置きなげーよ！！という感じである。これからはもはや猫も杓子もコンシステントハッシュ法を使わなければならない時代になったと言っても過言ではない。

コンシステントハッシュ法のアルゴリズムについては以下のサイトがわかりやすいので参照にしてもらいたい。（コンシステントハッシュ法について知らない人は何が何でも読むべし！！読みまくるべし！！熟読すべし！！）
http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing

アルゴリズムの詳細については上記のサイトに譲るのでここでは紹介しないのだが（しねーのかよ！＞俺）、自分がコンシステントハッシュ法を見て真っ先にイメージしたことをこのブログを見てくれている皆様方と共有したい。それは・・・

ホワイトノイズとホワイトノイズを重ね合わせるとホワイトノイズになる。だから各ノードに割り当てられるキーの数は確率的に同じだ！！

参考：ウィキペディア->ホワイトノイズ

そうイメージするとコンシステントハッシュ法を感覚的に理解できるのではないだろうか。（余計にワケが分からなくなったよ！！と思ったら申し訳ない！！）

イメージはさておき実際コンシステントハッシュ法は有用である。もし仮に100台のmemcachedサーバーを運用していたとすると、そこへサーバーを1台追加するときにはキャッシュのうち1/101のデータを捨てるだけで済む。逆に1台減らすときは1/100のデータを捨てるだけでいい。全てのキャッシュを捨て去ることに比べると、これは格段に小さい比率であると言える。

今日は何故かハイテンションな文章になってしまった。次回からはもう少し抑えようと思う。