論文メモ The Log-Structured Merge-Tree (LSM-Tree)
April 3, 2021LSM-Treeは、検索より挿入や削除が多い用途に向いたインデックス構造であり、例えば履歴テーブルやログの保存につかえる。 メモリにある1つ木とディスク上の1つ以上の木からなり、直近の挿入や削除をメモリの木で管理する。 メモリの木の大きさがしきい値を超えたとき、メモリの木の葉をディスクの木に移す。 移動時は、ディスク上の木の葉とメモリの葉をマージソートの要領でソートし、ソートした葉をディスクの新しい連続領域に書き込む。 連続領域に書き込み、アームの移動やディスクの回転を減らすことで、高速に挿入や削除ができる。 一方、検索速度は、複数の木を探索しなければならないために、1つの木でインデックスを構成するB木に劣る。
メモリにある木を\(C_0\)、ディスクにある木を\(C_i(i> 0)\)という。 \(C_{i-1}\)の大きさがしきい値をこえると、\(C_{i-1}\)の葉を\(C_{i}\)に移し、木のサイズを小さくする。 \(i\)が大きいほどしきい値のサイズが大きく、大きな木になる。 \(C_0\)には、任意の木構造を採用でき、例えば(2-3)木やAVL-treeで実装できる。 \(C_i\)はB木に似た木構造であり、マージ時に連続領域に新しい葉ページが書き込まれるので、同じ階層のページが連続領域にできる。 これにより、シーケンシャルなアクセスが高速になる。
１回マージで1つの葉ページができる。
図はマージの様子をあらわす。
\(C_1\)左端の葉ページを含むブロックをメモリ上に読み込み、\(C_1\)の一つの葉ページと\(C_0\)の葉のエントリをマージソードの要領でマージし、1つの葉ページを新しい連続領域に書き込む。
古いページを上書きしないので、マージ時にクラッシュしても、古いページをつかってリカバリできる。
マージが正常終了したら、マージ元の古いページを削除する。
\(C_i\)から\(C_{i+1}\)へのマージも同様の手続きであり、それぞれ非同期に実行できる。
削除も挿入と同じように、\(C_0\)にバッファし、複数の削除をディスクに一度に反映できる。 削除のリクエストが発生すると、\(C_0\)に削除したいレコードのIDをもったエントリ(delete node entry)を挿入する。 実際のレコードの削除は、マージ対象のエントリの中にdelete node entryを見つけたときに実行する。 検索時には複数の木が探索され、削除したレコードのキーをみつけてもdelete node entryが見つかれば、レコードの情報を返さない。 これにより、ユーザにはレコードを実際に削除したかのようにみせられる。
論文をこちらからダウンロードできます。