NGINX und der Load-Balancing-Algorithmus „Power of Two Choices“

Owen GarrettSenior Director, Produktmanagement

Neue Anwendungsfälle erfordern mitunter neue Load-Balancing-Algorithmen. In NGINX Plus R16 und NGINX Open Source 1.15.1 haben wir daher eine neue Methode eingeführt, die sich besonders für verteilte Load Balancer eignet: eine Implementierung des „Power of Two Choices“-Algorithmus.

Warum brauchen wir einen neuen Lastverteilungsalgorithmus?

Klassische Lastverteilungsverfahren wie Least Connections funktionieren sehr gut, wenn Sie einen einzelnen aktiven Load Balancer betreiben, der einen vollständigen Überblick über den Zustand der Knoten hat, auf die die Last verteilt wird. Der Ansatz „Power of Two Choices“ ist bei einem einzelnen Load Balancer weniger effektiv, verhindert jedoch geschickt das ungünstige „Herdenverhalten“, das auftreten kann, wenn Sie auf mehrere unabhängige Load Balancer skalieren.

Dieses Szenario tritt nicht nur bei der horizontalen Skalierung in Hochleistungsumgebungen auf, sondern auch in containerisierten Umgebungen, in denen mehrere Proxys jeweils den Datenverkehr auf dieselbe Gruppe von Dienstinstanzen verteilen.

Ein typisches Beispiel für dieses Szenario ist die Verwendung des NGINX Ingress Controller für Kubernetes mit einer Load-Balancing-Instanz pro Kubernetes-Knoten.

Der Algorithmus wird in der Fachliteratur 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 ist er als Variante des Random-Lastverteilungsalgorithmus implementiert, weshalb wir ihn auch als Random with Two Choices bezeichnen.

Wie funktioniert „Power of Two Choices“?

Beginnen wir mit einer Situation, die Ihnen vielleicht bekannt vorkommt. Sie sind gerade nach einem langen internationalen Flug gelandet und haben zusammen mit 400 anderen Reisenden eine belebte Ankunftshalle betreten.

Viele Flughäfen beschäftigen im Ankunftsbereich Mitarbeiter, die Reisende zu einer der verschiedenen Warteschlangen vor den Passkontrollschaltern leiten. Wenn wir uns diese Mitarbeiter als Load Balancer vorstellen:

• Sie und Ihre Mitreisenden sind Anfragen, die alle hoffen, so schnell wie möglich bearbeitet zu werden.
• Die Einreiseschalter sind (Backend-)Server, die jeweils einen Rückstau von Anfragen abarbeiten.
• Die Guides maximieren die Effizienz, indem sie für jede Anfrage den besten Server auswählen.
• Die den Guides zur Auswahl des besten Servers zur Verfügung stehenden Methoden entsprechen Lastverteilungsalgorithmen.

Betrachten wir, wie gut einige der möglichen Algorithmen in einem verteilten Lastverteilungsszenario wie der Ankunftshalle funktionieren.

Round-Robin-Lastverteilung

Round Robin ist ein einfacher Ansatz zur Lastverteilung. Dabei wählt der Lotse die 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 wurde, beginnt der Vorgang erneut bei Warteschlange A. Round Robin ist der standardmäßig von NGINX verwendete Lastverteilungsalgorithmus:

Dieser Ansatz funktioniert ausreichend gut, bis es in einer der Warteschlangen zu einer Verzögerung kommt. Vielleicht hat ein Reisender seine Dokumente verlegt oder erregt den Verdacht des Einwanderungsbeamten:

Die Warteschlange bewegt sich nicht mehr, doch der Guide weist ihr weiterhin Reisende zu. Der Rückstau wird immer länger – das wird die ungeduldigen Reisenden bestimmt nicht glücklicher machen!

Lastverteilung nach den wenigsten Verbindungen

Es gibt einen wesentlich besseren Ansatz. Der Mitarbeiter beobachtet jede Warteschlange und schickt jeden neu eintreffenden Reisenden zur kürzesten Warteschlange. Diese Methode entspricht dem Least-Connections-Lastverteilungsverfahren in NGINX, bei dem jede neue Anfrage dem Server mit den wenigsten ausstehenden (in der Warteschlange befindlichen) Anfragen zugewiesen wird:

Der Lastenausgleich nach dem Least-Connections-Prinzip kommt recht gut mit Reisenden zurecht, deren Abfertigung unterschiedlich lange dauert. Er versucht, die Längen der Warteschlangen auszugleichen, und vermeidet es, weitere Anfragen zu einer ins Stocken geratenen Warteschlange hinzuzufügen.

Lastverteilung nach der kürzesten Antwortzeit

Wir haben gesehen, dass die Abfertigung verschiedener Passagiere unterschiedlich lange dauert. Außerdem werden manche Warteschlangen schneller oder langsamer abgearbeitet als andere. Beispielsweise könnte ein Grenzbeamter Computerprobleme haben und Reisende deshalb langsamer abfertigen, während ein anderer besonders genau ist und Reisende sehr eingehend befragt. Wieder andere Beamte könnten sehr erfahren sein und Reisende schneller abfertigen.

Was wäre, wenn über jedem Einreiseschalter ein Zähler angebracht wäre, der beispielsweise anzeigt, wie viele Reisende in den letzten 10 Minuten abgefertigt wurden? Dann kann der Mitarbeiter die Reisenden anhand der Länge einer Warteschlange und der Geschwindigkeit, mit der sie abgearbeitet wird, einer Warteschlange zuweisen. Das ist eine effektivere Methode zur Lastverteilung – und genau das macht der Least Time-Load-Balancing-Algorithmus in NGINX Plus:

