etcd核心基础

版本变化

etcd v2 到 v3 的变化：

单版本->多版本（MVVC）
ttl -> lease
单key原子更新 -> 多key事务
内存树（treeIndex）-> boltdb
http/1.x api -> grpc api
json -> protobuf
http/1.x -> http/2.0（多路复用）

基础架构

按照分层模型，etcd 可分为 Client 层、API 网络层、Raft 算法层、逻辑层和存储层。这些层的功能如下：

Client层：Client 层包括 client v2 和 v3 两个大版本 API 客户端库，提供了简洁易用的 API，同时支持负载均衡、节点间故障自动转移，可极大降低业务使用 etcd 复杂度，提升开发效率、服务可用性。
API网络层：API 网络层主要包括 client 访问 server 和 server 节点之间的通信协议。一方面，client 访问 etcd server 的 API 分为 v2 和 v3 两个大版本。v2 API 使用 HTTP/1.x 协议，v3 API 使用 gRPC 协议。同时 v3 通过 etcd grpc-gateway 组件也支持 HTTP/1.x 协议，便于各种语言的服务调用。另一方面，server 之间通信协议，是指节点间通过 Raft 算法实现数据复制和 Leader 选举等功能时使用的 HTTP 协议。
Raft算法层：Raft 算法层实现了 Leader 选举、日志复制、ReadIndex 等核心算法特性，用于保障 etcd 多个节点间的数据一致性、提升服务可用性等，是 etcd 的基石和亮点。功能逻辑层：etcd 核心特性实现层，如典型的 KVServer 模块、MVCC 模块、Auth 鉴权模块、Lease 租约模块、Compactor 压缩模块等，其中 MVCC 模块主要由 treeIndex 模块和 boltdb 模块组成。
存储层：存储层包含预写日志 (WAL) 模块、快照 (Snapshot) 模块、boltdb 模块。其中 WAL 可保障 etcd crash 后数据不丢失，boltdb 则保存了集群元数据和用户写入的数据。

读请求过程

一个读请求从 client 通过 Round-robin 负载均衡算法，选择一个 etcd server 节点，发出 gRPC 请求，经过 etcd server 的 KVServer 模块、线性读模块、MVCC 的 treeIndex 和 boltdb 模块紧密协作，完成了一个读请求。

etcd通过拦截器实现了丰富的 metrics、日志、请求行为检查等机制。
etcd提供两种读模式：串行读和线性读（默认）
串行读：直接读状态机数据返回、无需通过 Raft 协议与集群进行交互，具有低延时、高吞吐量的特点，适合对数据一致性要求不高的场景
线性读：需要经过 Raft 协议模块，反应的是集群共识，因此在延时和吞吐量上相比串行读略差一点，适用于对数据一致性要求高的场景（通过readIndex机制确保最新的数据已经应用到状态机中）

当收到一个读请求时，它会从 Leader 节点获取集群最新的提交日志索引，Leader ReadIndex 请求时，向 Follower 发起心跳确认（为防止集群脑裂），半数以上节点确认后，会将已提交索引返回给请求的节点（上述的Follower C），节点C根据等待状态机完成索引更新后，通知读请求数据已是最新，可以去状态机读取了。

写请求过程

首先 client 端通过负载均衡算法选择一个 etcd 节点，发起 gRPC 调用。
然后 etcd 节点收到请求后经过 gRPC 拦截器、Quota 模块后，进入 KVServer 模块，KVServer 模块向 Raft 模块提交一个提案。随后此提案通过 RaftHTTP 网络模块转发、经过集群多数节点持久化后，状态会变成已提交，etcdserver 从 Raft 模块获取已提交的日志条目，传递给 Apply 模块，Apply 模块通过 MVCC 模块执行提案内容，更新状态机。

与读流程不一样的是写流程还涉及 Quota、WAL、Apply 三个模块。

Quota：限制db的配额大小，默认2G，超过配额会发出告警并保存到 db 中，通过 Raft 日志同步给其他节点，最后拒绝写入。
KVServer：经过配额检测后会到KVServer模块，此时会顺序执行一系列操作：
（1）限速判断（已提交的日志索引 - 已应用日志索引 > 5000，错误：etcdserver: too many requests）
（2）鉴权判断（Token是否无效，错误：auth: invalid auth token）
（3）大小判断（写入的包是否超过默认的 1.5MB ，错误 etcdserver: request is too large）
（4）写结果等待（默认7秒，5 秒磁盘 IO 延时 +2*1 秒竞选超时时间，若超时未返回结果，错误：etcdserver: request timed out）
WAL：Write Ahead Log，用于保证集群的一致性，可恢复性。写请求都会通过 Raft 模块转发给 Leader 处理，Leader 收到请求后会广播给其他节点，同时把集群 Leader 任期号、投票信息、已提交索引、提案内容持久化到一个 WAL文件中，随后会将内容持久化到磁盘，当一半以上节点完成持久化后，Raft 模块会通过 channel 告知 etcdserver 模块，提案状态已提交，然后 etcdserver 模块将提案内容放到一个 FIFO 队列，通过 Apply 模块执行提案内
Apply：Apply 模块基于 consistent index 和事务实现了幂等性，保证了节点在异常情况下不会重复执行重放的提案

