Hoe we 100 terabytes aan geheugen hebben bespaard door de DNS-cache van 1.1.1.1 te optimaliseren

Vijf opeenvolgende wijzigingen in de manier waarop cache-vermeldingen in het geheugen worden opgeslagen, hebben de voetafdruk per vermelding met meer dan 50% verminderd. Over onze vloot hebben deze wijzigingen ongeveer 100 terabytes aan geheugen vrijgemaakt, wat gelijkstaat aan de hoeveelheid RAM in 130 van onze Gen 13-servers. Daarnaast is de cache sneller geworden: de doorvoersnelheid bij invoegingen steeg met 43% en de latentie bij opvragingen daalde met 19%, omdat minder allocaties en een betere geheugenlokaliteit betekenden dat we snelheid niet hebben opgeofferd voor ruimte.

Wat we cachen

Bij een koude start begint Big Pineapple met een lege cache. Naarmate DNS-aanvragen binnenkomen, vult de cache zich totdat het maximale aantal vermeldingen is bereikt, waarna we oudere of minder populaire items verwijderen om ruimte te maken.

De exacte cachegrootte varieert per datacenter. Wanneer EDNS Client Subnet (ECS) wordt gebruikt, geven authoritatieve servers verschillende antwoorden afhankelijk van het netwerk van de cliënt, waardoor we meerdere versies van dezelfde aanvraag cachen. Dit verhoogt zowel het aantal vermeldingen als het geheugen dat elke vermelding verbruikt, wat de optimalisaties in dit artikel extra effectief maakt voor locaties met veel ECS-verkeer.

Elk item in de cache is een sleutel-waarde-paar. De sleutel identificeert wat er is opgevraagd:

pub struct CacheKey {
    qname: Name,
    qtype: Rtype,
    authenticated: bool,
    tag: Vec<u8>,
}

De waarde bevat het DNS-antwoord zelf: de secties answer, authority en additional, samen met metadata zoals de creatietijd, een hit-teller en de Time-to-Live (TTL).

pub struct CacheEntry {
    timestamp: UnixTimeStamp,
    pub inception: Instant,
    pub ttl: Ttl,
    pub hits: u32,
    pub answers: Vec<Record>,
    pub authority: Vec<Record>,
    pub additional: Vec<Record>,
    pub errors: Vec<ExtendedError>,
    ...
}

Beide structuren boden ruimte voor verbetering. Verschillende velden gebruikten typen die overhead met zich meebrengen die we niet nodig hebben zodra de vermelding is opgeslagen.

Geheugengebruik benchmarken

Om de impact van elke wijziging te meten, benchmarken we door de cache te vullen met willekeurig gegenereerde vermeldingen die ongeveer overeenkomen met de verkeersverdeling in productie: 56% A-records, 25% AAAA en 19% TXT. Elke vermelding bevat tussen één en vier records.

TXT-records dienen in de benchmark als vervanger voor alle niet-A/AAAA-recordtypen. Hun grootte is willekeurig tussen 64 en 224 bytes, wat dicht bij de gemiddelde antwoordgrootte ligt die we zien voor records met een variabele lengte.

We volgen het geheugengebruik met een aangepaste allocator die Rust's System allocator omhult en het aantal en de grootte van de allocaties per cache-vermelding registreert. Naast geheugen meten we de doorvoersnelheid bij invoegingen en de latentie bij opvragingen over de volledige cache-flow, om er zeker van te zijn dat geheugenbesparingen niet ten koste gaan van de prestaties.

Deze inputs benaderen de productieomgeving, maar reproduceren deze niet exact. Het geheugen van het proces hangt immers ook af van de verkeersmix, de bezettingsgraad van de cache, de status van de allocator en het geheugen dat buiten de cache wordt gebruikt. Daarom hebben we het resident geheugen in productie-instanties gemeten tijdens de uitrol.

De kosten van capaciteit

Vec<T> slaat drie velden op: een pointer naar heap-gealloceerde data, de huidige lengte en de totale capaciteit. Wanneer je een item toevoegt, controleert Vec of de lengte de capaciteit overschrijdt en heralloceert indien nodig. Als er ruimte is, wordt het item simpelweg toegevoegd en wordt de lengte verhoogd.

Zodra we echter een DNS-antwoord in de cache opslaan, wijzigen we dit nooit meer. Het capaciteitsveld dient geen enkel doel, maar kost toch 8 bytes per Vec. Ook de over-gealloceerde heap-ruimte is verspild; een Vec met capaciteit voor acht items maar slechts vijf opgeslagen items laat drie ongebruikte slots achter op de heap.

