Elasticsearchクラスターへのユーザーリクエストがロードバランサーによって分散される様子を示す図。( Wikipediaの例。)

コンピューティングにおいて、負荷分散とは、一連のタスクを一連のリソース（コンピューティングユニット）に分散させることで、全体的な処理効率を向上させるプロセスです。負荷分散により、応答時間を最適化し、一部のコンピューティングノードに不均一な過負荷がかかり、他のコンピューティングノードがアイドル状態になるといった事態を回避できます。

負荷分散は、並列コンピュータの分野における研究対象です。主なアプローチは2つあります。1つは静的アルゴリズム、もう1つは動的アルゴリズムです。動的アルゴリズムは通常より汎用的で効率的ですが、異なるコンピューティングユニット間での情報交換が必要となり、効率性が低下するリスクがあります。

問題の概要

負荷分散アルゴリズムは常に特定の問題を解決しようとします。特に、タスクの性質、アルゴリズムの複雑さ、アルゴリズムが実行されるハードウェアアーキテクチャ、そして必要なエラー許容度などを考慮する必要があります。したがって、アプリケーション固有の要件を最適に満たすための妥協点を見つける必要があります。

タスクの性質

負荷分散アルゴリズムの効率は、タスクの性質に大きく依存します。したがって、意思決定時に利用可能なタスクに関する情報が多ければ多いほど、最適化の可能性は高まります。

タスクのサイズ

各タスクの実行時間を完全に把握することで、最適な負荷分散を実現できます（プレフィックス合計のアルゴリズムを参照）。[1]残念ながら、これは実際には理想的なケースです。各タスクの正確な実行時間を把握できる状況は極めて稀です。

このため、異なる実行時間を把握するための手法はいくつか存在します。まず、タスクのサイズが比較的均一な場合、各タスクの実行時間はほぼ平均的であると見なすことができます。一方、実行時間が非常に不規則な場合は、より高度な手法を使用する必要があります。一つの手法として、各タスクにメタデータを追加することが挙げられます。類似のメタデータの過去の実行時間に基づいて、統計情報に基づいて将来のタスクを推測することが可能です。[2]

依存関係

場合によっては、タスクは互いに依存します。これらの相互依存性は、有向非巡回グラフで表すことができます。直感的に言えば、あるタスクは他のタスクが完了するまで開始できません。

各タスクの所要時間が事前にわかっていると仮定すると、最適な実行順序は総実行時間を最小化することにつながります。これはNP困難問題であるため、厳密に解くことは困難です。ジョブスケジューラのようなアルゴリズムは、メタヒューリスティック手法を用いて最適なタスク配分を計算します。

タスクの分離

負荷分散アルゴリズムの設計において重要なタスクのもう一つの特徴は、実行中にサブタスクに分割できることです。後述する ツリー型計算アルゴリズムは、この特異性を最大限に活用しています。

静的アルゴリズムと動的アルゴリズム

静的

負荷分散アルゴリズムが「静的」であるとは、タスクの配分においてシステムの状態を考慮しないことを意味します。この場合、システムの状態には、特定のプロセッサの負荷レベル（場合によっては過負荷）といった指標が含まれます。その代わりに、システム全体に関する仮定、例えば、タスクの到着時刻やリソース要件などが事前に設定されます。さらに、プロセッサの数、それぞれの処理能力、通信速度も既知です。したがって、静的負荷分散は、特定のパフォーマンス関数を最小化するために、既知のタスクセットを利用可能なプロセッサに関連付けることを目指します。その鍵となるのは、このパフォーマンス関数の概念です。

静的負荷分散技術は、一般的にルーター（マスター）を中心として集中化され、負荷を分散してパフォーマンス関数を最適化します。この最小化では、分散されるタスクに関する情報を考慮し、予想される実行時間を導き出すことができます。

静的アルゴリズムの利点は、設定が容易で、比較的定型的なタスク（ウェブサイトからのHTTPリクエストの処理など）において非常に効率的であることです。しかし、タスクの割り当てには依然として統計的なばらつきがあり、一部の計算ユニットに過負荷がかかる可能性があります。

動的

静的な負荷分散アルゴリズムとは異なり、動的アルゴリズムはシステム内の各コンピューティングユニット（ノードとも呼ばれます）の現在の負荷を考慮します。このアプローチでは、タスクを過負荷のノードから低負荷のノードへ動的に移動することで、処理速度を向上させることができます。これらのアルゴリズムの設計ははるかに複雑ですが、特にタスク間の実行時間が大きく異なる場合に優れた結果をもたらすことができます。

動的負荷分散アーキテクチャは、作業分散専用のノードを必ずしも必要としないため、よりモジュール化できます。タスクが特定の時点の状態に応じてプロセッサに一意に割り当てられる場合、それは一意割り当てと呼ばれます。一方、システムの状態や変化に応じてタスクが恒久的に再配分される場合、これは動的割り当てと呼ばれます。[3]当然のことながら、決定に至るまでに過度の通信を必要とする負荷分散アルゴリズムは、問題全体の解決を遅らせるリスクがあります。

ハードウェアアーキテクチャ

異機種マシン

並列コンピューティング インフラストラクチャは、多くの場合、異なるコンピューティング能力のユニットで構成されており、負荷分散ではこれを考慮する必要があります。

たとえば、低電力ユニットは、より少ない計算量を必要とするリクエストを受信したり、リクエスト サイズが均一または不明な場合は、より大きなユニットよりも少ないリクエストを受信したりすることがあります。

共有メモリと分散メモリ

並列コンピュータは、多くの場合、2 つの大きなカテゴリに分けられます。1 つは、すべてのプロセッサが単一の共通メモリを共有し、そのメモリ上で並列に読み取りと書き込みを行うコンピュータ ( PRAMモデル)、もう 1 つは、各コンピューティング ユニットが独自のメモリを持ち、情報がメッセージによって交換されるコンピュータ (分散メモリモデル) です。

