Log-structured merge-tree とは

コンピュータサイエンスでは、ログ構造のマージツリー(またはLSMツリー)は、トランザクションログデータなどの挿入量の多いファイルへのインデックス付きアクセスを提供することを魅力的にするパフォーマンス特性を備えたデータ構造です。 LSMツリーは、他の検索ツリーと同様に、キーと値のペアを維持します。 LSMツリーは2つ以上の別々の構造にデータを保持し、それぞれはそれぞれの基礎となる記憶媒体に最適化されています。データは2つの構造間でバッチで効率的に同期されます。
LSMツリーの簡単な1つのバージョンは、2レベルのLSMツリーです。 Patrick O'Neilが説明したように、2レベルのLSMツリーは、C0とC1と呼ばれる2つのツリー状の構造で構成されています。 C0は小さく、メモリには常駐していますが、C1はディスク上に常駐しています。新しいレコードは、メモリに常駐するC0コンポーネントに挿入されます。挿入によってC0コンポーネントが特定のサイズのしきい値を超えると、エントリの連続したセグメントがC0から削除され、ディスク上のC1にマージされます。 LSMツリーのパフォーマンス特性は、各コンポーネントがその基礎となる記憶媒体の特性に調整され、マージソートを連想させるアルゴリズムを使用して、データがローリングバッチでメディア間で効率的に移行されるという事実に由来します。
実際に使用されるほとんどのLSMツリーは、複数のレベルを使用します。レベル0はメインメモリに保持され、ツリーを使用して表すことができます。ディスク上のデータは、ソートされたデータの実行に編成されます。各実行には、索引キーでソートされたデータが含まれています。実行は、単一のファイルとしてディスク上に表現することも、重複しないキー範囲を持つファイルの集合として表すこともできます。関連する値を取得するために特定のキーに関するクエリを実行するには、レベル0のツリーとそれぞれの検索を検索する必要があります。
特定のキーがいくつかの実行で表示されることがあります。クエリの意味はアプリケーションによって異なります。アプリケーションによっては、特定のキーを持つ最新のキーと値のペアが必要なアプリケーションもあります。アプリケーションによっては、適切な集計値が返されるように値を組み合わせる必要があります。たとえば、Apache Cassandraでは、各値はデータベース内の行を表し、異なるバージョンの行は異なる列セットを持つことがあります。
クエリのコストを抑えるためには、実行が多すぎる状況を回避する必要があります。
BLSMやDiff-Indexなど、B +ツリー構造を組み込むための「均等化」メソッドの拡張が提案されています。
LSMツリーは、Bigtable、HBase、LevelDB、MongoDB、SQLite4、Tarantool、RocksDB、WiredTiger、Apache Cassandra、InfluxDBなどのデータストアで使用されます。