Robinhoo d, der hauseigene Load-Balancing-Dienst von Dropbox

• Robinhood ist der interne Load-Balancing-Dienst von Dropbox und wurde 2020 eingeführt
• Er routet internen Traffic zwischen Servern, um die Service-Last ausgewogen zu verteilen
• Vor Robinhood hatten die meisten Dropbox-Dienste mit einer unausgewogenen Lastverteilung zwischen den Backends zu kämpfen
• Unterschiede in der Hardware und Grenzen früherer Load-Balancing-Algorithmen führten zu Zuverlässigkeitsproblemen durch überlastete Instanzen
• Um das auszugleichen, mussten Service-Fleets übermäßig provisioniert werden, was zu höheren Hardwarekosten führte

Neue Funktionen von Robinhood

• Durch den Einsatz eines PID-Controllers (Proportional-Integral-Derivative) kann Lastungleichgewicht schneller und effektiver gesteuert werden
• Das führte zu einer besseren Zuverlässigkeit der Infrastruktur und erheblichen Einsparungen bei den Hardwarekosten
• Mit dem Anstieg von AI-Workloads für moderne intelligente Funktionen ist ein effektives Nachfragemanagement für GPU-Ressourcen wichtiger denn je

Herausforderungen beim Load Balancing bei Dropbox

• Das Service-Discovery-System von Dropbox ist auf Hunderttausende Hosts über mehrere Rechenzentren weltweit skalierbar
• Einige Dropbox-Dienste haben Millionen von Clients, aber es ist nicht möglich, jedem Client die Verbindung zu allen Serverinstanzen zu erlauben
  • Das würde zu zu hohem Speicherdruck auf den Servern führen, und bei Serverneustarts könnten TLS-Handshakes die Server überlasten
• Stattdessen liefert das Service-Discovery-System jedem Client eine Teilmenge der Server, zu denen er sich verbinden soll
• Die beste Load-Balancing-Strategie, die dem Client zur Verfügung steht, ist ein Round-Robin über die vom Service-Discovery-System bereitgestellte Adressliste
  • Mit dieser Methode kann die Last einzelner Serverinstanzen jedoch weiterhin stark unausgeglichen sein
  • Die Größe der Teilmenge zu erhöhen ist eine einfache Gegenmaßnahme, beseitigt das Ungleichgewicht aber nicht vollständig und gibt Service-Verantwortlichen nur einen weiteren Parameter an die Hand
• Das tieferliegende Problem ist, dass sich die zugrunde liegende Hardware von Server zu Server unterscheiden kann, selbst wenn an jeden Server gleich viele Requests gesendet werden
  • Das heißt, Requests verbrauchen auf unterschiedlichen Hardwareklassen unterschiedlich viele Ressourcen
• Der Kern des Problems ist, dass Clients keine Sicht auf die Serverlast haben
• In der Vergangenheit wurde versucht, dieses Problem zu lösen, indem Server die Last in Response-Headern mitlieferten
  • Clients konnten dann selbst Load Balancing betreiben, indem sie aus ihrer Adress-Teilmenge den am wenigsten ausgelasteten Endpoint auswählten
  • Die Ergebnisse waren vielversprechend, hatten aber weiterhin einige Nachteile
    • Da sowohl Server als auch Clients Codeänderungen für spezielle Last-Header benötigten, war eine unternehmensweite Einführung schwierig
    • Die Ergebnisse waren gut, aber nicht gut genug

Entscheidung für den Bau von Robinhood

• 2019 fiel die offizielle Entscheidung, Robinhood zu entwickeln
• Der neue Dienst wurde auf dem bestehenden internen Service-Discovery-System aufgebaut, sammelt Lastinformationen von den Servern und hängt sie an die Routing-Informationen an
• Robinhood nutzt den Endpoint Discovery Service von Envoy, um Lastinformationen in Endpoint-Gewichte zu integrieren, sodass Clients gewichtetes Round-Robin verwenden können
• Da die gRPC-Community das Envoy-xDS-Protokoll übernimmt, ist Robinhood sowohl mit Envoy- als auch mit gRPC-Clients kompatibel
• Da es damals keine bestehende Load-Balancing-Lösung gab, die die Anforderungen von Dropbox erfüllte, entschied man sich für den Aufbau eines neuen Dienstes

