08、MVCC原理

本篇内容主要来源于自己学习的视频，如有侵权，请联系删除，谢谢。

1、什么是 MVCC

MVCC（Multiversion concurrency control）是一个基于多版本技术实现的一种并发控制机制。

常见的并发机制有哪些？MVCC 的优点在哪里呢？

• 比如数据库中的悲观锁，也就是通过锁机制确保同一时刻只能有一个事务对数据进行修改操作，常见的实现方案有读写锁、互斥锁、两阶段锁等。

悲观锁是一种事先预防机制，它悲观地认为多个并发事务可能会发生冲突，因此它要求事务必须先获得锁，才能进行修改数据操作。但是悲观锁粒度过大、高并发场景下大量事务会阻塞等，会导致服务性能较差。

MVCC 机制正是基于多版本技术实现的一种乐观锁机制，它乐观地认为数据不会发生冲突，但是当事务提交时，具备检测数据是否冲突的能力。

在 MVCC 数据库中，你更新一个 key-value 数据的时候，它并不会直接覆盖原数据，而是新增一个版本来存储新的数据，每个数据都有一个版本号。版本号它是一个逻辑时间，为了方便你深入理解版本号意义，在下面我给你画了一个 etcd MVCC 版本号时间序列图。

• 随着时间增长，你每次修改操作，版本号都会递增。每修改一次，生成一条新的数据记录。
• 当你指定版本号读取数据时，它实际上访问的是版本号生成那个时间点的快照数据。
• 当你删除数据的时候，它实际也是新增一条带删除标识的数据记录。

2、MVCC 特性初体验

# 更新key hello为world1
$ etcdctl put hello world1
OK

# 通过指定输出模式为json,查看key hello更新后的详细信息
$ etcdctl get hello -w=json
{
    "kvs":[
        {
            "key":"aGVsbG8=",
            "create_revision":2,
            "mod_revision":2,
            "version":1,
            "value":"d29ybGQx"
        }
    ],
    "count":1
}

# 再次修改key hello为world2
$ etcdctl put hello world2
OK

# 确认修改成功,最新值为wolrd2
$ etcdctl get hello
hello
world2

# 指定查询版本号,获得了hello上一次修改的值
$ etcdctl get hello --rev=2
hello
world1

# 删除key hello
$ etcdctl del  hello
1

# 删除后指定查询版本号3,获得了hello删除前的值
$ etcdctl get hello --rev=3
hello
world2

3、整体架构

整个 MVCC 特性由 treeIndex、Backend/boltdb 组成。

当你执行 MVCC 特性初体验中的 put 命令后，请求经过 gRPC KV Server、Raft 模块流转，对应的日志条目被提交后，Apply 模块开始执行此日志内容。

思考:etcd是如何实现MVCC多版本控制的?

下图是 MVCC 模块的一个整体架构图，整个 MVCC 特性由 treeIndex、Backend/boltdb 组成。
当你执行 put 命令后，请求经过 gRPC KV Server、Raft 模块流转，对应的日志条目被提 交后，Apply 模块开始执行此日志内容。

• Apply 模块通过 MVCC 模块来执行 put 请求，持久化 key-value 数据。
• MVCC 模块将请求请划分成两个类别，分别是读事务(ReadTxn)和写事务 (WriteTxn)。读事务负责处理 range 请求，写事务负责 put/delete 操作。读写 事务基于 treeIndex、Backend/boltdb 提供的能力，实现对 key-value 的增删改查 功能。
• treeIndex 模块基于内存版 B-tree 实现了 key 索引管理，它保存了用户 key 与 版本号(revision)的映射关系等信息。
• Backend 模块负责 etcd 的 key-value 持久化存储，主要由 ReadTx、BatchTx、Buffer 组成，ReadTx 定义了抽象的读事务接口，BatchTx 在 ReadTx 之上定义了抽象的写事务接口，Buffer 是数据缓存区。

etcd 设计上支持多种 Backend 实现，目前实现的 Backend 是 boltdb。boltdb 是一个基于 B+ tree 实现的、支持事务的 key-value 嵌入式数据库。

4、treeIndex 原理

etcd 保存用户 key 与版本号映射关系的数据结构 B-tree

• 从 etcd 的功能特性上分析， 因 etcd 支持范围查询，因此保存索引的数据结构也必须支持范围查询才行。所以哈希表不适合，而 B-tree 支持范围查询。
• 从性能上分析，平横二叉树每个节点只能容纳一个数据、导致树的高度较高，而 B-tree 每个节点可以容纳多个数据，树的高度更低，更扁平，涉及的查找次数更少，具有优越的增、删、改、查性能。

Google 开源项目:

• btree

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

• 在一个度为 d 的 B-tree 中，节点保存的最大 key 数为 2d - 1，否则需要进行平衡、分裂操作。
• 在 etcd treeIndex 模块中，创建的是最大度 32 的 B-tree，也就是一个叶子节点最多可以保存 63 个 key。

上面是 b-tree 的一个基本介绍，接下来看看 etcd 中的 treeIndex。

对于 etcd v2 来说，当你通过 etcdctl 发起一个 put hello 操作时，etcd v2 直接更新内存 树，这就导致历史版本直接被覆盖，无法支持保存 key 的历史版本。

