程序锅

  • 首页
  • 分类
  • 标签
  • 归档
  • 关于

  • 搜索
基础知识 Etcd LeetCode 计算机体系结构 Kubernetes Containerd Docker 容器 云原生 Serverless 项目开发维护 ELF 深入理解程序 Tmux Vim Linux Kernel Linux numpy matplotlib 机器学习 MQTT 网络基础 Thrift RPC OS 操作系统 Clang 研途 数据结构和算法 Java 编程语言 Golang Python 个人网站搭建 Nginx 计算机通用技术 Git

Etcd MVCC 机制

发表于 2022-12-19 | 分类于 Etcd | 0 | 阅读次数 2866

前言

etcd v3 中 MVCC(Multiversion Concurrency Control) 机制的核心思想是保存 key-value 的多个历史版本。在 MVCC 中,更新一个 key-value 数据的时候,并不会直接覆盖原来的数据,而是会新增一个版本号来存储新的数据。当删除数据的时候,也会增加版本号,并且会新增一条带删除标识的数据记录。

因此,在 MVCC 机制中每个版本号都会对应一个的数据,同理每个数据也都会有一个版本号。指定版本号读取数据时,它实际上访问的是版本号生成时间点的快照数据。

基于 MVCC 机制,etcd 提供了可靠的 Watch 机制,避免了 client 频繁发起 list pod 等 expensive request 操作,保障 etcd 集群的稳定性。MVCC 还能以较低的并发控制开销,实现各类隔离级别的事务,保障事务的安全性,是事务特性的基础。

整体架构

下图是 etcd 的整体架构,其中 MVCC 模块由 Apply 模块调用,

  • 对于用户的读请求(比如 range 操作)来说。它会调用 MVCC 模块来获取 key 对应的 value。
  • 对于用户的写请求(比如 put/delete 操作)来说。在对应的 Raft 日志标识为 commited 之后,Apply 模块会异步执行 Raft 日志的内容,此时它就是调用 MVCC 模块来持久化 key-value 数据。

MVCC 主要基于 treeIndex、Backend/boltdb 两个模块,实现了对 key-value 的增删改查。以发起 get hello 请求为例,它会首先从 treeIndex 中获取到 hello 的 revision,然后再通过该 revision 从 boltdb 中获取 value 信息,这个 value 包含 key-value、各种 revision、lease 信息等。

treeIndex 和 boltdb 两个模块的关系如下图所示,

treeIndex

treeIndex 模块保存了用户 key 和 revision(版本号)之间的映射关系。treeIndex 使用了内存版 B-tree,一个 google 的开源项目,使用 go 实现,并对外提供简易的调用接口。在 B-tree 中,度是一个核心参数,它决定了每个节点上的数据量是多少。在一个度为 d 的 B-tree 中,每个节点保存的最大数据量为 2d-1,也就是 key 数为 2d-1。否则,需要进行平衡、分裂等操作。在 treeIndex 模块中,可创建的最大度是 32 的 B-tree,也就是一个节点最多可以保存 63 个 key。

那么 treeIndex 模块是怎么保存 key 和 revision 之间的映射关系的呢?针对每个 key,它都会在节点上保存一个 keyIndex 结构(包含了 key 和 revision 的内容),如下所示,

type keyIndex struct {
  // 用户的 key 名称,比如 "hello"
  key []byte
  // 最后一次修改 key 时的 etcd 版本号
  modified revision
  // generations 保存了一个 key 若干代版本号信息,每代中包含对 key 的多次修改的版本号列表
  generations []generation 
}

其中 generations 表示一个 key 从创建到删除的过程,对应 key 的一个生命周期的开始与结束。当第一次创建一个 key 时,会生成第 0 代,后续的修改操作都是在第 0 代中追加修改版本号。当把 key 删除后,会生成新的一代,第 1 代。一个 key 不断经历创建、删除的过程,会生成多个代。

type generation struct {
  ver int64 // 表示此 key 的修改次数
  created revision // 表示 generation 结构创建时的版本号
  revs []revision // 每次修改 key 时的 revision 追加到此数组
}

其中版本号 revision 并不是一个简单的整数,而是一个结构体,如下所示。

