etcd 存儲引擎之存儲設計

0 前言

本期我們繼續延續 etcd 存儲引擎系列的話題. 在該系列中，我們以 boltdb 作爲 b + 樹工程化落地的學習案例，該項目開源地址爲：https://github.com/etcd-io/bbolt，go 語言純度接近 100%. （本系列涉及走讀的 boltdb 源碼版本爲 v1.3.8）

下面是本專題的分享節奏，本文是其中的第二篇——存儲設計篇：

• etcd 存儲引擎之主幹框架（已完成）：偏宏觀視角下介紹 boltdb 的定位、架構、特性，通過幾個核心流程淺探 boltdb 實現源碼
• etcd 存儲引擎之存儲設計（本篇）：介紹 boltdb 存儲模型、機制的設計實現，包含磁盤、內存兩部分
• etcd 存儲引擎之 b + 樹實現（待填坑）：介紹 b+ 樹理論模型及 boltdb 實現案例，包括模型定義及 crud 流程梳理
• etcd 存儲引擎之事務實現（待填坑）：介紹 boltdb 事務的執行模式及實現原理

1 整體架構

1.1 宏觀模型

藉助上面這張存儲架構圖，我們總結一下 boltdb 的宏觀存儲模型設計：

• 單文件存儲：基於本地單個磁盤文件進行數據持久存儲，存儲數據均爲 kv 形式
• mmap：基於 mmap（memory-mapping file）技術，將 db 文件內容映射到內存指定區域（我們稱之爲 page buffer），於讀流程中屏蔽磁盤 io 細節
• pwrite+fdatasync：基於 file writeAt + fdatasync 技術，支持於文件指定 offset 寫入數據，並保證同步等待設備 io 結果
• 存儲分 page：借鑑局部性原理，以 page 作爲存儲交換的最小單位，向操作系統看齊
• page 分類：page 分爲 meta、freelist、branch 和 leaf 四類，前兩者偏向全局維度的元信息記錄；後兩者與實際數據存儲相關
• b+ tree：數據存儲採用 b+ 樹模型. branch page 和 leaf page 分別對應 b+ 樹的枝幹和葉子節點. 其在需要修改時，會基於懶加載機制在內存中反序列化爲 node 實例模型
• copy-on-write： 採取以空間換時間策略，全程基於寫時複製技術，實現髒數據副本拷貝處理，直到落盤完成纔對原數據進行覆蓋，以此保證數據安全性
• bucket：定位爲相互隔離的數據組，可以簡單類比於表. 每個 bucket 對應一棵獨立 b+ 樹，bucket 之間也通過 b+ 樹模型建立父子層級拓撲關係

（這些概念內容已在前文——etcd 存儲引擎之主幹框架中完成一輪鋪墊. 大家如果看完覺得恍惚，可以在完成本文後續章節學習後再回顧一遍，溫故而知新. ）

1.2 研究路線

下面介紹一下本文的學習路線：

• 第二章——page：包含 page 核心概念，源碼定義、正反序列化流程、四類 page 實現細節等；
• 第三章——緩存 & 持久化：介紹讀、寫流程採用的 mmap、pwrite+fdatasync 的原理，並結合幾個主流程向大家揭示 boltdb 如何採用 copy-on-write 機制
• 第四章——b+ tree：介紹內存中基於懶加載機制反序列化的 b+ 樹模塊. （有關 b+ 樹的內容，本篇只是點到爲止. 這部分會在下一篇——etcd 存儲引擎之 b + 樹實現中，以更聚焦的視角和大家一起展開進一步探討）
• 第五章——bucket：介紹有關 bucket 的概念及具體的源碼實現

2 page

2.1 概念

基於局部性原理，也爲了契合操作系統存儲交換模型，boltdb 內的數據也是也 page 爲單位組織的.

每個 page 分爲 header 和 body 兩部分：

