NGINX et l'algorithme d'équilibrage de charge « Power of Two Choices »

Les nouveaux cas d'utilisation nécessitent parfois de nouveaux algorithmes d'équilibrage de charge, et dans NGINX Plus R16 et NGINX Open Source 1.15.1, nous avons ajouté une nouvelle méthode particulièrement adaptée aux équilibreurs de charge distribués : une implémentation de l'algorithme « puissance de deux choix ».

Pourquoi avons-nous besoin d’un nouvel algorithme d’équilibrage de charge ?

Les méthodes d’équilibrage de charge classiques telles que les connexions minimales fonctionnent très bien lorsque vous utilisez un seul équilibreur de charge actif qui conserve une vue complète de l’état des nœuds équilibrés. L’approche « puissance de deux choix » n’est pas aussi efficace sur un seul équilibreur de charge, mais elle évite habilement le mauvais cas de « comportement grégaire » qui peut se produire lorsque vous évoluez vers un certain nombre d’équilibreurs de charge indépendants.

Ce scénario ne s’observe pas uniquement lorsque vous effectuez une mise à l’échelle dans des environnements hautes performances ; il s’observe également dans des environnements conteneurisés où plusieurs proxys équilibrent chacun la charge du trafic vers le même ensemble d’instances de service.

Une instance courante de ce scénario se produit lorsque vous utilisez NGINX Ingress Controller pour Kubernetes, avec une instance d’équilibrage de charge par nœud Kubernetes.

L'algorithme est appelé dans la littérature « puissance de deux choix », car il a été décrit pour la première fois dans la thèse de Michael Mitzenmacher de 1996, The Power of Two Choices in Randomized Load Balancing . Dans NGINX et NGINX Plus, il est implémenté comme une variante de l'algorithme d'équilibrage de charge aléatoire, nous l'appelons donc également Aléatoire avec deux choix .

Comment fonctionne le « pouvoir des deux choix » ?

Commençons par ce qui pourrait être une situation familière. Vous venez d’atterrir après un long vol international et, avec 400 autres voyageurs, vous êtes entré dans un hall d’arrivée très fréquenté.

De nombreux aéroports emploient des guides dans le hall des arrivées. Leur tâche consiste à diriger chaque voyageur vers l'une des nombreuses files d'attente pour chaque bureau d'immigration. Si nous considérons les guides comme des équilibreurs de charge :

• Vous et vos compagnons de voyage êtes des demandes , chacun espérant être traité le plus rapidement possible.
• Les bureaux d'immigration sont des serveurs (backend), chacun traitant un arriéré de demandes.
• Les guides maximisent l'efficacité en sélectionnant le meilleur serveur pour chaque requête.
• Les méthodes à disposition des guides pour sélectionner le meilleur serveur correspondent à des algorithmes d’équilibrage de charge.

Voyons dans quelle mesure certains algorithmes possibles fonctionnent dans un scénario d’équilibrage de charge distribué comme celui du hall des arrivées.

Équilibrage de charge à tour de rôle

Round Robin est une approche naïve de l’équilibrage de charge. Dans cette approche, le guide sélectionne chaque file d’attente à tour de rôle : le premier voyageur est dirigé vers la file d’attente A, le voyageur suivant vers la file d’attente B, et ainsi de suite. Une fois qu'un voyageur est dirigé vers la dernière file d'attente, le processus se répète à partir de la file d'attente A. Round Robin est l'algorithme d'équilibrage de charge par défaut utilisé par NGINX :

Cette approche fonctionne correctement, jusqu’à ce qu’il y ait un retard dans l’une des files d’attente. Il se peut qu'un voyageur ait égaré ses documents ou qu'il ait éveillé les soupçons de l'agent d'immigration :

La file d’attente s’arrête, mais le guide continue d’assigner les voyageurs à cette file d’attente. Les retards s’allongent de plus en plus, ce qui ne va pas rendre les voyageurs impatients plus heureux !

Équilibrage de charge avec le moins de connexions

