关于microsoft:使用-LSM-Tree-思想实现一个-KV-数据库

▌目录

设计思路

• 内存表
• WAL
• SSTable 的构造
• SSTable 元素和索引的构造
• SSTable Tree
• 内存中的 SSTable
• 数据查找过程
• 何为 LSM-Treee
• 参考资料
• 整体构造

实现过程

• 文件压缩测试
• 插入测试
• 加载测试
• 查找测试
• SSTable 构造
• SSTable 文件构造
• SSTable Tree 构造和治理 SSTable 文件
• 读取 SSTable 文件
• SSTable 文件合并
• SSTable 查找过程
• 插入 SSTable 文件过程
• WAL 文件复原过程
• 二叉排序树结构定义
• 插入操作
• 查找
• 删除
• 遍历算法
• Key/Value 的示意
• 内存表的实现
• WAL
• SSTable 与 SSTable Tree
• 简略的应用测试

笔者前段时间在学习数据结构时，恰好据说了 LSM Tree，于是试着通过 LSM Tree 的设计思维，本人实现一个简略的 KV 数据库。

代码已开源，代码仓库地址：https://github.com/whuanle/lsm

笔者应用 Go 语言来实现 LSM Tree 数据库，因为 LSM Tree 的实现要求对文件进行读写、锁的解决、数据查找、文件压缩等，所以编码过程中也进步了对 Go 的应用教训，我的项目中也应用到了一些栈、二叉排序树等简略的算法，也能够坚固了根底算法能力。适当给本人设定挑战指标，能够晋升本人的技术水平。

上面，咱们来理解 LSM Tree 的设计思维以及如何实现一个 KV 数据库。

设计思路

▌何为 LSM-Treee

LSM Tree 的全称为 Log-Structured Merge Tree，是一种对于键值类型数据库的数据结构。据笔者理解，目前 NoSQL 类型的数据库如 Cassandra、ScyllaDB 等应用了 LSM Tree。
LSM Tree 的外围理论依据是磁盘程序写性能比随机写的速度快很多。因为无论哪种数据库，磁盘 IO 都是对数据库读写性能的最大影响因素，因而正当组织数据库文件和充分利用磁盘读写文件的机制，能够进步数据库程序的性能。LSM Tree 首先会在内存中缓冲所有写操作，当应用的内存达到阈值时，便会将内存刷新磁盘中，这个过程只有程序写，不会产生随机写，因而 LSM 具备优越的写入性能。

这里笔者就不对 LSM Tree 的概念进行赘述，读者能够参考上面列出的材料。

▌参考资料

• 《What is a LSM Tree?》
• 生饼:《了解 LSM Tree：一种高效读写的存储引擎》
• https://mp.weixin.qq.com/s/7k…
• 肖汉松：《从 0 开始：500 行代码实现 LSM 数据库》
• 小屋子大侠：《golang 实际 LSM 相干内容》
• 《SM-based storage techniques: a survey》中文翻译

▌整体构造

下图是 LSM Tree 的整体构造，整体能够分为内存、磁盘文件两大部分，其中磁盘文件除了数据库文件 (SSTable 文件) 外，还包含了 WAL 日志文件。

内存表用于缓冲写入操作，当 Key/Value 写入内存表后，也会同时记录到 WAL 文件中，WAL 文件能够作为复原内存表数据的根据。程序启动时，如果发现目录中存在 WAL 文件，则须要读取 WAL 文件，恢复程序中的内存表。

在磁盘文件中，有着多层数据库文件，每层都会存在多个 SSTable 文件，SSTable 文件用于存储数据，即数据库文件。下一层的数据库文件，都是上一层的数据库文件压缩合并后生成，因而，层数越大，数据库文件越大。

上面咱们来理解具体一点的 LSM Tree 不同局部的设计思路，以及进行读写操作时，须要通过哪些阶段。

内存表

在 LSM Tree 的内存区域中，有两个内存表，一个是可变内存表 Memory Table，一个是不可变内存表 Immutable Memory Table，两者具备雷同的数据结构，个别是二叉排序树。
在刚开始时，数据库没有数据，此时 Memory Table 为空，即没有任何元素，而 Immutable Memory Table 为 nil，即没有被调配任何内存，此时，所有写操作均在 Memory Table 上，写操作包含设置 Key 的值和删除 Key。如果写入 Memory Table 胜利，接着操作信息会记录到 WAL 日志文件中。

当然，Memory Table 中存储的 Key/Value 也不能太多，否则会占用太多内存，因而，个别当 Memory Table 中的 Key 数量达到阈值时，Memory Table 就会变成 Immutable Memory Table，而后创立一个新的 Memory Table，Immutable Memory Table 会在适合的机会，转换为 SSTable，存储到磁盘文件中。

因而，Immutable Memory Table 是一个长期的对象，只在同步内存中的元素到 SSTable 时，长期存在。

