MVCC

MVCC（Multi-version Cocurrent Control）即多版本并发控制技术，多用于数据库中的事务管理，其基本思想是保存一个数据的多个历史版本，从而解决事务管理中数据隔离的问题。

这里的版本一般选择使用时间戳或事务ID来标识。在处理一个写请求时，MVCC不是简单的用新值覆盖旧值，而是为这一项添加一个新版本的数据。在读取一个数据项时，要先确定一个要读取的版本，然后根据版本找到对应的数据。这种写操作创建新版本，读操作访问旧版本的方式使得读写操作彼此隔离，他们之间就不需要用锁来协调。换句话说，在MVCC里读操作永远不会被阻塞，因此它特别适合etcd这种读操作比较多的场景。

MVCC的基本原理就是这么简单，下面来结合具体代码，看看etcd是怎么实现的。

数据结构

etcd的代码中，有关MVCC的实现都在一个叫mvcc的包里。在正式介绍读写流程之前，我们先来了解下这个包里面定义的几个基础数据结构。

revision

MVCC的每一个写操作都会创建一个新版本的数据，读操作会从有限多个版本的数据中挑选一个“最合适”(要么是最新版本，要么是指定版本) 的结果直接返回。通过这种方式，读写操作之间的冲突就不再需要受到关注。MVCC能最大化地实现高效的读写并发，尤其是高效的读，因此其非常适合etcd这种“读多写少”的场景。

前面已经说过，etcd v3存储的逻辑视图是一个扁平的二进制键空间。该键空间对key有一个词法排序索引，因此范围查询的成本很低。

etcd的键空间可维护多个revision。每个原子的修改操作(例如，一个事务操作可能包含多个操作)都会在键空间上创建一个新的revision。之前revision的所有数据均保持不变。旧版本(version)的key仍然可以通过之前的revision进行访问。同样，revision也是被索引的，因此Watcher可以实现高效的范围watch。revision在etcd中可以起到逻辑时钟的作用。revision在群集的生命周期内是单调递增的。如果因为要节省空间而压缩键空间，那么在此revision之前的所有revision都将被删除，只保留该revision 之后的。

我们将key的创建和删除过程称为一个生命周期。在etcd中，每个key都可能有多个生命周期，也就是说被创建、删除多次。创建一个新key时，如果在当前revision中该key不存在(即之前也没有创建过)，那么它的version就会被设置成1。删除key会生成一个key的墓碑，可通过将其version重置为0来结束key的当前生命周期。对key的每一次修改都会增加其version，因此，key的version在key的一次生命周期中是单调递增的。

revison是集群存储状态的版本号，存储状态的每一次更新(例如，写、删除、事务等)都会让revison 的值加1。

ResponseHeader.Revision代表该请求成功执行之后etcd的revision。
KeyValue.CreateRevision代表etcd的某个key最后一次创建时etcd的revison
KeyValue.ModRevision则代表etcd的某个key最后一次更新时etcd的revison。

verison特指etcd键空间某个key从创建开始被修改的次数，即 KeyValue.Versiono etcd v3 支持的 Get ( …, WithRev(rev)) 操作会获取etcd处于rev这个revision时的数据，就好像etcd的revision还是rev 的时候一样。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// A revision indicates modification of the key-value space.
// The set of changes that share same main revision changes the key-value space atomically.
type revision struct {
    // main is the main revision of a set of changes that happen atomically.
    main int64

    // sub is the the sub revision of a change in a set of changes that happen
    // atomically. Each change has different increasing sub revision in that
    // set.
    sub int64
}

这里的main属性对应事务ID，全局递增不重复，它在etcd中被当做一个逻辑时钟来使用。sub代表一次事务中不同的修改操作（如put和delete）编号，从0开始依次递增。所以在一次事务中，每一个修改操作所绑定的revision依次为{txID, 0}, {txID, 1}, {txID, 2}…

keyIndex

etcd将物理数据存储为一棵持久B+树中的键值对。为了高效，每个revision的存储状态都只包含相对于之前revision的增量。一个revision可能对应于树中的多个key。

B+树中键值对的key即revision, revision是一个2元组(main, sub)，其中main是该revision的主版本号（每次事务发起时+1），sub是同一revision的副版本号（事务中每次修改命令+1），其用于区分同一个revision的不同key。 B+树中键值对的value包含了相对于之前revision的修改，即相对于之前revision的一个增量。

B+树按key的字典字节序进行排序。这样，etcd对revision增量的范围查询(range query，即从某个 revision 到另一个 revision)会很快一一因为我们已经记录了从一个特定revision到其他revision的修改量。etcd v3 的压缩操作会删除过时的键值对。

etcd v3还在内存中维护了一个基于B树的二级索引来加快对key的范围查询。该B树索引的key是向用户暴露的etcd存储的key，而该B树索引的value则是一个指向上文讨论的持久化B+树的增量的指针。etcd的压缩操作会删除指向B树索引的无效指针。

keyIndex用来记录一个key的生命周期中所涉及过的版本（revision）。

1
2
3
4
5


