いくつかのシンプルな負荷分散アルゴリズム

負荷分散とは

負荷分散（英語名は Load Balance）とは、複数のサーバーを対称的に構成したサーバーセットを指します。各サーバーは同等のステータスを持ち、他のサーバーの支援なしに独立して外部にサービスを提供できます。何らかの負荷分散技術により、外部から送信されたリクエストは対称構造のサーバーに均等に分散され、リクエストを受信したサーバーはクライアントのリクエストに独立して応答します。ロード バランシングにより、クライアント要求をサーバー アレイに均等に分散できるため、重要なデータへの高速アクセスが可能になり、大量の同時アクセス サービスの問題が解決されます。このクラスター テクノロジにより、最小限の投資でメインフレームに近いパフォーマンスを実現できます。

負荷分散はソフトウェア負荷分散とハードウェア負荷分散に分かれます。前者はAlibabaの張文松博士が開発したLVSに代表され、後者はF5などのバランシングサーバーです。もちろん、これは言及しただけで、本質ではありません。

[[225437]]

この記事では、「外部から送られてきたリクエストを対称構造で均等にサーバーに分配する」ためのさまざまなアルゴリズムについて説明し、各アルゴリズムの具体的な実装を Java コードで示します。では、本題に入りましょう。本題に入る前に、IP リストをシミュレートするクラスを記述してみましょう。

ラウンドロビン

ポーリング方式はラウンドロビン方式で、そのコード実装はおおよそ次のようになります。

serverWeightMap のアドレス リストは動的であるため、マシンはいつでもオンラインになったり、オフラインになったり、クラッシュしたりする可能性があります。したがって、同時実行の問題を回避するために、メソッド内にローカル変数 serverMap が作成されます。serverMap の内容は、複数のスレッドによって変更されないように、スレッドにローカルにコピーされるようになりました。これにより、新たな問題が発生する可能性があります。レプリケーション後、serverWeightMap への変更は serverMap に反映されません。つまり、このサーバー選択ラウンドでは、負荷分散アルゴリズムは新しいサーバーまたはオフライン サーバーを認識しません。新しいアドレスを追加しても問題ありません。サーバーがオフラインまたはクラッシュしている場合は、存在しないアドレスにアクセスする可能性があります。したがって、サービス呼び出し元は、サーバーの選択と呼び出しの再開など、対応するフォールト トレラント処理を備えている必要があります。

現在のポーリング位置変数 pos については、サーバーの選択順序を保証するために、操作中にロックして、同時に 1 つのスレッドだけが pos の値を変更できるようにする必要があります。そうしないと、pos 変数が同時に変更された場合、サーバーの選択順序が保証されず、keyList 配列が境界を越える可能性もあります。

ラウンドロビン方式の利点は、リクエスト転送の絶対的なバランスを実現しようとすることです。

ポーリング方式の欠点は、リクエスト転送の絶対的なバランスを実現するために、かなりの代償を払わなければならないことです。POS 変数の変更の相互排他性を保証するために、重い悲観的ロック同期を導入する必要があり、これにより、このポーリング コードの同時スループットが大幅に低下します。

ランダム法

システムのランダム機能により、バックエンド サーバー リストのサイズに基づいて、バックエンド サーバーの 1 つがアクセス用にランダムに選択されます。確率統計の理論から、呼び出し回数が増えるにつれて、実際の効果は各バックエンド サーバーにトラフィックを均等に分散することにどんどん近づいていること、つまりポーリングの効果であることがわかります。

ランダム メソッドのコード実装は次のとおりです。

全体的なコードのアイデアはポーリング メソッドと一致しています。まず serverMap を再構築し、次にサーバー リストを取得します。サーバーを選択する際は、Random の nextInt メソッドを使用して 0 ～ keyList.size() の範囲でランダムな値を取得し、サーバーリストからサーバーアドレスをランダムに取得して返します。確率統計の理論に基づくと、スループットが大きいほど、ランダム アルゴリズムの効果がポーリング アルゴリズムの効果に近くなります。

送信元アドレスハッシュ方式

