Write an embedded time-series database in Go

Transcript

1. Write an embedded time-series database in Go @GoCon 2021 Autumn Ryo Nakao (@nakabonne)
2. 自己紹介 • 中尾 涼 (@nakabonne) • 株式会社サイバーエージェント • PipeCD フルタイム開発
3. Agenda • 時系列データの特徴 • tstorageの設計 • Goでの実装について
4. Write an embedded time-series database in Go Ryo Nakao (@nakabonne)
5. Write an embedded time-series database in Go Ryo Nakao (@nakabonne)
6. Embedded database • ライブラリとして提供されている埋め込み可能なデータベース • 有名なものでLevelDBやRocksDBなどがある
7. モチベーション 00
8. 負荷テストツールのメモリパフォーマンス低下
9. 負荷テストツールのメモリパフォーマンス低下 • 計測結果をSliceにappendしていくだけだった • ディスクも活用したストレージエンジンが欲しい • Go言語からEmbedded databaseとして利用できるものが無い • → 作るしかない
10. tstorage
11. 時系列データの特徴 01
12. 時系列データ • タイムスタンプ順に並んだ値（データ ポイントと呼ぶ）の集まり • 時間の経過とともにデータがどう変化 するかを見るために使われる • e.g. システムメトリクス、株価データ
13. 時系列データの特徴（一部） • データ量が膨大 • 直近のデータを読み出す • 期間指定して一括で読み出す
14. データ量が膨大 • 一定間隔おきに、永続的にデータが取り込まれる • データ量は線形的に増えていく
15. 直近のデータを読み出す 直近のデータの推移を観察するために使われることが多い
16. 期間を指定して一括で読み出す 時間の経過と共にどう変化したかを観察するために使われる
17. 速く書いて 速く読みたい こういった特徴がある中で なるべく多くのケースで
18. できるだけDRAMを使おう
19. データモデル 02
20. • タイムスタンプでパーティ ショニング • 完全に独立した小さなDBを 追加していく • 最近のデータはヒープ上 • ほとんどのケースで読み出 しが高速
21. • （再掲）読み出す時は範囲 指定して一括で読み出す • タイムスタンプが近いデー タが集まっているので、空 間的局所性を高める
22. Memory Partitionと Disk Partition に分ける とりあえず
23. 実装 ~ Memory Partition 03
24. Memory Partition • インメモリDB • データロスを防ぐために Write Ahead Logに書き 込む
25. Logical structure ~ Memory Partition
26. Logical structure ~ Memory Partition とにかくここへの書き込み &読み込みが 速度パフォーマンスに直結する
27. How to represent data points • Sliceは基底配列に基づいている • 要素数がcapacityを超えると自動的に基底配列のメモリコピーが 発生 • 際限なくデータが取り込まれるケースでは理論的には要素の追加 をO(1)で行えるLinked-listベースのデータ構造が良さそう
28. Benchmarks ~ Slice vs Linked-list
29. Benchmarks ~ Slice vs Linked-list 何度実行しても時間計算量の面ではSliceのほうが僅かに勝利
30. Benchmarks ~ Slice vs Linked-list 基底配列はRAM上の隣り合った場所に並んでいるため、 キャッシュの空間的局所性が効く
31. https://groups.google.com/g/golang-nuts/c/mPKCoYNwsoU/m/OSVy4gbCWwMJ
32. 速く書くのはいいけど... • メモリパーティションは揮発性ストレージ上で動作 • 突然のクラッシュに対応したい
33. Write Ahead Log (WAL) • 書き込みに先行して操作ログをディスクへ書き込む • リカバリ可能な形式で、なるべく小さくエンコード
34. WAL format op: オペレーションタイプ (Insert, Delete, etc) len metric: 後続するメトリック名文字列の長さ metric: メトリック名 timestamp: 最大64ビットの整数値型UNIXタイムスタンプ value: 最大64ビットの浮動小数点型の値
35. WAL format op: オペレーションタイプ (Insert, Delete, etc) len metric: 後続するメトリック名文字列の長さ metric: メトリック名 timestamp: 最大64ビットの整数値型UNIXタイムスタンプ value: 最大64ビットの浮動小数点型の値
36. Varints (Variable integers) • Protocol Bufferが内部で使用している可変長エンコーディン グ手法 • 数値の大きさに応じて消費サイズが変わる • Goでは binary.PutVarint が担当
37. 例) 10を64ビット整数値型として固定長エンコードした場合 → 必ず8バイト（64ビット）消費してしまう
38. 例) Varintsで可変長エンコードした場合 → 1バイト（8ビット）で収まる
39. 適切な位置で読み出しを終了 どのように終了位置を特定しているのか？
40. Varints の仕組み 先頭ビットが0であればそのバイトで読み出しを停止する
41. Varints (Variable integers) 数値型の値に関してはこのように Varints を用いて書き込んでいく
42. 実装 ~ Disk Partition 04
43. Disk Partition • オンディスクDB • 1つのファイルに書き込ま れる
44. File format • 時系列データは不変で、範囲指定 して一括で読み込むケースがほと んど • Metric 毎にデータポイントをまと めて圧縮することで局所性↑ • mmapによって透過的にキャッ シュ
45. Memory-mapped data • マップされたファイルは []byte としてアクセス可能 • なんらかのインデックス構造がないと非効率
46. Metadata file • パーティション毎にjson形式の メタデータファイル • メトリック毎のファイル内バイ トオフセットやサイズが保存さ れている • ヒープに乗るのはこのメタデー タのみ
47. やりたいこと • 書き込み時のオフセットの 保存 • 読み出し時のオフセットの 指定 • これらを同じインタフェー スで行いたい • Goではここでio.Seekerが活 躍
48. io.Seeker • 次に読み書きする位置を指定する • 現在のオフセットを返してくれるの で、取得も指定もこれ一つで可能 • ランダムアクセスを許容するバイト 列であれば基本何でもOK
49. When flushing • ディスクへ書き込む際に各メトリッ クのオフセットを保存する必要 • io.Seekerを満たす *os.File を利用 • メトリックの書き込みを開始するタ イミングでSeek(0, io.SeekCurrent) を呼ぶ
50. When reading • []byte の指定したオフセットから読 み出したい • io.ReadSeekerを満たす *bytes.Reader を利用
51. 高速に読み出せるようになっ たけど...
52. （再掲）データ量が膨大 • Varintsでもかなり圧縮されるが、最低でも1バイト必要 • 時系列データの特徴に注目して1バイト未満に圧縮できないか
53. Encoding • タイムスタンプは単調増加する傾向にある • 差分の差分だけ書き込めば良いのでは？ • → Delta-of-delta encoding
54. Delta-of-delta encoding 1600000000 1600000015 1600000030
55. Delta-of-delta encoding 1600000000 1600000015 1600000030 ±15 ±15
56. Delta-of-delta encoding 1600000000 1600000015 1600000030 ±15 ±15 ±0
57. Delta-of-delta encoding 1600000000 1600000015 1600000030 ±15 ±15 ±0 3番目以降はこの0 (1bit) だけを書き込んでいく
58. When reading 1600000000 1600000015 1600000030 ±15 ±15 ±0 シーケンシャルに読み出してこのdelta-of-deltaを加算していく
59. Bit単位でストリームに読み書きする • Goの標準ioパッケージの読み書き最小単位はbyte • bit単位で読み書きするためにはビット演算する必要
60. Bit単位でストリームに読み書きする 0001000 1 00010001 io.Writer.Write() byte完成!
61. Bit単位でストリームに読み書きする • bitはboolで表現
62. Bit単位でストリームに読み書きする
63. Bit単位でストリームに読み書きする • 0で敷き詰められた8bitsを 用意
64. Bit単位でストリームに読み書きする • 1を書き込む場合は末尾の0 と1のビット和を取る • そして必要な分だけ左シフ トする
65. 負荷テストツールのパフォーマンスが改善
66. • (ja) ゼロから作る時系列データベースエンジン : https://zenn.dev/nakabonne/articles/d300838a1500c7 • (en) Write a time-series database engine from scratch: https://nakabonne.dev/posts/write-tsdb-from-scratch • Repo: https://github.com/nakabonne/tstorage More...
67. Thanks Any questions? @nakabonne