zookeeper原理_paxos协议_一步一步理解paxos算法

《分布式系统理论基础 - 一致性、2PC和C》一文介绍了一致性、达成一致性需要面临的各种问题以及2PC、C模型，Paxos协议在节点宕机恢复、消息无序或丢失、网络分化的场景下能保证决议的一致性，是被讨论最广泛的一致性协议。

Paxos协议同时又以其“艰深晦涩”著称，下面结合Paxos Made Simple、The Part-Time Parliament 两篇论文，尝试通过Paxos推演、学习和了解Paxos协议。

Basic Paxos

何为一致性问题？简单而言，一致性问题是在节点宕机、消息无序等场景可能出现的情况下，相互独立的节点之间如何达成决议的问题，作为解决一致性问题的协议，Paxos的核心是节点间如何确定并只确定一个值(value)。

也许你会疑惑只确定一个值能起什么作用，在Paxos协议里确定并只确定一个值是确定多值的基础，如何确定多值将在第二部分Multi Paxos中介绍，这部分我们聚焦在“Paxos如何确定并只确定一个值”这一问题上。

和2PC类似，Paxos先把节点分成两类，发起提议(proposal)的一方为proposer，参与决议的一方为acceptor。假如只有一个proposer发起提议，并且节点不宕机、消息不丢包，那么acceptor做到以下这点就可以确定一个值：

当然上面要求的前提条件有些严苛，节点不能宕机、消息不能丢包，还只能由一个proposer发起提议。我们尝试放宽条件，假设多个proposer可以同时发起提议，又怎样才能做到确定并只确定一个值呢？

首先proposer和acceptor需要满足以下两个条件：

1. proposer发起的每项提议分别用一个ID标识，提议的组成因此变为(ID, value)

2.acceptor可以接受(accept)不止一项提议，当多数(quorum)acceptor接受一项提议时该提议被确定(chosen)

(注: 注意以上“接受”和“确定”的区别）

我们约定后面发起的提议的ID比前面提议的ID大，并假设可以有多项提议被确定，为做到确定并只确定一个值acceptor要做到以下这点：

(注: 乍看这个条件不太好理解，谨记目标是“确定并只确定一个值”)

由于一项提议被确定(chosen)前必须先被多数派acceptor接受(accepted)，为实现P2，实质上acceptor需要做到：

满足P2a则P2成立 (P2a => P2)。

目前在多个proposer可以同时发起提议的情况下，满足P1、P2a即能做到确定并只确定一个值。如果再加上节点宕机恢复、消息丢包的考量呢？

假设acceptor c 宕机一段时间后恢复，c 宕机期间其他acceptor已经确定了一项值为v的决议但c 因为宕机并不知晓；c 恢复后如果有proposer马上发起一项值不是v的提议，由于条件P1，c 会接受该提议，这与P2a矛盾。为了避免这样的情况出现，进一步地我们对proposer作约束：

满足P2b则P2a成立 (P2b =>P2a => P2)。

P2b约束的是提议被确定(chosen)后proposer的行为，我们更关心提议被确定前proposer应该怎么做：

满足P2c则P2b成立 (P2c =>P2b => P2a => P2)。

条件P2c是Basic Paxos的核心，光看P2c的描述可能会觉得一头雾水，我们通过The Part-Time Parliament中的例子加深理解：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29831-1.html