モスクワ取引所の取引および清算システムのアーキテクチャの進化。 パート1

こんにちは、みんな！ 私の名前はセルゲイ・コスタンバエフです。取引所で取引システムの中核を開発しています。

ハリウッド映画でニューヨーク証券取引所が描かれるとき、それはいつも次のようになります。人が群がり、誰もが何かを叫び、紙を振り、完全な混乱が起こっています。 ここモスクワ取引所ではこのようなことは一度も起こったことはありません。取引は当初から電子的に行われ、Spectra (外国為替市場) と ASTS (外国為替、株式、短期金融市場) という XNUMX つの主要なプラットフォームに基づいているからです。 そして今日は、ASTS 取引および清算システムのアーキテクチャの進化、さまざまなソリューションと発見について話したいと思います。 話が長くなりそうなので２部に分けさせていただきました。

当社は、あらゆるクラスの資産を取引し、あらゆる種類の取引サービスを提供する世界でも数少ない取引所の 25 つです。 例えば、昨年は債券取引高で世界第13位、全証券取引所中XNUMX位、公的取引所中資本金XNUMX位となりました。

プロの取引参加者にとって、応答時間、時間分布の安定性 (ジッター)、複合体全体の信頼性などのパラメータは重要です。 現在、私たちは XNUMX 日に数千万件のトランザクションを処理しています。 システム カーネルによる各トランザクションの処理には数十マイクロ秒かかります。 もちろん、大晦日の携帯電話事業者や検索エンジン自体の仕事量は当社よりも高いですが、上記の特性と合わせて、仕事量の点で当社に匹敵するものはほとんどないと思われます。 同時に、システムが一瞬たりとも速度を落とさず、完全に安定して動作し、すべてのユーザーが平等な立場にあることが私たちにとって重要です。

ちょっとした歴史

1994 年に、オーストラリアの ASTS システムがモスクワ銀行間通貨取引所 (MICEX) で開始され、その瞬間からロシアの電子取引の歴史は数えられます。 1998 年に、インターネット取引を導入するために取引所のアーキテクチャが最新化されました。 それ以来、すべてのシステムとサブシステムにおける新しいソリューションとアーキテクチャの変更の実装速度は加速するばかりです。

当時、交換システムはハイエンド ハードウェア、つまり非常に信頼性の高い HP Superdome 9000 サーバー ( PA-RISC)、入出力サブシステム、ネットワーク、RAM (実際には、RAM の RAID アレイがありました)、プロセッサ (ホットスワップ可能) など、すべてが複製されていました。 マシンを停止せずにサーバー コンポーネントを変更することができました。 私たちはこれらのデバイスに依存しており、事実上フェイルセーフであると考えていました。 オペレーティング システムは Unix に似た HP UX システムでした。

しかし、2010年頃から、高頻度取引（HFT）、または高頻度取引、簡単に言うと証券取引所ロボットと呼ばれる現象が出現しました。 わずか 2,5 年半で、サーバーの負荷は 140 倍に増加しました。

古いアーキテクチャと設備では、このような負荷に耐えることは不可能でした。 何らかの方法で適応する必要がありました。

開始

交換システムへのリクエストは XNUMX つのタイプに分類できます。

• 取引。 ドル、株、その他のものを購入したい場合は、取引システムにトランザクションを送信し、成功に関する応答を受け取ります。
• 情報リクエスト。 現在の価格を知りたい場合は、オーダーブックまたはインデックスを表示してから、情報リクエストを送信してください。

概略的に、システムのコアは XNUMX つのレベルに分割できます。

• ブローカーとクライアントが動作するクライアント レベル。 これらはすべてアクセス サーバーと対話します。
• ゲートウェイ サーバーは、すべての情報要求をローカルで処理するキャッシュ サーバーです。 ズベルバンク株が現在どのくらいの価格で取引されているか知りたいですか? リクエストはアクセス サーバーに送信されます。
• ただし、株式を購入したい場合、リクエストは中央サーバー (Trade Engine) に送られます。 市場の種類ごとにそのようなサーバーが XNUMX つあり、それらは重要な役割を果たしており、私たちがこのシステムを作成したのは彼らのためにです。

