ゼロから作る時系列データベースエンジン

軽量な時系列データベースエンジンをスクラッチで開発する機会があったので、どのように実装したのかを必要知識の解説を交えながらまとめていきます。

実装はGo言語によるものですが、本記事のほとんどは言語非依存な内容となっています。

モチベーション

筆者は時系列データを扱うツールをいくつか開発しています。その中の一つであるAliは負荷テスト用のcliツールで、メトリクスをクライアント側でリアルタイム描画できるのが特徴です。リクエスト毎にレイテンシーなどの計測結果が際限なく書き込まれてくる中、同時に一定のクエリパフォーマンスが求められます。
これは言ってしまえば、簡易クエリ機能付きのpush型モニタリングシステムを単一ホストで実現するようなものです。

以前までの実装ではヒープ上の可変長配列にデータポイントを追加していくだけだったので、当然ながら時間の経過とともにメモリ使用量が増加していく問題を抱えていました↓

Ali's heap usage measured by nakabonne/gosivy

これに対応するために、Goプログラムからライブラリとして利用できるストレージエンジンを探しました。

時系列データの特徴

解決するべき問題を整理するために、まずは時系列データについて理解する必要があります。
時系列データとは、タイムスタンプを持った複数の値の集まりです。通常は、時間の経過とともに変化するデータを観察するために使われます。一つ一つはデータポイントと呼ばれ、多くの場合タイムスタンプと値を持ったタプルで表現されます。この時系列データは、次にあげるような特徴を持っています。

Tremendous amount of data

時系列データはその性質上単一のデータポイントが意味を持つことが少なく、大量のデータが集まることで効力を発揮します。そしてそれが短期間の間に書き込まれることが多く、金融業界等ではデータの取り込み要件が1000000/sを超えることも珍しくありません。

Aliのユースケースだと、ユーザーが指定したリクエストレートがそのまま書き込みパフォーマンス要件になります（基本的にはファイルディスクリプタ数の上限がボトルネックになりますが）。

これに対応するために、とにかく書き込みの最適化に力を注ぐ必要があります。また、消費するディスクスペースをなるべく抑えるために何らかの工夫をする必要があります。

Append-only

一つ一つのデータポイントはイミュータブルで、更新されることは基本的にありません。また、特定のデータポイントを指定して削除することはなく、通常削除処理は古いものに対してバッチで行います。

Ordered by time

タイムスタンプによってソートされた状態で保存されるため、すでに時間によってインデックスされていると捉える事ができます。これをうまく使えば、オーバーヘッド無しでインデックスを構築していくことが可能です。

Accessed in bulk

読み込む時は期間を指定して、タイムスタンプが連続した複数のデータポイントを取得することがほとんどです。ここに着目すれば、読み出し時の局所性を高めることが簡単にできそうです。

Most recent first

多くのユースケースでは、最近のデータポイントを読み出して利用する傾向にあります。これは、キャッシュアルゴリズムの選択に影響を及ぼしそうです。

High cardinality

時系列データは、カーディナリティが高くなる傾向にあります。例えばシステムモニタリングの文脈ではそれが顕著に現れます。クラウドネイティブの時代になり、ホストやネットワークが動的に変わる環境でモニタリングすることが増えてきました。そういった意味で全く同じ種類メトリックというものはほとんどありません。そのためメトリックごとにファイルを作るような設計をしてしまうと、inodeの限界など様々な問題を引き起こします。

既存ソリューション

総じて時系列データというのは書き込みヘビーで、時間範囲内のデータをシーケンシャルに読み出し/書き込みする機会が非常に多いことがわかりました。

key-valueストレージエンジンとしてはGoogleのLevelDBが有名で、Go言語実装もいくつか公開されています。このLevelDBは、末尾へのシーケンシャルな書き込みのみを行うLSM treesをベースに実装されているため、appned-onlyな時系列データとは相性が良いです。また、keyでソートされる点も、タイムスタンプベースな時系列データに向いています。実際初期のPrometheusやInfluxDBのストレージエンジンも、LevelDBをベースとして作られていました。

