ランデブーハッシュ

ランデブーハッシュまたは最高ランダム重み（HRW）ハッシュ^{[1] [2]}は、クライアントが可能なオプションセットの中からオプションセットに関する分散合意を達成できるようにするアルゴリズムです。典型的なアプリケーションは、オブジェクトが割り当てられるサイト（またはプロキシ）についてクライアントが合意する必要がある場合です。 ${\displaystyle k}$${\displaystyle n}$

コンシステント ハッシュは、異なる方法を使用して 特殊なケースに対処します 。ランデブー ハッシュは、コンシステント ハッシュよりもはるかに単純で、より一般的です (以下を参照)。${\displaystyle k=1}$

ランデブーハッシュは、1996年にミシガン大学のDavid ThalerとChinya Ravishankarによって発明されました。^[1] コンシステントハッシュは、その1年後に文献に登場しました。

ランデブーハッシュは、そのシンプルさと汎用性から、実世界のアプリケーションではコンシステントハッシュ よりも好まれるようになっています。 ^{[3] [4] [5]ランデブーハッシュは、モバイルキャッシング、 [6]}ルーター設計、^[7]セキュアキー確立、^[8]シャーディングと分散データベースなど、多くのアプリケーションで非常に早い段階で使用されました。[ ^9]ランデブーハッシュを使用する実際のシステムの他の例としては、Githubロードバランサー、^[10] Apache Ignite分散データベース、^[11] Tahoe-LAFSファイルストア、^[12] CoBlitz大容量ファイル配信サービス、^[13] Apache Druid、^[14] IBMのCloud Object Store、^[15] Arvadosデータ管理システム、^[16] Apache Kafka、^[17] Twitter EventBusパブリッシュ/サブスクライブプラットフォームなどがあります。^[18]

ランデブーハッシュの最初の応用例の1つは、インターネット上のマルチキャストクライアント（ MBONEなどのコンテキスト）が分散方式でマルチキャストランデブーポイントを識別できるようにすることでした。^{[19] [20]これは、1998年にMicrosoftの}キャッシュアレイルーティングプロトコル（CARP）によって分散キャッシュ調整とルーティングに使用されました。 ^{[21] [22]}一部のプロトコル独立マルチキャストルーティングプロトコルは、ランデブーハッシュを使用してランデブーポイントを選択します。^[1]

ランデブー ハッシュは、分散ハッシュ テーブル問題の一般的なバージョンを解決します。サイト セット(サーバーまたはプロキシなど) が与えられます。オブジェクト が与えられた場合、クライアント セットは、に割り当てるサイトのkサブセットにどう同意できるでしょうか。この問題の標準バージョンでは、k = 1 を使用します。各クライアントは独立して選択を行いますが、すべてのクライアントが最終的に同じサイトのサブセットを選択する必要があります。中断を最小限に抑える制約を追加し、サイトが失敗または削除された場合、そのサイトにマッピングされているオブジェクトのみを他のサイトに再割り当てする必要があることを要求すると、これは簡単ではありません。 ${\displaystyle n}$${\displaystyle O}$${\displaystyle O}$

基本的な考え方は、各サイトに各オブジェクト のスコア (重み)を与え、そのオブジェクトを最高スコアのサイトに割り当てることです。すべてのクライアントは最初にハッシュ関数 に同意します。オブジェクト の場合、サイトは重み を持つように定義されます。各クライアントは独立してこれらの重みを計算し、k 個の最大ハッシュ値を生成するk 個のサイトを選択します。これにより、クライアントは分散合意を達成しました。 ${\displaystyle S_{j}}$${\displaystyle O_{i}}$${\displaystyle h(\cdot )}$${\displaystyle O_{i}}$${\displaystyle S_{j}}$${\displaystyle w_{i,j}=h(O_{i},S_{j})}$${\displaystyle w_{i,1},w_{i,2}\dots w_{i,n}}$${\displaystyle k}$

サイトが追加または削除された場合、マッピング先のオブジェクトのみが別のサイトに再マッピングされ、上記の最小限の中断制約が満たされます。HRW 割り当ては、割り当てられるサイトのセットとオブジェクトの 識別子のみに依存するため、どのクライアントでも独立して計算できます。${\displaystyle S}$${\displaystyle S}$${\displaystyle S_{1},S_{2}\dots S_{n}}$

