Répartition de charge et gestion de la surcharge

Servir des millions de requêtes par seconde interdit de tout confier à une seule machine : même une hypothétique super-machine resterait limitée par la physique du réseau — la vitesse de la lumière dans la fibre fixe une borne supérieure à la rapidité de service en fonction de la distance — et constituerait surtout un point unique de défaillance (single point of failure). La répartition de charge (load balancing) consiste à décider, parmi les très nombreuses machines, laquelle servira une requête donnée. Google attaque le problème à plusieurs niveaux : à la périphérie (frontend), entre datacenters, puis à l'intérieur d'un datacenter — et, comme la perfection n'existe jamais dans un système distribué, protège enfin chaque tâche individuelle contre la surcharge (overload). Ce chapitre suit ce trajet du paquet, de la résolution DNS jusqu'au délestage gracieux des requêtes en excès.

Pourquoi répartir, et à quel niveau

Il n'y a pas de répartition « optimale » unique : l'optimum dépend du niveau hiérarchique auquel on raisonne (global ou local), du niveau technique (matériel ou logiciel) et de la nature du trafic. Deux scénarios canoniques l'illustrent. Une requête de recherche veut avant tout de la latence faible : on l'envoie au datacenter le plus proche en temps d'aller-retour (round-trip time, RTT). Un envoi de vidéo, lui, vise le débit (throughput) : on le route éventuellement vers un lien sous-utilisé, quitte à sacrifier la latence. Au niveau local, à l'intérieur d'un bâtiment, on suppose au contraire toutes les machines à égale distance de l'utilisateur et sur le même réseau ; l'objectif devient alors l'utilisation optimale des ressources et la protection d'un serveur isolé contre la surcharge.

      Utilisateur
          │
          ▼
   [1] DNS  ──────────────────►  choisit un datacenter (global, RTT, capacité)
          │
          ▼
   [2] VIP + balanceur réseau ─►  choisit une machine derrière l'adresse virtuelle
          │
          ▼
   [3] Datacenter (RPC) ───────►  le client choisit une tâche backend (sous-ensemble, politique)
          │
          ▼
   [4] Tâche backend ──────────►  protection locale : throttling, criticité, délestage

La maxime tient en peu de mots — « répartir tôt, répartir souvent » — mais la difficulté est dans les détails. Pour fixer les idées, on raisonne sur des requêtes HTTP au-dessus de TCP ; les services sans état (comme le DNS sur UDP) diffèrent un peu, mais l'essentiel des mécanismes s'y applique aussi.

Répartir au frontend : DNS puis adresses virtuelles

La répartition par DNS

Avant même d'émettre sa requête HTTP, le client doit souvent résoudre une adresse IP : c'est la première couche de répartition. La solution la plus simple renvoie plusieurs enregistrements A ou AAAA, et laisse le client en choisir un au hasard. Trivial à implémenter, ce procédé pose pourtant plusieurs problèmes.

D'abord, il offre très peu de contrôle sur le client : les enregistrements sont tirés aléatoirement et attirent un trafic à peu près égal. En théorie, les enregistrements SRV permettraient poids et priorités, mais ils ne sont pas adoptés pour HTTP. Ensuite, le client ne sait généralement pas déterminer l'adresse la plus proche ; on peut atténuer cela par une adresse anycast pour les serveurs de noms faisant autorité, en s'appuyant sur le fait que la requête DNS s'écoule vers l'adresse la plus proche.

Le vrai obstacle est structurel : l'utilisateur final dialogue rarement directement avec le serveur faisant autorité. Un résolveur récursif s'interpose, proxant les requêtes et offrant une couche de cache. Ce « passeur » a trois implications majeures :