Ergebnisse von Robinhood

• Nach mehreren Jahren Einsatz in der Produktion zeigen sich vielversprechende Ergebnisse
• Bei einigen großen Diensten konnte die Größe der Fleets um 25 % reduziert werden, was jährlich erhebliche Hardwarekosten einspart
• Da weniger Prozesse übermäßig ausgelastet sind, hat sich auch die Zuverlässigkeit verbessert

Architektur von Robinhood

• In jedem Rechenzentrum werden Robinhood-Instanzen bereitgestellt; sie bestehen aus drei Teilen: dem Load-Balancing-Dienst, einem Proxy und einer Routing-Datenbank

Load-Balancing-Dienst (LBS)

• Das Herzstück von Robinhood
• Zuständig für das Sammeln von Lastinformationen und das Erzeugen von Routing-Informationen mit Endpoint-Gewichten
• Da mehrere Instanzen Routing-Informationen für Dienste gleichzeitig aktualisieren, wird ein interner Shard Manager verwendet, um jedem Dienst einen primären Worker zuzuweisen
• Da jeder Dienst unabhängig ist, kann der LBS pro Dienst partitioniert und horizontal skaliert werden

Proxy

• Zuständig dafür, Lastinformationen von Diensten an die jeweilige LBS-Partition innerhalb des Rechenzentrums weiterzuleiten
• Durch den Einsatz eines Proxys wird auch die Zahl direkter Verbindungen zu LBS-Prozessen reduziert
  • Ohne Proxy müsste sich jeder LBS-Prozess mit allen Knoten in der Infrastruktur verbinden
  • Stattdessen verbinden sich LBS-Prozesse nur mit dem Proxy, wodurch der Speicherdruck auf den LBS deutlich sinkt
• Der Proxy verbindet sich nur mit Knoten innerhalb desselben Rechenzentrums und kann daher horizontal skaliert werden
• Dieses Muster wird in vielen Teilen der Infrastruktur genutzt, um Dienste davor zu schützen, zu viele TLS-Verbindungen empfangen zu müssen

Routing-Datenbank

• Eine auf ZooKeeper/etcd basierende Datenbank, die Routing-Informationen für Dienste speichert, darunter Hostnamen, IP-Adressen und vom LBS erzeugte Gewichte
• ZooKeeper und etcd können alle Watcher in Echtzeit über Änderungen an Nodes/Keys informieren und eignen sich sehr gut für den leseintensiven Service-Discovery-Anwendungsfall von Dropbox
• Die von ZooKeeper/etcd garantierte Eventual Consistency ist auch für Service Discovery ausreichend

Der Load-Balancing-Dienst im Detail

• Ziel des Load Balancing ist es, die Auslastung aller Knoten auf das Niveau der durchschnittlichen Auslastung zu bringen
• Mithilfe eines PID-Controllers wird die Auslastung jedes Knotens nahezu auf dem Niveau der durchschnittlichen Auslastung gehalten
• Der LBS erstellt für jeden Knoten einen PID-Controller und verwendet die durchschnittliche Auslastung als Sollwert
• Der LBS verwendet die Ausgabe des PID-Controllers als Delta für die Endpoint-Gewichte und normalisiert die Gewichte über alle Endpoints eines Dienstes hinweg
• Zwar braucht ein neuer Knoten einige Anpassungsschritte, um sich der durchschnittlichen Auslastung anzunähern, doch PID-Controller sind für Load Balancing sehr effektiv

LBS-Betriebsszenarien

• Der LBS ist darauf ausgelegt, verschiedene Szenarien zu behandeln, die das Load Balancing beeinflussen können — von Serverneustarts bis hin zu fehlenden Lastberichten
• Um optimale Leistung aufrechtzuerhalten, implementiert der LBS mehrere Strategien für den Umgang mit solchen Ausnahmefällen

LBS-Start

