ロードバランシングのアルゴリズム入門 - ラウンドロビンから最少コネクション・P2Cまで

1台のサーバーでさばける処理量には限界があります。アクセスが増えれば、サーバーを増やして負荷を分け合う（スケールアウトする）のが定石です。ですが「サーバーを増やす」だけでは不十分で、どのリクエストをどのサーバーに送るかを決める仕組みが要ります。それがロードバランシング（負荷分散）であり、その振り分けの判断ロジックが本記事で扱うアルゴリズムです。この記事では、L4とL7の違いから主要アルゴリズムの挙動、nginx・HAProxy・Envoyの既定、そしてヘルスチェックやスティッキーセッションといった周辺概念までを、初中級者向けに順を追って整理します。

負荷分散はなぜ必要か

ロードバランサ（LB）は、クライアントとバックエンドサーバー群のあいだに立ち、受け取ったリクエストを複数のサーバーへ振り分ける中継役です。狙いは大きく3つあります。

• スケールアウト: 台数を増やして処理能力を水平に伸ばす
• 可用性の確保: 1台が落ちても、残りのサーバーで処理を継続する
• 負荷の平準化: 特定のサーバーだけが過負荷になるのを防ぐ

構成をMermaidで示すと次のようになります。クライアントはLBの1つのアドレスにアクセスし、LBが背後の複数サーバーへ配分します。

L4とL7 - どの層で振り分けるか

アルゴリズムの前に、ロードバランサがどの層で動くかを押さえます。ここはOSI参照モデルのレイヤに対応します。

L4（トランスポート層）ロードバランシングは、送信元・宛先のIPアドレスとTCP/UDPのポート番号だけを見て振り分けます。パケットの中身（アプリケーションデータ）は覗きません。処理がシンプルで高速、オーバーヘッドが小さいのが利点です。TCPの接続確立の仕組みはTCP/UDPと3ウェイハンドシェイクで解説しています。

L7（アプリケーション層）ロードバランシングは、HTTPヘッダ・URLのパス・Cookieなど、アプリケーションレベルの情報まで見て判断します。「/api で始まるパスはAPIサーバー群へ」「特定Cookieを持つリクエストは同じサーバーへ」といった、内容に応じた賢い振り分け（コンテンツスイッチング）ができます。そのぶんCPU負荷はL4より高くなります。

一言でいえば、L4は速くて単純、L7は柔軟で高機能です。両者の差は「パケットの中身をどこまで見るか」というデータの可視性にあります。

主要アルゴリズム

ここからが本題です。代表的な振り分けアルゴリズムを、挙動を正確に確認しながら一つずつ見ていきます。

ラウンドロビン（Round Robin）

サーバーを順番に一巡させて割り当てる、最も基本的な方式です。サーバー1、2、3、1、2、3……と機械的に回します。実装が単純で、各サーバーの性能が均一なら十分に機能します。弱点は、各サーバーの現在の負荷や処理中のリクエスト数を一切考慮しない点です。処理の重いリクエストが特定のサーバーに偏ると、負荷が不均衡になり得ます。

加重ラウンドロビン（Weighted Round Robin）

サーバーごとに重み（weight）を設定し、重みに比例した頻度で割り当てます。「性能の高いサーバーには多く、低いサーバーには少なく」配分でき、サーバーのスペックがまちまちな環境で有効です。ただし、動的な負荷ではなく静的な重みに基づく点はラウンドロビンと同じです。

最少コネクション（Least Connections）

現在アクティブな接続数が最も少ないサーバーに新規リクエストを送ります。ラウンドロビンと違い、実際の負荷状況を見て判断するため、リクエストの処理時間にばらつきがある場合（長く接続が続くセッションなど）に効果的です。加重最少コネクション（Weighted Least Connections）は、これに重みを組み合わせ、接続数を重みで割った値が最小のサーバーを選びます。性能差と現在の負荷を同時に考慮できます。

最短応答時間（Least Response Time / Least Time）

アクティブ接続数に加えて平均応答時間（レイテンシ）も考慮し、両方の観点で最も余裕のあるサーバーを選ぶ方式です。接続数だけでなく実際の速さを見るため、より実態に即した配分になります。なお後述するとおり、この方式は実装によって提供状況が異なります。

ハッシュ系（IPハッシュ・コンシステントハッシュ）

IPハッシュは、クライアントのIPアドレスをハッシュして割り当て先を決めます。同じクライアントは（サーバー構成が変わらない限り）常に同じサーバーへ届くため、後述のスティッキーセッションの一手段になります。素朴なハッシュはサーバーの増減で割り当てがほぼ総崩れになるため、実務ではコンシステントハッシュ法を使い、ノード増減時の再配置を最小限に抑えます。キャッシュサーバーの振り分けなどで重要な考え方です。

Power of Two Choices（P2C、ランダム2択）

全サーバーからランダムに2台だけ選び、そのうち負荷（接続数など）の低いほうへ送る方式です。全台をスキャンする最少コネクションと違い、選択コストが定数時間で済むうえ、ランダムな純粋な振り分けより負荷の偏りが劇的に小さくなることが知られています。「群れの挙動（herding）」に強く、サーバーの増減にも耐性があるため、近年のプロキシで広く採用されています。最も混んでいるサーバーが新規リクエストを引き当てても、もう1台のほうが選ばれやすいため、過負荷サーバーを避けやすいのが肝です。

Maglev

