Golang实现KV存储引擎

通过本系列的学习可以学到什么？

• WAL预写日志的实现
• LSM Tree（Log-Structed-Merge Tree)
• 如何构架一个企业级的项目
• KV数据的序列化和反序列化存储
• Golang的基本语法

简介

内存数据采用 SkipList 存储

通过 WAL (Write Ahead Log)保证内存数据 durability和 crash-safe能力

代码逻辑结构

1. 先通过 easydb.Open打开数据库 *DB对象；*DB内部基于 WAL恢复内存数据 openAllMemtables【就是读取 segment文件，解析出一个个 LogRecord保存到 skiplist中】，同时将内存数据分成活跃内存和不可变内存【参考 LSM Tree结构】。每个内存对象 *memtable内部除了定义 skiplist记录内存数据，同时定义 *wal对象记录磁盘，*wal对象中的磁盘文件按照指定的大小分段保存（这里类似kafka中日志数据文件分段原理）
2. 然后调用 db.Put方法，内部通过 batch开启写事物（对db上锁），将数据批量保存 batch的 pendingWrites中,然后在 batch.Commit一次性全部保存到内存和预写日志中同时关闭写事物（对db解锁）
3. 调用 db.Get方法，内部通过 batch开启读事物（对db上锁），读取所有的内存对象中的数据（倒序）方式，也就是从最近的内存对象 *memtable开始读，读取结束，提交事物(关闭读事物，对db解锁)

建议从下面 Open Get Put这几个函数开始看起

package main

import (
	"fmt"

	"https://github.com/mgface2022/easydb"
	"https://github.com/mgface2022/easydb/utils"
)

// this file shows how to use the basic operations of EasyDB
func main() {
	// specify the options
	options := easydb.DefaultOptions
	options.DirPath = utils.ExecDir() + "/data"

	// open a database
	db, err := easydb.Open(options)
	if err != nil {
		panic(err)
	}
	defer func() {
		_ = db.Close()
	}()

	// put a key
	err = db.Put([]byte("name"), []byte("easydb"), nil)
	if err != nil {
		panic(err)
	}

	// get a key
	val, err := db.Get([]byte("name"))
	if err != nil {
		panic(err)
	}
	println(string(val))

	// delete a key
	err = db.Delete([]byte("name"), nil)
	if err != nil {
		panic(err)
	}

	// get a key
	val, err = db.Get([]byte("name"))
	if err != nil {
		if err == easydb.ErrKeyNotFound {
			fmt.Println("key not exist")
			return
		}
		panic(err)
	}
	println(string(val))
}

WAL日志格式

• WAL日志文件按照 SegmentSize分成一个个的段文件；
• 每个段文件，按照 32KB为一块存储区域，存储 多个 chunk实际数据
• 每个 chunk由 7 字节 header + 数据 payload 组成；header头包括 4字节校验码，2字节数据长度 1字节数据类型；校验码校验的范围为：【length + type + payload】确保数据没有损坏
• 一个数据可能由多个 chunk组成

• 当在block中保存了多个chunk后，block剩余的空间不够保存数据，多余的空间浪费掉，填充一些无效字节即可

Ps：本项目主要参考 LotusDB 实现