• header：格式統一，記錄 page 的元信息，如頁號、數據量、類型等
• body：格式與頁類型有關，記錄 page 中的具體內容，共分爲 meta、freelist、branch、leaf 四類：
• meta page：存儲 boltdb 的元數據，如版本號、全局遞增的事務 id 記錄
• freelist page：存儲空閒 page 信息， (定位可類比於 go 語言中的 heap）
• branch element page：存儲數據索引， 邏輯意義上屬於 b + 樹中的枝幹節點
• leaf element page：存儲 kv 數據， 邏輯意義上屬於 b + 樹中的葉子節點

每當 boltdb 實例在初始化時，需要率先完成 4 個 page 的初始化和持久化：

• meta page * 2： 記錄好數據庫的元信息；meta page 數量是兩個，和 boltdb 採用的 copy-on-write 機制有關（本文 3.3 小節詳細展開）
• freelist： 全局維度的空閒 page 管理模塊
• leaf element page： 作爲一棵空白 b+ 樹的根節點，由於沒有數據，因此會屬於葉子節點

2.2 header

前面提到 page 由 header 和 body 兩部分組成. 下面我們首先來看一下各類 page 通用的 header 結構的詳細定義.

page header 核心屬性包括：

• id： page 的全局 id
• flags： page 類型，分爲 meta、freelist、branch、leaf 四類
• count： page 中數據量. 針對 freelist 爲空閒頁數量；針對 branch、leaf 爲 key 數量；meta 不使用此字段
• overflow： 溢出頁數量. 存在過大的數據條目時，會找到地址連續的多個 page body 拼接成一個邏輯意義上的 “big page” ，此時會通過 overflow 記錄溢出頁數量，body 總數則爲 overflow + 1，且共享同一個 header
• ptr： page body 起始位置

對應源碼如下，儘管命名爲 page，但大家需要知道其含義其實爲 page header：

// page header
type page struct {
    id       pgid    // page 的全局唯一 id. 藉由 page id 和 page size 可以推算出其在 boltdb 中的位置
    flags    uint16  // page 類型，包含：meta、freelist、branch、leaf 四類
    count    uint16  // page 中的數據條數. 針對 freelist，標識空閒頁數量；針對 branch 和 leaf，代表 key 的數量
    overflow uint32  // 溢出頁個數，倘若存在過大的數據，則需要使用到溢出頁. 溢出頁地址連續，共享相同的 page header
    ptr      uintptr // page body 的起始位置
}


type pgid uint64 // 頁 id


const (
    // 四種 page header flag
    branchPageFlag   = 0x01  // b+ 樹枝幹節點
    leafPageFlag     = 0x02  // b+ 樹葉子節點
    metaPageFlag     = 0x04  // meta 
    freelistPageFlag = 0x10  // freelist
)

2.3 meta

2.3.1 類定義

下面介紹的是 meta page 的 body.

meta 中主要記錄是 boltdb 的元數據，其核心屬性包括：

• magic： boltdb 定義的魔數. 用於校驗 db 的合法性
• version： boltdb 版本號
• pageSize： 每個 page 大小，通常和操作系統 page 大小保持一致
• root： 默認創建的始祖 bucket. 該 bucket 不直接存儲 kv 數據，其下 b+ 樹的 kv 標識的都是用戶創建的子 bucket（表）
• freelist： freelist page 的 id
• pgid：標識了已執行 mmap 映射的邊界，需要擴容時則需要推進 mmap 範圍，並遞增此字段
• txid： 標識下一個待分配的事務 id. 事務 id 是全局遞增的. 當有讀寫事務啓動時，會 copy 一份 meta 副本，並在其中遞增字段. 在獲取 meta 時，也會優先選用 txid 較大的那一例，因爲其數據實時性更高
• checksum： 校驗和，用於驗證數據合法性

具體代碼展示如下：

// meta 類型 page 的 page body
type meta struct {
    magic    uint32 // 魔數，與 bolt db 版本相關
    version  uint32 // bolt db 版本
    pageSize uint32 // 採用的頁大小，單位 byte
    flags    uint32 // 保留字段，暫未啓用
    root     bucket // 數據庫的始祖 bucket
    freelist pgid   //  freelist page 的 id
    pgid     pgid   // 下一個分配的 page id，mmap 擴容時使用
    txid     txid   // 下一個事務 id，遞增
    checksum uint64 // meta 頁校驗和
}

2.3.2 副本機制

在 boldtb 的 page buffer 中，index = 0 和 1 的兩個 page 一定是 2 個 meta page. 之所以要創建雙份，則和 boldtb 採用的 copy-on-write 策略相關：

• 前提：boltdb 中，全局同時只能存在一個讀寫事務
• step1：啓動讀寫事務： 從兩個 meta page 中獲取合法且 tx id 較大的那個 meta page，拷貝一份其副本到內存，並將對應 tx id 加 1
• step2：執行讀寫事務：執行數據更新，此時更新內容都會基於寫時複製策略，生成在一系列 page 副本中（成爲髒頁）
• step3：提交讀寫事務：一系列髒頁持久化落盤，成功後將讀寫事務手中持有的 meta page 副本也進行持久化，覆蓋回到 index = 0 或者 1 的其中一個 meta page（根據 tx id % 2 的規則映射）

至此，一次讀寫事務完成了，對應的 meta page 也實現了更新迭代.

值得一提的是：在 step3 中，倘若 meta page 在溢寫落盤過程中發生錯誤，則代表事務執行失敗，此時磁盤上的 meta page 內容可能也發生損壞，但是由於有雙份 meta page 兜底，因此 boltdb 還能基於另一份完好的 meta page 正常提供服務，數據也基於此會正常回溯到事務提交前的版本，這個點和 step1 中取 meta page 的策略形成了呼應.

（這個點大家第一次看大概率會覺得晦澀，沒關係，可以結合本文 3.3 小節的內容進行呼應）

下面是 db 類定義的代碼示例，可見其中確實持有雙份 meta page 的引用：

type DB struct {
    // ...
    meta0    *meta // 兩個輪換使用的 meta page 之一
    meta1    *meta // 兩個輪換使用的 meta page 之一
    // ...
}

下面是 boltdb 中 transaction 類的定義，其中持有的 meta 屬性正是在 step1 中拷貝生成的 meta 副本：

// 事務
type Tx struct {
    // ...
    db             *DB            // 事務從屬的 db 實例
    meta           *meta          // db meta page
    root           Bucket         // db 根 bucket
    pages          map[pgid]*page // 事務中反序列化過的 page
    // ...
}

2.3.3 序列化

接下來我們串一下 meta page 的正反序列化過程.

讀寫事務提交時，會需要將內存中 meta 副本轉成 page 實例，並最終進行溢寫落盤.

func (tx *Tx) Commit() error {
    // ...髒頁溢寫落盤
    // ...


    // 事務持有的 meta page 副本溢寫落盤
    if err := tx.writeMeta(); err != nil {
        tx.rollback()
        return err
    }
    // ...


    return nil
}

// writeMeta writes the meta to the disk.
func (tx *Tx) writeMeta() error {
    // 序列化 meta 副本
    tx.meta.write(p)


    // ... meta 落盤持久化


    return nil
}

meta 序列化方法爲 meta.write，核心步驟包括：

• 傳入 page 實例： page 實際是一個 page header 實例
• 設置 page id： id 根據 meta 中記錄的事務 id % 2 得到，因此結果必然爲 0 或者 1，呼應了 meta page 在 db file 中的位置
• 設置 page 類型：flag 取爲 metaPageFlag，對應爲 meta page 類型
• 設置校驗和：通過 sum64 算法生成 checksum
• 深拷貝 meta：本質上將 page header 的 ptr 指針指向 meta 在 page buffer 中的起始位置

// meta 內容寫入到 page
func (m *meta) write(p *page) {
    // 前置校驗 ...


    // meta page 的 id 只能是 0 或者 1. 根據 tx id 的單雙數可以得知
    p.id = pgid(m.txid % 2)
    // 標識 page 類型爲 meta
    p.flags |= metaPageFlag


    // 校驗和
    m.checksum = m.sum64()
    // 通過深拷貝方式，令 page ptr 指向 meta 副本的起始位置
    m.copy(p.meta())
}

2.3.4 反序列化

在 boltdb 每次執行 mmap 映射時（初始化或者擴容），都需要更新 db 實例持有的兩個 meta 引用，此時需要對 meta 進行反序列化：

// mmap
func (db *DB) mmap(minsz int) (err error) {
    // 1 加鎖 ...


    // 2 mmap 系統調用 ...


    // 3 更新 db 實例持有的 meta 引用實例
    db.meta0 = db.page(0).meta()
    db.meta1 = db.page(1).meta()


    // ...


    return nil
}

可以看到，獲取 meta 實例的方式是直接從 page buffer 取出 0 號和 1 號 page，並通過其 ptr 引用直接獲取到 meta body：

// 獲取 meta 類型的 page body
func (p *page) meta() *meta {
    return (*meta)(unsafe.Pointer(&p.ptr))
}

2.3.4 校驗

每當啓動事務時，需要從 2 個 meta page 中獲取合法且 tx id 較大的一個作爲拷貝的對象. 此時會涉及到對 meta page 的校驗：

// 初始化事務
func (tx *Tx) init(db *DB) {
    // ...
    // 1 創建 meta 副本
    tx.meta = &meta{}
    // 2 獲取合法且實時性更高的 meta 進行深拷貝
    db.meta().copy(tx.meta)


    // 3 設置 bucket


    // 4 讀寫事務需要遞增 meta 副本中的 tx id
    if tx.writable {
        tx.pages = make(map[pgid]*page)
        tx.meta.txid += txid(1)
    }
}

在 db.meta 方法中，會在優先獲取 tx id 更大的 meta 的同時，對 meta 合法性校驗，保證返回的 meta 內容是合法的：

// 從 db 中獲取合法且實時性更高的 meta
func (db *DB) meta() *meta {
    // 2 個輪換使用的 meta 實例
    metaA := db.meta0
    metaB := db.meta1
    // 優先取 tx id 較大的那個
    if db.meta1.txid > db.meta0.txid {
        metaA = db.meta1
        metaB = db.meta0
    }


    // 校驗 meta 合法性，保證返回的 meta 是合法的
    if err := metaA.validate(); err == nil {
        return metaA
    } else if err := metaB.validate(); err == nil {
        return metaB
    }


    // 兩個 meta 都有問題，panic
    panic("bolt.DB.meta(): invalid meta pages")
}

校驗 meta page 是否合法，包括對 magic、version 和 checksum 的校驗：（主要是 checksum）

// 校驗 meta page
func (m *meta) validate() error {
    if m.magic != magic {
        return ErrInvalid
    } else if m.version != version {
        return ErrVersionMismatch
    } else if m.checksum != 0 && m.checksum != m.sum64() {
        return ErrChecksum
    }
    return nil
}


// The data file format version.
const version = 2


// Represents a marker value to indicate that a file is a Bolt DB.
const magic uint32 = 0xED0CDAED

2.4 freelist

2.4.1 “只借不還”

在介紹 freelist 之前，需要先聊到 boltdb 中一個很重要的機制：boltdb 採取 mmap 操作時，只會擴容，不會縮容. 即便在讀寫事務中存在 page 的釋放，也只會將空閒的 page 緩存到 freelist 中統一管理，而不會將其歸還給操作系統，這樣設計的原因在於：

• 釋放的 page 可能位於 page buffer 內部而非尾端，倘若歸還操作系統，會打破 page buffer 的連續性
• 通過實踐經驗得知，在數據量達到某個閾值後，即便發生刪除操作導致某個時刻暫時低於閾值，最終往往也會再次超過該閾值

基於以上，freelist 應運而生，它用於存儲空閒 page 信息，定位類似於 go 語言中 heap，採取以空間換時間的策略，緩存並管理空閒的 page 以供後續複用，降低與操作系統的交互頻率.

2.4.2 類定義

freelist 的類定義如上所示，核心屬性包括：

• ids：可直接使用的已釋放 page 列表
• pending：等待被釋放的空閒 page 列表
• cache： ids + pending 的全集
• allocate：

對應代碼如下：

// 空閒頁 
type freelist struct {
    ids     []pgid          // 已經可用的釋放頁
    pending map[txid][]pgid // 等待被釋放的空閒頁. txid 爲仍在使用這些頁的最大 txid. 每當有事務被分配時，可以找到所有已經小於當前最小 txid 的 tx 使用的 pending page 進行批量釋放
    cache   map[pgid]bool   // 判斷某個頁是否是空閒的或者待釋放的
    allocate       func(txid txid, n int) pgid // 分配 page 的入口函數，有着不同的算法實現. n 爲要求的連續 page 數量.
}

如何理解上述提到的待釋放 pending 列表呢？

這部分內容和 boltdb 事務隔離性掛鉤，爲了保證事務的【可重複讀】語義，在一些讀寫事務中，哪怕已經歸還了某些 page，但只要這些 page 還在被一些版本更早的事務所 “閱讀”，那麼其內容就不能被覆蓋，需要保證閱讀視角的一致性.

（這裏算是做個簡單劇透，有關這部分內容，會在本系列第四篇——etcd 存儲引擎之事務實現中進一步展開介紹）

2.4.3 free page count

freelist 中的 ids 屬於 page body 部分，結合 page header 中的 count 字段，能夠推到得出 freelist 中的空閒 page 數量：

// page header
type page struct {
    // ...
    count    uint16  // page 中的數據條數. 針對 freelist，爲標識空閒頁數量；
    // ...
}

由於 count 字段爲 uint16，因此能表示的數值範圍有限，最大值即爲 0xFFFF，但在實踐場景中，free page 數可能大於該值，因此 freelist 在讀取 count 值時採取了一種特殊的協議：

• 倘若 free page 數 < 0xFFFF，則使用 count 記錄真實的 free page 數量
• 倘若 free page 數 >= 0xFFFF，則將 count 置爲 0xFFFF，並通過 freelist page body 中首個 pgid 的位置（uint64）記錄真實的 free page 數量

上述策略對應的實現示意圖如下：

2.4.4 free 空閒頁

在讀寫事務提交時，倘若有些 page 已經棄置不用，則通過 free 方法將其追加到 freelist 的 pending 列表：

// free 空閒頁
func (f *freelist) free(txid txid, p *page) {
    // meta page 不允許被 free
    if p.id <= 1 {
        panic(fmt.Sprintf("cannot free page 0 or 1: %d", p.id))
    }


    // 追加到 pending 中，key 爲釋放這些 page 的 tx id
    txp := f.pending[txid]
    if txp == nil {
        txp = &txPending{}
        f.pending[txid] = txp
    }
    
    // ...
    for id := p.id; id <= p.id+pgid(p.overflow); id++ {
        // ...
        // 分別追加到 pending 和 cache 中
        txp.ids = append(txp.ids, id)
        f.cache[id] = struct{}{}
    }
}

freelist 中的 pending 是一個 map，key 是事務 id，value 是該事務 free 的空閒頁列表. 之所以要通過 tx id 作爲鍵標識，是因爲 tx id 是全局遞增的，只要某個時刻，所有小於該 tx id 的事務都結束了，就代表這些 old page 已經不再存在 “讀者”，也就可以真正釋放這部分 page，進而得以保全【可重複讀】的語義.

2.4.5 release 空閒頁

當所有小於 txid 的事務都結束時，該 txid 下的空閒頁都能夠真正得到 release，只需要將其從 pending 中移除，並追加到 freelist 的 ids 中即可：

// release 所有 <= txid 的事務的 pending 列表
func (f *freelist) release(txid txid) {
    m := make(pgids, 0)
    for tid, txp := range f.pending {
        if tid <= txid {
            // pending 中的頁追加到 ids 中
            m = append(m, txp.ids...)
            // 從 pending 中移除
            delete(f.pending, tid)
        }
    }
    // ...
}

2.4.6 allocate page

讀寫事務提交時，會基於 copy-on-write 機制，針對所有涉及更改的節點分配新的 page 副本，此時會需要從 db 中分配可用的 page：

• 第一步：嘗試從 freelist 中分配 page
• 第二步：倘若 freelist 餘量不足，則需要進行擴容，此時會進行新一輪 mmap 操作拓寬容量範圍

// 提交事務
func (tx *Tx) Commit() error {
    // 1 rebalance b+ tree...
    // ...


    opgid := tx.meta.pgid
    // 2 spill b+ tree
    if err := tx.root.spill(); err != nil {
        tx.rollback()
        return err
    }
    
    // 3 free 不用的 page 到 freelist ...
    
    // 4 髒數據 page 溢寫落盤
     
    // 5 meta page 副本溢寫落盤


    // ...
}

func (n *node) spill() error {
    // ...
    // 針對所有涉及變更的 node，free 老的 page，申請分配新的 page
    for _, node := range nodes {
        // free 老的 page
        if node.pgid > 0 {
            tx.db.freelist.free(tx.meta.txid, tx.page(node.pgid))
            node.pgid = 0
        }


        // 分配新的 page
        p, err := tx.allocate((node.size() + tx.db.pageSize - 1) / tx.db.pageSize)
        if err != nil {
            return err
        }


        // ...
    }


    // ...
    return nil
}

func (tx *Tx) allocate(count int) (*page, error) {
    p, err := tx.db.allocate(tx.meta.txid, count)
    // ...
}

此時會使用到 db 中的對象池 pagePool，嘗試複用單個 page 對應的字節數組，並且嘗試從 freelist 中獲取可用的 page，如果沒有找到目標，則通過 mmap 進行擴容：

func (db *DB) allocate(txid txid, count int) (*page, error) {
    // 1 倘若需要獲取的 page 數量爲 1，通過 pagePool 複用字節數組
    var buf []byte
    if count == 1 {
        buf = db.pagePool.Get().([]byte)
    } else {
        buf = make([]byte, count*db.pageSize)
    }
    p := (*page)(unsafe.Pointer(&buf[0]))
    p.overflow = uint32(count - 1)


    // 2 嘗試從 freelist 獲取可用的 page
    if p.id = db.freelist.allocate(txid, count); p.id != 0 {
        return p, nil
    }


    // 3 freelist 資源不足，則通過 mmap 擴容...


    // ...
    return p, nil
}

至此，我們走到 freelist 分配可用 page 的入口方法，該方法是 freelist 類中的一個成員屬性——allocate：

type freelist struct {
    freelistType   FreelistType                // freelist 類型，默認使用 array 形式
    ids            []pgid                      // 所有已經釋放可用的 page
    // ...
    cache          map[pgid]struct{}           // 所有空閒 page
    // ...
    allocate       func(txid txid, n int) pgid // 分配可用 page 的入口函數
    // ...
}

默認情況下，allocate 方法的實現是 freelist.arrayAllocate 方法，其實現思路就是平鋪直敘地對可用頁列表 ids 從左往右進行遍歷，直到首次找到滿足要求的 n 個連續可用 page，則返回首個 page 對應 id：

// 爲某個事務分配連續的 n 個 可用 page
func (f *freelist) arrayAllocate(txid txid, n int) pgid {
    if len(f.ids) == 0 {
        return 0
    }


    // 按照正序在 freelist 的 ids 列表中遍歷，直到找到連續的 n 個可用 page 時，返回首個 page id
    // 倘若找不到目標，則返回 0
    var initial, previd pgid
    for i, id := range f.ids {
        // ...


        // 新的可用 page 和上一個不連續，則放棄上一個，從新的 page 開始嘗試
        if previd == 0 || id-previd != 1 {
            initial = id
        }


        // 找到連續可用的 n 個 page 了
        if (id-initial)+1 == pgid(n) {
            // 剛好是末尾，則直接從 ids 截斷最後被取走的部分
            if (i + 1) == n {
                f.ids = f.ids[i+1:]
            // 否則從 ids 中部截去被取走的部分
            } else {
                copy(f.ids[i-n+1:], f.ids[i+1:])
                f.ids = f.ids[:len(f.ids)-n]
            }


            // 被取用的 page 從 freelist 的 cache 中移除
            for i := pgid(0); i < pgid(n); i++ {
                delete(f.cache, initial+i)
            }
            // 返回首個 page id
            return initial
        }


        previd = id
    }
    return 0
}

2.4.7 序列化

在讀寫事務提交時，會將最新版本的 freelist 副本序列化成 page 的形式，並通過 meta 副本持有新版本 freelist 的引用：

// 提交讀寫事務
func (tx *Tx) Commit() error {
    // ...
    // 1 調整 b+ 樹
    
    // 2 序列化 freelist，並讓 meta 副本指向它
    if !tx.db.NoFreelistSync {
        err := tx.commitFreelist()
        if err != nil {
            return err
        }
    } 
    
    // 3 髒數據頁落盤
    
    // 4 meta page 落盤，freelist 隨之被落盤更新
    if err := tx.writeMeta(); err != nil {
        tx.rollback()
        return err
    }
    
    // ...


    return nil
}

func (tx *Tx) commitFreelist() error {
    // ...
    
    // freelist 序列化到 page 中
    if err := tx.db.freelist.write(p); err != nil {
        tx.rollback()
        return err
    }
    
    // meta 副本指向新的 freelist page
    tx.meta.freelist = p.id


    return nil
}

freelist.write 是將 freelist 內容序列化成 page 的核心方法：

• 設置 page flag 標識爲 freelist
• 獲取 freelist 中的空閒 page 總數，遵循 0xFFFF 的特殊協議，將 page 數量設置在 header 的 count 字段或者 body 的首個 pgid 的位置
• 將所有空閒 page 追加寫入到 header ptr 對應 body 所在位置

此處值得一提的是，不管是已釋放 ids 還是待釋放的 pending 中的空閒 page，都會被序列化到 page body 中. 這是因爲 boltdb 正常運行過程中，會統一使用到內存中的 freelist 實例，此時能夠通過 pending 區分出哪些 page 是待釋放的. 倘若未來需要用到 freelist page 反序列化成內存中的 page 實例，則必然是面臨 boltdb 重啓的場景，此時由於不存在運行的事務，因此不存在【可重複讀】的訴求，所有 pending page 都能被視作可用 page 進行復用.

// 將 freelist 的內容序列化的 page 中
func (f *freelist) write(p *page) error {
    // 通過 flag 標識該 page 類型 freelist
    p.flags |= freelistPageFlag


    // 獲取總的空閒頁數量
    lenids := f.count()
    // 如果爲 0
    if lenids == 0 {
        p.count = uint16(lenids)
        // 如果爲小於 0xFFFF 的值
    } else if lenids < 0xFFFF {
        p.count = uint16(lenids)
        // 將所有空閒頁有序的 copy 到 page ptr 的位置中
        f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
    } else {
        // 特殊協議
        p.count = 0xFFFF
        // 0 號位置記錄真實的空閒頁數量
        ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
        // 將所有空閒頁有序的 copy 到 page ptr 的 [1:] 位置中
        f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
    }


    return nil
}

2.4.8 反序列化

在 db 啓動時，倘若 db 文件已存在，則需要讀取其中 freelist 部分內容，將其反序列化成 freelist 實例：

func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
    // ...
    // 加載 freelist
    db.loadFreelist()
    // ...
}