ソースアドレスハッシュの考え方は、クライアントがアクセスした IP アドレス値を取得し、ハッシュ関数を通じて値を計算し、この値を使用してサーバーリストのサイズに対してモジュロ演算を実行することです。結果は、アクセスされるサーバーのシリアル番号です。送信元アドレス ハッシュ アルゴリズムのコード実装は次のとおりです。

最初の2つの部分はポーリング方式とランダム方式と同じなので、詳細は説明しません。違いはルーティングの選択部分にあります。クライアントの IP、つまり remoteIp を通じて、そのハッシュ値を取得し、サーバー リストのサイズを法として計算します。その結果が、サーバー リスト内の選択されたサーバーのインデックス値になります。

ソース アドレス ハッシュ方式の利点は、バックエンド サーバー リストが変更されるまで、同じクライアント IP アドレスが同じバックエンド サーバーにハッシュされることが保証されることです。この機能に基づいて、サービス コンシューマーとサービス プロバイダーの間でステートフル セッションを確立できます。

ソース アドレス ハッシュ アルゴリズムの欠点は、クラスター内のサーバーが非常に安定していて、基本的にオンラインまたはオフラインにならない限り、サーバーがオンラインまたはオフラインになると、ソース アドレス ハッシュ アルゴリズムによってルーティングされたサーバーが、サーバーがオンラインまたはオフラインになる前にルーティングされたサーバーである確率が非常に低くなることです。セッションの場合はセッションが取得できず、キャッシュの場合は「雪崩」が発生する可能性があります。この説明が適切でない場合は、MemCache の非常に詳細な解釈である、一貫性ハッシュ アルゴリズムに関する部分を書いた私の以前の記事を読んでください。

加重ラウンドロビン

サーバーによってマシン構成や現在のシステム負荷が異なる場合があり、ストレス耐性も異なります。構成が高く負荷が低いマシンには、より多くのリクエストを処理できるように高い重みが割り当てられ、構成が低く負荷が高いマシンには、システム負荷を軽減するために低い重みが割り当てられます。加重ラウンドロビン方式はこの問題を適切に処理し、重みに応じてリクエストの順序をバックエンドに分散します。加重ラウンドロビン方式のコード実装は次のとおりです。

ポーリング方式と似ていますが、サーバー アドレスを取得する前に重み計算コードが追加されます。重みに応じて、アドレスはサーバー アドレス リストに繰り返し追加されます。重みが大きいほど、サーバーが各ラウンドで受信するリクエストが多くなります。

加重ランダム法

加重ラウンドロビン方式と同様に、加重ランダム方式でも、バックエンド サーバーのさまざまな構成と負荷条件に基づいて異なる重みが構成されます。違いは、順序ではなく重みに基づいてサーバーをランダムに選択することです。重み付けランダム法のコード実装は次のとおりです。

このコードはランダム方式と重み付けポーリング方式を組み合わせたものと同じです。わかりやすいので説明は省きます。

最小接続法

これまでの方法では、サービス コンシューマーのリクエスト時間をバランスよく分散させるために最善を尽くしてきました。もちろん、これは正しいです。複数のバックエンド サーバーのワークロードを均等に分散し、サーバーの使用率を最大化できます。しかし、これは本当にそうでしょうか?実際の状況では、リクエスト時間のバランスは本当に負荷のバランスを表すことができるのでしょうか?これは考える価値のある質問です。

上記の問題を別の観点から見ると、リクエストの開始者ではなく、バックエンド サーバーの観点からシステム負荷を観察することを意味します。最小接続数方式はこのカテゴリに属します。

最小接続数アルゴリズムは、より柔軟でインテリジェントです。バックエンド サーバーの構成が異なるため、リクエストの処理速度は速くなったり遅くなったりする場合があります。バックエンド サーバーの現在の接続状態に基づいて、現在のリクエストを処理するために接続バックログが最も少ないサーバーを動的に選択し、バックエンド サーバーの利用効率を最大化し、各マシンに負荷を合理的に分散します。最小接続数は、サーバー接続数の集計と認識を伴うため、設計と実装がかなり面倒です。そのため、ここでは実装については説明しません。