Ein guter Tag für trie-hard: 1 % Compute einsparen
(blog.cloudflare.com)- Cloudflare hat die Open-Source-Rust-Crate trie-hard veröffentlicht, um die CPU-Nutzung des Rust-basierten Proxys Pingora in einem Netzwerk zu senken, das im Durchschnitt mehr als 60 Millionen HTTP-Requests pro Sekunde verarbeitet
- Der Engpass lag in der Funktion
clear_internal_headersvonpingora-origin: Sie entfernt bei nicht gecachten Requests, die Cloudflare verlassen, Header für internes Routing, Messung und Optimierung und läuft auf einem Pfad mit 35 Millionen Requests pro Sekunde - Die bisherige Implementierung versuchte, bei jedem Request mehr als 100 interne Header zu entfernen, benötigte dafür im Schnitt 3,65 µs und verbrauchte 1,71 % der gesamten CPU-Zeit von
pingora-origin– bei 40.000 compute-seconds/s entspricht das rund 680 CPU-Kernen - Ein Ansatz, zuerst die tatsächlichen Request-Header zu durchlaufen, war mit durchschnittlich 1,53 µs 2,39-mal schneller, senkte die gesamte CPU-Nutzung theoretisch aber nur um 0,993 %, sodass eine bessere Suchstruktur nötig war
- Die neue trie-Implementierung reduzierte die durchschnittliche Laufzeit auf 0,93 µs; auch beim Sampling im Produktionseinsatz seit Juli 2024 sank die tatsächliche CPU-Nutzung von
clear_internal_headersauf 0,34 %
Die Kosten, die Cloudflare senken wollte
- Das globale Netzwerk von Cloudflare verarbeitet im Durchschnitt mehr als 60 Millionen HTTP-Requests pro Sekunde
- Diese Optimierung begann bei Pingora, dem Kern des Rust-basierten Proxy-Dienstes, und beim darauf laufenden Produktionsdienst
pingora-origin pingora-originist für den letzten Schritt zuständig, bei dem nicht gecachte Requests von Nutzern an den eigentlichen Zielserver, den Origin, gesendet werden- Bevor ein Request die Cloudflare-Infrastruktur verlässt, muss dieser Dienst Informationen aus den Headern entfernen, die für internes Routing, Messungen und Optimierungen verwendet wurden
- Weltweit verlassen zum Zeitpunkt der Veröffentlichung 35 Millionen Requests pro Sekunde
pingora-origin
Engpassfunktion: clear_internal_headers
- Die betroffene Funktion liegt auf einem sehr heißen Pfad und wird für jeden Request ausgeführt
// PERF: heavy function: 1.7% CPU time
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
INTERNAL_HEADERS.iter().for_each(|h| {
request_header.remove_header(h);
});
}
- Allein diese kleine Funktion nutzt mehr als 1,7 % der gesamten CPU-Zeit von
pingora-origin - Die gesamte CPU-Zeit von
pingora-originbeträgt 40.000 compute-seconds pro Sekunde – eine Größenordnung, als würden 40.000 voll ausgelastete CPU-Kerne nur diesen Dienst ausführen - Davon werden 1,7 %, also etwa 680 CPU-Kerne, allein für die Auswertung von
clear_internal_headersaufgewendet
Basismessung und erste Verbesserung
- Für die Performance-Messung wurde die Rust-Crate criterion verwendet
- Criterion aggregiert mehrere isolierte Ausführungen, misst die Laufzeit von Rust-Code im Nanosekundenbereich und liefert auch Feedback zu Performance-Verbesserungen und -Regressionen über die Zeit
- Die Benchmark-Eingaben bestanden aus einer großen synthetischen Request-Menge, in der interne und nicht interne Header gleichmäßig verteilt waren
- Die durchschnittliche Laufzeit des bisherigen
clear_internal_headerswurde mit 3,65 µs gemessen -
Suchrichtung umkehren
- Der bisherige Code führt für jeden Eintrag in der internen Header-Liste
request_header.remove_header(h)aus; bei mehr als 100 internen Headern bedeutet das mehr als 100 Prüfungen pro Request - Da ein durchschnittlicher Request mit 10 bis 30 deutlich weniger Header als 100 hat, reduziert es die Anzahl der Lesezugriffe, die tatsächlichen Request-Header zu durchlaufen und sie in der Menge interner Header nachzuschlagen
- In Rusts
http::HeaderMapgibt es noch keinretain, daher müssen die zu entfernenden internen Header in einem separaten Schritt gesammelt und anschließend gelöscht werden - Allein diese Änderung senkte die durchschnittliche Laufzeit von 3,65 µs auf 1,53 µs und machte sie 2,39-mal schneller
- Theoretisch sinkt die gesamte CPU-Nutzung von 1,71 % auf 0,717 %; die Einsparung beträgt 0,993 %
- Der bisherige Code führt für jeden Eintrag in der internen Header-Liste
Suche nach einer besseren Suchdatenstruktur
- Nach dem Umkehren der Suchrichtung konnte ausgewählt werden, in welcher Datenstruktur die statische Liste interner Header gespeichert wird
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
let to_remove = request_header
.headers
.keys()
.filter_map(|name| INTERNAL_HEADER_SET.get(name))
.collect::<Vec<_>>();
to_remove.into_iter().for_each(|k| {
request_header.remove_header(k);
});
}
- Der erste Versuch war
std::HashMap, doch das Hashing von String-Schlüsseln muss jedes Byte lesen und ist daher zwar in Bezug auf die Tabellengröße konstant, aber in Bezug auf die Schlüssellänge L linear - Ziel war es, eine Datenstruktur zu finden, deren Leseverhalten in Bezug auf die Schlüssellänge besser als O(L) ist
-
Geprüfte Alternativen
- Sortierte Mengen wie
BTreeSetverwenden vergleichsbasierte Suche und bieten in Bezug auf die Schlüssellänge ein Verhalten von O(log(L)), benötigen aber auch logarithmische Zeit in Bezug auf die Größe der Menge - Auch die schnelle sortierte Menge FST war im Benchmark etwa 50 ns langsamer als die Standard-Hashmap
- Zustandsmaschinen wie Parser oder reguläre Ausdrücke nehmen Eingaben schrittweise entgegen und entscheiden bei jedem Schritt, ob die Auswertung fortgesetzt wird; dadurch können nicht übereinstimmende Strings schnell erkannt werden
- Da es pro Request im Durchschnitt nur 1 bis 2 interne Header gibt, passt das gut zu einer Situation, in der negative Fälle überwiegen
- Eine
clear_internal_headers-Implementierung mit regulärem Ausdruck dauerte etwa 2-mal so lange wie die Hashmap-basierte Lösung, war aber angesichts dessen, dass dieses Werkzeug nicht für rohe Geschwindigkeit bekannt ist, ein schnelles Ergebnis
- Sortierte Mengen wie
Warum ein trie passt
- Ein trie ist eine Baumdatenstruktur, die häufig für Präfixsuchen oder Autovervollständigung in bekannten String-Mengen verwendet wird
- Jeder Knoten eines trie steht für einen Teilstring, der in der ursprünglichen String-Menge vorkommt, und die Verbindungen zwischen Knoten stehen für Zeichen, die auf ein bestimmtes Präfix folgen können
- Ausgehend vom Wurzelknoten lässt sich der Suchraum bereits ab den möglichen ersten Zeichen verkleinern, sodass nicht enthaltene Strings schnell ausgeschlossen werden können
- Ein trie-Lesezugriff bietet für nicht übereinstimmende Fälle ein Verhalten von O(log(L)), während übereinstimmende Fälle weiterhin O(L) bleiben
- Da mehr als 90 % der Request-Header keine internen Header sind, eignet sich diese Anwendung gut für einen Use Case mit vielen Nichttreffern
-
Grenzen bestehender trie-Implementierungen
- Mehrere trie-Implementierungen von crates.io wurden benchmarked, doch die Ergebnisse blieben hinter den Erwartungen zurück
- Die meisten tries sind auf Use Cases wie Autovervollständigung bei Tastaturereignissen ausgelegt; die Optimierung heißer Pfade mit zig Millionen Requests pro Sekunde hat dort keine Priorität
- Die schnellste gefundene bestehende Implementierung war radix_trie, sie war aber immer noch 1 µs langsamer als die Hashmap
- Daher wurde schließlich eine neue trie-Implementierung speziell für diesen Use Case geschrieben
trie-hard und Ergebnisse in Produktion
-
Cloudflare hat die neue Open-Source-Rust-Crate trie-hard veröffentlicht
-
trie-hardgewinnt Geschwindigkeit, indem es Knotenbeziehungen in den Bits vorzeichenloser Integer speichert und den gesamten Baum in einem zusammenhängenden Speicherblock hält -
Im Benchmark senkte
trie-harddie durchschnittliche Laufzeit vonclear_internal_headersauf 0,93 µs -
Die erwartete CPU-Nutzung liegt bei 0,43 %; gegenüber den bisherigen 1,71 % entspricht das einer Reduzierung der gesamten Compute-Nutzung von
pingora-originum 1,28 % -
Tatsächliche Sampling-Ergebnisse
trie-hardläuft seit Juli 2024 in Produktion- Die Performance-Messung wurde über statistisches Sampling von Stack Traces im Zeitverlauf erhoben
- Aus dem Anteil der Samples, die eine bestimmte Funktion enthalten, wird die CPU-Nutzung dieser Funktion geschätzt
- Die Produktions-Sampling-Ergebnisse liegen im Großen und Ganzen nahe an den Vorhersagen der lokalen Benchmarks
Implementierung Stack-Trace-Samples mit clear_internal_headersTatsächliche CPU-Nutzung Vorhergesagte CPU-Nutzung Original 19 / 1111 1,71 % n/a Hashmap 9 / 1103 0,82 % 0,72 % trie-hard 4 / 1171 0,34 % 0,43 %
Fazit aus Betriebssicht
- Bevor man eine neue Datenstruktur schreibt, muss man wissen, wo der Code wie stark langsam ist
- Flame Graphs, Profiling- und Benchmarking-Tools helfen, selbst bei Funktionen im Mikrosekundenbereich sinnvolle Einsparungen zu finden
- Eine bereits sehr kurze Operation zu optimieren mag nebensächlich wirken, doch bei zig Millionen Requests pro Sekunde summieren sich kleine Verbesserungen und senken die gesamte Compute-Nutzung
1 Kommentare
Hacker-News-Meinungen
Wenn man mich gebeten hätte, grob zu raten, wie Cloudflare interne Header speichert und entfernt, hätte ich wohl an ein separates Dictionary oder eine Datenstruktur gedacht, an einen einzelnen Header, der sämtliche internen Metadaten enthält, an eine Trennung von intern/extern per Präfix oder an ein Präfix wie
CFIntAuf die Idee, Header-Namen aus einer bestimmten Liste als interne Header zu behandeln, wäre ich vermutlich nicht gekommen. Da stellen sich Fragen wie: Was passiert, wenn jemand anderes denselben Namen verwendet? Was, wenn beim Aufräumen etwas vergessen wird? Was, wenn gleichzeitig laufende Programme unterschiedliche Listen haben? Was, wenn der
Connection-Header auf einen internen Cloudflare-Header verweist? Was, wenn der Differenzmengen-Algorithmus langsam ist?Das Web ist ohnehin schon voll von nervig uneindeutigen In-Band-Signalen und Header-Benennungen; dass ein Unternehmen in Cloudflares Größenordnung intern einen so umständlichen und fehleranfälligen Mechanismus nutzt, fühlt sich seltsam an
cf-cache-statusEinschließlich des beidseitigen Entfernens interner Header am Edge-Proxy, also auch inbound
Der Listenansatz hat Nachteile, aber auch viele Vorteile. Wenn potenzielle Schwächen dieses Ansatzes angesprochen werden, scheint oft die Geschichte und die Komplexität zu fehlen, die bei Cloudflares Größenordnung entstanden sind. Eine Aufzählungsliste ist der einfachste und flexibelste Ansatz und erfordert keine vorherige Einigung über die Struktur von Header-Keys. Angesichts der Zahl der Teams bei Cloudflare, möglicher Technologieübernahmen usw. dürfte das wichtig gewesen sein
Wenn man sie vorab befüllt, kombiniert man diese Ideen im Grunde und fixiert die Zahl der internen Header pro Anfrage. Ab diesem Punkt kann man eine verkettete Hash-Tabelle verwenden, die die Erzeugungsreihenfolge bewahrt, und in der finalen Liste, die an den Client zurückgeht, einfach die ersten N Einträge entfernen
Ich habe kurz über den Effekt nachgedacht, UTF-8-Zeichen auf eine Bitmaske abzubilden, und zunächst wirkte das nicht besonders clever. Dann wurde mir klar, dass 32 Bit
a-zplus 6 Sonderzeichen aufnehmen können und 64 Bit zusätzlich GroßbuchstabenA-Zplus weitere 6 SonderzeichenFür HTTP-Header ist das ausreichend Platz, und wenn man nur ein paar Integer maskieren und vergleichen muss, ergibt das einen sehr schnellen Matching-Algorithmus. Welches Zeichen welchem Bit entspricht, ist ebenfalls nur ein Lookup in einer 256-Wort-Tabelle
Was der Autor ausgelassen hat: Technisch gesehen ist diese Technik ein Bloom-Filter. Interessant daran ist, dass es sich um eine Optimierung aus einer Zeit handelt, in der Rechenressourcen viel stärker begrenzt waren als heute, in diesem Fall von 1970, und dass dieselbe alte Optimierung noch immer irgendwo in der realen Welt eingesetzt wird
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardund einem Bloom-Filter gibt es einen großen Unterschied. Bloom-Filter sind probabilistisch und verwenden Hashing. Sie sind gut, wenn man seltene False Positives akzeptieren kann, aber keine False Negatives haben darf; das ist hier jedoch nicht gefragt. Hier braucht man Korrektheit, und das Hashing selbst ist der Schritt, den es zu schlagen giltDas hier ist eher eine verbesserte Version oder Variante des Liang-Algorithmus, der in TeX zum Speichern des Hyphenation-Wörterbuchs verwendet wurde. Die Arbeit behandelt Blooms Algorithmus als „superimposed coding“ und erinnert stark an eine Zeit, in der Speicher die knappste Ressource war. Könnte dir gefallen ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Die Daten, die zur Belegung des Vorteils vorgelegt wurden, haben tatsächlich zu wenig Power, um das zu zeigen. Die Stichprobe ist nicht groß genug
Eine sehr einfache Analyse in R wäre
prop.test(c(9, 4), c(1103,1171)), und beim Test auf Gleichheit zweier Anteile mit Kontinuitätskorrektur ergibt sich ein p-Wert von 0,222Ein p-Wert von 0,22 liegt nicht unter der magischen 0,05, und das 95-%-Konfidenzintervall deutet darauf hin, dass der Trie in Wirklichkeit sogar etwas schlechter sein könnte
Die Vorabanalyse lässt vermuten, dass der Trie besser sein dürfte, und es gibt auch schwache Evidenz dafür, aber es wäre besser, eine deutlich größere Stichprobe zu ziehen, um sicherer zu wissen, wie viel besser er ist
Wenn das Ziel eine Performance-Analyse ist, wirkt es seltsam, die Zahl der Vergleiche in Big-O-Notation zu beschreiben. Ein Vergleich kostet etwa 1 Zyklus, und mit Instruction-Level Parallelism und SIMD sind sogar mehrere pro Zyklus möglich
Der eigentliche Flaschenhals und die Quelle der Langsamkeit ist der Speicher. Ein Speicherzugriff kostet Tausende Zyklen, und wenn ein TLB-Walk oder ein OS-Interrupt nötig ist, können es Zehntausende oder Hunderttausende Zyklen werden. Wenn man Big-O verwenden will, sollte man es zur Abschätzung der Zahl der Cache Misses nutzen
Ich würde vermutlich eine maßgeschneiderte perfekte Hash-Funktion und Phil Bagwells
popcount-Trick verwenden. Das wäre schneller als andere Lösungen, die mehrfach in den Speicher greifenCPUs sind schnell, Speicher ist langsam
Ich bin zwar nicht besonders bewandert in der Optimierung von Datenstrukturen, aber gerade wenn man bedenkt, dass die Tabelle, in der gesucht wird, statisch ist, fand ich es überraschend, dass Hash-Tabellen so schnell ausgeschlossen wurden. Es fällt schwer zu glauben, dass eine speziell optimierte Hash-Tabelle nicht schneller wäre als ihre Trie-Implementierung
Für diesen Anwendungsfall ist das ein Vorteil, mit dem Hashing nicht mithalten kann. Bei den übrigen Techniken geht es darum, den konstanten Faktor des Tries so weit zu senken, dass sich dieser anfängliche Vorteil in der tatsächlichen Performance auszahlt
std::collections::HashMap: https://github.com/rust-lang/rustc-hashBei etwa 100 statischen Einträgen dürfte auch o1hash funktionieren: https://github.com/rurban/smhasher/blob/master/o1hash.h
Dieser Artikel baut mit einer schicken Datenstruktur die Menge
to_removeund iteriert dann darüber, um die Einträge aus der eigentlichen Header-Map zu entfernenDer Aufruf von
remove_headerscheint dieser Code zu sein: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Diese Funktion ruft
.remove()auf zwei anderen Datenstrukturen auf, und beide landen letztlich in diesem riesigen Code: https://docs.rs/http/latest/src/http/header/map.rs.html#1550Endlich ein Blogpost, in dem ein Trie vorkommt. Die Trie-Aufgaben auf LeetCode waren also nicht umsonst ;)
Trotzdem ist es definitiv kein Werkzeug, zu dem ich oft greife
Es ist ein User-Agent-Parser für Go: https://github.com/medama-io/go-useragent
Normalerweise stützen sich solche Probleme auf viel Regex-Parsing, daher war es schön, einen etwas neueren Ansatz ausprobieren zu können
Wenn die Menge der zu matchenden Einträge statisch ist, frage ich mich, ob sie eine perfekte Hash-Tabelle ausprobiert haben. Das würde auf ein paar arithmetische Operationen plus einen String-Vergleich hinauslaufen; es wäre interessant zu sehen, wie sich das gegenüber einem Trie schlägt
Theoretisch sollte man mit Regex, weil über eine Zustandsmaschine gematcht wird, ähnlich wie beim Trie im Worst Case auf O(k) kommen. Soweit ich es verstehe, verwenden Regex-Bibliotheken aber Backtracking, statt tatsächlich Zustandsmaschinen zu bauen, daher ist die Performance nicht mehr O(k)
Es überrascht mich zwar, dass sie keine bereits existierende, performante, zustandsmaschinenbasierte Regex-Bibliothek gefunden haben. Die sollte eigentlich eine ähnliche Performance wie ein Trie haben, aber in der Praxis spielen Faktoren wie Speicherzugriffsmuster oder die Performance bestimmter arithmetischer Operationen tiefer hinein, sodass es schwer abzuschätzen ist
Ob sie einen sehr kleinen Bloom-Filter ausprobiert haben? Wenn man den Header-Key schnell wie eine Faltung verarbeitet und gegen einen Bloom-Filter prüft, könnte man in den meisten Fällen die Trie-Traversierung für nur ein paar Zyklen Kosten komplett vermeiden
Optionen wie SIMD, eingebaute CRC-Instruktionen oder eine Bloom-Filter-Größe von 256 Bit scheinen ebenfalls möglich
Auch ein einfacherer Ansatz könnte sich lohnen. Wenn man die Treffer-/Fehlschlaghäufigkeiten der Trie-Knoten analysiert, findet man vielleicht bestimmte Zeichenpositionen mit einer höheren Fehlschlagrate als beim ersten Zeichen. Wenn man solche Spezialpositionen zuerst prüft, könnte es schneller werden. Natürlich setzt das voraus, dass die Header-Daten ihrer Natur nach ziemlich regelmäßig sind
Meine Sicht darauf: Erstens, lohnt sich das überhaupt? Es sieht so aus, als hätte man etwa 500 CPU-Cores eingespart, aber ich weiß nicht, ob das echte Cores sind oder ob Hyperthreading-Cores mitgezählt werden.
Cloudflares Kosten kenne ich nicht, aber das dürfte einer einstelligen Anzahl von Servern entsprechen, und die Einsparung liegt vermutlich auch nur bei einigen Zehntausend Dollar pro Jahr. Nicht vernachlässigbar, aber ich weiß nicht, ob man im Verhältnis zum Engineering-Aufwand einen positiven ROI erwarten kann.
Zweitens: Wenn man schon so tief ins Detail geht, frage ich mich, ob geprüft wurde, Filter in die Deserialisierung einzubauen, sodass die Header gar nicht erst erzeugt werden.
Auch der Stromverbrauch bleibt niedriger, und die CO₂-Emissionen sinken.
Mir ist es lieber, ein Unternehmen zu sehen, das etwas 1 % schneller machen will, als irgendeinen Unsinn zu treiben, etwa Header per KI zu analysieren, um einem Sandalen zu verkaufen.
Dieser Wert kann bei einer Million Dollar liegen.