Day 031 — Arc<Mutex<T>>による共有状態管理（デッドロックを起こさないロック順序設計）

📚 背景知識（読んでから問題へ）

昨日（Day 030）は「なぜRc<RefCell<T>>を複数スレッドで共有できないのか」をSend/Syncの観点から確認し、Arc<Mutex<T>>への置き換えで解決しました。今日はそのArc<Mutex<T>>を本格的に扱います。

Mutex<T>（相互排他ロック、mutual exclusion）は「ある時点で1つのスレッドだけがTへの&mutアクセスを持てる」ことを保証する仕組みです。.lock()を呼ぶと、他のスレッドがロックを保持していなければ即座にMutexGuard<T>を返し、保持していればそのスレッドが解放するまでブロックします。MutexGuard<T>がスコープを抜けてドロップされると自動的にロックが解放される、C++のstd::lock_guardと同じRAIIパターンです。

ここで実務上とても重要な論点が2つあります。

📝 問題

以下の2つの機能を持つ、スレッドセーフな「スコアボード」システムを実装してください。

要件1: Scoreboard（単一Mutexで守る集計）

• Arc<Mutex<HashMap<String, i64>>>を内部に持つScoreboard構造体を実装する
• increment(&self, player: &str, delta: i64)メソッド: 指定プレイヤーのスコアにdeltaを加算する（存在しないプレイヤーは0から開始）
• get(&self, player: &str) -> i64メソッド: 現在のスコアを取得する
• 8つのスレッドを立ち上げ、各スレッドが"alice"のスコアに125回+1、"bob"のスコアに125回+2を行い、全スレッド終了後にalice == 1000、bob == 2000になることを確認する

要件2: Ledger（プレイヤーごとに独立したMutexを持つ口座台帳）

• HashMap<String, Arc<Mutex<i64>>>を内部に持つLedger構造体を実装する
• transfer(&self, from: &str, to: &str, amount: i64)メソッド: fromの残高をamount減らし、toの残高をamount増やす。2つのMutexを同時にロックする必要があるが、デッドロックが起きないように実装すること
• 8つのスレッドを立ち上げ、半数はtransfer("alice", "bob", 3)を200回、残り半数はtransfer("bob", "alice", 3)を200回、同時に実行する。全スレッド終了後、両者の残高が変化していない（差し引きゼロ）ことを確認する

🔍 ヒント（段階的開示）

📋 コピーfn transfer(&self, from: &str, to: &str, amount: i64) {
    let from_lock = &self.accounts[from];
    let to_lock = &self.accounts[to];

    if from < to {
        let mut first = from_lock.lock().unwrap();
        let mut second = to_lock.lock().unwrap();
        /* ??? first から amount を引き、second に amount を足す */
    } else {
        let mut first = to_lock.lock().unwrap();
        let mut second = from_lock.lock().unwrap();
        /* ??? どちらが from でどちらが to かに注意して加減算する */
    }
}

✅ 模範解答

📋 コピー// cargo new day031_arc_mutex の後、src/main.rs をこの内容で置き換えて
// `cargo run` で検証できます（外部クレート依存なし、標準ライブラリのみ）。

use std::collections::HashMap;
use std::sync::{Arc, Mutex};
use std::thread;

// ── 要件1: Scoreboard（単一Mutexで守る集計） ──

/// 複数スレッドから安全に更新できるスコアボード。
/// 全プレイヤーのスコアを単一の Mutex<HashMap<...>> の下にまとめて置くことで、
/// 単一プレイヤーへの読み書きに対しては最もシンプルで安全な設計になる。
/// （複数プレイヤーをまたぐ操作が必要になると Ledger のような設計が要る）
struct Scoreboard {
    inner: Arc<Mutex<HashMap<String, i64>>>,
}

impl Scoreboard {
    fn new() -> Self {
        Scoreboard { inner: Arc::new(Mutex::new(HashMap::new())) }
    }

    fn clone_handle(&self) -> Self {
        Scoreboard { inner: Arc::clone(&self.inner) }
    }