共有メモリ型コンピュータでは、書き込み競合の管理によって各計算ユニットの個々の実行速度が大幅に低下します。しかし、並列処理では問題なく動作します。一方、メッセージ交換の場合は、各プロセッサがフルスピードで動作できます。一方、集合的なメッセージ交換の場合は、すべてのプロセッサは、最も遅いプロセッサが通信フェーズを開始するまで待機せざるを得ません。

現実には、これらのカテゴリのいずれかに正確に当てはまるシステムはほとんどありません。一般的に、プロセッサはそれぞれ、次の計算に必要なデータを格納するための内部メモリを備えており、連続したクラスタに編成されています。多くの場合、これらの処理要素は分散メモリとメッセージパッシングによって調整されます。したがって、負荷分散アルゴリズムは並列アーキテクチャに独自に適合させる必要があります。そうしないと、並列問題解決の効率が大幅に低下する リスクがあります。

階層

上記のハードウェア構造に適応すると、負荷分散アルゴリズムには主に2つのカテゴリがあります。1つは、タスクが「マスター」によって割り当てられ、「ワーカー」によって実行されるもので、ワーカーは作業の進捗状況をマスターに報告し、動的アルゴリズムの場合はマスターがワークロードの割り当てまたは再割り当てを担当します。文献ではこれをマスター・ワーカー・アーキテクチャと呼びます。もう1つは、制御を複数のノードに分散できるものです。負荷分散アルゴリズムは各ノードで実行され、タスクの割り当て（および必要に応じて再割り当てと分割）の責任が共有されます。最後のカテゴリは、動的な負荷分散アルゴリズムを想定しています。

各負荷分散アルゴリズムの設計はそれぞれ異なるため、前述の区別は明確化する必要があります。そのため、例えば各サブクラスタに「マスター」ノードを配置し、各サブクラスタ自体がグローバル「マスター」ノードの配下となるような中間的な戦略を採用することも可能です。また、マスタースレーブ方式と分散制御方式を交互に用いる多層構成も存在します。後者の戦略はすぐに複雑になるため、実際に使用されることは稀です。設計者は、制御が容易なアルゴリズムを好みます。

大規模アーキテクチャへの適応（スケーラビリティ）

非常に長期にわたって実行されるアルゴリズム（サーバー、クラウドなど）の文脈では、コンピュータアーキテクチャは時間とともに進化します。しかし、毎回新しいアルゴリズムを設計する必要がないことが望ましいです。

したがって、負荷分散アルゴリズムにとって極めて重要なパラメータは、スケーラブルなハードウェアアーキテクチャへの適応能力です。これはアルゴリズムのスケーラビリティと呼ばれます。アルゴリズムが入力パラメータに対してスケーラブルであると言われるのは、そのパラメータのサイズにパフォーマンスが比較的依存しないときです。

アルゴリズムが変化する演算ユニット数に適応できるものの、実行前に演算ユニット数を固定しなければならない場合、そのアルゴリズムは「成形可能」と呼ばれます。一方、アルゴリズムが実行中にプロセッサ数の変動に対応できる場合、そのアルゴリズムは「柔軟」と呼ばれます。ほとんどの負荷分散アルゴリズムは、少なくとも「成形可能」です。[4]

フォールトトレランス

特に大規模な計算クラスタでは、単一のコンポーネントの障害に耐えられないような並列アルゴリズムを実行することは許容されません。そのため、プロセッサの障害を検出し、計算を回復できるフォールトトレラントアルゴリズムが開発されています。[5]

アプローチ

タスクを完全に把握した静的配布:接頭辞合計

タスクが互いに独立しており、それぞれの実行時間とタスクを細分化できる場合は、単純で最適なアルゴリズムが存在します。

タスクの分割可能性に応じた負荷分散アルゴリズム

各プロセッサに同じ量の計算を割り当てるようにタスクを分割すれば、あとは結果をグループ化するだけです。プレフィックスサムアルゴリズムを用いることで、この分割はプロセッサ数に対する対数時間で計算できます。 [要出典]

しかし、タスクを細分化できない場合（つまり、タスクがアトミックである場合）、タスク割り当ての最適化は難しい問題ではあるものの、各タスクのサイズが各ノードで実行される計算量よりもはるかに小さいという条件で、比較的公平なタスクの配分を近似することは可能です。[1]

多くの場合、タスクの実行時間は不明であり、大まかな近似値しか得られません。このアルゴリズムは特に効率的ですが、このようなシナリオには適していません。

事前知識なしの静的荷重分散

実行時間が事前にまったくわからない場合でも、静的な負荷分散は常に可能です。

ラウンドロビンスケジューリング

ラウンドロビンアルゴリズムでは、最初のリクエストは最初のサーバーに送信され、次のリクエストは2番目のサーバーに送信され、これを繰り返して最後のサーバーまで続きます。その後、再び開始され、次のリクエストは最初のサーバーに割り当てられ、これを繰り返します。

このアルゴリズムは、最も強力なユニットが最も多くのリクエストを受信し、最初に受信するように重み付けできます。

ランダムな静的

ランダム化された静的負荷分散とは、タスクを異なるサーバーにランダムに割り当てるだけの単純な方法です。この方法は非常に有効です。一方、タスク数が事前にわかっている場合は、事前にランダムな順列を計算しておく方がさらに効率的です。これにより、割り当てごとの通信コストを回避できます。すべてのプロセッサが自分に割り当てられたタスクを把握しているため、分散マスターは不要になります。タスク数が不明な場合でも、すべてのプロセッサが認識している疑似ランダム割り当て生成によって通信を回避することができます。