L'extension EDNS0 atténue le premier point en glissant le sous-réseau du client dans la requête : le serveur faisant autorité répond alors de façon optimale du point de vue de l'utilisateur, et non du résolveur ; les plus gros résolveurs (OpenDNS, Google) la supportent déjà. Pour le reste, Google analyse en continu le trafic afin d'estimer la taille de la base d'utilisateurs derrière chaque résolveur et sa distribution géographique, et intègre le serveur DNS faisant autorité aux systèmes de contrôle globaux qui suivent trafic, capacité et état de l'infrastructure : la « meilleure localisation » n'est pas seulement la plus proche, c'est une localisation proche dont le datacenter a la capacité et la santé suffisantes.

La répartition à l'adresse IP virtuelle (VIP)

Une adresse IP virtuelle (virtual IP, VIP) n'est attachée à aucune interface réseau précise : elle est partagée entre de nombreuses machines, tout en restant pour l'utilisateur une IP unique et ordinaire. On masque ainsi les détails d'implémentation (nombre de machines, maintenance, ajout de capacité) sans que l'utilisateur s'en aperçoive. La pièce maîtresse est le balanceur de charge réseau (network load balancer) : il reçoit les paquets et les redirige vers l'une des machines (backends) derrière la VIP.

Comment choisir le backend ? Préférer le moins chargé semble idéal, mais s'effondre vite avec les protocoles à état (stateful) qui exigent que tous les paquets d'une connexion atterrissent sur le même backend : le balanceur devrait alors mémoriser chaque connexion. L'alternative est de calculer un identifiant de connexion à partir du paquet (par exemple id(packet) mod N, où N est le nombre de backends). Hélas, si un backend tombe, N devient N-1 et presque tous les paquets sont remappés vers un autre backend, forçant la réinitialisation de quasiment toutes les connexions. La parade est le hachage cohérent (consistent hashing), proposé en 1997 : un mappage qui reste relativement stable quand on ajoute ou retire des backends, minimisant la casse. En pratique, on utilise un simple suivi de connexions, avec repli sur le hachage cohérent sous pression (par exemple lors d'une attaque par déni de service).

Reste à savoir comment le balanceur transmet le paquet au backend choisi. Trois techniques :

Une fois le paquet arrivé dans le datacenter, on évite la fragmentation due à l'encapsulation en employant une MTU plus large à l'intérieur — au prix d'un réseau capable de gérer de grandes unités de données.

Répartir dans le datacenter

À l'intérieur du datacenter, on raisonne au niveau applicatif : un flux de requêtes arrive à un rythme qui n'excède pas (ou seulement très brièvement) les ressources disponibles. Les services sont faits de tâches backend (backend tasks) homogènes et interchangeables — au moins trois pour ne pas perdre 50 % ou plus de capacité à la chute d'une machine, parfois plus de 10 000, le plus souvent entre 100 et 1 000. Des tâches clientes (client tasks) maintiennent des connexions vers ces backends ; pour chaque requête entrante, le client doit choisir un backend. Au sommet de la pile, la plupart des requêtes HTTP externes atteignent le GFE (Google Frontend), le système de reverse proxy HTTP, qui route ensuite vers les applications, lesquelles réutilisent les mêmes algorithmes pour parler à leurs dépendances — d'où des chaînes transitives parfois profondes, avec un fort éventail (fan-out) en chemin.

Le cas idéal — et son coût

Dans le cas idéal, la charge se répartit parfaitement sur tous les backends : à tout instant, la tâche la moins chargée et la plus chargée consomment exactement le même CPU. Or on ne peut envoyer du trafic au datacenter que jusqu'au point où la tâche la plus chargée atteint sa limite. Plus formellement, si CPU[i] est le débit CPU de la tâche i et que la tâche 0 est la plus chargée, on gaspille la somme, sur toutes les tâches i, de (CPU[0] − CPU[i]) — « gaspillée » au sens de réservée mais inutilisée. Une mauvaise répartition limite donc artificiellement la disponibilité des ressources : vous réservez 1 000 CPU pour votre service mais ne parvenez à en utiliser que 700.

