0 前言
本期咱们延续专题——基于 go 语言从零到一实现 lsm tree 的分享内容，本专题共分为下述四篇，本文是其中的第二篇——memtable 结构篇：
• 基于go实现lsm tree之memtable结构（本篇）
• 基于go实现lsm tree之sstable结构
• 基于go实现lsm tree之level sorted merge流程
关于以上内容的源码均已上传到我的个人开源项目中，大家根据需要自取，如果觉得代码写得还凑合，可以留个 star，不胜感激.
开源项目 golsm 传送门 >> https://github.com/xiaoxuxiansheng/golsm
1 memtable&wal
1.1 memtable 定位
• memtable 是 lsm tree 架构最顶层使用到的内存有序表，分为读写表 active memtable，和只读表 read-only memtable 两类.
• active memtable: 又称读写表，是 lsm tree 唯一的写入口. 本身基于有序表实现，因此内部 kv 对是有序且不重复的 . 当读写表容量达到阈值，会切换为 read only 模式
• read-only memtable: 又称只读表. 是处于溢写磁盘流程的中间状态. 溢写落盘后，会成为 level0 层的 sstable 文件，因此能保证文件内部是有序且不重复的， 但是 level0 层文件与文件之间无法保证上述性质.
有序表指的是内部元素已经按照 key 大小指定好顺序的数据结构，能够在检索时提供更好的性能表现. 有序表本身可以理解为一个 interface，任何一个实现了各项功能的数据结构都可以称之为有序表，包括我们今天会提及的：红黑树（Red-Black Tree）以及跳表（Skiplist） .
1.2 memtable 选型
在 memtable 有序表的选型上，纳入我们考量范围的结构包括跳表（Skiplist） 和红黑树（Red-Black Tree） 两种.
• 跳表 skiplist
跳表 skiplist 是有序表下的一种经典实现，本质是采取以空间换时间的策略，在有序链表的基础之上，维护了多层级的索引结构，基于二分查找的方式实现 O(logN) 级别时间复杂度下的增删改查操作. 跳表结构示意图如下：
• 红黑树 Red-Black Tree
红黑树，顾名思义，整棵树由红、黑两种颜色的节点组成，该数据结构包含了下述性质：
（1）本身是一棵搜索二叉树（左子树 key 均小于自身，右子树 key 均大于自身）
（2）根节点为黑色
（3）所有叶节点也都是黑色（叶节点都是nil节点）
（4）从根节点到叶节点的路径上，不允许出现两个红色的节点
（5）从任意一条根节点到叶节点的路径中，都包含有相同数目的黑色节点
综上可以看出，从任意节点出发沿任意路径抵达叶子节点，途径的节点个数相差不会超过一倍，即红黑树的平衡性能够得到保证，其增删改查操作，均能维持在 O(logN) 的时间复杂度内.
• 有序表选型
首先给出选型结论：golsm 中选用跳表作为 memtable 的实现结构. 选型原因如下：
（1）跳表性能不弱于红黑树
（2）跳表实现难度低于红黑树
（3）跳表支持范围查询
（4）跳表具有更好的并发性能
实际上，上述第（4）点仅停留在理论层面，我曾根据该方向展开一次分享探讨，但最终结果还不具备落到工程实践的成熟程度. 具体内容可以参见我之前分享的文章——如何实现一个并发安全的跳表.
1.3 skiplist 实现原理
下面简要概括一下跳表结构的实现原理，更完整的原理剖析内容可以参见我之前发表的文章——基于 golang 从零到一实现跳表.
跳表核心性质：
• 由多层单向链表结构组成，最底层拥有全量数据，层数越高，数据量越稀疏. 高层可以理解为索引结构
• 每次节点个数接近于相邻下层节点数的一半（事实上，这个比例可以配置）；跳表在插入节点时，随机选取节点高度，保证每提高一层的概率都逐级递减，以满足不同层之间的节点个数比例分布
• 对于一个 m 层存在的节点，在 1~m-1层中这个节点也一定存在
• 头节点和尾节点的高度是动态扩缩的，其高度取决于当前跳表内数据节点的最大高度
• 跳表的”跳“字体现在，每跳过一个高层节点，实际上都过滤跳过了底层的大量数据，从而实现检索加速
1.4 wal 定位
wal 全称 write-ahead log，是基于磁盘存储的预写日志. 其功能是为了避免易失性存储的 memtable 出现数据丢失，保留基于 wal 恢复 memtable 数据的能力.
在 lsm tree 写数据的流程组织中，会保证先将写入的数据落到 wal 文件中，再进行 memtable 的写入操作. 在 wal 文件中，会基于【key长度】-【value长度】-【key内容】-【value内容】的形式完成内容存储，以实现不同 kv 对的数据分隔.
原理部分我们概述至此，从下一章开始，我们一起深入 golsm 源码看看有关于 memtable 和 wal 的实现细节.
2 memtable实现
2.1 memtable interface
有关 memtable 我们将其定义为抽象 interface，包括下述方法：
• Put：写入一条 kv 数据
• Get：读取一条 kv 数据
• All：返回其中所有 kv 数据
• Size：数据量总大小，单位 byte
• EntriesCnt：kv 对数
// 有序表 interface
type MemTable interface {
Put(key, value []byte) // 写入数据
Get(key []byte) ([]byte, bool) // 读取数据，第二个 bool flag 标识数据是否存在
All() []*KV // 返回所有的 kv 对数据
Size() int // 有序表内数据大小，单位 byte
EntriesCnt() int // kv 对数量
}
type KV struct {
Key, Value []byte
}
2.2 skiplist 数据结构
下面是有关跳表的实现部分.
skipNode 是跳表中的节点：
• key、value：节点中存储的数据
• nexts：下一个节点的指针. 由于跳表是多层结构，因此指针为切片的形式，切片 index 对应所属的层数
// 跳表节点
type skipNode struct {
nexts []*skipNode // 通过 next slice 来实现跳表节点多层指针结构
key, value []byte // 节点内存储的 kv 对数据
}
Skiplist 是跳表主体类，其中持有跳表头节点指针 head.
// 跳表，未加锁，不保证并发安全
type Skiplist struct {
head *skipNode // 跳表的头节点
entrisCnt int // 跳表中的 kv 对个数
size int // 跳表数据量大小，单位 byte
}
// 构造跳表实例
func NewSkiplist() MemTable {
return &Skiplist{
head: &skipNode{}, // 需要初始化根节点
}
}
2.3 跳表读流程
跳表读流程步骤如下：
（1）以 head 节点作为起点
（2）从当前跳表存在的最大高度出发
（3）倘若右侧节点 key 值小于 target，则持续向右遍历
（4）倘若右侧节点 key 值等于 target，则代表找到目标，直接取值返回
（5）倘若右侧节点为终点（nil）或者 key 值大于 target，则沿当前节点降低高度进入下一层
（6）重复上述（3）-（5）步
（7）倘若已经抵达第1层仍然找到不到 target，则返回 key 不存在的信息
// 从跳表中读取 kv 对
func (s *Skiplist) Get(key []byte) ([]byte, bool) {
// 倘若 key 存在，返回对应 val
if node := s.getNode(key); node != nil {
return node.value, true
}
return nil, false
}
// 根据 key 获取跳表中对应节点
func (s *Skiplist) getNode(key []byte) *skipNode {
move := s.head
// 层数自高向低，逐层检索
for level := len(s.head.nexts) - 1; level >= 0; level-- {
// 持续向右移动，直到右侧为空或者右侧节点 key >= 检索 key
for move.nexts[level] != nil && bytes.Compare(move.nexts[level].key, key) < 0 {
move = move.nexts[level]
}
// 如果右侧节点 key = 检索 key，则找到目标返回. 否则进入下一层
if move.nexts[level] != nil && bytes.Equal(move.nexts[level].key, key) {
return move.nexts[level]
}
}
return nil
}
跳表获取全量数据的流程比较简单，只需要沿着最底层依次遍历数据即可：
// 获取跳表中全量 kv 对数据
func (s *Skiplist) All() []*KV {
if len(s.head.nexts) == 0 {
return nil
}
kvs := make([]*KV, 0, s.entrisCnt)
// 从第 0 层开始自左向右依次遍历读取
for move := s.head; move.nexts[0] != nil; move = move.nexts[0] {
kvs = append(kvs, &KV{
Key: move.nexts[0].key,
Value: move.nexts[0].value,
})
}
return kvs
}
2.4 跳表写流程
（1）首先基于读流程检索出 key 对应的节点是否存在，倘若存在，则对值进行更新并直接返回
（2）随机出新插入节点的高度；倘若新插入节点的高度大于当前跳表的最大高度，则需要对起点和终点的高度进行扩容
（3）以 head 节点作为起点，从当前跳表存在的最大高度出发
（4）倘若右侧节点 key 值小于 target，则持续向右遍历
（5）倘若右侧节点为终点（nil）或者 key 值大于 target，则在该空隙插入新节点，并降低高度进入下一层
（6）重复（4）-（5）步
（7）倘若已经进入第 1 层，插入新节点后即可返回
// 写入一笔 kv 对到跳表. 如果 key 不存在，则为插入操作；如果 key 已存在则为覆盖操作
func (s *Skiplist) Put(key, value []byte) {
// 倘若 key 已存在
if node := s.getNode(key); node != nil {
// 根据新老 value dif 值，调整 skiplist 数据量 size 大小
s.size += (len(value) - len(node.value))
// 覆盖之
node.value = value
return
}
// key 不存在，则为插入行为. 在跳表 size 基础上加上 key 和 value 的大小
s.size += (len(key) + len(value))
s.entrisCnt++
// roll 出新节点高度
newNodeHeight := s.roll()
// 倘若跳表原高度不足，则补齐高度
if len(s.head.nexts) < newNodeHeight {
dif := make([]*skipNode, newNodeHeight+1-len(s.head.nexts))
s.head.nexts = append(s.head.nexts, dif...)
}
// 构造新节点
newNode := skipNode{
nexts: make([]*skipNode, newNodeHeight),
key: key,
value: value,
}
// 层数自高向低，每层按序插入节点
move := s.head
for level := newNodeHeight - 1; level >= 0; level-- {
// 层内持续向右遍历，直到右侧节点不存在或者 key 值更大
for move.nexts[level] != nil && bytes.Compare(move.nexts[level].key, key) < 0 {
move = move.nexts[level]
}
// 插入节点
newNode.nexts[level] = move.nexts[level]
move.nexts[level] = &newNode
}
}// roll 出一个节点的高度. 最小为 1，每提高 1 层，概率减少为 1//2
func (s *Skiplist) roll() int {
var level int
rander := rand.New(rand.NewSource(time.Now().Unix()))
for rander.Intn(2) == 1 {
level++
}
return level + 1
}
3 wal 实现
聊完跳表，接下来看一下预写日志 wal 的实现. wal 文件根据写入数据和读取数据的视角，拆分为 walWriter 和 walReader 两部分.
3.1 walWriter
用于写 wal 文件的 walWriter 类定义如下：
// 预写日志写入口
type WALWriter struct {
file string // 预写日志文件名，是包含了目录在内的绝对路径
dest *os.File // 预写日志文件
assistBuffer [30]byte // 辅助转移数据使用的临时缓冲区
}
// 构造器
func NewWALWriter(file string) (*WALWriter, error) {
// 打开 wal 文件，如果文件不存在则进行创建
dest, err := os.OpenFile(file, os.O_CREATE|os.O_WRONLY, 0644)
if err != nil {
return nil, err
}
return &WALWriter{
file: file,
dest: dest,
}, nil
}
写入 wal 文件的数据也是以 kv 对的形式存在. 为了能够找到 kv 对之间的间隔，采用【key长度】-【value长度】-【key内容】-【value内容】的形式完成内容的存储，读取时也采用同样的协议解析即可.
// 写入一笔 kv 对到 wal 文件中
func (w *WALWriter) Write(key, value []byte) error {
// 首先将key 和 value 长度填充到临时缓冲区 assistBuffer 中
n := binary.PutUvarint(w.assistBuffer[0:], uint64(len(key)))
n += binary.PutUvarint(w.assistBuffer[n:], uint64(len(value)))
// 依次将 key 长度、val 长度、key、val 填充到 buf 中
var buf []byte
buf = append(buf, w.assistBuffer[:n]...)
buf = append(buf, key...)
buf = append(buf, value...)
// 将以上内容写入到 wal 文件中
_, err := w.dest.Write(buf)
return err
}
func (w *WALWriter) Close() {
_ = w.dest.Close()
}
3.2 walReader
用于读 wal 文件的 walReader 类定义如下：
// wal 文件读取器
type WALReader struct {
file string // 预写日志文件名，是包含了目录在内的绝对路径
src *os.File // 预写日志文件
reader *bufio.Reader // 基于 bufio reader 对日志文件的封装
}
// 构造器函数.
func NewWALReader(file string) (*WALReader, error) {
// 以只读模式打开 wal 文件，要求目标文件必须存在
src, err := os.OpenFile(file, os.O_RDONLY, 0644)
if err != nil {
return nil, err
}
return &WALReader{
file: file,
src: src,
reader: bufio.NewReader(src),
}, nil
}
一个 wal 文件对应一个 memtable 的全量数据.
RestoreToMemtable 方法用于读取 wal 文件的全量内容，将所有 kv 对写入到 memtable 当中. 遵循数据格式，每次采用【key长度】-【value长度】-【key内容】-【value内容】的协议完成一组 kv 数据的读取，直到 wal 文件内容读完即可.
// 读取 wal 文件，将所有内容注入到 memtable 中，以实现内存数据的复原
func (w *WALReader) RestoreToMemtable(memTable memtable.MemTable) error {
// 读取 wal 文件全量内容
body, err := io.ReadAll(w.reader)
if err != nil {
return err
}
// 兜底保证文件偏移量被重置到起始位置
defer func() {
_, _ = w.src.Seek(0, io.SeekStart)
}()
// 将文件中读取到的内容解析成一系列 kv 对
kvs, err := w.readAll(bytes.NewReader(body))
if err != nil {
return err
}
// 将所有 kv 数据注入到 memtable 中
for _, kv := range kvs {
memTable.Put(kv.Key, kv.Value)
}
return nil
}
// 将文件中读到的原始内容解析成一系列 kv 对数据
func (w *WALReader) readAll(reader *bytes.Reader) ([]*memtable.KV, error) {
var kvs []*memtable.KV
// 循环读取每组 kv 对，直到遇到 eof 错误才终止流程
for {
// 从 reader 中读取首个 uint64 作为 key 长度
keyLen, err := binary.ReadUvarint(reader)
// 如果遇到 eof 错误说明文件内容已经读取完毕，终止流程
if errors.Is(err, io.EOF) {
break
}
if err != nil {
return nil, err
}
// 从 reader 中读取下一个 uint64 作为 val 长度
valLen, err := binary.ReadUvarint(reader)
if err != nil {
return nil, err
}
// 从 reader 中读取对应于 key 长度的字节数作为 key
keyBuf := make([]byte, keyLen)
if _, err = io.ReadFull(reader, keyBuf); err != nil {
return nil, err
}
// 从 reader 中读取对应于 val 长度的字节数作为 val
valBuf := make([]byte, valLen)
if _, err = io.ReadFull(reader, valBuf); err != nil {
return nil, err
}
kvs = append(kvs, &memtable.KV{
Key: keyBuf,
Value: valBuf,
})
}
return kvs, nil
}
4 memtable&wal 流程串联
接下来，我们从 lsm tree 整体视角出发，梳理一下有关于 memtable 和 wal 模块的交互流程.
4.1 写流程
在 lsm tree 的写流程中，需要先将 kv 对数据写入预写日志中，再将 kv 对数据写入读写 memtable.
// 写入一组 kv 对到 lsm tree. 会直接写入到读写 memtable 中.
func (t *Tree) Put(key, value []byte) error {
// 1 加写锁
t.dataLock.Lock()
defer t.dataLock.Unlock()
// 2 数据预写入预写日志中，防止因宕机引起 memtable 数据丢失.
if err := t.walWriter.Write(key, value); err != nil {
return err
}
// 3 数据写入读写跳表
t.memTable.Put(key, value)
// ...
return nil
}
在写流程结束前，需要校验一下读写 memtable 中的数据量大小是否达到溢写落盘的阈值，是的话，需要通过 refreshMemTableLocked 方法完成 memtable 的模式切换：
• 将 memtable 由读写模式切换为只读模式，然后通过 memCompactC 通道将其传递给 compact 协程进行溢写处理
• 构建一个新的 memtable 用于处理写请求，并构造与之相应的 wal 文件
// 切换读写跳表为只读跳表，并构建新的读写跳表
func (t *Tree) refreshMemTableLocked() {
// 辞旧
// 将读写跳表切换为只读跳表，追加到 slice 中，并通过 chan 发送给 compact 协程，由其负责进行溢写成为 level0 层 sst 文件的操作.
oldItem := memTableCompactItem{
walFile: t.walFile(),
memTable: t.memTable,
}
t.rOnlyMemTable = append(t.rOnlyMemTable, &oldItem)
t.walWriter.Close()
go func() {
t.memCompactC <- &oldItem
}()
// 迎新
// 构造一个新的读写 memtable，并构造与之相应的 wal 文件.
t.memTableIndex++
t.newMemTable()
}
func (t *Tree) newMemTable() {
t.walWriter, _ = wal.NewWALWriter(t.walFile())
t.memTable = t.conf.MemTableConstructor()
}
4.2 落盘流程
golsm 专门开启了一个 compact 协程用于处理 memtable 溢写落盘的流程. 在接收到待落盘的read-only memtable 后，会通过 flushMemTable 方法将其组织成一个 sstable 文件溢写到 level0 中，并从 lsm tree 的 rOnlyMemTable 切片中移除相应 memtable.
// 运行 compact 协程.
func (t *Tree) compact() {
for {
select {
// ...
// 接收到 read-only memtable，需要将其溢写到磁盘成为 level0 层 sstable 文件.
case memCompactItem := <-t.memCompactC:
t.compactMemTable(memCompactItem)
// ...
}
}
// 将只读 memtable 溢写落盘成为 level0 层 sstable 文件
func (t *Tree) compactMemTable(memCompactItem *memTableCompactItem) {
// 处理 memtable 溢写工作:
// 1 memtable 溢写到 0 层 sstable 中
t.flushMemTable(memCompactItem.memTable)
// 2 从 rOnly slice 中回收对应的 table
t.dataLock.Lock()
for i := 0; i < len(t.rOnlyMemTable); i++ {
if t.rOnlyMemTable[i].memTable != memCompactItem.memTable {
continue
}
t.rOnlyMemTable = t.rOnlyMemTable[i+1:]
}
t.dataLock.Unlock()
// 3 删除相应的预写日志. 因为 memtable 落盘后数据已经安全，不存在丢失风险
_ = os.Remove(memCompactItem.walFile)
}
4.3 复原流程
最后是 lsm tree 重启时，通过已有的 wal 文件还原出一系列 memtable 的复原流程.
// 构建出一棵 lsm tree
func NewTree(conf *Config) (*Tree, error) {
// ...
// 读取 wal 还原出 memtable
if err := t.constructMemtable(); err != nil {
return nil, err
}
// ...
}
复原流程入口方法是 constructMemtable，其中会读取所有 wal 文件，然后调用 restoreMemTable 方法将其一一还原成内存中的 memtable.
// 读取 wal 还原出 memtable
func (t *Tree) constructMemtable() error {
// 1 读 wal 目录，获取所有的 wal 文件
raw, _ := os.ReadDir(path.Join(t.conf.Dir, "walfile"))
// 2 wal 文件除杂
var wals []fs.DirEntry
for _, entry := range raw {
if entry.IsDir() {
continue
}
// 要求文件必须为 .wal 类型
if !strings.HasSuffix(entry.Name(), ".wal") {
continue
}
wals = append(wals, entry)
}
// 3 倘若 wal 目录不存在或者 wal 文件不存在，则构造一个新的 memtable
if len(wals) == 0 {
t.newMemTable()
return nil
}
// 4 依次还原 memtable. 最晚一个 memtable 作为读写 memtable
// 前置 memtable 作为只读 memtable，分别添加到内存 slice 和 channel 中.
return t.restoreMemTable(wals)
}
值得一提的是，复原流程会根据 wal 文件创建的先后顺序，将最后一个 memtable 作为提供读写能力的 active memtable，其余则作为只读的 read-only memtable 并继续推进其溢写落盘的流程.
// 基于 wal 文件还原出一系列只读 memtable 和唯一一个读写 memtable
func (t *Tree) restoreMemTable(wals []fs.DirEntry) error {
// 1 wal 排序，index 单调递增，数据实时性也随之单调递增
sort.Slice(wals, func(i, j int) bool {
indexI := walFileToMemTableIndex(wals[i].Name())
indexJ := walFileToMemTableIndex(wals[j].Name())
return indexI < indexJ
})
// 2 依次还原 memtable，添加到内存和 channel
for i := 0; i < len(wals); i++ {
name := wals[i].Name()
file := path.Join(t.conf.Dir, "walfile", name)
// 构建与 wal 文件对应的 walReader
walReader, err := wal.NewWALReader(file)
if err != nil {
return err
}
defer walReader.Close()
// 通过 reader 读取 wal 文件内容，将数据注入到 memtable 中
memtable := t.conf.MemTableConstructor()
if err = walReader.RestoreToMemtable(memtable); err != nil {
return err
}
if i == len(wals)-1 { // 倘若是最后一个 wal 文件，则 memtable 作为读写 memtable
t.memTable = memtable
t.memTableIndex = walFileToMemTableIndex(name)
t.walWriter, _ = wal.NewWALWriter(file)
} else { // memtable 作为只读 memtable，需要追加到只读 slice 以及 channel 中，继续推进完成溢写落盘流程
memTableCompactItem := memTableCompactItem{
walFile: file,
memTable: memtable,
}
t.rOnlyMemTable = append(t.rOnlyMemTable, &memTableCompactItem)
t.memCompactC <- &memTableCompactItem
}
}
return nil
}
5 小结
至此，本文内容结束. 本文和大家展开探讨了 lsm tree 中 memtable 和 wal 模块的底层实现细节. 在此展望未来几周继续和大家展开讨论的内容：
• 基于go实现lsm tree 之主干框架（已完成）
• 基于go实现lsm tree之memtable结构（本篇）
• 基于go实现lsm tree之sstable结构（待完成）
• 基于go实现lsm tree之level sorted merge流程（待完成）
