Docs

Appearance

10etcd存储：如何实现键值对的读写操作？ ​

我们在前面几讲介绍了 etcd 的整体架构以及 etcd 常用的通信接口。在介绍 etcd 整体架构时，我们梳理了 etcd 的分层架构以及交互概览。这一讲我们将会聚焦 etcd 存储如何实现键值对的读写操作。

下面我们围绕 etcd 底层读写的实现展开，首先简要介绍客户端访问 etcd 服务端读写的整个过程，然后我们来重点介绍读写的实现细节。这一讲内容环环相扣，希望你仔细阅读。

读写操作过程概述 ​

我们在08 讲《etcd 的架构是什么样的？》中介绍了 etcd 各个模块交互的总览，如下图所示。

虽然有些细节在图中没有标出，但是总体上的请求流程从上至下依次为客户端 → API 接口层 → etcd Server → etcd raft 算法库。

对于读请求来说，客户端通过负载均衡 选择一个 etcd 节点发出读请求，API 接口层提供了 Range RPC 方法，etcd 服务端拦截到 gRPC 读请求后，调用相应的处理器处理请求。

写请求相对复杂一些，客户端通过负载均衡 选择一个 etcd 节点发起写请求，etcd 服务端拦截到 gRPC 写请求 ，涉及一些校验和监控，之后KVServer 向 raft 模块发起提案，内容即为写入数据的命令。经过网络转发，当集群中的多数节点达成一致并持久化数据后，状态变更且 MVCC 模块执行提案内容。

下面我们就分别看一下读写请求的底层存储实现。

读操作 ​

在 etcd 中读请求占了大部分，是高频的操作。我们使用 etcdctl 命令行工具进行读操作：

java
$ etcdctl --endpoints http://localhost:2379 get foo
foo
bar

将整个读操作划分成如下几个步骤：

  • etcdctl 会创建一个 clientv3 库对象，选取一个合适的 etcd 节点；

  • 调用 KVServer 模块的 Range RPC 方法（上一课时有讲解），发送请求；

  • 拦截器拦截，主要做一些校验和监控；

  • 调用 KVServer 模块的 Range 接口获取数据；

接着就进入了读请求的核心步骤，会经过线性读 ReadIndex 模块、MVCC（包含 treeIndex 和 BlotDB）模块。

这里要提一下线性读，线性读是相对串行读来讲的概念。集群模式下会有多个 etcd 节点，不同节点之间可能存在一致性问题，串行读直接返回状态数据，不需要与集群中其他节点交互 。这种方式速度快，开销小，但是会存在数据不一致的情况。

线性读则需要集群成员之间达成共识，存在开销，响应速度相对慢。但是能够保证数据的一致性，etcd 默认读模式是线性读。我们将在后面的课时重点介绍如何实现分布式一致性。

继续往下，看看如何读取 etcd 中的数据。etcd 中查询请求，查询单个键或者一组键，以及查询数量，到了底层实际都会调用 Range keys 方法。下面我们具体分析一下这个方式的实现。

Range 请求的结构图如下所示：

从上至下，查询键值对的流程包括：

  • 在 treeIndex 中根据键利用 BTree 快速查询该键对应的索引项 keyIndex，索引项中包含 Revision；

  • 根据查询到的版本号信息 Revision，在 Backend 的缓存 Buffer 中利用二分法查找，如果命中则直接返回；

  • 若缓存中不符合条件，在 BlotDB 中查找（基于 BlotDB 的索引），查询之后返回键值对信息。

图中 ReadTx 和 BatchTx 是两个接口，用于读写请求。在创建 Backend 结构体时，默认也会创建 readTx 和 batchTx，readTx 实现了 ReadTx ，负责处理只读请求；batchTx 实现了 BatchTx 接口，负责处理读写请求。

rangeKeys方法的实现如下所示：

