共识问题

共识：一致同意，完整（只决定一次），有效，终止（宕机不回来）。要多数都同意，很慢。

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