アルゴリズム取引システム用のデータベースはどのように選択すればよいでしょうか?

[[314073]]

あらゆるソフトウェア システムの重要なコンポーネントは、データを保存、取得、分析するためのデータベースです。この記事では、アルゴリズム取引プラットフォームに適したデータベースの特徴について説明します。どのようなデータベースが利用可能ですか?

広い意味では、データベースはデータの記録と管理 (OLTP) およびデータの分析 (OLAP) の機能を提供します。ほとんどのデータベースは、これらの機能の 1 つに優れていますが、一部のメトリックには強みがあり、他のメトリックには欠けています。たとえば、一貫性と耐久性に優れたトランザクションに優れたリレーショナル データベースは、データ構造をロックし、すべてのディスク書き込みをフラッシュする必要があるため、パフォーマンスの面ではあまり優れていない可能性があります。対照的に、パフォーマンスを優先するデータベースでは、緩和された一貫性モデルを使用する必要がある場合があります。

特定の機能や特徴の優先順位に応じて、さまざまな種類のデータベースがさまざまなシナリオに適しています。

1. アルゴリズム取引システムのデータストレージ

完璧さ、つまり大量のデータを永続的かつ一貫して保存し、リアルタイム分析を迅速に実行することを望む場合、これは可能でしょうか?コンピュータサイエンスの理論では欲張りすぎないように警告していますが、参考にする価値のあるエンジニアリングのアイデアがいくつかあります。

主な設計目標は次のとおりです。

• 大量のイベントを永続的なストレージにすばやく取り込みます (1 日数時間で 1 秒あたり約 250K ～ 100 万イベント。各イベントは約 100 ～ 200 バイト、フィールド数は 10 ～ 30 を想定しています)
• 集計を含むリアルタイム分析
• パターンや傾向を調べるために大量の履歴データを処理できる

上記の設計目標に基づいて、いくつかのソリューションを構築できますが、基本的にはすべて、さまざまな追加機能を提供するためにデータ ストレージの階層化が必要です。

解決策の1つは次のとおりです。

1. トランザクション システム内のすべてのイベントを、追加専用のファイル ログなどの高速データ ストアに保存します (高可用性システムでは複数のノードに複製または再作成される可能性があります)。ファイルは永続的なストレージを提供しますが、実際のクエリ機能はありません。
2. ログ ファイルの内容は、メモリ内データベース/キャッシュに順番に抽出されます。このレイヤーでは一貫性チェック、レプリケーション、または耐久性の要件がないため、このステップは高速で、リアルタイムでも実行できます。このレイヤーは、リアルタイムの集約と分析を提供する必要があります。
3. インメモリ データベースの内容を定期的にディスクに保存します (1 時間ごと、1 日の終わりなど)。ここでは、ディスクに保存された大量のデータを操作できるデータベースが使用されます。この保存されたデータに対する操作は、基本的にオフラインまたはバッチ モードと見なされ、瞬時の応答時間は期待されません。
4. (オプション) ログ ファイルの関連部分のみをリレーショナル データベースに抽出し、毎日/毎月のレポートを作成します。たとえば、注文と実行のみがリレーショナル データベースにロードされ、市場相場はスキップされます。

あるいは、このソリューションは、たとえば手順 2、3、4 を組み合わせて、データを保存および分析するための複数のモードを提供するツールを使用することで簡素化できます。

次に、セグメント化された要件でのデータベース作業について説明します。

2. データベースに対する要件

データベースに対する要件は、非技術的要件と技術的要件の 2 つの部分に分けられます。

非技術要件のリスト:

コスト: コスト意識の高いスタートアップとして、私たちは無料または比較的安価な製品を探していました。現在利用可能な FOSS ソリューションが多数あることを考えると、これは無謀な要求ではないと思います。これは、Oracle や MS SQL Server などの標準の有料データベースが除外されることも意味します。

優れたドキュメントとコミュニティ サポート: ライセンスとサポートに料金を支払わない場合は、優れたドキュメントと、質問に答える別の方法が必要です。これは、メーリング リスト、アクティブなオンライン コミュニティ、または StackOverflow である可能性があります。

運用ツール: デプロイメント (可能なマルチノード クラスターを含む) の設定、管理、監視を行うための独自のツールが付属する、比較的成熟した製品を優先します。

技術要件:

