構造的アルゴリズム

論文翻訳: The Log-Structured Merge-Tree (LSM-Tree)

Takami Torao 1996年の論文 #LSMTree
  • このエントリーをはてなブックマークに追加
Patrick O'Neil 1 , Edward Cheng 2
Dieter Gawlick 3 , Elizabeth O'Neil 1
To be published: Acta Informatica

Abstract

高性能なトランザクションシステムアプリケーションは、通常、アクティビティトレースを提供するために履歴テーブルに行を挿入し、同時にトランザクションシステムはシステム回復のためのログレコードを生成する。どちらのタイプの情報生成も効率的なインデックス生成の恩恵を受けることができる。よく知られている例としては、特定のアカウントのアカウントアクティビティに関する履歴の効率的なクエリーをサポートするように変更した TPC-A ベンチマークアプリケーションがある。これには急速に拡大する履歴テーブルにアカウント ID によるインデックスを必要とする。しかし残念ながら B-Tree のような標準的なディスクベースのインデックス構造では、リアルタイムでこのようなインデックスを維持するためにトランザクションの I/O を実質的に 2 倍にし、システム全体のコストを最大 50% まで増加させる。リアルタイムインデックスを低コストで維持する方法が望ましいことは明らかである。LSM-Tree (Log-Structured Merge-Tree) は長期間にわたってレコードの挿入 (および削除) が頻繁に行われるファイルに対して、低コストのインデックスを提供するために設計されたディスクベースのデータ構造である。LSM-Tree はインデックス変更を延期しバッチ処理するアルゴリズムを使用して、マージソートを彷彿とさせる効率的な方法でメモリベースのコンポーネントから 1 つ以上のディスクコンポーネントにカスケードする。このプロセスの間、すべてのインデックス値はメモリコンポーネントまたはディスクコンポーネントのいずれかを介して (非常に短いロック期間を除き) 継続的に検索アクセスすることができる。このアルゴリズムは B-Tree のような従来のアクセス方法と比較し、ディスクアームを移動を大幅に削減し、従来のアクセス方法による挿入のためのディスクアームコストがストレージメディアコストを圧倒するような領域でのコストパフォーマンスを改善する。LSM-Tree のアプローチは挿入と削除の操作以外にも一般化される。しかし即時応答を必要とするインデックス検索では場合によって I/O 効率を低下させるため、エントリを取得する検索よりもインデックス挿入の方が一般的なアプリケーションでは LSM-Tree が最も有用である。セクション 6 の結論では、LSM-Tree アクセス方式におけるメモリとディスクコンポーネントのハイブリッド利用と、一般に理解されているディスクページをメモリにバッファリングするハイブリッド方式の利点を比較している。

Table of Contents

  1. Abstract
  2. 1. 導入
    1. 5 分ルール
  3. 2. 2-コンポーネント LSM-Tree アルゴリズム
    1. 2.1 2-コンポーネント LSM-Tree の成長過程
    2. 2.2 LSM-Tree インデックスでの検索
    3. 2.3 LSM-Tree における削除、更新、および長時間の遅延を伴う検索
  4. 3. コストパフォーマンスと複数コンポーネントの LSM-Tree
    1. 3.1 ディスクモデル
      1. 複数ページブロック I/O の利点
    2. 3.2 LSM-Tree と B-Tree の I/O コスト比較
      1. B-Tree 挿入コストの計算式
      2. LSM-Tree 挿入コストの計算式
      3. LSM-Tree と B-Tree の挿入コスト比較
    3. 3.3 複数コンポーネント LSM-Tree
    4. 3.4 LSM-Tree: コンポーネントサイズ
      1. Minimizing Total Cost
  5. 4. Consistency and Recovery in the LSM-tree
    1. 4.1 Concurrency in the LSM-tree
    2. 4.2 Recover in the LSM-tree
  6. 5. Cost-Performance Comparison with Other Access Methods
    1. Time-Split B-tree
    2. MD/OD R-Tree
    3. Differential File
    4. Selective Deferred Text Index Updates
  7. 6. Conclusions and Suggested Extensions
    1. 6.1 Extensions of LSM-tree Application
  8. Acknowledgements
  9. References
  10. 翻訳抄
  1. 1Dept. of Math & C.S, UMass/Boston, Boston, MA 02125-3393, {poneil | eoneil}@cs.umb.edu
  2. 2Digital Equipment Corporation, Palo Alto, CA 94301, edwardc@pa.dec.com
  3. 3Oracle Corporation, Redwood Shores, CA, dgawlick@us.oracle.com

1. 導入

アクティビティフロー管理システムにおける長寿命トランザクションが商用利用可能になるにつれ ([10], [11], [12], [20], [24], [27]) トランザクションログ記録へのインデックス付きアクセスを提供する必要性が高まるだろう。従来のトランザクションログは中断と回復に重点を置いており、回復はバッチ化されたシーケンシャルリードで実行され、システムは時折トランザクションロールバックが発生する通常の処理において、比較的短期間の履歴を参照する必要があった。しかしシステムがより複雑なアクティビティを担当するようになると 1 つの長期的なアクティビティを構成するイベントの期間と数が増加し、何が完了したかをユーザに思い出させるために過去のトランザクションステップをリアルタイムで確認する必要性が生じることがある。同時に、システムが認識するアクティブなイベントの総数は、メモリコストの継続的な低下が予想されるにもかかわらず、現在アクティブなログを追跡するために使用されているメモリ常駐データ構造がもはや現実不可能なレベルまで増加する。膨大な数の過去のアクティビティログに関するクエリーに応答する必要性は、インデックス化されたログアクセスがますます重要となることを意味する。現在のトランザクションシステムにおいても総乳量の多い履歴テーブルに対するクエリーをサポートするためにインデックスを提供することには明らかな価値がある。ネットワーク、電子メール、およびその他のほぼトランザクショナルなシステムは、多くの場合、ホストシステムに悪影響を与える膨大なログを生成する。具体的でよく知られた例から始めるために次の例 1.1 および 1.2 で TPC-A ベンチマークを改良したものを検討する。この文書で提示する例は説明を簡単にするために特定の数値パラメータ値を扱っていることに注意。履歴テーブルとログの両方に時系列データが含まれるが、LSM-Tree のインデックスエントリは時間的なキー順序が同一であるとは想定されていないことにも注意。効率を向上するための唯一の前提は、検索レートに比べて更新レートが高いことである。

5 分ルール

次の 2 つの例はどちらも 5 分ルール [13] に基づいている。この基本的な結果は、ページ参照頻度が約 60 秒に 1 回を超える場合、メモリバッファ領域を購入してページをメモリに保持しディスク I/O を回復することでシステムコストを削減できるというものである。60 秒という時間は、1 秒あたり 1 回の I/O を提供するディスクアームの償却コストと、1 秒で償却される 4kB のディスクページをバッファリングするためのメモリコストの比率である。セクション 3 の表記法では、この比率は COSTP / COSTM をメガバイト単位のページサイズで割ったものである。ここでは単にディスクアクセスとメモリバッファをトレードオフしているだけだが、メモリ価格はディスク価格より早く低下することから、60 秒の時間幅は年々大きくなることが予想されることに注意。1987 年に 5 分と定義されたときよりも 1995 年の現在の方が短くなっている理由は、一部には技術的な理由 (バッファリングの想定が異なる) であり、一部はその後に非常に安価な大量生産ディスクが導入されたことに依るものである。

例 1.1. TPC-A ベンチマーク [26] で想定される、1 秒あたり 1000 県のトランザクションを実行するマルチユーザアプリケーションを考える (このレートはスケール可能だが以下は 1000TPS のみを考える)。各トランザクションは、任意に選択された 100 バイトの行 Balance カラムから金額 Delta を引くことでカラムを更新し、次に 1000 行の Branch テーブル、10,000 行の Teller テーブル、100,000,000 行の Account テーブルの 3 つのテーブルそれぞれから行を選ぶ。トランザクションは次に Account-ID, Branch-ID, Teller-ID, Delta, Timestamp を含む 50 バイトの行を History テーブルに書き込んでからコミットする。

