質問への回答

歴史

Phaserは、Java 7で導入され、CyclicBarrierやCountDownLatchの堅牢な参加者制限および固定構造の制約を克服しました。これらは、事前に決定されたスレッド数を必要とし、数百のスレッドが単一の原子カウンタに同時にアクセスすると、大量のキャッシュ整合性トラフィックが発生しました。導入前は、大規模なフォーク-ジョインパイプラインや段階的計算グラフは、到着するスレッドごとに中央の64ビット状態単語を更新するために、すべてのプロセッサソケット間でキャッシュラインの無効化が必要であったため、CASの再試行の嵐により崩壊していました。

問題

平坦なバリアはメモリホットスポットを作成します。数百のスレッドが同時に**arriveAndAwaitAdvance()**を呼び出すと、 packed phase、party、および未到着カウントを含む単一の原子変数を通して直列化され、NUMAマシンは再試行ループでインターコネクトを飽和させます。この競合によりライブロックが発生し、CPUは有用な作業を行う代わりにキャッシュを調べたり、CMPXCHG命令のスピンをかけたりするのに多くのサイクルを費やし、スループットを利用可能なコアに関係なくシングルスレッドエグゼキュータのそれにまで低下させます。

解決策

Phaserは、ルートPhaserが子のphaserを親として持つ階層化された木構造を実装し、実質的に到着カウンタをハードウェアの境界に整列した異なるメモリ位置に分散させます。到着は子のフェーズが完了したときだけ上方に伝播され、競合を対数的に分散させます; ルートの原子状態単語は、スレッドごとではなく子の完了ごとに1回だけ変更され、不泊のロジックは待機者を解放する際にトンニングハードを回避するためにQNodeオブジェクトのTreiberスタックを利用します。

実生活からの状況

問題の説明

高頻度取引プラットフォームは、マーケットデータの取り込み、リスク計算、注文提出の3段階のパイプラインを必要とし、800スレッドを4つのNUMAソケットにわたって同期させる必要がありました。既存のCyclicBarrierの実装は、すべての800スレッドが単一の64ビット状態変数に争ったため、マーケットオープンのボラティリティ中にp99のレイテンシスパイクが80ミリ秒を超え、大量のバスロックとCASの再試行が発生し、コアが100%の稼働率でピン留めされながらもフェーズが進行しませんでした。

解決策評価

分散カウンタを用いたストライプバリア

障壁を32の小さなCyclicBarrierインスタンスに手動でシャーディングし、スレッドをシャードにラウンドロビンで割り当てることを検討しました。このアプローチは、バリアごとの競合を32倍に減少させることができましたが、全体のフェーズの整合性を保証するためには追加の調整層が必要で、それがレース状態の発生の原因となり、動的なスレッド登録が実行時スパイク中にシャード間でスレッドを再バランスさせることがほぼ不可能になるという壊滅的な複雑性をもたらしました。

平坦なPhaser構成

単一のルートPhaserへの移行は動的登録の利点を提供し、固定参加者制約を排除しましたが、プロファイリングでは800のスレッドが同時にarriveAndDeregisterを呼び出すことで依然として単一の原子状態単語でキャッシュラインストームを引き起こすことが明らかになりました。PhaserのTreiberスタックは、Object.wait()と比較して駐車オーバーヘッドを減少させましたが、ルートカウンタはメモリホットスポットのままであり、この参加者規模でのCyclicBarrierをわずかに改善するだけでした。

階層的Phaserツリー

我々はPhaserオブジェクトのバランスの取れたクアッドツリーを実装し、各物理的CPUソケットをブランチに、個々のコアを葉にマッピングしました。これにより、ローカル到着をソケットローカルキャッシュラインに制限します。この対数的な伝播により、ルートで競合するのはわずか4つのソケットレベルのphaserになり、クロスソケットキャッシュ整合性トラフィックが2桁のオーダーで減少し、取引スレッドがセッション中に参加しても動的な登録意味論を保持しました。

選択された解決策とその理由

