從頭開始建造 LSM-Tree 儲存引擎

前言

本文將引導您了解日誌結構合併樹（LSM-Tree），包括其核心概念和結構。到最後，您將能夠從頭開始建立自己的基於 LSM-Tree 的儲存引擎。

什麼是LSM樹？

基本概念

日誌結構合併樹（LSM-Tree）是一種針對高吞吐量寫入操作進行最佳化的資料結構。廣泛應用於資料庫和儲存系統，例如Cassandra、RocksDB、LevelDB。

LSM-Tree 的關鍵思想是首先將操作寫入記憶體資料結構（通常是跳躍列表或 AVL 樹等有序結構）。隨後，這些寫入會被批次並作為 SSTable 順序寫入磁碟，從而最大限度地減少隨機 I/O。

基本結構

LSM-Tree 分為兩個主要組件：

• 記憶體儲存
  • 記憶體中的核心結構是Memtable.
  • 所有寫入操作（例如，設定、刪除）首先進入 Memtable，Memtable 將這些操作插入到有序資料結構中（例如圖中的有序樹）。
  • 一旦Memtable達到一定的大小閾值，它就會作為SSTable刷新到磁碟（順序寫入）。
  • 新的寫入操作繼續在新的 Memtable 上進行。
• 磁碟儲存
  • 磁碟儲存涉及WAL和SSTable檔案。
  • WAL（預寫日誌） 確保最近的寫入（儲存在 Memtable 中但尚未持久化到磁碟）在資料庫崩潰時不會遺失。對 Memtable 的每次寫入都會附加到 WAL 中。重新啟動資料庫後，可以重播 WAL 中的項目，以便將 Memtable 還原到崩潰前的狀態。
  • SSTable（排序字串表） 是一種資料儲存格式，保存一系列有序的鍵值對。
  • 當 Memtable 達到其大小閾值時，它會產生一個新的 SSTable 並將其儲存到磁碟。由於 Memtable 依賴記憶體中的有序資料結構，因此在建構 SSTable 時不需要額外的排序。
  • 磁碟上的 SSTable 被組織成多個層級。新刷新的 SSTable 儲存在 Level 0 中。在後續的壓縮階段，L0 中的 SSTable 會合併到 1 級 及更高等級。
  • 當等級的大小超過閾值時，會觸發 SSTable 壓縮過程。在壓縮過程中，目前層級中的 SSTable 會合併到更高層級中，從而產生更大、更有序的檔案。這減少了碎片並提高了查詢效率。

通常，SSTable 的結構不僅包括一系列有序的鍵值對（資料塊）。它也包含索引區塊、元資料區塊和其他元件。這些細節將在實施部分深入討論。

寫入數據

寫入資料涉及新增新的鍵值對或更新現有的鍵值對。更新會覆蓋舊的鍵值對，這些鍵值對稍後會在壓縮過程中被刪除。

資料寫入時，首先進入Memtable，其中鍵值對被加入到記憶體中的有序資料結構中。同時，寫入操作會記錄在 WAL 中並持久保存到磁碟，以防止資料庫崩潰時資料遺失。

Memtable 有一個定義的閾值（通常基於大小）。當Memtable超過此閾值時，它會切換到唯讀模式並轉換為新的SSTable，然後在磁碟上持久化到Level 0。

一旦 Memtable 被刷新為 SSTable，對應的 WAL 檔案就可以安全刪除。後續的寫入操作將在新的 Memtable（和新的 WAL）上進行。

刪除數據

在LSM-Tree中，資料不會立即被刪除。相反，刪除是使用一種名為 邏輯刪除 的機制來處理的（類似於軟刪除）。當刪除某個鍵值對時，會寫入一個標示「墓碑」的新條目，表示對應的鍵值對被刪除。實際的移除發生在壓縮過程中。

這種基於邏輯刪除的刪除確保了 LSM-Tree 的 僅追加屬性，避免隨機 I/O 並保持對磁碟的順序寫入。

查詢數據

