Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。
問題
複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。
普通のハッシュ利用法だとどうなるか
オブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。
しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。
望ましいのは
キャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。
Consistent Hashingとは
キャッシュサーバを決めるのに、mod Nをしない。つまりサーバの台数に依存した計算をしない。しかしそれでどうやってキャッシュサーバを決定するのだろうか。
基本的なアイデア
ハッシュ値の値域にキャッシュサーバを表す点を配置する。例えば次の図のような具合いに。
Min Max
<------.--*------------.------.---*-----------.-*---.-> ハッシュ値空間
a α b c β d γ e
a,b,c,...: オブジェクト
α,β,γ,...: キャッシュサーバ
オブジェクトはその右側にある最も近いキャッシュサーバに配置されることにする。 つまり図では次のようになる。
- a, e → α
- b, c → β
- d → γ
(eはそれより右側にキャッシュサーバがないので先頭に戻ってαを選ぶ)
表現を変えると直前のキャッシュサーバ点から次のキャッシュサーバ点までがあるキャッシュサーバの担当区間と言える。
キャッシュサーバが追加されたら、その点より前のオブジェクトが新しいサーバに移る。 次の図ではキャッシュサーバδが追加され、オブジェクトbがδに移る。
Min δ Max
<------.--*------------.--*---.---*-----------.-*---.-> ハッシュ値空間
a α b c β d γ e
b: δに移動
キャッシュサーバが削除されたら、削除されたキャッシュサーバにあったオブジェクトは一つ右側のキャッシュサーバに移る。次の図ではキャッシュサーバβが削除され、オブジェクトcがγに移る。
Min δ Max
<------.--*------------.--*---.---------------.-*---.-> ハッシュ値空間
a α b c (β) d γ e
c: γに移動
影響の分散・負荷の均等
たしかにキャッシュサーバの増減があっても最小限しかキャッシュは移動しないが、これではキャッシュサーバの担当区間の大きさに著しい偏りが生じるではないかという疑問が当然出てくる。
そこでどうするかというと、キャッシュサーバの担当区間を多数の小さい区間に細かく分割し、それらの小区間がばらばらに入り交じるようにランダムに配置する。ばらばらに入り交じるようにとは、あるキャッシュサーバの小区間が様々なキャッシュサーバの小区間に隣接するようにということ。これがこのアルゴリズムの最大の要点。
この区間分割はハッシュ値域に配置するキャッシュサーバ点をサーバごとに一つではなく値域全体に渡って多数ランダムに配置することで実現される。
こうすることによって、キャッシュサーバ増減の影響は目出度く様々なキャッシュサーバに分散される。例えばキャッシュサーバが取り除かれるときはある小区間がキャッシュサーバγに吸収され、ある小区間がαに吸収され……となる。
またランダムに点を配置するためにそれぞれの小区間の大きさはばらつくものの、それらを合わせた担当区間の大きさの合計は大数の法則によりある程度均等になることが期待できる。
どれくらいに分割するのがいいかというと、件の記事では10のキャッシュサーバの場合で100〜200程度という目安を示している。
