前言

本文將引導(dǎo)您了解日志結(jié)構(gòu)合并樹(shù)（LSM-Tree），包括其核心概念和結(jié)構(gòu)。到最后，您將能夠從頭開(kāi)始構(gòu)建自己的基于 LSM-Tree 的存儲(chǔ)引擎。

什么是LSM樹(shù)？

基本概念

日志結(jié)構(gòu)合并樹(shù)（LSM-Tree）是一種針對(duì)高吞吐量寫(xiě)入操作進(jìn)行優(yōu)化的數(shù)據(jù)結(jié)構(gòu)。廣泛應(yīng)用于數(shù)據(jù)庫(kù)和存儲(chǔ)系統(tǒng)，例如Cassandra、RocksDB、LevelDB。

LSM-Tree 的關(guān)鍵思想是首先將操作寫(xiě)入內(nèi)存數(shù)據(jù)結(jié)構(gòu)（通常是跳躍列表或 AVL 樹(shù)等有序結(jié)構(gòu)）。隨后，這些寫(xiě)入會(huì)被批量并作為 SSTable 順序?qū)懭氪疟P(pán)，從而最大限度地減少隨機(jī) I/O。

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

LSM-Tree 分為兩個(gè)主要組件：

• 內(nèi)存存儲(chǔ)
  • 內(nèi)存中的核心結(jié)構(gòu)是Memtable.
  • 所有寫(xiě)操作（例如，設(shè)置、刪除）首先進(jìn)入 Memtable，Memtable 將這些操作插入到有序數(shù)據(jù)結(jié)構(gòu)中（例如圖中的有序樹(shù)）。
  • 一旦Memtable達(dá)到一定的大小閾值，它就會(huì)作為SSTable刷新到磁盤(pán)（順序?qū)懭耄?/li>
  • 新的寫(xiě)入操作繼續(xù)在新的 Memtable 上進(jìn)行。
• 磁盤(pán)存儲(chǔ)
  • 磁盤(pán)存儲(chǔ)涉及WAL和SSTable文件。
  • WAL（預(yù)寫(xiě)日志） 確保最近的寫(xiě)入（存儲(chǔ)在 Memtable 中但尚未持久化到磁盤(pán)）在數(shù)據(jù)庫(kù)崩潰時(shí)不會(huì)丟失。對(duì) Memtable 的每次寫(xiě)入都會(huì)附加到 WAL 中。重新啟動(dòng)數(shù)據(jù)庫(kù)后，可以重播 WAL 中的條目，以便將 Memtable 恢復(fù)到崩潰前的狀態(tài)。
  • SSTable（排序字符串表） 是一種數(shù)據(jù)存儲(chǔ)格式，保存一系列有序的鍵值對(duì)。
  • 當(dāng) Memtable 達(dá)到其大小閾值時(shí)，它會(huì)生成一個(gè)新的 SSTable 并將其保存到磁盤(pán)。由于 Memtable 依賴于內(nèi)存中的有序數(shù)據(jù)結(jié)構(gòu)，因此在構(gòu)建 SSTable 時(shí)不需要額外的排序。
  • 磁盤(pán)上的 SSTable 被組織成多個(gè)級(jí)別。新刷新的 SSTable 存儲(chǔ)在 Level 0 中。在后續(xù)的壓縮階段，L0 中的 SSTable 會(huì)合并到 1 級(jí) 及更高級(jí)別。
  • 當(dāng)級(jí)別的大小超過(guò)閾值時(shí)，會(huì)觸發(fā) SSTable 壓縮過(guò)程。在壓縮過(guò)程中，當(dāng)前級(jí)別中的 SSTable 會(huì)合并到更高級(jí)別中，從而生成更大、更有序的文件。這減少了碎片并提高了查詢效率。

通常，SSTable 的結(jié)構(gòu)不僅僅包括一系列有序的鍵值對(duì)（數(shù)據(jù)塊）。它還包含索引塊、元數(shù)據(jù)塊和其他組件。這些細(xì)節(jié)將在實(shí)施部分深入討論。

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

寫(xiě)入數(shù)據(jù)涉及添加新的鍵值對(duì)或更新現(xiàn)有的鍵值對(duì)。更新會(huì)覆蓋舊的鍵值對(duì)，這些鍵值對(duì)稍后會(huì)在壓縮過(guò)程中被刪除。

