区块的持久化之BoltDB(一)

在前面文章中，我们介绍说Bitcoin网络通过PoW共识以及选择最长链为主链来逐步达到共识，使得网络中各节点本地的区块链最终保持一致；同时，交易时节点会根据解锁脚本与锁定脚本来保证安全支付。那么，区块是如何在节点之间“传播”，又如何被验证的？它在节点上又是如何被存储的呢？这些问题是在共识与安全之后，Bitcoin网络实现上的又一核心问题。从本文开始，笔者将通过展示Btcd (Bitcoin节点的Golong实现) 的源码，来和大家一起探索这些问题。之所以选择Btcd，而不是Bitcoin Core (C++) 实现，是为了避免C++(特别是C11)的一些语法给源码阅读带来的一些障碍；Go因其语法与代码语句比较简洁，可以让大家更多地专注于Btcd的实现，而不至于陷入语法及可能存在的繁琐实现上。

在介绍Bitcoin网络中的网络协议时，不可避免地会涉及到区块的处理、存储与读取，所以我们先开始介绍区块存储相关的话题。Bticoin Core与Btcd均采用了levelDB作为存储区块的数据库，它们都是K-V型数据库。然而，levelDB不支持transaction，故Btcd在levelDB之上封装了ffldb，实现了transaction和针对Block存储的封装。ffldb中关于DB、Bucket、Transaction的概念和接口定义基本沿袭了BoltDB的定义，为了更好地了解ffldb，本文将先介绍BoltDB。同时，Bitcoin钱包的Go实现btcwallet也是用BoltDB作为其底层数据库的。

“Bolt was originally a port of LMDB so it is architecturally similar. Both use a B+tree, have ACID semantics with fully serializable transactions, and support lock-free MVCC using a single writer and multiple readers.”

“Bolt is a relatively small code base (<3KLOC) for an embedded, serializable, transactional key/value database so it can be a good starting point for people interested in how databases work.”

正如Bolt自己所说的那样，它确实是一个精干的K/V数据库，我们将通过对Bolt的源码分析来了解数据库的工作机制。

从gitbhub上clone完BoltDB的代码后，我们可以发现，它主要包含下列文件:

• bucket.go, cursor.go, db.go, freelist.go, node.go, page.go, tx.go --- 这些文件是BoltDB实现的核心，分别定义和实现了Transaction、Bucket及B+ Tree等机制，也是我们重点阅读与分析的代码。
• bucket_test.go, cursor_test.go,db_test.go, freelist_test.go, node_test.go, page_test.go, quick_test.go, simulation_test.go, tx_test.go --- 对应的测试文件。
• bolt_linux.go, bolt_openbsd.go, bolt_ppc.go, bolt_unix.go, bolt_unix_solaris.go, bolt_windows.go, boltsync_unix.go --- 这些文件封装了对应平台下的mmap、fdatasync、flock相关的系统调用。BoltDB只生成一个数据库文件，并通过mmap对文件进行只读映射，写时通过write和fdatasync系统调用修改文件。Go以文件名加"_"，再加"GOOS"或者“GOARCH”的形式或者源文件起始位置添加“// +build”的形式实现不同平台的条件编译。
• bolt_386.go, bolt_amd64.go, bolt_arm.go, bolt_arm64.go, bolt_s390x.go, bolt_ppc.go, bolt_ppc64.go, bolt_ppc64le.go --- 这些文件定义了对应ABI平台下mmap映射文件大小的上限maxMapSize、分配数组的最大长度maxAllocSize以及是否支持非对齐内存访问(unaligned memory access)。
• errors.go --- 定义了BoltDB的错误类型及对应的提示字符。
• doc.go - 包bolt的说明文档。

在剖析BoltDB之前，我们先来看看如何使用它，典型的调用方法如下：

func main() {
    // Open the database.
    db, err := bolt.Open(“test.db”, 0666, nil)
    if err != nil {
        log.Fatal(err)
    }
    defer os.Remove(db.Path())

    // Start a write transaction.
    if err := db.Update(func(tx *bolt.Tx) error {
        // Create a bucket.
        b, err := tx.CreateBucket([]byte("widgets"))
        if err != nil {
            return err
        }

        // Set the value "bar" for the key "foo".
        if err := b.Put([]byte("foo"), []byte("bar")); err != nil {
            return err
        }
        return nil
    }); err != nil {
        log.Fatal(err)
    }

    // Read value back in a different read-only transaction.
    if err := db.View(func(tx *bolt.Tx) error {
        value := tx.Bucket([]byte("widgets")).Get([]byte("foo"))
        return nil
    }); err != nil {
        log.Fatal(err)
    }

    // Close database to release file lock.
    if err := db.Close(); err != nil {
        log.Fatal(err)
    }
}

