BoltDB 源碼分析

• • node
  • • CopyOnWrite解決讀寫沖突
  • Element
  • bucket
  • • cursor
  • 內存分配
  • inline bucket
  • Cursor
  • rebalance
  • meta
  • bacth操作
  • 事務
  • • 原子性（Atomicity）
    • 一致性（Consistency）
    • 隔離性（Isolation）
    • 持久性（Durability）
  • 參考鏈接

---

BoltDB直接使用mmap, 直接將所有的頁, 也就是整個數據大文件, 全部映射到內存內，從而免去了自己實現pagecache等等，簡化了實現，并且數據持久化沒有編解碼，因此也避免了序列化的開銷。盡管Pavlo在15-445里教導我們千萬不要在數據庫領域用mmap代替page cache。

node

node為一個page在內存中的體現，也是數據插入的基本單元，每個node下存在innode，真正的存儲kv

每個node都有children和innode（如果innode沒有落盤，則不會分配pgid），并且有指針反指回parentNode

非leaf層的node節點至少要有2個inode元素

理論上，node中的元素，有一部分是mmap上來的指針地址，有一部分是新插入的元素。所以如果需要數據庫需要resize重新mmap的時候，就需要將之前mmap的指針全部拷貝到內存中。因此數據庫resize是個很重的操作。

CopyOnWrite解決讀寫沖突

一般的數據庫需要考慮"寫寫沖突", “讀寫沖突”, 由于BoltDB只支持單寫事務, 因此不存在"寫寫沖突";

現在考慮"讀寫沖突": 如果一個事務正在修改某個節點的數據, 但是還沒提交, 那對于另一個讀事務, 可能讀到臟數據;

BoltDB使用了CopyOnWrite的方法, 對需要修改節點單保存一份（把之前的那個頁的數據和增量數據都另存為到另外一個頁上）;

當事務進行提交時, 將這些緩存的數據, 全部同步到磁盤;

Element

分為branchPageElement和leafPageElement其中：

• branchPageElement指定了key的值和下一層的pgid，從而可以繼續向下查找

• leafPageElement通過flag指明當前leaf的內容

  • bucketLeafFlag表明當前的leaf中存儲的是其他的bucket，也就是bucket-root，一個blotDB存在唯一一個rootbucket
  • flag==0說明每個leaf里面是按順序存放的kv對，通過成員變量pos標明位置

• leafPageElement

|page|leafPageElement|leafPageElement|leafPageElement|...|leaf key|leaf value|leaf key|leaf value|...|

• branchPageElement

|page|branchPageElement|branchPageElement|branchPageElement|...|branch key|branch key|...|

上層branchnode存放下層node的第一個key

bucket

bucket是一些列的鍵值對的集合。一個bucket相當于一個命名空間，每個bucket中表示了一個完整的b+樹，另外bucket可以嵌套。對數據的增刪改查都基于bucket。

Bucket類比于mysql中的table，在boltdb中，meta頁面中有一個成員bucket，其存儲了整個數據庫根bucket的信息，而一個數據庫中存儲的其他table的信息，則作為子bucket存儲到Bucket中。其關系如下：

