paxos-分布式一致性协议.ppt

* 人们在研究Paxos时，很容易在这几个问题上纠结： 1）Paxos算法本身把一致性问题描述成了一个“游戏”场景，但是一致性问题究竟是个什么样的计算机系统问题？ 2）一致性问题的难点是什么呢？Paxos算法是怎样解决这些难点的？ Paxos算法分成两个阶段，那每个阶段都在做什么？ 3）Paxos算法解决的一致性问题和分布式存储有啥关系？怎么进行应用呢？ 我们今天首先会描述清楚Paxos希望解决的一致性问题。 以及如何在分布式存储系统里应用。 然后会按照循序渐进的方式，不断解决Paxos算法的难点， 直到最后引入Paxos算法。 那首先来看一下Paxos算法希望解决的计算机系统问题是什么，这个问题怎样应用再分布式存储系统里呢？ * 我们把确定Paxos希望解决的一致性问题定义为确定一个不可变变量的取值。 这个变量的取值可以为任意二进制数据。 初始为空，一旦被确定以后，不再更改。 因为变量取值确定后，不能再更改，所以我们称此值为不可变变量 那确定一个不可变变量在分布式存储系统里能干什么呢？ 我们知道分布式存储系统里数据是可变的，可以让多用户并发的增删改查。 如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。 即给并发乱序的更新操作定序，让多个副本按照 固定的操作序列【Op1, Op2, …, Opn】依次执行。 为保证每个节点执行相同的命令序列，我们可以在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。 具体的执行流程是： 先确定Op1是什么，让各个数据副本执行Opi，然后再确定Op2，依次类推 Google的Chubby、Megastore和Spanner都采用了Paxos来对数据的更新序列达成一致。 并为了性能考虑对Paxos进行了一些扩展。 * 我们可以把确定一个不可变变量这个问题，定义为： 设计一个系统，来存储名称为var的变量。 系统内部由多个Acceptor组成，负责存储和管理var变量。 外部有多个proposer机器并行调用API，向系统提交不同的var取值。 var的取值可以是任意二进制数据。 系统对外的API库接口为：propose(var, V) = ok, f or error， 任何机器可以安装API库，调用这个接口。 向系统请求将var的确定性取值设置为V。系统内部会进行处理。 最后接口会返回系统已经生成的确定性取值f。 如果系统内部把V设置为确定性取值，则f为V。否则f是其他调用提交的取值。 可以通过propose（var，null），来获取var的确定性取值。 系统需要保证var的取值满足一致性 如果var的取值没有确定，则var的取值为null。 一旦var的取值被确定，则不可被更改。并且可以一直获取到这个值。 如果一个propose调用返回ok, f，则任何调用都只能返回ok, f。 那解决好这个问题有哪些难点呢？ * 我们将循序渐进的解决好这些难点问题。 首先思考一下，如何控制Proposer的并发运行呢？ * * 首先我们来看一下基于互斥访问权的acceptor是怎样实现的。 Acceptor内部保存变量var和一个互斥锁lock。 Acceptor对外支持3个远程调用。 调用Prepare接口可以获取到互斥访问权和当前var取值f。F可能是null也可能不是。 acceptor内部会加互斥锁，给予var的互斥访问权，并返回var当前的取值f。 调用release接口可以释放互斥访问权。 acceptor内部会解互斥锁，收回var的互斥访问权 调用accept(var, V)，让acceptor将var取值设置为V。 Acceptor内部判断如果已经加锁，并且var没有取值，则设置var为value 。并且释放锁。 总结来说，如果想让acceptor的accept函数接收V ，则必须首先调用prepare获取互斥访问权。 所以Propose的运行分成两阶段： 第一阶段通过prepare获取互斥访问权，和当前var取值。 如果不能，则说明互斥访问权被其他proposer获取到了。 第二阶段根据当前var取值情况，来分别处理。 如果f为null，说明当前肯定没有确定性取值，此时可以提交请求中的取值V。 如果f不为空，说明f已经被acceptor接受为var的确定性取值，则通过Acceptor::release()释放访问权，返回ok, f。 总结来说， Proposer的运行首先获取到互斥访问权，然后运行，释放互斥访问权。 互斥访问权让多个propose调用一个一个的运行， 一旦一个proposer，在第一阶段获取到互斥访问权，在第二阶段将var的取值由null设置为V 。