Writing a Time Series Database from Scratch-Part5
０から時系列データベースを書く — Part5
時系列データベースについての記事をご紹介したいと思います。長い記事ですので６回に分けて掲載していきます。今回は第5回です。ラベルやベンチマークについての内容です。
Combining Labels
何百万ものシリーズに関連するラベルは一般的なものです。それぞれ数千の系列を伴った何百ものインスタンスを持ち、水平方向にスケーリングする「foo」マイクロサービスを想定してください。各シリーズは、ラベルl app=”foo”.を持ちます。もちろん、通常はすべての系列をクエリするわけではありませんが、それ以上のラベルでクエリを制限します。たとえば、サービスインスタンスが受け取ったリクエストの数や__name__=”requests_total” AND app=”foo”のクエリの数を知りたいと思います。
両方のラベルセレクターを満たすすべてのシリーズを見つけるために、それぞれの転地インデックスリストを取得してそれらを交差させます。結果として得られるセットは、通常、各インプットリストよりも個別に桁違いに小さくなります。各インプットリストの最悪の場合のサイズはO（n）なので、つまり両方のリストにわたる入れ子になったイテレーションの無理やり出した解決策は、O（n ^ 2）のランタイムがあります。同じコストが、和集合（(app=”foo” OR app=”bar”） などの他の集合演算にもかかります。クエリにさらにラベルセレクターを追加すると、指数はそれぞれに対してO（n ^ 3）、O（n ^ 4）、O（n ^ 5）、…O（n ^ k ）と増加します。 ）
実行順序を変更することで、効果的な実行時間を最小限に抑えるために多くのコツがあります。より洗練されたものになればなるほど、データの形状やラベル間の関係についての知識がさらに必要になります。これは非常に複雑になりますが、アルゴリズムの最悪の場合の実行時間を減らすことはありません。
これは基本的にV2ストレージでのアプローチであり、幸運にも一見わずかな変更で十分な効果が得られます。転置インデックスのIDがソートされていると仮定した場合はどうなるでしょうか？
最初のクエリのリストの例を次のようにします。
そのインターセクションはかなり小さいものです。各リストの先頭にカーソルを置き、常に小さい番号にカーソルを進めることでそれを見つけることができます。両方の数が同じ場合は、その数を結果に追加して両方のカーソルを進めます。全体的に、我々はこのジグザグパターンで両方のリストをスキャンし、どちらのリストでも先に進むだけなのでトータルコストＯ（２ｎ）＝ Ｏ（ｎ）を持つことになります。
異なる集合演算の3つ以上のリストに対する手順も同様に機能します。そして、k の数の集合演算 は、最悪の場合のルックアップ実行時の指数（O（n ^ k ））ではなく、係数（O（k * n） ）を 変更するだけです。素晴らしい改善ですね。
ここで説明したのは、事実上すべての全文検索エンジンで使用されているcanonical検索インデックスの簡易版です。すべてのシリーズデスクリプターは短い「文書」として扱われ、すべてのラベル（名前+固定値）はその中の「単語」として扱われます。単語の位置や頻度のデータなど、検索エンジンのインデックスでよく見られる多くの追加データは無視することが可能です。
実際には実行時間を改善するためのアプローチに関する無限の研究が存在し、しばしば入力データについての仮定もなされています。当然のことながら、長所と短所を持ち合わせる転地インデックスを圧縮するための技術もたくさんあります。私たちの「文書」は小さく、「単語」はすべてのシリーズにわたって非常に繰り返しが多いので、圧縮はほぼ不適切なものになります。たとえば、約12のラベルを持つ約440万シリーズの実世界データセットには、5,000未満のラベルがあります。私たちの初期のストレージバージョンでは、圧縮せずに基本的なアプローチにこだわり、そして交わることのないIDの広範囲をスキップするために少しだけ簡単な調整を加えました。
IDをソートしておくのは簡単に思えるかもしれませんが、それを維持するのが常に簡単で不変なものであるとは限りません。たとえば、V2ストレージはハッシュを新しいシリーズのIDとして割り当てます。ソートされた転地インデックスを効率的に構築することはできません。
データが削除または更新されたときに、ディスク上のインデックスを変更するのも厄介な作業です。通常、最も簡単な方法は、データベースを クエリ可能 で一貫性のある状態に保ちながら、単純に再計算して書き直すことです。V3ストレージでは、圧縮時の書き換えによってのみ変更されるブロックごとに個別の不変インデックスを持つことでこれを正確に実現しています。完全にメモリに保持されている可変ブロックのインデックスのみを更新する必要があります。
Benchmarking
実世界のデータセットから抽出した約440万個のベンチマークをベースにしたシリーズデスクリプターを伴ったストレージの初期開発を開始し、それらのシリーズにフィードするための合成データポイントを生成しました。このイテレーションでは、独立型ストレージをテストしたばかりで、パフォーマンスのボトルネックをすばやく特定し、同時並行性の高い負荷下でのみ発生するデッドロックを引き起こすために不可欠でした。
概念的な実装が完了した後、ベンチマークは Macbook Proで毎秒2000万データポイントの書き込みスループットを維持することができました- すべてダースのChromeタブとSlackが実行されていた間ずっとです。これは非常に素晴らしいことのように思えましたが、このベンチマークを推進すること（または、そのことに関してそれほどランダムではない環境で実行すること）にこれ以上の意味がないことも分かりました。結局のところ、それは合成であり、したがって良い第一印象をはるかに超える価値はありません。当初の設計目標の約20倍から始めて、これを実際のPrometheusサーバーに組み込んで、より現実的な環境でのみ経験される実用的なオーバーヘッドとフレークをすべて追加するタイミングでした。
Prometheusの再現可能なベンチマーク設定は、実際にはありませんでした。特に、異なるバージョンのA / Bテストを可能にする設定はありませんでした。後になって考えてみると分かることだったのですが、 今、私たちはこれを持っています！
私たちのツールは、ベンチマークシナリオをdeclarativeに定義することを可能にし、それはその後AWS上のKubernetesクラスターにデプロイされます。これは全面的なベンチマークにとって最良の環境ではありませんが、それは確かに64コアと128GBのメモリを搭載した専用のベアメタルサーバーよりも優れた当社のユーザー基盤を反映しています。
2.0の開発ブランチ（V3ストレージ）から2台のPrometheus 1.5.2サーバー（V2ストレージ）と2台のPrometheusサーバーをデプロイします。各PrometheusサーバーはSSDを搭載した専用のマシン上で稼働します。典型的なマイクロサービスメトリックをエクスポーズする水平方向にスケールされたアプリケーションはworker nodeにデプロイされます。さらに、Kubernetesはそれ自体をクラスタ化し、ノードは監視されています。全体の設定は、もう1つのMeta-Prometheusによって監視され、各Prometheusサーバーのヘルスとパフォーマンスを監視します。
シリーズチャーンをシミュレートするために、マイクロサービスを定期的に拡大縮小して古いポッドを削除し、新しいポッドを作成して新しいシリーズをエクスポーズします。クエリロードは、各Prometheusバージョンの1つのサーバに対して実行され、「典型的な」クエリの選択によってシミュレートされます。
全体的なスケーリングとクエリロード、およびサンプリング頻度は、今の本番環境でのPrometheusのデプロイメントを大幅に上回ります。たとえば、15分ごとにマイクロサービスインスタンスの60％をスワップアウトしてシリーズチャーンを生成します。現在のインフラでは、これは1日に1〜5回しか起こらないでしょう。これにより、当社のV3の設計は今後数年間のワークロードを処理できるようになっています。その結果、Prometheus 1.5.2と2.0のパフォーマンスの違いは、より穏やかな環境においてより大きくなります。
合計で、私たちは850のターゲットから毎秒約110,000のサンプルを収集し、一度に50万のシリーズをエクスポーズしています。
このセットアップをしばらく実行したままにした後、数値を見てみましょう。両方の バージョン が安定した状態に達してから、最初の12時間にわたっていくつかのメトリクスを評価します。
PrometheusグラフUIのスクリーンショットでは、Y軸がわずかに省略されていることに注意してください。
Orangesys.ioでは、kuberneteの運用、DevOps、監視のお手伝いをさせていただいています。ぜひ私たちにおまかせください。
