ethan

ethan

新知,热爱生活,码农,读书
twitter
email
github

etcd存储引擎之主干框架boltdb

本文背景#

Etcd 是一个开源的分布式键值存储系统,它主要用于共享配置和服务发现。在现代的分布式服务架构中,etcd 扮演着至关重要的角色,因为它提供了一个可靠、一致且高效的存储解决方案,用于维护集群状态和配置信息。

为什么使用 Etcd 作为配置中心:#

  1. 一致性和可靠性:Etcd 使用 Raft 一致性算法,确保在分布式环境中,即使在节点故障的情况下,配置数据也能保持一致性和可靠性。这对于需要高可用性的系统来说至关重要。
  2. 简单性:Etcd 提供了一个简单的 API,支持 gRPC 和 HTTP,使得客户端可以轻松地与存储系统交互。这降低了开发和维护分布式系统的复杂性。
  3. 高性能:Etcd 设计用于处理大量的并发请求,它能够快速响应客户端的读写操作,这对于需要实时更新配置的分布式服务来说非常重要。
  4. 服务发现:除了配置管理,etcd 还支持服务发现功能,允许服务实例在启动时注册自己,并在停止时注销。这样,其他服务可以通过查询 etcd 来发现和连接到这些服务实例。
  5. 版本控制:Etcd 提供了版本控制机制,这意味着配置的每次更改都会被记录和追踪。这对于审计和回滚配置更改非常有用。
  6. 跨语言客户端库:Etcd 社区提供了多种语言的客户端库,这意味着开发者可以使用他们熟悉的编程语言与 etcd 交互。

Etcd 在分布式服务中的重要性:#

  • 集群协调:在分布式系统中,服务之间的协调至关重要。Etcd 可以存储集群状态信息,帮助各个服务实例了解集群的整体状态。
  • 动态配置:在动态变化的分布式环境中,服务的配置可能需要频繁更新。Etcd 提供了一个中心化的配置存储,使得配置的更新可以快速且一致地分发到所有相关服务。
  • 故障恢复:在节点故障时,Etcd 可以确保配置数据不会丢失,并且可以快速恢复,这对于系统的稳定性和可靠性至关重要。
  • 扩展性:随着服务的扩展,管理配置的复杂性会增加。Etcd 的设计允许水平扩展,可以随着服务的增长而增加更多的节点,以保持性能。

研究价值性:#

  • 技术深度:研究 etcd 可以帮助团队深入理解分布式系统的核心概念,如一致性、容错性和数据复制。
  • 实践应用:通过研究 etcd,团队可以更好地设计和实现自己的分布式服务,提高系统的可靠性和可维护性。
  • 社区贡献:参与 etcd 的研究和开发,可以为开源社区做出贡献,同时也能从社区中获得支持和最佳实践。
  • 行业趋势:了解和掌握 etcd 这样的关键技术,有助于团队跟上云计算和微服务架构的行业趋势。

综上所述,etcd 不仅在技术层面上为分布式服务提供了强大的支持,而且在实际应用和研究价值上也具有重要意义。对于正在进行配置中心技术调研的团队来说,深入研究 etcd 是一个值得投入的决策。

核心概念#

bolt 之于 etcd#

etcd 是一个具有强一致性的分布式协调服务,基于 golang 实现,底层基于 raft 算法保证数据的强一致和高可用,对应的开源地址: github(etcd)
image.png
本篇文章将探讨 etcd 中存储层引擎 boltdb 的工作原理。在 etcd 的架构设计中,boltdb 占据了一个特定的层次,其结构图如上图所示。boltdb 是一个使用 Go 语言编写的单机键值存储系统,它直接将数据持久化到磁盘上,具有以下特点:

  • 单机操作:boltdb 专注于单机环境,无需处理复杂的分布式共识机制,这使得其实现更为简洁。
  • 持久化存储:数据以键值对的形式存储在磁盘上,确保了数据的持久性和可靠性。
  • 本地 I/O:在进行数据读写操作时,boltdb 直接与本地文件系统进行交互,省去了客户端与服务端之间的通信开销,这使得数据访问过程既直接又高效。

存储设计#

