【エルエスエムツリー】
LSMツリー とは？
最終更新:
💡 更新をためて書き出し、あとで統合する
更新をメモリにため、整列したファイルへ書き出して、後から統合するデータ構造。RocksDBの例で、WAL、SST、コンパクションと読み書きの負担を解説します。
📌 このページのポイント
- 更新をメモリの構造にため、整列したファイルへ書き出す
- コンパクションでファイルのデータを統合・整理する
- 復旧用ログ、読み取りの探索、削除情報の扱いも関係する
- 書き込み・読み取り・空き容量の負担を調整する
ひよこ LSMツリーは、何をまとめる？
ペンギン先生 ひよこ メモリだけに書いたら、落ちたとき消える？
ペンギン先生 ひよこ SSTは、何が入ったファイル？
ペンギン先生 キーの順に整列したデータのファイルだよ。MemTableを書き出すとファイルができる。読み取りではメモリや複数のファイルを確認する必要があるので、索引やフィルター、キャッシュ等も使って負担を抑えるんだ。
ひよこ コンパクションは、全部を一つにする？
ペンギン先生 対象のファイルを読み、データを統合して新しいファイルを作る処理だよ。常に全ファイルを一つにするわけではない。古い値や削除の情報を、必要な条件を満たす範囲で整理する。読み書きと一緒に動くため、処理の負担も考えるんだ。
ひよこ B木より、必ず速い？
ペンギン先生 書き込みをまとめる利点はあるけれど、一律には言えないよ。コンパクションでデータを書き直す量、読み取りで調べる量、空き容量などにトレードオフがある。データやアクセスの仕方、機器と設定を含めて測ることが大切なんだ。
もっと詳しく知りたい人へ
削除したキーは、すぐ全ファイルから消える？
LSM系の実装では削除を示す情報を記録し、読み取り時に古い値を隠す方法があります。古い値や削除情報をいつ除去できるかは、他のファイルやスナップショット等との関係によります。削除の要求が、その瞬間の物理消去と同じとは限りません。
コンパクションが追い付かないと、何が起きる？
ファイルや未処理の更新が増え、読み取りや容量に影響する場合があります。RocksDBの説明では、MemTableの書き出しが追い付かず、新しい書き込みが停止する場合もあります。書き込み速度だけでなく、統合や書き出しの負荷を監視します。
📖 おまけ：英語の意味
「Log-Structured Merge-Tree」 ＝ ログ構造マージツリー
💬 更新を蓄積して書き出し、整列したデータを統合する構造を表す名前です。実装やコンパクションの方針によって、データの整理方法は異なります。