算法--Paxos深入理解

  分布式系统中的节点通信存在两种模型:共享内存(Shared memory)消息传递(Messages passing)。基于消息传递通信模型的分布式系统,不可避免的会发生以下错误:进程可能会慢、被杀死或者重启,消息可能会延迟、丢失、重复,在基础Paxos场景中,先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致,保证不论发生以上任何异常,都不会破坏决议的一致性(来源维基百科)。

  • Paxos 是什么
  1. 一个可靠的存储系统: 基于多数派读写;
  2. 强一致性;
  3. 每个paxos实例用来存储一个值;
  4. 用2轮RPC来确定一个值;
  5. 一个值‘确定’后不能被修改;
  6. ‘确定’指被多数派接受写入。

理论基础

前提

  • 总结一句话:信息准确无篡改,通信环境可信。
  1. 网络消息的传送,可能需要任意长的时间,可能丢失,或者重复.但是消息并没有伪造,篡改的.即没有所谓”拜占庭问题“——非拜占庭模型。
  2. 拜占庭模型(Byzantine model): 消息可能丢失、重复或者内容损坏。换而言之,非拜占庭模型就是允许消息的丢失或者重复,但是不会出现内容损坏的情况。

目的

  • 解决多结点间一致性问题(集群中一个修改或者申请成为主结点的提议),所谓一致性算法就是要能够保证:在建议的不同的值之中,最终只能有一个被确定下来.
  • 三个特性:
  1. 终止性: 每一个进程最终确定了一个值
  2. 同意性: 每一个进程确定的值是相同的
  3. 正确性: 每一个所确定的值,是某个进程所”建议”的.即任一进程所确定的值,不是非法的.

主要角色

  • Proposer : 提议者,提出议案(同时存在一个或者多个,他们各自发出提案);
  • Acceptor : 接受者,收到议案后选择是否接受;
  • Learner : 学习者,只学习正确的决议;

概念

  • 提案 : 每个proposer向acceptor们提交提案时都会附带一个序号和决议内容{序号,决议内容};序号是取舍提案的依据,value是提案的唯一标识,即即使序号不一样value相同,依然是同一个提案。
  • prepare请求: 提案请求,proposer 向acceptor多数派发送提案请求。
  • 批准(chosen): 一个多数派接受了一个提案,并且在该proposer发送accept请求确认之后,那么我们说该提案被批准。
  • accept请求: 批准请求,proposer 征求acceptor批准自己的提案。
  • 接受(accept): acceptor总会接收它收到的第一个提案;如果序号比之前接受的提案序号都高,那么它也会接收提案;
  • 多数派: 是所有acceptor的一个子集,元素个数多余一半就称之为多数派。他代表了某一群acceptor。根据抽屉原理,任意两个多数派之间必然有交集。

约束

  • 算法保持一致性的约束
  1. P1:一个acceptor必须接受(accept)第一次收到的提案。
  2. P2:一旦一个具有value v的提案被批准(chosen),那么之后批准(chosen)的提案必须具有value v。
  • 算法保持一致性约束的加强,即加强上文提到的P2约束条件:
  1. P2a:一旦一个具有value v的提案被批准(chosen),那么之后任何acceptor再次接受(accept)的提案必须具有value v。
  2. P2b:一旦一个具有value v的提案被批准(chosen),那么以后任何proposer提出的提案必须具有value v。
  3. P2c:如果一个编号为n的提案具有value v,那么存在一个多数派,要么他们中所有人都没有接受(accept)编号小于n的任何提案,要么他们已经接受(accept)的所有编号小于n的提案中编号最大的那个提案具有value v。

过程描述

  1. Proposer(提议者) 首先选择一个提议序号 nAcceptor(接受者) 节点发出 prepare 消息。
  2. Acceptor 收到prepare消息后,有下面两种情况:
  3. Acceptor 没有回应过编号大于nprepare请求时,acceptor 接受(accept)编号为 n 的提案;
  4. Acceptor 已经回复过编号大于nprepare请求时,则Acceptor将自己上次接受的提议回复给Proposer,并且承诺不再回复小于n的提议;
  5. Proposers 没有收到 Acceptor 中的多数派的回复,Proposers生成一个新的提议值再次发送给Acceptor批准;
  6. Proposers 收到 Acceptor 中的多数派对 prepare 的回复后,进入批准阶段。
  7. 如果超过一半的Acceptor接受,提议值生效。Proposers发送acknowledge消息通知所有的Acceptor提议生效

实例证明

