Load balancer : algorithmes et quand les utiliser

1. Vue d’ensemble

Quand votre système a plusieurs instances en arrière-plan, la question est toujours : vers quelle instance la nouvelle requête doit-elle aller ? Cet article explique les algorithmes de load balancing courants, comment ils fonctionnent à travers du code Java, et les critères de sélection d’un algorithme adapté à chaque type de workload. Après la lecture, vous saurez quand Round Robin suffit, quand vous avez besoin de Least Connections ou de Consistent Hashing.

2. Qu’est-ce qu’un load balancer

Un load balancer (LB) est un composant situé entre les clients et un groupe de serveurs (backend pool), dont la mission est de distribuer les requêtes pour que :

Aucun serveur ne soit surchargé pendant que d’autres sont inactifs.
Le système tolère qu’un backend tombe en panne (failover).
On peut scalabiliser horizontalement (ajouter/supprimer des instances) sans que les clients le sachent.

Un LB peut être un logiciel (Nginx, HAProxy, Envoy), du matériel (F5), ou un service géré (AWS ALB/NLB, GCP Load Balancer). Au niveau de la couche OSI où il opère, un LB se divise en deux catégories principales :

Couche 4 (transport layer) : achemine en fonction de l’IP/port, ne lit pas le contenu HTTP. Rapide, peu de surcharge.
Couche 7 (application layer) : peut lire les headers, le path, les cookies… donc achemine de manière plus intelligente (par exemple router selon le path /api/orders) mais consomme plus de CPU.

Remarque : Choisir la mauvaise couche est une erreur de conception courante. Si vous avez besoin de router selon le URL path ou de sticky session basée sur les cookies, la couche 4 ne peut pas le faire — il faut utiliser la couche 7.

3. Algorithmes de load balancing courants

3.1. Round Robin

Les requêtes passent successivement par chaque serveur dans un ordre fixe, en boucle à partir du début quand la liste est épuisée.

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 incrémente le compteur de façon thread-safe, % servers.size() ramène l’indice dans la plage valide. Avec 3 serveurs [A, B, C], une série d’appels à nextServer() produit :

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

Round Robin est simple et ne nécessite pas de connaître l’état du serveur. Inconvénient : si les requêtes ont des durées très différentes (une requête prend 1ms, une autre 500ms), le serveur traitant les requêtes lourdes tend à être surchargé avec le temps.

3.2. Weighted Round Robin

Chaque serveur a un “poids” qui reflète sa capacité de traitement (CPU, RAM). Un serveur plus puissant reçoit plus de requêtes.

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

C’est l’algorithme “smooth weighted round robin” utilisé dans Nginx : un serveur avec un poids élevé est choisi plus souvent mais reste bien distribué, sans sélections consécutives. Avec la configuration {A: 5, B: 1, C: 1}, la séquence de sélection est approximativement :

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

3.3. Least Connections

Sélectionne le serveur ayant le moins de connexions en traitement. Adapté quand le temps de traitement des requêtes varie beaucoup.

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() parcourt la map et prend le serveur avec le nombre minimal de connexions. onRequestStart/onRequestEnd doivent être appelés en paire (par exemple dans un bloc try/finally) pour que les compteurs ne deviennent pas incohérents.

Remarque : Least Connections nécessite que le LB maintienne l’état (stateful) — ça représente un coût de synchronisation supplémentaire si vous avez plusieurs instances de LB fonctionnant en parallèle. Round Robin est complètement stateless.

3.4. Least Response Time

Une variante de Least Connections qui choisit le serveur ayant le score (nombre de connexions × temps de réponse moyen) le plus bas. C’est plus complexe mais reflète mieux la charge réelle en tenant compte de la latence de traitement.

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 est généralement calculée avec une moyenne mobile exponentielle, mise à jour après chaque réponse reçue. Cet algorithme est excellent pour les systèmes mélangeant des API rapides (cache lookups) et des API lentes (rapports, calculs lourds).

3.5. IP Hash / Consistent Hashing

À utiliser quand vous avez besoin d’une sticky session — un même client est toujours routé vers le même serveur (par exemple si le serveur garde la session en mémoire, ou du cache local).

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

Chaque serveur est distribué sur plusieurs “nœuds virtuels” sur un anneau de hash (ring) pour une distribution plus uniforme. serverFor trouve le point le plus proche sur l’anneau en direction des aiguilles d’une montre correspondant à la clé du client (généralement son IP ou user ID). Grand avantage : quand vous ajoutez/supprimez un serveur, seule une petite fraction des clés est remappée — pas de réorganisation complète comme avec un hash standard (hash(key) % n).

