etcd原理之mvcc机制

什么是MVCC

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

在 MVCC 数据库中，你更新一个 key-value数据的时候，它并不会直接覆盖原数据，而是新增一个版本来存储新的数据，每个数据都有一个版本号。

当你指定版本号读取数据时，它实际上访问的是版本号生成那个时间点的快照数据。当你删除数据的时候，它实际也是新增一条带删除标识的数据记录。

ETCD的实现

首先etcd在内存中使用b-tree维护了key与版本号revision的关系树treeIndex，再以revision作为boltdb的key存放value，boltdb内部同样使用b-tree作为查找结构。

get/put操作key首先在treeindex中查找/构建对应的版本revision，然后用revision作为key到boltdb中读写value。

treeIndex中每一个叶子节点为一个keyIndex结构。

type keyIndex struct {
   key         []byte //用户的key名称，比如我们案例中的"hello"
   modified    revision //最后一次修改key时的etcd版本号,比如我们案例中的刚写入hello为world1时的，版本号为2
   generations []generation //generations 表示一个 key 从创建到删除的过程，每代对应 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操作递增
}

boltdb中存储的Value为mvccpb.KeyValue结构。

type KeyValue struct {
    Key []byte
    CreateRevision int64 // 表示此 key 创建时的版本号
    ModRevision int64 // 表示 key 最后一次修改时的版本号
    Version int64 // 表示此 key 的修改次数
    Value []byte
    Lease int64
}

ETCD MVCC读写

更新key

初始化一个新集群，全局版本号默认为 1。

执行下面的 txn 事务，它包含两次 put、一次 get 操作，那么按照我们上面介绍的原理，全局版本号随读写事务自增，因此是 main 为 2，sub 随事务内的 put/delete 操作递增，因此 key hello 的 revison 为{2,0}，key world 的 revision 为{2,1}。

$ etcdctl txn -i
compares:

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

第一次创建 hello key，此时 keyIndex 索引为空，etcd会根据当前的全局版本号（空集群启动时默认为 1）自增，生成put hello操作对应的版本号revision{2,0}，这就是boltdb的key。

boltdb的value是mvccpb.KeyValue结构体，由key、value、create_revision、mod_revision、version、lease 组成。

{
    "key": "aGVsbG8=",
    "create_version": 2,
    "mod_version": 2,
    "version": 1,
    "value": "Mg=="
}

因为 key hello是首次创建，treeIndex会生成 key hello对应的keyIndex对象。

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

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

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

读取key

在读事务中，它首先需要根据 key从treeIndex 模块获取版本号，未带版本号读，默认是读取最新的数据。

treeIndex从b-tree中，根据key查找到keyIndex对象后，匹配有效的generation，返回generation的revisions数组中最后一个版本号{2,0}给读事务，读事务根据此版本号为key，从boltdb中查询此key的value信息。

删除key

与更新key生成botldb key相比，删除key生成的boltdb key 版本号{4,0,t}追加了删除标识(tombstone, 简写t)，treeIndex会给此 key hello 对应的keyIndex对象，追加一个空的generation对象，表示此索引对应的key被删除了。

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

文章目录