• Der LBS hält Lastinformationen und den Zustand der PID-Controller im Speicher
• Bei einem Neustart des LBS werden Gewichte nicht sofort aktualisiert; stattdessen wartet der Dienst kurz, bis Lastberichte eintreffen
• Für die Gewichte der PID-Controller liest der LBS die Endpoint-Gewichte aus der Routing-Datenbank und stellt sie wieder her

Cold-Start-Knoten

• Da regelmäßig neue Knoten einem Service-Fleet beitreten, ist es wichtig, das Thundering-Herd-Problem zu vermeiden
• Da die anfängliche Auslastung neuer Knoten typischerweise 0 ist, setzt der LBS deren Gewicht zunächst auf ein niedriges Endpoint-Gewicht und lässt den PID-Controller den Knoten auf die durchschnittliche Auslastung hochregeln

Fehlende Lastberichte

• In verteilten Systemen sind Ausfälle alltäglich
• Durch Netzwerküberlastung oder Hardwarefehler können Lastberichte einzelner Knoten verspätet eintreffen oder ganz ausbleiben
• Der LBS überspringt solche Knoten bei Gewichtsaktualisierungen, sodass sich ihre Endpoint-Gewichte nicht ändern
• Wenn jedoch viele Lastberichte fehlen, kann die Berechnung der durchschnittlichen Auslastung ungenau werden
• Zur Sicherheit überspringt der LBS in diesem Fall den gesamten Schritt der Gewichtsaktualisierung

Auslastungsmetriken

• Die CPU-Auslastung ist bei Dropbox die am häufigsten verwendete Metrik für Load Balancing
• Für Dienste, die nicht durch CPU limitiert sind, ist die Zahl laufender Requests eine gute alternative Messgröße
• Der LBS unterstützt Load Balancing auf Basis von CPU und/oder laufenden Requests

Einschränkungen

• Der PID-Controller bildet einen Regelkreis, um die Auslastung eines Knotens nahe am Zielwert, also der durchschnittlichen Auslastung, zu halten
• Wenn es kaum Feedback gibt, etwa bei Diensten mit sehr wenig Traffic oder Requests mit sehr hoher Latenz, die in Minuten gemessen wird, ist Load Balancing nicht besonders wirksam
• Dienste mit hochlatenten Requests sollten asynchron sein

Routing zwischen Rechenzentren

• LBS-Instanzen übernehmen das Load Balancing innerhalb eines Rechenzentrums
• Für Routing zwischen Rechenzentren gelten andere Überlegungen
  • So sollen Requests beispielsweise in das nächstgelegene Rechenzentrum geroutet werden, um die Round-Trip-Zeit zu verringern
• Dafür wurde eine Locality-Konfiguration eingeführt, die die Traffic-Aufteilung zwischen Ziel-Rechenzentren definiert

Bewertung der Load-Balancer-Performance

• Die Load-Balancing-Performance wird anhand des Verhältnisses max/avg gemessen
  • Wenn der Service-Owner CPU-basiertes Load Balancing auswählt, wird maxCPU/avgCPU als Leistungskennzahl verwendet
  • Service-Owner provisionieren Services in der Regel anhand der maximalen Auslastung über die Knoten hinweg, da das Hauptziel von Load Balancing darin besteht, die Flottengröße zu reduzieren
• Die Load-Balancing-Strategie mit PID-Controller kann das Verhältnis max/avg nahe bei 1 halten

Grafiken zur Bewertung der Load-Balancing-Performance

• Eine Grafik, die max/avg CPU und p95/avg CPU für den größten Cluster unter den Envoy-Proxy-Clustern zeigt
  • Nach der Aktivierung des PID-Controller-basierten Load Balancing fallen beide Metriken nahe an 1
  • Das Verhältnis max/avg sinkt von 1,26 auf 1,01 und zeigt damit eine Verbesserung um 20 %
• Eine Grafik, die eine Quantilanalyse der CPU-Auslastung pro Knoten zeigt
  • Nach der Aktivierung des PID-Controller-basierten Load Balancing verschmelzen max, p95, avg und p5 fast zu einer einzigen Linie
