拜占庭帝国问题

拜占庭帝国(Byzantine Empire)军队的几个师驻扎在敌城外，每个师都由各自的将军指挥。将军们只能通过信使相互沟通。在观察敌情之后，他们必须制定一个共同的行动计划，如进攻(Attack)或者撤退(Retreat)，且只有当半数以上的将军共同发起进攻时才能取得胜利。然而，其中一些将军可能是叛徒，试图阻止忠诚的将军达成一致的行动计划。更糟糕的是，负责消息传递的信使也可能是叛徒，他们可能篡改或伪造消息，也可能使得消息丢失。
细节请看：https://zhuanlan.zhihu.com/p/107439021

paxos算法

算法简介

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。
Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。
自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。
然而，Paxos的最大特点就是难，不仅难以理解，更难以实现。Paxos算法：一种基于消息传递且具有高度容错特性的一致性算法。
Paxos算法解决的问题：就是如何快速正确的在一个分布式系统中对某个数据值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

算法描述

在一个Paxos系统中，首先将所有节点划分为Proposer（提议者），Acceptor（接受者），和Learner（学习者）。（注意：每个节点都可以身兼数职）。
一个完整的Paxos算法流程分为三个阶段：
1、Prepare准备阶段
• Proposer向多个Acceptor发出Propose请求Promise（承诺）
• Acceptor针对收到的Propose请求进行Promise（承诺）
2、Accept接受阶段
• Proposer收到多数Acceptor承诺的Promise后，向Acceptor发出Propose请求
• Acceptor针对收到的Propose请求进行Accept处理
3、Learn学习阶段
• Proposer将形成的决议发送给所有Learners

算法流程

（1）Prepare准备阶段：Proposer生成全局唯一且递增的Proposal ID，向所有Acceptor发送Propose请求，这里无需携带提案内容，只携带Proposal ID即可。
（2）Promise：Acceptor收到Propose请求后，做出“两个承诺，一个应答”。
承诺1：不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Propose请求。
承诺2：不再接受Proposal ID小于（注意：这里是< ）当前请求的Accept请求。
应答：不违背以前做出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。
（3）Propose：Proposer收到多数Acceptor的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptor发送Propose请求。
（4）Accept: Acceptor收到Propose请求后，在不违背自己之前做出的承诺下，接受并持久化当前Proposal ID和提案Value。
（5）Learn: Proposer收到多数Acceptor的Accept后，决议形成，将形成的决议发送给所有Learner。

算法推演

下面我们针对上述描述做三种情况的推演举例：为了简化流程，我们这里不设置 Learner。

情况1：

有A1， A2， A3， A4， A5 5位议员，就税率问题进行决议。

A1发起1号Proposal的Propose，等待Promise承诺;
A2-A5回应Promise;
A1在收到两份回复时就会发起税率10%的Proposal;
A2-A5回应Accept;
通过Proposal，税率10%。

情况2：
现在我们假设在A1提出提案的同时，A5决定将税率定为20%
A1， A5同时发起Propose (序号分别为1， 2)
A2承诺A1， A4承诺A5， A3行为成为关键
情况1: A3先收到A1消息，承诺A1。
A1发起Proposal (1， 10%) ， A2， A3接受。
之后A3又收到A5消息，回复A1:(1， 10%) ，并承诺A5。
A5发起Proposal (2， 20%) ， A3， A4接受。之后A1， A5同时广播决议。

Paxos 算法缺陷：在网络复杂的情况下，一个应用 Paxos 算法的分布式系统，可能很久无法收敛，甚至陷入活锁的情况。

情况3：

现在我们假设在A1提出提案的同时，A5决定将税率定为20%

A1， A5同时发起Propose (序号分别为1， 2)
A2承诺A1， A4承诺A5， A3行为成为关键
情况2: A3先收到A1消息，承诺A1。之后立刻收到A5消息，承诺A5。
A1发起Proposal (1， 10%) ，无足够响应。A1重新Propose (序号3)，A3再次承诺A1。
A5发起Proposal (2， 20%) ，无足够相应。A5重新Propose (序号4)，A3再次承诺A5。
……

算法分析
造成这种情况的原因是系统中有一个以上的 Proposer，多个 Proposers 相互争夺 Acceptor，造成迟迟无法达成一致的情况。针对这种情况，一种改进的 Paxos 算法被提出：从系统中选出一个节点作为 Leader，只有 Leader 能够发起提案。这样，一次 Paxos 流程中只有一个Proposer，不会出现活锁的情况，此时只会出现例子中第一种情况

