Sepk

个人博客

0%

boltdb源码通读笔记

发表于 更新于 分类于 ， ， ，
本文字数： 8.4k 阅读时长 ≈ 8 分钟

Bolt 是一个完全由 go 写成的基于硬盘的 K/V 存储引擎，为了表示区分一般被称为 boltdb。对于一款存储引擎而言，boltdb 的源码非常短小精悍，包含测试代码仅有 17000 行左右。正是因为其体量比较小，boltdb 并不具备较为复杂的功能；在实现上，boltdb 主要借鉴了其他语言中的做法并将其改进，使之更加符合 go 语言的基础架构。

通读 boltdb 的代码，主要是为了学习作者是如何利用 go 语言的特性来实现数据库的，这是本文的重点内容。而 boltdb 的用法以及其中的基本概念，可以参考《自底向上分析 BoltDB 源码》。

各模块实现方式

首先介绍一下 boltdb 中各个模块的实现方式：

  • 数据库文件落盘：使用 mmap 读取数据库文件，使用 write 接口写回脏页；
  • 空闲页面管理：使用链表/哈希表进行管理，按需取出，不够时重新 mmap 映射；
  • 数据库文件 compact：使用写缓冲，重写数据库文件；
  • 内存硬盘之间页面大小保持一致，直接映射；
  • 无日志，事务提交时直接落盘，使用读写锁控制并发。

可以看到 boltdb 中的各个模块实现都是比较简单的，这也在一定程度上保障了其稳定性。boltdb 无日志的设计使得写写之间是禁止并发的，因此 boltdb 可以很轻松地实现可串行级别的事务隔离。同时这也导致 boltdb 的写入性能非常差，只适合多读少写的场景。另外，boltdb 直接使用了 mmap 来映射数据库文件，这在一方面避免了 go 中的 GC 保证了数据库的性能，但另一方面当数据库大小超过内存时，可能会导致内存页面频繁被置换从而影响性能。但在 go 语言中大量使用指针可能会导致 GC 问题，使用 mmap 映射相当于避免了内存 B+ 树页面的 GC 扫描，这在 go 语言限制下应该是一种比较好的设计。

mmap 映射

mmap 映射实现

boltdb 使用 mmap 系统调用的源码片段如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}

这部分内容很简单，将 mmap 映射获得的内存设置为只读，并且允许进程间共享；调用 madvise 将内存片段设置为随机读取模式，防止操作系统按照顺序读的方式来置换出内存页面。 最后，boltdb 将 mmap 获得的内存片段转换为了一个长度为maxMapSize的切片指针，这一个步骤主要是为了方便进行page、meta等数据结构的映射。设置切片长度为maxMapSize是为了能够方便地完成 Golang 中的 unsafe 转换，保证转换长度足够。

如果成功获得内存映射片段，boltdb 还会调用mlock尝试禁止页面置换，从而提升数据库读性能。

1
2
3
4
5
6
7
8
9
10
func (db *DB) mmap(minsz int) error {
	...
    if db.Mlock {
        // Don't allow swapping of data file
        if err := db.mlock(fileSize); err != nil {
            return err
        }
    }
    ...
}

虽然mlock调用会抛出 error，但是并不会影响数据库的正常处理流程。

boltdb 并没有使用 mmap 接口直接进行文件写入的操作，因为 mmap 的写入时机较为特殊，它不会立刻进行刷盘，而是等待内存页面被置换出时再进行刷盘，或者进程主动使用 madvise + msnyc 进行刷盘。这是因为操作系统并不确定进程是否会在未来的一段时间内再次对内存片段进行更新，因此采取惰性处理策略会更好。boltdb 中选择使用了writeAt接口进行文件写入。当一个写事务被提交时，它会将当前数据库文件中的所有脏页写回到硬盘中。

mmap 映射策略

随着数据库文件大小的增长，boltdb 从操作系统中获得的 mmap 内存大小可能会小于数据库文件的长度。这种情况发生时，boltdb 将会再次使用 mmap 来增加映射内存的长度。boltdb 每次进行内存映射时，映射的内存大小并不等于数据库文件的大小，而是根据一定策略来选择内存大小。选择映射内存大小的逻辑出现在 db.go 的mmapSize函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func (db *DB) mmapSize(size int) (int, error) {
	// Double the size from 32KB until 1GB.
	for i := uint(15); i <= 30; i++ {	// 数据库文件小于1GB时，每次映射的大小翻倍
		if size <= 1<<i {
			return 1 << i, nil
		}
	}
	// Verify the requested size is not above the maximum allowed.
    // maxMapSize == 0xFFFFFFFFFFFF
	if size > maxMapSize {
		return 0, fmt.Errorf("mmap too large")
	}
	// If larger than 1GB then grow by 1GB at a time.
	sz := int64(size)
    // maxMmapStep == 1 << 30
	if remainder := sz % int64(maxMmapStep); remainder > 0 {
		sz += int64(maxMmapStep) - remainder
	}
	// Ensure that the mmap size is a multiple of the page size.
	// This should always be true since we're incrementing in MBs.
	pageSize := int64(db.pageSize)
	if (sz % pageSize) != 0 {
		sz = ((sz / pageSize) + 1) * pageSize
	}
	// If we've exceeded the max size then only grow up to the max size.
	if sz > maxMapSize {
		sz = maxMapSize
	}
	return int(sz), nil
}