數(shù)據(jù)寫(xiě)入時(shí)，首先進(jìn)入Memtable，其中鍵值對(duì)被添加到內(nèi)存中的有序數(shù)據(jù)結(jié)構(gòu)中。同時(shí)，寫(xiě)入操作會(huì)記錄在 WAL 中并持久保存到磁盤(pán)，以防止數(shù)據(jù)庫(kù)崩潰時(shí)數(shù)據(jù)丟失。

Memtable 有一個(gè)定義的閾值（通?；诖笮。?。當(dāng)Memtable超過(guò)此閾值時(shí)，它會(huì)切換到只讀模式并轉(zhuǎn)換為新的SSTable，然后在磁盤(pán)上持久化到Level 0。

一旦 Memtable 被刷新為 SSTable，相應(yīng)的 WAL 文件就可以被安全刪除。后續(xù)的寫(xiě)入操作將在新的 Memtable（和新的 WAL）上進(jìn)行。

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

在LSM-Tree中，數(shù)據(jù)不會(huì)立即被刪除。相反，刪除是使用一種名為 邏輯刪除 的機(jī)制來(lái)處理的（類(lèi)似于軟刪除）。當(dāng)刪除某個(gè)鍵值對(duì)時(shí)，會(huì)寫(xiě)入一個(gè)標(biāo)有“墓碑”的新條目，表示對(duì)應(yīng)的鍵值對(duì)被刪除。實(shí)際的移除發(fā)生在壓縮過(guò)程中。

這種基于邏輯刪除的刪除確保了 LSM-Tree 的 僅追加屬性，避免隨機(jī) I/O 并保持對(duì)磁盤(pán)的順序?qū)懭搿?/p>

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

查詢數(shù)據(jù)的過(guò)程從在Memtable中搜索開(kāi)始。如果找到鍵值對(duì)，則將其返回給客戶端。如果找到墓碑標(biāo)記的鍵值對(duì)，則表明請(qǐng)求的數(shù)據(jù)已被刪除，也會(huì)返回此信息。如果在 Memtable 中找不到該鍵，則查詢將繼續(xù)從 Level 0 到 Level N 搜索 SSTable。

由于查詢數(shù)據(jù)可能涉及搜索多個(gè) SSTable 文件并可能導(dǎo)致隨機(jī)磁盤(pán) I/O，因此 LSM-Tree 通常更適合寫(xiě)入密集型工作負(fù)載，而不是讀取密集型工作負(fù)載。

查詢性能的一種常見(jiàn)優(yōu)化是使用布隆過(guò)濾器。布隆過(guò)濾器可以快速判斷特定SSTable中是否存在某個(gè)鍵值對(duì)，減少不必要的磁盤(pán)I/O。此外，SSTables 的排序特性使得高效的搜索算法（例如二分搜索）能夠用于更快的查找。

數(shù)據(jù)壓縮

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

另一種常見(jiàn)策略是大小分層壓縮策略，其中較新且較小的 SSTable 會(huì)依次合并到較舊且較大的 SSTable 中。

如前所述，SSTable 存儲(chǔ)一系列按鍵排序的條目。在分級(jí)壓縮策略中，SSTables被組織成多個(gè)級(jí)別（級(jí)別0到級(jí)別N）。

在 Level 0 中，SSTable 可以具有重疊的鍵范圍，因?yàn)樗鼈兪侵苯訌?Memtable 中刷新的。然而，在級(jí)別 1 到 N 中，同一級(jí)別內(nèi)的 SSTable 不具有重疊的鍵范圍，盡管不同級(jí)別的 SSTable 之間允許鍵范圍重疊。

下面顯示了一個(gè)說(shuō)明性（盡管不完全準(zhǔn)確）的示例。在 Level 0 中，第一個(gè)和第二個(gè) SSTable 的鍵范圍重疊，而在 Level 1 和 Level 2 中，每個(gè)級(jí)別內(nèi)的 SSTable 具有不相交的鍵范圍。然而，不同級(jí)別（例如，級(jí)別 0 和級(jí)別 1，或級(jí)別 1 和級(jí)別 2）之間的 SSTable 可能具有重疊的鍵范圍。

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

由于Level 0是一個(gè)特例，所以壓縮策略討論分為兩部分：