ZAB协议
Zab协议的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播），通过 Zab 协议来保证分布式事务的最终一致性。
Zab 是特别为 Zookeeper 设计的支持崩溃恢复的原子广播协议，在 Zookeeper 中主要依赖 Zab 协议实现数据一致性，基于该协议，Zookeeper 实现了一种主备模型（Leader 与 Follower）的系统架构保证集群中各个副本之间的数据一致性。

Zab 协议核心
在 Zookeeper 中只有一个 Leader，并且只有 Leader 可以处理外部客户端的事务请求，并将其转换成一个事务 Proposal（写操作），然后 Leader 服务器再将事务 Proposal 操作的数据同步到所有 Follower（数据广播/数据复制）。
Zookeeper 采用 Zab 协议的核心就是只要有一台服务器提交了 Proposal，就要确保所有服务器最终都能正确提交 Proposal，这也是 CAP/BASE 最终实现一致性的体现。

Zab 模式
Zab 协议有两种模式：一种是消息广播模式，另一种是崩溃恢复模式。

消息广播模式
在 Zookeeper 集群中数据副本的传递策略就是采用消息广播模式，Zookeeper 中的数据副本同步方式与2PC方式相似但却不同，2PC是要求协调者必须等待所有参与者全部反馈ACK确认消息后，再发送 commit 消息，要求所有参与者要么全成功要么全失败，2PC方式会产生严重的阻塞问题。
而 Zookeeper 中 Leader 等待 Follower 的 ACK 反馈是指：只要半数以上的 Follower 成功反馈即可，不需要收到全部的 Follower 反馈。

Zookeeper 中广播消息步骤：
客户端发起一个写操作请求
Leader 服务器处理客户端请求后将请求转换为 Proposal，同时为每个 Proposal 分配一个全局唯一 ID，即 ZXID
Leader 服务器与每个 Follower 之间都有一个队列，Leader 将消息发送到该队列
Follower 接收到proposal之后会与自己本地已经保存的最大zxid进行比较，如果当前的zxid较大，则把proposal保存到本地日志事务中，向 Leader 服务器发送 ACK 确认
Leader 服务器收到半数以上的 Follower 的 ACK 后，即认为可以发送 Commit
Leader 向所有的 Follower 服务器发送 Commit 消息
崩溃恢复模式
一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式。
Zookeeper 集群中为保证任何进程能够顺序执行，只能是 Leader 服务器接收写请求，其他服务器接收到客户端的写请求，也会转发至 Leader 服务器进行处理。
Zab 协议崩溃恢复需满足以下2个要求：
已处理的消息不能丢：如果有的follower还没收到commit消息的时候leader挂了，那么就会导致该事务有的server执行了有的没有。当新的leader被选出，经过恢复模式后，就需要保证集群中所有server执行了之前部分server执行的事务。
被丢的消息不能再现：当一个事务被通过，leader已经更新到本地了，但是还没向follower发送commit之前挂了。这台机器再次成为follower的时候，本地上就会比其他机器多一个事务，是不行的。因此，类似这样的事务是应该被丢弃的。而这种情况，服务端也不会向客户端返回成功的消息。
Leader 选举算法
可以通过配置项设置 Zookeeper 选举 Leader 的算法，可选项有：

0：基于UDP的 LeaderElection
1：基于UDP的 FastLeaderElection
2：基于UDP和认证的 FastLeaderElection
3：基于TCP的FastLeaderElection

在 3.4.10 版本中，默认值为3，另外三种算法已被弃用。下面重点介绍基于TCP的FastLeaderElection

FastLeaderElection 原理

三个数据

zxid：64位长度，高位32位是epoch，低32为xid
epoch：每个leader都有一个新的epoch，可以认为是年代
xid：流水号。

每个 Zookeeper 服务器，都需要在数据文件夹下创建一个名为 myid 的文件，该文件包含整个 Zookeeper 集群唯一的 ID，例如，某个 Zookeeper 集群包含三台服务器，hostname 分别为 zoo1，zoo2，zoo3，其中 myid 分别为1，2，3，则在配置文件中其 ID 与 hostname 必须一一对应，如在配置文件中，server.后面的数据即为 myid

