Cloudflare konnte nach einer Neugestaltung eines Teils des Algorithmus zur Anforderungsverteilung im Dienst Pingora Backend Router (PBR) weltweit mehr als 100 Terabyte RAM zurückgewinnen. Die Verbesserung ergab sich aus einer Kombination aus der komprimierten Darstellung der Hash-Punkte, der auf statistischen Analysen basierenden Reduzierung ihrer Anzahl und einer schrittweisen Umstellung, die die Stabilität des Caches und des Datenverkehrs zu den Origin-Servern bewahrte.
Das Problem bei der Anforderungsverteilung
Cloudflare verwendet die Bibliothek pingora-ketama zur Implementierung von Consistent Hashing. Diese Methode hilft dabei, cachefähige Anfragen nach Möglichkeit an denselben Server zu leiten. Dadurch kann eine einzige Kopie der Datei im Rechenzentrum vorgehalten und ein stabiler Zugriffsweg bereitgestellt werden.
Die Verwendung eines einzigen Hash-Punkts pro Server kann jedoch zu erheblichen Unterschieden bei der Größe der Bereiche führen, die die Server auf dem Hash-Ring besitzen, und damit zu einer unterschiedlichen Arbeitslast. Deshalb verwendet Pingora eine große Anzahl virtueller Hashes pro Server mit Gewichten, die an die Speicherkapazität gekoppelt sind. Außerdem werden separate Ringe für verschiedene Gruppen von Eigenschaften und Einschränkungen erstellt. Die Ansammlung dieser Ringe führte in einigen Fällen zu einem Speicherverbrauch von bis zu 6 Gigabyte pro Prozess.
Verbesserung der Datendarstellung und Reduzierung der Hashes
Jedes Element, das einen Punkt auf dem Ring darstellte, bestand aus einem 32 Bit großen Hash-Wert und einem 32 Bit großen Index auf den Server, also aus acht Bytes im Speicher. Das Cloudflare-Team stellte fest, dass der Index in der Praxis nicht mehr als 16 Bit benötigt, da der Dienst nicht mehr als etwa 65.000 Server gleichzeitig koordinieren würde.
Die Verkleinerung des Index-Typs allein reichte wegen der Ausrichtungsregeln in Rust jedoch nicht aus, da die Struktur weiterhin acht Bytes groß geblieben wäre. Deshalb speicherte Cloudflare den Wert und den Index in einem sechs Byte großen Raw-Array und ergänzte Funktionen für den Zugriff auf beide. Diese Änderung senkte den Speicherverbrauch der Hash-Struktur um 25 %.
Der größte Gewinn ergab sich jedoch aus der Überprüfung der Anzahl der Hashes. Der Dienst verwendete einen Basiswert von 160 Punkten pro Server, der mit dem an die Speicherkapazität gekoppelten Servergewicht multipliziert wurde. Die Analyse zeigte, dass große Erhöhungen der Hash-Anzahl nur abnehmende Verbesserungen beim Fehlerbereich bringen. Im von Cloudflare besprochenen Beispiel senkte das Hinzufügen der letzten 90.000 Hashes den Fehler lediglich um etwa 0,7 %.
Da Hash-Werte mit einer Größe von 32 Bit außerdem bei steigender Punktzahl mit höherer Wahrscheinlichkeit kollidieren, können sie einen unerwarteten Fehler in der Verteilung verursachen. Auf Grundlage von Berechnungen und Simulationen reduzierte Cloudflare die Anzahl der Hashes pro Server um 90 %, ohne den Fehler merklich zu erhöhen, was zu den endgültigen Einsparungen beitrug.
Was ändert sich in der Praxis?
Den Hash-Ring im gesamten Netzwerk auf einmal auszutauschen, war keine sichere Option, da dadurch die Anfragen neu verteilt und praktisch ein großer Teil der Cache-Effektivität verloren gegangen wäre. Zudem hätte dies den Datenverkehr zu den Origin-Servern erhöhen können. Deshalb behielt PBR vorübergehend sowohl den alten als auch den neuen Ring im Speicher und wählte für jede Anfrage zwischen ihnen, wodurch ein klarer Rückfallpfad geschaffen wurde.
Die Umstellung wurde schrittweise durchgeführt, beginnend mit kleinen Teststandorten und anschließend größeren Rechenzentren. Außerdem wurde die Steuerung des Anteils der Anfragen, die den neuen Ring verwenden, von der Festlegung der zur Teilnahme berechtigten Rechenzentren getrennt. Cloudflare überwachte die Auswirkungen der Serverauswahl, die Ringversionen, Verbindungsfehler, den Speicherverbrauch, die Startzeit, das Cache-Verhalten und den Datenverkehr zu den Origin-Servern, bevor der alte Pfad entfernt wurde.
Die technische Bedeutung
Das Experiment zeigt, dass sich Optimierungen auf niedriger Ebene, etwa die Wahl der Größe eines Feldes innerhalb einer Datenstruktur oder die Bestimmung einer geeigneten Anzahl von Hash-Punkten, bei ihrer Anwendung auf ein Netzwerk mit Tausenden von Servern erheblich auswirken können. Gleichzeitig bedeutet das Ergebnis nicht, dass eine Speicherreduzierung in jedem System sicher ist. Die Genauigkeit der Verteilung, die Kollisionswahrscheinlichkeiten, Servergewichte, Einschränkungen durch Features und die Art der Umstellung sind alles Faktoren, die vor einer Änderung gemessen werden müssen.
Die Änderungen sind im Paket pingora-ketama über ein derzeit nicht veröffentlichtes Cargo-Feature verfügbar. Version v2 unterstützt das komprimierte Speicherformat, eine schnellere Sortiermethode und die Möglichkeit, die Basisanzahl der Hashes festzulegen. Gleichzeitig bleibt Version v1 erhalten, und beide Ringe können gemeinsam betrieben werden, wobei die Entscheidung auf Anfrageebene getroffen wird.