Nog eens 100 TB RAM besparen met wiskunde (en Rust)

Cloudflare opereert op een schaal die zo groot is dat het, zelfs na jaren hier te hebben gewerkt, onwerkelijk lijkt. We hebben duizenden servers over de hele wereld met petabytes aan RAM en miljoenen CPU-cores, en alles wordt tot het maximum benut. Hoe enorm die middelen ook lijken, ze zijn nog steeds eindig. Wanneer elke service op elke node moet draaien, is er geen ruimte voor verspilling.

Op deze schaal worden kleine verbeteringen enorm uitvergroot, waardoor zelfs verbeteringen van 1% per keer het vieren waard zijn. Sommige aanpassingen leveren echter veel meer op: in dit artikel bekijken we hoe kleine wijzigingen in één enkel algoritme de geheugenvoetafdruk van een van onze op Pingora gebaseerde services aanzienlijk hebben verminderd. Hierdoor konden we wereldwijd meer dan 100 TB RAM terugwinnen, bovenop de 100 TB aan geheugen die het DNS-team vorige maand wist te besparen.

Verspilling voorkomen

Het behouden van een rechtvaardige verdeling van resources tussen teams is niet eenvoudig, zeker niet in grote organisaties. Een van de manieren waarop Cloudflare dit evenwicht bewaakt, is via de onvermoeibare inspanningen van het Performance-team.

Dit verhaal begint met een ticket dat werd ingediend door Ivan, die het volgende ontdekte: Excessive memory usage from pingora-ketama in Pingora Backend Router. De bevinding was dat onze interne load-balancing service, de Pingora Backend Router (PBR), significant meer geheugen gebruikte dan verwacht — specifiek in structuren geassocieerd met pingora-ketama, onze open-source bibliotheek voor het afhandelen van consistent hashing.

Om uit te leggen hoe we dit overmatige geheugengebruik hebben aangepakt, moeten we eerst bespreken wat consistent hashing precies is, waarom we het in PBR gebruiken en hoe het zo geheugenhongerig werd. Onderweg komen we wat Rust en een beetje wiskunde tegen.

Consistente hashing

Consistente hashing is een veelgebruikte methode om taken over meerdere servers te verdelen op een manier die geen grote wijzigingen vereist wanneer servers worden toegevoegd of verwijderd. Intern gebruiken we dit om cachebare verzoeken op basis van de URL naar servers te routeren. Hierdoor kunnen we per datacenter slechts één kopie van een bestand opslaan en is er een stabiele manier om de locatie van elk bestand te vinden.

Het kernconcept van consistente hashing is dat, hoewel hashfuncties elk type input kunnen accepteren, hun output beperkt is tot een enkel ongetekend geheel getal (32, 64 of 128-bit integers, afhankelijk van de hashfunctie). Dit stelt ons in staat om taken en servers op een consistente manier aan elkaar te koppelen. De meeste discussies over consistente hashing beschouwen die outputruimte als een continue, cirkelvormige ring die terugloopt van de maximale waarde naar nul. Voor onze discussie zullen we de 32-bit output van onze hashfunctie representeren als een getallenlijn.

Stel dat we een set servers hebben (A, B & C) en een set taken (t-z). We kunnen elk van deze op de getallenlijn plaatsen op basis van de hash van hun representatieve waarden, zoals IP-adressen voor servers en cache-keys voor taken.

Het toewijzen van taken aan servers is nu simpelweg een kwestie van het vinden van de eerste server links van elke taak. We kunnen dit visueel weergeven door het gebied van hashes dat aan elke server wordt gekoppeld, in te kleuren. Merk op dat het bereik dat door server C wordt bestreken, terugloopt naar het begin; vandaar het idee dat hashes in een ring bestaan.

Op basisniveau is consistente hashing dus heel eenvoudig — maar het duurt niet lang voordat men ziet dat er ruimte is voor verbetering. In ons voorbeeld is het bereik dat door server A wordt bestreken aanzienlijk groter dan dat van B of C. Dit is een probleem, omdat het fractie van de verzoeken die een server afhandelt, proportioneel is aan de grootte van zijn bereik op de getallenlijn. Idealiter willen we garanderen dat elke server een gelijkmatig bereik heeft, maar omdat hashes in essentie willekeurige getallen zijn, moeten we de grootte van de regio's in termen van statistiek bespreken.

