一貫性ハッシュアルゴリズムとは何ですか?

この記事はWeChatパブリックアカウント「Compass Krypton Gold Entrance」から転載したもので、著者はCompass Krypton Gold Entranceです。記事の転載については、コンパスクリプトンゴールドエントランス公式アカウントまでご連絡ください。

1. 前に書く

週末は太陽のようなもので、いつも来ていつも去っていきます。

現時点では、そうです、土曜日です！そして週末は休みです！

昨夜はビリビリで長い動画を何本か見たので、2時に寝てしまいました。朝起きたらもう10時でした。

友人全員に心温まるリマインダーを送ります。私たちは皆若者ですが、規則正しいスケジュールを守り、早寝早起きをする必要があります。

[[334228]]

では、早速今日の話題を始めましょう。

一貫性ハッシュアルゴリズムとは何ですか?

2. 「円」という言葉の文字通りの意味

この言葉を初めて聞いたとき、私はそれが何を意味するのか混乱しました。

一貫性は理解しています

ハッシュアルゴリズムについても知っている

一貫性 + ハッシュ アルゴリズムとは何ですか?

私は比較的頭が空っぽですが、ネットユーザー全員がこの用語を知っているとは思えないので、知乎で質問を見つけて、自分で書いたのだと思いました。

ダバイのように、あまり頭が良くないけれど好奇心旺盛な若者が本当にいるようです！

それで、私は旅に出て、それを実行することにしました!

3. 分散システムと一貫性ハッシュ

一貫性ハッシュアルゴリズムを理解するには、分散システムのいくつかの特性を知る必要があります。

若い人たちはこう思うに違いない。「なぜ？」

一貫性ハッシュ アルゴリズムは、分散システムにおけるいくつかの重要な問題を解決するように設計されているためです。

3.1 分散システムの概要

高い同時実行性と大量のデータ処理を伴うシナリオが増えるにつれて、サービス アプリケーションの高可用性、容易なスケーラビリティ、および短い待機時間を実現することが不可欠になります。

この場合、分散システムが誕生しました。インターネットのシナリオはストレージとコンピューティングに過ぎないため、分散システムは次のように簡単に分類できます。

• 分散ストレージ
• 分散コンピューティング

分散システムは、外部の世界にサービスを提供するために結合された、物理的に隣接していないコンピューターのグループとして簡単に考えることができます。

ユーザーには、リクエストを完了するために必要なコンピューターの数がわかりません。

分散システム内のコンピューターの数が増えると、コンピューティング リソースとストレージ リソースが増え、処理できる同時アクセスが増え、応答速度が速くなります。

次の図は、単純な全体アーキテクチャを示しています。

3.2 分散型とクラスタ型

クラスターは、元の単一のマシンから進化しました。単一のマシンでワークロードを処理できない場合は、サービス負荷、安定性、レイテンシなどの指標が満たされるまで、追加のマシンが追加されます。

クラスター内の N 台のマシンに同じプログラムを展開することは、1 台のマシンを複数のコピーに複製することと同じです。この形式はクラスタリングと呼ばれます。

分散とは、ビジネス機能に応じて完全なシステムを独立したサブシステムに分割することを意味します。これらのサービスは、RPC などのより効率的な通信プロトコルを使用してスケジュールを実行します。各サブサービスは単一のマシン上にあるのと同じであり、これによりビジネスの分離が実現され、同時実行機能が向上します。これは非常に優れています。

大規模な分散システムは、分割された後にクラスター化されたサブサービスとして理解でき、サブサービスは RPC に似たプロトコルを使用して直列に接続され、巨大なストレージおよびコンピューティング ネットワークを形成します。

図は単純な分散システム構造を示しています。

3.3 クラスタリングで遭遇する問題

一貫性ハッシュアルゴリズムの有用性を説明するために、分散ストレージシステムを例に挙げます。

クラスターの場合、マシンが多すぎると管理が難しくなります。マシンの物理的な障害は避けられません。また、ビジネスが拡大したり縮小したりすることもごく普通のことです。マシンの調整には、必然的にデータの移行が必要になります。

ストレージ クラスターに 5 台のマシンがあり、読み取りおよび書き込み要求がある場合、どのマシンからデータを操作するかを検討する必要があります。一般的に、いくつかの方法があります。

• ランダムアクセス
• 世論調査戦略
• 加重ラウンドロビン戦略
• ハッシュ係数戦略
• 一貫性のあるハッシュ戦略

それぞれの方法には、それぞれ長所と短所があります。