go
// 位于 mvcc/kvstore_txn.go:117
func (tr *storeTxnRead) rangeKeys(key, end []byte, curRev int64, ro RangeOptions) (*RangeResult, error) {
	rev := ro.Rev
	if rev > curRev {
		return &RangeResult{KVs: nil, Count: -1, Rev: curRev}, ErrFutureRev
	}
	if rev <= 0 {
		rev = curRev
	}
	if rev < tr.s.compactMainRev {
		return &RangeResult{KVs: nil, Count: -1, Rev: 0}, ErrCompacted
	}
  // 获取索引项 keyIndex，索引项中包含 Revision
	revpairs := tr.s.kvindex.Revisions(key, end, rev)
	tr.trace.Step("range keys from in-memory index tree")
  // 结果为空，直接返回
	if len(revpairs) == 0 {
		return &RangeResult{KVs: nil, Count: 0, Rev: curRev}, nil
	}
	if ro.Count {
		return &RangeResult{KVs: nil, Count: len(revpairs), Rev: curRev}, nil
	}
	limit := int(ro.Limit)
	if limit <= 0 || limit > len(revpairs) {
		limit = len(revpairs)
	}
	kvs := make([]mvccpb.KeyValue, limit)
	revBytes := newRevBytes()
	for i, revpair := range revpairs[:len(kvs)] {
		revToBytes(revpair, revBytes)
    // UnsafeRange 实现了 ReadTx，查询对应的键值对
		_, vs := tr.tx.UnsafeRange(keyBucketName, revBytes, nil, 0)
		if len(vs) != 1 {
			tr.s.lg.Fatal(
				"range failed to find revision pair",
				zap.Int64("revision-main", revpair.main),
				zap.Int64("revision-sub", revpair.sub),
			)
		}
		if err := kvs[i].Unmarshal(vs[0]); err != nil {
			tr.s.lg.Fatal(
				"failed to unmarshal mvccpb.KeyValue",
				zap.Error(err),
			)
		}
	}
	tr.trace.Step("range keys from bolt db")
	return &RangeResult{KVs: kvs, Count: len(revpairs), Rev: curRev}, nil
}

在上述代码的实现中，我们需要通过Revisions方法从 Btree 中获取范围内所有的 keyIndex，以此才能获取一个范围内的所有键值对。Revisions方法实现如下：

go
// 位于 mvcc/index.go:106
func (ti *treeIndex) Revisions(key, end []byte, atRev int64) (revs []revision) {
	if end == nil {
		rev, _, _, err := ti.Get(key, atRev)
		if err != nil {
			return nil
		}
		return []revision{rev}
	}
	ti.visit(key, end, func(ki *keyIndex) {
    // 使用 keyIndex.get 来遍历整棵树
		if rev, _, _, err := ki.get(ti.lg, atRev); err == nil {
			revs = append(revs, rev)
		}
	})
	return revs
}

如果只获取一个键对应的版本，使用 treeIndex 方法即可，但是一般会从 Btree 索引中获取多个 Revision 值，此时需要调用 keyIndex.get 方法来遍历整棵树并选取合适的版本。这是因为BoltDB 保存一个 key 的多个历史版本，每一个 key 的 keyIndex 中其实都存储着多个历史版本，我们需要根据传入的参数返回正确的版本。

对于上层的键值存储来说，它会利用这里返回的 Revision，从真正存储数据的 BoltDB 中查询当前 key 对应 Revision 的数据。BoltDB 内部使用的也是类似 bucket（桶）的方式存储，其实就是对应 MySQL 中的表结构，用户的 key 数据存放的 bucket 名字的是 key，etcd MVCC 元数据存放的 bucket 是 meta。

写操作 ​

介绍完读请求，我们回忆一下写操作的实现。使用 etcdctl 命令行工具进行写操作：

java
$ etcdctl --endpoints http://localhost:2379 put foo bar

将整个写操作划分成如下几个步骤：

  • 客户端通过负载均衡算法选择一个 etcd 节点，发起 gRPC 调用；

  • etcd Server 收到客户端请求；

  • 经过 gRPC 拦截、Quota 校验，Quota 模块用于校验 etcd db 文件大小是否超过了配额；

  • 接着 KVServer 模块将请求发送给本模块中的 raft，这里负责与 etcd raft 模块进行通信，发起一个提案，命令为put foo bar，即使用 put 方法将 foo 更新为 bar；

  • 提案经过转发之后，半数节点成功持久化；

  • MVCC 模块更新状态机。