しかし、いくつか勿体ない点があります。後述しますが、時系列データは単調なデータが続くため、その特徴を利用すればより小さなサイズへと符号化することが可能です。量が膨大である時系列データを扱うからには、これを利用したいところです。
また、データポイントは全て不変で更新処理が不要であるため、全ての書き込みをシーケンシャルに行うことが出来ます。にもかかわらず、SSTableのマージ時などにWrite amplificationが起きてしまうのは少し気になりました。

tstorage

というわけで、tstorageというデータベースエンジンライブラリを自作する運びとなりました。^[1]

https://github.com/nakabonne/tstorage

ローカルディスクを利用した軽量なエンジンで、全ての部分がpure Goで実装されています。

これをどのように実装したのか、作るにあたって必要になった知識の解説も交えながら書いていきます。

データベースエンジン

一般的なDBMSは、クライアントからのリクエストを捌いたり、クラスタリングのためにノード間での通信を制御したりします。また、クエリをパースして実行計画を立て、それに基づいてデータをディスクへ読み出し/書き込みします。データベースエンジンとは、最後の読み出し/書き込みの部分のみを行うコンポーネントを指します。下図におけるStorage Engineの部分です。

(Database Internals, Alex Petrov, 2019, Chapter1, Figure 1-1. Architecure of database management system)

ディスク/メモリ上でのデータ構造を抽象化し、上図におけるExecution EngineにAPIを提供します。その他にも、トランザクションやリカバリーの機能も提供します。

データモデル

前述した時系列データの特徴を踏まえ、tstorageでは以下のような線形的なデータモデルを採用しました。データをタイムスタンプでパーティショニングし、完全に独立した小さなデータベースを複数個作っていく設計となっています。

  │                 │
Read              Write
  │                 │
  │                 V
  │      ┌───────────────────┐ max: 1600010800
  ├─────>   Memory Partition
  │      └───────────────────┘ min: 1600007201
  │
  │      ┌───────────────────┐ max: 1600007200
  ├─────>   Memory Partition
  │      └───────────────────┘ min: 1600003601
  │
  │      ┌───────────────────┐ max: 1600003600
  └─────>   Disk Partition
         └───────────────────┘ min: 1600000000

LSM-treesに少し影響を受けており、PrometheusのV3ストレージもかなり近いモデルを採用しています。

Headとその次のパーティションのみがヒープ上で管理されており、且つ書き込み可能です。これをメモリパーティションと呼んでいます。メモリパーティションではデータロスを防ぐため、書き込む前にWrite Ahead Logの末尾に追記します（そこまでの耐久性が不要であればオフにすることも可能）。

それより古いパーティションはディスク上の単一ファイルへ書き込まれます。これをディスクパーティションと呼び、読み込み専用です。ディスクに書き込まれたファイルはmmap(2)でカーネルを通して透過的にキャッシュされます。これについては後述します。

パーティションには期間を設定することができ、それを過ぎると自動で新たなメモリパーティションがHeadに追加され、古くなったパーティションはディスクへフラッシュされます。

このモデルには様々な利点があります。まず、読み出し時に指定範囲外のパーティションを完全に無視できます。探索範囲を限りなく狭めるというこの考え方は、LevelDBでも使われているBloom filterに影響を受けています。また、最新のデータポイントがヒープにキャッシュされているので、ほとんどの読み出しは高速になります。

そしてtstorageでは、1パーティションを1ファイルに書き込む設計となっているため：

• 1つのファイルにシーケンシャルに書き込むだけなので、Write amplificationが発生することなく全ての書き込みをappend-onlyにすることができる
• ファイル数がカーディナリティの高さ（メトリック種類の数）に依存しない
• 前述のとおり読み出しは期間指定して隣り合ったデータポイントを取得することが多いため、局所性が高まる

続いて、それぞれのパーティションの実装におけるポイントを説明していきます。

メモリパーティション

Data point list

