実験・実装 · 基礎から応用へ

固定キーでハッシュ配置の変化を測る

10,000キーと安定ハッシュで三台から四台を比較し、移動先、件数の偏り、virtual node、元の配置の復元を検査します。

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

更新日

この記事の目次
  1. 同じキー集合で追加前後を比べる
  2. 決定的なハッシュと円の検索を読む
  3. 移った先がDだけかをassertする
  4. 一つのリングで移動率が大きい理由を見る
  5. データを動かす前に必要な検査
  6. 担当件数の合計を保存する
  7. キーを変えない比較の課題
  8. この記事をロゲイアに質問する理解を確かめる

同じキー集合で追加前後を比べる

この実験はkey-0からkey-9999までの10,000キーを、三台A、B、Cと、Dを足した四台へ配置します。前提はConsistent hashingです。動かすのは担当を計算する関数だけで、実データのコピーや権限切替は行いません。固定の文字列とSHA-256を使い、実行するたび同じ配置を再現します。別のキーを生成して比べると、構成変更の効果と入力の違いが混ざるため、追加前後でKEYSを共有します。

一台あたりのvirtual nodeを1個と64個に分け、それぞれで追加前後を検査します。二つの設定を同じ移行の途中状態とは扱いません。virtual node数自体を変えると既存の配置も変わるため、各設定内で三台から四台への差を求めます。比較の指標は移動する件数と担当ごとの件数です。時間やネットワークの転送量は測っていません。件数の均等と、本物のバイト数や要求頻度の均等も別です。

決定的なハッシュと円の検索を読む

コードをrebalance.pyへ保存し、Python 3.12以降でpython rebalance.pyとして実行します。hashlib、bisect、collectionsだけを使います。キー文字列はUTF-8へ符号化し、SHA-256のバイト列をbig-endianの整数へ読みます。virtual nodeはA:v0などの固定した名前です。点と物理ノードの組をソートし、キーの値以上の最初の点をbisect_leftで選びます。末尾を越えたら点の数で剰余を取り、円の最初へ戻ります。

Pythonの組込みhashは使いません。別プロセスでも同じ結果を必要とする配置では、計算の版と入力の符号化を固定する必要があるためです。このコードの既知の短いIDと区切りで意味が明確な名前を作ります。一般の任意文字列へ広げるなら、区切りの曖昧さを避ける規則を定めてください。同じハッシュ点にはソートされた物理IDの順が関係するので、同点処理も仕様に含めます。SHA-256の選択だけで全入力の表現が自動で正規化されるわけではありません。

移った先がDだけかをassertする

beforeとafterの担当が違うキーをmovedへ入れます。追加ノードDだけが新しい点を持ち、既存の点は変わらないので、移ったキーのafterが全てDであることをassertします。D以外へ残ったキーは元の担当と同じであることも確認します。最後にDを外して元の三台で再計算し、beforeと完全一致することを検査します。この一致は担当関数の性質で、Dへ書いた値を元の担当へ戻したという意味ではありません。

全キーの担当が存在すること、件数の合計が10,000であることも出力から確認できます。ノードIDの名前を追加時に変えたり、既存のvirtual nodeを別のseedで作り直したりすると、元の局所的な移動性を失う場合があります。そういう変更を試すなら、Dだけへ移るassertが失敗する理由を記録します。assertを消して何でも通すのではなく、どの配置の性質を維持したいかへ戻って設計を選びます。

python
import bisect,collections,hashlib
KEYS=[f'key-{i}' for i in range(10000)]
def digest(text):return int.from_bytes(hashlib.sha256(text.encode()).digest(),'big')
def place(nodes,virtuals):
    points=sorted((digest(f'{node}:v{v}'),node) for node in nodes for v in range(virtuals))
    tokens=[p[0] for p in points]
    return [points[bisect.bisect_left(tokens,digest(key))%len(points)][1] for key in KEYS]
for virtuals in [1,64]:
    before=place(['A','B','C'],virtuals);after=place(['A','B','C','D'],virtuals)
    moved=[i for i in range(len(KEYS)) if before[i]!=after[i]]
    assert moved and all(after[i]=='D' for i in moved)
    assert all(before[i]==after[i] for i in range(len(KEYS)) if after[i]!='D')
    restored=place(['A','B','C'],virtuals);assert restored==before
    print('virtuals',virtuals,'moved',len(moved),'before',dict(collections.Counter(before)),'after',dict(collections.Counter(after)))
print('placement verified; no live data was copied')

一つのリングで移動率が大きい理由を見る

今回の1点構成では追加前のCが8651キーを持ち、D追加で5593キーがDへ移りました。64点構成ではDへ2566キーが移り、追加後の各担当は2301、2365、2768、2566でした。これはこの固定したハッシュとキーの結果です。一点のリングが大きく偏る例であり、追加時の移動率が必ず四分の一になるという保証ではありません。平均的な期待の説明と、一つの有限なリングの観測を区別します。

64点ではこの入力の件数の偏りが小さく見えますが、全てのキー集合で必ず最良とはassertしていません。点数を増やすとメタデータと検索の費用も増えます。ホットキーが一つなら、件数が均等でも負荷が偏ります。キーのサイズや頻度を追加した重み付きの評価は別の実験として設計します。掲載コードは固定入力で正常終了し、移動先と復元を確認していますが、本番の性能や通信量を測った証跡ではありません。

データを動かす前に必要な検査

実装へつなぐなら、担当が変わったキーを本当にコピーし、移動中の更新と削除を追い、どの配置世代で書けるかを切り替える必要があります。このコードの最後のprintも、live dataはコピーしていないと明示します。配置の復元が成功したから、古いサーバーへそのまま切り戻してよいとは言えません。切替後の更新がどこにあるかを確認します。重複排除IDや未送信の予定も含むなら、移動対象の一覧へ加えます。

新規ノードの追加が失敗して途中で止まる場合、配置の公開前か公開後かで復旧の手順が違います。計算したafterを全クライアントへ同時に渡せるという仮定も、実環境では検証が必要です。構成の伝播と権限の境界をリバランスの段階表へ戻してください。模型の便利さを保ちながら、現実に実行していないことを区別して書くことで、次の実装の不足を具体的に見付けられます。

担当件数の合計を保存する

出力の辞書の値を足すと、追加前後でそれぞれ10,000になることを確認します。担当が変わった5593や2566は、全キーが消えた数でも、送信が終わった数でもありません。beforeとafterの同じ位置の担当が違う件数です。配置の検査を運用の転送進捗へつなぐ場合は、コピー、追い付き、切替のそれぞれで別のカウンタを持ちます。

指標の単位を件数かバイトかで揃えて比較します。

キーを変えない比較の課題

課題は追加前を10,000キー、追加後を別の10,000キーで計測する案です。解答は、同じキーの担当変化を比較できず、移動件数という指標にならない、です。KEYSを固定し、各キーのbeforeとafterを対応させます。新しいキーの分布を見る別の問いなら、その実験としてラベルを付けます。入力、構成、指標の三つを混ぜないでください。固定のハッシュでも、入力が違えば観測は変わります。

追加課題はDを削除してbeforeへ戻ったから値も復元できたと結論する案です。解答では担当の計算しか行っておらず、値の保存も移動もないと説明します。終了後に停止するサービスや削除するDBはありません。保存したコードと出力を、配置の性質の検証として残します。移動率、偏り、ライブコピー、読書きの保証を四つの別の問いとして述べられれば到達点です。

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

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

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

学習コースから次を選ぶ