Load Balancer: Algorithmen und wann man sie einsetzt

1. Übersicht

Wenn dein System mehrere Backend-Instanzen hat, stellt sich immer die Frage: Wohin soll der neue Request gehen? Dieser Artikel erklärt häufig verwendete Load-Balancing-Algorithmen, wie sie in simuliertem Java-Code funktionieren, und die Kriterien für die Auswahl des richtigen Algorithmus für jeden Workload-Typ. Nach der Lektüre weißt du, wann Round Robin ausreichend ist und wann du Least Connections oder Consistent Hashing brauchst.

2. Was ist ein Load Balancer?

Ein Load Balancer (LB) ist eine Komponente zwischen Clients und einer Gruppe von Servern (Backend Pool), die Requests so verteilt, dass:

• Kein Server überlastet wird, während andere idle sind.
• Das System einen Ausfall eines Backend-Servers toleriert (Failover).
• Horizontale Skalierung (Hinzufügen/Entfernen von Instanzen) möglich ist, ohne dass der Client es bemerkt.

Ein LB kann Software sein (Nginx, HAProxy, Envoy), Hardware (F5) oder ein verwalteter Service (AWS ALB/NLB, GCP Load Balancer). Je nach Schicht arbeitet ein LB auf zwei Hauptebenen:

• Layer 4 (Transportschicht): Routing basierend auf IP/Port, liest HTTP-Inhalte nicht. Schnell, wenig Overhead.

• Layer 7 (Anwendungsschicht): Liest Header, Pfad, Cookie… ermöglicht intelligenteres Routing (z. B. Routing nach Pfad /api/orders), verbraucht aber mehr CPU.

Hinweis: Die falsche Schicht zu wählen ist ein häufiger Designfehler. Wenn du nach URL-Pfad routen oder Sticky Sessions auf Cookie-Basis brauchst, kann Layer 4 das nicht — du musst Layer 7 verwenden.

3. Häufig verwendete Load-Balancing-Algorithmen

3.1. Round Robin

Requests gehen nacheinander durch jeden Server in fester Reihenfolge und wiederholen sich vom Anfang, wenn die Liste zu Ende ist.

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 erhöht den Counter thread-sicher, % servers.size() bringt den Index in den gültigen Bereich. Mit 3 Servern [A, B, C] liefern aufeinanderfolgende Aufrufe von nextServer() Folgendes:

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

Round Robin ist einfach und erfordert keine Kenntnis des Serverstatus. Nachteil: Wenn Requests unterschiedlich schwer sind (ein Request dauert 1 ms, ein anderer 500 ms), werden Server, die schwere Requests verarbeiten, im Laufe der Zeit stärker belastet.

3.2. Weighted Round Robin

Jeder Server hat ein “Gewicht”, das seine Verarbeitungskapazität (CPU, RAM) widerspiegelt. Stärkere Server erhalten mehr Requests.

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();
            }
        }
    }
}

Dies ist der “smooth weighted round robin”-Algorithmus, den Nginx verwendet: Server mit hohem Gewicht werden häufiger ausgewählt, aber gleichmäßig verteilt, nicht hintereinander. Mit der Konfiguration {A: 5, B: 1, C: 1} ist die ungefähre Auswahlreihenfolge:

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

3.3. Least Connections

Wählt den Server mit den wenigsten aktiven Verbindungen. Geeignet, wenn die Request-Verarbeitungszeit stark variiert.

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() durchsucht die Map und nimmt den Server mit den wenigsten Verbindungen. onRequestStart/onRequestEnd müssen korrekt gepaart aufgerufen werden (z. B. in try/finally), um Datenverlust zu vermeiden.

Hinweis: Least Connections erfordert einen zustandsbehafteten LB — zusätzliche Synchronisierungskosten, wenn du mehrere LB-Instanzen parallel laufen hast. Round Robin ist vollständig zustandslos.

3.4. Least Response Time

Eine Variante von Least Connections, wählt den Server mit dem niedrigsten (Anzahl Verbindungen × durchschnittliche Antwortzeit). Komplexer, aber genauer, da es auch die Verarbeitungsverzögerung berücksichtigt.

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 wird typischerweise durch exponentiellen gleitenden Durchschnitt berechnet und nach jeder Response aktualisiert. Dieser Algorithmus eignet sich gut für Systeme mit einer Mischung aus schnellen APIs (Cache-Lookups) und langsamen APIs (Berichte, schwere Berechnungen).

3.5. IP Hash / Consistent Hashing

Verwendet, wenn Sticky Sessions benötigt werden — derselbe Client wird immer zu denselben Server geleitet (z. B. wenn der Server Sessions im RAM speichert oder lokale Caches hat).

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;
    }
}

Jeder Server wird als mehrere “Virtual Nodes” auf einem Hash-Ring (ring) verteilt, um eine gleichmäßigere Verteilung zu erreichen. serverFor findet den nächsten Punkt im Ring im Uhrzeigersinn für den Client-Key (normalerweise IP oder User-ID). Großer Vorteil: Wenn ein Server hinzugefügt/entfernt wird, werden nur wenige Keys neu zugeordnet — nicht das gesamte System durcheinander wie bei normalem Hash (hash(key) % n).

