存储界的轮子一大堆，大部份都用 leveldb, 封个 redis protocol 就说实现了 kv 服务~ 看了下 bolt 官网，居然用的也很多，最出名的就是 etcd, 本来想看 etcd mvcc, 发现 boltdb 也得深入了解。botldb 设计来源于 LMDB，关于各单机引擎的对比参考这篇压测
主流 KV 引擎对比
整体概括
- 使用单一文件，
mmap映射，相当于将文件缓存交给操作系统。使用时以操作系统页为单位(比如常见的 4K)，数据删除时空闲页并不会被系统回收，而是挂载到freelist中，所以 boltdb 文件只会增大 - 支持事务，隔离级别为
serializable串行，写写串行，写读，读读并发。所以从这一点来看，boltdb 并不适合写集中业务。为了提高写性能，支持 batch 操作 - leveldb 用的
LSM数据结构，通过WAL将随机写变成顺序写，所以写非常快，但是读要分层去查找，过滤。而 boltdb 写会比较慢，但由于内部使用b+tree结构，所以读和范围读是很快的。另外 leveldb 支持 key 前辍压缩，value 也支持压缩，所以存储空间比 boltdb 小很多。 - boltdb 内部使用
bucket, 可以理解为表或是命名空间，不同的是bucket可以嵌套，不过一般不这么做。每个 kv 都关联到特定的bucket, 所有读写操作都会开启一个事务，读使用COW技术来模拟MVCC(准确说是模拟可重复读，后面看代码就清楚了)
综上所述，没有最好的选择，只有合适的场景。
整体架构
┌────────────────────────────────────────────────────────────────────────────────────────────────┐
│ │
│┌─────────────────────────────────────────────────────────────────────────────┐ │
││ DB │ │
│└─────┬──────────────┬──────────────┬─────────────────┬────────────────┬──────┘ │
│ │ │ │ │ │ │
│┌─────▼────┐ ┌─────▼────┐ ┌─────▼────┐ ┌────▼─────┐ ┌─────▼────┐ │
││ rwtx │ │ rtx1 │ │ rtx2 │ **** │ rtxN │ │ freelist │ │
│└──────────┘ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ │
│┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ Memory │
││ Bucket1 │ │ Bucket2 │ │ Bucket3 │ **** │ BucketN │ │
│└──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ │
│┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
││ cursor │ │ node │ │ inode │ │ inode │ │ inode │ │
│└──────────┘ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│─────────────────────────────────────────────────────────────────────────────────────────────── │
│ │
│┌────────────┐ ┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │
││ │ │ │ │ │ │ │ │
││ Page │ │ branchPageElement │ │ leafPageElement │ │ leafPageElement │ Disk │
││ │ │ │ │ │ │ │ │
│└────────────┘ └───────────────────┘ └───────────────────┘ └───────────────────┘ │
└────────────────────────────────────────────────────────────────────────────────────────────────┘
最烦看数据结构了，有的时候默名其秒，具体到每个流程再细看。整体架构拓扑分为内存表示和磁盘表示两部份，memory 部份的 node, inode 对应 disk 部份的 branchPageElement, leafPageElement
page 底层格式 meta
数据底层以页为单位，每个页有不同的类型。前两个页固定为 meta 页，其它的 freelist 用于存储空闲的页，分配置时直接使用，brand 页可以理解为 b+tree 的非叶子节点，leaf 就是底层页子节点了，存储真正的 kv
const (
branchPageFlag = 0x01
leafPageFlag = 0x02
metaPageFlag = 0x04
freelistPageFlag = 0x10
)
type pgid uint64
type page struct {
id pgid // 8
flags uint16 // 2
count uint16 // 2
overflow uint32 // 4
ptr uintptr // 8
}
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────┼────────────────────────────────────────────────────┐
│ │
│ meta 64bytes │
│ │
└────────────────────────────────────────────────────┘
上图是 meta 页结构图，page header 占 24 字节，flag 表示当前页的类型，但是最后一个 ptr 字段是用来内存中定位的，page 和 meta 结构体共用这 8 字节
// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
return (*meta)(unsafe.Pointer(&p.ptr))
}
这种 unsafe 的使用形式在 c 里面很常见，go 大家一般底层才会用到。
type meta struct {
magic uint32 // 魔数，用于判断
version uint32 // 版本
pageSize uint32 // 页大小
flags uint32
root bucket // 定位到 b+tree root page
freelist pgid // freelist 所在页
pgid pgid
txid txid // 当前最大事务 id
checksum uint64
}
pageSize 表示当前页大小，root 可以定位到根，也就是 b+tree 入口，freelist 表示空闲页 pgid, txid 是最大事务 id
page 底层格式 freelist
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────╋━━━━━━━┳───────┬───────┬───────┬───────┐ ┌───────┐
┃ │ │ │ │ │ │ │
┃page id│page id│page id│page id│page id│ ***** │page id│
┃ │ │ │ │ │ │ │
┗━━━━━━━┻───────┴───────┴───────┴───────┘ └───────┘
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────╋━━━━━━━┳───────┬───────┬───────┬───────┐ ┌───────┐
┃ │ │ │ │ │ │ │
┃ count │page id│page id│page id│page id│ ***** │page id│
┃ │ │ │ │ │ │ │
┗━━━━━━━┻───────┴───────┴───────┴───────┘ └───────┘
page count 表示后面的元素个数，如果是 freelist 页，表示 page id 个数。由于 count 是 2 bytes, 所以如果 count 值为 0xffff，那么紧临的第一个 int64 就不是 page id 而是真正的个数。
// 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()
}
通过读代码也能很好理解，全是 unsafe 操作。
page 底层格式 branch
// branchPageElement retrieves the branch node by index
func (p *page) branchPageElement(index uint16) *branchPageElement {
return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}
// 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)))[:]
}
// branchPageElement represents a node on a branch page.
type branchPageElement struct {
pos uint32 // 页内的 offset
ksize uint32 // key size 长度
pgid pgid // key 所在的页 id
}
// 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]
}
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────┼───────────────────────────┬ ─ ┌───────────────────────────┬───────┬───────┐ ┌───────┐
│ │ │ │ │ │ │ │
│ branchPageElement 1 │**** │ branchPageElement N │ key │ key │***│ key │
│ │ │ │ │ │ │ │
├──────┬──────┬─────────────┤ └───────────────────────────┴───────┴───────┘ └───────┘
│ │ │ │
│ pos │ksize │ page id │
│ │ │ │
└──────┴──────┴─────────────┘
branchPageElement 是 b+tree 非叶子节点在磁盘的表示，同样前 24 bytes 是 page header, count 表示后面多少个 branchPageElement 元素，ptr 字段用来定位。branchPageElement 中的 pos 和 ksize 用于定位当前页中 key 的位置，pgid 代表 key 叶子节点的页，这个 key 是叶子节点的下界，也就是 bytes order 的最小 key.
page 底层格式 leaf
// leafPageElement retrieves the leaf node by index
func (p *page) leafPageElement(index uint16) *leafPageElement {
n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
return n
}
// 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 represents a node on a leaf page.
type leafPageElement struct {
flags uint32
pos uint32 // 当前页中 kv 定位 offset
ksize uint32 // key size
vsize uint32 // value size
}
// 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 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]
}
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────┼───────────────────────────┬ ─ ┌───────────────────────────┬───────┬───────┐ ┌───────┐
│ │ │ │ │ │ │ │
│ leafPageElement 1 │**** │ leafPageElement 1 N │ kv │ kv │***│ kv │
│ │ │ │ │ │ │ │
├─────┬──────┬──────┬───────┤ └───────────────────────────┴───────┴───────┘ └───────┘
│ │ │ │ │
│flag │ pos │ksize │ vsize │
│ │ │ │ │
└─────┴──────┴──────┴───────┘
和 branch 很像，leaf page 需要存储 kv pair, 按照 key bytes order 排序，同样也是 unsafe 操作，比较好理解。
page 底层格式 bucket
bucket 存储的格式分两种：inline 与普通模式。也就是说如果 boltdb 存储的 kv 对很少，那就直接在 bucket 所在的页存放，这叫 inline, 如果一个页放不下，那就变成普通模式使用单独页。具体存储时由于 bucket 也有属性信息，所以 bucket 也是变相的 kv 记录，存储在 leaf 叶子节点中。
│ │ │ │
─────────8 bytes──────────────┼──2───├─ 2───├─────4────────┼─────────────8─────────────────
│ │ │ │
┌──────────────────────────────┬──────┬──────┬──────────────┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │ │ │ │
│ page id │ flag │count │ overflow │ ptr
│ │ │ │ │ │
└──────────────────────────────┴──────┴──────┴──────────────┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│
│
┌──────────────────────────────────────────────────────┘
│
▼
┌───────────────────────────┐ ┌───────────────────────────┬───────┬───────┐ ┌───────┐
│ │ │ │ │ │ │ │
│ leafPageElement 1 │**** │ leafPageElement 1 N │ kv │ kv │***│ kv │
│ │ │ │ │ │ │ │
├─────┬──────┬──────┬───────┤ └───────────────────────────┴───────┴───────┘ └───────┘
│ │ │ │ │ │
│flag │ pos │ksize │ vsize │ │
│ │ │ │ │ │
└─────┴──────┴──────┴───────┘ ┌──────────────────────────────────┘
│
│
▼
┌───────────────────────────┬───────────────────────────┐
│ │ │
│ key:name │ value: bucket header │
│ │ │
└───────────────────────────┼─────────────┬─────────────┤
│ │ │
│root page id │ sequence │
│ │ │
└─────────────┴─────────────┘
上图是非 inline 数据格式，leafPageElement flag 字段会标记当前 kv 是 bucket 类型。key 就是 bucket 的名字，value 是 bucket 的属性：root page id 是 b+tree 根所在的页 id， sequence 类似数据库表的自增 id，可以用这个做 bucket 里的 key，当然也可以不用。
┌───────────────────────────┬───────────────────────────┬──────────────────────────────┬───────────────────────────┬───────┐
│ │ │ │ │ │
│ key:name │ value: bucket header │ page header │ leafPageElement 1 │ kv │
│ │ │ │ │ │
└───────────────────────────┼─────────────┬─────────────┼──────────────────────────────┴───────────────────────────┴───────┘
│ │ │
│root page id │ sequence │
│ │ │
└─────────────┴─────────────┘
上图是 inline 的情况，value 就不只是 bucket header 了，还包括 kv 数据，这个数据实际上就是一个普通的 leaf page，也有 page header, 也有 leafPageElement
小结
到这里就可以看到两点：
- 碰盘的
b+tree是很矮胖的，branchPage 没几个，leafPage 里的 kv 也是按 byte order 顺序存放，所以了解mysql b+tree的就很容易理解。 - 数据是没有压缩的，全部裸存储，磁盘消耗肯定大
网友评论