06. 持久化到磁盘

上一章的B树数据结构可以轻松转存到磁盘上。让我们在此基础上构建一个简单的键值存储（KV store）。由于我们实现的B树是不可变的，所以我们将以追加的方式分配磁盘空间，磁盘空间的复用将在下一章讨论。

6.1 数据持久化方法

正如前面章节提到的，将数据持久化到磁盘不仅仅是把数据转存到文件中，还需要考虑以下几个方面：

1. 崩溃恢复（Crash recovery）：这包括数据库进程崩溃、操作系统崩溃和电源故障。重启后，数据库必须处于可用状态。
2. 持久性（Durability）：数据库成功响应后，所涉及的数据必须保证持久化，即使发生崩溃也是如此。换句话说，在响应客户端之前，数据就已经完成持久化。

有很多资料使用ACID术语（原子性atomicity、一致性consistency、隔离性isolation、持久性durability）来描述数据库，但这些概念并非相互独立，且难以解释，所以我们还是专注于实际示例吧。

1. 我们的B树具有不可变的特性：更新B树时不会触及B树的上一版本，这使得崩溃恢复变得简单——如果更新出错，我们可以直接恢复到上一版本。
2. 持久性通过Linux系统调用fsync来实现。通过write或mmap进行的常规文件输入输出（File IO）首先会进入页缓存，系统随后必须将页缓存刷新到磁盘。fsync系统调用会阻塞，直到所有脏页都被刷新。

如果更新出错，我们如何恢复到上一版本呢？我们可以将更新分为两个阶段：

1. 更新操作创建新节点，并将它们写入磁盘。
2. 每次更新都会创建一个新的根节点，我们需要将根节点的指针存储在某个地方。

第一阶段可能涉及将多个页面写入磁盘，这通常不是原子操作。但第二阶段只涉及一个指针，可以通过原子的单页面写入完成。这使得整个操作具有原子性——如果数据库崩溃，更新就不会发生。

第一阶段必须在第二阶段之前完成持久化，否则崩溃后，根指针可能会指向树的一个已损坏（部分持久化）的版本。两个阶段之间应该有一个fsync操作（作为屏障）。

并且在响应客户端之前，第二阶段也应该执行fsync操作。

6.2 基于内存映射（mmap）的输入输出

磁盘文件的内容可以通过mmap系统调用映射到一个虚拟地址。从这个地址读取数据会触发透明的磁盘输入输出，这与通过read系统调用读取文件是一样的，但无需用户空间缓冲区，也没有系统调用的开销。映射的地址是页缓存的代理，通过它修改数据与使用write系统调用是一样的。

mmap很方便，我们将在键值存储中使用它。不过，mmap的使用并非必不可少。

// 创建覆盖整个文件的初始内存映射。
func mmapInit(fp *os.File) (int, []byte, error) {
    fi, err := fp.Stat()
    if err != nil {
        return 0, nil, fmt.Errorf("stat: %w", err)
    }

    if fi.Size()%BTREE_PAGE_SIZE != 0 {
        return 0, nil, errors.New("File size is not a multiple of page size.")
    }

    mmapSize := 64 << 20
    assert(mmapSize%BTREE_PAGE_SIZE == 0)
    for mmapSize < int(fi.Size()) {
        mmapSize *= 2
    }
    // mmapSize 可以大于文件大小

    chunk, err := syscall.Mmap(
        int(fp.Fd()), 0, mmapSize,
        syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_SHARED,
    )
    if err != nil {
        return 0, nil, fmt.Errorf("mmap: %w", err)
    }

    return int(fi.Size()), chunk, nil
}

上述函数创建的初始映射至少与文件大小相同。映射的大小可以大于文件大小，超过文件末尾的范围是不可访问的（会触发SIGBUS信号），但文件稍后可以扩展。

随着文件的增长，我们可能需要扩展映射范围。用于扩展mmap范围的系统调用是mremap。遗憾的是，通过重新映射扩展范围时，我们可能无法保留起始地址。我们扩展映射的方法是使用多个映射——为溢出的文件范围创建一个新的映射。

type KV struct {
    Path string
    // 内部成员
    fp  *os.File
    tree BTree
    mmap struct {
        file   int      // 文件大小，可能大于数据库大小
        total  int     // mmap大小，可能大于文件大小
        chunks [][]byte // 多个mmap，可能不连续
    }
    page struct {
        flushed uint64   // 以页数表示的数据库大小
        temp    [][]byte // 新分配的页面
    }
}

