一貫性ハッシュアルゴリズムのグラフィカルな説明は、この記事を読んでください。

著者 |レモンコーダー

ソース |バックエンドテクノロジーアカデミー

多くの学生はハッシュ関数が何であるかを知っているはずです。バックエンドのインタビューや開発では、「一貫したハッシュ」に遭遇することになります。では、コンシステントハッシュとは何でしょうか?名前は印象的ですが、原理は実際には複雑ではありません。この記事は、コンシステント ハッシュを徹底的に理解するのに役立ちます。

本題に入る前に、楽しい模擬面接をしてみましょう。

模擬面接

面接官: あなたの履歴書を見ると、分散キャッシュ クラスターを使用した大規模なプロジェクトに参加したと書かれていますね。では、キャッシュのロードバランシングをどのように行ったか教えていただけますか?

新人さん：それは知っています。私たちはラウンドロビン方式を採用しています。最初のキーは最初のストレージ ノードに与えられ、2 番目のキーは 2 番目のストレージ ノードに与えられ、以下同様に続きます。

インタビュアー: 他に解決策はありますか?

初心者: ハッシュ関数を使用してリクエストを分割し、キャッシュ クラスター内のマシンにランダムに分散することができます。

インタビュアー: このハッシュベースの負荷分散のスケーラビリティとフォールト トレランスについて検討しましたか?

初心者:...

インタビュアー: 戻って通知を待ちます。

上記に類似点がある場合は盗作とみなされます。

ハッシュとは何か

データ構造では、ハッシュ テーブルはハッシュ テーブルとも呼ばれることを学びました。ハッシュテーブルの定義を確認しましょう。

ハッシュ テーブルは、キーに基づいて指定されたストレージ場所のデータに直接アクセスするデータ構造です。キーに関する関数 (ハッシュ関数とも呼ばれます) を計算することにより、必要なクエリ データがテーブル内の場所にマッピングされ、レコードにアクセスできるようになるため、検索が高速化されます。このマッピング関数は「ハッシュ関数」と呼ばれ、レコードを格納する配列はハッシュテーブルと呼ばれます。

ハッシュ関数を使用すると、データ シーケンスへのアクセス プロセスを高速化して効率化できます。空間を時間と交換するアルゴリズムです。ハッシュ関数を使用すると、データ要素をより迅速に見つけることができます。

次の図は、ハッシュ関数を使用して文字列をハッシュ テーブルにマッピングするプロセスを示しています。はい、入力文字列はフェイスロールキーボードを使用して入力されます :)

ハッシュ図.png

一般的なハッシュ アルゴリズムには、MD5、CRC、MurmurHash などがあり、以下で簡単に紹介します。 MD5アルゴリズム

広く使用されている暗号化ハッシュ関数である MD5 メッセージダイジェストアルゴリズムは、128 ビット (16 バイト) のハッシュ値を生成できます。 MD5 アルゴリズムは、データ (テキストなど) を別の固定長の値に変換します。これがハッシュ アルゴリズムの基本原理です。アメリカの暗号学者ロナルド・リン・リベストによって設計され、1992年に公開され、RFC 1321で標準化されました。CRCアルゴリズム

巡回冗長検査 (CRC) は、ネットワーク パケットやコンピュータ ファイルなどのデータに基づいて短い固定ビットのチェック コードを生成するハッシュ関数です。これは 1961 年に W. Wesley Peterson によって公開されました。生成された番号は計算され、送信または保存の前にデータに追加され、その後、受信者はデータが変更されたかどうかを確認します。この関数は、バイナリ コンピュータ ハードウェアで使いやすく、数学的に分析しやすく、伝送チャネルの干渉によって発生するエラーの検出に特に適しているため、広く使用されています。マーマーハッシュ

MurmurHash は、一般的なハッシュ取得操作に適した非暗号化ハッシュ関数です。 2008 年に Austin Appleby によって発明された MurmurHash には、複数のバリエーションがあります。他の一般的なハッシュ関数と比較すると、MurmurHash は規則性が強いキーのランダム分散特性において優れたパフォーマンスを発揮します。

このアルゴリズムは、libstdc++（バージョン4.6）、Perl、nginx（バージョン1.0.1以降）、Rubinius、libmemcached、maatkit、Hadoopなど、多くのオープンソースプロジェクトで使用されています。一般的なハッシュ方法

直接アドレス指定方法: キーワードまたはキーワードの線形関数値をハッシュ アドレスとして取得します。この線形関数の定義はさまざまであり、標準はありません。