server.1=zoo1:2888:3888 
server.2=zoo2:2888:3888 
server.3=zoo3:2888:3888

类似于 RDBMS 中的事务ID，用于标识一个 Proposal ID，为了保证顺序性，ZXID 必须单调递增，因此 Zookeeper 使用一个 64 位的数来表示，高 32 位是 Leader 的 epoch，从 1 开始，每次选出新的 Leader，epoch 加 1，低 32 位为该 epoch 内的序号，每次 epoch 变化，都将低 32 位的序号重置，这样保证了 ZXID 的全局递增性。

四个状态

Looking：不确定Leader状态，该状态下的服务器认为当前集群中没有Leader，会发起Leader选举
Following：跟随者状态，表明当前服务器角色是Follower，并且它知道Leader是谁
Leading：领导者状态，表明当前服务器角色是Leader，它会维护与Follower间的心跳
Observing：观察者状态，表明当前服务器角色是Observer，与Follower唯一的不同在于不参与选举，也不参与集群写操作时的投票
选举步骤
大致步骤如下：
①epoch大的直接胜出
②epoch相同，zxid大的胜出
③zxid相同，myid大的胜出
选票数据结构
每个服务器在进行领导选举时，会发送如下关键信息：

logicClock 每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票，可以理解为epoch值
state 当前服务器的状态
self_id 当前服务器的myid
self_zxid 当前服务器上所保存的数据的最大zxid
vote_id 被推举的服务器的myid
vote_zxid 被推举的服务器上所保存的数据的最大zxid

1、自增选举轮次
Zookeeper 规定所有有效的投票都必须在同一轮次中，每个服务器在开始新一轮投票时，会先对自己维护的 logicClock 进行自增操作。
2、初始化选票：
每个服务器在广播自己的选票前会将自己的投票箱清空，该投票箱记录了所收到的选票。
3、发送初始化选票
每个服务器最开始都是通过广播把票投给自己
4、接收外部投票
服务器会尝试从其他服务器获取投票，并计入自己的投票箱内，如果无法获取任何外部投票，则会确认自己是否与集群中其他服务器保持着有效连接，如果是，则发送自己的投票，如果否，则马上与之建立连接。
5、判断选举轮次
收到外部投票后，首先会根据投票信息中所包含的 logicClock 来进行不同处理：

外部投票的 logicClock 大于自己的 logicClock，说明该服务器的选举轮次落后于其他服务器轮次，立即清空自己的投票箱并将自己的 logicClock 更新为收到的 logicClock，然后再对自己之前的投票与收到的投票以确定是否需要变更自己的投票，最终再次将自己的投票广播出去。
外部投票的logicClock小于自己的logicClock。当前服务器直接忽略该投票，继续处理下一个投票
外部投票的logickClock与自己的相等，当时进行选票PK

6、选票PK（核心步骤）
基于(self_id， self_zxid)与(vote_id， vote_zxid)的对比：

epoch大的直接胜出

外部投票的logicClock大于自己的logicClock，则将自己的logicClock及自己的选票的logicClock变更为收到的logicClock

epoch相同，zxid大的胜出

若logicClock一致，则对比二者的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_myid更新为收到的票中的vote_zxid与vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self_myid， self_zxid)相同的选票，则直接覆盖

zxid相同，myid大的胜出

若二者vote_zxid一致，则比较二者的vote_myid，若外部投票的vote_myid比较大，则将自己的票中的vote_myid更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱
6、统计选票
如果已经确定有过半服务器认可了自己的投票（可能是更新后的投票），则终止投票。否则继续接收其它服务器的投票。
7、更新服务器状态
投票终止后，服务器开始更新自身状态。若过半的票投给了自己，则将自己的服务器状态更新为LEADING，否则将自己的状态更新为FOLLOWING。
参考文章：
https://zhuanlan.zhihu.com/p/31780743
https://blog.csdn.net/weixin_44966780/article/details/121767321
https://juejin.cn/post/7001070049200963621

数据结构与算法

分布式算法-paxos算法

拜占庭帝国问题

paxos算法

算法简介

算法描述

算法流程

算法推演

情况1：

情况2：

情况3：

算法分析

ZAB协议

Zab 协议核心

Zab 模式

消息广播模式

Zookeeper 中广播消息步骤：

崩溃恢复模式

Leader 选举算法

FastLeaderElection 原理

三个数据

四个状态

选举步骤

选票数据结构