在 etcd v3 中引入 treeIndex 模块正是为了解决这个问题，支持保存 key 的历史版本，提供稳定的 Watch 机制和事务隔离等能力。
etcd 在每次修改 key 时会生成一个全局递增的版本号(revision)。

然后通过数据结构 B-tree 保存用户 key 与版本号之间的关系;

再以版本号作为 boltdb key，以用户的 key-value 等信息作为 boltdb value，保存到 boltdb。

根据上述存储逻辑可知，boltdb 中只能通过reversion来查询数据,但是客户端都是通过 key 来查 询的。所以 etcd 在内存中使用 treeIndex 模块维护了一个kvindex,保存的就是 key-reversion 之 间的映射关系，用来加速查询。

这里有一个疑问，那就是 etcd server 重启后，内存中的 treeIndex 数据就不存在了，那 etcd 是如何查询的呢？

etcd是一个分布式键值存储系统，它用于在集群中保持共享配置数据和协调状态。在etcd中，树状结构被用来组织和存储键值对。

当etcd服务器重启后，内存中的treeIndex数据确实会丢失，因为treeIndex是内存中的数据结构，用于快速索引和查找键值对。但是，etcd具有持久化存储机制，它将数据写入磁盘以在重启后恢复数据。

具体来说，etcd使用一种称为WAL（Write-Ahead Log）的机制来持久化数据。每当在etcd中进行更改（比如添加、更新或删除键值对）时，这些更改会被追加到WAL日志中。WAL日志是一个顺序写入的日志文件，它确保了数据的持久性和一致性。

在etcd启动时，它会读取WAL日志文件并重新构建内存中的树状结构。通过读取WAL日志，etcd可以恢复先前保存的键值对和相应的索引信息，包括treeIndex。这样，即使etcd服务器重启，它仍然可以在重启后查询数据。

需要注意的是，由于etcd的持久化机制依赖于WAL日志，如果WAL日志文件损坏或丢失，可能会导致数据不一致或丢失。因此，在生产环境中，通常会配置etcd的快照和备份策略，以确保数据的安全性和可靠性。

当你发起一个get hello命令时，从treelndex中获取 key 的版本号，然后再通过这个版本 号，从 boltdb获取value信息。boltdb的value是包含用户key-value、各种版本号、lease 信息的结构体。

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

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

注意未删除之前，后续的操作都是往0代中追加版本号。

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

generation结构中包含此 key的修改次数、generation创建时的版本号、对此 key 的修改 版本号记录列表。

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操作递增。

5、MVCC更新key原理

第一步:查询 keyIndex
首先它需要从 treeIndex 模块中查询 key 的 keyIndex 索引信息。keyIndex 中存储了 key 的创建版本号、修改的次数等信息，这些信息在事务中发挥着重要作用，因此会存储在 boltdb 的 value 中。

第二步:写入 boltdb
其次 etcd 会根据当前的全局版本号(空集群启动时默认为 1)自增，生成 put hello 操作 对应的版本号 revision{2,0}，这就是 boltdb 的 key。
boltdb 的 value 是 mvccpb.KeyValue 结构体，它是由用户 key、value、 create_revision、mod_revision、version、lease 组成。它们的含义分别如下:

• **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 字段。

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

注意这里有两个缓存:

• boltdb 缓存 (内存页, 应该是 mmap)
• buffer (加速读)

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

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

因为 key hello 是首次创建，treeIndex 模块它会生成 key hello 对应的 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 数组中。

第四步:持久化
通过以上流程，一个 put 操作终于完成，但是此时数据还并未持久化。

为了提升 etcd 的写吞吐量性能，一般情况下（默认堆积的写事务数大于 1 万才在写事务结束时同步持久化），数据持久化由 Backend 的异步 goroutine 完成，它通过事务批量提交，定时将 boltdb 页缓存中的脏数据提交到持久化存储磁盘中。

6、MVCC查询key原理

执行 get 命令时，MVCC 模块首先会创建一个读事务对象(TxnRead)。在 etcd 3.4 中 Backend 实现了 ConcurrentReadTx， 也就是并发读特性。

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

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

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

指定版本号读取历史记录又是怎么实现的呢？

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

key hello的keyIndex:

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

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

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

7、MVCC删除key原理

当执行 del 命令时 etcd 实现的是延期删除模式，原理与 key 更新类似。 与更新 key 不一样之处在于:

• 一方面，生成的 boltdb key 版本号{4,0,t}追加了删除标识(tombstone, 简写 t)，boltdb value 变成只含用户 key 的 KeyValue 结构体。

• 另一方面 treeIndex 模块也会给此 key hello 对应的 keyIndex 对象，追加一个 空的 generation 对象，表示此索引对应的 key 被删除了。

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

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

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

• 另一方面，当你重启 etcd，遍历 boltdb 中的 key 构建 treeIndex 内存树时， 你需要知道哪些 key 是已经被删除的，并为对应的 key 索引生成 tombstone 标 识。

而真正删除 treeIndex 中的索引对象、boltdb 中的 key 是通过压缩 (compactor) 组件异步完成。

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