前言

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

什麼是LSM樹？

基本概念

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

LSM-Tree 的關(guān)鍵思想是首先將操作寫入記憶體資料結(jié)構(gòu)（通常是跳躍列表或 AVL 樹等有序結(jié)構(gòu)）。隨後，這些寫入會(huì)被批次並作為 SSTable 順序?qū)懭氪诺?，從而最大限度地減少隨機(jī) I/O。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

資料壓縮

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

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

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

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

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

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

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

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

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

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

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

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

執(zhí)行

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

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

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

跳過列表

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

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

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

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

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

在我們的實(shí)作中，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：跳過列表中目前的等級(jí)數(shù)。
• p：節(jié)點(diǎn)晉升到更高等級(jí)的機(jī)率。例如，如果 p = 0.5，則基礎(chǔ)層級(jí)有 10 個(gè)節(jié)點(diǎn)的鍊錶將在下一層索引中具有約 5 個(gè)節(jié)點(diǎn)。
• rand：用於與 p 進(jìn)行比較的隨機(jī)數(shù)產(chǎn)生器。
• 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è)元素的指標(biāo)。

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

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指標(biāo)引用每一級(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 使用邏輯刪除來執(zhí)行刪除，因此我們?cè)谔S清單實(shí)作中不需要?jiǎng)h除方法。要?jiǎng)h除元素，只需將條目的墓碑設(shè)為 true 即可。因此，Set 方法處理插入新的鍵值對(duì)、更新現(xiàn)有鍵值對(duì)以及刪除元素。

讓我們來探索Set方法的實(shí)作。透過從最高處開始遍歷每一層的節(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 ]

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

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

得到

跳過清單可以依靠多層索引來執(zhí)行快速搜尋操作。實(shí)作中的巢狀 for 迴圈代表基於索引的搜尋操作。如果最終在底層鍊錶中找到對(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
}

全部

我們選擇跳過清單的一個(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í)作可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go 找到。

前面提到，WAL（Write-Ahead Logging）的目的是為了防止資料庫(kù)崩潰導(dǎo)致Memtable中的資料遺失。因此，WAL需要記錄對(duì)Memtable的操作，並在資料庫(kù)重新啟動(dòng)時(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
}

寫

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

將這些條目寫入檔案時(shí)，我們需要標(biāo)準(zhǔn)化 WAL 檔案格式。我們這裡使用的格式是長(zhǎng)度資料。首先我們將Entry序列化，然後計(jì)算序列化資料的長(zhǎng)度，最後將長(zhǎng)度和序列化資料依序?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檔案格式長(zhǎng)度資料，所以在讀取的時(shí)候，我們先讀取8個(gè)位元組（int64）來取得資料的長(zhǎng)度，然後根據(jù)這個(gè)長(zhǎng)度讀取資料並反序列化檢索條目。

核心程式碼如下：

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

記憶體表

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

Memtable負(fù)責(zé)將客戶端操作寫入skip list並記錄在WAL中。它還可以在資料庫(kù)啟動(dòng)時(shí)從 WAL 中復(fù)原資料。

核心結(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 ]

得到

要檢索值，只需傳回跳過清單的 Get 操作的結(jié)果即可。

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

恢復(fù)

從 WAL 檔案復(fù)原 Memtable 需要先讀取 WAL 文件，然後依序?qū)?WAL 檔案中的 Entry 記錄套用到 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：

// 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ì)的資料儲(chǔ)存格式」。在這裡，我們將對(duì)SSTable的結(jié)構(gòu)進(jìn)行更詳細(xì)的解釋。

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

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

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

我們的SS表

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

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

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

資料區(qū)塊

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

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

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

• Encode：將資料區(qū)塊編碼為二進(jì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  
}

