memcached の分散アルゴリズム

すでに見たように、memcached の分散アルゴリズムはクライアントにゆだねられており、もっともシンプルな仕組みは、Cache::Memcached で採用されている「キーのCRC値を求め、ノードの数で割った余りでサーバを決定」というもの。

このやり方はノードの増減に弱い。そこで、基本的にはハッシュ値を使いつつも、ノードの増減に強いアルゴリズムが考案されている。

第4回 memcachedの分散アルゴリズム：memcachedを知り尽くす｜gihyo.jp … 技術評論社
にて紹介されているのが、「コンシステント・ハッシュ法(Consistent Hashing)」

で、わかりやすく説明されている。

詳しい説明がこちら。

キャッシュ用マシンを追加したら、そのマシンは他のマシンから適正な分量のオブジェクトをうけとる。同じくマシンを除去したら、除去したマシンのオブジェクトは残ったマシンがわけあう。コンシステント・ハッシュ法はまさにこう動く。可能な限り 一貫して 同じマシンに同じオブジェクトを割り当ててくれる。

コンシステント・ハッシュ法のミソは、オブジェクトとキャッシュ(キャッシュ用マシン)に同じハッシュ関数をつかうこと。キャッシュはある区間に対応づけられる。その区間は多くのオブジェクトのハッシュ値を含んでいる。キャッシュが除去されると、隣接する区間のキャッシュが除去されたキャッシュの区間を引き受ける。他のキャッシュは影響をうけない。

http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing

実際的な問題に関しての検討が以下の記事。（冒頭部だけ引用）

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

mixi engineer blog