共识问题

共识：一致同意，完整（只决定一次），有效，终止（宕机不回来）。要多数都同意，很慢。
paxos 完全符合，单 raft,zap 考虑的是宕机还会回来的情况，用日志保证。能解决诸如以下问题：

全序广播相当于重复多伦共识：但 raft 和 zap 等直接实现全序广播内有一次一值的共识。单领导者选取：1 选出一位领导者，2 对领导者的提议进行表决（防止 1，一个节点相信自己是领导）投票是同步的，动态成员扩展难，依靠超时检测节点失效，若只有一条特定网络不可靠，会进入领导频繁二人转局面

共识算法

raft

数据一致性是通过日志复制的方式，client 发给 leader(写只发给 leader，follower 备份恢复用),leader 写入日志，同步给 follower，当多数 follower 写入日志并返回给 leader 时，leader 提交数据，返回给客户端确认消息, 发给 follower 数据已提交，follower 提交数据，发回确认给 leader。所有的发送都随着调频发过去。raft 中所有 server 之间的通信都是 RPC 调用，并且只有两种类型的 RPC 调用：第一种是 RequestVote，用于选举 leader；第二种是 AppendEntries。日志和投票结果都需要持续化写在磁盘中，保证宕机后重启任然正常。

leader(有任期字段 term)，candidate, follower. 每个节点有在 T 到 2T 之间随机选择超时时间。leader 和 follower 通过跳频联系。当一个 follower 收不到 leader 的跳频超时时将发起投自己的票。任何一个 follower 只能投一票。当一轮投票结束有多个候选者时，这几个候选者重新分配随机的超时时间。

当确认提交后，leader 会一直不断地重试提交的 rpc 给 follower、重试，直到请求成功；即使 follower 宕机了，重启后 leader 仍会接着发请求，直到请求成功，当 leader 宕机，如何向 follower 继续发；1.leader 的日志只能增加，=》所以在选择时选 term 大,log 长的 2.leader 会把自己的 log 复制到其他机器，如果新达到多数并且此任期已有数据过半（挂前的一次数据不会被重复提交）就提交，只提交新任期的，同步还是要同步。
为了恢复 log 一致性，leader 为集群中所有 follower 都保存一个状态变量，即 nextIndex：1）nextIndex 是 leader 准备向某个 follower 发送的下一个 log entry 的 index；2）当 leader 刚刚即位后，nextIndex 的初始值是（1+leader’s last index）；
当 leader 看到请求被拒绝时，其动作非常简单：只需将 nextIndex-1，再次尝试。

term 需要存盘
任意一个 server 在一个 term 内只能投出一票；一旦已经投给了一个 candidate，它必须拒绝其他 candidate 的投票请求；其实 server 根本不在意把票投给谁，它只会把票投给最先到请求到它的 candidate；为了保证这一点，必须把投票信息持久保存到磁盘上，这样可以保证即使该 server 投完票后宕机，稍后又立即重启了，也不会在同一个 term 内给第二个 candidate 投票了。
每个日志 entry：iterm+index. 每次发送 AppendEntries 时需要带上一次的，检查是否一样，一样才接受来保证所有机器 log 一致，

paxos

• basic paxos
  
  这里有个错误。第二阶段若 N >=ResN, 接受提案，若 N <ResN 不接受。实际上这里的 proposal 是 leader。共识算法正常是 proposor,leader,accepter,leaner（先忽略），用来决议 proposer 的提议号和是否成功的。每次 proposal 先到 leader(可随机选取，不重要)，leader 发给 accepter 若没有冲突返回 any 否则返回已选的，继续上述过程。
  问题：多个 Proposal 可能出现死锁一直循环递增 N 的情况：

  上面这个是 https://www.microsoft.com/en-…
  为了方便理解，去除了实现细节。实时上再应用中，客户端不会自己处理冲突 + 1 再次投票和发送给其他 leaner，这些应该由另一个角色，在 basic 中，由一群 c 协调者，可以和 acceptor 一样，或者是其中的部分构成，每轮随机一个 c 作为 leader，负责收集本轮结果和通知 leaner。proposal->leader(每个 client 随机发就可以作为本轮 leader)->pre->acceptors 返回最大 N 的值 V -> 带 N 请求 ->acceptors->leader-> 返回给 proposal->client 失败或者成功或再次投票 -> 投票成功后发给 leaner。此过程中 CLIENT2 再次发送是另一个 leader。

