負荷分散：基本的なアルゴリズムと方法

負荷計画の問題は、Webプロジェクトの開発の初期段階で決定する必要があります。 サーバーの「クラッシュ」（そして、それは常に最も不適当な瞬間に予期せずに発生します）は、非常に深刻な結果-道徳と物質の両方であふれています。 最初は、サーバーの容量を増やすか、使用するアルゴリズム、プログラムコードなどを最適化することにより、ワークロードの増加によるサーバーのパフォーマンス不足の問題を解決できます。 しかし、遅かれ早かれ、これらの対策も不十分になる瞬間が来ます。



クラスタリングに頼らなければなりません。複数のサーバーがクラスターに結合されます。 それらの間の負荷は、バランシングと呼ばれる一連の特別な方法を使用して分散されます。 高いワークロードの問題を解決することに加えて、クラスタリングはサーバーの相互冗長性を確保するのにも役立ちます。

クラスタリングの効率は、クラスターの要素間で負荷がどのように分散（バランス）されるかに直接依存します。



負荷分散は、ハードウェアツールとソフトウェアツールの両方を使用して実行できます。 この記事では、主な方法とアルゴリズム、およびバランスについて説明します。

バランスレベル

バランシング手順は、OSIモデルの以下のレベルに対応するアルゴリズムと方法の全範囲を使用して実行されます。

• ネットワーク;
• 輸送;
• 適用されます。

これらのレベルをより詳細に検討してください。

ネットワークバランシング

ネットワークレベルでの分散には、次の問題の解決が含まれます。異なる物理マシンがサーバーの1つの特定のIPアドレスを担当していることを確認する必要があります。 このようなバランスは、さまざまな方法を使用して実現できます。

• DNSバランシング。 ドメイン名ごとに複数のIPアドレスが割り当てられます。 クライアント要求の送信先のサーバーは通常、ラウンドロビンアルゴリズムを使用して決定されます（以下でバランス方法とアルゴリズムについて詳しく説明します）。
• NLBクラスターの構築。 この方法を使用する場合、サーバーは入力ノードと計算ノードで構成されるクラスターに結合されます。 負荷分散は、特別なアルゴリズムを使用して実行されます。 Microsoftのソリューションで使用されます。
• オプションのルーターを使用したIPバランシング。
• 領土の均衡化は 、インターネットの地理的に異なる地域に同じアドレスを持つ同じサービスを配置することによって実行されます（これは、 すでに説明したエニーキャストDNSテクノロジーの方法です ）。 テリトリバランスは、多くのCDNでも使用されています（ 興味深い実装例を参照）。

トランスポートレベリング

このタイプのバランシングは最も簡単です。クライアントはバランサーに連絡し、バランサーはリクエストをサーバーの1つにリダイレクトし、サーバーはそれを処理します。 リクエストを処理するサーバーの選択は、さまざまなアルゴリズムに従って実行できます（以下で詳しく説明します）：単純なラウンドロビン検索、プールから最も負荷の少ないサーバーの選択など。



トランスポートレベルでのバランシングは、ネットワークレベルでのバランシングと区別することが難しい場合があります。 BSDシステムのpfネットワークフィルターに関する次のルールを考慮してください。たとえば、正式には特定のTCPポートでのトラフィックの分散について説明しています（BSDシステムのpfネットワークフィルターの例）。

 web_servers = "{10.0.0.10、10.0.0.11、10.0.0.13}"

 $ ext_if proto tcpでポート80に一致rdr-to $ web_serversラウンドロビンスティッキーアドレス

特定のTCPポートでトラフィックのバランスを取ることです。



次に、別の例を考えます。

 $ lan_netから$ int_ifを渡します\
    route-to {（$ ext_if1 $ ext_gw1）、（$ ext_if2 $ ext_gw2）} \
   ラウンドロビン

このルールは、ネットワークレベルでの発信トラフィックのバランスを取ります。 特定のポートまたは特定のプロトコルを示すものではありません。



バランス調整レベルの違いは、次のように説明できます。 ネットワーク層には、ユーザーセッションを終了しないソリューションが含まれています。 トラフィックをリダイレクトするだけで、プロキシモードでは機能しません。

ネットワークレベルでは、バランサーは単にパケットを送信するサーバーを決定します。 クライアントとのセッションはサーバーによって実行されます。



トランスポートレベルでは、クライアントとの通信はバランサー上で閉じられ、バランサーはプロキシとして機能します。 それに代わってサーバーと対話し、追加のデータとヘッダーでクライアントに関する情報を渡します。 したがって、たとえば、人気のあるHAProxyソフトウェアバランサーが機能します。

アプリケーションレベルのバランス

アプリケーションレベルでバランスを取る場合、バランサーは「スマートプロキシ」モードで動作します。 クライアントのリクエストを分析し、リクエストされたコンテンツの性質に応じて、それらを異なるサーバーにリダイレクトします。 これは、たとえば、フロントエンドとバックエンドの間でリクエストを分散するなど、Nginx Webサーバーの仕組みです。 Nginxでのバランス調整には、アップストリームモジュールが責任を負います。 さまざまなアルゴリズムに基づいたNginxバランシングの機能の詳細については、 こちらをご覧ください 。