Ein schneller Test, um zu bestätigen, dass derselbe Key immer auf denselben Server führt:

@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 und Power of Two Choices

Random wählt einfach willkürlich — etwa so effektiv wie Round Robin bei großen Request-Mengen, aber ohne State zu halten. Power of Two Choices (P2C) verbessert dies: Wähle zufällig 2 Server, nimm dann den mit weniger Verbindungen. Dieser Algorithmus reduziert nachweislich die “Tail Latency” erheblich gegenüber reinem Random, ohne dass das gesamte Cluster wie bei Least Connections überwacht werden muss.

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 und Failover

Ein Auswahlalgorithmus macht nur Sinn, wenn der LB weiß, welcher Server “am Leben” ist. Health Checks haben normalerweise zwei Typen:

• Active Check: LB sendet periodisch Anfragen an einen Endpoint wie /health.

• Passive Check: LB markiert einen Server als “down”, wenn aufeinanderfolgende echte Requests Fehler/Timeouts erhalten.

Beispiel einer Active-Health-Check-Konfiguration mit Nginx:

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 bedeutet, dass der Server nach 3 aufeinanderfolgenden Fehlern für fail_timeout Sekunden aus dem Pool entfernt wird, dann wird ein neuer Versuch unternommen. Ohne Health Check sendet der LB Requests weiterhin an den toten Server, bis der Client einen Timeout erhält — ein furchtbares Erlebnis.

5. Vergleichstabelle: Wann man welchen Algorithmus einsetzt

Algorithmus	Wann geeignet	Wann vermeiden
Round Robin	Homogene Server, Requests mit ähnlicher Last (einfache REST-APIs)	Server mit unterschiedlicher Konfiguration, Requests mit unterschiedlicher Last
Weighted Round Robin	Cluster mit Servern unterschiedlicher Kapazität (schrittweise Migration zu neuen Instanzen)	Echtzeitreaktion auf aktuelle Last erforderlich
Least Connections	Requests mit großen Verarbeitungszeitunterschieden (Datei-Upload, Long-Polling)	System mit vielen LB-Instanzen, hohe Synchronisierungskosten für State
Least Response Time	Mix aus schnellen und langsamen APIs, Latenz-Optimierung erforderlich	Kleines System, unzureichende zuverlässige Response-Time-Daten
IP Hash / Consistent Hashing	Sticky Sessions, Cache Locality, Sharding nach Client erforderlich	Server skalieren häufig schnell up/down (obwohl Remap-Effekt geringer ist, gibt es noch Overhead)
Random / P2C	Sehr großes System, Overhead durch zentrale State-Überwachung vermeiden	Absolute gleichmäßige Verteilung in kurzer Zeit erforderlich

6. Häufige Fehler beim Load-Balancing-Design

• Round Robin für nicht-homogene Workloads verwenden: Einige Server erhalten nur schwere Requests, während andere idle sind — verursacht stille Lastunausgeglichenheit, schwer zu erkennen in aggregiertem Monitoring (durchschnittliche CPU sieht noch “normal” aus).

• Sticky Sessions über IP Hash verwenden, wenn Clients hinter gemeinsamen NAT/Proxy sind: Mehrere echte Clients werden zu einer IP zusammengefasst, was zu abnormal hoher Last auf einem Server führt. Verwende stattdessen Cookie-basierte Sticky Sessions auf Layer 7.

• Kein Health Check oder falscher Health-Check-Endpoint: /health gibt 200 OK zurück, aber es wird nicht überprüft, ob die Datenbankverbindung funktioniert — der Server ist “am Leben” laut LB, kann aber tatsächlich keine Requests verarbeiten.

• Connection Draining bei Scale-in ignorieren: Den Server sofort abschalten lässt laufende Requests fallen. Es ist notwendig, auf die Fertigstellung bestehender Verbindungen zu warten (Graceful Shutdown), bevor der Server aus dem Pool entfernt wird.

• Single Point of Failure im Load Balancer selbst: Wenn es nur eine LB-Instanz gibt, wird sie zum Ausfallpunkt des gesamten Systems. Benötige mindestens 2 LB-Instanzen mit DNS-Failover oder Virtual IP (keepalived).

7. Fazit

Ein Load Balancer ist nicht nur “Requests gleichmäßig verteilen” — die richtige Algorithmenwahl hängt von den Workload-Merkmalen ab: homogen oder nicht, Sticky Sessions erforderlich oder nicht, kann das System zentrale State-Überwachung leisten oder nicht. Round Robin und Weighted Round Robin eignen sich für die meisten einfachen Fälle; Least Connections und Least Response Time handhaben variable Workloads gut; Consistent Hashing löst das Problem von Sticky Sessions und Sharding robust, wenn sich der Cluster verändert. Wichtiger als der Algorithmus sind richtige Health Checks und Failover — das entscheidet über die echte Zuverlässigkeit des Systems.