Futurelock: Subtiles Deadlock-Risiko in asynchronem Rust

• Futurelock ist ein Deadlock, der entsteht, wenn ein einzelner Task mehrere Futures gleichzeitig verwaltet, eines davon jedoch eine Ressource eines anderen Futures benötigt und dieses nicht mehr gepollt wird
• Tritt besonders leicht auf, wenn in tokio::select! referenzierte Futures (&mut future) zusammen mit Branches mit await verwendet werden
• Das Problem entsteht durch ein Scheitern der Trennung von Verantwortlichkeiten zwischen Task und Future: Derselbe Task wartet auf beide Futures, pollt aber nur noch eine Seite und gerät dadurch in einen Stillstand
• Ähnliche Formen können auch bei FuturesUnordered, bounded channel und Stream auftreten
• Für ein sicheres asynchrones Design ist entscheidend, Futures mit tokio::spawn in separate Tasks auszulagern oder await innerhalb von select zu vermeiden

---

Konzept und Beispiel von Futurelock

• Futurelock tritt auf, wenn Future A eine Ressource hält, die Future B benötigt, der Task, der beide Futures verwaltet, A aber nicht mehr pollt
• Im Beispielcode wird innerhalb von tokio::select! gleichzeitig auf &mut future1 und sleep gewartet; wenn sleep zuerst fertig wird, bleibt future1 weiter im Wartestatus auf das Lock
• Danach fordert future3 dasselbe Lock an, aber das Lock ist future1 zugeteilt, und da future1 nicht gepollt wird, bleibt das Programm dauerhaft stehen

Zusammenspiel von tokio::select! und Mutex

• tokio::sync::Mutex ist ein faires (fair) Lock und vergibt das Lock in der Reihenfolge des Wartens
• Das Lock wird an future1 übergeben, aber der Task pollt bereits nur noch future3, sodass future1 nicht ausgeführt wird
• Der Mutex kann nur den nächsten wartenden Task wecken, weiß aber nicht, welches Future tatsächlich gepollt wird

Allgemeine Ursachen von Futurelock

• Eine zyklische Abhängigkeitsstruktur, bei der Task T auf Future F1 wartet, F1 von F2 abhängt und F2 wiederum das Polling durch T benötigt
• Tritt vor allem in folgenden Situationen auf
  • Verwendung von &mut future in tokio::select!, gefolgt von await in einem anderen Branch
  • Ausführen anderer asynchroner Arbeit nach Abschluss einzelner Futures in FuturesOrdered oder FuturesUnordered
  • Ähnliches Verhalten in manuell implementierten Futures

Auftreten bei Streams und anderen Strukturen

• In FuturesOrdered oder FuturesUnordered kann ein Futurelock entstehen, wenn nach dem Herausnehmen eines Futures auf ein anderes Future gewartet wird, das eine damit verbundene Ressource verwendet
• join_all pollt weiterhin alle Futures und verursacht daher keinen Futurelock

Praxisfall und Debugging

• Im Fall Omicron#9259 gerieten alle Futures für Datenbankzugriffe in einen Futurelock, wodurch HTTP-Anfragen unbegrenzt warteten
• Das Senden über einen mpsc-Channel war blockiert, während die Empfängerseite als leer erschien, was die Ursachenanalyse erschwerte
• Beim Debugging können Tools wie tokio-console helfen, in den meisten Fällen ist die Ursachenverfolgung jedoch sehr schwierig

Richtlinien zur Vermeidung von Futurelock

• Wenn ein Task mehrere Futures pollt, muss darauf geachtet werden, das Polling bereits gestarteter Futures nicht zu unterbrechen
• Wenn möglich, Futures als neue Tasks spawnen und unabhängig ausführen lassen
  • Wird ein JoinHandle an tokio::select! übergeben, entfällt das Risiko eines Futurelocks
• Vorsicht bei der Verwendung von tokio::select!
  • &mut future und await nicht gleichzeitig verwenden
  • Wenn beide Bedingungen zusammen auftreten, ist das Futurelock-Risiko hoch
