# LSMツリー ## 定義 LSMツリー（Log-Structured Merge-Tree）は、書き込みをメモリ上のデータ構造（メムテーブル）にバッファリングし、閾値に達した時点でソート済みファイル（SSTable）としてディスクに逐次書き込みする永続化手法である。複数の SSTable はバックグラウンドのコンパクション処理でマージされる。すべてのディスク書き込みが逐次的であるため、ランダム書き込みが生じる B-Tree ベースの手法と比較して高い書き込みスループットを達成する。Bigtable と Cassandra がこのパイプラインを採用し、大規模分散ストレージの標準的な永続化アーキテクチャとなった（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]）。 ## 横断的知見 - Cassandra と Bigtable はともにコミットログ → メムテーブル → SSTable → コンパクションの同一パイプラインを採用しているが、実装上の差異がある。Bigtable は GFS 上に SSTable を格納し GFS のレプリケーションに耐久性を依存するのに対し、Cassandra はローカルファイルシステム上に SSTable を配置しアプリケーション層でレプリケーションを管理する。この違いにより、Cassandra は GFS のような分散ファイルシステムへの依存を排除し、独立したデプロイを可能にした（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]）。 - Cassandra はコミットログ用に専用ディスクを確保し、コミットログの書き込みスループットを最大化する設計を採用している。128 MB 超でコミットログをローリングし、ビットベクタで各カラムファミリの永続化状態を追跡してパージする仕組みは、Bigtable の論文には記述されておらず、Cassandra 固有の運用上の改良である（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]）。 - **LSM ツリーの長期運用課題は、コンパクションそのものをユーザー提供経路から切り離す方向へ進む**: 2006 年 Bigtable 論文はマイナー/マージ/メジャーコンパクションをタブレットサーバの基本機構として説明した。2026 年論文では、ファイル構築をタブレットサーバ外のジョブへ外部化し、タブレットサーバの CPU/RAM をユーザーリクエストへ残す設計へ移っている。LSM ツリーの書き込み効率はコンパクションの後払いコストを伴うため、大規模運用では「どのコンパクション戦略か」だけでなく「どの資源階層で実行するか」が重要になる。(Source: [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]], [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]) - **LSM ツリーの「階層（レベル）」は設計上の必須要素ではなく、フラット等価パート構造でも書き込み効率・継続的マージは成立する**: ClickHouse の MergeTree* は全パートを等価に扱いレベル管理を持たない。これによりレベルをまたいだマージが可能になるが、トゥームストーンによる更新・削除が使えないため、マージ戦略（置換マージ・集計マージ・TTL マージ）で代替する。WAL も使わず INSERT を直接ディスクに書き込み、ペイロード別マージ戦略を組み合わせることで OLAP 向け高スループットを実現する。（Source: [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]]） - **LSM ツリーは集計型やマテリアライズドビューの整合性メタデータを載せる基盤にもなる**: Bigtable のカウンタ/CRDT 実装は、各 LSM 層に subtotal と未解決操作を持つ changelog を保存し、コンパクション時に changelog を統合・トリミングする。これは LSM ツリーが単なる永続化構造ではなく、非同期レプリケーション下での集計整合性を維持するメタデータ構造にもなることを示す。(Source: [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]) - **コンパクション方針は WA/RA の静的トレードオフから平均クエリスループットの資源投資問題へ移る**: EcoTune は、現代 SSD ではフラッシュ用資源を予約すれば書き込みレイテンシはコンパクション方針に大きく左右されず、残り CPU/I/O をコンパクションとクエリへどう配分するかが中心だと示す。Leveling は瞬時 RA では有利でも、図1で CPU の 62% 超をコンパクションに使い、Lazy Leveling の 64% のクエリスループットに落ちた。これは既存の「コンパクション頻度のトレードオフ」問いに対し、平均性能とタイミングを目的関数に入れる回答である。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **現代 SSD 環境では、LSM ツリー優位の前提も B-Tree 優位の前提も再測定が必要になる**: EcoTune は LSM ツリーのコンパクションを平均クエリスループットへの資源投資問題として再定式化した。一方、B-Trees Are Back は、B-Tree が可変長レコード・4 KiB page・inline storage・適応 leaf layout を保つと、純インメモリ索引に近い lookup 性能と強い scan / paging 性能を両立できると示す。したがって、storage engine の選択は「LSM = write、B-Tree = read」という古典的二分法ではなく、background work、space efficiency、range scan、SSD read 確率を同じモデルで見る必要がある。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **LSM ツリーの write-ahead log と SSTable(あるいは WiredTiger の log/sst ストリーム)は、コンパクション戦略だけでなく物理的な配置(SSD のゾーン・ストリームへの分離)によっても性能を改善できる**: [[Valet]] は RocksDB の WAL と SST、および WiredTiger の log と sst をそれぞれ別々のデバイスストリーム(SSD のゾーンまたは書き込みバッファ)に隔離することで、f2fs 実装に対し RocksDB の fill/overwrite で2倍超、WiredTiger(LSM モード)のマルチスレッド書き込みで3倍のスループット改善を得た。これは、LSM ツリーの性能最適化がコンパクションポリシー(ソフトウェア層)だけでなく、下層デバイスへのデータ配置(ハードウェア/インターフェース層)にも及ぶことを示す、これまでのこの concept の知見に対する新しい軸である。(Source: [[@2025__SoCC__Valet - Efficient Data Placement on Modern SSDs]]) - **書き込み amplification を抑えるために値をツリー外へ追い出す設計は、KVS レイヤーだけでなくストレージノード内部の物理配置設計にも現れる**: WiscKey がキーバリューストア一般の設計として value を分離するのに対し、ShardStore は S3 のストレージノードという文脈で shard データ(value 相当)を LSM ツリー外の「エクステント」という append-only 物理領域へ配置し、LSM ツリー自体は shard 識別子からチャンクへのポインタのみを保持する。これにより、LSM ツリーの役割は「値の永続化」から「物理配置へのインデックス」へと純化される。さらに ShardStore は、この物理配置の crash-consistent な順序制御を soft updates 由来の宣言的な `Dependency` 型で扱っており、LSM ツリーと crash consistency protocol を独立した関心事として分離する設計判断は、Bigtable/Cassandra が GFS/ローカル FS のレプリケーション機構へ整合性を委ねるのと対照的である。(Source: [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]], [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]) ## 未解決の問い - EcoTune は平均スループットを最適化するが、クエリ到着率やレイテンシ SLO を直接目的関数に入れたコンパクション制御はどう設計されるべきか。 - メムテーブルのフラッシュ閾値と top level 容量は、EcoTune の $S=M/K$ 方針と、実運用のメモリ/SSD 比・多テナント制約の間でどう決めるべきか。 - 外部コンパクションはタブレットサーバの資源競合を減らすが、ファイル構築ジョブのオートスケール、失敗時リトライ、SSTable 導入前検証を含めた全体 TCO はどのように評価されるべきか。 - CRDT の changelog のように LSM 層へ意味的メタデータを載せる設計は、他のデータ型やセカンダリインデックスにも一般化できるか。 - LSM ツリーの block-level optimization と B-Tree の node-level optimization を、同一 key distribution・同一 memory/SSD 比・同一 range scan mix で比較する benchmark はどのように設計すべきか。 - ClickHouse の MergeTree* は WAL を使わず INSERT をディスクに直書きし電源断時の若干のデータ損失を許容するが、この設計が OLAP ユースケース一般でどこまで成立するかは検討の余地がある。 - ShardStore の「LSM ツリーと crash consistency を分離し、後者を宣言的な Dependency グラフで扱う」設計は、他の LSM ベースストレージシステム(RocksDB・WiredTiger 等)の crash consistency 実装(WAL ベース)と比べてどのような性能・保守性のトレードオフを持つか。 ## 関連 - ソース: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]] / [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]] / [[@2026__SIGMOD Companion__Twenty Years of Bigtable]] / [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] / [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] / [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]] / [[@2025__SoCC__Valet - Efficient Data Placement on Modern SSDs]] / [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]] - 概念: [[結果整合性]] / [[一貫性ハッシュ法]] / [[LSMツリーコンパクション]] / [[B-Tree]] / [[列指向OLAPデータベース]] / [[ホスト誘導データ配置]] / [[軽量形式手法]] - エンティティ: [[Apache Cassandra]] / [[EcoTune]] / [[RocksDB]] / [[ClickHouse]] / [[Valet]] / [[ShardStore]] ## 出典 - [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（§5.6 Local Persistence、§5.7 Implementation Details——コミットログ、メムテーブル、SSTable、コンパクション） - [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]（SSTable、コンパクション） - [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]（外部コンパクション、カウンタ/CRDT、SSTable 導入前検証） - [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]（§3 コンパクションの資源投資観、§4 EcoTune、§5 RocksDB 評価） - [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]（§8 LSM-Trees、B-Tree 最適化の LSM block への転用可能性） - [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]]（§2.1 Design Overview——エクステント外への shard データ配置、§2.2 Crash Consistency——Dependency 型）