分布式键值存储系统Etcd介绍
写在前面：9月份以来陆陆续续发生了很多事情，以至于忙得是焦头烂额、精疲力尽，没有时间和精力持续学习。有时候扪心自问这份执着的意义是什么，为了最初的念想或者守望？其实周末时候陪陪家人，偷得浮生半日闲也是挺好，却拿这点时间去做觉得更为有意义的事情，于自身而言于工作而言，这种技术的沉淀似乎并无实用处。适逢国庆假期，陪陪家人、见见亲友，也有时间冥想放空，本身这份坚持和守望已经是岁月最好的印记。
言归正传。前文介绍了分布式服务框架Zookeeper的一些概念，本文继续介绍ETCD相关概念。ETCD作为分布式键值存储系统，使用场景上和Zookeeper有很多相似之处，但在设计理念以及架构稳定性和性能上有了提升，本文将对其中的架构流程、一致性Raft算法以及存储模型作简要介绍。
1、ETCD基本概念
ETCD是一个分布式键值对存储，通常用于分布式系统中的配置管理、服务发现和分布式协调工作。
提示："etcd"这个名字源于两个想法，即 unix “/etc” 文件夹和分布式系统"d"istibuted。
“/etc” 文件夹为单个系统存储配置数据的地方，而 etcd 存储大规模分布式系统的配置信息。
因此，"d"istibuted 的 “/etc” ，是为 “etcd”。
1.1 ETCD的特点
简单：安装配置简单，而且提供了HTTP API进行交互，降低运维成本
数据一致性：集群之间没有单点故障，多节点之间采用Raft算法保障数据一致性
低容量：通过内存树仅存储key版本数据，value数据存储在内存
监测变更：监测特定的键或目录以进行更改，并对值的更改做出反应
键值对存储：将数据存储在分层组织的目录中，如同在标准文件系统中
1.2 ETCD相关概念
ETCD中存在许多概念，如下所示：
Raft：ETCD所采用的保证分布式系统强一致性的算法 Leader：Raft算法中通过竞选而产生的处理所有数据提交的节点
Follower：竞选失败的节点作为Raft中的从属节点, 为算法提供强一致性保证
Candidate：Follower超过一定的时间还接收不到Leader的心跳时, 会转变为Candidate开始竞选
Term：某个节点从成为Leader到下一次竞选的时间，称为一个Term
Proposal：一个需要经过Raft一致性协议的请求，例如写请求或配置更新请求
Quorum：Raft协议需要的、能够修改集群状态的、活跃的etcd集群成员数量称为Quorum(法定人数)，通俗地讲就是etcd集群成员的半数以上。Etcd使用仲裁机制， 若集群中存在n个节点，那么集群中有(n+l)/2个节点达成一致，则操作成功。
ETCD集群组成
Client：凡是连接Etcd服务器请求服务的，比如获取key-value、写数据等等，都统称为Client；所以Etcd命令行连接工具、编写的连接etcd服务的代码对应的进程都是Client
Node：一个Raft状态机实例
Member：一个Etcd实例，它管理着一个Node，并且可以为客户端请求提供服务
Cluster：由多个Member构成的，遵循Raft一致性协议的etcd集群
Peer：对同一个Etcd集群中另外一个Member的叫法
gRPC：grpc框架，使用protobuf协议，以及http2，一个客户端与服务端只需要一个tcp连接
ETCD相关特性
WAL：预写式日志，Etcd用于持久化存储的日志格式
Snapshot：Etcd集群在某一时间点的快照(备份), etcd为防止WAL文件过多而设置的快照，用于存储etcd的数据状态
Index：WAL日志数据项编号，Raft中通过Term和Index来定位数据
Key space：键空间，etcd集群内所有键的集合
Key Range：键范围，一个键的集合，这个集合既可以是一个key、也可以是在一个字典区间，例如(a, b]，或者是大于某个key的所有key
Lease：一个短时的(会过期)，可续订的契约(租约)，当它过期时，就会删除与之关联的所有键
Watcher：观察者，etcd最具特色的概念之一。客户端通过打开一个观察者来获取一个给定键范围的更新
Reversion版本：etcd集群范围内64位的计数器, 键空间的每次修改都会导致该计数器的增加
Modification Revision：一个key最后一次修改的revision
Compaction：etcd的压缩(Compaction)操作，丢弃所有etcd的历史数据并且取代一个给定revision之前的所有key
key version：键版本，即一个键从创建开始的写(修改)次数，从1开始。一个不存在或已删除的键版本是0，注意key version和revision的概念不同
1.3 ETCD和Zookeeper对比
动态的集群节点关系重配置
高负载条件下的稳定读写
多版本并发控制的数据模型
持久稳定的watch而不是简单的单次触发式watch。Zookeeper的单次触发式watch是指监听到一次事件之后，需要客户端重新发起监听，这样zookeeper服务器在接收到客户端的监听请求之前的事件是获取不到的，而且在两次监昕请求的时间间隔内发生的 事件，客户端也是没法感知的。etcd的持久监听是每当有事件发生时，就会连续触发，不需要客户端重新发起监听
租约(lease)原语实现了连接和会话的解耦
安全的分布式共享锁API
Etcd客户端协议是gRPC，广泛支持各种各样的语言和框架，但 zookeeper 只有它自己的客户端协议：Jute RPC协议，只在特定的语言库（Java和C）中绑定。
2、ETCD原理
2.1 ETCD基础架构
client 层：包含client v2和v3两个⼤版本API客户端 API⽹络层：
主要包含clent访问server和server节点之间的通信协议
clent访问server分为两个版本：v2 API采⽤ HTTP/1.x 协议，v3 API采用gRPC协议
server之间的通信：是指节点间通过Raft算法实现数据复制和Leader选举等功能时使⽤的HTTP协议
Raft算法层：
实现了Leader选举、⽇志复制、ReadIndex等核心算法特性
⽤于保障etcd多节点间的数据⼀致性、提升服务可⽤性等，是etcd的基⽯和亮点
功能逻辑层：
etcd核⼼特性实现层
如典型的KVServer模块、MVCC模块、Auth鉴权模块、Lease租约模块、Compactor压缩模块等
其中MVCC模块主要有treeIndex模块和boltdb模块组成
存储层：
包含预写⽇志WAL模块、快照Snapshot模块、boltdb模块
其中WAL可保障etcd crash后数据不丢失，boltdb则保存了集群元数据和⽤户写⼊的数据
2.1.1 读请求过程
客户端向ETCD服务端发起读请求 KVServer模块收到线性读请求后，向Raft模块发起ReadIndex请求
Raft模块将Leader最新的已提交日志索引封装在ReadState结构体中
通过channel层层返回给线性读模块
线性读模块等待本节点状态机追赶上Leader进度
追赶完成后，就通知KVServer模块，与状态机中的MVCC模块进⾏交互
2.1.2 写请求过程
客户端发送更新请求，PUT指令到KVServer ETCD Server在接收到写请求时，首先会检查当前ETCD DB的大小和写入数据的大小是否超出quota，若超过会产生告警，拒绝写入
KVServer将PUT写请求打包成Proposal发送到Raft模块
Raft模块为Proposal生成一个日志条目，并将日志写入WAL模块持久化，之后将日志写入Raft稳定日志中，此时标记为已提交状态
Apply模块接收到apply的消息后，利用consistent index字段记录已执行的日志
日志应用到MVCC模块，实现真正的存储。MVCC模块包含treeIndex和boltdb，treeIndex在内存中，维护版本号和用户key的映射关系，真正的数据存储在boltdb中
2.2 一致性Raft协议
ETCD使用Raft协议来维护集群内各个节点状态的一致性。简单说，ETCD集群是一个分布式系统，由多个节点相互通信构成整体对外服务，每个节点都存储了完整的数据，并且通过Raft协议保证每个节点维护的数据是一致的。
每个ETCD节点都维护了一个状态机，并且任意时刻至多存在一个有效的主节点。主节点处理所有来自客户端写操作，通过Raft协议保证写操作对状态机的改动会可靠的同步到其他节点。
Client客户端向ETCD Server发送请求 ETCD server的KVServer模块接收到请求后，向RAFT模块提交Proposal
Leader的RAFT模块获取到提案Proposal后，会为Proposal生成日志条目，并追加到本地日志
Leader会向Follower广播消息，为每个Follower生成追加的RPC消息，包括复制给Follower的日志条目
Follower会持久化消息到WAL日志中，并追加到日志存储
Follower向Leader回复一个应答日志条目的消息，告知Leader当前已复制日志的最大索引
Leader在收到Follower的应答后，将已复制日志的最大索引信息更新到跟踪Follower进展的Match Index字段
Leader根据Follower的MatchIndex信息，计算出一个位置。如果该位置已经被一半以上的节点持久化，那么这个日志之前的日志条目都可以标记为已提交
Leader发送心跳消息到Follower节点时，告知目前已经提交的索引位置
各个节点的etcdserver模块，根据已提交的日志条目，将内容apply到存储状态机，并返回结果给client端
2.3 Watcher特性
Watch机制指的是订阅/通知，当一个值发生变化的时候，通过订阅过的节点能够观察到这种变化。在ETCD中是key/value键值对的改变，在Zookeeper中则是znode的变化，但是在Zookeeper中只能watch子节点不能递归到孙节点，另外只能watch节点的创建和删除，不能watch节点值的变化。ETCD则做了改进，并且支持三种类型的watch：
单点Watch：仅对传入的单个Key进行watch
Ranged Watch：可以对传入的key的范围进行watch，范围内的key事件都会被捕捉
Prefix Watch：可以对所有给定的prefix的key进行watch
当客户端或者API发起watch key请求时，etcd的gRPCWatchServer收到watch请求时，会创建一个serverWatchStream serverWatchStream收到create watch请求后，会调用MVCC模块的WatchStream子模块分配一个watcher ID，并将watcher注册到MVCC的WatchableKV模块
ETCD启动的时候，WatchableKV模块会运行syncWatchLoop和syncVictimsLoop
2.4 数据版本机制
ETCD中有个term的概念，代表的是整个集群Leader的任期。当集群发生Leader切换，term的值就会+1。在节点故障，或者Leader节点网络出现问题，再或者是将整个集群停止后再次拉起，都会发生Leader的切换。
在ETCD中版本号叫做revision，revision代表的是全局数据的版本。当数据发生变更，包括创建、修改、删除，其revision对应的都会+1。特别的，在集群中跨Leader任期之间，revision都会保持全局单调递增。正是revision的这一特性，使得集群中任意一次的修改都对应着一个唯一的revision，因此可以通过revision来支持数据的MVCC，也可以支持数据的Watch。
第一个版本叫做create_revision，是KeyValue在创建时对应的revision；
第二个叫做mod_revision，是其数据被操作的时候对应的revision；
第三个version就是一个计数器，代表了KeyValue被修改了多少次。
2.5 ETCD数据存储
ETCD和其它存储系统不同，存储的一般是重要的元数据信息，通常变动较少，属于读多写少的场景。在ETCD V2版本中，整个ETCD是一个纯内存数据库，整个数据库在内存中是一个简单的树结构。写操作先通过Raft复制日志文件，复制成功后将数据写人内存。在ETCD V3版本中实现了MVCC，每个Key值都会保留多个历史版本，数据量会很大，因此需要保存到磁盘，整个数据库都会存储在磁盘上，默认的存储引擎是BlotDB。使用MVCC的好处是可以减轻用户设计分布式系统的难度，通过对多版本的控制，用户可以获得一个一致的键值空间的快照。用户可以在无锁的状态下查询快照上的键值，减少了锁冲突，提高了并发。
2.5.1 数据持久化BlotDB
SQL类数据库：支持ACID事务，但是作为一个关系型数据库，主要用于灵活的SQL查询及复杂的联表查询。ETCD作为一个简单的KV数据库，不需要复杂的SQL支持
LeveIDB和RocksDB：基本原理是将有序的key/value存储在不同的文件中，并通过“层级”将它们分开，并且周期性地将小的文件合并为大的文件，这样做就能把随机写转化为顺序写，从而提高随机写的性能，因此特别适合“写多读少”和“随机写多”的场景。LeveIDB和 RocksDB都不支持完整的ACID事务。
LMDB和BoltDB则是基于B树和mmap的数据库，具有如下特性：
使用mmap技术，避免IO操作，简单来讲就是：一般情况下进程读取文件内容，需要将文件内容复制到内核空间，再从内核空间复制到用户空间，而mmap技术可以直接通过指针直接读取该段内存，底层的操作系统能自动将数据写会到对应的文件中，提高了文件读写的效率
使用Copy-On-Write技术，提高读操作的并发，简单来讲就是复制一个文件时并不会把原先的文件复制一份到内存，而是在内存中做一个映射指向原始文件，只有当对文件有修改时才会复制更新后的文件到内存并且修改映射到新的地址
内部使用B+树实现
使用golang语言开发
支持完全可序列化ACID事务
BoltDB中的B+树存储如下所示，B+树的非叶子节点存储的是revision，对于revision可以理解为唯一并且递增的序列，包含两个字段，main和sub，main表示每个事务的一个id，是全局自增的，sub表示每个事务中对于每个key的更新操作，sub在每个事务中都从0开始。
Boltdb文件指的是etcd数据目录下的member/snap/db的文件，etcd的keyvalue、lease、meta、member、cluster、auth等所有数据存储在其中。 etcd启动的时候，会通过mmap机制将db文件映射到内存，后续可从内存中快速读取文件中的数据
写请求通过fwrite和fdatasync来写入、持久化数据到磁盘
文件的内容由若干个page组成，一般情况下page size为4KB
page按照功能可分为元数据页(meta page)、B+ tree索引节点页(branch page)、B+ tree叶子节点页(leaf page)、空闲页管理页(freelist page)、空闲页(free page)
文件最开头的两个page是固定的db元数据meta page
空闲页管理页记录了db中哪些页是空闲、可使用的
索引节点页保存了B+ tree的内部节点，如图中右边部分所示，它们记录了key值
叶子节点页记录了B+ tree中的key-value和bucket数据
boltdb逻辑上通过B+ tree来管理branch/leaf page，实现快速查找、写入key-value数据
2.5.2 内存存储结构
ETCD在内存中维护了一个基于B树的二级索引来通过业务的Key映射到底层存储中的B+树，其中B+树中，key为业务的key，value为keyIndex
type keyIndex struct {
key []byte
modified revision // the main rev of the last modification
generations []generation
}
key字段就是用户的原始key
modified字段记录了这个key的最后一次修改对应的revision信息
generations保存key的多版本信息（历史修改记录）
type generation struct {
ver int64 //key修改的次数
created revision // when the generation is created (put in first revision).
revs []revision //每次更新key时，append对应的revision
}
generation结构定义如上，当一个key从无到有的时候 ，就会创建一个generation，其created字段记录了引起本次key创建的revision信息。当用户继续更新这个key的时候，generation.revs数组会不断追加记录本次revision信息（main,sub）。如果一个key被删除后，又被再次创建，则新建一个generation。
2.5.3 WAL日志和快照
故障快速恢复：当你的数据遭到破坏时，就可以通过执行所有WAL中记录的修改操作，快速从最原始的数据恢复到数据损坏前的状态。
数据回滚（undo）/重做（redo）：因为所有的修改操作都被记录在WAL中，需要回滚或重做，只需要方向或正向执行日志中的操作即可。
在etcd的数据目录中，WAL文件以$seq-$index.wal的格式存储。最初始的WAL文件是0000000000000000-0000000000000000.wal，表示是所有WAL文件中的第0个，初始的Raft状态编号为0。运行一段时间后可能需要进行日志切分，把新的条目放到一个新的WAL文件中。假设，当集群运行到Raft状态为20时，需要进行WAL文件的切分时，下一份WAL文件就会变为0000000000000001-0000000000000021.wal。如果在10次操作后又进行了一次日志切分，那么后一次的WAL文件名会变为0000000000000002-0000000000000031.wal。可以看到-符号前面的数字是每次切分后自增1，而-符号后面的数字则是根据实际存储的Raft起始状态来定。
⽂件元数据记录
包含节点ID、集群ID信息，它在WAL⽂件创建的时候写⼊
⽇志条⽬记录
包含Raft⽇志信息，如put提案内容
状态信息记录
包含集群的任期号、节点投票信息等，⼀个⽇志⽂件中会有多条，以最后的记录为准
CRC记录
包含上⼀个WAL⽂件的最后的CRC（循环冗余校验码）信息
在创建、切割WAL⽂件时，作为第⼀条记录写⼊到新的WAL⽂件，⽤于校验数据⽂件的完整性、准确性等
快照记录
包含快照的任期号、⽇志索引信息，⽤于检查快照⽂件的准确性
⾸先将Raft⽇志条⽬内容（含任期号、索引、提案内容）序列化后保存到WAL记录的Data字段
然后计算Data的CRC值，设置Type为Entry Type
以上信息就组成了⼀个完整的WAL记录
最后计算WAL记录的⻓度，顺序写⼊WAL⻓度（Len Field）
然后写⼊记录内容，调⽤fsync持久化到磁盘，完成⽇志条⽬保存到持久化存储中
既然有了WAL实时存储了所有的变更，为什么还需要snapshot呢？随着使用量的增加，WAL存储的数据会暴增，为了防止磁盘很快就爆满，etcd默认每10000条记录做一次snapshot，经过snapshot以后的WAL文件就可以删除。因此，snapshot是为了防止数据过多而进行的状态快照，在Etcd V3的快照机制是从BoldDB中读取数据库的当前版本数据，然后序列化到磁盘中。通过引入WAL和快照机制，ETCD实现了故障的快速恢复。
2.6 租约Lease
lease是分布式系统中一个常见的概念，用于代表一个分布式租约。典型情况下，在分布式系统中需要去检测一个节点是否存活时，就需要租约机制。
如果希望这个租约永不过期，需要周期性的调用KeepAlive方法刷新租约。比如说需要检测分布式系统中一个进程是否存活，可以在进程中去创建一个租约，并在该进程中周期性的调用KeepAlive的方法。如果一切正常，该节点的租约会一致保持，如果这个进程挂掉了，最终这个租约就会自动过期。
在etcd中，允许将多个key关联在同一个lease之上，这个设计是非常巧妙的，可以大幅减少lease对象刷新带来的开销。试想一下，如果有大量的key都需要支持类似的租约机制，每一个key都需要独立的去刷新租约，这会给etcd带来非常大的压力。通过多个key绑定在同一个lease的模式，我们可以将超时间相似的key聚合在一起，从而大幅减小租约刷新的开销，在不失灵活性同时能够大幅提高etcd支持的使用规模。
3、ETCD使用场景
3.1 服务注册与发现
一个强一致性、高可用的服务存储目录。基于Raft算法的etcd天生就是这样一个强一致性和高可用的服务存储目录；
一种注册服务和监控服务健康状态的检测机制。用户可以在etcd中注册服务，并且对注册的服务配置key TTL，定义保持服务的心跳以达到监控健康状态的效果；
具备查找和连接服务的机制。在etcd指定的主题下注册的服务也能在对应的主题下找到；为了确保连接，可以在各个服务机器上都部署一个代理模式的etcd, 这样就可以确保访问etcd集群的服务都可以互相连接
在进程内部启动之后，可以将自身所在的地址注册到etcd； API网关够通过etcd及时感知到后端进程的地址，当后端进程发生故障迁移时会重新注册到etcd中，API网关也能够及时地感知到新的地址；
利用etcd提供的Lease机制，如果提供服务的进程运行过程中出现了异常（crash），API网关也可以摘除其流量避免调用超时。
3.2 消息发布与订阅
在分布式系统中，消息的发布和订阅机制适用于组件之间的通信机制。具体而言就是，设置一个配置共享中心，消息提供者在这个配置中心发布消息，而消息使用者则订阅它们关心的主题，一旦所关心的主题有消息发布，就会实时通知订阅者。通过这种方式，可以实现分布式系统配置的集中式管理和实时动态更新。
1） etcd集中管理应用配置信息更新
应用在启动的时候主动从etcd获取一次配置信息，同时在etcd节点上注册Watcher并等待。每当配置有更新的时候，etcd都会实时通知订阅者，以此达到获取最新配置信息的目的。
2）分布式日志收集系统
这个系统的核心工作是收集分布在不同机器上的日志。通过在etcd上创建一个以应用（或主题）为名字的目录，并将这个应用（或主题）相关的所有机器IP以子目录的形式存储在目录下。然后设置一个递归的etcd Watcher，递归式地监控应用（或主题）目录下所有信息的变动。这样就能够实现在机器IP（消息）发生变动时，系统能够实时接受收集器调整的任务分配。
3.3 元数据存储
Kubernetes将自身所用的状态存储在etcd中，其状态数据的高可用交给etcd来解决，Kubernetes系统自身不需要再应对复杂的分布式系统状态处理，自身的系统架构得到了大幅的简化。
3.4 分布式锁
因为ETCD使用Raft算法保持数据的一致性，某次操作存储到集群中的值必然是唯一的，因此很容易实现分布式锁功能。在前文“分布式锁实现机制”中也有介绍，ETCD分布式锁实现流程如下所示，主要分为6个阶段：
1）准备阶段
客户端连接Etcd，以/lock/mylock为前缀创建全局唯一的key，假设第一个客户端对应的key为“/lock/mylock/UUIDA”，第二个客户端对应的key为“/lock/mylock/UUIDB”，第三个客户端对应的key为“/lock/mylock/UUIDC”。客户端分别为自己的key创建租约lease，租约的长度根据业务耗时确定。
当客户端持有锁期间，其它客户端只能等到，为了避免等待期间租约失效，客户端需要创建一个定时任务作为心跳以保证租约的有效性。此外，如果持有锁期间客户端奔溃，心跳停止，key值也会因为租约到期而被删除，从而释放锁资源，避免死锁。
客户端进行Put操作，将步骤1中创建的key值绑定租约写入Etcd，根据ETCD的revision机制，ETCD中会根据事务的操作顺序记录revision值。同时，客户端需要记录Etcd返回的revision值，用于接下来判断是否获得锁。在图中，Etcd中插入三条key-value记录，Revision分别为1/2/3，其中客户端A返回的Revision值为1。
客户端以前缀/lock/mylock读取key-value列表，判断自己的Revision是否为当前key-value列表中最小的，如果是则认为获得锁；否则的话，会监听key-value中前一个Revision比自己小的key的DELETE事件，一旦监听到删除事件或者因为租约到期的删除事件，则客户端获得锁资源。在图中，客户端A执行完事务，释放锁资源执行DELETE操作，客户端B即获得锁资源。
客户端在获得锁资源后，执行业务逻辑。
完成业务流程后对应的key释放锁。
4、总结
ETCD作为持久化的key-value键值系统，以及基于Raft协议的分布式系统数据一致性提供者，已经广泛用于分布式系统中的共享配置、服务发现等场景。相比于Zookeeper，ETCD安装部署更为简单、架构更为稳定可靠，支持多版本并发控制，能够提供高性能和高吞吐的数据访问，已被Kubernetes用于核心的存储引擎。本文主要介绍了ETCD的基础架构以及读写流程、基于Raft的日志复制和Watcher这两个关键特性、租约和数据版本机制、数据存储的模型，最后简要介绍了典型的使用场景。
参考资料：
https://etcd.io/docs/v3.5/
https://www.cnblogs.com/traditional/p/9445930.html
ETCD实战培训，https://time.geekbang.org/column/intro/100069901
https://blog.csdn.net/songfeihu0810232/article/details/123786357
https://www.infoq.cn/article/etcd-interpretation-application-scenario-implement-principle
https://developer.aliyun.com/article/738563
https://blog.csdn.net/qq_34556414/article/details/125582162
https://blog.csdn.net/u012588879/article/details/119135021