上述代码段首先调用Open()方法打开或者创建指定文件并得到了DB对象db，然后通过db.Update()方法写数据库，利用Update方法内创建并返回的读写Tx对象创建了一个名为"widgets"的Bucket，并在这个Bucket中添加了一对K/V记录(foo, bar)，随后，通过db.View()方法读数据库，利用View方法内创建并返回的只读Tx对象查找名为widgets的Bucket中的Key为"foo"的记录，最后关闭数据库。在这个典型的调用示例中，涉及到了数据库文件的打开(创建)、关闭，Bucket的创建、查找，K/V记录的读写等，那BoltDB内部的数据库文件到底是什么样子的，如何对它进行读写，为什么需要通过Transaction去访问数据库，Bucket到底是什么，它们是如何组织K/V记录的，Bucket或者K/V是如何创建，如何查找的呢？我们将通过阅读其源码逐步揭示这些疑问。

我们先从Open()方法入手来看看DB是如何创建的：

//boltdb/bolt/db.go

// Open creates and opens a database at the given path.
// If the file does not exist then it will be created automatically.
// Passing in nil options will cause Bolt to open the database with the default options.
func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
    var db = &DB{opened: true}

    ......

    // Open data file and separate sync handler for metadata writes.
    db.path = path
    var err error
    if db.file, err = os.OpenFile(db.path, flag|os.O_CREATE, mode); err != nil {
        _ = db.close()
        return nil, err
    }

    // Lock file so that other processes using Bolt in read-write mode cannot
    // use the database  at the same time. This would cause corruption since
    // the two processes would write meta pages and free pages separately.
    // The database file is locked exclusively (only one process can grab the lock)
    // if !options.ReadOnly.
    // The database file is locked using the shared lock (more than one process may
    // hold a lock at the same time) otherwise (options.ReadOnly is set).
    if err := flock(db, mode, !db.readOnly, options.Timeout); err != nil {
        _ = db.close()
        return nil, err
    }

    // Default values for test hooks
    db.ops.writeAt = db.file.WriteAt

    // Initialize the database if it doesn't exist.
    if info, err := db.file.Stat(); err != nil {
        return nil, err
    } else if info.Size() == 0 {
        // Initialize new files with meta pages.
        if err := db.init(); err != nil {
            return nil, err
        }
    } else {
        // Read the first meta page to determine the page size.
        var buf [0x1000]byte
        if _, err := db.file.ReadAt(buf[:], 0); err == nil {
            m := db.pageInBuffer(buf[:], 0).meta()
            if err := m.validate(); err != nil {
                // If we can't read the page size, we can assume it's the same
                // as the OS -- since that's how the page size was chosen in the
                // first place.
                //
                // If the first page is invalid and this OS uses a different
                // page size than what the database was created with then we
                // are out of luck and cannot access the database.
                db.pageSize = os.Getpagesize()
            } else {
                db.pageSize = int(m.pageSize)
            }
        }
    }

    ......

    // Memory map the data file.
    if err := db.mmap(options.InitialMmapSize); err != nil {
        _ = db.close()
        return nil, err
    }


    // Read in the freelist.
    db.freelist = newFreelist()
    db.freelist.read(db.page(db.meta().freelist))

    // Mark the database as opened and return.
    return db, nil
}

可以看出，Open()执行的主要步骤为:

1. 创建DB对象，并将其状态设为opened；
2. 打开或创建文件对象
3. 根据Open参数ReadOnly决定是否以进程独占的方式打开文件，如果以只读方式访问数据库文件，则不同进程可以共享读该文件；如果以读写方式访问数据库文件，则文件锁将被独占，其他进程无法同时以读写方式访问该数据库文件，这是为了防止多个进程同时修改文件；
4. 初始化写文件函数；
5. 读数据库文件，如果文件大小为零，则对db进行初始化；如果大小不为零，则试图读取前4K个字节来确定当前数据库的pageSize。随后我们分析db的初始化时，会看到db的文件格式，可以进一步理解这里的逻辑；
6. 通过mmap对打开的数据库文件进行内存映射，并初始化db对象中的meta指针；
7. 读数据库文件中的freelist页，并初始化db对象中的freelist列表。freelist列表中记录着数据库文件中的空闲页。

这些步骤中比较重要的是第5步中的db.init()调用和第6步中的db.mmap()调用，我们分别来看下它们的代码:

//boltdb/bolt/db.go