• Eine weitere Grafik, die max/avg CPU und p95/avg CPU für den größten Cluster unter den Datenbank-Frontend-Clustern zeigt
  • Nach der Aktivierung des PID-Controller-basierten Load Balancing fallen beide Metriken nahe an 1
  • Das Verhältnis max/avg sinkt von 1,4 auf 1,05 und zeigt damit eine Verbesserung um 25 %
• Eine weitere Grafik, die eine Quantilanalyse der CPU-Auslastung pro Knoten zeigt
  • Nach der Aktivierung des PID-Controller-basierten Load Balancing verschmelzen max, p95, avg und p5 erneut fast zu einer einzigen Linie

Gründe für den Aufbau von Config Aggregator

• Robinhood bietet mehrere Optionen, die Service-Owner auswählen können, und kann Änderungen auch dynamisch anwenden
• Service-Owner erstellen und aktualisieren die Robinhood-Konfiguration für ihren Service im Service-Verzeichnis innerhalb der Codebasis
• Diese Einstellungen werden in einem Konfigurationsmanagement-Service gespeichert, einer praktischen Bibliothek, die Änderungen an der Robinhood-Konfiguration in Echtzeit empfängt
• Aufgrund einiger Probleme ist es jedoch nicht möglich, regelmäßig die Mega-Konfiguration von Robinhood aus der Codebasis zu bauen und zu pushen
  • Wenn Änderungen durch einen Konfigurations-Push eingeführt werden, ist es riskant, einfach den Rollback-Button zu drücken
    • Denn es ist nicht bekannt, wie viele andere Services sich seit dem letzten Push geändert haben
  • Das Team, dem Robinhood gehört, trägt außerdem die Verantwortung für jeden Push der Mega-Konfiguration
    • Das bedeutet, dass das Robinhood-Team an jedem Push geänderter Konfigurationen beteiligt sein muss, was Verschwendung von Engineering-Zeit ist
    • Denn die meisten Incidents können von den Service-Ownern gelöst werden
  • Um potenzielle Risiken zu minimieren, dauert jeder Push mehrere Stunden, um über mehrere Rechenzentren hinweg ausgerollt zu werden
• Um diese Probleme zu lösen, wurde ein weiterer kleiner Service namens Config Aggregator gebaut

Config Aggregator

• Config Aggregator sammelt alle dienstspezifischen Konfigurationen und erstellt die Mega-Konfiguration, die vom LBS verwendet wird
• Config Aggregator überwacht dienstspezifische Konfigurationen und propagiert Änderungen in Echtzeit in die Mega-Konfiguration
• Config Aggregator bietet auch eine Tombstone-Funktion, um zu verhindern, dass die Robinhood-Konfiguration eines Service versehentlich gelöscht wird
  • Wenn ein Service-Owner eine Änderung pusht, die einen Service aus der Robinhood-Konfiguration entfernt, markiert Config Aggregator den Service-Eintrag mit einem Tombstone, anstatt ihn sofort zu entfernen
  • Die tatsächliche Entfernung erfolgt erst einige Tage später
  • Diese Funktion löst auch Race Conditions, die durch unterschiedliche Push-Zyklen zwischen der Robinhood-Konfiguration und anderen Routing-Konfigurationen (z. B. Envoy-Konfiguration) entstehen können
• Ein Nachteil des Konfigurationsmanagement-Service ist, dass er derzeit nicht versioniert ist
• Für den Fall, dass die LBS-Konfiguration auf einen bekannten guten Zustand zurückgesetzt werden muss, wird die Mega-Konfiguration regelmäßig gesichert

Migrationsstrategie

• Es kann riskant sein, die Load-Balancing-Strategie auf einmal umzustellen
• Deshalb erlaubt Robinhood, mehrere Load-Balancing-Strategien für einen Service zu konfigurieren
• Dropbox verfügt über percent-basierte Feature Gates, daher wurde eine Mischstrategie implementiert, bei der der Client die gewichtete Summe der von zwei Load-Balancing-Strategien erzeugten Gewichte als Endpoint-Gewicht verwendet
• Dadurch ist eine schrittweise Migration zur neuen Load-Balancing-Strategie möglich, wobei alle Clients dieselbe Gewichtungszuweisung für Endpoints sehen

