スマートな分散で快適キャッシュライフ

今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。

問題定義

分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬とはいえ、ホットスポットのレコードが全てキャッシュミスしたらデータベース層に多大な負荷がかかってしまい、最悪の場合データベース層と共にウェブサイトが破綻してしまうという事です。ウェブサイトの規模にもよりますが、少なくともmixiは破綻してしまうでしょう。

Consistent Hashingで悪あがき

ここでConsistent Hashingが役に立ちます。libketamaの解説を基に説明すると、個々のノードは100〜200個のunsigned int（仮想ノード）にハッシュされ、それらの整数は0から2^32の連番で構成されている円(wheelやcontinuumと呼ばれている物)の中に配置されます。つまり個々のノードは多数の整数によってマッピングされた事になります。

libketamaに仮想ノードというコンセプトが存在する理由はTom Whiteのブログエントリー（日本語訳）で紹介された様に仮想ノードが無ければノード間でレコード分布が非一様になる危険性が存在するからです。

この状況が成立するとレコードのキーを0から2^32の間の整数にハッシュし、その数字が円の中でノードにマッピングされているかを確認する事ができます。マップされていたら、マップ先のノードにレコードを格納する、もしマップされていなかったら次に大きくてマップされている整数の先のノードに格納されます（オリジナルのアルゴリズムでは最も近い整数と定義されています）。

もし次に探索する値が限界値（例えば2^32)を超える様であったら、登録されている一番最初のノードにレコードを格納します（つまり円を一周した事になる）。

で、この構成の何処が嬉しいのか？というのはノードのサービスアウトをビジュアライズすると明らかになります。文章より図の方が解り易いかな〜と思ったのでもう一枚図を用意させて頂きました。

上記の図で解るようにConsistent Hashingを用いるとノードをプールから取り除いた場合にデータロスの損害が比較的に少なく済む事が解ります。逆の見かたをするとノードを追加する度にレコードを全てリハッシュしなくて良いという強力な利点の存在が見えます。

とまあ仕組み的にはこんな感じですが、もっと詳しく知りたい方は本家のDavid Kargerのスライドが参考になります。

実際の効果

Consistent Hashingを使うのと使わないのでは結果に明らかな差が生まれます。以前、kazeburoさんとCache::Memcached::Fastのketama実装を試してみた時の結果では以下の様な事になりました。初期セットアップはサーバ4台、レコード数は5000件です。そこにサーバを一台追加してみました。結果は：

合計台数	追加台数	ヒット率
5	1	77%

そして更に一台追加すると：

合計台数	追加台数	ヒット率
6	2	64%

良い感じっぽいので、最後にもう一台追加：

合計台数	追加台数	ヒット率
7	3	58%

ん〜む、上記の結果を見るだけでは効果があるのかが今いちピンときませんよね？という事でConsistent Hashingをdisableした状態で4台→5台増加のテストを行ってみたところ、結果（ヒット率）は19%でした。 Consistent Hashingを使うのと使わないのでは、評判通り結果がかなり違う事が解ります。

まとめ

今回はConsistent Hashingの実用性に関して語らせて頂きました。軽く行った比較テストの結果でConsistent Hashingを使うのと使わないのではキャッシュのヒット率に明白な差が生まれる事を観測する事が出来ました。今後、ウェブサイトのパフォーマンス向上にmemcachedのプールを設置する事を考えている方はソリューションの一つとして考慮に入れる価値があるかと思います。

今回のネタは色々なところで書かれていたりと、珍しい話ではありませんが実際に使って結果を見てみるとアルゴリズムの重要さと楽しさが体験できて良い刺激になります。これからもちょくちょくバックエンドに関する面白いネタを発見し、mixiに役立てながら皆さまとも共有していきたいと思う今日この頃です。