MVCC：MVCC 主要由两部分组成，一个是内存索引模块 treeIndex，保存 key 的历史版本号信息，另一个是 boltdb 模块，用来持久化存储 key-value 数据，boltdb 中的 key 包含版本号，在 etcd 中全局单调递增，通过异步、批量提交事务机制，以提升写 QPS 和吞吐量；并引入 bucket buffer 来保存暂未提交的事务数据，更新时会同时写入 bucket buffer，读时优先从 bucket buffer 读，实现读写性能提升，同时保证数据一致性

Raft分布式共识算法

动画网站：http://kailing.pub/raft/index.html

Leader选举

Raft 协议中定义了集群中的节点状态，任何时刻，每个节点肯定处于其中一个状态：

Follower，跟随者，同步从 Leader 收到的日志，etcd 启动的时候默认为此状态；
Candidate，竞选者，可以发起 Leader 选举；
Leader，集群领导者，唯一性，拥有同步日志的特权，需定时广播心跳给 Follower 节点，以维持领导者身份
当 Follower 节点接收 Leader 节点心跳消息超时后，那么他们可以成为候选人。然后，候选人从其他节点请求投票，节点将以他们的投票进行回复。如果候选人从多数节点中获得选票，它将成为领导者。

Raft 通过心跳机制、随机化等实现了 Leader 选举，只要集群半数以上节点存活可相互通信，etcd 就可对外提供高可用服务。

Leader crash后，etcd 是如何自愈的呢？

当 Leader 节点异常后，Follower 节点会接收 Leader 的心跳消息超时，当超时时间大于竞选超时时间后，它们会进入 Candidate 状态。（etcd 默认心跳间隔时间（heartbeat-interval）是 100ms，默认竞选超时时间（election timeout）是 1000ms ）。
etcd3.4引入一个PreVoter参数，Follower 在转换成 Candidate 状态前，先进入 PreCandidate 状态，不自增任期号，发起预投票。若获得集群多数节点认可，确定有概率成为 Leader 才能进入 Candidate 状态，发起选举流程，来避免异常的Leader节点恢复后因为数据太落后，导致触发无效选举。
选举时使用心跳机制维持 Leader 身份、触发 Leader 选举，etcd 基于它实现了高可用，只要集群一半以上节点存活、可相互通信，Leader 宕机后，就能快速选举出新的 Leader，继续对外提供服务。
日志复制
Leader 如何同步日志给 Follower 节点?
通过日志复制机制，如下图：

当 Leader 收到客户端请求后，etcdserver的 KV 模块回向 Raft 模块提交一个提案消息，Raft 模块收到后会为此提案生成一个日志条目并追加到 Raft 日志（内存中，未持久化、不稳定）中，随后会将日志条目同步给 Follower，此时Leader 会维护 NextIndex （给 Follower 的下一个日志条目索引）和 MatchIndex （Follower 已复制的最大日志条目索引），保证日志条目同步的正确性。
当日志条目被多数节点复制后，那么它的状态就会被设置为已提交，然后 Leader 通过心跳机制通知 Follower 该日志索引，同时写入到 WAL 文件中（一般在磁盘，可用来重建 raft 日志），最后各节点的 etcdserver 从 Reft 模块中获取日志条目并应用到存储状态机。

raft 日志和wal日志的区别？

WAL日志：是用来持久化raft日志条目和相关集群元数据信息的，可防止节点发生重启、crash后，对应的已提交日志条目丢失等异常情况，一般情况下，它是将数据持久化到磁盘中。
Raft日志：记录了节点过去一段时间内收到的写请求，如put/del/txn操作等，一般是通过一个内存数组
来存储最近一系列日志条目。当Follower节点落后Leader较小时，就可以通过Leader内存中维护的日
志条目信息, 将落后的日志条目发送给它，最终各个节点应用一样的日志条目内容，来确保各个节点
数据一致性。
etcd节点重启后，可通过WAL日志来重建部分raft日志条目。

MVCC

一种基于多版本技术实现的一种并发控制机制，属于悲观锁

整体架构

Apply模块 通过MVCC模块来执行put请求，持久化key-value数据。MVCC模块将请求请划分成两个类别，分别是读事务（ReadTxn）和写事务（WriteTxn）。读事务负责处理range请求，写事务负责put/delete操作。读写事务基于treeIndex、Backend/boltdb提供的能力，实现对key-value的增删改查功能。
treeIndex模块 基于内存版B-tree实现了key索引管理，它保存了用户key与版本号（revision）的映射关系等信息。
Backend模块 负责etcd的key-value持久化存储，主要由ReadTx、BatchTx、Buffer组成，ReadTx定义了抽象的读事务接口，BatchTx在ReadTx之上定义了抽象的写事务接口，Buffer是数据缓存区。etcd设计上支持多种Backend实现，目前实现的Backend是boltdb。boltdb是一个基于B+ tree实现的、支持事务的key-value嵌入式数据库。

