一貫性ハッシュアルゴリズムの使い方がわからない場合は、履歴書に負荷分散に取り組んだと書かないでください。

この記事はWeChatの公開アカウント「Programmer Insider Things」から転載したもので、著者はProgrammer Insider Thingsです。この記事を転載する場合は、Programmer Insider 公式アカウントまでご連絡ください。

この2日間、技術グループの友人たちがコンシステントハッシュアルゴリズムの問​​題について議論しているのを見ました。何も書くことがないのではないかと心配していたところ、この話題が持ち上がったので、その原理を簡単に紹介したいと思います。以下では、分散キャッシュの典型的なシナリオを例として取り上げます。これはインタビューでもよく取り上げられるトピックでもあり、一貫性のあるハッシュ アルゴリズムとは何か、そしてその利点は何かを説明します。

シーンを構築する

node0、node1、node2 という番号の付いた 3 つのキャッシュ サーバーがあり、現在 3,000 万個のキーがあり、これらのキーを 3 台のマシンに均等にキャッシュしたい場合、どのような解決策が考えられますか。

最初に思いつく解決策は、モジュロ アルゴリズム hash(key)% N です。これは、キーをハッシュした後にモジュロを取得します。ここで、N はマシンの数です。キーを 3 で割ったハッシュ結果は 0、1、または 2 でなければなりません。これは、サーバー node0、node1、node2 に対応します。データにアクセスするには、対応するサーバーを直接見つけることができます。これは単純で大まかな方法​​ですが、上記の問題を完全に解決できます。

ハッシュ化の問題

モジュロ アルゴリズムは使い方が簡単ですが、クラスターを拡張または縮小するときにマシン数のモジュロを取るときに一定の制限があります。これは、実稼働環境では、業務量の大きさに基づいてサーバー数を調整するのが一般的だからです。サーバー数 N が変わると、hash(key)% N の計算結果もそれに応じて変わります。

例えば、サーバーノードがクラッシュすると、計算式がhash(key)%3からhash(key)%2に変わり、結果が変わります。このとき、キーにアクセスしたい場合、キーのキャッシュ場所が変わる可能性が高く、以前キャッシュされていたキーのデータは機能と意味を失います。

多数のキャッシュが同時に故障すると、キャッシュ雪崩が発生し、キャッシュ システム全体が使用できなくなります。これは基本的に許容できません。上記の状況を解決して最適化するために、コンシステント ハッシュ アルゴリズムが生まれました。

では、コンシステント・ハッシュ・アルゴリズムはどのようにして上記の問題を解決するのでしょうか?

一貫性のあるハッシュ

コンシステント ハッシュ アルゴリズムも、本質的にはモジュロ アルゴリズムです。ただし、サーバーの数に基づいてモジュロ値を取得する上記のアルゴリズムとは異なり、コンシステント ハッシュ アルゴリズムは固定値 2^32 に基づいてモジュロ値を取得します。

IPv4 アドレスは 8 ビットの 2 進数の 4 つのグループで構成されているため、2^32 を使用すると、各 IP アドレスが一意にマッピングされることが保証されます。

ハッシュリング

この2^32個の値を円に抽象化できるでしょうか？？（円である必要はなく、わかりやすい形状を思い浮かべれば良いです）、円の真上にある点が0を表し、それを時計回りに1、2、3、4、5、6…と2^32-1まで並び、この2の32乗の点から構成される円を総称してハッシュリングと呼びます。

では、このハッシュ リングとコンシステント ハッシュ アルゴリズムの関係は何でしょうか? 上記のシナリオを例に考えてみましょう。node0、node1、node2 という番号の付いた 3 つのキャッシュ サーバーがあり、キーの数は 3,000 万です。

サーバーはハッシュリングにマッピングされます

このとき、計算式は hash(key)% N から hash(server ip)% 2^32 に変わります。ハッシュ計算にはサーバの IP アドレスが使用され、ハッシュ結果は 2^32 を法とします。結果は 0 から 2^32-1 までの整数である必要があります。ハッシュ リングにマッピングされたこの整数の位置がサーバを表します。3 つのキャッシュ サーバ node0、node1、node2 が順番にハッシュ リングにマッピングされます。

オブジェクトキーはハッシュリングにマッピングされます

次に、キャッシュされるキー オブジェクトもハッシュ リング、hash(key)% 2^32 にマップされます。サーバー ノードとキャッシュされるキー オブジェクトはハッシュ リングにマップされます。オブジェクト キーはどのサーバーにキャッシュする必要がありますか?

オブジェクトキーのサーバーへのマッピング

「キャッシュ オブジェクト キーの場所から時計回りに最初に遭遇したサーバーが、現在のオブジェクトがキャッシュされるサーバーです。

キャッシュされたオブジェクトとサーバーのハッシュ値は固定されているため、サーバーが変更されていない場合、オブジェクトキーは確実に固定サーバーにキャッシュされます。上記の規則に従うと、下の図のマッピング関係は次のようになります。

• キー 1 -> ノード 1
• キー3 -> ノード2
• キー4 -> ノード2
• キー5 -> ノード2
• キー2 -> ノード0

キーにアクセスする場合は、同じ計算方法を使用して、キーがキャッシュされているサーバーを見つけることができます。

コンシステントハッシュの利点

