Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。
問題
複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。
普通のハッシュ利用法だとどうなるか
オブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。
しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。
望ましいのは
キャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。
Consistent Hashingとは
キャッシュサーバを決めるのに、mod Nをしない。つまりサーバの台数に依存した計算をしない。しかしそれでどうやってキャッシュサーバを決定するのだろうか。
続きを読む