この戦略のパフォーマンス (特定の固定タスク セットの合計実行時間で測定) は、タスクの最大サイズとともに低下します。

その他

もちろん、他の割り当て方法もあります。

  • 作業の削減: より少ない[説明が必要]作業でより多くのタスクをサーバーに割り当てます(この方法は重み付けすることもできます)。
  • ハッシュ:ハッシュ テーブルに従ってクエリを割り当てます。
  • 2つの選択肢の力：ランダムに2つのサーバーを選択し、2つの選択肢のうちより良い方を選択する。[6] [7]

マスターワーカー制度

マスター・ワーカー方式は、最もシンプルな動的負荷分散アルゴリズムの一つです。マスターは、すべてのワーカー（「スレーブ」と呼ばれることもあります）にワークロードを分配します。初期状態では、すべてのワーカーはアイドル状態であり、そのことをマスターに報告します。マスターはワーカーからの要求に応答し、タスクを各ワーカーに分配します。マスターは、割り当てるタスクがなくなると、ワーカーにタスクの要求を停止するよう通知します。

このシステムの利点は、負担を非常に公平に分散できることです。実際、割り当てに必要な時間を考慮しなければ、実行時間は上記のプレフィックスの合計と同程度になります。

このアルゴリズムの問​​題点は、必要な通信量が多いため、多数のプロセッサへの適応が困難なことです。このスケーラビリティの欠如により、非常に大規模なサーバーや並列コンピュータではすぐに動作不能になります。マスターがボトルネックとして機能します。

マスターワーカーとボトルネック

しかし、マスターを複数のプロセッサで利用可能なタスクリストに置き換えることで、アルゴリズムの品質を大幅に向上させることができます。このアルゴリズムは実装がやや難しいものの、スケーラビリティは大幅に向上します。ただし、非常に大規模なコンピューティングセンターには依然として不十分です。

システムの知識を必要としない非階層型アーキテクチャ:仕事の窃盗

タスクの完了に必要な時間が不明な場合にスケーラビリティの問題を克服するもう 1 つの手法は、ワーク スティーリングです。

このアプローチは、各プロセッサに一定数のタスクをランダムまたは事前定義された方法で割り当て、非アクティブなプロセッサがアクティブなプロセッサまたは過負荷のプロセッサから作業を「奪う」ことを可能にするというものです。この概念には、タスク分割モデルとプロセッサ間の交換を決定するルールによって定義される、いくつかの実装方法があります。この手法は特に効果的ですが、プロセッサが問題の解決ではなく通信に重点を置かないようにする必要があるため、実装が困難です。

アトミックタスクの場合、主に2つの戦略が考えられます。1つは、負荷の低いプロセッサが自身の計算能力を負荷の高いプロセッサに提供する戦略、もう1つは、最も負荷の高いユニットが割り当てられたワークロードを軽減しようとする戦略です。[8]によると、ネットワークの負荷が高い場合、最も負荷の低いユニットが自身の可用性を提供する方が効率的であり、ネットワークの負荷が低い場合、過負荷のプロセッサが最も非アクティブなプロセッサからのサポートを必要とすることが示されています。この経験則により、交換されるメッセージの数が制限されます。

原子レベルを超えて分割できない単一の大きなタスクから開始する場合、親タスクが作業ツリーに分散される 非常に効率的なアルゴリズム「ツリー型計算」 [9]があります。

原理

最初は、多くのプロセッサが空のタスクを持っていますが、そのうち 1 つは順番に作業するものです。アイドル状態のプロセッサは、他のプロセッサ (必ずしもアクティブとは限らない) にランダムに要求を発行します。後者は、作業中のタスクを細分化できる場合、作業の一部を要求元のノードに送信することで細分化します。そうでない場合は、空のタスクを返します。これにより、ツリー構造が生成されます。サブタスクが完了したら、親プロセッサに終了信号を送信する必要があります。これにより、サブタスクはツリーのルートに到達するまで、その親プロセッサにメッセージを送信します。最初のプロセッサ (つまりルート) が終了したら、グローバル終了メッセージをブロードキャストできます。最後に、ツリーをさかのぼって結果をアセンブルする必要があります。

効率

このようなアルゴリズムの効率は、ジョブの分割と通信時間が実行すべき作業量に比べてそれほど高くない場合、プレフィックスの合計に近くなります。通信コストが高すぎないようにするために、共有メモリ上にジョブのリストを置くことが考えられます。つまり、マスタープロセッサからの要求に応じて、この共有メモリ上の特定の位置から読み取るという単純な処理で済みます。

ユースケース

並列計算による効率的な問題解決に加えて、負荷分散アルゴリズムは、大規模なユーザーがいるサイトで 1 秒あたり大量のリクエストを処理できなければならない HTTPリクエスト管理でも広く使用されています。

インターネットベースのサービス

負荷分散の最も一般的な用途の一つは、複数のサーバー（サーバーファームとも呼ばれる）から単一のインターネットサービスを提供することです。一般的な負荷分散システムには、人気のあるウェブサイト、大規模なインターネットリレーチャットネットワーク、高帯域幅のファイル転送プロトコル（FTP）サイト、ネットワークニュース転送プロトコル（NNTP）サーバー、ドメインネームシステム（DNS）サーバー、データベースなどがあります。

ラウンドロビンDNS

ラウンドロビンDNSは、専用のソフトウェアまたはハードウェアノードを必要としない負荷分散の代替手法です。この手法では、複数のIPアドレスが単一のドメイン名に関連付けられ、クライアントにはラウンドロビン方式でIPアドレスが割り当てられます。クライアントに割り当てられるIPアドレスの有効期限は短いため、クライアントが要求されたインターネットサービスに次回アクセスする際には、異なるIPアドレスを使用する可能性が高くなります。

DNS委任