コンシステント ハッシュの原理を簡単に理解できました。クラスター内のノードの追加と削減をどのように最適化し、通常のモジュロ アルゴリズムによって発生する大規模なキャッシュ サービスの利用不可の問題をどのように解決するのでしょうか。

まず、拡張シナリオを見てみましょう。ビジネス量が急増した場合、システムを拡張してサーバーノード 4 を追加する必要があります。ノード 4 は、ノード 1 とノード 2 の間にマップされています。オブジェクトを時計回りにマップすると、ノード 2 に元々キャッシュされていたオブジェクト key-4 と key-5 がノード 4 に再マップされていることがわかります。拡張プロセス全体を通じて、ノード 4 とノード 1 間のデータのごく一部だけが影響を受けます。

逆に、ノード 1 がダウンした場合、ノード 1 にキャッシュされたオブジェクト キー 1 は、オブジェクト マッピング ノードに沿って時計回りにノード 4 に再マッピングされます。このとき、影響を受けるのはノード 0 とノード 1 間のデータのごく一部だけです。

上記の 2 つの状況から、クラスター内のサーバーの数が変わっても、コンシステント ハッシュはデータのごく一部にのみ影響し、キャッシュ システム全体が外部にサービスを提供し続けることができることがわかります。

データの偏りの問題

原理を理解しやすくするために、図のノードは理想的には比較的均等に分散されていますが、理想と実際のシナリオは大きく異なることがよくあります。たとえば、私は年間ジムの会員ですが、ジムに行ったのは 2 回だけで、シャワーを浴びただけです。

運動したいなら

サーバー ノードの数が少なすぎると、ノードの分布が不均一になり、データ スキューの問題が簡単に発生する可能性があります。次の図に示すように、キャッシュされたオブジェクトのほとんどはノード 4 サーバーにキャッシュされ、他のノードのリソースが無駄になります。システム プレッシャーのほとんどはノード 4 ノードに集中します。このようなクラスターは非常に不健全です。

データ スキューの解決方法も簡単です。ハッシュ リングにマッピングするときに、ノードを比較的均等に分散させる方法を見つけるだけです。

コンシステント ハッシュ アルゴリズムでは仮想ノード メカニズムが導入され、各サーバー ノードに対して複数のハッシュ値が計算され、それらはすべてハッシュ リングにマッピングされます。これらの仮想ノードにマッピングされたオブジェクト キーは、最終的に実際のノードにキャッシュされます。

仮想ノードのハッシュ計算は、通常、対応するノードの IP アドレスに数値サフィックスを追加することで実行できます (ハッシュ (10.24.23.227#1))。たとえば、ノード 1 の IP アドレスは 10.24.23.227 であり、ノード 1 のハッシュ値は通常どおりに計算されます。

• ハッシュ(10.24.23.227#1)% 2^32

3 つの仮想ノード (node-1、node-1#1、node-1#2、node-1#3) を設定し、ハッシュした後に係数を取得するとします。

• ハッシュ(10.24.23.227#1)% 2^32
• ハッシュ(10.24.23.227#2)% 2^32
• ハッシュ(10.24.23.227#3)% 2^32

下の図に示すように、仮想ノードを追加した後、元のノードはハッシュ リング上で比較的均等に分散され、残りのノードにかかる負荷が分散されます。

「ただし、注目すべき点は、割り当てられる仮想ノードの数が増えるほど、ハッシュ リング上のマッピングがより均等になるということです。ノードが少なすぎると、効果を確認するのが難しくなります。

仮想ノードの導入により、仮想ノードと実ノード間のマッピングや、オブジェクト キー -> 仮想ノード -> 実ノード間の変換など、新たな問題も発生します。

コンシステントハッシュの応用シナリオ

分散システムで負荷分散を実装する場合、コンシステント ハッシュが推奨されるアルゴリズムです。実装は比較的柔軟で、クライアントまたはミドルウェアに実装できます。たとえば、一般的に使用されているキャッシュ ミドルウェアの memcached や redis クラスターで使用されています。

memcached クラスターは非常に特殊です。厳密に言えば、サーバー同士が通信できないため、疑似クラスターとしか見なせません。リクエストの分散ルーティングは、キャッシュされたオブジェクトがどのサーバーに配置されるべきかをクライアントが計算することに完全に依存しており、ルーティング アルゴリズムはコンシステント ハッシュを使用します。

Redis クラスターにはハッシュ スロットの概念もあります。実装は異なりますが、考え方は同じです。一貫性のあるハッシュに関するこの記事を読んだ後、Redis スロットの理解がはるかに容易になります。

他にも多くの応用シナリオがあります:

• RPCフレームワークDubboはサービスプロバイダーを選択するために使用されます
• 分散リレーショナルデータベースのサブライブラリとサブテーブル: データとノード間の関係のマッピング
• LVS 負荷分散スケジューラ
• ...............................

要約する

一貫性ハッシュについて簡単に説明しました。何か間違いがあれば、メッセージを残して訂正してください。完璧な技術はありません。一貫性ハッシュアルゴリズムにも潜在的なリスクがあります。ハッシュリング上のノードの数が非常に多い場合や更新が頻繁な場合は、検索パフォーマンスが比較的低くなります。さらに、分散キャッシュ全体には、負荷分散のためのルーティングサービスが必要です。ルーティングサービスに障害が発生すると、キャッシュ全体が使用できなくなるため、高可用性も考慮する必要があります。

しかし、問題を解決できる限り、それは優れた技術であり、ある程度の副作用は許容できるものです。