type revision struct {
  main int64	// 一个全局递增的主版本号,随 put/delete/事务请求递增
  sub int64		// 一个事务内的子版本号,从 0 开始随事务内 put/delete 操作递增
}

如下所示,如果一个空集群,全局版本号默认为 1,执行了一个包含两次 put、一次 get 的事务时。由于全局版本号是随着写请求递增的,因此 main 会变成 2,sub 是随着事务内的 put/delete 操作递增的,最终 key hello 的 revision 为 {2, 0},key world 的 revision 为 {2, 1}。

$ etcdctl txn -i
compares:

success requests (get,put,del):
put hello 1
get hello
put world 2

为什么使用 B-tree

为什么使用 B-tree 来保存 key 和 revision 之间的映射关系呢?而不是使用哈希表、或平衡二叉树呢。主要是考虑到 etcd 要支持范围查询,因此使用的数据结构也必须要支持范围查询才行。

哈希表不支持范围查询不适合,而平衡二叉树每个节点只能容纳一个数据、会导致树的高度较高。B-tree 由于每个节点可以容纳多个数据,相比之下树的高度更低、更扁平,涉及的查找次数更少,因此采用 B-tree。以下图的 B-tree 为例,当要查找 k95 的时候,只需要经过图中两次比较即可快速找到 k95 所在的节点。

boltdb

etcd 默认支持多种后端存储,后端存储模块(Backend)主要负责 key-value 的持久化存储,由 Buffer、ReadTx、BatchTx 组成。Buffer 是数据缓存区,ReadTx 定义了抽象的读事务接口(对应读请求),BatchTx 在 ReadTx 之上定义了抽象的写事务接口(对应写请求)。

目前,etcd 后端存储的实现采用的是 boltdb。boltdb 是一个基于 B+tree 实现的、支持事务的 key-value 嵌入式数据库。

  • 在 etcd 中 boltdb 存储的 key 是 revision,比如上文中的 {2,0},value 是 mvccpb.KeyValue 结构体,它由 key、value、create_revision、mod_revision、version、lease 组成。

    • create_revision 表示该 key 创建时的版本号。
    • mod_revision 表示 key 最后一次修改时的版本号。
    • version 表示 key 的修改次数。

    相比将用户的 key 作为 boltdb key,用户历史的 value 作为 boltdb value 的方式来说。以 revision 为 key 的好处是可以减少并发冲突、读写被放大的问题。因此以用户 key 作为 boltdb key 的话,如果两个 put 请求操作同一个 key 的话,则会出现并发冲突。

  • boltdb 通过 bucket 来隔离集群元数据与用户数据,bucket 类似 MySQL 的一个表。每个 bucket 都相当于一颗 B+ Tree。用户的 key 数据存放在名为 key 的 bucket 中,etcd 元数据存放在名叫 meta 的 bucket 中。

MVCC 的更新/增加

MVCC 针对 put 操作(写事务),如下图所示,

  1. 它首先从 treeIndex 模块中查询到 key 的 KeyIndex(包含 revision)。如果此时 KeyIndex 为空,etcd 会根据当前的全局版本号(空集群启动时默认为 1)自增,生成 revision。如果 KeyIndex 不为空,则根据 KeyIndex 中的内容和当前的全局版本号,生成 revision。

  2. 之后填充好 boltdb 的 mvccpb.KeyValue 结构体,并通过后端存储的写事务 BatchTx 接口,将 key:revision,value: mvccpb.KeyValue 保存到 Buffer 中,并更新 boltdb 对应的内存数据结构。

  3. 然后将新建/更新后的 KeyIndex 对象保存到 treeIndex 模块中。

    key hello 的 keyIndex:
    key: "hello"
    modified: <2,0>
    generations:
    [{ver:1,created:<2,0>,revisions: [<2,0>]}]
    
  4. 此时数据持久化往往是未完成的。etcd 的一个 backend goroutine 会定期、异步、批量持久化之前写事务所做的更改,也就是在 goroutine 中定期调用 boltdb 的 commit 接口。

    该接口会对内存数据结构中的 B+tree 进行平衡、分裂,并且将脏数据、元数据信息刷新到磁盘。由于该过程开销昂贵,如果每次 put 请求都同步调用一次 commit 接口,etcd 的写性能将会变得很差。因此,etcd 才采用合并多个写事务后再进行一次提交,这种方式显著提升了 QPS 和吞吐量。通常情况下,goroutine 会默认每隔 100ms,将累积的写事务一次性提交。但是,如果堆积的事务过多(大于 1w)时,也会触发同步提交。