这里还要留神的是，当内存表被同步到 SSTable 后，Wal 文件是须要删除的。应用 Wal 文件能够复原的数据该当与以后内存中的 KV 元素统一，即能够利用 WAL 文件复原上一次程序的运行状态，如果以后内存表曾经挪动到 SSTable，那么 WAL 文件曾经没必要保留，该当删除并从新创立一个空的 WAL 文件。

对于 WAL 局部的实现，有不同的做法，有的全局只有惟一一个 WAL 文件，有的则应用多个 WAL 文件，具体的实现会依据场景而变动。

WAL

WAL 即 Write Ahead LOG，当进行写入操作（插入、批改或删除 Key）时，因为数据都在内存中，为了防止程序解体进行或主机停机等，导致内存数据失落，因而须要及时将写操作记录到 WAL 文件中，当下次启动程序时，程序能够从 WAL 文件中，读取操作记录，通过操作记录复原到程序退出前的状态。

WAL 保留的日志，记录了以后内存表的所有操作，应用 WAL 复原上一次程序的内存表时，须要从 WAL 文件中，读取每一次操作信息，从新作用于内存表，即从新执行各种写入操作。因而，间接对内存表进行写操作，和从 WAL 复原数据从新对内存表进行写操作，都是一样的。

能够这样说，WAL 记录了操作过程，而且二叉排序树存储的是最终后果。

WAL 要做的是，可能还原所有对内存表的写操作，从新程序执行这些操作，使得内存表复原到上一次的状态。

WAL 文件不是内存表的二进制文件备份，WAL 文件是对写操作的备份，还原的也是写操作过程，而不是内存数据

SSTable 的构造

SSTable 全称是 Sorted String Table，是内存表的长久化文件。
SSTable 文件由数据区、稠密索引区、元数据三个局部组成，如下图所示。

内存表转换为 SSTable 时，首先遍历 Immutable Memory Table，程序将每个 KV 压缩成二进制数据，并且创立一个对应的索引构造，记录这个二进制 KV 的插入地位和数据长度。而后将所有二进制 KV 放到磁盘文件的结尾，接着将所有的索引构造转为二进制，放在数据区之后。再将对于数据区和索引区的信息，放到一个元数据结构中，写入到文件开端。

内存中每一个元素都会有一个 Key，在内存表转换为 SSTable 时，元素汇合会依据 Key 进行排序，而后再将这些元素转换为二进制，存储到文件的结尾，即数据区中。

然而，咱们怎么从数据区中分隔出每一个元素呢？

对于不同的开发者，编码过程中，设置的 SSTable 的构造是不一样的，将内存表转为 SSTable 的解决办法也不一样，因而这里笔者只说本人在写 LSM Tree 时的做法。

笔者的做法是在生成数据区的时候，不将元素汇合一次性生成二进制，而是一个个元素程序遍历解决。

首先，将一个 Key/Value 元素，生成二进制，放到文件的结尾，而后生成一个索引，记录这个元素二进制数据在文件的起始地位以及长度，而后将这个索引先放到内存中。

接着，一直解决剩下的元素，在内存中生成对应的索引。

稠密索引示意每一个索引执行文件中的一个数据块。

当所有元素处理完毕，此时 SSTable 文件曾经生成数据区。接着，咱们再将所有的索引汇合，生成二进制数据，追加到文件中。

而后，咱们还须要为数据区和稠密索引区的起始地位和长度，生成文件元数据，以便后续读取文件时能够宰割数据区和稠密索引区，将两局部的数据独自解决。

元数据结构也很简略，其次要有四个值：

// 数据区起始索引
  dataStart int64
  // 数据区长度
  dataLen int64
  // 稠密索引区起始索引
  indexStart int64
  // 稠密索引区长度
  indexLen int64

元数据会被追加到文件的开端中，并且固定了字节长度。

在读取 SSTable 文件时，咱们先读取文件最初的几个字节，如 64 个字节，而后依据每 8 个字节还原字段的值，生成元数据，而后就能够对数据区和稠密索引区进行解决了。

SSTable 元素和索引的构造

咱们将一个 Key/Value 存储在数据区，那么这块存储了一个 Key/Value 元素的文件块，称为 block，为了示意 Key/Value，咱们能够定义一个这样的构造：

`Key
Value
Deleted`

而后将这个构造转换为二进制数据，写到文件的数据区中。
为了定位 Key/Value 在数据区的地位，咱们还须要定义一个索引，其构造如下：

`Key
Start
Length
`
每个 Key/Value 应用一个索引进行定位。

SSTable Tree

每次将内存表转换为 SSTable 时，都会生成一个 SSTable 文件，因而咱们须要治理 SSTable 文件，免得文件数量过多。

上面是 LSM Tree 的 SSTable 文件组织构造。

在上图中能够看到，数据库由很多的 SSTable 文件组成，而且 SSTable 被分隔在不同的层之中，为了治理不同层的 SSTable，所有 SSTable 磁盘文件的组织也有一个树结构，通过 SSTable Tree，治理不同层的磁盘文件大小或者 SSTable 数量。

对于 SSTable Tree，有三个要点：

