LSM ツリー ストレージ エンジンを最初から構築する

序文

この記事では、中心となる概念や構造を含め、ログ構造マージ ツリー (LSM ツリー) を理解する方法を説明します。最終的には、LSM-Tree に基づいて独自のストレージ エンジンを最初から構築できるようになります。

LSMツリーとは何ですか?

基本概念

ログ構造マージ ツリー (LSM ツリー) は、高スループットの書き込み操作用に最適化されたデータ構造です。 Cassandra、RocksDB、LevelDB などのデータベースやストレージ システムで広く使用されています。

LSM ツリーの重要なアイデアは、まずメモリ内のデータ構造 (通常はスキップ リストや AVL ツリーのような順序付けられた構造) に操作を書き込むことです。その後、これらの書き込みはバッチ処理され、SSTable としてディスクに順次書き込まれるため、ランダム I/O が最小限に抑えられます。

基本構造

LSM ツリーは 2 つの主要コンポーネントに分かれています:

• メモリ内ストレージ
  • メモリ内のコア構造は Memtable です。
  • すべての書き込み操作 (設定、削除など) はまず Memtable に送られ、Memtable がこれらの操作を順序付けされたデータ構造 (図の順序付けされたツリーなど) に挿入します。
  • Memtable が特定のサイズのしきい値に達すると、SSTable としてディスクにフラッシュされます (順次に書き込まれます)。
  • 新しい書き込み操作は新しい Memtable で続行されます。
• ディスクストレージ
  • ディスク ストレージには、WAL および SSTable ファイルが含まれます。
  • WAL (先行書き込みログ) は、データベースがクラッシュした場合でも、最近の書き込み (Memtable に保存されているがまだディスクに保存されていない) が失われないようにします。 Memtable へのすべての書き込みは WAL に追加されます。データベースを再起動すると、Memtable をクラッシュ前の状態に復元するために、WAL からのエントリを再生できます。
  • SSTable (Sorted String Table) は、順序付けされた一連のキーと値のペアを保持するデータ ストレージ形式です。
  • Memtable はサイズのしきい値に達すると、新しい SSTable を生成し、ディスクに永続化します。 Memtable はメモリ内の順序付けされたデータ構造に依存しているため、SSTable を構築するときに追加の並べ替えは必要ありません。
  • ディスク上の SSTable は複数のレベルに編成されています。新しくフラッシュされた SSTable は レベル 0 に保存されます。後続の圧縮フェーズ中に、L0 の SSTable は レベル 1 以上のレベルにマージされます。
  • レベルのサイズがしきい値を超えると、SSTable 圧縮プロセスがトリガーされます。圧縮中に、現在のレベルの SSTable がより高いレベルにマージされ、より大きく、より順序付けられたファイルが生成されます。これにより断片化が軽減され、クエリの効率が向上します。

通常、SSTable の構造には、順序付けされた一連のキーと値のペア (データ ブロック) だけではありません。また、インデックス ブロック、メタデータ ブロック、およびその他のコンポーネントも含まれています。これらの詳細については、実装セクションで詳しく説明します。

データの書き込み

データの書き込みには、新しいキーと値のペアの追加または既存のキーと値のペアの更新が含まれます。更新により古いキーと値のペアが上書きされ、後で圧縮プロセス中に削除されます。

データが書き込まれると、まず Memtable に送られ、そこでキーと値のペアがメモリ内の順序付けされたデータ構造に追加されます。同時に、書き込み操作は WAL に記録され、データベース クラッシュ時のデータ損失を防ぐためにディスクに保存されます。

Memtable には定義されたしきい値があります (通常はサイズに基づきます)。 Memtable がこのしきい値を超えると、読み取り専用モード に切り替えられ、新しい SSTable に変換され、ディスク上の レベル 0 に永続化されます。

Memtable が SSTable としてフラッシュされると、対応する WAL ファイルを安全に削除できます。後続の書き込み操作は、新しい Memtable (および新しい WAL) 上で続行されます。

データの削除

LSM-Tree では、データはすぐには削除されません。代わりに、削除は トゥームストーン と呼ばれるメカニズム (論理的な削除と同様) を使用して処理されます。キーと値のペアが削除されると、「廃棄」のマークが付いた新しいエントリが書き込まれ、対応するキーと値のペアが削除されたことを示します。実際の削除は圧縮プロセス中に行われます。

