JA
FrançaisDeutschEnglishPortuguêsEspañolTiếng Việt한국어日本語简体中文
ホーム / アーキテクチャ・設計 / System Design

ロードバランサー：アルゴリズムと使い分け

Cris The Dev · 2026/10/05 · 8 分で読めます · 117

1. 概要

システムに複数の backend instance がある場合、いつも同じ問題が生じます：新しいリクエストはどの instance に送るべきか。この記事では、よく見かけるロードバランシングアルゴリズム、Java でのシミュレーション実装、そして各ワークロードに適したアルゴリズムの選択基準について説明します。読み終わったら、Round Robin で十分な場合と、Least Connections や Consistent Hashing が必要な場合の判断ができるようになります。

2. ロードバランサーとは

ロードバランサー（LB）は client と backend server のグループの間に位置し、以下を実現するためにリクエストを分散させる責務を持ちます：

  • どの server も過負荷にならず、他の server が遊んでいる状態を避ける。
  • backend が落ちても system 全体が停止しない（failover）。
  • client に知られないまま scale out/in できる。

LB はソフトウェア（Nginx、HAProxy、Envoy）、ハードウェア（F5）、またはマネージド service（AWS ALB/NLB、GCP Load Balancer）で実装できます。動作レイヤーで LB は主に 2 つに分かれます：

  • Layer 4（トランスポート層）：IP/port に基づいてルーティング。HTTP 内容は読まない。高速で overhead が少ない。
  • Layer 7（アプリケーション層）：header、path、cookie などを読み込むので、より賢いルーティングが可能（例：/api/orders という path に基づいてルーティング）。ただし CPU 処理が増える。

注意： レイヤー選びを間違えるのは一般的な設計ミスです。URL path や cookie ベースの sticky session が必要な場合、Layer 4 ではできません — Layer 7 が必須です。

3. 一般的なロードバランシングアルゴリズム

3.1. Round Robin

リクエストが順に各 server を回ります。リストの最後に達したら最初に戻ります。

public class RoundRobinBalancer {

    private final List<String> servers;
    private final AtomicInteger index = new AtomicInteger(0);

    public RoundRobinBalancer(List<String> servers) {
        this.servers = servers;
    }

    public String nextServer() {
        int i = index.getAndIncrement() % servers.size();
        return servers.get(Math.abs(i));
    }
}

getAndIncrement は複数 thread 間で安全にカウンタを増加させ、% servers.size() で index を有効範囲に収めます。3 つの server [A, B, C] がある場合、連続して nextServer() を呼び出すと：

A, B, C, A, B, C, ...

Round Robin はシンプルで server の状態を把握する必要がありません。欠点：リクエストの重さがばらばら（1 つは 1ms、別の 1 つは 500ms）な場合、重い request を処理する server が時間とともに overload しやすくなります。

3.2. Weighted Round Robin

各 server に「重み」があり、処理能力（CPU、RAM）を反映します。強い server がより多くの request を受け取ります。

public class WeightedRoundRobinBalancer {

    private record WeightedServer(String name, int weight) {}

    private final List<WeightedServer> servers;
    private int currentIndex = -1;
    private int currentWeight = 0;

    public WeightedRoundRobinBalancer(Map<String, Integer> weightedServers) {
        this.servers = weightedServers.entrySet().stream()
            .map(e -> new WeightedServer(e.getKey(), e.getValue()))
            .toList();
    }

    public synchronized String nextServer() {
        int maxWeight = servers.stream().mapToInt(WeightedServer::weight).max().orElse(1);
        int gcdWeight = servers.stream().mapToInt(WeightedServer::weight)
            .reduce((a, b) -> java.math.BigInteger.valueOf(a).gcd(java.math.BigInteger.valueOf(b)).intValue())
            .orElse(1);

        while (true) {
            currentIndex = (currentIndex + 1) % servers.size();
            if (currentIndex == 0) {
                currentWeight -= gcdWeight;
                if (currentWeight <= 0) {
                    currentWeight = maxWeight;
                }
            }
            if (servers.get(currentIndex).weight() >= currentWeight) {
                return servers.get(currentIndex).name();
            }
        }
    }
}

