paxos算法理解

basic paxos

base paxos讲的是,分布式环境下,多个节点之间,如何就某个值达成共识,是一种共识算法。
例如有一个三副本的kv存储系统,有三个节点,其中两个都接收到更新x的请求(如node 1收到的是set x-2, node 2 收到的是set x=5),base paxos的目标是,如何快速使三个node上x的值保持一致,x=2或者x=5.

三种角色

提议者:接收客户端请求,发起提案
接收者:对提案进行投票
学习者:备份已通过的提案值,不参与投票,对理解paxos算法可以忽略。

如何达成共识

分为两个阶段,第一阶段prepare阶段,获取提议权和当前提议值,第二阶段,根据发起提议

  1. 准备阶段
    1.1 提议者携带提案编号发送请求给接收者;
    1.2 接收者本地的提案编号如果大于提议者的编号,则拒绝;否则,答复自己的提议值,并将自己的提案编号改为提议者的提案编号;
    1.3 提议者收到大多数接收者的响应时,才可以进行提议
  2. 提议阶段
    如果所有prepare的响应都是尚无提案,则提议者将设置<提案编号,提议值>发送给接收者
    否则,提议者选择响应中,提案编号最大的提议值,发送给接收者。

上面的比较模糊,可以对比看一下,下面两篇文章

multi paxos

basic paxos在达成共识时,需要两轮rpc,效率低,multi paxos是对basic paxos的优化,
第一阶段提议者获取到提议权后,可以进行多次第二阶段提议。
这种模式实际相当于第一阶段选出了一个leader,之后提议都由leader提出,不再有多个提议者的场景。

原文地址:https://www.cnblogs.com/holidays/p/paxos.html