Robinhood, le service d’équilibrage de charge maison de Dropbox

• Robinhood est le service interne d’équilibrage de charge de Dropbox, déployé en 2020
• Il achemine le trafic interne entre les serveurs afin de répartir de manière équilibrée la charge des services
• Avant Robinhood, la plupart des services de Dropbox souffraient d’une répartition inégale de la charge entre les backends
• Des différences matérielles et les limites des anciens algorithmes d’équilibrage de charge provoquaient des problèmes de fiabilité dus à des instances surchargées
• Pour y remédier, il fallait surprovisionner excessivement les flottes de services, ce qui entraînait une hausse des coûts matériels

Nouvelles fonctionnalités de Robinhood

• Grâce à un contrôleur PID (Proportional-Integral-Derivative), il est désormais possible de gérer les déséquilibres de charge plus rapidement et plus efficacement
• Cela se traduit par une amélioration de la fiabilité de l’infrastructure et une réduction significative des coûts matériels
• Avec la hausse des workloads IA qui alimentent les fonctionnalités intelligentes les plus récentes, une gestion efficace de la demande en ressources GPU est plus cruciale que jamais

Les défis de l’équilibrage de charge chez Dropbox

• Le système de service discovery de Dropbox peut monter à l’échelle jusqu’à des centaines de milliers d’hôtes répartis dans plusieurs data centers à travers le monde
• Certains services de Dropbox comptent des millions de clients, mais il n’est pas possible d’autoriser chaque client à se connecter à toutes les instances de serveur
  • Cela exercerait une pression mémoire trop importante sur les serveurs, et lors des redémarrages, les handshakes TLS pourraient surcharger les serveurs
• À la place, le système de service discovery fournit à chaque client un sous-ensemble de serveurs auxquels se connecter
• La meilleure stratégie d’équilibrage de charge disponible côté client consiste à effectuer un round-robin sur la liste d’adresses fournie par le système de service discovery
  • Cependant, cette méthode peut entraîner un déséquilibre important de la charge entre les différentes instances de serveur
  • Augmenter la taille du sous-ensemble est une mesure d’atténuation simple, mais elle n’élimine pas totalement le déséquilibre et ajoute simplement un paramètre supplémentaire pour les propriétaires de services
• Le problème plus profond est que, même si chaque serveur reçoit le même nombre de requêtes, le matériel sous-jacent peut varier d’un serveur à l’autre
  • Autrement dit, une requête consomme des quantités de ressources différentes selon la classe matérielle
• Le point clé est que les clients n’ont aucune visibilité sur la charge des serveurs
• Par le passé, Dropbox a tenté de résoudre ce problème en faisant ajouter la charge par les serveurs dans les en-têtes de réponse
  • Les clients pouvaient alors effectuer eux-mêmes l’équilibrage de charge en sélectionnant l’endpoint le moins chargé dans leur sous-ensemble d’adresses
  • Les résultats étaient prometteurs, mais il restait plusieurs inconvénients
    • Il était difficile de l’adopter à l’échelle mondiale, car les en-têtes de charge spéciaux exigeaient des modifications de code à la fois côté serveur et côté client
    • Les résultats étaient bons, mais pas suffisamment bons

Décision de construire Robinhood

• En 2019, Dropbox a officiellement décidé de construire Robinhood
• Ce nouveau service a été construit au-dessus du système interne existant de service discovery afin de collecter les informations de charge auprès des serveurs et de les joindre aux informations de routage
• Robinhood s’appuie sur l’Endpoint Discovery Service d’Envoy pour intégrer les informations de charge dans les poids des endpoints, afin que les clients puissent effectuer un round-robin pondéré
• La communauté gRPC adoptant le protocole Envoy xDS, Robinhood est compatible à la fois avec Envoy et avec les clients gRPC
• Dropbox a choisi de développer ce nouveau service parce qu’il n’existait alors aucune solution d’équilibrage de charge répondant à ses besoins

Les résultats de Robinhood

• Après plusieurs années d’utilisation en production, Robinhood a montré des résultats prometteurs
• Dropbox a réussi à réduire de 25 % la taille de la flotte de certains services de grande envergure, générant ainsi d’importantes économies annuelles sur le matériel
• La fiabilité s’est également améliorée grâce à la diminution du nombre de processus surutilisés

L’architecture de Robinhood

