Akumuli-時系列データベース

こんにちは この記事では、時系列を収集および保存するための専用データベースであるAkumuliプロジェクトについてお話したいと思います。 私はこのプロジェクトに4年以上取り組んでおり、高い安定性と信頼性を達成し、この分野で何か新しいものを発明したかもしれません。

時系列とは、可能な限り単純化するために、時間順に並べられた一連の測定値です。これは、グラフに描くことができるものです。 時系列は、金融からDNA分析まで、多くのアプリケーションで自然に発生します。 時系列データベースの最も一般的な使用方法は、インフラストラクチャの監視にあります。 最も深刻な負荷がよく見られます。

「TSDBは必要ありません。すでにXがあります」

Xは、SQLデータベースからフラットファイルまで何でもかまいません。 実際、これはすべて、時系列を格納するために実際に使用できますが、1つの警告があります-データがほとんどありません。 SQLデータベースに10,000個の挿入を行うと、しばらくの間すべてが正常になります。その後、テーブルのサイズが大きくなり、挿入操作の実行時間が長くなります。

挿入する前にグループ化を開始しますが、これは役立ちますが、新しい問題が発生しました-どこかにデータを蓄積する必要があるため、データベースに書き込む時間がなかったすべてを失う可能性があります。 次のステップは、1つの行に1つのディメンション（id +タイムスタンプ+値）ではなく、複数の（id +タイムスタンプ+値+ 10秒の値+ 20秒の値+ ...）を格納するなど、いくつかのトリッキーなスキームの使用を試みることです。 これにより、書き込みスループットは向上しますが、新しい問題が発生します。 圧縮がそれほど強くないため、場所はすぐに終わります。異なるステップで時系列を保存する必要があり、可変ステップで時系列を保存する必要があり、集計（間隔ごとの最大値）をカウントする必要があり、1時間のステップで10秒のステップで時系列を作成する必要があります。

これらの問題はすべて克服可能で、SQLサーバー、フラットファイル、 Cassandra、またはPandaの上にTSDBを書き込むだけです。 実際、多くの人がすでにこの方法を採用しています。これは、他のDBの上で動作する既存のTSDBの数から推測できます。 Akumuiは、オリジナルのアルゴリズムに基づいた特殊なストレージを使用するという点でそれらと異なります。

設計

TSDBが解決する問題は、データが1つの順序で書き込まれ、別の順序で読み取られるという事実に帰着させることができます。 100万の時系列があり、それぞれに1秒に1回、現在のタイムスタンプで1つの値を書き込む必要があるとします。 それらをすばやく記録するには、到着した順に記録する必要があります。 残念ながら、1つの時系列から1時間のデータを読み取りたい場合、3600 * 1 000 000ポイントすべてを読み取り、ほとんどのデータをフィルタリングして3600だけを残す必要があります。これは読み取り増幅と呼ばれ、これは良くありません。

残念ながら、多くのTSDBがこれについてだけやっています。 唯一の違いは、データa）が圧縮されるb）小さなブロックに分割されることです。各ブロックは、すべてのコンテンツを解析せずに必要なデータにすぐにジャンプできる列形式（いわゆるPAX）を持っています。

私は別の道を選択することにしました（最初にPAXを試しました）が、各列に別々の時系列が保存される円柱状のストレージを実装しました。 これにより、クエリに必要なデータのみを読み取ることができます。 最新のSSDとNVMeでは、データベースからアクセスされるデータを厳密にシーケンシャルにする必要はありませんが、スループットが制限されているため、データベースがディスクシークを保存せずに本当に必要なもののみを読み取ることが非常に重要です。 以前は、逆の方法で、帯域幅をディスクシークに変更しました。多くのデータ構造がこの妥協点を中心に構築されています（hello LSMツリー）。 Akumuliはその逆です。

圧縮

これはTSDBにとって最も重要な側面です。 圧縮は妥協に強く影響し、そのバランスがデータベースの設計の基礎となります。 Akumuliの場合、私には思えるように、かなり良いアルゴリズムを開発しました。 本質的に2つの異なるアルゴリズムを使用して、タイムスタンプと値を圧縮します。 詳細については詳しく説明しません。 ホワイトペーパーもありますが、良い紹介をしようと思います。

ポイント（時間+値）は16のグループにまとめられ、一緒に圧縮されます。 これにより、固定長の配列を処理する単純なサイクルの形式でアルゴリズムを記述でき、コンパイラーは最適化とベクトル化を適切に行うことができます。 大部分の場合、分岐予測器が予測できないホットパスには分岐がありません。

