「MVCC」- 概述原理

整体架构

当执行 put 请求时,流程如图所示(图示已省略部分暂时无需关注的模块),Apply 模块通过 MVCC 模块来执行 put 请求,以持久化 KV 数据;

MVCC 模块将请求请划分成两个类别,分别是:
1)读事务(ReadTxn),读事务负责处理 range 请求,
2)写事务(WriteTxn),写事务负责 put/delete 操作;

treeIndex and boltdb

整个 MVCC 特性由 treeIndex、Backend/boltdb 组成,读写事务基于 treeIndex、Backend/boltdb 提供的能力,实现对 KV 的增删改查功能;

treeIndex 与 boltdb 关系如图:当发起 get hello 命令时,从 treeIndex 中获取 key 的版本号,然后再通过这个版本号,从 boltdb 获取 value 信息;

treeIndex

解释:该模块基于内存版 B-tree 实现 key 索引管理,它保存用户 key 与版本号(revision)的映射关系等信息;

用途:对于 etcd v2 来说,当你通过 etcdctl 发起一个 put hello 操作时,etcd v2 直接更新内存树,这就导致历史版本直接被覆盖,无法支持保存 key 的历史版本。在 etcd v3 中引入 treeIndex 模块正是为解决这个问题,支持保存 key 的历史版本,提供稳定的 Watch 机制和事务隔离等能力;

行为:etcd 在每次修改 key 时,会生成一个全局递增的 revision,然后通过数据结构 B-tree 保存用户 key 与 revision 间的关系,再以 revision 作为 boltdb key,以用户的 key-value 等信息作为 boltdb value,保存到 boltdb;

B-tree

Q:为什么 etcd 不使用哈希表、平衡二叉树?
从功能特性上分析, 因 etcd 支持范围查询,因此保存索引的数据结构也必须支持范围查询才行。所以哈希表不适合,而 B-tree 支持范围查询;B 树支持的范围查询很有限,如果在同一个 B 树节点的范围查询就还好,如果是跨 B 树节点就比较麻烦了。而 B+树的范围查询就很方便了;
从性能上分析,平横二叉树每个节点只能容纳一个数据、导致树的高度较高,而 B-tree 每个节点可以容纳多个数据,树的高度更低,更扁平,涉及的查找次数更少,具有优越的增、删、改、查性能;

Google 的开源项目 btree,使用 Go 语言实现了一个内存版的 B-tree,对外提供了简单易用的接口。etcd 正是基于 btree 库实现了一个名为 treeIndex 的索引模块,通过它来查询、保存用户 key 与版本号之间的关系;

下图是个最大度(degree > 1,简称 d)为 5 的 B-tree,度是 B-tree 中的一个核心参数,它决定了你每个节点上的数据量多少、节点的“胖”、“瘦”程度;

从图中你可以看到,节点越胖,意味着一个节点可以存储更多数据,树的高度越低。在一个度为 d 的 B-tree 中,节点保存的最大 key 数为 2d – 1,否则需要进行平衡、分裂操作。这里你要注意的是在 etcd treeIndex 模块中,创建的是最大度 32 的 B-tree,也就是一个叶子节点最多可以保存 63 个 key;

从图中你可以看到,你通过 put/txn 命令写入的一系列 key,treeIndex 模块基于 B-tree 将其组织起来,节点之间基于用户 key 比较大小。当你查找一个 key k95 时,通过 B-tree 的特性,你仅需通过图中流程 1 和 2 两次快速比较,就可快速找到 k95 所在的节点;

type keyIndex struct {}

在 treeIndex 中,每个节点的 key 是一个 keyIndex 结构,etcd 就是通过它保存了用户的 key 与版本号的映射关系;

keyIndex 结构包含的信息:

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

keyIndex 中包含用户的 key、最后一次修改 key 时的 etcd 版本号、key 的若干代(generation)版本号信息,每代中包含对 key 的多次修改的版本号列表。那我们要如何理解 generations?为什么它是个数组呢?

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

generation 结构详细信息如下:

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