func (db *DB) loadFreelist() {
    db.freelistLoad.Do(func() {
        // 構造 freelist 實例
        db.freelist = newFreelist(db.FreelistType)
        // 反序列化 freelist
        db.freelist.read(db.page(db.meta().freelist))
        // ...
    })
}

freelist.read 是反序列化入口方法：

• 遵循 0xFFFF 協議，讀取空閒 page 數量
• 深拷貝 freelist ids 列表
• 針對 freelist ids 列表進行排序

// 從 page 中讀取 freelist 的內容，將其反序列化到內存中的 freelist 實例
func (f *freelist) read(p *page) {
    // 讀取 page 的 count 值
    idx, count := 0, int(p.count)
    // 如果 count 值爲 65535，則觸發特殊協議，第 0 頁記錄的纔是真實的 free page 數量
    if count == 0xFFFF {
        idx = 1 // 真正的數據往後偏移一個 uint64 的位置
        count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
    }


    // count = 0，代表沒有空閒頁
    if count == 0 {
        f.ids = nil
    } else {
        // 從真正的起始位置開始讀取空閒頁列表
        ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
        // 將內容深拷貝的 freelist 實例的 ids 中
        f.ids = make([]pgid, len(ids))
        copy(f.ids, ids)


        // 對空閒頁進行排序
        sort.Sort(pgids(f.ids))
    }


    // ...
}

