HBaseを支えるLSM-tree

最近HBaseについてちょくちょく勉強しているので、まとめていこうかと

今回は、HBaseのストレージ構造であるLSM-treeについて。

LSM-treeとは

RDBMSがストレージ構造としてB-Tree(特にB+Tree)を用いているのに対して、HBaseはLog-structured merge-tree(LSM-tree)を用いている。 従来のB+Treeがシークを多用するのに対して、LSM-treeはシークを最小限にするよう設計されている。

書き込み

HBaseに対して書き込み処理が行われると、最初にログファイル(HLog)対してシーケンシャルにデータ変更が書き込まれる。 万が一の場合、このログファイルから変更を復元することができる。 ログファイルへの書き込みが成功すると、インメモリのストアであるMemStoreに対して変更が書き込まれる。 MemStoreの内部はB-Treeなどでソートされており、直近の変更に対する高速な読み出しを実現している。

MemStoreが一杯になると、データがディスクにフラッシュされ、新たなストアファイルとして永続化される。 なお、MemStoreのフラッシュが完了すると、その分のログファイルは破棄される。

読み込み

特定のKeyに対しての読み込み操作が要求されると、まずMemStoreから探索が行われ、データがない場合はストアファイルを順に探索していく。 ストアファイルの先頭にはKeyとファイル内のデータの位置が記録されたMapがあり、それを用いることで1回のシークで目的のデータを探索することが可能である。 以上の構造から、ディスクシークは最大でもストアファイルの個数分に抑えられる。

コンパクション

書き込み量が増加するにつれて必然的にストアファイル数も増加し、結果としてディスクシークの回数が増えてしまう。 これを防ぐためにHBaseは定期的にストアファイルのコンパクションを行う。 コンパクションとは、複数のストアファイルをマージ&ソートする処理で、これによって小さく多量なストアファイルを大きく少量のストアファイルにマージし、ストアファイル数の増大を防ぐことができる。

まとめ

ぱっと見ただけでも、シークを最小限にする仕組みが随所にあり、おもしろい。 まだまだ理解していない所がたくさんあるので、馬本読み進めたい。

参考