07. 空闲列表：重用页面

由于我们的B树是不可变的，键值存储（KV store）的每次更新都会在路径上创建新节点，而不是更新现有节点，这就导致一些节点从最新版本无法访问到。我们需要重用这些旧版本中无法访问的节点，否则数据库文件会无限增长。

7.1 设计空闲列表

为了重用这些页面，我们将添加一个持久化的空闲列表来跟踪未使用的页面。更新操作在追加新页面之前会从列表中重用页面，并且当前版本中未使用的页面会被添加到列表中。

这个列表用作栈（后进先出），每次更新操作都可以从列表顶部移除页面并添加新页面。

//  列表中的项目数量
func (fl *FreeList) Total() int
//  获取第n个指针
func (fl *FreeList) Get(topn int) uint64
//  移除popn个指针并添加一些新指针
func (fl *FreeList) Update(popn int, freed []uint64)

和我们的B树一样，空闲列表也是不可变的。每个节点包含：

1. 多个指向未使用页面的指针。
2. 指向下一个节点的链接。
3. 列表中项目的总数。这仅适用于头节点。

|   node1   |      |   node2   |      |   node3   |
+-----------+     +-----------+     +-----------+
|  total=xxx  |      |            |      |            |
|   next=yyy | ==> |   next=qqq  | ==> |   next=eee |  ==> . . .
|   size=zzz |       |   size=ppp |       |   size=rrr  |
|   pointers |       |   pointers |       |   pointers |

节点格式：

| type | size | total | next |   pointers |
|  2B   |  2B  |   8B  |  8B  | size * 8B  |

const BNODE_FREE_LIST = 3
const FREE_LIST_HEADER = 4 + 8 + 8
const FREE_LIST_CAP = (BTREE_PAGE_SIZE - FREE_LIST_HEADER) / 8

用于访问列表节点的函数：

func flnSize(node BNode) int
func flnNext(node BNode) uint64
func flnPtr(node BNode, idx int)
func flnSetPtr(node BNode, idx int, ptr uint64)
func flnSetHeader(node BNode, size uint16, next uint64)
func flnSetTotal(node BNode, total uint64)

7.2 空闲列表数据类型

FreeList类型由头节点指针和管理磁盘页面的回调函数组成。

type FreeList struct {
    head uint64
    //  用于管理磁盘页面的回调函数
    get func(uint64) BNode  //  解引用指针
    new func(BNode) uint64  //  追加新页面
    use func(uint64, BNode)  //  重用页面
}

这些回调函数与B树的不同，因为列表使用的页面由列表自身管理。

• new回调函数仅用于追加新页面，因为空闲列表必须重用自身的页面。
• 没有del回调函数，因为空闲列表会将未使用的页面添加到自身。
• use回调函数记录对重用页面的待处理更新。

type BTree struct {
    //  指针（非零的页号）
    root uint64
    //  用于管理磁盘页面的回调函数
    get func(uint64) BNode //  解引用指针
    new func(BNode) uint64 //  分配新页面
    del func(uint64)       //  释放页面
}

7.3 空闲列表的实现

从列表中获取第n个项目只是简单的列表遍历。

func (fl *FreeList) Get(topn int) uint64 {
    assert(0 <= topn && topn < fl.Total())
    node := fl.get(fl.head)
    for flnSize(node) <= topn {
        topn -= flnSize(node)
        next := flnNext(node)
        assert(next != 0)
        node = fl.get(next)
    }
    return flnPtr(node, flnSize(node)-topn-1)
}

更新列表比较复杂。它首先从列表中移除popn个项目，然后将释放的页面添加到列表中，这可以分为三个阶段：

1. 如果头节点的项目数大于popn，则移除该节点。该节点本身稍后会被添加到列表中。重复此步骤，直到无法再进行。
2. 我们可能需要从列表中移除一些项目，并可能向列表中添加一些新项目。更新列表头需要新页面，新页面应从列表自身的项目中重用。逐个从列表中弹出项目，直到有足够的页面用于下一阶段。
3. 通过添加新节点来修改列表。

//  移除popn个指针并添加一些新指针
func (fl *FreeList) Update(popn int, freed []uint64) {
    assert(popn <= fl.Total())
    if popn == 0 && len(freed) == 0 {
        return  //  无需操作
    }

    //  准备构建新列表
    total := fl.Total()
    reuse := []uint64{}
    for fl.head != 0 && len(reuse)*FREE_LIST_CAP < len(freed) {
        node := fl.get(fl.head)
        freed = append(freed, fl.head)  //  回收节点本身
        if popn >= flnSize(node) {
            //  阶段1
            //  移除该节点中的所有指针
            popn -= flnSize(node)
        } else {
            //  阶段2:
            //  移除一些指针
            remain := flnSize(node) - popn
            popn = 0
            //  从空闲列表本身重用指针
            for remain > 0 && len(reuse)*FREE_LIST_CAP < len(freed)+remain {
                remain--
                reuse = append(reuse, flnPtr(node, remain))
            }
            //  将节点中的剩余指针移动到freed列表
            for i := 0; i < remain; i++ {
                freed = append(freed, flnPtr(node, i))
            }
        }
        //  丢弃当前节点并移动到下一个节点
        total -= flnSize(node)
        fl.head = flnNext(node)
    }
    assert(len(reuse)*FREE_LIST_CAP >= len(freed) || fl.head == 0)

    //  阶段3:  在列表开头添加新节点
    flPush(fl, freed, reuse)

    //  完成
    flnSetTotal(fl.get(fl.head), uint64(total+len(freed)))
}