データポイントのリストは、ヒープ上では配列として表現されています（厳密には、Go言語のスライスという基底配列のポインタリストのようなもの）。際限なくデータポイントが書き込まれるリストであるため、一見すると要素の追加をO(1)で行えるLiked-listの方が最適に思えるかもしれません。
しかし、要素がRAM上の隣り合った場所に並ぶ配列は、キャッシュメモリの空間的局所性が効きます。また、時系列データは常にソート済みであるため、二分探索等の古典的な探索アルゴリズムを容易に実装することが出来ます。

Out-of-order data points

現実世界では、ネットワークの遅延やクロック同期の問題が原因でデータポイントが順不同になることは珍しくありません。書き込み時にはこれを考慮し、Partition内のデータポイントを常にソート済みに保っておく必要があります。

しかし注意点があります。配列でデータポイントを管理している以上、書き込む度に排他ロックをかける必要があります。順不同データポイントに対応するためにこのロック時間を伸ばすことにならないよう、上手く取り込む工夫が必要です。

順不同なデータポイントは2つのケースに分けることができます。１つ目は、書き込もうとしたパーティションの範囲内で順不同になっているケース。もう一つは、そもそも書き込もうとしたパーティションの範囲外のデータポイントであるケースです。

書き込まれたデータポイントが1つ目のケースに該当した場合、まずはそののデータポイントを順不同のまま別の配列としてバッファしておきます。そしてディスクにフラッシュするタイミングで、メモリパーティション内のデータポイントとマージしてソートし直します。

データモデルの節で、Headとその次のパーティションのみがヒープ上で管理されていると書きましたが、これは2つ目のケースに対応するためです。Headに新たなパーティションが追加されて間もない時期は、パーティションを跨ぐデータポイントが書き込まれる可能性があります。最新2つのパーティションを書き込み可能にしておくことで、これらが破棄されることを回避しています。

Write Ahead Log (WAL)

メモリパーティションは揮発性ストレージを利用しているため、突然のクラッシュや電源不足によりデータが損失する可能性があります。それに対応するために、メモリパーティションはまずWrite Ahead Log (WAL)に操作ログを書き込みます。もしクラッシュしても、ログの先頭から末尾にかけて書かれたオペレーションを実行することで復旧することが出来ます。

ディスク上のデータの更新処理をサポートするデータベースエンジンの場合、WALは非常に低レベルな操作を記述しなければなりません。更新処理を完全に復元するには、どのディスクブロック中のどのバイトが変更されたのかなどを正確に保存しておく必要があります。

しかし時系列データはappend-onlyで、tstorageでは全てのディスクパーティションを読み込み専用にしています。メモリパーティションにどのようなデータポイントが書き込まれたかという高レベルな情報のみを追記していけば良いため、ディスクに依存しないシンプルなフォーマットで、高速な復旧をサポートする事ができます。

ディスクパーティション

ディスクパーティションを理解するには、ファイルシステム上のマクロレイアウトを見てもらうのが一番早いと思います。

下に示すように、1つのパーティションにつき1ディレクトリを使っています。その下にメタデータと、圧縮された実際のデータがあります。Prometheusのレイアウトを簡素化したものなので、似たような構造を目にしたことがあるかもしれません。

$ tree ./data
./data
├── p-1600000001-1600003600
│   ├── data
│   └── meta.json
├── p-1600003601-1600007200
│   ├── data
│   └── meta.json
└── p-1600007201-1600010800
    ├── data
    └── meta.json

データ -> メタデータの順に、実装のポイントを解説していきます。

Memory-mapped data

前述の通り、パーティション内の全データポイントは1つのファイルへと書き込まれます。tstorageでは、以下のようなフォーマットを採用しています。

        ┌───────────────────────────┐
        │    Metric-1    │ Metric-2 │
        │───────────────────────────│
        │ Metric-3 │                │
        │──────────┘                │
        │          Metric-4         │
        │───────────────────────────│
        │   Metric-5  │   Metric-6  │
        │───────────────────────────│
        │         Metric-7      │   │
        │───────────────────────┘   │
        │         Metric-8          │
        │───────────────────────────│
        │Metric-9│     Metric-10    │
        └───────────────────────────┘
                 File format