• Bei der Verwendung von Stream sollte JoinSet genutzt werden, um jedes Future in einem separaten Task auszuführen
• Die Kapazität eines bounded channel zu erhöhen, ist keine grundlegende Lösung
  • Stattdessen kann mit try_send() Blockieren vermieden werden

Fehlerhafte Vermeidungsstrategien

• Die Channel-Kapazität unbegrenzt zu erhöhen ist unrealistisch und verursacht Nebenwirkungen wie Latenz und höheren Speicherverbrauch
• Zu versuchen, Abhängigkeiten zwischen Futures zu entfernen, ist fragil, da bei der Wartung neue Abhängigkeiten entstehen können
• Die einzig sichere Methode ist die Trennung in separate Tasks mittels tokio::spawn

Zukünftige Verbesserungen und Sicherheitsaspekte

• Es wird vorgeschlagen, über Clippy-Lints Warnungen auszugeben, wenn in tokio::select! &mut future verwendet wird oder await enthalten ist
• Futurelock kann in Form eines Denial of Service (DoS) ausgenutzt werden, ist aber im Kern ein Fehlverhalten, das verhindert werden sollte

[GN⁺]

Hacker-News-Kommentare

• Beim Überfliegen des Dokuments wirkte es auf mich wie ein ziemlich transparentes und gründliches Gutachten
  Besonders der Fußnotenabschnitt war interessant
  Eindrucksvoll fand ich, dass vielen das Problem der cancellation safety in Rust nicht bekannt war und dass sich solche Probleme vermutlich in ganz Omicron verbreitet finden
  Man hatte sich für Rust entschieden, um die Problems der Speichersicherheit von C zu vermeiden, und nun entstehen stattdessen ironischerweise Cancellation-Bugs, die zur Laufzeit schwer zu erfassen sind
  Besonders frustrierend ist, dass Programmierer dynamische Eigenschaften selbst garantieren müssen, bei denen der Compiler nicht helfen kann

  • Ich frage mich, ob man zur Vermeidung solcher Probleme nicht eine höhere Abstraktionsebene braucht
    Es scheint, als gebe es auch im Nebenläufigkeitsmodell von Rust weiterhin die Möglichkeit von Deadlocks
    Man könnte denken, dass Ressourcenverwaltung im RAII-Stil solche Probleme verhindern müsste, aber offenbar ist das nicht der Fall
    Ich frage mich, ob das nur ein Implementierungszufall ist oder eine strukturelle Grenze des Rust-/Tokio-Modells

• Das wirkt wie eine subtile Variante des Deadlocks, der im FuturesUnordered-Artikel von withoutboats beschrieben wird
  Bei der Nutzung von “intra-task”-Nebenläufigkeit muss man darauf achten, dass kein Future verhungert
  Im Grunde ist es sicherer, Tasks zu spawnen und Timeouts mit tokio::select! zu behandeln, wobei alle pending Futures darin verwaltet werden sollten
  FuturesUnordered würde ich nur empfehlen, wenn wirklich alle Edge Cases getestet wurden