Erkenntnisse

• Beim Entwurf und der Implementierung von Robinhood wurden einige zentrale Lehren darüber gewonnen, was gut funktioniert und was nicht
• Durch die Priorisierung von Einfachheit, die Minimierung von Client-Änderungen und die Planung der Migration von Anfang an konnten Entwicklung und Ausrollung des LBS vereinfacht und kostspielige Fallstricke vermieden werden

Konfiguration sollte so einfach wie möglich sein

• Robinhood führte viele Optionen ein, die von Service-Ownern konfiguriert werden können
• In den meisten Fällen benötigen sie jedoch nur die bereitgestellten Standardeinstellungen
• Eine gute und einfache Standardkonfiguration (oder noch besser gar keine Konfiguration) kann enorm viel Engineering-Zeit sparen

Auch Client-Änderungen sollten einfach gehalten werden

• Das Rollout von Änderungen an interne Clients kann Monate dauern
  • Die meisten Deployments werden wöchentlich gepusht, viele aber nur einmal im Monat oder über Jahre hinweg gar nicht
• Je mehr Änderungen in das LBS verlagert werden können, desto besser
  • Zum Beispiel wurde früh entschieden, im Client-Design Weighted Round Robin zu verwenden, und dies wurde seitdem nicht mehr geändert
  • Das hat die Umsetzung deutlich beschleunigt
• Wenn die meisten Änderungen auf das LBS beschränkt werden, sinkt auch das Stabilitätsrisiko
  • Denn Änderungen am LBS können bei Bedarf innerhalb weniger Minuten zurückgerollt werden

Migration sollte in der Projektentwurfsphase geplant werden

• Migration erfordert enorm viel Engineering-Zeit
• Es gibt auch Stabilitätsrisiken, die berücksichtigt werden müssen
• Es ist keine besonders spannende, aber eine wichtige Aufgabe
• Beim Entwurf eines neuen Service sollte so früh wie möglich darüber nachgedacht werden, wie bestehende Anwendungsfälle reibungslos auf den neuen Service migriert werden können
• Je mehr von den Service-Ownern verlangt wird, desto mehr wird die Migration zum Albtraum
  • Das gilt insbesondere für grundlegende Infrastrukturkomponenten
• Da der Migrationsprozess von Robinhood nicht von Anfang an gut entworfen war, wurde deutlich mehr Zeit als erwartet für die Neuimplementierung des Prozesses und die Neugestaltung der Konfiguration aufgewendet
• Die für die Migration benötigte Engineering-Zeit sollte eine zentrale Erfolgskennzahl sein

Die Wirkung von Robinhood

• Nach etwa einem Jahr in der Produktionsumgebung lässt sich sagen, dass die neueste Iteration von Robinhood die langjährigen Load-Balancing-Herausforderungen von Dropbox effektiv gelöst hat
• Der zentrale PID-Controller-Algorithmus zeigte vielversprechende Ergebnisse und erhebliche Performance-Verbesserungen bei den größten Services
• Es wurden wertvolle Erkenntnisse über den Entwurf und Betrieb eines Load-Balancing-Service im Maßstab von Dropbox gewonnen

Fußnoten

1. Seien N, M und s jeweils die Anzahl der Server, die Anzahl der Clients und die Größe der Teilmenge von Adressen. Die Anzahl der Clients, mit denen ein Server verbunden wird, folgt einer Stichprobe aus der Binomialverteilung B(M, s/n). Wie bereits erwähnt, führen Clients einfaches Round Robin über die von der Service Discovery bereitgestellte Adressmenge aus. Wenn also jeder Client ungefähr dieselbe Menge an Requests sendet, ähnelt die Lastverteilung auf Serverseite einer Binomialverteilung.

2. Das bestehende Service-Discovery-System wird erweitert, um das gRPC-xDS-Protokoll (A27) zu unterstützen. Zum Zeitpunkt der Veröffentlichung dieses Blogposts unterstützen gRPC-Clients kein Weighted Round Robin für Endpoint-Gewichte aus der Control Plane, daher wurde ein benutzerdefinierter Weighted-Round-Robin-Picker auf Basis von Earliest-Deadline-First-Scheduling implementiert.

