07 - MVCC：如何实现多版本并发控制？

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

MVCC 架构

|600

treeIndex 模块基于内存版 B-tree 实现了 key 索引管理，它保存了用户 key 与版本号（revision）的映射关系等信息。
Backend 模块负责 etcd 的 key-value 持久化存储，主要由 ReadTx、BatchTx、Buffer 组成，ReadTx 定义了抽象的读事务接口，BatchTx 在 ReadTx 之上定义了抽象的写事务接口，Buffer 是数据缓存区。
etcd 支持多种 Backend 实现，目前使用 boltdb。boltdb 是一个基于 B+ tree 实现的、支持事务的 key-value 嵌入式数据库。

treeIndex

为什么需要 treeIndex？

treeIndex 中存放 key 的历史记录信息，具体参考下面的数据结构。

为什么使用 B 树？

为了支持范围查询，那么保存索引等数据结构也需要支持范围查询。例如，要获取所有以 /my/prefix/ 开头的键。
B 树相对于平衡二叉树，高度更低，节点存储数据更多。

treeIndex 的实现方式

Google 的开源项目 btree，使用 Go 实现了内存版 B-tree。基于 btree 库实现了 treeIndex 模块。
每个节点的 key 是一个 keyIndex 结构

type keyIndex struct {
  key         []byte //用户的 key 名称，比如 "hello"
  modified    revision //最后一次修改 key 时的 etcd 版本号,比如上面案例中的刚写入 hello 为 world1 时的，版本号为 2
  generations []generation //generation 保存了一个 key 若干代版本号信息，每代中包含对 key 的多次修改的版本号列表
}
type generation struct {
  ver     int64    //表示此 key 的修改次数
  created revision //表示 generation 结构创建时的版本号
  revs    []revision //每次修改 key 时的 revision 追加到此数组
}
type revision struct {
  main int64    // 一个全局递增的主版本号，随 put/txn/delete 事务递增，一个事务内的 key main 版本号是一致的
  sub int64    // 一个事务内的子版本号，从 0 开始随事务内 put/delete 操作递增
}

怎么基于 treeIndex 找到历史数据？

比如找到某个 key 在历史版本号为 2 时的数据，treeIndex 模块会遍历 generation 内的历史版本号，返回这个 key 小于等于 2 的最大历史版本号，以它作为 boltdb 的 key，从 boltdb 中查询出 value 即可。

MVCC 更新 key 原理

|500

首先，从 treeIndex 中获取 key 对应的索引信息，包含创建版本号、修改次数等信息。
其次，全局版本号自增，作为新的版本号，如 revision{2,0}。该版本号为 boltdb 的 key，value 是 mvccpb.KeyValue 结构体，由 key + value + create_revision + mod_revision + version + lease 组成，写入到 boltdb 和 buffer 中。
create_revision = keyIndex.generations[i].created ，当前 key 创建时的全局版本号，本例子为 2。
mod_revision 最后一次修改时版本号
version = keyIndex.generations[i].ver + 1
然后，将本次修改的版本号和 key 保存到 treeIndex 模块中。

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

下一次再保存，boltdb 内容示例

MVCC 查询 key 原理

在早期的 etcd 版本中，读操作是通过独占锁（ReadLock）实现的，这会导致以下问题：

读性能瓶颈：即使多个读操作之间没有冲突，它们也需要串行执行，无法充分利用多核 CPU 的优势。
写操作阻塞：写操作需要获取写锁（WriteLock），而读锁和写锁是互斥的，这会导致写操作被读操作阻塞。

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

具体来说，etcd 会创建一个 ConcurrentReadTx，ConcurrentReadTx 基于当前的存储状态创建一个快照视图。读操作直接访问快照视图中的数据，不需要获取锁。

在事务内，首先根据 key 从 treeIndex 模块获取有效的版本号。查询没带版本号，那就 generation.revisions[-1]。然后，根据这个版本号 key 从 buffer、boltdb 读。

MVCC 删除 key 原理

MVCC 采取延迟删除 key，例如 boltdb 版本号为 {4,0,t}，追加了删除标识(tombstone,简写 t)，同时boltdb value 变成只含 key 的 KeyValue 结构体。treeIndex 模块，添加一个空的 generation 对象