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

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

读写操作过程概述

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

Drawing 0.png

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

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

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

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

读操作

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

$ 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 请求的结构图如下所示：

Drawing 1.png

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

在 treeIndex 中根据键利用 BTree 快速查询该键对应的索引项 keyIndex，索引项中包含 Revision；
根据查询到的版本号信息 Revision，在 Backend 的缓存 Buffer 中利用二分法查找，如果命中则直接返回；
若缓存中不符合条件，在 BlotDB 中查找（基于 BlotDB 的索引），查询之后返回键值对信息。

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

rangeKeys方法的实现如下所示：

// 位于 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方法实现如下：

// 位于 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 命令行工具进行写操作：

$ 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 接口的执行过程：

Drawing 2.png

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

//位于 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，方法实现如下：

// 位于 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 多版本控制实现的原理。

本讲内容总结如下：

Drawing 3.png

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

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