HRW は、サイト間の異なる容量に簡単に対応します。サイトの容量が他のサイトの 2 倍である場合、リストでは 2 倍を と表すだけです。明らかに、他のサイトの 2 倍のオブジェクトが にマップされることになります。 ${\displaystyle S_{k}}$${\displaystyle S_{k}}$${\displaystyle S_{k,1},S_{k,2}}$${\displaystyle S_{k}}$

問題の単純なバージョン、つまりk = 1 を考えてみましょう。このバージョンでは、すべてのクライアントがオブジェクトOの単一のサイトに同意する必要があります。この問題に単純にアプローチすると、 n 個のサイトをハッシュ テーブル内のバケットとして扱い、オブジェクト名O をこのテーブルにハッシュするだけで十分であるように思われます。残念ながら、いずれかのサイトに障害が発生したり、アクセスできなくなったりすると、ハッシュ テーブルのサイズが変わり、すべてのオブジェクトを再マップする必要があります。この大規模な中断により、このような直接ハッシュは実行不可能になります。

しかし、ランデブーハッシュでは、クライアントは次に大きな重みをもたらすサイトを選択することでサイトの障害に対処します。再マッピングは、障害が発生したサイトに現在マッピングされているオブジェクトに対してのみ必要であり、中断は最小限です。^{[1] [2]}

ランデブー ハッシュには次の特性があります。

1. オーバーヘッドが低い:使用されるハッシュ関数は効率的であるため、クライアントでのオーバーヘッドは非常に低くなります。
2. 負荷分散:ハッシュ関数はランダム化されるため、 n 個のサイトのそれぞれがオブジェクトO を受信する可能性は等しくなります。負荷はサイト間で均一になります。
   1. サイトの容量:異なる容量を持つサイトは、容量に比例した多重度でサイト リストに表示できます。他のサイトの 2 倍の容量を持つサイトはリストに 2 回表示され、他のすべてのサイトは 1 回表示されます。
3. 高いヒット率:すべてのクライアントがオブジェクトO を同じサイトS _Oに配置することに同意しているため、 OをS _Oにフェッチまたは配置するたびに、ヒット率の点で最大の効用が得られます。オブジェクトO は、 S _Oで何らかの置換アルゴリズムによって削除されない限り、常に見つかります。
4. 最小限の中断:サイトに障害が発生した場合、そのサイトにマップされているオブジェクトのみを再マップする必要があります。中断は最小限に抑えられ、次のことが証明されています。^{[1] [2]}
5. 分散k合意:クライアントは、順序付けで上位kサイトを選択するだけで、 kサイトに関する分散合意に達することができる。 ^[8]

上で説明したランデブーハッシュの標準バージョンは、中程度のnに対しては非常にうまく機能しますが、nが非常に大きい場合、ランデブーハッシュの階層的使用により実行時間を達成します。^{[23] [24] [25]}このアプローチは、仮想階層構造（「スケルトン」と呼ばれる）を作成し、階層を下る際に各レベルでHRWを適用することで実行時間を実現します。アイデアは、最初に定数を選択し、サイトをクラスターに編成することです。次に、定数を選択し、それぞれがファンアウトを持つ仮想ノードのツリーの葉に配置されたこれらのクラスターを想像することで、仮想階層を構築します。 ${\displaystyle n}$${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle c=\lceil n/m\rceil }$${\displaystyle C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots }$${\displaystyle f}$${\displaystyle c}$${\displaystyle T}$${\displaystyle f}$

添付の図では、クラスター サイズは、スケルトン ファンアウトは です。便宜上、108 サイト (実ノード) と仮定すると、3 層の仮想階層が得られます。 であるため、各仮想ノードには 8 進数の自然な番号が付けられます。したがって、最下位層の 27 個の仮想ノードには 8 進数の番号が付けられます (もちろん、各レベルでファンアウトを変更することもできます。その場合、各ノードは対応する混合基数で識別されます)。 ${\displaystyle m=4}$${\displaystyle f=3}$${\displaystyle f=3}$${\displaystyle 000,001,002,...,221,222}$