背景

  • 下面我们有一个集群五个节点,即A、B、C、D、E五台机器,处于一种平等地位阶段,需要从中选择一个主节点,来管理这个集群,例如zookeeper的选举机制。
  • 参选者为A、B两台机器(提议者),C、D、E机器来为AB投票(接受者)。
  • 这里为了简化理解,就不像zookeeper那样还投自己一票,这里我们只让C、D、E三台机器参与投票。

一种串行场景

  1. 首先A、B分别去获取了一个唯一的编号1、2;
  2. 然后带着各自的编号去询问(提议)C、D、E看他们是否可以投票给自己(注:如果还没有投就可以投,已经投了就不能投了);
  3. 如果机器C、D、E都收到了编号1的询问,由于之前还没有任何机器询问,于是把(编号1)保存下来;并返回信息给A机器,告诉A机器我可以投你(此时还没投);
  4. 机器A收到了至少两个回复,有点激动了,发出提议“投我”,内容为(编号1,投A);
  5. C、D、E机器收到消息后,发现编号和自己保存的编号一致,就把信息(编号1,投A)保存下来,返回内容(Accepted)表示已投A(已接受);
  6. 此时A机器,就收到至少2台机器的投票(Accepted),总票数大于一半(得到大多数的支持);
  7. 此时如果B机器发起内容(编号2)的提议,C、D、E机器收到后,由于(编号2)比(编号1)大,会把(编号2)保存下来;又由于之前已经投了A机器了,所以没办法投B了,就返回信息给B说可能已经晚了,已经投了A机器内容(编号1,投了A)
  8. B机器,接收到至少2台机器返回信息(编号1,投了A),发现大多数都已经投了A机器,明白大势已去,即不再发起询问,接受A为Master的现实。

并发场景

  1. 首先A、B分别去获取了一个唯一的编号1、2;
  2. A机器到达C、D,此时C、D还不知道投谁呢,现在拉票的A机器来了,就记录(编号1)表示要投A机器;
  3. B机器到达D、E,此时D由于之前说好了投A但是还没投,来了一个编号更大的,由于之前规定在还没投的情况下如果遇到了更大编号的就选择投更大的,D机器于是决定改为投B,记录(编号2)、E记录之前都还没准备投,现在就肯定是投B了,记录(编号2);
  4. A机器这时候慢悠悠的到达E,殊不知E已由更大的编号2,所以A机器的编号1被拒绝了;
  5. 此时A机器,至少收到两个回复,感觉还是有希望,发出“投我”(编号1,投A)去询问C、D、E;
  6. 此时B机器,也至少收到两个回复,感觉有希望,发出“投我”(编号2,投B)去询问C、D、E;
  7. 机器C收到A的提议,发现编号一样,保存信息(编号1,投A),返回信息(Accepted)表示我投你了;
  8. 机器D收到A的提议,发现编号小于(编号2),因此返回信息(Rejected,编号2),告诉A机器我已经准备投2;
  9. 机器E可能没有收到A的提议;
  10. 机器B同时发送“投我”(编号2,投B)给C、D、E,D、E都到信息,发现和自己准备投的编号相同,于是返回信息(Accepted)表示我投你了;
  11. 此时B机器,至少收到了两台机器的(Accepted)内容,确认已被多数派所接受;
  12. 此时A机器,收到一个(Accepted)和(Rejected,编号2);机器A重新发起提议,编号提升为3,即内容为(编号3);
  13. 机器C收到A机器提议,发现(编号3)大于之前保存的(编号1),就把(编号3)保存下来;由于C机器之前已经接受A机器上次的提议,于是返回信息(编号1,投A);
  14. 机器D收到A机器提议,发现(编号3)大于之前保存的(编号2),把(编号3)保存下来;由于D机器之前已经接受B机器上次的提议,于是返回信息(编号2,投B);
  15. 机器E有可能没有收到提议,如收到就返回(编号2,投B)
  16. 此时机器A至少收到两台机器的回复,比较两个回复的编号大小,选择大编号对应的值为最新的提议;
  17. 机器A会再次发出消息给回复它的那至少两台机器,内容为(编号3,投B);
  18. 机器C、D或E收到(编号3,投B),发现和自己保存的编号相同,因此保存(编号3,投B),同时返回消息内容为(Accepted);
  19. 机器A收到了至少2台机器(accepted)内容,确认投B已经被多数派接受;
  • 参考资料
  1. http://www.happy615.com/?p=344
  2. http://iunknown.iteye.com/blog/2246484?from=message&isappinstalled=0
  3. https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
  4. https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
  5. paxos-simple.pdf

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器