タイムスタンプは次のように圧縮されます。最初にデルタデルタエンコーディングが適用され（最初のデルタがカウントされ、次に各デルタから最小要素が減算されます）、VByteエンコーディングを使用してすべて圧縮されます。 VByteエンコードは、プロトコルバッファで使用されるエンコードと似ていますが、ビット単位の操作が必要ないという違いがありますが、動作は高速です。 これは、タイムスタンプがペアに結合され、各ペアのメタデータ（制御バイト）が1バイトに格納されるという事実により実現されます。

値を圧縮するには、差分有限コンテキストメソッド（DFCM）予測子を使用して次の値を予測しようとする予測アルゴリズムが使用されます。

さらに、XOR-itアルゴリズムは、それら自体の予測値と実際の値であり、結果として、末尾または先頭に多数のゼロが含まれるビット列になります。 このビット文字列は次のようにエンコードされます。

• 行の先頭と末尾のゼロの数を考慮します。行の先頭にさらにゼロがある場合は、特別なフラグを設定します。
• このビット文字列を書き込むために必要なバイト数（N）をカウントします（フラグを考慮して）。
• フラグが設定されている場合、ビット文字列を左に64-N * 8ビットだけシフトします。
• ビット文字列の最初のNバイトを出力バッファーに書き込みます。

その結果、Nバイトのデータがありますが、これに加えて、メタデータを保存する必要があります-値Nとフラグは4ビットです。 スペースを節約するために、値をペアで組み合わせて、最初に両方の値のメタデータ（制御バイト）でバイトを書き込み、次に値自体を書き込みます。

さらに、別のトリックが使用されます。 「便利な」データを扱う場合、このアルゴリズムは100％の精度で次の値を予測できます。 監視では、これは非常に一般的であり、値は時間とともに変化しないか、一定の割合で増加する場合があります。 この場合、XORの後、常にゼロ値を取得します。 それらのそれぞれを完全な半バイトでエンコードしないために、アルゴリズムには特別なケースがあります-16個すべての値を予測できる場合、特別な制御バイトのみを書き込みます。 この場合、値に費やしているのは少しです。 測定のステップが固定されている場合、タイムスタンプにも同様のショートカットが実装されます。

このアルゴリズムには分岐がなく、バイト境界で機能します。 私の測定では、圧縮率は約1GB / sです。

ストレージエンジン

各時系列は、個別のデータ構造としてディスクに表示されます。 数値B +ツリーと呼びます。なぜなら 数値データを保存するためのものですが、実際には、セグメントがB +ツリーであるLSMツリーです。 通常（必ずしもではありませんが）セグメント（SSTable）は、ソートされた配列として実装されます。

このLSMツリーのMemTableロールは、B +ツリーの単一の葉を実行します。 データがいっぱいになると、2番目のレベルに移動し、2つのレベルで構成される別のB +ツリーを単純に結合します。 このツリーがいっぱいになると、3番目のレベルに移動し、3つのレベルなどで構成されるB +ツリーに参加します。 このプロセスの詳細を示すホワイトペーパーがあります。

このデータ構造により、次のことが可能になります。

• ディスク全体からセグメントを読み取らずにセグメントをマージします（通常のLSMツリーのように）。 Akumuliは、ディスクからデータを読み取って書き込むことはありません。 このおかげで、読者は読むためにドライブの帯域幅を使い果たすことによって書き込みプロセスを遅くすることはできません。
• 1つのファイルに多くの独立したツリーがあります。 異なるツリーのノードは、ディスク上に互いに点在しているだけです。 このため、ディスクへの書き込みは引き続きシーケンシャルです。 1つのシリーズを読み取ると、ランダムな順序でディスクからデータが選択されますが、最新のSSDではこれは問題ではありません。
• SSDおよびNVMeドライブの最適化。 すべての読み取りおよび書き込み操作は、ブロック境界に揃えられます（これにより、書き込みの増幅が減少します）。 書き込みと読み取りの両方を並行して実行できます（これなしでは、最新のSSDを飽和させることは困難です）。 データベースは、バイトアドレス可能なデバイス（Intel Optane SSDなど）に対応しています。 データをメモリにマップし、さらに細かく読み書きできます。
• WALを使用せずに災害復旧を実行します。 これは複雑な問題であり、その詳細は記事に記載されています。 つまり、AkumuliはWALを使用せず、ツリーノード間の追加リンクを使用して障害から回復します。
• マルチバージョン同時実行制御により、クラスとしての同期エラーがなくなります。 また、書き込みと読み取りは並行して実行でき、リーダー/ライターは互いに依存していません。