ディスクとメモリのコストを予測する一般的な計算の結果、Account テーブルのページは今後数年間はメモリに常駐することは無く (参考文献 [6] 参照)、一方で Branch テーブルと Teller テーブルは現時点で完全にメモリ常駐になるはずである。与えられた仮定の下では Account テーブルの同一ディスクページへの繰り返し参照は約 2,500 秒間隔で行われ、5 分ルールによるバッファ常駐を正当化するために必要な頻度を遙かに下回る。ここで各トランザクションは約 2 回のディスク I/O を必要とし、1 回は目的の Account レコードを読み込むため (アクセスしたページが既にバッファ内にあるという希なケースは重要で無いと見なす)、もう 1 回はバッファに読み込み用のスペースを確保するために以前のダーティな Account ページを書き出すため (定常の動作に必要) である。従って 1000 TPS は毎秒約 2000 回の I/O に相当する。これは [13] で想定されているディスクアーム 1 秒あたり 25 I/O の公称レート 80 個のディスクアーム (アクチュエータ) を必要とする。それ以降の 8 年間 (1987 年から 1995 年まで) で速度は年間 10% 未満の割合で上昇し、公称レートは現在 1 秒あたり約 40 I/O、つまり 1 秒あたり 2000 I/O に対して 50 ディスクアームとなっている。TPC アプリケーションのディスクコストは [6] ではシステムの総コストの約半分と計算されているが IBM のメインフレームシステムではいくらか低くなる。しかしメモリと CPU のコストはディスクよりも急速に低下するため、I/O をサポートするためのコストは明らかにシステムの総コストの増加要因となっている。

例 1.2. 次に、挿入量の多い History テーブルのインデックスを検討し、このようなインデックスによって TPC アプリケーションのディスクコストが実質的に 2 倍になることを示す。History の「Timestamp と連結された Account-ID」(Acct-ID || Timestamp) のインデックスは、次のような最近のアカウントアクティビティに対する効率的なクエリーをサポートするために非常に重要である:

(1.1) Select * from History
    where History.Acct-ID = %custacctid
    and History.Timestamp > %custdatetime;

Acct-ID || Timestamp がインデックスが存在しない場合、このようなクエリーでは History テーブルのすべての行を直接検索する必要があるため現実的ではない。Acct-ID のインデックスのみでもほとんどの利点が得られるが Timestamp が省略されても後に続くコストの考慮は変わらないため、ここではより有用な連結インデックスを仮定する。このようなセカンダリ B-Tree インデックスをリアルタイムで維持するにはどのようなリソースが必要だろうか。B-Tree のエントリは毎秒 1000 件生成され、20 日間の累積機関、1 日 8 時間、16 バイトのインデックスエントリを想定すると、9.2GB のディスクに 576,000,000 エントリ、またインデックスリーフページで約 230 万ページが必要となる。トランザクションの Acct-ID 値はランダムに選択されるため、各トランザクションではこのインデックスから少なくとも 1 ページを読み込む必要があり、定常状態ではページの書き込みも必要となる。5 分ルールではこれらのインデックスページはバッファに常駐しない (ディスクページは約 2300 秒間隔で読み取られる) ため、すべての I/O はディスクに対して行われる。既にアカウントテーブルの更新に必要な 2000 I/O に加えてこの毎秒 2000 の I/O を追加するには、さらに 50 本のディスクアームを追加購入する必要がありディスク要件は 2 倍になる。この考えは、ログファイルのインデックスを 20 日間だけ維持するために必要な削除は、利用が少ない時間帯にバッチジョブとして実行できると楽観的に想定している。

履歴ファイルの Acct-ID || Timestamp インデックスに B-Tree を考慮したのは、それが商用システムで使用される最も一般的なディスクスペースのアクセス方法であり、実際、古典的では一貫して優れた I/O コスト・性能が得られるディスクインデックス構造は無いためである。この結論に至った考察についてはセクション 5 で述べる。

この論文で紹介する LSM-Tree のアクセス方法は、ディスクアームの使用を大幅に減らして Account-ID || Timestamp インデックスの頻繁な頻繁なインデックス挿入を実行できるためコストが桁違いに低くなる。LSM-Tree はインデックス変更を延期 (defer) しバッチ処理 (batch) するアルゴリズムを使用する、マージソートを彷彿とさせる特に効率的な方法で変更をディスクに移行する。セクション 5 で説明するように、インデックスエントリの配置を最終的なディスク位置まで延期する機能は基本的に重要であり、一般的な LSM-Tree ではこのような延期された配置がカスケード状に連続している。LSM-Tree 構造は削除、更新、および長い待ち時間 (long latency) の検索操作など、インデックス作成の他の操作も同じ遅延効率でサポートする。即時の応答を必要とする検索のみが比較的コストの高いままである。LSM-Tree が効率的に使用される主な領域は、例 1.2 のような検索が挿入よりもはるかに少ない頻度で行われるアプリケーションである (ほとんどの人は、小切手を書いたり預金をしたりするのと同じくらいの頻度で最近のアカウントアクティビティを尋ねることはない)。このような状況ではインデックス挿入のコストを削減することが最も重要である。同時に、すべてのレコードを逐次検索することは問題外であるため、頻繁な検索アクセスを行うために何らかのインデックスを維持する必要がある。

この論文の計画は次の通り。セクション 2 では 2-コンポーネント LSM-Tree アルゴリズムを紹介する。セクション 3 では LSM-Tree の性能を分析し、マルチコンポーネント LSM-Tree の動機づけを説明する。セクション 4 では LSM-Tree の平行性と回復性の概念を概説する。セクション 5 では競合するアクセス方法とその性能について検討する。セクション 6 の結論では LSM-Tree のいくつかの意味を評価し拡張のための多くの提案を示す。

2. 2-コンポーネント LSM-Tree アルゴリズム

LSM-Tree は 2 つ以上のツリー状のコンポーネントデータ構造で構成される。このセクションでは単純な 2 つのコンポーネントでのケースを扱う。以下では例 1.2 のように LSM-Tree が History テーブルの行をインデックス付けしていると仮定する。以下の Figure 2.1 参照。

2-コンポーネント LSM-Tree には C0 ツリー (または C0 コンポーネント) と呼ばれる完全にメモリ常駐の小さなコンポーネントと、C1 ツリー (または C1 コンポーネント) と呼ばれるディスク常駐の大きなコンポーネントがある。C1 コンポーネントはディスク常駐だが、C1 内の頻繁に参照されるページノードは通常通りメモリバッファに残る (バッファは図示されていない) ため、C1 の人気上位ディレクトリノードはメモリ常駐であることが期待できる。

Figure 2.1. 2-コンポーネント LSM-Tree の概略図。