取引システムの中核は、すべての取引が為替取引である賢いメモリ内データベースです。 ベースは C で書かれており、唯一の外部依存関係は libc ライブラリであり、動的なメモリ割り当てはまったくありませんでした。 処理時間を短縮するために、システムは配列の静的セットと静的データの再配置から開始します。まず、当日のすべてのデータがメモリにロードされ、それ以上のディスク アクセスは実行されず、すべての作業がメモリ内でのみ実行されます。 システムの起動時には、すべての参照データがすでにソートされているため、検索は非常に効率的に機能し、実行時間はほとんどかかりません。 すべてのテーブルは動的データ構造の侵入型リストとツリーで作成されているため、実行時にメモリ割り当てが必要ありません。

当社の取引および清算システムの開発の歴史を簡単に振り返ってみましょう。
取引および清算システム アーキテクチャの最初のバージョンは、いわゆる Unix インタラクションに基づいて構築されました。共有メモリ、セマフォ、キューが使用され、各プロセスは単一のスレッドで構成されていました。 このアプローチは 1990 年代初頭に広く普及しました。

システムの最初のバージョンには、XNUMX つのレベルのゲートウェイと取引システムの中央サーバーが含まれていました。 作業の流れはこんな感じでした。

• クライアントがリクエストを送信すると、そのリクエストはゲートウェイに到達します。 形式の有効性 (データ自体の有効性はチェックしません) をチェックし、不正なトランザクションを拒否します。
• 情報要求が送信された場合、それはローカルで実行されます。 トランザクションについて話している場合、トランザクションは中央サーバーにリダイレクトされます。
• 次に、取引エンジンはトランザクションを処理し、ローカル メモリを変更し、別のレプリケーション エンジンを使用してレプリケーションのためにトランザクションとトランザクション自体に応答を送信します。
• ゲートウェイはセントラル ノードから応答を受信し、それをクライアントに転送します。
• しばらくすると、ゲートウェイはレプリケーション メカニズムを通じてトランザクションを受信し、今度はそれをローカルで実行し、次の情報要求で最新のデータが表示されるようにデータ構造を変更します。

実際、これはゲートウェイが取引システムで実行されるアクションを完全に複製する複製モデルを記述しています。 別個のレプリケーション チャネルにより、複数のアクセス ノード間でトランザクションが同じ順序で実行されることが保証されます。

コードはシングルスレッドであったため、多くのクライアントにサービスを提供するために、プロセス フォークを使用した古典的なスキームが使用されました。 ただし、データベース全体をフォークするには非常にコストがかかるため、TCP セッションからパケットを収集し、それらを XNUMX つのキュー (SystemV メッセージ キュー) に転送する軽量のサービス プロセスが使用されました。 Gateway と Trade Engine はこのキューでのみ動作し、そこからトランザクションを実行します。 どのサービス プロセスがそれを読み取るべきかが明確ではなかったため、それに応答を送信することはできなくなりました。 そこで私たちはあるトリックに頼りました。フォークされた各プロセスはそれ自体の応答キューを作成し、受信キューにリクエストが入ると、応答キューのタグが即座にキューに追加されました。

大量のデータをキューからキューへ絶えずコピーすると、特に情報要求によく見られる問題が発生しました。 そこで、別のトリックを使用しました。応答キューに加えて、各プロセスが共有メモリ (SystemV 共有メモリ) も作成しました。 パッケージ自体はその中に配置され、タグのみがキューに保存されるため、元のパッケージを見つけることができます。 これは、プロセッサのキャッシュにデータを保存するのに役立ちました。

SystemV IPC には、キュー、メモリ、およびセマフォ オブジェクトの状態を表示するためのユーティリティが含まれています。 私たちはこれを積極的に使用して、特定の瞬間にシステムで何が起こっているか、パケットがどこに蓄積されているか、何がブロックされているかなどを理解しました。

最初のアップグレード