• Une instance de Robinhood est déployée dans chaque data center et se compose de trois parties : le service d’équilibrage de charge, le proxy et la base de données de routage

Service d’équilibrage de charge (LBS)

• Le cœur de Robinhood
• Il collecte les informations de charge et génère les informations de routage contenant les poids des endpoints
• Comme plusieurs instances mettent simultanément à jour les informations de routage d’un service, un shard manager interne est utilisé pour attribuer un worker principal à chaque service
• Chaque service étant indépendant, il est possible de partitionner le LBS par service et de le faire évoluer horizontalement

Proxy

• Il a pour rôle d’acheminer les informations de charge d’un service vers la partition LBS correspondante dans le data center
• L’utilisation d’un proxy permet aussi de réduire le nombre de connexions directes vers les processus LBS
  • Sans proxy, chaque processus LBS devrait se connecter à tous les nœuds de l’infrastructure
  • À la place, les processus LBS ne se connectent qu’aux proxys, ce qui réduit fortement la pression mémoire sur le LBS
• Les proxys ne se connectent qu’aux nœuds du même data center, ce qui permet une montée en charge horizontale
• Ce schéma est largement utilisé dans l’infrastructure pour protéger les services contre un trop grand nombre de connexions TLS entrantes

Base de données de routage

• Une base de données fondée sur ZooKeeper/etcd qui stocke les informations de routage d’un service, notamment les noms d’hôte, les adresses IP et les poids générés par le LBS
• ZooKeeper et etcd peuvent notifier en temps réel à tous les observateurs les changements de nœuds/clés, ce qui convient parfaitement au cas d’usage de service discovery orienté lecture chez Dropbox
• La cohérence finale garantie par ZooKeeper/etcd est également suffisante pour la service discovery

Regard détaillé sur le service d’équilibrage de charge

• L’objectif de l’équilibrage de charge est de faire en sorte que le taux d’utilisation de tous les nœuds soit égal au taux d’utilisation moyen
• Un contrôleur PID est utilisé pour maintenir le taux d’utilisation de chaque nœud quasiment identique au taux d’utilisation moyen
• Le LBS crée un contrôleur PID pour chaque nœud et utilise le taux d’utilisation moyen comme point de consigne
• Le LBS utilise la sortie du contrôleur PID comme delta sur le poids des endpoints, puis normalise les poids entre tous les endpoints du service
• Même si un nouveau nœud nécessite quelques ajustements pour converger vers le taux d’utilisation moyen, le contrôleur PID est très efficace pour l’équilibrage de charge

Scénarios de fonctionnement du LBS

• Le LBS est conçu pour gérer divers scénarios susceptibles d’affecter l’équilibrage de charge, des redémarrages de nœuds jusqu’aux rapports de charge manquants
• Afin de maintenir des performances optimales, le LBS met en œuvre plusieurs stratégies pour traiter ces cas exceptionnels

Démarrage du LBS

• Le LBS conserve en mémoire les informations de charge ainsi que l’état du contrôleur PID
• Lors d’un redémarrage du LBS, il ne commence pas immédiatement à mettre à jour les poids, mais attend brièvement que des rapports de charge arrivent
• Pour les poids du contrôleur PID, le LBS lit et restaure les poids des endpoints depuis la base de données de routage

Nœuds en cold start

• De nouveaux nœuds rejoignent fréquemment la flotte d’un service, il est donc important d’éviter le problème de thundering herd
• Comme le taux d’utilisation initial d’un nouveau nœud est généralement nul, le LBS définit le poids de ce nœud à une faible valeur d’endpoint weight, puis laisse le contrôleur PID amener le nœud jusqu’au taux d’utilisation moyen

Rapports de charge manquants

• Dans un environnement de systèmes distribués, les pannes sont courantes
• En raison de la congestion réseau ou de défaillances matérielles, les rapports de charge de certains nœuds peuvent être retardés ou ne pas arriver
• Le LBS ignore ces nœuds lors des mises à jour de poids, de sorte que leurs endpoint weights ne changent pas
• Cependant, si un grand nombre de rapports de charge manque, le calcul du taux d’utilisation moyen peut devenir imprécis
• Par sécurité, le LBS saute alors entièrement l’étape de mise à jour des poids

Métriques d’utilisation

