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

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

  前篇文章对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文件结构:

image.png

SSTable索引文件结构:

image.png

具体实现

加载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}

image.png

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

image.png

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

目前存在的问题

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

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