paxos实现.pdfVIP

paxos paxos ppaaxxooss 实现 本文主要介绍zookeeper 中zookeeper Server leader 的选举，zookeeper 在选举leader 的 时候采用了paxos 算法(主要是fast paxos)，这里主要介绍其中两种：LeaderElection 和 FastLeaderElection. 我们先要清楚以下几点 • 一个Server 是如何知道其它的Server 在zookeeper 中,一个zookeeper 集群有多少个Server 是固定，每个Server 用于选举的IP 和PORT 都在配置文件中 • 除了IP 和PORT 能标识一个Server 外，还有没有别的方法 每一个Server 都有一个数字编号，而且是唯一的，我们根据配置文件中的配置来对每一个 Server 进行编号，这一步在部署时需要人工去做，需要在存储数据文件的目录中创建一个文 件叫myid 的文件，并写入自己的编号,这个编号在处理我提交的value 相同很有用 • 成为Leader 的必要条件 获得n/2 + 1个Server 同意(这里意思是n/2 + 1个Server 要同意拥有zxid 是所有Server 最 大的哪个Server) • zookeeper 中选举采用UDP 还是TCP zookeeper 中选举主要是采用UDP，也一种实现是采用TCP，在这里介绍的两种实现采用的 是UDP • zookeeper 中有哪几种状态 LOOKING 初始化状态 LEADING 领导者状态 FOLLOWING 跟随者状态 • 如果所有zxid 都相同(例如: 刚初始化时),此时有可能不能形成n/2+1个Server，怎 么办 zookeeper 中每一个Server 都有一个ID,这个ID 是不重复的，而且按大小排序，如果遇到这 样的情况时，zookeeper 就推荐ID 最大的哪个Server 作为Leader • zookeeper 中Leader 怎么知道Fllower 还存活，Fllower 怎么知道Leader 还存活 Leader 定时向Fllower 发ping 消息，Fllower 定时向Leader 发ping 消息，当发现Leader 无法ping 通时，就改变自己的状态(LOOKING)，发起新的一轮选举 名词解释 zookeeer Server： zookeeper 中一个Server,以下简称Server zxid(zookeeper transtion id)： zookeeper 事务id，他是选举过程中能否成为leader 的关 键因素，它决定当前Server 要将自己这一票投给谁(也就是我在选举过程中的value,这只是 其中一个,还有id) myid/id(zookeeper server id)： zookeeper server id ，他也是能否成为leader 的一个因素 epoch/logicalclock：他主要用于描述leader 是否已经改变,每一个Server 中启动都会有一个 epoch,初始值为0,当 开始新的一次选举时epoch 加1,选举完成时 epoch 加1。 tag/sequencer：消息编号 xid：随机生成的一个数字，跟epoch 功能相同 Fast Paxos 消息流向图与Basic Paxos 的对比 消息流向图 • basic paxos 消息流向图 Client Proposer Acceptor Learner | | | | | | | X| | | | | | Request | X|-|-| | | Prepare(N)//向所有Server 提议 | |X--X--X | | Promise(N,{Va,Vb,Vc})//向提议人回复是否 接受提议(如果不接受回到上一步) | X|-|-| | | Accept!(N,Vn)//向所有人发送接受提议消息 | |X--X--X|-| Accepted(N,Vn)//向提议人回复自己已经接 受提议) |X--X Response | | | | | | | • fast paxos 消息流向图