第三节 空闲列表页

空闲列表页中主要包含三个部分：所有已经可以重新利用的空闲页列表ids、将来很快被释放掉的事务关联的页列表pending、页id的缓存。详细定义在freelist.go文件中，下面给大家展示其空闲页的定义。

  1. freelist.go
  3. // freelist represents a list of all pages that are available for allocation.
  4. // It also tracks pages that have been freed but are still in use by open transactions.
  5. type freelist struct {
  6.     // 已经可以被分配的空闲页
  7.     ids     []pgid          // all free and available free page ids.
  8.     // 将来很快能被释放的空闲页，部分事务可能在读或者写
  9.     pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
  10.     cache   map[pgid]bool   // fast lookup of all free and pending page ids.
  11. }
  13. // newFreelist returns an empty, initialized freelist.
  14. func newFreelist() *freelist {
  15.     return &freelist{
  16.         pending: make(map[txid][]pgid),
  17.         cache:   make(map[pgid]bool),
  18.     }
  19. }

下图展示的是空闲列表的存储方式。

../imgs/空闲列表存储.png

1. freelist->page

将空闲列表转换成页信息，写到磁盘中，此处需要注意一个问题，页头中的count字段是一个uint16，占两个字节，其最大可以表示2^16 即65536个数字，当空闲页的个数超过65535时时，需要将p.ptr中的第一个字节用来存储其空闲页的个数，同时将p.count设置为0xFFFF。否则不超过的情况下，直接用count来表示其空闲页的个数

  1. // write writes the page ids onto a freelist page. All free and pending ids are
  2. // saved to disk since in the event of a program crash, all pending ids will
  3. // become free.
  4. //将 freelist信息写入到p中
  5. func (f *freelist) write(p *page) error {
  6.     // Combine the old free pgids and pgids waiting on an open transaction.
  8.     // Update the header flag.
  9.     // 设置页头中的页类型标识
  10.     p.flags |= freelistPageFlag
  12.     // The page.count can only hold up to 64k elements so if we overflow that
  13.     // number then we handle it by putting the size in the first element.
  15.     lenids := f.count()
  16.     if lenids == 0 {
  17.         p.count = uint16(lenids)
  18.     } else if lenids < 0xFFFF {
  19.         p.count = uint16(lenids)
  20.         // 拷贝到page的ptr中
  21.         f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
  22.     } else {
  23.         // 有溢出的情况下，后面第一个元素放置其长度，然后再存放所有的pgid列表
  24.         p.count = 0xFFFF
  25.         ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
  26.         // 从第一个元素位置拷贝
  27.         f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
  28.     }
  29.     return nil
  30. }
  32. // copyall copies into dst a list of all free ids and all pending ids in one sorted list.
  33. // f.count returns the minimum length required for dst.
  34. func (f *freelist) copyall(dst []pgid) {
  35.     // 首先把pending状态的页放到一个数组中，并使其有序
  36.     m := make(pgids, 0, f.pending_count())
  37.     for _, list := range f.pending {
  38.         m = append(m, list...)
  39.     }
  40.     sort.Sort(m)
  41.     // 合并两个有序的列表，最后结果输出到dst中
  42.     mergepgids(dst, f.ids, m)
  43. }
  45. // mergepgids copies the sorted union of a and b into dst.
  46. // If dst is too small, it panics.
  47. // 将a和b按照有序合并成到dst中，a和b有序
  48. func mergepgids(dst, a, b pgids) {
  49.     if len(dst) < len(a)+len(b) {
  50.         panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
  51.     }
  52.     // Copy in the opposite slice if one is nil.
  53.     if len(a) == 0 {
  54.         copy(dst, b)
  55.         return
  56.     }
  57.     if len(b) == 0 {
  58.         copy(dst, a)
  59.         return
  60.     }
  62.     // Merged will hold all elements from both lists.
  63.     merged := dst[:0]
  65.     // Assign lead to the slice with a lower starting value, follow to the higher value.
  66.     lead, follow := a, b
  67.     if b[0] < a[0] {
  68.         lead, follow = b, a
  69.     }
  71.     // Continue while there are elements in the lead.
  72.     for len(lead) > 0 {
  73.         // Merge largest prefix of lead that is ahead of follow[0].
  74.         n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
  75.         merged = append(merged, lead[:n]...)
  76.         if n >= len(lead) {
  77.             break
  78.         }
  80.         // Swap lead and follow.
  81.         lead, follow = follow, lead[n:]
  82.     }
  84.     // Append what's left in follow.
  85.     _ = append(merged, follow...)
  86. }

