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

[[413431]]

一貫性のあるハッシュ

コンシステントハッシュ法は、ノードを削除または追加する際に、既存のキーのマッピング関係をできるだけ変更しないハッシュアルゴリズムです。通常は時計回りに動作します。答える前に、実際の状況に対処する方法を考えてください。コンシステントハッシュ法は、ハッシュ値空間全体を仮想リングに整理します。ハッシュ関数の値空間が0〜2^32-1であると仮定すると、ハッシュ空間リング全体は、以下の左の図に示されています。

コンシステント ハッシュの基本的な考え方は、同じハッシュ アルゴリズムを使用して、データとノードの両方を図のリング ハッシュ空間にマッピングすることです。右上の図は、リング上の 4 つのデータ オブジェクト 1 ～ オブジェクト 4 の分布を示しています。

ノードとデータのマッピング

サーバーのグループがある場合は、IPまたはホスト名をハッシュのキーワードとして使用し、結果をハッシュリングにマップすることができます。3つのサーバーはnodeA-nodeCです。

これで、サーバーに保存する必要があるデータ バッチ (object1 ～ object4) ができました。同じハッシュ アルゴリズムを使用してデータをハッシュできます。結果もリング上にある必要があります。時計回りに検索できます。ノード (サーバー) が見つかったら、このノードにデータを保存します。このようにして、次の図に示すように、データとノードは 1 対 1 で関連付けられます。

ノードを削除

上図のノード B のように、サーバーに問題がある場合は、反時計回りの方向と次のノードの間のデータが影響を受けます。このデータを時計回りの最初のノードにマップするだけで済みます。

1566573901641

ノードを追加

新しいサーバー nodeD が追加されると、サーバーから反時計回りの次のノードまでのデータが影響を受けます。このデータは、右の図に示すように、nodeD にマッピングできます。

仮想ノード

サーバーが 2 つ (nodeA と nodeC) しかないと仮定します。nodeA は 1 つのデータをマップし、nodeC は 3 つのデータをマップします。これは、データ分散が不均衡であることを意味します。仮想ノードを導入し、ノードの複製数が 2 であると仮定すると、nodeA は nodeA1 と nodeA2 になり、nodeC は nodeC1 と nodeC2 になり、マッピングは次のようになります。

これにより、データの配分がより均等になり、バランスが大幅に改善されます。