デジタル解析法: キーワードが基数 r を持つ数値であり、ハッシュ テーブルに出現する可能性のあるキーワードが事前にわかっていると仮定すると、キーワードのいくつかの桁を取得してハッシュ アドレスを形成できます。

スクエアミドル方式: キーワードのスクエアの中央の数桁をハッシュアドレスとして取得します。通常、ハッシュ関数を選択する場合、キーワードの全体の状況が必ずしもわかるわけではなく、どのビットを取るべきかはわかりません。数値の二乗後の中央の数字は数値の各ビットに関連しているため、ランダムに分散されたキーワードによって得られるハッシュ アドレスもランダムになり、取得されるビット数はテーブルの長さによって決まります。

折りたたみ方式: キーワードを同じ桁数の複数の部分に分割し (最後の部分の桁数は異なる場合があります)、これらの部分の合計 (繰り上がりは破棄) をハッシュ アドレスとして取得します。

モジュロ方式: キーワードをハッシュテーブルの長さ m 以下の数 p で割った余りがハッシュアドレスです。つまり、hash(key) = key % p (p<= M) です。キーワードは直接剰余をとることができるだけでなく、折り畳み法や正方形中心法などの操作の後に剰余をとることもできます。 p の選択は非常に重要です。一般的には素数またはmが選択されます。 p が適切に選択されていない場合、競合が発生する可能性があります。

キャッシュシステムの負荷分散

memcached キャッシュ クラスターなどの分散クラスター キャッシュの負荷分散実装では、キャッシュされたデータが各分散ストレージ ノードに均等に分散されるように、キャッシュされたデータのキーをハッシュ関数を使用してハッシュする必要があります。このような負荷分散を実現するには、通常、ハッシュ アルゴリズムを使用します。次の図は、この分散ストレージ プロセスを示しています。

分散キャッシュハッシュストレージ図

通常のハッシュアルゴリズムの負荷分散

これまで、さまざまなハッシュ手法を紹介してきました。どのハッシュ方法を選択した場合でも、このアプリケーション シナリオでは、キャッシュされたデータはハッシュ関数を使用してサーバー クラスターに均等にマップされる必要があります。このプロセスを説明するために、単純な「モジュラス法」を選択します。

番号 [0 - 2] のサーバーノードが 3 つあり、番号 [1 - 6] のキャッシュキーと値のペアが 6 つあると仮定します。ハッシュ マッピングが完了すると、3 つのキャッシュ データ マッピングは次のようになります。

ハッシュ計算式: キー % ノード総数 = ハッシュノードインデックス 1%3=12%3=23%3=04%3=15%3=26%3=0

キャッシュハッシュインスタンス

各接続は 3 つの異なるサーバー ノードに均等に分散されます。完璧ですね！

しかし、このモデルでは、分散クラスタシステムで負荷分散を実装する際に2つの問題があります。1. スケーラビリティが低い

サービス機能を動的に調整するには、サービス ノードの容量を拡張または縮小する必要があることがよくあります。例えば、電子商取引サービスであれば、ダブルイレブン期間中のサービスマシンの数は間違いなく通常よりもはるかに多くなります。新しく追加されたマシンにより、元々計算されたハッシュ値が不正確になります。負荷分散の効果を得るには、ハッシュ値を再計算して更新する必要があります。更新後にハッシュ値が不一致になったキャッシュデータについては、更新されたノードに移行する必要があります。

新しいサーバー ノードが追加され、元の 3 つのサービス ノードが [0 - 3] の番号が付けられた 4 つのノードになったとします。ハッシュマッピングは次のとおりです。

ハッシュ計算式: キー % ノード総数 = ハッシュノードインデックス 1%4=12%4=23%4=34%4=05%4=16%4=2

最後の 3 つのキャッシュ キー 4、5、6 に対応するストレージ ノードはすべて無効であることがわかります。したがって、これらのノードのキャッシュ データを更新されたノードに移行する必要があります (時間がかかり、労力がかかります)。つまり、元のノード [1, 2, 0] からノード [0, 1, 2] に移行する必要があります。移行後のストレージ図は次のとおりです。

キャッシュハッシュのスケーラビリティ図 2. フォールトトレランスが低い

オンライン環境のサービスノードにはさまざまな高可用性保証がありますが、ダウンタイムが発生する可能性は依然として存在します。ダウンタイムがない場合でも、容量を削減する必要があります。ダウンタイムと縮小はどちらもサービス ノードの削除に起因する可能性があります。以下では、サービス ノードの削除が負荷分散ハッシュ値に与える影響を分析します。

