バースト下の L2 マーケットデータ:シーケンスのギャップ、リカバリ、数百セッションへのファンアウト

バースト下で L2 の更新を落とし、順序を入れ替えるハンドラは、たいてい一つの症状の裏にある二つの別々の障害である。一つは取り込み側にある。フィードのシーケンスを追い、ギャップを吸収せずに検出しなければならない場所だ。もう一つは配信側にある。正規化した一つの板を多数のセッションへファンアウトし、たった一つの遅いリーダーが他のセッションの受け取るものを変えてしまう場所だ。

二つの直し方は違い、間違ったほうを当てると、症状は消えずに移動する。以下は、バーストの中でもシーケンスを保たねばならないときのパイプラインの形である。ギャップとは実際に何か、リカバリはスナップショットをライブのストリームにどう接合するか、ファンアウトはどうやって順序を一度だけ決めるか、そしてコンフレーションはどこまで正直か。

シーケンス番号が約束するのは順序であって配信ではない

フィードは更新に番号を振る。その番号だけが、順序についての唯一のよりどころである。到着時刻はよりどころにならない。マルチキャスト経路は順序を入れ替え、一つの銘柄が複数のチャネルに乗り、受信キューは複数のコアに散り、バーストはそのすべてを引き伸ばす。到着順に並べるハンドラが正しいのは、ネットワークが静かなあいだだけ ― 誰も心配していなかった条件のときだけである。

リカバリのロジックを書く前に、フィードの六つの性質を知っておく必要がある。どれもギャップの意味を変える。

• シーケンスが対象とする単位 ― チャネル、銘柄、板のいずれか。チャネル単位の番号は、どの銘柄が更新を落としたかを教えてくれず、銘柄単位の番号は、チャネルが止まったことを教えてくれない
• 増分の規則。単位の中で厳密に連番か、穴が許された増加か。どちらも実在し、後者を前者と読むと、必要のなかったリカバリが起きる
• セッションの区切りで番号が振り直されるかどうか、そしてその印は何か ― 振り直しをギャップと読むと、全銘柄が同じ瞬間にリカバリへ入る
• ハートビートが現在のシーケンスを運ぶかどうか。運ばないなら、死んだ接続と静かな銘柄は見分けがつかない
• 再送があるかどうか、あるならどの範囲までか。ないなら、戻る道はスナップショットによるリカバリだけであり、頻繁に使えるだけ安くしておく必要がある
• スナップショットがどのシーケンス番号に揃っているか。それがなければ、スナップショットをライブのストリームに接合することは、そもそもできない

性質が本当に分からないところは、推測を書き込まずに計測する。六つはそれぞれリカバリ経路の分岐になり、そこでの思い違いは後になって、取引所と静かに食い違う板として見つかる。

ギャップと順序の入れ替わりは、数ミリ秒のあいだ見分けがつかない

どちらも始まり方は同じだ。次の更新が期待した番号を持っていない。違いは時間にある。だから判別は到着時ではなく、有界の待ちが切れた時点で行う。

• 順序ずれ:N を期待して N+2 を受け取り、待ちが開いているあいだに N+1 が届く。失われたものはなく、代償は待ち時間だけである
• 重複または再送:最後に適用した番号以下の番号。板に触れずに捨て、そして数える。重複率の上昇は経路について何かを語るからだ
• ギャップ:待ちが切れ、N+1 はついに来なかった。板は穴の先へ進めず、この銘柄はリカバリに入る
• 陳腐化:番号は正しいが、役に立つには遅すぎる。バイトは届いており、下流にとっては欠落と同じである

待ちは、伸びるキューではなく有界の構造である。期待した番号より先の更新を、シーケンスをキーにして保持する。だから解放は、並べ替えではなく引き当てになる。

• 解放はループである。期待した番号を適用し、続けてバッファ済みのものを、番号が連続するあいだ適用していく
• 期限は、保留中の更新の件数だけでなく時間で表す ― バーストは、件数で決めた枠を設計の意図よりはるかに早く埋める
• バッファが待つ分だけ、すべてのコンシューマが待つ。期限の長さは、安全そうに思えた数字ではなく、自分の経路で計測した順序の入れ替わりから決める
• バッファのあふれ自体がギャップの宣言である。待ちは時間だけでなくメモリでも有界だ
• 待ちは銘柄単位かチャネル単位であって、全体で一つにはしない。静かな銘柄が一つ、周りのすべてを止めてはならない