まず第一に、単一プロセスのゲートウェイを廃止しました。 その重大な欠点は、クライアントからの XNUMX つのレプリケーション トランザクションまたは XNUMX つの情報要求を処理できることです。 また、負荷が増加すると、ゲートウェイはリクエストの処理に時間がかかり、レプリケーション フローを処理できなくなります。 さらに、クライアントがトランザクションを送信した場合は、その有効性を確認してさらに転送するだけで済みます。 したがって、単一のゲートウェイ プロセスを、並列実行できる複数のコンポーネント、つまりマルチスレッドの情報プロセスとトランザクション プロセスを、RW ロックを使用して共有メモリ領域上で互いに独立して実行できるものに置き換えました。 そして同時にディスパッチとレプリケーションのプロセスを導入しました。

高頻度取引の影響

上記のバージョンのアーキテクチャは 2010 年まで存在していました。 その一方で、私たちは HP Superdome サーバーのパフォーマンスに満足できなくなりました。 さらに、PA-RISC アーキテクチャは事実上機能不全に陥り、ベンダーは重要なアップデートを提供しませんでした。 その結果、HP UX/PA RISC から Linux/x86 への移行が始まりました。 移行は、アクセス サーバーの適応から始まりました。

なぜ再びアーキテクチャを変更する必要があったのでしょうか? 実際のところ、高頻度取引によりシステム コアの負荷プロファイルが大幅に変化しました。

重大な価格変動を引き起こした小規模な取引があるとします。誰かが XNUMX 億ドルを購入したとします。 数ミリ秒後、すべての市場参加者がこれに気づき、修正を開始します。 当然のことながら、リクエストは巨大なキューに並び、システムがキューをクリアするには長い時間がかかります。

この 50 ミリ秒間隔では、平均速度は 16 秒あたり約 20 トランザクションになります。 ウィンドウを 90 ミリ秒に短縮すると、平均速度は 200 秒あたり XNUMX 万トランザクション、ピーク時には XNUMX 万トランザクションになります。 言い換えれば、負荷は一定ではなく、突然のバーストを伴います。 また、リクエストのキューは常に迅速に処理される必要があります。

しかし、そもそもなぜ行列ができるのでしょうか？ したがって、この例では、多くのユーザーが価格の変更に気づき、それに応じてトランザクションを送信しました。 これらは Gateway に到着し、シリアル化され、特定の順序が設定されてネットワークに送信されます。 ルーターはパケットをシャッフルして転送します。 誰の荷物が最初に到着したか、その取引は「勝ち」となります。 その結果、取引所クライアントは、同じトランザクションが複数のゲートウェイから送信された場合、そのトランザクションが高速に処理される可能性が高まることに気づき始めました。 すぐに、交換ロボットがゲートウェイにリクエストを大量に送り込み始め、雪崩のようにトランザクションが発生しました。

新たな進化のラウンド

広範なテストと研究を行った後、私たちはリアルタイム オペレーティング システム カーネルに切り替えました。 このために、RedHat Enterprise MRG Linux (MRG はメッセージング リアルタイム グリッドの略) を選択しました。 リアルタイム パッチの利点は、可能な限り高速に実行できるようにシステムを最適化することです。すべてのプロセスが FIFO キューに並べられ、コアを分離でき、イジェクトがなく、すべてのトランザクションが厳密な順序で処理されます。

赤 - 通常のカーネルでキューを使用して動作、緑 - リアルタイム カーネルで動作。

ただし、通常のサーバーで低遅延を実現するのはそれほど簡単ではありません。

• x86 アーキテクチャにおいて重要な周辺機器を操作するための基礎となる SMI モードは、大きく干渉します。 あらゆる種類のハードウェア イベントの処理とコンポーネントとデバイスの管理は、いわゆるトランスペアレント SMI モードでファームウェアによって実行されます。このモードでは、オペレーティング システムはファームウェアが何を行っているかをまったく認識しません。 原則として、すべての主要ベンダーは、SMI 処理量を削減できるファームウェア サーバー用の特別な拡張機能を提供しています。
• プロセッサ周波数を動的に制御してはなりません。これにより、ダウンタイムがさらに発生します。
• ファイル システム ログがフラッシュされると、カーネル内で特定のプロセスが発生し、予測できない遅延が発生します。
• CPU アフィニティ、割り込みアフィニティ、NUMA などに注意する必要があります。