仮想階層を理解する最も簡単な方法は、最上位から始めて、仮想階層を下っていくことです。階層の各レベルで仮想ノードのセットにランデブー ハッシュを連続的に適用し、勝者の仮想ノードによって定義されたブランチを下っていきます。実際には、仮想階層のどのレベルからでも開始できます。階層の下位から開始すると、より多くのハッシュが必要になりますが、障害が発生した場合の負荷分散が改善される可能性があります。

たとえば、図の 108 個の実ノードすべてに HRW を適用する代わりに、まず 1 つを選択して、最下位層の 27 個の仮想ノードに HRW を適用することができます。次に、そのクラスター内の 4 個の実ノードに HRW を適用し、勝者サイトを選択します。必要なのは108 個ではなくハッシュだけです。この方法を階層の 1 レベル上から適用すると、勝者サイトに到達するためにハッシュが必要になります。図は、スケルトンのルートから開始して、仮想ノード、、を順に選択し、最終的にサイト 74 に到達する様子を示しています。 ${\displaystyle 27+4=31}$${\displaystyle 9+3+4=16}$${\displaystyle (2)_{3}}$${\displaystyle (20)_{3}}$${\displaystyle (200)_{3}}$

仮想階層は保存する必要はなく、必要に応じて作成できます。これは、仮想ノード名が単に基数(または混合基数) 表現​​の接頭辞であるためです。必要に応じて、数字から適切にソートされた文字列を簡単に作成できます。例では、文字列(階層 1)、(階層 2)、(階層 3) を操作します。明らかに、の高さは です。これは、と が両方とも定数であるためです。各レベルで行われる作業は です。これは、が定数である ためです。${\displaystyle f}$${\displaystyle 0,1,2}$${\displaystyle 20,21,22}$${\displaystyle 200,201,202}$${\displaystyle T}$${\displaystyle h=O(\log c)=O(\log n)}$${\displaystyle m}$${\displaystyle f}$${\displaystyle O(1)}$${\displaystyle f}$

の値は、予想される障害率や必要な負荷分散の程度などの要因に基づいて選択できます。 の値が高いほど、障害発生時の負荷偏りが少なくなりますが、検索オーバーヘッドは高くなります。 ${\displaystyle m}$${\displaystyle m}$

この選択は、非階層型ランデブー ハッシュと同等です。実際には、ハッシュ関数は非常に低コストなので、非常に高くない限り、非常にうまく機能します。 ${\displaystyle m=n}$${\displaystyle h(\cdot )}$${\displaystyle m=n}$${\displaystyle n}$

任意のオブジェクトについて、各リーフ レベルのクラスター、つまり各サイトが等しい確率で選択されること は明らかです。${\displaystyle n}$

必要な回復力のレベルに基づいてr を選択し、Oの最高ランクのr < mサイトに各オブジェクトO を複製することで、障害に対する回復力を高めることができます。最も単純な戦略は、リーフ レベルのクラスター内でのみ複製することです。

O用に選択されたリーフ レベルのサイトが利用できない場合は、同じリーフ レベルのクラスター内でO用に次にランク付けされたサイトを選択します。Oがリーフ レベルのクラスター内で複製されている場合は、rサイトのランク付け順で次に利用可能なサイトにO が確実に見つかります。障害が発生したサーバーによって保持されていたすべてのオブジェクトは、そのクラスター内の他のサイトに表示されます。(別のオプションは、スケルトン内の 1 つ以上の層を上に移動し、その層の兄弟仮想ノードから代替を選択することです。その後、上記のように階層を実際のノードまで下ります。)

システムにサイトが追加されると、そのサイトは、すでに他のサイトに割り当てられている一部のオブジェクトの優先サイトになる場合があります。他のクラスターにマップされているオブジェクトは、この新しいサイトにマップされることはないため、そのクラスター内の他のサイトが保持しているオブジェクトのみを考慮する必要があります。サイトがキャッシュの場合、新しいサイトにマップされているオブジェクトにアクセスしようとするとキャッシュ ミスが発生し、対応するオブジェクトが取得されてキャッシュされ、操作が通常に戻ります。

