2023 年 4 月 6 日に記録され、HBase の原理の学習に基づいています。
LSM の核心思想#
LSM ツリーには次の 3 つの重要な構成要素があります：
-
MemTable
MemTable はメモリ内のデータ構造であり、最新の更新データを保存するために使用されます。これらのデータはキーに基づいて順序付けられ、LSM ツリーはデータを具体的にどのように整理するかについて明確なデータ構造の定義はありません。たとえば、HBase ではスキップリストを使用してメモリ内のキーを順序付けます。
データは一時的にメモリに保存されるため、メモリは信頼性のあるストレージではありません。したがって、通常は WAL（Write-ahead logging、先行書き込みログ）を使用してデータの信頼性を確保します。
-
Immutable MemTable
MemTable が一定のサイズに達すると、Immutable MemTable に変換されます。Immutable MemTable は MemTable を SSTable に変換する中間状態です。書き込み操作は新しい MemTable によって処理され、変換プロセス中にデータの更新操作をブロックしません。
-
SSTable（Sorted String Table）
ソートされたキーと値のセットであり、LSM ツリーのディスク上のデータ構造です。SSTable の読み取りを高速化するために、キーのインデックスの構築やブルームフィルターの使用が行われます。
LSM ツリーのコンパクト戦略#
主に 2 つの基本的な戦略、サイズティアードとレベルドについて説明します。
重要な概念
- Read Amplification（読み取り増幅）：実際に読み取られるデータ量が実際のデータ量よりも大きいこと。LSM ツリーでは、まず MemTable で現在のキーが存在するかどうかを確認し、存在しない場合は SSTable から検索します。
- Write Amplification（書き込み増幅）：実際に書き込まれるデータ量が実際のデータ量よりも大きいこと。LSM ツリーでは、書き込み時に Compact 操作がトリガーされる可能性があり、実際に書き込まれるデータ量がキーのデータ量よりもはるかに大きくなることがあります。
- Space Amplification（スペース増幅）：データが実際に占めるディスクスペースが実際のデータサイズよりも大きいこと。前述の冗長なストレージにより、1 つのキーに対して最新のレコードのみが有効であり、以前のレコードはクリーンアップされて回収される可能性があります。
サイズティアード戦略#
サイズティアード戦略は、各レベルの SSTable のサイズを近く保ち、各レベルの SSTable の数を制限します。上記の図のように、各レベルでは SSTable を N 個に制限し、各レベルの SSTable が N に達すると、これらの SSTable を結合して次のレベルに書き込む Compact 操作がトリガーされます。
これにより、レベルの数が一定の量に達すると、最下層の単一の SSTable のサイズが非常に大きくなります。また、サイズティアード戦略はスペース増幅を引き起こす傾向があります。同じレベルの SSTable でも、各キーのレコードは複数存在する可能性がありますが、そのレベルの SSTable が Compact 操作を実行すると、これらのキーの冗長なレコードが削除されます。
レベルド戦略#
レベルド戦略も階層的なアプローチを採用しており、各レベルで総ファイルサイズを制限します。
ただし、サイズティアード戦略とは異なり、レベルド戦略では各レベルを同じサイズの SSTable に分割します。これらの SSTable は各レベルでグローバルにソートされており、1 つのキーにつき最大 1 つのレコードしか存在しないため、冗長なレコードは存在しません。
レベルド戦略は、サイズティアード戦略と比較して、各レベル内のキーが重複しないため、最悪の場合でも最下層以外のすべてのレベルで重複キーはありません。隣接するレベルのサイズ比率を 10 とすると、冗長性の割合も非常に小さくなります。したがって、スペース増幅の問題は緩和されますが、書き込み増幅の問題はより顕著になります。