高速取り込み: データベースは 1 秒あたり 250K 挿入の速度で取り込める必要があります。この速度が速いほど良いです。挿入をバッチ処理する必要がある場合は問題ありません。複数のスレッドまたは接続を使用する必要がある場合も問題ありません。

高速集約: 私たちのシステムではイベント ソーシング パターンを使用する予定です。このアーキテクチャ パターンでは、システム内のすべての状態の変化を個別の不変のイベントとして記録することが規定されています。これらのイベントからシステムの最新の状態を再現するには、ウィンドウ関数、アップサート、その他の横断的な集計など、高速なメモリ内集計のサポートが必要です。

時系列操作: 時間バケット、移動ウィンドウ集計、時点結合などの操作をサポートします。

表現力豊かなクエリ言語: SQL は問題ありませんが、高度な分析には表現力が足りません。理想的には、データベースはベクトル化された操作を備えた関数型言語を使用してデータ アクセスと処理をサポートします。ユーザー定義関数やサーバー側スクリプトを作成する機能も便利です。

インメモリ テーブル: 作業データ セットを高速に分析します。

ディスク上のテーブル: このカテゴリのほとんどのデータベースでは、列指向ストレージが使用されることが予想されます。

データベースは最適化されたディスク上のデータ レイアウトをサポートしている必要があります。これにより、パフォーマンスが大幅に向上します。

• データは日付ごとに分割され、セグメントに保存されるため、データ管理が容易になります。
• 各パーティションでは、データは複数のノードにまたがってシンボル（トランザクションコード）によって分割され、並列性と冗長性が実現されます。
• 各パーティションとシャードでは、データレコードは（シンボル+交換）によってクラスタ化され、ディスクの連続読み取りを容易にします。
• 最後に、各クラスタリング キー レコード内で、データはタイムスタンプによってソートされ、順次操作が高速化されます。
• さらに、ディスク上でデータを圧縮して、ディスクから読み取られるデータの総量を削減することもできます。
• 階層型データ ストレージ: データベースは階層型ストレージ戦略もサポートし、古いデータを低速のストレージに移動することで、ストレージ コストを削減できます。

評価したデータのサイズの推定値は次のとおりです。

1. 1日あたりのデータ増加: 50～100 GB (非圧縮) 約10億件のレコード
2. 履歴データ（最終）：100 TB（非圧縮）～1Tレコード

3. テストはどのように実施しますか?

すべてのテストは、単一またはデュアルの AWS 専用インスタンス (m5n-2xlarge) で実施されました。これらのインスタンスは Amazon Linux 2 AMI を実行し、8 個の vCPU、32 GB の RAM、100～200 GB の SSD ボリュームを備えています。

テストしたデータベースの中には、特にメモリ メトリックの観点から、これらのインスタンスがそれほど大きくないものがあることがわかります。しかし、私たちがこの選択をしたのは理由があります。第一に、これらのリソースは私たちが行いたいテストには十分であると信じていたこと、第二に、リソースが不足した場合にこれらのツールがどのように劣化したり機能しなくなったりするかを理解したかったからです。

私たちは、時間の制約内で各ツールが最適なパフォーマンスを発揮するように構成するために最善を尽くしましたが、推奨される構成、ハードウェア、またはノード数を常に使用できるとは限りません。また、ドキュメントに従って、データ レイアウト (シャーディング スキームなど) を可能な限り最適な方法で設定するように努めました。

実際に実施したテストは次のとおりです。

• NYSE TAQ の 1 日分のデータを読み込みます (ファイルは 20180730 です)。これにより、3,500 万件の取引が 1 つのテーブルにロードされ、7 億 1,900 万件の相場が別のテーブルにロードされます。このデータベースを相場データ分析に使用するつもりはありませんが、良いサンプルデータセットになることは間違いありません。
• 各取引について、取引が行われている取引所の現在の相場を調べます。単一のビジーシンボル (SPY など) に対するクエリは 1 分未満で完了すると予想され、すべてのシンボルに対するクエリは 30 分以内に完了すると予想されます。これは、複雑な結合を表現するクエリ言語の能力と、妥当な時間内に結合を実行するデータベースの能力をテストするものです。
• 各シンボルについて、取引日の各分ごとに取引数、平均サイズ、取引量加重平均価格が計算されます。トランザクション テーブル全体に 10 秒以上かからないようにしたいと考えています。
• OHLC バーは、取引日の毎分、各シンボルごとに計算されます。
• 取引日中の各シンボルの時間加重平均スプレッドを計算します。これは、次の 2 つの理由で興味深いテストです。1) 引用の継続時間を決定するには、LEAD や next などのウィンドウ関数を使用する必要があります。2) すべての引用を処理する必要があるため、これは生のスキャン速度のテストです。

