時系列データベースに関する基礎知識と時系列データの符号化方式について

こんにちは。インフラストラクチャー部 SRE グループの吉川 ( @rrreeeyyy ) です。今期オススメのアニメはツインエンジェル BREAK です。

普段の業務並びに趣味の一環として、サーバのモニタリング環境の調査や改善に取り組んでいます。そこで本稿では、モニタリングのコンポーネントの一つとして外すことが出来ない、時系列データベースの基礎知識に関して紹介します。

そもそも時系列データ・時系列データベースとは？

時系列データというのは、特定の時間ごとに何らかの値を取得した際の、取得した一連の値を指します。例えば、以下のようなフォーマットをしたデータなどは時系列データにあたるでしょう。

timestamp1,key,value1
timestamp2,key,value2
timestamp3,key,value3
:

時系列データベースとは、上記のような時系列データの保存・処理に特化したデータベースです。 Web インフラストラクチャーの文脈では、サーバのメトリクス等が時系列データにあたります。

Web サービスの文脈では、Web サーバの増加や複雑化により、高い解像度の様々なメトリクスを長期間保持したいという要望や、サーバのメトリクスをより統計的に解析し、アラーティングの精度を向上させたいという要望などがあり、様々な会社や組織で独自の時系列データベースが開発されているという事情があります。

数年前の時系列データベース

最近の時系列データベースの話をする前に、数年前の時系列データベース界隈の状況を少しだけ振り返ってみます。数年前に主流であった時系列データベースとして、RRDtool や Graphite などがあります。

これらの時系列データベースはシンプルであるため、時系列データベースの基本的な機能を知るには有用です。しかし、様々な問題点があるのも事実です。

RRDTool では、時系列データの作成・更新・グラフの作成をする際にコマンドラインでオプションを複数指定する必要があります。グラフの作成で使えるコマンドラインオプションは、柔軟である一方で、SQL などの標準化された書式などではなく、一部の習熟したエンジニアのみが扱える状況でした。また、時系列データの内部的な扱いに関しても、符号化や分散などのスケーラビリティを考慮されたものではなく、大量のデータを蓄積にするにつれて、更新や、複雑な解析をした場合に掛かる時間が線形的に増えていき、要求を満たせないという問題点がありました。

Graphite に関しては、現在でも非常に安定して動いており、様々な会社で採用されている優れた時系列データベースと言えそうです。スケーラビリティに関しても、Graphite に関する様々なツールが OSS で開発されていたり、様々な分散構成の資料がカンファレンスなどで公開されています。データの更新方法に関しても、HTTP API を用意しており、Graphite 形式と互換の HTTP API で書き込むことが出来る時系列データベースが新たに開発されている程度には普及しています。一方で、時系列データを保存する構造に関しては非常に単純であるために、時系列データにタグを付けて管理・解析することや、数秒単位でデータを書き込み続けた場合に、高性能なストレージを複数用意する必要があるなどの、いくつかの課題が未だに残っているような状態です。

その他にも、検索エンジンや RDBMS 等を時系列データベースとして利用するケースも増えてきています。これらは、非常に安定したストレージエンジンとしての実績や、標準化された SQL などを統計手法として扱うことが出来るという特色があります。その一方で、時系列データ専用に作られたものではないため、時系列データの解像度を上げ、数秒程度の間隔で同じデータを書き込み続けた場合、ストレージ容量の肥大化が発生したり、頻繁に解析を行うためには、メモリを多く確保する必要がある等の問題点があることがあります。

上記のような都合から、更に時系列データの取り扱いや、時系列データの統計的解析のみに更に特化したデータベースを開発するという流れが発生してきていました。

最近の時系列データベース

最近出てきた時系列データベースとして、InfluxDB や、Gorilla(Beringei) などがあります。これらを含め、最近の時系列データベースでは共通して、時系列データの符号化方式や、メモリもしくはストレージの使用法などのアーキテクチャに工夫がなされており、ストレージ容量の節約や、解析時に使用するメモリ量の削減などの効果を上げることに成功しています。また、ほとんどの時系列データベースにおいて、SQL 等をベースにしたデータ解析の方法が用意されているという特色もあります。

