MVCC 在 etcd 中的实现

简介

在数据库领域，面对高并发环境下数据冲突的问题，业界常用的解决方案有两种：

想办法避免冲突。使用悲观锁来确保同一时刻只有一人能对数据进行更改，常见的实现有读写锁（Read/Write Locks）、两阶段锁（Two-Phase Locking）等。
允许冲突，但发生冲突的时候，要有能力检测到。这种方法被称为乐观锁，即先乐观的认为冲突不会发生，除非被证明（检测到）当前确实产生冲突了。常见的实现有逻辑时钟（Logical Clock）、MVCC（Multi-version Cocurrent Control）等。

在这些解决方案中，MVCC 由于其出色的性能优势，而被越来越多的数据库所采用，比如Oracle、PostgreSQL、MySQL InnoDB、etcd 等。它的基本思想是保存一个数据的多个历史版本，从而解决事务管理中数据隔离的问题。

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

MVCC 的基本原理就是这么简单，下面来结合具体代码，看看 etcd 是怎么实现的。跟上篇一样，这里的分析仍以etcd v3.3.10 为例。

数据结构

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

revision

revision 即对应到MVCC中的版本，etcd 中的每一次key-value的操作都会有一个相应的 revision。

 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

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数组，代表在它这一代中，所经历过的版本变更。

不知所云？没关系，我刚开始看这段代码的时候也是一脸懵逼，不明白为啥要这样层层包装。不过还好我们有UT，跟着UT里面的测试样例大概梳理出这样的逻辑：

假设我们有一个值为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顾名思义就是一个树状索引，它通过在内存中维护一个B树，来达到加速查询key的功能。

这棵树的每一个节点都是keyIndex，它实现了Item接口，其中的比较函数主要是比较key的大小。这样，给定一个key就能很快查到它对应的keyIndex，进而可以得知它所有的版本信息。树状结构比较简单，看看图就能明白，我就不再分析了。

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

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

backend

backend封装了etcd中的存储，按照设计，backend可以对接多种存储，当前使用的是boltdb，但作为一个CNCF项目，官方也在考虑接入更多的存储引擎¹。boltdb是一个纯Go语言实现的支持事务的KV存储，etcd的事务就是基于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。下面这个图很好的表示了这个过程²：

基本概念就介绍到这里了，下面我们把这些概念串起来，看看读写操作的完整流程是怎样的。

写操作

首先客户端的Put请求会被EtcdServer的Put函数接受到，它经过一套 raft 协议的流转后，在 apply 阶段被写入，精简后的写入逻辑大概是这样的：

 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)
}

正如前面所分析的，这里的写入操作首先获取了当前事务开始时的ID（tw.beginRev），构造出了新的revision，然后将 value 写入到后端的boltdb中，并更新了内存中 key 的索引（treeIndex）。

读操作

读操作的处理函数是由EtcdServer的Range函数处理的，在走完一段Linearizable Read协议后，我们发现最终的操作是由storeTxnRead.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。拿到了key以及感兴趣的revision之后，我们去treeIndex中查询，满足指定条件的revision有哪些，然后再根据这些revision去boltdb中查询当时存的key-value是什么，并封装成RangeResult返回出去。

小结

本文将乐观锁的原理及其在 etcd 中的实现 MVCC 梳理了一遍，希望对读者在理解和使用乐观锁上能有所帮助。

在 etcd 中，MVCC 的实现还是比较简单直接的。但在阅读代码的过程中，我也有一些看不明白的地方，毕竟一段代码在演化的过程中，会多出各种各样的细节处理，比如边界情况，性能调优等。这些细节会扰乱视线，让我们难以抓住主干。一般碰到这种情况，我会采用两种方法：

阅读UT，看他们都在测试什么。一般UT的输入输出都比较确定，它能够向我们揭示这段代码的作者期望完成的功能是什么。有了这个目标后我们再去看实现，就能剔出哪些是跟主干功能有关的，哪些是细节处理。
查找较早的提交。既然代码是演进出来的，那它刚开始的几个版本一般都比较粗糙，有很多细节没有处理，但那也是这个功能最直接的实现。通过阅读作者早期的实现，也能帮助我们快速抓住主干。

文章目录

简介

数据结构

revision

keyIndex

treeIndex

backend

写操作

读操作

小结