// init creates a new database file and initializes its meta pages.
func (db *DB) init() error {
    // Set the page size to the OS page size.
    db.pageSize = os.Getpagesize()

    // Create two meta pages on a buffer.
    buf := make([]byte, db.pageSize*4)
    for i := 0; i < 2; i++ {
        p := db.pageInBuffer(buf[:], pgid(i))
        p.id = pgid(i)
        p.flags = metaPageFlag

        // Initialize the meta page.
        m := p.meta()
        m.magic = magic
        m.version = version
        m.pageSize = uint32(db.pageSize)
        m.freelist = 2
        m.root = bucket{root: 3}
        m.pgid = 4
        m.txid = txid(i)
        m.checksum = m.sum64()
    }

    // Write an empty freelist at page 3.
    p := db.pageInBuffer(buf[:], pgid(2))
    p.id = pgid(2)
    p.flags = freelistPageFlag
    p.count = 0

    // Write an empty leaf page at page 4.
    p = db.pageInBuffer(buf[:], pgid(3))
    p.id = pgid(3)
    p.flags = leafPageFlag
    p.count = 0

    // Write the buffer to our data file.
    if _, err := db.ops.writeAt(buf, 0); err != nil {
        return err
    }
    if err := fdatasync(db); err != nil {
        return err
    }

    return nil
}

在init()中:

1. 先分配了4个page大小的buffer；
2. 将第0页和第1页初始化meta页，并指定root bucket的page id为3，存freelist记录的page id为2，当前数据库总页数为4，同时txid分别为0和1。我们将在随后对meta的介绍中说明各个字段的意义；
3. 将第2页初始化为freelist页，即freelist的记录将会存在第2页；
4. 将第3页初始化为一个空页，它可以用来写入K/V记录，请注意它必须是B+ Tree中的叶子节点；
5. 最后，调用写文件函数将buffer中的数据写入文件，同时通过fdatasync()调用将内核中磁盘页缓冲立即写入磁盘。

init()方法创建了一个空的数据库，通过它，我们可以了解boltdb数据库文件的基本格式：数据库文件以页为基本单位，一个数据库文件由若干页组成。一个页的大小是由当前OS决定的，即通过os.GetpageSize()来决定，对于32位系统，它的值一般为4K字节。一个Boltdb数据库文件的前两页是meta页，第三页是记录freelist的页面，事实上，经过若干次读写后，freelist页并不一定会存在第三页，也可能不止一页，我们后面再详细介绍，第4页及后续各页则是用于存储K/V的页面。init()执行完毕后，新创建的数据库文件大小将是16K字节。随后Open()方法便调用db.mmap()方法对该文件进行映射:

//boltdb/bolt/db.go

// mmap opens the underlying memory-mapped file and initializes the meta references.
// minsz is the minimum size that the new mmap can be.
func (db *DB) mmap(minsz int) error {
    db.mmaplock.Lock()
    defer db.mmaplock.Unlock()

    info, err := db.file.Stat()
    if err != nil {
        return fmt.Errorf("mmap stat error: %s", err)
    } else if int(info.Size()) < db.pageSize*2 {
        return fmt.Errorf("file size too small")
    }

    // Ensure the size is at least the minimum size.
    var size = int(info.Size())
    if size < minsz {
        size = minsz
    }
    size, err = db.mmapSize(size)
    if err != nil {
        return err
    }

    // Dereference all mmap references before unmapping.
    if db.rwtx != nil {
        db.rwtx.root.dereference()
    }

    // Unmap existing data before continuing.
    if err := db.munmap(); err != nil {
        return err
    }

    // Memory-map the data file as a byte slice.
    if err := mmap(db, size); err != nil {
        return err
    }

    // Save references to the meta pages.
    db.meta0 = db.page(0).meta()
    db.meta1 = db.page(1).meta()

    // Validate the meta pages. We only return an error if both meta pages fail
    // validation, since meta0 failing validation means that it wasn't saved
    // properly -- but we can recover using meta1. And vice-versa.
    err0 := db.meta0.validate()
    err1 := db.meta1.validate()
    if err0 != nil && err1 != nil {
        return err0
    }

    return nil
}

在db.mmap()中:

1. 获取db对象的mmaplock，这里大家可以先忽略它，我们后面再专门介绍DB对象中的锁；
2. 通过db.mmapSize()确定mmap映射文件的长度，因为mmap系统调用时要指定映射文件的起始偏移和长度，即确定映射文件的范围；
3. 通过munmap()将老的内存映射unmap；
4. 通过mmap将文件映射到内存，完成后可以通过db.data来读文件内容了;
5. 读数据库文件的第0页和第1页来初始化db.meta0和db.meta1，前面init()方法中我们了解到db的第0面和第1页确实写入的是meta；
6. 对meta数据进行校验。