この廃棄ベースの削除により、LSM ツリーの 追加専用 プロパティが保証され、ランダム I/O が回避され、ディスクへの順次書き込みが維持されます。

データのクエリ

データのクエリのプロセスは、Memtable での検索から始まります。キーと値のペアが見つかった場合は、クライアントに返されます。廃棄マークが付けられたキーと値のペアが見つかった場合は、要求されたデータが削除されたことを示し、この情報も返されます。 Memtable でキーが見つからない場合、クエリは レベル 0 から レベル N まで SSTable の検索に進みます。

データのクエリには複数の SSTable ファイルの検索が含まれる可能性があり、ランダムなディスク I/O が発生する可能性があるため、LSM-Tree は一般に、読み取り集中型のワークロードよりも、書き込み負荷の高い ワークロードに適しています。

クエリ パフォーマンスの一般的な最適化の 1 つは、ブルーム フィルター の使用です。ブルーム フィルターは、キーと値のペアが特定の SSTable に存在するかどうかを迅速に判断し、不必要なディスク I/O を削減します。さらに、SSTable のソートされた性質により、バイナリ検索などの効率的な検索アルゴリズムを使用して検索を高速化できます。

データ圧縮

ここでは、LevelDB と RocksDB で使用される レベルドコンパクション戦略 を紹介します。

もう 1 つの一般的な戦略は サイズ階層型圧縮戦略 です。この戦略では、新しくて小さい SSTable が、古くて大きい SSTable に連続的にマージされます。

前述したように、SSTable にはキーによってソートされた一連のエントリが保存されます。レベル圧縮戦略では、SSTable は複数のレベル (レベル 0 からレベル N) に編成されます。

レベル 0 では、SSTable は Memtable から直接フラッシュされるため、重複するキー範囲を持つことができます。ただし、レベル 1 から N では、同じレベル内の SSTable に重複するキー範囲はありませんが、異なるレベルの SSTable 間でのキー範囲の重複は許可されます。

説明のための (完全に正確ではありませんが) 例を以下に示します。 レベル 0 では、最初と 2 番目の SSTable のキー範囲が重複していますが、レベル 1 と レベル 2 では、各レベル内の SSTable のキー範囲が互いに素になっています。ただし、異なるレベル間の SSTable (例: レベル 0 とレベル 1、またはレベル 1 とレベル 2) では、キー範囲が重複する場合があります。

次に、レベルド・コンパクション戦略がこの組織構造をどのように維持するかを見てみましょう。

レベル 0 は特殊なケースであるため、圧縮戦略の説明は 2 つの部分に分かれています。

• レベル 0 からレベル 1 レベル 0 では SSTable 間でキーの重複が許可されるため、レベル 0 から SSTable を選択し、キー範囲が重複するレベル 0 内の他のすべての SSTable を選択することで圧縮が開始されます。次に、重複するキー範囲を持つレベル 1 のすべての SSTable が選択されます。これらの選択された SSTable はマージされ、単一の新しい SSTable に圧縮され、その後レベル 1 に挿入されます。圧縮プロセスに関与した古い SSTable はすべて削除されます。
• レベル N ～ レベル N 1 (N > 0) レベル 1 以降、同じレベル内の SSTable には重複するキー範囲がありません。圧縮中に、SSTable がレベル N から選択され、キー範囲が重複するレベル N 1 のすべての SSTable も選択されます。これらの SSTable はマージされ、1 つ以上の新しい SSTable に圧縮され、レベル N 1 に挿入されます。一方、古い SSTable は削除されます。

レベル 0 からレベル 1 圧縮と レベル N からレベル N 1 (N > 0) 圧縮の主な違いは、下位レベル (レベル) での SSTable の選択にあります。 0 またはレベル N)。

マルチ SSTable の圧縮とマージのプロセスを以下に示します。マージ中は、各キーの最新の値のみが保持されます。最新の値に「廃棄」マーカーがある場合、キーは削除されます。実装では、k-way マージ アルゴリズムを使用してこのプロセスを実行します。

