一貫ハッシュ

台数を変えると全部動く

前回の余りで分ける方法には、困る所が1つあります。

3台を4台にすると割る数が変わるので、ほとんどの鍵の置き場所が変わります。

置き場所が変わるというのは、そのデータを別の台へ運ぶということです。1台足すだけで、ほぼ全件が動きます。

困ります。運んでいる間、そのデータは読めないか、古い場所と新しい場所の両方を見ることになります。

台を足す作業が、そのまま大きな障害の種になります。

円の上に並べる

一貫ハッシュは、台も鍵も同じ円の上の位置として置きます。

鍵は、自分の位置から時計回りで最初に見つけた台のものになります。

# 位置は 文字の符号の合計 に 31 を掛けて 360 で割った余り
# 31 を掛けるのは、似た名前が同じ場所に固まらないようにするため

台を1つ足すと、新しい台の手前にある鍵だけが動きます。他の台の担当は変わりません。

割る数が変わらないからです。

余りの方法は台数で割るので、台数が変われば全部の答えが変わります。円の方法は台数を式に使いません。

足した台の周りだけを見ればよくなります。

動く数を目で見る

演習の1つ目と2つ目は、同じ7件の鍵を3台と4台に配ります。

見比べると、担当が変わるのは1件だけです。残りの6件は動きません。

できません。新しい台に何も来ないなら、足した意味がありません。

減らせるのは動かさなくてよい鍵まで動かしてしまう分で、一貫ハッシュが消しているのはそこです。

演習

鍵と台の一覧を受け取り、円の上での持ち主と、台の位置を返します。

1. positions は台の名前から位置への辞書。位置は ring_position で出す
2. 鍵の持ち主は、鍵の位置以上にある台のうち位置が一番小さいもの。1つも無ければ、位置が一番小さい台へ回り込む
3. 位置が同じ台が2つあるときは名前が小さいほうを選ぶ。台が1つも無ければ owners も positions も空にする