時系列DBをゼロから作ってみる

• Goで書かれているが、ほぼ言語非依存

• 時系列データはタイムスタンプ付きの複数の値のコレクション。各項目はデータポイント

→ 量が多い。多くてこそ意味を持つ。秒間100万回キャプチャされるケースも多い

→ Append-only、時間順ソート、最近のデータ優先

→ 特定の時間単位でのバルクリード

→ High Cardinality（集合の単位が非常に大きい）

→ ほとんどは最近のデータを読み取って利用する

• 時系列データは主に書き込みが多いことを踏まえ、TStorage DBエンジンライブラリをGo言語で開発

• データモデル

→ 線形データモデル

→ データポイントを時間単位でパーティショニング

→ 各パーティションは、その時間内のすべてのデータを持つ別個の独立したDBのように動作

→ ヘッドとその次のパーティションだけをヒープに保存するメモリパーティションへ変更可能

→ データ損失を防ぐため、書き込み前にWAL(Write Ahead Log)へ記録

→ それ以前のパーティションデータはディスクに単一ファイルで保存。ディスクパーティションは読み取り専用

• メモリパーティション

→ データポイントのリストをヒープ上の配列として表現（GoのSliceに似ている）

→ レイテンシーや同期のため Out-of-order が頻繁に発生。同じパーティション内ならバッファリングで保存時に再ソートし、別のパーティションならヘッドではない以前のパーティションの後ろに追加することで対応可能

→ WAL に実際に記録されるものと同じデータを保存し、障害時にも復旧できるようにする

• ディスクパーティション

→ パーティションごとに1つのディレクトリへメタデータと圧縮済みの実データを保存（Prometheus V3 Storage の縮小版）

→ Memory-Mapped データ形式（カーネルで mmap によりキャッシュ可能）

→ メタデータはJSON形式でインデックスを構成

• タイムスタンプと値のタプルで表現されるデータのエンコーディングには、FacebookのGorilla論文で提案された方式を使用

→ タイムスタンプと値を異なるメソッドでエンコード

→ timestamp は unsigned 64-bit integer 値として Delta-of-delta エンコーディングを利用

→ Deltaエンコーディング：前の値と現在の値の差だけを記録する方式

→ Delta-of-Deltaエンコーディング：通常は一定時間ごとに発生するため、デルタのデルタだけを記録

→ 可変長でエンコードされるため、Delta-of-Delta が最も小さい容量を使う

→ values は signed 64-bit floating-point 値として XOR エンコーディングを使用

→ 最初の値はそのまま保存

→ 次の値とXORして0なら前の値と同じなので、0ビット1つだけ保存

→ 0でなければ異なるビット群に基づいて計算（Meaningful Bit）

→ 前後の0を計算し、0の個数が同じなら0と意味のあるビットだけを保存し、異なるなら先頭のゼロ数、Meaningful Bit の個数、そのビット列自体を保存