圧縮プロセスに関する上記の説明は、高レベルの概要のみを提供していることに注意することが重要です。実際の実装では多くの詳細に対処する必要があります。

たとえば、LevelDB では、圧縮中にレベル N 1 の新しい SSTable を構築するときに、新しい SSTable がレベル N 2 の 10 個を超える SSTable と重複する場合、プロセスは別の SSTable の構築に切り替わります。これにより、1 回の圧縮に含まれるデータ サイズが制限されます。

実装

上記の LSM-Tree の概要に基づいて、LSM-Tree の基本とその実装に関するいくつかのアイデアを理解できたと思います。次に、LSM-Tree に基づいたストレージ エンジンを最初から構築します。以下では、コアコードのみを紹介します。完全なコードについては、https://github.com/B1NARY-GR0UP/originium を参照してください。

LSM ツリーの実装を次のコア コンポーネントに分割し、それらを 1 つずつ実装します。

• スキップリスト
• ウォル
• メムテーブル
• SSTテーブル
• K-Way マージ
• ブルームフィルター
• レベル圧縮

スキップリスト

データ書き込みの紹介の過程で、LSM ツリーが最初にデータをメモリ内の順序付けされたデータ構造に書き込むと述べました。一般的な順序付きデータ構造とその操作の時間計算量は次のとおりです。

Data Structure	Insert	Delete	Search	Traverse
Skip List	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
AVL Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
Red-Black Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)

スキップ リストを選択した主な理由は 2 つあります。1 つは実装と保守が簡単 (KISS 原則)、もう 1 つは基礎となるリンク リスト構造によりシーケンシャル トラバーサルが容易で、メモリ内データをディスクに永続化することが容易です。

コア構造

スキップ リストの完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go で入手できます。

スキップ リストは、基本リンク リストとその上に構築された複数レベルのインデックスで構成されます。大規模なデータセットの場合、インデックス レイヤーにより検索パスが大幅に短縮されます。

私たちの実装では、スキップ リストのコア構造は次のように定義されています。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

• maxLevel: スキップ リストの最大レベル数 (基本リンク リストには 1 つのレベルがあります)。
• レベル: スキップ リストの現在のレベル数。
• p: ノードがより高いレベルに昇格する確率。たとえば、p = 0.5 の場合、基本レベルに 10 個のノードがあるリンク リストには、次のレベルのインデックスに約 5 個のノードが含まれます。
• rand: p との比較に使用される乱数ジェネレーター
• サイズ: スキップ リストに保存されているキーと値のペアの数。Memtable がサイズのしきい値を超えているかどうかを判断するために使用されます。
• head: ヘッド ノード。各レベルの最初のノードへの参照を保持します。

スキップ リストに格納される要素の構造は次のように定義されます。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

• types.Entry は、キー、値、削除用の廃棄フラグを含む、ストレージ エンジン内のキーと値のペアを表します。

• next: 各レベルの次の要素へのポインターが含まれます。

この構造は抽象的に見えるかもしれないので、例で説明してみましょう:

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

この 3 レベルのスキップ リストでは、ヘッド ノードの次のポインターは各レベルの最初のノードを参照します。要素 3 と 6 には、各レベルの次の要素が格納されます。

たとえば、レベル 2 で要素 19 の次のノードを見つけたい場合は、e19.next[2-1] を使用します。

セット

func (s *SkipList) Set(entry types.Entry)

LSM ツリーは削除を実行するためにトゥームストーンを使用するため、スキップ リストの実装に Delete メソッドは必要ありません。要素を削除するには、エントリの Tombstone を true に設定するだけです。したがって、Set メソッドは、新しいキーと値のペアの挿入、既存のキーと値のペアの更新、要素の削除を処理します。

Set メソッドの実装を見てみましょう。各レベルのノードを最上位からたどることで、設定するキーより小さい最後の要素が更新スライスに保存されます。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

この走査の終わりに、curr は最下位レベルのリンク リストに設定されるキーより小さい最後の要素を指します。したがって、curr の次の要素が設定したいキーと等しいかどうかを確認するだけで済みます。一致する場合、要素はすでに挿入されています。既存の要素を更新して戻ります。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