根据源码，我们可以得到 boltdb 中内存映射的策略具有两个阶段，即快速增长期与慢速增长期。当数据库文件小于 1GB 时，boltdb 的内存分配处于快速增长期，进行内存映射时会直接按照数据库文件大小向上取整为 2 的幂。当数据库文件大于 1GB 时，每一次进行内存映射时的内存大小较上一次增长 1GB。由于在慢速增长期，内存映射策略是步进的，可能会出现步进后的内存大小并不是页面大小(4 KB)的整数倍，这种情况下使用最后一个页面将会导致程序越界访问内存，导致程序崩溃；因此需要向上取整为页面的大小。

struct 零成本重建

boltdb 使用了直接映射的方式来完成一些数据结构的写入和重建，该方式并不会拷贝内存而是重新解释 unsafe pointer 来完成对象的重建，这些操作使用了 unsafe.go 中的接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func unsafeAdd(base unsafe.Pointer, offset uintptr) unsafe.Pointer {
    return unsafe.Pointer(uintptr(base) + offset)
}

func unsafeIndex(base unsafe.Pointer, offset uintptr, elemsz uintptr, n int) unsafe.Pointer {
    return unsafe.Pointer(uintptr(base) + offset + uintptr(n)*elemsz)
}

func unsafeByteSlice(base unsafe.Pointer, offset uintptr, i, j int) []byte {

    return (*[maxAllocSize]byte)(unsafeAdd(base, offset))[i:j:j]
}

// unsafeSlice modifies the data, len, and cap of a slice variable pointed to by
// the slice parameter.  This helper should be used over other direct
// manipulation of reflect.SliceHeader to prevent misuse, namely, converting
// from reflect.SliceHeader to a Go slice type.
func unsafeSlice(slice, data unsafe.Pointer, len int) {
    s := (*reflect.SliceHeader)(slice)
    s.Data = uintptr(data)
    s.Cap = len
    s.Len = len
}

该方法可以用来进行简单对象的转换，相当于进行了一次对象的引用，重建后的对象地址会发生改变，但对象内容中的各个子对象地址都不会发生改变；下面使用一个 demo 来演示该方法是如何工作的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type Foo struct {
	content1 int32
	content2 int32
}

func (d *Foo) unsafeByteSlice() []byte {

	return (*[unsafe.Sizeof(*d)]byte)(unsafe.Pointer(d))[0:unsafe.Sizeof(*d)]
}

func parseFromByteSlice(serialized []byte) *Foo {

	return (*Foo)(unsafe.Pointer(&serialized[0]))
}

func ObjectSerializedTest() {
	d := Foo{1, 2}

	now := time.Now()

	slice := d.unsafeByteSlice()
	d.content2 = 3

	dd := parseFromByteSlice(slice)
	println("time cost:", time.Since(now).Nanoseconds(), "ns")
	println("dd.content1:", dd.content1)
	println("dd.content2:", dd.content2)
	println("d address:", &d)
	println("dd address:", &dd)
	println("d content1 address:", &d.content1)
	println("dd content2 address:", &dd.content1)
}

demo 先获取对象 d 的内存片段，然后修改对象 dd 的值，再使用该内存片段重建对象，程序输出结果为：

1
2
3
4
5
6
7
time cost: 162 ns
dd.content1: 1
dd.content2: 3
d address: 0xc000062f38
dd address: 0xc000062f50
d content1 address: 0xc000062f38
dd content2 address: 0xc000062f38

可以看到，dd 与 d 两个对象的地址是不同的，但是 dd.content1 与 d.content1 地址是相同的；因此即使在进行映射后更改 d 中的值，也会造成 dd 的改变。运用此方法进行 struct -> slice -> struct 耗时仅为 162ns，主要耗时集中在类型转换上。

接口设计

由于 boltdb 内部使用了读写锁，为了对读写事务加以区分，并给予用户较高的自由度，boltdb 设计了如下接口：