double-delta-encoding や XOR encoding と呼ばれるような、時系列データ内の差分を利用した符号化方法は、最近の多くの時系列データベースで使用されています。詳細は、Facebook の作っている時系列データベースである Gorilla の論文にありますが、簡単に説明します。

double-delta-encoding (timestamp)

double-delta-encoding は、時系列データのタイムスタンプが等間隔に配置される事に着目し、タイムスタンプ値の符号化を行う方法です。具体的には、次のように計算された値を使用して、タイムスタンプ値として実際に格納する値を決定します。ここで、t_n は n 番目の時系列データのタイムスタンプ値とします。

f:id:rrreeeyyy:20170525225447p:plain

書き込む値は、上記で計算した D の値によって決まります。具体的には次のようなルールになります。

D の値が 0 の場合、0 をそのまま書き込むため、単一ビットのみの容量で済みます。
D の値が [-63, 64] の区間内にあった場合、10 の後に D (7bits) の値を格納します。
D の値が [-255, 256] の区間内にあった場合、110 の後に D (9bits) の値を格納します。
D の値が [-2047, 2048] の区間内にあった場合、1110 の後に D (12bits) の値を格納します。
上記のルール以外の場合、1111 の後に 32bits を使用して D の値を全て格納します。

このルールだけだと分かりづらいので、具体的な例で見ていきましょう。次のような時系列データのブロックを仮定します。このブロックが作られた時間を、先頭に値無しのタイムスタンプとして表現しています。

1343232000
1343232062,value1
1343232122,value2
1343232182,value3

delta 並びに delta-of-delta を計算してみます。

1343232000        #=> block header
1343232062,value1 #=> delta: 62
1343232122,value2 #=> delta: 60, delta-of-delta: -2
1343232182,value3 #=> delta: 60, delta-of-delta: 0

先頭のタイムスタンプは、時系列データのブロックヘッダとして格納します (64bits)。

value1 のタイムスタンプは、まだ差分の差分を計算することが出来ません。 Gorilla では、時系列データのブロックを 4 時間 (16,384 秒) ごとに作成する事を仮定しているため、最大限遅れたとしてもブロックヘッダのタイムスタンプと value1 のタイムスタンプの差分は、16383 (14bits) で収まります。そのため、ブロックヘッダの次の値としては 14bits を利用して、62 (00000000111110) を書き込みます。

その先からは、先ほど説明したルールに基づいて値を書き込んでいきます。 value2 の delta-of-delta は -2 であるため、10 を書き込んだ後に 7bits を使用して -2 (1111110) を書き込みます。

value3 の delta-of-delta は 0 であるため、そのまま 0 を書き込みます。

これで 4 つ分のタイムスタンプの表現を書き込むことが出来ました。ブロックヘッダから順に数えていくと、64bits, 14bits, 9bits, 1bit となり、合計 88bits で 4 つ分のタイムスタンプを表現することに成功しています。

仮に、4 つ分のタイムスタンプを全て符号化無しで書き込んだ場合は、64 * 4 = 256bits を使用することになるため、大きく符号化することに成功していると言えそうです。

また、この符号化方法は、時系列データが規則正しく並んでいれば並んでいるほど符号化効率が良くなる事が重要になっています。

XOR encoding

先ほどはタイムスタンプの符号化について確認しました。タイムスタンプの場合と同じく、サーバのメトリクスやセンサデータについても、多くの場合で、異常がない限り似た値を推移する可能性が高い、という性質があります。

次のような double 型の値を持つ時系列データを書き込む事を考えます。

timestamp1,12.0
timestamp2,24.0

近い値で推移する double 値を効率よく書き込むため、まず 2 値の XOR を取る戦略を取ります。これは、近い値の XOR を取った場合、浮動小数点の符号部と、指数部並びに仮数部の上位ビットは 0 になりやすい、という特性があるためです。

例として、いくつかの近い 2 値の XOR を取った値を列挙していきます。

12.0 ^ 24.0 #=> 0000000000010000000000000000000000000000000000000000000000000000
24.0 ^ 15.0 #=> 0000000000010110000000000000000000000000000000000000000000000000
15.0 ^ 12.0 #=> 0000000000000110000000000000000000000000000000000000000000000000

