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

2016-06-20

はじめに

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

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

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

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

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

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

TiDB自体はGoで書かれている。
MySQLのプロトコルを解釈できる。
MySQLで使用できるSQLのサブセットを実装している。
TiDBはRustで書かれRaftアルゴリズムを使った分散トランザクション対応のキーバリューデータベース TiKVを使っている。
- What is TiDB?にはGolevelDB, LevelDB, RocksDB, LMDB, BoltDBに対応しているとあるのですが、TiDBの開発者のLi Shenさんによるとgoleveldbはローカルストレージとしてのみ利用可能で、分散環境ではTiKVを使っているそうです。
- TiKVのストレージエンジンはLSM Treeの実装であるRocksDBを採用。Li ShenさんによるとTiDBの開発チームはRocsDBのチームとも連絡をとっているそうです。
- TiKV用のGoのクライアントもある。
現在バリバリ開発中。ロードマップ
TiDBの紹介記事: MySQL は分散DBの夢を見るか、Google F1 論文を実装した TiDB を使ってみた | 株式会社インフィニットループ技術ブログ
TiDBの起源についてのブログ記事。Thoughts behind TiDB - Part I。私は中国語読めないのでGoogle翻訳で英語にして読みました。

CoackroachDBはGoで書かれている。
PostgreSQLのプロトコルを解釈できる。
PostgreSQLで使用できるSQLのサブセットを実装している。
ストレージエンジンはRocksDBを採用。
現在バリバリ開発中。
- バージョン1.0に向けてベータ版を頻繁に出している。 Releases
- ロードマップ
デザインドキュメント Design overview, full design docとFrequently Asked Questionsがとても充実しています
- Lock-Free Distributed TransactionsにCockroachDBの分散トランザクションの設計について解説があります。

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の今後に注目したいと思います。