需要注意的是版本号(revision)并不是一个简单的整数,而是一个结构体。revision 结构及含义如下:

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

revision 包含 main 和 sub 两个字段,main 是全局递增的版本号,它是个 etcd 逻辑时钟,随着 put/txn/delete 等事务递增。sub 是一个事务内的子版本号,从 0 开始随事务内的 put/delete 操作递增;

比如启动一个空集群,全局版本号默认为 1,执行下面的 txn 事务,它包含两次 put、一次 get 操作,那么按照我们上面介绍的原理,全局版本号随读写事务自增,因此是 main 为 2,sub 随事务内的 put/delete 操作递增,因此 key hello 的 revison 为{2,0},key world 的 revision 为{2,1}(同一个事务中的 put/del 只改变子版本号);

$ etcdctl txn -i
compares:


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

Backend(boltdb)

该模块负责 etcd 的 key-value 持久化存储,主要由:
1)ReadTx 定义抽象的读事务接口,
2)BatchTx 在 ReadTx 之上定义抽象的写事务接口,
3)Buffer 是数据缓存区;

etcd 设计上支持多种 Backend 实现,目前实现的 Backend 是 boltdb;

boltdb 的 value 是包含用户 key-value、各种版本号、lease 信息的结构体;

MVCC 更新 key 原理

当你通过 etcdctl 发起一个 put hello 操作时,如下面的 put 事务流程图流程一所示,在 put 写事务中,首先它需要从 treeIndex 模块中查询 key 的 keyIndex 索引信息,keyIndex 中存储了 key 的创建版本号、修改的次数等信息,这些信息在事务中发挥着重要作用,因此会存储在 boltdb 的 value 中;

第一步、创建 keyIndex 结构

因为是第一次创建 hello key,此时 keyIndex 索引为空

其次 etcd 会根据当前的全局版本号(空集群启动时默认为 1)自增,生成 put hello 操作对应的版本号 revision{2,0},这就是 boltdb 的 key;

boltdb 的 value 是 mvccpb.KeyValue 结构体,其组成字段及其含义分别如下:

create_revision 表示此 key 创建时的版本号。在我们的案例中,key hello 是第一次创建,那么值就是 2。当你再次修改 key hello 的时候,写事务会从 treeIndex 模块查询 hello 第一次创建的版本号,也就是 keyIndex.generations[i].created 字段,赋值给 create_revision 字段;

mod_revision 表示 key 最后一次修改时的版本号,即 put 操作发生时的全局版本号加 1;

version 表示此 key 的修改次数。每次修改的时候,写事务会从 treeIndex 模块查询 hello 已经历过的修改次数,也就是 keyIndex.generations[i].ver 字段,将 ver 字段值加 1 后,赋值给 version 字段;

第二步、同步 buffer 模块

填充好 boltdb 的 KeyValue 结构体后,这时就可以通过 Backend 的写事务 batchTx 接口将 key{2,0},value 为 mvccpb.KeyValue 保存到 boltdb 的缓存中,并同步更新 buffer,如上图中的流程二所示;

此时存储到 boltdb 中的 key、value 数据如下

第三步、写入 treeIndex 模块

然后 put 事务需将本次修改的版本号与用户 key 的映射关系保存到 treeIndex 模块中,也就是上图中的流程三;

因为 key hello 是首次创建,treeIndex 模块它会生成 key hello 对应的 keyIndex 对象,并填充相关数据结构;

keyIndex 填充后的结果如下所示:

key hello 的 keyIndex:
key:     "hello"
modified: <2,0>
generations:
[{ver:1,created:<2,0>,revisions: [<2,0>]} ]

key 为 hello,modified 为最后一次修改版本号 <2,0>,key hello 是首次创建的,因此新增一个 generation 代跟踪它的生命周期、修改记录;
generation.ver 表示修改次数,首次创建为 1,后续随着修改操作递增;
generation.created 表示创建 generation 时的版本号为 <2,0>;
revision 数组保存对此 key 修改的版本号列表,每次修改都会将将相应的版本号追加到 revisions 数组中;

第四步、持久化到 boltdb 存储