Wiskunde en consequenties

Wanneer we spreken over statistische distributies, zijn er twee grote factoren die ons helpen onzekerheid op een nuttige manier te kwantificeren: de verwachtingswaarde (expected value) en de standaarddeviatie (standard deviation). In vereenvoudigde termen geeft de verwachtingswaarde ons een punt waar metingen op basis van een distributie gecentreerd zullen zijn, en de standaarddeviatie vertelt ons hoe dicht de meeste metingen waarschijnlijk bij dat centrale punt liggen.

Voor consistente hashing kunnen we deze factoren berekenen voor de fractionele grootte van het bereik dat geassocieerd is met één van de $N$ servers:

$$ \begin{align} \text{Exp} &= \frac{1}{N} \\ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align} $$

Concreet: stel dat we 100 servers hebben. De bovenstaande formules geven:

$$ \text{Exp}=1/100 = 1\% \\ \text{SD}= \frac{1}{100}\sqrt{\frac{100-1}{100+1}} \approx 0.99\% $$

Dit betekent dat we kunnen verwachten dat het bereik dat elke server afhandelt gecentreerd is rond 0,99% van het totaal, en dat de meeste lengtes binnen 1% van wat verwacht wordt vallen. Dit klinkt goed, totdat we beseffen dat dit 0,99% van de totale lengte is. We moeten de standaarddeviatie schalen met de verwachtingswaarde om te zien hoe groot de fout is als fractie van de doelsegrootte. Deze waarde wordt de variatiecoëfficiënt (coefficient of variation of CV) genoemd.

$$ \text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}} $$

Bij $N=100$ is $\text{CV} \approx 99\%$. Dit betekent dat sommige servers waarschijnlijk 99% harder zullen werken dan ze zouden moeten (twee keer zoveel verzoeken afhandelen), terwijl anderen praktisch niets doen. Nu we een manier hebben om te voorspellen hoe gelijkmatig servers belast worden bij consistente hashing, kunnen we beginnen met verbeteringen.

Wat als we meer hashes toevoegen?

De eenvoud van consistente hashing is een tweesnijdend zwaard. Het is gemakkelijk te begrijpen en te implementeren, maar elke verbetering aan het systeem moet ook relateerbaar zijn aan diezelfde getallenlijn. Dat betekent dat de oplossing voor elk probleem met consistente hashing simpelweg "meer hashes" moet zijn.

Om het probleem van ongebalanceerde werklasten op te lossen, kunnen we meerdere hashes toevoegen om elke server te representeren in plaats van slechts één. Hoewel elk individueel bereik een grote standaarddeviatie heeft, zou het combineren van meerdere bereiken de totale grootte moeten egaliseren. Als we in ons voorbeeld met drie servers twee extra willekeurige hashes per server toevoegen, zien we dat dit helpt om de werklast per server gelijkmatiger te verdelen.

Dit is een versimpeld voorbeeld. Vanwege de willekeurige aard van het systeem is er geen garantie hoeveel verbetering je krijgt door 2 extra hashes per server toe te voegen, maar intuïtief is duidelijk dat het combineren van meer hashsegmenten een gelijkmatigere distributie oplevert. Dit is in feite wat de wet van de grote getallen ons vertelt.

Het probleem is dat dit alleen werkt voor grote getallen. In NGINX is het basisaantal hashes per server hardcoded op 160, en Pingora gebruikt dezelfde waarde als standaard. Als we teruggaan naar ons voorbeeld van 100 servers: als we 160 punten per server gebruiken in plaats van één, daalt de variatiecoëfficiënt (die we kunnen zien als een foutenmarge) van ongeveer 99% naar ongeveer 8%, een aanzienlijke verbetering.

Wat als we nóg meer hashes toevoegen?

We hebben gezien dat het verhogen van het aantal hashes per server met een constante factor de distributie verbetert, maar wat als we de werklast niet gelijkmatig willen verdelen? In het geval van Cloudflare hebben sommige servers meer opslagruimte dan andere. Het is daarom beter als het aantal verzoeken dat aan een server wordt toegewezen proportioneel is aan de schijfruimte.

