基于LSM的Key-Value数据库实现初篇

2023-11-07 22:06:28

前篇文章对LSM的基本原理，算法流程做了简单的介绍，这篇文章将实现一个简单的基于LSM算法的迷你Key-Value数据库，结合上篇文章的理论与本篇文章的实践使之对LSM算法有更好的理解，当然此版本还有很大问题只是Demo模型，后面也会指出；
此LSMDB有支持常见的数据库四大功能：CURD（增删查改），从前篇文章可知要实现基于LSM的数据库此程序中需存在这么几种数据结构：memTable、immutable、SSTable、WAL，分别为内存表、只读内存表、排序字符串表、预写式日志，将这几种数据结构组合起来即可实现一个简单的Key-Value数据库；

结构介绍

MemTable： 内存表，此结构为一个有序的内存结构此处是一个红黑树，当数据达到指定的阈值时会发出刷盘操作，将MemTable拷贝到Immutable生成SSTable，MemTable开始新的周期；
Immutable： 只读内存表，为避免MemTable在刷盘操作时继续有新的入库操作导致出现数据异常情况，引入了此结构使之简单化，在触发刷盘操作时将MemTable数据拷贝到此只读结构，清空MemTable，将Immutable数据生成SSTable，清空Immutable；
SSTable： 为immutable持久化到磁盘后的排序字符串表；
WAL： 为避免MemTable数据还未持久化SSTable到磁盘程序崩溃导致数据丢失的情况引入的，WAL为顺序写入日志，在接收到数据时添加到MemTable的同时将数据写入到WAL文件中，数据刷盘持久化的同时将WAL文件删除，新创建WAL文件，本篇文章暂未实现；

触发SSTable持久化到磁盘时会生成两个文件，一个为SSTable文件由两部分组成数据区与元数据，数据区为所存储的值，元数据为数据与索引的开始Offset、长度组成；另一个为索引文件：索引文件记录了每个Key的起始Offset与长度；

SSTable文件结构：

SSTable索引文件结构：

具体实现

加载SSTable文件

在程序启动时会初始化上面提到到LSM相关结构，同时检查目录是否存在SSTable文件，存在则从新到旧扫描加载每个SSTable文件的元数据，根据其元数据加载SSTable索引文件到内存中。

/**
还原索引
*/
func (s *SSTable) restoreIndex() {
   s.meta.readFormFile(s.dataFile)
   len := s.meta.indexLen
   offset := s.meta.indexStart
   s.indexFile.Seek(int64(offset), 0)
   b := make([]byte, len)
   s.indexFile.Read(b)
   s.indexTree.FromJSON(b)
}

写入操作

LSMDB在执行写操作时会先写入到内存表memoryTable，当memoryTable大小超过某个阈值时会执行切换内存表，将memoryTable数据拷贝到immuTable，清空memoryTable，执行持久化写入SSTable，清空immuTable；

/**
设置键值
*/
func (l *LSMStore) Set(key string, value string) {
  var cmd = &SetCommand{Command{1}, key, value}
  //todo 写入wal
  //写入内存表
  l.memoryTable.Put(key, cmd)
   if l.memoryTable.Size() > storeThreshold {
     l.switchTable()
     l.toSSTable()
   }
}

删除数据

LSMDB数据库中的删除并不是真正的删除，只是追加一条相同Key标志位为删除的数据，在读取时再做相应的处理，其他流程与添加类似；

/**
删除数据
*/
func (l *LSMStore) Del(key string) {
   var cmd = &RMCommand{Command{2}, key}
   //todo 写入wal
   //写入内存表
   l.memoryTable.Put(key, cmd)
    if l.memoryTable.Size() > storeThreshold {
    l.switchTable()
    l.toSSTable()
  }
}

读取数据

读取数据时会先检查memoryTable是否有数据，没有则检查immuTable是否存在，最后会依次检查所加载的SSTable索引是否存在，如存在则根据索引执行的Offset、len从SSTable文件读取相对应的内容数据；

/**
获取数据
*/
func (l *LSMStore) Get(key string) interface{} {
   cmd, found := l.memoryTable.Get(key)
   log.Println("memory：", found, cmd)
   if found {
       if v, ok := cmd.(*SetCommand); ok {
	  return v.Value
        }
    }
 if l.immuTable != nil && l.immuTable.Size() > 0 {
	cmd, found := l.immuTable.Get(key)
	if found {
		if v, ok := cmd.(*SetCommand); ok {
			return v.Value
		}
	}
  } else {
	for _, t := range l.sstableList.Values() {
		table := t.(*SSTable)
		v := table.query(key)
		return v
	}
   }
  return nil
}

WebApi

开放用于查询、添加、删除的RESTFUL格式api：

查询： http://localhost:8080/lsmdb/{key}

添加： http://localhost:8080/lsmdb/{key}
{"key":"211213","value":"aaaaaaaa"}

删除： DELETE http://localhost:8080/lsmdb/{key}

目前存在的问题

目前此版本的实现还有多处都有问题，也是后续版本需改进的地方：
1、此处的索引文件为全量索引，为每个key都记录相应的数据，此处的索引文件大小是非常大的，对性能影响很大；
2、此版本没有实现WAL功能程序崩溃时数据丢失；
3、此版本并没有后台执行SSTable合并功能，没有对修改、删除操作做任何处理，只是在查询时做了相应的忽略操作，影响性能；
4、单机版本不是分布式程序

文章首发地址：https://mp.weixin.qq.com/s/HoRjSMYumG4A40kHn5UKvQ

码农公寓