Wer einen DNS-Resolver betreibt, denkt meist zuerst an Geschwindigkeit, selten an Speicherverbrauch. Dabei entscheidet gerade der über die Rechnung: Bei 250 Milliarden gespeicherten Einträgen kostet jedes eingesparte Byte pro Eintrag in der gesamten Flotte mehr als 250 Gigabyte RAM. Cloudflare hat in einem technischen Beitrag beschrieben, wie fünf aufeinanderfolgende Änderungen an der Speicherstruktur des Caches von Big Pineapple, der Plattform hinter 1.1.1.1, den Speicherbedarf pro Eintrag um über 50 Prozent senkten. Am Ende standen rund 100 Terabyte freigewordener Arbeitsspeicher, was dem RAM von 130 Servern der aktuellen Generation entspricht. Der Cache wurde dabei schneller: Die Schreibgeschwindigkeit stieg um 43 Prozent, die Leselatenz sank um 19 Prozent.
Um zu verstehen, warum solche Optimierungen nötig sind, lohnt ein Blick darauf, was der Cache speichert. Bei jedem Start ist Big Pineapple leer. Mit jeder hereinkommenden DNS-Anfrage füllt er sich, bis eine maximale Anzahl an Einträgen erreicht ist. Danach werden ältere oder selten genutzte Einträge verdrängt. Die genaue Größe variiert je nach Rechenzentrum. Kommt EDNS Client Subnet zum Einsatz, liefern autoritative Server je nach Netzwerk des Anfragenden unterschiedliche Antworten, weshalb mehrere Varianten derselben Anfrage parallel im Cache liegen können. Das erhöht sowohl die Anzahl der Einträge als auch den Speicherverbrauch pro Eintrag.
Was ein Cache-Eintrag enthält
Ein Eintrag besteht aus zwei Teilen: einem Schlüssel, der beschreibt, was angefragt wurde, und einem Wert, der die eigentliche DNS-Antwort enthält. Im Wert stecken die Antwort-, Authority- und Additional-Sektion, ergänzt um Metadaten wie Erstellzeitpunkt, einen Trefferzähler und die Time-to-Live. Beide Strukturen boten reichlich Raum für Verbesserungen, denn mehrere Felder nutzten Typen, deren eingebauter Overhead nach dem Speichern keinen Nutzen mehr hat.
Um die Wirkung jeder Änderung messen zu können, baute das Team einen Benchmark, der den Cache mit zufällig erzeugten Einträgen füllt. Die Verteilung entspricht in etwa der Produktion: 56 Prozent A-Records, 25 Prozent AAAA-Records und 19 Prozent TXT-Records. Jeder Eintrag enthält zwischen einem und vier Records. Ein eigener Allocator umschließt den System-Allocator von Rust und protokolliert Anzahl und Größe der Allokationen pro Cache-Eintrag. Neben dem Speicher werden Schreibdurchsatz und Leselatenz über den gesamten Cache-Pfad gemessen, damit Speicherersparnis nicht auf Kosten der Geschwindigkeit geht. Diese Werte bilden die Realität näherungsweise ab, ersetzen sie aber nicht. Der tatsächliche Prozessspeicher hängt auch vom Verkehrsmix, der Cache-Auslastung und der Arbeit außerhalb des Caches ab. Deshalb wurde zusätzlich der residente Speicher in der Produktion während des Rollouts gemessen.
Warum Vec mehr kostet als es sollte
In Rust ist Vec einer der am häufigsten genutzten Typen für dynamische Sammlungen. Intern speichert er drei Felder: einen Zeiger auf die heap-allokierten Daten, die aktuelle Länge und die Gesamtkapazität. Beim Anhängen eines Elements prüft Vec, ob die Länge die Kapazität überschreitet, und reserviert bei Bedarf neuen Speicher. Ist noch Platz, wird das Element einfach angefügt und der Zähler erhöht. Das ist praktisch, aber für einen DNS-Cache suboptimal. Sobald eine DNS-Antwort im Cache liegt, wird sie nie wieder verändert. Das Kapazitätsfeld hat keinen Zweck mehr, kostet aber acht Byte pro Vec. Dazu kommt der bereits reservierte, aber ungenutzte Heap-Bereich, etwa wenn ein Vec Platz für acht Elemente hält, aber nur fünf davon befüllt sind.
Die Lösung ist Box<[T]>, ein unveränderlicher Slice auf dem Heap. Er kann nach der Erstellung nicht mehr wachsen, braucht also weder Kapazitätsfeld noch Reserveplatz. Das gleiche Prinzip gilt für String, das ebenfalls eine Kapazität mitführt und sich durch Box<str> ersetzen lässt. Jeder Cache-Eintrag speichert acht Felder vom Typ Vec oder String. Der Austausch spart acht Byte pro Feld, also 64 Byte pro Eintrag. Hinzu kommt der eingesparte, brachliegende Heap-Speicher. Bei über 250 Milliarden Einträgen summiert sich das auf mehr als 15 Terabyte.
Weniger Listen, weniger Zeiger
Statt Antwort-, Authority- und Additional-Sektion als getrennte Listen zu speichern, fassten die Entwickler sie zu einer einzigen Liste zusammen und setzten Offsets, die auf den Anfang jeder Sektion verweisen. Da die Anzahl der Records pro Sektion in einen u16 passt, reichen 2-Byte-Offsets aus, verglichen mit 8 Byte Zeiger und 8 Byte Länge, die jede separate Box<[T]> mit sich bringt. Zwei Listen verschwinden, zwei 2-Byte-Offsets treten an deren Stelle, das spart 28 Byte pro Eintrag.
Die Ersparnis spiegelt sich allerdings nicht immer direkt in den Feldgrößen wider. Rust fügt Padding ein, um die Ausrichtung der Daten im Speicher zu gewährleisten, und rundet die Größe eines Structs auf ein Vielfaches seiner Ausrichtung auf. Wird ein kleines Feld entfernt, kann dadurch zusätzliches Padding wegfallen. Im konkreten Fall wurden mehrere boolesche Felder zu einem einzigen Bitflag zusammengefasst, was das umgebende Padding reduzierte und den Struct stärker schrumpfen ließ, als die reinen Boolean-Größen vermuten lassen.
Den Besitzer einsparen, wenn er ohnehin gleich ist
Jeder DNS-Record hat einen Besitzer, also die Domain, zu der er gehört. In vielen Fällen ist dieser Besitzer identisch mit der angefragten Domain. Eine Anfrage nach example.com A liefert zwei Records mit demselben Besitzer. Bei einem CNAME kann der Besitzer jedoch abweichen. Das DNS-Wire-Format löst wiederholte Besitzer per Name Compression auf, wie sie RFC 1035 definiert. Statt eine Domain zweimal zu kodieren, speichert jede weitere Stelle einen 2-Byte-Zeiger auf das erste Vorkommen. Für den Cache funktioniert das nicht direkt, weil das Verfolgen solcher Zeiger auf dem Hot Path zu teuer wäre. Also wird der vollständige Besitzername im Cache redundant mitgespeichert, was Speicher kostet.
Da die meisten Records denselben Besitzer haben wie die angefragte Domain, lässt sich das Feld in diesen Fällen komplett weglassen und beim Lesen aus dem Schlüssel rekonstruieren. Nur wenn der Besitzer abweicht, etwa bei A-Records hinter einem CNAME, wird der vollständige Name im Eintrag gehalten. Das bedeutet, dass der Record nicht mehr für sich allein stehen kann, aber der Schlüssel liegt bei jedem Lookup sowieso vor. Wenn der Besitzer fehlt, restauriert die Antwortkonstruktion die Domain aus dem Cache-Schlüssel und spart eine Heap-Allokation. Weicht der Besitzer ab, speichert Some einen Zeiger auf den vollständigen Namen. In der Praxis haben die meisten gecachten Records einen identischen Besitzer, sodass der überwiegende Teil keine Heap-Allokation für das Feld benötigt.
Wenn Enums größer werden als nötig
Rust-Enums sind Summentypen: Jede Variante kann unterschiedliche Daten tragen, aber das Enum ist immer so groß wie seine größte Variante. Option<T> ist entweder Some mit einem Wert oder None ohne Wert. Beide Varianten belegen denselben Speicher. Intern speichert das Enum ein Tag für die aktive Variante, gefolgt von genug Platz für die Daten der größten Variante. Ist die Variante None, bleibt dieser Platz ungenutzt. Für Record-Daten liegt es nahe, jeden DNS-Record-Typ als Enum-Variante abzubilden, aber genau das erzeugt Overhead. NAPTR ist im konkreten Fall die größte Variante mit 136 Byte, weil sie drei variabel lange Textfelder, einen Domainnamen und zwei Integer enthält. Mit Varianten-Tag und Padding landet das Enum bei 144 Byte. Ein A-Record braucht dagegen nur 4 Byte, ein AAAA-Record 16 Byte. Da A und AAAA zusammen über 80 Prozent des Verkehrs ausmachen, verschwenden die meisten Records über 120 Byte mit Padding.
Boxen, was groß wird
Die größeren Varianten des Enums zu boxen, verschiebt sie auf eine separate Heap-Allokation. Das Enum speichert dann einen 8-Byte-Zeiger auf den Heap, wo die Daten nur so viel Platz einnehmen, wie sie tatsächlich brauchen. Für A und AAAA spart das 120 Byte pro Record. Kleinere Varianten wie TXT und CNAME profitieren ebenfalls. Sie belegen weiterhin die 24 Byte des Enums, aber ihre Heap-Allokation ist auf die tatsächlichen Daten zugeschnitten statt auf 144 Byte gepolstert. NAPTR, die größte Variante, zahlt allerdings etwas drauf, weil ein Heap-Zeiger und der Allokationsoverhead hinzukommen. Da NAPTR-Records in der Praxis selten sind, lohnt sich der Kompromiss.
Was Boxen kostet
Boxen bringt zwei Kosten mit sich. Erstens den Allokator-Overhead. Jede geboxte Variante wird zu einer eigenen Heap-Allokation, und Allokatoren runden auf die nächste Größenklasse auf. Big Pineapple nutzt jemalloc, einen Allokator für mehrthreadige, allocationslastige Workloads. jemalloc gruppiert ähnlich große Allokationen in festen Größen-Bins. Ein TXT-Record möchte 32 Byte und passt exakt in eine 32-Byte-Bin, ohne Verschnitt. Ein MX-Record möchte 40 Byte und wird auf 48 aufgerundet, was 8 Byte verschwendet. Zweitens die schlechte Speicherlokalität. Ohne Boxen liegen die Record-Enums eines Cache-Eintrags in einer zusammenhängenden Allokation. Mit Boxen lebt jede Variante in einem eigenen Heap-Bereich. Um sie zu lesen, muss die CPU einem Zeiger folgen, und wenn der irgendwo weit entfernt liegt, muss eine neue Cache-Line geladen werden. Bei Millionen von Einträgen verteilen sich die geboxten Daten über den gesamten Heap statt kompakt beieinander zu liegen.
Records im Wire-Format speichern
Ein naheliegender nächster Schritt wäre, die komplette DNS-Antwort im Wire-Format zu speichern und bei jedem Lookup nur wenige feldspezifische Werte wie die Message-ID anzupassen. Das hat aber Nachteile. DNSSEC-Records werden nur ausgeliefert, wenn der Client das DO-Flag gesetzt hat. Eine komplette Wire-Format-Nachricht im Cache würde entweder zwei Varianten erzwingen, eine mit und eine ohne DNSSEC, oder DNSSEC-Records aus einer bereits gebauten Nachricht wieder herausfiltern. Dazu kommt der Aufwand, die komplette Nachricht bei jedem Lookup neu zu parsen, was die bisherige Enum-Variante mit bereits geparsten Records vermeidet.
Als Mittelweg speichert das Team nur die Record-Daten als rohe Bytes, während der Rest des Cache-Eintrags weiterhin aus strukturierten Feldern besteht. Statt einer Liste geparster Enum-Varianten liegen die Records jetzt in einer einzigen Box<[u8]>, in der jeder Record mit einem 2-Byte-Längenprefix versehen ist, gefolgt von seinen Rohdaten. Das beseitigt den Enum-Overhead pro Variante und die geboxten Heap-Allokationen aus dem vorherigen Schritt. Die Daten liegen kompakt hintereinander, was die CPU-Cache-Lokalität verbessert. Der Preis ist, dass Records nicht mehr direkt indizierbar sind, sondern sequenziell durchlaufen werden müssen. Das macht Funktionen wie die Round-Robin-Rotation von A- und AAAA-Records etwas aufwendiger, aber da die Record-Anzahl pro Eintrag klein ist, fällt das kaum ins Gewicht.
Beim Bau einer DNS-Antwort aus gecachten Records lassen sich die meisten Record-Typen direkt aus dem Buffer in die ausgehende Nachricht kopieren. Zuvor musste jeder geparste Record feldweise zurück ins Wire-Format serialisiert werden. Das neue Layout spart diesen Schritt für A, AAAA, TXT und sämtliche DNSSEC-Record-Typen, weil ihre kodierten Bytes unverändert übernommen werden. Nur Records mit Domainnamen wie CNAME, NS, MX und SOA müssen weiterhin geparst werden, um DNS Name Compression anzuwenden. Da Record-Typen, die direkt kopiert werden können, den Großteil des Verkehrs ausmachen, sinkt die Arbeit auf dem Lookup-Pfad. Zusammen mit der besseren Speicherlokalität reduzierte das die Lookup-Latenz im Benchmark um 5%. Um den Record-Buffer zu bauen, schreibt der Code in einen wiederverwendbaren Scratchspace-Buffer, der zwischen Cache-Inserts bestehen bleibt. Da ältere Schreibvorgänge ihn bereits vergrößert haben, ist eine Neuzuweisung selten nötig. Erst nachdem die Records im Scratchspace serialisiert sind, wird eine Box<[u8]> allokiert und die Daten per memcpy hineinkopiert. Das ersetzt die separate Allokation für jeden geboxten Record und sorgt dafür, dass am Ende nur eine einzige Allokation pro Eintrag nötig ist.
Was am Ende herauskam
Im Benchmark sank der Speicherbedarf pro Cache-Eintrag über die fünf Schritte von 953 auf 420 Byte, also um 56 Prozent; die Allokationen pro Eintrag gingen von 1,1 Kilobyte auf 461 Byte zurück. In der Produktion fallen die Werte kleiner aus, weil der residente Speicher eines Prozesses mehr umfasst als den Cache: Auf dem 99. Perzentil sank er je Instanz von 9,3 auf 5,3 Gigabyte, auf dem 90. Perzentil von 6,5 auf 3,8 Gigabyte. Über die gesamte Flotte summierte sich das nach dem Rollout auf rund 100 Terabyte. Der Schreibdurchsatz stieg von 625.000 auf 893.000 Einträge pro Sekunde, die Lookup-Latenz sank von 828 auf 670 Nanosekunden.
Den frei gewordenen Speicher will Cloudflare nicht einsparen, sondern in mehr Cache-Kapazität stecken: mehr Einträge bei gleichem Speicherverbrauch bedeuten eine höhere Trefferquote und weniger Anfragen an die vorgelagerten autoritativen Server. Weitere Optimierungen am Cache sind angekündigt.
Quelle: blog.cloudflare.com
