Frage Welche Art von Lastausgleichsalgorithmen gibt es?


Ich untersuchte verschiedene Load-Balancing-Algorithmen für HTTP und fand gerade 3. Random, Round Robin und Weighted Round Robin. Gibt es noch andere Möglichkeiten?

Vielen Dank Paul


27
2018-02-12 15:34


Ursprung




Antworten:


Die gebräuchlichsten Lastenausgleichsalgorithmen für HTTP Load Balancer sind IMHO:

  • Round Robin (manchmal "Next in Loop" genannt).

  • Gewichtete Round Robin - als Round Robin, aber einige Server bekommen einen größeren Anteil am gesamten Traffic.

  • Zufällig.

  • Quell-IP Hash. Verbindungen werden basierend auf der Quell-IP-Adresse an Back-End-Server verteilt. Wenn ein Webknoten fehlschlägt und außer Betrieb genommen wird, ändert sich die Verteilung. Solange alle Server einen bestimmten Client ausführen, wird die IP-Adresse immer an denselben Webserver gesendet.

  • URL Hash. Ähnlich wie der Quell-IP-Hash, außer Hashing für die URL der Anfrage. Dies ist nützlich beim Lastenausgleich vor Proxy-Caches, da Anfragen für ein bestimmtes Objekt immer nur an einen einzigen Backend-Cache gesendet werden. Dies vermeidet Cache-Duplizierung, wobei dasselbe Objekt in mehreren / allen Caches gespeichert ist, und erhöht die effektive Kapazität der Backend-Caches.

  • Kleinste Verbindungen, gewichtete kleinste Verbindungen. Der Load Balancer überwacht die Anzahl der offenen Verbindungen für jeden Server und sendet diese an den Server mit der geringsten Auslastung.

  • Geringster Verkehr, geringster Verkehr. Der Load Balancer überwacht die Bitrate von jedem Server und sendet sie an den Server mit dem geringsten ausgehenden Datenverkehr.

  • Geringste Latenz. Perlbal macht eine schnelle HTTP OPTIONS-Anfrage an die Backend-Server und sendet die Anfrage an den ersten Server zu beantworten.

Möglicherweise handelt es sich bei den oben genannten Algorithmen nicht um Algorithmen im Sinne der Computerwissenschaft, sondern um allgemeinere Beschreibungen gängiger Ansätze. Hier ist eine kleine Arbeit von Cisco, die einige der Algorithmen, die sie genauer verwenden. Implementierungen von anderen Anbietern werden etwas anders aussehen.

Es gibt Randfälle, in denen die exotischeren Algorithmen nützlich sind - zum Beispiel kann Video-Streaming sich gut für "geringsten Verkehr" eignen. Im Allgemeinen ist die optimale Lösung für die meisten Webanwendungen und Websites:

  • EIN gemeinsames / verteiltes Sitzungssystem, so dass jeder Webnode jede Benutzeranforderung beantworten kann (d. h. Benutzersitzungsdaten wie Session-Cookies sind gleichermaßen für alle Server verfügbar).

  • Lastenausgleich mit Round Robin (optional gewichtete Round Robin) oder Zufällig Verteilung. Round Robin und Random sind einfache und belastbare Algorithmen ohne "Hotspot" -Probleme, d. H. Die Lastverteilung auf Backends bleibt in allen Situationen fair.


28
2018-02-20 10:50





Die Frage ist unvollständig:

Lastenausgleich WAS?

CPUs können Sättigung einnehmen; Die übliche Perspektive ist rückwärts - eine Ressource drängen, anstatt an sie zu ziehen.

Festplatten haben viele verschiedene Arten von Lasten, wie Speicherplatz, Lesegeschwindigkeiten, Schreibgeschwindigkeiten, Durchsatz usw.

Netzwerke können basierend auf der Latenz oder dem Gesamtdurchsatz auf die Last abgestimmt werden ...

Menschen können basierend auf ihrer individuellen Kapazität ausgeglichen werden; einige Multitasking gut, andere nicht und dann gibt es Qualität gegen Quantität. Sie können Ihre Personalressourcen basierend auf vielen Faktoren und mit unterschiedlichen Gewichten für verschiedene Attribute optimieren.

Das Obige ist bei weitem nicht erschöpfend; Der Punkt ist, dass verschiedene Ressourcen völlig unterschiedliche Arten des Lastausgleichs verwenden. Von ihren verfügbaren Attributen und Kapazitäten müssen Sie angeben, welche von Interesse für den Ausgleich sind.

Was Sie versuchen auszugleichen, ist das erste Kriterium für einen guten Balancing-Algorithmus. Und der Vorschlag, dass es nur drei gibt, ist ... unerklärt. Es wäre eine Doktorarbeit wert, einen ordentlichen Job zu machen, um alle Wege zu beschreiben, wie "Lasten ausgeglichen sind".

RT


4
2018-02-12 16:17



Sie vermissen die Frage Richard, Algorithmen sind Grundlage jeder Methode oder Implementierung. - monomyth
Tut mir leid, Monomyth, ich habe kein verdammtes Ding vermisst. Öffne deine Meinung. - Richard T
@monomyth, @Richard hat recht - Die Wahl des Algorithmus hängt davon ab, was Sie auslasten. Sie können einen Algorithmus entwickeln, um die Speicherbelegung des Plattenspeichers auszugleichen, der möglicherweise gar nicht auf andere Anwendungen wie HTTP-Anforderungen zutrifft. - Josh
@Josh, @ Richard, die Konzepte der Lastverteilung sind jedoch die gleichen. Sie können immer noch Round Robin verwenden, um die Plattennutzung, iSCSI, HTTP, CPU, alles auszugleichen. - Mark Henderson♦
@Farseeker Ich stimme zu, Round Robin ist ziemlich universell. Aber gibt es nicht einige Lastenausgleichsalgorithmen, die für die Aufgabe spezifisch sind? - Josh


Nicht eine direkte Antwort auf Ihre Frage, sondern eine tatsächliche Lösung, die wir für nützlich befunden haben. Mit LVS und dem Impulsdämon ist unser HTTP-Lastausgleich so konfiguriert, dass er ein benutzerdefiniertes Bash-Skript aufruft, das die Belastung der "echten Server" über eine einfache SSH-Verbindung und einen Anruf an bestimmt Betriebszeit.

Basierend auf dem Lastdurchschnitt der Server wird dann eine Gewichtung pro Server festgelegt. Dies ist nicht der wissenschaftlichste Ansatz, da der Lastdurchschnitt nicht unbedingt auf HTTP-Verbindungen oder CPU-Last hinweist, die durch diese Verbindungen verursacht werden. Trotzdem hatten wir überraschend effektive Ergebnisse.

Mein 2c. YMMV.

PS: Sieh dir das an LVS-Projekt - Sie werden auf jeden Fall Informationen über Load-Balance-Scheduling-Implementierungen finden.


0
2018-02-13 22:00



Cool. Danke für den Link! - Paul Sheldrake