MVCC机制的核心思想是保存一个key-value数据的多个历史版本,etcd基于它不仅实现了可靠的Watch机制,避免了client频繁发起expensive request操作,
保证etcd集群稳定性。MVCC实现各类隔离级别的事务,保障事务的安全性,是事务特性的基础。
什么是MVCC
MVCC机制是基于多版本技术实现的一种乐观锁机制。
当指定版本号读取数据时,它是机上访问的是版本号生成那个时间点的快照数据。
MVCC模块将请求划分为两个请求,分别是读事务和写事务。读事务负责处理range请求,写事务负责put/delete请求。读写事务基于treeIndex、Background/boltdb
提供的能力,实现对key-value的增删改查功能。
treeIndex模块基于内存版B-Tree实现了key索引管理,它保存了用户key与版本号的映射关系等信息。
Backend模块负责etcd的key-value持久化存储,主要由ReadTx、BatchTx、Buffer组成,ReadTx定义了抽象的读事务接口,BatchTx在ReadTx之上定义了
抽象的写事物接口,Buffer是数据缓存区。
etcd设计上支持多种Backend实现,目前实现的Backend是boltdb。boltdb是一个基于B+tree实现的、支持事务的key-value嵌入式数据库。
TreeIndex
在etcd v3中引入treeIndex模块是为了解决无法支持保存key的历史版本,支持保存key的历史版本,提供稳定的Watch机制和事务隔离等能力。
etcd在每次修改key时会生成一个全局递增的版本号,然后通过数据结构B-tree保存用户key与版本号之间的关系,再以版本号作为boltdb key,
以用户的key-value等信息作为botldb value,保存到boltdb。
哈希表不适合范围查询,平衡二叉树每个节点只能容纳一个数据、导致数的高度较高,B-tree支持范围查询、每个节点可以容纳多个数据,数的高度更低,更扁平,
具有优越的增、删、改、查性能。
在TreeIndex中,每个节点的key是一个keyIndex结构,etcd是通过这个结构保存了用户的key与版本号的映射关系。
type keyIndex struct {
key []byte // 用户的key
modified revision // 最后一次修改key的etcd版本号
generations []generation //generation保存了一个key若干代版本号信息,每代中包含对key的多次修改的版本号列表
}
generations表示一个key从创建到删除的过程,每代对应key的一个生命周期的开始和结束。
type generation struct {
ver int64 //表示此key对的修改次数
created revision //表示generation结构创建时的版本号
revs []revision //每次修改key时的revision追加到此数组
}
generation结构中包含此key的修改次数、generation创建时的版本号、对此key的修改版本号记录列表。
type revision struct {
main int64 //一个全局递增的主版本号,随put/tx/delete事务递增,一个事务内的key main版本号是一致的
sub int64 //一个事务内的子版本号,从0开始随事务内put/delete操作递增
}
revision包含main和sub两个字段,main是全局递增的版本号,它是etcd逻辑时钟,随着put/txn/delete等事务递增。sub是一个事务内的子版本号,从0开始随事务内
的put/delete操作递增。
MVCC 更新key原理
在put写事务中,需要从treeIndex模块中查询key的keyIndex索引信息,keyIndex中存储了key的创建版本号、修改的次数等信息,这些信息存储在boltdb中。
其次etcd会根据当前的全局版本号自增,生成put操作对应的版本号<2,0>这就是boltdb的key。
boltdb的value是mvccpb.KeyValue结构体,由用户key、value、create_version、mod_revision、version、lease组成。
- create_version表示此key创建时的版本号。在修改key时,写事务会从treeIndex模块查询key第一次创建的版本号,也就是keyIndex.generations[i].created
字段,赋值给create_revision字段。- mod_revision:key最后一次修改时的版本号,即put操作发生时的全局版本号加1。
- version表示key的修改次数。
此时数据还并未持久化,为了提升etcd的写吞吐量、性能,一般情况下(默认堆积的写事务大于1万才在写事务结束时同步持久化),数据持久化有Backend的异步
goroutine完成,通过事务批量提交,定期将boltdb页缓存的脏数据提交到持久化存储磁盘中.
MVCC 查询key原理
在etcd 3.4中Backedn实现了ConcurrentReadTx,就是并发独特性。
并发独特性的核心是创建读事务对象时,它会全量拷贝当前写事务未提交的buffer,并发的读事务不在阻塞在一个buffer资源锁上,实现了全并发读。
如果从buffer里面读取不到数据,去boltdb里面读取数据。
指定版本号读取历史数据又是怎么实现:treeIndex模块会遍历generation内的历史版本号,返回小于等于指定版本号的最大历史版本号。
MVCC删除key原理
etcd实现的是延期删除模式。
在删除key的时候,生成的boltdb key版本号{txid,0,t}追加了删除标识。另一个方面treeIndex模块也会给此key对应的keyIndex对象,追加一个空的generation
对象,表示此索引对应的key被删除了。
再次查询key的时候,treeIndex模块根据key查到keyIndex对象后,如果发现存在空的generation对象,并且查询的版本号大于等于被删除时的版本号,则返回空。
什么时候真正删除:
- 删除key时会生成events,Watch模块根据key的删除标识,会生成对应的delete事件。
- 重启etcd,遍历boltdb中的key构建treeIndex内存树时,需要知道那些key索引生成tombstone标识。真正删除treeIndex中的索引对象、boltdb中的key是通过
压缩组建异步完成。
etcd采用延迟删除,是为了保证key对应的watcher能够获取到key的所有状态信息,留给watcher时间做相应的处理;实时从boltdb删除key可能会触发树的不平衡,影响其他读写请求的性能。
网友评论