type keyIndex struct {
    key         []byte
    modified    revision // the main rev of the last modification
    generations []generation
}

它保存的是当前key的具体值（key），最近一次修改的版本号（modified），以及记录key生命周期的generation，一个generation代表了一个key从创建到被删除的过程。因为一个key可能会经历创建 -> 删除 -> 创建的好几个轮回，所以它有可能会有一个或多个generation。下面来看看一个generation包含哪些内容：

1
2
3
4
5
6


// generation contains multiple revisions of a key.
type generation struct {
    ver     int64
    created revision // when the generation is created (put in first revision).
    revs    []revision
}

可以看到，一个generation中最重要的信息就是那个revision数组，代表在它这一代中，所经历过的版本变更。

假设我们有一个值为foo的key

1

ki := &keyIndex{key: []byte("foo")}

为它记录两次版本变更

1
2


ki.put(zap.NewExample(), 2, 0) // 第一次变更发生在ID为2的事务中，且是第一次操作
ki.put(zap.NewExample(), 4, 2) // 第二次变更发生在ID为4的事务中，且是第三次操作

那这个keyIndex变成这样的结构

1
2
3
4


key: "foo"
modified: {4, 2}
generations:
    [{2, 0}, {4, 2}]

如果在此后的事务中这个key经历了被删除，再创建的过程：

1
2
3


ki.tombstone(zap.NewExample(), 6, 0)  // 在第6次事务中被删除
ki.put(zap.NewExample(), 8, 0)
ki.put(zap.NewExample(), 10, 0)

那它会多一个generation

1
2
3
4
5


key: "foo"
modified: {10, 0}
generations:
    [{2, 0}, {4, 2}, {6, 0}(t)],
    [{8, 0}, {10, 0}]

好了，在知道了key的版本信息及相应的操作后，我们来看看怎么把它们组织起来：

treeIndex

treeIndex顾名思义就是一个树状索引，它通过在内存中维护一个BTree，来达到加速查询key的功能。

这棵树的每一个节点都是keyIndex。这样，给定一个key就能很快查到它对应的keyIndex，进而可以得知它的版本信息。树状结构比较简单，看看图就能明白，我就不再分析了。

值得注意的是，这里只存有key的信息，value保存在磁盘里，一方面key一般比较小，同样的内存可以支持存储更多的key；另一方面，value和版本是一一对应的，内存中维护了版本的信息，也就没必要再多存一份value了。

看完了key以及key在内存中的组织结构，我们再来看看value是怎么处理的。

backend

backend封装了etcd中的存储，按照设计，backend可以对接多种存储，当前使用的是boltdb，但作为一个CNCF项目，官方也在考虑接入更多的存储引擎1。boltdb是一个单机的支持事务的KV存储，etcd的事务是基于boltdb的事务实现的。

BoltDB是基于B树和mmap的数据库，基本原理是用mmap将磁盘的page映射到内存的page，而操作系统则是通过COW (copy-on-write) 技术进行page管理，通过cow技术，系统可实现无锁的读写并发，但是无法实现无锁的写写并发，这就注定了这类数据库读性能超高，但写性能一般，因此非常适合于“读多写少”的场景。同时BoltDB支持完全可序列化的ACID事务。因此最适合作为etcd的底层存储引擎。

我们知道，etcd v3当前使用BoltDB将数据存储在磁盘中。etcd在BoltDB中存储的key是reversion, value是etcd自己的key-value组合，也就是说etcd会在BoltDB中保存每个版本，从而实现多版本机制。

这样的实现方式有一个很明显的问题，那就是如果保存一个key的所有历史版本，那么整个数据库就会越来越大，最终超出磁盘的容量。因此MVCC还需要定期删除老的版本，etcd提供了命令行工具以及配置选项，供用户手动删除老版本数据，或者每隔一段时间定期删除老版本数据，etcd中称这个删除老版本数据的操作为数据压缩(compact)。

了解了etcd v3的磁盘存储之后，可以看到要想从BoltDB中查询数据，必须通过reversion，但是客户端都是通过key来查询value的，所以etcd在内存中还维护了一个kvindex，保存的就是key与reversion之前的映射关系，用来加速查询的。kvindex，是基于Google开源的Golang的B树实现的，也就是前文提到的etcdv3在内存中维护的二级索引。这样当客户端通过key来查询value的时候，会先在kvindex中查询这个key的所有revision，然后再通过revision从BoltDB中查询数据。

etcd在boltdb中存储的key是reversion，value是etcd自己的key-value组合。因此，每次更新时，新的reversion会被记在keyIndex中，同时，这个reversion所对应的key-value组合会被存到boltdb中。

举个例子：用etcdctl通过批量接口写入两条记录：

1
2
3
4


etcdctl txn <<<'
put key1 "v1"
put key2 "v2"
'

再通过批量接口更新这两条记录：

1
2
3
4


etcdctl txn <<<'
put key1 "v12"
put key2 "v22"
'

boltdb中其实有了4条数据：

1
2
3
4


rev={3 0}, key="key1", value="v1"
rev={3 1}, key="key2", value="v2"
rev={4 0}, key="key1", value="v12"
rev={4 1}, key="key2", value="v22"