1，第 0 层的 SSTable 文件，都是内存表转换的。
2，除第 0 层，下一层的 SSTable 文件，只能由上一层的 SSTable 文件通过压缩合并生成，而一层的 SSTable 文件在总文件大小或数量达到阈值时，能力进行合并，生成一个新的 SSTable 插入到下一层。
3，每一层的 SSTable 都有一个程序，依据生成工夫来排序。这个特点用于从所有的 SSTable 中查找数据。

因为每次长久化内存表，都会创立一个 SSTable 文件，因而 SSTable 文件数量会越来越多了，文件多了之后，须要保留较多的文件句柄，而且在多个文件中读取数据时，速度也会变慢。如果不进行管制，那么过多的文件会 导致读性能变差以及占用空间过于收缩 ，这一景象被称为 空间放大和读放大。

因为 SSTable 是不能更改的，那么如果要删除一个 Key，或者批改一个 Key 的值，只能在新的 SSTable 中标记，而不能批改，这样会导致不同的 SSTable 存在雷同的 Key，文件比拟臃肿。

因而，还须要对小的 SSTable 文件进行压缩，合并成一个大的 SSTable 文件，放到下一层中，以便进步读取性能。

当一层的 SSTable 文件总大小大于阈值时，或者 SSTable 文件的数量太多时，就须要触发合并动作，生成新的 SSTable 文件，放入下一层中，再将原先的 SSTable 文件删除，下图演示了这一过程。

尽管对 SSTable 进行合并压缩，能够克制空间放大和读放大问题，然而对多个 SSTable 合并为一个 SSTable 时，须要加载每个 SSTable 文件，在内存读取文件的内容，创立一个新的 SSTable 文件，并且删除掉旧的文件，这样会耗费大量的 CPU 工夫和磁盘 IO。这种景象被称为写放大。

下图演示了合并前后的存储空间变动。

内存中的 SSTable

当程序启动后，会加载每个 SSTable 的元数据和稠密索引区到内存中，也就是 SSTable 在内存中缓存了 Key 列表，须要在 SSTable 中查找 Key 时，首先在内存的稠密索引区查找，如果找到 Key，则依据 索引的 Start 和 Length，从磁盘文件中读取 Key/Value 的二进制数据。接着将二进制数据转换为 Key/Value 构造。

因而，要确定一个 SSTable 是否存在某个 Key 时，是在内存中查找的，这个过程很快，只有当须要读取 Key 的值时，才须要从文件中读出。

可是，当 Key 数量太多时，全副缓存在内存中会耗费很多的内存，并且一一查找也须要消耗肯定的工夫，还能够通过应用布隆过滤器 (BloomFilter) 来更快地判断一个 Key 是否存在。

数据查找过程

首先依据要查找的 Key，从 Memory Table 中查问。

如果 Memory Table 中，找不到对应的 Key，则从 Immutable Memory Table 中查找。

笔者所写的 LSM Tree 数据库中，只有 Memory Table，没有 Immutable Memory Table。

如果在两个内存表中都查找不到 Key，那么就要从 SSTable 列表中查找。

首先查问第 0 层的 SSTable 表，从该层最新的 SSTable 表开始查找，如果没有找到，便查问同一层的其余 SSTable，如果还是没有，则接着查下一层。

当查找到 Key 时，无论 Key 状态如何(无效或已被删除)，都会进行查找，返回此 Key 的值和删除标记。

实现过程

在本节中，笔者将会阐明本人实现 LSM Tree 大体的实现思路，从中给出一部分代码示例，然而残缺的代码须要在仓库中查看，这里只给出实现相干的代码定义，不列出具体的代码细节。

下图是 LSM Tree 次要关注的对象：

对于内存表，咱们要实现增删查改、遍历；
对于 WAL，须要将操作信息写到文件中，并且可能从 WAL 文件复原内存表；
对于 SSTable，可能加载文件信息，从中查找对应的数据；
对应 SSTable Tree，负责管理所有 SSTable，进行文件合并等。

▌Key/Value 的示意

作为 Key/Value 数据库，咱们须要可能保留任何类型的值。虽说 GO 1.18 减少了泛型，然而泛型构造体并不能任意存储任何值，解决寄存各种类型的 Value 的问题，因而笔者不应用泛型构造体。而且，无论存储的是什么数据，对数据库来说是不重要，数据库也齐全不用晓得 Value 的含意，这个值的类型和含意，只对使用者有用，因而咱们能够间接将值转为二进制存储，在用户取数据时，再将二进制转换为对应类型。

定义一个构造体，用于保留任何类型的值：

// Value 示意一个 KV
type Value struct {
  Key     string
  Value   []byte
  Deleted bool
}

Value 构造体援用门路是 kv.Value。

如果有一个这样的构造体：

type TestValue struct {
  A int64
  B int64
  C int64
  D string
}

那么能够将构造体序列化后的二进制数据放到 Value 字段里。

data,_ := json.Marshal(value)

v := Value{
    Key: "test",
    Value: data,
    Deleted: false,
}

Key/Value 通过 json 序列化值，转为二进制再存储到内存中。