• ランダムアクセスにより、サーバーの負荷が不均一になる可能性があります。
• ポーリング戦略の要求は均等に分散されますが、サーバーのパフォーマンスが異なる場合は、パフォーマンスに応じて分散することはできません。
• 重みは静的に設定する必要があり、自動的に調整することはできません。
• ハッシュモジュロ マシンが動的に変更されると、ルーティングの変更と大量のデータ移行が発生します。

実際には、ハッシュ モジュロ戦略は小規模なシステムで広く使用されています。次に、ハッシュ モジュロとコンシステント ハッシュの違いと関連性に焦点を当てます。

4. ハッシュモジュロの原理、利点、欠点

ハッシュ モジュロ戦略は、同じリクエストが同じマシンで処理されることを保証できる、一般的に使用されるアプローチです。これは、並列を直列に変換する方法であり、エンジニアリングでは非常に一般的です。

データが比較的独立していれば、スレッド間の通信や同期を避けられ、ロックフリーの処理が実現できるため、やはり非常に有用です。

インデックス = hash_fun(キー) % N

上記の通常のハッシュ係数の式から、N が変化しないか、または積極的に制御できる場合は、データの負荷分散とロックフリー処理を実現できますが、N の変化が制御されなくなると、問題が発生することがわかります。

ハッシュ係数戦略がスケーリングの問題にどのように対処するかを見てみましょう。問題モデルを簡略化するために、次の例ではインスタンスのマスター/スレーブ構成を考慮していないことに注意してください。

• 穏やかで平和な

現在、N = 4 台のマシン S1 ～ S4 があります。要求連結キーはハッシュ関数 %N に渡され、指定されたマシン番号が取得され、要求がマシンに転送されます。

• ディスク障害リクエストサポート

ディスク障害のため、S3 マシンがクラッシュしました。プロキシ レイヤーは障害アラームを受信し、N=3 に調整しました。問題が発生しました。キャッシュとして使用すると、S3 マシン上のすべてのキーに対して CacheMiss が表示されます。

元々 S1 に格納されていたキー abc は、新しい N を使用して S4 に調整されます。このように、abc のデータは S4 上で見つからないため、abc にも CacheMiss が発生します。

このようなシナリオはドミノ効果であり、キャッシュ シナリオではキャッシュの崩壊を引き起こし、量が多い場合はキャッシュ雪崩を引き起こす可能性があります。

• 兄弟たち、待ってください、助けが来ます!

S3 がダウンしているため、管理者はマシン S5 を追加し、プロキシ層は再び N=4 に調整します。このとき、ステージ 2 と同様のデータ移行が再び発生し、CacheMiss が依然として発生します。

5. 一貫性のあるハッシュアルゴリズム

まずWikipediaの英語の定義を見てみましょう。

コンピュータサイエンスにおいて、コンシステントハッシュは、ハッシュテーブルのサイズが変更されたときに、平均して K/n 個のキーのみを再マップする必要がある特殊な種類のハッシュです。ここで、K はキーの数、n はスロットの数です。

簡単な翻訳：

コンシステント ハッシュは、特殊なタイプのハッシュ アルゴリズムです。

一貫性のあるハッシュ アルゴリズムを使用した後、ハッシュ テーブル スロットの数 (サイズ) を変更するには、平均して K/n 個のキーワードの再マッピングのみが必要になります。ここで、K はキーワードの数、n はスロットの数です。

従来のハッシュ テーブルでは、スロットを追加または削除するには、ほぼすべてのキーを再マッピングする必要があります。

定義から、コンシステントハッシュは特殊なハッシュアルゴリズムであることがわかります。ハッシュ係数とは異なり、この特殊なハッシュアルゴリズムは、少量のデータの移行を実現し、ほぼすべてのデータの移動を回避することで、通常のハッシュ係数の動的調整によって引き起こされる完全なデータ変更を解決します。

これはかなり印象的です。どのように実現されるか見てみましょう。

5.1 一貫性ハッシュアルゴリズムの考え方

アルゴリズムの具体的な実装を見ずに、まず通常のハッシュ モジュロの問題の根本的な原因は何かを考えてみましょう。

そうです！根本的な原因は、Nの変化とデータの所有権の問題にあります。

• Nの変化

では、N が固定されている場合はどうなるでしょうか?

N が大きい場合、毎回移動するキーの数は K_all/Slot_n になります。これは、スロットの概念、または小さなシャードの概念があることを意味します。簡単に言えば、卵は固定数のバスケットに入れられます。

