书籍链接《凤凰架构》

本篇主要记录分布式一致性算法中Paxos，Raft以及Zab协议的相关zhizhi

Paxos

Paxos算法中将分布式系统中的节点分为三种：

（1）Proposer：提案节点，对某个值进行设置的节点，该行为称为提案(Proposal)，值一旦设置成功，就不会丢失也不可变。

（2）Acceptor：决策节点，提案一旦得到过半数量的节点接收，即称为提案被接受，称为批准(Accept)。

（3）Learner：记录节点，只是单纯从提案和决策节点中获取达成共识的结果。

Paxos算法中包括两个阶段：

（1）准备阶段(Prepare)，某个提案节点准备发起提案，必须先向所有决策节点发送Prepare请求。Prepare请求中会携带一个全局唯一的数字n作为提案ID（Paxos算法本身不关注该全局唯一数字的生成），决策节点接收到Prepare请求之后，会给提案节点两个承诺和一个应答：

承诺：

  • 承诺不会再接受天ID小于或等于n的Prepare请求。
  • 承诺不会再接受提案ID小于n的Accept请求。

应答：

  • 在不违背前面做出的承诺的前提下，回复已经批准的提案中ID最大的ID和值，如果该值从来没有被设定过，则返回空值。如果收到的提案ID并不是接收到的最大的，允许直接对此Prepare请求不与理会。

当提案节点接收到多数决策节点的应答(Promise)后，开始第二阶段批准(Accept)过程，此时存在两种情况：

  • 如果所有决策节点的响应中都没有设置过该值，则可以随意决定要设定的值，并将设定的值和提案ID组成二元组发送给所有的决策节点（Accept请求）
  • 如果决策节点中已经至少有一个决策节点包含设定值，则不能随便设定值，必须无条件使用应答中的提案ID最大的值，组成二元组并再次发送给所有的决策节点

当多数决策节点应答(Accepted)之后，协商结束。

推导过程

为了加深理解，参考《从Paxos到Zookeeper分布式一致性原理与实践》，大概梳理了一下Paxos算法的推导过程。

（1）在没有失败和消息丢失的情况下，我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案，为了保证这个需求，需要满足下面这个原则：

P1：一个Acceptor必须批准它收到的第一个提案。

但是这个需求引出了另外一个问题，当多个提案被多个Proposer同时提出，可能出现每个Acceptor批准了它接收到的第一个提案，但是没有任何提案是由多数决策节点批准的，最终无法达成共识。

—————未完待续————