lsmdb

基于Wisckey论文的LSM数据存储引擎

heap包

heap的实现使用到了小根堆，下面先对堆做个简单说明

1. 堆的概念

• 堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值
• 最大堆和最小堆是二叉堆的两种形式
• 最大堆：根结点的键值是所有堆结点键值中最大者
• 最小堆：根结点的键值是所有堆结点键值中最小者

2. heap

• heap包提供了对任意类型（实现了heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树
• 树的最小元素为其根元素，索引0的位置
• heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目

a(-1) b(-2) c(-3) c的权重最大 c的权重值最小

成员函数

Init

func Init(h Interface) 一个堆在使用任何堆操作之前应先初始化。接受参数为实现了heap.Interface接口的对象。

Fix

func Fix(h Interface, i int) 在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。

Push&Pop

Push和Pop是一对标准堆操作，Push向堆添加一个新元素，Pop弹出并返回堆顶元素，而在push和pop操作不会破坏堆的结构

Remove

删除堆中的第i个元素，并保持堆的约束性

工业级实现badger

• DB 初始化
• 读写事务
• 只读事务
• 范围查询
• GC
• LSM日志合并

DB 初始化

1. 构造配置参数对象
2. 打开或创建工作目录并上锁
3. 打开或创建ManifestFile文件
4. 创建DB对象
   1. 创建内存表列表,用于预写日志
   2. 创建通知刷新任务的channel
   3. 创建写入任务的channel
   4. 配置对象
   5. manifest文件对象
   6. 目录锁
   7. value目录锁
   8. 创建oracle对象，用于并发事务的控制
5. 创建一个块缓存
6. 创建一个索引缓存
7. 开启key注册器
8. 打开memtable 并全部追加到 imm 的列表中
   1. 创建一个内存跳表对象
   2. 封装.mem文件为一个logFile对象取名为wal
   3. 打开 .mem结尾的文件并关联为mmap文件
9. 创建一个激活的内存表
10. 创建一个level管理器
    1. 创建一个tables的二维数组
    2. 初始化每一个.sst结尾的文件关联为一个mmap文件
    3. 根据manfist里的记录，初始化每一层的table对象
    4. 如果是L0层则按fid排序，否则按每个表中最小key进行排序
11. vlog初始化
12. 打开一个DISCARD的文件并关联为mmap文件
13. 启动日志合并过程
14. 获取DB的事务最大版本号
    1. 打开vlog文件, 关联mmap
    2. 按fid排序处理vlog文件
    3. 读取目录填充vlog file 的map
    4. 如果没有vlog 文件则创建一个新的
    5. 如果vlog文件是空的则删除
    6. 获取vlog文件的实际大小并截断文件
    7. 创建一个新的活跃的vlog文件
15. 开启负责处理写请求的工作协程
16. 启动vlog文件的GC过程

读写事务

只读事务

范围查询

GC

LSM日志合并