HN 日本語サマリー

← 一覧へ戻る
プログラミング

コンパイルされないデータ競合

A data race that doesn't compile (corentin-core.github.io)

23 pointsby stmw6 コメント

要約

本記事では、Rustの型システムを活用して、並列Reduxパターンにおけるデータ競合をコンパイル時に防止する方法について解説しています。特に、レデューサーが異なる状態スライスにのみアクセスすることを型レベルで保証する「非共有性(disjointness)」の概念に焦点を当て、その実装における課題と解決策を探ります。しかし、Rustの型システムにおける型不平等を直接表現する機能の欠如という制約に直面し、著者は解決策を模索します。

全文翻訳

コンパイルできないデータ競合

並列Reduxのデータ競合を、一度の誤った開始と一度の思考の転換を経て、Rustの型システムに拒否させる方法。


私が数え切れないほどの夜を費やして追いかけてきた、ある種のバグがあります。負荷がかかったときにのみ発生し、デバッガーを接続すると消え去り、それを特定するのにエンジニア3人で週末がかかるようなものです。データ競合です。

Rustの借用チェッカーは、値レベルでのほとんどのデータ競合を防ぎます。しかし、すべてを防ぐわけではありません。そして、私がここで興味を持った問い、すなわち「2つのreducerが状態の同じ部分に書き込む可能性のある並列reducerパイプラインをコンパイラが構築拒否できるか?」という問いには、間違いなく対応していません。

その答えは「はい」です。この記事は、私のRedux風Rust学習ライブラリであるruxeで、私がどのようにしてそれを実現したかの物語です。

Reduxとは

Reduxは状態管理パターンです。フロントエンドJavaScriptで有名になりましたが、その形状はより一般的です。離散的なイベントを通じて状態が変化するあらゆるシステムが、このモデルに適合します。

    User([User code]) -->|dispatch event| Store
    Store -->|state + event| Reducer
    Reducer -->|new state| Store
    Store -->|read| User

ReduxをReduxたらしめているのは、3つのルールです。

1つ目:単一の真実の源。状態はストアによって所有され、それ以外のものではありません。

2つ目:状態は外部からは不変です。直接触ることはできません。何が起こったかを記述するイベント(JavaScriptの世界では「アクション」と呼ばれます)をディスパッチします。

3つ目:状態遷移は純粋なreducer、すなわち (state, event) → new state という関数を経由します。同じ入力、同じ出力、副作用はありません。

この3番目のルールが、Reduxが有名にデバッグ可能である理由です。イベントストリームを記録し、それを再生すれば、毎回同じ最終状態が得られます。タイムトラベルデバッグ。本番環境のトレースからのクラッシュ診断。再現可能なバグ。この特性を持たないステートフルUIのデバッグを試みたことがある人なら誰でも、なぜ人々がReduxを繰り返し再発明するのかを知っています。

なぜ私が気にしたのか

私の日々の仕事では、産業現場で稼働するエネルギー管理システムに取り組んでいます。そのスタックの1つの基盤は、PythonでReduxライクなパターンを使用しています。制御レイヤーでは、複数のコントローラーが並行して実行され、プラント状態の共有された一貫したビューが必要です。イベントが流れ込み、reducerパイプラインが新しい状態を計算し、コントローラーがそこから読み取ります。

その数字は、あなたが思うよりも速く積み重なります。典型的なプラントには数十個の機器があり、それぞれが独自の周期でポーリングされ、一部の周期は50ミリ秒にまで短くなります。各デバイスは、読み取りごとに数ダースのレジスタを公開できます。これは連続的で高ボリュームのイベントストリームであり、純粋なPython Reduxは追いつくのに苦労します。

私たちはそれを回避しました。読み取りをキャッシュし、基盤となるテレメトリよりも粗い頻度でリダクションをトリガーします。これは機能しますが、パターンは純粋さを失います。状態は最新のテレメトリと同期しなくなり、Reduxの魅力の一部を犠牲にすることになります。

