Etcd
Etcd是CoreOS基于Raft开发的分布式key-value存储，可用于服务发现、共享配置以及一致性保障（如数据库选主、分布式锁等）。
在分布式系统中，如何管理节点间的状态一直是一个难题，etcd像是专门为集群环境的服务发现和注册而设计，它提供了数据TTL失效、数据改变监视、多值、目录监听、分布式锁原子操作等功能，可以方便的跟踪并管理集群节点的状态。
- 键值对存储：将数据存储在分层组织的目录中，如同在标准文件系统中.
- 监测变更：监测特定的键或目录以进行更改，并对值的更改做出反应.
- 简单：curl可访问的用户的API（HTTP+JSON).
- 安全：可选的SSL客户端证书认证.
- 快速：单实例每秒1000次写操作，2000+次读操作.
- 可靠：使用Raft算法保证一致性
其主要功能包括：
- 基本的key-value存储
- 监听机制
- key的过期及续约机制，用于监控和服务发现
- 原子Compare And Swap和Compare And Delete，用于分布式锁和leader选举
使用场景包括：
- 也可以用于键值对存储，应用程序可以读取和写入etcd中的数据
- etcd比较多的应用场景是用于服务注册与发现
- 基于监听机制的分布式异步系统
键值对存储
etcd 是一个键值存储的组件，其他的应用都是基于其键值存储的功能展开。
- 采用kv型数据存储，一般情况下比关系型数据库快。
- 支持动态存储(内存)以及静态存储(磁盘)。
- 分布式存储，可集成为多节点集群。
- 存储方式，采用类似目录结构。（B+tree）
- 只有叶子节点才能真正存储数据，相当于文件。
- 叶子节点的父节点一定是目录，目录不能存储数据。
服务注册与发现
- 强一致性、高可用的服务存储目录。基于 Raft 算法的 etcd 天生就是这样一个强一致性、高可用的服务存储目录。
- 一种注册服务和服务健康状况的机制。用户可以在 etcd 中注册服务，并且对注册的服务配置 key TTL，定时保持服务的心跳以达到监控健康状态的效果。
消息发布与订阅
在分布式系统中，最适用的一种组件间通信方式就是消息发布与订阅。即构建一个配置共享中心，数据提供者在这个配置中心发布消息，而消息使用者则订阅他们关心的主题，一旦主题有消息发布，就会实时通知订阅者。
通过这种方式可以做到分布式系统配置的集中式管理与动态更新。
应用中用到的一些配置信息放到etcd上进行集中管理。应用在启动的时候主动从etcd获取一次配置信息，同时，在etcd节点上注册一个Watcher并等待，以后每次配置有更新的时候，etcd都会实时通知订阅者，以此达到获取最新配置信息的目的。
TTL（time to live） 指的是给一个key设置一个有效期，到期后这个key就会被自动删掉，这在很多分布式锁的实现上都会用到，可以保证锁的实时有效性。
Atomic Compare-and-Swap（CAS） 指的是在对key进行赋值的时候，客户端需要提供一些条件，当这些条件满足后，才能赋值成功。这些条件包括：
prevExist：key当前赋值前是否存在
prevValue：key当前赋值前的值
prevIndex：key当前赋值前的Index
这样的话，key的设置是有前提的，需要知道这个key当前的具体情况才可以对其设置。
# 基本的数据读写数据:
# 写入数据
etcdctl --endpoints=localhost:12379 put /a b
# 读取数据
etcdctl --endpoints=localhost:12379 get /a
# 按key的前缀查询数据
etcdctl --endpoints=localhost:12379 get --prefix /
# 只显示键值
etcdctl --endpoints=localhost:12379 get --prefix / --keys-only --debug
Raft协议
Raft协议是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。Raft协议基于quorum机制，即大多数同意原则，任何的变更都需超过半数的成员确认.
在上图中，服务器中的一致性模块(Consensus Modle)接受来自客户端的指令，并写入到自己的日志中，然后通过一致性模块和其他服务器交互，确保每一条日志都能以相同顺序写入到其他服务器的日志中，即便服务器宕机了一段时间。
在raft体系中，有一个强leader，由它全权负责接收客户端的请求命令，并将命令作为日志条目复制给其他服务器，在确认安全的时候，将日志命令提交执行。当leader故障时，会选举产生一个新的leader。在强leader的帮助下，raft将一致性问题分解为了三个子问题：
- leader选举：当已有的leader故障时必须选出一个新的leader
- 日志同步：leader接受来自客户端的命令，记录为日志，并复制给集群中的其他服务器，并强制其他节点的日志与leader保持一致
- 安全措施：通过一些措施确保系统的安全性，如确保所有状态机按照相同顺序执行相同命令的措施
Raft协议中每个节点承担了不同的角色：
- leader：负责和客户端进行交互，并且负责向其他节点同步日志的，一个集群只有一个leader
- candidate：当leader宕机后，部分follower将转为candidate，并为自己拉票，获得半数以上票数的candidate成为新的leader
- follower：一般情况下，除了leader，其他节点都是follower
另外，Raft4.2.1引入了新角色：learner（只接收数据，不参与投票，当数据同步的时候会成为flower，现在默认新节点加入的其实就是learner）
当出现一个etcd集群需要增加节点时，新节点与Leader的数据差异较大，需要较多数据同步才能跟上leader的最新的数据。
此时Leader的网络带宽很可能被用尽，进而使得leader无法正常保持心跳。进而导致follower重新发起投票。进而可能引发etcd集群不可用。
因此有了Learner.Learner角色只接收数据而不参与投票，因此增加learner节点时，集群的quorum不变。
Raft协议中的一些其他概念：
- term：term使用连续递增的编号的进行识别，每一个term都从新的选举开始。同时term也有指示逻辑时钟的作用，最新日志的term越大证明越有资格成为leader
- RequestVote RPC：它由选举过程中的candidate发起，用于拉取选票
- AppendEntries RPC：它由leader发起，用于复制日志或者发送心跳信号
leader选举
raft通过心跳机制发起leader选举。节点都是从follower状态开始的，如果收到了来自leader或candidate的RPC，那它就保持follower状态，避免争抢成为candidate。leader会发送空的AppendEntries RPC作为心跳信号来确立自己的地位，如果follower一段时间(election timeout)没有收到心跳，它就会认为leader已经挂了，发起新的一轮选举
选举发起后，一个follower会增加自己的当前term编号并转变为candidate。它会首先投自己一票，然后向其他所有节点并行发起RequestVote RPC，之后candidate状态将可能发生如下三种变化：
- 赢得选举，成为leader：如果它在一个term内收到了大多数的选票，将会在接下的剩余term时间内称为leader，然后就可以通过发送心跳确立自己的地位。每一个server在一个term内只能投一张选票，并且按照先到先得的原则投出
- 其他server成为leader：在等待投票时，可能会收到其他server发出AppendEntries RPC心跳信号，说明其他leader已经产生了。这时通过比较自己的term编号和RPC过来的term编号，如果比对方大，说明leader的term过期了，就会拒绝该RPC，并继续保持候选人身份; 如果对方编号不比自己小，则承认对方的地位,转为follower
- 选票被瓜分，选举失败：如果没有candidate获取大多数选票，则没有leader产生, candidate们等待超时后发起另一轮选举。为了防止下一次选票还被瓜分，必须采取一些额外的措施，raft采用随机election timeout的机制防止选票被持续瓜分。通过将timeout随机设为一段区间上的某个值，因此很大概率会有某个candidate率先超时然后赢得大部分选票。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
日志复制过程
一旦leader被选举成功，就可以对客户端提供服务了。客户端提交每一条命令都会被按顺序记录到leader的日志中，每一条命令都包含term编号和顺序索引，然后向其他节点并行发送AppendEntries RPC用以复制命令(如果命令丢失会不断重发)，当复制成功也就是大多数节点成功复制后，leader就会提交命令，即执行该命令并且将执行结果返回客户端，raft保证已经提交的命令最终也会被其他节点成功执行。leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的，而且之前的命令也是相同的。当发送AppendEntries RPC时，会包含leader上一条刚处理过的命令，接收节点如果发现上一条命令不匹配，就会拒绝执行。
在这个过程中可能会出现一种特殊故障：如果leader崩溃了，它所记录的日志没有完全被复制，会造成日志不一致的情况，follower相比于当前的leader可能会丢失几条日志，也可能会额外多出几条日志，这种情况可能会持续几个term。如下图所示：
在上图中，框内的数字是term编号，a、b丢失了一些命令，c、d多出来了一些命令，e、f既有丢失也有增多，这些情况都有可能发生。比如f可能发生在这样的情况下：f节点在term2时是leader，在此期间写入了几条命令，然后在提交之前崩溃了，在之后的term3中它很快重启并再次成为leader，又写入了几条日志，在提交之前又崩溃了，等他苏醒过来时新的leader来了，就形成了上图情形。在Raft中，leader通过强制follower复制自己的日志来解决上述日志不一致的情形，那么冲突的日志将会被重写。为了让日志一致，先找到最新的一致的那条日志(如f中索引为3的日志条目)，然后把follower之后的日志全部删除，leader再把自己在那之后的日志一股脑推送给follower，这样就实现了一致。而寻找该条日志，可以通过AppendEntries RPC，该RPC中包含着下一次要执行的命令索引，如果能和follower的当前索引对上，那就执行，否则拒绝，然后leader将会逐次递减索引，直到找到相同的那条日志。
然而这样也还是会有问题，比如某个follower在leader提交时宕机了，也就是少了几条命令，然后它又经过选举成了新的leader，这样它就会强制其他follower跟自己一样，使得其他节点上刚刚提交的命令被删除，导致客户端提交的一些命令被丢失了，下面一节内容将会解决这个问题。Raft通过为选举过程添加一个限制条件，解决了上面提出的问题，该限制确保leader包含之前term已经提交过的所有命令。Raft通过投票过程确保只有拥有全部已提交日志的candidate能成为leader。由于candidate为了拉选票需要通过RequestVote RPC联系其他节点，而之前提交的命令至少会存在于其中某一个节点上,因此只要candidate的日志至少和其他大部分节点的一样新就可以了, follower如果收到了不如自己新的candidate的RPC,就会将其丢弃.
还可能会出现另外一个问题, 如果命令已经被复制到了大部分节点上,但是还没来的及提交就崩溃了,这样后来的leader应该完成之前term未完成的提交. Raft通过让leader统计当前term内还未提交的命令已经被复制的数量是否半数以上, 然后进行提交.
日志压缩
随着日志大小的增长，会占用更多的内存空间，处理起来也会耗费更多的时间，对系统的可用性造成影响，因此必须想办法压缩日志大小。Snapshotting是最简单的压缩方法，系统的全部状态会写入一个snapshot保存起来，然后丢弃截止到snapshot时间点之前的所有日志。Raft中的snapshot内容如下图所示：
每一个server都有自己的snapshot，它只保存当前状态，如上图中的当前状态为x=0,y=9，而last included index和last included term代表snapshot之前最新的命令，用于AppendEntries的状态检查。
虽然每一个server都保存有自己的snapshot，但是当follower严重落后于leader时，leader需要把自己的snapshot发送给follower加快同步，此时用到了一个新的RPC：InstallSnapshot RPC。follower收到snapshot时，需要决定如何处理自己的日志，如果收到的snapshot包含有更新的信息，它将丢弃自己已有的日志，按snapshot更新自己的状态，如果snapshot包含的信息更少，那么它会丢弃snapshot中的内容，但是自己之后的内容会保存下来。
etcd基于Raft的一致性
选举方法
初始启动时，节点处于follower状态并被设定一个election timeout，如果在这一时间周期内没有收到来自 leader 的 heartbeat，节点将发起选举：将自己切换为 candidate 之后，向集群中其它 follower节点发送请求，询问其是否选举自己成为 leader。
当收到来自集群中过半数节点的接受投票后，节点即成为 leader，开始接收保存 client 的数据并向其它的 follower 节点同步日志。如果没有达成一致，则candidate随机选择一个等待间隔（150ms ~ 300ms）再次发起投票，得到集群中半数以上follower接受的candidate将成为leader
leader节点依靠定时向 follower 发送heartbeat来保持其地位。
任何时候如果其它 follower 在 election timeout 期间都没有收到来自 leader 的 heartbeat，同样会将自己的状态切换为 candidate 并发起选举。每成功选举一次，新 leader 的任期（Term）都会比之前leader 的任期大1
日志复制
当Leader收到客户端的日志（事务请求）后先把该日志追加到本地的Log中，然后通过heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送ACK，当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下heartbeat中Leader将通知所有的Follower将该日志存储在自己的本地磁盘中。
安全性
安全性是用于保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader commit Log时变得不可用了，稍后可能该Follower又会被选举为Leader，这时新Leader可能会用新的Log覆盖先前已committed的Log，这就是导致节点执行不同序列；Safety就是用于保证选举出来的Leader一定包含先前 committed Log的机制；
选举安全性（Election Safety）：每个任期（Term）只能选举出一个Leader
Leader完整性（Leader Completeness）：指Leader日志的完整性，当Log在任期Term1被Commit后，那么以后任期Term2、Term3…等的Leader必须包含该Log.
Raft在选举阶段就使用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大或Term相同Index更大则投票，否则拒绝该请求。
失效处理
1）Leader失效：其他没有收到heartbeat的节点会发起新的选举，而当Leader恢复后由于步进数小会自动成为follower（日志也会被新leader的日志覆盖）
2）follower节点不可用：follower 节点不可用的情况相对容易解决。因为集群中的日志内容始终是从 leader 节点同步的，只要这一节点再次加入集群时重新从 leader 节点处复制日志即可。
3）多个candidate：冲突后candidate将随机选择一个等待间隔（150ms ~ 300ms）再次发起投票，得到集群中半数以上follower接受的candidate将成为leader
wal日志
wal日志是二进制的，解析出来后是以上数据结构LogEntry。
第一个字段type，主要有两种，一种是0表示Normal，1表示ConfChange（ConfChange表示 Etcd 本身的配置变更同步，比如有新的节点加入等）。
第二个字段是term，每个term代表一个主节点的任期，每次主节点变更term就会变化。
第三个字段是index，这个序号是严格有序递增的，代表变更序号。
第四个字段是二进制的data，将raft request对象的pb结构整个保存下。etcd 源码下有个tools/etcd-dump-logs，可以将wal日志dump成文本查看，可以协助分析Raft协议。
Raft协议本身不关心应用数据，也就是data中的部分，一致性都通过同步wal日志来实现，每个节点将从主节点收到的data apply到本地的存储，Raft只关心日志的同步状态，如果本地存储实现的有bug，比如没有正确的将data apply到本地，也可能会导致数据不一致。
WAL 机制使得 etcd 具备了以下两个功能：
1.故障快速恢复： 当你的数据遭到破坏时，就可以通过执行所有 WAL 中记录的修改操作，快速从最原始的数据恢复到数据损坏前的状态。
2.数据回滚（undo）/重做（redo）：因为所有的修改操作都被记录在 WAL 中，需要回滚或重做，只需要正向执行日志中的操作即可
etcd v3 存储，Watch以及过期机制
etcd v3 store 分为两部分，一部分是内存中的索引，kvindex，是基于Google开源的一个Golang的btree实现的，另外一部分是后端存储。按照它的设计，backend可以对接多种存储，当前使用的boltdb。boltdb是一个单机的支持事务的kv存储，etcd 的事务是基于boltdb的事务实现的。etcd 在boltdb中存储的key是reversion版本号信息，value是 etcd 自己的key-value组合，也就是说 etcd 会在boltdb中把每个版本都保存下，从而实现了多版本机制。
revision 主要由两部分组成：
- 第一部分 main rev，每次事务进行加一。
- 第二部分 sub rev，同一个事务中的每次操作加一。
如果要从 boltdb 中查询数据，必须通过 revision，但客户端都是通过 key 来查询 value，所以 Etcd 的内存 kvindex 保存的就是 key 和 revision 之前的映射关系，用来加速查询。
参考：
Raft论文
Kubernetes 控制平面组件：etcd
Raft协议详解
Raft协议原理详解
etcd中Raft协议
etcd实现-全流程分析