DNSを用いた負荷分散のより効果的な手法として、www.example.orgをサブドメインとして委任し、そのゾーンをウェブサイトを提供している各サーバーで管理するという方法があります。この手法は、個々のサーバーがインターネット上に地理的に分散している場合に特に効果的です。例えば、次のようになります。

one.example.org A 192.0.2.1
two.example.org A 203.0.113.2
www.example.org NS one.example.org
www.example.org NS two.example.org

しかし、各サーバーのwww.example.orgのゾーンファイルは異なっており、各サーバーは自身のIPアドレスをAレコードとして解決します。[10]サーバー1のwww.example.orgのゾーンファイルは次のように報告しています。

192.0.2.1の@

サーバー2では同じゾーン ファイルに次の内容が含まれます。

203.0.113.2の@

この方法により、サーバーがダウンした場合、そのDNSは応答しなくなり、Webサービスはトラフィックを受信しなくなります。あるサーバーへの回線が混雑した場合、DNSの信頼性が低いため、そのサーバーに到達するHTTPトラフィックは減少します。さらに、リゾルバへの最も速いDNS応答は、ほぼ常にネットワークに最も近いサーバーからの応答であるため、地理的な負荷分散が確保されます[要出典] 。AレコードのTTLを短くすることで、サーバーがダウンした際にトラフィックが迅速に迂回されるようになります。この手法では、個々のクライアントがセッション中に個々のサーバー間を切り替えてしまう可能性があることを考慮する必要があります。

クライアント側ランダム負荷分散

負荷分散のもう一つのアプローチは、サーバーのIPアドレスのリストをクライアントに提供し、接続ごとにクライアントにリストからランダムにIPアドレスを選択させることである。[11] [12]これは基本的に、すべてのクライアントが同様の負荷を生成することと、大数の法則[12]を利用してサーバー間で比較的均一な負荷分散を実現するというものである。クライアント側のランダム負荷分散は、ラウンドロビンDNSよりも優れた負荷分散を実現する傾向があると主張されている。これは、ラウンドロビンDNSのキャッシュの問題に起因する。大規模なDNSキャッシュサーバーの場合、ラウンドロビンDNSの分散が歪む傾向があるのに対し、クライアント側のランダム選択はDNSキャッシュの有無にかかわらず影響を受けない。[12]

このアプローチでは、クライアントへのIPリストの配信方法は多様であり、DNSリスト（ラウンドロビンなしですべてのクライアントに配信）として実装することも、リストにハードコーディングすることもできます。「スマートクライアント」を使用すると、ランダムに選択されたサーバーがダウンしていることを検出し、ランダムに再接続することで、フォールトトレランスも実現できます。

サーバー側ロードバランサー

インターネットサービスにおいて、サーバー側ロードバランサは通常、外部クライアントがサービスにアクセスするために接続しているポートをリッスンするソフトウェアプログラムです。ロードバランサはリクエストを「バックエンド」サーバーの1つに転送し、通常、バックエンドサーバーはロードバランサに応答します。これにより、クライアントは内部の機能分離を意識することなく、ロードバランサからクライアントに応答できます。また、クライアントがバックエンドサーバーに直接アクセスするのを防ぐため、内部ネットワークの構造を隠蔽し、カーネルのネットワークスタックや他のポートで実行されている無関係なサービスへの攻撃を防ぐというセキュリティ上の利点もあります。

一部のロードバランサは、すべてのバックエンドサーバーが利用できなくなった場合に特別な処理を実行するメカニズムを備えています。これには、バックアップロードバランサへの転送や、障害に関するメッセージの表示などが含まれます。

ロードバランサ自体が単一障害点とならないことも重要です。通常、ロードバランサは高可用性ペアで実装され、特定のアプリケーションで必要に応じてセッション持続データの複製も行われます。[13]一部のアプリケーションでは、定義されたネットワークの外側にある差分共有プラットフォームを介してロードバランシングポイントをオフセットすることで、この問題の影響を受けないようにプログラムされています。これらの機能とペアになっているシーケンシャルアルゴリズムは、特定のデータベースに固有の柔軟なパラメータによって定義されます。[14]

スケジューリングアルゴリズム

ロードバランサーは、リクエストをどのバックエンドサーバーに送信するかを決定するために、様々なスケジューリングアルゴリズム（負荷分散方式とも呼ばれる）を使用します。単純なアルゴリズムには、ランダム選択、ラウンドロビン、最小接続数などがあります。[15]より高度なロードバランサーでは、サーバーの報告負荷、最小応答時間、稼働/停止状態（何らかの監視ポーリングによって決定）、アクティブな接続数、地理的な場所、機能、最近割り当てられたトラフィック量など、追加の要素を考慮する場合があります。

粘り強さ

負荷分散型サービスを運用する際の重要な課題は、ユーザーセッション内の複数のリクエストに渡って保持する必要がある情報をどのように処理するかです。この情報が1つのバックエンドサーバーにローカルに保存されている場合、異なるバックエンドサーバーへの後続のリクエストではその情報を見つけることができません。これはキャッシュされた情報であり、再計算可能である可能性があります。その場合、リクエストを別のバックエンドサーバーに負荷分散すると、パフォーマンスの問題が発生するだけです。[15]

理想的には、ロードバランサーの背後にあるサーバークラスターはセッションを認識しないようにする必要があります。そうすることで、クライアントがいつどのバックエンドサーバーに接続しても、ユーザーエクスペリエンスは影響を受けません。これは通常、共有データベースまたはMemcachedのようなインメモリセッションデータベースによって実現されます。

