アルゴリズムに関する漫画: コンシステント・ハッシュとは何ですか?

1年前——

同システムでは、今後2年間で総注文数が約1億件に達すると予測している。

1 つの MySQL テーブルに 500 万件のレコードが格納されている場合、当面はデータベースをシャードする必要はありません。1 つのデータベースに 30 個のシャードがある方が、より適切な水平シャーディング ソリューションです。

そこで、Xiao Hui は次のテーブル パーティション分割ロジックを設計しました。

1. 注文テーブルは、単一のデータベースに30個のサブテーブルを作成します。
2. ユーザー ID と 30 の剰余によって、レコードが格納されるサブテーブルが決まります。
3. クエリを実行する際は、ユーザー ID を条件として使用する必要があり、モジュロ結果に基づいてクエリ対象のサブテーブルが決定されます。

表の分割方法は以下の通りです（説明を簡単にするため、5つの表に簡略化しています）。

2ヵ月後—

それから半年以上が経ち——

小慧の記憶は終わりを迎える――

1. まず、キャッシュ空間全体をリングストレージ構造として扱います。環状空間は合計 2^32 個のキャッシュ領域に分割され、Redis ではキャッシュ キーが 16384 個のスロットに割り当てられます。

2. 各キャッシュ キーは、ハッシュ アルゴリズムを通じて 32 ビットの 2 進数に変換でき、リング空間内のキャッシュ領域に対応します。すべてのキャッシュ キーを環状空間内の異なる場所にマッピングします。

3. 各キャッシュ ノード (シャード) も、IP をハッシュとして使用し、それをリング スペースにマッピングするなど、同じハッシュ アルゴリズムに従います。

4. キーとノードをどのように一致させるか? 非常に簡単です。各キーの時計回り方向で最も近いノードが、キーが属するストレージ ノードです。したがって、図では、key1 は node1 に格納され、key2 と key3 は node2 に格納され、key4 は node3 に格納されます。

1. ノードを追加する

キャッシュ クラスター内のノード数が増加しても、環状空間全体のマッピングでは一貫したハッシュの時計回りのルールが維持されるため、少数のキーの所有権が影響を受けます。

どのキーが影響を受けるでしょうか? 図では、node1 と node2 の間に新しいノード node4 が追加されています。時計回りのルールに従うと、node1 から node4 までのキャッシュは node2 ではなく、新しいノード node4 に属します。したがって、影響を受けるキーは key2 のみです。

最後に、key2 のキャッシュ データが node2 から node4 に移行され、一貫性のあるハッシュ ルールに準拠した新しいキャッシュ構造が形成されます。

2. ノードを削除する

キャッシュ クラスター内のノードを削除する必要がある場合 (たとえば、ノードがクラッシュした場合)、環状空間全体のマッピングでも一貫性のあるハッシュの時計回りのルールが維持され、少数のキーの所有権も影響を受けます。

どのキーが影響を受けるでしょうか? 元のノード node3 はグラフから削除されます。時計回りのルールに従って、元々 node3 が所有していたキャッシュされたデータは、node3 の時計回りの後継ノード node1 に「委託」される必要があります。したがって、影響を受けるキーは key4 のみです。

最後に、key4 のキャッシュ データが node3 から node1 に移行され、一貫性のあるハッシュ ルールに準拠した新しいキャッシュ構造が形成されます。

上図に示すように、node1 の IP アドレスが 192.168.1.109 の場合、リング空間内の元の node1 の位置は hash("192.168.1.109") になります。

node1 に基づいて 2 つの仮想ノード (node1-1、node1-2) を構築します。リング空間内の仮想ノードの位置は、(IP+サフィックス) を使用して計算できます。例:

ハッシュ("192.168.1.109#1")、ハッシュ("192.168.1.109#2")

この時点で、環状空間には物理ノード node1 と node2 は存在せず、仮想ノード node1-1、node1-2、node2-1、および node2-2 のみが存在することになります。仮想ノードの数が多いため、キャッシュ キーと仮想ノード間のマッピング関係は比較的バランスが取れたものになります。