# 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ツリーのコンパクションはディスク I/O を大量に消費し、書き込みアンプリフィケーション（write amplification）を引き起こす。Cassandra 論文ではサイズが近いファイル同士をマージする方針を述べているが、レベルドコンパクションやティアードコンパクションなど後に登場した戦略との性能比較は定量化されているか。 - メムテーブルのフラッシュ閾値の決定方法と、コンパクション頻度のトレードオフについて、ワークロード特性（書き込み集中 / 読み取り集中）に応じた最適化指針はどの程度体系化されているか。 ## 関連 - ソース: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]] / [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]] - 概念: [[結果整合性]] / [[一貫性ハッシュ法]] - エンティティ: [[Apache Cassandra]] ## 出典 - [[@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、コンパクション）