基於 go 實現 lsm tree 之主幹框架

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 流程（待完成）

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/KpkiBQNycLoDskUr00WeEg