こんにちは、Tochiです。 しばらくサボっていたので、久しぶりにアウトプット
はじめに
最近、「データ思考アプリケーションデザイン」という本を読み進めています。 www.oreilly.co.jp
第三章にて、SSTableという単語とLSMツリーという知らない単語を見たので軽く深掘っていきます
前提
Hash IndexやB-Treeインデックスのこと知っているといいかも
SSLTableとは
ソート済み文字列テーブル（Sorted String Table）の略です。
Hash Index のsegment fileのフォーマットに対してキーバリューのペアの並びが、 キーでソートされているという条件と マージされたセグメント内のキーに重複がないという条件を付け加えたもの。
SSLTableの構築と管理
キーをソートしてデータを保存するにはどうするのか？
赤黒木やAVLツリーなどのツリー型のデータ構造を使えば、できます。
書き込み要求が来たら、インメモリのバランスドツリーデータ構造に追加する
- このインメモリツリーをmemtableという
memtableがなんらかの閾値よりも大きくなった場合はSSLTableとしてディスクに書き出す
- この時点ですでにツリーはソートされたキーと値のペアとして管理されているので効率的に下記出せる
- 新しく作成されたSSLTableは最新尾DBのセグメントになる
読み取り要求が来たら、そのキーのmemtableを探す。その次にSSLTableの最新のセグメントを見に行く。
マージとコンパクションのプロセスをバックグラウンドで実行し、セグメントファイルの結合と上書きされた値や削除された値を破棄する
この管理方法は基本的にはうまくいくが、データベースがクラッシュした際に直近の書き込みが失われます。 そのため、全ての書き込みのログを即座に追記しておくことが必要
参考: データはどのように書き込まれるか
SSLTableのメリット
このSSLTableと、Bitcastのようなストレージエンジのログセグメント（ハッシュインデックス）と比較すると大きく3つの利点がある。
- ファイルが利用可能なメモリ量よりも大きくなっても、セグメントのマージをシンプルに行える。
マージソートのアルゴリズムに似ています。すでにソートされているので、各セグメントの最初のキーを見て出力ファイルに移していきます。 複数ある場合は、最新のものだけを残します
- 特定のキーを探す際は、全てのキーをメモリに保持しておく必要はない。
例えば、handiworkというキーを探しているときは、正確なセグメントファイルのオフセットをわかっている必要はないです。handbagとhandsomeというキーのオフセットがわかっていればその間にあることは明確なので、handbagのオフセットに飛んでからスキャンすれば良いわけです。
一般には、キロバイトごとに一つのキーがわかっていればいい。
- ディスクに書き込む前にレコードをブロックとしてグループ化して圧縮しておける。 読み取りリクエストの処理では、要求された範囲内にある複数のキーと値のペアをスキャンしないといけないです。 この場合、インメモリインデックスの各エントリは圧縮されたブロックの開始地点を指すことになります。 圧縮はディスクの領域削減や、I/Oの帯域削減にもなります。
LSMツリー
上記で述べたアルゴリズムがLevelDBやRocksDBで使われている このインデックス構造をLSMツリー（Log-Structured Merge-Tree）という。
ソート済みのファイルのあマージコンパクションという原理を基盤とするストレージエンジンはLSMストレージエンジンと言います。
ログ構造化マージ ツリー( LSM ツリー、またはLSMT [1]とも呼ばれる) は、トランザクション ログなど、挿入量の多いファイルへのインデックス付きアクセスを提供するのに魅力的なパフォーマンス特性を持つデータ構造です。データ。LSM ツリーは、他の検索ツリーと同様に、キーと値のペアを維持します。LSM ツリーは 2 つ以上の個別の構造でデータを維持し、それぞれが基礎となるストレージ メディアに合わせて最適化されています。データは 2 つの構造間でバッチで効率的に同期されます。 参考: Log-structured merge-tree - Wikipedia
Bツリーとの比較
一般にインデックスといえば、Bツリーです。 こちらと比較をされていたのでまとめます。
| 要素 | Bツリー | LSM |
|---|---|---|
| 書き込みの増幅 | ディスクへの書き込みが最低2回発生 (WAL＆ページ) | 書き込みは1回のみ |
| ページが分割された場合はさらに書き込みが必要 | コンパクション＆マージがバックグラウンドで発生するため、 | |
| 負荷は小さい | ||
| 書き込みスループット | ランダムな書き込みのためLSM-Treeより遅い | 連続した書き込みのため高速 |
| データ量 | フラグメンテーションにより未使用のディスク領域が生じる | 圧縮率を高めることが可能で、ファイルサイズが小さくなる |
| ページが分割されたり、行が既存のページに収まらない場合 | 定期的なコンパクション＆マージにより未使用領域は削除される | |
| インデックス | 必ず一意であること | コンパクション＆マージはバックグラウンドで行われるため、 |
| 複数のセグメントに存在することがあります | ||
| トランザクション管理 | 範囲内のキーのロックを使用して実装されている | 直接ツリーにアタッチ可能 |
参考: Storage Engine(Hash Index, LSM-Tree, B-Tree)
まとめ
SSTableとLSMツリーについて軽く見ました。
一般的にインデックスといえばBツリーを思い出します。 Bツリーを深く理解する比較対象としてLSMストレージエンジンを見てみるのもいいなあと思いました。