查詢資料的過程從在Memtable中搜尋開始。如果找到鍵值對，則將其傳回給客戶端。如果找到墓碑標記的鍵值對，表示要求的資料已被刪除，也會傳回此資訊。如果在 Memtable 中找不到該鍵，則查詢將繼續從 Level 0 到 Level N 搜尋 SSTable。

由於查詢資料可能涉及搜尋多個SSTable 檔案並可能導致隨機磁碟I/O，因此LSM-Tree 通常更適合寫入密集型工作負載，而不是讀取密集型工作負載。

查詢效能的常見最佳化是使用布隆過濾器。布隆過濾器可以快速判斷特定SSTable中是否存在某個鍵值對，減少不必要的磁碟I/O。此外，SSTables 的排序特性使得高效的搜尋演算法（例如二分搜尋）能夠用於更快的查找。

資料壓縮

這裡，我們介紹一下Leveled Compaction策略，LevelDB和RocksDB都使用該策略

另一個常見策略是大小分層壓縮策略，其中較新且較小的 SSTable 會依序合併到較舊且較大的 SSTable 中。

如前所述，SSTable 儲存一系列按鍵排序的項目。在分級壓縮策略中，SSTables被組織成多個層級（等級0到等級N）。

在 Level 0 中，SSTable 可以具有重疊的鍵範圍，因為它們是直接從 Memtable 中刷新的。然而，在等級 1 到 N 中，同一層級內的 SSTable 不具有重疊的鍵範圍，儘管不同層級的 SSTable 之間允許鍵範圍重疊。

下面顯示了一個說明性（儘管不完全準確）的範例。在Level 0 中，第一個和第二個SSTable 的鍵範圍重疊，而在Level 1 和Level 2 中，每個等級內的SSTable 具有不相交的鍵範圍。然而，不同層級（例如，層級 0 和層級 1，或層級 1 和層級 2）之間的 SSTable 可能具有重疊的按鍵範圍。

現在讓我們探討一下 Leveled Compaction 策略是如何維持這種組織架構的。

由於Level 0是一個特例，所以壓縮策略討論分為兩部分：

• 0 級到 1 級 由於 Level 0 允許 SSTable 之間重疊鍵，因此壓縮首先從 Level 0 選擇一個 SSTable，以及 Level 0 中與其具有重疊鍵範圍的所有其他 SSTable。接下來，選擇等級 1 中具有重疊鍵範圍的所有 SSTable。這些選取的 SSTable 被合併並壓縮為一個新的 SSTable，然後插入到 Level 1。壓縮過程中涉及的所有舊 SSTable 都將被刪除。
• N 級到 N 1 級（N > 0） 從等級 1 開始，同一層級內的 SSTable 沒有重疊的鍵範圍。在compaction過程中，會從Level N中選擇一個SSTable，並且會選擇Level N 1中所有具有重疊鍵範圍的SSTable。這些 SSTable 被合併並壓縮為一個或多個新的 SSTable，這些新的 SSTable 被插入到 Level N 1，同時舊的 SSTable 被刪除。

Level 0 to Level 1 壓縮和 Level N to Level N 1 (N > 0) 壓縮的主要差異在於較低等級（Level 0 或 N 級）。

多SSTable的壓縮和合併流程如下圖所示。合併期間，僅保留每個鍵的最新值。如果最新值具有「墓碑」標記，則該鍵將被刪除。在實作中，我們使用k路合併演算法來執行此過程。

要注意的是，上面對壓縮過程的描述僅提供了進階概述。實際實施過程中還有很多細節需要解決。

例如，在LevelDB中，在壓縮過程中為Level N 1建立新的SSTable時，如果新的SSTable與Level N 2中的10個以上SSTable重疊，則流程切換到建置另一個SSTable。這限制了單次壓縮所涉及的資料大小。

執行

透過上面對LSM-Tree的概述，相信您現在已經對LSM-Tree有了基本的了解，並對其實現有了一些想法。接下來我們將從頭開始建立一個基於LSM-Tree的儲存引擎。下面，我們只介紹核心程式碼；完整程式碼請參考https://github.com/B1NARY-GR0UP/originium。

