NGINX und der Lastausgleichsalgorithmus „Power of Two Choices“

Neue Anwendungsfälle erfordern manchmal neue Lastausgleichsalgorithmen, und in NGINX Plus R16 und NGINX Open Source 1.15.1 haben wir eine neue Methode hinzugefügt, die sich besonders für verteilte Lastausgleichsfunktionen eignet: eine Implementierung des „Power of Two Choices“-Algorithmus.

Warum brauchen wir einen neuen Lastausgleichsalgorithmus?

Klassische Lastausgleichsmethoden wie Least Connections funktionieren sehr gut, wenn Sie einen einzelnen aktiven Lastausgleichsdienst betreiben, der einen vollständigen Überblick über den Status der lastausgeglichenen Knoten behält. Der Ansatz der „Macht der zwei Möglichkeiten“ ist bei einem einzelnen Load Balancer nicht so effektiv, vermeidet aber geschickt das ungünstige „Herdenverhalten“, das bei der Skalierung auf mehrere unabhängige Load Balancer auftreten kann.

Dieses Szenario ist nicht nur beim Skalieren in Hochleistungsumgebungen zu beobachten; es kommt auch in Containerumgebungen vor, in denen mehrere Proxys den Datenverkehr jeweils auf denselben Satz von Serviceinstanzen verteilen.

Dieses Szenario tritt häufig auf, wenn Sie NGINX Ingress Controller für Kubernetes mit einer Lastausgleichsinstanz pro Kubernetes-Knoten verwenden.

Der Algorithmus wird in der Literatur als „Power of Two Choices“ bezeichnet, da er erstmals 1996 in Michael Mitzenmachers Dissertation The Power of Two Choices in Randomized Load Balancing beschrieben wurde. In NGINX und NGINX Plus wird es als Variante des zufälligen Lastausgleichsalgorithmus implementiert, weshalb wir es auch als „Random mit zwei Auswahlmöglichkeiten“ bezeichnen.

Wie funktioniert „Power of Two Choices“?

Beginnen wir mit einer möglicherweise vertrauten Situation. Sie sind gerade nach einem langen internationalen Flug gelandet und betreten gemeinsam mit 400 anderen Reisenden eine geschäftige Ankunftshalle.

Viele Flughäfen beschäftigen in der Ankunftshalle Guides. Ihre Aufgabe besteht darin, jeden Reisenden in eine der zahlreichen Warteschlangen vor den einzelnen Einwanderungsschaltern einzureihen. Wenn wir uns die Anleitungen als Lastenausgleich vorstellen:

• An Sie und Ihre Mitreisenden werden Anfragen gerichtet , von denen jeder hofft, dass sie so schnell wie möglich bearbeitet werden.
• Bei den Einwanderungsschaltern handelt es sich um (Backend-) Server , die jeweils einen Rückstand an Anfragen abarbeiten.
• Die Anleitungen maximieren die Effizienz, indem sie für jede Anfrage den besten Server auswählen.
• Die in den Anleitungen verfügbaren Methoden zur Auswahl des besten Servers entsprechen den Lastausgleichsalgorithmen.

Lassen Sie uns überlegen, wie gut einige der möglichen Algorithmen in einem Szenario mit verteiltem Lastausgleich wie der Ankunftshalle funktionieren.

Round-Robin-Lastausgleich

Round Robin ist ein naiver Ansatz zum Lastenausgleich. Bei diesem Ansatz wählt der Reiseleiter die einzelnen Warteschlangen der Reihe nach aus: Der erste Reisende wird zu Warteschlange A geleitet, der nächste zu Warteschlange B und so weiter. Sobald ein Reisender zur letzten Warteschlange geleitet wird, wiederholt sich der Vorgang ab Warteschlange A. Round Robin ist der von NGINX verwendete Standardalgorithmus für den Lastausgleich:

Dieser Ansatz funktioniert angemessen, bis es in einer der Warteschlangen zu einer Verzögerung kommt. Vielleicht hat ein Reisender seine Dokumente verlegt oder erregt beim Einwanderungsbeamten Misstrauen:

Die Warteschlange bewegt sich nicht mehr, doch der Reiseführer weist weiterhin Reisende dieser Warteschlange zu. Der Rückstau wird immer länger – das erfreut die ungeduldigen Reisenden nicht gerade!

Lastenausgleich mit der geringsten Anzahl an Verbindungen

Es gibt einen viel besseren Ansatz. Der Reiseleiter behält jede Warteschlange im Auge und schickt jeden ankommenden Reisenden in die kürzeste Warteschlange. Diese Methode entspricht der Lastausgleichsmethode „Least Connections“ in NGINX, die jede neue Anfrage dem Server mit den wenigsten ausstehenden (in die Warteschlange gestellten) Anfragen zuweist:

Durch die Lastverteilung bei geringsten Verbindungen kann recht effektiv mit Reisenden gearbeitet werden, deren Verarbeitung unterschiedlich lange dauert. Es versucht, die Länge der Warteschlangen auszugleichen und verhindert, dass einer ins Stocken geratenen Warteschlange weitere Anfragen hinzugefügt werden.

Lastausgleich mit minimalem Zeitaufwand

Wir haben festgestellt, dass die Abfertigung bei verschiedenen Passagieren unterschiedlich lange dauert; außerdem werden manche Warteschlangen schneller oder langsamer abgefertigt als andere. Beispielsweise hat ein Einwanderungsbeamter möglicherweise Computerprobleme und bearbeitet die Einreiseanträge deshalb langsamer; ein anderer Beamter legt vielleicht großen Wert auf Details und befragt die Reisenden sehr genau. Andere Beamte verfügen möglicherweise über viel Erfahrung und können Reisende schneller abfertigen.

Was wäre, wenn über jeder Einwanderungskabine ein Zähler angebracht wäre, der anzeigt, wie viele Reisende beispielsweise in den letzten 10 Minuten abgefertigt wurden? Anschließend kann der Reiseführer die Reisenden je nach Länge und Abfertigungsgeschwindigkeit zu einer Warteschlange leiten. Dies ist eine effektivere Möglichkeit, die Last zu verteilen. Genau das macht der Least Time -Lastausgleichsalgorithmus in NGINX Plus:

Dieser Algorithmus ist spezifisch für NGINX Plus, da er auf zusätzlichen Daten basiert, die mit den erweiterten Statusmetriken von NGINX Plus erfasst werden. Dies ist insbesondere in Cloud- oder virtuellen Umgebungen effektiv, in denen die Latenz zu den einzelnen Servern unvorhersehbar variieren kann und die Warteschlangenlänge allein daher nicht ausreicht, um die Verzögerung abzuschätzen.

Mit mehreren Anleitungen fällt alles auseinander

Bisher hatten wir einen Leitfaden (d. h. einen Lastenausgleich) mit einer vollständigen Ansicht der Warteschlangen und Reaktionszeiten in der Ankunftshalle. Dieser Reiseführer versucht, für jeden Reisenden auf Grundlage der ihm vorliegenden Informationen die beste Wahl zu treffen.

Überlegen Sie nun, was passiert, wenn wir mehrere Reiseführer haben, die die Reisenden jeweils unabhängig voneinander anleiten. Die Guides verfügen über unabhängige Ansichten der Warteschlangenlängen und -wartezeiten – sie berücksichtigen nur die Reisenden, die sie in die jeweilige Warteschlange schicken.

In diesem Szenario kommt es häufig zu unerwünschtem Verhalten: Alle Reiseleiter bemerken, dass eine Warteschlange vorübergehend kürzer und schneller ist, und schicken die Reisenden in diese Warteschlange. Simulationen zeigen, dass dieses „Herdenverhalten“ zu einer unausgewogenen und unfairen Verteilung der Reisenden führt. Auf die gleiche Weise können mehrere unabhängige Load Balancer einige Upstream-Server überlasten, unabhängig davon, welchen „Best Choice“-Algorithmus Sie verwenden.

Der Lastausgleichsalgorithmus „Die Macht der zwei Möglichkeiten“