因为在 LSM Tree 中，即便一个 Key 被删除了，也不会清理掉这个元素，只是将该元素标记为删除状态，所以为了确定查找后果，咱们须要定义一个枚举，用于判断查找到此 Key 后，此 Key 是否无效。

// SearchResult 查找后果
type SearchResult int

const (
  // None 没有查找到
  None SearchResult = iota
  // Deleted 曾经被删除
  Deleted
  // Success 查找胜利
  Success
)

对于代码局部，读者能够参考：
https://github.com/whuanle/ls…

▌内存表的实现

LSM Tree 中的内存表是一个二叉排序树，对于二叉排序树的操作，次要有设置值、插入、查找、遍历，具体的代码读者能够参考：

• https://github.com/whuanle/ls…

上面来简略阐明二叉排序树的实现。

假如咱们要插入的 Key 列表为 [30,45,25,23,17,24,26,28]，那么插入后，内存表的构造如下所示：

笔者在写二叉排序树时，发现几个容易出错的中央，因而这里列举一下。

首先，咱们要记住：节点插入之后，地位不再变动，不能被移除，也不能被更换地位。
第一点，新插入的节点，只能作为叶子。

上面是一个正确的插入操作：

如图所示，自身曾经存在了 23、17、24，那么插入 18 时，须要在 17 的右孩插入。
上面是一个谬误的插入操作：

进行插入操作时，不能挪动旧节点的地位，不能扭转左孩右孩的关系。

第二点，删除节点时，只能标记删除，不能真正删除节点。

二叉排序树结构定义

二叉排序树的构造体和办法定义如下：

// treeNode 有序树节点
type treeNode struct {
  KV    kv.Value
  Left  *treeNode
  Right *treeNode
}

// Tree 有序树
type Tree struct {
  root   *treeNode
  count  int
  rWLock *sync.RWMutex
}


// Search 查找 Key 的值
func (tree *Tree) Search(key string) (kv.Value, kv.SearchResult) {
}

// Set 设置 Key 的值并返回旧值
func (tree *Tree) Set(key string, value []byte) (oldValue kv.Value, hasOld bool) {
}

// Delete 删除 key 并返回旧值
func (tree *Tree) Delete(key string) (oldValue kv.Value, hasOld bool) {}

具体的代码实现请参考：
https://github.com/whuanle/ls…

因为 Go 语言的 string 类型是值类型，因而可能间接比拟大小的，因而在插入 Key/BValue 时，能够简化不少代码。

插入操作

因为树是有序的，插入 Key/Value 时，须要在树的根节点从上到下比照 Key 的大小，而后以叶子节点的模式插入到树中。

插入过程，能够分为多种状况。

第一种，不存在相干的 Key 时，间接作为叶子节点插入，作为上一层元素的左孩或右孩。

if key < current.KV.Key {
      // 左孩为空，直接插入右边
      if current.Left == nil {
        current.Left = newNode
                // ... ...
      }
      // 持续比照下一层
      current = current.Left
    } else {
      // 右孩为空，直接插入左边
      if current.Right == nil {
        current.Right = newNode
                // ... ...
            }
      current = current.Right
        }

第二种，当 Key 曾经存在，该节点可能是无效的，咱们须要替换 Value 即可；该节点有可能是被规范删除了，须要替换 Value，并且将 Deleted 标记改成 false。

      node.KV.Value = value
      isDeleted := node.KV.Deleted
      node.KV.Deleted = false

那么，当向二叉排序树插入一个 Key/Value 时，工夫复杂度如何？

如果二叉排序树是比拟均衡的，即左右比拟对称，那么进行插入操作时，其工夫复杂度为 O(logn)。

如下图所示，树中有 7 个节点，只有三层，那么插入操作时，最多须要比照三次。

如果二叉排序树不均衡，最坏的状况是所有节点都在右边或左边，此时插入的工夫复杂度为 O(n)。
如下图所示，树中有四个节点，也有四层，那么进行插入操作时，最多须要比照四次。

插入节点的代码请参考：
https://github.com/whuanle/ls…

查找

在二叉排序树中查找 Key 时，依据 Key 的大小来抉择左孩或右孩进行下一层查找，查找代码示例如下：

  currentNode := tree.root
  // 有序查找
  for currentNode != nil {
    if key == currentNode.KV.Key {
      if currentNode.KV.Deleted == false {return currentNode.KV, kv.Success} else {return kv.Value{}, kv.Deleted
      }
    }
    if key < currentNode.KV.Key {
      // 持续比照下一层
      currentNode = currentNode.Left
    } else {
      // 持续比照下一层
      currentNode = currentNode.Right
    }
  }

其工夫复杂度与插入统一。
查找代码请参考：https://github.com/whuanle/ls…

删除

删除操作时，只须要查找到对应的节点，将 Value 清空，而后设置删除标记即可，该节点是不能被删除的。

        currentNode.KV.Value = nil
        currentNode.KV.Deleted = true

其工夫复杂度与插入统一。

删除代码请参考：https://github.com/whuanle/ls…

遍历算法