Identifier les tâches malades : contrôle de flux et canard boiteux

Avant de choisir un backend, il faut éviter ceux qui sont en mauvaise santé. Du point de vue du client, un backend est dans l'un de trois états : sain (healthy), refusant les connexions (en démarrage, arrêt ou état anormal), ou canard boiteux (lame duck).

Un premier garde-fou très basique est le contrôle de flux (flow control) : le client compte ses requêtes actives sur chaque connexion ; au-delà d'une limite (100 est raisonnable), il traite le backend comme malsain et cesse de l'alimenter. C'est aussi une forme rudimentaire de répartition — si un backend s'engorge, la charge se répand organiquement ailleurs. Mais ce mécanisme ne protège que contre les surcharges extrêmes : un backend peut s'engorger bien avant la limite, ou un client l'atteindre alors que le backend a des ressources libres (requêtes longues). On a même vu ce plafond par défaut se retourner et rendre tous les backends injoignables, requêtes bloquées jusqu'au timeout.

L'approche robuste est l'état de canard boiteux (lame duck) : le backend continue d'écouter sur son port et de servir, mais demande explicitement à ses clients de cesser de lui envoyer des requêtes. Il diffuse ce fait à ses clients actifs ; les clients inactifs l'apprennent via les contrôles de santé périodiques en UDP de l'implémentation RPC — l'information se propage typiquement en 1 ou 2 RTT. Le grand intérêt est un arrêt propre : on peut éteindre un backend ayant des requêtes en cours sans servir d'erreurs, ce qui facilite déploiements, maintenances et redémarrages. La séquence type :

1. L'ordonnanceur envoie SIGTERM à la tâche backend.
2. Le handler SIGTERM appelle l'API RPC → la tâche entre en lame duck
   et demande à ses clients d'aller voir ailleurs.
3. Les requêtes déjà en cours s'exécutent normalement.
4. À mesure que les réponses repartent, le nombre de requêtes actives décroît vers 0.
5. Après un délai configuré (≈ 10 s à 150 s selon la complexité des clients),
   la tâche sort proprement — ou l'ordonnanceur la tue.

Limiter le pool de connexions : le subsetting

Chaque client maintient un pool de connexions longue durée vers ses backends. Or chaque connexion coûte de la mémoire et du CPU (contrôles de santé périodiques) aux deux extrémités — négligeable en théorie, mais vite considérable sur des milliers de machines. Le subsetting (sous-ensemblage) consiste à limiter le pool de backends avec lesquels un client interagit, pour éviter qu'un client ne se connecte à un nombre énorme de backends, ou qu'un backend ne reçoive des connexions d'un nombre énorme de clients.

Le bon sous-ensemble se définit par sa taille (typiquement 20 à 100 backends) et son algorithme de sélection. On prend une taille plus grande si les clients sont bien moins nombreux que les backends (sinon certains backends ne reçoivent jamais de trafic), ou en cas de déséquilibres fréquents entre clients (rafales). L'algorithme doit assigner les backends uniformément — un surplus de 10 % sur un backend force un surdimensionnement de 10 % de tout l'ensemble — et minimiser le churn (le renouvellement de connexions lors des redémarrages et pannes), y compris quand on redéploie clients ou backends un à un.

Le subsetting aléatoire (random subsetting) — chaque client mélange une fois la liste et prend les premiers backends sains — répartit hélas très inégalement. Avec 300 clients, 300 backends et un sous-ensemble de 30 % (90 backends par client), le backend le moins chargé reçoit 63 % de la charge moyenne et le plus chargé 121 % ; à 10 %, c'est 50 % contre 150 %. Il faudrait des sous-ensembles de 75 % pour lisser correctement — impraticable. La solution de Google est le subsetting déterministe (deterministic subsetting) : on groupe les clients en « tours » (rounds), chaque tour utilisant un mélange (shuffle) différent de la liste de backends ; dans un tour, chaque backend est assigné à exactement un client.