Il existe une bien meilleure approche. Le guide surveille chaque file d'attente et chaque fois qu'un voyageur arrive, il envoie ce voyageur vers la file d'attente la plus courte. Cette méthode est analogue à la méthode d'équilibrage de charge Least Connections dans NGINX, qui attribue chaque nouvelle requête au serveur avec le moins de requêtes en attente (en file d'attente) :

L'équilibrage de charge des connexions minimales est très efficace pour les voyageurs dont le traitement prend des durées différentes. Il cherche à équilibrer la longueur des files d’attente et évite d’ajouter des requêtes supplémentaires à une file d’attente bloquée.

Équilibrage de charge au minimum

Nous avons constaté que le temps de traitement des dossiers varie selon les passagers ; de plus, certaines files d’attente sont traitées plus rapidement ou plus lentement que d’autres. Par exemple, un agent d’immigration peut avoir des problèmes informatiques, ce qui signifie qu’il traite les voyageurs plus lentement ; un autre agent peut être très pointilleux sur les détails et interroger les voyageurs de manière très approfondie. D’autres agents pourraient être très expérimentés et capables de traiter les voyageurs plus rapidement.

Et si chaque guichet d’immigration était doté d’un compteur indiquant combien de voyageurs ont été traités au cours, par exemple, des 10 dernières minutes ? Le guide peut ensuite orienter les voyageurs vers une file d'attente en fonction de sa longueur et de la rapidité de son traitement. C'est une manière plus efficace de répartir la charge, et c'est ce que fait l'algorithme d'équilibrage de charge Least Time de NGINX Plus :

Cet algorithme est spécifique à NGINX Plus car il s'appuie sur des données supplémentaires collectées avec les métriques d'état étendu de NGINX Plus. Il est particulièrement efficace dans les environnements cloud ou virtuels où la latence de chaque serveur peut varier de manière imprévisible, de sorte que la longueur de la file d'attente seule n'est pas suffisante pour estimer le délai.

Tout s'écroule avec plusieurs guides

Jusqu’à présent, nous n’avions qu’un seul guide (c’est-à-dire un équilibreur de charge) avec une vue complète des files d’attente et du temps de réponse dans le hall des arrivées. Ce guide essaie de faire le meilleur choix pour chaque voyageur en fonction des informations qu'il connaît.

Considérons maintenant ce qui se passe si nous avons plusieurs guides, chacun dirigeant les voyageurs de manière indépendante. Les guides ont des vues indépendantes sur la longueur des files d'attente et les temps d'attente – ils ne prennent en compte que les voyageurs qu'ils envoient dans chaque file d'attente.

Ce scénario est sujet à un comportement indésirable, où tous les guides remarquent qu'une file d'attente est momentanément plus courte et plus rapide, et tous envoient les voyageurs vers cette file d'attente. Les simulations montrent que ce « comportement grégaire » répartit les voyageurs de manière déséquilibrée et injuste. De la même manière, plusieurs équilibreurs de charge indépendants peuvent surcharger certains serveurs en amont, quel que soit l’algorithme de « meilleur choix » que vous utilisez.

L'algorithme d'équilibrage de charge « Power of Two Choices »

La solution réside dans l’algorithme d’équilibrage de charge « puissance de deux choix ». Au lieu de faire le meilleur choix absolu en utilisant des données incomplètes, avec le « pouvoir de deux choix », vous choisissez deux files d’attente au hasard et choisissez la meilleure option des deux, en évitant le pire choix .

Le « pouvoir de deux choix » est efficace à mettre en œuvre. Vous n’avez pas besoin de comparer toutes les files d’attente pour choisir la meilleure option à chaque fois ; au lieu de cela, vous n’avez besoin d’en comparer que deux. Et, peut-être de manière contre-intuitive, cela fonctionne mieux à grande échelle que les algorithmes de meilleur choix. Il évite le comportement indésirable du troupeau en évitant simplement la pire file d'attente et en répartissant le trafic avec un certain degré d'aléatoire.

Utilisation de la « puissance des deux choix » avec NGINX et NGINX Plus

Dans NGINX et NGINX Plus, la méthode d’équilibrage de charge « puissance de deux choix » est implémentée comme une variante de l’algorithme aléatoire, nous l’appelons donc Aléatoire avec deux choix.

Dans NGINX Open Source, Random with Two Choices choisit entre deux serveurs sélectionnés au hasard en fonction de celui qui a actuellement le moins de connexions actives. Il s’agit du même critère de sélection que celui utilisé pour l’algorithme des moindres connexions. (Il s'agit également de l'algorithme par défaut dans NGINX Plus et peut être configuré explicitement en ajoutant le paramètre least_conn .)

service en amont1 { zone service1 64k; serveur 192.168.1.11; serveur 192.168.1.12; serveur 192.168.1.13; aléatoire deux ; }

NGINX Plus prend également en charge le paramètre least_time , qui utilise le même critère de sélection que l'algorithme Least Time. Comme avec cet algorithme, vous choisissez en outre de prendre en compte soit :

• Le temps nécessaire pour recevoir l' en-tête de réponse ( least_time=header )
• Le temps nécessaire pour recevoir la réponse complète ( least_time=last_byte ), comme dans l'extrait suivant. Le critère du temps minimum est idéal pour les situations où la latence de chaque serveur en amont peut varier.

service en amont1 { zone service1 64k; serveur 192.168.1.11; serveur 192.168.1.12; serveur 192.168.1.13; aléatoire deux least_time=last_byte ; # utiliser l'en-tête ou le dernier octet }

Conclusion

NGINX et NGINX Plus prennent en charge une gamme de méthodes d’équilibrage de charge ; dans cet article, nous n’avons pas pris en compte les méthodes de hachage déterministe et de hachage IP .

Les méthodes Least Connections (et pour NGINX Plus, Least Time) sont très efficaces pour équilibrer les charges lorsque l'équilibreur de charge dispose d'une vue complète de la charge de travail attribuée à chaque nœud et de ses performances passées. Ils sont moins efficaces lorsque plusieurs équilibreurs de charge attribuent des requêtes et que chacun a une vue incomplète de la charge de travail et des performances.

La « puissance de deux choix » utilise un algorithme aléatoire biaisé et s’est avérée efficace pour équilibrer les charges lorsque chaque équilibreur de charge a une vue incomplète ou retardée. Il évite le « comportement grégaire » dont font preuve d’autres algorithmes qui cherchent à prendre la meilleure décision pour chaque demande.

Considérez Random with Two Choices, l'implémentation de NGINX du « pouvoir de deux choix », pour les environnements à très hautes performances et pour les scénarios d'équilibrage de charge distribués. Un bon cas d’utilisation se présente lors de l’utilisation de plusieurs contrôleurs Ingress sur Kubernetes.