概念・定理図鑑 · 基礎から応用へ

コンシステントハッシュ:配置変更の範囲を限定する

ハッシュリング上の所有者を計算し、仮想ノード、偏り、再配置と整合性の責務を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 台数で割る配置の変更を考える
  2. リングで所有者を求める
  3. 仮想ノードは負荷を自動で均等にしない
  4. 配置、移送、整合性は別の仕事
  5. この記事をロゲイアに質問する理解を確かめる

台数で割る配置の変更を考える

キーをハッシュしてNで割った余りで保存先を決めると、Nを変更したときに多くのキーの保存先が変わる場合があります。コンシステントハッシュは、キーと参加ノードを同じハッシュ空間へ配置し、参加者の追加や削除で移るキーの範囲を限定する考え方です。ここでは円環上の位置から時計回りで次のノードを所有者にする方式を使います。すべての実装が同じリング方式とは限りませんが、配置の安定性と負荷の均等性を分けて考える入口になります。

リングで所有者を求める

説明用の0以上100未満の円環で、ノードAを20、Bを60、Cを90へ置きます。キーの位置10はA、45はB、75はC、95は円周を回ってAが担当します。位置40にDを追加すると、20より大きく40以下の範囲の担当が、BからDへ変わります。例えば30はDへ移りますが、45はBのままです。元の担当はその範囲ではBであり、移動はBからDへの引き継ぎです。すべてのキーを再配置する必要はありませんが、その範囲のデータ移送と更新の調整は必要です。

仮想ノードは負荷を自動で均等にしない

物理ノードを一つの位置だけで表すと、担当する円弧の長さにばらつきが出ます。一台へ複数の位置を割り当てる仮想ノードは、担当範囲を分散させ、容量に応じた重み付けにも使えます。ただし、キーの人気が極端に偏る場合、キー数や円弧の長さが等しくても要求負荷はそろいません。同じ人気キーへの大量アクセスは、仮想ノード数を増やしただけでは分割できません。キー数、データ量、要求数、書き込みの重さを別々に観察し、複製やキャッシュなど必要な対策を検討します。

配置、移送、整合性は別の仕事

ノード追加時には、古い配置表と新しい配置表を参照するクライアントが混在する場合があります。移送中の書き込みをどこへ送り、二重化するか、古いコピーをいつ削除するかを定めないと、配置の計算が正しくてもデータを失えます。複製先を時計回りに選ぶ設計では、異なる物理ノードや故障領域へ置くことも確認します。コンシステントという名前は、読み取りが常に最新になる意味ではありません。メンバーシップ、ルーティング、移送、版管理と整合性の規約を合わせて設計して、初めて保存システムとしての保証を説明できます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 18

学習コースから次を選ぶ