要素が見つからない場合は、新しい要素として挿入されます。 randomLevel を使用して、この要素のインデックス レベルを計算します。スキップ リストの現在のレベル数を超える場合は、ヘッド ノードを更新スライスに追加し、s.level を新しいレベル数に更新します。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

次に、挿入する要素を構築します。各レベルの次のポインターが更新されて、挿入が完了します。

func (s *SkipList) Set(entry types.Entry)

得る

スキップ リストは、複数のインデックス層に依存して高速な検索操作を実行できます。実装内のネストされた for ループは、インデックスベースの検索操作を表します。最終的に対応する要素が最下位のリンク リストで見つかった場合は、それが返されます。

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key 



<h4>
  
  
  全て
</h4>

<p>スキップ リストを選択した理由の 1 つは、その便利な順次走査です。これは、最下位レベルのリンク リストを走査するだけで可能になります。<br>
</p>

<pre class="brush:php;toolbar:false">// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

ウォール

WAL の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go にあります。

前述したように、WAL (Write-Ahead Logging) の目的は、データベースのクラッシュによる Memtable でのデータ損失を防ぐことです。したがって、WAL は Memtable 上の操作を記録し、データベースの再起動時に WAL ファイルから Memtable を復元する必要があります。

コア構造

WAL のコア構造は次のとおりです。ここで、fd は WAL ファイルのファイル記述子を保存します。

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i 



<h4>
  
  
  書く
</h4>

<p>Memtable で操作を記録する必要があるため、これには基本的に各操作 (Set、Delete) をエントリとして WAL に書き込むことが含まれます。 Write メソッドの定義は次のとおりです:<br>
</p>

<pre class="brush:php;toolbar:false">e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

これらのエントリをファイルに書き込むときは、WAL ファイル形式を標準化する必要があります。ここで使用する形式は長さデータです。まず、エントリをシリアル化し、次にシリアル化されたデータの長さを計算し、最後に長さとシリアル化されたデータを WAL ファイルに順番に書き込みます。

コアコードは次のとおりです:

func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
    curr := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for curr.next[i] != nil && curr.next[i].Key 



<h4>
  
  
  読む
</h4>

<p>WAL ファイル形式 <strong>長さデータ</strong> を使用しているため、読み取り時には、まず 8 バイト (int64) を読み取り、データの長さを取得し、次にこの長さに基づいてデータを読み取り、デシリアライズします。エントリを取得します。</p>

<p>コアコードは次のとおりです:<br>
</p><pre class="brush:php;toolbar:false">type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

メムテーブル

Memtable の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go にあります。

Memtable は、クライアント操作をスキップ リストに書き込み、WAL に記録する役割を果たします。データベースの起動時に WAL からデータを復元することもできます。

コア構造

Memtable のコア構造は次のとおりです。これには、2 つの主要コンポーネント Skiplist と wal が含まれます。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

セット

Set 操作を実行する場合、スキップ リストと WAL の両方を同時に更新する必要があります。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

得る

値を取得するには、単純にスキップ リストの Get オペレーションの結果を返します。

func (s *SkipList) Set(entry types.Entry)

回復する

WAL ファイルから Memtable を復元するには、まず WAL ファイルを読み取り、次に WAL ファイルからエントリ レコードを Memtable に順次適用し、最後に復元された WAL ファイルを削除します。

WAL ファイルのリストを取得します:

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key 



<p>WAL を読み取り、Memtable を回復します:<br>
</p>

<pre class="brush:php;toolbar:false">// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

SSTテーブル

LevelDB SSTable

前回の紹介では、「SSTable (Sorted String Table) は、順序付けされた一連のキーと値のペアを維持するデータ ストレージ形式である」とだけ説明しました。ここでは、SSTableの構造についてより詳しく説明します。

LevelDB では、SSTable は異なる目的を持つ複数のブロックで構成されます。概略図を以下に示します。

• データ ブロック: 順序付けられたキーと値のペアのシーケンスを保存します。
• メタブロック: フィルターと統計の 2 つのタイプが含まれます。フィルター タイプはブルーム フィルターのデータを保存し、統計タイプはデータ ブロックに関する統計情報を保存します。
• MetaIndex Block: メタ ブロックのインデックス情報を保存します。
• インデックス ブロック: データ ブロックのインデックス情報を保存します。
• フッター: 固定長で、MetaIndex BlockとIndex Blockのインデックス情報とマジックナンバーを格納します。

