从头开始构建 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中文网其他相关文章！