これは Nginx で使用される「smooth weighted round robin」アルゴリズムです。weight が高い server はより頻繁に選ばれますが、連続して選ばれることはなく分散します。{A: 5, B: 1, C: 1} の設定では、選択順序はおおよそ：

A, A, B, A, C, A, A

3.3. Least Connections

現在処理中の connection がもっとも少ない server を選びます。リクエストの処理時間にばらつきが大きい場合に適しています。

public class LeastConnectionsBalancer {

    private final Map<String, AtomicInteger> activeConnections = new ConcurrentHashMap<>();

    public LeastConnectionsBalancer(List<String> servers) {
        servers.forEach(s -> activeConnections.put(s, new AtomicInteger(0)));
    }

    public String nextServer() {
        return activeConnections.entrySet().stream()
            .min(Comparator.comparingInt(e -> e.getValue().get()))
            .map(Map.Entry::getKey)
            .orElseThrow();
    }

    public void onRequestStart(String server) {
        activeConnections.get(server).incrementAndGet();
    }

    public void onRequestEnd(String server) {
        activeConnections.get(server).decrementAndGet();
    }
}

nextServer() は map をスキャンして connection 数が最少の server を取得します。onRequestStart/onRequestEnd は必ずペアで呼び出される必要があります（例えば try/finally の中で）。そうしないとカウント数が狂います。

注意： Least Connections は LB が状態を追跡する必要があり、複数の LB instance が並行稼働する場合、状態同期のコストが高くなります。Round Robin は完全にステートレスです。

3.4. Least Response Time

Least Connections の変種で、(connection 数 × 平均応答時間) が最小の server を選びます。Least Connections より複雑ですが、応答遅延も考慮するため、実際の負荷をより正確に反映します。

public record ServerStats(String name, int activeConnections, double avgResponseTimeMs) {
    double score() {
        return activeConnections * avgResponseTimeMs;
    }
}

public String pickFastest(List<ServerStats> stats) {
    return stats.stream()
        .min(Comparator.comparingDouble(ServerStats::score))
        .map(ServerStats::name)
        .orElseThrow();
}

avgResponseTimeMs は通常、exponential moving average で計算され、response が返るたびに更新されます。このアルゴリズムは API が速い（キャッシュ lookup）ものと遅い（レポート、重い計算）ものが混在するシステムに適しています。

3.5. IP Hash / Consistent Hashing

sticky session が必要な場合に使用します。つまり同じ client は常に同じ server にルーティングされるべき場合です（例：server が session を in-memory で保持する、またはローカルキャッシュがある）。

public class ConsistentHashBalancer {

    private final SortedMap<Long, String> ring = new TreeMap<>();
    private static final int VIRTUAL_NODES = 100;

    public ConsistentHashBalancer(List<String> servers) {
        for (String server : servers) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                ring.put(hash(server + "#" + i), server);
            }
        }
    }

    public String serverFor(String clientKey) {
        long hash = hash(clientKey);
        SortedMap<Long, String> tail = ring.tailMap(hash);
        Long nodeKey = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeKey);
    }

    private long hash(String input) {
        return input.hashCode() & 0xFFFFFFFFL;
    }
}

各 server は複数の「virtual node」として hash ring 上に分散されます。これにより分散がより均等になります。serverFor はクライアント key（通常は IP または user ID）に対応する ring 上の最も近いポイント（時計回り）を見つけます。大きな利点：server を追加/削除するとき、通常の hash（hash(key) % n）と異なり、全 key を再割り当てするのではなく、小さな部分だけが再割り当てされます。

同じ key が常に同じ server にルーティングされることを確認するクイックテスト：

@Test
void sameClientKey_alwaysRoutesToSameServer() {
    ConsistentHashBalancer balancer =
        new ConsistentHashBalancer(List.of("server-1", "server-2", "server-3"));

    String first = balancer.serverFor("user-42");
    String second = balancer.serverFor("user-42");

    assertThat(first).isEqualTo(second);
}

3.6. Random と Power of Two Choices

Random はシンプルにランダムに選択します。リクエスト数が大きいと Round Robin に近い効果を得られますが、state を保持する必要がありません。Power of Two Choices（P2C）はこれを改善します：ランダムに 2 つの server を選び、その 2 つの中で connection 数が少ないものを選びます。このアルゴリズムは、cluster 全体をトラッキングする Least Connections と比べ、「tail latency」を著しく減らすことが理論的に証明されており、かつ state 追跡の overhead がありません。