我們將LSM-Tree的實作分解為以下核心元件並一一實現：

• 跳過列表
• 沃爾
• 記憶體表
• SSTable
• K-Way 合併
• 布隆過濾器
• 分層壓實

跳過列表

在介紹資料寫入的過程中，我們提到LSM-Tree首先將資料寫入記憶體中的有序資料結構。一些常見的有序資料結構及其操作的時間複雜度如下：

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)

我們選擇Skip List主要有兩個原因：它更容易實現和維護（KISS原則），底層鍊錶結構有利於順序遍歷，更容易將記憶體中的資料持久化到磁碟。

核心結構

跳過清單的完整實作可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go 取得。

跳過列表由一個基本鍊錶和建立在其之上的多層索引組成。對於大型資料集，索引層顯著縮短了搜尋路徑。

在我們的實作中，Skip List的核心結構定義如下：

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

• maxLevel：Skip List 的最大等級數（基礎鍊錶只有一級）。
• level：跳過列表中目前的等級數。
• p：節點晉升到更高等級的機率。例如，如果 p = 0.5，則基礎層級有 10 個節點的鍊錶將在下一層索引中具有約 5 個節點。
• rand：用於與 p 進行比較的隨機數產生器。
• size：Skip List 中儲存的鍵值對數量，用於判斷 Memtable 是否超出其大小閾值。
• head：頭節點，保存每個層級中第一個節點的引用。

Skip List中儲存的元素結構定義如下：

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 ]

在這個三級Skip List中，頭節點的next指標引用每一級的第一個節點。元素 3 和 6 儲存每個層級的下一個元素。

例如，如果我們想在第 2 層尋找元素 19 的下一個節點，我們使用 e19.next[2-1]。

放

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

LSM-Tree 使用邏輯刪除來執行刪除，因此我們在跳躍清單實作中不需要刪除方法。要刪除元素，只需將條目的墓碑設為 true 即可。因此，Set 方法處理插入新的鍵值對、更新現有鍵值對以及刪除元素。

讓我們來探索Set方法的實作。透過從最高處開始遍歷每一層的節點，將最後一個比要設定的key小的元素保存在更新切片中。

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

這次遍歷結束時，curr指向底層鍊錶中最後一個比要設定的key小的元素。因此，我們只需要檢查 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 ]

接下來構造要插入的元素，更新每一層的next指針，完成插入。

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

全部

我們選擇跳過清單的一個原因是它方便的順序遍歷，只需遍歷底層鍊錶即可實現。

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

寫

由於我們需要記錄對 Memtable 的操作，這本質上涉及將每個操作（Set、Delete）作為一個 Entry 寫入 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 檔案格式。我們這裡使用的格式是長度資料。首先我們將Entry序列化，然後計算序列化資料的長度，最後將長度和序列化資料依序寫入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負責將客戶端操作寫入skip list並記錄在WAL中。它還可以在資料庫啟動時從 WAL 中復原資料。

核心結構

Memtable的核心結構如下，包括兩個主要組件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操作時，skip list和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 檔案中的 Entry 記錄套用到 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 < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

讀取 WAL 並還原 Memtable：

// 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
}

SS表

LevelDB SS表

在前面的介紹中，我們只提到「SSTable（Sorted String Table）是一種維護一系列有序鍵值對的資料儲存格式」。在這裡，我們將對SSTable的結構進行更詳細的解釋。

在LevelDB中，SSTable由多個具有不同用途的區塊組成。示意圖如下：

• 資料塊：儲存一系列有序的鍵值對。
• 元區塊：包括過濾和統計兩種類型。過濾器類型儲存布隆過濾器的數據，而統計類型則儲存有關數據塊的統計資料。
• 元索引塊：儲存元塊的索引資訊。
• 索引塊：儲存資料塊的索引資訊。
• Footer：長度固定，存放MetaIndex Block和Index Block的索引訊息，以及一個幻數。

索引資訊本質上是一個名為BlockHandle的指標結構，它包含兩個屬性：offset和size，用於定位對應的Block。

我們的SS表

