面接でコンシステントハッシュアルゴリズムについて再度質問されました。この答えは面接官を即死させるでしょう!

[[284994]]

データシャーディング

まずは例を見てみましょう。

多くの場合、キャッシュには Redis を使用し、データ負荷を軽減するために一部のデータをそこに配置します。

データ量が少なく、アクセス負荷が大きくない場合は、通常 1 つの Redis で処理できます。高可用性を実現するには、マスター スレーブで十分です。

データ量が増え、同時実行数が増えると、キャッシュされたデータをすべて 1 台のマシンに置くことが難しくなります。結局のところ、マシンのリソースには限りがあります。通常は、各 Redis にデータをできるだけ均等に分散するクラスター環境を構築します。たとえば、クラスターには 4 つの Redis があります。

では、これらの 4 つの Redis サーバーにデータをできるだけ均等に配置するにはどうすればよいでしょうか。最も簡単な方法は、モジュロ アルゴリズムです。

hash( key ) % N、N は Redis の数です。ここでは N = 4 です。

この方法を使用すると、データを 4 つの Redis サーバーに均等に保存できるため、非常に便利です。新しいリクエストが届いたときに、データがどの Redis サーバーにあるかを特定できるため、キャッシュされたデータを正確にクエリできます。

02データシャーディングで発生する問題

しかし、4 台の Redis サーバーでは不十分であり、さらに 4 台の Redis サーバーが必要です。

剰余アルゴリズムは次のようになります: hash( key ) % 8;

したがって、現在のキャッシュの場所のほとんどは間違っていると想像できます。極端な場合には、キャッシュの雪崩が発生します。

03一貫性ハッシュアルゴリズム

一貫性のあるハッシュ アルゴリズムはこの問題を非常にうまく解決できます。その一般的なプロセスは次のとおりです。

0を始点、2^​​32-1を終点として直線を描き、始点と終点を一致させます。直線は円になり、方向は小さい方から大きい方へ時計回りになります。 0 の右側の最初の点は 1、次は 2 というようになります。

3 つのサーバーの IP アドレスまたはその他のキーワードをハッシュし、モジュロ 2^32 をとった後、それらは必然的にこの円のどこかに収まり、Node1、Node2、および Node3 として記録されます。

次に、データ キーに対して同じ操作を実行すると、必然的に円上のどこかに落ちます。その後、時計回りに進むと、このキーが保存されるサーバーである特定のノードを見つけることができます。

サーバーを追加または削除すると、データの一部のみが影響を受けます。

ただし、ノード数が少なすぎたり、分散が不均一だったりすると、データの偏り、つまりほとんどのデータが特定のサーバーに集中する状態が発生しやすくなります。

データの偏りの問題を解決するために、コンシステント ハッシュ アルゴリズムでは、各サービス ノードに対して複数のハッシュを計算し、それらを円上の異なる位置に配置する [仮想ノード] を提案します。

もちろん、一貫性のあるハッシュ アルゴリズムではほとんどのデータの問題を解決できることもわかります。