セッションデータの問題に対する基本的な解決策の一つは、ユーザーセッション内のすべてのリクエストを一貫して同じバックエンドサーバーに送信することです。これは「永続性」または「スティッキネス」と呼ばれます。この手法の大きな欠点は、自動フェイルオーバーが機能しないことです。バックエンドサーバーがダウンすると、セッションごとの情報にアクセスできなくなり、そのサーバーに依存するセッションはすべて失われます。同じ問題は、中央データベースサーバーにも共通して発生します。Webサーバーが「ステートレス」で「スティッキネス」ではない場合でも、中央データベースはステートレスです（下記参照）。

特定のサーバーへの割り当ては、ユーザー名、クライアント IP アドレス、またはランダムに基づく場合があります。DHCP、ネットワーク アドレス変換、およびWeb プロキシによってクライアントが認識しているアドレスが変化するため、この方法は信頼できない場合があります。 ランダム割り当てはロード バランサーで記憶する必要があるため、ストレージに負担がかかります。 ロード バランサーが交換または障害を起こすと、この情報が失われる可能性があり、割り当てテーブルで使用可能なスペースを超えないように、タイムアウト期間後または高負荷期間中に割り当てを削除する必要がある場合があります。 ランダム割り当て方法では、クライアントが何らかの状態を維持する必要があり、たとえば Web ブラウザーが Cookie の保存を無効にしている場合などに問題が発生する可能性があります。 高度なロード バランサーは、複数の永続化手法を使用して、1 つの方法の欠点の一部を回避します。

もう一つの解決策は、セッションごとのデータをデータベースに保存することです。これはデータベースの負荷を増加させるため、一般的にパフォーマンスに悪影響を及ぼします。データベースは、セッションごとのデータよりも一時的ではない情報を保存するのに最適です。データベースが単一障害点となるのを防ぎ、スケーラビリティを向上させるために、データベースは複数のマシンに複製され、負荷分散によってクエリ負荷がレプリカ間で分散されることがよくあります。Microsoft のASP.net State Serverテクノロジは、セッションデータベースの一例です。Webファーム内のすべてのサーバーは、セッションデータをState Serverに保存し、ファーム内のどのサーバーからでもデータを取得できます。

クライアントが Web ブラウザである非常に一般的なケースでは、シンプルですが効率的な方法は、ブラウザ自体にセッションごとのデータを保存することです。これを実現する 1 つの方法は、適切にタイムスタンプを付けて暗号化したブラウザ Cookie を使用することです。もう 1 つの方法はURL 書き換えです。クライアントにセッション データを保存することが、一般的に推奨されるソリューションです。そうすれば、ロード バランサはリクエストを処理するバックエンド サーバを自由に選択できます。ただし、この状態データ処理方法は、セッション状態ペイロードが大きく、サーバ上でリクエストごとにそれを再計算することが不可能な、一部の複雑なビジネス ロジックシナリオには適していません。URL 書き換えには、エンド ユーザが簡単に送信 URL を変更してセッション ストリームを変更できるため、セキュリティ上の大きな問題があります。

永続的なデータを保存するためのもう 1 つのソリューションは、各データ ブロックに名前を関連付け、分散ハッシュ テーブルを使用して、その名前を利用可能なサーバーの 1 つに疑似ランダムに割り当て、そのデータ ブロックを割り当てられたサーバーに保存することです。

ロードバランサの機能

ハードウェアおよびソフトウェアロードバランサには、様々な特殊機能があります。ロードバランサの基本的な機能は、スケジューリングアルゴリズムに従って、受信リクエストをクラスタ内の複数のバックエンドサーバーに分散させることです。以下の機能のほとんどはベンダー固有のものです。

