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

Owen GarrettDirecteur senior de la gestion des produits

De nouveaux cas d’usage nécessitent parfois de nouveaux algorithmes d’équilibrage de charge. 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 « power of two choices ».

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

Les méthodes classiques d’équilibrage de charge telles que Moins de connexions fonctionnent très bien lorsque vous utilisez un seul équilibreur de charge actif qui dispose d’une vue complète de l’état des nœuds entre lesquels la charge est répartie. L’approche dite de la « puissance de deux choix » est moins efficace avec un seul équilibreur de charge, mais elle évite habilement le « comportement grégaire » indésirable qui peut se produire lorsque vous déployez plusieurs équilibreurs de charge indépendants.

Ce scénario ne s’observe pas uniquement lors d’une mise à l’échelle horizontale dans des environnements hautes performances ; il se produit également dans des environnements conteneurisés, où plusieurs proxys répartissent chacun le trafic entre le même ensemble d’instances de service.

Ce scénario se présente fréquemment lorsque vous utilisez NGINX Ingress Controller pour Kubernetes, avec une instance d’équilibrage de charge par nœud Kubernetes.

Dans la littérature, cet algorithme est appelé « puissance de deux choix », car il a été décrit pour la première fois dans la thèse de Michael Mitzenmacher publiée en 1996, intitulée La puissance de deux choix dans l’équilibrage de charge aléatoire. Dans NGINX et NGINX Plus, il est implémenté comme une variante de l’algorithme d’équilibrage de charge aléatoire (Random). Nous l’appelons donc également Aléatoire avec deux choix.

Comment fonctionne la « puissance de deux choix » ?

Commençons par une situation qui vous est peut-être familière. Vous venez d’atterrir après un long vol international et, avec 400 autres voyageurs, vous entrez dans un hall des arrivées bondé.

De nombreux aéroports emploient des agents d’orientation dans le hall des arrivées. Leur rôle consiste à diriger chaque voyageur vers l’une des différentes files d’attente aux guichets de l’immigration. Si l’on considère ces agents comme des répartiteurs de charge :

• Vous et les autres voyageurs êtes des « requêtes », chacun espérant être traité le plus rapidement possible.
• Les guichets de l’immigration sont des serveurs (backend), chacun traitant une file d’attente de requêtes.
• Les guides optimisent l’efficacité en sélectionnant le meilleur serveur pour chaque requête.
• Les méthodes dont disposent les guides pour sélectionner le meilleur serveur correspondent à des algorithmes d’équilibrage de charge.

Examinons l’efficacité de quelques-uns des algorithmes possibles dans un scénario d’équilibrage de charge distribué tel que celui du hall des arrivées.

Équilibrage de charge à tour de rôle

La méthode round-robin est une approche rudimentaire de l’équilibrage de charge. Avec cette méthode, le guide sélectionne chaque file à tour de rôle : le premier voyageur est dirigé vers la file A, le suivant vers la file B, et ainsi de suite. Une fois qu’un voyageur a été dirigé vers la dernière file, le processus reprend à la file A. Round-robin est l’algorithme d’équilibrage de charge utilisé par défaut par NGINX :

Cette approche fonctionne correctement, jusqu’à ce qu’un retard survienne dans l’une des files d’attente. Peut-être qu’un voyageur a égaré ses documents ou éveillé les soupçons de l’agent d’immigration :

La file d’attente n’avance plus, mais le guide continue d’y envoyer des voyageurs. Elle ne cesse donc de s’allonger, ce qui ne va certainement pas réjouir les voyageurs impatients !

Équilibrage de charge selon le nombre minimal de connexions

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

L’équilibrage de charge « Least Connections » gère assez efficacement les voyageurs dont le traitement prend plus ou moins de temps. Il cherche à équilibrer la longueur des files d’attente et évite d’ajouter de nouvelles requêtes à une file bloquée.

Équilibrage de charge selon le temps de réponse le plus court

Nous avons vu que le temps nécessaire au traitement varie selon les passagers et que certaines files avancent plus ou moins vite que d’autres. Par exemple, un agent de l’immigration peut rencontrer des problèmes informatiques qui le ralentissent, tandis qu’un autre peut être très pointilleux et interroger les voyageurs de manière approfondie. D’autres agents peuvent être très expérimentés et traiter les voyageurs plus rapidement.