サイトがサーバーである場合、一部のオブジェクトをこの新しく追加されたサイトに再マップする必要があります。以前と同様に、他のクラスターにマップされたオブジェクトはこの新しいサイトにマップされないため、そのクラスター内のサイトが保持するオブジェクトのみを考慮する必要があります。つまり、システム内のオブジェクトのセット全体ではなく、このローカル クラスター内のmサイトに現在存在するオブジェクトのみを再マップする必要があります。このサイトにマップされる新しいオブジェクトは、もちろん自動的にこのサイトに割り当てられます。

ランデブーハッシュは、そのシンプルさ、低オーバーヘッド、汎用性（ k < nであれば動作）から、コンシステントハッシュよりも好まれるようになってきています。最近の使用例としては、Githubロードバランサ^[10] 、 Apache Ignite分散データベース^[11]、Twitter EventBus pub/subプラットフォーム^{[18]などが挙げられます。}

コンシステント ハッシュは、トークンと呼ばれる単位円上の点にサイトを均一かつランダムにマッピングすることで機能します。オブジェクトも単位円にマッピングされ、オブジェクトの位置から時計回りに移動して最初に遭遇したトークンのサイトに配置されます。サイトが削除されると、そのサイトが所有するオブジェクトは、時計回りに移動して次に遭遇したトークンのサイトに移されます。各サイトが多数のトークン (たとえば 100 ～ 200) にマッピングされている場合、残りのサイト間で比較的均一な方法でオブジェクトが再割り当てされます。

たとえば、サイト ID の 200 種類のハッシュ値を使用してサイトを円上の点にランダムにマッピングすると、オブジェクトの割り当てには、サイトごとに 200 個のハッシュ値を保存または再計算する必要があります。ただし、特定のサイトに関連付けられたトークンは事前に計算してソートされたリストに保存できるため、オブジェクトにハッシュ関数を 1 回適用し、バイナリ検索を実行して割り当てを計算するだけで済みます。ただし、サイトごとにトークンが多数ある場合でも、コンシステント ハッシュの基本バージョンでは、サイト間でオブジェクトが均一に分散されない可能性があります。これは、サイトが削除されると、そのサイトに割り当てられている各オブジェクトは、サイトのトークンと同じ数 (たとえば 100～200) の他のサイトにのみ分散されるためです。

より複雑なロジックを使用して単位円上にトークンを分散するコンシステントハッシュのバリエーション（AmazonのDynamoなど）は、基本的なコンシステントハッシュよりも優れた負荷分散を提供し、新しいサイトを追加するオーバーヘッドを削減し、メタデータのオーバーヘッドを削減し、その他の利点を提供します。^[26]

ランデブー ハッシュ (HRW) は、概念的にも実際的にもはるかに単純です。また、均一なハッシュ関数が与えられれば、オブジェクトをすべてのサイトに均一に分散します。コンシステント ハッシュとは異なり、HRW ではトークンの事前計算や保存は必要ありません。k =1 の場合を考えます。ハッシュ値を計算し、最も高いハッシュ値を生成するサイトを選択することで、オブジェクトはサイトの1つに配置されます。新しいサイトが追加されると、新しいオブジェクトの配置または要求によってハッシュ値が計算され、そのうち最大のものが選択されます。システム内の既存のオブジェクトがこの新しいサイト にマップされる場合、そのオブジェクトは新たに取得され、 にキャッシュされます。今後、すべてのクライアントはこのサイトからオブジェクトを取得し、 の古いキャッシュされたコピーは最終的にローカル キャッシュ管理アルゴリズムによって置き換えられます。 がオフラインになると、そのオブジェクトは残りのサイトに均一に再マップされます。 ${\displaystyle O_{i}}$${\displaystyle n}$${\displaystyle S_{1},S_{2}\dots S_{n}}$${\displaystyle n}$${\displaystyle h(O_{i},S_{j})}$${\displaystyle S_{k}}$${\displaystyle S_{n+1}}$${\displaystyle n+1}$${\displaystyle S_{k}}$${\displaystyle S_{n+1}}$${\displaystyle S_{n+1}}$${\displaystyle S_{k}}$${\displaystyle S_{k}}$${\displaystyle n-1}$