查询原理

针对 range 操作(读事务)来说,如下图所示,

  1. 首先 treeIndex 模块根据 key 查找到 KeyIndex 对象,然后匹配有效的 generation。

    • 如果是未带版本号的读,默认是读取最新的数据,会返回匹配到的 generation 的 revisions 数组中最后一个 revision。

    • 如果是指定版本号,要读取历史记录的话。treeIndex 模块会先遍历匹配到的 generation 的 revisions 数组,返回小于等于指定版本号的最近的 revision。

  2. 之后以返回的 revision 为 key,通过 Backend 提供的并发读事务(ConcurrentReadTx)接口,优先从 Buffer 中查询,命中则返回;否则则从 boltdb 中查询。

    ConcurrentReadTx 并发读特性,在 etcd 3.4 中的 Backend 实现。它的核心原理是在进行一次读事务时,会全量拷贝当前写事务未提交的 buffer 数据,此时读事务不再阻塞在一个 Buffer 资源锁上,实现了并发读。

删除原理

MVCC 针对 delete 操作来说,整体流程与 put 流程类似,但是有几点不太相同。

  1. 首先从 treeIndex 模块中查询到 key 的 KeyIndex(包含 revision)。

    • 一方面会生成新的 revision,这个 revision 追加了删除标识(tombstone,简写 t),比如 {4,0,t}

    • 另一方面会给该 KeyIndex 对象,追加一个空的 generation 对象,表示该 key 已经被删除了,示例如下所示。

      key hello的keyIndex:
      key: "hello"
      modified: <4,0>
      generations:
      [
      {ver:3,created:<2,0>,revisions: [<2,0>,<3,0>,<4,0>(t)]},
      {empty}
      ]
      

      当再次查询被删除 key 的时候,treeIndex 模块在查找到 KeyIndex 对象后,发现存在空的 generation 对象,并且查询的版本号大于等于被删除时的版本号时,会返回空。

  2. 之后针对该 revision {4,0,t} 生成 KeyValue 结构体,并将其持久化。此时 KeyValue 结构体中只包含了用户的 key。为什么要持久化呢?如果不持久化,那么发生错误,etcd 重启后在构建 treeIndex 的时候不知道哪些 key 是已经被删除了的。

  3. 之后压缩组件(compactor)异步完成删除 treeIndex 中的 KeyIndex 和 boltdb 中的 key-value 内容。etcd 针对删除 key 的操作,不是立刻从 treeIndex 和 boltdb 中删除此数据,而是延期删除模式。

  4. 另外,key 打上删除标记之后,

    • Watch 模块会根据 key 的删除标识,生成相应的 delete event 推送给 etcd 客户端,比如 kubernetes。
    • 在重启 etcd 的时候,etcd 会遍历 boltdb 中的 key-value 构建 treeIndex 内存树,此时可以清楚获取哪些 key 是已经被删除了的,并为对应的 key 构建带删除标识的索引。

总结

通过以上原理的分析,可以看到 etcd 实现了对 key 历史版本的保存,同时也为 Watch 机制提供了基础。etcd v2 不支持保存 key 的历史版本,v2 为了解决 Watch 依赖历史版本的问题,它会在内存中维护一个较短的全局事件变更窗口(窗口大小为 1000)。但是,在集群写请求较多等场景下,全局事件变更窗口会很容易爆满,仍旧无法提供可靠的 Watch 机制。

卷死我
dawnguo 微信支付

微信支付

dawnguo 支付宝

支付宝

  • 本文作者: dawnguo
  • 本文链接: /archives/268
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# Kubernetes # Etcd
Etcd WAL 日志&&Snapshot
boltdb 介绍
  • 文章目录
  • 站点概览
dawnguo

dawnguo

215 日志
24 分类
37 标签
RSS
Creative Commons
© 2018 — 2025 程序锅
0%