Het gebruik van Box<[T]> lost beide problemen op. Het kan na creatie niet groeien, dus het heeft geen capaciteitsveld nodig en reserveert geen ruimte voor toekomstige elementen. Hetzelfde geldt voor String, die ook een capaciteitsveld heeft; Box<str> laat dit weg.

Elke cache-vermelding bevat 8 Vec- en String-velden. Door deze te vervangen door Box<[T]> en Box<str> besparen we 8 bytes per veld, oftewel 64 bytes per vermelding. Ook wordt het overtollige heap-geheugen dat Vec reserveert voor toekomstige groei geëlimineerd. De gecombineerde besparing bedraagt meer dan 15 terabytes over de 250 miljard cache-vermeldingen.

Minder lijsten, minder pointers

In plaats van de secties answer, authority en additional in aparte lijsten op te slaan, kunnen we één enkele lijst opslaan met offsets naar het begin van elke sectie. Aangezien DNS-recordaantallen per sectie passen in een u16, kunnen we een u16 (2 bytes) gebruiken voor elke offset, in vergelijking met de 8-byte pointer en 8-byte lengte die elke aparte Box<[T]> vereist.

Dit verwijdert twee lijsten (elk met een 8-byte pointer en 8-byte lengte) en vervangt deze door twee 2-byte offsets, wat 28 bytes per vermelding bespaart.

Deze besparingen vertalen zich niet altijd direct één-op-één naar het aantal verwijderde bytes uit individuele velden. Rust voegt padding toe om te voldoen aan alignment-vereisten en rondt de grootte van een struct af naar een veelvoud van zijn alignment. Het verwijderen van een klein veld kan dus extra padding elimineren. Zo hebben we ook verschillende boolean-velden samengevoegd in één enkele bitflag. Dit verminderde de omliggende padding, waardoor de struct meer kromp dan de grootte van de individuele booleans.

De eigenaar weglaten

Elk DNS-record heeft een eigenaar: het domein waartoe het record behoort. In veel gevallen is deze eigenaar identiek aan het domein dat is opgevraagd. Bijvoorbeeld, een aanvraag voor example.com A geeft twee records terug met dezelfde eigenaar:

$ dig example.com A
;; ANSWER SECTION:
example.com.        300    IN    A        198.51.100.1
example.com.        300    IN    A        198.51.100.2

Maar wanneer er een CNAME in het spel is, kan de eigenaar van het record verschillen van het opgevraagde domein:

$ dig example.com A
;; ANSWER SECTION:
example.com.        300    IN    CNAME    cdn.example.com.
cdn.example.com.    300    IN    A        198.51.100.1
cdn.example.com.    300    IN    A        198.51.100.2

Het DNS-wire-formaat gaat om herhaalde eigenaren via name compression, zoals gedefinieerd in RFC 1035. In plaats van hetzelfde domein twee keer te coderen, slaan opeenvolgende vermeldingen een 2-byte pointer op naar de eerste vermelding. Een domein als www.example.com kan zo gecodeerd worden als enkel www, gevolgd door een pointer naar waar example.com al in het bericht verscheen.

Dit werkt goed tijdens het transport, maar in onze cache sloegen we de volledige eigenaarsnaam op naast elk record. Het volgen van compressie-pointers tijdens cache-opvragingen is duur op het kritieke pad, dus we ruilden geheugen in voor snelheid.

De meeste records hebben echter een eigenaar die identiek is aan het opgevraagde domein. Voor die kunnen we de eigenaar volledig weglaten en deze bij het uitlezen afleiden. Wanneer de eigenaar verschilt, zoals bij de A-records achter een CNAME, slaan we de volledige naam op.

pub struct Record {
    owner: Option<Box<Name>>,
    class: Class,
    ttl: Ttl,
    rtype: Rtype,
    data: RecordData,
}

Wanneer owner gelijk is aan None, herstelt de constructie van het antwoord het opgevraagde domein uit de cache-sleutel, waardoor een heap-allocatie wordt voorkomen. Dit betekent dat het record niet langer zelfvoorzienend is, maar de cache-sleutel is bij elke opvraging al beschikbaar. Wanneer de eigenaar verschilt, slaat Some een pointer op naar de volledige naam op de heap.

In de praktijk hebben de meeste gecachte records een eigenaar die identiek is aan het opgevraagde domein, waardoor de meerderheid geen heap-allocatie vereist voor het eigenaarsveld.

Enum-dimensionering

Rust enums zijn sum types: elke variant kan verschillende data bevatten, maar de enum is altijd zo groot als zijn grootste variant.

pub enum Option<T> {
    Some(T),
    None,
}

