- Futurelock は、1つのタスクが複数の Future を同時に管理しているとき、そのうちの1つが別の Future のリソースを必要としているにもかかわらず、もはやポーリングされないことで発生する デッドロック(deadlock) 現象
tokio::select! 構文で、参照された Future(&mut future) と await を含む分岐 が一緒に使われると発生しやすい- この問題は タスクと Future の責務分離の失敗 に起因し、同じタスクが2つの Future をともに待ちながら片方だけをポーリングする構造によって停止状態に陥る
- FuturesUnordered、bounded channel、Stream などでも類似の形で発生する可能性がある
- 安全な非同期設計のためには、
tokio::spawn で Future を別タスクに分離するか、select 内で await を使わないことが重要
Futurelock の概念と例
- Futurelock は、Future A が保持するリソース を Future B が必要としているが、2つの Future を担当する タスクが A をもはやポーリングしない 状況で発生する
- 例のコードでは、
tokio::select! 内で &mut future1 と sleep を同時に待ち、sleep が先に完了すると future1 は依然としてロック待ち状態のまま残る
- その後
future3 が同じロックを要求するが、ロックは future1 に割り当てられており、future1 はポーリングされないため、プログラムは永久に停止する
tokio::select! と Mutex の相互作用
tokio::sync::Mutex は 公平(fair) なロックであり、待機順にロックを付与する- ロックは
future1 に渡されるが、タスクはすでに future3 だけをポーリングしているため、future1 は実行されない
- Mutex は次の待機タスクを起こす役割しか持たず、どの Future が実際にポーリングされるかは分からない
Futurelock の一般的な原因
- タスク T が Future F1 を待ち、F1 が F2 に依存し、F2 が再び T のポーリングを必要とする 循環依存構造
- 主に次の状況で発生する
tokio::select! で &mut future を使った後、別の分岐で await を実行するFuturesOrdered または FuturesUnordered で一部の Future 完了後に別の非同期処理を行う- 手動実装された Future で類似の動作がある
Streams およびその他の構造での発生例
FuturesOrdered や FuturesUnordered で Future を取り出したあと、それに関連するリソースを使う別の Future を待つと Futurelock が発生するjoin_all はすべての Future を継続してポーリングするため、Futurelock は発生しない
実例とデバッグ
- Omicron#9259 の事例では、すべてのデータベースアクセス Future が Futurelock に陥り、HTTP リクエストが無限待機になった
mpsc チャネル送信がブロックされていた一方で、受信側は空に見えていたため、原因の特定が難しかった- デバッグ時には
tokio-console のようなツールが役立つ可能性があるが、多くの場合 原因追跡は非常に難しい
Futurelock を防ぐための指針
- 1つのタスクが複数の Future をポーリングするときは、すでに開始した Future のポーリングを中断しないよう注意する
- 可能であれば Future を 新しいタスクとして spawn して独立実行させる
JoinHandle を tokio::select! に渡せば Futurelock のリスクを除去できる
tokio::select! 使用時の注意点
&mut future と await を同時に使わないこと- 両方の条件がそろうと Futurelock のリスクが高い
Stream 使用時は JoinSet を活用して各 Future を別タスクとして実行するbounded channel の容量を増やすことは根本的な解決策ではない
- 代わりに
try_send() を使ってブロッキングを回避できる
誤った回避パターン
- チャネル容量を無限に増やす方法 は非現実的であり、副作用として遅延やメモリ増加を招く
- Future 間の依存関係をなくそうとする試み は、保守中に新たな依存が生じる可能性があり脆弱
- 唯一安全な方法は
tokio::spawn によるタスク分離
今後の改善とセキュリティ上の考慮
- Clippy lint によって、
tokio::select! 内での &mut future の使用や await を含む場合に警告を出せる可能性が示されている
- Futurelock は サービス拒否(DoS) の形で悪用される可能性があるが、本質的には 異常動作 であるため予防が必要
1件のコメント
Hacker Newsのコメント
文書をざっと読んだ感じ、かなり透明性が高く徹底したレポートのように思えた
特に脚注の部分が興味深かった
Rustのcancellation safetyの問題を知らなかった人が多く、Omicron全体にこうした問題が広がっている可能性が高いという点が印象的だった
Rustを選んだ理由がCのメモリ安全性の問題を避けるためだったのに、今回はランタイムで捉えにくいcancellationバグが発生するというのは皮肉に感じられた
コンパイラが助けてくれない動的な性質をプログラマが自分で保証しなければならないという点が、特にもどかしかった
Rustの並行性モデルでも依然としてデッドロックの可能性が存在するようだ
RAIIスタイルのリソース管理がこうした問題を防いでくれそうなのに、実際にはそうではない点が混乱を招く
これが単なる実装上の偶然なのか、それともRust/Tokioモデルの構造的な限界なのか気になる
これはwithoutboatsのFuturesUnorderedの記事で説明されていたデッドロックの微妙な変種のように見える
“intra-task”並行性を使うときは、どのfutureも飢餓状態に陥らないよう注意しなければならない
基本的にはtaskをspawnするのが安全で、
tokio::select!でtimeoutを処理する場合でも、すべてのpending futureをその中で管理すべきだFuturesUnorderedは本当にあらゆるエッジケースをテストしない限り勧めにくいこれは優先度逆転(priority inversion)の問題に似て聞こえる
OSでは低優先度スレッドがロックを保持しているときに高優先度スレッドが待つと、低優先度側が優先度継承を受けて実行される
Tokioでも似た概念を適用できるのか気になる — たとえば、実行不能なfutureがMutexを保持しているなら、そのfutureを代わりにpollするような形で
ただし、「実行不能」状態を検知するにはかなりのオーバーヘッドがかかりそうだ
このアプローチはTokioのtask単位では可能かもしれない
しかし、task内部のfutureには適用できない
async Rustの基本設計が「futures are inert」だからだ — futureは単なる構造体にすぎず、ランタイムはその内部を知ることができない
ランタイムが把握しているのはtask単位だけで、内部futureの状態はまったく追跡しない
Rustのasyncはstackless coroutineモデルなので、すでに実行中のasync関数の実行を任意に継続するのは安全ではない
stacklessモデルはローカル状態を共有スタックに保存するため、LIFO順でしか安全に実行できない
そのためcoloringが必要で、stackful coroutineのように自由にyieldすることはできない
コードがあまりにも複雑に感じる
Erlang、Elixir、Go、さらにはCで書く場合よりもずっと冗長に見える
これは基本的な2ロックデッドロックに似ていると思う
TokioのMutex待機キューとtaskスケジューリングが互いに絡み合ってデッドロックを作る構造だ
OS Mutexなら別の待機スレッドを起こして解決できただろうが、async Rustではfutureの状態マシン構造のため難しいと思う
待機キューのfutureを順番にpollする形で解消できるかもしれないが、それはまた予期しない副作用を生みかねない
async Rustエコシステムでこうした問題を一緒に扱った経験がある
select!で参照を使えないようにすればこうした問題は避けられるが、そうするとキュー上の位置を失わずに繰り返しselect!するパターンが不可能になるcancellationの問題と合わせて、こうした点はRustの専門家にとっても予想外の落とし穴になり得る
それでもコールバックベースのコードより驚きはずっと少ない
そのとおりで、私たちのチームもこのデッドロックを分析したあと「これをどう防げたのか？」を議論したが、誰のせいでもなかったという結論に至った
Tokioのすべてのプリミティブは意図どおりに動作し、コードも正しく書かれていたのに、相互作用によって予期しないデッドロックが生まれたのだ
&mut futureをselect!で禁止すれば防げるが、それでは多くの正当なコードまで妨げてしまう結局、「ただ気をつけるしかない部分だ」という苦い結論に達した
関連する議論はこのコメントでも続いている
select!が選ばれなかったfutureをdropせずに返すようにすれば、状態を失わずに済むただしこれは不便で、根本的な解決策ではない
本当の原因はこのスレッドで説明されているとおり、cancellation処理の不完全さにある
FAQにあった「future1はキャンセルされないのか？」という質問が興味深かった
cancellationには二つの段階がある — pollの停止とdropだ
この例ではdropが遅延され、そのせいでguardを持ち続けて副作用が起きている
この二つの動作が常に同時に起こるよう保証できるのか考えさせられる
Rustの設計者に聞いてみたい — なぜactorモデルではなくasyncパターンを選んだのか
Erlangを使ってみると、actorモデルの方がずっとクリーンで安全に感じられる
JSは言語構造上asyncを使うしかなかったが、Rustは新しい言語だったのに、なぜその道を選んだのか気になる
Rustのasync設計では組み込み環境のサポートが大きな理由だった
mallocやスレッドを使わずに動作しなければならなかったため、actorモデルは不可能だった
Tokioでactorスタイルのコードを書くことはできるが、自然ではない
もう一つの理由は性能だ
actorモデルはメッセージコピーのコストが大きく、Rustは性能が重要なシステム言語なので、async state machineによるzero-cost abstractionを目指した
ErlangやGoは別のトレードオフを選んだ言語だ
RustはC FFI呼び出し時のオーバーヘッドを許容しない方針だったため、green threadベースのモデルは排除された
async/awaitは状態マシンにコンパイルされるためオーバーヘッドが少ない
Goも初期にはpreemptionがなく、同様の飢餓問題があったが、後にスケジューラがこれを解決した
結局のところ、言語ごとに異なる目標と制約があったということだ
私もOxideがasyncを採用したのは意外だった
組み込みやHTTPサーバーでは見慣れているが、Oxideのようなシステム企業でもここまで深く使うとは思わなかった
文書を読んでいて理解できなかったのは、なぜロックを保持しているfutureではなくメインスレッドが起こされるのかという点だった
公平なロックならfuture1が起こされるはずなのに、なぜランタイムが別のスレッドを選んだのか不思議だった
記事は本当に興味深かった
サンプルコードも明確だったし、こういうバグを見つけるのは悪夢のようだが、見つかったあとにパズルのピースがはまる快感がある
Eliza、Sean、John、Daveの4人が一緒にブレインストーミングしながら原因を突き止めていく場面が印象的だった
月曜日にこの内容を扱うポッドキャストのエピソードを公開する予定だ
関連映像はRFD 537とこのイベントリンクで見られる
Rustがすべてのアクティブなtaskを同時に進行させないのは、理解しづらくバグを量産しやすい設計のように見える
PythonのTrioのようにstructured concurrencyを導入した方が直感的なのではないかと思う
Rustでもこうしたモデルを導入できるのか気になる
Rustでもstructured concurrencyは可能だが、task単位でしか適用されない
futureは単にpollされて初めて進行する構造体にすぎないので、「アクティブなfuture」という概念がない
すべてをtaskとしてspawnすれば解決するようにも見えるが、それでも一部の有用なパターンを妨げてしまう
taskとfutureの区別が重要だ
futureはpollされなければ何もしない
cancellationを「dropされるまでpollされない状態」と定義すると、今回の問題のようにロックを握ったまま止まるfutureが生まれる
RustのRAII哲学ではdrop時のクリーンアップを期待するが、pollが止まった状態ではそれすら起こらない
最近見ていると、Rustのasyncはあまりにも急いでリリースされたのではないかという気がする
Pinや文法の一部は洗練できるだろうが、根本構造を変える必要はない
まだ「家を完成させていない基礎工事」の段階にすぎず、急ぎすぎた結果というわけではない
ただ、汎用的なcoroutineのような下位レイヤーはもっと必要だと思う