def Subset(backends, client_id, subset_size):
    subset_count = len(backends) / subset_size
    # Grouper les clients en tours ; chaque tour utilise la même liste mélangée :
    round = client_id / subset_count
    random.seed(round)
    random.shuffle(backends)
    # Le sous-ensemble correspondant au client courant :
    subset_id = client_id % subset_count
    start = subset_id * subset_size
    return backends[start:start + subset_size]

Le mélange est essentiel : sans lui, un client reçoit des backends consécutifs qui peuvent tous devenir indisponibles ensemble (déploiement séquentiel). Le seed différent par tour garantit qu'à la chute d'un backend, sa charge se redistribue sur tous les backends restants et non sur les seuls voisins de son sous-ensemble — sinon, les pannes successives s'aggravent en cascade. Résultat : avec 300 clients connectés chacun à 10 backends sur 300, chaque backend reçoit exactement le même nombre de connexions.

Les politiques de répartition

Une fois le sous-ensemble de connexions saines établi, le client choisit pour chaque requête, en temps réel et avec une information partielle et parfois périmée, quel backend solliciter.

Le Round Robin simple répartit mal pour quatre raisons : petits sous-ensembles (les clients n'émettent pas au même rythme), coût variable des requêtes (les plus chères consomment 1 000 fois — ou plus — le CPU des moins chères, et le coût est souvent imprévisible), hétérogénéité des machines (d'où l'unité virtuelle « GCU », Google Compute Units, pour normaliser les débits CPU), et facteurs de performance imprévisibles — voisins antagonistes (jusqu'à 20 % d'écart par compétition sur les caches ou la bande passante) et redémarrages de tâches (une tâche redémarrée consomme plus quelques minutes ; d'où le préchauffage en lame duck).

Gérer la surcharge

Aussi efficace soit la répartition, une partie du système finira toujours par être surchargée ; gérer gracieusement cette condition est fondamental. Une première parade est de servir des réponses dégradées (degraded responses) : moins précises ou moins complètes, mais moins coûteuses (chercher un petit échantillon du corpus, s'appuyer sur une copie locale un peu périmée). Sous surcharge extrême, le service peut n'avoir d'autre choix que de servir des erreurs. La devise : rediriger quand on peut, dégrader quand il faut, gérer les erreurs de ressources de façon transparente en dernier recours.

Le piège des « requêtes par seconde »

Modéliser la capacité en requêtes par seconde (queries per second, QPS) — ou via une caractéristique statique censée approcher le coût (« combien de clés la requête lit-elle ») — fait un mauvais indicateur, car le coût d'une requête varie énormément (selon le client émetteur, l'heure, le type de trafic) et les ratios changent, parfois brutalement (une nouvelle version rend certaines fonctions bien moins coûteuses). Une cible mouvante est une mauvaise métrique. Mieux vaut mesurer la capacité directement en ressources disponibles : par exemple 500 cœurs CPU et 1 To de mémoire réservés pour un service dans un datacenter. Dans la grande majorité des cas, utiliser la consommation CPU comme signal de provisionnement fonctionne bien : sur les plateformes à ramasse-miettes (garbage collection), la pression mémoire se traduit naturellement par plus de CPU, et l'on peut souvent provisionner les autres ressources pour qu'elles ne s'épuisent pas avant le CPU.

Limites par client et throttling adaptatif

La surcharge globale (global overload) arrive fréquemment, surtout pour les services internes aux nombreux clients. Quand elle survient, le service ne doit livrer des erreurs qu'aux clients fautifs, en épargnant les autres. Pour cela, on définit des quotas par client (per-customer limits) selon l'usage négocié. Par exemple, pour un service de 10 000 CPU dans le monde :