参考代码：https://github.com/whuanle/ls…
为了将二叉排序树的节点程序遍历进去，递归算法是最简略的，然而当树的档次很高时，递归会导致耗费很多内存空间，因而咱们须要应用栈算法，来对树进行遍历，程序拿到所有节点。

Go 语言中，利用切片实现栈：
https://github.com/whuanle/ls…

二叉排序树的程序遍历，实际上就是前序遍历，依照前序遍历，遍历实现后，取得的节点汇合，其 Key 肯定是程序的。
参考代码如下：

// 应用栈，而非递归，栈应用了切片，能够主动扩大大小，不用放心栈满
  stack := InitStack(tree.count / 2)
  values := make([]kv.Value, 0)

  tree.rWLock.RLock()
  defer tree.rWLock.RUnlock()

  // 从小到大获取树的元素
  currentNode := tree.root
  for {
    if currentNode != nil {stack.Push(currentNode)
      currentNode = currentNode.Left
    } else {popNode, success := stack.Pop()
      if success == false {break}
      values = append(values, popNode.KV)
      currentNode = popNode.Right
    }
  }

遍历代码：
https://github.com/whuanle/ls…

栈大小默认调配为树节点数量的一半，如果此树是均衡的，则数量大小比拟适合。并且也不是将所有节点都推送到栈之后能力进行读取，只有没有左孩，即可从栈中取出元素读取。

如果树不是均衡的，那么理论须要的栈空间可能更大，然而这个栈应用了切片，如果栈空间有余，会主动扩大的。

遍历过程如下动图所示：

动图制作不易~
能够看到，须要多少栈空间，与二叉树的高度无关。

▌WAL

WAL 的构造体定义如下：

type Wal struct {
  f    *os.File
  path string
  lock sync.Locker
}

WAL 须要具备两种能力：
1，程序启动时，可能读取 WAL 文件的内容，复原为内存表（二叉排序树）。
2，程序启动后，写入、删除操作内存表时，操作要写入到 WAL 文件中。
参考代码：
https://github.com/whuanle/ls…

上面来解说笔者的 WAL 实现过程。

上面是写入 WAL 文件的简化代码：

// 记录日志
func (w *Wal) Write(value kv.Value) {data, _ := json.Marshal(value)
  err := binary.Write(w.f, binary.LittleEndian, int64(len(data)))
  err = binary.Write(w.f, binary.LittleEndian, data)
}

能够看到，先写入一个 8 字节，再将 Key/Value 序列化写入。

为了可能在程序启动时，正确从 WAL 文件复原数据，那么必然须要对 WAL 文件做好正确的分隔，以便可能正确读取每一个元素操作。
因而，每一个被写入 WAL 的元素，都须要记录其长度，其长度应用 int64 类型示意，int64 占 8 个字节。

WAL 文件复原过程

在上一大节中，写入 WAL 文件的一个元素，由元素数据及其长度组成。那么 WAL 的文件构造能够这样对待：

因而，在应用 WAL 文件复原数据时，首先读取文件结尾的 8 个字节，确定第一个元素的字节数量 n，而后将 8 ~ (8+n) 范畴中的二进制数据加载到内存中，而后通过 json.Unmarshal() 将二进制数据反序列化为 kv.Value 类型。

接着，读取 (8+n) ~ (8+n)+8 地位的 8 个字节，以便确定下一个元素的数据长度，这样一点点把整个 WAL 文件读取结束。

个别 WAL 文件不会很大，因而在程序启动时，数据恢复过程，能够将 WAL 文件全副加载到内存中，而后一一读取和反序列化，辨认操作是 Set 还是 Delete，而后调用二叉排序树的 Set 或 Deleted 办法，将元素都增加到节点中。
参考代码如下：

代码地位：
https://github.com/whuanle/ls…

▌SSTable 与 SSTable Tree

SSTable 波及的代码比拟多，能够依据保留 SSTable 文件、从文件解析 SSTable 和搜寻 Key 三局部进行划分。

笔者所写的所有 SSTable 代码文件列表如下：

SSTable 构造
SSTable 的构造体定义如下：

// SSTable 表，存储在磁盘文件中
type SSTable struct {
  // 文件句柄
  f        *os.File
  filePath string
  // 元数据
  tableMetaInfo MetaInfo
  // 文件的稠密索引列表
  sparseIndex map[string]Position
  // 排序后的 key 列表
  sortIndex []string
  lock sync.Locker
}

sortIndex 中的元素是有序的，并且元素内存地位相连，便于 CPU 缓存，进步查找性能，还能够应用布隆过滤器，疾速确定该 SSTable 中是否存在此 Key。

当确定该 SSTable 之后，便从 sparseIndex 中查找此元素的索引，从而能够在文件中定位。

其中元数据和稠密索引的构造体定义如下：

type MetaInfo struct {
  // 版本号
  version int64
  // 数据区起始索引
  dataStart int64
  // 数据区长度
  dataLen int64
  // 稠密索引区起始索引
  indexStart int64
  // 稠密索引区长度
  indexLen int64
}

