AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Boltdb学习笔记之一--存储管理

2022-06-10 184
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Boltdb学习笔记之一--存储管理

磁盘和内存的管理

磁盘是持久化存储，内存是非持久化存储。当数据库执行查询时，会以page为单位的读取磁盘上的数据库文件，并同步到内存中。当数据库执行写入操作时，也会以page为单位将内存中的结果flush到磁盘中。数据库关于如何管理磁盘和内存中数据的同步，主要有两种选择


  • 选择一：依赖Linux操作系统mmap系统调用，将磁盘文件映射到进程的地址空间。此时对于进程来说，读写内存即读写磁盘，此过程完全依赖操作系统。


  • 选择二：数据库自行管理磁盘和内存之间的数据同步。


选择一的好处是可大大减小数据库实现的复杂度，因为何时何地读写磁盘完全由操作系统负责，对数据库应用是透明的。坏处是，操作系统是所有进程共用的，其他进程会对数据库进程有影响；另外容易发生page fault导致stall, 数据库完成query的时间不可控；另外数据库依赖操作系统的实现，影响可移植性


选择二的好处是去除了对操作系统的依赖，自行实现磁盘和内存同步使很多优化变成了可能，例如direct IO和prefetch。坏处是实现起来比较复杂，需要考虑很多细节问题，例如内存缓冲区多大，满了之后flush哪个page到磁盘等等


boltdb选择了一种折中的方案，只有读取磁盘通过mmap, 写入磁盘则由自己控制。


读磁盘

在boltdb中，用户新建db时需要指定一个数据库文件的路径（你没看错，boltdb中一个db对应一个文件）。


// Open creates and opens a database at the given path.
// If the file does not exist then it will be created automatically.
// Passing in nil options will cause Bolt to open the database with the default options.
func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
 var db = &DB{opened: true}
  ...
}


接着执行mmap建立内存映射


// Memory map the data file.
 if err := db.mmap(options.InitialMmapSize); err != nil {
  _ = db.close()
  return nil, err
 }


DB中的dataref和data记录了mmap返回的内存缓冲区的地址


type DB struct {
  ...
  dataref  []byte   // mmap'ed readonly, write throws SEGV
 data     *[maxMapSize]byte
  ...
}


在成功建立内存映射关系之后，后续所有的读磁盘操作都转化为对DB.data的访问。DB.page函数输入参数为pageid, 从内存映射缓冲区data中读取并返回对应的page对象。


// page retrieves a page reference from the mmap based on the current page size.
func (db *DB) page(id pgid) *page {
 pos := id * pgid(db.pageSize)
 return (*page)(unsafe.Pointer(&db.data[pos]))
}


写磁盘


至于写磁盘操作，则通过调用DB.ops.WriteAt完成，其初始化如下，db.file.WriteAt是golang标准库提供的写文件方法


// Default values for test hooks
 db.ops.writeAt = db.file.WriteAt


在写事务中会调用DB.ops.WriteAt, 并使用fdatasync将内核缓冲区数据全部flush到磁盘中。


// writeMeta writes the meta to the disk.
func (tx *Tx) writeMeta() error {
 // Create a temporary buffer for the meta page.
 buf := make([]byte, tx.db.pageSize)
 p := tx.db.pageInBuffer(buf, 0)
 tx.meta.write(p)
 // Write the meta page to file.
 if _, err := tx.db.ops.writeAt(buf, int64(p.id)*int64(tx.db.pageSize)); err != nil {
  return err
 }
  if !tx.db.NoSync || IgnoreNoSync {
  if err := fdatasync(tx.db); err != nil {
   return err
  }
 }
  ...
}


而随着写入的增加，渐渐的db文件大小可能变得不够用，这时候需要对db文件进行扩容。扩容代码如下：首先计算扩容后的新大小，然后调用Truncate对文件扩容，最后调用Sync将相关元数据同步到文件系统中。


