Zookeeper -- 选主过程

蜻蜓点水提下CAP和paxos.

CAP

C:一致性 A：可用性 P:分区容忍

为什么说cap是不能同时满足的？我们假设不满足P，即任何情况下，系统内的节点均不会挂，节点之间通信都不会中断。那么对于任意一个用户读写：
1.我们只需要用一个节点保存数据，这就确保了一致性。
2.由于只有一个节点存储数据，我们只需将请求重定向到这个节点，就可以快速返回，这确保了高可用性。

但真实情况是P是我们必须要考虑的(系统内一个节点挂掉，整个系统就不能工作，这不是我们愿意看到的)，那么为了确保分区容忍性，我们需要对数据进行多备，这样少数节点分区了也可以使系统正常工作。我们提高分区容忍性，会带来一致性和可用性的冲突:

• 越高的分区容忍性，要求更多的从节点。 我们如果需要保证强一致性，对于每个用户读写，我们需要将请求广播到对应HA的全部节点，等待所有请求成功返回了再返回给用户，这势必延长响应时间，影响高可用性。

所以在真实的工程环境，我们需要根据具体的场景，在三者中找到平衡。zk在节点数量大于(n+1)/2的情况下都可以工作，分区容忍性很高。对于读操作，直接返回当前节点的数据库情况，不保证强一致性。

PAXOS

paxos的证明困难，但是只是理解他的做法还是比较简单的。

paxos有以下几个步骤:

1.预提案:所有Proposer向Acceptor广播预值，Acceptor会返回当前自身收到的最大的预值并返回，当Proposer接收到过半的回复，自身即进入下个步骤。

2.提案:Acceptor将回复中的最大预值所有者的value广播给Acceptor，Acceptor批复第一个value，并且不再变更。

3.Observer对结果进行统计并公布最终结果。

Zookeeper选主过程

在zk的工程应用中,每轮选主看成一次提案，这个value实际就是leader的id。预值由，epoch，zxid以及节点自身的myid组成。当然，为了让节点的使用效率更高，Zk中的节点同时是Proposer和Acceptor(Observer除外)。

参与选主的节点(下文提及的节点均不包括观察者)状态有以下几种

   LOOKING, FOLLOWING, LEADING

其中，LOOKING是不稳定状态，进入这个状态则开始leader的选举。我们分为两种情况讨论:1.一个失联的node加入stable的集群中；2.一个unstable的集群选举出leader。

第一种情况比较简单

由于stable集群中的节点对自身的视图必定是经过过半节点认可的，所以任意一个节点的视图数据必定是某个epoch的真实情况。所以只要直接向集群,发送广播，接受到一个状态为follower\leader状态的节点，可以直接从消息内容中拿到leader的id。自身变成follower，向这个leader同步数据即可。

对于第二种情况

步骤1

当节点启动时，会向集群中广播（包括自己），投自身一票，当获取到回复时，将这个选票放入投票器中（SyncedLearnerTracker）,同时将回复的投票信息与自身做对比，如果回复的投票预值更大(FastLeaderElection#totalOrderPredicate)，则将自身的选票改成对方的，重新广播（FastLeaderElection#sendNotifications）。
当投票器中的过半的数据投给了同一个节点(SyncedLearnerTracker#hasAllQuorums , 细节:每次只需判断当前收到的选票是否得到大部分认可就可以了，不需要遍历一次)。那么预提案完成。

步骤2

zookeeper用了一个很巧妙的方法实现提案第二阶段。因为最大的选票已经出来了，如果接下来一段时间(200ms)，都没有收到新的反对意见，那么选主完成，各个节点均可以确认自己在集群中的位置了。如果有新的预值更大的投票(通常也就是新加入了一个myid更大的节点)，那么回到第一步重来。

步骤3

Observer的角色由leader兼职，当leader认为自己是leader了，调用Leader#lead开始领导工作:
1.开启端口等待follower的连接（LearnerCnxAcceptor#run）;
2.当过半的follower连接成功，那么说明自己得到了认可，将纪元+1;
3.开始同步数据,保持心跳

TODO

1. 为什么有两个投票器