分布式算法分析：

Paxos 帕克西斯算法

有3个角色：
proposer: 提案方
acceptor: 投票方
learner: 记录方

2种实现算法：

basic-paxos

  1. 选举提案发起方
  2. 提案方发起广播到所有投票方(投票方只认可最新提案),
  3. 投票方投票，将结果告知提案方
  4. 提案方 根据投票结果裁决：
    a. 投票过半，议案通过，广播获得所有投票方认可后，由记录方纪录议案结果
    b. 投票未通过，隔一个随机时间，更新提案编号，重新发起投票，继续上面流程第二步开始

Note：
每次发起投票，都要选举一个提案方，效率低下
实际上提案方不会经常挂掉不需要每次选举，从而优化版本为 multi-paxos

multi-paxos
解决每次投票都要重新选举提案方的性能问题
选举一个proposer为Leader，每次由Leader发起投票
如果Leader挂了 重新发起选举Leader
Leader只有一个
目前基本上paxos都是使用multi-paxos算法

具体提案操作流程类似basic-paxos，只是去掉了第一步选举提案方改由leader发起投票
一旦Leader挂了，重新选举新的Leader

Raft算法 实现案例：redis etcd等

Raft算法 是 multi-paxos算法的简化模型 paxos算法太复杂

区别：
Raft中追加日志的操作必须是连续的 （multi-paxos是并行的）
Raft中只有拥有最新，最全日志的节点 才能当选Leader，只有该节点追加日志（区别multi-paxos都可以写日志）

具体运作流程同multi-paxos

概念不大一样：
Leader ： 领导者 作用同：提案方和记录方 双重角色
Follower：跟随者 作用同 投票方，进行投票供Leader裁决
Candidate 候选者 只有选举Leader过程中的临时角色

Zab协议 实现案例：zk

https://cloud.tencent.com/developer/article/1585594

Zookeeper Atomic Broadcast （Zookeeper原子广播）,支持崩溃恢复的广播协议

基本原理：

Leader向其他节点广播消息
Leader的选举：集群启动时（FastLeaderElection快速选举法），Leader崩溃，Leader和一半节点断连以后
Leader重新选举后，需要和其他节点进行数据同步

角色：
Leader —主节点 可以给客户端提供读写功能
Follower —从节点 提供读功能 参与选举
Observer —观察节点 提供读功能 不参与选举，不计入过半策略 提升集群读性能

事务ID设计概念
zxid 是一个64位数字 低32位是 单调递增计数器 高32位为Leader周期epoch编号
每次选举重新选出Leader 从当前Leader中取出最大的zxid
然后高32位epoch自增一次(加一操作)，低32位位置0

（epoch编号类似于 不同Leader时代的 年号一样），保证旧的Leader即使恢复了也不会再发命令了。

ZAB 协议主要用于构建一个高可用的分布式数椐主备系统，例如ZooKeeper,

Paxos算法 则是用于构建一个分布式的一致性状态机系统，保持分布式状态同步。

ZK如何保证强一致性CP
1.在选主期间整个集群不可用
2.在选主后的数据同步完成之前整个集群不可用
3.每次写请求,保证大于半数的节点写成功(一致性保证)

所以ZK不是很适合做注册中心，注册中心需要可以容忍短暂的数据不一致，例如服务列表，但是要保证高可用。

ZK的缺点：

  1. 复杂，
  2. 选主过程时间长，选举期间集群功能不可用
  3. 无法跨机房，只有一个master节点，不能保证高可用
  4. 集群伸缩性不够灵活，集群变更加新机器，要更新所有zoo.cfg的配置，然后逐台重启

主从结构问题：

  1. 客户端派发任务操作都要从主节点绕一圈确认通知客户端
  2. 主节点崩溃 无法分派任务
  3. 从节点崩溃 已分配任务无法完成
  4. 通信故障 如果从节点跟主节点失联了，无法接受新任务分配

ZK的脑裂：
因为一些特殊原因,例如主节点负载很高,导致消息任意延迟,然后备份节点接管主节点的工作,成为第二个主要主节点
如果一些从节点无法与主节点通信,如由于网络分区错误导致,这些从节点可能会停止与主要主节点通信,而与第二个主要主节点接力主从关系
即: 系统中两个或者多个部分开始独立工作,导致整体行为不一致性

使用ZK实现分布式锁（分布式独享锁和共享锁）存在的问题：

独享锁： watch机制 + 临时节点特性
共享锁： watch机制 + 临时节点顺序性

羊群效应：
当集群中机器规模较大时，例如超过10，每次只有一个节点能获得锁，但是watch机制会向机器中所有10台机器发通知
对ZK服务器造成资源浪费，性能受影响和经受网络冲击，容易扛不住。

改进方案：只对比自己机器序号小的ZK节点进行监听。

分布式系统数据的复制方式：

  1. 主从复制 写操作都在主服务上，主更新到从，从节点只能分担读压力
  2. 对等复制 副本之间不区分主从 副本之间可能存在数据冲突需要解决

Eureka使用对等复制策略，数据冲突的时候通过 lastDirtyTimestamp 来认定最新数据。