// grow grows the size of the database to the given sz.
func (db *DB) grow(sz int) error {
 // Ignore if the new size is less than available file size.
 if sz <= db.filesz {
  return nil
 }
 // If the data is smaller than the alloc size then only allocate what's needed.
 // Once it goes over the allocation size then allocate in chunks.
 if db.datasz < db.AllocSize {
  sz = db.datasz
 } else {
  sz += db.AllocSize
 }
 // Truncate and fsync to ensure file size metadata is flushed.
 // https://github.com/boltdb/bolt/issues/284
 if !db.NoGrowSync && !db.readOnly {
  if runtime.GOOS != "windows" {
   if err := db.file.Truncate(int64(sz)); err != nil {
    return fmt.Errorf("file resize error: %s", err)
   }
  }
  if err := db.file.Sync(); err != nil {
   return fmt.Errorf("file sync error: %s", err)
  }
 }
 db.filesz = sz
 return nil
}




Page

page是磁盘和内存之间进行数据同步的最小单位。boltdb中的page大小默认为操作系统中内存页的大小，一般为4 KB。可通过以下命令查看


$ getconf PAGESIZE
4096

d2460aeefb4785f7d32bb7d3f57c01b4.png


在boltdb中，page由两部分组成，一部分是page header, 另一部分是page body。page body如何组成是由具体page类型决定的。而page header结构是固定的，定义如下：


const (
 branchPageFlag   = 0x01
 leafPageFlag     = 0x02
 metaPageFlag     = 0x04
 freelistPageFlag = 0x10
)
type pgid uint64
type page struct {
 id       pgid
 flags    uint16
 count    uint16
 overflow uint32
 ptr      uintptr
}


其中数据成员如下：


  • id: boltdb中每个page都有一个唯一的id。类型为pgid, 实际上是uint64。page id在磁盘上按照空间顺序递增，即db文件中第一个page的id是0， 第二个page的id是1，以此类推。通过这样的设计，知晓了page id便可得到对应page在db文件中的位置：pageSize * (id - 1)


  • flags: page类型。page按照功能的不同，分为meta page, free list page, branch page和leaf page。稍后我们会一一提到。


  • count: page中包含的数据条数。该参数对meta page无意义。对于freelist来说，count表示其中空间page id数量与待释放page id数量之和。对于branch page来说，count表示其中key的数量，对于leaf page，count表示其中key/value对的数量。


  • overflow: 如果当前页面还不够存放数据，就会有后续页面，这个字段表示后续页面的数量。


  • ptr: 指向page body.


明白了page结构，那么db文件中不同类型的page是如何排列的呢？


从下面的代码中可看到，boltdb在初始化db文件时，首先生成两个meta page, page id分别是0和1。接着生成一个freelist page, page id为2，最后生成一个空的leaf page, page id为3。


// init creates a new database file and initializes its meta pages.
func (db *DB) init() error {
 // Set the page size to the OS page size.
 db.pageSize = os.Getpagesize()
 // Create two meta pages on a buffer.
 buf := make([]byte, db.pageSize*4)
 for i := 0; i < 2; i++ {
  p := db.pageInBuffer(buf[:], pgid(i))
  p.id = pgid(i)
  p.flags = metaPageFlag
  // Initialize the meta page.
  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()
 }
 // Write an empty freelist at page 3.
 p := db.pageInBuffer(buf[:], pgid(2))
 p.id = pgid(2)
 p.flags = freelistPageFlag
 p.count = 0
 // Write an empty leaf page at page 4.
 p = db.pageInBuffer(buf[:], pgid(3))
 p.id = pgid(3)
 p.flags = leafPageFlag
 p.count = 0
  ...
}


因此page在db文件中分布如下图所示：

eb3397ad903c9e29931b731d6394ffb1.png


meta page

d34159d9e9d939eaacdd052e98d54ac9.png


当page中的flags等于metaPageFlag时，该page便是meta page类型，此时page.ptr指向一个meta对象，meta类型如下：


type meta struct {
 magic    uint32
 version  uint32
 pageSize uint32
 flags    uint32
 root     bucket
 freelist pgid
 pgid     pgid
 txid     txid
 checksum uint64
}


其中的数据成员：


  • magic: 魔数，值为0xED0CDAED


  • version: 数据格式版本，值为2


  • pageSize: 系统分页大小，记录在meta page中方便下次加载db文件


  • freelist: freelist page id。


  • root: 根bucket。boltdb中所有的B+树都通过Bucket结构组织起来。


  • pgid: 当前已分配的最大page id。


  • txid: 本meta所关联的tx id。


  • checksum: meta的数据校验和


meta的反序列化：函数page.meta可从page对象中抽取出meta对象


// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
 return (*meta)(unsafe.Pointer(&p.ptr))
}


