TwitterFacebookRSS Feed
データベースストレージエンジン B+treeとLSM treeについて

データベースストレージエンジン B+treeとLSM treeについて

こんにちは、アンチパターンの山本です。

現在「Build Your Own Database From Scratch in Go」という記事を読んで、原子性（全部成功するか何もしなかった状態にする）と耐久性（電源落ちても消えない）を持ったデータベースをGo言語で実装するというのを勉強中です。

その中でMySQL にも使われているB+treeと、もう一つのデータ構造であるLSM treeがとても面白かったためブログにまとめました！

まず、そもそもデータベースの用途は、大きく分けてこの2つに分類されます。

  • OLTP（オンライン・トランザクション処理）
    スマホアプリやECサイトのように、「1件の登録」　「1件の更新」など細かい大量の読み書きを捌くシステム。MySQLやPostgreSQLがそうです。
  • OLAP（分析処理）
    大量のデータから「過去1年間の顧客単価」などを計算するシステム。こちらでは「列指向（カラムナー）ストレージ」という全く別のデータ構造が使われる。Amazon Redshiftなどがこれにあたります。

今回はOLTPのお話になります。
OLTPのような大量の読み書きを捌くことが出来る仕組みは多くなく、この2つに二分されます。

  • B+tree　:検索が最適化されている
  • LSM tree（Log-Structured Merge-tree）: 書き込みが最適化されている

B+tree

B+treeは素早く検索するために、ディスク上に完璧に整頓されたツリーを維持し続けるデータ構造です。
B-treeは途中のノードにも実際のデータを置きますが、B+treeはノードにはキーしか置かず、実際のデータはすべて一番下のリーフに置きます。

ノードに実データを置かないことで、1つの箱に大量の分岐を詰め込めるようになり、木の高さを低く抑えることができます。実際にMySQLでデータが1億個ある場合でも、たった4層で実データまでたどりつくことができます！

ノードを4KBで統一することで効率化

B+treeは、1つのノードのサイズを4KB（もしくはその倍数）に固定します。
SSDがデータを読み書きする最小ブロックが4KB、OSがメモリとディスクの間でデータを読み書きする最小単位（ページ）も4KBであるためです。
（４KBは原稿用紙4枚分くらい）

もしノードを5KBなどにすると、SSDは8KBの容量を確保する必要があり、OSは1つのノードを確認するのに2度データを読み取りしなければならず、効率が落ちてしまうのです。

LSM tree

LSM treeは新しく来たデータをメモリ上にある小さな箱（MemTable）に一旦溜めます。MemTableがいっぱいになったらディスクの空いている場所に「新しいファイル」として書き出す。そして（バックグラウンド）で大きな箱（SSTable）へと綺麗にマージ（合体・整理）していく。

  • B+木のようなその都度直接上書きする処理が発生しないため、書き込みが圧倒的に速く、ディスクへの書き込み回数を削減出来る

FacebookとRocksDB

Facebookは、B+木による容量の増大と書き込み量が問題になっていました。
そこで、圧縮率が高くディスクにも優しいLSM treeベースのエンジンMyRocksを開発します。
2017年に移行した結果、データサイズを62.3%も削減し、DBサーバー台数を半分に減らすコスト削減を実現しました。

参考記事：
https://enterprisezine.jp/article/detail/9450?p=2
https://www.vldb.org/pvldb/vol13/p3217-matsunobu.pdf

なぜそんなに圧縮できるのか

B+treeはノードからデータが溢れたとき、ノードを2つに分割してデータを半分に分けます。
その時できた2つのノードはデータがスカスカな状態で保存されることになります。このように、ほとんどのノードはデータがびっちり入っているわけではなく、容量に余白がある状態なのです。

一方でLSM treeはデータを一つ大きいレイヤーに保存する時、きれいに並び替えてマージしたデータを新しい領域に保存していきます。そのためぎちぎちにデータを詰めて保存することが出来るのです。

B+treeがどうして書き込みが多いのか

B+treeは書き込みに対して、ツリーの整合性とノードのサイズを保つためにその都度SSDへの書き込みが発生します。
さらに書き込みの途中で中途半端なデータが保存されるようなことがないようにデータを追記したノードを1回仮にストレージに書き込んで、その後清書するというようなダブルライトという仕組みもあり、書き込みが多くなりやすい仕組みになっています。

余談：なぜSSDは劣化するのか

SSDは、データを保存するために電子を酸化皮膜（酸化シリコンのガラス状の壁）でできた箱に閉じ込めています。
電子が入っている状態を0、入っていない状態を1として扱いデータを保存しています。
データ書き込む際、高電圧をかけることで通常では通り抜けられない酸化皮膜の壁をトンネル効果によって通過させ、電子を閉じ込めます。トンネル効果によって何度も電子が通過すると酸化皮膜がにぶつかり、物理的に壁がボロボロになり、電子を閉じ込められなくなって寿命を迎えるのです。

余談：トンネル効果とは

通常電子は電圧をかけたところで酸化皮膜を通り抜けるほどのエネルギーを持てない。でも電子は波の性質も持っているため、電子の波（存在する確率）は酸化皮膜の向こう側にも漏れ出すため、一定確率でFloating gateまでたどり着くことが出来る！

電子の波
~~~~~~~＼
        ███████  壁
        ~~＼
            ~＼~~~ 反対側にも少し残る

まとめ

B+treeとLSM tree、どちらか一方が最強で優れているという話ではなく、事業のフェーズやボトルネックは何かによって何を選ぶのがいいんだなと感じました。

また、複雑そうに見えるデータベースやコンピュータも突き詰めると原子や電子の動きによってできていると思うと、みなさんも胸がときめく思いですよね！

おわり