スケルトンの使用などの HRW アルゴリズムのバリエーション (下記参照) は、オブジェクトの配置にかかる時間を に短縮できますが、配置の全体的な均一性は低下します。ただし、 が大きすぎない場合、基本的な HRW の配置コストは問題になりません。HRW は、各サイトおよび関連するメタデータの複数のトークンを正しく処理することに関連するすべてのオーバーヘッドと複雑さを完全に回避します。 ${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle n}$${\displaystyle O(n)}$

ランデブー ハッシュには、分散合意などの他の重要な問題に対しても簡単なソリューションを提供するという大きな利点もあります。 ${\displaystyle k}$

ランデブー ハッシュは、コンシステント ハッシュよりも単純かつ一般的です。コンシステント ハッシュは、2 桁ハッシュ関数を適切に選択することで、HRW の特殊なケースとして示すことができます。サイト識別子から、最も単純なバージョンのコンシステント ハッシュは、トークンの位置のリストを計算します。たとえば、は単位円上の場所に値をハッシュします。2 桁ハッシュ関数を と定義します。 は単位円に沿ったからまでの距離を表します(はゼロ以外の最小値を持つため、この値をある制限された範囲内の一意の整数に変換しても問題ありません)。これにより、コンシステント ハッシュによって生成された割り当てが正確に複製されます。 ${\displaystyle S}$${\displaystyle t_{s}=h_{c}(S)}$${\displaystyle h_{c}}$${\displaystyle h(S,O)}$${\displaystyle {\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}}$${\displaystyle h_{c}(O)-t_{s}}$${\displaystyle h_{c}(O)}$${\displaystyle t_{s}}$${\displaystyle h_{c}(O)-t_{s}}$

ただし、HRW は削除されたサイトのオブジェクトを無制限の数の他のサイトに再割り当てする可能性があるため、HRW を一貫性のあるハッシュに縮小することはできません(サイトあたりのトークンの数に制限があると仮定)。

ランデブー ハッシュの標準実装では、各ノードは静的に等しい割合のキーを受け取ります。ただし、割り当てられたキーを処理または保持するノードの容量が異なる場合、この動作は望ましくありません。たとえば、ノードの 1 つが他のノードの 2 倍のストレージ容量を持っている場合、この強力なノードが他の各ノードの 2 倍の数のキーを受け取るようにアルゴリズムでこれを考慮することができれば有益です。

このケースに対処するための簡単なメカニズムは、このノードに 2 つの仮想ロケーションを割り当て、その大きなノードの仮想ロケーションのいずれかに最高のハッシュがある場合に、そのノードがキーを受け取るようにすることです。ただし、相対的な重みが整数倍でない場合は、この戦略は機能しません。たとえば、1 つのノードのストレージ容量が 42% 多い場合、さまざまな割合で多くの仮想ノードを追加する必要があり、パフォーマンスが大幅に低下します。この制限を克服するために、ランデブー ハッシュに対するいくつかの変更が提案されています。

キャッシュアレイ ルーティング プロトコル(CARP) は、1998 年の IETF ドラフトで、各ノードのハッシュ スコアを乗じてノードに異なる重み付けを行うための任意の精度レベルを生成できる負荷係数を計算する方法を説明しています。 ^[21]ただし、このアプローチの欠点の 1 つは、ノードの重みが変更された場合、またはノードが追加または削除された場合、すべての負荷係数を再計算して相対的にスケーリングする必要があることです。負荷係数が互いに変化すると、重みは変更されていないが、システム内の他のノードと比較して負荷係数が変化するノード間でキーの移動がトリガーされます。これにより、キーが過剰に移動します。^[27]

スケーラブルハッシュ法またはCRUSH法^{[28]による制御された複製は、RUSH法[29]}の拡張版であり、擬似乱数関数（ハッシュ）を使用してツリーを構築し、特定のキーを最終的に処理するノードを見つけることにより、ランデブーハッシュ法を改良する。ノードの追加に対しては完全な安定性が認められるが、ノードの削除や重み付けの変更に対しては、キーの過剰な移動がツリーの高さに比例するため、完全には安定しない。

