| layout | post | |||
|---|---|---|---|---|
| category | 分布式 | |||
| description | 分布式算法Paxos的介绍和相关参考资料,Paxos算法原文,Paxos算法解读,ZooKeeper的灵魂Paxos | |||
| keywords | 分布式算法 | |||
| title | 分布式一致性算法Paxos | |||
| tags |
|
|||
| summary | 分布式算法Paxos介绍 |
####一.简介 Paxos是基于消息传递的一致性算法，解决的是分布式系统中的一致性问题。
Paxos算法的核心和精华就是确保每次表决只产生一个Value。
Google的Chubby和Apache的ZooKeeper都基于此实现。
Paxos假设发生在一个可信的网络环境中，不会有拜占庭的问题。
####二.简单理解Paxos算法：Paxos岛上的议案 假设有个叫Paxos的岛，岛上的所有事情都是有一群叫议员(Senator)的人决定的，这些议员组成了一个议会。
岛上的所有事务都必须要经过一个叫议案(proposal)来决定的，每个proposal都有个编号，且编号不断往前长。
一个议案只有超过议会一半的议员通过才会生效。
每个议员都会有个笔记本，记录自己当前的提议编号。
每个议员只会通过比自己编号大的议案。
议会不能保证每个议员笔记本上的编号都相同。
#####无冲突的议案 好，现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。
有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1元/度。
#####有冲突的议案 假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。
####三.ZooKeeper中的Paxos
小岛：ZooKeeper集群
议员：ZooKeeper中的server
议案：ZNode的变更
议案编号:ZXID
在ZooKeeper中只有leader才能发起议案，因此还有leader的角色。
以上第二、三小节引用自： Zookeeper全解析——Paxos作为灵魂
####四.算法详述 #####（一）.Wiki上的Paxos算法介绍
分布式系统上的节点通信包含两种方式：共享存储和消息传递。
基于消息传递的系统，可能发生进程慢、重启、崩溃等状况，消息可能出现延迟、丢失和重复，因此需要一个算法能在此环境中保证状态一致。
假设一个分布式的系统中，初始状态一致，如果应用相同顺序的操作，那么最终它将到达一个一致性的状态。
######角色划分 议员的角色被分为三种：
- proposer
- acceptors
- learner
proposer可以提出一个提案，acceptors可以选择接受它，只有大部分的acceptors接受后，提案才能通过，成为决议。
learner只能学习决议的内容，不参与提案决定的过程。
#####(二).陈国庆的Paxos算法介绍
####参考资料