知识卡片
实例编号与提议编号分工
Multi Paxos把许多个单值共识实例按实例编号排列成序列。实例编号标识要决定哪个位置,提议编号则标识为这个位置进行的哪轮竞争;二者不能混用。独立实例的实现要分别保存各位置的promise和accepted状态。稳定leader复用prepare可以降低后续位置开销,但换leader时仍须恢复各位置已有结果,不能用新领导身份抹去已选值。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 共识算法Paxos(含第3部分导读) · 查看原书依据
运行的每一个Paxos consensus算法,被称为一个实例,为每一个实例都设定一个实例编号。 Paxos算法,或者叫作Multi Paxos算法,就是多次运行Paxos consensus算法,形成多个实例的算法。 Paxos完整算法可以有多种实现方式。接下来将介绍两种具体的完整Paxos算法,其中一种是独立实例运行的完整Paxos算法;另一种是只运行一次prepare消息的完整Paxos算法。无论哪种方式,Paxos算法都会产生这样一个结果:类似于每个进程都会形成一个数组,数组中的每个元素都是一个达成一致的值。 10.4.2 独立实例运行的完整Paxos算法 我们先来介绍第一种完整的Paxos算法。 1.算法简述 类似于10.3节中介绍的方法,我们具体化一些信息,可以得到实际的一个算法过程。当然,也存在其他具体化方式,产生的具体算法不尽相同。为了区分实例,我们在Paxos consensus算法的消息中添加一个实例编号,也就是instanceid参数,简写成i,得到表10.11。
参考来源
- 位置:《分布式系统与一致性》第10章(来源项目:book-sources;源文件:extracted/分布式系统与一致性/_epub-src/OEBPS/Text/chapter14.xhtml)
- 结论依据:本章对上述机制的流程与约束说明;图表部分按本书对应图表阅读。
- 原始内容:运行的每一个Paxos consensus算法,被称为一个实例,为每一个实例都设定一个实例编号。 Paxos算法,或者叫作Multi Paxos算法,就是多次运行Paxos consensus算法,形成多个实例的算法。 Paxos完整算法可以有多种实现方式。接下来将介绍两种具体的完整Paxos算法,其中一种是独立实例运行的完整Paxos算法;另一种是只运行一次prepare消息的完整Paxos算法。无论哪种方式,Paxos算法都会产生这样一个结果:类似于每个进程都会形成一个数组,数组中的每个元素都是一个达成一致的值。 10.4.2 独立实例运行的完整Paxos算法 我们先来介绍第一种完整的Paxos算法。 1.算法简述 类似于10.3节中介绍的方法,我们具体化一些信息,可以得到实际的一个算法过程。当然,也存在其他具体化方式,产生的具体算法不尽相同。为了区分实例,我们在Paxos consensus算法的消息中添加一个实例编号,也就是instanceid参数,简写成i,得到表10.11。