Ein guter Tag für trie-hard: 1 % Rechenleistung sparen

Motivation

• Das globale Netzwerk von Cloudflare verarbeitet mehr als 60 Millionen HTTP-Anfragen pro Sekunde
• Mit einer neuen Open-Source-Rust-Crate wurde die CPU-Auslastung gesenkt und die Verarbeitungskapazität des CDN verbessert
• Pingora ist der Kern von Cloudflares Rust-basiertem Proxy-Dienst und wurde als Open Source veröffentlicht
• Der Dienst Pingora-origin übernimmt die Weiterleitung von Nutzeranfragen an das tatsächliche Ziel
• Wenn Anfragen Cloudflare verlassen, müssen interne Informationen entfernt werden
• Dieser Vorgang tritt sehr häufig auf und macht 1,7 % der CPU-Auslastung aus

Benchmarking

• Mit der Rust-Crate Criterion wurde die Performance der Funktion im Nanosekundenbereich gemessen
• Die ursprüngliche Funktion clear_internal_headers benötigte im Durchschnitt 3.65µs

Weniger Lesezugriffe

• Die Richtung beim Entfernen der Header wurde umgekehrt, um die Anzahl der Lesezugriffe zu verringern
• Dadurch verbesserte sich die Laufzeit der Funktion von 3.65µs auf 1.53µs
• Die CPU-Auslastung sank von 1.71 % auf 0.717 %

Suche in Datenstrukturen

• Es wurde versucht, interne Header mit einer HashMap zu speichern und nachzuschlagen
• Die Lesezeit der HashMap ist linear proportional zur Schlüssellänge
• Auch andere Datenstrukturen wie sortierte Mengen oder Zustandsmaschinen wurden ausprobiert
• Eine Implementierung mit regulären Ausdrücken war doppelt so langsam wie die HashMap

Einsatz eines Trie

• Ein Trie ist eine Baumdatenstruktur, die für Präfixsuchen oder Autovervollständigungssysteme verwendet wird
• Ein Trie kann schnell erkennen, wenn ein String nicht enthalten ist
• Bestehende Trie-Implementierungen waren langsamer als die HashMap
• Cloudflare entwickelte daher eine eigene optimierte Trie-Implementierung namens trie-hard

Trie Hard

• trie-hard speichert Knotenbeziehungen in den Bits von Integern und nutzt zusammenhängenden Speicher, um die Geschwindigkeit zu erhöhen
• Die Laufzeit der Funktion clear_internal_headers wurde auf 0.93µs reduziert
• Die CPU-Auslastung sank von 1.71 % auf 0.43 %
• In der tatsächlichen Produktionsumgebung entsprach die Performance von trie-hard den Benchmark-Ergebnissen

Fazit

• Es ist wichtig, langsame Teile des Codes zu identifizieren und zu optimieren
• Viele kleine Optimierungen können zusammen große Performancegewinne bringen
• Cloudflares Connectivity Cloud bietet Funktionen wie Netzwerkschutz, Beschleunigung von Internetanwendungen und Abwehr von DDoS-Angriffen

Zusammenfassung von GN⁺

• Cloudflare senkte mit einer neuen Open-Source-Rust-Crate die CPU-Auslastung und steigerte die Verarbeitungskapazität seines CDN
• Durch die Optimierung der Entfernung interner Header im Dienst Pingora-origin wurde die CPU-Auslastung um 1.28 % gesenkt
• Mit trie-hard entwickelte das Unternehmen eine eigene optimierte Trie-Implementierung und verbesserte die Performance deutlich
• Der Artikel unterstreicht die Bedeutung von Code-Optimierung und der Wahl geeigneter Datenstrukturen und zeigt, dass kleine Optimierungen große Performancegewinne bringen können
• Ähnliche Projekte mit vergleichbarer Funktionalität sind unter anderem NGINX und HAProxy

[GN⁺]

Hacker-News-Kommentare

• Es gab verschiedene Vermutungen darüber, wie Cloudflare interne Header speichert und entfernt

  • Verwendung eines separaten Wörterbuchs oder einer eigenen Datenstruktur
  • Ein einzelner Header, der sämtliche internen Metadaten enthält
  • Präfixe für alle Header, wobei interne mit „I“ und externe mit „E“ beginnen
  • Alle internen Header beginnen mit "CFInt"
  • Nicht erwartet wurde, dass Header aus einer bestimmten Liste als interne Header behandelt werden
  • Das Web ist bereits voller mehrdeutiger Signale und Header-Bezeichnungen
  • Es wirkt seltsam, dass ein großes Unternehmen wie Cloudflare einen Mechanismus verwendet, bei dem solche Fehler leicht auftreten können

• Das Abbilden von UTF-8-Zeichen auf eine Bitmaske erschien zunächst ineffizient

  • Mit 32 Bit lassen sich a-z und sechs Sonderzeichen unterbringen
  • Mit 64 Bit lassen sich Großbuchstaben A-Z und sechs Sonderzeichen unterbringen
  • Das bietet genug Raum für HTTP-Header und ermöglicht schnelle Matching-Algorithmen
  • Diese Technik ist ein Bloom Filter
  • Sie wurde in den 1970er Jahren entwickelt, als Ressourcen knapp waren, ist aber weiterhin nützlich

• Zweifel daran, ob Cloudflares Optimierung den Aufwand wert ist

  • Etwa 500 CPU-Kerne wurden eingespart
  • Die Kosten bei Cloudflare sind unbekannt, aber es dürfte sich um Einsparungen in Höhe von einigen Zehntausend Dollar handeln
  • Fraglich ist, ob dafür ein positiver ROI beim Engineering zu erwarten ist
  • Möglicherweise wäre es besser, den Filter bereits beim Deserialisieren anzuwenden, damit die Header gar nicht erst erzeugt werden

• Kein tiefes Wissen über die Optimierung von Datenstrukturen, aber überraschend, dass Hash-Tabellen so schnell verworfen wurden

  • Beim Durchsuchen statischer Tabellen hätte eine Hash-Tabelle wohl schneller sein können

• Verwendung einer fancy Datenstruktur, um zu entfernende Einträge zu organisieren und sie dann anhand dessen aus der Header-Map zu entfernen

  • Ein Code-Link zur beteiligten remove_header-Aufrufstelle wurde bereitgestellt

• Endlich mal ein Blogpost mit einem Trie

  • Die ganzen Trie-Aufgaben waren also doch nicht umsonst

• Neugier, ob ein kleiner Bloom Filter ausprobiert wurde

  • Eine schnelle Faltung über die Header-Keys und ein Bloom-Filter-Test könnten das Durchlaufen des Trie vermeiden

• Neugier, ob bei einer statischen Menge von Einträgen eine perfekte Hash-Tabelle ausprobiert wurde

  • Das könnte auf einige arithmetische Operationen und einen einzelnen String-Vergleich reduziert werden

• Die Optimierung ist interessant

  • Fraglich ist, ob sich Header beim Erzeugen der Anfrage als intern markieren ließen
  • Das Filtern bei der Ausgabe würde dadurch einfacher werden

• Neugier, warum das regex-Crate nicht besser funktionierte

  • Es sollte Suchen nach mehreren Literal-Strings in einen Aho-Corasick-Automaten kompilieren