階層的ツリーが選ばれたのは、製品ハードウェアのNUMAアーキテクチャに直接アプローチし、O(N)のキャッシュ無効化をO(log N)のソケットレベル更新に変換したからです。ストライプバリアとは異なり、ツリーはPhaser APIの簡潔さを維持し、トポロジに気づくことなくスレッドが葉ノードに登録できるようにし、内部の親-子参照がarriveAndAwaitAdvanceの再帰を通じて伝播を自動的に処理しました。

実装スニペット

// 2層ツリーを構築中: ルート -> ソケット -> コア
Phaser root = new Phaser() {
    protected boolean onAdvance(int phase, int parties) {
        return phase >= MAX_PHASES || parties == 0; // 終了ロジック
    }
};

Phaser[] socketPhasers = new Phaser[SOCKET_COUNT];
for (int s = 0; s < SOCKET_COUNT; s++) {
    socketPhasers[s] = new Phaser(root);
    for (int c = 0; c < CORES_PER_SOCKET; c++) {
        Phaser corePhaser = new Phaser(socketPhasers[s]);
        corePhaser.register(); // 作業スレッドの事前登録
        corePhasers.add(corePhaser);
    }
}

結果

本番のデプロイは、フェーズ遷移レイテンシp99を80ミリ秒から1ミリ秒未満に削減し、ボラティリティスパイク中のコアピンニングを排除し、負荷に応じてスレッドプールの動的スケーリングを可能にし、最終的に追加で4万トランザクション/秒を処理しました。

候補者が見落とすことが多いこと

どのようにしてPhaserは、アクティブなフェーズ中にarriveAndDeregister()を呼び出すスレッドと、別のスレッドがregister()を呼び出すことを防ぎますか？

register()は、原子性を持ってpartiesとunarrivedカウントを64ビット状態単語内にあるCASを使用してインクリメントしますが、arriveAndDeregister()はそれらを原子性を持ってデクリメントし、未到着カウントがゼロに達した場合にフェーズの進行をトリガーする必要があります。この実装は、状態単語上のCAS操作を再試行してフェーズ番号が安定するまで待機することによってこれを解決します; フェーズが操作中に進むと、新しい登録は待機者のTreiberスタックを介して次のフェーズにDeferredされ、これは新しい当事者が部分的なフェーズ遷移や内部カウントの損傷を決して観察しないことを保証します。

なぜPhaserはスレッドをブロックするためにLockSupport.parkNanos()**を使用し、**Object.wait()/notify()を使用しないのでしょうか、また、これは「階層的到着」プロトコル中にどのような特定の危険を避けますか？

Object.monitorメカニズムは、スレッドが待機する前にモニターロックを取得する必要があり、これは中央のロックオブジェクトでの追加の競合ポイントを生じさせ、到着のための待たない進行保証を侵害します。Phaserは、待機スレッドが短時間スピンの後にLockSupport.parkNanos()を呼び出し、到着スレッドがロックを保持せずにLockSupport.unpark()を介して特定の後続者を解除できるようにするQNodeオブジェクトのTreiberスタックを使用します。これにより、待機者がモニタに入る前に通知スレッドが信号を送信する可能性があるという「失われたウェイクアップ」の危険を防ぎます。

フェーズ整数がInteger.MAX_VALUEからゼロにラッピングされる代数的な重要性は何ですか、そしてこの整数のオーバーフローがどのようにして時間に関する順序を保証しますか？

フェーズカウンタは意図的に2^32でオーバーフローする符号なし32ビット整数です; Phaserはフェーズpが状態単語のボラティリティ書き込み-読み取りペアを介してフェーズp+1の前に発生することを保証するため、オーバーフローは4億フェーズの後にリセットされる前の発生-前関係のサイクルを作成します。候補者はしばしば、比較 (phase - targetPhase) < 0がオーバーフローバウンダリを越えても時間の順序を正しく決定することを見逃します。これは2の補数算術により、フェーズ0で解放された待機者が、JMMのvolatileセマンティクスを介してフェーズInteger.MAX_VALUEで行われたすべての書き込みを正しく認識することを保証し、フェーズ空間を可視性エッジのリングバッファとして効果的に扱います。