1 つのサーバー ノードが削除され、元の 3 つのサービス ノードが 2 つに削減され、ノード番号が [0 - 1] になったとします。ハッシュマッピングは次のとおりです。

ハッシュ計算式: キー % ノード総数 = ハッシュノードインデックス 1%2=12%2=03%2=14%2=05%2=16%2=0

次の図は、ノードがダウンしたときに共通ハッシュ負荷分散アルゴリズムによって発生するキャッシュ データ移行の分散を示しています。

キャッシュハッシュフォールトトレランス図

図に示すように、この例では、サービスノードを削除するだけでもハッシュ値の大規模な更新が発生します。ハッシュ値の更新は、ノード キャッシュ データの移行も意味します (キャッシュされたデータは非常に疲れていることを意味します)。

一貫性のあるハッシュアルゴリズムの負荷分散

通常のハッシュ アルゴリズムによって実装されるキャッシュ負荷分散ではスケーラビリティとフォールト トレランスが低いため、コンシステント ハッシュ アルゴリズムを導入します。では、コンシステントハッシュとは何でしょうか?まず、Wikipedia のコンシステント ハッシュの定義を見てみましょう。

コンシステント ハッシュは、MIT の David Karger 氏とその協力者によって提案され、現在ではそのアイデアは他の分野にも拡張されています。 1997 年に発表されたこの学術論文では、不安定なユーザーを持つ分散 Web サービスに一貫性のあるハッシュを適用する方法について説明しています。一貫性のあるハッシュは、大規模な Web アプリケーションにおける部分的なシステム障害による悪影響を軽減するための堅牢なキャッシュを実装するためにも使用できます。

コンシステント ハッシュについて説明したこの論文は 1997 年に発表されました。読書障害のある学生は、この論文を直接読んで理解を深めることができます。論文のダウンロードリンクを添付します: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879

一貫性のあるハッシュペーパー

コンシステント ハッシュを一言でまとめると、これは通常のモジュロ ハッシュ アルゴリズムの改良版です。ハッシュ関数の計算方法は変わりませんが、通常の線形ハッシュ空間の代わりに循環ハッシュ空間が構築されます。具体的な手順は次のとおりです。

まず、ハッシュ リングを形成するために十分な大きさのハッシュ スペース (通常は 0 ~ 2^32) を選択します。

一貫性のあるハッシュリング

次に、キャッシュ クラスター内の各ストレージ サーバー ノードのハッシュ値が計算されます。ハッシュ値は、サーバーの IP またはホスト名を使用して計算できます。計算されたハッシュ値は、ハッシュ リング上のサービス ノードの位置です。

ノードハッシュ

最後に、保存する必要があるデータ キーごとにハッシュ値が計算されます。計算されたハッシュもリングにマッピングされ、データは時計回り方向に見つかったリング上の最初のノードに保存されます。次の図は、ノードに保存されるデータの例を示しています。以下の説明も現在の保管状況に基づいています。

画像

原理を説明したので、この設計が上記の通常のハッシュの 2 つの問題を解決できる理由を見てみましょう。スケーラビリティの向上

先ほど分析したように、通常のハッシュ アルゴリズムでは、容量を拡張してサービス ノードを追加する必要がある場合、粗いハッシュ マッピングの大規模な障害が発生します。ここで、一貫性ハッシュがこの問題をどのように解決するかを見てみましょう。

次の図に示すように、新しいノード node3 がキャッシュ サービス クラスターに追加されると、key3 に対応するデータ value3 のみが影響を受けます。この時点では、元のノード node0 から新しいノード node3 に value3 を移行するだけでよく、他のノードに保存されているデータは変更されません。

一貫性のあるハッシュ - 拡張ノードのフォールトトレランスの改善

一般的なハッシュ アルゴリズムのサービス ノードがオフラインになると、元のハッシュ マッピングにも大規模な障害が発生します。マッピングが失敗すると、データ移行がトリガーされ、キャッシュ サービスのパフォーマンスに影響し、フォールト トレランスが不十分になります。一貫性のあるハッシュによってフォールト トレランスがどのように向上するかを見てみましょう。

下の図に示すように、node2 がオフラインになったと仮定すると、元々 node2 に格納されていたデータ value2 と value5 は、他のノードのデータに影響を与えることなく、新しいストレージ ノード node0 に時計回り方向に格納するだけで済みます。一貫性のあるハッシュにより、ノード障害の影響を時計回りに隣接するノードに限定し、クラスター全体への影響を回避できます。

一貫性ハッシュ - ノードの削除

一貫性のあるハッシュ最適化

問題