• Le taux d’utilisation CPU est la métrique d’équilibrage de charge la plus utilisée chez Dropbox
• Pour les services qui ne sont pas limités par le CPU, le nombre de requêtes en cours constitue une bonne mesure de remplacement
• Le LBS a été implémenté pour prendre en charge l’équilibrage de charge sur la base du CPU et/ou des requêtes en cours

Limites

• Le contrôleur PID forme une boucle de rétroaction afin de maintenir le taux d’utilisation d’un nœud proche de la valeur cible, c’est-à-dire le taux d’utilisation moyen
• Lorsqu’il y a très peu de feedback, comme pour les services à très faible trafic ou les requêtes à très forte latence mesurées en minutes, l’équilibrage de charge n’est pas efficace
• Les services avec des requêtes à forte latence doivent être asynchrones

Routage entre data centers

• Les instances LBS gèrent l’équilibrage de charge à l’intérieur d’un data center
• Le routage entre data centers implique d’autres considérations
  • Par exemple, il est souhaitable d’acheminer les requêtes vers le data center le plus proche afin de réduire le temps aller-retour des requêtes
• Pour cela, Dropbox a introduit une configuration de localité qui définit la répartition du trafic entre les data centers cibles

Évaluation des performances de l’équilibreur de charge

• Les performances d’équilibrage de charge sont mesurées par le ratio max/avg
  • Si le propriétaire du service choisit un équilibrage de charge basé sur le CPU, alors maxCPU/avgCPU est utilisé comme indicateur de performance
  • Les propriétaires de service dimensionnent généralement leurs services en fonction du taux d’utilisation maximal entre les nœuds, car l’objectif principal de l’équilibrage de charge est de réduire la taille de la flotte
• La stratégie d’équilibrage de charge avec contrôleur PID permet de maintenir le ratio max/avg proche de 1

Graphiques d’évaluation des performances de l’équilibrage de charge

• Graphique montrant le CPU max/avg et le CPU p95/avg du plus grand cluster de proxys Envoy
  • Après activation de l’équilibrage de charge basé sur un contrôleur PID, les deux métriques chutent pour se rapprocher de 1
  • Le ratio max/avg est passé de 1,26 à 1,01, soit une amélioration de 20 %
• Graphique montrant une analyse par quantiles de l’utilisation CPU par nœud
  • Après activation de l’équilibrage de charge basé sur un contrôleur PID, max, p95, avg et p5 se confondent presque en une seule ligne
• Autre graphique montrant le CPU max/avg et le CPU p95/avg du plus grand cluster de frontends de base de données
  • Après activation de l’équilibrage de charge basé sur un contrôleur PID, les deux métriques chutent pour se rapprocher de 1
  • Le ratio max/avg est passé de 1,4 à 1,05, soit une amélioration de 25 %
• Autre graphique montrant une analyse par quantiles de l’utilisation CPU par nœud
  • Après activation de l’équilibrage de charge basé sur un contrôleur PID, max, p95, avg et p5 se confondent à nouveau presque en une seule ligne

Pourquoi avoir construit Config Aggregator

• Robinhood offre plusieurs options que les propriétaires de service peuvent choisir, et peut aussi appliquer les changements de manière dynamique
• Les propriétaires de service créent et mettent à jour la configuration Robinhood de leur service dans le répertoire du service au sein de la base de code
• Ces paramètres sont stockés dans un service de gestion de configuration, qui fournit une bibliothèque pratique recevant en temps réel les changements apportés à la configuration Robinhood
• Cependant, plusieurs problèmes empêchent de construire et de publier régulièrement depuis la base de code la méga-configuration de Robinhood
  • Lorsqu’un changement est introduit par une publication de configuration, appuyer sur le bouton de rollback est risqué
    • car on ne sait pas combien d’autres services ont été modifiés depuis la dernière publication
  • L’équipe responsable de Robinhood est aussi tenue pour responsable de chaque publication de méga-configuration
    • Cela signifie que l’équipe Robinhood doit participer à toutes les publications de configuration modifiée, ce qui représente une perte de temps d’ingénierie
    • alors que, dans la plupart des incidents, les propriétaires de service peuvent résoudre le problème eux-mêmes
  • Pour minimiser les risques potentiels, chaque publication met plusieurs heures à être déployée dans plusieurs data centers
• Pour résoudre ces problèmes, un autre petit service, Config Aggregator, a été développé

Config Aggregator