Gmail        : jusqu'à 4 000 CPU-secondes / seconde
Calendar     : jusqu'à 4 000 CPU-secondes / seconde
Android      : jusqu'à 3 000 CPU-secondes / seconde
Google+      : jusqu'à 2 000 CPU-secondes / seconde
Tout le reste: jusqu'à   500 CPU-secondes / seconde

La somme dépasse les 10 000 CPU : on parie qu'ils n'atteindront pas tous leur plafond en même temps. L'usage global est agrégé en temps réel depuis toutes les tâches, puis des limites effectives sont poussées vers chaque tâche.

Quand un client dépasse son quota, le backend rejette vite ses requêtes — en supposant que renvoyer « hors quota » coûte bien moins que traiter. Mais ce n'est pas toujours vrai : pour une simple lecture en RAM, rejeter coûte presque autant qu'accepter, et un volume massif de rejets peut engorger le backend alors qu'il ne fait que rejeter. D'où le throttling côté client (client-side throttling) : quand un client constate qu'une part notable de ses requêtes récentes est rejetée pour « hors quota », il s'autolimite et plafonne son trafic sortant ; les requêtes en excès échouent localement sans même atteindre le réseau.

P(rejet local) = max(0, (requests − K × accepts) / (requests + 1))

Criticité

La criticité (criticality) classe chaque requête en quatre niveaux, propagés automatiquement par le système RPC (une requête sortante hérite par défaut de la criticité de la requête entrante) :

Quatre valeurs suffisent à modéliser presque tout service. La criticité est un concept de première classe du RPC, intégré aux mécanismes de contrôle : un client hors quota ne voit rejeter une criticité donnée que si toutes les criticités inférieures sont déjà rejetées ; une tâche surchargée rejette plus tôt les criticités basses ; le throttling adaptatif tient des statistiques séparées par criticité. La criticité est orthogonale à la latence : des suggestions affichées pendant la frappe sont très « sheddables » mais exigent une faible latence. On la fixe au plus près du client (généralement dans les frontends HTTP), pour que les dépendances surchargées, si profondes soient-elles dans la pile, respectent la criticité voulue.

Signaux d'utilisation

La protection au niveau de la tâche repose sur la notion d'utilisation (utilization) — souvent le débit CPU (CPU courant / CPU réservé), parfois aussi la mémoire. À mesure que l'utilisation approche des seuils configurés, la tâche rejette des requêtes selon leur criticité (seuils plus hauts pour les criticités hautes). Le signal le plus utile est l'executor load average : on compte les threads actifs (en exécution ou prêts à s'exécuter), lissés par décroissance exponentielle, et l'on rejette quand ce nombre dépasse les processeurs disponibles. Le lissage avale les pics très brefs (une requête à fort fan-out qui ordonnance une rafale d'opérations courtes), mais si la charge reste haute durablement, la tâche se met à rejeter. D'autres signaux (pression mémoire) peuvent se brancher, voire se combiner.

Gérer les erreurs de surcharge et décider de réessayer

Face à une erreur de surcharge, le client distingue deux situations. Si une grande partie des backends est surchargée (ce qui n'arriverait pas si la répartition inter-datacenters était parfaite), il ne faut pas réessayer : l'erreur doit remonter jusqu'à l'appelant. Si une petite partie l'est (imperfection de la répartition interne, par exemple une tâche venant de recevoir une requête très chère), la bonne réponse est de réessayer immédiatement : il reste probablement de la capacité ailleurs. Du point de vue des politiques, un réessai est indiscernable d'une nouvelle requête — on ne force pas explicitement un backend différent, on parie sur la probabilité offerte par la taille du sous-ensemble. C'est une forme de répartition organique : les réessais redirigent la charge vers des tâches mieux placées.

Trois garde-fous évitent l'explosion des réessais :

• un budget de réessais par requête plafonné à trois tentatives ; après quoi l'échec remonte ;
• un budget de réessais par client : on ne réessaie que tant que le ratio de réessais reste sous 10 %. Sans lui, dans le pire cas, le volume grimperait jusqu'à près de 3× ; avec lui, il se limite à environ 1,1× ;
• un compteur de tentatives dans les métadonnées : les backends en tiennent des histogrammes ; s'ils révèlent beaucoup de réessais (donc d'autres tâches probablement surchargées), le backend renvoie « surchargé ; ne pas réessayer » au lieu de l'erreur standard qui déclenche un réessai.