db.mmapSize()的实现比较简单，这里不再贴出其代码，它的思想是：映射文件的最小size为32KB，当文件小于1G时，它的大小以加倍的方式增长，当文件大于1G时，每次remmap增加大小时，是以1G为单位增长的。前述init()调用完毕后，文件大小是16KB，即db.mmapSize的传入参数是16384，由于mmapSize()限制最小映射文件大小是32768，故它返回的size值为32768，在随后的mmap()调用中第二个传入参数便是32768，即32K。但此时文件大小才16KB，这个时候映射32KB的文件会不会有问题？window平台和linux平台对此有不同的处理:

//boltdb/bolt/bolt_windows.go

// mmap memory maps a DB's data file.
// Based on: https://github.com/edsrzf/mmap-go
func mmap(db *DB, sz int) error {
    if !db.readOnly {
        // Truncate the database to the size of the mmap.
        if err := db.file.Truncate(int64(sz)); err != nil {
            return fmt.Errorf("truncate: %s", err)
        }
    }

    // Open a file mapping handle.
    sizelo := uint32(sz >> 32)
    sizehi := uint32(sz) & 0xffffffff
    h, errno := syscall.CreateFileMapping(syscall.Handle(db.file.Fd()), nil, syscall.PAGE_READONLY, sizelo, sizehi, nil)
    ......

    // Create the memory map.
    addr, errno := syscall.MapViewOfFile(h, syscall.FILE_MAP_READ, 0, 0, uintptr(sz))

    ......

    // Convert to a byte array.
    db.data = ((*[maxMapSize]byte)(unsafe.Pointer(addr)))
    db.datasz = sz

    return nil
}

在针对windows平台的实现中，在进行mmap映射之前都会通过ftruncate系统调用将文件大小调整为待映射的大小，而在linux/unix平台的实现中是直接进行mmap调用的：

//boltdb/bolt/bolt_unix.go

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

    ......
 
    // 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
}

我们知道，mmap也是以页为单位进行映射的，如果文件大小不是页大小的整数倍，映射的最后一页肯定超过了文件结尾处，这个时候超过部分的内存会初始化为0，对其的写操作不会写入文件。但如果映射的内存范围超过了文件大小，且超出范围大于4k，那对于超过文件所在最后一页地址空间的访问将引发异常。比如我们这里文件实际大小是16K，但我们要映射32K到进程地址空间中，那对超过16K部分的内存访问将会引发异常。实际上，我们前面分析过，Boltdb通过mmap进行了只读映射，故不会存在通过内存映射写文件的问题，同时，对db.data(即映射的内存区域)的访问是通过pgid来访问的，当前database文件里实际包含多少个page是记录在meta中的，每次通过db.data来读取一页时，boltdb均会作超限判断的，所以不会存在对超过当前文件实际页数以外的区域访问的情况。正如我们在db.init()中看到的，此时meta中记录的pgid为4，即当前数据库文件总的page数为4，故即使mmap映射长度为32KB，通过pgid索引也不会访问到16KB以外的地址空间。这个我们在后面的代码分析中会再次提及，这里可以暂时略过。需要说明的是，当对数据库进行写操作时，如果要增加文件大小，针对linux/unix系统，boltdb也会通过ftruncate系统调用增加文件大小，但是它并不是为了避免访问映射区域发生异常的问题，因为boltdb写文件不是通过mmap，而是直接通过fwrite写文件。强调一下，boltdb对数据库的读操作是通过读mmap内存映射区完成的；而写操作是通过文件fseek及fwrite系统调用完成的。

通过对上面db.mmapSize及mmap的分析，db.mmap()调用完成后，新创建的数据库文件在windows平台上将是32KB，而linux/unix平台仍然是16KB。这时的数据库文件的样子是:

这是一个模糊的样子，每一页内部的数据布局究竟是什么样的呢？ 我们在db.init()中接触过meta及page的初始化过程，我们可以先从page的实现入手，来看看一个page的格式，然后再来分析meta页包含哪些数据。

// boltdb/bolt/page.go

const (
    branchPageFlag   = 0x01
    leafPageFlag     = 0x02
    metaPageFlag     = 0x04
    freelistPageFlag = 0x10
)

......

type pgid uint64

type page struct {
    id       pgid
    flags    uint16
    count    uint16
    overflow uint32
    ptr      uintptr
}

上面是page的类型定义，它的各个字段意义如下:

