zookeeper Leader的选举过程

假如有三个节点(s1,s2,s3)组成的集群。在集群启动过程中，当有一台zookeeper节点s1启动完成后，此时集群中只有一个节点无法进行leader的选举。当第二个节点s2启动成功后，此时两个节点可以正常通信，进入leader的选举过程，具体如下：

还是假如有三台服务器(s1,s2,s3)组成的集群,s2时leader。在集群运行中时，只有当集群中的leader宕机才会触发leader的重新选举，集群中follower宕机或者新节点的加入并不影响leader的地位。
选举过程如下：

zk通过Multi-Paxos思想实现分布式一致性，Multi-Paxos为了解决Paxos需要2轮RPC通讯(准备阶段和接受阶段)往返消息多、耗性能、延迟大的问题引入了Leader-Follower-Learner模式；考虑到高可用性，有Leader就会涉及选举Leader的问题，本节就来分析下zk是如何实现选主的；

以三个节点同时启动为例：

以3个节点中Server1作为Follower重启为例：

以4个节点中Server4作为Leader宕机为例：

Leader ：一个zk集群同一时刻只有一个Leader，所有写 *** 作必须通过Leader完成，然后再广播给其他服务器；
Follower ：一个zk集群同一时刻有多个Follower。Follower可以直接处理读请求，但是写请求需要转发给Leader处理，同时负责在Leader处理写请求时对请求进行投票；
Observer ：功能跟Follower类似，但是没有投票权；

Looking ：寻找Leader状态，处于该状态的服务器会发起选主；
Following ：跟随者状态，表明当前服务器是Follower；
Leading ：领导者状态，表明当前服务器是Leader;
Observing ：观察者状态，表明当前服务器是Observer;

Listenerrun 监听2888端口，阻塞在ServerSocketaccept，等待其他服务器请求创建连接；
RecvWorkerrun 阻塞在DataInputStreamread，获取对应服务器发送的投票信息；
SendWorkerrun 阻塞在ArrayBlockingQueuepoll，获取待发送消息，发送给对应服务器；
WorkerReceiverrun 阻塞在recvqueuepoll，获取RecvWorkerrun中接收的投票消息Notification；
WorkerSenderrun 阻塞在sendqueuepoll，获取待发送ToSend到SendWorkerrun进行处理；
QuorumPeerrun 集群模式启动过程中选举结束后，根据当前服务器状态进行之后的异步流程处理；

LinkedBlockingQueue<ToSend> sendqueue FastLeaderElection中的请求发送队列，存放的是ToSend；

LinkedBlockingQueue<Notification> recvqueue FastLeaderElection中的请求接受队列，存放的是Notification；

ConcurrentHashMap<Long, SendWorker> senderWorkerMap sid -> 当前服务器到该sid的SendWorker；每个服务器会跟比自己sid小的服务器创建一个SendWorker用于投票选主时发送投票信息；
ConcurrentHashMap<Long, ArrayBlockingQueue<ByteBuffer>> queueSendMap sid -> 当前服务器需要发送到该sid的投票消息的队列；WorkerSenderrun中会根据不同sid把对用的选票信息放入对应的ArrayBlockingQueue中；
ConcurrentHashMap<Long, ByteBuffer> lastMessageSent sid->最后一次发送到该sid的投票信息；
ArrayBlockingQueue<Message> recvQueue WorkerReceiverrun中接收到的投票信息，解析字节流转成Message放到recvQueue中；

zk选主涉及6个线程、多个集合，过程比较饶，必须要先把选主的流程和各个线程、集合的作用等搞清楚，不然理解起来比较难。下一节通过源码来具体分析选主的实现；
------ over ------

--listen-peer-urls

--listen-client-urls

--initial-advertise-peer-urls

--initial-cluster

--initial-cluster-state

--advertise-client-urls

1code

headless svc, 像DNS RR ClusterIP:None

kubectl -n stg1 get endpoints

client 怎么访问：

2配置文件