2.5 branch&leaf

2.5.1 branch

branch page 用於存儲數據索引， 對應的是 b+ 樹中的枝幹節點. 由於 boltdb 中，key 數據是不定長的，因此在 branch page 中採取了 shadow paging 技術，通過在 page body 中放入一系列定長的 branchPageElement，在其中分別標註好對應 key 數據的地址和長度，以及該 key 所映射的子節點的 page id.

branchPageElement 的示意圖如下：

對應 branchPageElement 的實現代碼如下：

• pos：key 的起始位置
• ksize：key 的長度，單位 byte
• pgid：key 映射的子節點 page id

// b+樹中的枝幹節點中的一個元素
type branchPageElement struct {
    pos   uint32 // 對應 key 的起始位置
    ksize uint32 // 對應 key 的大小
    pgid  pgid   // key 對應子節點的 page id
}

倘若某個 page 是 branch 類型，則通過 page header 獲取指定 index 的 branchPageElement 的方法如下：

// 獲取 index 對應的 branch page element
func (p *page) branchPageElement(index uint16) *branchPageElement {
    return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}

獲取到 branchPageElement 後，可以結合 ksize 和 pos 信息，通過地址偏移的方式獲取其對應的 key 值：

func (b *branchPageElement) key() []byte {
    buf := (*[maxAllocSize]byte)(unsafe.Pointer(b))
    return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[b.pos]))[:b.ksize]
}

2.5.2 leaf

leaf page 用於存儲 kv 數據， 對應的是 b+ 樹中的葉子節點. 和 branch page 情況相同，由於 key 和 value 不定長，因此此處同樣採取了 shadow paging 技術，通過在 page body 中放入一系列定長的 leafPageElement，在其中標註好對應 key 數據的地址、長度以及 value 數據的長度.

elementPageElement 的示意圖如下：

leafPageElement 對應實現代碼如下：

• flags：標識 value 是普通數據還是一個子 bucket
• pos：key 的起始位置
• ksize：key 的長度，單位 byte
• vsize：value 的長度，單位 byte. 需要知道，value 和 key 是相鄰的，因此其起始位置爲 pos + ksize

// b+樹中的葉節點中的一個元素
type leafPageElement struct {
    flags uint32 // 標識 kv 對標識內容是普通數據還是 bucket
    pos   uint32 // key 的起始位置
    ksize uint32 // key 的大小
    vsize uint32 // value 的大小
}

倘若某個 page 類型爲 leaf，則通過 page header 獲取指定 index 的 leafPageElement 的方法如下：

// 獲取 index 對應的 leaf page element
func (p *page) leafPageElement(index uint16) *leafPageElement {
    n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
    return n
}

獲取到 leafPageElement 後，結合 pos、ksize、vsize 等信息，通過地址偏移的方式可以讀取對應的 key 和 value 內容：

func (l *leafPageElement) key() []byte {
    buf := (*[maxAllocSize]byte)(unsafe.Pointer(l))
    return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[l.pos]))[:l.ksize]
}

func (l *leafPageElement) value() []byte {
    buf := (*[maxAllocSize]byte)(unsafe.Pointer(l))
    return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[l.pos+l.ksize]))[:l.vsize]
}

3 緩存 & 持久化

從本章開始，我們從讀、寫流程的視角，來梳理 boltdb 中有關數據緩存與持久化的機制.

3.1 mmap

3.1.1 核心概念

boltdb 的讀流程基於 mmap 技術實現.