• 0 級(jí)到 1 級(jí) 由于 Level 0 允許 SSTable 之間重疊鍵，因此壓縮首先從 Level 0 選擇一個(gè) SSTable，以及 Level 0 中與其具有重疊鍵范圍的所有其他 SSTable。接下來(lái)，選擇級(jí)別 1 中具有重疊鍵范圍的所有 SSTable。這些選定的 SSTable 被合并并壓縮為一個(gè)新的 SSTable，然后插入到 Level 1。壓縮過(guò)程中涉及的所有舊 SSTable 都將被刪除。
• N 級(jí)到 N 1 級(jí)（N > 0） 從級(jí)別 1 開(kāi)始，同一級(jí)別內(nèi)的 SSTable 沒(méi)有重疊的鍵范圍。在compaction過(guò)程中，會(huì)從Level N中選擇一個(gè)SSTable，并且會(huì)選擇Level N 1中所有具有重疊鍵范圍的SSTable。這些 SSTable 被合并并壓縮為一個(gè)或多個(gè)新的 SSTable，這些新的 SSTable 被插入到 Level N 1，同時(shí)舊的 SSTable 被刪除。

Level 0 to Level 1 壓縮和 Level N to Level N 1 (N > 0) 壓縮的主要區(qū)別在于較低級(jí)別（Level 0 或 N 級(jí)）。

多SSTable的壓縮和合并過(guò)程如下圖所示。合并期間，僅保留每個(gè)鍵的最新值。如果最新值具有“墓碑”標(biāo)記，則該鍵將被刪除。在實(shí)現(xiàn)中，我們使用k路合并算法來(lái)執(zhí)行此過(guò)程。

需要注意的是，上面對(duì)壓縮過(guò)程的描述僅提供了高級(jí)概述。實(shí)際實(shí)施過(guò)程中還有很多細(xì)節(jié)需要解決。

例如，在LevelDB中，在壓縮過(guò)程中為L(zhǎng)evel N 1構(gòu)建新的SSTable時(shí)，如果新的SSTable與Level N 2中的10個(gè)以上SSTable重疊，則流程切換到構(gòu)建另一個(gè)SSTable。這限制了單次壓縮所涉及的數(shù)據(jù)大小。

執(zhí)行

通過(guò)上面對(duì)LSM-Tree的概述，相信您現(xiàn)在已經(jīng)對(duì)LSM-Tree有了基本的了解，并對(duì)其實(shí)現(xiàn)有了一些想法。接下來(lái)我們將從頭開(kāi)始構(gòu)建一個(gè)基于LSM-Tree的存儲(chǔ)引擎。下面，我們只介紹核心代碼；完整代碼請(qǐng)參考https://github.com/B1NARY-GR0UP/originium。

我們將LSM-Tree的實(shí)現(xiàn)分解為以下核心組件并一一實(shí)現(xiàn)：

• 跳過(guò)列表
• 沃爾
• 內(nèi)存表
• SSTable
• K-Way 合并
• 布隆過(guò)濾器
• 分層壓實(shí)

跳過(guò)列表

在介紹數(shù)據(jù)寫(xiě)入的過(guò)程中，我們提到LSM-Tree首先將數(shù)據(jù)寫(xiě)入內(nèi)存中的有序數(shù)據(jù)結(jié)構(gòu)。一些常見(jiàn)的有序數(shù)據(jù)結(jié)構(gòu)及其操作的時(shí)間復(fù)雜度如下：

我們選擇Skip List主要有兩個(gè)原因：它更容易實(shí)現(xiàn)和維護(hù)（KISS原則），底層鏈表結(jié)構(gòu)有利于順序遍歷，更容易將內(nèi)存中的數(shù)據(jù)持久化到磁盤(pán)。

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

跳過(guò)列表的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go 獲取。

跳過(guò)列表由一個(gè)基本鏈表和建立在其之上的多層索引組成。對(duì)于大型數(shù)據(jù)集，索引層顯著縮短了搜索路徑。

在我們的實(shí)現(xiàn)中，Skip List的核心結(jié)構(gòu)定義如下：

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

