一貫性のあるハッシュを使用して重要な負荷を分散する

大規模なネットワーク サービス (コンテンツ ホスティングなど) を実行するには、各サーバーが過負荷にならないようにクライアントを複数のサーバーに均等に分散する負荷分散が必要です。さらに、クライアントとサーバーがいつでも追加または削除される可能性がある動的な環境では、時間の経過とともに大幅に変化しない配布スキームを見つけることが望ましいです。つまり、時間の経過とともに一貫してクライアントをサーバーに割り当てる必要があります。

背景

一貫性のあるハッシュ アルゴリズムの概念は、動的な環境での負荷分散の問題を解決するために過去に開発されてきましたが、これまでに開発されたソリューションにはすべて根本的な問題があります。特定のシナリオでは、多くのサーバーで負荷分散が最適にならない可能性があります。

さらに、クライアントとサーバーはいつでも追加または削除される可能性があるため、このような変更を行うときにあまり多くのクライアントを移動しないようにする必要があります。したがって、動的割り当てアルゴリズムは、常に正しい負荷分散を保証するだけでなく、システムが変更されるたびに移動されるクライアントの数を最小限に抑える必要があります。この割り当ての問題は、各サーバーの容量に厳しい制約がある場合、つまり、各サーバーに厳しい容量制限があり、負荷がこの制限を超えてはならない場合、さらに深刻になります。通常、容量は平均負荷に近くなるようにする必要があります。

言い換えれば、最終的な割り当てにおいて均一性と一貫性の両方を実現したいと考えています。サーバーのセットが固定され、クライアントのセットのみが更新される、はるかに単純なケースのソリューションを説明した文献は多数ありますが、この記事では、クライアントとサーバーの両方をいつでも追加および削除できる完全に動的なケースのソリューションについて説明します。

アルゴリズム

サーバーをゴミ箱に、クライアントをボールに例えることで、よく研究されているボールからゴミ箱への確率過程のモデルと同様の抽象化を使用できます。均一性の目標では、すべてのビンに平均密度 (ボールの数をビンの数で割ったもの) とほぼ等しい数のボールが含まれている必要があります。パラメータ ε については、各ビンの容量を平均負荷 (1+ε) の *** または *** 倍に設定します。この追加容量により、均一性と一貫性の両方の目標を満たす割り当てアルゴリズムを設計できます。

特定の範囲内の数字の集合が円上に分布していると想像してください。ボールに 1 つのハッシュ関数を適用し、ビンに別のハッシュ関数を適用して、円上のさまざまな位置に対応する範囲内の数字を取得します。次に、ハッシュ値とは関係のない特定の順序でボールを配布し始めます（ID に基づいていると仮定）。次に、各ボールを時計回りに移動して、空き容量のある最初のビンに割り当てます。

上記の例を分析してみましょう。 2 つの異なるハッシュ関数を使用して、6 個のボールと 3 つのゴミ箱を円上の異なる位置にランダムに割り当てます。この例では、各ビンの容量が 2 に設定されていると想定します。 ID 値の昇順でボールを配布し始めます。ボールNo.1は時計回りに動き、ゴミ箱Cに入ります。ボール番号 2 はビン A に入ります。ボール 3 と 4 はビン B に入ります。ボール番号 5 はビン C に入ります。ボール6番は時計回りに動き、最初にゴミ箱Bに入ります。ただし、ビン B の容量は 2 で、すでにボール 3 と 4 が入っています。したがって、ボール番号 6 はビン C に到達するまで前進し続けます。ただし、そのビンもいっぱいです。 ***、ボール番号 6 は、まだ空きスペースがあるビン A に入ります。

システムの更新（ボールまたはビンの挿入/削除）が行われると、均一性目標を維持するために割り当てが再計算されます。分析により、小さな更新 (少数のボールまたはビンの挿入と削除) によって割り当て状態がわずかに変化し、一貫性の目標が達成できることが示されました。私たちの論文では、このシステムでは、ボールを挿入または取り外すたびに、他のボールが O(1/ε2) 回移動することを示しています。最も重要なことは、この上限はシステム内のボールやビンの総数とはまったく関係がないということです。したがって、ボールまたはビンの数が 2 倍になっても、この上限は変わりません。この上限はボールやビンの数とは無関係であり、より大きなインスタンスに移行しても一貫性の目標を達成できるため、スケーラビリティに大きな余裕が生まれます。以下はゴミ箱/サーバーの更新時に、更新ごとに発生する移動(再割り当て)回数のシミュレーション結果です。

赤い曲線は移動平均回数を表し、青いバーは異なるε値（X軸）に対する分散を表します。破線は理論的な結果によって示唆された上限を表しており、実際の移動回数を予測するのに非常に適しています。さらに、ε の値がどのような値であっても、各ビンの負荷は平均負荷の最大 (1+ε) 倍であることがわかっています。以下に、ε=0.1、ε=0.3、ε=0.9 の異なる値に対するゴミ箱の荷重分布を示します。

▲ 異なるε値における荷重分布。すべての負荷範囲（0 から平均負荷の (1+ε) 倍まで）において、負荷分布はほぼ均一であり、多くのビンの負荷は平均負荷の (1+ε) 倍に等しくなります。

ここではトレードオフがあり、ε 値が低いと均一性には良いが一貫性には悪い、一方 ε 値が大きいと一貫性には良いということがわかります。 ε の値が小さいと、多くの負荷のハード容量制限が平均負荷の (1+ε) 倍になり、他の負荷は降順で分散されます。

コンテンツ ホスティング サービスを提供する場合、さまざまな特性を持つ多数のインスタンスに対応する準備が必要です。この一貫性のあるハッシュ方式は、最悪のシナリオでも適切に機能するため、このような状況に適しています。

社内の研究結果も興味深いものですが、より広範なコミュニティが私たちのソリューションを有用であると評価し、オープンソース化して誰でも利用できるようにしてくれたことに、さらに満足しています。

https://github.com/arodland/haproxy

[この記事は51CTOコラム「Google Developers」のオリジナル記事です。転載については原作者（WeChat公開アカウント：Google_Developers）までご連絡ください。]

この著者の他の記事を読むにはここをクリックしてください