MaglevはGoogleのソフトウェアロードバランサ（NSDI 2016で発表）が用いるルックアップテーブル方式です。均等な分散と、障害時にできるだけ既存の割り当てを崩さない（最小攪乱で接続を維持する）ことを両立するよう設計されており、L4の大規模分散に向きます。

主要なアルゴリズムを整理すると次のとおりです。

nginx / HAProxy / Envoy の既定と対応

代表的な実装が何を既定にし、何をサポートするかを、公式ドキュメントで確認できた範囲で整理します。バージョンで変わる点があるため、既定は必ず利用中のバージョンで確認してください。

nginxのupstreamは、既定がラウンドロビンです（有効化ディレクティブは無く、無指定なら重み付きラウンドロビン）。オープンソース版で least_conn（最少コネクション）、ip_hash、hash（ketama でコンシステントハッシュ）、random [two]（ランダム/P2C）が使えます。least_time（最短応答時間）は、公式ドキュメントによると1.31.0より前は商用版（NGINX Plus）専用でした。設定例は次のとおりです。

upstream backend {
    least_conn;                 # 最少コネクションを指定（無指定ならラウンドロビン）
    server 10.0.0.1:8080 weight=3;   # 重み付き
    server 10.0.0.2:8080;
    server 10.0.0.3:8080 backup;     # 予備。他が落ちたときだけ使う
}
 
server {
    location / {
        proxy_pass http://backend;
    }
}

HAProxyは balance ディレクティブで指定します。既定のアルゴリズムはバージョン依存で変わっています。公式ドキュメントによると、3.2以前は roundrobin、3.3以降は random（ランダム2択でP2Cの考え方に基づく）が既定です。leastconn は接続数が最少のサーバーを選び、長いセッションに推奨されます。

backend web_servers
    balance roundrobin
    server web1 10.0.0.1:8080 weight 3 check
    server web2 10.0.0.2:8080 check
    server web3 10.0.0.3:8080 check

check は後述のヘルスチェックを有効にする指定です。

Envoyは、既定がラウンドロビンです。LEAST_REQUEST（最少リクエスト）は、重みが等しい場合にP2C（既定でランダム2台）で最少アクティブリクエストのホストを選びます。ほかに RING_HASH や MAGLEV といったハッシュ系もサポートします。

周辺概念: ヘルスチェック・スティッキー・ドレイン

アルゴリズムと同じくらい、運用では次の3つが重要です。

ヘルスチェックは、各サーバーが正常かをLBが定期的に確認する仕組みです。異常なサーバーを振り分け対象から外し、復帰したら戻します。HTTPでヘルスチェック用エンドポイントを叩き、200や503などのステータスコードで健全性を判定するのが典型です。これがないと、落ちたサーバーへリクエストを送り続けてしまいます。

スティッキーセッション（セッションアフィニティ）は、同じクライアントのリクエストを毎回同じサーバーへ届ける仕組みです。サーバーのメモリ上にセッション状態を持つ場合や、WebSocketなどの永続接続で有効です。Cookieやクライアントのハッシュで実現します。ただし特定サーバーへ固定するぶん負荷が偏りやすく、そのサーバーが落ちるとセッションが切れます。可能ならセッションを外部ストア（Redisなど）に逃がし、ステートレスにするのが本筋です。

コネクションドレイン（グレースフルシャットダウン）は、サーバーを停止・入れ替えする際に、新規リクエストの振り分けは止めつつ、処理中のリクエストは完了まで待つ仕組みです。デプロイやスケールインで既存接続を強制切断しないために欠かせません。

実務での選び方

最初に迷ったら、まずはラウンドロビンから始めるのが無難です。サーバー性能が均一で処理時間が安定していれば、これで十分に機能します。そこから状況に応じて調整します。

• サーバーのスペックに差がある: 加重ラウンドロビン / 加重最少コネクション
• リクエストの処理時間にばらつきが大きい、長い接続がある: 最少コネクション
• レイテンシを重視したい: 最短応答時間
• 大規模で、サーバーの増減が頻繁: Power of Two Choices（ランダム2択）
• 同一クライアントを同一サーバーへ寄せたい: ハッシュ系 + コンシステントハッシュ

過負荷を根本から防ぐには、負荷分散だけでなくレート制限で流入自体を制御する、CDNやエッジキャッシュで origin への到達数を減らす、といった手段を組み合わせるのが定石です。

まとめ

ロードバランシングは、スケールアウト・可用性・負荷平準化を支える基盤技術です。要点を振り返ります。

• L4は速くて単純、L7はHTTPの中身まで見て柔軟に振り分ける
• ラウンドロビン系は静的、最少コネクション/最短応答時間は現在の負荷を見る、P2Cはランダム2択で軽く偏りを抑える
• nginxの既定はラウンドロビン、HAProxyの既定はバージョン依存（3.2以前 roundrobin、3.3以降 random）、Envoyの既定はラウンドロビン
• ヘルスチェック・スティッキーセッション・コネクションドレインは、アルゴリズムと同じくらい運用で効く
• まずラウンドロビンで始め、負荷特性に応じて選び直す

「どのアルゴリズムが正解か」は環境次第です。自分のトラフィックの性質（処理時間のばらつき、接続の長さ、サーバーの均一性）を見極めることが、正しい選択への近道になります。

参考リンク

• Module ngx_http_upstream_module（nginx公式）
• Using nginx as HTTP load balancer（nginx公式）
• Backends / balance algorithms（HAProxy公式）
• Supported load balancers（Envoy公式）
• What Is Layer 4 Load Balancing?（F5）
• Maglev: A Fast and Reliable Software Network Load Balancer（USENIX NSDI 2016）