meta的序列化：函数meta.write将meta对象填充到page对象中


// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
 return (*meta)(unsafe.Pointer(&p.ptr))
}



freelist page

237db640f31ad9bb352f8aff27fc4dcf.png


freelist page记录了db文件中有哪些是空闲的page, 有哪些是被正在执行中的事务释放的page。在内存中用freelist表示


// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
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.
}


其中的数据成员：


  • ids: 空闲的page id，可用于分配page。


  • pending: 被正在执行中的事务释放的page, 根据事务id分组


  • cache: 存储ids和pending中的page id, 用于加快索引速度


freelist的序列化



调用freelist.read从page对象生成freelist对象


// read initializes the freelist from a freelist page.
func (f *freelist) read(p *page) {
 // If the page.count is at the max uint16 value (64k) then it's considered
 // an overflow and the size of the freelist is stored as the first element.
 idx, count := 0, int(p.count)
 if count == 0xFFFF {
  idx = 1
  count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
 }
 // Copy the list of page ids from the 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)
  // Make sure they're sorted.
  sort.Sort(pgids(f.ids))
 }
 // Rebuild the page cache.
 f.reindex()
}


首先将page.ptr强转成一个指向数组[maxAllocSize]pgid的指针，从中读取前count个page id复制到freelist的ids中，并对其排序。最后重建freelist的cache。


freelist的反序列化


调用freelist.write从freelist对象生成page。首先设置page中的flags为freelistPageFlag, 然后将freelist中的ids复制到page.ptr所指向的缓冲区中。


// write writes the page ids onto a freelist page. All free and pending ids are
// saved to disk since in the event of a program crash, all pending ids will
// become free.
func (f *freelist) write(p *page) error {
 // Combine the old free pgids and pgids waiting on an open transaction.
 // Update the header flag.
 p.flags |= freelistPageFlag
 // The page.count can only hold up to 64k elements so if we overflow that
 // number then we handle it by putting the size in the first element.
 lenids := f.count()
 if lenids == 0 {
  p.count = uint16(lenids)
 } else if lenids < 0xFFFF {
  p.count = uint16(lenids)
  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
}


从上面的代码可以看到，freelist序列化之后可能不止占据一个page。下面分情况讨论


  • 当ids数组长度小于0xFFFF时，freelist不会溢出，即freelist的数据可被一个page所容纳。此时page.count与freelist.ids数组长度相等。


  • 当ids数组长度超过0xFFFF时，freelist发生溢出。首个page中page.count的值为0xFFFF，其用意是标记该freelist page发生溢出。首个page中body部分头部记录freelist.ids的长度，接下来便是所有freelist.ids数据，首个page存不下时，用第二个page存，直到完成freelist.ids的复制


allocate：分配page


从freelist中的空闲page中寻找n个page id连续的page。如果分配成功，说明被分配的pages已经被占用，则将其从空闲page列表和cache中清除，并返回起始page id。如果分配失败，则返回零。代码见freekust.allocate


free：预释放page


该接口主要用于写事务提交之前释放已占用page。将待释放的page id加入到pending和cache中。如果待释放的page的overflow大于零，则对其关联的其他page做同样的处理。


release：完全释放page


该接口用于写事务提交时，将该事务的pending pages移动到ids中，表示这些page已经被真正释放，可用于继续分配。


rollback：回滚page


该接口用于写事务回滚时，将该事务的pending pages从pending和cache中删除。


branch page

5c086a0cf401a4ed0b6b1dd677d3019d.png


boltdb中用B+树表示数据，其中branch page用于表示B+树的非叶子节点。branch page的数据中只包含key。


type branchPageElement struct {
 pos   uint32
 ksize uint32
 pgid  pgid
}


其中：


  • pos: key相对于本branchPageElement对象在内存中的偏移量


  • ksize: key的长度


  • pgid: 该条branchPageElement数据所指向的children page id.


从branch page中获取branchPageElement数组。数组的数据存储于page.ptr所指向的缓冲区中


// branchPageElements retrieves a list of branch nodes.
func (p *page) branchPageElements() []branchPageElement {
 if p.count == 0 {
  return nil
 }
 return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
}


从branch page中获取第index个branchPageElement对象。


// branchPageElement retrieves the branch node by index
func (p *page) branchPageElement(index uint16) *branchPageElement {
 return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}


从branchPageElement中获取key值


// key returns a byte slice of the node key.
func (n *branchPageElement) key() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
}