Dieser Algorithmus ist speziell für NGINX Plus ausgelegt, da er auf zusätzlichen Daten basiert, die mithilfe der Extended-Status-Metriken von NGINX Plus erfasst werden. Er ist besonders effektiv in Cloud- oder virtuellen Umgebungen, in denen die Latenz zu den einzelnen Servern unvorhersehbar schwanken kann, sodass die Warteschlangenlänge allein nicht ausreicht, um die Verzögerung abzuschätzen.

Mit mehreren Leitfäden bricht alles zusammen

Bisher hatten wir einen einzigen Lotsen (also einen Load Balancer), der einen vollständigen Überblick über die Warteschlangen und die Reaktionszeiten in der Ankunftshalle hatte. Dieser Lotse versucht, anhand der ihm vorliegenden Informationen für jeden Reisenden die bestmögliche Entscheidung zu treffen.

Betrachten wir nun, was passiert, wenn wir mehrere Lotsen haben, die Reisende jeweils unabhängig voneinander weiterleiten. Die Lotsen haben jeweils eine eigene Sicht auf die Warteschlangenlängen und Wartezeiten – sie berücksichtigen nur die Reisenden, die sie selbst an die jeweilige Warteschlange verwiesen haben.

Dieses Szenario begünstigt ein unerwünschtes Verhalten: Alle Lotsen bemerken, dass eine Warteschlange vorübergehend kürzer ist und schneller vorankommt, und schicken sämtliche Reisenden dorthin. Simulationen zeigen, dass dieses „Herdenverhalten“ zu einer unausgewogenen und unfairen Verteilung der Reisenden führt. Ebenso können mehrere unabhängig voneinander arbeitende Load Balancer einige Upstream-Server überlasten – unabhängig davon, welchen Algorithmus zur Auswahl der „besten Option“ Sie verwenden.

Der Load-Balancing-Algorithmus „Power of Two Choices“

Die Lösung liegt im Lastverteilungsalgorithmus „Power of Two Choices“. Anstatt anhand unvollständiger Daten die absolut beste Wahl zu treffen, wählt man bei „Power of Two Choices“ zufällig zwei Warteschlangen aus und entscheidet sich für die bessere der beiden Optionen, wodurch die schlechtere Wahl vermieden wird.

„Power of Two Choices“ lässt sich effizient implementieren. Sie müssen nicht jedes Mal alle Warteschlangen vergleichen, um die beste Option auszuwählen, sondern lediglich zwei. Und auch wenn es vielleicht nicht intuitiv erscheint, funktioniert dieser Ansatz bei zunehmender Skalierung besser als Algorithmen, die stets die beste Option auswählen. Unerwünschtes Herdenverhalten wird durch den einfachen Ansatz vermieden, die schlechteste Warteschlange auszuschließen und den Datenverkehr mit einem gewissen Maß an Zufälligkeit zu verteilen.

„Power of Two Choices“ mit NGINX und NGINX Plus verwenden

In NGINX und NGINX Plus ist die Lastverteilungsmethode „Power of Two Choices“ als Variante des Random-Algorithmus implementiert. Daher bezeichnen wir sie als „Random with Two Choices“.

In NGINX Open Source wählt Random with Two Choices zwischen zwei zufällig ausgewählten Servern denjenigen aus, der aktuell weniger aktive Verbindungen aufweist. Dies ist dasselbe Auswahlkriterium wie beim Least-Connections-Algorithmus. (Dies ist auch der Standardalgorithmus in NGINX Plus und kann durch Hinzufügen des Parameters least_conn explizit konfiguriert werden.)

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

NGINX Plus unterstützt außerdem den Parameter „least_time“, der dasselbe Auswahlkriterium wie der Least-Time-Algorithmus verwendet. Wie bei diesem Algorithmus können Sie zusätzlich wählen, ob Folgendes berücksichtigt werden soll:

• Die Zeit bis zum Empfang des Antwort-Headers (least_time=header)
• Die Zeit bis zum Empfang der vollständigen Antwort (least_time=last_byte), wie im folgenden Codeausschnitt dargestellt. Das Kriterium „Least Time“ eignet sich ideal für Situationen, in denen die Latenz der einzelnen Upstream-Server variieren kann.

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
}

Fazit

NGINX und NGINX Plus unterstützen eine Reihe von Lastverteilungsverfahren. In diesem Artikel wurden die deterministischen Verfahren „Hash“ und „IP Hash“ nicht berücksichtigt.

Die Methoden „Least Connections“ (und bei NGINX Plus „Least Time“) sorgen für eine sehr effektive Lastverteilung, wenn der Load Balancer einen vollständigen Überblick über die den einzelnen Knoten zugewiesene Arbeitslast und deren 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 gewichteten Zufallsalgorithmus und hat sich bei der Lastverteilung als effektiv erwiesen, wenn die einzelnen Load Balancer nur über unvollständige oder verzögerte Informationen verfügen. Dadurch wird das „Herdenverhalten“ vermieden, das bei anderen Algorithmen auftritt, die für jede Anfrage die bestmögliche Entscheidung treffen wollen.

Ziehen Sie für Umgebungen mit sehr hohen Leistungsanforderungen und für verteilte Lastverteilungsszenarien „Random with Two Choices“ in Betracht, die NGINX-Implementierung des Prinzips „Power of Two Choices“. Ein guter Anwendungsfall ergibt sich beim Einsatz mehrerer Ingress-Controller in Kubernetes.

Über den Autor

Owen GarrettSenior Director, Produktmanagement

Weitere Blogbeiträge von Owen Garrett