所謂 mmap，全稱 memory mapping，這種技術能夠實現磁盤文件與內存空間的映射，屏蔽磁盤 io 的細節，使得使用方能夠像訪問內存中的字節數組一樣去訪問磁盤文件內容.

3.1.2 流程源碼

boltdb 中 mmap 的大小上限爲 256TB，mmap 映射後，對應的內容通過 db.data 字段獲取，並且通過一把讀寫鎖 mmaplock 保證其併發安全性：

const maxMapSize = 0xFFFFFFFFFFFF // 256TB


type DB struct {
    // ...
    path     string   // db 文件路徑
    openFile func(string, int, os.FileMode) (*os.File, error) // 打開 db 文件方法
    file     *os.File  // db 文件
    // ...
    dataref  []byte // mmap 原始字節數組，爲只讀模式，不可寫
    data     *[maxMapSize]byte  // mmap 映射 db 文件得到的字節數組
    datasz   int  // mmap size
    // ...
    mmaplock sync.RWMutex // 保護 mmap 操作併發安全的讀寫鎖
    // ...
}

在 db 啓動或者提交讀寫事務發現可用 page 不足時，都會執行 mmap 操作. 前者是初始化，後者是擴容：

// 啓動 boltdb
func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
    // 1 構造 db 實例 ...


    // 2 讀取配置 ...
    
    // 3 打開 db 文件 ...
    
    // 4 初始化 db 文件頭 4 個 page ...


    // 5 執行 mmap 操作
    if err := db.mmap(options.InitialMmapSize); err != nil {
        _ = db.close()
        return nil, err
    }


    // 6 返回 db 實例 ...
}

// 提交讀寫事務時，需要爲事務分爲指定數量的 page
func (db *DB) allocate(txid txid, count int) (*page, error) {
    // 1 嘗試取 freelist ...
    
    // 2 freelist 空間不足，則通過 mmap 擴容
    p.id = db.rwtx.meta.pgid
    var minsz = int((p.id+pgid(count))+1) * db.pageSize
    if minsz >= db.datasz {
        if err := db.mmap(minsz); err != nil {
            return nil, fmt.Errorf("mmap allocate error: %s", err)
        }
    }


    // 3 更新 meta 副本中的 pgid 範圍...
    return p, nil
}

mmap 操作的入口是 db.mmap 方法，核心步驟爲：

• 加鎖——mmaplock
• 調整合適的 mmap size（小於 1GB 倍增，大於 1GB 向上取整）
• 如果有讀寫事務在運行，需要執行 dereference 操作（將所有 b+ 樹節點反序列化到內存，這樣在持久化時會有機會更新 page 信息）
• 如果之前有過 mmap 操作，需要執行 unmmap 系統調用
• 進行新一輪 mmap 系統調用
• 校驗 meta page 合法性

// 執行 mmap 操作
func (db *DB) mmap(minsz int) (err error) {
    // 1 加鎖保證併發安全
    db.mmaplock.Lock()
    defer db.mmaplock.Unlock()


    // ...
    // 2 調整合適的 mmap size
    size, err = db.mmapSize(size)
    
    // ...
    // 3 如果有讀寫事務在運行，需要更新其引用的 b+ 樹節點(即將新一輪 mmap，節點對應 page 可能需要調整)
    // 做法就是將這些節點都反序列化到內存，這樣在溢寫落盤時，就會有更新的機會
    if db.rwtx != nil {
        db.rwtx.root.dereference()
    }


    // 4 如果之前進行過 mmap，需要解除映射
    if err = db.munmap(); err != nil {
        return err
    }


    // 5 建立新的 mmap 映射
    if err = mmap(db, size); err != nil {
        return err
    }


    // ...
    
    // 6 校驗 meta page 合法性
    db.meta0 = db.page(0).meta()
    db.meta1 = db.page(1).meta()
    
    err0 := db.meta0.validate()
    err1 := db.meta1.validate()
    if err0 != nil && err1 != nil {
        return err0
    }


    return nil
}

mmap 系統調用的實現與操作系統版本有關，這裏我簡單給出 unix 系統的實現：

// mmap memory maps a DB's data file.
func mmap(db *DB, sz int) error {
    // Map the data file to memory.
    b, err := unix.Mmap(int(db.file.Fd()), 0, sz, syscall.PROT_READ, syscall.MAP_SHARED|db.MmapFlags)
    if err != nil {
        return err
    }


    // Advise the kernel that the mmap is accessed randomly.
    err = unix.Madvise(b, syscall.MADV_RANDOM)
    if err != nil && err != syscall.ENOSYS {
        // Ignore not implemented error in kernel because it still works.
        return fmt.Errorf("madvise: %s", err)
    }


    // Save the original byte slice and convert to a byte array pointer.
    db.dataref = b
    db.data = (*[maxMapSize]byte)(unsafe.Pointer(&b[0]))
    db.datasz = sz
    return nil
}

3.1.3 mmap size

由於 mmap 系統調用的成本較高，爲了減少執行頻率，boltdb 在每輪執行 mmap 時會預留一部分空間：在新容量小於 1GB 時，則從 32KB 基礎上持續倍增找到首個滿足條件容量；在新容量超過 1GB 時，則基於 GB 向上取整.

// 獲取合適的 mmap 大小
func (db *DB) mmapSize(size int) (int, error) {
    // 32KB - 1GB 範圍內採取倍增策略
    for i := uint(15); i <= 30; i++ {
        if size <= 1<<i {
            return 1 << i, nil
        }
    }


    // ...


    // 大於 1GB，則基於 GB 向上取整
    sz := int64(size)
    if remainder := sz % int64(maxMmapStep); remainder > 0 {
        sz += int64(maxMmapStep) - remainder
    }


    // ...
}


const maxMmapStep = 1 << 30 // 1GB

3.2 pwrite+fdatasync

3.2.1 核心概念

boltdb 寫流程採用 pwrite + fdatasync 技術實現：

• pwrite： 該操作本質上是文件的 writeAt 方法，能實現將數據寫入到文件指定 offset 的能力. 需要注意的是，在 linux 系統中，出於性能優化的目的，pwrite 系統調用不會等待磁盤 io 完成，而是僅在將任務提交到設備 io 隊列後就返回，因此在嚴格意義上無法保證持久化操作的穩定性
• fdatasync： 該操作會在確保設備 io 執行完成後才返回，以此來保證數據持久化操作的穩定性，與 pwrite 操作形成一套嚴絲合縫的組合拳

3.2.2 流程源碼

pwrite 操作默認爲文件的 writeAt 方法，入口是 db 的 ops 成員屬性：

type DB struct {
    // ...


    ops struct { // 將數據寫到 db 文件指定位置的 pwrite 操作
        writeAt func(b []byte, off int64) (n int, err error)
    }


    // ...
}

在讀寫事務提交過程中，不論是髒數據頁還是 meta 副本的溢寫落盤流程，都會應用到 pwrite + fdatasync 指令：

func (tx *Tx) Commit() error {
    // 1 調整各個 bucket 下的 b+ 樹，保證其平衡性


    // ...
    // 2 倘若 b+ 樹平衡性調整後，page 空間不足，則需要進行擴容...


    // 3 髒數據溢寫落盤
    if err := tx.write(); err != nil {
        tx.rollback()
        return err
    }


    // ...
    // 4 meta page 溢寫落盤
    if err := tx.writeMeta(); err != nil {
        tx.rollback()
        return err
    }
    
    // 5 關閉事務...
    // 6 執行 commit 回調函數...


    return nil
}

// 髒頁溢寫落盤
func (tx *Tx) write() error {
    // 1 獲取髒頁並排序...


    // 遍歷每個髒頁，依次寫入到 db 文件中
    for _, p := range pages {
        // ...
        // 如果 page 過大，則需要拆分多個批次寫入
        for {
            // ...


            // pwrite 操作
            if _, err := tx.db.ops.writeAt(buf, offset); err != nil {
                return err
            }


            // ...         
        }
    }


    // 執行 fdatasync 操作，保證髒頁成功落盤
    if !tx.db.NoSync || IgnoreNoSync {
        if err := fdatasync(tx.db); err != nil {
            return err
        }
    }


    // ...
    return nil
}