我們使用前綴壓縮對(duì)鍵值序列進(jìn)行編碼。在緩衝區(qū)中，我們依序?qū)懭牍睬熬Y的長(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壓縮資料。

S2 是 Snappy 壓縮演算法的高效能擴(kuò)充。

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

• 解碼：將二進(jìn)位資料解碼為資料區(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)完整的鍵值對(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
}

索引區(qū)塊

索引塊的結(jié)構(gòu)定義如下。它儲(chǔ)存每個(gè)資料塊的第一個(gè)和最後一個(gè)鍵，以及對(duì)應(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ū)塊實(shí)作了三個(gè)主要方法：編碼、解碼和搜尋。 Encode 和 Decode 方法的實(shí)作想法基本上相同，所以我們專注於 Search 方法。

資料區(qū)塊的搜尋方法旨在在單一資料區(qū)塊中儲(chǔ)存的有序鍵值序列中定位特定的鍵值對(duì)。相反，索引區(qū)塊的搜尋方法用於在整個(gè) 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
}

元塊和頁(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í)作非常簡(jiǎn)單，都只需要Encode和Decode方法。

建造

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

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

K 路合併

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

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

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

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

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

堆疊

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

• 首先，定義最小堆的基本結(jié)構(gòu)。切片用於儲(chǔ)存元素。每個(gè)元素不僅包含一個(gè) Entry，還包含一個(gè) LI 來指示該元素源自於哪個(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í)作sort.Interface方法對(duì)堆中的元素進(jìn)行排序。需要特別注意的是Less方法：透過比較元素的LI，我們確保當(dāng)元素具有相同的鍵時(shí)，來自較早序列的元素會(huì)先排序。這有助於將元素合併到結(jié)果集中時(shí)進(jìn)行重複資料刪除。這項(xiàng)要求也意味著在使用 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í)作 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é)果佇列中。如果彈出元素的序列仍有更多元素，則將該序列中的下一個(gè)元素插入到堆中。這裡，使用映射而不是結(jié)果序列。映射會(huì)自動(dòng)處理重複資料刪除，新的鍵總是覆蓋舊的鍵。

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

蒲隆地

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

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

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

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

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

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

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

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

新的

建立 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
}

添加

當(dāng)新增元素時(shí)，所有雜湊函數(shù)都用於計(jì)算鍵的雜湊值。然後將這些值對(duì)應(yīng)到位數(shù)組中的索引，並將對(duì)應(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ì)算雜湊值並將它們對(duì)應(yīng)到位數(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í)作可以在 https://github.com/B1NARY-GR0UP/originium/blob/main/level.go 找到。

實(shí)作了 K-Way Merge 和 Bloom Filter 等元件後，我們就可以完成實(shí)作的最後部分，也就是 LSM-Tree 儲(chǔ)存引擎中最關(guān)鍵的 SSTable 壓縮過程。此實(shí)作遵循「資料壓縮」部分中所述的分級(jí)壓縮策略。

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

因此，我們實(shí)作了一個(gè)名為 levelManager 的結(jié)構(gòu)。我們使用一個(gè)[]*list.List來儲(chǔ)存每個(gè)層級(jí)的SSTable訊息，其中切片的索引對(duì)應(yīng)於該層級(jí)。切片中的每個(gè)元素都是一個(gè)列表。 List，雙向鍊錶，保存特定層級(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 有重疊鍵範(fàn)圍的所有 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ì)依照從最舊到最新的順序處理。來自資料區(qū)塊的鍵值對(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
}

透過合併的鍵值對(duì)，我們建立了一個(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，並將新建的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 級(jí)到 1 級(jí)壓縮。與compactLN不同的是，它不僅從L0中選擇一個(gè)SSTable，而且還從L0中選擇所有重疊的SSTable。其餘過程與compactLN 相同。

搜尋

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

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

資料庫(kù)

至此，我們已經(jīng)實(shí)現(xiàn)了基於LSM-Tree的儲(chǔ)存引擎的所有核心元件。透過按照 LSM-Tree 介紹中的描述組裝這些組件，我們可以最終確定資料庫(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)求的流程。最終，我們從頭開始建立了自己的 LSM-Tree 儲(chǔ)存引擎。

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

本文涵蓋的所有內(nèi)容到此結(jié)束。如果有任何錯(cuò)誤或疑問，請(qǐng)隨時(shí)透過私訊聯(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

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