アプリケーションレベルのバランシングツールのもう1つの例は、クライアントとPostgreSQLデータベースサーバー間の中間層であるpgpoolです。 これを使用すると、コンテンツに応じてデータベースサーバーにクエリを配布できます。たとえば、読み取り要求は1つのサーバーに送信され、書き込み要求は別のサーバーに送信されます。 この記事でpgpoolとそれを使った作業の詳細について読んでください。

アルゴリズムとバランス方法

さまざまな負荷分散アルゴリズムと方法があります。 特定のアルゴリズムを選択するには、まず特定のプロジェクトの詳細から、次に目標から進める必要があります。 これを達成する予定です。



バランシングが使用される目標の中で、次の点を強調する必要があります。

• 公平性 ：各リクエストの処理にシステムリソースが割り当てられることを保証し、1つのリクエストが処理され、他のすべてのリクエストが順番に待機する状況を防ぐことが必要です。
• 効率性 ：要求を処理するすべてのサーバーは100％ビジーである必要があります。 サーバーの1つがリクエストの処理を待機しているアイドル状態を許可しないことをお勧めします（実際には、この目標が常に達成されるとは限らない予約をすぐに行います）。
• クエリの実行時間の短縮 ：要求の処理の開始（または処理のためにキューに入れる）から完了までの最小時間を確保する必要があります。
• 応答時間の短縮 ：ユーザー要求に対する応答時間を最小限に抑える必要があります。

また、バランシングアルゴリズムには次の特性があることが非常に望ましいです。

• 予測可能性 ：アルゴリズムがタスクを解決するのに効果的である状況と負荷を明確に理解する必要があります。
• システムリソースの均一なロード 。
• スケーラビリティ ：アルゴリズムは負荷が増加しても動作し続ける必要があります。

ラウンドロビン

ラウンドロビン、またはラウンドロビンアルゴリズムはラウンドロビン検索です。最初の要求が1つのサーバーに送信され、次に次の要求が別のサーバーに送信され、最後のサーバーに到達するまで続きます。



このアルゴリズムの最も一般的な実装は、もちろん、ラウンドロビンDNSバランシング方式です。 ご存知のように、DNSサーバーには、特定のドメインの各マシンの「ホスト名-IPアドレス」のペアが保存されています。 このリストは次のようになります。

 example.com xxx.xxx.xxx.2
 www.example.com xxx.xxx.xxx.3

リスト内の各名前に複数のIPアドレスを関連付けることができます。

 example.com xxx.xxx.xxx.2
 www.example.com xxx.xxx.xxx.3
 www.example.com xxx.xxx.xxx.4
 www.example.com xxx.xxx.xxx.5
 www.example.com xxx.xxx.xxx.6

DNSサーバーは、テーブル内のすべてのレコードを調べて、新しい要求ごとに次のIPアドレスを提供します。たとえば、最初の要求-xxx.xxx.xxx.2、2番目の要求-xxx.xxxx.xxx.3など。 その結果、クラスター内のすべてのサーバーが同じ数の要求を受け取ります。



このアルゴリズムの疑いのない利点の中で、まず、高レベルのプロトコルからの独立性と呼ばれるべきです。 ラウンドロビンアルゴリズムで動作するには、サーバーが名前でアクセスされるプロトコルが使用されます。

ラウンドロビンアルゴリズムに基づく分散は、サーバーの負荷にまったく依存しません。DNSサーバーをキャッシュすると、クライアントの流入に対処するのに役立ちます。



ラウンドロビンアルゴリズムを使用すると、サーバー間の通信が不要になるため、ローカルバランシングとグローバルバランシングの両方に使用できます。

最後に、ラウンドロビンアルゴリズムに基づくソリューションは低コストで注目に値します。それらを機能させるには、DNSにいくつかのレコードを追加するだけです。



ラウンドロビンアルゴリズムには、多くの重大な欠点もあります。 このアルゴリズムによる負荷分散が上記の公平性と効率の基準を満たすためには、各サーバーに同じリソースセットが必要です。 すべての操作を実行する場合、同じ量のリソースも関与する必要があります。 実際には、ほとんどの場合、これらの条件は不可能です。



また、ラウンドロビンアルゴリズムに従って分散する場合、クラスター内のサーバーの負荷はまったく考慮されません。 次の仮想的な状況を想像してください。ノードの1つは100％ロードされ、他のノードは10-15％ロードされているだけです。 ラウンドロビンアルゴリズムは、原則としてこのような状況の可能性を考慮していないため、過負荷のノードは引き続き要求を受信します。 この場合、正義、効率性、および予測可能性に疑問の余地はありません。



上記の状況により、ラウンドロビンアルゴリズムの範囲は非常に限られています。

加重ラウンドロビン

これは、ラウンドロビンアルゴリズムの改良バージョンです。 改善の本質は次のとおりです。各サーバーには、パフォーマンスとパワーに応じて重み係数が割り当てられます。 これは、負荷をより柔軟に分散するのに役立ちます。重みが大きいサーバーは、より多くの要求を処理します。 ただし、フォールトトレランスに関するすべての問題を解決できるわけではありません。 負荷を計画および分散するときに、より多くのパラメーターを考慮に入れる他の方法により、より効率的なバランシングが提供されます。