func (tx *Tx) writeMeta() error {
    // ...
    // pwrite
    if _, err := tx.db.ops.writeAt(buf, int64(p.id)*int64(tx.db.pageSize)); err != nil {
        return err
    }
    
    // fdatasync
    if !tx.db.NoSync || IgnoreNoSync {
        if err := fdatasync(tx.db); err != nil {
            return err
        }
    }


    // ...
    return nil
}

pwrite 操作爲 os/file 標準庫下的 WriteAt 方法：

package os/file


func (f *File) WriteAt(b []byte, off int64) (n int, err error) {
    // ...
    for len(b) > 0 {
        m, e := f.pwrite(b, off)
        if e != nil {
            err = f.wrapErr("write", e)
            break
        }
        n += m
        b = b[m:]
        off += int64(m)
    }
    return
}

unix 系統下，fdatasync 的實現爲 file.sync 方法：

// fdatasync flushes written data to a file descriptor.
func fdatasync(db *DB) error {
    return db.file.Sync()
}


func (f *File) Sync() error {
    // ...
    if e := f.pfd.Fsync(); e != nil {
        return f.wrapErr("sync", e)
    }
    return nil
}

3.3 copy on write

縱觀整個 boltdb 的交互流程，都貫徹了對 copy-on-write 策略的應用，下面我們就以一個事務開啓和提交的流程，來總結一下其中哪些環節提現了寫時複製的思路.

3.3.1 meta&bucket 副本

在一個新事務初始化時，會拷貝出一份 meta page 和 bucket 副本，後續涉及到對這部分內容的修改時，都在副本的基礎上執行，再通過事務提交環節一次性實現修改內容的覆蓋生效.

func (tx *Tx) init(db *DB) {
    // ...
    // 爲當前事務複製一份 meta 副本
    tx.meta = &meta{}
    db.meta().copy(tx.meta)


    // 深拷貝複製出一份 bucket 實例
    tx.root = newBucket(tx)
    tx.root.bucket = &bucket{}
    *tx.root.bucket = tx.meta.root
    // ...
}

// 深拷貝一份 meta 副本
func (m *meta) copy(dest *meta) {
    *dest = *m
}

3.3.2 髒數據 page 副本

在提交讀寫事務過程中，會基於 copy on write 機制，將所有涉及變更的節點序列化成一份新的 page 副本，而不是在原 page 上直接更新：

// 提交事務
func (tx *Tx) Commit() error {
    // 1 rebalance ...


    // 2 記錄原本已分配的 page 範圍
    // ...
    // 3 spill spill 時，還會針對改動的部分，基於 copy on write 機制生成一系列髒數據的 page 副本
    if err := tx.root.spill(); err != nil {
        tx.rollback()
        return err
    }
    
    // ...
    // ...


    // 4 髒頁落盤持久化
    if err := tx.write(); err != nil {
        tx.rollback()
        return err
    }


    // ...


    // 5 meta page 落盤持久化
    if err := tx.writeMeta(); err != nil {
        tx.rollback()
        return err
    }
    
    // 至此，代表事務已經提交成功了，數據已經成功更新！
    // ...


    return nil
}

// 針對當前 node 進行拆分
func (n *node) spill() error {
    // ...
    // 遍歷所有涉及變更的節點
    for _, node := range nodes {
        // ...
        
        // 分配對應數量的 page 副本
        p, err := tx.allocate((node.size() / tx.db.pageSize) + 1)
        if err != nil {
            return err
        }


        // ...
        // 將變更後的 node 內容寫入到 page 副本中中
        node.pgid = p.id
        node.write(p)
        node.spilled = true


        // ...
    }


    // ...
}

3.3.3 副本覆蓋生效

在事務提交的持久化環節，隨着一些髒數據 page 副本的溢寫落盤，其中的內容已經得到了持久化保證：

func (tx *Tx) write() error {
    // ...
    // 髒數據 page pwrite
    for _, p := range pages {
        // ...
        for {
            // ...
            // pwrite
            if _, err := tx.db.ops.writeAt(buf, offset); err != nil {
                return err
            }
            // ...
        }
    }


    // fdatasync
    if !tx.db.NoSync || IgnoreNoSync {
        if err := fdatasync(tx.db); err != nil {
            return err
        }
    }


    // ...
}

但大家需要注意，截止到此時，這部分數據還不會被 boltdb 所認可，因爲 db 中的 meta 還是老版本，其中的 b+ 樹也還是原本的引用，接下來就是真正 “畫龍點睛” 的一步——讀寫事務 meta 副本落盤：

// 讀寫事務 meta 副本落盤
func (tx *Tx) writeMeta() error {
    // pwrite
    if _, err := tx.db.ops.writeAt(buf, int64(p.id)*int64(tx.db.pageSize)); err != nil {
        return err
    }
    
    // fdatasync
    if !tx.db.NoSync || IgnoreNoSync {
        if err := fdatasync(tx.db); err != nil {
            return err
        }
    }


    // ...
    return nil
}

隨着新版本 meta 的落盤持久化，由其所指向的新版 bucket 以及其中一系列修改後的 b+ 樹節點也就真正得到了 “正名”.

只要該 meta 落盤成功，那麼其中的 tx id 就是全局最大的，未來在新的讀寫流程中，都會以該版本 meta 爲準，一輪 copy-on-write 策略的實施至此完美收官！

3.4 擴容

在讀寫事務提交時，倘若發現可用 page 不足，則會推動 boltdb 進行擴容：

func (tx *Tx) Commit() error {
    // 1 調整各個 bucket 下的 b+ 樹，保證其平衡性
    // 1 rebalance ...
    
    // 2 記錄原本已分配的 page 範圍
    opgid := tx.meta.pgid


    // ...
    // 3 spill spill 時，還會針對改動的部分，基於 copy on write 機制生成一系列髒數據的 page 副本
    if err := tx.root.spill(); err != nil {
        tx.rollback()
        return err
    }
    // ...
    // 4 倘若 b+ 樹平衡性調整後，page 範圍右擴，需要對文件對應調整
    if tx.meta.pgid > opgid {
        if err := tx.db.grow(int(tx.meta.pgid+1) * tx.db.pageSize); err != nil {
            tx.rollback()
            return err
        }
    }


    // ...
    return nil
}

前文已經針對上述的 spill 流程做過一些介紹，在申請可用 page 作爲髒數據 page 副本時，可能存在 freelist 資源不足的情況，此時則會推動 boltdb 發動新一輪 mmap 操作，並且更新其 meta 副本中的 pgid 值.

於是，db.grow 方法得以執行，其中會通過 truncate 方法實現文件截斷操作，實現 “擴容” 語義，並通過 fdatasync 確保其生效：

// db 擴容
func (db *DB) grow(sz int) error {
    // 1 調整合適的擴容大小 ...    
    if db.datasz <= db.AllocSize { // AllocSize 默認值爲 16M
        sz = db.datasz
    } else {
        // 超過 16M，則每次增長 16M
        sz += db.AllocSize
    }    


    // 2 通過 truncate + fsync 操作，確保擴容完成
    if !db.NoGrowSync && !db.readOnly {
        if runtime.GOOS != "windows" {
            if err := db.file.Truncate(int64(sz)); err != nil {
                return fmt.Errorf("file resize error: %s", err)
            }
        }
        // fdatasync
        if err := db.file.Sync(); err != nil {
            return fmt.Errorf("file sync error: %s", err)
        }
        // ...
    }


    // 3 新的文件大小
    db.filesz = sz
    return nil
}

4 b+ tree

本章我們簡單點一些有關 b+ 樹部分的內容（聚焦內存部分），詳細內容我們在下一篇——etcd 存儲引擎之 b + 樹實現中展開.

4.1 設定

在 boltdb 中，採用 b+ 樹模型進行數據的存儲. 實際上，依附於不同的存儲介質，我們也同樣可以從兩個視角出發來看待其針對 b+ 樹的實現.