// 通过添加新的映射来扩展mmap。
func extendMmap(db *KV, npages int) error {
    if db.mmap.total >= npages*BTREE_PAGE_SIZE {
        return nil
    }

    // 双倍地址空间
    chunk, err := syscall.Mmap(
        int(db.fp.Fd()), int64(db.mmap.total), db.mmap.total,
        syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_SHARED,
    )
    if err != nil {
        return fmt.Errorf("mmap: %w", err)
    }

    db.mmap.total += db.mmap.total
    db.mmap.chunks = append(db.mmap.chunks, chunk)
    return nil
}

新映射的大小呈指数级增长，这样我们就不必频繁调用mmap。

下面是我们从映射地址访问页面的方法。

// BTree的回调函数，解引用指针。
func (db *KV) pageGet(ptr uint64) BNode {
    start := uint64(0)
    for _, chunk := range db.mmap.chunks {
        end := start + uint64(len(chunk))/BTREE_PAGE_SIZE
        if ptr < end {
            offset := BTREE_PAGE_SIZE * (ptr - start)
            return BNode{chunk[offset : offset+BTREE_PAGE_SIZE]}
        }
        start = end
    }
    panic("bad ptr")
}

6.3 主页面

文件的第一页用于存储根节点的指针，我们称之为 “主页面”。分配新节点时需要知道页面总数，所以页面总数也存储在主页面中。

|     the_master_page     |  pages . . . |  tree_root  |  pages . . .  |
| btree_root | page_used |                 ^                  ^
|             |                       |                 |
+------------+----------------------+                 |
|                                         |
+---------------------------------------+

下面的函数在初始化数据库时读取主页面：

const DB_SIG = "BuildYourOwnDB05"

// 主页面格式。
// 它包含根节点的指针和其他重要信息。
//   |   sig   |   btree_root   |   page_used   |
//   |   16B   |            8B            |            8B          |
func masterLoad(db *KV) error {
    if db.mmap.file == 0 {
        // 空文件，首次写入时将创建主页面。
        db.page.flushed = 1 // 为主页面保留
        return nil
    }

    data := db.mmap.chunks[0]
    root := binary.LittleEndian.Uint64(data[16:])
    used := binary.LittleEndian.Uint64(data[24:])

    // 验证页面
    if!bytes.Equal([]byte(DB_SIG), data[:16]) {
        return errors.New("Bad signature.")
    }
    bad :=!(1 <= used && used <= uint64(db.mmap.file/BTREE_PAGE_SIZE))
    bad = bad ||!(0 <= root && root < used)
    if bad {
        return errors.New("Bad master page.")
    }

    db.tree.root = root
    db.page.flushed = used
    return nil
}

下面是更新主页面的函数。与读取代码不同，写入时它不使用映射地址。这是因为通过mmap修改页面不是原子操作。内核可能会在中途刷新页面，从而损坏磁盘文件，而不跨越页面边界的小写入操作则可以保证是原子的。

// 更新主页面。它必须是原子操作。
func masterStore(db *KV) error {
    var data [32]byte
    copy(data[:16], []byte(DB_SIG))
    binary.LittleEndian.PutUint64(data[16:], db.tree.root)
    binary.LittleEndian.PutUint64(data[24:], db.page.flushed)
    // 注意：通过mmap更新页面不是原子操作。
    // 使用pwrite()系统调用代替。
    _, err := db.fp.WriteAt(data[:], 0)
    if err != nil {
        return fmt.Errorf("write master page: %w", err)
    }
    return nil
}

6.4 分配磁盘页

在接下来的章节添加空闲列表之前，我们简单地将新页面追加到数据库的末尾。

新页面会暂时保留在内存中，直到之后（在可能扩展文件之后）被复制到文件中。

type KV struct {
    // 省略部分代码...
    page struct {
        flushed uint64   // 以页数表示的数据库大小
        temp    [][]byte // 新分配的页面
    }
}