このアプローチには欠点もあります。

• タイムスタンプが増加する順にデータを記録する必要があります。
• 落下すると、最後に記録されたデータ、たとえば最後の5分間の監視データが失われる可能性があります。

遅かれ早かれ、これらの問題は解決されますが、解決されるまで考慮に入れる必要があります。

リクエスト処理

Pandasデータフレームに似た機能を取得したかったのです。 まず、データを任意の順序で読み取り、好きなようにグループ化できるようにするために、タイムスタンプの昇順またはその逆で、まず1つのシリーズのデータ​​、次に次のデータ（クエリは多くの時系列を返すことができます）、または最初に1つのラベルを持つすべてのシリーズのデータ時間、その後、次のタイムスタンプなどを使用して、同じ順序ですべてのシリーズのデータ 私の経験では、できることが必要であることが示されています。 要求されたデータのサイズはクライアントのRAMの量を超える可能性があり、単にローカルで並べ替えることはできませんが、データが正しい順序で到着した場合は、それらを部分的に処理できます。

さらに、複数のシリーズを1つにマージし、ポイントを単純に結合するか、複数のタイムシリーズをタイムスタンプで結合し、シリーズデータ（最小、最大、平均など）を集計し、ステップで集計（リサンプル）し、あらゆる種類の関数を計算できるようにしたかった（レート、absなど）。

クエリプロセッサは、現在の形式では階層構造になっています。 下位レベルでは、演算子が機能します。演算子は常に、1つの時系列に対応し、1つのツリーに格納されている1つの列のデータを処理します。 演算子は一種の反復子です。 これらはストレージレベルで実装され、その機能を使用できます。 イテレーターとは異なり、データベースオペレーターはデータの読み取りだけでなく、集計とフィルター処理もでき、これらの操作は圧縮データに対して実行できます（常にではありません）。

オペレータは、ディスクから読み込むことなく、ツリーの一部をスキップ（プルーニング）できます。 たとえば、クエリがダウンサンプル変換なしでデータを読み取る場合、スキャンステートメントが使用され、そのままデータが返されますが、クエリが任意のステップでグループ集約を実行する場合、ディスクからすべてを読み取らずにダウンサンプリングを実行できる別の演算子が使用されます。

次のステップは、クエリ結果の具体化です（Akumuliは初期の具体化のみを実行します）。 オペレーターが返すデータから、タプルが形成され、計画の基本操作（結合など）がマテリアライズされたデータに対して既に実行されます。 すべての種類の機能がここで実行されます（たとえば、速度）。

すべての処理は怠zyな方法で行われます。 最初に、要求ハンドラーがオペレーターのパイプラインを形成し、次にデータがそれを介して実行されます。 データの読み取りと処理の速度は、クライアントがデータを読み取る速度に依存します。 クエリ結果の一部を読み取って停止すると、サーバーでのクエリの実行が停止します。 実際には、これはクライアントアプリケーションがストリーミングモードでデータを処理できることを意味し、このデータをクライアントまたはサーバーのRAMに配置する必要はありません。

テスト

このプロジェクトで最も興味深いのはテストです。 テストはCIサーバーで自動的に行われます（私はTravis-CIを使用しています）。 プロジェクトでは次のタイプのテストが使用されます。