インデックス情報は本質的に BlockHandle と呼ばれるポインター構造であり、対応するブロックを見つけるために使用されるオフセットとサイズの 2 つの属性が含まれます。

私たちのSSTテーブル

SSTable の実装では、LevelDB SSTable 構造を簡素化しました。概略図を以下に示します。

• データ ブロック: 順序付けられたキーと値のペアのシーケンスを保存します。
• メタ ブロック: SSTable のメタデータを保存します。
• インデックス ブロック: データ ブロックのインデックス情報を保存します。
• フッター: 固定長で、メタブロックとインデックスブロックのインデックス情報が格納されます。

SSTable の完全な実装は、https://github.com/B1NARY-GR0UP/originium/tree/main/sstable にあります。

データブロック

データ ブロックの構造は次のように定義され、順序付けられた一連のエントリが格納されます。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

データ ブロックに 3 つの主要なメソッドを実装しました。

• エンコード: データ ブロックをバイナリ データにエンコードします。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

プレフィックス圧縮を使用してキーと値のシーケンスをエンコードします。バッファーには、共通プレフィックスの長さ、サフィックスの長さ、サフィックス自体、値の長さ、値、および「廃棄」マーカーを順番に書き込みます。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

最後に、s2 を使用してデータを圧縮します。

S2 は、Snappy 圧縮アルゴリズムの高性能拡張です。

func (s *SkipList) Set(entry types.Entry)

• Decode: バイナリ データをデータ ブロックにデコードします。

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key 



<p>デコード中は、プロセスが単に逆に行われます。完全なキーと値のペアは、プレフィックスとサフィックスを使用して再構築されます。<br>
</p>

<pre class="brush:php;toolbar:false">// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

• 検索: 二分検索を使用してキーと値のペアを見つけます。

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i 



<h4>
  
  
  インデックスブロック
</h4>

<p>インデックスブロックの構造は以下のように定義されます。各データ ブロックの最初と最後のキーと、対応するデータ ブロックの BlockHandle が保存されます。<br>
</p>

<pre class="brush:php;toolbar:false">e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

同様に、インデックス ブロックは、エンコード、デコード、および検索の 3 つの主要なメソッドを実装します。 Encode メソッドと Decode メソッドの実装の考え方は基本的に同じであるため、Search メソッドに焦点を当てます。

データ ブロックの検索メソッドは、単一のデータ ブロックに格納されている順序付けされたキーと値のシーケンス内で特定のキーと値のペアを見つけるように設計されています。対照的に、インデックス ブロックの Search メソッドは、SSTable 全体内で指定されたキーを含むデータ ブロックを見つけるために使用されます。

func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
    curr := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for curr.next[i] != nil && curr.next[i].Key 



<h4>
  
  
  メタブロックとフッター
</h4>



<pre class="brush:php;toolbar:false">func (s *SkipList) All() []types.Entry {
    var all []types.Entry

    for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
        all = append(all, types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        })
    }

    return all
}

これら 2 つのブロックの実装は非常に簡単で、両方とも Encode メソッドと Decode メソッドのみが必要です。

建てる

SSTable にすべてのブロックを導入した後、SSTable を構築するには、キーと値のペアに基づいて各ブロックを段階的に構築するだけです。最後に、メモリ内のインデックスとエンコードされた SSTable が返されます。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

K-Way マージ

K-Way Merge の完全な実装は、https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway で入手できます。

概念的なセクションでは、複数の SSTable を圧縮およびマージするプロセスを図で説明します。このプロセスは、k-way merge アルゴリズムを使用して実行されます。

k ウェイ マージ アルゴリズムは、k 個のソートされたシーケンスを単一のソートされたシーケンスにマージする方法であり、時間計算量は O(knlogk) です。

このアルゴリズムの 1 つの実装では、min-heap を補助構造として使用します。