1
2
3
4
5
6
7
8
// 只读事务
func (db *DB) View(fn func(*Tx) error) error
// 写事务
func (db *DB) Update(fn func(*Tx) error) error
// 批处理事务
func (db *DB) Batch(fn func(*Tx) error) error
// 原始事务接口
func (db *DB) Begin(writable bool) (*Tx, error)

在事务的开启阶段，就可以简单地对事务进行区分，更好地处理读写并行关系。

空闲页索引

boltdb 的设计中，并不会直接在 B+树上进行修改，而是会先分配出一块缓冲区，写入缓冲区后再 merge 到 B+树上，即 COW。这种策略能够实现多读一些的并行。写事务的内存分配是由如下代码片段来实现的，该代码主要具有两个部分的功能，一部分是尝试用内存池中获取或者直接分配出一块缓冲区用于写入，另一部分则是在 B+树中找出合适的写入位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func (db *DB) allocate(txid txid, count int) (*page, error) {
    // 分配用于 COW 的内存
    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)

    // 试图从当前 mmap 内存中找到可用的页
    if p.id = db.freelist.allocate(txid, count); p.id != 0 {
      return p, nil
    }

    // 如果未找到，说明数据库过大，需要调整 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)
      }
    }

    // 将之前的最后一页分配给事务（mmap 分配出的新页在该页之后）
    db.rwtx.meta.pgid += pgid(count)

    return p, nil
}

可以看到，freelist的功能只是为了调控当前事务需要再 B+树中写入的位置，而不直接管理内存。当事务需要写入时，必须分配一次内存，这样做的好处是不需要做内存池的管理了。当无法从freelist中获取可写的页时，代表当前 B+树已经无可用位置给事务写入，这并不代表当前 B+树已经写满了，可能是由于当前事务需要写入的数据量过大。具体如何去界定，是由不同的分配策略来决定的。

在 boltdb 中，使用freelist结构体来统一管理 mmap 获得的内存在当前时刻下的视图。该结构体只使用 pageid 来管理当前时刻的状态，但并不直接管理页面的内存，因为 boltdb 中使用的是 COW 机制，所有的写入操作并不会直接在 mmap 的内存上写入，而是先写入到其他内存上，等待写入完毕后再 merge 到 B+ 树中。这样是为了避免 mmap 的低效写入问题，并且更加具有安全性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type freelist struct {
    freelistType   FreelistType                // freelist type
    ids            []pgid                      // all free and available free page ids.
    allocs         map[pgid]txid               // mapping of txid that allocated a pgid.
    pending        map[txid]*txPending         // mapping of soon-to-be free page ids by tx.
    cache          map[pgid]struct{}           // fast lookup of all free and pending page ids.
    freemaps       map[uint64]pidSet           // key is the size of continuous pages(span), value is a set which contains the starting pgids of same size
    forwardMap     map[pgid]uint64             // key is start pgid, value is its span size
    backwardMap    map[pgid]uint64             // key is end pgid, value is its span size
    allocate       func(txid txid, n int) pgid // the freelist allocate func
    free_count     func() int                  // the function which gives you free page number
    mergeSpans     func(ids pgids)             // the mergeSpan func
    getFreePageIDs func() []pgid               // get free pgids func
    readIDs        func(pgids []pgid)          // readIDs func reads list of pages and init the freelist
}

freelist以不同的视角来记录每一个页面上的可用范围，并根据写事务所需要的范围来分配具体的页面。在 boltdb 的实现中，freelist具有 FreelistArrayType 和 FreelistMapType 两种分配策略，前者会使用线性查找的方式来查询一块可用的内存页，而后者则使用索引的方式来查找可用的内存范围。FreelistMapType 分配策略的性能要远好于 FreelistArrayType。其具体做法是在归还的过程中将邻接页中可用的内存区域进行“合并”，并且这一块区域的整体大小注册到 freemaps 数据结构中。这样在查询可用区域的时候就不需要进行遍历，而是采用哈希表的方式进行查询。具体的细节可以参考该设计的博客文章。

写入性能

归根结底，一个基于硬盘的数据库系统的性能瓶颈是硬盘的 IO 速度，在其他的数据库设计中，面对写入，都是先使用低成本的操作记录写入日志，然后再将写入内容搬运到具体的位置上，才能够获得较高的写入性能。而 boltdb 的设计中，并没有对写入操作进行任何的缓冲机制，而是直接将写入内容放入到硬盘中，这是其写入性能较低的根本原因。但是这种设计能够很简单地实现事务的串行，任何设计都有取舍，写入性能就是 boltdb 舍弃掉的东西。