上記は、一貫性のあるハッシュが通常のハッシュのスケーラビリティとフォールト トレランスの問題をどのように解決するかを示しています。原理は比較的単純で、理想的な条件下ではうまく機能しますが、実際の使用では考慮する必要がある実用的な問題がいくつかあります。以下は詳細な分析です。データの偏り

この例の 3 つのノードのように、キャッシュ クラスター内のサービス ノードの数が少なく、ハッシュ リング スペースが非常に大きい場合 (通常は 0 ~ 2^32)、どのような問題が発生するでしょうか。

考えられる状況の 1 つは、少数のサービス ノード ハッシュ値がクラスター化されている場合です。たとえば、下の図に示すように、node0、node1、および node2 がクラスター化されています。キャッシュされたデータのキーハッシュはすべて、ノード 2 の時計回り方向にマッピングされます。データは時計回りにストレージ ノードを検索するため、すべてのデータが node0 に保存され、単一のノードに大きな負荷がかかります。この状況はデータスキューと呼ばれます。

一貫性のあるハッシュ - データ偏向ノードの雪崩

データ スキューとノード クラッシュの両方がキャッシュ アバランシェを引き起こす可能性があります。

前述のデータ スキューの例を挙げると、データ スキューにより、キャッシュされたすべてのデータが node0 にプッシュされ、node0 が過負荷になってクラッシュする可能性があります。 Node0 がダウンし、データが node1 にプッシュされますが、node1 もダウンします。 Node1 も崩壊し、障害は node2 に渡されます。この時点で、障害は雪崩の中の雪玉のように、どんどん大きくなっていきます。

もう 1 つの状況は、さまざまな理由によりノードがオフラインになることです。たとえば、下の図に示すように、ノード node2 がオフラインになり、元々 node2 にあったデータが node0 にプッシュされます。データ量が特に多い場合は、ノードアバランチが発生する可能性もあります。具体的なプロセスは先ほどの分析と同様です。

つまり、キャッシュ クラスター全体が使用できなくなる連鎖反応をノード アバランシェと呼びます。

一貫性ハッシュ - ノードアバランチ仮想ノード

では、上記の 2 つの難しい問題をどのように解決すればよいのでしょうか?これは「仮想ノード」を使用することで解決できます。

いわゆる仮想ノードは、ハッシュ リング上の元の単一の物理ノードの複数の仮想クローンを作成することです。これらのクローンは「仮想ノード」と呼ばれます。クローン ノードにヒットしたデータは、実際にはクローンに対応する物理ノードにマッピングされるため、物理ノードは仮想ノードを通じてハッシュ リングのさまざまな部分に均等に分散され、データの偏りの問題が解決されます。

仮想ノードはハッシュ リング全体に分散されているため、ノードがオフラインになると、そのノードが保存するデータは他のノードに均等に分散され、単一のノードへの突然の負荷によって発生するノード アバランシェ問題を回避します。

次の図は、仮想ノードのハッシュ リング分布を示しています。左側は仮想ノードなしのノード分布を示しています。右側の緑の背景色の 2 つの node0 ノードは、node0 ノードの仮想ノードです。背景色が赤い node1 ノードは node1 の仮想ノードです。

一貫性ハッシュ - 仮想ノード

総括する

この記事では、まずハッシュ アルゴリズムとは何か、一般的なハッシュ アルゴリズムと一般的なハッシュ方法について紹介し、次に一般的なハッシュ アルゴリズムに基づくキャッシュ負荷分散の実装について説明し、一般的なアルゴリズムのスケーラビリティとフォールト トレランスの問題を示す例を示します。

通常のアルゴリズムのスケーラビリティとフォールト トレランスの問題を解決するために、コンシステント ハッシュ アルゴリズムが導入されています。一貫性のあるハッシュによってスケーラビリティとフォールト トレランスがどのように向上するかを、グラフィックと例を使用して分析します。最後に、ラフ・コンシステント・ハッシュ・アルゴリズムには、データ・スキューとノード・アバランチの問題もあります。仮想ノードを使用して一貫性ハッシュ アルゴリズムを最適化し、データ スキューとアバランシェの問題を解決する方法について説明します。ここまで、コンシステント・ハッシュについて学びましたか?

コンシステント ハッシュの知識ポイントは難しくありませんが、ブルーム フィルタ アルゴリズムと同様に頻繁にテストされます。聞いたことのない人は、とても高度なものだと思っているかもしれませんが、それは単に勉強してみるだけの問題です。したがって、学生の皆さんは、面接官に勝つために幅広い知識を身につけていなければなりません。