リカバリとは、すでにバッファしていたストリームにスナップショットを接合すること

壊れるのは接合の部分である。スナップショットとは、あるシーケンス番号時点の板であり、作られた瞬間から古い。それを使えるものにするのは、取得しているあいだにバッファしていた差分ストリームだ。

• スナップショットを要求する前に差分ストリームのバッファを始める。背後にライブのストリームがないスナップショットは、届いた時点ですでに相場に遅れている
• スナップショットがどのシーケンス番号と整合しているかを読む。フィードがそれを出さないなら、そのフィードは実質スナップショットのみであり、設計はそれを口に出して書かねばならない
• バッファした更新のうち、スナップショットのシーケンス以下のものを捨て、残りを順に適用する。その先頭がスナップショットの直後の更新でなければ、接合は失敗であり、リカバリをやり直す
• スナップショットが届く前にバッファがあふれたら、途中まで適用するのではなくリカバリをやり直す ― 部分的に適用したリカバリは、健全な板と見分けがつかない
• リカバリ中の銘柄は「劣化中」として、ストリーム上の明示的な状態で配信する。穴の空いた板を現在の板として配るのは、板がないことより悪い
• 接合の後に検証する。フィードがチェックサムを出しているならそれで、出していないなら、畳み込んだ自分の板と次のスナップショットが一致するかで

リカバリは障害ではなく通常の事象であり、そのコストは容量計画に入る。スナップショットの取得にどれだけかかるか、その間にどれだけのストリームをバッファするか、スナップショットのサービスがボトルネックになる前に、同時に何銘柄までリカバリできるか。

ファンアウト:正規化は一度、エンコードも一度、送信は多数へ

数百のターミナルセッションが同じ板を欲しがる。バーストで倍々に効いてくる間違いは、本来セッションごとではない仕事をセッションごとに行うことだ。購読者ごとに板を作り直す、あるいは同じ更新をソケットごとにシリアライズする。

• 板を所有するのは、銘柄シャードごとに一つのライターである。リーダーは決して書き換えない。これでロックも、どのバージョンが正なのかという問いも消える
• ライターは版を付けた更新をリングバッファへ書き、リーダーは各自のペースでそれを追う。だから遅れたリーダーが誰かを遅くすることはない
• 各更新はワイヤ形式ごとに一度だけエンコードし、セッション間では参照で共有する。セッションごとに行うのはフレーミングとフロー制御だけである
• 各セッションは自分の送信側シーケンス番号を持つ。だからクライアントは、上流のフィードを何も知らずに自分の欠落を検出できる
• 順序は銘柄ごとに保証する。クライアントが頼っているのはその保証だからだ。銘柄をまたぐ順序は、明示的に約束して実装するか、まったく約束しないかのどちらかである
• 単一プロセスの外へ出ると、ファンアウトはリレー層になる。各リレーは上流の購読を一つ取り、セッションの一部を受け持つ。だからライターの仕事量は一定のままである

ファンアウトのコストを決めるのは、更新を何回変換するかであって、いくつのソケットが受け取るかではない。一度エンコードして参照を渡す方式はセッション数に対してスケールし、セッションごとに板を作り直す方式はスケールしない。

遅いコンシューマは選ぶ方針であって、起きる事故ではない

どこかに、回線の悪いセッションや、描画ループが止まったターミナルがあり、その送信バッファが埋まる。取りうる振る舞いは四つあり、そのうち二つは事故でしか選ばれない。

• 遅いセッションが捌けるまでライターを止める:これは無し。一本の悪い接続を、そのシャード上の全員にとっての latency 事象に変えてしまう
• キューを無制限に伸ばす:遅いコンシューマがメモリ枯渇になり、次に、元のセッションとは無関係な停止になる
• 有界キューとコンフレーション:板の状態には正しい。クライアントが欲しいのは途中の一歩一歩ではなく現在の姿だからだ
• 有界キューとハイウォーターマークでの切断:コンフレーションできないストリームには正しい。一件落とすことが意味を落とすからだ
• どの方針を取るにせよ、キューはセッションごとであり、遅れは継続して計測する ― キューの深さと、配信したシーケンスとソケットへ書いたシーケンスの差である
• 切断は理由を伝える。理由のないクローズはループで再試行され、理由のあるクローズには再購読が続く