3. Es gab einen interessanten Fall, in dem ein Service gelegentlich durch I/O mit verschlechterter Performance blockiert wurde. In einer solchen Situation bleibt die CPU auf dem betroffenen Knoten niedrig, und das LBS beginnt, das Gewicht des Knotens zu erhöhen, um die CPU auf den Durchschnitt anzuheben, was zu einer Todesspirale führt. Als Lösung wurde der Maximalwert aus CPU und laufenden Requests als Lastmesswert verwendet, um den Service auszubalancieren.

Meinung von GN⁺

• Robinhood wirkt wie ein hervorragender Dienst, der die Load-Balancing-Herausforderungen von Dropbox effektiv gelöst hat. Besonders beeindruckend ist der Einsatz eines PID-Controllers.
• Dies ist ein gutes Beispiel dafür, wie schwierig Load Balancing in einer globalen Infrastruktur sehr großer Größenordnung ist. Es gibt viele Faktoren zu berücksichtigen, etwa Hardware-Unterschiede, ungleichmäßige Lastverteilung und Netzwerküberlastung.
• Wichtig erscheint, dass alle Komponenten so entworfen sind, dass sie organisch miteinander verbunden funktionieren. LBS, Proxy und Routing-DB sind getrennt, interagieren aber in Echtzeit eng miteinander.
• Beeindruckend sind die Diagramme, die die Load-Balancing-Performance quantitativ bewerten und Verbesserungen visualisieren. Sie zeigen besonders gut, dass es für die Optimierung der Fleet-Größe wichtig ist, das Verhältnis von max/avg nahe bei 1 zu halten.
• Auch die Einführung des Config Aggregator zur Trennung dienstspezifischer Konfigurationen wirkt wie eine gute Idee. So können Service-Verantwortliche ihre Änderungen unabhängig verwalten.
• Auch Schutzmechanismen wie tombstone sind ein sorgfältig durchdachtes Detail. Es ist wichtig, versehentliche Löschungen von Konfigurationen zu verhindern.
• Die Lehren zur Migrationsstrategie wirken ebenfalls nützlich. Wenn Migrationen nicht von Anfang an berücksichtigt werden, kostet das später viel Zeit.
• Insgesamt wirkt Robinhood wie eine systematische und ausgereifte Lösung für Load Balancing in der Größenordnung von Dropbox. Auch andere Unternehmen mit großer Infrastruktur können sich daran orientieren.

Ähnliche Lösungen:

• AWS Elastic Load Balancing (ELB) und Google Cloud Load Balancing bieten ebenfalls gemanagte Dienste für Load Balancing in großem Maßstab an.
• Kubernetes verfügt zwar über einen eigenen Load Balancer (kube-proxy), doch mit Service-Mesh-Lösungen wie Istio oder Linkerd lassen sich leistungsfähigere Funktionen für Load Balancing und Traffic-Management nutzen.
• Auch Netflix Zuul und Lyft Envoy bieten proxybasiertes Load Balancing.

Worauf man bei der Einführung achten sollte:

• Die Kompatibilität mit der bestehenden Infrastruktur und den vorhandenen Services muss geprüft werden. Falls eine Migration nötig ist, sollte dafür eine Strategie erstellt werden.
• Die Auswirkungen auf Performance und Stabilität sollten ausreichend getestet und überwacht werden. Fehler in der Load-Balancing-Logik können kritisch sein.
• Unter Berücksichtigung der Teamfähigkeiten sollte über Umfang und Geschwindigkeit der Einführung entschieden werden. Statt einer vorschnellen flächendeckenden Einführung ist ein schrittweises Vorgehen sinnvoller.
• Langfristig sind kontinuierliche Optimierung und Verbesserung erforderlich. Maßnahmen wie das situationsgerechte Tuning von Load-Balancing-Algorithmen und das Beseitigen von Engpässen werden hilfreich sein.

[kbumsik]

Es ist interessant, im Softwarebereich von einem PID-Regler zu hören, haha.