// Position 元素定位，存储在稠密索引区中，示意一个元素的起始地位和长度
type Position struct {
  // 起始索引
  Start int64
  // 长度
  Len int64
  // Key 曾经被删除
  Deleted bool
}

能够看到，一个 SSTable 构造体除了须要指向磁盘文件外，还须要在内存中缓存一些货色，不过不同开发者的做法不一样。就比如说笔者的做法，在一开始时，便固定了这种模式，须要在内存中缓存 Keys 列表，而后应用字典缓存元素定位。

// 文件的稠密索引列表
  sparseIndex map[string]Position
  // 排序后的 key 列表
  sortIndex []string

但实际上，只保留 sparseIndex map[string]Position 也能够实现所有查找操作，sortIndex []string 不是必须的。

SSTable 文件构造

SSTable 的文件，分为数据区，稠密索引区，元数据 / 文件索引，三个局部。存储的内容与开发者定义的数据结构无关。如下图所示：

数据区是 序列化后的 Value 构造体列表，而稠密索引区是序列化后的 Position 列表。不过两个区域的序列化解决形式不一样。

稠密索引区，是 map[string]Position 类型序列化为二进制存储的，那么咱们能够读取文件时，能够间接将稠密索引区整个反序列化为 map[string]Position。

数据区，是一个个 kv.Value 序列化后追加的，因而是不能将整个数据区反序列化为 []kv.Value，只能通过 Position 将数据区的每一个 block 逐渐读取，而后反序列化为 kv.Value。

SSTable Tree 构造和治理 SSTable 文件

为了组织大量的 SSTable 文件，咱们还须要一个构造体，以层次结构，去治理所有的磁盘文件。
咱们须要定义一个 TableTree 构造体，其定义如下：

// TableTree 树
type TableTree struct {levels []*tableNode  // 这部分是一个链表数组
  // 用于防止进行插入或压缩、删除 SSTable 时发生冲突
  lock *sync.RWMutex
}

// 链表，示意每一层的 SSTable
type tableNode struct {
  index int
  table *SSTable
  next  *tableNode
}

为了不便对 SSTable 进行分层和标记插入程序，须要制订 SSTable 文件的命名规定。
如下文件所示：

├── 0.0.db
├── 1.0.db
├── 2.0.db
├── 3.0.db
├── 3.1.db
├── 3.2.db

SSTable 文件由 {level}.{index}.db 组成，第一个数字代表文件所在的 SSTable 层，第二个数字，示意在该层中的索引。

其中，索引越大，示意其文件越新。

插入 SSTable 文件过程

当从内存表转换为 SSTable 时，每个被转换的 SSTable，都是插入到 Level 0 的最初面。

每一层的 SSTable 应用一个链表进行治理：

type tableNode struct {
  index int
  table *SSTable
  next  *tableNode
}

因而，在插入 SSTable 时，沿着往下查找，放到链表的最初面。
链表插入节点的代码局部示例如下：

for node != nil {
      if node.next == nil {
        newNode.index = node.index + 1
        node.next = newNode
        break
      } else {node = node.next}
    }

从内存表转换为 SSTable 时，会波及比拟多的操作，读者请参考代码：https://github.com/whuanle/ls…

读取 SSTable 文件

当程序启动时，须要读取目录中所有的 SSTable 文件到 TableTree 中，接着加载每一个 SSTable 的稠密索引区和元数据。
笔者的 LSM Tree 处理过程如图所示：

笔者的 LSM Tree 加载这些文件，一共耗时 19.4259983s。

加载过程的代码在:
https://github.com/whuanle/ls…

上面笔者说一下大略的加载过程。

首先读取目录中的所有 .db 文件：

  infos, err := ioutil.ReadDir(dir)
  if err != nil {log.Println("Failed to read the database file")
    panic(err)
  }
  for _, info := range infos {
    // 如果是 SSTable 文件
    if path.Ext(info.Name()) == ".db" {tree.loadDbFile(path.Join(dir, info.Name()))
    }
  }

而后创立一个 SSTable 对象，加载文件的元数据和稠密索引区：

// 加载文件句柄的同时，加载表的元数据
  table.loadMetaInfo()
    // 加载稠密索引区
  table.loadSparseIndex()

最初依据 .db 的文件名称，插入到 TableTree 中指定的地位：

SSTable 文件合并

当一层的 SSTable 文件太多时，或者文件太大时，须要将该层的 SSTable 文件，合并起来，生成一个新的、没有反复元素的 SSTable，放到新的一层中。

因而，笔者的做法是在程序启动后，应用一个新的线程，查看内存表是否须要被转换为 SSTable、是否须要压缩 SSTable 层。查看时，从 Level 0 开始，查看两个条件阈值，第一个是 SSTable 数量，另一个是该层 SSTable 的文件总大小。

SSTable 文件合并阈值，在程序启动的时候，须要设置。

  lsm.Start(config.Config{
    DataDir:    `E:\ 我的项目 \lsm 数据测试目录 `,
    Level0Size: 1,    // 第 0 层所有 SSTable 文件大小之和的阈值
    PartSize:   4,    // 每一层 SSTable 数量阈值
    Threshold:  500,    // 内存表元素阈值
        CheckInterval: 3, // 压缩工夫距离
  })

