序文

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

LSMツリーとは何ですか?

基本概念

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

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

基本構(gòu)造

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

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

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

データの書き込み

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

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

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

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

データの削除

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

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

データのクエリ

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

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

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

データ圧縮

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

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

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

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

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

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

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

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

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

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

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

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

実裝

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

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

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

スキップリスト

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

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

コア構(gòu)造

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

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

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

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

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

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

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 は、キー、値、削除用の廃棄フラグを含む、ストレージ エンジン內(nèi)のキーと値のペアを表します。

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

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

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 ツリーは削除を?qū)g行するためにトゥームストーンを使用するため、スキップ リストの実裝に Delete メソッドは必要ありません。要素を削除するには、エントリの Tombstone を true に設(shè)定するだけです。したがって、Set メソッドは、新しいキーと値のペアの挿入、既存のキーと値のペアの更新、要素の削除を処理します。

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

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

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

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 を使用して、この要素のインデックス レベルを計算します。スキップ リストの現(xiàn)在のレベル數(shù)を超える場合は、ヘッド ノードを更新スライスに追加し、s.level を新しいレベル數(shù)に更新します。

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 ]

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

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

得る

スキップ リストは、複數(shù)のインデックス層に依存して高速な検索操作を?qū)g行できます。実裝內(nèi)のネストされた 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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

全て

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

// 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 を復(fù)元する必要があります。

コア構(gòu)造

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

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

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

書く

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

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 ファイル形式を標(biāo)準(zhǔn)化する必要があります。ここで使用する形式は長さデータです。まず、エントリをシリアル化し、次にシリアル化されたデータの長さを計算し、最後に長さとシリアル化されたデータを 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 < key {
            curr = curr.next[i]
        }
    }

    curr = curr.next[0]

    if curr != nil && curr.Key == key {
        return types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        }, true
    }
    return types.Entry{}, false
}

読む

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

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

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 からデータを復(fù)元することもできます。

コア構(gòu)造

Memtable のコア構(gòu)造は次のとおりです。これには、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 操作を?qū)g行する場合、スキップ リストと 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 オペレーションの結(jié)果を返します。

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

回復(fù)する

WAL ファイルから Memtable を復(fù)元するには、まず WAL ファイルを読み取り、次に WAL ファイルからエントリ レコードを Memtable に順次適用し、最後に復(fù)元された 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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

WAL を読み取り、Memtable を回復(fù)します:

// 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の構(gòu)造についてより詳しく説明します。

LevelDB では、SSTable は異なる目的を持つ複數(shù)のブロックで構(gòu)成されます。概略図を以下に示します。

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

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

私たちのSSTテーブル

SSTable の実裝では、LevelDB SSTable 構(gòu)造を簡素化しました。概略図を以下に示します。

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

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

データブロック

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

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

データ ブロックに 3 つの主要なメソッドを?qū)g裝しました。

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

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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

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

// 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 < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

インデックスブロック

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

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 つの主要なメソッドを?qū)g裝します。 Encode メソッドと Decode メソッドの実裝の考え方は基本的に同じであるため、Search メソッドに焦點(diǎn)を當(dāng)てます。

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

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 < key {
            curr = curr.next[i]
        }
    }

    curr = curr.next[0]

    if curr != nil && curr.Key == key {
        return types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        }, true
    }
    return types.Entry{}, 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 にすべてのブロックを?qū)毪筏酷?、SSTable を構(gòu)築するには、キーと値のペアに基づいて各ブロックを段階的に構(gòu)築するだけです。最後に、メモリ內(nèi)のインデックスとエンコードされた 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 で入手できます。

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

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

このアルゴリズムの 1 つの実裝では、min-heap を補(bǔ)助構(gòu)造として使用します。

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

ヒープ

標(biāo)準(zhǔn)ライブラリはコンテナ/ヒープでヒープ実裝を提供します。 heap.Interface を?qū)g裝することで、最小ヒープを構(gòu)築できます。

• まず、最小ヒープの基本構(gòu)造を定義します。スライスは要素を保存するために使用されます。各要素には、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 メソッドを?qū)g裝して、ヒープ內(nèi)の要素を並べ替えます。 Less メソッドには特別な注意が必要です。要素の LI を比較することで、要素が同じキーを持つ場合、以前のシーケンスの要素が最初に順序付けされることが保証されます。これにより、要素を結(jié)果セットにマージする際の重複排除が容易になります。この要件は、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 メソッドを?qū)g裝します。 Push はスライスの最後に要素を追加し、Pop はスライスから最後の要素を削除します。

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

マージ

Merge メソッドの関數(shù)定義:

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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

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

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

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

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

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  
}

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

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 にあります。

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

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

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

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

コア構(gòu)造

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

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

新しい

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

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

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

追加

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

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  
}

含まれています

キーがセット內(nèi)にあるかどうかを確認(rèn)するために、ハッシュ関數(shù)はハッシュ値を計算し、それらをビット配列のインデックスにマップします。これらの位置のいずれかが 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 マージやブルーム フィルターなどのコンポーネントを?qū)g裝した後、実裝の最後の部分、つまり LSM-Tree ストレージ エンジンで最も重要な SSTable 圧縮プロセスを完了できます。この実裝は、「データ コンパクション」セクションで説明されているレベルド コンパクション戦略に従います。

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

そこで、levelManager と呼ばれる構(gòu)造を?qū)g裝しました。 []*list.List を使用して各レベルの SSTable 情報を保存します。スライスのインデックスはレベルに対応します。スライス內(nèi)の各要素は list.List であり、特定のレベルのすべての SSTable に関する情報を保持する二重リンク リストです。

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

コンパクトLN

compactLN メソッドは、レベル N からレベル N 1 (N > 0) までの圧縮を擔(dān)當(dāng)します。 LN から最も古い SSTable と、この SSTable と重複するキー範(fàn)囲を持つ 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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

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

// 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 を構(gòu)築します。新しい SSTable に関する関連情報は、レベル N 1 の最後に追加されます。

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

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

最後に、古い SSTable が削除され、新しく構(gòu)築された SSTable がディスクに書き込まれます。

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 內(nèi)の重複するすべての SSTable も選択します。プロセスの殘りの部分は、compactLN と同じです。

検索

検索メソッドは、すべての SSTable にわたって対応するキーと値のペアを見つけます。 L0 から開始し、LN まで各レベルを反復(fù)します。ブルーム フィルターと SSTable の順序付けされた構(gòu)造を活用することで、目的のキーと値のペアを含まない 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 を理解し、そのコアコンポーネントとクライアントリクエストを処理するプロセスに慣れることから始めました。最終的に、私たちは獨(dú)自の LSM-Tree ストレージ エンジンをゼロから構(gòu)築しました。

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

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

參照

• 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 ツリー ストレージ エンジンを最初から構(gòu)築するの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。