ノード追加で変える担当を限定する
単純にhash(key) mod Nで担当を決めると、Nを3から4へ変えたとき多くのキーの余りが変わります。Consistent hashingのリング配置は、キーと担当の点を同じ空間へ置き、ノード追加で主に新しい担当へ渡す部分だけを変更する設計です。前提は分割とリバランスです。ここでのconsistentは配置の変化に関する性質で、読取りが常に最新になる整合性の保証ではありません。配置を計算することと、値を複製して合意することを分けます。
説明用の円を0以上300未満とし、Aを0、Bを100、Cを200へ置きます。キーのハッシュ位置から時計回りに進み、最初の担当点を選びます。ちょうど同じ位置ならその点を選び、最後を越えれば0へ戻ります。キー120はC、240はAです。規則が曖昧だと境界のキーだけ実装間で違うので、点と一致したとき、円の最後、衝突の順序を具体的に決めます。ハッシュを計算する文字列やバイト列も契約の一部です。
一点を加えた前後を手で比較する
Dを150へ追加すると、Bの100を越えDの150までのキーがDへ移ります。キー120はCからDへ、170はCのまま、240はAのままです。新しい点を挿入した区間以外の担当点は変わりません。既存点を同時に全て作り直さないことが、この性質の前提です。追加のたびに全ノードの名前やseedを変えると、同じ規則の利点を失います。構成の版と、各ノードの安定IDを保存します。
Dを外したときは、Dが担当していたキーが次のCへ戻ります。この配置上の戻り方と、Dが書いた新しい値をCへ安全に戻すことは別です。故障したDからデータを読めないなら、別の複製やバックアップから回復できる必要があります。担当を再計算できるから値も残っている、とは判断しません。リバランスのガイドのコピー、追い付き、権限切替へつなぎ、古い配置で届いた要求の扱いまで含めて運用します。
| キー位置 | 追加前 | D=150の追加後 |
|---|---|---|
| 90 | B | B |
| 120 | C | D |
| 170 | C | C |
| 240 | A | A |
virtual nodeで偏りを小さくする
一台に一点だけを置くと、点の間隔が偏り、担当するキー空間も偏る場合があります。一台を複数のvirtual nodeとしてリングへ置き、離れた区間を持たせる方法が使えます。大きいノードへ多い点を割り当てることで、容量の重みを反映する候補にもなります。ただし点数の比が、そのまま有限のキーの件数や実負荷の比になるとは限りません。分布を測り、仮想点の管理、検索、移動の費用と比べます。
一つの熱いキーはvirtual nodeを増やしても一つの担当へ残ります。キー件数が均等でも、値のサイズや要求頻度は違います。仮想点の数を変えると既存の点を残す方式か、全て作り直す方式かも確認します。既存の点を保つなら追加の変化を追いやすい一方、ノードごとの点数の変更は別のリバランスです。「64個なら必ず均等」という固定値を正解にせず、キー数、最大と最小、バイト、実負荷を分けて観測します。
複製先は物理ノードと障害領域で選ぶ
リングを時計回りに三点たどるだけでは、三つとも同じ物理ノードのvirtual nodeかもしれません。複製先には異なる物理IDを選び、必要ならラックやゾーンも分けます。選択する規則は、全クライアントが同じ構成から同じ結果を出せるようにします。ただし異なる担当が同じ複製集合を計算しても、どの値を確定するかのプロトコルは別です。クォーラムやリーダーの規則を配置関数の中の暗黙の保証として扱いません。
利用できないノードを飛ばす場合は、誰を一時的な担当とし、正規の所有権へいつ戻すかを決めます。各クライアントが自分から見えるノードだけで自由に別のリングを作ると、同じキーへ別の担当を計算します。可用性を求める代替配置と、権威のある配置を混同しないでください。構成の伝播、世代、古い担当の拒否や誘導を使い、障害時の読み書きの意味を明記します。メンバー変更の合意は、ハッシュの計算だけでは完了しません。
実装の再現条件を保存する
ハッシュの種類、文字の符号化、区切り、整数のバイト順、衝突時の規則、安定したノードID、virtual nodeの名前を固定します。Pythonの組込みhashのように実行ごとに変わり得る関数を、仕様なしに永続配置へ使わないでください。付属実験ではSHA-256と固定した文字列を使い、10,000キーで三台から四台への担当を比較します。SHA-256を使うのは再現できる共通の計算のためで、全ての配置に暗号ハッシュが必須という意味ではありません。
実験は追加後に移ったキーがDだけへ向かったことと、D以外の担当が変わらないことをassertします。virtual node1個と64個の分布も出しますが、常に後者が全ての指標で良いとはassertしません。ライブデータはコピーしていません。実運用の検証には配置の比較に加え、移行中の更新と削除、再送、権限の切替を含めます。配置のテストが通っただけで本番のリバランスを完了したという記録にはしないでください。
mod方式との比較で入力を固定する
単純な余りの方式と比べる場合、同じキー、同じハッシュ、同じ追加前後のノードを使います。ノードの番号付けまで変えると、方式以外の変化が混ざります。移動したキー数だけでなく、担当ごとの件数とlookupの費用を残します。リングの移動が少なくても、一台へ偏って通常の負荷が増える例があるため、移動量だけを唯一の採用指標にはしません。
移動が少ないことと、必要な容量を使えることは別に評価します。
追加の区間を求める課題
課題はA=0、B=100、C=200へD=150を加え、キー100、120、150、170、299の担当を求めることです。解答はB、D、D、C、Aです。同じ点を含む規則と、円の最後から0へ戻る規則を使います。Dへ移すのは100より大きく150以下の区間です。半開区間のRange shardingと境界の書き方が違う場合も、採用した対応規則へ一貫して従ってください。文字だけを真似て境界を取り違えないようにします。
追加課題は、次の三点が全てAのvirtual nodeだった場合、複製数3を満たすかです。解答は、異なる物理ノード三台という要件を満たしません。点数と故障の独立性は別です。配置の変化、分布、実データの移動、複製の確定を四つに分けて説明できれば到達点です。Rendezvous hashingでは、円ではなく各候補とのスコアから担当を選ぶ方式を比較します。