Die Lösung liegt im Lastausgleichsalgorithmus „Power of Two Choices“. Anstatt auf der Grundlage unvollständiger Daten die absolut beste Wahl zu treffen, wählen Sie bei der „Power of Two Choices“ zwei Warteschlangen nach dem Zufallsprinzip aus und entscheiden sich für die bessere der beiden, wobei Sie die schlechtere Wahl vermeiden .

„Die Macht der zwei Entscheidungen“ ist effizient umzusetzen. Sie müssen nicht alle Warteschlangen vergleichen, um jedes Mal die beste Option auszuwählen; stattdessen müssen Sie nur zwei vergleichen. Und es funktioniert – vielleicht unbemerkt – im großen Maßstab besser als die Best-Choice-Algorithmen. Es vermeidet das unerwünschte Herdenverhalten durch den einfachen Ansatz, die schlimmste Warteschlange zu vermeiden und den Verkehr mit einem gewissen Maß an Zufälligkeit zu verteilen.

Verwenden der „Power of Two Choices“ mit NGINX und NGINX Plus

In NGINX und NGINX Plus ist die Lastausgleichsmethode „Power of Two Choices“ als Variante des Random-Algorithmus implementiert, daher nennen wir sie „Random mit zwei Auswahlmöglichkeiten“.

In NGINX Open Source wählt Random with Two Choices zwischen zwei zufällig ausgewählten Servern, basierend darauf, welcher derzeit weniger aktive Verbindungen hat. Dies ist dasselbe Auswahlkriterium, das für den Least Connections-Algorithmus verwendet wird. (Dies ist auch der Standardalgorithmus in NGINX Plus und kann durch Hinzufügen des Parameters least_conn explizit konfiguriert werden.)

Upstream-Dienst1 { Zone Dienst1 64k; Server 192.168.1.11; Server 192.168.1.12; Server 192.168.1.13; zufällig zwei ; }

NGINX Plus unterstützt auch den Parameter least_time , der dasselbe Auswahlkriterium wie der Least Time-Algorithmus verwendet. Wie bei diesem Algorithmus können Sie außerdem zwischen folgenden Optionen wählen:

• Die Zeit zum Empfangen des Antwortheaders ( least_time=header )
• Die Zeit bis zum Empfang der vollständigen Antwort ( least_time=last_byte ), wie im folgenden Snippet. Das Kriterium „Least Time“ ist ideal für Situationen, in denen die Latenz zu jedem Upstream-Server variieren kann.

Upstream-Dienst1 { Zone Dienst1 64k; Server 192.168.1.11; Server 192.168.1.12; Server 192.168.1.13; zufällig zwei least_time=last_byte ; # Header oder last_byte verwenden }

Abschluss

NGINX und NGINX Plus unterstützen eine Reihe von Methoden zum Lastenausgleich. In diesem Artikel haben wir die deterministischen Hash- und IP-Hash- Methoden nicht berücksichtigt.

Die Methoden „Least Connections“ (und bei NGINX Plus „Least Time“) sind beim Lastenausgleich sehr effektiv, wenn der Load Balancer einen vollständigen Überblick über die jedem Knoten zugewiesene Arbeitslast und seine bisherige Leistung hat. Sie sind weniger effektiv, wenn mehrere Load Balancer Anfragen zuweisen und jeder nur einen unvollständigen Überblick über die Arbeitslast und Leistung hat.

„Power of two choices“ verwendet einen voreingenommenen Zufallsalgorithmus und hat sich beim Lastenausgleich als effektiv erwiesen, wenn jeder Lastenausgleich eine unvollständige oder verzögerte Ansicht hat. Es vermeidet das „Herdenverhalten“ anderer Algorithmen, die versuchen, bei jeder Anfrage die beste Entscheidung zu treffen.

Erwägen Sie „Random with Two Choices“, die Implementierung der „Power of Two Choices“ von NGINX, für Umgebungen mit sehr hoher Leistung und für Szenarien mit verteiltem Lastausgleich. Ein guter Anwendungsfall ergibt sich bei der Verwendung mehrerer Ingress-Controller auf Kubernetes.