Key_all は保存されているキーの合計数です。Slot_n はスロットまたはシャードの合計数です。Min_Change は変更の最小数です。Min_change = Key_all/Slot_nMin_change はデータの最小シャードでもあります。

• 小さな破片の所有権

ここで解決すべき別の問題があります。N が固定され、大きな値に設定されると、データ シャードが非常に小さくなり、シャードの所有権の問題が発生します。

たとえば、N = 100w で、クラスター内に 10 台のマシンがある場合、理論上は各マシンの平均は 10w になります。もちろん、マシンのパフォーマンスに基づいて差別化された割り当て構成を行うこともできます。つまり、パフォーマンスの高いマシンにはシャードを多くし、パフォーマンスの低いマシンにはシャードを少なくします。

この時点で、雲はほぼ晴れて月が出ていますが、1997 年に MIT が発明したコンシステント ハッシュ アルゴリズムの原理についてまだ見てみましょう。

5.2 カーガーの一貫性ハッシュアルゴリズム

コンシステント ハッシュ アルゴリズムは、分散キャッシュ問題を解決するために、1997 年にマサチューセッツ工科大学の Karger らによって提案されました。その設計目標は、インターネット上のホット スポット問題を解決することであり、当初の意図は CARP と非常に似ていました。

一貫性のあるハッシュは、CARP で使用される単純なハッシュ アルゴリズムによって引き起こされる問題を修正し、DHT を P2P 環境に真に適用できるようにします。

Karger の一貫性ハッシュ アルゴリズムの基本原理と、スケーリングの問題に対処する方法を見てみましょう。

• ハッシュリングシャーディング

前に考えたように、Karger の一貫性ハッシュ アルゴリズムは N を 2^32 に設定し、0 ~ (2^32-1) のハッシュ リングを形成します。これは、通常のハッシュの係数を取ると N = 2^32 に相当します。

データ キーがハッシュされると、0 ~ (2^32-1) のハッシュ リングに該当します。キーの合計数が Sum の場合、単一のハッシュ リングの最小単位のキーの数は次のようになります。

ユニットキー =合計/2^32

N は非常に大きいため、ハッシュ リングの最小単位である unit_keys のデータ サイズは非常に小さくなります。

• サービスノードとハッシュリングシャーディング

サーバー ノードをハッシュ リングのキーとして配布します。

 con_hash(ip_key)%2^32

一貫性のあるハッシュアルゴリズムは、時計回りの方法を使用してハッシュリングシャードへのノードの帰属を実装しますが、サーバーノードの数は2^32よりはるかに少ないため、宇宙の天体のように非常にまばらです。天体はたくさんあると思いますが、広大な宇宙と比較すると、それらはまだ空っぽです。

• 不均衡な一貫性ハッシュ

物理サーバー ノードの数が少なく、ハッシュ リング シャード内のデータ量が少ないため、一貫性のあるハッシュのデータ スキューが決まります。数が少ないと、サービス ノードの分散が不均一になり、マシン負荷の不均衡が生じます。

図に示すように、サーバー 1 の負荷は他のマシンの負荷よりもはるかに大きくなっています。

• 仮想ノードの導入

はっきり言えば、サーバーノードが足りないと、サーバーのディスク、メモリ、CPUがすべてスペースを占有します。これは現実でも同じです。12306が登場する前、人々は駅で切符を買うために夜通し並んでいました。当時、ランドセル、水カップ、グラスはすべて張三、李四、王二邁子を表していました。

同様に、サーバー ノードは特定のルールに従ってより多くのノードに仮想化されますが、これらの仮想ノードはサーバーのクローンと同等です。

