knight_ka | 生活及学习笔记

什么是Paxos算法，zookeeper是怎么使用它的

发表于 | 分类于 | | 阅读次数
Paxos所解决的一致性问题是分布式环境中，各个节点的数据一致性，比如Zookeeper集群中，各个节点为了保持数据一致，需要把每个节点上多出来的数据同步到其它节点上。还有当zk集群中选举leader时，每个节点都投票给自己，为了保证最终节点中只存在一个leader，可以使用Paxos算法来决定。

用通俗易懂的话说一说什么是Paxos算法

Paxos是什么

百度百科对Paxos算法的简介

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX中的”La”，此人现在在微软研究院）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

可以从这段话中看出paxos的三个重要特点：

1. Paxos是基于消息传递的
2. Paxos有高容错性
3. Paxos是一种一致性算法

值得注意的是这里所说的一致性的理解可能会出现偏差。

Paxos一致性的理解
传统的一致性的理解可能会有：

* 关系型数据库的ACDI特性中的一致性。比如经典转账案例中，假如我们卡里有100元，对方卡里有100元，我们转账50元，自己账号中就要扣除50元，对方账号中就要多出50元。转账前后的总钱数是不会变的，总钱数都是200 保持一致。

Paxox所解决的一致性问题并不是这个一致性。Paxos所解决的一致性问题是分布式环境中，各个节点的数据一致性，比如Zookeeper集群中，各个节点为了保持数据一致，需要把每个节点上多出来的数据同步到其它节点上。还有当zk集群中选举leader时，每个节点都投票给自己，为了保证最终节点中只存在一个leader，可以使用Paxos算法来决定。

Paxos一致性 白话介绍

假设有5个小伙伴决定十一去旅游，a说去上海，b说去云南，c说去西藏，d说去新疆，e说去泰国。这时候5个小伙伴的意见有分歧，(Paxos的使用场景一：决定最终答案，目的地。) 一般的做法是我们5个小伙伴创建一个qq群，商量出最终的决定。

而Paxos认为：1.qq群不可靠，如果qq服务器挂了，我们就没办法进行决策了。2.商量出最终的决定可能会造成不公平的现象，Paxos用更加公平的算法最大让大家都心服口服。

因为不依赖第三方工具(qq),所以我们5个小伙伴要决定最终去哪里，就要先制定一套每个人都认同的规则，比如，根据5个小伙伴的钱数来决定，如果有人的钱连买去泰国的机票都买不起，那么就不能去泰国。然后再在5个人中选出一个人来收集大家的信息(身上有多少钱)，收集到大家的钱数之后，根据定义好的规则去判断，我们可以去哪里，比如第一轮统计决定去上海，然后把结果告诉其他4个伙伴，然后如果其中有3个伙伴(半数以上)说不同意去上海，那么就得重新开始决定，直到决定最终的目的地。

其实在paxos算法中，分为4种角色：

* Proposer ：提议者
* Acceptor：决策者
* Client：产生议题者
* Learner：最终决策学习者

5个小伙伴中的其它4个小伙伴就是Proposer提议者。

被选出来做决定的那个人就是Acceptor决策者。(其他两种角色上面例子中并不涉及)

client是Proposer的人民，Proposer收集到人民的信息，然后统一提交给决策者。

Learner学习者：是用来学习Acceptor决策者最终决定了什么结果。

Paxos的使用 之 Zookeeper

Zookeeper的选举策略就是用Paxos来实现的，默认使用的是Fast Paxos(Paxos的优化版,为了更快统计出来大家对最终决定的态度)，选举算法可以在配置zoo.cfg中进行配置。

在比如5台Zookeeper集群的选举中：

1.zk1启动，此时集群中就它一个节点，所以它提议自己做leader，还没有人同意。此时zk1 是LOOKING状态

2.zk2启动，并提议自己做Leader，zk1投票自己，zk2也投票自己，但是zk2的leader id 大于zk1的leader id，所以zk2获胜，现在zk2两票，zk1 零票。但是集群中是5台服务器，zk2的票数并没有过半。所以它也是LOOKING状态。

3.zk3 启动，此时他的id最大，所以在投票过程中获胜，zk3三票，票数过半，直接当认Leader,zk3为LEADING状态，zk1和zk2变成FOLLOW状态。

  1. zk4启动。投票自己，并与1 2 3 交换信息，但是发现集群中已经有了领导者，尽管它的id大，但是它只能当小弟了。
  2. zk5启动。投票自己，并与1 2 3 4交换信息，发现有领导者，认作小弟。

本次选举过程中，zk3就是Acceptor决策者，每加入一个zk，这个zk发起投票，它就是Proposer提议者和CLient产生议题者。他们选举的规则很简单，就是1.根据leader id来决定谁是leader 2.如果集群中已经有了leader，并且leader状态正常，则不重新决策。

然后当集群中Leader宕机了，或者它的Follow有一半以上宕机了，此时就要重新发起选举，因为此时其它节点中可能有一些数据还没有同步，所以此时的选举规则就比较麻烦。但是它还是利用的Paxos的决策者，提议者，产生议题者的计算思想。

  1. zk3宕机，此时集群中其它节点发现检测不到leader的状态了，则他们就提议要重新选举了。

  2. zk1 zk2 zk4 zk5每个节点都发出自己的自己的状态信息到其它节点。数据id,Leader id,逻辑时钟。

  3. 4个节点各自接收到其它三个节点的信息，并和自己本机现在的状态进行对比1.逻辑时钟是不是一致，如果不一致，逻辑时钟最大的那个节点获胜。2.如果逻辑时钟一致，取出数据id(ZXID也就是事务id)，如果事务id不一致，则取出事务id大的那个节点获胜。3.如果事务id也一致，那么根据leader id判断，leader id大的那个获胜。最终每个节点都重新发出一份自己的投票结果。

    4.如果本次的投票结果有半数以上都是一样的结果，那么选举结束，开始数据同步工作。如果没有半数以上的投票结果，则继续第三步。直到选举成功为止。

选举的标准：

1、逻辑时钟小的选举结果被忽略，重新投票

2、统一逻辑时钟后，数据id大的胜出

3、数据id相同的情况下，leader id大的胜出

根据这个规则选出leader。

ZK集群的特点
Zookeeper虽然在配置文件中并没有指定master和slave

但是，zookeeper工作时，是有一个节点为leader，其他则为follower

Leader是通过内部的选举机制临时产生的