CRUSHアルゴリズムは、Cephデータストレージシステムによって、データオブジェクトをそれらを保存するノードにマッピングするために使用されます。^[30]

2005年、クリスチャン・シンデルハウアーとグンナー・ショメーカーは、ノードの重みが変わったり、ノードが追加または削除されたりしても負荷係数の相対的なスケーリングを必要としない方法でハッシュスコアを再重み付けする対数法を説明しました。 ^[31]これにより、ノードに再マッピングする必要があるキーの数が最小限で済むため、ノードに重み付けする際の完全な精度と完全な安定性という2つの利点が得られます。

同様の対数ベースのハッシュ戦略は、Cleversafeのデータストレージシステム（現在はIBM Cloud Object Storage）のストレージノードにデータを割り当てるために使用されています。^[27]

ランデブーハッシュは、実世界のシステムで広く使用されています。その一部を挙げると、Oracleのデータベースインメモリ、^[9] GitHubロードバランサー、^[10] Apache Ignite分散データベース、^[11] Tahoe-LAFSファイルストア、^[12] CoBlitz大容量ファイル配信サービス、^[13] Apache Druid、^[14] IBMのクラウドオブジェクトストア、^[15] Arvadosデータ管理システム、^[16] Apache Kafka、^{[17] Twitter EventBusパブリッシュ/サブスクライブプラットフォーム[18]}などがあります。

ハッシュ関数 を選択すれば、実装は簡単です(HRW 方式の元の作業ではハッシュ関数の推奨が示されています)。^{[1] [2]}各クライアントは、各サイトのハッシュ値を計算し、最大の値を選択するだけです。このアルゴリズムは時間内に実行されます。ハッシュ関数が効率的であれば、非常に大きくない 限り実行時間は問題になりません。${\displaystyle h(\cdot )}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle n}$

重み付きランデブーハッシュを実装するPythonコード: ^[27]

 mmh3
をインポートします。math をdataclassesからインポートします。dataclass を enteringからインポートします。Listをインポートします。
   
   

def  hash_to_unit_interval ( s :  str )  ->  float : 
"""文字列を単位間隔 (0, 1] にハッシュします""" return ( mmh3 . hash128 ( s ) + 1 ) / 2 ** 128    
         

@dataclass 
class  Node : 
"""重み付けされたランデブーハッシュの一部としてキーが割り当てられたノードを表すクラス。""" name : str weight : float    
     
     

    def  compute_weighted_score ( self ,  key :  str ): 
        score  =  hash_to_unit_interval ( f " { self . name } : { key } " ) 
        log_score  =  1.0  /  - math . log ( score ) 
        return  self . weight  *  log_score

def  determine_responsible_node ( nodes :  list [ Node ],  key :  str ): 
"""さまざまな重みのノード セットのうち、どのノードが指定されたキーを担当するかを決定します。""" return max ( nodes 、key = lambda node : node . compute_weighted_score ( key )、default = None )    
     
            

WRH の出力例:

>>> wrhをインポート >>>ノード 1 = wrh 。ノード( "node1" , 100 ) >>>ノード 2 = wrh 。ノード( "node2" , 200 ) >>>ノード 3 = wrh 。ノード( "node3" 、300 ) >>> str ( wrh . determine_responsible_node ([ node1 、node2 、node3 ]、"foo" )) "ノード (名前 = 'node1'、重み = 100)" >>> str ( wrh .determine_responsible_node ( [ node1 , node2 , node3 ] , "bar" )) "Node(name='node2', weight=300)" >>> str ( wrh .determine_responsible_node ([ node1 , node2 , node3 ], "hello" )) "Node(name='node2', weight=300)" >>> nodes = [ node1 , node2 , node3 ] >>> from collections import Counter >>> responsible_nodes = [ wrh . determine_responsible_node ( ... nodes , f "キー: {キー} " ) 。範囲( 45_000 )のキーの名前] >>> print ( Counter ( responsible_nodes )) Counter({'node3': 22487, 'node2': 15020, 'node1': 7493})
   
   
   
   

   

   

    
   
  
         

• ランデブーハッシュ：コンシステントハッシュの代替