• Config Aggregator collecte toutes les configurations propres à chaque service et compose la méga-configuration utilisée par le LBS
• Config Aggregator surveille les configurations par service et propage les changements vers la méga-configuration en temps réel
• Config Aggregator fournit aussi une fonctionnalité de tombstone pour éviter qu’une configuration Robinhood de service soit supprimée par erreur
  • Si un propriétaire de service publie un changement qui supprime le service de la configuration Robinhood, Config Aggregator marque l’entrée du service comme tombstone au lieu de la supprimer immédiatement
  • La suppression effective intervient quelques jours plus tard
  • Cette fonctionnalité résout aussi des conditions de concurrence pouvant survenir à cause des cycles de publication différents entre la configuration Robinhood et d’autres configurations de routage, comme la configuration Envoy
• Un inconvénient du service de gestion de configuration est qu’il n’est actuellement pas versionné
• La méga-configuration est donc sauvegardée périodiquement au cas où il faudrait ramener la configuration du LBS à un état connu comme sain

Stratégie de migration

• Basculer de stratégie d’équilibrage de charge en une seule fois peut être risqué
• C’est pourquoi Robinhood permet de configurer plusieurs stratégies d’équilibrage de charge pour un service
• Dropbox dispose d’une feature gate basée sur un pourcentage, ce qui a conduit à implémenter une stratégie hybride dans laquelle le client utilise comme poids d’endpoint une somme pondérée des poids générés par les deux stratégies d’équilibrage de charge
• Cela permet de migrer progressivement vers la nouvelle stratégie d’équilibrage de charge tout en garantissant que tous les clients voient la même attribution de poids pour les endpoints

Enseignements tirés

• La conception et l’implémentation de Robinhood ont permis de dégager plusieurs leçons clés sur ce qui fonctionne et ce qui ne fonctionne pas
• En donnant la priorité à la simplicité, en minimisant les changements côté client et en planifiant la migration dès le départ, il a été possible de simplifier le développement et le déploiement du LBS et d’éviter des pièges coûteux

La configuration doit être aussi simple que possible

• Robinhood a introduit de nombreuses options configurables par les propriétaires de service
• Cependant, dans la plupart des cas, les paramètres par défaut fournis sont tout ce dont ils ont besoin
• Une bonne configuration par défaut simple — ou mieux encore, l’absence de configuration — peut faire gagner énormément de temps d’ingénierie

Les changements côté client doivent eux aussi rester simples

• Le déploiement de changements sur les clients internes peut prendre plusieurs mois
  • La plupart des déploiements sont publiés chaque semaine, mais beaucoup ne le sont qu’une fois par mois, voire pas du tout pendant des années
• Plus il est possible de déplacer de changements vers le LBS, mieux c’est
  • Par exemple, il a été décidé très tôt d’utiliser un weighted round robin dans la conception du client, et ce choix n’a plus changé depuis
  • Cela a considérablement accéléré l’avancement
• Limiter la plupart des changements au LBS réduit aussi les risques pour la stabilité
  • car, si nécessaire, les changements dans le LBS peuvent être annulés en quelques minutes

La migration doit être planifiée dès la phase de conception du projet

• La migration consomme une quantité énorme de temps d’ingénierie
• Il existe aussi des risques de stabilité à prendre en compte
• Ce n’est pas la partie la plus amusante, mais c’est un travail important
• Lors de la conception d’un nouveau service, il faut réfléchir le plus tôt possible à la manière de migrer en douceur les cas d’usage existants vers ce nouveau service
• Plus les exigences imposées aux propriétaires de service sont nombreuses, plus la migration devient un cauchemar
  • en particulier pour les composants d’infrastructure de base
• Le processus de migration de Robinhood n’ayant pas été bien conçu dès le départ, bien plus de temps que prévu a été consacré à réimplémenter le processus et à repenser la configuration
• Le temps d’ingénierie requis pour la migration doit être considéré comme un indicateur clé de réussite

L’impact de Robinhood

• Après environ un an en production, on peut dire que la version la plus récente de Robinhood a effectivement résolu les défis historiques de Dropbox en matière d’équilibrage de charge
• L’algorithme central, le contrôleur PID, a produit des résultats prometteurs et montré des gains de performance significatifs sur les plus gros services
• Des enseignements précieux ont été tirés sur la conception et l’exploitation d’un service d’équilibrage de charge à l’échelle de Dropbox

