2026/04/09 2:36
Surelock：Rust 用のデッドロックフリーミューチュエックス
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
surelock ライブラリは、ロック安全性をコンパイル時に証明することで Rust プログラムがデッドロック不可能であることを保証し、危険な実行時チェックやパニックの必要を取り除きます。このアプローチは、従来の手法が沈黙して失敗することが多い並行プログラミングにおける主要な信頼性課題に対処します。システムは、2 つの特別なメカニズムによってカーフマン（Coffman）の循環待機条件を破ることでこれを達成します：LockSet は、同じレベル内での原子化ロックを管理し、一意で単調増加する ID を使用して決定論的な順序を確保し、Level は、異なるロックレベル間の厳格な全順序を強制してサイクルを防ぎます。設計は、happylock プロジェクトからのような概念（例：原子能力トークン）を取り入れていますが、より安定したアドレスを得るためにこれらの ID を使用することでそれらを改善しています。lock_tree などのツールで使われるより複雑な依存関係グラフとは異なり、surelock は、コンパイラが簡単にチェックできるこの厳格な順序付けシステムを用いて検証を簡素化します。柔軟性を必要とする開発者向けに、
Mutex::unchecked_lock()unsafethiserrorportable-atomiccritical-sectionunsafe本文
こんにちは、r/rust の皆様！
この作業への関心と、誠に楽しい対話に心から感謝申し上げます ❤️
私はデッドロック（互斥排他によるシステム停止）を嫌います。おそらく皆様も同様でしょう。Fission に在籍していた頃は、誰かが Mutex の導入を提案するたびに、「Mutex は NG！」というチャントが始まりました。「Mutex！DEADLOCK！Mutex！DEADLOCK！」という掛け声です。デッドロックは潜伏しており、コードレビューでは完全に目に見えないし、CI を何千回もパスさせられた挙句、誰も予期しないリクエストパターンが 3 時の深夜にシステムをロックアウトさせてしまうこともあります。
デッドロックには独自のトレードオフがありますが、Haskell の TVars は懐かしいです。純粋性（purity）を保証できない言語では、本物の TVar を実装する方法がないと考えられています。私たちは「锁フリープログラミング」を好むべきですが、Rust の標準的なスタイルでも Mutex が非常に一般的です。「アクターモデルはデッドロックを排除する」とよく聞きますが、Elixir でそれなりのコードを書いた者として告げるのは、これは 100%の嘘です（ただし発生頻度は少ないことは事実）。
Rust は有名なようにコンパイル時に関データ races（データ競合）を検出しますが、デッドロックについてはどうでしょうか？Mutex を受け取り、背中をポンして「がんばってね、ベイベー」と言われるだけです。コード分析に役立ついくつかのツールは存在しますが、開発中のフィードバックを求めています。私はこの問題へのより良いアプローチについてしばらく考えており、他のいくつかの試みも検討した結果、Rust の多くの一般的な使用ケースをカバーすると考えられる、使いやすさと機能性のバランスが良いと思われる「surelock」というデッドロックフリーなライブラリを実現しました。コードがコンパイルさえすれば、デッドロックしません。Result も Option もなく、ロック経路でのランタイムパニックもありません。すべての取得は、コンパイラーによって安全性が証明されているか、ビルド時に拒絶されます¹。
これはプレリリース版です。コアな設計は堅固だと考えますが、荒削りの部分があることに驚かないのはむしろ自然でしょう。フィードバックとコントリビューションを大歓迎します！
TL;DR
- デッドロックは、Coffman の 4 つの条件が同時に満たされた時に発生する
- Surelock は「循環待機（circular wait）」という条件を、2 つの補完的なメカニズムによって破る
- 同じレベルのロックは、原子かつ決定論的な順序で取得される (LockSet)
- 異なるレベルのロックは、累積的に取得され、コンパイル時の順序強制が施される (Level)
- 全体の公開 API は安全 — unsafe はローカルの Mutex 内部に限定されている
- no_std 互換であり、ランタイム依存関係は zero（ゼロ）²
なぜ注意するだけではダメなのか？
正直な答えは、「注意すればいい」という考え方はスケールしないからです。コードを組み立てる過程で、足を引っ掛けるのは簡単です。「待ってください、それが Rust が私たちに助けてくれるべきことではないですか？」 borrow チェッカーはコンパイル時にデータ競合を捉えるので、デッドロックについても同じことが期待できないでしょうか？
根本的な問題はよく理解されています。Coffman らは 1971 年にデッドロックが発生するための 4 つの必要条件を特定しました：
| 条件 | 意味 |
|---|---|
| 相互排他 (Mutual exclusion) | 少なくとも一つの資源が排他的に保持されている |
| 保持かつ待機 (Hold and wait) | スレッドは一つのロックを持ちながら、別のロックを待っている |
| 先行不能性 (No preemption) | ロックは強制的に取り上げられない |
| 循環待機 (Circular wait) | 待機グラフにサイクルが存在する |
これらの条件の一つでも破れば、デッドロック是不可能になります。相互排他こそが Mutex の存在意義であり、先行不能性は新たな種類のバグを引き起こします。残ったのは「保持かつ待機」と「循環待機」です。
私たちは 50 年以上も前に（！）解決策の空間を特定しました。非常に棘のある問題で、合意された単一の解決策がないのに、Mutex は十分に有用なので依然として使用されています。これは、何か Mutex を完全に置き換えるものが出るまで、Mutex を安全に使うためのユーザビリティ（使いやすさ）向上が領域だということです。
安全性技術が正確に安全な使用法と一致するのは稀です。型システムは、いくつかの不整合を許容するか、正当な用途を排除するか（あるいは両方）してしまうことで有名です — そのために、不整合を排しつつすべての安全な使用法を直接表現できるより洗練された型システムを作るための多大な努力が続けられています。鍵は、扱うのに最も容易で論理的なモデルを導入しながら、それらを可能な限り一致させることにあります。私は、ツールたちが私たち自身に問題について考える手助けをするようにしたいと考えます。
Surelock は物理世界の比喩を基盤としています：ロックと相互作用するには鍵が必要です。当方でいうと、Mutex が使用中である間はその鍵を保持し、解凍するまで鍵を返すだけです。 これを
MutexKey.lock()💡 これが核心となるトリックです：鍵を移動しかできない値として作り、すべての取得を通じて流すことで、現在のロック状態のコンパイル時検証（witness）を得られます。グローバルな分析もランタイムでの追跡も不要 — 型チェッカーが最も得意とすることをします。
この比喩はこれだけで尽きませんが：
MutexKey先行事例（Prior Art）
設計に影響を与えた既存のライブラリが 2 つあり、それらに適切なクレジットを付けたいと思います。
happylock
- botahamec が、能力トークンとソートされた複数ロック取得を組み合わせてデッドロックを防ぐという核心的な洞察を導入しました。Surelock はこのパターンを直接借用しています。
- 両者のアプローチが異なる点：happylock は「保持かつ待機」の条件を破ります。コレクションを通じてロックすると、鍵が消費され、解放されるまで全く新たなロックを取得できません。これは安全ですが、「設定を読み、どのアカウントを更新するか読む、次にそのアカウントをロックする」といったことは不可能です。累積的な取得が必要な並行システムにおいて、これは実質的な制限です — 累積的なロックが必要な場合は、真に累積的なロックが必要です。
- happylock はまた、メモリアドレスによってロックをソートしますが、Vec の再割り当てや移動では安定しません。ライブラリはアドレスの安定性を維持するために unsafe（Box::leak, transmute など）を用い、その不安全性が公開 API に波及します。
lock_tree
- Google の Fuchsia プロジェクトから、
特異体によるコンパイル時ロック順序を導入しました。レベル A がレベル B より来ると宣言し、逆順で取得しようとするコードはコンパイラーが拒絶します。LockAfter - Surelock はこれをいくつかの点で拡張しています：同じレベルでのマルチロック（lock_tree は表現できない）、
を通じたインスタンスごとのレベル割り当て、スコープ唯一性強制など。Surelock は意図的に lock_tree の DAG ベースの順序付けを厳密な全順序に替えており、その理由は後述します。new_higher
二重メカニズム設計
Surelock は 2 つのメカニズムを使用し、補完的なケースをカバーします。両者は重複しません：
| メカニズム | 何时 | 取得強制 |
|---|---|---|
| LockSet | 同じレベルでの複数のロック | 原子操作（全か無か）ランタイムで安定 ID でソート |
| Levels (Level) | 異なるレベルのロック | 累積的コンパイル時特異体境界 |
同じレベル：LockSet
各 Mutex は作成時にグローバルな
AtomicU64LockIdlet alice = Mutex::new("alice"); let bob = Mutex::new("bob"); // アーグメントの順序に関係なく、取得順序は決定論的 let set = LockSet::new((&alice, &bob)); key_handle.scope(|key| { let (a, b) = set.lock(key); // 両方ロック済み、デッドロック不可能 });
スレッド A スレッド B │ │ ▼ ▼ LockSet::new((&acct_1, &acct_2)) LockSet::new((&acct_2, &acct_1)) │ │ ▼ ▼ sorted: [acct_1, acct_2] sorted: [acct_1, acct_2] │ │ ├─ acct_1 のロックを取得 │ │ ├─ acct_1 のロックを待つ ├─ acct_2 のロックを取得 │ │ │
│ │ ├─ acct_2 を解放 │ │ │ (まだ lock 1 を待っている) ├─ acct_1 を解放 │ │ ├─ acct_1 のロックを取得 │ ├─ acct_2 のロックを取得 │ │ ▼ ▼ OK OK (サイクル不可能) #### 異なるレベル：コンパイル時順序付け ロックが異なる種類の資源を表す場合（例えば、設定ガード対アカウント別ロック）は、異なるレベルに割り当てます。`Level<N>` タイプと `LockAfter` 特異体境界は、厳密な昇順の取得を強制します： ```rust use surelock::level::{Level, lock_scope}; type Config = Level<1>; type Account = Level<2>; let config: Mutex<_, Config> = Mutex::new(AppConfig::default()); let account: Mutex<_, Account> = Mutex::new(Balance(0)); lock_scope(|key| { let (cfg, key) = config.lock(key); // レベル 1 -> OK let (acct, key) = account.lock(key); // レベル 2 で 1 の後 -> OK // account.lock(key) 次に config.lock(key) -> コンパイルエラー }); ``` 鍵（ハッ！）は `MutexKey` です。各 `lock()` 呼び出しで消費され、新しいレベルで再発射されます。後ろ向きに行おうとして（例えば `Level<3>` に続いて `Level<1>` を取得しようとした場合）、`LockAfter` 境界が満たされないため、コンパイラーは親切な（カスタム）エラーメッセージを出力して拒絶します。 #### なぜ全順序ではなく DAG か？ これは意図的な設計決定です。`lock_tree` は DAG を使用し、ブランチ A と B が相互依存せず、互いに優先されなくてもよいことを宣言できます。素晴らしいようですが、微妙な問題があります：スレッド 1 が A 然後 B を取得し、スレッド 2 が B 然後 A を取得し、両方の順序付けが DAG で有効なら、コンパイラーが快く承認したデッドロックが発生します。 ロックは `(Level, LockId)` によって全順序でソートされます。全順序はより制限的ですが、実際には健全です。システムで参加する 2 つのロックがあれば、それらの相対的な順序は固定されます。概念的に DAG を線形化することもできます（多くの操作ベース CRDT のように）が、それは論理的になりにくく、追加の機構を多数加えることになります。 ### キーの取得 両方のメカニズム（LockSet とレベル）は `MutexKey` を使用します。鍵をスコープの一種と考えられます：各 `lock()` 呼び出しで消費され、新しいレベルで再発射されます。同一不変ライファイトタイム（同じ技法として `std::thread::scope` のように）でブランド付けされており、クロージャーから逃げることはできず、`!Send` なので作成スレッドにとどまります。 取得方法は暗黙的と明示的な 2 つあります。 #### 暗黙的：lock_scope 多くの人がこれを使うはずです。std 上では `lock_scope` は内部にすべてのセットアップを処理し、単に書けば： ```rust use surelock::{Mutex, lock_scope}; let data = Mutex::new(42); lock_scope(|key| { let (guard, key) = data.lock(key); assert_eq!(*guard, 42); }); ``` 内部では、`lock_scope` は `thread_local! KeyHandle` を管理します。`KeyHandle` の `scope` メソッドは `&mut self` を取るので、borrow チェッカーがネストされたスコープを防止し、アクティブなスコープの中で新しいロックスコープを開始することはできません。 #### 明示的：Locksmith と KeyVoucher no_std、組み込み、あるいはどのコアがどの能力を受け取るかより厳密に制御したい場合のために、完全に明示的な連鎖があります： - **Locksmith**: プロジェクト全体でのシングルトン（`!Send`）。`KeyVouchers` を発行し、これらは `Send` なので、セットアップ中にキーをスレッド間で分散できます。voucher は宛先スレッドで交換され、`KeyHandle` が得られ、これは `!Send` で元の場所にとどまります。 - これは多くの式（ceremony）のように聞こえますが、主に安全不変を強制するための型機構です。bare metal で `thread_local!` がない場合、このレベルの制御は望ましく、初期化時にどのコアが鍵を受け取るかを正確に決めることができます、型システムにより他の誰も空から鍵を作り出すことはできません。 ### 図表 以下に図解例を示します。ロックレベルは厳密なコンパイル時シーケンスにあることがわかりますが、ランタイムで割り当てられるロック ID は任意の順序で表示されます。これは完全に問題ありません；それらは単にすべての呼び出し元之间で一致している必要があります。 ここでは、レベル 0 より「上」をロックできるルートキーから始めます。2 つのレベルにわたってロックを取得し、ID でソートしてその順序で取得します（以前的时间軸で説明した理由により）。これはルートキーを消費し、レベル 2 より上のロックができるキーを放出します。将来的には、レベル 3 と以降をロックでき、解放するまで以前の鍵を回収できます。 ``` Key{Level > 0} │ ┌─────────Level 1───────────┐ ▼ │ │ ┌─────────LockSet────────┐ │ │ │ │ │ lock_1 │ │ │ │ lock_3 ────┼─────────────┼────▶ lvl_1-lock_3 ─────┼────────▶ guard-3 │ │ │ │ │ lock_8 ────────────┼─────────────┼────▶ lvl_1-lock_8 ─────┼────────▶ guard-8 │ │ │ │ └───────────────────────────┘ │ │ │ │ ┌─────────Level 2───────────┐ │ │ │ │ │ │ │ │ │ │ │ lock_5 ────┼─────────────┼────▶ lvl_2-lock_5 ─────┼────────▶ guard-5 │ │ │ │ │ lock_7 │ │ │ │ │ │ │ └───────────────────────────┘ └────────────────────────┘ ``` ### no_std と組み込み このクレートは核心で `#![no_std]` であり、alloc のみを必要とします。std 上では、デフォルトバックエンドとして `StdMutex` を得られ、`lock_scope` は便利なエントリポイントとなります。no_std 上では、独自のバックエンドを用意する必要があります — `lock_api::RawMutex` を実装する任意のものは機能フラグの後ろにブランクン impl 経由で動作します。 CAS を持つネイティブがないターゲット（例：Cortex-M0）も、`portable-atomic` および `critical-section` 機能をサポートしています。これは重要だと考えます；デッドロックフリー你最必要としている場所 — デバッグアタッチされた bare-metal ファームウェア — は、まさに現在のツールが最もあなたが助けられない場所だからです。 ### エスケープハッチ（Escape Hatch） 現実のコードは時には規則を破る必要があることがあります。Surelock は `Mutex::unchecked_lock()` をエスケープハッチ機能フラグの後ろで提供します。これらは機能ゲート付きなので、使用すれば Cargo.toml で表示され、grep でき、コードレビューで目立います。IMO これは代替案よりも優れています；開発者が静かに `parking_lot::Mutex` を Surelock の Mutex に沿って使うことでシステム全体を無効にすることです。 ### まとめ デッドロックは理論的に解決された問題であり、1971 年以来どのように防ぐかを知っています。挑戦は、その防止が実際の使用で十分使いやすくすることです。Surelock はそれにわたる私の試み：Rust の型システムを活用して正しいことは容易なものにし、誤ったことをコンパイラーエラーにします。 このクレートは Codeberg で公開され、crates.io にも公開されています。MIT/Apache-2.0 で双重ライセンスです。フィードバックを大歓迎し、特に組み込みまたは no_std ターゲットで作業されている方々から — そこではまだ実世界テストが少ないからです。 ¹ 例外が一つ：同じ Mutex を原子操作で一度以上に取得すること。このエッジケースに満足していませんが、自分自身と共に同じ Mutex を取ることはあまり一般的ではありません。 ² `thiserror` のみが唯一のランタイム依存関係であり、ランタイム上ゼロコストです。デフォルト std バックエンドは直接 `std::sync::Mutex` をラップします。 ³ 技術的には Rust の型システムではアフィン（dropped できるが複製できない）ですが、意図は線形です — 使用するのが期待され、API は設計されているのでそれを早期にドロップしてもスコープが終了するだけです。