• fast paxos
  若 proposal 和 acceptor,leader,leaner 都是分布式，且要持久化，持久化 + 发送来回的代价就多了，
  若 leader 发现没有冲突，不再参与，proposal 直接提交给 acceptor（同一轮只投给先到的），直接发送给 leaner，可以理解为基于乐观锁的思想，leaner 和 CLIENT 都自行决议，
  若 proposal 没有决策成功（先到的就是投票，没有半数以上的），1. 重新引入 leader，异步发送给协调者，协调者选择（因为 acceptor 只投一次）, 发给 proposal 结果。（再次引入 leader）2. 无 leader，在 acceptor 决议后发送给所有 acceptor，其他 acceptor 收到此消息后对 i + 1 轮的可以比较投票（即使同时刻一个一半也可以再比较投一次）。
  https://www.microsoft.com/en-…
• muti-paxos
  当 leader 稳定，可以省去 prepare 阶段
  具体做法如下：

① 当某个副本节点通过选举成为 Master 后，就会使用新分配的编号 N 来广播一个 Prepare 消息，该 Prepare 消息会被所有未达成一致的 Instance 和目前还未开始的 Instance 共用。

② 当 Acceptor 接收到 Prepare 消息后，必须对多个 Instance 同时做出回应，这通常可以通过将反馈信息封装在一个数据包中来实现，假设最多允许 K 个 Instance 同时进行提议值的选定，那么：

- 当前之多存在 K 个未达成一致的 Instance，将这些未决的 Instance 各自最后接受的提议值封装进一个数据包，并作为 Promise 消息返回。

- 同时，判断 N 是否大于当前 Acceptor 的 highestPromisedNum 值（当前已经接受的最大的提议编号值），如果大于，那么就标记这些未决 Instance 和所有未来的 Instance 的 highestPromisedNum 的值为 N，这样，这些未决 Instance 和所有未来 Instance 都不能再接受任何编号小于 N 的提议。

③ Master 对所有未决 Instance 和所有未来 Instance 分别执行 Propose->Accept 阶段的处理，如果 Master 能够一直稳定运行的话，那么在接下来的算法运行过程中，就不再需要进行 Prepare->Promise 处理了。但是，一旦 Master 发现 Acceptor 返回了一个 Reject 消息，说明集群中存在另一个 Master 并且试图使用更大的提议编号发送了 Prepare 消息，此时，当前 Master 就需要重新分配新的提议编号并再次进行 Prepare->Promise 阶段的处理。

可见 chubby 就是一个典型的 Muti-Paxos 算法应用，在 Master 稳定运行的情况下，只需要使用同一个编号来依次执行每一个 Instance 的 Promise->Accept 阶段处理。

raft 和 paxos 区别

raft 要有一个 leader。在 选主时每个 follower 只能投一次，不成功随机时间下一次。有主时的共识由主来给日志编号，比较就好。follower 保证稳定可替换即可。
paxos leader 不能那么重要（fast paxos 在无冲突时甚至无 leader 参与），每次可以随机选，只是汇总投票，prososol 是否通过由多数决定，prososol 回复客户端和同步其他 leaner。算是无主的模型。
zap 还是有 leader 的。zap 在无主的时候选举算法和 fast paxos 很像，有最大 xid（类似 pre 阶段，只不过是上次存好的），每次投票直接给 acceptor 并且无协调者的冲突处理。在有主时，用 paxos 的思想先 pre 收集并同步信息保证一致，主处理写，多数处理成功后回复。

优势就是单主能不能抗住了。

zookeeper

Zookeeper 对于每个节点 QuorumPeer 的设计相当的灵活，QuorumPeer 主要包括四个组件：客户端请求接收器(ServerCnxnFactory)、数据引擎(ZKDatabase)、选举器(Election)、核心功能组件（Leader/Follower/Observer 不同）