4. 代替案

明確に申し上げますと、当社は kdb+ に関して豊富な経験を有しており、応答時間に対する当社の期待の多くはその経験に基づいています。生のシングルコア速度に関して言えば、kdb+ よりも高速なツールは見つかりませんでした。しかし、価格、学習曲線の急峻さ、運用作業の不足のため、kdb+ は候補リストに含めませんでした。

フラットファイル

データベースは最も一般的なデータ ストアですが、フラット ファイルを直接操作すると、データの保存に最大限の柔軟性が得られるため、競争上の重要な優位性が得られます。現在、Python (Pandas with Jupyter)、Apache Spark、Amazon Redshift Spectrum、さらには clickhouse-local など、ローカル ディスクまたは S3 バケットに保存されているフラット ファイルを効率的に操作できるツールがいくつかあります。

私たちは、Apache Spark を使用して AWS で EMR (Elastic Map Reduce) クラスターを試してみましたが、セットアップは比較的簡単でしたが、ファイルや JDBC ソースからデータをロードする方法や、Spark Datasets と PySpark DataFrames を使用する方法を理解するのに時間がかかりました。適切なスケーリング機能を備えたバッチ分析には使用できるが、プライマリ データベースとしては使用できないという結論に達しました。ただし、Hadoop と Spark に関する私たちの理解は限られているため、結論に影響する可能性があります。

それでも、これは適切なツールと計画されたジョブを使用してファイルとディレクトリを適切な方法で整理する、適切に設計されたシステムであり、適切なリソースを割り当てることができる上級ユーザーにとっては実行可能なオプションになる可能性があると考えています。しかし、私たちにとっては、それはあまりにも壊れやすく、整理されていないかもしれないと考え、他の洗練された機能が必要だと考えました。

マイグレーション

私たちは、主に従来の RDBMS が私たちにとって本当に適切な答えではないことを確認するために、MySQL を出発点としてのみ検討しました。 MySQL は時系列データベースではなく、列指向でもなく、私たちが求めていた高度な分析機能やパフォーマンス メトリックをサポートしていません。

利点は、無料であり、巨大なコミュニティがあることです。支持者は、やり方さえわかれば何でもできると主張するでしょう。私たちのテストでは、MySQL (InnoDB エンジン) は接続プールでの 250K/秒の高速一括挿入に対応できず、テーブルが数百万のレコードに拡大するにつれて挿入速度が低下しました。ディスク上のデータ サイズは非常に大きいようで、数百万件のレコードをクエリするときの応答時間は数秒です。たとえインデックスを追加できたとしても、何百万ものレコードを含むテーブルの結合は許容できる時間内に完了しません。

この記事の草稿を校正しているときに、元同僚が MariaDB Column Store を勧めてくれましたが、時間の制約により十分に評価することができませんでした。

PostgreSQL と TimescaleDB

当社の負荷テストでは、挿入率とテーブル サイズの増加に伴う応答時間の低下レベルに関して特に PostgreSQL のパフォーマンスが MySQL よりも優れていましたが、実際のニーズには十分ではありません。

TimescaleDB は非常に競争力があるようです。これは、いくつかの通常の PostgreSQL テーブルを使用して、ハイパーテーブルと呼ばれる仮想テーブルを作成する PostgreSQL 拡張機能です。ハイパーテーブル上のすべてのクエリと操作は、適切なブロック テーブルに渡されます。ここでの主な目的は、挿入速度を上げ、大量のデータを処理する際に予測可能なクエリ時間を提供することです。 TimescaleDB は、分析に役立つ時系列関連の関数もいくつか提供します。