最小接続

前のセクションでは、ラウンドロビンアルゴリズムの主な欠点をリストしました。 もう一度呼び出しましょう。現在アクティブな接続の数は考慮されていません。



実用的な例を考えてみましょう。 2つのサーバーがあります-条件付きでAおよびBとして指定します。サーバーAには、サーバーBよりも少ないユーザーが接続されます。同時に、サーバーAはより過負荷になります。 これはどのように可能ですか？ 答えは非常に簡単です。サーバーAへの接続は、サーバーBへの接続に比べて長い時間サポートされます。



説明されている問題は、最小接続（短-leastconn）として知られるアルゴリズムを使用して解決できます。 サーバーで現在サポートされている接続の数が考慮されます。 次の各質問は、アクティブな接続の数が最も少ないサーバーに渡されます。



このアルゴリズムには改良されたバージョンがあり、主に異なる技術的特性と異なるパフォーマンスを持つサーバーで構成されるクラスターでの使用を目的としています。 これは加重最小接続と呼ばれ、アクティブな接続の数だけでなく、サーバーの重み係数も負荷を分散するときに考慮されます。



最小接続アルゴリズムのその他の改善点には、ローカリティベースの最小接続スケジューリングおよびレプリケーションスケジューリングを使用したローカリティベースの最小接続スケジューリングがあります。



最初のメソッドは、プロキシをキャッシュするために特別に作成されました。 その本質は次のとおりです。アクティブな接続の数が最も少ないサーバーに最大数の要求が送信されます。 各クライアントサーバーには、クライアントIPのグループが割り当てられます。 これらのIPからの要求は、完全にロードされていない場合、「ネイティブ」サーバーに送信されます。 それ以外の場合、要求は別のサーバーにリダイレクトされます（半分以下でロードする必要があります）。



複製スケジューリングアルゴリズムを使用したローカリティベースの最小接続スケジューリングでは、各IPアドレスまたはIPアドレスのグループは、個別のサーバーではなく、サーバーのグループ全体に割り当てられます。 要求は、グループから最も負荷の少ないサーバーに渡されます。 「ネイティブ」グループのすべてのサーバーが過負荷になると、新しいサーバーが予約されます。 この新しいサーバーは、要求の送信元のIPサービスグル​​ープに追加されます。 次に、このグループから最もビジーなサーバーが削除されます-これにより、過剰な複製が回避されます。

宛先ハッシュスケジューリングとソースハッシュスケジューリング

Destination Hash Schedulingアルゴリズムは、キャッシュプロキシのクラスターで動作するように作成されましたが、他の場合によく使用されます。 このアルゴリズムでは、リクエストを処理するサーバーは、受信者のIPアドレスによって静的テーブルから選択されます。



ソースハッシュスケジューリングアルゴリズムは前のアルゴリズムと同じ原則に基づいており、要求を処理するサーバーのみが送信者のIPアドレスによってテーブルから選択されます。

スティッキーセッション

スティッキーセッションは、着信要求を分散するためのアルゴリズムで、接続はグループ内の同じサーバーに転送されます。 たとえば、Nginx Webサーバーで使用されます。 IPハッシュ方式を使用して、特定のサーバーにユーザーセッションを割り当てることができます（詳細については、 公式ドキュメントを参照してください）。 この方法を使用すると、要求はクライアントのIPアドレスに基づいてサーバーに配信されます。 ドキュメントに記載されているように（上記のリンクを参照）、「この方法により、同じクライアントからの要求が同じサーバーに送信されます。」 特定のアドレスに割り当てられたサーバーが利用できない場合、リクエストは別のサーバーにリダイレクトされます。 構成ファイルのフラグメントの例：

アップストリームバックエンド{
 ip_hash;

サーバーbackend1.example.com;
サーバーbackend2.example.com;
サーバーbackend3.example.com;
サーバーbackend4.example.com;
 }

各サーバーのNginxのバージョン1.2.2以降では、重みを指定できます。



この方法の使用には、いくつかの問題が伴います。 クライアントが動的IPを使用している場合、セッションバインディングの問題が発生する可能性があります。 多数の要求が1つのプロキシサーバーを通過する状況では、バランスを効果的かつ公平とは言い切れません。 ただし、説明されている問題は、Cookieを使用して解決できます。 Nginxの商用バージョンには、Cookieを使用してバランスを取る特別なスティッキーモジュールがあります。 彼は無料の類似物も持っています-例えばnginx-sticky-module 。

HAProxyでsticky-sessionsメソッドを使用できます。これについての詳細は、たとえばここにあります。

おわりに

この記事は、本質的に負荷分散の概要です。 このトピックについては、今後の出版物で引き続き議論します。 質問、コメント、追加がある場合-コメントへようこそ。 また、さまざまなプロジェクトの負荷分散の構成の重要な実例を共有していただけるとありがたいです。



何らかの理由でここにコメントを投稿できない読者は、私たちのブログに参加してください 。