Een manier om dit te bereiken is met het Ketama-algoritme. Het algoritme komt neer op het volgende: voor twee servers, $S1$ & $S2$, als we willen dat de verzoeken die door $S1$ worden afgehandeld $w \times$ meer zijn dan die door $S2$, moet het aantal hashes geassocieerd met $S1$ zijn $H1 = w \times H_2$. Dit stelt ons in staat om een "gewicht" voor elke server in te stellen, wat het aantal hashes voor die server schaalt.

Dit is echter geen vervanging voor de constante schaalfactor die we eerder bespraken. Die schaling moet aanwezig blijven om een minimale foutenmarge in te stellen, wat vooral zichtbaar is bij de servers met de laagste gewichten. Voor ons, aangezien we de werklast willen schalen op basis van opslag, gebruiken we de schijfruimte als gewicht.

Wat als we écht veel meer hashes toevoegen?

Het laatste probleem is dat we tot nu toe ervan uitgingen dat elke server elk verzoek kan afhandelen, maar in de praktijk is dat niet zo. Compliance-vereisten of specifieke caching-functies betekenen dat slechts een subset van servers een bepaald verzoek kan afhandelen.

In tegenstelling tot eerdere problemen kunnen we dit niet oplossen door meer hashes aan dezelfde ring toe te voegen. We moeten volledig nieuwe ringen toevoegen. Bovendien heeft elke combinatie van functies potentieel zijn eigen specifieke ring nodig.

Duplicatie op basis van combinaties is een klassiek recept voor een exponentiële explosie. In ons geval leiden een handvol verschillende functies tot $2^{\text{handvol}}$ (tientallen) aparte consistente hashringen. Het "excessieve geheugengebruik" (in sommige gevallen 6 GB) dat Ivan vond, was dus het gevolg van een enorm aantal hashes om aan alle benodigde functionaliteit te voldoen, die allemaal in het geheugen opgeslagen moesten worden.

Verbeteringen in opslag

Een grote verbetering kwam van Zaidoon, die een inzicht kreeg over onze struct voor het opslaan van hashes in PBR. De struct zag er als volgt uit:

struct Point {
    hash: u32,
    index: u32,
}

In het geheugen wordt dit gerepresenteerd als acht bytes, waarvan vier naar de hash gaan (wat onvermijdelijk is) en vier naar een index die verwijst naar de server in een andere array. Zaidoons inzicht was dat een 32-bit integer voor die index verspillend is, omdat PBR waarschijnlijk nooit meer dan $2^{16} \approx 65\text{k}$ servers tegelijkertijd hoeft te coördineren. Een 16-bit integer zou dus volstaan.

We konden de struct dus vervangen door:

struct PointV2 {
    hash: u32,
    index: u16,
}

Helaas maakt Rust dit niet zo eenvoudig. Het wijzigen van de grootte van de index heeft op zichzelf geen effect op de geheugenvoetafdruk. Dit komt door de alignment-regels van Rust, die vereisen dat de grootte van een structuur in het geheugen een veelvoud is van het grootste (meest uitgelijnde) veld. In dit geval is de hash het grootst (vier bytes), waardoor een Point minimaal acht bytes groot moet zijn.

Er zijn echter bekende manieren om dit te omzeilen. Een veiligere, hoewel minder leesbare oplossing is om de hash en index op te slaan als een raw byte array en deze te benaderen met getters.

struct Point([u8; 6]);

impl Point {
    fn hash(&self) -> u32 {
        u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
    }
    fn index(&self) -> u16 {
        u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
    }
}

Deze eenvoudige wijziging vermindert de hoeveelheid geheugen die wordt gebruikt voor consistente hashing met maar liefst 25%! Om nog meer te besparen, moesten we opnieuw naar de wiskunde kijken.

Wat als we minder hashes proberen?

We hebben eerder de formule voor de standaarddeviatie gezien voor het geval waarin er slechts één hash per server is. De afleiding voor het geval waarin er $k$ hashes per server zijn, is complexer. De volledige afleiding staat in een aanvullend bericht, maar dit is het resultaat:

