0 导读
去年4月的时候，我和大家分享了一篇文章——初探 rocksDB 之 lsm tree，和大家一起探讨了 lsm tree 结构的底层实现原理. 秉着 【基于源码支撑原理】 的一贯原则，从本期开始，咱们把源码篇的坑填上.
接下来我将开启一个新的专题——基于 go 语言从零到一实现 lsm tree，本专题共分为下述四篇内容：
• 基于go实现lsm tree 之主干框架（本篇）
• 基于go实现lsm tree之memtable结构
• 基于go实现lsm tree之sstable结构
• 基于go实现lsm tree之level sorted merge流程
关于以上内容的源码均已上传到我的个人开源项目中，大家根据需要自取，如果代码写得觉得还凑合，可以留个 star，不胜感激.
开源项目 golsm 传送门 >> https://github.com/xiaoxuxiansheng/golsm
1 lsm tree 概念
1.1 应用场景
存储组件根据读写频次的不同，可以被分为适用于读多写少场景的读密集型和写多读少场景的写密集型两大类.
lsm tree 属于后者，在是实现上通过磁盘顺序写取代随机写的方式，保证了写操作的性能和稳定性；同时其又通过文件分层以及各层次间的排序归并操作，保证了内容的有序性，进一步能够兼顾保证不俗的读性能.
在实际的工程应用上，比较知名的 TiDB、RocksDB、LevelDB 均是由 lsm tree 完成存储结构的组织，因此都能很好地胜任写密集型的应用场景.
1.2 架构概览
下面我们简单串一下 lsm tree 的整体架构，有关这部分内容更详尽的细节，大家可以参见我之前发表的原理篇内容——初探 rocksDB 之 lsm tree.
lsm tree 全称 Log Structure Merge Tree，核心知识点包括：
• 磁盘+内存：在存储上主要依赖于磁盘文件 sstable（sorted string table） 进行数据持久存储；使用内存中有序表（memtable）作为数据的写入口，保证写性能及数据的局部有序
• memtable：内存有序表，分为读写表 active memtable，和只读表 read-only memtable. active memtable 是唯一的写入口，当其容量达到阈值，会切换为 read only 模式，进入溢写磁盘流程，同时会创建出一个新的 active memtable 作为新的写入口
• wal：write-ahead log，落于磁盘的预写日志. 为了避免易失性存储的 memtable 数据出现丢失，数据在写入前需要事先在 wal 中留痕. 当 memtable 成功溢写到磁盘成为 sstable 文件时，对应的 wal 文件即可清除
• level: 磁盘文件分为0~k层，表层为更晚的热数据，底层为更早的冷数据；层数越深，磁盘文件容量越大；每层由多个存储数据的磁盘文件构成；
• level0：level0层是特殊的，其中的磁盘文件由 read-only memtable 溢写生成. 由于 memtable 本身是有序表，能保证每个磁盘文件内局部有序. 但不同文件间的数据是重叠无序的；
• level1~levelk：当一层磁盘文件容量达到阈值，会对本层和下层涉及到的文件进行排序归并，最终生成新的文件插入下层. 因此 level1~levelk 的文件是全局有序且无重复的
• sstable：sorted string table. 每个存储数据的磁盘文件称为 sstable. 其中以 block 为单位进行数据分组拆分并建立索引辅助提升检索效率. 针对每个 block 建立布隆过滤器，辅助进行数据存在性校验
• 写流程：很简单，写入 active memtable 即可
• 读流程：需要花费常数次磁盘 IO. 遵循数据新旧流向，依次读 active memtable、read-only memtable、自尾向首遍历 level0 层每个 sstable 文件（文件间有重复且越晚写入越新）、自上而下遍历 level1~levelk 每层至多一个 sstable 文件（越上层数据越新、每层文件全局有序且无重复）. 在这个流程中，严格遵循先后顺序，但凡某一步取得结果则结束流程返回结果.
下面展示一下 lsm tree 整体架构示意图.
至此，我们简单总结了有关 lsm tree 的原理内容. 从下章开始将展开介绍我的个人项目 golsm 中，有关如何基于 go 语言从零到一实现 lsm tree 的技术细节.
2 核心数据结构
下面正式进入到喜闻乐见的手撕源码环节，首先是关于 golsm 中几类核心数据结构的介绍.
2.1 Conf
Conf 类聚合了有关于 lsm tree 运行所需的所有配置项，各项配置参数可以通过 option 模式进行灵活注入，对应的参数含义展示如下：
type Config struct {
Dir string // sst 文件存放的目录
MaxLevel int // lsm tree 总共多少层
// sst 相关
SSTSize uint64 // 每个 sst table 大小，默认 4M
SSTNumPerLevel int // 每层多少个 sstable，默认 10 个
SSTDataBlockSize int // sst table 中 block 大小 默认 16KB
SSTFooterSize int // sst table 中 footer 部分大小. 固定为 32B
Filter filter.Filter // 过滤器. 默认使用布隆过滤器
MemTableConstructor memtable.MemTableConstructor // memtable 构造器，默认为跳表
}
2.2 Tree
Tree 类对应的就是 lsm tree 的宏观结构：
• memTable：为支持读写操作的内存有序表. 数据是全局最新的
• rOnlyMemTable：一系列待溢写成 sst 文件的只读 memtable. 因为数据插入时使用的 append 操作，所以 index 越大，数据越新
• walWriter：wal 预写日志的写入口，与每个 memtable 一一对应
• nodes：采用二维切片表示 lsm tree 多层级多节点的拓扑结构，每个节点对应为树中的一个 sst 文件. 第一维为层数，第二维为 sst 文件在某一层中的索引
• memCompactC：compact 协程用于接收只读 memtable 的通道，收到后会进行溢写磁盘操作
• levelCompactC：compact 协程用于接收驱动 level sorted merge 操作信号的通道
• levelToSeq：每个 level 层新生成 sst 文件的序号，各 level 层内单调递增
其中完整各项成员属性含义如下：
type Tree struct {
conf *Config
// 读写数据时使用的锁
dataLock sync.RWMutex
// 每层 node 节点使用的读写锁
levelLocks []sync.RWMutex
// 读写 memtable
memTable memtable.MemTable
// 只读 memtable
rOnlyMemTable []*memTableCompactItem
// 预写日志写入口
walWriter *wal.WALWriter
// lsm树状数据结构
nodes [][]*Node
// memtable 达到阈值时，通过该 chan 传递信号，进行溢写工作
memCompactC chan *memTableCompactItem
// 某层 sst 文件大小达到阈值时，通过该 chan 传递信号，进行溢写工作
levelCompactC chan int
// lsm tree 停止时通过该 chan 传递信号
stopc chan struct{}
// memtable index，需要与 wal 文件一一对应
memTableIndex int
// 各层 sstable 文件 seq. sstable 文件命名为 level_seq.sst
levelToSeq []atomic.Int32
}
2.3 Node
Node 类对应为 lsm tree 中的一个 sstable 文件，核心字段包括：
• level：该节点在 lsm tree 中的 level 层数
• seq：该节点对应的 seq 号，注意这不代表其在 nodes[level] 的索引位置（除了 level0 层外，其余层 node 索引是依据数据 key 的大小决定的），只是文件名的后缀，根据生成先后顺序是单调递增的
• size：该节点对应 sstable 文件的大小，单位 byte
• blockToFilter：该节点对应 sstable 文件的每个 block 块对应的过滤器 bitmap. 用于辅助快速判断一个 key 是否存在于某个 block 中，以期能减少磁盘 io 操作
• index：该节点对应 sstable 文件的每个 block 块的索引，用于在 sstable 中快速检索 key 可能存在的 block
• startKey、endKey：该节点对应 sstable 文件中最小的 key 和最大的 key
• sstReader：该节点对应 sstable 文件的 reader 读取器入口
type Node struct {
conf *Config // 配置文件
file string // sstable 对应的文件名，不含目录路径
level int // sstable 所在 level 层级
seq int32 // sstable 的 seq 序列号. 对应为文件名中的 level_seq.sst 中的 seq
size uint64 // sstable 的大小，单位 byte
blockToFilter map[uint64][]byte // 各 block 对应的 filter bitmap
index []*Index // 各 block 对应的索引
startKey []byte // sstable 中最小的 key
endKey []byte // sstable 中最大的 key
sstReader *SSTReader // 读取 sst 文件的 reader 入口
}
2.4 Block
有关 block 的内容我们在此仅作简要概括. 本系列第三篇【基于go实现lsm tree之sstable结构】中，会再作详细展开.
每个 sstable 文件均以数据块 block 的形式进行数据分组. 后续无论是索引 index 还是过滤器 filter，都是与 block 对应存在的.
type Block struct {
conf *Config
buffer [30]byte // 进行数据转移时使用的临时缓冲区
record *bytes.Buffer // 记录全量数据的缓冲区
entriesCnt int // kv 对数量
prevKey []byte // 最晚一笔写入的数据的 key
}
2.5 SSTable
有关 sstable 的内容仅作简要概括. 本系列第三篇 【基于go实现lsm tree之sstable结构】中，再作详细展开.
sstWriter 对应为一个 sstable 文件的写入口，核心属性包括：
• dest：对应为 sstable 文件
• dataBuf：缓存整个 sstable 文件的所有 kv 数据，最终一次性落到 sst 文件
• filterBuf：缓存整个 sstable 文件的过滤器数据，最终一次性落到 sst 文件
• indexBuf：缓存整个 sstable 文件的索引数据，最终一次性落到 sst 文件
• blockToFilter：基于内存 map 形式，记录 block 到 filter bitmap 的映射关系
• dataBlock：kv 对数据会以 block 的形式依次添加到 dataBuf 中. 一个 sst 文件会对应有多个 dataBlock，每当一个 dataBlock 记录满后会切换使用新的 dataBlock
• fitlerBlock：filter 的数据最终也是以 block 的形式添加到 filterBuf 中. 一个 sst 文件对应只有一个 filterBlock
• index：index 的数据最终也是以 block 的形式添加到 indexBuf 中. 一个 sst 文件对应只有一个 indexBlock
• assistScratch：用于转移数据使用的临时缓冲区
• prevKey：最晚写入的一笔 key
• prevBlockOffset：前一个 dataBlock 起始位置的 offset
• prevBlockSize：前一个 dataBlock 的大小，单位 byte
// 对应于 lsm tree 中的一个 sstable. 这是写入流程的视角
type SSTWriter struct {
conf *Config // 配置文件
dest *os.File // sstable 对应的磁盘文件
dataBuf *bytes.Buffer // 数据块缓冲区 key -> val
filterBuf *bytes.Buffer // 过滤器块缓冲区 prev block offset -> filter bit map
indexBuf *bytes.Buffer // 索引块缓冲区 index key -> prev block offset, prev block size
blockToFilter map[uint64][]byte // prev block offset -> filter bit map
index []*Index // index key -> prev block offset, prev block size
dataBlock *Block // 数据块
filterBlock *Block // 过滤器块
indexBlock *Block // 索引块
assistScratch [20]byte // 用于在写索引块时临时使用的辅助缓冲区
prevKey []byte // 前一笔数据的 key
prevBlockOffset uint64 // 前一个数据块的起始偏移位置
prevBlockSize uint64 // 前一个数据块的大小
}
sstReader 对应为一个 sstable 文件的读取器：
• src：对应为 sstable 磁盘文件
• reader：src 的读取器封装
• filterOffset：filterBlock 起始位置在 sst 文件的 offset
• filterSize：filterBlock 的大小，单位 byte
• indexOffset：indexBlock 起始位置在 sst 文件的 offset
• indexSize：indexBlock 的大小，单位 byte
// 对应于 lsm tree 中的一个 sstable. 这是读取流程的视角
type SSTReader struct {
conf *Config // 配置文件
src *os.File // 对应的文件
reader *bufio.Reader // 读取文件的 reader
filterOffset uint64 // 过滤器块起始位置在 sstable 的 offset
filterSize uint64 // 过滤器块的大小，单位 byte
indexOffset uint64 // 索引块起始位置在 sstable 的 offset
indexSize uint64 // 索引块的大小，单位 byte
}
2.6 Index
有关 index 的内容仅作简要概括. 本系列第三篇 【基于go实现lsm tree之sstable结构】中，再作详细展开.
索引 index 是在逻辑意义上是插入在 sst 文件各个 dataBlock 之间的记录桩点:
• key：需要保证大于等于前一个 dataBlock 中的最大 key，小于后一个 dataBlock 中的最小 key
• PrevBlockOffset：对应为前一个 dataBlock 起始位置在 sstable 文件的 offset
• PrevBlockSize：对应为前一个 dataBlock 的大小，单位 byte
// sstable 中用于快速检索 block 的索引
type Index struct {
Key []byte // 索引的 key. 保证其 >= 前一个 block 最大 key； < 后一个 block 的最小 key
PrevBlockOffset uint64 // 索引前一个 block 起始位置在 sstable 中对应的 offset
PrevBlockSize uint64 // 索引前一个 block 的大小，单位 byte
}
2.7 MemTable
有关 MemTable 的内容我们在此简要概括. 本系列第二篇 【基于go实现lsm tree之memtable结构】中，再作详细展开.
MemTable 是 lsm tree 中使用的内存有序表，此处声明为一个 interface，使用方可以根据需要实现具体的版本进行注入，默认会使用 golsm 项目下实现的跳表结构.
// memtable 构造器
type MemTableConstructor func() MemTable
// 有序表 interface
type MemTable interface {
Put(key, value []byte) // 写入数据
Get(key []byte) ([]byte, bool) // 读取数据，第二个 bool flag 标识数据是否存在
All() []*KV // 返回所有的 kv 对数据
Size() int // 有序表内数据大小，单位 byte
EntriesCnt() int // kv 对数量
}
2.8 Filter
有关 filter 的内容仅作简要概括. 本系列第三篇 【基于go实现lsm tree之sstable结构】中再作详细展开.
Filter 为 sstable 文件中针对每个 block 使用的过滤器，用于辅助快速判断一个 key 是否可能存在于某个 block 块中.
此处将 filter 声明为一个 interface，使用方可以根据需要实现具体的版本进行注入，默认使用 golsm 项目下实现的布隆过滤器.
// 过滤器. 用于辅助 sstable 快速判定一个 key 是否存在于某个 block 中
type Filter interface {
Add(key []byte) // 添加 key 到过滤器
Exist(bitmap, key []byte) bool // 是否存在 key
Hash() []byte // 生成过滤器对应的 bitmap
Reset() // 重置过滤器
KeyLen() int // 存在多少个 key
}
3 启动流程
接下来我们启动一棵 lsm tree 的主流程.
3.1 构造配置
在启动 lsm tree 之前，需要完成各个配置项的设置，此处采用的是 option 模式，实现配置项的灵活注入，同时通过 repair 方法保证一些核心参数在缺失的情况下，能有一个合适的属性值进行兜底.
// 配置文件构造器.
func NewConfig(dir string, opts ...ConfigOption) (*Config, error) {
c := Config{
Dir: dir, // sstable 文件所在的目录路径
SSTFooterSize: 32, // 对应 4 个 uint64，共 32 byte
}
// 加载配置项
for _, opt := range opts {
opt(&c)
}
// 兜底修复
repaire(&c)
return &c, c.check() // 校验一下配置是否合法，主要是 check 存放 sst 文件和 wal 文件的目录，如果有缺失则进行目录创建
}
构造配置文件时，还需要对使用到的目录进行校验，包括用于存放一系列 sst 文件的 conf.Dir 以及存放 wal 文件的 {conf.Dir}/walfile，如果对应目录不存在，则需要提前完成目录的创建.
// 校验一下配置是否合法，主要是 check 存放 sst 文件和 wal 文件的目录，如果有缺失则进行目录创建
func (c *Config) check() error {
// sstable 文件目录确保存在
if _, err := os.ReadDir(c.Dir); err != nil {
_, ok := err.(*fs.PathError)
if !ok || !strings.HasSuffix(err.Error(), "no such file or directory") {
return err
}
if err = os.Mkdir(c.Dir, os.ModePerm); err != nil {
return err
}
}
// wal 文件目录确保存在
walDir := path.Join(c.Dir, "walfile")
if _, err := os.ReadDir(walDir); err != nil {
_, ok := err.(*fs.PathError)
if !ok || !strings.HasSuffix(err.Error(), "no such file or directory") {
return err
}
if err = os.Mkdir(walDir, os.ModePerm); err != nil {
return err
}
}
return nil
}
此处涉及到的完整配置参数展示如下：
// 配置项
type ConfigOption func(*Config)
// lsm tree 最大层数. 默认为 7 层.
func WithMaxLevel(maxLevel int) ConfigOption {
return func(c *Config) {
c.MaxLevel = maxLevel
}
}
// level0层每个 sstable 文件的大小，单位 byte. 默认为 1 MB.
// 且每加深一层，sstable 文件大小限制阈值放大 10 倍.
func WithSSTSize(sstSize uint64) ConfigOption {
return func(c *Config) {
c.SSTSize = sstSize
}
}
// sstable 中每个 block 块的大小限制. 默认为 16KB.
func WithSSTDataBlockSize(sstDataBlockSize int) ConfigOption {
return func(c *Config) {
c.SSTDataBlockSize = sstDataBlockSize
}
}
// 每个 level 层预期最多存放的 sstable 文件个数. 默认为 10 个.
func WithSSTNumPerLevel(sstNumPerLevel int) ConfigOption {
return func(c *Config) {
c.SSTNumPerLevel = sstNumPerLevel
}
}
// 注入过滤器的具体实现. 默认使用本项目下实现的布隆过滤器 bloom filter.
func WithFilter(filter filter.Filter) ConfigOption {
return func(c *Config) {
c.Filter = filter
}
}
// 注入有序表构造器. 默认使用本项目下实现的跳表 skiplist.
func WithMemtableConstructor(memtableConstructor memtable.MemTableConstructor) ConfigOption {
return func(c *Config) {
c.MemTableConstructor = memtableConstructor
}
}
各项配置参数如果出现缺省，则会使用默认值进行兜底：
func repaire(c *Config) {
// lsm tree 默认为 7 层.
if c.MaxLevel <= 1 {
c.MaxLevel = 7
}
// level0 层每个 sstable 文件默认大小限制为 1MB.
// 且每加深一层，sstable 文件大小限制阈值放大 10 倍.
if c.SSTSize <= 0 {
c.SSTSize = 1024 * 1024
}
// sstable 中每个 block 块的大小限制. 默认为 16KB.
if c.SSTDataBlockSize <= 0 {
c.SSTDataBlockSize = 16 * 1024 // 16KB
}
// 每个 level 层预期最多存放的 sstable 文件个数. 默认为 10 个.
if c.SSTNumPerLevel <= 0 {
c.SSTNumPerLevel = 10
}
// 注入过滤器的具体实现. 默认使用本项目下实现的布隆过滤器 bloom filter.
if c.Filter == nil {
c.Filter, _ = filter.NewBloomFilter(1024)
}
// 注入有序表构造器. 默认使用本项目下实现的跳表 skiplist.
if c.MemTableConstructor == nil {
c.MemTableConstructor = memtable.NewSkiplist
}
}
3.2 启动lsm tree
下面梳理启动一棵 lsm tree 实例的流程，以构造器方法 NewTree 作为入口，核心步骤包括：
• 构造 lsm tree 实例
• 执行 constructTree 方法，读取 conf.Dir 下已存在的 sst 文件，在内存中还原出 lsm tree 的拓扑结构：nodes
• 异步启动 compact 协程，由于持续接收指令，执行 memtable 的溢写落盘操作或者 sstable 的 level sorted merge 操作
• 执行 constructMemtable 方法，读取 {conf.Dir}/walfile 目录下的 wal 文件，在内存中还原出一系列只读 memtable 和读写 memtable
// 构建出一棵 lsm tree
func NewTree(conf *Config) (*Tree, error) {
// 1 构造 lsm tree 实例
t := Tree{
conf: conf,
memCompactC: make(chan *memTableCompactItem),
levelCompactC: make(chan int),
stopc: make(chan struct{}),
levelToSeq: make([]atomic.Int32, conf.MaxLevel),
nodes: make([][]*Node, conf.MaxLevel),
levelLocks: make([]sync.RWMutex, conf.MaxLevel),
}
// 2 读取 sst 文件，还原出整棵树
if err := t.constructTree(); err != nil {
return nil, err
}
// 3 运行 lsm tree 压缩调整协程
go t.compact()
// 4 读取 wal 还原出 memtable
if err := t.constructMemtable(); err != nil {
return nil, err
}
// 5 返回 lsm tree 实例
return &t, nil
}
constructTree 方法用于读取已有的 sst 文件，在内存中还原出一系列 lsm node 节点
// 读取 sst 文件，还原出整棵树
func (t *Tree) constructTree() error {
// 读取 sst 文件目录下的 sst 文件列表
sstEntries, err := t.getSortedSSTEntries()
if err != nil {
return err
}
// 遍历每个 sst 文件，将其加载为 node 添加 lsm tree 的 nodes 内存切片中
for _, sstEntry := range sstEntries {
if err = t.loadNode(sstEntry); err != nil {
return err
}
}
return nil
}
constructMemTable 方法用于读取已有 wal 文件，在内存中还原出一系列只读 memtable 和读写 memtable
// 读取 wal 还原出 memtable
func (t *Tree) constructMemtable() error {
// 1 读 wal 目录，获取所有的 wal 文件
wals, _ := os.ReadDir(path.Join(t.conf.Dir, "walfile"))
// 2 倘若 wal 目录不存在或者 wal 文件不存在，则构造一个新的 memtable
if len(wals) == 0 {
t.newMemTable()
return nil
}
// 3 依次还原 memtable. 最晚一个 memtable 作为读写 memtable
// 前置 memtable 作为只读 memtable，分别添加到内存 slice 和 channel 中.
return t.restoreMemTable(wals)
}
3.3 compact协程
compact 协程是异步持续运行的，通过 for + select 实现一个自旋多路复用的模型，持续监听 chan，处理 memtable 的溢写流程以及某个 level 层 sstable 的 compact 流程.
// 运行 compact 协程.
func (t *Tree) compact() {
for {
select {
// 接收到 lsm tree 终止信号，退出协程.
case <-t.stopc:
// log
return
// 接收到 read-only memtable，需要将其溢写到磁盘成为 level0 层 sstable 文件.
case memCompactItem := <-t.memCompactC:
t.compactMemTable(memCompactItem)
// 接收到 level 层 compact 指令，需要执行 level~level+1 之间的 level sorted merge 流程.
case level := <-t.levelCompactC:
t.compactLevel(level)
}
}
}
4 读写流程
下面梳理一下通过 lsm tree 实现读写操作的主流程.
4.1 写流程
写流程是比较简单的，以 Put 方法作为入口：
• 将 kv 对数据写入预写日志中，防止 memtable 丢失数据
• 将 kv 对数据写入读写 memtable
// 写入一组 kv 对到 lsm tree. 会直接写入到读写 memtable 中.
func (t *Tree) Put(key, value []byte) error {
// 1 加写锁
t.dataLock.Lock()
defer t.dataLock.Unlock()
// 2 数据预写入预写日志中，防止因宕机引起 memtable 数据丢失.
if err := t.walWriter.Write(key, value); err != nil {
return err
}
// 3 数据写入读写跳表
t.memTable.Put(key, value)
// 4 倘若读写跳表的大小未达到 level0 层 sstable 的大小阈值，则直接返回.
// 考虑到溢写成 sstable 后，需要有一些辅助的元数据，预估容量放大为 5/4 倍
if uint64(t.memTable.Size()*5/4) <= t.conf.SSTSize {
return nil
}
// 5 倘若读写跳表数据量达到上限，则需要切换跳表
t.refreshMemTableLocked()
return nil
}
值得一提的是，在写流程结束前，需要校验一下读写 memtable 中的数据量大小是否达到溢写落盘的阈值，是的话，需要通过 refreshMemTableLocked 方法完成 memtable 的模式切换：
• 将 memtable 由读写模式切换为只读模式，然后通过 memCompactC 通道将其传递给 compact 协程进行溢写处理
• 构建一个新的 memtable 用于处理写请求，并构造与之相应的 wal 文件
// 切换读写跳表为只读跳表，并构建新的读写跳表
func (t *Tree) refreshMemTableLocked() {
// 辞旧
// 将读写跳表切换为只读跳表，追加到 slice 中，并通过 chan 发送给 compact 协程，由其负责进行溢写成为 level0 层 sst 文件的操作.
oldItem := memTableCompactItem{
walFile: t.walFile(),
memTable: t.memTable,
}
t.rOnlyMemTable = append(t.rOnlyMemTable, &oldItem)
t.walWriter.Close()
go func() {
t.memCompactC <- &oldItem
}()
// 迎新
// 构造一个新的读写 memtable，并构造与之相应的 wal 文件.
t.memTableIndex++
t.newMemTable()
}
4.2 读流程
lsm 的读流程分为一系列步骤，需要严格按照顺序执行：
• 读取读写 memtable，如果读到数据，直接返回
• 倒序遍历读取只读 memtable，如果读到数据，直接返回
• 倒序遍历读取 level0 层的每个 sstable 文件，如果读到数据，直接返回
• 在 level1~levelk 之间由浅到深逐层检索 key，如果读到数据，直接返回
• 走完全流程仍未找到 kv 对，则返回 key 不存在
// 根据 key 读取数据.
func (t *Tree) Get(key []byte) ([]byte, bool, error) {
t.dataLock.RLock()
// 1 首先读 active memtable.
value, ok := t.memTable.Get(key)
if ok {
t.dataLock.RUnlock()
return value, true, nil
}
// 2 读 readOnly memtable
for i := len(t.rOnlyMemTable) - 1; i >= 0; i-- {
value, ok = t.rOnlyMemTable[i].memTable.Get(key)
if ok {
t.dataLock.RUnlock()
return value, true, nil
}
}
t.dataLock.RUnlock()
// 3 读 sstable level0 层.
var err error
t.levelLocks[0].RLock()
for i := len(t.nodes[0]) - 1; i >= 0; i-- {
if value, ok, err = t.nodes[0][i].Get(key); err != nil {
t.levelLocks[0].RUnlock()
return nil, false, err
}
if ok {
t.levelLocks[0].RUnlock()
return value, true, nil
}
}
t.levelLocks[0].RUnlock()
// 4 依次读 sstable level 1 ~ i 层.
for level := 1; level < len(t.nodes); level++ {
t.levelLocks[level].RLock()
node, ok := t.levelBinarySearch(level, key, 0, len(t.nodes[level])-1)
if !ok {
t.levelLocks[level].RUnlock()
continue
}
if value, ok, err = node.Get(key); err != nil {
t.levelLocks[level].RUnlock()
return nil, false, err
}
if ok {
t.levelLocks[level].RUnlock()
return value, true, nil
}
t.levelLocks[level].RUnlock()
}
// 5 至此都没有读到数据，则返回 key 不存在.
return nil, false, nil
}
5 小结
本期作为整个 【基于go实现lsm tree】专题的开篇之作，和大家简单回顾了 lsm tree 的底层原理，并和大家一起走进了我的开源项目 golsm 当中，梳理了实现 lsm tree 的大体框架.
在此展望未来几周继续和大家展开讨论的内容：
• 基于go实现lsm tree 之主干框架（本篇）
• 基于go实现lsm tree之memtable结构（待完成）
• 基于go实现lsm tree之sstable结构（待完成）
• 基于go实现lsm tree之level sorted merge流程（待完成）