プロファイリングは、実際にはどこに時間が費やされているかを示しました。reducerフェーズです。プラントには多くの独立したサブシステムがあります。ソーラー、バッテリー、メーター、グリッドコントローラーなどです。各サブシステムはグローバル状態のスライスを保持し、それぞれがそのスライスのみに触れる独自のreducerを持っています。

    Event[Event] --> R1[Solar reducer] --> S1[Solar slice]
    Event --> R2[Battery reducer] --> S2[Battery slice]
    Event --> R3[Meter reducer] --> S3[Meter slice]

これがすべてを開始した観察です。reducerは独立しています。ソーラーのreducerはバッテリーのスライスに触れることはありません。バッテリーのreducerはメーターのスライスに触れることはありません。各イベントは、それらすべてを通過する単一のパスです。

それらをシーケンシャルに実行すると、レイテンシがN倍になります。それらを並列に実行すると、max(latency_i)になります。

したがって、reducerを並列化します。外部からのイベントフローは同じで、決定論的な結果も同じですが、ディスパッチあたりの壁時計時間はN倍少なくなります。

ただし、1つの落とし穴があります。

並列処理と共有状態はデータ競合につながります。reducerが誤って別のスライスに書き込んだ場合、古典的な並行性バグが発生します。非決定論的な出力、本番環境でのヒーゼンバグ、死ぬまで覚えているデバッグセッションです。

ほとんどの言語では、ここで型システムは諦めます。C++はミューテックスとアトミックを提供し、幸運を祈ります。より高レベルな言語は同期プリミティブとメモリモデルを提供しますが、競合を回避する負担は開発者に残ります。コンパイラは何も強制せず、チームの規律がそれを担当します。

Rustの型システムは、このプロパティを直接エンコードできます。コンパイラ自体が、競合する可能性のあるコードのビルドを拒否できます。それが私がruxeで証明しようとしたことです。

メンタルモデル:スライスと離散性

以下のすべてを支える2つの概念があります。これ以上進む前に明確に定義する価値があります。

A スライスは状態のサブフィールドです。状態が counter、user、notifications フィールドを保持している場合、それらは3つのスライスです。

A スライスreducerは、そのスライスのみを参照するreducerです。他のスライスに触れることはできません。型システムがそれを禁止します。関数シグネチャは &Slice のみを示し、それ以外は何も示しません。

    subgraph State
        SA[counter]
        SB[user]
        SC[notifications]
    end
    R1[CounterReducer] -.touches.-> SA
    R2[UserReducer] -.touches.-> SB
    R3[NotificationsReducer] -.touches.-> SC

私たちが望むプロパティは離散性です。すなわち、私たちのセットアップ内の任意のスライスreducerのペアが異なるスライスを対象とすることです。2つのreducerが同じスライスに触れることは決してありません。

    subgraph Disjoint["✅ 離散 — 並列化しても安全"]
        D1[Reducer A] -.-> SA1[Slice A]
        D2[Reducer B] -.-> SB1[Slice B]
    end
    subgraph NotDisjoint["❌ 重複 — データ競合の可能性あり"]
        N1[Reducer A] -.-> SX[Slice X]
        N2[Reducer B] -.-> SX
    end

離散性は安全な並列実行に必要かつ十分です。それが成り立つなら、並列化は健全です。成り立たないなら、並列化は競合します。

エンジニアリング上の問題はこうなります。並列reducerのルートが離散性を違反した場合、コンパイラにビルドを拒否させることはできるか?

最初のアイデア:AllDistinct

私が開始したとき、そしてそれがなぜ機能すると思ったかの考えは次のとおりです。

私はC++からRustに来ました。C++では、この種のチェックはテンプレートメタプログラミングの得意技です。std::is_same_v<H, T> はコンパイル時に型の一致を提供します。!std::is_same_v<H, T> は不一致を提供します。それを static_assert(またはC++20ではconcept)でラップすると、コンパイラが残りを処理します。このパターンは、十分に豊富な型システムに自然に移ります。

Rustは表面上は似ていました。再帰的なトレイト実装はどこにでもあります。Vec<T> は T が Clone なら Clone です。Option<T> は T が Send なら Send です。「この型はその部分がプロパティPを持つならプロパティPを持つ」というパターンは、言語に組み込まれています。

したがって、reducer型のリスト、例えばタプル (R1, R2, R3) を書いた場合、Ri::Slice 型のどれも同じでない場合に成り立つ AllDistinct というトレイトを定義できるはずです。タプルを再帰的にウォークします。各ステップで、ヘッドのスライスがテールのすべてのスライスと異なることを確認します。再帰します。

