PAXOS

paxos 是什么, 解决什么问题

Paxos算法是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

在分布式系统中, 节点通信主要依靠两种模型. 共享内存和消息传递. 如果基于消息传递,必然会有各种问题: 譬如进程变慢, 重启,消息丢失.为了解决消息传递里的问题, 就出现了一致性算法.

paxos算法解决的问题是: 在分布式系统中保证某个值达成一致.

paxos的典型的场景是用在分布式数据库系统中.

我们通常认为, 在分布式系统中,如果每个节点的初始状态一致, 并且执行相同的操作, 那么最后可以得到一致的结果. 为了得到这个相同的命令, 需要在每一条指令上,执行”一致性算法”, 保证每个节点看到的指令相同.

具体来说, 可能的场景包括

数据库的数据复制. 保持多个节点数据的一致性
naming service (zookeeper的经典功能) naming service 是指, 在集群里, 经常会需要有地方能够存hostname/ip映射关系, 服务名和服务地址映射等等. 如果单机在每台机器上存放这些信息,随着系统的变大, 可能会出现信息不一致. 于是有一种做法是提供集中式的naming service服务. 于是也可以分布式的服务. 这种场景时, 可以使用paxos
config配置管理 (zookeeper经典的功能)
id分配.

如果目的是比较分布式数据存储,有以下解决方案.(严格意义上来说, 这一篇不算是paxos 同类产品的比较)

算法	简单介绍	优点	缺点
master/slave		成熟稳定	master还是会有单点故障
multi master	一个系统多个master, 每个master都有read-write的能力	解决了master slave的单点问题	合并版本比较复杂
两阶段提交(Two phase commit)	第一个阶段,锁定所有的参与者的资源. 第二个阶段, 通知所有的参与者.	相对简单	1. 需要阻塞. 2, 容错机制较差
三阶段提交 (Three phase commit)	针对两阶段提交容错机制差的问题, 做了改进. 分成vote, pre commit, commit 三个阶段.	不会由于单点故障,出现问题
paxos	在三阶段提交的基础上, 分成了6个步骤,纤细看下文	目前最完整的一致性算法

paxos算法里, 分成3种角色

主要的步骤包括

提案者生成唯一编号N. 向50%以上的决策者发出预提案请求P
被发送消息的决策者收到提案请求P, 对应编号N. 决策者查看自己关于时间P,是否有收到过提案. 分成三种情况 a) 没有收到过提案, 返回通过 b) 已经收到过提案, 提案编号为M. 如果M大于N, 则返回拒绝 c) 如果M<N, 返回 “通过, 但是哥收到过M”
提案者如果收到的都是通过, 则可以正式提议了. 如果收到了一个”拒绝”, 则提案被拒绝如果收到了”通过,但是哥收到过M”, 提案者用收到的所有M中最大值, 重新提案, 回到第一步
提案者正式提议. 决策者 类似于第二步, 重新选择通过或者拒绝
提案者如果发现提案被50%以上的决策者同意了, 则决策通过. 通知书记官, 记录这条法令. 如果不够50%的决策者赞成, 提案者接着找其他的决策者来决策. 有任一决策者返回拒绝, 提案终止
书记官记录这条法案