# The Log-Structured Merge-Tree (LSM-Tree) > [!abstract] 概要(Abstractの日本語訳) > 高性能トランザクションシステムのアプリケーションは典型的に、活動履歴を提供するためHistory表に行を挿入すると同時に、システム回復のためのログレコードを生成する。両方の情報は効率的なインデックス付けから恩恵を受けうる。よく知られた設定での例はTPC-Aベンチマークアプリケーションであり、特定口座のアカウント活動に対する効率的なクエリをサポートするよう修正されたものである。これは急成長するHistory表に対しAccount-idによるインデックスを要求する。残念ながら、B-treeのような標準的なディスクベースのインデックス構造は、このようなインデックスをリアルタイムで維持するためにトランザクションのI/Oコストを事実上倍増させ、総システムコストを最大50パーセント増加させる。低コストでリアルタイムインデックスを維持する手法が明らかに望ましい。Log-Structured Merge-tree(LSM-tree)は、長期間にわたって高いレコード挿入(および削除)率を経験するファイルに対して低コストのインデックス付けを提供するよう設計された、ディスクベースのデータ構造である。LSM-treeはインデックス変更を遅延させバッチ化するアルゴリズムを用い、マージソートを思わせる効率的な方法で、メモリベースの成分から1つ以上のディスク成分へと変更をカスケードさせる。この過程を通じて、すべてのインデックス値は(非常に短いロック期間を除いて)常に検索可能であり、メモリ成分またはいずれかのディスク成分を通じてアクセスできる。このアルゴリズムはB-treeのような従来のアクセス手法と比較してディスクアーム移動を大幅に削減しており、従来のアクセス手法での挿入に対するディスクアームコストがストレージメディアコストを上回る領域でコスト性能を改善する。LSM-treeのアプローチは挿入・削除以外の操作にも一般化できる。しかし、即時応答を要求するインデックス検索(finds)は場合によってI/O効率を失うため、LSM-treeはインデックス挿入がエントリを検索するfindsより多いアプリケーションで最も有用である。これはHistory表やログファイルに共通する性質のようである。第6章の結論では、LSM-treeアクセス手法におけるメモリとディスク成分のハイブリッド利用を、ディスクページをメモリにバッファリングするというハイブリッド手法の一般に理解されている利点と比較する。 ## 論文情報 - タイトル: The Log-Structured Merge-Tree (LSM-Tree) - 著者: Patrick O'Neil(UMass/Boston Dept. of Math & C.S.)、Edward Cheng(Digital Equipment Corporation)、Dieter Gawlick(Oracle Corporation)、Elizabeth O'Neil(UMass/Boston Dept. of Math & C.S.) - 媒体: Acta Informatica 33, pp. 351-385(1996年6月)。DOI: 10.1007/s002360050048(Crossref で確認。本文自体には "To be published: Acta Informatica" とのみ記載され、本文の分析は1995年時点のディスク/メモリ価格に基づく)。 - 先行技術報告: UMass/Boston Math & CS Dept Technical Report 91-6(1991年11月、参考文献[19]) ## 概要 LSM-tree(Log-Structured Merge-Tree)は、insert(および delete)率が find 率を大きく上回るファイルに低コストのインデックス付けを提供するために設計されたディスクベースのデータ構造である。メモリ常駐の小さな成分 C0 とディスク常駐のより大きな成分 C1(以降)からなり、C0 が閾値サイズに達するたびに rolling merge と呼ばれる過程が C0 と C1 の間でマージソートに似た方式でエントリを移動させる。この設計により、新規挿入はメモリ内操作のみで完結し、ディスクへの反映は多ページブロック単位のシーケンシャル I/O にバッチ化されるため、B-tree に対しディスクアームコストを大幅に削減できる。 ## 問題設定 TPC-A ベンチマークを修正した設定(Example 1.1・1.2)を題材とする。1000 TPS のトランザクションシステムが、Account-ID・Branch-ID・Teller-ID・Delta・Timestamp を持つ 50 バイトの行を History 表へ書き込み続ける。Account-ID と Timestamp を結合したキーで History 表にインデックスを張ろうとすると、20 日間の蓄積で 5億7600万エントリ(9.2 GBytes、約 230 万ページ)に達する。Account-ID は一様ランダムに選ばれるため、B-tree では新規エントリの挿入位置がインデックス全体にランダムに分布し、Five Minute Rule(60 秒に一度未満しか参照されないページはメモリバッファに常駐させても得しない、という基本原則。詳細は[[Five Minute Rule]])により、このインデックスの葉ページはメモリ常駐にできない。結果として挿入 1 件あたり最低 2 回のランダム I/O(読み込み 1 回・書き出し 1 回)が発生し、Account 表更新に必要な I/O 量をほぼ倍増させ、システム総コストを最大 50% 押し上げる。 ## 提案手法 - **アーキテクチャ**: 2成分の基本形では、メモリ常駐の C0 木(任意の平衡木、例えば (2-3)木や AVL木でよい。ディスク上に存在しないため CPU 効率のためにディスクページサイズへ合わせる必要がない)と、ディスク常駐の C1 木(B-tree に類似した構造だが、ルート直下から下の全レベルでノードを 100% 満杯にし、隣接する単一ページノードを 256 KByte の多ページブロックへ詰め込んでシーケンシャルアクセスに最適化している。この最適化は SB-tree [21] でも使われている)からなる(Figure 2.1)。 **Figure 2.1: 2成分LSM-treeの模式図** ![[_attachments/The-Log-Structured-Merge-Tree-LSM-Tree/fig01-two-component-lsm-tree.png]] (Figure 2.1. C0木(メモリ常駐)とC1木(ディスク常駐)からなる2成分LSM-treeの概念図。C1がC0より大きな三角形で描かれ、ディスク/メモリの境界が明示される。) 新規 History 行が生成されるたびに、まず回復用のログレコードがシーケンシャルログファイルへ書かれ、続いてそのインデックスエントリがメモリ常駐の C0 木へ挿入される(この挿入はI/Oコストを持たない)。検索はまず C0、次に C1 の順で行う。C0 がクラッシュ時に失われても、シーケンシャルログを論理ログとして再生することで C0 の内容を再構築できる(回復は§4で詳述)。 - **rolling merge アルゴリズム**: C0 が閾値サイズに達すると、C0 の連続した(左端から始まる)エントリ区間を削除し C1 へマージする rolling merge が進行する。C1 の多ページブロック(leaf ノードを含む)を読み込んで "emptying block" とし、そこから読み出した leaf ノードと C0 の leaf レベルのエントリをマージして新しい leaf ノードを作り、別の多ページブロック("filling block")へ左から右へ順に詰めていく。filling block が満杯になると新しいディスク領域へ書き出される(古いブロックは上書きせず、クラッシュ回復のため保持する)。マージステップは C0 と C1 の最小値側から最大値側へ向けて繰り返し進み、最大値に達すると再び最小値から始まる循環(circulation)を行う(Figure 2.2)。 **Figure 2.2: rolling mergeの概念図** ![[_attachments/The-Log-Structured-Merge-Tree-LSM-Tree/fig02-rolling-merge.png]] (Figure 2.2. C1木とC0木それぞれの一部が円で囲まれ、マージ結果が新しい多ページブロックとして右側のディスク領域へ書き出される様子を示す。矢印は削除される旧ノードから新しいマージ結果ノードへの対応を表す。) - **多成分への一般化**: 2成分では C0/C1 比を大きく保つほどマージのバッチ効率(パラメータ M、後述)が上がるが、C0 を大きくするとメモリコストが増える。この最適化問題を緩和するため、C0(メモリ)・C1・C2・…・CK(ディスク、サイズ増加順)からなる K+1 成分 LSM-tree に一般化できる。隣接成分ペア (Ci-1, Ci) の間でそれぞれ非同期の rolling merge が走り、小さい方の成分が閾値を超えるたびにエントリを大きい方へ移動させる(Figure 3.1、K+1成分版)。 **Figure 3.1: K+1成分LSM-tree** ![[_attachments/The-Log-Structured-Merge-Tree-LSM-Tree/fig04-k-plus-1-component-lsm-tree.png]] (Figure 3.1. C0(メモリ)からC1, ..., CK(ディスク、サイズ増加順)へ"merge"の矢印が連なる図。全体としてサイズが幾何級数的に増加する成分の連鎖を示す。) - **find・delete・update・long-latency find**: exact-match find や range find は C0 から順に各成分の索引構造を辿る必要があるが、タイムスタンプの一意性が保証される場合や直近の値のみを対象とする場合は早い段階の成分だけで完了できる最適化がある。delete は C0 に delete node entry(削除対象の RID を記録)を挿入し、rolling merge 中に実際のエントリと出会った時点で両者を相殺(annihilate)する遅延削除として実装される。update は delete+insert として扱う。さらに predicate deletion(述語を満たすエントリをマージ通過時に一括で捨てるバッチ削除)と long-latency find(find note entry を C0 に挿入し、最も遅いカーソルの循環周期にわたって結果を蓄積する遅延応答検索)という2種類の追加操作も提案されている。 ## 新規性 既存のディスクベースアクセス手法(B-tree・SB-tree・Bounded Disorder File・extendible hashing 等)はほぼすべて「Continuum Structure」である、と本論文は定義する(Definition 5.1)。Continuum Structure とは、新規挿入エントリを他の全エントリとの最終的な照合順序上の位置に即座に配置するインデックス方式を指す。Continuum Structure では挿入位置がインデックス全体にランダムに分布するため、Five Minute Rule により葉ページをメモリ常駐にできず、挿入ごとに最低2回のランダムI/O(読み込みと書き出し)を要する。 TSB-tree [17][18]・MD/OD R-tree [15]・Differential File [25] は、いずれもエントリを1つのセグメントから別のセグメントへ移行させる非Continuum構造だが、いずれも「移行元の成分をメモリ常駐に保証する」設計を欠く。TSB-tree の current tree はディスク常駐として提示され、MD/OD R-tree の current (MD R-tree) もディスク常駐、Differential File もメモリ常駐化は「示唆される」に留まり体系的に扱われていない。LSM-tree はこの2要因(C0のメモリ常駐保証と、慎重に遅延された配置)を明示的に組み合わせることで、これらの先行手法にない性能保証を得る。 ## 性能分析(Cost-Performance) ### ディスクモデルとデータ温度 本論文はディスクコストを COSTd(1 MByteあたりのディスク媒体コスト)、COSTm(1 MByteあたりのメモリコスト)、COSTP(ランダムページ1件/秒のI/Oレート提供に必要なディスクアームコスト)、COSTπ(多ページブロックI/Oの一部としての同コスト)の4つでモデル化する。ある量のデータ S MBytes に対する総アクセスコストは次で与えられる。 ``` COST-TOT = min(max(S・COSTd, H・COSTP), S・COSTm + S・COSTd) ``` ここで H はランダムページアクセス率。この式から、アクセス頻度 H/S(「データ温度」)に応じて cold(ディスク媒体コストが支配的)・warm(ディスクアームコストが支配的)・hot(メモリコストが支配的、Five Minute Rule によりメモリバッファ常駐が正当化される領域)の3領域に分かれることが導かれる(Figure 3.1、温度グラフ)。 **Figure 3.1: アクセス温度とコストの関係** ![[_attachments/The-Log-Structured-Merge-Tree-LSM-Tree/fig03-cost-vs-temperature.png]] (Figure 3.1. 横軸を温度H/S(accesses/sec/Mbyte)、縦軸をCOST-TOT/MByteとし、Cold Data(定数)→Warm Data(傾斜)→Hot Data(平坦)の3領域を示す。境界点は freezing point Tf = COSTd/COSTP、boiling point Tb = COSTm/COSTPとして定義される。) 1995年時点の典型的なワークステーション価格例として、COSTm=$100/MByte、COSTd=$1/MByte、COSTP=$25/(IOs/sec)、COSTπ=$2.5/(IOs/sec)が示され、Tf=0.04、Tb=4 IOs/(sec・MByte)と算出される。多ページブロックI/Oの優位性(COSTπ/COSTP ≈ 1/10)は、1989年のIBM DB2ユーティリティ性能分析(単一ページ読み込み約20msに対し64ページの連続プリフェッチ読み込みは約2ms/ページ)と、SCSI-2ディスクの分析(単一4KBページ読み込み16msに対し64ページ連続読み込み約1.5ms/ページ)の両方から裏付けられる。 ### LSM-treeとB-treeの挿入コスト比較 B-tree への1挿入のコストは、実効深さ De(ランダムキー値検索でバッファに見つからない平均ページ数、Example 1.2規模のB-treeでは典型的に約2)を用いて次式で与えられる。 ``` COST(B-ins) = COSTP・(De + 1) ... (3.1) ``` LSM-treeの挿入コストは、C0からC1のleafノードへ1回のI/Oでマージされるエントリ数の平均を表すバッチマージパラメータ M(Definition 3.2.1)を用いて次式で与えられる。 ``` M = (Sp/Se)・(S0/(S0+S1)) ... (3.2) COST(LSM-ins) = 2・COSTπ/M ... (3.3) ``` ここで Se はエントリサイズ、Sp はページサイズ、S0・S1 はそれぞれ C0・C1 の leaf レベルサイズ。典型例として S1=40・S0、Sp/Se=200 のとき M=5 になる。両コストの比は ``` COST(LSM-ins)/COST(B-ins) = K1・(COSTπ/COSTP)・(1/M) ... (3.4) ``` K1 = 2/(De+1) ≈ 0.67 とすると、2つの比 COSTπ/COSTP と 1/M の積により、典型的にはほぼ2桁のコスト改善が得られると論じる。 ### 多成分の最適サイズ比(Theorem 3.1・3.2) K+1成分のLSM-treeにおいて、最大成分サイズ SK・メモリ成分サイズ S0・挿入率 R を固定したとき、全マージ処理に必要な総ページI/Oレート H を最小化する成分サイズ比 ri = Si/Si-1(i=1..K)は、全ての ri が単一の定数 r に等しいときに最小化される(Theorem 3.1)。このとき ``` S = S0 + r・S0 + r²・S0 + ... + rK・S0 ... (3.5) H = (2R/Sp)・(K・(1+r) - 1/2) ... (3.6) ``` 総サイズ S を固定した場合(Theorem 3.2)は Lagrange 乗数法によるやや複雑な漸化式 rK-1=rK+1, rK-2=rK-1+1/rK-1, ... が導かれるが、実用上の r 値(20以上)では両者の近似は近い。 コスト最小化では、相対コスト C = COSTtot/(COSTd・S1) が正規化温度 t と正規化メモリ量 s の関数として C ≈ s + max(1, t/s) で近似され、t ≥ 1(暖かい領域)では最小コストが ``` COST(min) = 2・[(COSTm・S1)・(2・COSTπ・R/Sp)]^(1/2) ... (3.8) ``` というメモリコストとディスクI/Oコストの幾何平均の2倍になることが示される。t が大きくなるにつれ総コストは R の平方根に比例して増加するのに対し、B-tree では R に線形比例するため、挿入率が高いワークロードほどLSM-treeの優位性が拡大する。 ### 数値例(Example 3.3・3.4) Account-ID||Timestamp インデックス(挿入率 R=16,000 バイト/秒、9.2 GBytes)に対し、B-tree の総コストは $56,400(ディスクI/O $50,000 + ディレクトリバッファ用メモリ $6,400)と算出される。同じワークロードに対する2成分LSM-treeの総コストは $11,400(ディスク $9,200 + メモリ $2,200)で、r=460(C1がC0の460倍)、C0=20 MBytesという構成が最適となる。挿入率を10倍(R=160,000バイト/秒)にすると、B-treeコストは$506,400へ増加する一方、2成分LSM-treeは$27,200、3成分LSM-tree(r=23、S0=17 MBytes)ではさらに$11,300まで下がる。成分数が増えるほど S0 は小さくなるが、r が e≈2.71 に近づく、または冷データ領域に達すると、成分追加による改善は逓減する。実務上は3成分程度が現実的な上限になると論じられている。 ## 並行性制御と回復(§4) LSM-tree のノードは B-tree と同様の階層構造を持つが、ディレクトリの下位レベルは複数ノードが多ページブロックへまとめられている点が異なる。並行性制御はノード単位のロックで実現され、rolling merge によって更新中のノードは write ロック、find による読み取り中のノードは read ロックで保護される。3種類の物理的競合を回避する必要がある:(i) find がロールマージ中のノードを読まないこと、(ii) C0 への find/insert がロールマージによる変更と衝突しないこと、(iii) 内側成分(Ci-1→Ci)のカーソルが外側成分(Ci→Ci+1)のカーソルを追い越せること。emptying block と filling block という2種類のバッファ済み多ページブロックの概念を用い、ノードが完全に空になるたびにロックを解放することで、より速いカーソルが遅いカーソルを追い越せるようにしている。 回復は、新規挿入行のトランザクションログ(既存のシーケンシャルログファイル)を論理ログとして再利用する設計を取る。チェックポイント時には (1) C0 の内容を既知のディスク位置へ書き出し、(2) 全ディスク成分のダーティな多ページブロックをフラッシュし、(3) 最終挿入行のLSN・全成分のルートアドレス・全マージカーソル位置・多ページブロック動的割当情報を記録したチェックポイントログを作成する。クラッシュ後はこのチェックポイントから復元し、LSN以降のログを再生してC0へ再挿入することでrolling mergeが自動的に未完了分を再実行する。新しいマージ結果は常に新しいディスク位置へ書かれる(上書きしない)ため、チェックポイント以降のクラッシュでも旧情報が失われない。 ## 競合手法との比較(§5) - **Time-Split B-tree(TSB-tree)[17][18]**: タイムスタンプとキー値の2次元で分割する構造。current node set は移行元成分としてディスク常駐で提示され、メモリ常駐化の保証がない。挿入性能改善を意図した設計ではない。 - **MD/OD R-tree [15]**: 磁気ディスク(MD)と光ディスク(OD)にまたがるR-tree変種。Vacuum Cleaner Process (VCP) が閾値超過時に古いleafページをアーカイブ側(光ディスク)へ移す。[15]のシミュレーション(Figure 4)では、挿入あたりの平均読み込みページ数が両変種(MD/OT-RT-1, MD/OT-RT-2)とも2を下回ることはない、と本論文は指摘する。 - **Differential File [25]**: メインファイルとは別のオーバーフロー領域(Differential File)へ変更を蓄積し、後で本体へ統合する方式。差分-差分ファイルをメモリキャッシュに保持するアイデアが§3.4で示唆されるが、詳細な分析はなく、常時メモリ常駐を保証する設計にはなっていない。 - **選択的遅延テキストインデックス更新 [7]**: テキストインデックスの更新をメモリにキャッシュし、クエリとの競合またはバックグラウンドタスクでディスクへ反映する方式。メモリキャッシュは正式なインデックスの一部ではなく、更新パターンはなお Continuum Structure に近い。 いずれの先行手法も「移行元成分のメモリ常駐保証」を欠くため、LSM-treeのような挿入コスト削減効果は得られない、というのが本論文の中心的主張である。 ## 考察・結論(§6) B-treeはディレクトリノードをメモリにバッファすることで、ディスク媒体の低コストとメモリの高いアクセス性を組み合わせるハイブリッド構造である。LSM-treeはこの階層をさらに拡張し、マージI/Oの効率(多ページシーケンシャルディスク読み込み)を組み込んだものと位置づけられる。Figure 3.1を Insert Temperature 軸で拡張した Figure 6.1 では、LSM-tree(K=1)がB-treeに比べ「論理的な挿入率(inserts/sec)」では hot でも「物理的なディスクアクセス率」では warm 相当に留まる効果が示される。 **Figure 6.1: 挿入温度とコストの比較(B-tree vs LSM-tree)** ![[_attachments/The-Log-Structured-Merge-Tree-LSM-Tree/fig05-cost-vs-insert-temperature.png]] (Figure 6.1. Figure 3.1を拡張し、B-treeの折れ線(Hot Dataで平坦化)とLSM-tree K=1の折れ線(Insert Temperatureが上がってもコストの伸びが緩やか)を対比。B-treeはメモリバッファリングによりHot Data領域でコストの傾きが平坦化するが、LSM-treeはmergeable操作(insert・delete)についてより広い温度範囲でコストをcold data寄りに抑える。) ### 拡張の提案 - LSM-treeのエントリ自体にレコード本体を格納し、RIDによる間接参照を避けてキー値でクラスタリングする拡張(エントリサイズ増大とのトレードオフ)。 - Escrowトランザクション方式 [20] のログを Transaction ID と Field ID の2種類のキーでクラスタリングする用途への応用(コミット時はTID順、アボート処理時はFID順に読み替える)。 - 直近τi秒のエントリを成分Ci内に留め、時刻キーインデックス(TSB-tree的な構造)を生成する変種。この方向性は後続の会議論文 [22](LHAM)で扱われている。 - find操作の負荷とマージI/Oの負荷を同時にバランスさせるコスト解析の拡張。 - CPUオフロード(ログ生成側と別のCPUでLSM-tree維持を行う分散設計)。 ## 強み / 弱点・課題 **強み** - insertが支配的なワークロード(History表・ログファイル)において、B-treeに対し最大2桁のディスクアームコスト削減を数学的導出とともに示す。 - 2成分・多成分いずれについても最適構成サイズを閉形式(Theorem 3.1・3.2)で導出しており、設計時のパラメータ選択に直接使える。 - rolling merge・checkpoint・ロック粒度など、実装可能な水準まで並行性制御と回復の設計を具体化している。 **弱点・課題** - 即時応答を要するfind操作は、成分数が増えるほど追加I/O(成分あたり最大1回)が必要になり、find中心のワークロードには不向きである。 - 並行性・回復アルゴリズムの形式的正当性の証明は「今後の課題」として明示的に先送りされている。 - 高レベルディレクトリノードのバッファリング戦略やCPUオフロード設計など、複数の拡張が具体的な実装や評価を伴わない提案に留まっている。