私が考えていた形状は、疑似Rust(実際のタプルはこのように再帰的にウォークできない。私はウォーク部分を無視していた。これは最終的に否定壁によって無意味になる)です。

trait AllDistinct {}

impl AllDistinct for () {}

impl<H, Tail>
    AllDistinct for (H, Tail)
where
    Tail: AllDistinct,
    H: NotIn<Tail>, // そして H はテールに含まれない
{}

妥当に見えます。再帰は空のタプルで底を打ちます。各ステップは、残りが離散的であり、ヘッドが残りに含まれないことを要求します。標準的な構造的再帰です。

私はそれを構築しました。NotIn<H> に到達しました。フリーズしました。

NotIn<H> は、「テールのすべての要素Xについて、H ≠ X」と言う必要があります。Rustの構文では、それは次のようになります。

trait NotIn<T> {}

impl<H, Tail, T>
    NotIn<T> for (H, Tail)
where
    Tail: NotIn<T>,
    H != T, // ← これは存在しない
{}

コンパイラ:

error: expected one of `!`, `(`, `+`, `::`, `:`, `<`, `==`, or `=`, found `!=`

[画像]

安定版Rustには、境界での型不一致の構文がありません。H != T もありません。「このトレイトは、他のトレイトが実装されていない場合に実装される」と書く方法もありません。不安定な機能である negative_impls は長年存在していますが、coherence concerns の背後に留まっています。期待しないでください。

これは単なる演算子の欠如ではありません。トレイトシステムは、実装を単調に推論します。コードベースでより多くの実装を追加しても、コンパイルできるコードが増えるだけで、既存のコードが無効になることは決してありません。否定的な推論(「このトレイトは実装されていない」)は、そのプロパティを壊す可能性があります。誰かが新しい肯定的な実装を追加すると、それに基づいて既存のコードが無効になる可能性があります。Rustは、推論を許可しないことによって、この種のすべての問題を回避します。

ここでRustはC++と大きく異なります。C++では、!std::is_same_v<H, T> は計算できる値であり、static_assert で使用できます。Rustでの同等のものには表面構文がなく、その理由は不注意ではなく、設計上の選択です。

安定版Rustでの AllDistinct は、少なくとも私がスケッチした形状では、表現できません。

ピボット

私はしばらくこの問題に取り組みました。壁は現実でした。しかし、壁は間違ったドアであることもあります。

私は否定(重複がないこと)を証明しようとしていました。Rustは肯定を話します。それを逆の形で同じプロパティを言い換えたらどうなるでしょうか?

定式化形式安定版Rustでの実現性
「2つのreducerが同じスライスを対象としない」否定不可能(否定が必要)
「各状態スライスには正確に1つの対応するreducerがある」肯定(全単射)実現可能(実装の存在)

これらは論理的に同等です。スライスとreducerの間の全単射は、各スライスに正確に1つのマッチがあること、そして2つのreducerがスライスを共有しないことを意味します。2番目の条件は最初の条件から導き出されます。したがって、「重複があるか?」と問う代わりに、「完全なマッチングがあるか?」と問うべきです。最初の質問は不可能な否定を必要とします。2番目の質問は、Rustが得意とする特定のトレイト実装の存在を求めるだけです。

具体的には、ユーザーが明示的に宣言するスライスのリストをウォークし、各スライス型について、reducerのHListからそのSlice関連型がそれに一致するreducerを見つけます。3つの結果があります。

検索結果アクションコンパイル時結果
ちょうど1つのreducerが一致使用し、続行OK
2つ以上一致—曖昧な実装エラー
ゼロ一致—トレイト境界が満たされない

エラーはRustのトレイトcoherenceルールから来ます。明示的なチェックを記述する必要はありません。トレイトリゾルバが実行するすべての検索でそれらを強制します。

HList:適切なツール

コンパイル時にスライスリストをウォークするには、コンパイラが再帰的にウォークできる構造が必要です。タプルは適格ではありません。各アリティは異なる型であり、 (A,)、 (A, B)、 (A, B, C) などに対して個別の実装が必要になります。私が欲しいのは、その再帰構造が型の一部であるリストであり、トレイト解決がそれ自体で下降できるようにすることです。