func flPush(fl *FreeList, freed []uint64, reuse []uint64) {
    for len(freed) > 0 {
        new := BNode{make([]byte, BTREE_PAGE_SIZE)}

        //  构建一个新节点
        size := len(freed)
        if size > FREE_LIST_CAP {
            size = FREE_LIST_CAP
        }
        flnSetHeader(new, uint16(size), fl.head)
        for i, ptr := range freed[:size] {
            flnSetPtr(new, i, ptr)
        }
        freed = freed[size:]

        if len(reuse) > 0 {
            //  从列表中重用一个指针
            fl.head, reuse = reuse[0], reuse[1:]
            fl.use(fl.head, new)
        } else {
            //  或者追加一个页面来存储新节点
            fl.head = fl.new(new)
        }
    }
    assert(len(reuse) == 0)
}

7.4 管理磁盘页面

步骤1：修改数据结构

数据结构被修改了。临时页面保存在一个以分配的页号为键的映射中。被移除的页号也记录在其中。

type KV struct {
    //  省略部分代码...
    page struct {
        flushed uint64 //  以页数表示的数据库大小
        nfree   int    //  从空闲列表获取的页面数量
        nappend int    //  要追加的页面数量
        //  新分配或释放的页面，以指针为键。
        //  nil值表示已释放的页面。
        updates map[uint64][]byte
    }
}

步骤2：B树的页面管理

pageGet函数被修改，使其也能返回临时页面，因为空闲列表代码依赖此行为。

//  B树和空闲列表的回调函数，解引用指针。
func (db *KV) pageGet(ptr uint64) BNode {
    if page, ok := db.page.updates[ptr]; ok {
        assert(page != nil)
        return BNode{page}  //  对于新页面
    }
    return pageGetMapped(db, ptr)  //  对于已写入的页面
}

func pageGetMapped(db *KV, 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")
}

分配B树页面的函数被修改为首先从空闲列表中重用页面。

//  B树的回调函数，分配新页面。
func (db *KV) pageNew(node BNode) uint64 {
    assert(len(node.data) <= BTREE_PAGE_SIZE)
    ptr := uint64(0)
    if db.page.nfree < db.free.Total() {
        //  重用已释放的页面
        ptr = db.free.Get(db.page.nfree)
        db.page.nfree++
    } else {
        //  追加新页面
        ptr = db.page.flushed + uint64(db.page.nappend)
        db.page.nappend++
    }
    db.page.updates[ptr] = node.data
    return ptr
}

被移除的页面会被标记，以便稍后更新空闲列表。

//  B树的回调函数，释放页面。
func (db *KV) pageDel(ptr uint64) {
    db.page.updates[ptr] = nil
}

步骤3：空闲列表的页面管理

空闲列表追加新页面和重用页面的回调函数：

//  空闲列表的回调函数，分配新页面。
func (db *KV) pageAppend(node BNode) uint64 {
    assert(len(node.data) <= BTREE_PAGE_SIZE)
    ptr := db.page.flushed + uint64(db.page.nappend)
    db.page.nappend++
    db.page.updates[ptr] = node.data
    return ptr
}

//  空闲列表的回调函数，重用页面。
func (db *KV) pageUse(ptr uint64, node BNode) {
    db.page.updates[ptr] = node.data
}

步骤4：更新空闲列表

在扩展文件并将页面写入磁盘之前，我们必须先更新空闲列表，因为它也会产生待处理的写入操作。

func writePages(db *KV) error {
    //  更新空闲列表
    freed := []uint64{}
    for ptr, page := range db.page.updates {
        if page == nil {
            freed = append(freed, ptr)
        }
    }
    db.free.Update(db.page.nfree, freed)

    //  如果需要，扩展文件和内存映射
    //  省略部分代码...

    //  将页面复制到文件
    for ptr, page := range db.page.updates {
        if page != nil {
            copy(pageGetMapped(db, ptr).data, page)
        }
    }
    return nil
}

列表头指针被添加到主页面：

| sig | btree_root | page_used | free_list |
| 16B  |     8B     |     8B      |     8B    |

步骤5：完成

键值存储完成了。它是持久化的并且具有抗崩溃能力，尽管只能顺序访问。

本专栏第二部分还有更多内容要学习：

• 在键值存储之上构建关系型数据库。
• 数据库的并发访问和事务处理。