本文背景#
Etcd 是一个开源的分布式键值存储系统，它主要用于共享配置和服务发现。在现代的分布式服务架构中，etcd 扮演着至关重要的角色，因为它提供了一个可靠、一致且高效的存储解决方案，用于维护集群状态和配置信息。
为什么使用 Etcd 作为配置中心：#
- 一致性和可靠性：Etcd 使用 Raft 一致性算法，确保在分布式环境中，即使在节点故障的情况下，配置数据也能保持一致性和可靠性。这对于需要高可用性的系统来说至关重要。
- 简单性：Etcd 提供了一个简单的 API，支持 gRPC 和 HTTP，使得客户端可以轻松地与存储系统交互。这降低了开发和维护分布式系统的复杂性。
- 高性能：Etcd 设计用于处理大量的并发请求，它能够快速响应客户端的读写操作，这对于需要实时更新配置的分布式服务来说非常重要。
- 服务发现：除了配置管理，etcd 还支持服务发现功能，允许服务实例在启动时注册自己，并在停止时注销。这样，其他服务可以通过查询 etcd 来发现和连接到这些服务实例。
- 版本控制：Etcd 提供了版本控制机制，这意味着配置的每次更改都会被记录和追踪。这对于审计和回滚配置更改非常有用。
- 跨语言客户端库：Etcd 社区提供了多种语言的客户端库，这意味着开发者可以使用他们熟悉的编程语言与 etcd 交互。
Etcd 在分布式服务中的重要性：#
- 集群协调：在分布式系统中，服务之间的协调至关重要。Etcd 可以存储集群状态信息，帮助各个服务实例了解集群的整体状态。
- 动态配置：在动态变化的分布式环境中，服务的配置可能需要频繁更新。Etcd 提供了一个中心化的配置存储，使得配置的更新可以快速且一致地分发到所有相关服务。
- 故障恢复：在节点故障时，Etcd 可以确保配置数据不会丢失，并且可以快速恢复，这对于系统的稳定性和可靠性至关重要。
- 扩展性：随着服务的扩展，管理配置的复杂性会增加。Etcd 的设计允许水平扩展，可以随着服务的增长而增加更多的节点，以保持性能。
研究价值性：#
- 技术深度：研究 etcd 可以帮助团队深入理解分布式系统的核心概念，如一致性、容错性和数据复制。
- 实践应用：通过研究 etcd，团队可以更好地设计和实现自己的分布式服务，提高系统的可靠性和可维护性。
- 社区贡献：参与 etcd 的研究和开发，可以为开源社区做出贡献，同时也能从社区中获得支持和最佳实践。
- 行业趋势：了解和掌握 etcd 这样的关键技术，有助于团队跟上云计算和微服务架构的行业趋势。
综上所述，etcd 不仅在技术层面上为分布式服务提供了强大的支持，而且在实际应用和研究价值上也具有重要意义。对于正在进行配置中心技术调研的团队来说，深入研究 etcd 是一个值得投入的决策。
核心概念#
bolt 之于 etcd#
etcd 是一个具有强一致性的分布式协调服务，基于 golang 实现，底层基于 raft 算法保证数据的强一致和高可用，对应的开源地址: github(etcd)
本篇文章将探讨 etcd 中存储层引擎 boltdb 的工作原理。在 etcd 的架构设计中，boltdb 占据了一个特定的层次，其结构图如上图所示。boltdb 是一个使用 Go 语言编写的单机键值存储系统，它直接将数据持久化到磁盘上，具有以下特点：
- 单机操作：boltdb 专注于单机环境，无需处理复杂的分布式共识机制，这使得其实现更为简洁。
- 持久化存储：数据以键值对的形式存储在磁盘上，确保了数据的持久性和可靠性。
- 本地 I/O：在进行数据读写操作时，boltdb 直接与本地文件系统进行交互，省去了客户端与服务端之间的通信开销，这使得数据访问过程既直接又高效。
存储设计#
在本文中，我们将从宏观的角度探讨 boltdb 的存储技术实现。由于篇幅所限，我们将对 boltdb 的内部机制进行简要的概述，以提供一个高层次的理解。
BoltDB 存储技术实现概述：#
- 数据模型：BoltDB 使用键值对（KV）作为其核心的数据模型。这种模型简单直观，易于理解和操作。
- 事务支持：BoltDB 提供了事务支持，允许进行原子性的读写操作。这意味着在事务中的所有更改要么全部成功，要么全部失败，保证了数据的一致性。
- 存储结构：数据在磁盘上以 B 树（B + 树）的形式存储，这种结构适合快速查找、插入和删除操作，同时保持了高效的磁盘利用率。
- 写入优化：为了提高写入性能，BoltDB 使用了一种称为 “写入前优化” 的技术。在数据被写入磁盘之前，它会在内存中进行合并和优化，减少磁盘 I/O 操作。
- 读取性能：BoltDB 的读取操作直接映射到磁盘上的 B 树结构，这使得读取操作非常快速，尤其是对于范围查询。
- 数据压缩：为了节省存储空间，BoltDB 对存储的数据进行了压缩。这不仅减少了磁盘占用，也提高了数据传输的效率。
- 并发控制：虽然 BoltDB 是为单机设计的，但它提供了一定程度的并发控制，允许多个 goroutine 安全地访问数据库。
- 持久化与恢复：BoltDB 支持数据的持久化，即使在系统崩溃后也能恢复数据。它通过定期创建快照和记录日志来实现这一点。
- 版本控制：BoltDB 允许用户在打开数据库时指定版本号，这有助于在升级数据库时保持兼容性。
- 安全性：虽然 BoltDB 本身不提供加密功能，但它允许用户在存储数据之前自行加密，以增强数据的安全性。
本文的讨论旨在提供一个对 BoltDB 存储技术的宏观理解，为读者提供一个框架，以便更好地理解其在 etcd 中的应用和价值。对于希望深入了解其内部实现的读者，建议查阅 BoltDB 的官方文档和源代码。
读写#
boltdb 存储依赖于磁盘，针对于存储数据的交互，分为读、写流程：
- 在读流程上：基于 mmap (memory-mapping) 技术实现，隐藏于磁盘交互细节，使用方能够像访问内存中的字节数组一样读取磁盘文件中的内容。
- 在写流程上：基于 pwrite+fdatasync, 实现数据落盘，兼顾效率和稳定
BoltDB 的存储结构#
BoltDB 在存储数据时采用了类似操作系统中内存与磁盘交换的 “页”（page）概念。这种设计使得数据的组织和管理更加高效。在 BoltDB 中，页分为几种类型，每种类型承担不同的角色：
- 元数据页（Meta Page）：存储 BoltDB 的元数据，如版本号、校验和等。此外，还包括全局递增的事务 ID 记录，这些信息属于全局维度的内容。
- 空闲列表页（Freelist Page）：记录哪些页是空闲的，哪些页将被事务释放。这类似于 Go 语言中的堆（heap），采用空间换时间的策略，缓存并管理空闲页以供复用，减少与操作系统的交互。
- 分支元素页（Branch Element Page）：存储索引节点，对应于 B + 树中的分支节点。这些页提供了较细粒度的索引，与具体数据相关联。
- 叶子元素页（Leaf Element Page）：存储数据节点，对应于 B + 树的叶子节点。这些页同样提供了细粒度的数据存储，与数据实体直接相关。
在数据库初始化时，BoltDB 会创建并持久化四个页： - 元数据页（Meta Page）：初始化两个元数据页，这是为了实现效率与稳定性，与 BoltDB 采用的 copy-on-write 机制有关。
- 空闲列表页（Freelist）：初始化全局维度的空闲页管理块。
- 叶子元素页（Leaf Element Page）：作为 B + 树的根节点，同时也是叶子节点，为数据库提供一个空白的起点。
B + 树的实现#
BoltDB 的数据存储基于 B + 树，这是一种优化过的 B 树结构。B + 树是一种多路平衡查找树，其特点是所有数据都存储在叶子节点中，而内部节点仅用于索引。BoltDB 在实现 B + 树时进行了一些改造：
- 引用游标：由于叶子节点之间不是通过链表直接连接，BoltDB 使用一个游标工具来辅助范围检索，记录移动路径。
- 调整频率：为了平衡操作效率和树的平衡性，BoltDB 仅在数据溢写到磁盘前进行一次性的 B + 树平衡调整。
桶（Bucket）的概念#
BoltDB 引入了桶（Bucket）的概念，用于实现业务数据的隔离。可以将桶类比为数据库中的表，但桶的形式更加灵活，支持嵌套式的拓扑关系。每个数据库都有一个默认的根桶（root bucket），从这个根桶可以衍生出多叉树结构。每个桶在逻辑上都有一棵独立的 B + 树，用于存储该桶范围内的键值对数据。这种设计使得数据的组织更加灵活，便于管理和扩展。
BoltDB 事务处理#
BoltDB 支持两种类型的事务：只读事务（read-only transactions）和读写事务（read-write transactions）。这两种事务类型在操作权限和并发处理上有所不同：
- 读写事务：这类事务允许执行修改数据的操作，如插入、更新和删除。由于这些操作可能会改变数据库状态，因此读写事务不是幂等的。在任何时刻，只有一个读写事务可以执行，以避免并发写操作导致的数据不一致。然而，读写事务可以与多个只读事务并行执行。
- 只读事务：这类事务仅包含查询操作，不会修改数据库内容。因此，只读事务是幂等的，可以安全地与其他只读事务或读写事务并行执行，而不会影响数据的一致性。
核心操作流程概览#
在本节中，我们将简要探讨 BoltDB 中几个核心操作的流程，但不会深入到源代码的细节：
- 打开数据库：在打开 BoltDB 数据库时，会进行一系列的初始化操作，包括加载元数据页、空闲列表页和根节点页。这些操作确保数据库处于一致的状态，并且准备好接受后续的读写请求。
- 事务开始：当发起一个事务时，BoltDB 会根据事务类型（只读或读写）分配相应的资源。对于读写事务，会确保当前没有其他读写事务在执行。
- 数据查询：在只读事务中，数据查询操作可以直接访问数据库的 B + 树结构，检索所需的键值对。查询操作不会锁定任何数据，因此可以高效地并行执行。
- 数据修改：在读写事务中，数据的修改操作需要更复杂的处理。BoltDB 可能会创建新的页来存储修改后的数据，并更新 B + 树的结构。在事务提交时，这些更改会被持久化到磁盘。
- 事务提交：无论是只读还是读写事务，在提交时都需要确保所有更改都已经正确处理。对于读写事务，这可能包括更新元数据页、重新平衡 B + 树以及持久化所有新创建的页。
- 事务回滚：如果事务在执行过程中遇到错误，或者显式地被回滚，BoltDB 会撤销所有未提交的更改，确保数据库状态的一致性。
通过这些核心操作流程，BoltDB 提供了一个高效且可靠的键值存储解决方案，适用于需要高性能和数据一致性的应用场景。
db 定义#
首先介绍 boldb 中的一个核心类 --DB，对应为一个数据库实例的代码抽象，其中包含的核心成员属性：
// boltdb 抽象的数据库
type DB struct {
// ...
// 数据库文件名称
path string
// 打开文件方法
openFile func(string, int, os.FileMode) (*os.File, error)
// 数据库文件，所有数据存储于此
file *os.File
// 基于 mmap 技术映射的数据库文件内容
data *[maxMapSize]byte
// ...
// 两个轮换使用的 meta page
meta0 *meta
meta1 *meta
// 数据库单个 page 的大小，单位 byte
pageSize int
// 数据库是否已启动
opened bool
// 全局唯一的读写事务
rwtx *Tx
// 一系列只读事务
txs []*Tx
// freelist，管理空闲的 page
freelist *freelist
freelistLoad sync.Once
// 提高 page 字节数组复用率的对象池
pagePool sync.Pool
// ...
// 互斥锁，保证读写事务全局唯一
rwlock sync.Mutex
// 保护 meta page 的互斥锁
metalock sync.Mutex
// 保护 mmap 的读写锁
mmaplock sync.RWMutex
// 数据落盘持久化时使用的操作方法，对应为 pwrite 操作
ops struct {
writeAt func(b []byte, off int64) (n int, err error)
}
// 是否已只读模式启动数据库
readOnly bool
}
启动#
主流程#
通过 open 方法可以启动 db, 核心流程包括：
- 通过 db 实例，并读取各项 option 完成配置
- 通过传入的 path, 打开对应的数据库文件（如果文件之前不存在，则会进行全新文件的创建）
- 倘若在创建新的数据库文件，则需要完成 2 个 meta page, 1 个 freelist page 和 1 个 leaf element page 的初始化
- 构造 pagePool 对象池，后续可复用 page 的字节数组
- 执行 mmap 操作，完成数据库文件和内存空间的映射
- 返回构造好的 db 实例
func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
// 构造 db 实例
db := &DB{
opened: true,
}
// 启用默认配置
if options == nil {
options = DefaultOptions
}
// ...
// 默认不启用只读模式
if options.ReadOnly {
flag = os.O_RDONLY
db.readOnly = true
} else {
// always load free pages in write mode
db.PreLoadFreelist = true
}
// 打开数据库文件的操作方法
db.openFile = options.OpenFile
if db.openFile == nil {
db.openFile = os.OpenFile
}
// 打开数据库文件
var err error
if db.file, err = db.openFile(path, flag|os.O_CREATE, mode); err != nil {
_ = db.close()
return nil, err
}
// 数据库文件名称赋值
db.path = db.file.Name()
// ...
// 数据落盘操作
db.ops.writeAt = db.file.WriteAt
// 数据 page 大小
if db.pageSize = options.PageSize; db.pageSize == 0 {
// 默认等于操作系统 page 大小
db.pageSize = defaultPageSize
}
// 倘若从零到一创建一个新的 db 文件，则需要进行初始化
if info, err := db.file.Stat(); err != nil {
_ = db.close()
return nil, err
} else if info.Size() == 0 {
// 初始化 db
if err := db.init(); err != nil {
// ...
_ = db.close()
return nil, err
}
}
// ...
// 对象池，用于复用 page 的字节数组
db.pagePool = sync.Pool{
New: func() interface{} {
return make([]byte, db.pageSize)
},
}
// 基于 mmap 建立数据库文件和内存空间的映射
if err := db.mmap(options.InitialMmapSize); err != nil {
_ = db.close()
return nil, err
}
// 预加载 freelist
if db.PreLoadFreelist {
db.loadFreelist()
}
// ...
return db, nil
}
mmap#
通过 mmap 实现数据文件和内存映射，核心步骤包括：
- 加锁保证 mmap 操作并发安全
- 设置合适的 mmap 空间大小
- 若之前已经执行过 mmap，则需要善后粗粒
- 执行新一轮 mmap 操作
func (db *DB) mmap(minsz int) (err error) {
// 互斥锁，保护 mmap 并发安全
db.mmaplock.Lock()
defer db.mmaplock.Unlock()
info, err := db.file.Stat()
// ...
// 调整合适的 mmap 容量
fileSize := int(info.Size())
var size = fileSize
if size < minsz {
size = minsz
}
size, err = db.mmapSize(size)
if err != nil {
return err
}
// ...
// 倘若此前已经有读写事务在运行，此时因为要执行 mmap 操作，则需要对 bucket 内容进行重塑
if db.rwtx != nil {
db.rwtx.root.dereference()
}
// 解除之前建立的 mmap 映射
if err = db.munmap(); err != nil {
return err
}
// 建立新的 mmap 映射
if err = mmap(db, size); err != nil {
return err
}
// ...
return nil
}
注意：mmap 底层通过系统调用实现，不同的操作系统会有不同的实现细节。
建 bucket (表)#
一个 bucket 本质上是从属于其父 bucket b + 树中的一笔特殊的 kv 对数据。因此创建 bucket 的过程会和写入 kv 数据的流程类似：
- 借助游标，找到 bucket key 从属的父 bucket b + 树的位置
- 创建子 bucket 实例，并取得序列化后的结果
- 将 bucket 名称作为 key, bucket 序列化结果作为 value，以一组 kv 对的形式插入到父 bucket b + 树中
func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
// ...
// 获取游标
c := b.Cursor()
// 借助游标找到桶名 key 对应的位置
k, _, flags := c.seek(key)
// 桶已存在
if bytes.Equal(key, k) {
if (flags & bucketLeafFlag) != 0 {
return nil, ErrBucketExists
}
return nil, ErrIncompatibleValue
}
// 创建新的桶实例
var bucket = Bucket{
bucket: &bucket{},
rootNode: &node{isLeaf: true},
FillPercent: DefaultFillPercent,
}
// 取得桶的序列化结果
var value = bucket.write()
// 将这个新桶对应的 kv 对数据写入到 b+ 树中
key = cloneBytes(key)
c.node().put(key, key, value, 0, bucketLeafFlag)
// ...
// 返回创建好的新桶
return b.Bucket(key), nil
}
查 bucket（表）#
通过名称检索 bucket 的流程，一定程度上和数据的查询流程相类似：
- 查看父 bucket 的缓存 map，如果子 bucket 已反序列化过，则直接复用
- 通过游标 cursor 检索父 bucket 的 b + 树，找到对应子 bucket 的 kv 对数据
- 根据 kv 数据反序列化生成 bucket 实例
- 将子 bucket 添加到父 bucket 的缓存 map 中
- 返回检索得到的子 bucket
func (b *Bucket) Bucket(name []byte) *Bucket {
// 如果 map 中已经缓存了对应的桶，直接返回
if b.buckets != nil {
if child := b.buckets[string(name)]; child != nil {
return child
}
}
// 借助游标在 b+ 树中检索 kv 对
c := b.Cursor()
k, v, flags := c.seek(name)
// ...
// 找到桶后，对其反序列化
var child = b.openBucket(v)
// 缓存到 map 中
if b.buckets != nil {
b.buckets[string(name)] = child
}
// 返回桶
return child
}
数据落盘#
在 boltdb 提交读写事务时，会一次性将更新的脏数据溢写落盘：
- 通过 rebalance 和 spill 操作，保证 B + 树的平衡性满足要求
- 执行 pwrite+fdatasync 操作，完成脏数据的 page 的一些落盘
- 通过 pagepool 回收用于指向这部分 page 对应的字节数组
- 由于更新了事务进度，meta page 也需要溢写落盘
- 关闭读写事务
func (tx *Tx) Commit() error {
// ...
// 数据溢写磁盘前，需要调整一轮 b+ 树，保证其平衡性
// rebalance 是为了避免因为 delete 操作，导致某些节点 kv 对数量太少，不满足 b+ 树平衡性要求
tx.root.rebalance()
// ...
// spill 是为了避免因为 put 操作，导致某些节点 kv 对数量太多，不满足 b+ 树平衡性要求
if err := tx.root.spill(); err != nil {
tx.rollback()
return err
}
// 事务更新到的脏数据溢写落盘
if err := tx.write(); err != nil {
tx.rollback()
return err
}
// ...
// meta page 溢写落盘
if err := tx.writeMeta(); err != nil {
tx.rollback()
return err
}
// ...
// 关闭事务
tx.close()
// ...
return nil
}
事务脏页溢写落盘
func (tx *Tx) write() error {
// 事务缓存的脏页
pages := make(pages, 0, len(tx.pages))
for _, p := range tx.pages {
pages = append(pages, p)
}
// 清空缓存
tx.pages = make(map[pgid]*page)
// 对脏页进行排序
sort.Sort(pages)
// 按照顺序，将脏页溢写落盘
for _, p := range pages {
// page 总大小，包含 overflow 不分
rem := (uint64(p.overflow) + 1) * uint64(tx.db.pageSize)
// page 的 offset，可以根据 page id 推算得到
offset := int64(p.id) * int64(tx.db.pageSize)
var written uintptr
// Write out page in "max allocation" sized chunks.
for {
sz := rem
if sz > maxAllocSize-1 {
sz = maxAllocSize - 1
}
buf := unsafeByteSlice(unsafe.Pointer(p), written, 0, int(sz))
// 将 page 溢写到文件对应 offset 的位置
if _, err := tx.db.ops.writeAt(buf, offset); err != nil {
return err
}
rem -= sz
// 一次性写完了
if rem == 0 {
break
}
// 如果没有一次性写完，下一轮接着写
offset += int64(sz)
written += uintptr(sz)
}
}
// fdatasync 操作，确保数据溢写落盘完成
if !tx.db.NoSync || IgnoreNoSync {
if err := fdatasync(tx.db); err != nil {
return err
}
}
// 释放这部分已落盘 page，倘若其不存在 overflow，说明是标准规格的字节数组，则清空内容，然后添加到对象池中进行复用
for _, p := range pages {
// Ignore page sizes over 1 page.
// These are allocated using make() instead of the page pool.
if int(p.overflow) != 0 {
continue
}
buf := unsafeByteSlice(unsafe.Pointer(p), 0, 0, tx.db.pageSize)
// See https://go.googlesource.com/go/+/f03c9202c43e0abb130669852082117ca50aa9b1
for i := range buf {
buf[i] = 0
}
tx.db.pagePool.Put(buf) //nolint:staticcheck
}
return nil
}
总结#
本文提供了对 BoltDB 架构和关键特性的高层次概览。我们探讨了 BoltDB 的存储结构，包括不同类型的页（如元数据页、空闲列表页、分支元素页和叶子元素页），以及它们在数据库中的作用。同时，我们也介绍了 BoltDB 的事务处理机制，区分了只读事务和读写事务，并简要说明了它们的并发处理方式。
此外，我们还从宏观角度审视了 BoltDB 的 B + 树实现，包括其对 B 树的优化和在实际应用中的调整。我们还提到了 BoltDB 中的桶（Bucket）概念，它为数据提供了灵活的隔离和组织方式。
尽管本文的内容较为浅显，但它为读者提供了一个框架，以便更好地理解 BoltDB 在分布式存储系统中的作用。未来，我们可以深入探讨这些核心概念的具体实现细节，以及它们如何共同作用以提供高效、可靠的数据存储解决方案。随着对 BoltDB 更深层次的理解，我们可以进一步讨论其在实际应用中的性能优化、故障恢复策略以及与其他分布式系统的集成。