我们重点关注最后一步，学习如何更新和插入键值对。与上面一张图相对应，我们来看下 put 接口的执行过程：

调用 put 向 etcd 写入数据时，首先会使用传入的键构建 keyIndex 结构体，基于 currentRevision 自增生成新的 Revision 如{1,0}，并从 treeIndex 中获取相关版本 Revision 等信息；写事务提交之后，将本次写操作的缓存 buffer 合并（merge）到读缓存上（图中 ReadTx 中的缓存）。代码实现如下所示：

go
//位于 mvcc/index.go:53
func (ti *treeIndex) Put(key []byte, rev revision) {
	keyi := &keyIndex{key: key}
  // 加锁，互斥
	ti.Lock()
	defer ti.Unlock()
  // 获取版本信息
	item := ti.tree.Get(keyi)
	if item == nil {
		keyi.put(ti.lg, rev.main, rev.sub)
		ti.tree.ReplaceOrInsert(keyi)
		return
	}
	okeyi := item.(*keyIndex)
	okeyi.put(ti.lg, rev.main, rev.sub)
}

treeIndex.Put 在获取 Btree 中的 keyIndex 结构之后，会通过 keyIndex.put 在其中加入新的 revision，方法实现如下：

go
// 位于 mvcc/key_index.go:77
func (ki *keyIndex) put(lg *zap.Logger, main int64, sub int64) {
	rev := revision{main: main, sub: sub}
  // 校验版本号
	if !rev.GreaterThan(ki.modified) {
		lg.Panic(
			"'put' with an unexpected smaller revision",
			zap.Int64("given-revision-main", rev.main),
			zap.Int64("given-revision-sub", rev.sub),
			zap.Int64("modified-revision-main", ki.modified.main),
			zap.Int64("modified-revision-sub", ki.modified.sub),
		)
	}
	if len(ki.generations) == 0 {
		ki.generations = append(ki.generations, generation{})
	}
	g := &ki.generations[len(ki.generations)-1]
	if len(g.revs) == 0 { // 创建一个新的键
		keysGauge.Inc()
		g.created = rev
	}
	g.revs = append(g.revs, rev)
	g.ver++
	ki.modified = rev
}

从上述代码我们可以知道，构造的 Revision 结构体写入 keyIndex 键索引时，会改变 generation 结构体中的属性，generation 中包括一个键的多个不同的版本信息，包括创建版本、修改次数等参数。因此我们可以通过该方法了解 generation 结构体中的各个成员如何定义和赋值。

revision{1,0} 是生成的全局版本号，作为 BoltDB 的 key，经过序列化包括 key 名称、key 创建时的版本号（create_revision）、value 值和租约等信息为二进制数据之后，将填充到 BoltDB 的 value 中，同时将该键和 Revision 等信息存储到 Btree。

小结 ​

这一讲我们主要介绍了 etcd 的底层如何实现读写操作。我们首先简单介绍了客户端与服务端读写操作的流程，之后重点分析了在 etcd 中如何读写数据。

通过上面的分析不难发现，etcd 最底层的读写其实并不是很复杂。根据 etcd 读写流程图，可以知道读写操作依赖 MVCC 模块的 treeIndex 和 BoltDB，treeIndex 用来保存键的历史版本号信息，而 BoltDB 用来保存 etcd 的键值对数据。通过这两个模块之间的协作，实现了 etcd 数据的读取和存储。因此后续的课程将会进一步介绍 etcd 分布式一致性实现以及 MVCC 多版本控制实现的原理。

本讲内容总结如下：

学习完本课时，给大家留个小问题，etcd 写事务的提交会涉及 B+ 重新平衡，但这部分开销昂贵，该如何权衡呢？欢迎你在留言区提出自己的观点。

当然，本课时仅是介绍了底层的存储，对于如何实现分布式数据一致性并没有展开讲解。我们将在下一讲介绍 etcd-raft 如何实现分布式一致性。