每一层的 SSTable 文件大小之和，是依据第 0 层生成的，例如，当你设置第 0 层为 1MB 时，第 1 层则为 10MB，第 2 层则为 100 MB，使用者只须要设置第 0 层的文件总大小阈值即可。

上面来阐明 SSTable 文件合并过程。
压缩合并的残缺代码请参考：https://github.com/whuanle/ls…
上面是初始的文件树：

首先创立一个二叉排序树对象：
memoryTree := &sortTree.Tree{}
而后在 Level 0 中，从索引最小的 SSTable 开始，读取文件数据区中的每一个 block，反序列化后，进行插入操作或删除操作。

for k, position := range table.sparseIndex {
      if position.Deleted == false {value, err := kv.Decode(newSlice[position.Start:(position.Start + position.Len)])
        if err != nil {log.Fatal(err)
        }
        memoryTree.Set(k, value.Value)
      } else {memoryTree.Delete(k)
      }
    }

将 Level 0 的所有 SSTable 加载到二叉排序树中，即合并所有元素。

而后将二叉排序树转换为 SSTable，插入到 Level 1 中。

接着，删除 Level 0 的所有 SSTable 文件。

注，因为笔者的压缩形式会将文件加载到内存中，应用切片存储文件数据，因而可能会呈现容量过大的谬误。

这是一个值得关注的中央。

SSTable 查找过程

残缺的代码请参考：
https://github.com/whuanle/ls…

当须要查找一个元素时，首先在内存表中查找，查找不到时，须要在 TableTree 中，一一查找 SSTable。

// 遍历每一层的 SSTable
  for _, node := range tree.levels {
    // 整顿 SSTable 列表
    tables := make([]*SSTable, 0)
    for node != nil {tables = append(tables, node.table)
      node = node.next
    }
    // 查找的时候要从最初一个 SSTable 开始查找
    for i := len(tables) - 1; i >= 0; i-- {value, searchResult := tables[i].Search(key)
      // 未找到，则查找下一个 SSTable 表
      if searchResult == kv.None {continue} else { // 如果找到或已被删除，则返回后果
        return value, searchResult
      }
    }
  }

在 SSTable 外部查找时，应用了二分查找法：

// 元素定位
  var position Position = Position{Start: -1,}
  l := 0
  r := len(table.sortIndex) - 1

  // 二分查找法，查找 key 是否存在
  for l <= r {mid := int((l + r) / 2)
    if table.sortIndex[mid] == key {
      // 获取元素定位
      position = table.sparseIndex[key]
      // 如果元素已被删除，则返回
      if position.Deleted {return kv.Value{}, kv.Deleted
      }
      break
    } else if table.sortIndex[mid] < key {l = mid + 1} else if table.sortIndex[mid] > key {r = mid - 1}
  }

  if position.Start == -1 {return kv.Value{}, kv.None
  }

对于 LSM Tree 数据库的编写，就到这里结束了，上面理解笔者的数据库性能和应用办法。

▌简略的应用测试

示例代码地位：
https://gist.github.com/whuan…
首先下载依赖包：

go get -u github.com/whuanle/lsm@v1.0.0

而后应用 lsm.Start() 初始化数据库，再增删查改 Key，示例代码如下：

package main

import (
  "fmt"
  "github.com/whuanle/lsm"
  "github.com/whuanle/lsm/config"
)

type TestValue struct {
  A int64
  B int64
  C int64
  D string
}

func main() {
  lsm.Start(config.Config{
    DataDir:    `E:\ 我的项目 \lsm 数据测试目录 `,
    Level0Size: 1,
    PartSize:   4,
    Threshold:  500,
        CheckInterval: 3, // 压缩工夫距离
  })
  // 64 个字节
  testV := TestValue{
    A: 1,
    B: 1,
    C: 3,
    D: "00000000000000000000000000000000000000",
  }

  lsm.Set("aaa", testV)

  value, success := lsm.Get[TestValue]("aaa")
  if success {fmt.Println(value)
  }

  lsm.Delete("aaa")
}

testV 是 64 字节，而 kv.Value 保留了 testV 的值，kv.Value 字节大小为 131。

文件压缩测试

咱们能够写一个从 26 个字母中取任意 6 字母组成 Key，插入到数据库中，从中察看文件压缩合并，和插入速度等。

不同循环档次插入的元素数量：

生成的测试文件列表：

文件压缩合并动图过程的如下(约 20 秒)：

插入测试

上面是一些不谨严的测试后果。

设置启动数据库时的配置：

  lsm.Start(config.Config{
    DataDir:    `E:\ 我的项目 \lsm 数据测试目录 `,
    Level0Size: 10,  // 0 层 SSTable 文件大小
    PartSize:   4,   // 每层文件数量
    Threshold:  3000, // 内存表阈值
        CheckInterval: 3, // 压缩工夫距离
  })

  lsm.Start(config.Config{
    DataDir:    `E:\ 我的项目 \lsm 数据测试目录 `,
    Level0Size: 100,
    PartSize:   4,
    Threshold:  20000,
        CheckInterval: 3,
  })

