Rust で matching engine を設計する:GC の停止のない price-time priority

現物取引所の matching engine の仕事は狭い。順序づけられたコマンド列 ― 新規、キャンセル、訂正 ― を受け取り、price-time priority のもとで order book に適用し、約定・板更新・拒否・受理確認という順序づけられたイベント列を出す。

難しさはすべて、その仕事の上に積まれた3つの制約から来る。同じ入力を再生すれば結果は毎回同一でなければならない。一部約定した注文の残数はキューでの位置を保たなければならない。そしてバーストが来ても latency の裾は動いてはならない。

order book は、FIFO キューの上に載る価格レベルのソート済みインデックスである

板は2つのサイドからなり、それぞれ価格順のレベルの集まりである。レベルは数値ではない ― その価格にある待機注文の、到着順のキューである。マッチングは最良レベルに絶えず触れ、奥のレベルにはめったに触れない。構造は優雅さではなく、そのアクセスパターンに合わせて選ぶ。

• 価格は tick 単位の整数で、浮動小数点は使わない ― tick はその銘柄の単位であり、整数の比較と算術は厳密である
• 各サイドはレベルを価格順に保ち、最良気配は探索なしで到達できる ― 板の最良気配はコマンドごとに毎回読まれる
• 各プライスレベルは待機注文の FIFO キューと、集計済みの待機数量を保持する。キューをたどって集計を計算し直す必要はない
• 注文は事前確保したスラブに置かれ、インデックスのハンドルで参照する。キューは intrusive で、次と前のリンクは注文レコードの中にある
• クライアント注文 ID からスラブハンドルへの別のマップにより、キャンセルと訂正は直接引きになる。キャンセルが板を走査することはない
• キューからの削除は探索ではなくハンドルで行う ― 板の奥にある待機注文のキャンセルは、最良気配でのキャンセルと同じコストで済む

intrusive なキューとインデックスハンドルの帰結として、待機注文は生きている間メモリ上を動かない。キューでの位置はリンクの性質であって、たまたま置かれている場所の性質ではない。それが後の部分約定を安く済ませる。

price-time priority は、レベルを回り、次にキューを回すループである

入ってきた攻撃側の注文は、反対側を最良気配から内側へたどる。各レベルでは FIFO キューを先頭からたどる。そのレベルの価格が入ってきた注文にとって受け入れられなくなるか、入ってきた数量がゼロになった時点で止まる。

• 反対側の最良レベルを取る。その価格が入ってきた指値と交差しなければ、そこで止める
• そのレベルのキューの先頭の注文を取る ― その価格で最も古く、時間優先により最初に約定する
• 約定数量は2つの残数のうち小さいほう。約定価格は待機注文の価格である。条件を先に示したのは待機注文だからだ
• 両方の残数を減らし、約定イベントを出し、レベルの集計値を減らす
• 待機注文の残数がゼロになれば、キューから外してスラブのスロットを返す。レベルが空になれば、そのレベルを削除する
• 入ってきた数量がゼロになるか、受け入れ可能なレベルが尽きるまで繰り返す

注文種別の意味論は、このループの内側ではなく境界で決める。Immediate-or-cancel は残数を板に置かず捨てる。Fill-or-kill はまず空打ちで確認し、全量執行するか拒否する。Post-only は到着時に交差するなら拒否する。これらをループの外に置くことで、板の状態が変わる場所はループだけに保たれる。

自己約定防止、最小数量、tick とロットの検証も、ループの前に置くべきものだ。マッチングに届いた注文はすでに正しい形だと証明されている。だからループには、速度を落としたり判断が食い違ったりするエラー分岐が無い。

裾を予測可能にするのは決定論性であり、それを壊すのはアロケーションである

平均 latency が問題になることはめったにない。問題はバースト中の最悪値だ。エンジンが最も重要になるのはそのときであり、stop-the-world の停止が最も起きやすいのもそのときである。garbage collector を持つマネージドランタイムでは、その停止はあなたではなくコレクタが決め、ごみを生んだバーストの真ん中で起きる。

手動のアロケーションも同じ問題の小さい版だ。汎用アロケータはフリーリストをたどり、ロックを取り、カーネルにメモリを要求することがある。そしてそれをした呼び出しこそが裾に現れる。どちらの場合も対処は同じ。ホットパスではそもそもアロケートしない。

• 注文レコード、レベルレコード、イベントバッファは、起動時にサイズを決めたアリーナから取る ― 定常状態でのマッチング経路のアロケーション回数はゼロ
• 解放されたスロットはアリーナ内のフリーリストに戻る。売買の多い銘柄はセッション中ずっと同じメモリを使い回す
• 構造は形もサイズも固定で、容量の上限は拡張ではなく拒否として扱う
• 外向きのイベントは事前確保したリングバッファに書き、別スレッドが読み出す ― マッチングスレッドが消費側でブロックすることはない
• マッチングスレッドは板に対する唯一の書き手である。だから板の状態にロックは要らず、解決すべき順序の曖昧さも無い
• 入力はエンジンに届く前に採番され、順序を決めるのは到着時刻ではなくシーケンス番号である