• 各シーケンスの最初の要素をヒープに挿入します。
• ヒープから最小値をポップし、結果セットに追加します。ポップされた要素のシーケンスにまだ要素がある場合は、そのシーケンスの次の要素をヒープに挿入します。
• すべてのシーケンスのすべての要素がマージされるまで、このプロセスを繰り返します。

ヒープ

標準ライブラリはコンテナ/ヒープでヒープ実装を提供します。 heap.Interface を実装することで、最小ヒープを構築できます。

• まず、最小ヒープの基本構造を定義します。スライスは要素を保存するために使用されます。各要素には、Entry だけでなく、この要素がどのソートされたシーケンスから生じているかを示す LI も含まれます。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

• sort.Interface メソッドを実装して、ヒープ内の要素を並べ替えます。 Less メソッドには特別な注意が必要です。要素の LI を比較することで、要素が同じキーを持つ場合、以前のシーケンスの要素が最初に順序付けされることが保証されます。これにより、要素を結果セットにマージする際の重複排除が容易になります。この要件は、k-way マージ アルゴリズムを使用する場合、ソートされたシーケンスが古いものから新しいものへの順序で配置される必要があることも意味します。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

• 最後に、Push メソッドと Pop メソッドを実装します。 Push はスライスの最後に要素を追加し、Pop はスライスから最後の要素を削除します。

func (s *SkipList) Set(entry types.Entry)

マージ

Merge メソッドの関数定義:

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key 



<p>k-way マージ アルゴリズム プロセスに従います。</p>

• まず、ソートされた各シーケンスの最初の要素を最小ヒープに挿入します。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

• 最小ヒープから要素を繰り返しポップし、結果キューに追加します。ポップされた要素のシーケンスにまだ要素がある場合は、そのシーケンスの次の要素をヒープに挿入します。ここでは、結果シーケンスの代わりにマップが使用されます。マップは重複排除を自動的に処理し、新しいキーが常に古いキーを上書きします。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

最後に、マップを走査して結果キューに要素を追加し、「廃棄」としてマークされたキーと値のペアをすべて削除します。マップには順序がないため、結果キューは返される前に並べ替える必要があります。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

ブルームフィルター

ブルーム フィルターの完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go にあります。

ブルーム フィルターは、要素がセットのメンバーであるかどうかを効率的にチェックするデータ構造です。

• ビット配列と複数のハッシュ関数を使用します。
• 要素を追加するとき、要素は複数のハッシュ関数を使用してハッシュされ、ビット配列内の異なる位置にマッピングされ、それらの位置が 1 に設定されます。
• クエリ中に、ハッシュ関数によってマップされたすべての位置が 1 の場合、要素は存在する可能性があります。いずれかの位置が 0 の場合、その要素は確実に存在しません。

挿入操作とクエリ操作の両方の時間計算量は O(k) です。k はハッシュ関数の数です。 偽陽性が発生する可能性があります (ブルーム フィルターは、要素がセット内に存在すると予測しますが、実際には存在しません)。しかし、偽陰性は発生しません (ブルーム フィルターは、要素がセット内に存在しないと予測します)セットではありますが、実際にはそうなります)。

真陽性 (TP): システムはイベントを「陽性」と予測し、実際に陽性です。
偽陽性 (FP): システムはイベントを「陽性」であると予測しますが、実際は陰性です。
真陰性 (TN): システムはイベントを「陰性」と予測し、実際に陰性です。
偽陰性 (FN): システムはイベントを「陰性」と予測しますが、実際には陽性です。

コア構造

ブルーム フィルターのコア構造には、ビット配列 (uint8 を使用するように最適化可能) と複数のハッシュ関数が含まれます。

func (s *SkipList) Set(entry types.Entry)

新しい

ブルーム フィルター インスタンスを作成するメソッドは、n (予想される要素数) と p (希望する誤検知率) の 2 つのパラメーターを受け入れます。

まず、パラメータが検証されます。次に、ビット配列のサイズ (m) とハッシュ関数の数 (k) が特定の式を使用して計算されます。最後に、ビット配列とハッシュ関数が m と k に基づいて初期化されます。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

追加

要素を追加するとき、すべてのハッシュ関数を使用してキーのハッシュ値が計算されます。これらの値はビット配列内のインデックスにマッピングされ、対応する位置が true に設定されます。

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