• id: 页面id，如0, 1, 2，...，是从数据库文件内存映射中读取一页的索引值；
• flags: 页面类型，可以分为branchPageFlag、leafPageFlag、metaPageFlag和freelistPageFlag等，branchPageFlag和leafPageFlag分别对应B+ Tree中的内节点和叶子节点，比如上述看到的第4页(id为3)就被初始化为leafPage；
• count: 页面内存储的元素个数，只在branchPage或leafPage中有用，对应的元素分别为branchPageElement和leafPageElement；
• overflow: 当前页是否有后续页，如果有，overflow表示后续页的数量，如果没有，则它的值为0，主要用于记录连续多页；
• ptr：用于标记页头结尾或者页内存储数据的起始处，一个页的页头就是由上述id、flags、count和overflow构成。需要注意的是，ptr本身不是页头的组成部分，它不是页的一部分，也不被存于磁盘上。

一个page的格式如下图所示:

elements部分的格式根据不同的page类型而不同，我们先看看metaPage的格式，freeListPage的格式比较简单，读者可以自行分析，branchPageElement和leafPageElement与B+ Tree关系，我们将在后文详细介绍。

//boltdb/bolt/db.go

type meta struct {
    magic    uint32
    version  uint32
    pageSize uint32
    flags    uint32
    root     bucket
    freelist pgid
    pgid     pgid
    txid     txid
    checksum uint64
}

上面是meta的类型定义，它的各字段意义如下:

• magic: boltdb的magic number，为0xED0CDAED;
• version: boltdb文件格式的版本号，为2;
• pageSize：boltdb文件的页大小;
• flags: 保留字段，暂时未用到；
• root: boltdb根Bucket的头信息，后面介绍Bucket时再详细介绍；
• freelist: boltdb文件中存freelist的页号，freelist用来存空闲页面的页号；
• pgid: 简单理解为boltdb文件中总的页数，即最大页号加1。这个字段与BoltDB的MVCC实现有一定联系，我们将在后续文章中再进一步理解它;
• txid: 上一次写数据库的transactoin id，可以看作是当前boltdb的修改版本号，每次读写数据库时加1，只读时不改变；
• checksum: 上面各字段的64位FNV-1哈希校验。

为了进一步了解meta页是如果存储的，我们可以看看meta的write(*page)方法:

//boltdb/bolt/db.go

// write writes the meta onto a page.
func (m *meta) write(p *page) {
    ......

    // Page id is either going to be 0 or 1 which we can determine by the transaction ID.
    p.id = pgid(m.txid % 2)
    p.flags |= metaPageFlag

    // Calculate the checksum.
    m.checksum = m.sum64()

    m.copy(p.meta())
}

从上面的代码中可看到，meta信息在写入页框时，

1. 指定写入的页号为m.txid % 2，即第0或者第1页，这与我们之前看到的第0页或者第1页初始化为meta页是相符的。更重要的是，写入第0页还是第1页是由当前meta中的transction id决定的，若当前meta中的transaction id为偶数则写入第0页，若当前meta页的 transaction id为奇数则写入第1页。前面介绍说meta中的txid实际上可以看作是数据库的修改版本号，每次写时会增加1，也就是说每次写数据库后会交替更新meta页。如当前txid为10，它对应的meta存在第0页，当对数据库进行一次读写时，txid增加为11，写完后需要更新meta页，这时会将新的meta写入第1页，而不是覆盖原来的第0页，下次读写数据库时将会选择txid更大的meta页来提取meta信息。我们后面介绍读写数据库时会进一步介绍，这里先提一个问题供大家思考: boltdb为什么要维护两页meta(让我们称之为双meta)呢？
2. 将页面flags设定为metaPageFlag，指明为一个meta页面;
3. 将meta信息拷贝到页面p中缓存的相应位置，我们来看看这个位置是如何确定的:

//boltdb/bolt/page.go

// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
    return (*meta)(unsafe.Pointer(&p.ptr))
}

可以看到，meta信息被写入了页框的ptr处，即页框头的结尾处。了解了meta的详细信息及写入页框的机制后，我们就可以知道一个meta页面的磁盘布局情况了：

到此， 我们就了解了boltdb数据库文件的创建过程及其文件格式。boltdb是以页为单位存储的，并包含起始的两个meta页，一个(或者多个)页来存空闲页的页号及剩下的分支页(branchPage)和叶子页(leafPage)。在创建一个boltdb文件时，通过fwrite和fdatasync系统调用向磁盘写入32K或者16K的初始文件；在打开一个botldb文件时，用mmap系统调用创建只读内存映射，用来读取文件中各页数据。

我们提到的branchPage和leafPage的格式、Bucket、Transaction等与数据库的读写紧密相关，涉及到B+Tree中节点的合并、分裂及再平衡等机制，我们将在后续文章中陆续介绍。