前言

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

什麼是LSM樹？

基本概念

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

LSM-Tree 的關(guān)鍵思想是首先將操作寫入記憶體資料結(jié)構(gòu)（通常是跳躍列表或 AVL 樹等有序結(jié)構(gòu)）。隨後，這些寫入會被批次並作為 SSTable 順序?qū)懭氪诺瑥亩畲笙薅鹊販p少隨機 I/O。

基本結(jié)構(gòu)

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

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

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

寫入數(shù)據(jù)

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

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

Memtable 有一個定義的閾值（通?；洞笮。?。當Memtable超過此閾值時，它會切換到唯讀模式並轉(zhuǎn)換為新的SSTable，然後在磁碟上持久化到Level 0。

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

刪除數(shù)據(jù)

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

這種基於邏輯刪除的刪除確保了 LSM-Tree 的 僅追加屬性，避免隨機 I/O 並保持對磁碟的順序?qū)懭搿?

查詢數(shù)據(jù)

查詢資料的過程從在Memtable中搜尋開始。如果找到鍵值對，則將其傳回給客戶端。如果找到墓碑標記的鍵值對，表示要求的資料已被刪除，也會傳回此資訊。如果在 Memtable 中找不到該鍵，則查詢將繼續(xù)從 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 中，同一層級內(nèi)的 SSTable 不具有重疊的鍵範圍，儘管不同層級的 SSTable 之間允許鍵範圍重疊。

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

現(xiàn)在讓我們探討一下 Leveled Compaction 策略是如何維持這種組織架構(gòu)的。

由於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 開始，同一層級內(nèi)的 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路合併演算法來執(zhí)行此過程。

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

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

執(zhí)行

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

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

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

跳過列表

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

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

核心結(jié)構(gòu)

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

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

在我們的實作中，Skip List的核心結(jié)構(gòu)定義如下：

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

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

Skip List中儲存的元素結(jié)構(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 表示儲存引擎中的鍵值對，包括鍵、值和用於刪除的墓碑標記。

• next：包含指向每個層級的下一個元素的指標。

這個結(jié)構(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 ]

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

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

放

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

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

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

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

這次遍歷結(jié)束時，curr指向底層鍊錶中最後一個比要設(shè)定的key小的元素。因此，我們只需要檢查 curr 的下一個元素是否等於我們想要設(shè)定的鍵。如果匹配，則該元素已插入；我們更新現(xià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，我們計算該元素的索引等級。如果它超出了跳躍列表中當前的級別數(shù)，我們將頭節(jié)點添加到更新切片中，並將 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)造要插入的元素，更新每一層的next指針，完成插入。

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

得到

跳過清單可以依靠多層索引來執(zhí)行快速搜尋操作。實作中的巢狀 for 迴圈代表基於索引的搜尋操作。如果最終在底層鍊錶中找到對應(yīng)的元素，則傳回該元素。

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
}

全部

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

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

核心結(jié)構(gòu)

WAL的核心結(jié)構(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 的操作，這本質(zhì)上涉及將每個操作（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序列化，然後計算序列化資料的長度，最後將長度和序列化資料依序?qū)懭隬AL檔案。

核心程式碼如下：

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）來取得資料的長度，然後根據(jù)這個長度讀取資料並反序列化檢索條目。

核心程式碼如下：

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 中復原資料。

核心結(jié)構(gòu)

Memtable的核心結(jié)構(gòu)如下，包括兩個主要組件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  
}

放

執(zhí)行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 操作的結(jié)果即可。

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

恢復

從 WAL 檔案復原 Memtable 需要先讀取 WAL 文件，然後依序?qū)?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的結(jié)構(gòu)進行更詳細的解釋。

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

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

索引資訊本質(zhì)上是一個名為BlockHandle的指標結(jié)構(gòu)，它包含兩個屬性：offset和size，用於定位對應(yīng)的Block。

我們的SS表

在我們的 SSTable 實作中，我們簡化了 LevelDB SSTable 結(jié)構(gòu)。示意圖如下：

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

SSTable 的完整實作可以在 https://github.com/B1NARY-GR0UP/originium/tree/main/sstable 找到。

資料區(qū)塊

資料塊的結(jié)構(gòu)定義如下，儲存有序的條目序列。

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

我們?yōu)橘Y料塊實作了三種主要方法：

• Encode：將資料區(qū)塊編碼為二進位資料。

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  
}

我們使用前綴壓縮對鍵值序列進行編碼。在緩衝區(qū)中，我們依序?qū)懭牍睬熬Y的長度、後綴的長度、後綴本身、值的長度、值和「墓碑」標記。

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)

• 解碼：將二進位資料解碼為資料區(qū)塊。

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
}

索引區(qū)塊

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

類似地，索引區(qū)塊實作了三個主要方法：編碼、解碼和搜尋。 Encode 和 Decode 方法的實作想法基本上相同，所以我們專注於 Search 方法。