2. page->freelist

从磁盘中加载空闲页信息，并转为freelist结构，转换时，也需要注意其空闲页的个数的判断逻辑，当p.count为0xFFFF时，需要读取p.ptr中的第一个字节来计算其空闲页的个数。否则则直接读取p.ptr中存放的数据为空闲页ids列表

  1. //从磁盘中的page初始化freelist
  2. // read initializes the freelist from a freelist page.
  3. func (f *freelist) read(p *page) {
  4.     // If the page.count is at the max uint16 value (64k) then it's considered
  5.     // an overflow and the size of the freelist is stored as the first element.
  6.     idx, count := 0, int(p.count)
  7.     if count == 0xFFFF {
  8.         idx = 1
  9.         // 用第一个uint64来存储整个count的值
  10.         count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
  11.     }
  13.     // Copy the list of page ids from the freelist.
  14.     if count == 0 {
  15.         f.ids = nil
  16.     } else {
  17.         ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
  18.         f.ids = make([]pgid, len(ids))
  19.         copy(f.ids, ids)
  21.         // Make sure they're sorted.
  22.         sort.Sort(pgids(f.ids))
  23.     }
  25.     // Rebuild the page cache.
  26.     f.reindex()
  27. }
  29. // reindex rebuilds the free cache based on available and pending free lists.
  30. func (f *freelist) reindex() {
  31.     f.cache = make(map[pgid]bool, len(f.ids))
  32.     for _, id := range f.ids {
  33.         f.cache[id] = true
  34.     }
  35.     for _, pendingIDs := range f.pending {
  36.         for _, pendingID := range pendingIDs {
  37.             f.cache[pendingID] = true
  38.         }
  39.     }
  40. }

3. allocate

开始分配一段连续的n个页。其中返回值为初始的页id。如果无法分配，则返回0即可

  1. // allocate returns the starting page id of a contiguous list of pages of a given size.
  2. // If a contiguous block cannot be found then 0 is returned.
  3. // [5,6,7,13,14,15,16,18,19,20,31,32]
  4. // 开始分配一段连续的n个页。其中返回值为初始的页id。如果无法分配，则返回0即可
  5. func (f *freelist) allocate(n int) pgid {
  6.     if len(f.ids) == 0 {
  7.         return 0
  8.     }
  10.     var initial, previd pgid
  11.     for i, id := range f.ids {
  12.         if id <= 1 {
  13.             panic(fmt.Sprintf("invalid page allocation: %d", id))
  14.         }
  16.         // Reset initial page if this is not contiguous.
  17.         // id-previd != 1 来判断是否连续
  18.         if previd == 0 || id-previd != 1 {
  19.             // 第一次不连续时记录一下第一个位置
  20.             initial = id
  21.         }
  23.         // If we found a contiguous block then remove it and return it.
  24.         // 找到了连续的块，然后将其返回即可
  25.         if (id-initial)+1 == pgid(n) {
  26.             // If we're allocating off the beginning then take the fast path
  27.             // and just adjust the existing slice. This will use extra memory
  28.             // temporarily but the append() in free() will realloc the slice
  29.             // as is necessary.
  30.             if (i + 1) == n {
  31.                 // 找到的是前n个连续的空间
  32.                 f.ids = f.ids[i+1:]
  33.             } else {
  34.                 copy(f.ids[i-n+1:], f.ids[i+1:])
  35.                 f.ids = f.ids[:len(f.ids)-n]
  36.             }
  38.             // Remove from the free cache.
  39.             // 同时更新缓存
  40.             for i := pgid(0); i < pgid(n); i++ {
  41.                 delete(f.cache, initial+i)
  42.             }
  44.             return initial
  45.         }
  47.         previd = id
  48.     }
  49.     return 0
  50. }

考虑是否需要补充其他的freelist的方法