LSM-TreeとRocksDB、TiDB、CockroachDBが気になる

はじめに

キーバリューストアについて調べていたらLSM-Treeというデータ構造とRocksDBが気になったということで調査メモです。ただし、それぞれの技術詳細を調査したり自分で検証してみたというメモではないです。

そうではなく、いろんな記事で言及されていたり、ソフトウェアで採用されているのが気になったというだけの浅いメモです。が、脳内バッファからあふれる量になったので自分用に軽くまとめ。

LSM Tree

Log-structured merge-treeを略してLSM Treeと呼ぶそうです。概要はLog-structured merge-tree - Wikipediaを参照してください。

CockroachDBのデザインドキュメントのRead vs. Write Optimization Spectrumによると、B+ Treeというデータ構造は書き込みより読み取りが多いケースに最適化されているが、LSM Treeのほうは書き込みが多いケースに最適化されているそうです。

一方、LSM Treeのほうはディスク使用量は肥大化しがちで定期的にコンパクションする必要があって、コンパクションには負荷がかかるので、この方式を各実装で工夫しているという話を何処かで読んだんですがリンクを紛失してしまいました。

InfluxDBの事例

InfluxData | Documentation | Storage EngineによるとInfluxDBのストレージエンジンは以下の変遷を辿ったそうです。

  1. LSM Treeの実装の1つであるLevelDBを採用
  2. B+Treeの実装の1つであるBoltDBを採用
  3. LSM Treeに似た独自のデータ構造でストレージエンジンを自作

TiDBの事例

pingcap/tidb: TiDB is a distributed NewSQL database compatible with MySQL protocol

CockroachDBの事例

cockroachdb/cockroach: A Scalable, Survivable, Strongly-Consistent SQL Database

名前の由来: Why the name Cockroach?

LSM Treeの実装はいろいろあるがRocksDBが良いらしい

InfluxDBの開発元influxdataのブログのベンチマーク記事 Benchmarking LevelDB vs. RocksDB vs. HyperLevelDB vs. LMDB Performance for InfluxDB | InfluxDataでも値の書き込みとクエリ実行の性能が良いのはRocksDBとなっています。

Small Datum: Comparing LevelDB and RocksDB, take 2にRocksDBとLevelDBのベンチマークがありますが、RocksDBのほうが良い感じです。

上記の通りTiDBでもCockroachDBでもRocksDBを採用していますし、現在のところ有望そうです。

Rocksdb: The History of RocksDBにRocksDBを開始した頃の話が書かれていました。

RocksDB FAQの "Q: What's the maximum key and value sizes supported?" によると、RocksDBは大きなサイズのキー用にはデザインされておらず、推奨されるキーと値の最大サイズはそれぞれ8MBと3GBとのことです。

おわりに

書き込みが多いケースに向いているキーバリューストアであるRocksDBと、RocksDBをつかて分散トランザクションを実現しているデータベースであるTiDBとCockroachDBの今後に注目したいと思います。