エンジンが決定論的であるとは、同じ入力列が、別のマシンでも1年後でも、バイト単位で同じ出力列を生むということだ。マッチング経路の中で実時間、スレッドのスケジューリング、ハッシュの反復順を読むものはすべて、その性質を壊す。

したがってタイムスタンプは入力であり、エンジンが自分で読むものではない。シーケンサはコマンドを受理したときに時刻を刻み、マッチングループはその刻印をデータとして扱う。乱数が要るなら、シードがジャーナルの一部になっている生成器から得る。

ジャーナルこそがエンジンの状態であり、板はそのキャッシュである

復旧は、マッチングが動いた後に取って付ける機能ではない。エンジンは受理したコマンドを順序どおり追記専用のジャーナルに書き、メモリ上の板はそのジャーナルを畳んだ結果にすぎない。クラッシュ後の再構築とは、それを再生することだ。

• コマンドはマッチングの前にジャーナルへ記録され永続化される。そのため、受理された注文が確認応答と実行の間のクラッシュで失われることはない
• ジャーナルは入力の列であって出力ではない ― 出力は導かれるものであり、それを導き直すことが再生そのものだ
• 板の定期スナップショットは取得時のシーケンス番号を持つ。復旧はスナップショットを読み込み、ジャーナルの末尾だけを再生する
• スナップショットと再生の一致は仮定せずに検査する。前のスナップショットから再生すれば、次のスナップショットが再現されなければならない
• イベント列は同じシーケンス番号を持つ。下流の消費者 ― リスク、決済、マーケットデータ ― は手作業で同期し直すのではなく、既知の地点から再開できる

ジャーナルを書くのはエンジンだが、永続性はストレージ経路の性質であり、確認応答を返す前に何台のマシンがその記録を持っているかの性質である。これはレプリケーションとハードウェアの決定であり、復旧時間が実際に決まるのはそこだ。

テストとは、決定論的な再生と、常に成り立つべき不変条件である

決定論性こそがエンジンをテスト可能にする。同じ入力が同じ出力を返すから、記録したセッションはそのまま回帰テストになり、一度見つけた不具合は追い回すのではなく正確に再現できる。

• リプレイ用ハーネス。記録したコマンド列を流し、出力されたイベント列を保存済みのものと比較し、最初に食い違ったところでシーケンス番号とともに失敗させる
• テストビルドではコマンドごとに不変条件を検査する ― キューは到着順、レベルの集計値はキューの合計と一致、板は交差しない、数量の総和はすべての約定を通じて保存される
• ランダムだが正しい形のコマンド列を生成し、個別の結果ではなく不変条件を検証するプロパティベーステスト
• 差分参照モデル。素朴なデータ構造による低速だが明らかに正しい実装を同じ入力で走らせ、食い違いはすべて高速側のバグとして扱う
• デコーダの境界でのファジング。不正な入力が外から届くのはここであり、panic が起きればマッチングスレッドごと落ちる
• 心配しているバーストの形で latency を測り、平均ではなく分布を記録する。設計を決めるのは裾の数字だからだ

ここで Rust が与えるもの、与えないもの

Rust はループ自体を速くするというより、問題のひとつのカテゴリを消す。garbage collector が無いので、背後で勝手に停止が計画されることはない。所有権のおかげで、単一書き手という規律はコードレビューが気づくものではなく、コンパイラが強制するものになる。ライフタイムのない言語では間違えやすいスラブハンドルと intrusive なリンクも、ここでは検査できる。デバッグビルドでの整数オーバーフローの panic は、板を静かに壊す種類のバグを捕まえる。

正直に線を引けば、裾の latency を決めるものの大半は言語ではない:

• カーネルのスケジューリング、割り込み処理、CPU ピニング、電源管理のほうが、マッチングのコードより裾を大きく動かす
• ネットワークインターフェース、カーネルバイパスの有無、取引所までの物理経路が、エンジンには下回れない下限を決める
• 境界でのシリアライズとワイヤプロトコルが支配的なコストであることが多く、マッチングそのものではない
• マッチングの意味論、注文種別、手数料とリベートの規則、市場フェーズはビジネス上の決定である ― 素早く実装された誤った規則は、やはり誤りだ
• リスクチェック、ポジション上限、決済経路はエンジンの外にあり、それぞれ固有の latency と障害モードを持つ
• 運用 ― デプロイ、監視、再生に失敗したときの手順書 ― が、その保証が本番障害との接触を生き延びるかを決める

Rust には代償もある。borrow checker は、まだ形の定まらない設計の最初の数週間を遅くする。取引所固有のプロトコルのエコシステムは古い言語より薄い。ロックフリー構造まわりの unsafe ブロックは、他の言語の同等コードと同じレビューの規律を要する。Rust を選ぶのは、latency の裾と、単一書き手のコアにおけるメモリ安全性についての判断であって、開発者の快適さについての判断ではない。

amBrain は2019年からアルメニア・エレバンでトレーディング基盤を作り、ホットパスは Rust で書いてきた ― マーケットデータの配信は 5 ms 未満、pre-trade リスクチェックは 1 ms 未満。matching engine を設計中で、板の構造やジャーナル形式、リプレイ用ハーネスを一緒に見ていきたいなら、その話はホットパスの1行目を書く前にしておく価値がある。