非対称荷重
比率を手動で割り当てることで、一部のバックエンドサーバーに他のサーバーよりも多くのワークロードを割り当てることができます。これは、一部のサーバーのキャパシティが他のサーバーよりも高いことを考慮するための大まかな方法​​として使用される場合があり、必ずしも期待どおりに機能するとは限りません。
優先アクティベーション
利用可能なサーバーの数が一定数を下回ったり、負荷が高くなりすぎたりすると、スタンバイ サーバーをオンラインにすることができます。
TLS オフロードと加速
TLS（またはその前身であるSSL）アクセラレーションは、暗号プロトコルの計算を専用ハードウェアにオフロードする技術です。ワークロードによっては、TLSリクエストの暗号化と認証処理がWebサーバーのCPU負荷の大部分を占める場合があります。負荷が増加すると、TLSのオーバーヘッドがWebサーバー間で分散されるため、ユーザーの応答時間が低下します。Webサーバーへの負荷を軽減するために、バランサーはTLS接続を終了し、HTTPSリクエストをHTTPリクエストとしてWebサーバーに渡します。バランサー自体が過負荷になっていなければ、エンドユーザーが体感するパフォーマンスはそれほど低下しません。このアプローチの欠点は、すべてのTLS処理が単一のデバイス（バランサー）に集中するため、新たなボトルネックとなる可能性があることです。一部のロードバランサーアプライアンスには、TLS処理専用のハードウェアが搭載されています。非常に高価な専用ハードウェアであるロードバランサーをアップグレードする代わりに、TLSオフロードを諦めてWebサーバーをいくつか追加する方がコストを抑えられる場合があります。また、Oracle/Sunなどの一部のサーバーベンダーは、T2000などのCPUに暗号化アクセラレーションハードウェアを組み込んでいます。F5 Networksは、TLSトラフィックの暗号化と復号化に使用するローカルトラフィックマネージャ（LTM）に専用のTLSアクセラレーションハードウェアカードを組み込んでいます。バランサーにおけるTLSオフロードの明確な利点の一つは、HTTPSリクエスト内のデータに基づいてバランシングやコンテンツスイッチングを行えることです。
分散型サービス拒否（DDoS）攻撃からの保護
ロード バランサは、 SYN クッキーや遅延バインディング (バックエンド サーバーは TCP ハンドシェイクが完了するまでクライアントを認識しない)などの機能を提供して、 SYN フラッド攻撃を軽減し、一般的にサーバーの作業をより効率的なプラットフォームにオフロードします。
HTTP圧縮
HTTP圧縮は、すべての最新ウェブブラウザで利用可能なgzip圧縮を利用することで、HTTPオブジェクトの転送データ量を削減します。レスポンスのサイズが大きく、クライアントとの距離が遠いほど、この機能によるレスポンス時間の改善効果は大きくなります。ただし、この機能はロードバランサーのCPU負荷を増加させるため、ウェブサーバーで処理することも可能です。
TCPオフロード
ベンダーによって用語は異なりますが、基本的に各クライアントからのHTTPリクエストはそれぞれ異なるTCP接続で処理されます。この機能はHTTP/1.1を利用して、複数のクライアントからの複数のHTTPリクエストをバックエンドサーバーへの単一のTCPソケットに統合します。
TCPバッファリング
ロード バランサは、サーバーからの応答をバッファリングし、そのデータを低速クライアントに少しずつ送信することで、Web サーバーが、リクエスト全体をクライアントに直接送信する場合よりも速く、他のタスクのためにスレッドを解放できるようにします。
直接サーバーリターン
要求と応答が異なるネットワーク パスを持つ非対称負荷分散のオプション。
ヘルスチェック
バランサは、アプリケーション層の正常性についてサーバーをポーリングし、障害のあるサーバーをプールから削除します。
HTTPキャッシュ
バランサーは静的コンテンツを保存するため、一部のリクエストはサーバーに接続せずに処理できます。
コンテンツフィルタリング
一部のバランサーは、通過中のトラフィックを任意に変更できます。
HTTPセキュリティ
一部のバランサーは、HTTP エラー ページを非表示にしたり、HTTP 応答からサーバー識別ヘッダーを削除したり、Cookie を暗号化してエンド ユーザーが操作できないようにしたりできます。
優先キューイング
レート シェーピングとも呼ばれ、異なるトラフィックに異なる優先順位を付ける機能です。
コンテンツ認識スイッチング
ほとんどのロード バランサは、要求が暗号化されていない (HTTP) か、暗号化されている (HTTPS 経由) 場合は HTTPS 要求がロード バランサで終了 (復号化) されることを前提として、要求されている URL に基づいて異なるサーバーに要求を送信できます。
クライアント認証
ウェブサイトへのアクセスを許可する前に、さまざまな認証ソースに対してユーザーを認証します。
プログラムによるトラフィック操作
少なくとも 1 つのバランサーでは、スクリプト言語を使用して、カスタム バランシング メソッドや任意のトラフィック操作などが可能になります。
ファイアウォール
ファイアウォールは、ネットワーク セキュリティ上の理由から、バックエンド サーバーへの直接接続をブロックできます。
侵入防止システム
侵入防止システムは、ファイアウォール セキュリティによって提供されるネットワーク/トランスポート層に加えて、アプリケーション層のセキュリティも提供します。

通信

負荷分散は、冗長化された通信リンクを備えたアプリケーションで役立ちます。例えば、企業では複数のインターネット接続があり、そのうちの1つの接続に障害が発生した場合でもネットワークへのアクセスを確保できる場合があります。フェイルオーバー構成では、1つのリンクを通常使用に割り当て、もう1つのリンクはプライマリリンクに障害が発生した場合にのみ使用されます。

ロードバランシングを使用することで、両方のリンクを常に使用できます。デバイスまたはプログラムは、すべてのリンクの可用性を監視し、パケットを送信するパスを選択します。複数のリンクを同時に使用することで、利用可能な帯域幅が増加します。

最短経路ブリッジング

TRILL（Transparent Interconnection of Lots of Links）は、イーサネットが任意のトポロジを持つことを容易にし、ダイクストラのアルゴリズムを用いて、設定やユーザーの介入なしに、フローごとにペアワイズ負荷分散を可能にします。TRILLのきっかけとなったのは、2002年11月13日にベス・イスラエル・ディーコネス医療センターで始まったイベントでした。 [16] [17] Rブリッジ[18] [sic] の概念は、2004年に電気電子学会（IEICE）に初めて提案されましたが、 [19] IEICEは2005年に[20] 、後にTRILLとして知られるようになった概念を却下しました。そして、2006年から2012年にかけて[21] 、互換性のない派生形として最短パスブリッジング（Shortest Path Bridging ）を考案しました。

IEEEは2012年5月にIEEE 802.1aq規格を承認しました[22]。これは最短パスブリッジング（SPB）としても知られています。SPBは、複数の等コストパスを介してすべてのリンクをアクティブにすることを可能にし、より高速な収束時間を提供してダウンタイムを削減し、トラフィックをネットワークのすべてのパスに分散させることで、メッシュネットワークトポロジ（部分接続および/または完全接続）における負荷分散の使用を簡素化します[23] [24] 。SPBは、設定時の人為的ミスを事実上排除するように設計されており、イーサネットをレイヤー2の事実上のプロトコルとして確立したプラグアンドプレイの性質を維持しています[25]。

ルーティング1

多くの通信会社は、自社ネットワーク内または外部ネットワークへの複数のルートを保有しています。高度な負荷分散技術を用いてトラフィックをあるパスから別のパスへ切り替えることで、特定のリンクにおけるネットワーク輻輳を回避し、場合によっては外部ネットワークを経由する転送コストを最小限に抑えたり、ネットワークの信頼性を向上させたりしています。

負荷分散のもう一つの用途は、ネットワーク監視です。ロードバランサーは、膨大なデータフローを複数のサブフローに分割し、複数のネットワークアナライザーでそれぞれ元のデータの一部を読み取ることができます。これは、10GbEやSTM64のような高速ネットワークの監視に非常に役立ちます。これらのネットワークでは、ワイヤースピードでは複雑なデータ処理が不可能な場合があります。[26]

