LSM-Treeって何だろう
今回の記事は本当だったら数ヶ月前に書こうと思っていた内容です。
どうしてもMySQLに関する記事を書きたい欲が勝ってしまい、遅くなってしまいました…
今回は単純に調べた内容を書くだけの短い内容となっています。
以前Qiitaで興味深い記事を拝見しました。
お恥ずかしながらNewSQLという概念を初めて知ったのですが、非常にワクワクしながら読ませていただきました。
この記事の通りNewSQLを構成する各技術は全くの新しい技術というわけではないようです。
今回はその中でもLSM-Treeについて調べてみました。
LSM-Treeとは
LSM-TreeとはLog Structured Merge Treeの略で書き込みワークロードが多い環境で比較的優れたパフォーマンスを発揮するデータ構造です。 B-Treeなどの木構造と同様にキーとそれに対応する値のペアを保持します。
LSM-Treeを採用しているプロダクトとしてHBase, Cassandra, RocksDBなどを挙げられます。
B-Tree
ご存じの通り多くのRDBMSではインデックスのデータ構造にB-Tree(MySQLではB+Tree)が採用されています。 B-Treeによりデータはソートされていることが保証されるため、欲しいデータを取得するために必要なディスクアクセスの回数を減らせます。 低速なディスクへのアクセスの頻度を下げることにより読み取りパフォーマンスを向上させることができます。
またB-Treeは探索にかかる計算量のオーダーがとなるため探索対象のデータ量が増えても探索時間が大幅に遅くなるといったことを防げます。
なぜB-Treeではだめなのか
上記の通り読み取りに関しては優れたパフォーマンスを発揮するB-Treeですが、もちろん弱点もあります。 それは書き込みパフォーマンスが良くないということです。
B-Treeにはソート済みのデータが格納されるため新しいデータが挿入されたりデータをが更新されたりすると、 場合によっては木構造を再構築する必要があります。 木構造の再構築はコストがかかるため、読み取りのワークロードより書き込みのワークロードが多いような環境ではB-Treeは最適なデータ構造ではなくなってしまいます。
LSM-Treeの立ち位置
さきほど、B-Treeでは書き込みのワークロードが多いような環境には不向きであるということを書きました。
それでは書き込み最適化なデータ構造とはどんなものでしょうか。
そもそもなぜ書き込みが遅いのかというと低速なディスクに対してランダムにアクセスするからです。 ログのように追記型であれば書き込みであってもそこまで遅くはありませんが、これはシーケンシャルに行われるからです。
一方でログから必要な情報を探すことは一般的には大変な作業です。 （大量のログから特定の文字列を探すために苦労した方もいらっしゃるのではないでしょうか。）
ログデータの検索が難しいのは、そこにインデックスが無いからです。 （DBMSでもインデックスのないテーブルは参照に多くの時間を要します）
B-Treeだと読み取りは高速だけど書き込みは低速、追記型では書き込みは高速だけど読み取りは低速と、どちらも一長一短があります。
ちょうどこの間に位置するのがLSM-Treeです。
LSM-Treeのアルゴリズム
LSM-Treeのアルゴリズムはそこまで複雑なものではありません。
まずはLSM-Treeのイメージとして下記リンクを見ていただきたいです。
Log-structured merge-tree - Wikipedia
レベルという概念が存在していて、下にいくにつれてレベルが大きくなっていきます。 このイメージは非常に重要です。
Write
書き込み要求が来るとその内容をメモリに保持します。 メモリ内でも赤黒木のような木構造に格納されるため、ソートされていることが保証されます。(メモリ上の操作はディスクのそれと比べると極めて高速ですので、木構造の再構築のコストは高くないことに注意してください) これをmemtableと呼びます。 メモリは揮発性ですので、障害に備えてmemtableの内容はWALでディスクに複製されます。 （正確にはWALで書き込むためログへの書き込みが先に行われてます）
memtableがいっぱいになるとその内容をファイルとしてディスクにフラッシュします。ここで重要なことは各ファイルはソートされているためシーケンシャルなディスク操作しかしないことです。 また各ファイルは変更されないため、重複したファイルが作成される可能性があります。
Compaction
LSM-Treeは定期的にCompactionと呼ばれる操作を行います。
これはディスクにフラッシュされた各ファイルをいくつか選択してマージする処理です。これにより重複するデータを削除することができます。 Compactionによりデータの無駄な冗長性をなくすことができ、加えてこれは読み取りパフォーマンスを劣化させない働きもします。
具体的にはレベルが低いファイルをいくつか選択してマージし、よりレベルの高いファイルとして生成されていきます。 下記リンクのイメージが分かりやすいです。
Read
読み取り要求が来ると、まずはmemtableの中に対象のデータが含まれていないかをチェックします。 memtableになければ若いレベルから順番に対象のデータが含まれていないかチェックをし、見つかるまで各ファイルを走査します。 すなわちデータの数が増えるごとに読み取りパフォーマンスは劣化します。
さきほどLSM-Treeに含まれるデータは重複している可能性があると書きました。 つまりあるキーに対して異なる値を持つ複数のデータが存在しうるということです。 例えばすでにディスクに保存されている[1:'a']というデータはメモリ上では[1:'b']に更新されている可能性があります。 古いデータを読み取ってしまうことは無いのでしょうか。
このとき、若いレベルから順番に探索していくというのがポイントです。 LSM-Treeはその構造上、大きいレベルに含まれるデータは若いレベルに含まれるそれと比べて古いデータです。 そのため若いレベルから順番に探索していき、初めて見つかったデータに関しては最新バージョンであることが保証されるということですね。
なお、読み取りパフォーマンスを向上させるためにBloom flterと呼ばれる空間効率が良い確率的データ構造が利用されるようなのですが、 ちょっとまだ詳しく調べられていないので割愛します。
まとめ
今回はLSM-Treeについて調べてみました。
LSM-TreeはB-Treeに比べて書き込みワークロードに対して効率的であることが分かりました。
実際にどの程度の書き込みワークロードでればB-Treeよりもスループットが上がるのか、 実際のプロダクトではどのように実装されているのかなどまだまだ気になる点はありますが、 今回はこのあたりで切り上げようと思います。