Test rapide pour vérifier qu’une même clé client route toujours vers le même serveur :

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

Random choisit simplement un serveur au hasard — c’est presque aussi efficace que Round Robin avec un grand nombre de requêtes mais sans besoin de maintenir un état. Power of Two Choices (P2C) l’améliore : on choisit 2 serveurs au hasard, puis on prend celui ayant le moins de connexions parmi ces 2. Cet algorithme réduit significativement la “tail latency” comparé au random pur, sans avoir besoin de suivre le cluster entier comme avec Least Connections.

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 et failover

L’algorithme de sélection de serveur n’a de sens que si le LB sait quel serveur est “vivant”. Les health checks se répartissent en deux catégories :

Active check : le LB envoie régulièrement une requête vers un endpoint comme /health.
Passive check : le LB marque un serveur comme “down” après avoir reçu consécutivement des erreurs/timeouts sur des requêtes réelles.

Exemple de configuration de health check actif avec 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 signifie qu’après 3 échecs consécutifs, le serveur est retiré du pool pour fail_timeout secondes puis retesté. Sans health check, le LB continue à envoyer des requêtes vers un serveur mort jusqu’à ce que le client timeout — l’expérience est très mauvaise.

5. Tableau comparatif : quand utiliser quel algorithme

Algorithme	Quand c’est adapté	Quand à éviter
Round Robin	Serveurs homogènes, requêtes de poids équivalent (simple API REST)	Serveurs avec configurations différentes, requêtes de poids très variable
Weighted Round Robin	Cluster avec serveurs de capacité différente (migration progressive vers une nouvelle instance)	Besoin de réagir à la charge réelle instantanée
Least Connections	Requêtes avec temps de traitement très variables (upload de fichiers, long-polling)	Système avec plusieurs instances de LB, coût de synchronisation d’état élevé
Least Response Time	Mix d’API rapides/lentes, optimiser la latence globale	Petit système, pas assez de données pour mesurer les temps de réponse de façon fiable
IP Hash / Consistent Hashing	Besoin de sticky session, cache locality, sharding par client	Serveurs scaled up/down très régulièrement (bien que le remapping soit réduit, il y a toujours un overhead)
Random / P2C	Très grand système, vouloir éviter l’overhead du suivi d’état centralisé	Besoin de garantir une distribution parfaitement uniforme sur une courte période

6. Erreurs courantes lors du design du load balancing

Utiliser Round Robin pour une workload non uniforme : quelques serveurs reçoivent toutes les requêtes lourdes tandis que d’autres sont inactifs — provoque un déséquilibre de charge silencieux, difficile à détecter avec le monitoring global (CPU moyen semble toujours “normal”).
Sticky session par IP Hash quand le client est derrière un NAT/proxy partagé : plusieurs vrais clients sont agrégés sous une même IP, ce qui envoie une charge anormale sur un serveur. Préférer la sticky session basée sur les cookies en couche 7 à la place du IP Hash dans ce cas.
Pas de health check ou health check sur le mauvais endpoint : /health retourne 200 OK mais ne vérifie pas la connexion à la base de données — le serveur semble “vivant” au LB mais ne peut pas traiter les requêtes.
Oublier le connection draining lors du scale-in : arrêter un serveur immédiatement perd les requêtes en cours de traitement. Il faut attendre que les connexions actuelles se terminent (graceful shutdown) avant de retirer le serveur du pool.
Single point of failure au niveau du LB lui-même : s’il n’y a qu’une instance de LB, elle devient le point faible de tout le système. Il faut au minimum 2 instances de LB avec failover DNS ou une adresse IP virtuelle (keepalived).

7. Conclusion

Un load balancer n’est pas juste “quelque chose qui répartit les requêtes équitablement” — choisir le bon algorithme dépend des caractéristiques de votre workload : uniforme ou pas, besoin de sticky session ou pas, le système a-t-il la capacité de suivre l’état de manière centralisée ou pas. Round Robin et Weighted Round Robin conviennent à la plupart des cas simples ; Least Connections et Least Response Time gèrent bien les workloads variables ; Consistent Hashing résout les problèmes de sticky session et sharding de manière robuste quand le cluster change. Plus important que l’algorithme, les health checks et failovers correctement configurés sont ce qui détermine la véritable fiabilité du système.