Option is ofwel Some en bevat een waarde, of None en bevat niets. Beide varianten nemen dezelfde hoeveelheid geheugen in beslag. De enum slaat een tag op die de actieve variant aangeeft, gevolgd door ruimte die groot genoeg is voor de data van de grootste variant. Wanneer de variant None is, blijft die ruimte ongebruikt.

Voor recorddata leek het natuurlijk om elk DNS-recordtype als een enum-variant op te slaan:

pub enum RecordData {
    A(Ipv4Addr),
    Aaaa(Ipv6Addr),
    Txt(Txt),
    Naptr(Naptr),
    Svcb(Svcb),
    // ...
}

Maar de enum is altijd zo groot als de grootste variant. In ons geval is dat NAPTR met 136 bytes. Deze bevat drie tekstvelden van variabele lengte, een domeinnaam en twee integers. Als resultaat wordt de volledige enum, inclusief de variant-tag en padding, 144 bytes.

Een A-record heeft slechts 4 bytes nodig, en een AAAA-record 16 bytes. A- en AAAA-records maken meer dan 80% van ons verkeer uit, waardoor de meeste records meer dan 120 bytes aan padding verspillen. Aangezien één cache-vermelding veel records kan bevatten, telt dit snel op.

Het 'boxen' van varianten

Om dit probleem op te lossen, kunnen we de grotere varianten van de enum 'boxen', waardoor ze naar een aparte heap-allocatie worden verplaatst. De enum slaat dan een 8-byte pointer naar de heap op, waar de data slechts de ruimte inneemt die daadwerkelijk nodig is.

pub enum RecordData {
    // Kleine en veelvoorkomende varianten worden inline opgeslagen
    A(Ipv4Addr),
    Aaaa(Ipv6Addr),
    // Grote varianten worden op de heap opgeslagen
    Txt(Box<Txt>),
    Naptr(Box<Naptr>),
    Svcb(Box<Svcb>),
    // ...
}

Voor A- en AAAA-records bespaart dit 120 bytes per record. Ook kleinere varianttypen zoals TXT en CNAME profiteren hiervan. Ze nemen nog steeds de 24-byte enum in beslag, maar hun heap-allocatie is afgestemd op hun werkelijke data in plaats van opgevuld tot 144 bytes. NAPTR, de grootste variant, betaalt nu iets meer: er komt de kosten van een heap-pointer en allocatie-overhead bij. Maar NAPTR-records zijn in de praktijk zeldzaam, dus de afweging is de moeite waard.

Het boxen van de grotere recordvarianten introduceert echter eigen kosten.

De kosten van boxing

Boxing heeft twee kosten. De eerste is de allocator-overhead. Elke geboxte variant wordt een aparte heap-allocatie, en allocators ronden af naar de dichtstbijzijnde size class. Big Pineapple gebruikt jemalloc, een allocator ontworpen voor multithreaded, allocatie-intensieve workloads. jemalloc groepeert allocaties van vergelijkbare grootte in bins met een vaste grootte. Een TXT-record vraagt 32 bytes en past exact in een 32-byte bin, maar een MX-record vraagt 40 bytes en wordt afgerond naar 48, waardoor 8 bytes worden verspild.

De tweede kost is een slechte geheugenlokaliteit. Zonder boxing zitten de enum-waarden voor een cache-vermelding in één aaneengesloten allocatie. Met boxing leeft de data voor elke geboxte variant in een apart heap-gebied. Het lezen ervan vereist het volgen van een pointer, en wanneer die pointer ver verwijderd is van de rest van de vermelding, moet de CPU een nieuwe cache-line ophalen. Met miljoenen cache-vermeldingen eindigt geboxte data verspreid over de heap in plaats van compact samen.

Geen van beide kosten is op zichzelf catastrofaal, maar het elimineren van beide levert, zoals in de volgende sectie wordt beschreven, een meetbare verbetering op in zowel geheugengebruik als latentie bij opvragingen.

Records opslaan in wire-formaat

Een voor de hand liggende volgende stap zou zijn om het volledige DNS-antwoord in wire-formaat op te slaan, waarbij alleen per-cliënt-velden zoals het bericht-ID bij elke opvraging worden aangepast. Maar dit heeft nadelen. DNSSEC-records worden alleen opgenomen wanneer de cliënt de DO (DNSSEC OK) flag instelt. Een volledig wire-formaat bericht opslaan betekent dat we ofwel twee varianten moeten cachen (één met DNSSEC en één zonder), of ze uit een reeds gebouwd bericht moeten filteren. Ook is er een kost aan het parsen van het volledige bericht bij elke opvraging, wat de enum-benadering voorkomt door reeds geparsede records op te slaan.