• Das klingt ähnlich wie ein Problem der priority inversion
  In Betriebssystemen erbt ein Thread mit niedriger Priorität die Priorität, wenn ein Thread mit hoher Priorität warten muss, während der niedrig priorisierte den Lock hält
  Ich frage mich, ob man ein ähnliches Konzept auch in Tokio anwenden könnte — etwa indem man ein nicht lauffähiges Future anstelle pollt, wenn es ein Mutex hält
  Allerdings dürfte es ziemlich viel Overhead verursachen, den Zustand „nicht lauffähig“ zu erkennen

  • Auf Task-Ebene könnte so ein Ansatz in Tokio vielleicht möglich sein
    Auf Futures innerhalb eines Tasks lässt er sich aber nicht anwenden
    Der Grund liegt im Grunddesign von async Rust: „futures are inert“ — ein Future ist nur eine einfache Datenstruktur, und die Runtime kennt sein Inneres nicht
    Die Runtime kennt nur die Task-Ebene und verfolgt den Zustand interner Futures überhaupt nicht

  • Rusts async folgt einem stackless-coroutine-Modell, deshalb ist es nicht sicher, die Ausführung einer bereits laufenden Async-Funktion beliebig fortzusetzen
    Im stackless-Modell wird lokaler Zustand auf einem gemeinsam genutzten Stack gespeichert, daher ist sichere Ausführung nur in LIFO-Reihenfolge möglich
    Deshalb braucht man Coloring und kann nicht wie bei stackful Coroutines frei yielden

  • Der Code wirkt viel zu komplex
    Er sieht deutlich umständlicher aus als in Erlang, Elixir, Go oder sogar C

  • Ich halte das für ähnlich wie einen grundlegenden 2-Lock-Deadlock
    Tokios Mutex-Warteschlange und das Task-Scheduling greifen ineinander und erzeugen so den Deadlock
    Bei einem OS-Mutex hätte man das wohl lösen können, indem man einen anderen wartenden Thread weckt, aber in async Rust ist das wegen der Zustandsmaschinenstruktur der Futures schwierig
    Man könnte es vielleicht lösen, indem man die Futures in der Warteschlange nacheinander pollt, aber das könnte wiederum unerwartete Nebenwirkungen haben

• Ich habe in der async-Rust-Umgebung schon erlebt, wie man gemeinsam mit solchen Problemen umgeht
  Wenn man in select! keine Referenzen zulässt, kann man solche Probleme vermeiden, aber dann wird das Muster unmöglich, wiederholt select! auszuführen, ohne die Queue-Position zu verlieren
  Zusammen mit den Cancellation-Problemen kann das selbst für Rust-Experten eine unerwartete Falle sein
  Trotzdem gibt es weit weniger Überraschungen als bei callback-basiertem Code

  • Genau, unser Team hat nach der Analyse dieses Deadlocks ebenfalls diskutiert: „Wie hätte man das verhindern können?“ — und ist zu dem Schluss gekommen, dass niemand schuld war
    Alle Tokio-Primitiven funktionierten wie vorgesehen, und auch der Code war korrekt geschrieben, aber ihr Zusammenspiel erzeugte einen unerwarteten Deadlock
    Man könnte ihn verhindern, indem man &mut future in select! verbietet, aber das würde auch viel legitimen Code verhindern
    Am Ende blieb die bittere Schlussfolgerung: „Da muss man einfach vorsichtig sein“
    Die zugehörige Diskussion geht auch in diesem Kommentar weiter

  • Wenn select! die nicht ausgewählten Futures zurückgäbe, statt sie zu droppen, könnte man den Zustand erhalten
    Das wäre allerdings unpraktisch und keine grundlegende Lösung
    Die eigentliche Ursache liegt, wie in diesem Thread erklärt, in der Unvollständigkeit der Cancellation-Behandlung

• Die FAQ-Frage „Wird future1 nicht abgebrochen?“ fand ich interessant
  Cancellation hat zwei Phasen — das Einstellen des Pollens und das Droppen
  In diesem Beispiel wird das Droppen verzögert, sodass der Guard weiter gehalten wird und Nebenwirkungen entstehen
  Ich frage mich, ob man garantieren könnte, dass beide Vorgänge immer gleichzeitig passieren

