設計パターン・最適化図鑑 · 基礎から応用へ

Rendezvous hashingで担当を選ぶ

キーと安定IDのスコアから、ノード追加・削除、同点、複製、重み、計算費用を分けて考えます。

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

更新日

この記事の目次
  1. キーと候補の組を採点する
  2. 追加と削除の変化を計算する
  3. 文字列と同点の規則を固定する
  4. 複製と重みは別の規則として加える
  5. 移動量と計算費用を比べる
  6. 上位候補をキャッシュするときの条件
  7. 最高点と次点を読む課題
  8. この記事をロゲイアに質問する理解を確かめる

キーと候補の組を採点する

Rendezvous hashingは、キーと各ノードの安定IDの組から決定的なスコアを作り、最も高い候補を担当にする配置方式です。最高乱数重み法と呼ばれることもありますが、毎回新しい乱数を振る方式ではありません。前提はハッシュと分割です。同じキー、同じ候補集合、同じ計算規則なら、複数のクライアントが同じ担当を選べることが出発点です。リング上の点を検索するConsistent hashingとは、担当の計算方法が違います。

説明用にorder-7のスコアをA=17、B=81、C=54と置けばBです。D=90を追加するとDへ移ります。order-8がA=91、B=24、C=40、D=12なら、Dの追加後もAです。表の数字は方式を追うための仮定で、特定のハッシュの実測出力ではありません。新しい候補が最高にならないキーでは、以前の候補同士の順位は変わらないことを確認します。この性質には、既存のIDとスコア計算を変えないという条件があります。

追加と削除の変化を計算する

ノード追加では、追加した候補が従来の最高点を超えたキーだけが移ります。削除では、そのノードが担当していたキーだけが、残りの候補の次点へ移ります。全キーのスコアを全ノードについて計算し直しても、既存のスコアが同じなので、この局所的な変更が成り立ちます。単純な実装では一回のlookupにN候補の計算が必要です。リングの検索と比べ、メタデータ、候補数、キャッシュできるものが違うため、方式名だけで速さを決めないでください。

メンバー集合がクライアントごとに違えば、同じキーでも違う最高点を選びます。ノードが見えないときに独自に候補から外す設計は、権威ある担当を変える場合があります。到達可能な代替先へ読むことと、書込みの所有権を変えることを分けます。構成の世代、更新の伝播、古い担当の拒否や誘導は、Rendezvousでも必要です。ハッシュ関数はメンバー変更への合意や、実データのコピーを自動では実行しません。

キーABCD追加前→追加後
order-717815490B→D
order-891244012A→A

文字列と同点の規則を固定する

キーとノードIDを単純につなぐと、abとc、aとbcが同じabcになる場合があります。長さを含む符号化や明確な構造を使い、同じ組が同じバイト列になる規則を定めます。文字の正規化、UTF-8などの符号化、整数への読み方、ハッシュの版を固定します。スコアの同点には安定IDの順を使うなど、全実装で一致する規則が必要です。ネットワークから届いた順を同点解決へ使えば、同じ候補でも選ぶ先がずれる可能性があります。

Pythonの組込みhashなど、プロセスで変わり得る値を仕様なしで永続的な配置へ使いません。実装を別言語へ移すときも、文字列の同じ見た目だけで互換性を仮定せず、固定の入力と全スコア、選んだ先をテストベクトルへ残します。安定したノードIDはIPアドレスと同じとは限りません。単なるアドレス変更で全キーが別の候補へ動く設計を望むかを検討し、論理IDと接続先を分ける場合は対応の更新も管理します。

複製と重みは別の規則として加える

複製先をk台選ぶなら、スコア上位kの異なる物理ノードを使う候補があります。ただし同じ障害領域ばかりなら、必要な独立性はありません。ゾーンなどの制約を加えると、単純な上位kと変わる場合があるので、選択手順を全実装で揃えます。上位を選べたことと、そこへ値が耐久に保存されたこと、書込みが確定したことは別です。クォーラムや合意の規則は引き続き必要です。

容量の重みを反映したい場合、単に整数スコアへ重みを掛ければ希望する割当比になるとは限りません。既存の重み付き方式の式、入力の一様性、同点、実装精度を確認し、有限のキーで分布と移動量を測ります。この記事の表は重みなしです。重みの変更も配置変更なので、データと権限の移行へつなぎます。重いノードを足せばキー件数だけでなく実負荷も比例して分散するという保証はなく、ホットキーや値のサイズを別に観測します。

移動量と計算費用を比べる

比較では固定したキー集合とノードIDを使い、追加前後の担当、移動件数、担当ごとの件数、最大負荷、lookupの費用を残します。キーを変えてから比べると、配置の変化と入力の変化が混ざります。ノード追加では移った先が追加ノードだけか、削除では影響したキーが元の担当分だけかを検査します。方式の性質を確かめる試験と、現実のデータ移行の完了確認は別です。副次的な実験を本文の表の数字と混ぜないようにします。

候補が非常に多い場合はスコア計算が費用になり、階層化や候補を絞る設計が考えられます。ただし絞り方が変われば元の移動性質も確認し直します。少数のキャッシュサーバーを選ぶような場面では、単純な全候補の計算が扱いやすい場合があります。必要な範囲検索があるならRange shardingも比較します。この教材はアルゴリズムの手計算で、重み付き配置や本番の検索性能を測定した記録ではありません。

上位候補をキャッシュするときの条件

同じキーの順位をキャッシュするなら、候補集合と重みの世代もキーへ含めるなど、古い順位を見分ける必要があります。新しいDを加えた後も古い最高点Bを使い続ければ、計算規則が正しくても配置の更新は届きません。キャッシュの省略による性能と、構成変更の伝播を一緒に検証します。古い担当への要求を正しく拒否できるかも、ライブ移行の手順へ戻して確認してください。

構成を更新した後の再現テストにも、キャッシュの世代を含めます。

最高点と次点を読む課題

課題はorder-7でA=17、B=81、C=54、D=90のとき、Dを外した担当と複製上位二台です。解答は担当B、Dを含む元の集合の上位二台ならDとBです。Dを外した後の上位二台を問うならBとCになります。どの候補集合の順位かを明記しないと、違う答えを比較してしまいます。上位二点を選んだだけで、二つの値が既に保存されたという解答にはしません。

追加課題は、ノードIDを全て毎回作り直す案です。解答では既存スコアも変わるため、追加ノードだけへ移るという前提を失い得ると説明します。安定ID、符号化、メンバー世代、同点処理の四つを揃える必要があります。リングとの違いをlookupの手順で説明し、共通する移行と合意の責務も挙げられれば到達点です。

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

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

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

学習コースから次を選ぶ