Notes

1. Soient N, M et s respectivement le nombre de serveurs, le nombre de clients et la taille du sous-ensemble d’adresses. Le nombre de clients auxquels un serveur se connecte suit un échantillon de la loi binomiale B(M, s/n). Comme indiqué plus haut, les clients effectuent un simple round robin sur l’ensemble d’adresses fourni par la découverte de services. Ainsi, si chaque client envoie à peu près le même volume de requêtes, la distribution de charge côté serveur ressemble à une distribution binomiale.

2. Le système existant de découverte de services a été étendu pour prendre en charge le protocole gRPC xDS (A27). À la date de rédaction de ce billet, les clients gRPC ne prennent pas en charge le weighted round robin sur les poids d’endpoint du control plane ; un sélecteur personnalisé de weighted round robin a donc été implémenté sur la base d’un ordonnancement shortest deadline first.

3. Un cas intéressant s’est présenté où un service se retrouvait parfois bloqué à cause d’entrées/sorties dégradées. Dans ce type de situation, le CPU du nœud concerné reste faible, et le LBS commence à augmenter le poids du nœud pour remonter le CPU vers la moyenne, ce qui entraîne une spirale mortelle. La solution adoptée a consisté à utiliser comme mesure de charge le maximum entre le CPU et le nombre de requêtes en cours afin de rééquilibrer le service.

L’avis de GN⁺

• Robinhood semble être un excellent service qui a efficacement résolu les défis de load balancing de Dropbox. L’utilisation d’un contrôleur PID est particulièrement impressionnante.
• C’est un bon exemple de la difficulté du load balancing à très grande échelle sur une infrastructure mondiale. Il faut prendre en compte de nombreux facteurs, comme les différences matérielles, la répartition inégale de la charge et la congestion réseau.
• Il semble essentiel de concevoir le système de façon à ce que tous les composants fonctionnent ensemble de manière organique. Le LBS, le proxy et la base de routage sont séparés, mais interagissent étroitement en temps réel.
• Les graphiques qui évaluent quantitativement les performances du load balancing et visualisent les améliorations sont particulièrement marquants. Ils montrent notamment bien qu’il est important de maintenir le ratio max/moy proche de 1 pour optimiser la taille de la flotte.
• L’introduction du Config Aggregator, qui sépare les configurations par service, semble aussi être une bonne idée. Cela permet aux responsables de chaque service de gérer leurs modifications de manière indépendante.
• La mise en place de garde-fous comme les tombstones est également un détail apprécié. Il est important d’éviter les suppressions de configuration accidentelles.
• Les leçons tirées de la stratégie de migration semblent elles aussi utiles. Si la migration n’est pas prise en compte dès le départ, elle peut ensuite faire perdre beaucoup de temps.
• Dans l’ensemble, Robinhood apparaît comme une solution méthodique et sophistiquée pour le load balancing à l’échelle de Dropbox. C’est un cas dont d’autres entreprises disposant d’infrastructures de grande ampleur peuvent s’inspirer.

Solutions similaires :

• Elastic Load Balancing (ELB) d’AWS et Cloud Load Balancing de Google Cloud proposent eux aussi des services managés pour le load balancing à grande échelle.
• Dans le cas de Kubernetes, il existe un load balancer intégré (kube-proxy), mais des solutions de service mesh comme Istio ou Linkerd permettent d’aller plus loin en matière de load balancing et de gestion du trafic.
• Zuul de Netflix et Envoy de Lyft offrent également des fonctionnalités de load balancing basées sur des proxys.

Points à considérer avant l’adoption :

• Il faut vérifier la compatibilité avec l’infrastructure et les services existants. Si une migration est nécessaire, une stratégie doit être définie.
• Il faut tester et surveiller suffisamment l’impact sur les performances et la stabilité. Un bug dans la logique de load balancing peut être critique.
• Il faut définir le périmètre et le rythme d’adoption en tenant compte des capacités de l’équipe. Une adoption progressive semble préférable à un déploiement précipité à grande échelle.
• À long terme, des efforts continus d’optimisation et d’amélioration seront nécessaires. Des actions comme l’ajustement de l’algorithme de load balancing selon le contexte ou la suppression des goulets d’étranglement pourront être utiles.

[kbumsik]

On parle même d’un contrôleur PID côté logiciel, haha.