• maxLevel：Skip List 的最大級(jí)別數(shù)（基礎(chǔ)鏈表只有一級(jí)）。
• level：跳過(guò)列表中當(dāng)前的級(jí)別數(shù)。
• p：節(jié)點(diǎn)晉升到更高級(jí)別的概率。例如，如果 p = 0.5，則基礎(chǔ)級(jí)別有 10 個(gè)節(jié)點(diǎn)的鏈表將在下一級(jí)索引中具有大約 5 個(gè)節(jié)點(diǎn)。
• rand：用于與 p 進(jìn)行比較的隨機(jī)數(shù)生成器。
• size：Skip List 中存儲(chǔ)的鍵值對(duì)數(shù)量，用于判斷 Memtable 是否超出其大小閾值。
• head：頭節(jié)點(diǎn)，保存每個(gè)級(jí)別中第一個(gè)節(jié)點(diǎn)的引用。

Skip List中存儲(chǔ)的元素結(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 表示存儲(chǔ)引擎中的鍵值對(duì)，包括鍵、值和用于刪除的墓碑標(biāo)記。

• next：包含指向每個(gè)級(jí)別的下一個(gè)元素的指針。

這個(gè)結(jié)構(gòu)可能看起來(lái)很抽象，所以我們用一個(gè)例子來(lái)說(shuō)明它：

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è)三級(jí)Skip List中，頭節(jié)點(diǎn)的next指針引用每一級(jí)的第一個(gè)節(jié)點(diǎn)。元素 3 和 6 存儲(chǔ)每個(gè)級(jí)別的下一個(gè)元素。

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

放

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

LSM-Tree 使用邏輯刪除來(lái)執(zhí)行刪除，因此我們?cè)谔S列表實(shí)現(xiàn)中不需要?jiǎng)h除方法。要?jiǎng)h除元素，只需將條目的墓碑設(shè)置為 true 即可。因此，Set 方法處理插入新的鍵值對(duì)、更新現(xiàn)有鍵值對(duì)以及刪除元素。

讓我們探索一下Set方法的實(shí)現(xiàn)。通過(guò)從最高處開(kāi)始遍歷每一層的節(jié)點(diǎn)，將最后一個(gè)比要設(shè)置的key小的元素保存在更新切片中。

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

本次遍歷結(jié)束時(shí)，curr指向底層鏈表中最后一個(gè)比要設(shè)置的key小的元素。因此，我們只需要檢查 curr 的下一個(gè)元素是否等于我們想要設(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，我們計(jì)算該元素的索引級(jí)別。如果它超出了跳躍列表中當(dāng)前的級(jí)別數(shù)，我們將頭節(jié)點(diǎn)添加到更新切片中，并將 s.level 更新為新的級(jí)別數(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 ]

接下來(lái)構(gòu)造要插入的元素，更新每一層的next指針，完成插入。

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

得到

跳過(guò)列表可以依靠多層索引來(lái)執(zhí)行快速搜索操作。實(shí)現(xiàn)中的嵌套 for 循環(huán)代表基于索引的搜索操作。如果最終在底層鏈表中找到對(duì)應(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
}

全部

我們選擇跳過(guò)列表的一個(gè)原因是它方便的順序遍歷，只需遍歷底層鏈表即可實(shí)現(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 的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go 找到。

前面提到，WAL（Write-Ahead Logging）的目的是為了防止數(shù)據(jù)庫(kù)崩潰導(dǎo)致Memtable中的數(shù)據(jù)丟失。因此，WAL需要記錄對(duì)Memtable的操作，并在數(shù)據(jù)庫(kù)重啟時(shí)從WAL文件中恢復(fù)Memtable。

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

WAL的核心結(jié)構(gòu)如下，其中fd存儲(chǔ)WAL文件的文件描述符：

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

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

寫(xiě)

由于我們需要記錄對(duì) Memtable 的操作，這本質(zhì)上涉及將每個(gè)操作（Set、Delete）作為一個(gè) Entry 寫(xiě)入 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)))

將這些條目寫(xiě)入文件時(shí)，我們需要標(biāo)準(zhǔn)化 WAL 文件格式。我們這里使用的格式是長(zhǎng)度數(shù)據(jù)。首先我們對(duì)Entry進(jìn)行序列化，然后計(jì)算序列化數(shù)據(jù)的長(zhǎng)度，最后將長(zhǎng)度和序列化數(shù)據(jù)依次寫(xiě)入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文件格式長(zhǎng)度數(shù)據(jù)，所以在讀取的時(shí)候，我們首先讀取8個(gè)字節(jié)（int64）來(lái)獲取數(shù)據(jù)的長(zhǎng)度，然后根據(jù)這個(gè)長(zhǎng)度讀取數(shù)據(jù)并反序列化檢索條目。