插入数据：

func insert() {

  // 64 个字节
  testV := TestValue{
    A: 1,
    B: 1,
    C: 3,
    D: "00000000000000000000000000000000000000",
  }

  count := 0
  start := time.Now()
  key := []byte{'a', 'a', 'a', 'a', 'a', 'a'}
  lsm.Set(string(key), testV)
  for a := 0; a < 1; a++ {
    for b := 0; b < 1; b++ {
      for c := 0; c < 26; c++ {
        for d := 0; d < 26; d++ {
          for e := 0; e < 26; e++ {
            for f := 0; f < 26; f++ {key[0] = 'a' + byte(a)
              key[1] = 'a' + byte(b)
              key[2] = 'a' + byte(c)
              key[3] = 'a' + byte(d)
              key[4] = 'a' + byte(e)
              key[5] = 'a' + byte(f)
              lsm.Set(string(key), testV)
              count++
            }
          }
        }
      }
    }
  }

  elapse := time.Since(start)
  fmt.Println("插入实现，数据量：", count, ", 耗费工夫：", elapse)
}

两次测试，生成的 SSTable 总文件大小都是约 82MB。
两次测试耗费的工夫：

插入实现，数据量：456976 , 耗费工夫：1m43.4541747s

插入实现，数据量：456976 , 耗费工夫：1m42.7098146s

因而，每个元素 131 个字节，这个数据库 100s 能够插入 约 45w 条数据，即每秒插入 4500 条数据。

如果将 kv.Value 的值比拟大，测试在 3231 字节时，插入 456976 条数据，文件约 1.5GB，耗费工夫 2m10.8385817s，即每秒插入 3500 条。

插入较大值的 kv.Value，代码示例：https://gist.github.com/whuan…

加载测试

上面是每个元素 3231 字节时，插入 45 万条数据后的 SSTable 文件列表，程序启动时，咱们须要加载这些文件。

2022/05/21 21:59:30 Loading wal.log...
2022/05/21 21:59:32 Loaded wal.log,Consumption of time :  1.8237905s
2022/05/21 21:59:32 Loading database...
2022/05/21 21:59:32 The SSTable list are being loaded
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /1.0.db
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /1.0.db ,Consumption of time :  92.9994ms
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /1.1.db
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /1.1.db ,Consumption of time :  65.9812ms
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /2.0.db
2022/05/21 21:59:32 Loading the  E:\ 我的项目 \lsm 数据测试目录 /2.0.db ,Consumption of time :  331.6327ms
2022/05/21 21:59:32 The SSTable list are being loaded,consumption of time :  490.6133ms

能够看到，除 WAL 加载比拟耗时（因为要一一插入内存中），SSTable 文件的加载还是比拟快的。

查找测试

如果元素都在内存中时，即便有 45 万条数据，查找速度也是十分快的，例如查找 aaaaaa(Key 最小)和 aazzzz(Key 最大)的数据，耗时都很低。

上面应用每条元素 3kb 的数据库文件进行测试。

查找代码：

  start := time.Now()
  elapse := time.Since(start)
  v, _ := lsm.Get[TestValue]("aaaaaa") // 或者 aazzzz
  fmt.Println("查找实现，耗费工夫：", elapse)
  fmt.Println(v)

如果在 SSTable 中查找，因为 aaaaaa 是首先被写入的，因而必定会在最底层的 SSTable 文件的开端，须要耗费的工夫比拟多。
SSTable 文件列表：

├── 1.0.db      116MB
├── 2.0.db    643MB
├── 2.1.db    707MB

约 1.5GB

aaaaaa 在 2.0db 中，查找时会以 1.0.db、2.1.db、2.0.db 的程序加载。
查问速度测试：

2022/05/22 08:25:43 Get aaaaaa
查找 aaaaaa 实现，耗费工夫：19.4338ms

2022/05/22 08:25:43 Get aazzzz
查找 aazzzz 实现，耗费工夫：0s

对于笔者的 LSM Tree 数据库，就介绍到这里，具体的实现代码，请参考 Github 仓库。

微软最有价值专家（MVP）

微软最有价值专家是微软公司授予第三方技术专业人士的一个寰球奖项。29 年来，世界各地的技术社区领导者，因其在线上和线下的技术社区中分享专业知识和教训而取得此奖项。
MVP 是通过严格筛选的专家团队，他们代表着技术最精湛且最具智慧的人，是对社区投入极大的激情并乐于助人的专家。MVP 致力于通过演讲、论坛问答、创立网站、撰写博客、分享视频、开源我的项目、组织会议等形式来帮忙别人，并最大水平地帮忙微软技术社区用户应用 Microsoft 技术。
更多详情请登录官方网站：
https://mvp.microsoft.com/zh-cn

长按辨认二维码
关注微软中国 MSDN

点击申请加入微软最有价值专家我的项目