所以总的来说，内存btree维护的是key => keyIndex的映射，keyIndex内维护多版本的revision信息，而revision可以映射到磁盘bbolt中具体的value。下面这个图很好的表示了这个过程：

日志与快照

etcd对数据的持久化，采用的是binlog(日志，也称为WAL, 即Write-Ahead-Log)加Snapshot(快照)的方式。

在计算机科学中，预写式日志(Write-Ahead-Log,WAL)是关系数据库系统中用于提供原子性和持久性的一系列技术。在使用WAL的系统中，所有的修改在提交之前都要先写入log文件中。

log文件中通常包括redo信息和undo信息。假设一个程序在执行某些操作的过程中机器掉电了。在重新启动时，程序可能需要知道当时执行的操作是完全成功了还是部分成功了或者是完全失败了。如果使用了WAL，那么程序就可以检查log文件，并对突然掉电时计划执行的操作内容与实际上执行的操作内容进行比较。在这个比较的基础上，程序就可以决定是撤销已做的操作还是继续完成己做的操作，或者只是保持原样。

etcd数据库的所有更新操作都需要先写到binlog中，而binlog是实时写到磁盘上的，因此这样就可以保证不会丢失数据，即使机器断电，重启以后etcd也能通过读取并重放binlog里的操作记录来重建整个数据库。

etcd数据的高可用和一致性是通过Raft来实现的，Master节点会通过Raft协议向Slave节点复制binlog, Slave节点根据binlog对操作进行重放，以维持数据的多个副本的一致性。也就是说binlog不仅仅是实现数据库持久化的一种手段，其实还是实现不同副本间一致性协议的最重要手段。客户端对数据库发起的所有写操作都会记录在binlog中，待主节点将更新日志在集群多数节点之间完成同步以后，便在内存中的数据库中应用该日志项的内容，进而完成一次客户的写请求。

如果一个etcd集群运行了很久，那么就会有很多binlog，这样在故障恢复时，需要花很多时间来复原数据，这时候就需要快照系统，它会把当前存储的当前数据存储下来。然后删除生成快照之前的log内容，这样只需要重现少量的log就能恢复数据了。

etcd v3的日志管理和快照管理的流程与v2的基本一致，区别是做快照的时候etcd v2是把内存里的数据库序列化成JSON，然后持久化到磁盘，而etcd v3是读取磁盘里的数据库的当前版本(从BoltDB中读取)，然后序列化到磁盘。

写操作

首先写操作的入口是applierV3的Put函数，它开启一个写事务，然后进过层层封装，最后干活的是写事务的put函数，精简后的逻辑大概是这样的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


// https://github.com/etcd-io/etcd/blob/v3.3.10/mvcc/kvstore_txn.go#L151
func (tw *storeTxnWrite) put(key, value []byte, leaseID lease.LeaseID) {
    rev := tw.beginRev + 1

    ibytes := newRevBytes()
    idxRev := revision{main: rev, sub: int64(len(tw.changes))}
    revToBytes(idxRev, ibytes)

    kv := mvccpb.KeyValue{
        Key:            key,
        Value:          value,
        CreateRevision: c,
        ModRevision:    rev,
        Version:        ver,
        Lease:          int64(leaseID),
    }
    d, err := kv.Marshal()

    tw.tx.UnsafeSeqPut(keyBucketName, ibytes, d)
    tw.s.kvindex.Put(key, idxRev)
    tw.changes = append(tw.changes, kv)
}

正如前面所分析的，这里的put操作首先获取了当前事务的ID（tw.beginRev），以及当前事务中已经进行过的更改数（tw.changes），然后以此为基础生成了revision，并向boltdb和treeIndex分别执行了两次写入操作。

读操作

读操作的入口是applierV3的Range函数，跟写操作一样，它开启了一个只读事务，然后一路调用到rangeKeys函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// https://github.com/etcd-io/etcd/blob/v3.3.10/mvcc/kvstore_txn.go#L111
func (tr *storeTxnRead) rangeKeys(key, end []byte, curRev int64, ro RangeOptions) (*RangeResult, error) {
    rev := ro.Rev

    revpairs := tr.s.kvindex.Revisions(key, end, rev)

    limit := int(ro.Limit)
    kvs := make([]mvccpb.KeyValue, limit)
    revBytes := newRevBytes()

    for i, revpair := range revpairs[:len(kvs)] {
        revToBytes(revpair, revBytes)
        _, vs := tr.tx.UnsafeRange(keyBucketName, revBytes, nil, 0)
        kvs[i].Unmarshal(vs[0])
    }
    return &RangeResult{KVs: kvs, Count: len(revpairs), Rev: curRev}, nil
    }

这里函数的参数curRev代表当前事务ID。拿到这个ID后，我们去treeIndex中查询，满足指定条件的revision有哪些，然后再根据这些revision去boltdb中查询当时存的key-value是什么。

参考:
https://blog.betacat.io/post/mvcc-implementation-in-etcd/
https://www.jianshu.com/p/a23031ec02a6

etcd的MVCC

文章目录