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

「自分自身の並列Reduxデータ競合をRustの型システムに拒否させる方法、一度の誤った開始と一度の思考の転換を伴って。」 私が追いかけた夜の数を数えきれないほどのバグの一種があります。それは負荷がかかったときにしか発生せず、デバッガをアタッチすると消え去り、3人のエンジニアが週末をかけてようやく追い詰めるようなものです。データ競合。Rustの借用チェッカーは、そのほとんどを値レベルで防ぎます。しかし、すべてではありませんし、ここで私が興味を持った問題も明確には防ぎません。つまり、2つのレデューサーが同じ状態の一部に書き込む可能性のある並列レデューサーパイプラインの構築をコンパイラが拒否できるか、という問題です。 結果として、可能です。この投稿は、私のRedux風味のRust学習ライブラリであるruxeで、私がどのようにそこに到達したかの物語です。 Reduxとは？# Reduxは状態管理パターンです。フロントエンドのJavaScriptで有名になりましたが、その形はより一般的です。状態が離散的なイベントを介して変化するあらゆるシステムがこのモデルに適合します。 flowchart LR User([User code]) -->|dispatch event| Store Store -->|state + event| Reducer Reducer -->|new state| Store Store -->|read| User ReduxをReduxたらしめる3つのルールがあります。1つ目：単一の信頼できる情報源。状態はストアによって所有され、他にはありません。2つ目：状態は外部から不変です。直接操作することはありません。何が起こったかを記述するイベント（JSの世界では「アクション」と呼びます）をディスパッチします。3つ目：状態遷移は純粋なレデューサー、つまり関数 (state, event) → new state を介して行われます。同じ入力には同じ出力があり、副作用はありません。 この3つ目のルールこそが、Reduxがデバッグしやすいと評判である理由です。イベントストリームを記録し、それを再生すれば、毎回同じ最終状態が得られます。タイムトラベルデバッグ。本番環境のトレースからのクラッシュ診断。再現可能なバグ。この特性を持たないステートフルなUIをデバッグしようとしたことのある人なら誰でも、なぜ人々がReduxを再発明し続けるのか理解できるでしょう。 なぜ私が関心を持ったのか# 私の本業では、産業現場で稼働するエネルギー管理システムに携わっています。スタックの一つの要素は、PythonでReduxのようなパターンを使用しています。それは制御レイヤーで、複数のコントローラーが並行して実行され、プラントの状態の一貫した共有ビューを必要とします。イベントが流れ込み、レデューサーパイプラインが新しい状態を計算し、コントローラーはそこから読み取ります。 数字は思ったよりも早く積み上がります。典型的なサイトでは数十の機器があり、それぞれが独自の周期でポーリングされ、一部の周期は50msにまで短縮されます。各デバイスは読み取りごとに数十のレジスタを公開できます。これは継続的で大量のイベントストリームであり、純粋なPython Reduxでは追いつくのが困難です。 私たちはそれに対応しました。読み取りをキャッシュし、基礎となるテレメトリーよりも粗い頻度でリダクションをトリガーします。これは機能しますが、パターンはより純粋でなくなります。状態は最新のテレメトリーに追いつかず、Reduxを魅力的にしていた部分を一部手放してしまいます。 プロファイリングによって、実際に時間が費やされていた場所が明らかになりました。レデューサーフェーズです。プラントには多くの独立したサブシステムがあります。太陽光発電、バッテリー、メーター、グリッドコントローラーなどです。各サブシステムはグローバル状態の一部を保持し、それぞれが自身のスライスのみを触る独自のレデューサーを持っています。 flowchart LR Event[Event] --> R1[Solar reducer] --> S1[Solar slice] Event --> R2[Battery reducer] --> S2[Battery slice] Event --> R3[Meter reducer] --> S3[Meter slice] すべてを始めた観察は次のとおりです。レデューサーは独立している。太陽光発電のレデューサーはバッテリーのスライスを触らない。バッテリーのレデューサーはメーターのスライスを触らない。各イベントは、これらすべてを一度通過します。順次実行すると、レイテンシがN倍になります。並列実行すると、max(latency_i)になります。 したがって、レデューサーを並列化します。外部からのイベントフローは同じで、決定論的な結果も同じですが、ディスパッチあたりの実時間がN分の1になります。 一つ注意点があります。並列と共有状態はデータ競合を引き起こします。もしレデューサーが誤って他のスライスに書き込んだ場合、古典的な並行性バグが発生します。非決定論的な出力、本番環境でのハイゼンバグ、死ぬまで覚えているようなデバッグセッションです。 ほとんどの言語では、そこで型システムが諦めます。C++はミューテックスとアトミックを提供し、幸運を祈ります。より高レベルの言語は同期プリミティブとメモリモデルを提供しますが、競合を避ける負担は開発者にかかります。コンパイラは何も強制せず、チームの規律がそれを実現します。 Rustの型システムは、この特性を直接エンコードできます。コンパイラ自体が競合を引き起こすコードの構築を拒否できるのです。それが私がruxeで証明しようとしたことです。 メンタルモデル：スライスと非共有性# これから続くすべてを支える2つの概念があります。先に明確に定義しておく価値があります。 スライスとは、状態のサブフィールドです。状態がカウンター、ユーザー、通知フィールドを保持している場合、それらは3つのスライスです。 スライスレデューサーとは、そのスライスのみを見るレデューサーです。他のスライスを触ることはできません。型システムがそれを禁止します。関数シグネチャは &Slice のみを表示し、他には何も表示しません。 flowchart LR subgraph State SA[counter] SB[user] SC[notifications] end R1[CounterReducer] -.touches.-> SA R2[UserReducer] -.touches.-> SB R3[NotificationsReducer] -.touches.-> SC 私たちが望む特性は非共有性 (disjointness) です。設定内の任意の2つのスライスレデューサーについて、それらが異なるスライスをターゲットにすることです。どの2つのレデューサーも同じスライスを触らない。 flowchart LR subgraph Disjoint["✅ Disjoint — safe to parallelize"] D1[Reducer A] -.-> SA1[Slice A] D2[Reducer B] -.-> SB1[Slice B] end subgraph NotDisjoint["❌ Overlap — data race possible"] N1[Reducer A] -.-> SX[Slice X] N2[Reducer B] -.-> SX end 非共有性は安全な並列実行に必要かつ十分です。それが成り立てば、並列は健全です。そうでなければ、並列競合が発生します。 エンジニアリング上の疑問は次のようになります。非共有性に違反する並列ルートレデューサーの構築をコンパイラに拒否させることができるか？ 最初のアイデア：AllDistinct# 私が始めたときに考えていたことと、なぜそれがうまくいくと思ったのかを説明します。私はC++からRustに来ました。C++では、この種のチェックはテンプレートメタプログラミングの基本です。std::is_same_v<H, T> はコンパイル時に型の等価性を提供します。!std::is_same_v<H, T> は不等式を提供します。これをstatic_assert（またはC++20ではコンセプト）でラップすれば、コンパイラが残りの処理を行います。 このパターンは、十分に豊かな型システムを持つあらゆる言語に自然に転用できます。Rustも表面的には似ているように見えました。再帰的なトレイト実装は至る所にあります。Vec<T> は T が Clone であれば Clone です。Option<T> は T が Send であれば Send です。「この型は、その部分がプロパティPを持つ場合、プロパティPを持つ」というパターンは言語に組み込まれています。 したがって、レデューサー型のリスト、例えばタプル (R1, R2, R3) を書いた場合、どの2つの Ri::Slice 型も同じではない場合に成り立つ AllDistinct トレイトを定義できるはずです。タプルを再帰的に走査します。各ステップで、ヘッドのスライスがテールのどのスライスとも異なることを確認します。再帰します。 私が考えていた形は、擬似Rustで次のようなものです（実際のタプルはこのように再帰的に走査できません。走査部分は手書きでごまかしていましたが、結局否定の壁によって無意味になります）。 trait AllDistinct {} impl AllDistinct for () { } // 空のタプルは自明に異なる impl<H, Tail> AllDistinct for (H, Tail) where Tail: AllDistinct, H: NotIn<Tail>, // and H is not in the tail {} 妥当に見えます。再帰は空のタプルで終了します。各ステップでは、残りの部分が異なり、ヘッドが残りの部分に含まれないことが要求されます。標準的な構造再帰です。 私はこれを構築しました。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, // ← this is not a thing {} コンパイラ：error: expected one of `!`, `(`, `+`, `::`, `:`, `<`, `==`, or `=`, found `!=` 安定版Rustには、境界で型の不等式を表現する構文がありません。H != T はありません。「このトレイトは、他のトレイトが実装されていない場合に実装される」と書く方法はありません。不安定な機能である negative_impls は何年も前から存在しますが、コヒーレンス上の懸念から保留されたままです。期待しないほうが良いでしょう。 これは単に演算子が欠けているだけではありません。トレイトシステムは単調に実装について推論します。コードベースに実装を追加すると、より多くのコードがコンパイル可能になるだけで、既存のコードが無効になることはありません。負の推論は…