バックプレッシャーは二つの側が出会う場所だ。送信側が板のライターを押し戻せてしまうと、遅いターミナルがやがてフィードの畳み込みを遅らせ、取引所とは何の関係もない理由でギャップ検出が鳴りはじめる。両者のあいだに置いた有界のリングが、その連鎖を止める。

コンフレーションは状態には正直、イベントには誤り

板は状態である。クライアントが欲しいのは現在のレベルであり、すでに置き換わった値それ自体に意味はない。約定テープはイベントのログであり、その一件一件が起きた事実であって、要約して消せるものではない。

• コンフレーションしてよいもの:価格レベルの更新、最良気配、集計した板の厚み、そして直近価格やセッション出来高のような派生統計
• コンフレーションしてはいけないもの:約定と歩み値、注文と執行のレポート、オークションと立会フェーズの変化、そしてクライアントが時間で集計するものすべて ― コンフレーション済みのストリームから作ったテープは、自信をもって握られた誤った数字である
• コンフレーションはストリーム単位ではなくキー単位で行う。価格レベルごとに最新の更新を残せば板は保たれるが、全体で最新の更新だけを残すと、最後に動かなかったレベルがすべて失われる
• コンフレーション済みの更新は、それが表す状態のシーケンス番号を持つ。だからクライアントは、それがどの時点に対応するかを知れる
• コンフレーションの間隔は、報告する latency の一部である。間隔でコンフレーションしたストリームは、していないストリームで測った latency では説明できない
• 中間状態をすべて必要とするクライアント ― バックテスト、コンプライアンス記録 ― は、コンフレーションしていないストリームを取り、帯域で支払う

再接続は再同期であり、それらは一斉に来る

セッションが戻ってきたとき、サーバが連続性を証明できない限り、そのセッションが持つ板に価値はない。既定は、購読ごとに新しいスナップショットをシーケンス番号付きで渡し、クライアントは先にローカルの状態を捨ててからそれを適用することである。

• シーケンス番号からの再開を提供するのは、有界のリプレイバッファがある場合だけである。要求された番号がすでに落ちていれば、サーバはそう伝え、穴の空いたストリームを送るのではなくスナップショットに切り替える
• 再接続をまたぐセッション状態は明示的に決める。サーバがセッショントークンのもとで購読を有限時間だけ保持するか、クライアントが接続時に購読を出し直すかだ。どちらも成り立つが、暗黙の混在は成り立たない
• 再開後に重複が届くのは想定内であり、クライアントはシーケンスで捨てる。at-least-once とシーケンス番号の組み合わせは、exactly-once より正しく実装しやすい
• 再接続はまとまって来る。一つのセッションを切ったものは、たいてい多数を切っているからだ。クライアント側のジッター付きバックオフと、サーバ側のアドミッション制御が、リカバリが二度目の障害になるのを防ぐ
• その一斉の要求に対するスナップショットは、一定間隔で更新される銘柄ごとのキャッシュから配る。ライターがスナップショットをシリアライズするのは決まった周期であって、再接続してくるセッションごとではない
• クライアント側の板は作り直す。継ぎ当てはしない。古いレベルを残したまま新しい差分を上から当てるターミナルは、切断前の誤りを、見た目だけ新しい板へ持ち込む

設計で備えるべき障害は、一つの再接続ではない。ネットワーク事象によって数百のセッションが同じ一秒のうちに戻ってきて、それぞれが見ていた全銘柄のスナップショットを求め、その一方で取り込み側は同じ事象が生んだギャップから復旧している ― これである。

amBrain が公に裏付けられること:私たちはアルメニア・エレバンから、低 latency のトレーディングプラットフォーム、matching engine、リアルタイムビディングのシステムを Rust で作っており、公開しているマーケットデータの latency ― 5 ms 未満 ― は私たちが作る経路で計測したものである。あなたのハンドラがバーストでシーケンスを落としているなら、価値のある話は、どちらかを書き直す前に取り込み側と配信側を切り分ける話である。