データセンターネットワーク

負荷分散は、データセンターネットワークにおいて、任意の2つのサーバー間の既存の多数のパスにトラフィックを分散させるために広く利用されています。[27]これにより、ネットワーク帯域幅をより効率的に利用し、プロビジョニングコストを削減できます。一般的に、データセンターネットワークにおける負荷分散は、静的と動的に分類できます。

静的負荷分散は、トラフィックフローの送信元アドレスと宛先アドレス、およびポート番号のハッシュを計算し、それに基づいてフローを既存のパスの1つに割り当てる方法を決定することでトラフィックを分散します。動的負荷分散は、異なるパスの帯域幅使用状況を監視することで、トラフィックフローをパスに割り当てます。動的割り当てには、プロアクティブとリアクティブがあります。前者の場合、割り当ては一度行われると固定されますが、後者の場合、ネットワークロジックは利用可能なパスを監視し続け、ネットワーク利用率の変化（新しいフローの到着や既存のフローの完了など）に応じてフローをパス間で切り替えます。データセンターネットワークにおける負荷分散の包括的な概要が公開されています。[27]

フェイルオーバー

負荷分散は、フェイルオーバー、つまり1つまたは複数のコンポーネントに障害が発生した後もサービスを継続する仕組みを実現するためによく利用されます。コンポーネントは継続的に監視され（例えば、ウェブサーバーは既知のページを取得することで監視されます）、あるコンポーネントが応答しなくなると、ロードバランサーに通知され、そのコンポーネントへのトラフィックの送信を停止します。あるコンポーネントがオンラインに戻ると、ロードバランサーはそのコンポーネントへのトラフィックの再ルーティングを開始します。この仕組みが機能するには、サービスのキャパシティを超えるコンポーネントが少なくとも1つ必要です（N+1冗長性）。これは、稼働中のすべてのコンポーネントが、障害発生時に処理を引き継ぐ単一のバックアップコンポーネントとペアになっているフェイルオーバー方式（デュアルモジュール冗長性）よりもはるかに安価で柔軟性に優れています。一部のRAIDシステムでは、同様の効果を得るためにホットスペアを利用することもできます。 [28]

この手法は、システムの中で最も複雑で障害が発生しやすい部分を迅速に代替することで、フォールトトレランスを向上させることができます。ただし、ロードバランサ自体が単一障害点になる可能性があります。

AIモデルトレーニングのためのデータ取り込み

人工知能（ AI）の トレーニングや推論システム（「 AIファクトリー」と呼ばれることもある）に供給される大容量データ取り込みパイプラインの管理に、負荷分散技術がますます利用されるようになっています。これらのAI駆動型環境では、膨大な量の構造化データと非構造化データを継続的に処理する必要があり、ネットワーク、ストレージ、計算リソースに大きな負荷がかかります。[29]必要な高スループットと低レイテンシを維持するために、組織では高度なTCP最適化、接続プーリング、適応型スケジューリング機能を備えた負荷分散ツールを導入することが一般的です。これらの機能は、受信データ要求をサーバーまたはノード間で均等に分散し、輻輳を防ぎ、計算リソースが効率的に利用されるようにするのに役立ちます。[30]

大規模または高性能なAI環境に導入されたロードバランサーは、帯域幅の制約を緩和し、さまざまなデータガバナンス要件に対応します。特に、機密性の高いトレーニングデータをサードパーティのクラウドサービスに送信できない場合に有効です。ロードバランサーは、データをローカル（オンプレミス）またはプライベートクラウドにルーティングすることで、AIワークフローがパブリッククラウドの帯域幅制限を回避し、転送コストを削減し、規制基準へのコンプライアンスを維持できるようにします。AIモデルの規模が拡大するにつれて（数十億、あるいは数兆の​​パラメータで測定されることが多い）、データ取り込みのためのロードバランシングは、AIファクトリーの信頼性、拡張性、コスト効率を維持するために、ますます重要になっています。

参照

