集合ハッシュリング (Rendezvous Hashing)：ステートレスで高機能な分散ハッシュリングの実装とベンチマーク

一貫ハッシュリング（Consistent Hashing）は、分散 Elixir システムにおいて分散レートリミッターやキャッシュなどの重要な構成要素を実現する土台となります。

以前にこのテーマについて執筆しましたが、今回はより簡潔で汎用的な「集合ハッシュリング」のメリットと実装方法について解説します。

現状の課題：ExHashRing の弱点

分散システムにおいてノードへのキー割り当てを行う最も一般的なライブラリは、Discord が開発した

ExHashRing

しかし、いくつかの弱点があります：

• プロセスの起動と管理が必要: リングのプロセスを開始し、**監督木（supervision tree）**の下に配置する必要があります。
• 状態の保持: プロセスは永続的なオブジェクトとして状態を持ち続けており、その管理が常に必要となります。

著者は、このように「ステートフル」な代替案を求め、ステートレスな関数型アプローチに興味を惹かれました。

集合ハッシュリング (HRW) の概要

集合ハッシュリング（Rendezvous Hashing）は、ExHashRing よりもはるかにシンプルかつ汎用的です。ウィキペディアでは「最高ランダム重量（Highest Random Weight: HRW）」とも呼ばれます。

実装の簡易性比較

ExHashRing の例:

{:ok, ring} = ExHashRing.Ring.start_link()
Ring.add_nodes(ring, ["a", "b", "c"])

Ring.find_node(ring, "key1")
# => "b"

HRW の例（ステートレス）:

HRW.owner("key1", ["a", "b", "c"])
# => "b"

HRW の主な特徴

• 状態不要: プロセスの起動や初期設定が不要です。
• 純粋な関数: 入出力に基づく関数プログラミングアプローチです。
• クラスタ跨ぎの整合性: マシンを跨いで一貫性が保たれ、ノードリスト変更時にドリフト（偏移）が発生しません。

パフォーマンスベンチマークと分析

1. ノード数が少ない場合（例：14 ノード）

ExHashRing は極めて高速ですが、HRW も実用的な速度でした。

• 比較:

  HRW.owner

  は ExHashRing の約 1.11 倍（+42.93 ns）遅いです。
• 結論: ノード数が少ない場合のホットパスでは、この程度の差は無視できると判断されます。

2. ノード数が多い場合（例：10,000 ノード）

ノード数が指数関数的に増加すると、アルゴリズムの違いが顕著になります。

• 比較:

  HRW.owner

  は ExHashRing の約 4,200 倍遅いです（+2.20 ms）。
• 許容範囲: マシンでは約 2 ミリ秒かかりますが、用途によっては十分かもしれません。ただし、線形計算（O(n)）のためノード増大に弱いです。

基本アルゴリズムの実装と改善

基礎的な HRW アルゴリズム

キーを各ノードに対してハッシュ計算し、最大値を持つノードを返すというシンプルなお作法です。

BEAM

:erlang.phash2

defmodule HRW do
  def owner(key, nodes) do
    Enum.max_by(nodes, fn node ->
      :erlang.phash2({key, node})
    end)
  end
end

HRW スケレトン（骨格）による最適化

ノード数が増える際の性能劣化を解消するため、ウィキペディアにあるクラスター分割技術を採用しました。

1. ノードリストをソートしてクラスターに分割する。
2. まずクラスターのアドレスを計算し、該当クラスター内のノードのみをハッシュする。

これにより、計算量は O(n) から O(log n) に改善されました。

スケレトンを使用したベンチマーク結果（10,000 ノード）

• 比較:

  • HRW.owner (skeleton)

    は ExHashRing の約 3.06 倍遅い（+0.00095 ms）。
  • 改善効果: 処理時間を2 ミリ秒から 141 マイロ秒に大幅短縮しました。
• 注意点: スケレトン構造体は追加/削除時にリストシフトが発生するため、厳密にはソート済みリストの扱いを考慮する必要がありますが、多くのユースケースで十分なトレードオフです。

ハッシュ関数の分布特性比較

ノード集合全体に対するワークロードの分散効率も検証しました。 キー数を 10 万、ノード数をそれぞれ 10, 100, 1000 と変化させた場合の標準偏差（stddev）を比较しました。

ベンチマーク結果のまとめ

ノード数：10 (理想的には各ノード 10,000 キー)

• murmur3 x64_128

  : 最良（平均値の 0.98% の偏差）

• murmur3 x86_32

  : 平均値の 1.12% の偏差

• phash2 (HRW)

  : 平均値の 2.5% の偏差

ノード数：100 (理想的には各ノード 1,000 キー)

• murmur3 x86_32

  /

  x64_128

  : 平均値の約 2.7〜2.9% の偏差（最良）

• HRW.Skeleton

  : 平均値の 4.66% の偏差

• ExHashRing

  : 劣悪（平均値の 27.97% の偏差、Min: 0 あり）

ノード数：1000 (理想的には各ノード 100 キー)

• murmur3 x64_128

  /

  x86_32

  : 平均値の約 9.6〜9.8% の偏差（最良）

• HRW.Skeleton

  /

  phash2

  : 平均値の約 9.8〜9.9% の偏差

• ExHashRing

  : 劣悪（平均値の 31.42% の偏差、Min: 0 あり）

考察

• :erlang.phash2

  は十分なパフォーマンスを発揮しており、特に小規模ノード数では最善の結果を出します。

• MurMurMurmur3

  はノード数が少ない場合にわずかに優れていますが、本質的な違いではありません。
• 最大の教訓: デフォルト設定の ExHashRing は、ノード数が増えるほど分布が偏りやすく（Min: 0 など）、大きなノード数で苦労することがわかりました。解決策は vnodes の増加ですが、今回は HRW がそれを回避できることを示しました。

結論と推奨事項

当プロジェクトでは、Hex.pm で公開した

hrw

シナリオ別への推奨

1. 超大規模ノード数の場合:

   • ExHashRing

     または

     HRW.Skeleton

     を使用することを推奨します。
2. 一般的なユースケースの場合:
   • ステートレスであり、設定が不要な単純な

     HRW.owner

     の使用を継続することを強く推奨します。

当ライブラリにはさらに拡張機能も含まれています：

• HRW.Weighted

  : ノードに重み付けを付与し、特定ノードにキー空間を割り当てる（不均一なクラスタ向け）。

• HRW.Bounded

  : キーの内容が事前にわかっている場合、分布の精度を高める機能。

どのようなご感想かお知らせください。