この時、12.0 ^ 24.0 では先頭の 11 個の 0 並びに 1 の後に続く全ての 0 が符号化出来そうだと考えられます。この時の有意なビット (meaningful bits) は 1 のみであると考えられます。

24.0 ^ 15.0 でも、先頭の 11 個の 0 並びに、1011 の後に続く全ての 0 が符号化できそうです。この時の有意なビット (meaningful bits) は 1011 であると考えられます。

このような性質を利用し、double 値の書き込みは、次のルールに従って行われます。

前の値との XOR が 0 (=同じ値) の場合は 0 を書き込みます
前の値との XOR が 0 でない場合、まず 1 を書き込んだ後に次を計算します
- meaningful bits が前の値の meaningful bits と同じであれば 0 を書き込んだ後に meaningful bits を書き込みます
- meaningful bits が前の値と違う場合、1 を書き込んだ後に次の 3 つを順番に書き込みます
  - 先頭の 0 の数を 5bits 表現で書き込みます
  - meaningful bits の長さを 6bits 表現で書き込みます
  - meaningful bits 自体を書き込みます

先ほど同様に、次のような時系列データのブロックを仮定します。

timestamp1,12.0
timestamp2,12.0
timestamp3,24.0

timestamp1 の値は最初の値なのでそのまま書き込まれます(64bits)。 timestamp2 の値は前の値との XOR を取り、同じ値であるので 0 が書き込まれます。

timestamp3 の値は前の値との XOR を取り、違う値であるので 1 を書き込んだ後、前の値の meaningful bits を確認し、同じではないため 1 を書き込みます。その後、先頭の 0 のビットの数 (11 個) を 5bits を使って書き込みます。その後、meaningful bits の長さ (1) を 6bits を使って書き込みます。最後に、meaningful bits 自体 (1) を書き込みます。この時長さは 1 なので 1 bit になります。

結果として、3 つの double 型の値を書き込むのに、64bits, 1bit, 14bits の合計 79 bits で済んでいます。

仮に、3 つ分の double 値を全て符号化無しで書き込んだ場合は、64 * 3 = 192bits を使用することになるため、こちらも、大きく符号化することに成功していると言えそうです。

また、この符号化方法も、double 値が近い値で推移するほど符号化効率が良くなる事が重要になっています。

timestamp と value の符号化をまとめた図は次のようになります (Gorilla の論文 Figure 2 から引用)。

f:id:rrreeeyyy:20170525225443p:plain

ただし、これらのエンコーディング方式を用いた場合、時系列データ内のランダムアクセスが不可能になる、といったデメリットもあります。 Gorilla では、上記のように時系列データを符号化し、基本的に全ての時系列データをメモリ上に乗せる事が可能なサイズにすることで、時系列データのほぼ全てをメモリ上で処理し、処理速度を高速にするといった戦略を取っています。また、長期間のデータに関しては、別のストレージを用意し、定期的にそちらに書き込むことで、別途参照が可能なようになっているようです。

様々な時系列データベースについて

先ほどは、最近の時系列データベースの象徴であるような Gorilla を例に取り紹介しましたが、現在開発されているそれぞれの時系列データベースにも様々な特徴があるため、いくつかピックアップして簡単に紹介をします。

Beringei (Gorilla)

Beringei は、先ほど紹介した Gorilla のアイデアをオープンソースで再実装したものです。

オープンソースとして発表された事が最近であるため、Beringei 自体に書き込みをするライブラリがあまりないことや、読み込みに SQL などの言語を使うことが出来ないことに加え、Gorilla の論文にて紹介されている全ての機能(例えば、長期間のデータの書き出しなど)が実装されていないため、使用されている例はあまり聞きませんが、今後の動きに注目したい時系列データベースの一つです。

InfluxDB

InfluxDB は、InfluxData 社が開発している Go 製の時系列データベースです。 2013 年頃から開発が進められており、2017/05 時点での最新バージョンは 1.2.4 になっており、安定してきていると言えそうです。

InfluxDB ではタイムスタンプにナノ秒を使用することができ、タイムスタンプ自体のエンコーディング・圧縮には delta-encoding や simple8b 等の方法が使用されています。書き込む事が出来る値は、Integer, Float, String, Boolean など様々で、Float の符号化には先ほど説明した XOR encodig が使用されていたり、 String に対しては Snappy 圧縮が使用されています。