在我們的 SSTable 實作中，我們簡化了 LevelDB SSTable 結構。示意圖如下：

• 資料塊：儲存一系列有序的鍵值對。
• 元資料塊：儲存SSTable的一些元資料。
• 索引塊：儲存資料塊的索引資訊。
• 頁腳：長度固定，存放Meta Block和Index Block的索引資訊。

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
}

我們為資料塊實作了三種主要方法：

• Encode：將資料區塊編碼為二進位資料。

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)

• 解碼：將二進位資料解碼為資料區塊。

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
}

在解碼過程中，過程只是相反。使用前綴和後綴重構完整的鍵值對。

// 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
}

索引區塊

索引塊的結構定義如下。它儲存每個資料塊的第一個和最後一個鍵，以及對應資料塊的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)))

類似地，索引區塊實作了三個主要方法：編碼、解碼和搜尋。 Encode 和 Decode 方法的實作想法基本上相同，所以我們專注於 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 < 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
}

這兩個Block的實作非常簡單，都只需要Encode和Decode方法。

建造

引入SSTable中的所有Block後，建構SSTable只需根據鍵值對逐步建立每個Block。最後返回記憶體索引和編碼後的SSTable。

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

K 路合併

K-Way Merge 的完整實作可在 https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway 取得。

在概念部分，我們以圖表說明了壓縮和合併多個SSTable的過程。此過程是使用 k 路合併 演算法完成的。

k 路合併演算法是將 k 個排序序列合併為單一排序序列的方法，時間複雜度為 O(knlogk)。

此演算法的一個實作使用 最小堆 作為輔助結構：

• 將每個序列的第一個元素插入堆中。
• 從堆中彈出最小值並將其添加到結果集中。如果彈出元素的序列還有更多元素，則將該序列中的下一個元素插入到堆疊中。
• 重複此過程，直到合併所有序列中的所有元素。

堆疊

標準函式庫在容器/堆中提供了堆實作。透過實作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 路合併演算法時，排序後的序列應按照從最舊到最新的順序排列。

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

遵循k路合併演算法流程。

• 首先，將每個排序序列的第一個元素插入到最小堆中。

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  
}

最後，遍歷映射以將元素新增至結果佇列中，刪除任何標記為「墓碑」的鍵值對。由於map是無序的，所以結果隊列在回傳之前需要先排序。

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)

新的

建立 Bloom Filter 實例的方法接受兩個參數：n（期望的元素數量）和 p（期望的誤報率）。

首先，驗證參數。然後，使用特定公式計算位數組的大小（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 Merge 和 Bloom Filter 等元件後，我們就可以完成實作的最後部分，也就是 LSM-Tree 儲存引擎中最關鍵的 SSTable 壓縮過程。此實作遵循「資料壓縮」部分中所述的分級壓縮策略。

在分級壓縮策略中，SSTables被組織成多個層級（Level 0 - Level N）。我們需要一個結構來儲存這些資訊並管理不同層級的 SSTable。

因此，我們實作了一個名為 levelManager 的結構。我們使用一個[]*list.List來儲存每個層級的SSTable訊息，其中切片的索引對應於該層級。切片中的每個元素都是一個列表。 List，雙向鍊錶，保存特定層級中所有 SSTable 的資訊。

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

緊湊型LN

compactLN 方法負責 Level N 到 Level N 1 (N > 0) 的壓縮。它從 LN 中選擇最舊的 SSTable 以及 LN 1 中與此 SSTable 有重疊鍵範圍的所有 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 會依照從最舊到最新的順序處理。來自資料區塊的鍵值對被加入到二維切片中，然後使用 K-Way Merge 演算法進行合併。

// 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
}

透過合併的鍵值對，我們建立了一個新的 Bloom Filter 和 SSTable。新SSTable的相關資訊附加在Level 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，並將新建的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中選擇一個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
}

資料庫

至此，我們已經實現了基於LSM-Tree的儲存引擎的所有核心元件。透過按照 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-Tree 儲存引擎的詳細內容。更多資訊請關注PHP中文網其他相關文章！