• 最初のステップは単体テストです。 単体テストは約1〜2分で動作し、ディスクに触れないため、非常に迅速に動作します。 回帰を見つけることはめったにありませんが、回帰を行うと、問題の場所に関する最も多くの情報を提供します。
• 統合テスト。 このアプリケーションは、ストレージシステムを実装するライブラリであるlibakumuliを使用します。 少量のデータを使用した簡単なテストが多数含まれています。 テストのタスクは、契約が破られていないことを確認することです。 ライブラリAPI関数の動作は変更されていません。
• 機能テスト。 これらのテスト（20以上あります）はpythonで記述されており、最高レベルで動作します。 各テストは、新しいデータベースを作成し、データベースサーバーを起動して何かを実行する個別のスクリプトです。 たとえば、単にデータを記録し、すべてが記録されたことを確認するテスト、すべての可能なクエリオプションを確認するテスト、クラッシュリカバリを確認するためにkill -9を介してデータベースサーバーを強制終了するテストなどがあります。 これらは、ほとんどの問題を見つける最も重要なテストです。 通常、ここに回帰を追加します-すでに修正された問題をチェックするテスト。
• 往復テスト。 これは、一見単純なテストであり、完全にbashで記述されています。 S2からすぐに書き込める形式でS2から数百MBのテストデータをダウンロードし、データベースを作成し、データベースサーバーを起動して、テストデータを書き込みます。次に、テストデータとまったく同じ形式で記録されたすべてのデータを発行する結合要求を生成します。 すべてがうまくいった場合、両方のファイルは同一であり、テストは成功しました。 これは、2つの入力データ形式（RESPおよびOpenTSDB）に対して2回行われます。
• ファズテスト。 これらのテストは手動で実行されます。 タイムスタンプや時系列名を解析するコードなど、入力を解析する圧縮アルゴリズムとコードをチェックします。 プルリクエストがこれらのコードセクションの1つに影響する場合、AWSで特別に作成されたEC2インスタンスで数日間、適切なテストでAFLを実行します。 目を見張るような体験！

• ランダム化されたテスト。 最も奇妙な種類のテスト。 場合によっては、非常に低い確率で何かを行う特別なコードを追加します。 たとえば、ディスクからデータを読み取ろうとするとエラーが発生し、実際に発生するまで待機しません。 最近のものから、シャドウページを使用して過去のデータの変更に取り組み、過去への書き込みが何も壊さないことを確認するために、過去への書き込みの手順が何も変更せずに行うのと同じことを行うコードを追加しました。 このコードは、低い確率で作業するプロセスで呼び出され、時系列のランダムなポイントに適用されました。 これらの変更を含むデータベースを収集した後、AWSインスタンスで何かが落ちるまで何時間も統合テストを行い、エラーを修正して、エラーが表示されなくなるまでやり直しました。 当然、これはCIサーバーでは実行されません。さらに、誤ってマスターにならないように、このようなコードは常に削除します。

ベンチマーク

通常、Akumuliは各コアで1秒あたり約50万の書き込み操作を実行できます。 すなわち デュアルコアマシンでは約1M、4x-2Mなどになります。 この記事では、32倍の核機械でのテストプロセスについて説明しました。これにより、1秒あたり約1600万の書き込み操作が発生しました。 このような負荷を作成するには、4台のマシンが必要でした（m3.xlargeインスタンス）。 テストデータは事前​​に準備されました（実際のコレクターがRESP形式で16GBを圧縮形式で生成するものに可能な限り近いため）。 オンザフライで生成するには、さらに多くのコンピューティングリソースが必要になります。 私はすべてのマシンで並列SSHを同時に実行し、3分以内にすべてが記録されました。 テスト中、データベースは64MB / sの速度でディスクに書き込みました。

ここで読書速度もテストしました 。 そこにあるデータボリュームは非常に小さく、すべてがメモリに収まりますが、テストを開始する前に、データベースサーバーを再起動し、ディスクキャッシュをクリアしました。 大量のデータがあり、データベースへのアクティブな書き込みがある場合、Akumuliは非常にうまく動作するはずです。

今後の計画

私は現在、過去に書く問題の解決に取り組んでいます。 これは、データ複製とHAを実装できるようにするために必要です。 シャドウページに基づいた実装が既に1つありますが、現在はWALを使用した代替に取り組んでいます。 これらの2つのオプションのいずれかがマスターになると思いますが、すぐには発生しません。 深刻なテストとハードウェアが必要であり、ハードウェアについてはウルトラブックしか持っていないので、AWS ES2こんにちは。

開発の別の領域は、あらゆる種類の統合とツールです。 OpenTSDBプロトコルのサポートを実装しました。現在、Akumuliはcollectdなどの多くのコレクターで使用できます。 Grafana用のプラグインもあります。これは、プラグインストアに追加されるのを待っています。 Redashも見ていますが、これが必要かどうかはまだわかりません。

Akumuliは、Apache 2.0ライセンスで公開されているオープンソースプロジェクトです。 ここでソースコードを見つけることができます。 ここでは、最新の安定ビルドでdockerコンテナーを使用できます。これは、graphansのプラグインです。 このプロジェクトは、プルリクエストまたはバグレポートを送信することで支援できます。