宣伝は素晴らしかったが、実際にはうまくいかなかった。初期の挿入速度は良好 (250K/秒) でしたが、3,500 万件のトランザクション レコードを取り込むことができませんでした。原因不明のメモリ不足が発生しました。また、テキスト ファイル ローダーがサーバー上の利用可能なコアをすべて利用できなかったこともわかりました。データを抽出する際に、ディスク圧縮が不足しているためと思われる、サーバーの IOWait 時間が他のデータベースよりもはるかに長いことがわかりました。ディスク領域の使用量も高く、保存されたデータは完全に圧縮されていないテキスト データよりも多くの領域を占有します。これは奇妙です (事前割り当てが原因でしょうか?)。最近のバージョンではネイティブ圧縮がサポートされていることはわかっていますが、新しく取り込まれたデータに対して自動的にそれを使用することはできません。

クリックハウス

ClickHouse は基本的に新しいプレーヤーであり、私たちが夢見ているほぼすべての機能を備えています。

• これは FOSS であり、非常に高速で、水平方向にスケーラブルで、フォールト トレラントであり、ハードウェアによるサポートが充実しており、ディスク上の高度なデータ管理機能 (階層型ストレージを含む) を備えています。
• 開発プロセスは非常に透明性が高く、Github には活発なコミュニティがあり、新機能、改善、修正を加えたアップデートが 2 ～ 3 週間ごとにリリースされます。
• ドキュメントは充実しており、メンテナーからの質問に対する回答を得るのは簡単です。

ClickHouse は主に OLAP エンジンであり、実際のトランザクション サポートはありません。たとえば、扱いにくい非同期 ALTER TABLE コマンド以外では、挿入されたデータの更新と削除はサポートされません。また、ウィンドウ関数もサポートされていません (neighbor や runningAccumulate などの特殊なケースを除く)。これは、主に時系列を対象としているため、少し意外です。

レプリケーションを有効にせずに、単一ノードで ClickHouse をテストしました。 ClickHouse は、100 万/秒を超える速度で 3,500 万件のトランザクションと 7 億 1,900 万件の見積もりを読み込むことができます。特殊なディスク データ構造 (MergeTree) を使用して、できるだけ早くデータを一時ファイルに書き込み、バックグラウンドでそれらをマージすることで、非常に高速な処理を実現します。メモリ不足になることは一度もありませんでした (1 つの例外を除く)。また、圧縮されたソース ファイルを使用するとディスク領域がほぼ半分に削減されるため、非常に効率的です。

残念ながら、いくつかの重要な障害を克服することができませんでした。

• クエリを発行する唯一の方法は、SQL のようなクエリ言語を使用することですが、いくつかの厳しい制限があります。リクエストごとに発行できる選択ステートメントは 1 つだけで、ユーザー定義関数 (UDF) やストアド プロシージャはサポートされていません。
• 彼らの哲学は「私にしかできない」と要約できます。メンテナーは、datetime データ型での 1 秒未満の精度のサポートなど、いくつかの合理的なユーザー要求に対して満足のいく回答を提供しませんでした。公平に言えば、これらの応答のいくつかには正当な理由がありますが、それでもこれらのやり取りを見ると少し不安になります。

全体として、私たちは ClickHouse に大きな可能性があると考えており、その開発を注意深く監視し、システムの重要でない部分に ClickHouse を導入する可能性もあります。

ドルフィンDB

DolphinDB は、この評価を行う前にはまったく私たちの目に留まらなかった、特異で特殊な製品です。これは高速分散時系列分析データベースであり、kdb+ の実行可能な代替手段です。 kdb+ の経験があったので、有料製品であったにもかかわらず、試してみるほど興味をそそられました。

全体的な印象は良好です。 ClickHouse よりも高速で、おそらく kdb+ よりも高速です。マルチノード クラスターのネイティブ サポート、機能豊富な関数型プログラミング言語、最適化されたメモリ内およびディスク上のデータ構造を備えています。わずか 6 秒で 3,500 万件のトランザクションがテーブルにロードされました。すべての SPY 取引とその主要相場の結合をわずか 358 ミリ秒で実行し、すべてのティッカー間で同じ結合を 25 秒で実行しました。一方、kdb+ での単一のクエリには約 5 分かかりました。さらに、データを保存するために使用されるディスク容量は、圧縮されたソース ファイルの半分以下になります。

また、ストリーミングとパブリッシュ/サブスクライブのサポート、リアルタイム集計/ウィンドウエンジン、リアルタイム異常検出エンジン、高度な統計分析機能、機械学習機能など、いくつかの高度な機能（テストは行いませんでした）も備えています。