在本文中,我们将从宏观的角度探讨 boltdb 的存储技术实现。由于篇幅所限,我们将对 boltdb 的内部机制进行简要的概述,以提供一个高层次的理解。

BoltDB 存储技术实现概述:#

  1. 数据模型:BoltDB 使用键值对(KV)作为其核心的数据模型。这种模型简单直观,易于理解和操作。
  2. 事务支持:BoltDB 提供了事务支持,允许进行原子性的读写操作。这意味着在事务中的所有更改要么全部成功,要么全部失败,保证了数据的一致性。
  3. 存储结构:数据在磁盘上以 B 树(B + 树)的形式存储,这种结构适合快速查找、插入和删除操作,同时保持了高效的磁盘利用率。
  4. 写入优化:为了提高写入性能,BoltDB 使用了一种称为 “写入前优化” 的技术。在数据被写入磁盘之前,它会在内存中进行合并和优化,减少磁盘 I/O 操作。
  5. 读取性能:BoltDB 的读取操作直接映射到磁盘上的 B 树结构,这使得读取操作非常快速,尤其是对于范围查询。
  6. 数据压缩:为了节省存储空间,BoltDB 对存储的数据进行了压缩。这不仅减少了磁盘占用,也提高了数据传输的效率。
  7. 并发控制:虽然 BoltDB 是为单机设计的,但它提供了一定程度的并发控制,允许多个 goroutine 安全地访问数据库。
  8. 持久化与恢复:BoltDB 支持数据的持久化,即使在系统崩溃后也能恢复数据。它通过定期创建快照和记录日志来实现这一点。
  9. 版本控制:BoltDB 允许用户在打开数据库时指定版本号,这有助于在升级数据库时保持兼容性。
  10. 安全性:虽然 BoltDB 本身不提供加密功能,但它允许用户在存储数据之前自行加密,以增强数据的安全性。
    本文的讨论旨在提供一个对 BoltDB 存储技术的宏观理解,为读者提供一个框架,以便更好地理解其在 etcd 中的应用和价值。对于希望深入了解其内部实现的读者,建议查阅 BoltDB 的官方文档和源代码。

读写#

boltdb 存储依赖于磁盘,针对于存储数据的交互,分为读、写流程:

  • 在读流程上:基于 mmap (memory-mapping) 技术实现,隐藏于磁盘交互细节,使用方能够像访问内存中的字节数组一样读取磁盘文件中的内容。
    image.png
  • 在写流程上:基于 pwrite+fdatasync, 实现数据落盘,兼顾效率和稳定
    image

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 中几个核心操作的流程,但不会深入到源代码的细节:

  1. 打开数据库:在打开 BoltDB 数据库时,会进行一系列的初始化操作,包括加载元数据页、空闲列表页和根节点页。这些操作确保数据库处于一致的状态,并且准备好接受后续的读写请求。
  2. 事务开始:当发起一个事务时,BoltDB 会根据事务类型(只读或读写)分配相应的资源。对于读写事务,会确保当前没有其他读写事务在执行。
  3. 数据查询:在只读事务中,数据查询操作可以直接访问数据库的 B + 树结构,检索所需的键值对。查询操作不会锁定任何数据,因此可以高效地并行执行。
  4. 数据修改:在读写事务中,数据的修改操作需要更复杂的处理。BoltDB 可能会创建新的页来存储修改后的数据,并更新 B + 树的结构。在事务提交时,这些更改会被持久化到磁盘。
  5. 事务提交:无论是只读还是读写事务,在提交时都需要确保所有更改都已经正确处理。对于读写事务,这可能包括更新元数据页、重新平衡 B + 树以及持久化所有新创建的页。
  6. 事务回滚:如果事务在执行过程中遇到错误,或者显式地被回滚,BoltDB 会撤销所有未提交的更改,确保数据库状态的一致性。
    通过这些核心操作流程,BoltDB 提供了一个高效且可靠的键值存储解决方案,适用于需要高性能和数据一致性的应用场景。

db 定义#

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
}

启动#

主流程#

image.png
通过 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 (表)#

image.png
一个 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
}

数据落盘#

image.png
在 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 更深层次的理解,我们可以进一步讨论其在实际应用中的性能优化、故障恢复策略以及与其他分布式系统的集成。

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.