$$ \text{Exp}k = \frac{1}{N}, \quad \text{SD}k=\sqrt{\frac{(k+1)}{N(kN+1)}-\frac{1}{N^2}} $$

Om te zien hoe het verhogen van het aantal hashes de nauwkeurigheid verbetert, kijken we opnieuw naar de variatiecoëfficiënt:

$$ \text{CV}k=\frac{\text{SD}k}{\text{Exp}_k}=\sqrt{\frac{N-1}{(N \cdot k+1)}} $$

Het plotten van $\text{CV}_k$ laat een potentieel probleem zien bij de mentaliteit van "gewoon meer hashes toevoegen" (naast het overmatige gebruik van RAM). Elke stap in de vermindering van de foutenmarge vereist bijna een orde van grootte meer hashes per server. Dit betekent dat het toevoegen van meer hashes steeds minder verbetering oplevert.

We gebruiken een basis van 160 hashes, geschaald door de opslagcapaciteit van de server. Stel dat de wegingsfactor $m_w$ voor een server 625 is, dan krijgen we $k = 160 \times 625 = 100.000$. Uit de berekeningen blijkt dat de laatste 90.000 hashes die we toevoegen ons slechts een minuscule vermindering van de fout met 0,7% opleveren.

Bovendien werken deze voorspellingen alleen als we hashes in een continue ring beschouwen. In de praktijk gebruiken we 32-bit getallen die potentieel kunnen botsen (collisions). De waarschijnlijkheid van botsingen stijgt verrassend snel naarmate het aantal hashes toeneemt (zie de birthday paradox). Botsingen zijn problematisch omdat ze ertoe leiden dat sommige bijdragen willekeurig wegvallen, wat onvoorspelbare fouten introduceert.

Uiteindelijk concludeerden we dat we het aantal hashes dat we per server genereerden met 90% konden verminderen zonder dat dit leidde tot een merkbare toename van de foutmarge.

Migreren zonder de origin-servers te overbelasten

Er was nog één probleem: het wijzigen van de hashring verandert waar sommige cachebare verzoeken naartoe gaan. Zelfs als de nieuwe ring beter is, zou het gelijktijdig overschakelen van het hele netwerk bijna alle gecachte content ongeldig maken. Dit zou een geheugenoptimalisatie veranderen in een apocalyptische toename van het verkeer naar de origin-servers.

Daarom hebben we geen globale "flip" gedaan. Voor een tijdje hield PBR beide versies van de cachebare loadbalancer in het geheugen: de oude Ketama-ring en de nieuwe, kleinere ring. Elk verzoek gebruikte ons normale migratiekader om te bepalen welke ring de backend moest selecteren. Dit betekende dat de beslissing stabiel was per verzoek-hash en dat we een zuivere rollback-route hadden.

We hebben de migratie in lagen uitgerold:

1. We begonnen met kleine validatielocaties.
2. We gingen over naar progressief grotere groepen datacenters.
3. Daarna rolden we het uit naar de rest van de wereld.

Door de uitrol per datacenter te beperken, bleef de blast radius klein en was het veel gemakkelijker om te bepalen of een wijziging veilig was. Tijdens de migratie hielden we backend-selectie traces, ring-versie counters, PBR-connectie fouten, procesgeheugen, opstarttijd, cachegedrag en origin-verkeer in de gaten.

Zodra de migratie 100% had bereikt, verwijderden we het tijdelijke pad naar de oude ring. Het resultaat was bevredigend: onze wijzigingen verminderden het gebruikte geheugen met 100 TB!

Probeer het zelf

Alle wijzigingen die in dit artikel worden besproken, zijn nu beschikbaar in de pingora-ketama crate als een (voorlopig) niet-geadverteerde cargo-feature. De v2-ring bevat het gecomprimeerde opslagformaat, een snellere sorteermethode en de mogelijkheid om het basisaantal hashes per node te schalen.

Naast het uitproberen van deze specifieke wijzigingen in consistente hashing, hoop ik dat dit dient als inspiratie om in je eigen systemen te graven. Kijk welke "simpele" of "voor de hand liggende" beslissingen potentieel grote winsten verbergen, mits je bereid bent in de cijfers te duiken. Je kunt misschien niet al je problemen oplossen met Rust, maar wiskunde is universeel.