優れたパフォーマンスにもかかわらず、克服できないマイナス面がいくつかあります。

• コスト: kdb+ よりは安いようですが、私たちにとってはまだ高すぎます。
• 非標準言語の学習が必要ですが (kdb+ よりはるかに簡単です)、幸いなことにドキュメントは完全かつ優れています。
• ビジネスに不可欠なコンポーネントの場合、（私たちにとって）実証されておらず、その限界をまだ判断できないクローズドソース製品にお金を払うことを本当に検討できるでしょうか?躊躇する理由は、数回のクラッシュと不可解なメモリ不足状態に悩まされたことであり、どちらも減点ポイントとなる。

しかし、高得点を獲得した kdb+ よりも高速で、より機能が豊富な製品が見つかったようです。私たちはこの製品に注目しており、これらの機能（ティックデータ調査環境など）を備えた製品に対する強い需要があれば、間違いなく検討します。

メムSQL

それでは、最終的な選択である MemSQL についてお話ししましょう。 MemSQL は有料製品ですが、最大 4 ノードの初期クラスター、128 GB のメモリ、無制限のディスク データの無料商用ライセンスも提供しています。有料製品を検討する前に、これが当初のニーズを満たすのに十分であると感じました。

MemSQL は、HTAP (ハイブリッド トランザクション/分析処理) と呼ばれる新しいカテゴリのデータベースとして定義されています。 MemSQL の主なセールスポイントは、高速な分析機能を提供し、豊富なトランザクション サポートを備え、SQL と完全に互換性があることです。 MySQL とも互換性があるため、すべての MySQL ツールとドライバーを使用できます。大規模なツール エコシステムとの統合は素晴らしいですが、純粋な SQL を使用して特定の高度な分析を表現することが難しいため、いくつかの障害があります。 UDF とストアド プロシージャの形式で手続き型言語を完全にサポートしているため、この特定の欠点は受け入れました [注: 手続き型メソッドは、通常のベクトル化された操作よりも少なくとも 1 桁遅くなります]。

MemSQL は、インメモリ行ストア テーブルと、シャーディング、ソート、圧縮機能を備えたディスク上の列ストア テーブルの両方をサポートしています (最近、ハイブリッド シングル ストア形式もリリースされました)。テスト インスタンスのメモリが 32 GB しかないことを考慮して、列ストアのみを使用してテストしました。MemSQL は、展開、管理、監視、クラスターのセットアップ、さらにはデータの読み込みやクエリの点でも、最も使いやすいツールの 1 つです。

毎秒 500,000 件を超えるレコードの速度で取引と見積りを読み込むことができます。サーバー上のロードプロセスでは、複数のコアを使用して抽出を並列化できることに気付きました。ロードされたデータは、圧縮されたソース ファイルとほぼ同じスペースを占めます。また、JDBC インターフェースを使用すると、外部ツールが MemSQL から 1Gbps を超える速度でデータを読み取ることができることも確認されました。これは特に印象的でした。

ほとんどの単一テーブル クエリと複数のテーブルを結合するクエリの全体的なパフォーマンスは良好です。これは、as-of 結合ではうまく機能しませんが、結局のところ、その使用ケース向けにはまったく設計されていません。私たちは SQL で as-of 結合を最適に表現しようと多くの時間を費やし、最終的にはエンジンに (比較的) 高速な MergeJoin を実行させました。将来的には、ベンダーがカスタム操作として as-of-join の専門的なサポートを追加することが予想されます。

全体として、MemSQL は私たちの調査で発見できた最もバランスの取れたソリューションです。成熟しており、使いやすく、無料（今のところ）、高速で、効率的で、必要なすべての標準ツールと相互運用可能です。

5. 結果統計

上記のテストでは、詳細なデータ統計と比較を行いました。

テスト結果を詳しく確認したい場合は、こちらをご覧ください:

https://github.com/prerak-proof/dbtests

6. 結論

評価できるツールは他にもたくさんあり、特にさまざまな NoSQL データベースがあることはわかっています。全体的な感想としては、これらのオプションはデータ サイズも処理できるかもしれませんが、パフォーマンスの期待には応えられない可能性が高いというものでした。少なくとも現時点では、MemSQL が当社のニーズと制約を満たす最も適切な製品であると考えています。