Writing a Time Series Database from Scratch-Part4

０から時系列データベースを書く — Part4

時系列データベースについての記事をご紹介したいと思います。長い記事ですので６回に分けて掲載していきます。今回は第4回です。mmap、圧縮についての内容です。

mmap

何百万もの小さなファイルから一握りの大きなファイルに移動することで、わずかなオーバーヘッドですべてのファイルを開いたままにすることができます。これにより、ファイルコンテンツによって仮想メモリ領域を透過的にバックアップすることを可能にするシステムコール、mmap (2）が使用できるようになります。分かりやすく言えば、スワップスペースのように考えることができます。データはすべてディスク上に既に存在し、メモリからデータをスワップするときに書き込みは行われません。

つまり、データベースのすべての内容を、物理的なRAMを占有することなく、メモリ内にあるかのように扱うことができるということです。データベースファイルの特定のバイト範囲にアクセスした場合にのみ、オペレーティングシステムはディスクからページをかなりゆっくりの速度でロードします。これにより、オペレーティングシステムに、保存されたデータに関連するすべてのメモリに関する役目を引き受けてもらうことになります。一般的に、マシン全体とそのすべてのプロセスを完全に把握しているため、このような決定を下すことがより適しています。クエリされたデータはかなり積極的にメモリにキャッシュされますが、メモリの負荷がかかるとページは削除されます。マシンに未使用のメモリがある場合、Prometheusはデータベース全体をうまくキャッシュしますが、別のアプリケーションがそれを必要とするとすぐにそれを返します。

したがって、クエリは、RAMに収まるよりも多くの保存データをクエリすることによって、より長く簡単にプロセスをOOMすることができます。メモリキャッシュサイズは完全に適応され、クエリが実際にそれを必要としたときにのみデータがロードされます。

私の理解するところでは、これは今日の多くのデータベースの動作方法であり、ディスクフォーマットが対応するならそれを実行する理想的な方法です。ただ、プロセスでＯＳに勝つ自信がない限り、ですが。確かに少しの働きで多くのことができるようになります。

Compaction

ストレージは定期的に新しいブロックを「カット」して、現在完了している前のブロックをディスクに書き込む必要があります。ブロックが正常に保存された後にのみ、メモリ内ブロックの復元に使用されるログ先行書き込みファイルがきちんと削除されます。

メモリに大量のデータが蓄積されないように、各ブロックを合理的に短く（通常のセットアップでは約2時間）するのは、とても興味深いことです。複数のブロックをクエリするときは、それらの結果を全体的な結果にマージする必要があります。このマージには明らかにコストがかかり、1週間にわたるクエリで80以上の部分的な結果をマージする必要はありません。

両方を達成するために、 圧縮を用います。圧縮とは、1つ以上のデータブロックを取得し、それらを潜在的により大きなブロックに書き込むプロセスのことです。また、削除されたデータをドロップしたり、クエリのパフォーマンスを向上させるためにサンプルチャンクを再構築するなど、既存のデータを途中で変更することもできます。

この例では、シーケンシャルブロック [1, 2, 3, 4]があります。ブロック1、2、3はまとめて圧縮でき、新しいレイアウトは [1, 4]です。あるいは、それらを2つ1 組にして [1, 3].にまとめます。すべての時系列データはまだ存在しますが、現在は全体的により数の少ないブロックにあります。これにより、部分クエリ結果のマージが少なくて済むため、クエリ時のマージコストが大幅に削減されます。

Retention

私たちは、古いデータを削除することはV2ストレージでは遅いプロセスであり、CPU、メモリ、そしてディスクにも同様に大きな負担をかけることを見ました。では、どのようにブロックベースのデザインに古いデータをドロップすることができるのでしょうか。簡単に言うと、フィギュアしたリテンションウィンドウにデータがないブロックのディレクトリを削除するだけです。以下の例では、ブロック1は安全に削除できますが、ブロック2は境界の後ろに完全に収まるまできちんと確認する必要があります。

より古いデータを取得すると、以前に圧縮されたブロックを圧縮し続けるにつれてブロックが大きくなる可能性があります。ブロック全体がデータベース全体に広がらないように上限を設定する必要があるため、設計の本来のメリットが損なわれます。

好都合なことに、これによって保持ウィンドウの一部内側および一部外側にあるブロック、すなわち上記の例ではブロック２も制限されます。最大ブロックサイズを総保存ウィンドウの10％に設定すると、ブロック2を維持するためのトータルのオーバーヘッドも10％に制限されます。

要約すると、保存期間の削除は非常に高価なものから、実質的に無料のものまであるということになります。

この段階にきて、もしあなたがデータベースについて少し知っているのであれば、一つ聞きたいことがあるのではないでしょうか。「これどれも新しいのですか？」- 新しくはないです。でも、こちらのほうがいいと思います。

データをメモリー内でバッチ処理し、先行書き込みログに記録し、定期的にディスクにフラッシュするというパターンは、今日ではどこにでもあります。

これまで見てきた利点は、データのドメインの詳細にかかわらず、ほぼ普遍的に当てはまります。このアプローチに続く有名なオープンソースの例は、 LevelDB 、Cassandra、 InfluxDB 、HBaseです。重要なのは、土台から作り直したり、実証済みの方法を研究したり、そして正しい方法でそれらを適用することをなど避けることです。

The Index

ストレージの改善を調査する最初の動機は、 シリーズチャーンが起こした問題でした。ブロックベースのレイアウトは、クエリを処理するために考慮する必要があるシリーズの総数を減らします。そのため、索引の検索が複雑度O（n ^ 2）であると仮定すると、n の量を適正な量まで減らし、今や O（n ^ 2）の複雑さが改善されています。―あ、ちょっと待って、だめだ。

「アルゴリズム101」への素早いフラッシュバックは、理論上、これが私たちに何の意味もなかったことを思い出させます。以前に物事が悪かったとしたら、それは今と同じくらい悪いです。無意味な理論も存在するのです。

実際には、私たちのクエリのほとんどにかなり速く対応できるでしょう。それでも、全範囲にわたるクエリは、ほんの一握りのシリーズを見つける必要がある場合でも、遅いままです。この作業が開始された方法の前に思いついた、この私のオリジナルのアイデアは、まさにこの問題に対する解決策だったのです。つまり、我々には転地インデックスが必要なのです。転地インデックスはそのコンテンツのサブセットに基づいてデータ項目を高速に検索します。簡単に言うと、ラベルが app=”nginx” であるすべてのシリーズを調べてそのラベルが含まれているかどうかを調べることができます。

そのために、各シリーズには、それを一定時間内に検索することができる唯一のID、すなわちO（1）が割り当てられます。この場合、IDは普通のインデックスです。

例： ID 10、29、9の系列にラベル app=”nginx” が含まれている場合、ラベル” nginx “の転置インデックスは簡単なリスト [10, 29, 9],であり、これを使用してラベルを含むすべてのシリーズすばやく検索できます。さらに200億のシリーズがあったとしても、この検索の速度には影響しません。

要するに、n がシリーズの総数だとすれば、m は所定のクエリのためのresult sizeです。インデックスを使ったクエリの複雑さは現在 O(m)です。検索対象のデータ本体（n ）ではなく、検索するデータ量（m ）に応じてスケーリングをクエリは、mが一般的により小さいことから、とても優れた性質だと言えます。

簡潔にするために、転地インデックスリスト自体を一定時間で取得できるとします。

実際、これはほぼ正確なV2が持つ転地インデックスの種類であり、何百万ものシリーズにわたってパフォーマンスの高いクエリを処理するための最低限の要件です。最悪の場合、ラベルがすべての系列に存在し、このようにmが再びO(n)の中にあることに気付いた熱心な方もいるでしょう。これは事前に予想されたものであって、まったく問題ありません。すべてのデータをクエリすると、当然時間がかかります。より複雑なクエリに関わるようになると、問題が起こりやすくなります。

Orangesys.ioでは、kuberneteの運用、DevOps、監視のお手伝いをさせていただいています。ぜひ私たちにおまかせください。