//  B树的回调函数，用于分配新页面。
func (db *KV) pageNew(node BNode) uint64 {
    //  TODO:  重用已释放的页面
    assert(len(node.data) <= BTREE_PAGE_SIZE)
    ptr := db.page.flushed + uint64(len(db.page.temp))
    db.page.temp = append(db.page.temp, node.data)
    return ptr
}

//  B树的回调函数，用于释放页面。
func (db *KV) pageDel(uint64) {
    //  TODO:  实现此功能
}

在写入待处理页面之前，我们可能需要先扩展文件。对应的系统调用是fallocate。

//  将文件扩展到至少npages页。
func extendFile(db *KV, npages int) error {
    filePages := db.mmap.file / BTREE_PAGE_SIZE
    if filePages >= npages {
        return nil
    }

    for filePages < npages {
        //  文件大小呈指数增长，
        //  这样我们就不必每次更新都扩展文件。
        inc := filePages / 8
        if inc < 1 {
            inc = 1
        }
        filePages += inc
    }

    fileSize := filePages * BTREE_PAGE_SIZE
    err := syscall.Fallocate(int(db.fp.Fd()), 0, 0, int64(fileSize))
    if err != nil {
        return fmt.Errorf("fallocate: %w", err)
    }

    db.mmap.file = fileSize
    return nil
}

6.5 初始化数据库

将我们所做的内容整合起来。

func (db *KV) Open() error {
    //  打开或创建数据库文件
    fp, err := os.OpenFile(db.Path, os.O_RDWR|os.O_CREATE, 0644)
    if err != nil {
        return fmt.Errorf("OpenFile: %w", err)
    }
    db.fp = fp

    //  创建初始内存映射
    sz, chunk, err := mmapInit(db.fp)
    if err != nil {
        goto fail
    }
    db.mmap.file = sz
    db.mmap.total = len(chunk)
    db.mmap.chunks = [][]byte{chunk}

    //  B树回调函数
    db.tree.get = db.pageGet
    db.tree.new = db.pageNew
    db.tree.del = db.pageDel

    //  读取主页面
    err = masterLoad(db)
    if err != nil {
        goto fail
    }

    //  完成
    return nil

fail:
    db.Close()
    return fmt.Errorf("KV . Open: %w", err)
}

//  清理操作
func (db *KV) Close() {
    for _, chunk := range db.mmap.chunks {
        err := syscall.Munmap(chunk)
        assert(err == nil)
    }
    _ = db.fp.Close()
}

6.6 更新操作

与查询不同，更新操作必须在返回前将数据持久化。

//  读取数据库
func (db *KV) Get(key []byte) ([]byte, bool) {
    return db.tree.Get(key)
}

//  更新数据库
func (db *KV) Set(key []byte, val []byte) error {
    db.tree.Insert(key, val)
    return flushPages(db)
}

func (db *KV) Del(key []byte) (bool, error) {
    deleted := db.tree.Delete(key)
    return deleted, flushPages(db)
}

flushPages函数用于持久化新页面。

//  在更新后持久化新分配的页面
func flushPages(db *KV) error {
    if err := writePages(db); err != nil {
        return err
    }
    return syncPages(db)
}

如前所述，它分为两个阶段。

func writePages(db *KV) error {
    //  如果需要，扩展文件和内存映射
    npages := int(db.page.flushed) + len(db.page.temp)
    if err := extendFile(db, npages); err != nil {
        return err
    }
    if err := extendMmap(db, npages); err != nil {
        return err
    }

    //  将数据复制到文件
    for i, page := range db.page.temp {
        ptr := db.page.flushed + uint64(i)
        copy(db.pageGet(ptr).data, page)
    }
    return nil
}

fsync操作在这两个阶段之间以及之后执行。

func syncPages(db *KV) error {
    //  将数据刷新到磁盘。必须在更新主页面之前完成。
    if err := db.fp.Sync(); err != nil {
        return fmt.Errorf("fsync: %w", err)
    }
    db.page.flushed += uint64(len(db.page.temp))
    db.page.temp = db.page.temp[:0]

    //  更新并刷新主页面
    if err := masterStore(db); err != nil {
        return err
    }
    if err := db.fp.Sync(); err != nil {
        return fmt.Errorf("fsync: %w", err)
    }
    return nil
}

我们的键值存储（KV store）已经可以使用，但随着数据库的更新，文件不能无限增长。在下一章，我们将通过重用磁盘页面来完善键值存储。