Boltdb 源码导读（一）：Boltdb 数据组织

const (
  branchPageFlag   = 0x01
  leafPageFlag     = 0x02
  metaPageFlag     = 0x04
  freelistPageFlag = 0x10
)

type pgid uint64
type page struct {
  id       pgid
  flags    uint16  // 页类型，值为四种类型之一
  count    uint16  // 对应的节点包含元素个数，比如说包含的 kv 对
  overflow uint32  // 对应节点溢出页的个数，即使用 overflow+1 个页来保存对应节点
  ptr      uintptr // 指向数据对应的 byte 数组，当 overlay>0 时会跨越多个连续页；不过多个物理也在内存中也只会用一个 page 结构体来表示
}

type meta struct {
  magic    uint32
  version  uint32
  pageSize uint32 // 该 db 页大小，通过 syscall.Getpagesize() 获取，通常为 4k
  flags    uint32 // 
  root     bucket // 各个子 bucket 根所组成的树
  freelist pgid   // 空闲列表所存储的起始页 id
  pgid     pgid   // 当前用到的最大 page id，也即用到 page 的数量
  txid     txid   // 事务版本号，用以实现事务相关
  checksum uint64 // 校验和，用于校验 meta 页是否写完整
}

// 表示当前已经释放的 page 列表
// 和写事务刚释放的 page
type freelist struct {
  ids        []pgid            // all free and available free page ids.
  pending    map[txid][]pgid   // mapping of soon-to-be free page ids by tx.
  cache      map[pgid]bool     // fast lookup of all free and pending page ids.
}

func (f *freelist) write(p *page) error {
  // 设置页类型
  p.flags |= freelistPageFlag

  // page.count 是 uint16 类型，其能表示的范围为 [0, 64k-1] 。如果空闲页 id 列表长度超出了此范围，就需要另想办法。
  // 这里用了个 trick，将 page.count 置为 64k 即 0xFFF，然后在数据部分的第一个元素存实际数量（以 pgid 为类型，即 uint64）。
  lenids := f.count()
  if lenids == 0 {
    p.count = uint16(lenids)
  } else if lenids < 0xFFFF {
    p.count = uint16(lenids)
    // copyall 会将 pending 和 ids 合并并排序
    f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:]) 
  } else {
    p.count = 0xFFFF
    ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
    f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
  }

  return nil
}

func (f *freelist) read(p *page) {
  // count == 0xFFFF 表明实际 count 存储在 ptr 所指向的内容的第一个元素
  idx, count := 0, int(p.count)
  if count == 0xFFFF {
    idx = 1
    count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
  }

  // 将空闲列表从 page 拷贝内存中 freelist 结构体中
  if count == 0 {
    f.ids = nil
  } else {
    ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
    f.ids = make([]pgid, len(ids))
    copy(f.ids, ids)

    // 保证 ids 是有序的
    sort.Sort(pgids(f.ids))
  }

  // 重新构建 freelist.cache 这个 map.
  f.reindex()
}

// 如果可以找到连续 n 个空闲页，则返回起始页 id
// 否则返回 0
func (f *freelist) allocate(n int) pgid {
  if len(f.ids) == 0 {
    return 0
  }

  // 遍历寻找连续空闲页，并判断是否等于 n
  var initial, previd pgid
  for i, id := range f.ids {
    if id <= 1 {
      panic(fmt.Sprintf("invalid page allocation: %d", id))
    }

    // 如果不连续，则重置 initial
    if previd == 0 || id-previd != 1 {
      initial = id
    }

    if (id-initial)+1 == pgid(n) {
      // 当正好分配到 ids 中前 n 个 page 时，仅简单往前调整 f.ids 切片即可。
      // 尽管一时会造成空间浪费，但是在对 f.ids append/free 操作时，会按需
      // 重新空间分配，重新分配会导致这些浪费空间被回收掉
      if (i + 1) == n {
        f.ids = f.ids[i+1:]
      } else {
        copy(f.ids[i-n+1:], f.ids[i+1:])
        f.ids = f.ids[:len(f.ids)-n]
      }

      // 从 cache 中删除对应 page id
      for i := pgid(0); i < pgid(n); i++ {
        delete(f.cache, initial+i)
      }

      return initial
    }

    previd = id
  }
  return 0
}

// page ptr 指向的字节数组中的单个元素
type leafPageElement struct { 
  flags         uint32    // 普通 kv （flags=0）还是 subbucket（flags=bucketLeafFlag）
  pos           uint16    // kv header 与对应 kv 的距离
  ksize         uint32    // key 的字节数
  vsize         uint32    // val 字节数
}

inodes := p.leafPageElements()
index := sort.Search(int(p.count), func(i int) bool {
  return bytes.Compare(inodes[i].key(), key) != -1
})

func (n *branchPageElement) key() []byte {
  buf := (*[maxAllocSize]byte)(unsafe.Pointer(n)) // buf 是元素头起始地址
  return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
}

func (db *DB) init() error {
  // 设置页大小与操作系统一致
  db.pageSize = os.Getpagesize()

  buf := make([]byte, db.pageSize*4)
  // 在 buffer 中创建两个元信息页.
  for i := 0; i < 2; i++ {
    p := db.pageInBuffer(buf[:], pgid(i))
    p.id = pgid(i)
    p.flags = metaPageFlag

    // 初始化元信息页.
    m := p.meta()
    m.magic = magic
    m.version = version
    m.pageSize = uint32(db.pageSize)
    m.freelist = 2
    m.root = bucket{root: 3}
    m.pgid = 4
    m.txid = txid(i)
    m.checksum = m.sum64()
  }

  // 在 pgid=2 的页写入一个空的空闲列表.
  p := db.pageInBuffer(buf[:], pgid(2))
  p.id = pgid(2)
  p.flags = freelistPageFlag
  p.count = 0

  // 在 pgid=3 的页写入一个空的叶子元素.
  p = db.pageInBuffer(buf[:], pgid(3))
  p.id = pgid(3)
  p.flags = leafPageFlag
  p.count = 0

  // 将 buffer 中的这四个页写入数据文件并刷盘
  if _, err := db.ops.writeAt(buf, 0); err != nil {
    return err
  }
  if err := fdatasync(db); err != nil {
    return err
  }

  return nil
}

func (db *DB) mmapSize(size int) (int, error) {
  // 从 32KB 开始，直到 1GB.
  for i := uint(15); i <= 30; i++ {
    if size <= 1<<i {
      return 1 << i, nil
    }
  }

  // Verify the requested size is not above the maximum allowed.
  if size > maxMapSize {
    return 0, fmt.Errorf("mmap too large")
  }

  // 对齐到 maxMmapStep = 1G
  sz := int64(size)
  if remainder := sz % int64(maxMmapStep); remainder > 0 {
    sz += int64(maxMmapStep) - remainder
  }

  // 对齐到 db.pageSize
  pageSize := int64(db.pageSize)
  if (sz % pageSize) != 0 {
    sz = ((sz / pageSize) + 1) * pageSize
  }

  // 不能超过 maxMapSize
  if sz > maxMapSize {
    sz = maxMapSize
  }

  return int(sz), nil
}