Paxos算法原理 Paxos算法原理

Paxos算法是图灵奖获得者提出的分布式系统一致性算法。对于分布式系统来讲，由于分布式系统具有多个节点，一旦涉及到修改数据并持久化存储，最终必须达成数据的一致性，否则分布式系统就是错误混乱不可用的。
一算法的基本前提
这个算法解决依赖于三个基本假设，即必须满足这三个约束条件

? 只有一个值(value)被建议(proposed )的时候才可能被选择（chosen）,? 选择只能选择一个值, 并且? 一个进程不能读取这个选择的值除非该值被确认。

关于第一条，也就是说不能节点自己提出建议值自己选择，只通知选择后的结果，因为这样搞的话就退化成了一个建议，自我选择对一致性是没有意义的。
关于第二条，只能一个值，因为这是受一致性的约束，必须保证单机范围的一致性，否则这个问题也就没有意义。
第三条很容易理解，因为没有确认的值也就没有达成一致性，这与系统的一致性要求相悖。
从这个假设我们看到一致性算法划分3个角色：提出建议值者（proposer），批准建议值者（acceptor）和接收值者（listener）表示。这些角色并不局限于一个节点，也就是一个节点可以充当多个角色。
二算法的推导过程
提出建议就很简单了，任何节点有需求时都可以广播这个建议。
我们看选择和接受值的过程，退化下这个问题，简单的情形下，只有一个节点充当批准建议者，这个时候只要让接收的先后顺序依次确认就行了，但是一旦这个节点失效，就会使得系统瘫痪陷入不可用状态。
因此必须有多个批准节点，这种情况选择一个值遵守大多数协议，也就是大多数节点选择了这个值，这个数多大呢，应该是至少为总数的一半+1，也就是n/2+1，因为这样的话后续的修改就会有至少一个节点是相同的节点去处理一致性问题。假设不需要这个节点的话，如果是n/2，我们要把一个值由3修改为4，然后再4修改为5，第一次修改在n/2的节点达成一致，而第二次修改恰好在另外n/2达成一致，那么这个修改就不可行，因为系统的这一半节点当前值不是4，而是3。如果强行修改为5的话，后续的读取这个值就会正好一半节点认为是4，另一半节点认为是5，系统就会陷入两难，只能随机了，这样系统就成了一个不稳定的错误系统。
这样我们就有了一个必须满足的约束条件
R1：大多数批准者(acceptor)接受了某个值后，该值才算被接受，即可以被接收值者读到该值。
我们再退化下这个问题，假设只有一个建议被提出，那么批准者(acceptor)必须选择该值，因为批准者并不知道这是唯一的建议，只知道这是第一次接收到的建议，因此有第二个约束条件，作者标记为P1
【Paxos算法原理】P1 一个acceptor需要接受/同意其第一次收到的proposal中的value。
由R1约束条件的导出我们知道必须有一个节点处理多个建议，由P1我们知道必须有建议的时序性，为了标记这个时序性，我们用数字编号大小记录区分。
因此，一个proposal需要包含两个元素：编号和value。（这里将这个proposal表示为p，n表示编号，v表示value）。
为了保证不同的proposer提出的proposal上面的编号不一样，需要特殊的机制来获取编号，编号必须包含节点信息以及节点本身提出的时序性（比如可以根据系统中的acceptor的数量n以及这个proposer的编号m，例如编号为m的proposer提出的proposal的编号变化方式为m+i*n，i是提出proposal的次数，即i>=0）。这时候R1就可以描述为一个value被接受的条件就是一个带有该value的不同proposal被大多数的acceptor接受。这样，我们就说这个value和该proposal被接受了。
这样的话，我们必须允许多个proposal被系统所接受，这时我们需要保证所有的被选中的proposal里面带有的value是相同的，也就是说达成了一致性。
而这多个proposal不可避免的存在编号不同的问题，因为单个节点可以重复发起建议，后续时序的发起编号必然是大的编号，由于最先提出的约束第二条，只能批准一个值。因此我们得出了下面的约束条件：
P2：如果一个带有某个value的proposal被选中，那么所有的带有较高编号的proposal中的值必须也是这个value。
也就是说
P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。
批准一个 value 意味着多个 acceptor 接受（accept）了该 value。因此，可以对 P2 进行加强，推广到所有acceptor 的情况：
P2a：如果一个带有某个value的proposal被选中，那么所有被acceptor接受的带有较高编号的proposal中的值必须也是这个value。
P2b：如果一个带有某个value的proposal被选中，那么所有proposer提出的带有较高编号的proposal中的值必须也是这个value。
P2b可以推出P2a，因为提出的都是这个value，接受的不可能有其他value。
P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n
的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。
下面证明P2c可以推出P2b
对于所有编号小于n的任何提案没有被接受的多数派，那么通过提案的多数派必然和这个多数派必然有一个公共的acceptor,这时说明可以确保没有任何提案被通过，所以我提案值不受任何约束。
对于已经接受编号小于n的最大编号m提案是value v的多数派，同理这个时候任意其他多数派和这个的公共acceptor不接受其他提案，那么选出的值必然是这个多数派接受的值组成的集合中一员，如果不是value v，假设是u,
同时不是最大的的编号，假设编号为k,k 三算法的提出
要满足P2c的约束，proposer提出一个提案前，首先要和足以形成多数派的acceptors进行通信，获得他们进行的最近一次接受（accept）的提案（prepare过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数acceptors接受（accept）后，提案获得批准（chosen），由proposer将这个消息告知learner。这个简略的过程经过进一步细化后就形成了Paxos算法。
在一个paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和proposer的名字拼接起来。如何做到这一点不在Paxos算法讨论的范围之内。
如果一个没有chosen过任何proposer提案的acceptor在prepare过程中回答了一个proposer针对提案n的问题，但是在开始对n进行投票前，又接受（accept）了编号小于n的另一个提案（例如n-1），如果n-1和n具有不同的value，这个投票就会违背P2c。因此在prepare过程中，acceptor进行的回答同时也应包含承诺：不会再接受（accept）编号小于n的提案。这是对P1的加强：
P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案。
现在已经可以提出完整的算法了。
通过一个决议分为两个阶段：
1. prepare阶段：
1. proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派；
2. acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；
2. 批准阶段：
1. 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的value（如果根据P2c没有已经接受的value，那么它可以自由决定value）。
2. 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。
这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述prepare过程中，如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。
五算法的补充见解
算法本质是通过大多数acceptor prepare阶段获取一个锁，再达成一致前只能是可能的值v，如果有新的值v1要被建议只能是后续的时序。
与分布式事务的关系分布式事务与算法的目的相同，都是保证数据一致性。保证数据一致性本质上只有一个途径，就是这个算法提出的大多数投票达成共识，因此从这一点上看，其他算法都是这个算法的变种，而分布式事务本质上是这个算法的事务概念的包装实现。
算法与分布式系统的关系分布式系统的基本原理 CAP 必然满足其中一条，这个算法是一致性的保证的基石。算法解决的是一致性问题，无论强一致性还是弱一致性都要保证最终的一致性，算法是一致性的基础。
参考资料：
https://blog.csdn.net/chao2016/article/details/81149674
https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
https://www.jianshu.com/p/d9d067a8a086
https://cloud.tencent.com/developer/article/1352070