前言

伟大的Linus曾说过下面的话:

“烂程序员关心的是代码。好程序员关心的是数据结构和它们之间的关系。”

以前的我在阅读开源代码时,经常过于痴迷于复杂的业务逻辑,而不能自拔。每每将仔细陷入一种痛苦万分却又无可奈何的境地,苦不堪言却也收获甚微。

随着年岁的增长,阅历的丰富,发现,阅读开源代码的目的不在于理清其复杂的业务逻辑,这没用,除非你真的在工作中需要使用它。

阅读此类代码,我们应该站在一种更高的角度,把握其框架,发现其设计和实现上的亮点,用于指导自己的工作。而这框架是什么,没错儿,数据结构。

数据结构如同人体的骨骼,支撑起了整个躯体,不能正确理解数据结构及其之间的联系,那么阅读代码便如盲人摸象,往往会一叶障目而不见泰山。

本博文我结合自己阅读BoltDB的经验来梳理其中的核心数据结构以及之间的关联,一方面提升自己,另外一方面最好能造福更多人。

BoltDB的数据结构设计

DB

DB代表了被打开的数据库实例。以后客户的基本所有操作都是围绕该数据结构展开,包括:为DB创建事务,事务的提交,事务回滚,读DB,更新DB等,除此之外还有一些用户可配置的可控制读写行为的参数。DB在BoltDB中的定义如下:

type DB struct {
    StrictMode bool
    NoSync bool
    NoGrowSync bool
    MmapFlags int
    MaxBatchDelay time.Duration
    AllocSize int

    path     string
    file     *os.File
    lockfile *os.File // windows only
    dataref  []byte   // mmap'ed readonly, write throws SEGV
    data     *[maxMapSize]byte
    datasz   int
    filesz   int // current on disk file size
    // meta0&meta1记录系统元数据
    meta0    *meta
    meta1    *meta
    pageSize int
    opened   bool
    // 存储DB上正在执行的事务, rwtx读写事务,txs只读事务
    rwtx     *Tx
    txs      []*Tx
    freelist *freelist
    stats    Stats

    pagePool sync.Pool

    batchMu sync.Mutex
    batch   *batch

    // 写并发控制锁
    rwlock   sync.Mutex  
    metalock sync.Mutex   
    mmaplock sync.RWMutex
    statlock sync.RWMutex

    ops struct {
        writeAt func(b []byte, off int64) (n int, err error)
    }

    readOnly bool
}

DB数据结构相对来说比较容易理解,不涉及太多底层内容,更多的只是一些逻辑概念的抽象,如事务等。我们无需作太深入探究。

Tx

Tx是BoltDB中的事务抽象,事务是数据库系统几个核心概念之一,其重要性自然不言而喻。BoltDB的几乎所有接口,如Update()、View()的内部实现都是首先创建事务,然后在事务上执行查询或者更新,最后根据结果决定事务是提交(commit)还是回滚(rollback)。

BoltDB支持读读并发,读写并发,但不支持写写并发。

type Tx struct {
    writable       bool
    managed        bool
    db             *DB
    meta           *meta
    root           Bucket
    pages          map[pgid]*page
    stats          TxStats
    commitHandlers []func()

    WriteFlag int
}

BoltDB中支持两种Tx,读Tx和RWTx,writeable作了区分。Tx的结构中最主要的可能就是root了,它记录了Tx内所有操作的查询路径的起点,root在Tx被创建出来的时候初始化,彼时root指向当前数据库系统的root(存储在数据库的meta page中),在Tx执行过程中可能会被修改(还记得我们前面描述过的COW技术吗)。该root是一个Bucket数据结构,会在下面描述。

Bucket

这可能是BoltDB中最重要也是最复杂的数据结构了。我们在前面花费了众多笔墨来描述该结构。

简单来说,它是为了将整个数据库划分成多个命名空间,不同的KV记录可被存储在特定的命名空间,可以参照关系型数据库的表。

而每个Bucket便是KV这种聚合在内存中的表现:

type Bucket struct {
    *bucket
    tx       *Tx               
    buckets  map[string]*Bucket
    page     *page              
    rootNode *node              
    nodes    map[pgid]*node  

    FillPercent float64
}

不要被Bucket简单的外表所欺骗了,虽然成员并不多,但是不容易理解:
bucket: 该Bucket在底层文件的位置信息,主要是该Bucket记录所在底层page的id
rootNode: 这是Bucket的关键,Bucket的主要作用还是用来安置KV记录,Bucket结构便通过rootNode来索引其内部的所有KV,我们在前面已经详细描述过Bucket的内部存储结构,而rootNode的类型node我们也将在下面仔细阐述;
page: 当Bucket是Inline时,page指向了该Bucket的KV存储的起始地址,当Bucket变成非Inline时,page就失去了其用武之地。

node

type node struct {
    bucket     *Bucket
    isLeaf     bool
    unbalanced bool
    spilled    bool
    key        []byte
    pgid       pgid
    parent     *node
    children   nodes
    inodes     inodes
}

Bucket的所有KV记录在内存中都是存储在node中,因此Bucket的rootNode也是一种node类型。每个node存储一部分KV记录,每个Bucket内的node组织成了一颗B树,Bucket的rootNode便是树根,在这棵树上,某些node是叶子节点(存储KV数据),而某些node则是中间节点,存储到叶子节点的索引。

浅谈BoltDB的数据结构设计

node作为KV的载体,一方面连接了Bucket,另外一方面连接了底层结构,可以说它应该是BoltDB中最为核心的数据结构了。

page

上面说完node,接下来就不得不说page了,因为它们的关系是如此紧密。node是内存中所有KV记录的载体,而page则是磁盘上KV记录的家。

type page struct {
    id       pgid
    flags    uint16
    count    uint16
    overflow uint32
    ptr      uintptr
}
  • id: page id
  • flags: page flag,如有meta page等
  • count: page上的KV记录数;
  • ptr: page实际内容存储区

因此,node和page他们有着密不可分的关系,node有从page加载KV记录的接口,也有将node的KV记录写入到page的接口。

// read initializes the node from a page.
func (n *node) read(p *page)

// write writes the items onto one or more pages.
func (n *node) write(p *page)

inode

这里的inode可不是文件系统里面所说的inode。这里的inode代表的是内存中的KV记录信息。前面说过,这些KV信息记录在node中,所以我们回顾一下node结构定义,会发现其中的inode数组。

type inode struct {
    flags uint32
    pgid  pgid
    key   []byte
    value []byte
}
  • flags: 对于索引节点(非leaf node中的KV),取值为
  • pgid:该inode对应的物理存储page id
  • key: KV记录的key
  • value: KV记录的value

leafPageElement

我们上面说了KV记录在内存中的结构,那自然它也有在磁盘上的存储结构,就是leafPageElement

type leafPageElement struct {
    flags uint32
    pos   uint32
    ksize uint32
    vsize uint32
}

只是多了一个pos,以记录该KV在page内的偏移,没什么难以理解的。

总结

我们上面罗列了这种种的数据结构,接下来我们用一张图来总结这几张数据结构的关系:

浅谈BoltDB的数据结构设计