基于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文件结构:
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