参考文献

  1. ^ ab サンダース, ピーター; メルホーン, クルト; ディーツフェルビンガー, マーティン; デメンティエフ, ローマン (2019年9月11日).シーケンシャルおよびパラレルアルゴリズムとデータ構造：基本ツールボックス. シュプリンガー. ISBN 978-3-030-25208-3。
  2. ^ Liu, Qi; Cai, Weidong; Jin, Dandan; Shen, Jian; Fu, Zhangjie; Liu, Xiaodong; Linge, Nigel (2016年8月30日). 「異機種分散環境におけるランタイムタスクの実行時間の推定精度」. Sensors . 16 (9): 1386. Bibcode :2016Senso..16.1386L. doi : 10.3390/s16091386 . PMC 5038664. PMID 27589753.  S2CID 391429  . 
  3. ^ Alakeel, Ali (2009年11月). 「分散コンピュータシステムにおける動的負荷分散ガイド」. International Journal of Computer Science and Network Security . 10 .
  4. ^ Asghar, Sajjad; Aubanel, Eric; Bremner, David (2013年10月). 「動的成形可能なジョブスケジューリングに基づく並列SATソルバー」. 2013年第42回国際並列処理会議. pp.  110– 119. doi :10.1109/ICPP.2013.20. ISBN 978-0-7695-5117-3. S2CID  15124201。
  5. ^ Punetha Sarmila, G.; Gnanambigai, N.; Dinadayalan, P. (2015). 「フォールトトレラントに関する調査 — クラウドコンピューティングにおける負荷分散アルゴリズム」2015年第2回国際電子通信システム会議 (ICECS) . pp.  1715– 1720. doi :10.1109/ECS.2015.7124879. ISBN 978-1-4799-7225-8. S2CID  30175022。
  6. ^ 「NGINXと「2つの選択肢の力」負荷分散アルゴリズム」nginx.com 2018年11月12日。2019年12月12日時点のオリジナルよりアーカイブ。
  7. ^ 「「Power of Two Random Choices」負荷分散のテスト」haproxy.com 2019年2月15日。2019年2月15日時点のオリジナルよりアーカイブ。
  8. ^ Eager, Derek L; Lazowska, Edward D; Zahorjan, John (1986年3月1日). 「受信側開始型と送信側開始型の適応型負荷分散の比較」.パフォーマンス評価. 6 (1): 53– 68. doi :10.1016/0166-5316(86)90008-8. ISSN  0166-5316.
  9. ^ ピーター・サンダース (1998)。 「並列アプリケーションのモデルとしてのツリー型計算」。アプリケーションベースの負荷分散に関するワークショップ (Alv '98)、ミュンヘン、25. - 26. März 1998 - Veranst。 Vom Sonderforschungsbereich 342「Werkzeuge und Methoden für die Nutzung Paralleler Rechnerarchitekturen」。編集: A. ボーデ: 123.土井:10.5445/ir/1000074497。
  10. ^ 「第8章 IPv4アドレス（A）レコード」www.zytrax.com。
  11. ^ 「パターン: クライアント側の負荷分散」。2015年10月15日。2020年11月29日時点のオリジナルよりアーカイブ。
  12. ^ abc 「サーバーサイドアーキテクチャ。フロントエンドサーバーとクライアントサイドランダムロードバランシング」。IT Hare on Soft.ware。2015年12月28日。
  13. ^ 「高可用性」. linuxvirtualserver.org . 2013年11月20日閲覧。
  14. ^ Ranjan, R (2010). 「ピアツーピアクラウドプロビジョニング：サービス検出と負荷分散」.クラウドコンピューティング.
  15. ^ ab 「Load Balancing 101: Nuts and Bolts」. F5 . 2017年12月5日. オリジナルより2017年12月5日時点のアーカイブ。 2018年3月23日閲覧。
  16. ^ 「All Systems Down」（PDF） . cio.com . IDG Communications, Inc. 2020年9月23日時点のオリジナル（PDF）からアーカイブ。 2022年1月9日閲覧。
  17. ^ 「All Systems Down」. cio.com . IDG Communications, Inc. 2022年1月9日時点のオリジナルよりアーカイブ。 2022年1月9日閲覧。
  18. ^ 「Rbridges: Transparent Routing」（PDF） . courses.cs.washington.edu . Radia Perlman、Sun Microsystems Laboratories. 2022年1月9日時点のオリジナル（PDF）からアーカイブ。 2022年1月9日閲覧。
  19. ^ 「Rbridges: Transparent Routing」. researchgate.net . Radia Perlman（サン・マイクロシステムズ）; Donald Eastlake 3rd（モトローラ）。
  20. ^ 「TRILLチュートリアル」（PDF） . postel.org . Donald E. Eastlake 3rd、Huawei. 2023年3月29日時点のオリジナル（PDF）からアーカイブ。 2022年1月14日閲覧。
  21. ^ 「IEEE 802.1: 802.1aq - 最短パスブリッジング」. ieee802.org . 米国電気電子学会.
  22. ^ Shuang Yu (2012年5月8日). 「IEEE、新しいIEEE 802.1aq™最短経路ブリッジング標準を承認」. IEEE. 2013年5月14日時点のオリジナルよりアーカイブ。 2012年6月2日閲覧。
  23. ^ Peter Ashwood-Smith (2011年2月24日). 「Shortest Path Bridging IEEE 802.1aq Overview」(PDF) . Huawei. 2013年5月15日時点のオリジナル(PDF)からアーカイブ。 2012年5月11日閲覧。
  24. ^ Jim Duffy (2012年5月11日). 「イリノイ州最大の医療システムがシスコを買収し、4,000万ドル規模のプライベートクラウドを構築」PC Advisor . 2012年5月11日閲覧。イーサネットファブリックでは、スパニングツリーに代わって最短パスブリッジングが採用される。
  25. ^ 「IEEE、新たなIEEE 802.1aq最短パスブリッジング規格を承認」Tech Power Up、2012年5月7日。 2012年5月11日閲覧。
  26. ^ Noormohammadpour, Mohammad; Raghavendra, Cauligi S. (2018). 「ポスターアブストラクト：データセンター間広域ネットワークにおける適応型ルーティングを用いたフロー完了時間の最小化」. IEEE INFOCOM 2018 - IEEE Con​​ference on Computer Communications Workshops (INFOCOM WKSHPS) . IEEE. pp.  1– 2. arXiv : 1802.09080 . doi : 10.1109/INFCOMW.2018.8406853 . ISBN 978-1-5386-5979-3。
  27. ^ ab Noormohammadpour, Mohammad; Raghavendra, Cauligi S. (2018). 「データセンタートラフィック制御：手法とトレードオフの理解」. IEEE Communications Surveys & Tutorials . 20 (2): 1492– 1525. arXiv : 1712.03530 . doi : 10.1109/COMST.2017.2782753 . ISSN  1553-877X.
  28. ^ 「フェイルオーバーと負荷分散」IBM . 2019年1月6日閲覧。
  29. ^ 「AIファクトリーのデータ取り込みにおけるトラフィック管理の最適化」F5, Inc. 2025年1月30日閲覧。
  30. ^ 「AIインタラクションの最適化、拡張、セキュリティ確保」F5, Inc. 2025年1月30日閲覧。
ウィキメディア コモンズには、負荷分散 (コンピューティング)に関連するメディアがあります。
  • Wayback Machineにおける、完全自動障害回復機能を備えた負荷分散用サーバールーティング(2023 年 3 月 29 日アーカイブ)