Als tussenoplossing slaan we alleen de recorddata op als ruwe bytes, terwijl we de rest van de cache-vermelding als gestructureerde velden behouden. In plaats van een lijst van geparsede enum-varianten, slaan we de records op als een enkele Box<[u8]> die elk record bevat, gecodeerd als een 2-byte lengte-prefix gevolgd door de ruwe bytes.

Dit elimineert de per-variant enum-overhead en de geboxte heap-allocaties uit de vorige optimalisatie. De data wordt bovendien aaneengesloten opgeslagen, wat de CPU-cache-lokaliteit verbetert. De afweging is dat records niet langer willekeurig geïndexeerd kunnen worden; we moeten sequentieel door de buffer itereren. Dit voegt wat complexiteit toe aan functies zoals round-robin rotatie van A/AAAA-records, maar aangezien het aantal records per vermelding klein is, zijn de kosten verwaarloosbaar.

Bij het bouwen van een DNS-antwoord uit gecachte records kunnen de meeste recordtypen direct vanuit de buffer naar het uitgaande bericht worden gekopieerd. Voorheen moest elk geparsed record veld voor veld weer worden geserialiseerd naar het DNS-wire-formaat. De nieuwe layout slaat dat werk over voor A, AAAA, TXT en alle DNSSEC-recordtypen door hun gecodeerde bytes direct te kopiëren. Alleen records die domeinnamen bevatten, zoals CNAME, NS, MX en SOA, vereisen nog steeds parsing zodat we DNS-naamcompressie kunnen toepassen. Aangezien records die directe kopiering ondersteunen het overgrote deel van ons verkeer vormen, vermindert deze wijziging de werklast op het opvraagpad. In combinatie met de verbeterde geheugenlokaliteit verminderde dit de latentie bij cache-opvragingen met 5% in onze benchmarks.

Om de buffer met recorddata te bouwen, schrijven we naar een herbruikbare scratchspace-buffer die behouden blijft over cache-invoegingen heen. Omdat eerdere schrijfacties deze al hebben vergroot, hoeft de buffer zelden opnieuw te worden gealloceerd. Records variëren in grootte, dus we weten de exacte buffergrootte pas nadat ze zijn geserialiseerd. Zodra de records in de scratchspace-buffer staan, alloceren we een Box<[u8]> en kopiëren we de data erheen met memcpy. Dit vervangt de aparte allocatie per geboxte record door één allocatie voor alle recorddata. Het voorkomt ook verspilling door het verkleinen van een Vec<u8>, waarbij de allocator mogelijk het ongebruikte uiteinde van de oorspronkelijke allocatie niet kan terugvorderen. In onze benchmark verhoogde deze wijziging alleen al de doorvoersnelheid bij cache-invoegingen met 13%.

De resultaten

De productiemetingen laten zien hoe de gebenchingte besparingen per vermelding zijn vertaald naar het resident geheugen van het volledige proces.

Per-instantie geheugengebruik daalde over alle percentielen. Bij p99 daalde het geheugen van 9,3 GB naar 5,3 GB, een reductie van 43% in resident geheugen. Bij p90 daalde het van 6,5 GB naar 3,8 GB, een reductie van 42%. Instanties met voller caches zagen de grootste absolute besparingen.

In onze benchmarks reduceerden deze vijf optimalisaties de geheugenvoetafdruk per vermelding van 953 bytes naar 420 bytes, een reductie van 56%. De allocaties per vermelding daalden van 1,1 KB naar 461 bytes. De reducties gemeten in productie zijn kleiner, omdat resident geheugen de cache bevat naast alle andere procesdata. Nadat de uitrol was voltooid, was het totale werkset-geheugen over de vloot ongeveer 100 terabytes lager.

Ook de prestaties verbeterden. De doorvoersnelheid bij cache-invoegingen steeg met 43%, terwijl de latentie bij opvragingen met 19% daalde.

MetriekVoorheenDaarnaWijziging
Netto voetafdruk per vermelding953 bytes420 bytes-56%
Allocaties per vermelding1,1 KB461 bytes-58%
Doorvoersnelheid cache-invoeging625.000 entries/s893.000 entries/s+43%
Latentie cache-opvraging828 ns670 ns-19%

We zijn van plan het vrijgemaakte geheugen te herinvesteren in het vergroten van de cachecapaciteit zonder het geheugengebruik te verhogen, wat de cache hit rates verbetert en het volume aan upstream-aanvragen vermindert. Daarnaast onderzoeken we verdere optimalisaties voor de cache zelf.