采用了递增的事务 id 号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了 zxid。实现中 zxid 是一个 64 位的数字，它高 32 位是 epoch 用来标识 leader 关系是否改变，每次一个 leader 被选出来，它都会有一个新的 epoch，标识当前属于那个 leader 的统治时期。低 32 位用于递增计数。

本身的数据组织以文件形式。

作用

1. 单独 zk 集群元数据的可靠性和一致性保证，元数据保存在 zk 所有副本中（少量完全可以放在内存中数据）
路由，选择数据库，调度程序
2. 单独 zk 集群，锁，防护令牌，获取锁或者 zxid
3. 变更通知，每个变更都会发送到所有节点
watch 机制
4. 用于检测，服务发现
session:
每个 ZooKeeper 客户端的配置中都包括集合体中服务器的列表。在启动时，客户端会尝试连接到列表中的一台服务器。如果连接失败，它会尝试连接另一台服务器，以此类推，直到成功与一台服务器建立连接或因为所有 ZooKeeper 服务器都不可用而失败。
只要一个会话空闲超过一定时间，都可以通过客户端发送 ping 请求（也称为心跳）保持会话不过期。ping 请求由 ZooKeeper 的客户端库自动发送，因此在我们的代码中不需要考虑如何维护会话。这个时间长度的设置应当足够低，以便能档检测出服务器故障（由读超时体现），并且能够在会话超时的时间段内重新莲接到另外一台服务器。

zookeeper 数据同步过程：

• zab protocol

  Leader election
      leader 选举过程，electionEpoch 自增，在选举的时候 lastProcessedZxid 越大，越有可能成为 leader
  Discovery：第一：leader 收集 follower 的 lastProcessedZxid，这个主要用来通过和 leader 的 lastProcessedZxid 对比来确认 follower 需要同步的数据范围
      第二：选举出一个新的 peerEpoch，主要用于防止旧的 leader 来进行提交操作（旧 leader 向 follower 发送命令的时候，follower 发现 zxid 所在的 peerEpoch 比现在的小，则直接拒绝，防止出现不一致性）Synchronization：follower 中的事务日志和 leader 保持一致的过程，就是依据 follower 和 leader 之间的 lastProcessedZxid 进行，follower 多的话则删除掉多余部分，follower 少的话则补充，一旦对应不上则 follower 删除掉对不上的 zxid 及其之后的部分然后再从 leader 同步该部分之后的数据
  Broadcast
      正常处理客户端请求的过程。leader 针对客户端的事务请求，然后提出一个议案，发给所有的 follower，一旦过半的 follower 回复 OK 的话，leader 就可以将该议案进行提交了，向所有 follower 发送提交该议案的请求，leader 同时返回 OK 响应给客户端

实际上 zookeeper 中算法三阶段：FSE=>Recovery=>Broadcast(广播和上面的一致)

• fast leader election
  基于 fast paxos。发送给所有的节点。没有随机 leader 参与收集。
  

  LOOKING：进入 leader 选举状态
  FOLLOWING：leader 选举结束，进入 follower 状态
  LEADING：leader 选举结束，进入 leader 状态
  OBSERVING：处于观察者状态
  1.serverA 首先将 electionEpoch 自增，然后为自己投票
  2 serverB 接收到上述通知，然后进行投票 PK
  如果 serverB 收到的通知中的 electionEpoch 比自己的大，则 serverB 更新自己的 electionEpoch 为 serverA 的 electionEpoch
  如果该 serverB 收到的通知中的 electionEpoch 比自己的小，则 serverB 向 serverA 发送一个通知，将 serverB 自己的投票以及 electionEpoch 发送给 serverA，serverA 收到后就会更新自己的 electionEpoch
  在 electionEpoch 达成一致后，就开始进行投票之间的 pk，优先比较 proposedEpoch，然后优先比较 proposedZxid，最后优先比较 proposedLeader
  pk 完毕后，如果本机器投票被 pk 掉，则更新投票信息为对方投票信息，同时重新发送该投票信息给所有的 server。如果本机器投票没有被 pk 掉，如果是 looking，过半更改状态, 如果 FOLLOWING/LEADING 说明落后，加速收敛

• Recovery
  略：https://my.oschina.net/pingpa…

follower 读写过程图：

ectd