前篇文章对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
Original: https://www.cnblogs.com/softlin/p/15705367.html
Author: AiFly
Title: 基于LSM的Key-Value数据库实现初篇
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/622162/
转载文章受原作者版权保护。转载请注明原作者出处！