Paxos Made Simple

https://zhuanlan.zhihu.com/p/380587949

1.Introduction

        Paxos一种实现分布式系统容错的算法本质是共识算法。最后一节使用状态机来构建分布式系统。

2 The Consensus Algorithm

2.1 The Problem

        定义共识问题一些进程均可以提出建议值大家进行协商最终只能选出一个某进程的值并且最终大家都接受。
        系统中包含三种角色建议者、接受者、学习者单进程可扮演多种角色。对于系统的假设

1. 节点可以发生错误、重启但是需要记住已经选择的值这则信息便于错误恢复
2. 信息传递可以重复、丢失但不可以被破坏非拜占庭

2.2 Choosing a Value

        论文实际上是逐步加上条件最终来实现Paxos的规则。逐步从不满足要求的规则过渡到最终满足要求的Paxos。
        单个接受者存在单点故障使用多个接受者足够多的接受者接受即可选定。至于足够多是多少见The implementation of reliable distributed multiprocess systems。

P1. acceptor必须接收第一个它收到的proposal
        存在问题不同的建议者提出不同的值无法达成共识。需要接受者可以接受多个建议值避免算法失效并且建议值需要和建议编号关联。
        我们可以允许多个proposal建议值被选中但是我们必须保证被选中的proposal有相同的value。通过归纳proposal number足以保证
P2.如果一个value为v的proposal被选中那么所有被选中的higher-numbered proposal都具有value v
        因为number都是有序的条件P2保证了只有单一的value被选中这一重要特性。为了能够被选中proposal必须至少被一个acceptor所接受。所以我们可以通过满足以下条件满足P2
P2a.如果一个value为v的proposal被选中那么每一个被任何acceptor所接受的high-numbered proposal都有value v
P2b.如果一个value为v的proposal被选中那么之后每个proposer发出的high-numbered proposal都有value v
        我们可以通过满足以下条件来确保标号为n的proposal有value为v
P2c.对于任意的v和n如果有一个value为vnumber为n的proposal被发出了那么就存在一个由majority个acceptor组成的集合S。要么(a)S中没有一个acceptor接受过number小于n的proposal要么(b)v是S中的acceptor接受过的number小于n的最高number的proposal的value
        推断出存在上面这两种情况为了满足上述两种情况。如果proposer想要发出一个number为n的proposal那么它必须要获取已经或者将要被一个majority接受的最高number不大于n的proposal的value。获取那些已经被接受的proposal是非常简单的但是对未来的接受情况进行预测就非常困难了。为了避免对未来进行预测proposer通过获得不会有这样的接受情况的承诺来进行控制。换句话说proposer请求acceptor不要接受任何number小于n的proposal。这就导出了以下发送proposal的算法proposer的算法

1. 一个proposer选择了一个新的proposal number n并且给一些acceptor集合的每个成员发送了一个请求并希望它们回复
   1承诺再也不接受number小于n的proposal
   2如果已经接受了最高number小于n的proposal返回
   我们将这样的请求称为number为n的prepare request
2. 如果proposer接受了来自一个majority对于请求的回复那么它就可以发送一个number为nvalue为v的proposal。其中v要么是返回的最高number的proposal的value如果没有proposal返回那么proposer随意选择一个值。

        cceptor它总允许对prepare request进行回复。它可以对一个accept request进行回复代表接受一个proposal如果它没有承诺不那么做的话。换句话说
P1a.acceptor可以接受number为n的proposal如果它之前没有回复任何number大于n的prepare request
        现在我们已经为满足安全性要求地选择value提供了一个完整的算法——假设proposal number唯一的情况。最终的算法只是在这基础之上做了一个小小的优化。
        优化假设一个acceptor接受了一个number为n的prepare request但是它已经回复了一个number大于n的prepare request。因此它承诺不会接受任何number为n的新的proposal。因此该acceptor是不会接受该proposer想要发出的number为n的proposal的所以该acceptor没有理由回复这个prepare request。因此我们让acceptor忽略这样的prepare request。同样我们对于已经接受的proposal对应的prepare request也是忽略的。
        经过这样的优化以后acceptor只需要记住它接受过的最高number的proposal以及它回复过的最高number的prepare request。即使发生了故障也要满足P2c,因此即使发生了故障或者重启了acceptor也要记住这些信息。需要注意的是proposer总是可以放弃一个proposal并且将它忘得一干二净——只要它不再发送另一个具有相同number的proposal。

        算法包含proposer和acceptor

1. aproposer选择一个proposal number n然后向一个majority发送number为n的prepare request
   b如果n大于任何它已经回复的prepare request的number那么acceptor接受了一个number为n的prepare request且将承诺不再接受任何number小于n的proposal并且回复已经接受的最高number的proposal如果有的话
2. a如果proposer接受了来自majority对它的prepare request的回复那么接下来它将给这些acceptor发送一个number为nvalue为v的proposal作为accept request。其中v是收到的回复中最高number的proposal的value或者如果回复中没有proposal的话就可以是它自己选的任意值
   b如果acceptor收到一个number为n的accept request如果它没有对number大于n的prepare request进行过回复那么就接受该accept request

        提案随时失效当其他的proposer已经开始发出更高number的proposal时最好放弃当前的proposal。因此。如果acceptor因为它已经接受了更高number的prepare request而忽略了其他的prepare或者accept request那么它应该通知对应的proposer放弃该proposal。这是对性能优化并不会影响正确性。

2.3 Learning a Chosen Value

        问题是学习者如何获取已经被选中的值几个策略如下
        让每个acceptor在接受了一个proposal之后向所有的learner发送这个proposal。通讯量大收敛快。
        先发给distinguished learner再发给其他learners。通讯减低两轮请求单点失效。
        先发给distinguished learner的集合再发给其他learners。权衡。
        learner可以直接问acceptor它们接受了什么proposal使用上文描述的算法。

2.4 Progress

        实际情况存在活锁使用随机超时机制。

2.5 The Implementation

        持久化存储必要的信息。
        接下来所有的内容都将用于描述如何保证两个proposal不会有相同的number。不同的proposer会从不相交的数据集中选择number所以不同的proposer不会发送具有相同number的proposal。每个proposer都会用stable storage记住它尝试发送的最高number的proposal并用一个比所有已经使用过的number都高的number开始phase 1。

3 Implementing a State Machine

        状态机模型单一节点过度到集群。对于每个Paxos实例可以确定一个命令这样状态机集群就都有着相同的命令序列。
        Paxos共识算法效率的关键在于直到phase 2之前都不对提出的value进行选择。回忆一下是在完成了phase 1之后才知道要发送的value要么已经被决定了要么proposer可以被任意选择。
        出错的情况当前一个leader刚刚发送故障但是新的leader还没有选举出来的情况系统刚刚启动时是一个特殊的情况那时候还没有任何命令被提交。
        出现gap的情况proposer在刚提议完之后发生故障并且提案值并没有被接受可能由于网络原因接着选举出新的leader。疑惑那gao位置的命令就算丢失了吗

核心思想

        容错性半数以下节点故障仍然可以确定系统取值

• 在抢占式访问权的基础上引入多个acceptor
• 一个提案编号只给一个proposer使用
• 新的proposer采用“后者认同前者”的思路