含まれています

キーがセット内にあるかどうかを確認するために、ハッシュ関数はハッシュ値を計算し、それらをビット配列のインデックスにマップします。これらの位置のいずれかが true でない場合、その要素はセットに含まれず、false が返されます。

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

平坦な圧縮

Leveled Compaction の完全な実装は、https://github.com/B1NARY-GR0UP/originium/blob/main/level.go にあります。

K-Way マージやブルーム フィルターなどのコンポーネントを実装した後、実装の最後の部分、つまり LSM-Tree ストレージ エンジンで最も重要な SSTable 圧縮プロセスを完了できます。この実装は、「データ コンパクション」セクションで説明されているレベルド コンパクション戦略に従います。

レベル圧縮戦略では、SSTable は複数のレベル (レベル 0 ～ レベル N) に編成されます。この情報を保存し、さまざまなレベルにわたって SSTable を管理するための構造が必要です。

そこで、levelManager と呼ばれる構造を実装しました。 []*list.List を使用して各レベルの SSTable 情報を保存します。スライスのインデックスはレベルに対応します。スライス内の各要素は list.List であり、特定のレベルのすべての SSTable に関する情報を保持する二重リンク リストです。

func (s *SkipList) Set(entry types.Entry)

コンパクトLN

compactLN メソッドは、レベル N からレベル N 1 (N > 0) までの圧縮を担当します。 LN から最も古い SSTable と、この SSTable と重複するキー範囲を持つ LN 1 のすべての SSTable を選択します。

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key 



<p>選択した SSTable は、古いものから新しいものの順に処理されます。データ ブロックのキーと値のペアは 2 次元スライスに追加され、K-Way マージ アルゴリズムを使用してマージされます。<br>
</p>

<pre class="brush:php;toolbar:false">// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

マージされたキーと値のペアを使用して、新しいブルーム フィルターと SSTable を構築します。新しい SSTable に関する関連情報は、レベル N 1 の最後に追加されます。

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i 



<p>最後に、古い SSTable が削除され、新しく構築された SSTable がディスクに書き込まれます。<br>
</p>

<pre class="brush:php;toolbar:false">e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

compactL0 メソッドは、レベル 0 からレベル 1 への圧縮を処理します。 CompactLN とは異なり、L0 から 1 つの SSTable だけでなく、L0 内の重複するすべての SSTable も選択します。プロセスの残りの部分は、compactLN と同じです。

検索

検索メソッドは、すべての SSTable にわたって対応するキーと値のペアを見つけます。 L0 から開始し、LN まで各レベルを反復します。ブルーム フィルターと SSTable の順序付けされた構造を活用することで、目的のキーと値のペアを含まない SSTable を効率的にスキップできます。

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

DB

これにより、LSM ツリーベースのストレージ エンジンのすべてのコア コンポーネントが実装されました。 LSM-Tree の概要で説明したようにこれらのコンポーネントを組み立てることにより、データベース インターフェイスを完成させることができます。

• 完全なコード: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go

• ドキュメント: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage

まとめ

私たちは LSM-Tree を理解し、そのコアコンポーネントとクライアントリクエストを処理するプロセスに慣れることから始めました。最終的に、私たちは独自の LSM-Tree ストレージ エンジンをゼロから構築しました。

もちろん、この実装は単なるプロトタイプです。実稼働グレードのストレージ エンジンでは、さらに多くの詳細を考慮する必要があります。 ORIGINIUM は今後も最適化と改善を続けていきます。この記事と ORIGINIUM が LSM-Tree への理解をさらに深めるのに役立つことを願っています。

これで、この記事で説明した内容はすべて終了です。エラーや質問がある場合は、プライベートメッセージでご連絡いただくか、コメントを残してください。ありがとうございます!

参照

• https://github.com/B1NARY-GR0UP/originium
• https://www.cnblogs.com/whuanle/p/16297025.html
• https://vonng.gitbook.io/vonng/part-i/ch3#sstables-he-lsm-shu
• https://github.com/google/leveldb/blob/main/doc/table_format.md

以上がLSM ツリー ストレージ エンジンを最初から構築するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。