但是此时数据还并未持久化,为了提升 etcd 的写吞吐量、性能,一般情况下(默认堆积的写事务数大于 1 万才在写事务结束时同步持久化),数据持久化由 Backend 的异步 goroutine 完成,它通过事务批量提交,定时将 boltdb 页缓存中的脏数据提交到持久化存储磁盘中,也就是下图中的黑色虚线框住的流程四;

MVCC 查询 key 原理

完成 put hello 为 world1 操作后,这时你通过 etcdctl 发起一个 get hello 操作,MVCC 模块首先会创建一个读事务对象(TxnRead),在 etcd 3.4 中 Backend 实现了 ConcurrentReadTx, 也就是并发读特性;

并发读特性的核心原理是创建读事务对象时,它会全量拷贝当前写事务未提交的 buffer 数据,并发的读写事务不再阻塞在一个 buffer 资源锁上,实现了全并发读;

如上图所示,在读事务中,它首先需要根据 key 从 treeIndex 模块获取版本号,因我们未带版本号读,默认是读取最新的数据。treeIndex 模块从 B-tree 中,根据 key 查找到 keyIndex 对象后,匹配有效的 generation,返回 generation 的 revisions 数组中最后一个版本号{2,0}给读事务对象;

读事务对象根据此版本号为 key,通过 Backend 的并发读事务(ConcurrentReadTx)接口,优先从 buffer 中查询,命中则直接返回,否则从 boltdb 中查询此 key 的 value 信息;

通过指定版本号来读取历史记录的实现

当你再次发起一个 put hello 为 world2 修改操作时,key hello 对应的 keyIndex 的结果如下面所示,keyIndex.modified 字段更新为 <3,0>,generation 的 revision 数组追加最新的版本号 <3,0>,ver 修改为 2;

boltdb 插入一个新的 key revision{3,0},此时存储到 boltdb 中的 key-value 数据如下:

这时你再发起一个指定历史版本号为 2 的读请求时,实际是读版本号为 2 的时间点的快照数据。treeIndex 模块会遍历 generation 内的历史版本号,返回小于等于 2 的最大历史版本号,在我们这个案例中,也就是 revision{2,0},以它作为 boltdb 的 key,从 boltdb 中查询出 value 即可;

MVCC 删除 key 原理

etcd 实现的是延期删除模式,原理与 key 更新类似。当你执行 etcdctl del hello 命令时,etcd 会增加一个标记实现延迟删除(lazy delete);

与更新 key 不一样之处在于:
1)生成的 boltdb key 版本号{4,0,t}追加删除标识(tombstone, 简写 t),boltdb value 变成只含用户 key 的 KeyValue 结构体;
2)treeIndex 模块也会给此 key hello 对应的 keyIndex 对象,追加一个空的 generation 对象,表示此索引对应的 key 被删除了;

当你再次查询 hello 的时候,treeIndex 模块根据 key hello 查找到 keyindex 对象后,若发现其存在空的 generation 对象,并且查询的版本号大于等于被删除时的版本号,则会返回空;

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

boltdb 此时会插入一个新的 key revision{4,0,t},此时存储到 boltdb 中的 key-value 数据如下:

删除 Key 的时机

那么 key 打上删除标记后有哪些用途呢?什么时候会真正删除它呢?

一方面删除 key 时会生成 events,Watch 模块根据 key 的删除标识,会生成对应的 Delete 事件;

另一方面,当你重启 etcd,遍历 boltdb 中的 key 构建 treeIndex 内存树时,你需要知道哪些 key 是已经被删除的,并为对应的 key 索引生成 tombstone 标识。而真正删除 treeIndex 中的索引对象、boltdb 中的 key 是通过压缩 (compactor) 组件异步完成;

正因为 etcd 的删除 key 操作是基于以上延期删除原理实现的,因此只要压缩组件未回收历史版本,我们就能从 etcd 中找回误删的数据;

参考文献

极客时间 /etcd 实战课(唐聪,腾讯云资深工程师,etcd 活跃贡献者)
《etcd 工作笔记:架构分析、优化与最佳实践》
etcd/Documentation versions