資料區(qū)塊的搜尋方法旨在在單一資料區(qū)塊中儲存的有序鍵值序列中定位特定的鍵值對。相反，索引區(qū)塊的搜尋方法用於在整個 SSTable 中定位包含給定鍵的資料區(qū)塊。

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後，建構(gòu)SSTable只需根據(jù)鍵值對逐步建立每個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)。

此演算法的一個實作使用 最小堆 作為輔助結(jié)構(gòu)：

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

堆疊

標準函式庫在容器/堆中提供了堆實作。透過實作heap.Interface，我們可以建構(gòu)一個最小堆。

• 首先，定義最小堆的基本結(jié)構(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方法對堆中的元素進行排序。需要特別注意的是Less方法：透過比較元素的LI，我們確保當元素具有相同的鍵時，來自較早序列的元素會先排序。這有助於將元素合併到結(jié)果集中時進行重複資料刪除。這項要求也意味著在使用 k 路合併演算法時，排序後的序列應(yīng)按照從最舊到最新的順序排列。

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方法的函數(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路合併演算法流程。

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

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é)果佇列中，刪除任何標記為「墓碑」的鍵值對。由於map是無序的，所以結(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 找到。

布隆過濾器是一種資料結(jié)構(gòu)，可以有效檢查元素是否是集合的成員。

• 它使用一個位數(shù)組和多個雜湊函數(shù)。
• 新增元素時，使用多個雜湊函數(shù)對元素進行雜湊處理，將其對應(yīng)到位數(shù)組中的不同位置，並將這些位置設(shè)為 1。
• 在查詢過程中，如果雜湊函數(shù)對應(yīng)的所有位置均為1，則該元素可能存在。如果任意位置為0，則該元素肯定不存在。

插入和查詢操作的時間複雜度都是O(k)，其中k是雜湊函數(shù)的數(shù)量。 可能會出現(xiàn)誤報（布隆過濾器預測某個元素在集合中，但事實並非如此），但不會出現(xiàn)誤報（布隆過濾器預測某個元素不在集合中）在集合中，但實際上是）。

真陽性（TP）：系統(tǒng)將事件預測為“陽性”，而且它確實是陽性。
誤報（FP）：系統(tǒng)將事件預測為“正”，但實際上是負的。
真陰性（TN）：系統(tǒng)將事件預測為“陰性”，並且它確實是陰性。
假陰性（FN）：系統(tǒng)將事件預測為“陰性”，但實際上是陽性。

核心結(jié)構(gòu)

布隆過濾器的核心結(jié)構(gòu)包括位數(shù)組（可以最佳化為使用 uint8）和多個雜湊函數(shù)。

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

新的

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

首先，驗證參數(shù)。然後，使用特定公式計算位數(shù)組的大?。╩）和雜湊函數(shù)的數(shù)量（k）。最後根據(jù)m和k初始化位數(shù)組和哈希函數(shù)。

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

添加

當新增元素時，所有雜湊函數(shù)都用於計算鍵的雜湊值。然後將這些值對應(yīng)到位數(shù)組中的索引，並將對應(yīng)位置設(shè)為 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  
}

包含

為了檢查某個鍵是否在集合中，雜湊函數(shù)計算雜湊值並將它們對應(yīng)到位數(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 Merge 和 Bloom Filter 等元件後，我們就可以完成實作的最後部分，也就是 LSM-Tree 儲存引擎中最關(guān)鍵的 SSTable 壓縮過程。此實作遵循「資料壓縮」部分中所述的分級壓縮策略。

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

因此，我們實作了一個名為 levelManager 的結(jié)構(gòu)。我們使用一個[]*list.List來儲存每個層級的SSTable訊息，其中切片的索引對應(yīng)於該層級。切片中的每個元素都是一個列表。 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 會依照從最舊到最新的順序處理。來自資料區(qū)塊的鍵值對被加入到二維切片中，然後使用 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的相關(guān)資訊附加在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 中找到對應(yīng)的鍵值對。它從 L0 開始，迭代每個層級直至 LN。透過利用布林過濾器和 SSTable 的有序結(jié)構(gòu)，可以有效地跳過不包含所需鍵值對的 SSTable。

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

資料庫

至此，我們已經(jīng)實現(xiàn)了基於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 儲存引擎。

當然，這個實作只是一個原型。生產(chǎn)級儲存引擎需要考慮更多細節(jié)。 ORIGINIUM未來將持續(xù)進行最佳化和改進。希望本文和 ORIGINIUM 能幫助您加深對 LSM-Tree 的理解。

本文涵蓋的所有內(nèi)容到此結(jié)束。如果有任何錯誤或疑問，請隨時透過私訊聯(lián)繫或發(fā)表評論。謝謝！

參考

• 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 儲存引擎的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！