avatar个人博客

从头实现数据库-7

Oct 31, 2023
因为这里的B树是不可变的，所以对KV存储的每一个更新都会在路径中创建新的节点，而不是更新当前的节点，使得一些节点无法从最新版本中到达。我们需要重用旧版本中这些无法访问的节点，否则，数据库文件将无限期地增长。

设计自由列表

为了重用这些页面，将添加一个持久的空闲列表来跟踪未使用的页面。更新操作在追加新页之前重用列表中的页，并将当前版本中未使用的页添加到列表中。
该列表用作堆栈(先到后出)，每个更新操作都可以从列表顶部删除和添加。
// number of items in the list
func (fl *FreeList) Total() int
// get the nth pointer
func (fl *FreeList) Get(topn int) uint64
// remove `popn` pointers and add some new pointers
func (fl *FreeList) Update(popn int, freed []uint64)
自由列表也像我们的B树一样是不可变的。每个节点包含：
  • 未使用页面的多个指针。
  • 下一个节点的链接。
  • 列表中的项目总数。这只适用于头节点。
|   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)

自由列表数据类型

FreeList类型由指向头节点的指针和用于管理磁盘页的回调组成。
type FreeList struct {
    head uint64
    // callbacks for managing on-disk pages
    get func(uint64) BNode  // dereference a pointer
    new func(BNode) uint64  // append a new page
    use func(uint64, BNode) // reuse a page
}
这些回调与B树不同，因为列表使用的页面是由列表本身管理的。
  • new 回调仅用于追加新页面，因为空闲列表必须重用自身的页面。
  • 没有del回调，因为空闲列表会将未使用的页面添加到它自己。
  • use回调将挂起的更新注册到重用页。
type BTree struct {
    // pointer (a nonzero page number)
    root uint64
    // callbacks for managing on-disk pages
    get func(uint64) BNode // dereference a pointer
    new func(BNode) uint64 // allocate a new page
    del func(uint64)       // deallocate a page
}

自由列表的实现

从列表中获取第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项，然后将free项添加到列表中，这可以分为3个阶段:
  • 如果头节点大于popn，则将其删除。节点本身将在稍后添加到列表中。重复此步骤，直到不再可能。
  • 可能需要从列表中删除一些项目，并可能在列表中添加一些新项目。更新列表标题需要新的页面，新页面应该从列表本身的项中重用。逐个弹出列表中的一些项，直到有足够多的页面可供下一阶段重用。
  • 通过添加新节点修改列表。
// remove `popn` pointers and add some new pointers
func (fl *FreeList) Update(popn int, freed []uint64) {
    assert(popn <= fl.Total())
    if popn == 0 && len(freed) == 0 {
        return // nothing to do
    }

    // prepare to construct the new list
    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) // recyle the node itself
        if popn >= flnSize(node) {
            // phase 1
            // remove all pointers in this node
            popn -= flnSize(node)
        } else {
            // phase 2:
            // remove some pointers
            remain := flnSize(node) - popn
            popn = 0
            // reuse pointers from the free list itself
            for remain > 0 && len(reuse)*FREE_LIST_CAP < len(freed)+remain {
                remain--
                reuse = append(reuse, flnPtr(node, remain))
            }
            // move the node into the `freed` list
            for i := 0; i < remain; i++ {
                freed = append(freed, flnPtr(node, i))
            }
        }
        // discard the node and move to the next node
        total -= flnSize(node)
        fl.head = flnNext(node)
    }
    assert(len(reuse)*FREE_LIST_CAP >= len(freed) || fl.head == 0)

    // phase 3: prepend new nodes
    flPush(fl, freed, reuse)

    // done
    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)}

        // construct a new node
        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 {
            // reuse a pointer from the list
            fl.head, reuse = reuse[0], reuse[1:]
            fl.use(fl.head, new)
        } else {
            // or append a page to house the new node
            fl.head = fl.new(new)
        }
    }
    assert(len(reuse) == 0)
}

管理磁盘页面

  1. 修改数据结构
数据结构被修改。临时页面保存在一个映射中，映射的键是分配的页面号。被删除的页面号也在其中。
type KV struct {
    // omitted...
    page struct {
        flushed uint64 // database size in number of pages
        nfree   int    // number of pages taken from the free list
        nappend int    // number of pages to be appended
        // newly allocated or deallocated pages keyed by the pointer.
        // nil value denotes a deallocated page.
        updates map[uint64][]byte
    }
}
  1. B树的页面管理
pageGet函数被修改为也返回临时页面，因为空闲列表代码依赖于此行为。
// callback for BTree & FreeList, dereference a pointer.
func (db *KV) pageGet(ptr uint64) BNode {
    if page, ok := db.page.updates[ptr]; ok {
        assert(page != nil)
        return BNode{page} // for new pages
    }
    return pageGetMapped(db, ptr) // for written pages
}

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树页面的函数被更改为首先重用空闲列表中的页面。
// callback for BTree, allocate a new page.
func (db *KV) pageNew(node BNode) uint64 {
    assert(len(node.data) <= BTREE_PAGE_SIZE)
    ptr := uint64(0)
    if db.page.nfree < db.free.Total() {
        // reuse a deallocated page
        ptr = db.free.Get(db.page.nfree)
        db.page.nfree++
    } else {
        // append a new page
        ptr = db.page.flushed + uint64(db.page.nappend)
        db.page.nappend++
    }
    db.page.updates[ptr] = node.data
    return ptr
}
移除的页面会标记为稍后的自由列表更新。
// callback for BTree, deallocate a page.
func (db *KV) pageDel(ptr uint64) {
    db.page.updates[ptr] = nil
}
  1. 自由列表的页面管理
追加新页面和为空闲列表重用页面的回调：
// callback for FreeList, allocate a new page.
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
}

// callback for FreeList, reuse a page.
func (db *KV) pageUse(ptr uint64, node BNode) {
    db.page.updates[ptr] = node.data
}
  1. 更新自由列表
在扩展文件并将页面写入磁盘之前，我们必须首先更新空闲列表，因为它也会创建挂起的写入。
func writePages(db *KV) error {
    // update the free list
    freed := []uint64{}
    for ptr, page := range db.page.updates {
        if page == nil {
            freed = append(freed, ptr)
        }
    }
    db.free.Update(db.page.nfree, freed)

    // extend the file & mmap if needed
    // omitted...

    // copy pages to the file
    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    |
  1. 完成
KV存储就完了。它是持久性和抗崩溃的，虽然它只能按顺序访问。
 
 
 

Copyright © 2025 later

logo