Golang实现KV存储引擎(一)

77人浏览 / 0人评论 / 添加收藏

Golang实现KV存储引擎

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

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

简介

内存数据采用 SkipList 存储

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

代码逻辑结构

  1. 先通过 easydb.Open打开数据库 *DB对象;*DB内部基于 WAL恢复内存数据 openAllMemtables【就是读取 segment文件,解析出一个个 LogRecord保存到 skiplist中】,同时将内存数据分成活跃内存和不可变内存【参考 LSM Tree结构】。每个内存对象 *memtable内部除了定义 skiplist记录内存数据,同时定义 *wal对象记录磁盘,*wal对象中的磁盘文件按照指定的大小分段保存(这里类似kafka中日志数据文件分段原理)
  2. 然后调用 db.Put方法,内部通过 batch开启写事物(对db上锁),将数据批量保存 batchpendingWrites中,然后在 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 实现

全部评论