新しい History 行が生成されるたびに、まず、この挿入を回復するためのログレコードが通常の方法で逐次ログファイルに書き込まれる。次に History 行のインデックスエントリがメモリ常駐の C0 ツリーに挿入され、その後にディスク上の C1 ツリーに移行する。インデックスエントリの検索は、最初に C0 で検索して次に C1 で検索する。C0 ツリーのエントリがディスク常駐の C1 `ツリーに移行するまでにはある程度の待ち時間 (遅延) があり、これはクラッシュ前にディスクに書き込まれなかったインデックスエントリの回復の必要性を示唆している。回復についてはセクション 4 で説明するが、ここでは History 行の新規挿入を回復できるログレコードを論理ログとして扱うことだけを述べておく。回復中は、挿入された History 行を再構築し、同時に C0 の失われた内容を取り戻すためにこれらの行のインデックスに必要なエントリを再作成することができる。

インデックスエントリをメモリ常駐の C0 ツリーに挿入する操作には I/O コストがかからない。ただし C0 コンポーネントを格納するメモリ容量のコストはディスクに比べて高く、このためサイズが制限される。エントリを低コストのディスクメディアにある C1 ツリーに移行する効率的な方法が必要である。これを実現するには、挿入の結果として C0 ツリーが割り当てられた最大値に近いしきい値サイズに達するたび、継続的なローリングマージ (rolling merge) プロセスが C0 ツリーからエントリの連続セグメントを削除してディスク上の C1 ツリーにマージする。Figure 2.2 にローリングマージプロセスの概念図を示す。

Figure 2.2. 結果をディスクに書き戻すローリングマージステップの概念図

C1 ツリーは B-Tree と同様のディレクトリ構造を持つが、シーケンシャルディスクアクセスに最適化されており、ノードは 100% 満たされ、ルート以下の各レベルのシングルページノードのシーケンスは効率的なアーム使用のために連続した複数ページディスクブロックにまとめられている。この最適化は SB-Tree [21] でも使用されている。複数ページブロック I/O はローリングマージ中と長距離 (long range) 検索に使用され、単一ページノードはバッファリング要件を最小化するためにインデックス付き検索のマッチングに使用される。256kB の複数ページブロックサイズはルート以下のノードを含むように想定されている。ルートノードは定義により常に 1 ページである。

ローリングマージは一連のマージステップで実行される。C1 ツリーのリーフノードを含む複数ページのブロックを読み取ると C1 バッファ内のエントリの範囲が常駐する。その後、各マージステップでは、このブロックにバッファされている C1 ツリーのディスクページサイズのリーフノードを読み取り、リーフノードのエントリを C0 ツリーのリーフレベルから取得したエントリとマージすることで C0 のサイズを縮小し、C1 ツリーの新しくマージされたリーフノードを作成する。

マージ前の古い C1 ツリーノードを含むバッファリングされたマルチページブロックは空ブロック (emptying block) と呼ばれ、新しいリーフノードは充填ブロック (filling block) と呼ばれる別のバッファリングされたマルチページブロックに書き込まれる。この充填ブロックが C1 の新しくマージされたリーフノートでいっぱいになると、ブロックは新しい空き領域に書き込まれる。Figure 2.2 では、マージされた結果を含む新しいマルチページブロックは以前のノードの右側にあるように示されている。後続のマージステップでは C0 および C1 コンポーネントの増加するインデックス値セグメントをまとめ、最大値に達するとローリングマージが最小値から再び開始される。

新しくマージされたブロックは新しいディスク位置に書き込まれるため、古いブロックは上書きされずクラッシュした場合のリカバリに利用できる。メモリにバッファリングされた C1 の親ディレクトリノードもこの新しいリーフ構造を反映するように更新されるが、通常は I/O を最小限に抑えるためにバッファ内に長時間残る。C1 コンポーネントの古いリーフノードはマージステップの完了後に無効化され C1 ディレクトリから削除される。一般に、古いリーフノードが空になったタイミングでマージステップによって新しいノードが生成される可能性は低いため、各マージステップの後にはマージされた C1 コンポーネントのリーフレベルエントリが残る。一般に、充填ブロックが新しくマージされたノードでいっぱいになると、縮小ブロックにエントリを含む多数のノードが存在するため、同じ考慮点はマルチページのブロックにも当てはまる。これらの残りのエントリは更新されたディレクトリノード情報と同様にディスクに書き込まれることなくしばらくブロックメモリバッファに残る。マージステップ中の並行性と、クラッシュ時に失われたメモリからのリカバリについてはセクション 4 で詳しく説明する。リカバリ時の再構築時間を短縮するために、マージプロセスのチェックポイントが定期的に作成され、バッファリングされたすべての情報がディスクに強制的に書き込まれる。

2.1 2-コンポーネント LSM-Tree の成長過程

LSM-Tree の成長初期からその変容をたどるために、まずメモリ上の C0 ツリーコンポーネントへの最初の挿入から始めよう。C1 ツリーとは異なり C0 ツリーは B ツリーのような構造を持つことは想定されていない。まず、ノードは任意のサイズにすることができる。C0 ツリーはディスク上に置かれることがないため、ディスクページサイズのノードにこだわる必要はなく、深さを最小限に抑えるために CPU 効率を犠牲にする必要はない。したがって (2-3) ツリーや AVL ツリー (例えば [1] などで説明されている) は C0 ツリーの代替構造として考えられる。成長中の C0 ツリーがしきい値サイズに達すると、左端のエントリシーケンスが C0 ツリーから削除され (これは一度に 1 つのエントリでは無く、効率的なバッチ方式で行う必要がある)、100% フルパックされた C1 ツリーのリーフノードに再編成される。連続するリーフノードは、ブロックがいっぱいになるまでバッファ常駐の複数ページブロックの初期ページに左から右に配置される。その後、このブロックはディスクに書き出され、C1 ツリーのディスク常駐リーフレベルの最初の部分になる。連続するリーフノードが追加されるにつれて、C1 ツリーのディレクトリノード構造がメモリバッファに作成される。詳細は以下で説明する。

C0 のしきい値サイズがしきい値を超えないように、C1 ツリーのリーフレベルの連続する複数ページブロックは、増え続けるキーシーケンスの順序でディスクに書き出される。上位レベルの C1 ツリーのディレクトリノードは、合計メモリとディスクアームコストの観点からより適切な個別の複数ページブロックバッファに保持されるか単一ページバッファに保持される。これらのディレクトリノードのエントリには B ツリーのように下位の個々の単一ページノードへのアクセスを導くセパレータが含まれる。その目的は、単一ページインデックスノードのパスに沿ってリーフレベルまで効率的な完全一致アクセスを提供し、そのような場合には複数ページブロックの読み取りを回避して、メモリバッファ要件を最小限に抑えることである。したがって、ローリングマージまたは長距離検索の場合は複数ページブロックの読み取りと書き込みを行い、インデックス検索 (完全一致) アクセスの場合は単一ページノードの読み取りと書き込みを行う。このような二項対立をサポートするやや異なるアーキテクチャが [21] で紹介されている。C1 ディレクトリノードの部分的にいっぱいになった複数ページブロックは、通常、一連のリーフノードブロックが書き出される間、バッファに残すことができる。C1 ディレクトリノードは次の場合にディスク上の新しい位置に強制的に移動される:

  • ディレクトリノードを含む複数ページブロックバッファがいっぱいになる

  • ルートノードが分割され、C1 ツリーの深さが増加する (深さが 2 を超える)

  • チェックポイントが実行される

最初のケースではいっぱいになった 1 つの複数ページブロックがディスクに書き出される。後の 2 つのケースでは、すべての複数ページブロックバッファとディレクトリノードバッファがディスクにフラッシュされる。

C0 ツリーの右端の葉エントリが初めて C1 ツリーに書き出されたあと、2 つのツリーの左端から処理が最初からやり直される。ただし、この時点とそれ以降のパスでは C1 ツリーの複数ページにわたる葉レベルブロックをバッファに読み込み、C0 ツリーのエントリとマージする必要がある。これにより C1 の新しい複数ページのはブロックが生成されディスクに書き込まれる。

マージが開始すると状況はより複雑になる。2 つのコンポーネントから成る LSM-tree におけるローリングマージプロセスは、概念的なカーソルが C0 ツリーと C1 ツリーの等しいキー値を量子化されたステップでゆっくりと循環し、インデックスデータを C0 ツリーからディスク上の C1 ツリーに描画してゆくものと考えることができる。ローリングマージカーソルは C1 ツリーの葉レベルと、各上位ディレクトリレベルとに位置する。各レベルでは、C1 ツリーの現在マージ中のすべてのマルチページブロックは一般的に 2 つのブロックに分割される。これは、エントリが枯渇しているがマージカーソルがまだ到達していない情報を保持している "emptying" ブロックと、この時点までのマージの結果を反映する "filling" ブロックである。カーソルを定義する類似の "filling ノード" と "emptying ノード" が存在し、これらは確実にバッファ常駐となる。同時アクセスを目的として各レベルの emptying ブロックと filling ブロックには C1 ツリーのページサイズのノードが整数個含まれているが、これらはたまたまバッファ常駐となる。(個々のノードを再構築するマージステップの間、それらのノー土壌のエントリへの他のタイプの同時アクセスはブロックされている。) バッファリングされたすべてのノードをディスクに完全にフラッシュする必要がある場合、各レベルのバッファリングされたすべての情報をディスク上の新しい位置に書き込む必要がある (位置は上位ディレクトリ情報に反映され、回復のために順次ログエントリが作成される)。後になって C1 ツリーの特定のレベルのバッファ内の filling ブロックがいっぱいになり再度フラッシュする必要がある場合は新しい位置に書き込まれる。回復中に必要となる可能性のある古い情報がディスク上で上書きされることは決してなく、より最新の情報で新しい書き込みが成功したときにのみ無効化される。ローリングプロセスのより詳細な節目は、同時実行性と回復設計について検討するセクション 4 で示されている。

LSM-Tree の効率性に関する重要な考慮事項は、C1 の特定のレベルにおけるローリングマージプロセスが比較的高い割合でノードを通過するときに、すべての読み取りと書き込みが複数ページのブロックで行われることである。シーク時間と回転待ち時間を排除することで、通常の B-Tree エントリの挿入に伴うランダムページ I/O に比べて大きな利点が得られると期待されている。(この利点については以下のセクション 3.2 で分析する。) 常に新しい場所に複数ページブロックを書き込むというアイディアは Rosenblum と Ousterhout [23] が考案したログ構造ファイルシステム (Log-Structured File System) から着想を得たもので、ログ構造マージツリー (Log-Structured Merge-Tree) という名称もそこに由来している。新しいディスク領域を継続的に使用して新しい複数ページブロックを書き込むと、書き込まれているディスクが巻き戻され、古い破棄されたブロックを再利用しなければならないことに注意。この記録 (bookkeeping) はメモリテーブルで実行できる。古い複数ページのブロックは無効化され、単一のユニットとして再利用され、チェックポイントにより回復が保証される。ログ構造ファイルシステムでは古いブロックの再利用には大量の I/O が伴う。これは通常、ブロックは部分的にしか解放されないため、再利用にはブロックの読み取りと書き込みが必要になるためである。LSM-Tree ではローリングマージの終了時にブロックが完全に解放されるため余計な I/O は発生しない。

2.2 LSM-Tree インデックスでの検索

LSM-Tree インデックスを使用して即時応答を必要とする完全一致検索 (exact-match find) または範囲検索 (range find) を実行する場合、最初に C0 ツリー、次に C1 ツリーで目的の値または値の集合を検索する。この場合、2 つのディレクトリを検索する必要があるため、B-Tree の場合と比較して若干の CPU オーバーヘッドが発生する可能性がある。2 つ以上のコンポーネントを持つ LSM-Tree では I/O のオーバーヘッドも発生する可能性もある。第三章を先取りすると、複数コンポーネント LSM-Tree をコンポーネント C0, C1, C2, ..., Ck-1, Ck を持つ、サイズが増加するインデックス付きツリー構造と定義する。C0 はメモリ常駐で、他のすべてのコンポーネントはディスク常駐である。すべてのコンポーネントペア (Ci-1, Ci) 間で非同期のローリングマージプロセスが逐次実行され、小さい方のコンポーネント Ci-1 がしきい値サイズを超過するたびに小さい方のコンポーネントから大きい方のコンポーネントにエントリが移動する。原則として、LSM-Tree 内のすべてのエントリが検査されたことを保証するには、完全一致検索または範囲検索がインデックス構造を通じて各コンポーネント Ci にアクセスする必要がある。しかし、この検索をコンポーネントの初期サブセットに限定できる最適化はいくつもある。

まず、タイムスタンプが一意であることが保証されているときのように、一意なインデックス値が生成のロジックによって保証されている場合、一致するインデックスによる検索は初期の Ci コンポーネントで目的の値を見つけることができれば完了となる。別の例として、検索基準が最近のタイムスタンプ値を使用する場合、検索対象とエントリがまだ最大のコンポーネントに移行していないように検索を制限することができる。マージカーソルが (Ci, Ci+1) ペアを循環するとき、最近 (最後の τi 秒) に挿入された Ci のエントリを保持する理由がしばしばあり、古いエントリのみが Ci+1 へ移動するようにする。最も頻繁に参照される検索結果が最近挿入された値である場合、多くの検索結果は C0 ツリーで完了できるため、C0 ツリーは貴重なメモリバッファリング機能を果たす。この点は [23] でも指摘されており、効率性に関する重要な考慮事項を表している。例えば、中断時にアクセスされる短期トランザクションの UNDO ログへのインデックスは、作成後の比較的短い期間でのアクセスの割合が大きく、これらのインデックスのほとんどがメモリに常駐したままであると予想される。各トランザクションの開始時間を追跡することで、例えば直近の τ0 秒に開始されたトランザクションのすべてのログが、ディスクコンポーネントに頼ることなくコンポーネント C0 にあることを保証できる。

2.3 LSM-Tree における削除、更新、および長時間の遅延を伴う検索

削除は挿入と同様に、遅延とバッチ処理という貴重な特性を共有できることに注意。インデックス付きの行が削除されるときに C0 ツリーの適切な位置にキー値エントリが見つからない場合、削除ノードエントリ (delete node entry) をその位置に配置できる。このエントリもキー値でインデックスが付けられるが、削除するエントリ Row ID (RID) が示される。実際の削除はローリングマージプロセス中に実際のインデックスエントリが検出された時点で行うことができる。つまり、削除ノードエントリはマージ中により大きなコンポーネントに移行 (migrate out) し、関連付けられたエントリに遭遇したときに消滅 (annihilate) する。その間に、検索リクエストは削除ノードエントリを介してフィルタリングされ、削除されたレコードへの参照が返されないようにする必要がある。このフィルタリングは関連するキー値の検索中に簡単に実行できる。これは削除ノードエントリはエントリ自体よりも前のコンポーネントの適切なキー値の位置に配置されるためである。そして多くの場合、このフィルタによりエントリが削除されたかどうかを判断するオーバーヘッドが削減される。インデックス付けされた値への変更を引き起こすレコードの更新は、どのような種類のアプリケーションでも珍しいものだが、そのような更新は更新と削除に続く挿入と見なせば LSM-Tree によって遅延された方式で処理できる。

効率的なインデックス更新のための別の種類の操作について概説する。述語削除 (predicate deletion) と呼ばれるプロセスは、述語をアサートする (asserting) だけでバッチ削除を実行する手段を提供する。例えば 20 日以上前のタイムスタンプを持つすべてのインデックス値を削除するという述語である。ローリングマージの通常の過程で、最も古い (最も大きい) コンポーネント内の影響を受けるエントリが常駐すると、このアサーションによりマージプロセス中にそれらのエントリが単純に削除される。さらに別の種類の操作である長い待ち時間の検索は、最も遅いカーソルの循環期間を問い合わせに応答する効率的な手段を提供する。検索ノートエントリ (find note entry) はコンポーネント C0 に挿入され、検索は実際には後のコンポーネントに移行するときに長時間かけて実行される。検索ノートエントリが LSM-Tree の最大の関連コンポーネントの適切な領域まで循環すると、長い待ち時間の検索のための RID の累積リストが完成する。

3. コストパフォーマンスと複数コンポーネントの LSM-Tree

このセクションでは 2 つのコンポーネントを持つ LSM-Tree のコストパフォーマンスを分析する。同じインデックス機能を提供する B-Tree との類推で LSM-Tree を分析し、大量の新規挿入処理に使用される I/O リソースを比較する。セクション 5 で説明するように、他のディスクベースのアクセス方法は新規インデックスエントリの挿入処理における I/O は B-Tree と同等である。ここで LSM-Tree と B-Tree を比較する最も重要な理由は、これら 2 つの構造が比較しやすいことである。どちらも葉のレベルで照合順序にインデックス付けされた各行のエントリを含み、ページサイズのノードのパスに沿ってアクセスを導く上位レベルのディレクトリ情報を持っている。LSM-Tree への新しいエントリの挿入における I/O の利点の分析は、効率は劣るもののよく理解されている B-Tree の動作の類似性によって効果的に説明される。

次のセクション 3.2 では I/O 挿入コストを比較し、2 コンポーネントの LSM-Tree と B-Tree のコストの比が小さいのは 2 つの要因の積であることを示す。最初の要因である COSTπ/COSTP はすべての I/O を複数ページブロックで実行することによって LSM-Tree で得られる利点に対応し、その結果、シークと回転待ち時間を大幅に節約することによってディスクアームをより効率的に利用する。COSπ 項は複数ページブロックの一部としてディスク上のページを読み書きするときのディスクアームコストを表し、COSP はページをランダムに読み書きするコストを表している。LSM-Tree と B-Tree の間の I/O コスト比を決定する台の要素は 1/M として与えられ、これはマージステップ中に得られるバッチ処理の効率を表す。M は C0 から C1 のページサイズ葉ノードにマージされるエントリの平均数である。葉ごとに複数のエントリを挿入することは、エントリが挿入されるたびにそのエントリが存在する葉ノードの読み書きするために通常 2 回の I/O を必要とする (大きな) B-Tree よりも有利である。5 分ルールにより、例 1.2 では B-Tree から読み込まれた葉ページがバッファに残っている短い時間の間に 2 回目の挿入のために再参照される可能性は低い。しがたって B-Tree インデックスにはバッチ処理の影響はなく、各葉ノードが読み込まれ、新しいエントリが挿入され、再び書き出される。しかし LSM-Tree では C0 コンポーネントが C1 コンポーネントと比較して十分に大きい限り重要なバッチ処理の影響が発生する。たとえば 16 バイトのインデックスエントリがある場合、完全にパックされた 4KB のノードには 250 エントリが期待できる。この 2 つの要因から LSM-Tree が B=Tree よりも効率的に優れていることは明らかであり、この優位性を得るには "ローリングマージ" が不可欠である。

複数ページブロックの効率と単一ページ I/O の効率の比率に対応する係数 COSTπ/COSTP は定数であり、LSM-Tree 構造でこれに影響を与えることはできない。しかしマージステップのバッチ処理効率 1/M は C0 コンポーネントと C1 コンポーネントのサイズ比に比例する。C1 コンポーネントに比べて C0 コンポーネントが大きいほどマージ効率が向上する。これは、ある時点まではより大きな C0 コンポーネントを使用することでディスクアームのコストをさらに節約できることを意味するが、これには C0 コンポーネントを格納するためのより大きなメモリコストを伴う。ディスクアームとメモリ容量の合計コストを最小限に抑えるには最適なサイズの組み合わせがあるが、大きな C0 を使用する場合、この解決策はメモリの面でかなり高価になる可能性がある。この考察が、セクション 3.3 で兼手王するマルチコンポーネント LSM-Tree の必要性を動機づけた。3-コンポーネント LSM-Tree はメモリ常駐コンポーネントの C0 とディスク常駐のコンポーネント C1 および C2 があり、コンポーネントのサイズは添え字が大きくなるにつれて大きくなる。C0 と C1 の間にはローリングマージプロセスが進行中であり、C1 と C2 の間にも別のローリングマージがあり、小さい方のコンポーネントがしきい値サイズを超えるたび、小さい方のコンポーネントから大きい方のコンポーネントにエントリが移動する。3-コンポーネント LSM-Tree の利点は、C0 と C1 の間、および C1 と C2 の間のサイズの合計比率を最適化するように C0 を選択することでバッチ処理の効率を幾何学的に改善できることである。その結果、C0 メモリコンポーネントのサイズを総インデックスに比例して大幅に小さくすることができ、コストが大幅に改善される。

セクション 3.4 では、メモリとディスクの総コストを最小化するためにマルチコンポーネント LSM-Tree のさまざまなコンポーネントの最適な相対サイズを導き出す数学的手法を導入する。

3.1 ディスクモデル

B-Tree に対する LSM-Tree の利点は主に I/O コストの削減にある (ただし 100% フルなディスクコンポーネントは、他の既知の柔軟なディスク構造よりも容量超すとの点で有利である)。LSM-Tree のこの I/O コストの利点の 1 つは、ページ I/O が複数ページブロックの他の多くのページとともに償却できることである。

定義 3.1.1. I/O コストとデータ温度. 特定の種類のデータ、つまりテーブルの行やインデックスのエントリをディスクに保存する場合、保存するデータの量が増えるにつれて特定のアプリケーション環境での通常の使用時にディスクアームの使用率がますます高くなることがわかる。ディスクを購入するとき我々は 2 つのものにお金を払っている。1 つ目はディスク容量、2 つ目はディスク I/O レートである。通常、これら 2 つのうちの 1 つがあらゆる使用においても制限要因になる。容量が制限要因である場合、ディスクがいっぱいになり I/O を提供するディスクアームがアプリケーションによってほんの僅かしか利用されていないことがわかる。一方、データを追加するとディスクが部分的にしかいっぱいでないときにディスクアームが最大使用率に達することがある。これは I/O レートが制限要因であることを意味する。

ピーク使用時のランダムページ I/O には、ディスクアームの適正な使用量に基づくコスト COSTP がかかる。一方、大規模な複数ページブロック I/O の一部であるディスク I/O のコストは COSπ で表され、複数ページにわたるシーク時間と回転待ち時間を償却するためにこの量はかなり小さくなる。ストレージコストについては次の命名法を採用する:

  • COSTd = 1 MByte のディスクストレージのコスト
  • COSTm = 1 MByte のメモリストレージのコスト
  • COSTP = 1 ページ/秒の I/O レートを提供するためのディスクアームコスト (ランダムページ用)
  • COSTπ = 1 ページ/秒の I/O レートを提供するためのディスクアームコスト (複数ページブロック I/O の一部)

S MByte のストレージと 1 秒あたり H のランダムページ I/O 転送 (データはバッファリングされないと仮定) のデータ本体を参照するアプリケーションがあるとすると、ディスクアームの使用コストは S・COSTP、ディスクメディアの使用コストは S・COSTd で与えられる。どちらのコストが制限要因であるかによってもう一方のコストは無コストになるため、このディスク常駐データのアクセスにかかる計算コスト COST-D は次のように与えられる。\[ {\sf COST\mbox{-}D} = \max({\sf S}\cdot{\sf COST}_{\sf d}, {\sf H}\cdot{\sf COST}_{\sf P}) \] COST-D は、ディスクスペースがメモリにバッファリングされない当仮定の下で、このアプリケーションのデータアクセスをサポートするための総コスト COST-TOT でもある。この場合、総ストレージ要件 S が一定であっても、総コストはランダム I/O レート H に応じて直線的に増加する。ここでメモリバッファリングのポイントは、同じ合計ストレージ S に対して I/O レートが増加する特定の時点でディスク I/O をメモリバッファに置き換えることである。このような状況下でランダム I/O 要求をサポートするためにメモリバッファを事前に投入できると仮定すると、ディスクのコストはディスクメディアのみのコストまで低下するため、このバッファ常駐データにアクセスするための計算コスト COST-B は単純にメモリのコストとディスクメディアのコストを足したものになる: \[ {\sf COST\mbox{-}B} = {\sf S}\cdot{\sf COST}_{\sf m} + {\sf S}\cdot{\sf COST}_{\sf d} \] ここでこのアプリケーションのデータアクセスをサポートするための合計コストはこれら 2 つの計算コストの最小値となる: \[ {\sf COST\mbox{-}TOT} = \min( \max({\sf S}\cdot{\sf COST}_{\sf d}, {\sf H}\cdot{\sf COST}_{\sf P}), {\sf S}\cdot{\sf COST}_{\sf m} + {\sf S}\cdot{\sf COST}_{\sf d} ) \]

与えられたデータ S に対してページアクセスレート H が増加すると COST-TOT のグラフには 3 つのコスト状態が現われる。Figure 1.1 では COST-TOT/MByte と H/S (1 秒当たりのアクセス数/メガバイト) をグラフにしている。S が小さい場合、COST-TOT はディスクメディアのコスト S・COSTd によって制限され、これは S が固定されている場合は一定である。H/S が増加するにつれてコストはディスクアームの使用量 H・COSTP が支配的に形、S が固定されている場合は H/S の増加に比例する。最後に、5 分ルールによってメモリ常駐が決定される時点で S・COSTm + S・COSTd が支配的な要因になり、これは現在のコストのメモリ項 COSTm >> COSTd によって支配される。Copeland ら [6] に従いデータ本体の温度 (temperature) を H/S と定義し、これらの 3 つのコスト状態をコールド、ウォーム、ホットと名付ける。ホットデータはアクセスレート H が十分に高く、したがって H/S も高いためメモリバッファの常駐が正当化される ([6] 参照)。もう一方の極端な例では、コールドデータはディスク容量が制限される。つまり、コールドデータが占有するディスクボリュームには I/O レートを満たすのに十分なディスクアームが付属する。その中間にあるのがウォームデータで、そのアクセス要件は各ディスクアームで使用されるデータ容量を制限することによって満たされる必要があり、ディスクアームが使用限界となる。これらなお範囲は次のように分割される:

  • Tf = COSTd/COSTP = コールドデータとウォームデータの温度分割点 ("freezing")
  • Tb = COSTm/COSTP = ウォームデータとホットデータの温度分割点 ("boiling")

COSTπ を使用した複数ページブロックアクセスの場合にも同様に定義された範囲が存在する。ウォーム領域とホット領域の区分は 5 分ルール [13] の一般化である。

[6] で強調されているように、データベーステーブルが均一にアクセスされている場合にその温度を計算するのは簡単である。しかしこの温度の妥当性はアクセス方法に依存する。関連する温度には、論理挿入率 (バッチ化されたバッファ挿入を含む) ではなく、実際のディスクアクセス率が含まれる。LSM-Tree が達成することを表現する 1 つの方法は実際のディスクアクセスを減らしてインデックスデータの実効温度を下げることである。この考え方はセクション 6 の結論で再論される。

Figure 1.1. MByteあたりのアクセスコストと温度のグラフ

複数ページブロック I/O の利点

複数ページブロック I/O によって得られる利点は Bounded Disorder ファイル [16]、SB-Tree [21]、Log Structured ファイル [23] などのいくつかの過去のアクセス方法の中心的なものである。IBM 3380 ディスク [29] での DB2 ユーティリティのパフォーマンスを分析した 1989 年の IBM の出版物では次のような分析が示されている: "... [単一ページの読み取り] を完了するのにかかる時間は約 20ms と推定される (シークに 10ms、回転遅延に 8.3ms、読み取りに 1.7ms を想定)。... [連続する 64 ページ] のシーケンシャルプリフェッチ読み取りを実行する時間は約 125ms (シーク 10ms、回転遅延 8.3ms、64 レコード[ページ]の読み取り 106.9ms と想定)、つまり 1 ページあたり約 2ms と推定される。" したがって、複数ページブロック I/O のページあたり 2ms とランダム I/O の 20ms の比率は、ディスクアームのレンタルコストの比率 COSTπ/COSTP が約 1/10 に等しいことを意味する。より最近の SCSI-2 ディスクの 4KByte ページの読み取りを分析すると、シーク 9ms、回転遅延 5.5ms、読み取り 1.2ms で合計 16ms になる。連続する 64 の 4KByte ページを読み取るには、シーク 9ms、回転遅延 5.5ms、64 ページの読み取り 80ms、つまり合計 95ms、1 ページあたり約 1.5ms が必要である。この場合も COSTπ/COSTP は約 1/10 に等しくなる。

我々は 1GB の容量を持ちピーク時の I/O レートを毎秒約 60～70 であるような SCSI-2 ディスクを搭載した約 1,000 ドルのワークステーションサーバシステムを分析する。長い I/O キューを回避するために使用できる公称 I/O レートはもっと低く毎秒約 40 I/O である。マルチブロック I/O の利点は顕著である。

1995 年の典型的なワークステーションコスト
COSTm = $100/MByte
COSTd = $1/MByte
COSTP = $25/(IOs/sec)
COSTπ = $2.5/(IOs/sec)
Tf = COSTd/COSTP = .04 IOs/(sec・MByte) ("freezing ポイント")
Tb = COSTm/COSTP = 4 IOs/(sec・MByte) ("boiling ポイント")

我々は Tb 値を使って 5 分ルールの基準間隔 τ を導出する。このルールは毎秒 1 ページの I/O レートを維持するデータには、そのデータを保持するために必要なメモリと同じコストがかかることを主張している。この一般的なコストは: \[ (1/\tau) \cdot {\sf COST}_{\sf P} = {\sf pagesize} \cdot {\sf COST}_{\sf m} \] τ について解くと τ = (1/pagesize)・(COSTP/COSTm) = 1/(pagesize・Tb) となり、上記の値ではページが 0.004MByte の場合、τ = 1/(.004・4) = 62.5 秒/IO となる。

例 3.1. 例 1.1 の TPC-A アプリケーションで 1000 TPS の速度を達成するには、Account テーブルに対して 1 秒あたり H = 2000 回の I/O が発生する。このテーブル自体は 100 バイトの 100,000,000 行で構成され、合計 S = 10 GB になる。ここでのディスクストレージコストは S・COSTd = $10,000 だが、ディスク I/O コストは H・COSTP = $50,000 である。温度 T = H/S = 2000/10,000 = 0.2 は freezing よりはるかに高い (5 分の 1) が boiling ポイントよりははるかに低い。このウォームデータはデータストレージにディスク容量の 1/5 しか使わない。我々はディスクアームに対価を払っているのであって容量に対して払っているのではない。例 1.2 の History テーブルに対する 20 日間の Acct-ID || Timestamp インデックスについて考える場合も同じ状況である。例 1.2 で計算したようにこのような B-Tree インデックスには約 9.2 GB の葉レベルエントリを必要とする。成長中のツリーが約 70% しか満たされていないことを考えるとツリー全体では 13.8 GB を必要とするが、これは Account テーブルと同じ I/O レート (挿入のみ) を持ち、温度が同等であることを意味する。

3.2 LSM-Tree と B-Tree の I/O コスト比較

ここでは、挿入、削除、更新、および長い待ち時間のかかる検索など、マージ可能 (mergeable) と呼ばれるインデックス操作の I/O コストについて検討する。以下の議論では LSM-Tree と B-Tree を比較する分析を示している。

B-Tree 挿入コストの計算式

B-Tree の挿入を実行するためのディスクアームのレンタルコストについて考えてみよう。まずエントリを配置するツリーの位置にアクセスする必要があり、これにはツリーのノードを検索する必要がある。ツリーへの連続的な挿入は葉レベルのランダムな位置に行われると仮定し、アクセス経路のノードページは過去の挿入によって常にバッファに常駐していることはないとする。キーが常に増加する連続挿入、つまり insert-on-the-right の状況はこの想定に従わない比較的一般的なケースである。このような insert-on-the-right の状況は B-Tree が常に右に成長するので I/O がほとんどないため、B-Tree データ構造によってすでにかなり効率的に処理できることに注意。実際、これが B-Tree ロードが発生する基本的な状況である。増え続ける値によるログレコードのインデックスを扱うための構造は他にもいくつか提案されている [8]。

[21] では De で表される B-Tree の有効深 (effective depth) は B-Tree のディレクトリレベルをランダムに Key-Value 検索したときにバッファ内で見つからなかったページの平均数であると定義された。例 1.2 の Account-ID || Timestamp インデックス作成に使用されたサイズの B-Tree では De の値は通常約 2 である。

B-Tree への挿入を実行するには葉レベルページへの Key-Value 検索を実行し (De I/O)、それを更新し、(定常状態では) 対応するダーティ葉ページを書き出す (1 I/O)。比較的頻度の少ないノード分割は我々の分析に重要な影響を与えないことを示すことができるため無視する。このプロセスで読み書きされるページはすべてランダムアクセスでコストは COSTP である。したがって B-Tree での挿入の合計 I/O コスト COSTB-ins は次式で与えられる: \[ \begin{equation} {\sf COST_{B\mbox{-}ins}} = {\sf COST_P} \cdot ({\sf D_e} + 1) \tag{3.1} \label{eq31} \end{equation} \]

LSM-Tree 挿入コストの計算式

LSM-Tree への挿入コストを評価するには複数の挿入の償却という観点から考える必要がある。これは、メモリコンポーネント C0 への単一の挿入ではまれにしか I/O の効果が発生しないためである。このセクションの冒頭で説明したように、LSM-Tree が B-Tree に対して持つ性能上の利点は 2 つの異なるバッチ効果に基づいている。1 つ目は既に述べたようにページ I/O のコスト COSTπ が削減されることである。2 つ目は新しく挿入されたエントリを C1 ツリーにマージする際の遅延により、通常は C0 に多数のエントリが蓄積される時間が生じ、したがってディスクからメモリへ、そしてメモリからディスクへの往復の間に複数のエントリが各 C1 ツリーの葉ページにマージされるという考えに基づいている。これに対して B-Tree の葉ページはメモリ上で参照される頻度が低すぎるため、複数のエントリが挿入されることはないものと想定している。

定義 3.2.1. バッチ-マージパラメータ M. この複数エントリの葉あたりのバッチ処理効果を定量化するために、ローリングマージ中に C1 ツリーの各単一ページ葉ノードに挿入される C0 ツリーのエントリの平均数として、与えられた LSM-Tree のパラメータ M を定義する。パラメータ M は LSM-Tree を特徴付ける比較的安定した値であると主張する。実際、M の値はインデックスエントリのサイズと C1 ツリーの葉レベルと C0 ツリーの葉レベルのサイズの比によって決まる。次の新しいサイズパラメータを定義する:

Se = エントリ (インデックスエントリ) サイズ (Bytes)
Sp = ページサイズ (Bytes)
S0 = C0 コンポーネント葉レベルのサイズ (MBytes)
S1 = C1 コンポーネント葉レベルのサイズ (MBytes)

このとき 1 ページのエントリ数はおよそ Sp/Se となり、コンポーネント C0 を占める LSM-Tree のエントリの割合は S0/(S0+S1) となるため、パラメータ M は次式で与えられる: \[ \begin{equation} {\sf M} = ({\sf S_p} / {\sf S_e}) \cdot ({\sf S_0} / ({\sf S_p} + {\sf S_1})) \tag{3.2} \label{eq32} \end{equation} \] コンポーネント C0 が C1 に比べて大きいほどパラメータ M も大きくなることに注意。一般的な実装では S1 = 40・S0 でディスクページあたりのエントリ数 Sp/Se が 200 であるため M = 5 となる。パラメータ M が与えられれば LSM-Tree へのエントリ挿入コスト COSTLSM-ins の大まかな式が得られる。C1 ツリー葉ノードをメモリに取り込んで再び書き出すまでの 1 ページ当たりのコスト 2・COSTπ を、この間に C1 ツリーの葉ノードにマージされる M 個の挿入に償却するだけである。\[ \begin{equation} {\sf COST_{LSM\mbox{-}ins}} = 2 \cdot {\sf COST_\pi} / {\sf M} \tag{3.3} \label{eq33} \end{equation} \] LSM-Tree と B-Tree の両方のケースで、インデックス更新の I/O に関連する比較的重要でないコストを無視していることに注意。

LSM-Tree と B-Tree の挿入コスト比較

2 つのデータ構造への挿入のコスト式 (\(\ref{eq31}\)) と (\(\ref{eq33}\)) を比べると次のような比率になる: \[ \begin{equation} {\sf COST_{LSM\mbox{-}ins}} / {\sf COST_{B\mbox{-}ins}} = {\sf K_1} \cdot ({\sf COST_\pi} / {\sf COST_P}) \cdot (1 / {\sf M}) \tag{3.4} \label{eq34} \end{equation} \] ここで K1 は (ほぼ) 定数の 2/(De+1) で、検討しているインデックスサイズでは約 0.67 となる。この式は、LSM-Tree への挿入と B-Tree への挿入のコスト比が、これまでに説明した 2 つのバッチ効果のそれぞれに直接比例していることを示している。COSTπ/COSTP は複数ページブロックのページ I/O とランダムページ I/O のコスト比に対応する小さな割合であり、1/M はローリングマージ中にページごとにバッチ処理されるエントリの数である。通常、2 つの比率の積はコスト比率をほぼ 2 桁改善する。当然、このような改善はインデックスが B-Tree として比較的高い温度を持つ領域でのみ可能であり、LSM-Tree インデックスに移行する際にディスク数を大幅に削減することが可能である。

例 3.2. 例 1.2 のようなインデックスが 1GB のディスクスペースを占有するが、必要なディスクアームアクセスレートを達成するためには 10GB の領域に保持する必要があると仮定すると、ディスクアームコストの節約には確かに改善の余地がある。式 (\(\ref{eq34}\)) で示される挿入コストの比率が 0.02 = 1/50 であるならば、インデックスとディスクコストを縮小することができる。しかし、より効率的な LSM-Tree ではコストをディスク容量に必要な量までしか削減できないことがわかる。必要なディスクアームサービスを受けるために 35GB に制限された 1GB の B-Tree から始めていた場合、1/50 のコスト改善の比率を完全に実現できる可能性がある。

3.3 複数コンポーネント LSM-Tree

特定の LSM-Tree のパラメータ M は、ローリングマージ中に C1 ツリーの各単一ページの葉ノードに挿入される C0 ツリーのエントリの平均数として定義された。新しいエントリが挿入され C1 ツリーのノードにマージされる前に C0 ツリーに蓄積される遅延時間があるため、量 M は 1 より大きいと考えてきた。しかし、式 (\(\ref{eq32}\)) から明らかなように、C1 ツリーが C0 ツリーに比べて極端に大きかったり、エントリが極端に大きく 1 ページに収まる数が少ない場合は量 M が 1 未満になることがある。このような M の量は C0 ツリーからマージされるエントリごとに平均して 1 つ以上の C1 ツリーページをメモリに出し入れする必要があることを意味する。式 (\(\ref{eq34}\)) から見て M が非常に小さい場合、具体的には M < K1 ・COSTπ / COSTP の場合、複数ページのディスク読み取りのバッチ効果を打ち消す可能性さえあるため、挿入には LSM-Tree の代わりに通常の B-Tree を使用する方が良い。

M の値が小さくならないようにするには 2-コンポーネント LSM-Tree で C0 コンポーネントのサイズを C1 のサイズに対して増やすしかない。葉エントリの合計サイズが S (S = S0 + S1, ほぼ安定した値) である 2-コンポーネント LSM-Tree を考え、C0 への新しいエントリの挿入速度が 1 秒あたり R で一定であると仮定する。簡単のため C0 に挿入されたエントリは C1 コンポーネントに出力される前に削除されないと仮定する。これより C0 のサイズをしきい値サイズ近くに保つには、エントリは C0 に挿入される速度と同じ速度でローリングマージを通じて C1 コンポーネントに移行する必要がある (合計サイズ S がほぼ安定であることを考えると、これはまた C0 への挿入速度が (おそらく一連の述語削除 (predicate deletes) の連続を使用して) C1 から一定の削除速度によってバランスが取られる必要があることも意味する)。C0 のサイズを変えるとマージカーソルの循環速度に影響する。C1 へのバイト/秒での一定の移行速度は、ローリングマージカーソルが C0 のエントリをバイト/秒での一定の速度で移動する必要がある。したがって C0 のサイズが小さくなると C0 の最小インデックス値から最大インデックス値への循環速度が増加する。その結果、ローリングマージを実行するための C1 の複数ページブロックの I/O 速度も増加する必要がある。C0 のサイズを 1 エントリにすることが可能であれば、この概念乗の極端な時点で、新しく挿入されたエントリごとに C1 のすべての複数ページブロックを循環する必要があり、I/O に膨大な負荷がかかる。B-Tree で行われているように、新しく挿入されたエントリごとに C1 の関連ノードにアクセスするのではなく、C0 と C1 をマージするアプローチは我々にとって負担となるだろう。比較すると、C0 コンポーネントのサイズが大きいほどマージカーソルの循環が遅くなり、挿入の I/O コストが減少する。しかし、これによりメモリ常駐コンポーネント C0 のコストが増加する。

ここで、C0 の標準サイズは LSM-Tree の総コスト (C0 のメモリコスト、プラス、C1 コンポーネントのメディア/ディスクアームコスト) が最小になるポイントによって決まる。このバランスに到達するにはまず大きな C0 コンポーネントから始めて C1 コンポーネントをディスクメディアに密着させる。C0 コンポーネントが十分に大きければ C1 への I/O レートは非常に小さくなる。ここで、C1 を処理するための I/O レートが C1 コンポーネントのメディアの上に置かれたディスクアームがフルレートで動作するポイントまで高価なメモリを安価なディスクスペースと交換しながら C0 のサイズを縮小してゆくことができる。この時点で C0 のメモリコストをさらに削減すると、ディスクアームの負荷を軽減するために C1 コンポーネントを部分的にいっぱいになったディスクに分散する必要があるため、メディアコストが増加することになる。また C0 を縮小し続けるとある時点で最小コストポイントに到達する。ここで 2 つのコンポーネントからなる LSM-Tree では C0 について決定した標準サイズがメモリ使用の点で依然として高価になることが一般的である。代替案としては、3 つ以上のコンポーネントを持つ LSM-Tree の採用を検討することである。概念的には、C0 コンポーネントのサイズが非常に大きくメモリコストが重要な要因となる場合、2 つの極端なサイズの間に別の中間サイズのディスクベースのコンポーネントを作成することを検討する。これによりディスクアームのコストを抑えながら C0 コンポーネントのサイズを縮小できる。

一般に、K+1 個のコンポーネントからなる LSM-Tree にはコンポーネント C0, C1, ..., CK-1, CK を持ち、これらはサイズが増加するインデックスツリー構造である。C0 コンポーネントツリーはメモリ常駐で、他のすべてのコンポーネントはディスク常駐である (ただしディスク常駐アクセスツリーと同様にアクセスの多いページはメモリにバッファリングされる)。挿入による圧力の下ですべてのコンポーネントペア (Ci-1, Ci) 間で非同期のローリングマージ処理が行われており、小さい方のコンポーネント Ci-1 がしきい値サイズを超えるたびに、絵小さい方のコンポーネントから大きい方のコンポーネントにエントリが移動する。LSM-Tree に挿入された長寿命エントリはその存続期間中に C0 ツリーから始まり一連の K 回の非同期ローリングマージステップを経て最終的に CK に移動する。

ここでは LSM-Tree が挿入を主とする環境に存在すると想定しているため挿入トラフィックでのパフォーマンスに焦点が当てられている。通常、3 つ以上のコンポーネントの LSM-Tree 検索ではディスクコンポーネントごとに 1 つの追加ページ I/O によりパフォーマンスが多少低下する。

Figure 3.3. K+1 コンポーネントの LSM-Tree

3.4 LSM-Tree: コンポーネントサイズ

このセクションでは複数コンポーネントの LSM-Tree への挿入にかかる I/O コストの公式を導出し、さまざまなコンポーネントに最適なしきい値サイズを選択する方法を数学的に示す。拡張された例 3.3 は、B-Tree のシステムコスト、2-コンポーネントの LSM-Tree のシステムコストの改善、および 3 コンポーネントの LSM-Tree で得られる大きな節約を示している。

LSM-Tree のコンポーネントのサイズを S(Ci) を葉ノードに含まれるエントリのバイト数と定義する。コンポーネント Ci のサイズは Si と示し、S(Ci) = Si であり、すべての葉レベルのエントリの合計サイズを S = Σi Si と表す。ここで LSM-Tree のコンポーネント C0 にバイト/秒で比較的安定した挿入速度 R があると仮定し、簡単のため、新しく挿入されたすべてのエントリは一連のローリングマージステップによってコンポーネント CK に循環すると仮定する。また各コンポーネント C0, C1, ..., CK-1 のサイズ葉現在の分析で決定される最大しきい値サイズに近いと仮定する。コンポーネント CK はある一定の標準機関にわたって削除と挿入のバランスがとれているため、比較的安定したサイズであると仮定する。コンポーネント CK からの削除は、コンポーネント C0 への挿入速度 R に追加することなく行われると考えることができる。

Minimizing Total Cost

4. Consistency and Recovery in the LSM-tree

4.1 Concurrency in the LSM-tree

4.2 Recover in the LSM-tree

5. Cost-Performance Comparison with Other Access Methods

Time-Split B-tree

MD/OD R-Tree

Differential File

Selective Deferred Text Index Updates

6. Conclusions and Suggested Extensions

6.1 Extensions of LSM-tree Application

Acknowledgements

The authors would like to acknowledge the assistance of Jim Gray and Dave Lomet, both of whom read an early version of this paper and made valuable suggestions for improvement. In addition, the reviewers for this journal article made many valuable suggestions.

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley.
  2. Anon et al., "A Measure of Transaction Processing Power", Readings in Database Systems, edited by Michael Stonebraker, pp 300-312, Morgan Kaufmann, 1988.
  3. R. Bayer and M Schkolnick, "Concurrency of Operations on B-Trees", Readings in Database Systems, edited by Michael Stonebraker, pp 129-139, Morgan Kaufmann 1988.
  4. P. A. Bernstein, V. Hadzilacos, and N. Goodman, "Concurrency Control and Recovery in Database Systems", Addison-Wesley, 1987.
  5. D. Comer, "The Ubiquitous B-tree", Comput. Surv. 11, (1979), pp 121-137.
  6. George Copeland, Tom Keller, and Marc Smith, "Database Buffer and Disk Configuring and the Battle of the Bottlenecks", Proc. 4th International Workshop on High Performance Transaction Systems, September 1991.
  7. P. Dadam, V. Lum, U. Praedel, G. Shlageter, "Selective Deferred Index Maintenance &Concurrency Control in Integrated Information Systems," Proceedings of the Eleventh International VLDB Conference, August 1985, pp. 142-150.
  8. Dean S. Daniels, Alfred Z. Spector and Dean S. Thompson, "Distributed Logging for Transaction Processing", ACM SIGMOD Transactions, 1987, pp. 82-96.
  9. R. Fagin, J. Nievergelt, N. Pippenger and H.R. Strong, Extendible Hashing — A Fast Access Method for Dynamic Files, ACM Trans. on Database Systems, V 4, N 3 (1979), pp 315-344
  10. H. Garcia-Molina, D. Gawlick, J. Klein, K. Kleissner and K. Salem, "Coordinating MultiTransactional Activities", Princeton University Report, CS-TR-247-90, February 1990.
  11. Hector Garcia-Molina and Kenneth Salem, "Sagas", ACM SIGMOD Transactions, May 1987, pp. 249-259.
  12. Hector Garcia-Molina, "Modelling Long-Running Activities as Nested Sagas", IEEE Data Engineering, v 14, No 1 (March 1991), pp. 14-18.
  13. Jim Gray and Franco Putzolu, "The Five Minute Rule for Trading Memory for Disk Accesses and The 10 Byte Rule for Trading Memory for CPU Time", Proceedings of the 1987 ACM SIGMOD Conference, pp 395-398.
  14. Jim Gray and Andreas Reuter, "Transaction Processing, Concepts and Techniques", Morgan Kaufmann 1992.
  15. Curtis P. Kolovson and Michael Stonebraker, "Indexing Techniques for Historical Databases", Proceedings of the 1989 IEEE Data Engineering Conference, pp 138-147.
  16. Lomet, D.B.: A Simple Bounded Disorder File Organization with Good Performance, ACM Trans. on Database Systems, V 13, N 4 (1988), pp 525-551
  17. David Lomet and Betty Salzberg, "Access Methods for Multiversion Data", Proceedings of the 1989 ACM SIGMOD Conference, pp 315-323.
  18. David Lomet and Betty Salzberg, "The Performance of a Multiversion Access Method", Proceedings of the 1990 ACM SIGMOD Conference, pp 353-363.
  19. Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil, "The Log-Structured Merge-Tree (LSM-tree)", UMass/Boston Math & CS Dept Technical Report, 91-6, November, 1991.
  20. Patrick E. O'Neil, "The Escrow Transactional Method", TODS, v 11, No 4 (December 1986), pp. 405-430.
  21. Patrick E. O'Neil, "The SB-tree: An index-sequential structure for high-performance sequential access", Acta Informatica 29, 241-265 (1992).
  22. Patrick O'Neil and Gerhard Weikum, "A Log-Structured History Data Access Method (LHAM)," Presented at the Fifth International Workshop on High-Performance Transaction Systems, September 1993.
  23. Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation of a Log Structured File System", ACM Trans. on Comp. Sys., v 10, no 1 (February 1992), pp 26-52.
  24. A. Reuter, "Contracts: A Means for Controlling System Activities Beyond Transactional Boundaries", Proc. 3rd International Workshop on High Performance Transaction Systems, September 1989.
  25. Dennis G. Severance and Guy M. Lohman, "Differential Files: Their Application to the Maintenance of Large Databases", ACM Trans. on Database Systems, V 1, N 3 (Sept. 1976), pp 256-267.
  26. Transaction Processing Performance Council (TPC), "TPC BENCHMARK A Standard Specification", The Performance Handbook: for Database and Transaction Processing Systems, Morgan Kauffman 1991.
  27. Helmut Wächter, "ConTracts: A Means for Improving Reliability in Distributed Computing", IEEE Spring CompCon 91.
  28. Gerhard Weikum, "Principles and Realization Strategies for Multilevel Transaction Management", ACM Trans. on Database Systems, V 16, N 1 (March 1991), pp 132-180.
  29. Wodnicki, J.M. and Kurtz, S.C.: GPD Performance Evaluation Lab Database 2 Version 2 Utility Analysis, IBM Document Number GG09-1031-0, September 28, 1989.

翻訳抄

メモリ内のデータを定期的にストレージ上の大規模構造にマージすることで高い書き込みスループットと効率的なクエリー処理を実現するデータ構造である LSM-Tree に関する 1996 年の論文。

  1. O’NEIL, Patrick, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33: 351-385.