5.6 KiB
+++ title="Paxos算法详解" date="2023-05-08" +++
前言
目前主流分布式共识算法有etcd使用的raft,zookeeper使用的zab,其思想或多或少受到paxos启发。paxos算法由Leslie Lamport在《The part-time parliament》论文中首次提出。
为描述该算法,Lamport虚构出一个paxos小岛,利用类比的手法提出共识算法,本文旨在理解该论文后并结合相关经验对该算法进行重新描述。
文章整体结构与论文相同:
(1) 首先阐述Lamport提出的三条约束,由这三条约束推导出一致性。
(2) 在保证约束条件情况下,导出算法。
术语
- 一致性:一致性是一种状态。
- 活性:共识算法能够保证最终达成一致性。
- 共识:共识是过程(节点通过何种共识算法达成一致)。
- 决议:分布式系统想要达成一致的值、操作等。
- 提议:提出决议的过程。
- 投票:对决议表示赞同。
- 未决决议:已投票的决议,能否达成一致性未知。
- 已决决议:通过共识算法达成一致性的决议。
- 节点:参与共识算法的进程。
- 投票节点集:对当前决议进行投票的节点。
- 法定投票节点集:若法定投票节点集中所有节点对当前提议进行投票,则当前决议成为已决决议。
例:
存在一个256节点的集群,需要对集群管理密码进行统一配置,即所有节点密码与集群密码相同,存放在变量password
中。一致性:任意一台功能正常节点密码相同;活性:修改密码过程能够完成,中止或者成功;共识过程:客户端进行密码修改,令set password xxx
,发送给集群中主节点,主节点进行提议,提议后当前决议成为未决决议,集群其他节点进行投票,经过共识过程使决议成为已决决议,密码修改生效。
条件
- 非拜占庭环境,节点不会伪造信息,都尽力完成任务。
- 消息在信道中可能存在丢失、重复、乱序。
- 节点可能会发生故障(掉电,磁盘损坏等)。
约束
所有轮次提议构成的集合需要满足下列三条约束:
约束Ⅰ 决议的每一轮提议都有唯一提议号。
约束Ⅱ 任意两次提议的法定投票节点集都存在至少一个公共节点。
约束Ⅲ 任意一次提议的决议与该提议法定投票节点集中所有节点已投票决议中具有最大提议号的决议一致。
注意:提议号可以进行大小比较,但是一般不反应时间先后顺序。
提议号 | 决议 | 法定投票节点集 |
---|---|---|
002 | 123 | 00 01 02 03 |
005 | abc | 00 01 02 04 |
114 | 123 | 01 03 04 |
127 | abc | 00 02 03 |
229 | abc | 01 02 03 |
如上是一个满足约束条件的提议集:提议号唯一,任意两次提议法定节点集都有至少一个公共节点。
002和005号提议中法定投票节点之前都没有进行投票(投票节点标记),所以决议可以为任意值;114号提议中,03节点在002号提议中进行投票,01和04节点未进行投票,所以该轮提议的决议需与002号提议中的决议一致;127号提议中,02和03节点在之前提议中进行投票,且最大提议号为005,所以该轮提议的决议需与005号提议中的决议一致;229号提议中,01、02和03节点均在之前提议中进行投票,且最大提议号为114,所以该轮提议的决议需与114号提议中的决议一致。
在127号提议中,法定投票节点集中所有节点进行了投票,这本次决议达成一致,成为已决决议,最终值达成一致为abc
(01和04节点可能并不知晓该次决议,但是不影响最终对外一致性)。
一致性
当提议形成的提议集,满足上述约束,能够保证一致性。
若某轮提议达成一致,成为已决决议,则任意提议号大于该提议的决议都与其相同
证明(反证法):
- 假设在已决决议提议之后存在提议的决议与已决决议不同,取这些提议中提议号最小的提议,记为提议甲。
- 提议甲中的法定节点集一定与已决决议投票节点集有交集(约束Ⅱ保证法定节点集之间有交集,已决决议保证法定节点集是投票节点集的子集)。
- 提议甲的法定节点集中一定存在节点,在大于等于已决决议提议号,小于提议甲提议号之间进行了投票(由2推出至少存在一个节点,即在已决决议提议中进行投票的节点)。取这些投票所对应的提议号距提议甲最近的一次决议,记为决议乙。
- 由约束Ⅲ的存在,决议甲的法定节点集在决议乙中进行了投票,则决议甲等于决议乙,两则与已决决议不等。
- 违法决议甲是不同于已决决议中拥有最小提议号的假设。
参考
- Leslie, Lamport. "The part-time parliament." ACM Trans. on Computer Systems 16 (1998): 133-169.
- Lamport, Leslie. "Paxos made simple." ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001): 51-58.