Et si chaque guichet de l’immigration était surmonté d’un compteur indiquant combien de voyageurs ont été pris en charge, par exemple, au cours des 10 dernières minutes ? Le guide pourrait alors orienter les voyageurs vers une file d’attente en fonction de sa longueur et de la vitesse à laquelle elle avance. C’est une façon plus efficace de répartir la charge, et c’est précisément ce que fait l’algorithme d’équilibrage de charge Least Time de NGINX Plus :

Cet algorithme est propre à NGINX Plus, car il s’appuie sur des données supplémentaires collectées à l’aide des métriques « É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, si bien que la longueur de la file d’attente ne suffit pas à elle seule pour estimer le délai.

Tout s’effondre avec plusieurs guides

Jusqu’à présent, nous avions un seul guide (c’est-à-dire un répartiteur de charge) disposant d’une vue d’ensemble des files d’attente et des 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 dont il dispose.

Voyons maintenant ce qui se passe si plusieurs guides orientent chacun les voyageurs de manière indépendante. Chaque guide a sa propre vision de la longueur des files d’attente et des temps d’attente : il ne tient compte que des voyageurs qu’il envoie vers chaque file.

Ce scénario est susceptible d’entraîner un comportement indésirable : tous les guides remarquent qu’une file d’attente est momentanément plus courte et avance plus vite, et y envoient tous les voyageurs. Les simulations montrent que ce « comportement grégaire » répartit les voyageurs de manière déséquilibrée et inéquitable. De même, plusieurs répartiteurs de charge indépendants peuvent surcharger certains serveurs en amont, quel que soit l’algorithme de « meilleur choix » utilisé.

L’algorithme d’équilibrage de charge « puissance de deux choix »

La solution réside dans l’algorithme d’équilibrage de charge dit de la « puissance de deux choix ». Au lieu de chercher à faire le meilleur choix absolu à partir de données incomplètes, cette méthode consiste à sélectionner deux files d’attente au hasard et à choisir la meilleure des deux, évitant ainsi le pire choix.

L’algorithme de « la puissance de deux choix » est facile à mettre en œuvre. Il n’est pas nécessaire de comparer toutes les files d’attente pour sélectionner systématiquement la meilleure option : il suffit d’en comparer deux. Et, aussi contre-intuitif que cela puisse paraître, il est plus performant à grande échelle que les algorithmes qui recherchent le meilleur choix. Il évite les effets de troupeau indésirables grâce à une approche simple : écarter la pire file d’attente et répartir le trafic avec une part d’aléatoire.

Utiliser la « puissance de 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 Random. Nous l’appelons donc Random with Two Choices.

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

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two; 
}

NGINX Plus prend également en charge le paramètre « least_time », qui utilise le même critère de sélection que l’algorithme du temps minimal. Comme avec cet algorithme, vous pouvez choisir de prendre en compte l’un des deux éléments suivants :

• Le délai de réception de 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 minimal est idéal lorsque la latence de chaque serveur en amont peut varier.

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two least_time=last_byte; # use header or last_byte
}

Conclusion

NGINX et NGINX Plus prennent en charge différentes méthodes de répartition de charge ; dans cet article, nous n’avons pas abordé les méthodes déterministes « Hash » et « IP Hash ».

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. Elles sont moins efficaces lorsque plusieurs équilibreurs de charge répartissent les requêtes et que chacun ne dispose que d’une vue partielle de la charge de travail et des performances.

La méthode « Power of Two Choices » utilise un algorithme aléatoire biaisé et s’est révélée efficace pour équilibrer les charges lorsque chaque répartiteur de charge dispose d’une vue incomplète ou différée. Elle évite le « comportement grégaire » observé avec d’autres algorithmes qui cherchent à prendre la meilleure décision pour chaque requête.

Envisagez Random with Two Choices, l’implémentation par NGINX de la « puissance de deux choix », pour les environnements à très hautes performances et les scénarios d’équilibrage de charge distribué. Cette solution est particulièrement adaptée à l’utilisation de plusieurs contrôleurs Ingress sur Kubernetes.

À propos de l’auteur

Owen GarrettDirecteur senior de la gestion des produits

Autres articles de Owen Garrett