• page：基於 mmap 技術實現的 page 底層本質上和磁盤文件內容關聯. 因此如本文 2.5 小節介紹的 branch& leaf page，可以理解爲 “磁盤上” 的 b+ 樹節點，通過 branchPageElement、leafPageElement，以及其中針對 key、value 和子節點的指向，形成一顆邏輯上的 b+ 樹拓撲結構
• node：內存中反序列化得到的 b+ 樹節點，是基於懶加載機制實現的，因此只有在需要修改某個節點時，纔會從對對應的 branch&leaf page 中將其反序列化成 node 實例，並最終基於 copy-on-write 機制將其序列化成新的 page 副本，並通過 pwrite + fdatasync 實現持久化

4.2 node

node 是內存中反序列化得到的 b+ 樹節點類，其核心成員屬性定義爲：

• bucket：從屬的 bucket. 每棵 b+ 樹必然從屬於某個 bucket（表）
• isLeaf： 標識該節點是葉子節點還是枝幹節點
• unbalanced： 倘若節點執行過刪除 key 操作，則 unbalanced 會被置爲 true. 該節點在持久化前需要先執行 rebalance 操作
• spilled： 標識該節點是否已經執行過 spill 操作
• key： 該節點中最小的一個 key
• pgid： 該節點對應的 page id，即其反序列化的來源. 值得一提的是，node 在持久化時會被寫入到一個新的 page 副本中，正是所謂的 copy on write 機制
• parent： 父節點
• children： 一系列子節點，在 dereference、rebalance 和 spill 流程中使用
• inodes：該節點下的一系列 kv 數據（廣義的 kv，如爲 branch 類型，則此處的 “v” 指子節點）

// 內存中的 b+ tree 節點，對應磁盤上的一個 branch/leaf element page
type node struct {
    bucket     *Bucket // 該節點從屬的 bucket
    isLeaf     bool    // 是否爲 b+ tree leaf 節點，爲 false 則爲 branch 節點
    unbalanced bool    // 該節點是否刪除過數據，是的話需要在落盤前進行 rebalance 操作
    spilled    bool    // 該節點是否執行過 spill 操作
    key        []byte  // 該節點下的首個 key (最小的 key)
    pgid       pgid    // 該節點對應 page  id
    parent     *node   // 父節點
    children   nodes   // 子節點列表，該節點爲分支節點時使用
    inodes     inodes  // kv 數據列表，該節點爲葉子節點時使用
}

inode 標識某個 node 中的一筆 kv 數據（廣義的 kv，如爲 branch 類型，則此處的 “v” 指子節點）：

• flags： 標識 value 是否標識一個子 bucket
• key： 標識鍵 key
• pgid：如果 node 爲 branch 類型，則 “v” 取 pgid 字段，標識子節點的 pgid
• value：如果 node 爲 leaf 類型，則直接通過 value 取值

// b+ tree 葉子節點中的一個 kv 對
type inode struct {
    flags uint32 // 標識其是否是 bucket
    pgid  pgid   // 從屬的 page id
    key   []byte // key
    value []byte // value
}

4.3 序列化

在讀寫事務提交時，需要將所有 node 序列化到 page 副本中 (會被反序列化成 node 的節點往往都發生過變更)，對應方法爲 node.write：

func (n *node) write(p *page) {
    // ...
    // 設置對應的 page flag，標識是分支還是葉子節點
    if n.isLeaf {
        p.flags = leafPageFlag
    } else {
        p.flags = branchPageFlag
    }


    // 記錄節點的 key 數量
    p.count = uint16(len(n.inodes))


    // 沒有 key 數據，直接返回
    if p.count == 0 {
        return
    }


    // 下面針對每筆 kv (inode) 進行序列化
    // 記錄 offset 偏移量
    off := unsafe.Sizeof(*p) + n.pageElementSize()*uintptr(len(n.inodes))
    for i, item := range n.inodes {
        // ...
        // key + value 的大小
        sz := len(item.key) + len(item.value)
        // 用於存儲 key + value 內容的容器
        b := unsafeByteSlice(unsafe.Pointer(p), off, 0, sz)
        // 累加偏移量
        off += uintptr(sz)


        // 針對葉子節點的 key-value 數據，對 leafPageElement 進行賦值，標識數據元信息
        if n.isLeaf {
            elem := p.leafPageElement(uint16(i))
            elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
            elem.flags = item.flags
            elem.ksize = uint32(len(item.key))
            elem.vsize = uint32(len(item.value))
        // 針對分支節點的 key-child node 數據，對 branchPageElement 進行賦值，標識數據元信息
        } else {
            elem := p.branchPageElement(uint16(i))
            elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
            elem.ksize = uint32(len(item.key))
            elem.pgid = item.pgid
            // ...
        }


        // 深拷貝 key value 數據到對應的 offset 位置
        l := copy(b, item.key)
        copy(b[l:], item.value)
    }
}

4.4 反序列化

讀寫事務運行過程中，倘若涉及到對某個 b+ 樹節點的調整，則需要將其反序列化爲 node 實例，在內存中完成修改：

// 從 page 中讀取節點內容，將其反序列化到 node 實例中
func (n *node) read(p *page) {
    // 傳承 page 的 id
    n.pgid = p.id
    // 標識節點是否爲葉子節點
    n.isLeaf = ((p.flags & leafPageFlag) != 0)
    // 反序列化對應數量的 inode
    n.inodes = make(inodes, int(p.count))


    // 針對每個 inode 進行反序列化
    for i := 0; i < int(p.count); i++ {
        inode := &n.inodes[i]
        if n.isLeaf {
            elem := p.leafPageElement(uint16(i))
            inode.flags = elem.flags
            inode.key = elem.key()
            inode.value = elem.value()
        } else {
            elem := p.branchPageElement(uint16(i))
            inode.pgid = elem.pgid
            inode.key = elem.key()
        }
    }


    // 冗餘記錄最小的 key
    if len(n.inodes) > 0 {
        n.key = n.inodes[0].key
    } else {
        n.key = nil
    }
}

4.5 cursor

遊標 cursor 是 boltdb 中針對 b+ 樹實現的一個改造點，它會通過一個棧結構記錄某次操作在 b+ 樹上的移動路徑，以此來輔助完成一些複雜的回溯檢索操作.

cursor 實現代碼如下：

type Cursor struct {
    bucket *Bucket
    stack  []elemRef // 通過棧記錄移動路徑. 最後一個元素代表此時所在位置
}

elemRef 對應爲移動路徑涉足的一個 b+ 樹節點，由於內存中的 b+ 樹 node 是懶加載機制，因此倘若移動路徑涉足到一些未反序列化的節點（沒有數據變更），則可能會通過 page 字段來標識：

• node： 倘若某個節點反序列化過了，則指向對應 node
• page： 倘若某個節點未反序列化，則指向對應 page
• index：檢索目標在節點中的 key 的 index

// 由於 b+ 樹採用懶加載機制，因此樹中的節點可能是 page，也可能是 node
type elemRef struct {
    page  *page
    node  *node
    index int
}

cursor 一定是依附於 bucket 存在的，其構造方法如下：

// 返回對應的遊標卡尺
func (b *Bucket) Cursor() *Cursor {
    // ...
    // 返回遊標實例
    return &Cursor{
        bucket: b,
        // 遊標對應的棧
        stack: make([]elemRef, 0),
    }
}

5 bucket

5.1 設定

在 boltdb 中引入了桶 bucket 的設定，作用是實現業務數據的隔離, 可以簡單把 bucket 類比於數據庫中的表，只不過 bucket 的形式會更加靈活一些，還能支持嵌套式的拓撲關係，形如上圖，school 和 school-class 是兩個合法的 bucket，且彼此爲父子關係.

在邏輯意義上，每個 bucket 會有一棵獨立的 b+ 樹，用於存放當前 bucket 範圍內的 kv 數據.

5.2 類定義

Bucket 類定義代碼如下：