核心代碼如下：

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

內(nèi)存表

Memtable 的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go 找到。

Memtable負(fù)責(zé)將客戶端操作寫(xiě)入skip list并記錄在WAL中。它還可以在數(shù)據(jù)庫(kù)啟動(dòng)時(shí)從 WAL 中恢復(fù)數(shù)據(jù)。

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

Memtable的核心結(jié)構(gòu)如下，包括兩個(gè)主要組件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操作時(shí)，skip list和WAL都需要同時(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 ]

得到

要檢索值，只需返回跳過(guò)列表的 Get 操作的結(jié)果即可。

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

恢復(fù)

從 WAL 文件恢復(fù) Memtable 需要先讀取 WAL 文件，然后依次將 WAL 文件中的 Entry 記錄應(yīng)用到 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 并恢復(fù) 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）是一種維護(hù)一系列有序鍵值對(duì)的數(shù)據(jù)存儲(chǔ)格式”。在這里，我們將對(duì)SSTable的結(jié)構(gòu)進(jìn)行更詳細(xì)的解釋。

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

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

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

我們的SS表

在我們的 SSTable 實(shí)現(xiàn)中，我們簡(jiǎn)化了 LevelDB SSTable 結(jié)構(gòu)。示意圖如下：

• 數(shù)據(jù)塊：存儲(chǔ)一系列有序的鍵值對(duì)。
• 元數(shù)據(jù)塊：存儲(chǔ)SSTable的一些元數(shù)據(jù)。
• 索引塊：存儲(chǔ)數(shù)據(jù)塊的索引信息。
• 頁(yè)腳：長(zhǎng)度固定，存放Meta Block和Index Block的索引信息。

SSTable 的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/tree/main/sstable 找到。

數(shù)據(jù)塊

數(shù)據(jù)塊的結(jié)構(gòu)定義如下，存儲(chǔ)有序的條目序列。

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

我們?yōu)閿?shù)據(jù)塊實(shí)現(xiàn)了三種主要方法：

• Encode：將數(shù)據(jù)塊編碼為二進(jìn)制數(shù)據(jù)。

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  
}

我們使用前綴壓縮對(duì)鍵值序列進(jìn)行編碼。在緩沖區(qū)中，我們依次寫(xiě)入公共前綴的長(zhǎng)度、后綴的長(zhǎng)度、后綴本身、值的長(zhǎng)度、值和“墓碑”標(biāo)記。

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壓縮數(shù)據(jù)。

S2 是 Snappy 壓縮算法的高性能擴(kuò)展。

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

• 解碼：將二進(jìn)制數(shù)據(jù)解碼為數(shù)據(jù)塊。

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
}

在解碼過(guò)程中，過(guò)程只是相反。使用前綴和后綴重構(gòu)完整的鍵值對(duì)。

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

• 搜索：使用二分搜索查找鍵值對(duì)。

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

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

索引塊

索引塊的結(jié)構(gòu)定義如下。它存儲(chǔ)每個(gè)數(shù)據(jù)塊的第一個(gè)和最后一個(gè)鍵，以及相應(yīng)數(shù)據(jù)塊的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)))

類(lèi)似地，索引塊實(shí)現(xiàn)了三個(gè)主要方法：編碼、解碼和搜索。 Encode 和 Decode 方法的實(shí)現(xiàn)思路基本相同，所以我們重點(diǎn)關(guān)注 Search 方法。

數(shù)據(jù)塊的搜索方法旨在在單個(gè)數(shù)據(jù)塊中存儲(chǔ)的有序鍵值序列中定位特定的鍵值對(duì)。相反，索引塊的搜索方法用于在整個(gè) SSTable 中定位包含給定鍵的數(shù)據(jù)塊。

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
}

元塊和頁(yè)腳

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
}

這兩個(gè)Block的實(shí)現(xiàn)非常簡(jiǎn)單，都只需要Encode和Decode方法。

建造

引入SSTable中的所有Block后，構(gòu)建SSTable只需根據(jù)鍵值對(duì)逐步構(gòu)建每個(gè)Block。最后返回內(nèi)存索引和編碼后的SSTable。

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

K 路合并

K-Way Merge 的完整實(shí)現(xiàn)可在 https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway 獲取。