leaf page

364c46f87fb8a6709b49cce79e1be117.png


boltdb中用B+树表示数据，leaf page即B+树的叶子节点，其中既包含key又包含value。每对key/value数据使用leafPageElement表示：


type leafPageElement struct {
 flags uint32
 pos   uint32
 ksize uint32
 vsize uint32
}


其中


  • flags: 用于判断该条kv数据是否为bucket(当flags != 0时)还是普通数据。


  • pos: key/value相对于leafPageElement的偏移量


  • ksize: key的长度。


  • vsize: value的长度。


leafPageElements从leaf类型的page中获取数组[]leafPageElement，从中可看到该数组位于page.ptr指向的缓冲区


// leafPageElements retrieves a list of leaf nodes.
func (p *page) leafPageElements() []leafPageElement {
 if p.count == 0 {
  return nil
 }
 return ((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[:]
}


leafPageElement从leaf类型的page中获取第index个leafPageElement对象。


// leafPageElement retrieves the leaf node by index
func (p *page) leafPageElement(index uint16) *leafPageElement {
 n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
 return n
}


key返回leafPageElement中的key值。


// key returns a byte slice of the node key.
func (n *leafPageElement) key() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize]
}


value返回leafPageElement中的value值


// value returns a byte slice of the node value.
func (n *leafPageElement) value() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos+n.ksize]))[:n.vsize:n.vsize]
}



文章标签：
Go
索引
Linux
数据格式
数据库
存储
r3ya7mqz6iacc
目录
相关文章
季风泯灭的季节
|
6月前
|
存储 缓存 关系型数据库
InnoDB 引擎底层存储和缓存原理
InnoDB 引擎底层存储和缓存原理
季风泯灭的季节
87 0
武子康
|
1月前
|
消息中间件 存储 缓存
大数据-71 Kafka 高级特性 物理存储 磁盘存储特性 如零拷贝、页缓存、mmp、sendfile
大数据-71 Kafka 高级特性 物理存储 磁盘存储特性 如零拷贝、页缓存、mmp、sendfile
武子康
50 3
dulu~dulu
|
6月前
|
存储 算法
分页存储管理与段式存储管理
分页存储管理与段式存储管理
dulu~dulu
116 3
桃子红了呐
|
存储 NoSQL 数据库
mongodb底层存储和索引原理——本质是文档数据库，无表设计，同时wiredTiger存储引擎支持文档级别的锁，MMAPv1引擎基于mmap，二级索引（二级是文档的存储位置信息『文件id + 文件内offset 』）
桃子红了呐
4384 0
闻缺陷则喜何志丹
读loki有感，TYPEList原理
读loki有感，TYPEList原理
闻缺陷则喜何志丹
25 0
myysophia
|
存储 JSON 缓存
K8s日志组件-Loki是如何存储数据的？
日志记录本质上是一个事件。大多数语言、应用程序框架或库都支持日志，表现形式可以是字符串这样原始的非结构化数据，也可以是JSON等半结构化数据。开发者可以通过日志来分析应用的执行状况，报错信息，分析性能…… 正因为日志极其灵活，生成非常容易，没有一个统一的结构，所以它的体量也是最大的。
myysophia
534 0
人民邮电出版社
|
存储 Linux 虚拟化
带你读《存储漫谈：Ceph原理与实践》——3.1.1 块设备映射
带你读《存储漫谈：Ceph原理与实践》——3.1.1 块设备映射
人民邮电出版社
699 0
人民邮电出版社
|
存储 Swift 索引
带你读《存储漫谈：Ceph原理与实践》——2.1 数据寻址方案
带你读《存储漫谈：Ceph原理与实践》——2.1 数据寻址方案
人民邮电出版社
170 0
训练营小助手
|
存储 SQL 算法
【视频】存储管理1 | 学习笔记
快速学习【视频】存储管理1
训练营小助手
141 0
【视频】存储管理1 | 学习笔记
木鸟杂记
|
缓存 NoSQL Go
Boltdb 源码导读（一）：Boltdb 数据组织(2)
Boltdb 源码导读（一）：Boltdb 数据组织(2)
木鸟杂记
259 0
Boltdb 源码导读（一）：Boltdb 数据组织(2)