• *bucket：Bucket header 部分. 這部分是需要被持久化的，其餘字段只存在於內存副本中
• tx： 當前 Bucket 實例所從屬的事務. 因爲這是內存中的 Bucket 實例，因此一定是在開啓了某個事務的前提下才會被創建出來
• buckets： 當前 Bucket 下緩存的子 Bucket map. 注意這裏非全量，也是採取懶加載機制，被用到過的子 Bucket 纔會緩存在這裏
• page： 如果當前 Bucket 是一個內聯 Bucket，則用該字段表示其虛擬 page（5.3 小節介紹何謂內聯 Bucket）
• rootNode： Bucket 下的 b+ 樹根節點
• nodes：緩存的 b+ 樹節點. 同樣非全量，涉及變更的節點纔會被反序列化成 node，纔會緩存於此 map

// 內存中的 Bucket 實例，一定是基於某個 tx 創建的
type Bucket struct {
    *bucket                     // bucket header，記錄元信息
    tx       *Tx                // 創建當前桶實例的事務
    buckets  map[string]*Bucket // 子桶
    page     *page              // 如果爲 inline bucket，則爲對應 page 的引用
    rootNode *node              // 當前桶下 b+ 樹的根節點
    nodes    map[pgid]*node     // 當前桶下已反序列化後緩存的 node 節點


    // ...
}


// bucket header. 需要序列化部分的元信息
type bucket struct {
    root     pgid   // bucket 中根節點對應的 page id
    sequence uint64 // bucket 的序列號，全局單調遞增
}

5.3 內聯

正如上文所述，每個 bucket 都有一顆獨立的 b+ 樹，而每個 b+ 樹至少有一個節點，即 boltdb 至少要爲每個 bucket 分配一個 page.

然而在實際使用場景中，很多 bucket 存儲的數據量可能遠小於一個 page，爲避免造成空間浪費，boltdb 針對數據量小於 pageSize/4 且只需要單個 page 的 bucket 採取 inline bucket 策略——借鑑虛擬內存實現思路，在緊挨着 Bucket header 的位置取出一塊小於 page 但仍按照 page 格式組織的空間，組成一個邏輯意義的 “page” 進行數據存儲.

判斷一個 Bucket 是否需要採取 inline 模式的方法如下：

// 判斷 bucket 是否爲 inline 類型
func (b *Bucket) inlineable() bool {
    var n = b.rootNode


    // 只有某個 bucket 僅包含一個葉子類型的根節點時，纔有可能是 inline bucket
    if n == nil || !n.isLeaf {
        return false
    }


    // 統計一下 bucket 的總大小
    var size = pageHeaderSize
    for _, inode := range n.inodes {
        // 累加每個 inode 的大小
        size += leafPageElementSize + len(inode.key) + len(inode.value)
        // 如果存在 inode 不是 leaf element，則當前 node 不是 inline bucket
        if inode.flags&bucketLeafFlag != 0 {
            return false
            // 判斷總大小是否超過 inline bucket 限制(pageSize/4)
        } else if size > b.maxInlineBucketSize() {
            return false
        }
    }


    return true
}


func (b *Bucket) maxInlineBucketSize() uintptr {
    return uintptr(b.tx.db.pageSize / 4)
}

5.4 序列化

每個 Bucket 在剛被創建出來時，都是一個 inline bucket，此時需要對其進行序列化，將其數據組裝成 kv 對的形式寫入到其父 Bucket 的 b+ 樹中. inline bucket 序列化方法是 bucket.write

func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
    // ...


    // 創建 bucket 實例(此時爲 inline bucket)
    var bucket = Bucket{
        bucket:      &bucket{},
        rootNode:    &node{isLeaf: true},
        FillPercent: DefaultFillPercent,
    }
    
    // 序列化 bucket
    var value = bucket.write()


    // 組裝成 kv 對形式寫入到父 bucket b+ 樹中
    key = cloneBytes(key)
    c.node().put(key, key, value, 0, bucketLeafFlag)


    // ...
}

此外，在讀寫事務提交時，也會涉及對 Bucket 的序列化操作，此時針對常規 bucket 會直接對 Bucket header 部分進行深拷貝，針對 inline bucket 則同樣會調用 bucket.write 方法作序列化：

// spill writes all the nodes for this bucket to dirty pages.
func (b *Bucket) spill() error {
    // 處理每個子 bucket
    for name, child := range b.buckets {
        // 記錄子 bucket 序列化數據
        var value []byte
        // inline bucket 序列化
        if child.inlineable() {
            // ...
            value = child.write()
        // 普通 bucket 序列化
        } else {
            // ...
            // 直接進行 bucket 深拷貝
            value = make([]byte, unsafe.Sizeof(bucket{}))
            var bucket = (*bucket)(unsafe.Pointer(&value[0]))
            *bucket = *child.bucket
        }


        // ...
    }
    // ...
    return nil
}

inline bucket 的序列化方法如下：

func (b *Bucket) write() []byte {
    // 獲取數據大小
    var n = b.rootNode
    var value = make([]byte, bucketHeaderSize+n.size())


    // 深拷貝出 bucket header 部分內容
    var bucket = (*bucket)(unsafe.Pointer(&value[0]))
    *bucket = *b.bucket


    // 將數據部分寫入到緊挨着 bucket header 的後繼部分
    var p = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
    n.write(p)


    // 返回序列化結果
    return value
}

5.5 反序列化

當用戶需要獲取某個 Bucket 時，需要對其進行反序列化：

func (b *Bucket) Bucket(name []byte) *Bucket {
    // ... 如果子 bucket 已反序列化過，進行復用


    // 反序列化對應的子 bucket
    var child = b.openBucket(v)
    
    // ... 緩存反序列化後的子 bucket
    return child
}

反序列化核心方法爲 Bucket.openBucket，其中主語的 Bucket 是擬獲取 Bucket 的 parent：

• 構造一個空白 Bucket 實例
• 針對讀寫事務，基於 copy-on-write 機制，深拷貝一份 bucket header；針對只讀事務，則直接傳遞 header 引用
• 針對 inline bucket，需要讀取虛擬 page 內的數據

// 反序列化子 bucket
func (b *Bucket) openBucket(value []byte) *Bucket {
    創建一個空白的 bucket 實例
    var child = newBucket(b.tx)


    // ...
    // 針對讀寫事務，需要對 bucket 副本拷貝 copy-on-write
    if b.tx.writable && !unaligned {
        child.bucket = &bucket{}
        *child.bucket = *(*bucket)(unsafe.Pointer(&value[0]))
    } else { // 針對只讀事務，直接複用 bucket
        child.bucket = (*bucket)(unsafe.Pointer(&value[0]))
    }


    // 針對內聯 bucket，讀取對應的 page
    if child.root == 0 {
        child.page = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
    }


    return &child
}

func newBucket(tx *Tx) Bucket {
    var b = Bucket{tx: tx, FillPercent: DefaultFillPercent}
    // 針對讀寫事務反序列化的 bucket，需要初始化對應的緩存 map
    if tx.writable {
        b.buckets = make(map[string]*Bucket)
        b.nodes = make(map[pgid]*node)
    }
    return b
}

至此正文結束. 祝賀走到這裏各位朋友，我們又一起打贏了一場硬仗！

6 展望

本文是 etcd 存儲引擎系列的第二篇，帶着大家一起深入瞭解了 boltdb 的存儲設計原理. 在此回顧整個系列的研究進程並對後續內容進行展望：

• etcd 存儲引擎之主幹框架（已完成）：偏宏觀視角下介紹 boltdb 的定位、架構、特性，通過幾個核心流程淺探 boltdb 實現源碼
• etcd 存儲引擎之存儲設計（本篇）：介紹 boltdb 存儲模型、機制的設計實現，包含磁盤、內存兩部分
• etcd 存儲引擎之 b + 樹實現（待填坑）：介紹 b+ 樹理論模型及 boltdb 實現案例，包括模型定義及 crud 流程梳理
• etcd 存儲引擎之事務實現（待填坑）：介紹 boltdb 事務的執行模式及實現原理

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