type DB struct {// ...meta0 *metameta1 *meta } type meta struct {// ...root bucket // 根bucket的信息，通過這個可以找到根bucket的page，根bucket中存放所有的其他root bucket// |bucket|bucket|bucket|bucket|...|// 每個子bucket中再保存各種映射信息 } type Bucket struct {*bucket// ...buckets map[string]*Bucket // 存儲子bucket的對應關系 } type bucket struct {// 根節點的page idroot pgid // page id of the bucket's root-level page// 單調遞增的序列號sequence uint64 // monotonically incrementing, used by NextSequence() }

子bucket保存在leafPageElement中，通過其中的元素flag來標識其是否是一個bucket

// leafPageElement represents a node on a leaf page. type leafPageElement struct {flags uint32pos uint32ksize uint32vsize uint32 }// key returns a byte slice of the node key. func (n *leafPageElement) key() []byte {buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize] }// value returns a byte slice of the node value. func (n *leafPageElement) value() []byte {buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos+n.ksize]))[:n.vsize:n.vsize] }

Bucket會有一個當前關聯的事務Tx

綜上，boltdb 支持嵌套的 Bucket，對于父 Bucket 而言，subbucket 只是特殊的 value 而已，設置 leafPageElement.flags = bucketLeafFlag 標記，而 subbucket 本身是一個完整的 B+ 樹:

cursor

我們創建了bucket之后，可以通過cursor進行遞歸查找，直到某個leaf node，cursor會維護一個棧，當找到時，棧頂元素就保存了對應的節點和位置（這個時候有兩種可能，一是在內存中（node），二是在page中（持久化到磁盤））

內存分配

在一個bucket創建的時候，會創建與之對應的node。然后會開辟一片內存，存放存放bucketHeader和node的數據結構，具體代碼在Bucket::write()函數中，內存分布如下：

內存中元素分布： |bucketHeader||page header | leaf/branch element .... | kv pair ... |分布示意圖： |<--bucket-->|<-- node... -->|

inline bucket

如果子Bucket中的數據量很少，就會造成磁盤空間的浪費。為了針對這類型Bucket進行優化，boltdb提供了inline page這個特殊的頁面，將小的子Bucket數據存放在這里。

這類型的子Bucket需要滿足以下兩個條件：

• 該子Bucket再沒有嵌套的子Bucket了。
• 整個子Bucket的大小不能超過page size/4。

Cursor

由于數據在inodes是按順序存放的，因此我們通過cursor進行二分，他會從rootbucket向下查找，并將路上的element放入stack中。最終，stack頂部的元素就是葉子節點，可以可以進行CRUD操作。

首先通過meta->root_找到root—bucket，然后cursor就會從這個地方為起點進行search

rebalance

由于CRUD操作是在內存中進行的，因此下刷磁盤的時候需要調整B+Tree結構。此時會涉及兩個操作：

rebalance:刪除操作會對node打上unbalanced標記，因為刪除數據可能會引起page填充率不夠，此時會對這些節點檢查并進行合并。如果水位超過25%就不需要rebalance

情況一、當前的parent node只有一個節點，將下層的節點提升

情況二、當前node已經不存在任何inode了，需要移除

情況三、本層的兩個node合并，選擇相鄰的兩個節點，將右邊節點的內容移入左邊

spill：添加操作會使得page填充率過高，需要對節點進行分裂。如果超過水位（默認50%）就需要進行spill

實際spill的時候，首先在bucket層面進行spill自底向下spill（下一層分裂會影響到上面一層），在這個過程中spill node

簡單來說，update操作涉及到的頁都會新申請頁，然后自底向上修改，在修改的同時將之前的頁放回freeList，最后更新meta page，更新完成會后持久化各個節點。

meta

Page1, Page2都被作為META_PAGE, 其原因是可用于人工backup。

實際操作meta page的時候，會按照txid依次使用兩個page，這樣在事務的進行中，這兩個page可以互為備份

BoltDB提供了一個Backup的接口, 使用這個接口后, 會將整個數據庫文件, 重新拷貝一份。

bacth操作

boltdb 不支持多個寫事務同時執行，在創建寫事務的時候會加上鎖，不過 boltdb 提供了 db.Batch():

當多個 goroutine 同時調用時，會將多個寫事務合并為一個大的寫事務執行。若其中某個事務執行失敗，其余的事務會重新執行，所以要求事務是冪等的。

事務

Bolt中的事務類Tx代表具體的事務。

每次事務開始的時候（創建Tx類）的時候，創建rootBucket_，通過meta進行初始化

寫事務需要將事務id加一。DB類中的鎖保證同一時間只有一個寫事務。讀寫事務通過讀寫鎖進行并發控制。

原子性（Atomicity）

修改事務在事務開始時拷貝metadata

使用COW操作，所有的修改操作都在內存中完成，不會影響到數據庫文件。但是每次update都要重寫root到實際node的所有頁，包括meta，meta page寫入成功事務才算更新成功。如果任何一步寫入失敗，直接丟掉freelist中該事務分配的pageid，重新載入freelist即可。

一致性（Consistency）

寫事務只有在metadata成功寫入才算事務成功執行

隔離性（Isolation）

boltdb 支持多個讀事務與一個寫事務同時執行（拓寬了mysql讀寫鎖的定義），寫事務提交時會釋放舊的 page，分配新的 page，只要確保分配的新 page 不會是其他讀事務使用到的就能實現 Isolation。

在寫事務提交時，釋放的老 page 有可能還會被其他讀事務訪問到，不能立即用于下次分配，所以放在 freelist.pending 中， 只有確保沒有讀事務會用到時，才將相應的 pending page 放入 freelist.ids 中用于分配:

• freelist.pending: 維護了每個寫事務釋放的 page id。因為寫事務開始時會拷貝一份meta，因此只要pending不被刪除，原來的數據就可以一直被訪問到。
• freelist.ids: 維護了可以用于分配的 page id。

每個事務都有一個 txid，db.meta.txid 保存了最大的已提交的寫事務 id:

• 讀事務: txid == db.meta.txid。
• 寫事務：txid == db.meta.txid + 1。

當寫事務成功提交時，會更新 metadata，也就更新了 db.meta.txid。

txid 相當于版本號，只有低版本的讀事務才有可能訪問高版本寫事務釋放的 node，當沒有讀事務的 txid 比該寫事務的 txid 小時，就能釋放 pending page 用于分配。

持久性（Durability）

使用兩個meta page保證了一定的容錯性，通過checksum校驗數據完整性。

參考鏈接

boltdb 1.3.0實現分析（一）

BoltDB模型與實現

boltdb 源碼分析

boltdb源碼閱讀

總結

以上是生活随笔為你收集整理的BoltDB 源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。