• Ich würde den Rust-Designern gern die Frage stellen: Warum hat man sich für ein Async-Muster statt für das Actor-Modell entschieden?
  Nach Erfahrungen mit Erlang wirkt das Actor-Modell deutlich sauberer und sicherer
  JavaScript musste wegen seiner Sprachstruktur auf async setzen, aber Rust war eine neue Sprache — deshalb frage ich mich, warum man diesen Weg gewählt hat

  • Ein wichtiger Grund für das async-Design in Rust war die Unterstützung von Embedded-Umgebungen
    Es musste auch ohne malloc oder Threads funktionieren, daher kam ein Actor-Modell nicht infrage
    Man kann mit Tokio Code im Actor-Stil schreiben, aber natürlich fühlt sich das nicht an

  • Ein weiterer Grund ist die Performance
    Beim Actor-Modell sind die Kosten für das Kopieren von Nachrichten hoch, und Rust als systemnahe Sprache mit Fokus auf Leistung strebte mit Async-State-Machines eine zero-cost abstraction an
    Erlang und Go haben eben andere Trade-offs gewählt

  • Da Rust bei C-FFI-Aufrufen keinen zusätzlichen Overhead zulassen wollte, wurde ein Modell auf Basis von green threads ausgeschlossen
    async/await wird in Zustandsmaschinen kompiliert und hat dadurch wenig Overhead
    Go hatte anfangs ebenfalls keine Preemption und litt daher unter ähnlichen Starvation-Problemen, die später durch den Scheduler gelöst wurden
    Letztlich hatten die Sprachen einfach unterschiedliche Ziele und Randbedingungen

  • Auch ich war überrascht, dass Oxide async übernommen hat
    Für Embedded oder HTTP-Server ist das vertraut, aber ich hätte nicht erwartet, dass eine Systemfirma wie Oxide es so tiefgehend einsetzt

• Beim Lesen des Dokuments war für mich unklar, warum der Main-Thread und nicht das Future mit gehaltenem Lock aufgeweckt wird
  Bei einem fairen Lock müsste eigentlich future1 aufgeweckt werden, deshalb frage ich mich, warum die Runtime einen anderen Thread ausgewählt hat

• Der Artikel war wirklich interessant
  Auch der Beispielcode war klar, und obwohl das Finden solcher Bugs ein Albtraum ist, gibt es beim Auffinden dieses Gefühls, dass die Puzzleteile zusammenpassen

  • Unser Unternehmen zeichnet alle Meetings und Debugging-Sessions auf, und genau dieser Moment, in dem „das Puzzle zusammenpasst“, ist auf Video festgehalten
    Es war eindrucksvoll zu sehen, wie Eliza, Sean, John und Dave gemeinsam Brainstorming betrieben und der Ursache auf die Spur kamen
    Am Montag wollen wir dazu eine Podcast-Episode veröffentlichen
    Das zugehörige Video gibt es in RFD 537 und unter diesem Event-Link

• Dass Rust nicht sicherstellt, dass alle aktiven Tasks gleichzeitig Fortschritt machen, wirkt auf mich wie ein schwer verständliches und fehleranfälliges Design
  Mit structured concurrency wie in Python Trio wäre das vielleicht intuitiver
  Ich frage mich, ob Rust so ein Modell ebenfalls einführen könnte

  • Structured concurrency ist in Rust ebenfalls möglich, aber nur auf Task-Ebene
    Ein Future ist lediglich eine Datenstruktur, die nur dann Fortschritt macht, wenn sie gepollt wird; ein Konzept wie „aktives Future“ gibt es nicht
    Wenn man alles als Task spawnt, scheint das Problem gelöst, aber damit verhindert man wiederum einige nützliche Muster

  • Die Unterscheidung zwischen Task und Future ist wichtig
    Ein Future tut gar nichts, wenn es nicht gepollt wird
    Definiert man Cancellation als den Zustand „wird nicht mehr gepollt, bis es gedroppt wird“, entstehen wie hier Futures, die mit gehaltenem Lock stehen bleiben
    In Rusts RAII-Philosophie erwartet man Cleanup beim Drop, aber wenn das Pollen stoppt, passiert selbst das nicht

• In letzter Zeit denke ich öfter, dass Rusts async vielleicht zu überhastet veröffentlicht wurde

  • Ich finde auch, dass es viel zu verbessern gibt, aber das Grunddesign selbst ist eine hervorragende Basis
    Pin oder Teile der Syntax kann man verfeinern, aber an der grundlegenden Struktur muss man nichts ändern
    Wir sind eher noch in der Phase eines „Fundaments für ein Haus, das noch nicht fertig gebaut ist“, nicht bei einem überstürzten Ergebnis
    Allerdings glaube ich, dass noch eine tiefere Schicht wie generalisierte Coroutines nötig ist