3apply

官方的code有两个问题

本地访问

扩容

利用反亲和性 分布etcd pod到不同节点

~ ❯❯❯ etcdctl get / --prefix

从 etcd 的架构图中我们可以看到，etcd 主要分为四个部分。

etcd 目前支持 V2 和 V3 两个大版本，这两个版本在实现上有比较大的不同，一方面是对外提供接口的方式，另一方面就是底层的存储引擎，V2 版本的实例是一个纯内存的实现，所有的数据都没有存储在磁盘上，而 V3 版本的实例就支持了数据的持久化。

v3默认boltdb

consortium etcd2+mysql

数据默认会存放在 /var/lib/etcd/default/ 目录。我们会发现数据所在的目录，会被分为两个文件夹中，分别是 snap 和 wal目录。

解决三个问题：节点选举、日志复制以及安全性 。

每一个 Raft 集群中都包含多个服务器，在任意时刻，每一台服务器只可能处于 Leader 、 Follower 以及 Candidate 三种状态；在处于正常的状态时，集群中只会存在一个 Leader 状态，其余的服务器都是 Follower 状态。

所有的 Follower 节点都是被动的，它们不会主动发出任何的请求 ，只会响应 Leader 和 Candidate 发出的请求。对于每一个用户的可变 *** 作，都会被路由给 Leader 节点进行处理，除了 Leader 和 Follower 节点之外，Candidate 节点其实只是集群运行过程中的一个临时状态。

每一个服务器都会存储当前集群的最新任期，它就像是一个单调递增的逻辑时钟，能够同步各个节点之间的状态，当前节点持有的任期会随着每一个请求被传递到其他的节点上。Raft 协议在每一个任期的开始时都会从一个集群中选出一个节点作为集群的 Leader 节点，这个节点会负责集群中的日志的复制以及管理工作。

客户端通过 监听指定的key可以迅速感知key的变化并作出相应处理 ，watch机制的实现依赖于 资源版本号revision的设计 ，每一次key的更新都会使得revision原子递增，因此根据不同的版本号revision的对比就可以感知新事件的发生。etcd watch机制有着广泛的应用，比如利用etcd实现分布式锁； k8s中监听各种资源的变化 ，从而实现各种controller逻辑等。

watch机制的实现主要可分为三个部分

client使用 watchClient 的watch接口发起watch请求，与server端建立一个 gRPCStream 连接。

server端会为每个client生成唯一一个watch id，并记录每个client也就是watcher监听的key或者key range，通过recvLoop接收client请求，通过sendLoop发送请求，server端只负责收发请求和响应。

主要的实现都放在了watchalbStore层，watchalbStore会监听key的变化，然后通过syncWatchersLoop和syncVictimsLoop两个处理流程将key的更新变化包装成event，通过channel发送给gRPC server。

MVCC（Multiversion Concurrency Control）多版本并发控制机制

场景1:

这就是悲观锁

悲观锁：悲观得认为并发事务会冲突，所以要先拿锁，拿到锁的作修改 *** 作

场景2

数据库：写回磁盘，A写好了。哎，B和C都是version 13，我咋写？算了，报错吧。。

就是乐观锁，默认不加锁，你尽管写，冲突我认怂！乐观锁其实不是锁，只是相对悲观锁来定义，适合读多写少。

乐观锁：乐观得认为数据不会冲突，但发生冲突时要能检测到。

场景3

这就是MVCC，在 MVCC 数据库中，你更新一个 key-value 数据的时候，它并不会直接覆盖原数据，而是 新增一个版本来存储新的数据，每个数据都有一个版本号 ，版本号是一个逻辑时钟，不会因为服务器时间的差异而受影响。

MVCC不等于乐观锁！

--rev 查的是main

在底层boltdb里，实际分布是这样的：

底层的key是revision，/奥特曼是用户key，“他很帅”就是用户value

删除

之前有delete动作，但是依然有版本记录。为什么？