Metric-1 ~ Metric-10は、それぞれメトリクスのデータポイントリストを表しています。

時系列データの特徴を思い出して下さい。データポイントは不変であり、範囲指定してメトリクスを一括で取得することがほとんどでした。そのためメトリックごとにデータポイントをまとめることで、局所性を高めています。

このファイルは、mmap(2)でカーネルを通して透過的にキャッシュされます。これにより、ユーザー空間へのコピー無しでファイルをキャッシュすることが出来ます。また、カーネルが必要に応じてメモリを解放してくれるため、プロセスがヒープを専有することもありません。Aliが時間の経過とともにヒープを食っていく問題を解決することが当初のモチベーションであったため、これはかなり効果を発揮します。

メモリマップされたファイルは、Goプログラムからはヒープ上のバイト列と同じように[]byteとしてアクセスする事ができます。

type diskPartition struct {
	// file descriptor of data file
	f *os.File
	// memory-mapped file backed by f
	mappedFile []byte

さて、この自己完結したバイト列に対してどのように探索をかければ良いのでしょうか。ヒープ上へコピーして、Goプログラム上のデータ構造へとデコードすれば簡単に探索することが可能ですが、そんなことをしたらメモリマップした意味がありません。どうにか、バイト列のまま効率よくアクセスするためのインデックス構造が必要です。そのために使われるのが、次に紹介するメタデータです。

メタデータ

メタデータの中身はこのようになっています。パーティション毎に1つしか無いため、多少冗長にはなりますがプログラムから扱いやすいJSONフォーマットを採用しています。

$ cat ./data/p-1600000001-1600003600/meta.json
{
  "minTimestamp": 1600000001,
  "maxTimestamp": 1600003600,
  "numDataPoints": 7200,
  "metrics": {
    "metric-1": {
      "name": "metric-1",
      "offset": 0,
      "minTimestamp": 1600000001,
      "maxTimestamp": 1600003600,
      "numDataPoints": 3600
    },
    "metric-2": {
      "name": "metric-2",
      "offset": 36014,
      "minTimestamp": 1600000001,
      "maxTimestamp": 1600003600,
      "numDataPoints": 3600
    }
  }
}

メタデータは、パーティション内のインデックス構築に使われます。ここには、メトリック毎のファイル内オフセットやバイトサイズが保存されており、このメタデータのみがヒープに乗ります。これらを用いてカーネル空間にマップされているデータに対してランダムアクセスを試みます。以下のようなイメージです。

     {
       "minTimestamp": 1600000001,
       "maxTimestamp": 1600003600,
       "numDataPoints": 7200,
       "metrics": {
         "metric-1": {
           "name": "metric-1",
   ┌─────  "offset": 0,
   │       "minTimestamp": 1600000001,
   │       "maxTimestamp": 1600003600,
   │       "numDataPoints": 3600
   │     },
   │     "metric-2": {
   │       "name": "metric-2",
   │       "offset": 36014, ────────────┐
   │       "minTimestamp": 1600000001,  │
   │       "maxTimestamp": 1600003600,  │
   │       "numDataPoints": 3600        │
   │     }                              │
   │   }                                │
   │ }              ┌───────────────────┘
   │                │
   V                V
   0              36014
   ┌───────────────────────────┐
   │    Metric-1    │ Metric-2 │
   │───────────────────────────│
   │ Metric-3 │                │
   │──────────┘                │
   │          Metric-4         │
   │───────────────────────────│
   │   Metric-5  │   Metric-6  │
   │───────────────────────────│
   │         Metric-7      │   │
   │───────────────────────┘   │
   │         Metric-8          │
   │───────────────────────────│
   │Metric-9│     Metric-10    │
   └───────────────────────────┘

メトリック毎のスタートオフセットを保存するためにも、ディスクへフラッシュする時にそれを取得しておく必要があります。メトリック毎にデータポイントのリストを符号化し、オフセットをメタデータファイルに書き込んでいきながらインデックスを構築していきます。

符号化

前述したとおり、時系列データはタイムスタンプと値のタプルで表現されることが多く、これらは工夫すれば非常に小さなサイズへと符号化することが可能です。

Facebookが2015年にGorilla: A Fast, Scalable, In-Memory Time Series Databaseという論文を出し、そこで時系列データの特徴を生かした符号化方式について紹介しています。現在主流となっている多くの時系列データベースがこれをベースにした符号化を行っており、tstorageもこれを参考に実装しました。

タイムスタンプと値はそれぞれ異なる方法を用いて符号化されます。まず、tstorageにおけるUNIXタイムスタンプは符号なし64ビット整数型で表現されています。このタイムスタンプは単調増加する傾向にあるため、直前の値との差分のみを保存する符号化方式が有効です。そこで、Delta-of-delta encodingが採用されています。

また、tstorageにおける値は符号あり64ビット浮動小数点型で表現されています。この値も単調増加/単調減少はしないものの近い数値を推移することが多い傾向にあるため、XOR encodingを用いて符号化しています。

ここからはそれぞれの符号化方式について解説していきます。

Delta encoding

Delta-of-delta encodingはDelta encodingを活用した符号化方式なので、まずはDelta encodingについて少し説明します。

Delta encodingでは、一つ前の数値とのとの差分のみを書き込んでいきます。

例えば、先頭のタイムスタンプが1600000000だとします。それに続いて1600000060 -> 1600000120 -> 1600000181が書き込まれると、deltaはそれぞれ60, 60, 61となります。

Timestamp	Delta
1600000000	-
1600000060	60
1600000120	60
1600000181	61

ファイルには、このdelta値のみを順番通りに書き込んでいきます。デコードする時は順番通りにdeltaを適用してけば元通り復元することが可能です。

Delta-of-delta encoding

Delta encodingした結果でも、何らかの可変長エンコーディングを施せばそれなりにサイズを節約することが出来ます。しかし時系列データのタイムスタンプは一定間隔であることが多く、delta値自体が近い数値になる可能性が高いです。そこで、このdelta値のdelta値を取ることで更なるサイズ節約を狙います。このdelta値のdelta値をdelta-of-deltaと呼びます。

先程のタイムスタンプのdelta-of-deltaを取ってみます。

Timestamp	Delta	Delta-of-delta
1600000000	-	-
1600000060	60	-
1600000120	60	0
1600000181	61	1

まず1番目のタイムスタンプはdelta値が計算できないため、1600000000をそのまま書き込みます。論文によるとGorillaでは固定長エンコーディングを用いて符号化するようですが、tstorageではVarintsという可変長エンコーディング手法を採用しました。

2番目のタイムスタンプはまだdelta-of-deltaが計算できないため、delta値である60をそのまま書き込みます。Gorillaは時系列データのブロックを 4時間(=16384秒)ごとに作成する事を仮定しているため、 取りうる最大のビット数が14bitsであることから、14bitsの固定長を確保してエンコードしています。しかしこちらもtstorageではVarintsを用いて可変長エンコードします。（Prometheusも先頭2つのタイムスタンプをVarintsで符号化しており、正直なぜGorillaでは固定長を使っているか分かりません）

Varintsの仕組みに関しては以前の記事で解説したので興味ある方は是非：
https://zenn.dev/nakabonne/articles/cc0cde2bd94639#可変長エンコーディング

delta-of-deltaは可変長エンコーディングを用いて符号化されるため、書き込まれる数値の大きさによってサイズが変わります。delta-of-deltaが0の場合は、1bitを使って0を書き込みます。-64 ~ 64 の範囲内に収まっている場合は、2bits使って1と0を書き込んだすぐ後に7bitsを使ってdelta-of-deltaを書き込みます。

従って、それぞれのタイムスタンプのサイズは次のようになります。

Timestamp	Delta	Delta-of-delta	Length
1600000000	-	-	40bits
1600000060	60	-	8bits
1600000120	60	0	1bits
1600000181	61	1	9bits

合計のサイズは、40 + 8 + 1 + 9 = 58bits になりました。

元々の4つのタイムスタンプを固定長エンコードしたら64 x 4 = 256bits になるため、かなり節約されたことが分かります。

ご覧のとおり、タイムスタンプが一定間隔おきに並んでいればdelta-of-deltaは常に0になるため、非常に符号化効率が良くなります。サイズをなるべく抑えたい場合は一定間隔でデータポイントを書き込むようにしておくと良いでしょう。

もっと詳しく理解したい方は論文の4.1.1 Compressing time stampsを一読することをおすすめします。

XOR encoding

XOR encodingは、浮動小数点型の2値のXORをとって、実際の値の代わりにそれを書き込んでいく方法です。

近い値のXORをとるとLeading zerosとTrailing zerosが多くなりやすいという特徴があり、書き込むサイズの省略が望めそうです。例えば、2.0と3.0のXORをとると：

2.0 ^ 3.0 = 0000000000001000000000000000000000000000000000000000000000000000
            └leading 0s┘ └                  trailing 0s                     ┘

ご覧の通り3つのパートに分かれます。

• Leading zeros (12bits)
• 1 (1bits)
• Trailing zeros (51bits)

この1という値はmeaningful bitsと呼ばれ、このmeaningful bitsとLeading zerosの数を書き込むことで、数値を正確に表現していきます。次のルールに従って符号化していきます。

• 前の値とのXORが同じ場合
  • 0を書き込んで終了
• 前の値とのXORが異なる場合
  • 1を書き込む
  • meaningful bitsが前の値と同じ場合
    • 0を書き込んでmeaningful bitsを書き込む
  • meaningful bitsが前の値と異なる場合
    • 先頭の0の数を書き込む（5bits）
    • meaningful bitsの長さを書き込む（6bits）
    • meaningful bits自体を書き込む

もっと詳しく理解したい方は論文の4.1.2 Compressing valuesを一読することをおすすめします。

注意点

これらの符号化方式は隣り合う値同士の関係性に注目したものなので、そのままランダムアクセスすることが出来ない点に注意してください。

Aliのパフォーマンスが改善

Before:

After:

時系列ストレージレイヤーを追加したことで、時間の経過とともにヒープ使用量が増加する問題が解決していることが分かります。

tstorageの欠点

tstorageは非常にシンプルな作りになっているため、まだまだ力及ばない点があります。

例えば、1つのディスクパーティションが大量の種類のメトリクスを持ってしまうとヒープが圧迫されていく問題があります。前述したとおりデータ自体はカーネル空間にマップされているため、データ量が増えることは問題ありません。しかしインデックスのためのメタデータは全てヒープに乗っています。メタデータはメトリック毎に存在するため、メトリックの種類が増えるにつれて1パーティション毎のメタデータ数が増えていき、ヒープ使用量の増加分も線形的に上がっていきます。

まとめ

時系列データは扱うべき問題がシンプルで、割り切った設計をすることが出来るためストレージエンジンを初めて実装するには適した題材だと思います。

本記事では実装のポイントについて抽象的に解説しましたが、興味がある方は是非ソースコードも見てもらえればと思います。

間違い等ありましたらコメントかTwitterまでご連絡いただけると大変助かります。

参考

• https://misfra.me/state-of-the-state-part-iii
• https://fabxc.org/tsdb
• https://questdb.io/blog/2020/11/26/why-timeseries-data
• https://questdb.io/blog/2021/05/10/questdb-release-6-0-tsbs-benchmark
• http://www.vldb.org/pvldb/vol8/p1816-teller.pdf
• https://blog.timescale.com/blog/time-series-compression-algorithms-explained

脚注

1. というかまあ、とにかく作りたかったというのが本音