public String pickWithPowerOfTwo(List<String> servers, Map<String, Integer> loadMap, Random random) {
    String candidate1 = servers.get(random.nextInt(servers.size()));
    String candidate2 = servers.get(random.nextInt(servers.size()));
    return loadMap.get(candidate1) <= loadMap.get(candidate2) ? candidate1 : candidate2;
}

4. Health check と failover

server を選ぶアルゴリズムは、LB が「生きている」server を把握していてこそ意味があります。Health check は大きく 2 種類あります：

  • Active check：LB が定期的に /health といったエンドポイントに request を送る。
  • Passive check：実際の request でエラー/timeout が連続すると、LB は server を「down」と判定する。

Nginx で active health check を設定する例：

upstream backend_pool {
  server 10.0.0.1:8080 max_fails=3 fail_timeout=30s;
  server 10.0.0.2:8080 max_fails=3 fail_timeout=30s;
}

max_fails=3 は連続 3 回の失敗後、fail_timeout 秒の間 server をプールから除外し、その後再試行することを意味します。Health check がないと、LB は死んだ server にリクエストを送り続けます。client が timeout するまで — 非常に悪い体験になります。

5. 比較表：どのアルゴリズムをいつ使うか

アルゴリズム 適している場合 避けるべき場合
Round Robin Server が同じ性能、リクエストの重さが同等（シンプルな REST API） Server のスペックが異なる、リクエストの重さがばらばら
Weighted Round Robin Cluster に異なるスペックの server がある（新 instance への段階的な移行） 実時間の負荷に応じた反応が必要
Least Connections リクエストの処理時間がばらつく（ファイルアップロード、long-polling） 複数の LB instance が稼働している、状態同期のコストが高い
Least Response Time 高速 API と遅い API が混在、全体的な latency を最適化したい System が小さい、安定した応答時間データが不足
IP Hash / Consistent Hashing Sticky session が必要、cache locality、client 単位の sharding Server が頻繁に scale up/down する（remap の overhead が減ってはいるが、なくはない）
Random / P2C 非常に大規模な system、集約的な state tracking overhead を避けたい 短時間での完全に均等な分散が必須

6. ロードバランシング設計でよくあるミス

  • 不均一なワークロードに Round Robin を使う：一部の server が重い request ばかり受け取り、他の server は遊んでいる — 負荷が偏っているが、平均 CPU のような集計メトリクスでは「正常」に見えるため検出が難しい。
  • NAT/proxy 共有下の client に IP Hash を使った sticky session：複数の実クライアントが 1 つの IP にまとめられ、結果として 1 つの server が異常な負荷を受ける。Layer 7 の cookie ベース sticky session を使うべき。
  • Health check がない、または endpoint が不正確：/health が 200 OK を返すが database への接続をチェックしていない — LB からは「生きている」が実際には request を処理できない。
  • Scale-in 時に connection draining を無視：server を即座にシャットダウンすると処理中の request が失われる。現在の connection が完了するのを待つ（graceful shutdown）べき。
  • LB 自体が single point of failure：LB が 1 台だけだと、LB 障害が system 全体を停止させる。最低 2 台の LB に DNS failover または virtual IP（keepalived）が必要。

7. まとめ

ロードバランサーは単なる「リクエストを均等に分散させる」以上のものです — 正しいアルゴリズムの選択は workload の特性に依存します：uniform か否か、sticky session が必要か、system が集約的な state 追跡を可能とするか。Round Robin と Weighted Round Robin はシンプルなケースに適切；Least Connections と Least Response Time は処理時間が変動するワークロードを上手く扱います；Consistent Hashing は sticky session と sharding の問題を、cluster の変更時も堅牢に解決します。アルゴリズム選択と同じくらい、健全な health check と failover こそが system の信頼性を本当に左右するのです。

system-designload-balancerscalabilitydistributed-systemsbackend
著者のアプリAlterTurn photos into postage stamps, collected in a stamp bookiOS · Android

同じトピックの記事