删除这个动作，其实etcd是在blotdb里写了一条，“删除用户/奥特曼”

此时有个问题：用户说我的确删除了啊，真的不要了！请把空间还给我啊！

回收 compact（压缩）

etcdctl compact {version}

compact 需要一个版本号。这个版本号就是写事务递增的那个版本号，compact 12345，就是说把版本12345以前的 标记删除了的数据 释放掉，用户没删除的数据肯定不能回收。

如何压缩：

注意修改gomod

Watch

服务发现要解决的也是分布式系统中最常见的问题之一，即在同一个分布式集群中的进程或服务，要如何才能找到对方并建立连接。本质上来说，服务发现就是想要了解集群中是否有进程在监听 udp 或 tcp 端口，并且通过名字就可以查找和连接。

需要实现的功能；

discovergo

eBay payment

ebay kubernetes 控制面架构

问题

  ZAB是Zookeeper使用的分布式一致性协议，英文全称是：Zookeeper Atomic Broadcast，因此ZAB也称之为Zookeeper原子广播协议。在解决分布式一致性方面，Zookeeper并没有使用Paxos，而是采用了ZAB协议。基于ZAB协议，Zookeeper实现一种主备模式的系统架构来保持集群中主备副本之间数据的一致性。ZAB协议包括两种基本模式：消息广播（Message Broadcasting）和崩溃恢复（Leader Activation）。下面来详细介绍这两种基本模式的实现过程。

  消息广播是Zookeeper用来保证写入事务一致性的方法，在Zookeeper集群中，存在以下三种角色的节点：
Leader： Zookeeper集群的核心角色，在集群启动或崩溃恢复中通过Follower参与选举产生，为客户端提供读写服务，并对事务请求进行处理。
Follower： Zookeeper集群的核心角色，在集群启动或崩溃恢复中参加选举，没有被选上就是这个角色，为客户端提供读取服务，也就是处理非事务请求，Follower不能处理事务请求，对于收到的事务请求会转发给Leader。
Observer： 观察者角色，不参加选举，为客户端提供读取服务，处理非事务请求，对于收到的事务请求会转发给Leader。使用Observer的目的是为了扩展系统，提高读取性能。
  下面通过几张图对ZAB的消息广播过程进行简单的介绍。

  Zookeeper的消息广播过程类似 2PC（Two Phase Commit），ZAB仅需要超过一半以上的Follower返回 Ack 信息就可以执行提交，大大减小了同步阻塞，提高了可用性。

  在Zookeeper集群启动、运行过程中，如果Leader出现崩溃、网络断开、服务停止或重启等异常情况，或集群中有新服务器加入时，ZAB会让当前集群快速进入崩溃恢复模式并选举出新的Leader节点，在此期间整个集群不对外提供任何读取服务。当产生了新的Leader后并集群中过半Follower完成了与Leader的状态同步，那么ZAB协议就会让Zookeeper集群从崩溃恢复模式转换成消息广播模式。崩溃恢复的目的就是保证当前Zookeeper集群快速选举出一个新的Leader并完成与其他Follower的状态同步，以便尽快进入消息广播模式对外提供服务。
  Zookeeper崩溃恢复的主要任务就是选举Leader（Leader Election），Leader选举分两个场景：一个是Zookeeper服务器启动时Leader选举，另一个是Zookeeper集群运行过程中Leader崩溃后的Leader选举。在详细介绍Leader选举过程之前，需要先介绍几个参数：

