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

Moderne Computer sind wie geschäftige Städte aufgebaut, mit mehreren Distrikten, von denen jeder über eigene Rechenleistung und Speicher verfügt. Wenn ein Programm Arbeit verrichten muss, sendet es eine Anfrage an einen bestimmten Distrikt. Wenn die benötigten Daten bereits im lokalen Speicher dieses Distrikts vorhanden sind, geschieht die Aufgabe augenblicklich. Wenn die Anfrage jedoch in einen anderen Distrikt reisen muss, um Informationen abzurufen, dauert die Reise signifikant länger. Diese Verzögerung, die durch die physische Distanz zwischen den Distrikten verursacht wird, ist eine fundamentale Grenze dessen, wie diese Maschinen gebaut sind. Seit Jahrzehnten versuchen Softwareentwickler, Programme zu schreiben, die Daten und die sie nutzenden Arbeiter im selben Distrikt halten, in der Hoffnung, die langsamen Reisen quer durch das Land zu vermeiden. Die Herausforderung besteht darin, dass, wenn viele Arbeiter gleichzeitig auf eine gemeinsame Liste von Aufgaben zugreifen wollen, die Staus, die sie verursachen, genauso schädlich sein können wie die Distanz selbst.

Ein Forscher setzte sich zum Ziel, einen besseren Weg zu entwickeln, um diese gemeinsamen Listen zu verwalten, speziell für Computer mit zwei unterschiedlichen Distrikten. Er entwickelte ein System namens NumaRing, das darauf ausgelegt ist, Arbeiter und ihre Daten nach Möglichkeit lokal in ihrem eigenen Distrikt zu halten. Die Idee war simpel: Wenn ein Arbeiter im ersten Distrikt ist, sollte er nur die Liste im ersten Distrikt betrachten. Wenn diese Liste voll oder leer wird, würde das System dann einen Stapel von Aufgaben in einem Rutsch in den anderen Distrikt bewegen, anstatt sie einzeln zu bewegen. Dieser Ansatz versprach, den schnellen, lokalen Verkehr am Fließen zu halten und gleichzeitig die langsamen, langen Reisen zu minimieren. Doch als der Forscher sein System einem Test unterzog, entdeckte er, dass seine besten Absichten versteckte Fallen bereithielten. Indem er sein System mit extremer Präzision maß, anstatt nur zu raten, wie es funktionierte, fand er heraus, dass zwei spezifische Fehler das System stärker ausbremsten als die Hardware selbst, und dass ein gängiger Ratschlag zur Behebung von Computerverlangsamungen tatsächlich die Dinge verschlimmerte.

Der Forscher begann damit, sein System auf einem Cloud-Computer mit zwei Distrikten aufzubauen, wobei jeder Distrikt sechzehn virtuelle Prozessoren enthielt. Er füllte ihn mit einem stetigen Strom von Aufgaben und beobachtete, wie lange eine Aufgabe von Anfang der Schlange bis zum Ende benötigte. Zu Beginn war das System überraschend langsam. Der Forscher stellte fest, dass jedes Mal, wenn ein Arbeiter versuchte, eine Aufgabe hinzuzufügen oder zu entfernen, die Software eine Frage stellte: „In welchem Distrikt befinde ich mich gerade?“ Diese Frage schien harmlos, aber die Antwort zu berechnen, dauerte lange. Die Software berechnete den Standort jedes Mal von Grund auf neu, obwohl sich der Standort des Arbeiters selten änderte. Diese wiederholte Berechnung war wie ein Fahrer, der an jeder Kreuzung anhält, um nach dem Weg zu fragen, obwohl er genau wusste, wohin er gehen wollte. Die Kosten dieser Frage waren so hoch, dass sie mehr als das Elffache der eigentlichen Anstrengung zum Bewegen der Daten beanspruchten.

Sobald der Forscher dies behob, indem er den Standort speicherte und ihn nur bei Bedarf überprüfte, beschleunigte sich das System dramatisch. Die Anzahl der pro Sekunde verarbeiteten Aufgaben sprang sechs- bis siebenmal höher. Aber die Geschichte endete dort nicht. Als er mehr Arbeiter auf die Maschine setzte, stieß das System gegen eine neue Wand. Die Arbeiter warteten immer noch zu lange, besonders wenn das System unter hohem Druck stand. Bei tieferer Untersuchung fand er ein zweites Problem in der Art und Weise, wie Arbeiter Aufgaben zwischen den Distrikten teilten. Wenn ein Arbeiter einen Stapel von Aufgaben aus einem anderen Distrikt abholen wollte, kämpften alle Arbeiter um denselben kleinen Zähler, um zu entscheiden, wer als Nächstes an der Reihe ist. Dies verursachte einen massiven Stau am Tor. Indem er jedem Arbeiter einen eigenen privaten Zähler gab, beseitigte der Forscher diesen Engpass. Diese Änderung war sogar noch dramatischer und senkte die Zeit, die ein Arbeiter in der Mitte der Schlange warten musste, um mehr als zweihundertfach.

Mit diesen zwei großen Korrekturen im System hatte der Forscher erwartet, dass sein System ein Champion sein würde. Er hatte die Softwarefehler eliminiert, die ihn zurückgehalten hatten. Doch als er die Maschine mit zweiunddreißig Arbeitern an ihre absolute Grenze trieb, konnte das System dennoch nicht die Geschwindigkeit erreichen, die er ursprünglich erhofft hatte. Der Forscher testete daraufhin eine Standardtechnik zur Lösung von Computerverlangsamungen, die sogenannte „Backoff“-Strategie. Die Idee hinter Backoff ist, dass ein Arbeiter, wenn er eine Aufgabe nicht greifen kann, einen winzigen Moment warten sollte, bevor er es erneut versucht, in der Hoffnung, dass sich die Schlange auflöst. In vielen Situationen hilft diese Pause. Aber in dieser spezifischen, unter Hochdruck stehenden Umgebung war die Pause ein Fehler. Der Forscher maß, dass das Warten ihm tatsächlich fünfzehn bis dreißig Prozent seiner Gesamtgeschwindigkeit kostete. Der schnellste Weg war, sofort weiter zu versuchen, da die Hardware den Konflikt bereits effizient genug handhabte, sodass Warten nur Zeit verschwendete.

Das abschließende Bild war eines von sowohl Erfolg als auch harten Grenzen. Der Forscher baute erfolgreich ein System, das Daten lokal hielt und zwei große Softwarefehler behob, die massive Verzögerungen verursachten. Er bewies, dass eine gängige Optimierungsstrategie in bestimmten Hochgeschwindigkeitsszenarien schädlich sein kann. Dennoch, trotz dieser Siege, konnte das System die Aufgaben immer noch nicht so schnell verarbeiten wie das ursprüngliche Designziel. Der Forscher kam zu dem Schluss, dass die verbleibende Verlangsamung kein Softwarefehler war, den er beheben konnte, sondern ein physisches Limit der Maschine selbst. Die Distanz zwischen den beiden Distrikten und die Bandbreite der Straße, die sie verbindet, schufen eine Decke, die kein cleverer Code durch dieses Design hindurch durchbrechen konnte. Er berichtete seine Ergebnisse ehrlich und zeigte genau auf, wo sein System erfolgreich war, wo es scheiterte und warum die Hardware selbst der letzte Richter war. Seine Arbeit dient als Erinnerung daran, dass in der Welt des Hochleistungsrechnens das Verständnis der physischen Maschine genauso wichtig ist wie das Schreiben des Codes.