- Lamport在1990年提出了Paxos算法，并给出了理论证明。Paxos算法是基于消息传递且具有高效容错特性的一致性算法，目前公认的解决分布式一致性问题最有效的算法之一。Paxos广泛应用于Google 的 chubby、雅虎的Zookeeper，阿里还推出了Paxos底层库。Google公司Chubby锁的作者Mike Burrows评价说只有一种一致性算法，那就是Paxos。
- Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。
-
产生背景：在常见的 分布式系统 中，总会发生 节点宕机 或 网络异常 (包括消息的 重复、丢失、延迟、乱序、网络分区) 等情况。Paxos 算法主要就是解决如何在一个 发生如上故障 的分布式系统中，快速正确的在集群内 对某个值达成一致，并且保证 整个系统的一致性。
paxos要解决的问题
1、问题与假设
拜占庭帝国想要进攻一个城市，为此派出了10个将军率领10支军队，这个城市足以抵御5支常规拜占庭军队的同时袭击。这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击，至少6支军队同时袭击才能攻下敌国。10支军队分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。这里的问题是，对应于有的主机坏掉了，将军中可能会有叛徒，忠诚的将军希望达成命令的一致（比如约定某个时间一起进攻），但背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？
- 分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础 Paxos 场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。（一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。）
- 为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。
2、paxos算法
角色划分：首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以接受（accept）提案，若提案获得多数派（majority）的 acceptors 的接受，则称该提案被批准（chosen）；learners 只能“学习”被批准的提案
角色划分
算法前置条件：
1、决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
2、在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
3、learners 只能获得被批准（chosen）的 value。
算法内容：首先选出一个leader（也就是proposer），proposer提出一个提案前，首先要和足以形成多数派的acceptors进行通信，获得他们进行的最近一次接受（accept）的提案（prepare过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数acceptors接受（accept）后，提案获得批准（chosen），由acceptor将这个消息告知learner。这个简略的过程经过进一步细化后就形成了Paxos算法。
算法执行步骤：
1、选择一个节点成为leader/proposer。
2、leader选择一个值，发送到所有的节点（Paxos中称之为acceptor），这个消息被称为“接受请求”消息。acceptor可以回应接受或拒绝。
3、一旦节点中的大多数回应接受，共识就能达成，协调者将“提交”消息发送到所有节点
算法证明：https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
3、用一个故事讲解paxos算法
https://www.cnblogs.com/endsock/p/3480093.html
4、总结
- 要证明分布式一致性算法的正确性通常比实现算法还困难。所以很多系统实际中使用的都是以 Paxos 理论 为基础而 衍生 出来的变种和简化版。例如 Google 的 Chubby、MegaStore、Spanner 等系统，ZooKeeper 的 ZAB 协议，还有更加容易理解的 Raft 协议。
网友评论