在概念部分，我們通過(guò)圖表說(shuō)明了壓縮和合并多個(gè)SSTable的過(guò)程。此過(guò)程是使用 k 路合并 算法完成的。

k 路合并算法是將 k 個(gè)排序序列合并為單個(gè)排序序列的方法，時(shí)間復(fù)雜度為 O(knlogk)。

該算法的一個(gè)實(shí)現(xiàn)使用 最小堆 作為輔助結(jié)構(gòu)：

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

堆

標(biāo)準(zhǔn)庫(kù)在容器/堆中提供了堆實(shí)現(xiàn)。通過(guò)實(shí)現(xiàn)heap.Interface，我們可以構(gòu)建一個(gè)最小堆。

• 首先，定義最小堆的基本結(jié)構(gòu)。切片用于存儲(chǔ)元素。每個(gè)元素不僅包含一個(gè) Entry，還包含一個(gè) LI 來(lái)指示該元素源自哪個(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  
}

• 實(shí)現(xiàn)sort.Interface方法對(duì)堆中的元素進(jìn)行排序。需要特別注意的是Less方法：通過(guò)比較元素的LI，我們確保當(dāng)元素具有相同的鍵時(shí)，來(lái)自較早序列的元素會(huì)先排序。這有助于將元素合并到結(jié)果集中時(shí)進(jìn)行重復(fù)數(shù)據(jù)刪除。這一要求也意味著在使用 k 路合并算法時(shí)，排序后的序列應(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 ]

• 最后，實(shí)現(xiàn) Push 和 Pop 方法。 Push 將一個(gè)元素追加到切片的末尾，而 Pop 則從切片中刪除最后一個(gè)元素。

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路合并算法流程。

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

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

• 迭代地從最小堆中彈出一個(gè)元素并將其添加到結(jié)果隊(duì)列中。如果彈出元素的序列仍有更多元素，則將該序列中的下一個(gè)元素插入到堆中。這里，使用映射而不是結(jié)果序列。映射會(huì)自動(dòng)處理重復(fù)數(shù)據(jù)刪除，新的鍵總是覆蓋舊的鍵。

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é)果隊(duì)列中，刪除任何標(biāo)記為“墓碑”的鍵值對(duì)。由于map是無(wú)序的，所以結(jié)果隊(duì)列在返回之前需要先排序。

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 ]

布隆過(guò)濾器

布隆過(guò)濾器的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go 找到。

布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，可以有效地檢查元素是否是集合的成員。

• 它使用一個(gè)位數(shù)組和多個(gè)哈希函數(shù)。
• 添加元素時(shí)，使用多個(gè)哈希函數(shù)對(duì)元素進(jìn)行哈希處理，將其映射到位數(shù)組中的不同位置，并將這些位置設(shè)置為 1。
• 在查詢過(guò)程中，如果哈希函數(shù)映射的所有位置均為1，則該元素可能存在。如果任意位置為0，則該元素肯定不存在。

插入和查詢操作的時(shí)間復(fù)雜度都是O(k)，其中k是哈希函數(shù)的數(shù)量。 可能會(huì)出現(xiàn)誤報(bào)（布隆過(guò)濾器預(yù)測(cè)某個(gè)元素在集合中，但事實(shí)并非如此），但不會(huì)出現(xiàn)誤報(bào)（布隆過(guò)濾器預(yù)測(cè)某個(gè)元素不在集合中）在集合中，但實(shí)際上是）。

真陽(yáng)性（TP）：系統(tǒng)將事件預(yù)測(cè)為“陽(yáng)性”，而且它確實(shí)是陽(yáng)性。
誤報(bào)（FP）：系統(tǒng)將事件預(yù)測(cè)為“正”，但實(shí)際上是負(fù)的。
真陰性（TN）：系統(tǒng)將事件預(yù)測(cè)為“陰性”，并且它確實(shí)是陰性。
假陰性（FN）：系統(tǒng)將事件預(yù)測(cè)為“陰性”，但實(shí)際上是陽(yáng)性。

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

布隆過(guò)濾器的核心結(jié)構(gòu)包括位數(shù)組（可以優(yōu)化為使用 uint8）和多個(gè)哈希函數(shù)。

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

新的

創(chuàng)建 Bloom Filter 實(shí)例的方法接受兩個(gè)參數(shù)：n（期望的元素?cái)?shù)量）和 p（期望的誤報(bào)率）。