    fn increment(&self, player: &str, delta: i64) {
        // ロックを保持するのは「HashMapへの1回のエントリ更新」の間だけ。
        // guard はこのメソッドの終わりでスコープを抜け、即座にドロップ = ロック解放される。
        let mut guard = self.inner.lock().unwrap();
        *guard.entry(player.to_string()).or_insert(0) += delta;
    }

    fn get(&self, player: &str) -> i64 {
        let guard = self.inner.lock().unwrap();
        *guard.get(player).unwrap_or(&0)
    }
}

fn demo_scoreboard() {
    let board = Scoreboard::new();
    let mut handles = Vec::new();

    for _ in 0..8 {
        let board = board.clone_handle();
        let handle = thread::spawn(move || {
            for _ in 0..125 {
                board.increment("alice", 1);
                board.increment("bob", 2);
            }
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    assert_eq!(board.get("alice"), 8 * 125 * 1); // = 1000
    assert_eq!(board.get("bob"), 8 * 125 * 2);    // = 2000
    println!(
        "demo_scoreboard: alice={}, bob={}",
        board.get("alice"),
        board.get("bob")
    );
}

// ── 要件2: Ledger（プレイヤーごとに独立したMutexを持つ口座台帳） ──

/// プレイヤーごとに独立した Arc<Mutex<i64>> を持つ口座台帳。
/// Scoreboard と違い、「AからBへamountを移す」という操作は
/// 2つのロックを同時に(かつ一貫した順序で)保持する必要がある。
struct Ledger {
    accounts: HashMap<String, Arc<Mutex<i64>>>,
}

impl Ledger {
    fn new(players: &[&str], initial: i64) -> Self {
        let accounts = players
            .iter()
            .map(|p| (p.to_string(), Arc::new(Mutex::new(initial))))
            .collect();
        Ledger { accounts }
    }

    fn balance(&self, player: &str) -> i64 {
        *self.accounts[player].lock().unwrap()
    }

    /// from から to へ amount を移す。
    /// デッドロックを避けるため、引数の順序に関わらず
    /// 「キー名の辞書式順序が小さい方を先にロックする」というグローバルな順序を守る。
    fn transfer(&self, from: &str, to: &str, amount: i64) {
        let from_lock = &self.accounts[from];
        let to_lock = &self.accounts[to];

        // 常に同じ順序でロックを取ることで、2スレッドが逆方向に
        // transfer("alice","bob",..) / transfer("bob","alice",..) を同時実行しても
        // お互いが相手の持つロックを待ち続ける状況(デッドロック)が起こらない。
        if from < to {
            let mut from_guard = from_lock.lock().unwrap();
            let mut to_guard = to_lock.lock().unwrap();
            *from_guard -= amount;
            *to_guard += amount;
        } else {
            let mut to_guard = to_lock.lock().unwrap();
            let mut from_guard = from_lock.lock().unwrap();
            *from_guard -= amount;
            *to_guard += amount;
        }
    }
}

fn demo_transfer() {
    let ledger = Arc::new(Ledger::new(&["alice", "bob"], 1000));
    let mut handles = Vec::new();

    // 半数のスレッドは alice -> bob、残り半数は bob -> alice へ、
    // 同時に何度もtransferを行う。ロック順序が一貫しているため、
    // 何回実行してもハングせずに完了する。
    for i in 0..8 {
        let ledger = Arc::clone(&ledger);
        let handle = thread::spawn(move || {
            for _ in 0..200 {
                if i % 2 == 0 {
                    ledger.transfer("alice", "bob", 3);
                } else {
                    ledger.transfer("bob", "alice", 3);
                }
            }
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    // 4スレッドが alice->bob を200回、4スレッドが bob->alice を200回行うので
    // 差し引きゼロになり、両者の残高は初期値(1000)のまま変わらない。
    assert_eq!(ledger.balance("alice"), 1000);
    assert_eq!(ledger.balance("bob"), 1000);
    println!(
        "demo_transfer: alice={}, bob={}",
        ledger.balance("alice"),
        ledger.balance("bob")
    );
}

fn main() {
    demo_scoreboard();
    demo_transfer();
    println!("OK");
}

$ cargo run
demo_scoreboard: alice=1000, bob=2000
demo_transfer: alice=1000, bob=1000
OK

🪜 Step-by-Step 解説

💡 設計思想・なぜこう書くのか

Rustの標準ライブラリには、C++のstd::lock(m1, m2)（複数のミューテックスをデッドロックしないアルゴリズムでまとめてロックする関数）に相当する仕組みは用意されていません。つまりMutexを複数使う設計をした時点で、デッドロック回避の責任はプログラマ（あるいはコードレビュー・設計規約）に委ねられます。これは、所有権や借用のように「コンパイラが機械的に保証してくれる安全性」の範囲を超えた領域です。

だからこそ実務では、「複数のロックを同時に取る箇所を極力減らす」「どうしても必要な場合はロック順序を明文化する（今回のように&strの辞書式順序、あるいはID・生成順などの一貫した基準を決める）」「可能ならLedgerのような細粒度ロックではなく、Scoreboardのように1つのMutexの中に複数プレイヤーをまとめる設計に倒す」といった設計判断そのものが重要になります。細粒度ロック（プレイヤーごとにMutex）は並行性（スループット）を上げられる代わりにデッドロックのリスクを持ち込み、粗粒度ロック（全体を1つのMutex）は安全に書きやすい代わりに並行性を犠牲にする——これはRustに限らずロックベースの並行プログラミング全般に共通するトレードオフです。

🛑 コンパイルエラーが出た場合

今回は実装問題ですが、MutexとHashMapを組み合わせるときに非常によく踏む借用チェッカーのエラーがあります。次のような「間違った実装」を試すと発生します。

📋 コピー// このコードはコンパイルエラーになる
fn buggy_increment(inner: &Mutex<HashMap<String, i64>>, player: &str, delta: i64) {
    let mut guard = inner.lock().unwrap();
    if let Some(score) = guard.get(player) {
        // score は guard から借用された &i64 のまま、このifブロックの中で生き続けている
        guard.insert(player.to_string(), score + delta); // ここでエラー
    } else {
        guard.insert(player.to_string(), delta);
    }
}

読み方: guard.get(player)が返す&i64（score）は、guard（HashMap本体）を不変借用したままです。その借用が生きている間にguard.insert(...)で可変借用しようとしているため、借用規則違反になります。修正方針は、模範解答のように*guard.entry(player.to_string()).or_insert(0) += delta;という1行のAPI（entry API）を使うことです。entryは「参照を取り出してから書き戻す」という2段階の操作を1回の可変借用に畳み込んでくれるため、このエラーそのものが起こりません。HashMapをMutex越しに更新するときは、素朴なget→insertではなくentry APIを使う習慣をつけると、この種のエラーに遭遇しにくくなります。

🌐 他言語との比較

🏆 実務での使いどころ

• Webサーバーのアプリケーション状態（例: axum/actixのAppState）でインメモリのカウンタ・キャッシュ・接続プールの参照を複数リクエストハンドラ間で共有する際、Arc<Mutex<T>>（読み取りが多いならArc<RwLock<T>>）が定番の組み合わせになる
• 複数の独立したリソース（口座・在庫・セッションなど）を個別にロックする設計は並行性を高めるが、今回のLedgerのように「2つ以上のリソースをまたぐ操作」が必要になった瞬間、ロック順序の設計・レビューが必須になる。実務では「エンティティIDの昇順で常にロックする」といったチーム内規約を明文化することが多い
• テストで並行処理のバグ（デッドロック・データ競合）を検出するには、loom（並行処理の網羅的モデル検査クレート）や、ロック取得にtry_lockとタイムアウトを組み合わせたデバッグ用ヘルパーが実務でよく使われる

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: Ledger::transferを、from == to（自分自身への送金）が呼ばれた場合にどうなるか考えてみましょう。今の実装だと同じMutexを2回ロックしようとして自己デッドロックします。from == toのケースを先頭でガードする（早期リターンする）修正を加えてみてください
• 次回予告: 次回はチャンネル（mpsc）を扱います。今日学んだ「共有状態にロックをかけてアクセスする」アプローチとは対照的な、「状態を共有せず、値の所有権をメッセージとしてスレッド間で受け渡す」という設計思想（"Don't communicate by sharing memory; share memory by communicating"）を体験します

🎯 自己評価

自分の回答

気づき・メモ