たとえば、仮想ノードを特定するために IP サフィックスに #index を追加するには、次のルールを使用します。

 vnode_A_index = con_hash(ip_key_#A)%2^32
 vnode_B_index = con_hash(ip_key_#B)%2^32
 ...
 vnode_k_index = con_hash(ip_key_#k)%2^32

これは、仮想ノードが導入されているため、仮想ノードのシャードは実際には実際のサービスノードに属している必要があり、実際には仮想ノードと物理ノードのマッピングの問題が発生するためです。

• 新しいサーバーノードを追加する

管理者がサーバー 4 を追加すると、元々サーバー 3 とサーバー 1 に分散されていたハッシュ リング ユニット上のデータの一部がサーバー 4 に移行されます。もちろん、仮想ノードの導入により、この部分のデータの移行はそれほど大きくはなりません。

サーバー 4 とサーバー 1 の間のすべてのデータを時計回りに移行する必要はないため、マシンを追加するときに移動する必要があるのは少量のデータのみです。

• サーバーノードの削除

サーバー ノード 2 がダウンした場合、フェイルオーバーのために削除する必要があります。元の S2 とその仮想ノードのデータは、時計回りに次の物理ノードまたは仮想ノードに移行されます。

6. Redisの一貫性ハッシュ実装

Redis クラスターには 16,384 個の固定スロットがあります。スロットは仮想であり、各マスターに分散されます。キーがスロットを担当するマスターにマップされると、対応するマスターがキーに対してサービスを提供します。

各マスター ノードは、16384/8 バイトのビットマップを保持します。つまり、マスターはビットマップの原理を使用してスロットの添え字を表します。マスター ノードはビットを使用して、所有するスロットを識別します。たとえば、スロット番号が 1 の場合、マスターはシーケンスの 2 番目のビットが 1 であるかどうかを判断するだけで済みます。

このようにして、シャードとサービス ノード間の関係が確立されるため、プロセス全体も 2 つの原則に従います。これは、前述の一貫性のあるハッシュの考え方と一致しています。

 hash_slot_index =CRC16(キー) mod 16384

7. 考察とまとめ

これまでの比較と理解を通じて、コンシステント・ハッシュ・アルゴリズムの本質について考える必要があります。

7.1 コンシステントハッシュアルゴリズムの2つの重要なポイント

コンシステント ハッシュ アルゴリズムは、特別なハッシュ アルゴリズムです。このアルゴリズムの特別な点は、通常のハッシュの係数 N が固定されているため、同じキーが同じ位置にあることが保証され、1 回の移動がシステム全体に影響するという問題が回避されることです。これが、コンシステント ハッシュを理解するための鍵です。

コンシステント ハッシュ アルゴリズムのもう 1 つの重要な点は、N が固定され、大きな値に設定された後に、実際にデータ シャーディングが実行されることです。分散された小さな断片は、実際のマシンに関連付けられている必要があります。つまり、どのマシンがどの小さな断片を担当するかということです。

ただし、コンシステント ハッシュ アルゴリズムは、サーバー データの動的調整によって発生するデータ移行の問題を完全に解決するわけではありませんが、通常のハッシュ係数によって発生する移行のほとんどを、データのごく一部の移動に減らします。これは非常に大きな最適化です。

個人的には、コンシステント ハッシュ アルゴリズムには 2 つの重要なポイントがあると考えています。

• 多数の小さなデータブロックをシャーディングする
• 小さなシャードのサーバー所有権の問題

7.2 アルゴリズムの他のエンジニアリングバージョン

Redis は 2^32 ハッシュ リングを使用せず、代わりに 16384 の固定スロットを使用します。各サーバー マスターはビットマップを使用して、独自の管轄スロットを決定します。

管理者は、マシンの構成と負荷状況に基づいてスロットを動的に調整できるため、基本的に最初のいくつかの負荷分散戦略の欠点が解決されます。

したがって、一貫性のあるハッシュ アルゴリズムを設計するように求められた場合、2 つの原則を把握するだけで済みます。MIT Karger によって提案されたハッシュ アルゴリズムは 1 つだけではありません。これは、アイデアと方向性を提供するだけです。

7.3 一貫性ハッシュアルゴリズムの命名

元の質問に戻ります。なぜ「一貫性のあるハッシュ アルゴリズム」という名前を使用するのでしょうか?

元の英語のテキストは Consistent hashing で、Consistent は「一貫性のある、首尾一貫した」と翻訳されています。私は、consistent の方が適切だと思います。この特別なハッシュ アルゴリズムは、通常のハッシュ係数アルゴリズムのスムーズで首尾一貫したバージョンを実装しており、consistent hashing アルゴリズムと呼ぶ方が適切です。これは、私のささやかな意見です。私のレベルには限界があるので、見てみるだけでいいと思います。

8. まとめ

Compass のベテラン読者なら、これが古い記事だとわかるはずですが、実際そうです、申し訳ありません。

【編集者のおすすめ】

1. オープンソースの Go プロジェクトの推奨事項: 中国語の文字をピンインに変換します (声調も含む)
2. Go GC はどのようにメモリをマークしますか?色は何を意味していますか?グラフィック3色ラベル
3. Go プログラムをデバッグするために Println の代わりに Delve を使用する
4. クラウドネイティブ時代は Java か Go か?
5. Ant Wang Yi: Go+はPythonの欠点を効果的に補うことができる