また、ストレージエンジンの構造として、LSM-Tree を参考に時系列データ用にチューニングした TSM-Tree というデータ構造が使われています。 Storage Engine の章に詳細が書かれているので、興味がある人は読んでみてください。

なお、InfluxDB には Enterprise 版があり、Enterprise 版では Raft を利用して複数ノードで分散して InfluxDB を運用できる事が出来るようになります。バージョン 0.8 までは OSS 版でも使用できた機能なので、ある程度の実装は公開されており、こちらの実装も興味深いものになっています。

DalmatinerDB

DalmatinerDB は、他の時系列データベースとは少し毛色が違った、Erlang 製の時系列データベースです。本来は SmartOS 用に最適化されているようですが、Outlayer(旧 Dataloop.IO) 社が Linux 版のメンテナンスをしているようです。

DalmatinerDB は、時系列データベース自体に圧縮の機能はあまりついておらず、Snappy によるデータの圧縮が存在している程度です。これは、データの圧縮等をファイルシステムで処理させる、という方針を取っているためで、ZFS が推奨のファイルシステムとなっています。

メタデータサーバは時系列データベース自体と分離しており、PostgreSQL が使用されているようです。

DalmatinerDB 用に作られている proxy である ddb_proxy が非常に多くのプロトコルに対応しており、様々なメトリクス取得ツールからデータを送信できる事が強みの一つとしてありそうです。

また、Outlayer 社のベンチマークでは、他の時系列データベースより書き込みが 2 〜 3 倍程度高速であるという結果が出ていることや、内部で Riak Core を使用して実装されているため、クラスタリングが行える、といった旨が書かれており、こちらも興味深いデータベースになっています。

Prometheus

Prometheus は厳密には時系列データベースではなく、監視システムそのものですが、内部で実装されている時系列データベースには、様々な興味深い工夫が施されています。

例えば、時系列データのエンコーディングとして、Gorilla の delta-of-delta encoding や XOR encoding を参考にして作られた、 varbit encoding というエンコーディングが導入されていることや、時系列データを chunk という 1024 bytes の固定長のデータに分割してメモリ上に保持し、定期的にディスクに書き込む等の方法を使用し、書き込み・読み込みが高速で行えるようになっています。

また、PromQL という Prometheus 上の時系列データを処理するための言語がよく出来ており、様々な時系列データの処理を簡単に行うことが出来るようになっています。

Prometheus そのものは時系列データベースではなく監視ツールですが、監視システムと合わせて使う用途の時系列データベースとしては非常に洗練されている印象があります。

DiamonDB

日本製の時系列データベースとして、株式会社はてなのウェブオペレーションエンジニアである @y_uuk1 さんが作っている、 DiamonDB というものもあります。こちらはまだ WIP となっていますが、AWS のマネージドサービスと連携して動く時系列データベースは構想として珍しく、現場で大規模な時系列データベースを実際に運用してきた知見が生きていると推察でき、今後に期待をしています。

その他の時系列データベース

上記で紹介した時系列データベース以外にも、Spotify の作っている Heroic や、 Netflix の作っている atlas、Hadoop ベースの OpenTSDBなど、本当に様々な時系列データベースがあります。

その他の時系列データベースに関しては、少し古い内容ですが、Outlayer (旧 Dataloop.IO) という会社の Top 10 Time Series Databases という記事並びに、当該の記事中にある Open Source Time Series DB Comparison というページが非常によくまとまっています。

もし時系列データベースに興味を持たれた方がいたら、上記のページも目を通してみることをおすすめします。

まとめ

時系列データや時系列データベースとは何かというところから、時系列データベースのエンコーディング手法や、ここ数年間の幾つかの時系列データベースについて紹介しました。

大量のデータ・書き込み・読み込み処理に対して、アーキテクチャやデータ構造の工夫によって改善をしていくのは、調査していても非常に面白く、普段の業務でも意識して取り組みたい事の一つだと改めて感じられました。引き続き、内部アーキテクチャやデータ構造を正しく理解しつつ、ミドルウェアの選定・作成を行っていきたいと思います。

参考文献

本記事を書くにあたり、以下の記事・スライド・論文を参考にしました。