PAXOS算法的理论实现
攻城狮小明
今天我们就接着上节课，继续学习PAXOS算法，小白你要认证听哦。
程序猿小白
嗯，我会的。
Paxos的两个原则
安全原则
保证不能做错的事
1. 只能有一个值被批准，不能出现第二个值把第一个覆盖的情况
2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值
存活原则
只要有多数服务器存活并且彼此间可以通信最终都要做到的事
1. 最终会批准某个被提议的值
2. 一个值被批准了，其他服务器最终会学习到这个值
Paxos的两个主要组件
01
Proposer
提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。
02
Acceptor
提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
paxos的定义
首先从最简单的方式开始，假设只有一个Acceptor，多个Proposer，让它做决定是否批准一个值。每一个proposer提议一个值给Acceptor来批准，然后Acceptor批准一个值作为最终的值。如何保证一致性？使用互斥（锁），只有一个proposer能够得到锁，一旦值被写入，后面得到锁的proposer无法改变值。但是如果某个proposer获得锁以后，在赋值前down掉了，还没有释放锁资源，那么此时产生了死锁。
Paxos算法主要分为两个阶段
1. Prepare阶段
1
Proposer 向所有Acceptor发送Prepare申请访问权，并携带一个提案号(epoch)，Acceptor赋予访问权或拒绝，并且返回该Acceptor 已经接受的值和对应的提案号。如果Proposer获得超过半数Acceptor的访问权那么会进入第二阶段
特点：喜新厌旧
当Acceptor接收到Prepare请求时，它将当前自己发放了访问权的epoch号和该Prepare请求携带的epoch进行比较，如果前者小于后者，则将访问权赋予新请求的这个Proposer，否则拒绝发放访问权。这里我们认为epoch值越大的越新。
2.Accept阶段
1
如果所有的Acceptor返回值都为空，则Proposer将携带自己预设的值v和自己的epoch号向获取到访问权的Acceptor发送请求
2
如果Proposer第一阶段获得某些Acceptor的返回值不为空，则将epoch号最大的提案号对应的值f作为自己的预设值，和自己的提案号一起向Acceptor发送请求(如果第一阶段返回f的Acceptor已经超过了半数，则表示已经形成确定性取值，此时直接返回成功，不需要进行Accept请求了)
特点：一视同仁
当Acceptor接收到Accept请求时，它 将当前自己发放了访问权的epoch号和该Prepare请求携带的epoch进行比较，如果前者大于后者，则拒绝该请求。如果这两个epoch号相等， 并且Acceptor当前接受的取值为空，则接受该Acceptor请求，同时将该Accept请求的值设置为接受值。如果之后又更大的epoch号申请 到访问权，并发出Accept请求，该值也不会改变，即Acceptor在确定了值之后不再改变，谁先设置就用谁的值。虽然在发放访问权时是喜新厌旧，但 在取值这个问题上一视同仁，不会因为新epoch号大而改变取值。
攻城狮小明
最后我们来讲一下提议ID生成算法（epoch）
提议ID生成算法（epoch）
在Google的Chubby论文中给出了这样一种方法：假设有n个proposer，每个编号ir(0<=ir<n)，proposor编号的任何值s都应该大于它已知的最大值，并且满足：s %n = ir => s = m*n + ir
proposer已知的最大值来自两部分：proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值以3个proposer P1、P2、P3为例，开始m=0,编号分别为0，1，2
1. P1提交的时候发现了P2已经提交，P2编号为1 > P1的0，因此P1重新计算编号：new P1 = 1*3+0 = 4
2. P3以编号2提交，发现小于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5
攻城狮小明
今天我们讲的都是理论知识，下节课我将通过一个具体的例子来学习paxos的算法的流程，帮助大家更好的理解。
程序猿小白
好的，很期待下节课。
小白程序猿
你若有干货或程序开发中的趣事，欢迎前来爆料啊~