另外在选举的过程中，每个节点的当前状态会在以下几种状态之中进行转变。

  假设现在存在一个由5个Zookeeper服务器组成的集群Sever1，Sever2，Sever3，Sever4和Sever5，集群的myid分别为：1， 2，3，4，5。依次按照myid递增的顺序进行启动。由于刚启动时zxid和epoch都为0，因此Leader选举的关键因素成了myid。

  在Zookeeper集群刚启动的时候，zxid和epoch并不参与群首选举。但是如果Zookeeper集群在运行了一段时间之后崩溃了，那么epoch和zxid在Leader选举中的重要性将大于myid。重要性的排序为：epoch zxid myid。当某一个Follower与Leader失去通信的时候，就会进入Leader选举，此时Follower会跟集群中的其他节点进行通信，但此时会存在两种情况：

  这种崩溃后的Leader选举机制也很好理解，如果Leader挂了，优先选择集群中最后做过（epoch）Leader的节点为新的Leader节点，其次选取有最新事务提交的节点（zxid）为Leader，最后才按默认的最大机器编号（myid）进行投票。

任期的概念：

个人理解：

任期的作用：

当一个 candidate 获得集群中过半服务器节点针对同一个任期的投票，它就赢得了这次选举并成为 leader 。
对于同一个任期，每个服务器节点只会投给一个 candidate ，按照先来先服务（first-come-first-served）的原则（注意：54 节在投票上增加了额外的限制）。
要求获得过半投票的规则确保了最多只有一个 candidate 赢得此次选举（图 3 中的选举安全性）。
一旦 candidate 赢得选举，就立即成为 leader 。然后它会向其他的服务器节点发送心跳消息来确定自己的地位并阻止新的选举。

在等待投票期间，candidate 可能会收到另一个声称自己是 leader 的服务器节点发来的 AppendEntries RPC 。
如果这个 leader 的任期号（包含在RPC中）不小于 candidate 当前的任期号，那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。
如果 RPC 中的任期号比自己的小，那么 candidate 就会拒绝这次的 RPC 并且继续保持 candidate 状态。

第三种可能的结果是 candidate 既没有赢得选举也没有输：如果有多个 follower 同时成为 candidate ，那么选票可能会被瓜分以至于没有 candidate 赢得过半的投票。
当这种情况发生时，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，如果没有其他机制的话，该情况可能会无限重复。

Raft 算法使用随机选举超时时间的方法来确保很少发生选票瓜分的情况，就算发生也能很快地解决。为了阻止选票一开始就被瓜分，选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时；然后该服务器赢得选举并在其他服务器超时之前发送心跳。同样的机制被用来解决选票被瓜分的情况。每个 candidate 在开始一次选举的时候会重置一个随机的选举超时时间，然后一直等待直到选举超时；这样减小了在新的选举中再次发生选票瓜分情况的可能性。93 节展示了该方案能够快速地选出一个 leader 。

个人理解：
选举其实看其实PK3个指标：term、LastLogIndex、lastLogTerm，至少要不比自己小才会vote给你，实际上这并不能保证最新的数据

因为vote RPC里面，只有lastLogIndex和Term，可能leader里面的lastLog是未提交的状态，但是其它follower的状态是提交的。所以新一任leader上任之前做的第一件事就是发一个心跳，update lastCommitIndex

follow在一定时间内未接收到leader发过来的heartbeat，超时后自己状态成为候选者，并且向其它的所有节点发起一个投票消息

一个完整的投票消息包括4个参数

receiver节点：先判断term，再判断日志是否是最新的。至少任期以及日志记录，不比自己旧，才会投票给你。所以过时的节点不会得到大多数的投票。

candidate之所以会发起选举，是因为没有收到leader的心跳，但是在选举期间又重新收到心跳会如何？
论文中描述，当重新受到leader的心跳时会判断term，至少不能比自己小，也就是说，即使是因为自己网络原因没有收到心跳而发起投票，也不会终止这次投票，因为老leader的term比现在的要小，自己是自增了一次的。
但是如果在投票等待期间，已经有新的leader产生，并且接收到leader的 appending的RPC时，candidate会放弃投票，因为term不小于当前candidate，说明这个leader不是老leader，要么和自己是同一个term的leader，要么比自己更新term的leader。
所以理论上存在某一个follower的节点因为网路延迟而发起leader申请，并且还有可能成功顶替leader的可能性，即使leader的功能正常，是这个follower自己的网络突然发生了延迟。

---