La charge des connexions

On ne mesure parfois que la charge causée directement par les requêtes — l'un des défauts du modèle QPS — en oubliant le coût CPU et mémoire de maintenir un large pool de connexions ou un fort taux de renouvellement. Négligeable à petite échelle, le problème devient sérieux à grande échelle. Le protocole RPC exige des clients inactifs des contrôles de santé périodiques ; après une période d'inactivité, le client lâche TCP et bascule en UDP. Mais avec un très grand nombre de clients émettant très peu de requêtes, le seul contrôle de santé peut coûter plus que servir les requêtes — d'où l'intérêt de régler finement les paramètres de connexion, voire de créer et détruire les connexions dynamiquement.

Le second problème, lié, est la rafale de nouvelles connexions : un gros job batch crée d'un coup une multitude de tâches clientes, et négocier simultanément trop de connexions peut engorger un groupe de backends. Deux parades : exposer cette charge à la répartition inter-datacenters (répartir selon l'utilisation du cluster, pas le seul nombre de requêtes), et imposer aux jobs batch un proxy dédié — au lieu de « client batch → backend », on a « client batch → proxy batch → backend ». Quand le gros job démarre, seul le proxy souffre : il agit comme un fusible protégeant les backends et les clients prioritaires, tout en réduisant le nombre de connexions vers le backend (de plus gros sous-ensembles, une meilleure vue de l'état).

Il n'existe pas de solution miracle : la répartition exige une compréhension profonde du système et de la sémantique de ses requêtes. Ces techniques — subsetting déterministe, Round Robin pondéré, throttling côté client, quotas, criticité — ont évolué avec les besoins des systèmes de Google, et continueront de le faire.

À retenir

• On répartit la charge à plusieurs niveaux : DNS (choix global du datacenter), VIP et balanceur réseau (choix de la machine), RPC dans le datacenter (choix de la tâche), enfin protection locale de la tâche — « répartir tôt, répartir souvent ».
• Le DNS est la couche la plus simple mais la moins contrôlable (résolveurs récursifs, cache, TTL bas, limite de 512 octets) ; les VIP la complètent, le hachage cohérent stabilise le mappage, et l'encapsulation GRE transmet les paquets à travers les continents.
• Dans le datacenter, on évite les tâches malsaines par le contrôle de flux et surtout l'état de canard boiteux (lame duck) qui permet un arrêt propre sans servir d'erreurs.
• Le subsetting déterministe répartit les connexions uniformément là où le subsetting aléatoire échoue ; côté politiques, le Round Robin pondéré (utilisation renvoyée par le backend) bat nettement le Round Robin simple et le « moins chargé » — qui souffre du piège du sinkholing.
• Modéliser la capacité en QPS est piégeux : mieux vaut la mesurer en ressources (le CPU comme signal de provisionnement) ; les quotas par client isolent les clients fautifs lors d'une surcharge globale.
• Le throttling adaptatif est purement local : le client s'autolimite via la probabilité max(0, (requests − K × accepts) / (requests + 1)) (Google préfère K = 2) ; la criticité (CRITICAL_PLUS, CRITICAL, SHEDDABLE_PLUS, SHEDDABLE), propagée par le RPC, ordonne quoi délester en premier.
• On contient les réessais par un budget par requête (3), un budget par client (10 %) et l'erreur « surchargé ; ne pas réessayer » qui empêche l'explosion combinatoire ; une tâche doit tenir jusqu'à 2× voire 10× son débit sans s'écrouler, pour prévenir les défaillances en cascade.