treeIndex

treeIndex模块基于Google开源的btree库实现，它的核心数据结构keyIndex，保存了用户key与版本号关系。每次修改key都会生成新的版本号，生成新的boltdb key-value。boltdb的key为版本号，value包含用户key-value、各种版本号、lease的mvccpb.KeyValue结构体。
在一个度为d的B-tree中，节点保存的最大key数为2d - 1，否则需要进行平衡、分裂操作。这里你要注意的是在etcd treeIndex模块中创建的是最大度32的B-tree，也就是一个叶子节点最多可以保存63个key。
在treeIndex中，每个节点的key是一个keyIndex结构，etcd就是通过它保存了用户的key与版本号的映射关系。

type keyIndex struct {
    key []byte //用户的key名称，比如我们案例中的"hello"
    modified revision //最后一次修改key时的etcd版本号,比如我们案例中的刚写入hello为world1时的，版本号为2
    generations []generation //generation保存了一个key若干代版本号信息，每代中包含对key的多次修改的版本号列表
}

//每次key删除都会新增一代
type generation struct {
    ver int64 //表示此key的修改次数
    created revision //表示generation结构创建时的版本号
    revs []revision //每次修改key时的revision追加到此数组
}

type revision struct {
    main int64 // 一个全局递增的主版本号，随put/txn/delete事务递增，一个事务内的key main版本号是一致的
    sub int64 // 一个事务内的子版本号，从0开始随事务内put/delete操作递增
}

MVCC更新key原理

MVCC查询key原理

完成put hello为world1操作后，这时你通过etcdctl发起一个get hello操作，MVCC模块首先会创建一个读事务对象（TxnRead），在etcd 3.4中Backend实现了ConcurrentReadTx，也就是并发读特性。
并发读特性的核心原理是创建读事务对象时，它会全量拷贝当前写事务未提交的buffer数据，并发的读写事务不再阻塞在一个buffer资源锁上，实现了全并发读。

MVCC删除key原理

etcd实现的是延期删除模式，原理与key更新类似。

boltdb key里的版本号会追加了删除标识（tombstone,简写t），并且 value 变成只含用户 key 的 Key Value 结构体；
treeIndex模块此 key 对应的 keyIndex 对象，追加一个空的 generation 对象，表示此索引对应的 key 被删除了。

那么key打上删除标记后有哪些用途呢？什么时候会真正删除它呢？

一方面删除key时会生成events，Watch模块根据key的删除标识，会生成对应的Delete事件。
另一方面，当你重启etcd，遍历boltdb中的key构建treeIndex内存树时，你需要知道哪些key是已经被删除的，并为对应的key索引生成tombstone标识。而真正删除treeIndex中的索引对象、boltdb中的key是通过压缩(compactor)组件异步完成。
etcd延时

数据一致性

etcd 各个节点数据一致性基于 Raft 算法的日志复制实现的，etcd 是个基于复制状态机实现的分布式系统。下图是分布式复制状态机原理架构，核心由 3 个组件组成，一致性模块、日志、状态机。
其工作流程如下：

client 发起一个写请求（set x = 3）；
server 向一致性模块（假设是 Raft）提交请求，一致性模块生成一个写提案日志条目。若
server 是 Leader，把日志条目广播给其他节点，并持久化日志条目到 WAL 中；
当一半以上节点持久化日志条目后，Leader 的一致性模块将此日志条目标记为已提交
（committed），并通知其他节点提交；
server 从一致性模块获取已经提交的日志条目，异步应用到状态机持久化存储中（boltdb
等），然后返回给 client。

配置说明

ETCD_NAME ：ETCD的节点名
ETCD_DATA_DIR：ETCD的数据存储目录
ETCD_SNAPSHOT_COUNTER：多少次的事务提交将触发一次快照
ETCD_HEARTBEAT_INTERVAL：ETCD节点之间心跳传输的间隔，单位毫秒
ETCD_ELECTION_TIMEOUT：该节点参与选举的最大超时时间，单位毫秒
ETCD_LISTEN_PEER_URLS：该节点与其他节点通信时所监听的地址列表，多个地址使用逗号隔开，其格式可以划分为scheme://IP:PORT，这里的scheme可以是http、https
ETCD_LISTEN_CLIENT_URLS：该节点与客户端通信时监听的地址列表
ETCD_INITIAL_ADVERTISE_PEER_URLS：该成员节点在整个集群中的通信地址列表，这个地址用来传输集群数据的地址。因此这个地址必须是可以连接集群中所有的成员的。
ETCD_INITIAL_CLUSTER：配置集群内部所有成员地址，其格式为：ETCD_NAME=ETCD_INITIAL_ADVERTISE_PEER_URLS，如果有多个使用逗号隔开
ETCD_ADVERTISE_CLIENT_URLS：广播给集群中其他成员自己的客户端地址列表
ETCD_INITIAL_CLUSTER_STATE：初始化集群状态，new表示新建
ETCD_INITIAL_CLUSTER_TOKEN:初始化集群token