paxos协议

协议解决的问题

paxos解决了分布式系统就某一个值达成一致的问题。下面就分布式系统中选主来介绍paxos协议过程，协议详细过程见https://en.wikipedia.org/wiki/Paxos_(computer_science)

协议过程

在分布式系统中选主最直接的方法是直接选定集群的一个节点为leader，其它的节点为follower，这样引入的一个问题是如果leader节点挂掉，整个集群就挂掉了。需要有一种算法自动选主，如果leader节点挂掉，则从follower节点中选出一个主节点。协议分为这几个角色：

• Proposer： 决议提出者
• Acceptor：决议接收者
• Learner：对结果进行学习

集群中的一个节点可以同时扮演多个角色，协议分为两阶段：

• 一阶段
  一阶段分为两个步骤：Prepare和Promise，如下图所示

paxos第一阶段.jpg

（1）1a:Prepare
Proposer向所有Acceptor提出Prepare请求，prepare请求包含一个全局唯一递增的序号N1，全局唯一是指每次每个Proposer发起的序号都不一样，递增是指每个Proposer发起的序列号是递增的。
（2）1b:Promise
Acceptor收到Proposer的Prepare请求时，先和Acceptor的maxNum（此Acceptor收到的最大序号）进行比较，如果maxNum > N1，则抛弃此Proposer的请求；maxNum < N1，设置maxNum的值为N1，且maxNum = N1，回复此Acceptor接受的最大编号N及其对应的值V

• 二阶段
  二阶段也分为两个步骤：Accept Request和Accepted，如下图所示
  paxos第二阶段.jpg
  （3）2a:Accept Request
  Proposer收到超过半数的Acceptor的Promise时，会从Promise中选出返回编号最大的N对应的值V1，发送给Acceptor；此时如果N1小于maxNum，抛弃请求；N1大于maxNum，更新此Acceptor接受的最大编号N
  （4）2b:Accepted
  Acceptor对满足2a阶段的请求，返回Accepted给Proposer，Proposer收到超过半数的回复，发送选主信息给Leaner