来源： 《etcd实战课》（极客时间） ---唐聪
etcd应用场景相当广泛，从服务发现到分布式锁，从配置存储到分布式协调等等。可以说，etcd 已经成为了云原生和分布式系统的存储基石。
1. 可用性
采用Raft算法，只要集群一半以上节点存活就可提供服务，具备良好的可用性。
2. 数据模型
参考ZooKeeper，使用的是基于目录的层次模式。使用了简单、易用的 REST API，提供了常用的 Get/Set/Delete/Watch 等 API，实现对 key-value 数据的查询、更新、删除、监听等操作。
基础架构
1. Client层
Client 层包括 client v2 和 v3 两个大版本 API 客户端库，提供了简洁易用的 API，同时支持负载均衡、节点间故障自动转移，可极大降低业务使用 etcd 复杂度，提升开发效率、服务可用性。
2. 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 协议。
3. Raft 算法层
Raft 算法层实现了 Leader 选举、日志复制、ReadIndex 等核心算法特性，用于保障 etcd 多个节点间的数据一致性、提升服务可用性等，是 etcd 的基石和亮点。
4. 功能逻辑层
etcd 核心特性实现层，如典型的 KVServer 模块、MVCC 模块、Auth 鉴权模块、Lease 租约模块、Compactor 压缩模块等，其中 MVCC 模块主要由 treeIndex 模块和 boltdb 模块组成。
5. 存储层
存储层包含预写日志 (WAL) 模块、快照 (Snapshot) 模块、boltdb 模块。其中 WAL 可保障 etcd crash 后数据不丢失，boltdb 则保存了集群元数据和用户写入的数据。
etcd 是典型的读多写少存储，在我们实际业务场景中，读一般占据 2/3 以上的请求。
读请求执行流程
client
当用etcd客户端工具etcdctl执行一个get hello命令时：
# 通常，生产环境下中需要配置多个 endpoints，
# 这样在 etcd 节点出现故障后，client 就可以自动重连到其它正常的节点，
# 从而保证请求的正常执行。
etcdctl get hello --endpoints http://127.0.0.1:2379
hello
world
在解析完请求中的参数后，etcdctl 会创建一个 clientv3 库对象，然后使用负载均衡算法来选择一个合适etcd server节点。
选择好 etcd server 节点后，client 就可调用 etcd server 的 KVServer 模块的 Range RPC 方法，把请求发送给 etcd server。
client 和 server 之间的通信，使用的是基于 HTTP/2 的 gRPC 协议。
KVServer
串行读
状态机数据返回、无需通过 Raft 协议与集群进行交互。它具有低延时、高吞吐量的特点，适合对数据一致性要求不高的场景。
线性读
etcd 默认读模式是线性读，在延时和吞吐量上相比串行读略差一点，适用于对数据一致性要求高的场景。
当收到一个线性读请求时，它首先会从 Leader 获取集群最新的已提交的日志索引。
Leader 收到 ReadIndex 请求时，为防止脑裂等异常场景，会向 Follower 节点发送心跳确认，一半以上节点确认 Leader 身份后才能将已提交的索引 (committed index) 返回给节点。
节点则会等待，直到状态机已应用索引 (applied index) 大于等于 Leader 的已提交索引时 (committed Index)，然后去通知读请求，数据已赶上 Leader，你可以去状态机中访问数据了
MVCC
多版本并发控制 (Multiversion concurrency control) 模块是为了解决 etcd v2 不支持保存 key 的历史版本、不支持多 key 事务等问题而产生的。
etcd保存一个key的多个历史版本的方案为：每次修改操作，生成一个新的版本号 (revision)，以版本号为 key， value 为用户 key-value 等信息组成的结构体。
treeIndex
基于btree库实现，只保存用户的 key 和相关版本号信息。而用于的key，value数据则存储在boltdb里面，相比于etcd v2 全内存存储，etcd v3 对内存要求更低。
buffer
并不是所有请求都一定要从 boltdb 获取数据。etcd 出于数据一致性、性能等考虑，在访问 boltdb 前，首先会从一个内存读事务 buffer 中，二分查找你要访问 key 是否在 buffer 里面，若命中则直接返回。
boltdb
若 buffer 未命中，此时就真正需要向 boltdb 模块查询数据了。
写请求执行流程
当etclctl执行一个写请求时，
etcdctl put hello world --endpoints http://127.0.0.1:2379
OK
client首先会通过一个负载均衡算法选择一个etcd节点，发起gRPC 调用。然后 etcd 节点收到请求后经过 gRPC 拦截器、Quota 模块后，进入 KVServer 模块，KVServer 模块向 Raft 模块提交一个提案，提案内容为“大家好，请使用 put 方法执行一个 key 为 hello，value 为 world 的命令”。
随后此提案通过 RaftHTTP 网络模块转发、经过集群多数节点持久化后，状态会变成已提交，etcdserver 从 Raft 模块获取已提交的日志条目，传递给 Apply 模块，Apply 模块通过 MVCC 模块执行提案内容，更新状态机。
Quoto模块
client 端发起 gRPC 调用到 etcd 节点，和读请求不一样的是，写请求需要经过流程二 db 配额（Quota）模块。
当 etcd server 收到 put/txn 等写请求的时候，会首先检查下当前 etcd db 大小加上你请求的 key-value 大小之和是否超过了配额（quota-backend-bytes）。如果超过了配额，它会产生一个告警（Alarm）请求，告警类型是 NO SPACE，并通过 Raft 日志同步给其它节点，告知 db 无空间了，并将告警持久化存储到 db 中。
配额为'0'表示使用 etcd 默认的 2GB 大小，可以根据业务常见进行调优。etcd社区建议不超过8G。如果填小于0的数，表示禁用配额功能，但这会让db大小处于失控状态，导致性能下降，所以不建议使用。
KVServer模块
etcd 是基于 Raft 算法实现节点间数据复制的，因此它需要将 put 写请求内容打包成一个提案消息，提交给 Raft 模块。
WAL模块
Raft 模块收到提案后，如果当前节点是 Follower，它会转发给 Leader，只有 Leader 才能处理写请求。Leader 收到提案后，通过 Raft 模块输出待转发给 Follower 节点的消息和待持久化的日志条目，日志条目则封装了提案内容。
Apply模块
put请求如果在执行提案内容的时候crash了，重启恢复的时候，会从 WAL 中解析出 Raft 日志条目内容，追加到 Raft 日志的存储中，并重放已提交的日志提案给 Apply 模块执行。
etcd 是个 MVCC 数据库，每次更新都会生成新的版本号。如果没有幂等性保护，同样的命令，一部分节点执行一次，一部分节点遭遇异常故障后执行多次，则系统的各节点一致性状态无法得到保证，导致数据混乱，这是严重故障。
Raft 日志条目中的索引（index）字段是全局单调递增的，每个日志条目索引对应一个提案，在 db 里面也记录下当前已经执行过的日志条目索引。
MVCC模块
Apply 模块判断此提案未执行后，就会调用 MVCC 模块来执行提案内容。MVCC 主要由两部分组成，一个是内存索引模块 treeIndex，保存 key 的历史版本号信息，另一个是 boltdb 模块，用来持久化存储 key-value 数据。
Raft协议
如何避免单点故障
为了解决单点问题，软件系统工程师引入了数据复制技术，实现多副本。通过数据复制方案，一方面我们可以提高服务可用性，避免单点故障。另一方面，多副本可以提升读吞吐量、甚至就近部署在业务所在的地理位置，降低访问延迟。
主从复制
全同步复制
主收到一个写请求后，必须等待全部从节点确认返回后，才能返回给客户端成功。
如果一个从节点故障，整个系统就会不可用。这种方案为了保证多副本的一致性，而牺牲了可用性，一般使用不多。
异步复制
主收到一个写请求后，可及时返回给 client，异步将请求转发给各个副本。
若还未将请求转发到副本前就故障了，则可能导致数据丢失，但是可用性是最高的。
半同步复制
主收到一个写请求后，至少有一个副本接收数据后，就可以返回给客户端成功
在数据一致性、可用性上实现了平衡和取舍。
去中心化复制
在一个 n 副本节点集群中，任意节点都可接受写请求，但一个成功的写入需要 w 个节点确认，读取也必须查询至少 r 个节点。
缺陷是去中心化复制，势必会导致各种写入冲突，业务需要关注冲突处理。
共识算法
为了解决以上复制算法的缺陷，人们提出了复制状态机，它由共识模块、日志模块、状态机组成。通过共识模块保证各个节点日志的一致性，然后各个节点基于同样的日志、顺序执行指令，最终各个复制状态机的结果实现一致。
Raft算法将共识问题拆分成了三个子问题：
- Leader 选举，Leader 故障后集群能快速选出新 Leader；
- 日志复制， 集群只有 Leader 能写入日志， Leader 负责复制日志到 Follower 节点，并强制 Follower 节点与自己保持相同；
- 安全性，一个任期内集群只能产生一个 Leader、已提交的日志条目在发生 Leader 选举时，一定会存在更高任期的新 Leader 日志中、各个节点的状态机应用的任意位置的日志条目内容应一样等。
Leader选举
Raft协议中定义了集群中的节点状态，任何时刻，每个节点必定处于其中一个状态：
- Follower，跟随者， 同步从 Leader 收到的日志，etcd 启动的时候默认为此状态；
- Candidate，竞选者，可以发起 Leader 选举；
- Leader，集群领导者， 唯一性，拥有同步日志的特权，需定时广播心跳给 Follower 节点，以维持领导者身份。
当 Follower 节点接收 Leader 节点心跳消息超时后，它会转变成 Candidate 节点，并可发起竞选 Leader 投票，若获得集群多数节点的支持后，它就可转变成 Leader 节点。
etcd的默认心跳间隔是100ms，默认竞选超时是1000ms，可根据实际部署环境、业务场景适当调优，否则就很可能会频繁发生 Leader 选举切换，导致服务稳定性下降。
任期号
Raft 将时间划分成一个个任期，任期用连续的整数表示，每个任期从一次选举开始，赢得选举的节点在该任期内充当 Leader 的职责，随着时间的消逝，集群可能会发生新的选举，任期号也会单调递增。
通过任期号，可以比较各个节点的数据新旧、识别过期的 Leader 等，它在 Raft 算法中充当逻辑时钟，发挥着重要作用。
进入 Candidate 状态的节点，会立即发起选举流程，自增任期号，投票给自己，并向其他节点发送竞选 Leader 投票消息（MsgVote）。
当其他节点收到竞选Leader消息后，会有两种情况：
- 竞选节点数据至少和自己一样新，任期号大于大于自己当前记录的Leader任期号，且未投票给其他候选者，则可投票给竞选节点。
- 自己也心跳超时了，也发起了选举，并且投票给了自己，故将拒绝给竞选节点投票。为了避免选票被瓜分导致竞选超时，每个节点等待发起选举的时间是一个随机数。
为了避免单节点无法连接其他节点，不停增加任期号发起选举，增加了PreCandidate状态，它会先发起预投票，只有获得集群多数节点认可，确定有概率成为Leader才能进入Candidate状态。
日志复制
日志由一个个递增的有序序号索引标识。Leader维护了所有Follow节点的日志复制进度，在新增一个日志后，会将其广播给所有Follow节点。Follow节点处理完成后，会告知Leader当前已复制的最大日志索引。Leader收到后，会计算被一半以上节点复制过的最大索引位置，标记为已提交位置，在心跳中告诉Follow节点。
只有被提交位置以前的日志才会应用到存储状态机。
日志复制规则
Leader完全特性
如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有 Leader 中。
这是因为已提交的日志表示以被集群中的大部分节点复制，如果一个节点进度小于它，则不可能会被选举成为Leader。
日志匹配特性
为了保证各个节点日志一致性，Raft 算法在追加日志的时候，引入了一致性检查。Leader 在发送追加日志 RPC 消息时，会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。Follower 节点会检查相同索引位置的任期号是否与 Leader 一致，一致才能追加。
- Follower 日志与 Leader 冲突
在老Leader崩溃，新Leader选举后，有些节点可能会拥有一些新Leader没有的日志。
- Follower 删除无效日志
Leader通过强制Follower复制自己的日志来解决。如果当前日志冲突，则Leader会减小日志索引号重试，直到找到和Follower一致的索引开始让Follow复制。
