Golang实现自己的KV存储引擎

通过本项目可以学到什么？

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

项目已托管GitHub : https://github.com/gofish2020/easydb 欢迎学习Star，如果有看不懂的欢迎私信

整个代码量1000多行，基本的大框架也好理解，容易出现错误的点在于代码细节的处理（特别是wal文件的读写部分）

简介

内存数据采用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"

	"github.com/gofish2020/easydb"
	"github.com/gofish2020/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 实现