リアルタイム処理用の Linux ハードウェアとカーネルのセットアップに関するトピックは、別の記事に値すると言わざるを得ません。 良い結果が得られるまで、私たちは実験と研究に多くの時間を費やしました。

PA-RISC サーバーから x86 に移行する場合、実際にはシステム コードを大幅に変更する必要はなく、適応して再構成するだけで済みました。 同時に、いくつかのバグを修正しました。 たとえば、PA RISC がビッグ エンディアン システムであり、x86 がリトル エンディアン システムであるという事実の影響は、すぐに表面化しました。たとえば、データが正しく読み取られなかったなどです。 さらに厄介なバグは、PA RISC が使用するものでした。 一貫して一貫した (逐次的に一貫性のある) メモリ アクセスに対して、x86 は読み取り操作の順序を変更できるため、あるプラットフォームでは完全に有効だったコードが別のプラットフォームでは壊れてしまいます。

x86 に切り替えた後、パフォーマンスはほぼ 60 倍に向上し、平均トランザクション処理時間は XNUMX μs に短縮されました。

次に、システム アーキテクチャにどのような重要な変更が加えられたかを詳しく見てみましょう。

ホットリザーブエピック

コモディティサーバーに切り替えるとき、私たちは信頼性が低いことを認識していました。 したがって、新しいアーキテクチャを作成するときは、XNUMX つ以上のノードで障害が発生する可能性を事前に想定していました。 したがって、バックアップ マシンに迅速に切り替えることができるホット スタンバイ システムが必要でした。

さらに、他にも次のような要件がありました。

• いかなる状況でも、処理されたトランザクションが失われることはありません。
• システムはインフラストラクチャに対して完全に透過的である必要があります。
• クライアントには切断された接続が表示されないはずです。
• これは交換にとって重要な要素であるため、予約によって大幅な遅延が生じてはなりません。

ホット スタンバイ システムを作成するとき、二重障害 (たとえば、XNUMX 台のサーバー上のネットワークが動作を停止し、メイン サーバーがフリーズする) などのシナリオは考慮していませんでした。 ソフトウェアのエラーはテスト中に特定されるため、その可能性は考慮されていませんでした。 また、ハードウェアの誤った動作は考慮されていませんでした。

その結果、次のようなスキームにたどり着きました。

• メイン サーバーはゲートウェイ サーバーと直接対話しました。
• メイン サーバーで受信されたすべてのトランザクションは、別のチャネルを介してバックアップ サーバーに即座に複製されました。 問題が発生した場合は、裁定者 (ガバナー) が切り替えを調整します。

  

• メイン サーバーは各トランザクションを処理し、バックアップ サーバーからの確認を待ちました。 遅延を最小限に抑えるために、バックアップ サーバーでトランザクションが完了するのを待つ必要はありませんでした。 トランザクションがネットワークを通過するのにかかる時間は実行時間と同程度であったため、追加の遅延は発生しませんでした。
• 前回のトランザクションではメインサーバとバックアップサーバの処理状況しか確認できず、今回のトランザクションの処理状況は不明でした。 まだシングルスレッドプロセスを使用していたので、バックアップからの応答を待っていると処理フロー全体が遅くなる可能性があるため、合理的な妥協策を講じました。つまり、前のトランザクションの結果を確認しました。

このスキームは次のように機能しました。

メインサーバーが応答を停止しても、ゲートウェイは通信を続けているとします。 バックアップ サーバーでタイムアウトが発生すると、バックアップ サーバーはガバナーに連絡し、ガバナーがバックアップ サーバーにメイン サーバーの役割を割り当て、すべてのゲートウェイが新しいメイン サーバーに切り替わります。

メイン サーバーがオンラインに戻ると、一定期間ゲートウェイからサーバーへの呼び出しがないため、内部タイムアウトもトリガーされます。 それから彼は知事にも頼って、知事は彼を計画から除外した。 その結果、取引所は取引期間の終了まで XNUMX つのサーバーで動作します。 サーバー障害の可能性が非常に低いため、このスキームは非常に許容できると考えられ、複雑なロジックが含まれておらず、テストが簡単でした。

継続するために。

出所： habr.com