その構造はRustエコシステムに存在します。それはHListと呼ばれ、既知のパターンです。

異種リスト(heterogeneous list)は、その名前が示すとおりです。各セルが異なる型の値を持つことができる連結リストです。形状は次のとおりです。

struct HCons<H, T> { head: H, tail: T }
struct HNil;

目を細めると、これはLispのconsセルですが、型付けされ、型レベルで表現されています。

3要素のHListは次のようになります。

HCons<i32, HCons<String, HCons<f64, HNil>>>
//    ^      ^             ^             ^
//    head   ネストされたcons   ネストされたcons   終端子

マクロを使えば、これをより楽に書けます。

HList!(i32, String, f64)
// 次のように展開されます:
// HCons<i32, HCons<String, HCons<f64, HNil>>>

視覚的にはネストされた人形です。

    L1[HCons] --> H1[i32] & T1[HCons]
    T1 --> H2[String] & T2[HCons]
    T2 --> H3[f64] & T3[HNil]

この構造はタプルがなれないものです。再帰的なトレイト実装によってコンパイラがウォークできます。なぜなら?すべてのHListは HNil(終端子、ベースケースのマッチ)または HCons<H, T>(T がそれ自体HListである)のいずれかです(再帰ステップのマッチ)。

2つの実装を書き、ケースごとに1つずつ書きます。これにより、任意のアリティを処理できます。タプルは、サポートしたいアリティごとに個別の実装が必要になり、通常はマクロによって12に制限されます。

クレートfrunkは、標準的なRust HListライブラリです。私は構造とパターンを借用しました。ruxe内に最小限の実装を再実装して、最終的には内部詳細であるものに対して推移的な依存関係を回避しました。以下で使用する語彙(HCons、HNil、Sculptor、位置の証人)はすべてそこから来ています。

これでコンパイラがウォークできるリストができました。適用する時間です。

ブレークスルー:スライスreducerのためのSculptor

frunkにはSculptorと呼ばれるパターンがあります。HListを取り、その型によって特定の要素を抽出し、マッチした要素と残りを返します。

let list = hlist![1i32, "hello", 3.14f64];
let (matched, leftover) = list.sculpt::<HList!(f64, i32), _>();
// matched  : HList!(3.14f64, 1i32)
// leftover : HList!("hello")

コンパイラはソースHListをウォークし、マッチを見つけるまで再帰して各要求された型を抜き取り、マッチしたタプルを構築し、残りを返します。

リゾルバが無料でキャッチする2つの失敗モードがあります。ソースに存在しない型を要求した場合:コンパイルエラー。型が複数回出現した場合:コンパイルエラー(曖昧)。

これを私の問題に適用します。ユーザーが明示的に宣言した状態のスライスリスト(HList!(CounterSlice, UserSlice, NotificationSlice) のようなもの)と、reducerのHList(ユーザーが渡したタプルから派生)があります。

スライスリストをウォークします。各スライスについて、Slice 関連型がそのスライスに一致する reducer の HList から reducer を検索します。Sculptor風の検索ですが、具体的な型ではなく関連型でマッチします。

    subgraph Slices
        S1[CounterSlice]
        S2[UserSlice]
        S3[NotificationSlice]
    end
    subgraph Reducers
        R1[CounterReducer]
        R2[UserReducer]
        R3[NotificationReducer]
    end
    S1 -.match.-> R1
    S2 -.match.-> R2
    S3 -.match.-> R3

私が望む失敗モードは、リゾルバから自然に発生します。

    subgraph Happy["✅ 正常系 — 一意のマッチ"]
        direction LR
        H1[Slice A] --> H2[位置0で見つかったA用のReducer]
    end
    subgraph Duplicate["❌ 同じスライスのreducerが2つある"]
        direction LR
        D1[Slice A] --> D2{A用のReducer?}
        D2 --> D3[位置0でマッチ]
        D2 --> D4[位置2でマッチ]
        D3 & D4 --> D5[曖昧:コンパイルエラー]
    end
    subgraph Missing["❌ reducerのない状態スライス"]
        direction LR
        M1[Slice B] --> M2{B用のReducer?}
        M2 --> M3[どこにもマッチしない]
        M3 --> M4[実装なし:コンパイルエラー]
    end

    Happy ~~~ Duplicate
    Duplicate ~~~ Missing

