肝了一个月的ETCD，从Raft原理到实践
很有意思的Raft原理，带你动画还原，后面附带具体ETCD示例，欢迎来戳~~
前言
高能预警，本文是我今年年初写了，当时花了一个月时间，所以内容会比较长，其中的Raft协议非常硬核，由于当时对文章排版不熟练，所以可读性不高，现在对文章重新整理，提炼了比较核心的内容。
我相信90%的读者不会一口气看完，虽然文章精简了，但是还是比较长，只是希望想日后想学习ETCD的同学，或者面试前需要了解的同学回头翻一下就够了，那么我写这篇文章的意义就有了。
也不多BB，直接开整。
走进ETCD
什么是ETCD
etcd是一个Go言编写的分布式、高可用的一致性键值存储系统，用于提供可靠的分布式键值存储、配置共享和服务发现等功能，具有以下特点：
简单： 易使用：基于HTTP+JSON的API让你用curl就可以轻松使用； 易部署：使用Go语言编写，跨平台，部署和维护简单。 可靠： 强一致：使用Raft算法充分保证了分布式系统数据的强一致性； 高可用：具有容错能力，假设集群有n个节点，当有(n-1)/2节点发送故障，依然能提供服务； 持久化：数据更新后，会通过WAL格式数据持久化到磁盘，支持Snapshot快照。 快速：每个实例每秒支持一千次写操作，极限写性能可达10K QPS。 安全：可选SSL客户认证机制。
ETCD框架
从etcd的架构图中我们可以看到，etcd主要分为四个部分：
HTTP Server：用于处理用户发送的API请求以及其它etcd节点的同步与心跳信息请求。 Store：用于处理etcd支持的各类功能的事务，包括数据索引、节点状态变更、监控与反馈、事件处理与执行等等，是etcd对用户提供的大多数API功能的具体实现。 Raft：Raft强一致性算法的具体实现，是etcd的核心。 WAL：Write Ahead Log（预写式日志），是etcd的数据存储方式。除了在内存中存有所有数据的状态以及节点的索引以外，etcd就通过WAL进行持久化存储。WAL中，所有的数据提交前都会事先记录日志。Snapshot是为了防止数据过多而进行的状态快照；Entry表示存储的具体日志内容。
Raft协议
基本概念
名词解释
Raft协议一共包含如下3类角色：
Leader（领袖）：领袖由群众投票选举得出，每次选举，只能选出一名领袖； Candidate（候选人）：当没有领袖时，某些群众可以成为候选人，然后去竞争领袖的位置； Follower（群众）：这个很好理解，就不解释了。
然后在进行选举过程中，还有几个重要的概念：
Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖； Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举； Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。
角色转换
这幅图是领袖、候选人和群众的角色切换图，我先简单总结一下：
群众 -> 候选人：当开始选举，或者“选举超时”时 候选人 -> 候选人：当“选举超时”，或者开始新的“任期” 候选人 -> 领袖：获取大多数投票时 候选人 -> 群众：其它节点成为领袖，或者开始新的“任期” 领袖 -> 群众：发现自己的任期ID比其它节点分任期ID小时，会自动放弃领袖位置 备注：后面会针对每一种情况，详细进行讲解。
选举
领导人选举
为了便于后续的讲解，我画了一副简图，“选举定时器”其实就是每个节点的“超时时间”。
选举领导人：候选人B开始发起投票，群众A和C返回投票，当候选人B获取大部分选票后，选举成功，候选人B成为领袖。
心跳探测：为了时刻宣誓自己的领导人地位，领袖B需要时刻向群众发起心跳，当群众A和C收到领袖B的心跳后，群众A和C的“超时时间”会重置为0，然后重新计数，依次反复。
这里需要说明一下，领袖广播心跳的周期必须要短于“选举定时器”的超时时间，否则群众会频繁成为候选者，也就会出现频繁发生选举，切换Leader的情况。
领袖挂掉情况
当领袖B挂掉，群众A和C会的“选举定时器”会一直运行，当群众A先超时时，会成为候选人，然后后续流程和“领导人选举”流程一样，即通知投票 -> 接收投票 -> 成为领袖 -> 心跳探测。
出现多个候选者情况
当出现多个候选者A和D时，两个候选者会同时发起投票，如果票数不同，最先得到大部分投票的节点会成为领袖；如果获取的票数相同，会重新发起新一轮的投票。
当C成为新的候选者，此时的任期Term为5，发起新一轮的投票，其它节点发起投票后，会更新自己的任期值，最后选择新的领袖为C节点。
日志复制
复制状态机
复制状态机的基本思想是一个分布式的状态机，系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在操作日志中。如下图所示，服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中，它与其他服务器上的一致性模块进行通信，以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。
数据同步流程
数据同步流程，借鉴了“复制状态机”的思想，都是先“提交”，再“应用”。当Client发起数据更新请求，请求会先到领袖节点C，节点C会更新日志数据，然后通知群众节点也更新日志，当群众节点更新日志成功后，会返回成功通知给领袖C，至此完成了“提交”操作；当领袖C收到通知后，会更新本地数据，并通知群众也更新本地数据，同时会返回成功通知给Client，至此完成了“应用”操作，如果后续Client又有新的数据更新操作，会重复上述流程。
日志原理
每一个日志条目一般包括三个属性：整数索引Log Index、任期号Term和指令Commond。每个条目所包含的“整数索引”即该条目在日志文件中的槽位，“任期号”对应到图中就是每个方块中的数字，用于检测在不同服务器上日志的不一致问题，指令即用于被状态机执行的外部命令，图中就是带箭头的数字。
领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的呢？一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的。例如，图中的9号条目在其中4节点（一共7个节点）上具有复制，所以9号条目是可被提交的；但条目10只在其中3个节点上有复制，因此10号条目不是可被提交的。
一般情况下，Leader和Follower的日志都是保存一致的，如果Leader节点在故障之前没有向其它节点完全复制日志文件之前的所有条目，会导致日志不一致问题。在Raft算法中，Leader会强制Follower和自己的日志保存一致，因此Follower上与Leader的冲突日志会被领导者的日志强制覆写。为了实现上述逻辑，就需要知道Follower上与Leader日志不一致的位置，那么Leader是如何精准找到每个Follower日志不一致的那个槽位呢？
Leader为每一个Follower维护了一个nextlndex，它表示领导人将要发送给该追随者的下一条日志条目的索引，当一个Leader赢得选举时，它会假设每个Follower上的日志都与自己的保持－致，于是先将 nextlndex初始化为它最新的日志条目索引数+1，在上图中，由于Leader最新的日志条目index是10 ，所以nextlndex的初始值是11。当Leader向Follower发送AppendEntries RPC时，它携带了（item_id，nextIndex - 1）二元组信息，item_id即为nextIndex - 1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后，会进行一致性检查，即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就像Leader返回AppendEntries RPC失败，然后领导人会将nextIndex递减，然后进行重试，直到成功为止。之后的逻辑就比较简单，Follower将nextIndex之前的日志全部保留，之后的全部删除，然后将Leader的nextIndex之后的日志全部同步过来。
上面只是讲述了方法，下面举个例子，加深一下理解，还是以上面的图为例。Leader的nextlndex为11，向b发送AppendEntries RPC(6,10)，发现b没有，继续发送(6,9)(6,8) (5,7) (5,6) (4,5)，最后发送(4,4)才找到，所以对于b，nextlndex=4之后的日志全部删除，然后将Leader的nextlndex=4的日志全部追加过来。
脑裂情况
当网络问题导致脑裂，出现双Leader情况时，每个网络可以理解为一个独立的网络，因为原先的Leader独自在一个区，所以向他提交的数据不可能被复制到大多数节点上，所以数据永远都不会提交，这个可以在第4幅图中体现出来（SET 3没有提交）。
当网络恢复之后，旧的Leader发现集群中的新Leader的Term比自己大，则自动降级为Follower，并从新Leader处同步数据达成集群数据一致，同步数据的方式可以详见“3.3.3 日志原理”。
脑裂情况其实只是异常情况的一种，当Leader通知Follower更新日志、Leader提交更新时，都存在各种异常情况导致的问题，这个我就不再详述了，具体可以参考《云原生分布式存储基石-etcd深入解析》书中的“1.4.3 异常情况”这一章，里面讲述的比较清楚。
ETCD集群部署
ETCD安装，请参考文章
《ETCD系列教程2 - ETCD体验》 吕梦楼，公众号：楼仔进阶之路ETCD教程-3.ETCD体验
下面我们可以部署一个etcd集群，我把代码还是写到文件中，第一个脚本为不支持在 Docs 外粘贴 block，内容如下（启动etcd需要很多参数，这些参数我都已经注释说明，更多参数详见：https://www.cnblogs.com/linuxws/p/11194403.html）：
TOKEN=token-01
CLUSTER_STATE=new
NAME_1=etcd-01
NAME_2=etcd-02
NAME_3=etcd-03
HOST_1=127.0.0.1
HOST_2=127.0.0.1
HOST_3=127.0.0.1
PORT_API_1=2379
PORT_PEER_1=2380
PORT_API_2=2479
PORT_PEER_2=2480
PORT_API_3=2579
PORT_PEER_3=2580
CLUSTER=${NAME_1}=http://${HOST_1}:${PORT_PEER_1},${NAME_2}=http://${HOST_2}:${PORT_PEER_2},${NAME_3}=http://${HOST_3}:${PORT_PEER_3}
# For every machine
THIS_NAME=${NAME_1}
THIS_IP=${HOST_1}
THIS_PORT_API=${PORT_API_1}
THIS_PORT_PEER=${PORT_PEER_1}
# 用于杀死进程
lsof -i:2379 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9
# --enable-v2 支持v2接口，可以省略
# --data-dir 数据存储目录，可以省略
# --name 节点名称，必须
# --initial-advertise-peer-urls 数据在集群内进行交互的url，必须
# --listen-peer-urls 集群节点之间通信监听的url，必须
# --advertise-client-urls 客户通过该地址与本member交互信息，可以省略
# --listen-client-urls 监听客户端请求的url，必须
# --initial-cluster 初始启动的集群配置，必须
# --initial-cluster-state 初始化集群状态，取值为new和existing，可以省略
# --initial-cluster-token 集群初始化token，可以省略
etcd --enable-v2=true --data-dir=data.${THIS_NAME} --name ${THIS_NAME} \
--initial-advertise-peer-urls http://${THIS_IP}:${THIS_PORT_PEER} --listen-peer-urls http://${THIS_IP}:${THIS_PORT_PEER} \
--advertise-client-urls http://${THIS_IP}:${THIS_PORT_API} --listen-client-urls http://${THIS_IP}:${THIS_PORT_API} \
--initial-cluster ${CLUSTER} \
--initial-cluster-state ${CLUSTER_STATE} --initial-cluster-token ${TOKEN}
第二个脚本需要把里面的内容替换如下：
# For every machine
THIS_NAME=${NAME_2}
THIS_IP=${HOST_2}
THIS_PORT_API=${PORT_API_2}
THIS_PORT_PEER=${PORT_PEER_2}
# 用于杀死进程
lsof -i:2479 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9
第三个脚本需要把里面的内容替换如下：
# For every machine
THIS_NAME=${NAME_3}
THIS_IP=${HOST_3}
THIS_PORT_API=${PORT_API_3}
THIS_PORT_PEER=${PORT_PEER_3}
# 用于杀死进程
lsof -i:2579 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9
有了这3个脚本，分别开3个窗口，分别执行，服务启动截图如下：
当这3个脚本全部启动后，集群部署完毕，我们检查一下3个节点的健康状态：
curl http://127.0.0.1:2379/health
curl http://127.0.0.1:2479/health
curl http://127.0.0.1:2579/health
如果都返回{"health":"true"}，表示部署成功，下面我们查看一下部署的节点信息：
curl http://127.0.0.1:2379/v2/members
返回结果如下，其中peerURLs是节点互相通信访问的url，clientURLs是对外访问的url：
{
"members":[
{
"id":"264ae6bc59e99892",
"name":"etcd-01",
"peerURLs":[
"http://127.0.0.1:2380"
],
"clientURLs":[
"http://127.0.0.1:2379"
]
},
{
"id":"dbafe5ad6b652eda",
"name":"etcd-02",
"peerURLs":[
"http://127.0.0.1:2480"
],
"clientURLs":[
"http://127.0.0.1:2479"
]
},
{
"id":"f570ae41f524bdcb",
"name":"etcd-03",
"peerURLs":[
"http://127.0.0.1:2580"
],
"clientURLs":[
"http://127.0.0.1:2579"
]
}
]
}
ETCD使用
集群管理
我们在部署集群时，用到一些方法，这里我简单汇总一下：
// 版本检查，输出{"etcdserver":"3.4.14","etcdcluster":"3.4.0"}
curl http://127.0.0.1:2379/version
// 健康检查，输出{"health":"true"}
curl http://127.0.0.1:2379/health
// 查看集群节点
curl http://127.0.0.1:2379/v2/members
键值操作
设置键的值：
curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world"
返回结果：
{
"action":"set",
"node":{
"key":"/message",
"value":"hello world",
"modifiedIndex":43,
"createdIndex":43
}
}
读取键的值：
curl http://127.0.0.1:2379/v2/keys/message
返回结果：
{
"action":"get",
"node":{
"key":"/message",
"value":"hello world",
"modifiedIndex":43,
"createdIndex":43
}
}
给键设置10s的超时时间：
curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world" -d ttl=10
返回结果（prevNode是旧值）：
{
"action":"set",
"node":{
"key":"/message",
"value":"hello world",
"expiration":"2021-01-21T00:16:13.777434Z",
"ttl":10,
"modifiedIndex":44,
"createdIndex":44
},
"prevNode":{
"key":"/message",
"value":"hello world",
"modifiedIndex":43,
"createdIndex":43
}
}
获取该键值，超时后，就提示“key not found”：
watch通知
可以对key设置监听，当key的值有变化时，会通知监听的客户端，我们先在客户端A监听key：
curl http://127.0.0.1:2379/v2/keys/message?wait=true
然后在客户端B，修改该key的值：
curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world2"
客户端A返回并退出，返回结果：
{
"action":"set",
"node":{
"key":"/message",
"value":"hello world2",
"modifiedIndex":48,
"createdIndex":48
}
}
如果希望客户端A能持续监听，不退出，可以通过增加stream=true参数：
curl "http://127.0.0.1:2379/v2/keys/message?wait=true&stream=true"
当在客户端B执行如下时：
curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world" -d ttl=10
客户端A会实时监听返回，比如当给key设置值，或者当key过期时，客户端A都会监听到：
ETCD安装，请参考文章
《ETCD系列教程2 - ETCD体验》 吕梦楼，公众号：楼仔进阶之路ETCD教程-3.ETCD体验
初探ETCD 3.0
该部分作为扩展知识，仅供了解，更多内容请参考文章
《ETCD系列教程3 - 深入ETCD》 吕梦楼，公众号：楼仔进阶之路ETCD教程-4.深入ETCD
版本说明
目前etcd主要经历了3个大的版本，分别为etcd 0.4版本、etcd 2.0版本和etcd 3.0版本。对于etcd 2.0版本，已经可以很好满足etcd的初步需求，主要包括：
专注于key-value存储，而不是一个完整的数据库； 通过HTTP + JSON的方式暴露给外部API； watch机制提供持续监听某个key变化的功能，以及基于TTL的key的自动过期机制。
但是在实际过程中，我们也发现了一些问题，比如客户端需要频繁地与服务端进行通信，集群在空间和时间上都需要承受较大的压力，以及垃圾回收key的时间不稳定等，同时“微服务”架构要求etcd能够单集群支撑更大规模的并发，因此诞生了etcd 3.0版本，主要对HTTP + JSON的通信方式、key的自动过期机制、watch机制、数据持久化等进行了优化，下面我们看看etcd 3.0版本对每个模块都做了哪些优化。
客户端通信方式
gRPC是Google开源的 个高性能、跨语言的RPC框架，基于HTTP/2协议实现。它使用protobuf作为序列化和反序列化协议，即基于 protobuf 来声明数据模型和RPC接口服务。protobuf的效率远高于JSON，尽管etcd v2的客户端已经对JSON的序列号和反序列化进行了大量的优化，但是etcd v3的gRPC序列号和反序列化的速度依旧是etcd v2的两倍多。
etcdv3的客户端使用gRPC与server进行通信，通信的消息协议使用protobuf进行约定，代替了v2版本的HTTP+JSON格式，使用二进制替代文本，更加节省空间。同时gRPC使用的是HTTP/2协议，同一个连接可以同时处理多个请求，不必像HTTP1.1协议中，多个请求需要建立多个连接。同时，HTTP/2会对请求的Header和请求数据进行压缩编码，常见的有Header帧，用于传输Header内容，另外就是Data帧，来传输正文实体。客户端可以将多个请求放到不同的流中，然后将这些流拆分成帧的形式进行二进制传输，传输的帧也会有一个编号，因此在一个连接中客户端可以发送多个请求，减少了连接数，降低了对服务器的压力，二进制的数据传输格式也会是传输速度更快。
总结一下，其实这里主要进行2点优化：
二进制取代字符串：通过gRPC进行通信，代替了v2版本的HTTP+JSON格式； 减少TCP连接：使用HTTP/2协议，同一个连接可以同时处理多个请求，摒弃多个请求需要建立多个连接的方式。
键的过期机制
etcdv2中的键的实效是使用TTL机制来实现的，每个有存活时间的键，客户端必须定期的进行刷新重新设置保证它不被自动删除，每次刷新同时还会重新建立连接去更新键。也就是说，及时整个集群都处于空闲状态，也会有很多客户端与服务器进行定期通信，以保证某个key不被自动删除。
etcdv3版本中采用了租约机制进行实现，每个租约会有一个TTL，然后将一些key附加到租约上，当租约到期后，附加到它上边的key都会被删除。利用键的过期机制可以实现服务注册功能，我们可以将一个服务的域名、IP等信息注册到etcd中，并给相应的键设置租约，并在TTL时间内定期维持一个心跳进行刷新。当服务故障后，心跳消失从而相应的键就会自动删除，从而实现了服务的注册功能和服务的健康检查功能。
总结一下，就是v2版本比较傻瓜，需要时刻维护每个key的通信，v3就比较智能，整个统一的过期key的代号，我们把代号称之为“租约”，我们只需要维护这个代号即可，避免客户端去维护所有的key。
watch机制
etcdv2中的键被废除以后，为了能够跟踪key的变化，使用了事件机制进行跟踪，维护键的状态，来防止被删除掉的后键还能恢复和watch到，但是有一个滑动窗口的大小限制，那么如果要获取1000个时间之前的键就获取不到了。因此etcdv2中通过watch来同步数据不是那么可靠，断开连接一段时间后就会导致有可能中间的键的改动获取不到了。在etcdv3中支持get和watch键的任意的历史版本记录。
另外，v2中的watch本质上还是建立很多HTTP连接，每一个watch建立一个tcp套接字连接，当watch的客户端过多的时候会大大消耗服务器的资源，如果有数千个客户端watch数千个key，那么etcd v2的服务端的socket和内存资源会很快被耗尽。v3版本中的watch可以进行连接复用，多个客户端可以共用相同的TCP连接，大大减轻了服务器的压力。
总结一下，其实这里主要进行2点优化：
实时监听key的更新：解决v2中途key的数据更新，客服端不会感知的问题； 多路复用：这个可以想到select和epool模型，就是一个客户之前需要建立多个TCP连接，现在只需要建立一个即可。
数据存储模型
etcd是一个key-value数据库，ectd v2只保存了key的最新的value，之前的value会被直接覆盖，如果需要知道一个key的历史记录，需要对该key维护一个历史变更的窗口，默认保存最新的1000个变更，但是当数据更新较快时，这1000个变更其实“不够用”，因为数据会被快速覆盖，之前的记录还是找不到。为了解决这个问题，etcd v3摒弃了v2不稳定的“滑动窗口”式设计，引入MVCC机制，采用从历史记录为主索引的存储结构，保存了key的所有历史记录变更，并支持数据在无锁状态下的的快速查询。etcd是一个key-value数据库，etcdv2的key是一个递归的文件目录结构，在v3版本中的键改成了扁平化的数据结构，更加简洁，并通过线段树的优化方式，支持key的快速查询。
由于etcd v3实现了MVCC，保存了每个key-value pair的历史版本，数据大了很多，不能将整个数据库都存放到内存中。因此etcd v3摒弃了内存数据库，转为磁盘数据库，即整个数据都存储在磁盘上，底层的存储引擎使用的是BoltDB。
总结一下，其实这里主要进行3点优化：
保存历史数据：摈弃v2的“滑动窗口”式设计，通过MVCC机制，保存了所有的历史数据； 数据落磁盘：因为要保存历史数据，数据量态度，不适合全内存存储，使用BoltDB存储； 查询优化：摒弃v2的目录式层级化设计，使用线段树优化查询。
欢迎大家多多点赞，更多文章，请关注微信公众号“楼仔进阶之路”，点关注，不迷路~~