首先，驗(yàn)證參數(shù)。然后，使用特定公式計(jì)算位數(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í)，所有哈希函數(shù)都用于計(jì)算鍵的哈希值。然后將這些值映射到位數(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  
}

包含

為了檢查某個(gè)鍵是否在集合中，哈希函數(shù)計(jì)算哈希值并將它們映射到位數(shù)組中的索引。如果這些位置中的任何一個(gè)不為 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 ]

平整壓實(shí)

Leveled Compaction 的完整實(shí)現(xiàn)可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/level.go 找到。

實(shí)現(xiàn)了 K-Way Merge 和 Bloom Filter 等組件后，我們就可以完成實(shí)現(xiàn)的最后部分，即 LSM-Tree 存儲(chǔ)引擎中最關(guān)鍵的 SSTable 壓縮過(guò)程。此實(shí)現(xiàn)遵循“數(shù)據(jù)壓縮”部分中描述的分級(jí)壓縮策略。

在分級(jí)壓縮策略中，SSTables被組織成多個(gè)級(jí)別（Level 0 - Level N）。我們需要一個(gè)結(jié)構(gòu)來(lái)存儲(chǔ)這些信息并管理不同級(jí)別的 SSTable。

因此，我們實(shí)現(xiàn)了一個(gè)名為 levelManager 的結(jié)構(gòu)。我們使用一個(gè)[]*list.List來(lái)存儲(chǔ)每個(gè)級(jí)別的SSTable信息，其中切片的索引對(duì)應(yīng)于該級(jí)別。切片中的每個(gè)元素都是一個(gè)列表。List，一個(gè)雙向鏈表，保存特定級(jí)別中所有 SSTable 的信息。

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

緊湊型LN

compactLN 方法負(fù)責(zé) 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 會(huì)按照從最舊到最新的順序進(jìn)行處理。來(lái)自數(shù)據(jù)塊的鍵值對(duì)被添加到二維切片中，然后使用 K-Way Merge 算法進(jì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
}

通過(guò)合并的鍵值對(duì)，我們構(gòu)建了一個(gè)新的 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，并將新構(gòu)建的SSTable寫(xiě)入磁盤(pán)。

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 級(jí)到 1 級(jí)壓縮。與compactLN不同的是，它不僅從L0中選擇一個(gè)SSTable，而且還從L0中選擇所有重疊的SSTable。其余過(guò)程與compactLN 相同。

搜索

搜索方法在所有 SSTable 中找到相應(yīng)的鍵值對(duì)。它從 L0 開(kāi)始，迭代每個(gè)級(jí)別直至 LN。通過(guò)利用布隆過(guò)濾器和 SSTable 的有序結(jié)構(gòu)，可以有效地跳過(guò)不包含所需鍵值對(duì)的 SSTable。

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

數(shù)據(jù)庫(kù)

至此，我們已經(jīng)實(shí)現(xiàn)了基于LSM-Tree的存儲(chǔ)引擎的所有核心組件。通過(guò)按照 LSM-Tree 介紹中的描述組裝這些組件，我們可以最終確定數(shù)據(jù)庫(kù)接口。

• 完整代碼：https://github.com/B1NARY-GR0UP/originium/blob/main/db.go

• 文檔：https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage

概括

我們首先了解LSM-Tree，熟悉其核心組件以及處理客戶端請(qǐng)求的流程。最終，我們從頭開(kāi)始構(gòu)建了自己的 LSM-Tree 存儲(chǔ)引擎。

當(dāng)然，這個(gè)實(shí)現(xiàn)只是一個(gè)原型。生產(chǎn)級(jí)存儲(chǔ)引擎需要考慮更多細(xì)節(jié)。 ORIGINIUM未來(lái)將持續(xù)得到優(yōu)化和改進(jìn)。希望本文和 ORIGINIUM 能夠幫助您加深對(duì) LSM-Tree 的理解。

本文涵蓋的所有內(nèi)容到此結(jié)束。如果有任何錯(cuò)誤或疑問(wèn)，請(qǐng)隨時(shí)通過(guò)私信聯(lián)系或發(fā)表評(píng)論。謝謝！

參考

• 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

以上是從頭開(kāi)始構(gòu)建 LSM-Tree 存儲(chǔ)引擎的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！