「重複があるか?」や「すべてカバーされているか?」といったチェックを一度も記述しませんでした。リゾルバがそれを行いました。なぜなら、それは他のすべての検索に対してそれを行うからです。私は単に、それが答えられるように質問をフレーズ化する必要がありました。

位置の証人:型システムにおけるペアノ数

これを実装する際に重要な詳細があります。ターゲットスライスTのreducerを「検索する」再帰トレイトには2つの実装があります。

// ベースケース:ヘッドがターゲットに一致する
impl FindReducerBySlice<TargetSlice> for HCons<HeadReducer, Tail>
where HeadReducer: SliceReducer<Slice = TargetSlice> { ... }

// 再帰ケース:ヘッドが一致しない、テールを検索する
impl FindReducerBySlice<TargetSlice> for HCons<HeadReducer, Tail>
where Tail: FindReducerBySlice<TargetSlice> { ... }

曖昧化子がないと、これらの実装は重複します。どちらもシグネチャ impl ... for HCons<H, T> を持ちます。Rustのcoherenceルールは「いいえ」と言います。

frunkの解決策:トレイトに位置の証人を追加します。

struct Here;
struct There<I> { _marker: PhantomData<I> }

trait FindReducerBySlice<TargetSlice, Index> { ... }

impl ... for HCons<...> { ... }     // Index = Here       (このレベルでマッチ)
impl ... for HCons<...> { ... }     // Index = There<I>   (内部インデックスIで再帰)

Here と There<I> は型レベルのペアノ数です。

ペアノ数: ゼロと後続関数という2つの要素のみから自然数を定義する方法です。数値0は単に「ゼロ」です。1は「ゼロの後続」です。2は「ゼロの後続の後続」です。3はさらに1つ深いsuccessorであり、以下同様です。すべての正の整数線は、ゼロの上に後続を積み重ねることによって構築されます。数学(1889年にペアノが自然数を形式化した方法)や、実行時値に頼ることなくカウントをエンコードする必要がある型レベルプログラミングで役立ちます。

この場合:Here はゼロの役割を果たします。There<I> は後続関数の役割を果たし、内部に小さい数値をラップします。There<Here> は1、There<There<Here>> は2、そしてそれ以降です。これらは、コンパイラがマッチを見つけるためにたどったパス、すなわちヘッドがターゲットスライスに一致する前に何回のtailホップがあったかをエンコードします。

    A[Here = 0] -.successor.-> B["There<Here> = 1"]
    B -.successor.-> C["There<There<Here>> = 2"]
    C -.successor.-> D[...]

ユーザーはこれらを決して書きません。コンパイラはトレイト解決中にそれらを推論します。それらは、そうでなければ重複する実装を曖昧化するために存在します。

実世界の摩擦

この部分は機械的な作業が多いため、省略します。自分でこのようなものを作成する場合、次のものに遭遇することを期待してください。

E0207: 型パラメータXは、implトレイト、self型、または述語によって制約されていません。Rustは、implのすべてのジェネリックパラメータが一意に決定されることを要求します。impl<I> SomeTrait for SomeStruct where SomeStruct: SomeOtherTrait<I> と書き、I が他のどこにも現れない場合、Rustは拒否します。修正は通常、問題のあるパラメータを関連型に変換するか、PhantomData を介して Self 型にドラッグすることです。

PhantomData: 型パラメータの値を持たずに「使用」できるようにするゼロサイズのマーカーです。難解に聞こえます。実際にはRustの型システムの負荷を支えるツールの1つです。ほとんどのジェネリック構造体は、ファントム型を保持するためにこれを使用します。

これらはどちらも概念的なものではありません。それらは配管作業です。しかし、この道を行くなら、それぞれに半日を予算してください。コンパイラがますます巧妙な試みを拒否するのを見るのは謙虚な経験です。

[画像]

ペイオフ

ユーザー向けのAPIは次のようになります。

struct AppState {
    counter: CounterSlice,
    user: UserSlice,
}

