NumaRing: Topology-Aware Routing for NUMA-Local MPMC Queues, and What Broke When We Optimized It

Moderne computers zijn gebouwd als bruisende steden met meerdere districten, die elk hun eigen rekenkracht en geheugen huisvesten. Wanneer een programma werk moet verrichten, stuurt het een verzoek naar een specifiek district. Als de benodigde gegevens al in het lokale geheugen van dat district aanwezig zijn, vindt de taak direct plaats. Maar als het verzoek naar een ander district moet reizen om informatie op te halen, duurt de reis aanzienlijk langer. Deze vertraging, veroorzaakt door de fysieke afstand tussen de districten, is een fundamentele limiet van hoe deze machines zijn gebouwd. Decennialang hebben software-engineers geprobeerd programma's te schrijven die gegevens en de werkers die ze gebruiken in hetzelfde district houden, in de hoop de trage reizen door het land te vermijden. De uitdaging is dat wanneer veel werkers tegelijkertijd toegang willen krijgen tot een gedeelde lijst met taken, de verkeersopstoppingen die zij veroorzaken net zo schadelijk kunnen zijn als de afstand zelf.

Een onderzoeker zette zich het doel om een betere manier te bouwen om deze gedeelde lijsten te beheren, specifiek voor computers met twee afzonderlijke districten. Hij creëerde een systeem genaamd NumaRing, ontworpen om werkers en hun gegevens zo veel mogelijk lokaal aan hun eigen district te houden. Het idee was simpel: als een werker in het eerste district is, moet hij alleen naar de lijst in het eerste district kijken. Als die lijst vol of leeg raakt, zou het systeem dan een batch taken in één keer naar het andere district verplaatsen, in plaats van ze één voor één te verplaatsen. Deze aanpak beloofde het snelle, lokale verkeer draaiende te houden terwijl de trage, langeafstandstochten werden geminimaliseerd. Echter, toen de onderzoeker zijn systeem op de proef stelde, ontdekte hij dat zijn beste bedoelingen verborgen vallen bevatten. Door het systeem met extreme precisie te meten in plaats van te gokken hoe het werkte, ontdekte hij dat twee specifieke fouten het systeem vertraagden meer dan de hardware zelf, en dat een gangbaar stuk advies voor het oplossen van computervertragingen de boel juist erger maakte.

De onderzoeker begon met het bouwen van zijn systeem op een cloudcomputer met twee districten, elk bevattende zestien virtuele processoren. Hij vulde het met een constante stroom taken en hield in de gaten hoe lang het duurde voordat een taak van het begin van de rij naar het einde ging. In het begin was het systeem verrassend traag. De onderzoeker realiseerde zich dat elke keer dat een werker een taak probeerde toe te voegen of te verwijderen, de software een vraag stelde: "In welk district ben ik op dit moment?" Deze vraag leek onschuldig, maar het antwoord duurde lang om te berekenen. De software berekende de locatie telkens opnieuw vanaf nul, ook al veranderde de locatie van de werker zelden. Deze herhaalde berekening was als een chauffeur die bij elk kruispunt stopt om de weg te vragen, terwijl hij precies wist waar hij naartoe ging. De kosten van deze vraag waren zo hoog dat het meer dan elf keer zoveel inspanning kostte als de eigenlijke taak van het verplaatsen van de gegevens.

Zodra de onderzoeker dit oploste door de locatie te onthouden en deze alleen te controleren wanneer dat nodig was, versnelde het systeem drastisch. Het aantal verwerkte taken per seconde steeg zes tot zeven keer hoger. Maar het verhaal eindigde daar niet. Toen hij meer werkers aan de machine toevoegde, liep het systeem tegen een nieuwe muur aan. De werkers moesten nog steeds te lang wachten, vooral wanneer het systeem onder zware druk stond. Bij een diepere analyse ontdekte hij een tweede probleem in de manier waarop werkers taken tussen districten deelden. Wanneer een werker een batch taken uit een ander district wilde pakken, vochten alle werkers tegelijkertijd om dezelfde kleine teller om te beslissen wie er als volgende aan de beurt was. Dit creëerde een enorme verkeersopstopping bij de poort. Door elke werker zijn eigen privé-teller te geven, elimineerde de onderzoeker deze flessenhals. Deze verandering was nog indrukwekkender en verminderde de wachttijd van een werker in het midden van de lijn met meer dan tweehonderd keer.

Met deze twee belangrijke verbeteringen op hun plaats, verwachtte de onderzoeker dat zijn systeem een kampioen zou zijn. Hij had de softwarefouten geëlimineerd die hem tegenhielden. Echter, toen hij de machine tot het absolute uiterste dreef met tweeëndertig werkers, kon het systeem nog steeds niet de snelheid bereiken die hij oorspronkelijk had gehoopt. De onderzoeker testte vervolgens een standaardtechniek die wordt gebruikt om computervertragingen op te lossen, genaamd "backoff". Het idee achter backoff is dat als een werker een taak niet kan pakken, hij een kort moment moet wachten voordat hij het opnieuw probeert, in de hoop dat de rij zal opklaren. In veel situaties helpt deze pauze. Maar in deze specifieke, hoge-drukomgeving was de pauze een fout. De onderzoeker mat dat wachten hem daadwerkelijk vijftien tot dertig procent van zijn totale snelheid kostte. De snelste route was om onmiddellijk te blijven proberen, omdat de hardware het conflict al efficiënt genoeg afhandelde, waardoor wachten alleen maar tijd verspilde.

Het definitieve beeld dat naar voren kwam, was er een van zowel succes als harde limieten. De onderzoeker had succesvol een systeem gebouwd dat gegevens lokaal hield en twee grote softwarebugs opgelost die voor enorme vertragingen zorgden. Hij bewees dat een gangbare optimalisatiestrategie in bepaalde scenario's met hoge snelheid schadelijk kan zijn. Desondanks, ondanks deze overwinningen, kon het systeem de taken nog steeds niet zo snel verwerken als het oorspronkelijke ontwerpdoel. De onderzoeker concludeerde dat de resterende vertraging geen softwarefout was die hij kon oplossen, maar een fysieke limiet van de machine zelf. De afstand tussen de twee districten en de bandbreedte van de weg die hen verbindt, creëerden een plafond waar geen enkele slimme codering doorheen kon breken met dit ontwerp. Hij rapporteerde zijn bevindingen eerlijk, waarbij hij precies liet zien waar zijn systeem slaagde, waar het faalde en waarom de hardware zelf de uiteindelijke rechter was. Zijn werk dient als een herinnering dat in de wereld van high-speed computing, het begrijpen van de fysieke machine net zo belangrijk is als het schrijven van de code.