impl HasSlice<CounterSlice> for AppState { /* ... */ }
impl HasSlice<UserSlice>    for AppState { /* ... */ }

impl StateSlices for AppState {
    type Slices = HList!(CounterSlice, UserSlice);
}

let root = ParallelRootReducer::new((counter_reducer, user_reducer));

これはコンパイルされ、Rayonを介して並列に実行され、StateSlices で宣言されたすべてのスライスに対して証明可能な競合フリーです。

ここでタイプミスをします。counter_reducer を2回渡します。

let root = ParallelRootReducer::new((counter_reducer, counter_reducer));
//                                                    ^^^^^^^^^^^^^^^^
//                                                    最初のものと同じスライス

コンパイラ:

error[E0283]: type annotations needed
  |
  | let _ = root.reduce(&state, &event);
  |              ^^^^^^ cannot infer type of the type parameter `I`
  |
note: multiple `impl`s satisfying `HCons<CounterReducer, ...>: FindReducerBySlice<CounterSlice, _>` found

reducerを忘れます。

let root = ParallelRootReducer::new((counter_reducer,));   // user reducer が欠落

コンパイラ:

error[E0277]: the trait bound `HCons<CounterReducer, HNil>: FindReducerBySlice<UserSlice, _>` is not satisfied

どちらの場合も、バイナリが生成される前にビルドが失敗します。離散性の保証は実行時に強制される必要はありません。コンパイラが最初に競合する可能性のある並列reducerの組み立てを拒否するためです。実際には必要ありません。わずかなニュアンスとして指摘する価値があります。エラーはコンストラクタのサイトではなく、.reduce() の呼び出しサイトで表面化します。コンストラクタ自体は制約がないため、任意のタプルを喜んで受け入れます。スライスからreducerへの全単射は、.reduce() がそのトレイト境界を解決するときにのみチェックされます。これは、Rustが Indices と Event の型を決定する必要がある最初のポイントです。実際には、これはビルドされてもディスパッチされない ParallelRootReducer はサイレントにコンパイルされることを意味します。実際に使用すると、コンパイラが介入します。

実際の並列速度向上を示す実行可能な並列比較については、ruxeのEMS例で同じシナリオをシーケンシャルおよび並列で実行しています。3つのスライスreducerがそれぞれ約50ミリ秒の作業を行う場合、約3倍高速です。

まとめ

Sculptorパターンは転用可能です。異種コレクション内で一意のコンパイル時ルックアップをどこでも行いたい場合、この形状が適用されます。曖昧さまたは欠如が安全チェックになる肯定的なルックアップです。ECSクエリシステムは関連するトリックを使用します。型安全な依存性注入コンテナも同様です。実行時に「重複がないことを確認する」という手段に達したら、代わりに「コンパイル時にちょうど1つのマッチを確認する」とフレーズ化することを検討してください。

安定版Rustでの否定は本当に困難です。もし H != T を使いたいと思ったら、立ち止まって言い換えを試してください。それはほとんどの場合可能です。言い換えは、元のものよりも明確になることが多いです。

Rustのトレイトシステムは、見た目よりも表現力豊かです。他の言語でunsafe、Box<dyn>、または実行時チェックに頼るようなことが、型システムにエンコードできることがよくあります。コストはメンタルジグソーパズルです。ペイオフは、存在できないバグです。

frunkはこれらのパターンをエコシステムのために正規化しました。型レベルのRustをさらに深く掘り下げるなら、frunkがリファレンスです。ruxe内に最小限のサブセットを再実装して依存関係のフットプリントを小さく保ちましたが、デザイン語彙はすべてそこから来ています。

AllDistinctでの誤った開始を含め、旅全体で数日間かかりました。最終的なコードは約200行の再帰的なトレイト実装です。洞察ごとのリファクタリングの量は多かったです。結果は密で、読むには少し威圧的です。

しかし、コンパイラは競合する可能性のあるコードの組み立てを拒否するようになりました。これはまさに私がそれをさせるために設定したことです。


ソースコード:GitHub上のruxe。この機能が追加されたプルリクエスト:#26。

著者の注記:AnthropicのClaudeでドラフトされ、複数のパスを経て書き直されました。決定と旅自体は私のものです。