简述paxos算法的实现过程

‘壹’ 如何浅显易懂地解说 Paxos 的算法

Paxos算法解决的问题是在一个可能发生消息可能会延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。

分析Paxos算法的目的

Paxos算法的目的是为了解决分布式环境下一致性的问题。多个节点并发操纵数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性（系统如何就一个值达到统一）。

Paxos算法中，可分为4种角色：

• Proposer：提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。

• Acceptor：提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值。

• Client：产生议题者，Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。

• Learner：最终决策学习者，最终学习的目标是Acceptor们最终接受了什么议题？

Paxos算法的原理

例如：公司商定年会举办的地点，每个人都可以提出建议。在现实环境中我们可以在一个会议室共同讨论或在微信群中讨论（基于内存共享方式）；但在基于消息传递的分布式环境中每个人只能通过手机短信与其它人通过。如何在这种会延迟、丢失的环境中确定一个年会举办地点。

Paxos算法是这样解决这个问题：

每个人都可以提出建议、同意建议、接受建议

少数服从多数。只要建议被多数人同意即可确定该建议。

于是确定以下讨论方式：

• 只有被提出来的建议才能被大家同意。

• 最终只能确定一个建议。

• 如果某个人认为大家同意了某 个建议，那么这个建议必须真的是被大家同意的。

Paxos算法图解



在实现环境中会通过一次提议，选择一个Leader。后续所有的提议都只能由Leader提出。

原来paxos算法里的角色都是这样的不靠谱，不过没关系，结果靠谱就可以了。该算法就是为了追求结果的一致性。

原文链接：什么是Paxos算法？Paxos算法是区块链核心算法之一

‘贰’ paxos算法是什么

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是LaTeX中的＂La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

兰伯特提出的Paxos算法包含2个部分：

一个是Basic Paxos算法，描述的是多节点之间如何就某个值（提案Value）达成共识；

另一个是Multi-Paxos思想，描述的是执行多个Basic Paxos实例，就一系列值达成共识

可因为兰伯特提到的Multi-Paxos思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。Basic Paxos是Multi-Paxos思想的核心。

(2)简述paxos算法的实现过程扩展阅读

背景

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos算法就是一种基于消息传递模型的一致性算法。

‘叁’ 如何浅显易懂地解说 Paxos 的算法

Paxos真的并不是很容易理解，而且最初版本的Paxos也不能实现，相对而言一些变种算法更加容易理解，而且在工程实现上也比较简单。

其实看论文确实是最有效的，但却不是最高效的。理解运作过程也好，推导过程也好，大家的回答都是为了帮助大家更高效的掌握这门算法。大家的回答已经很好， 我这里作为补充，也是算另一个角度，帮助大家去理解paxos的数学推导过程，写了这么一篇文章：Paxos理论介绍(1): 朴素Paxos算法理论推导与证明 - 分布式一致性与高可用实践 - 知乎专栏。希望能帮到大家。

‘肆’ 一致性算法（Paxos、Raft、ZAB)

一致性算法（Paxos、Raft、ZAB)

什么是一致性

1、弱一致性
a、最终一致性
i、DNS（Domain Name System）
j、Gossip（Cassandra的通信协议）

以DNS为例：

2、强一致性
a、同步
b、Paxos
c、(multi-paxos)
d、ZAB(multi-paxos)

DNS 就是一种最终一致性，比如 上图中 增加一条记录： www.hyb.small.com , 我们从其他DNS服务器一时会读取不到，但是过一会就会读取得到了。

数据不能存在单点上。
分布式系统对fault tolerence的一般解决方案是state machine replication 。

准确的来说应该是 state machine replication 的共识（consensus）算法。

paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为

主从同步复制

1、Master 接受写请求
2、Master 复制日志到slave
3、Master 等待，直到所有从库返回

问题：

任何一个节点失败，哪怕是从节点（Slave）同步失败，都会导致整个集群不可用，虽然保证了一致性，但是可用性却大大降低

基本想法：
a、多数派：
每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读。
比如5个节点，每次写大于3个节点才算成功；读也是大于3个节点才算成功。

b、多数派还不够！
在并发环境下，无法保证系统正确性，顺序非常重要。比如下图的 Inc 5; Set 0; 执行顺序乱了，结果就会引发错乱。

Lesile Lamport,Latex的发明者。

为描述Paxos算法早昌，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这种事上，所以无论是议员、议长或者传递消息的时间。

Paxos

1、Basic Paxos
2、Multi Paxos
3、Fast Paxos

强一致性算法---Basic Paxos

角色丛睁晌介绍：

Client:系统外部角色，请求发起者。像民众

Propser: 接渗锋受Client 请求，向集群提出提议(propose)。并在冲突发生时，起到冲突调节的作用。像议员替民众提出议案

Accpetor(Voter): 提议投票和接收者，只有在形成法定人数(Quorum,一般即为majority 多数派)时，提议才会最终接受，像国会。

Learner:提议接受者，backup，备份，对集群一致性没什么影响，像记录员；

步骤、阶段(phases):
1、Phase 1a:Prepare
proposer 提出一个提案，编号为N，此N 大于这个proposer之前提出提案编号，向acceptors请求同意，要求有quorum接受的才行。

2、Phase 1b:Promise
N 必须大于此acceptor之前接受的任何提案编号，才会接受，否则会拒绝。

3、Phase 2a: Accept
如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N ,以及提案内容。

4、Phase 2b:Accepted
如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。

流程图如下：

操作步骤如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;

1、Acceptor部分节点失败，但达到了Quoroms，此时仍然会成功。

如果有一个Acceptor因为各种原因挂掉了，3个Acceptors变成了2个Acceptors，还是满足>n/2 的要求，所以还是会成功。

2、Proposer失败，上一次记录不会被写入Proposer表，然后重新开启一个新的Proposer，来替代上次的Proposer来处理未完成请求，此时编号已经增加为2，也就是Prepare(2)

Basic Paxos when an Proposer fails
如果Proposer 在发送了一条Accept消息之后，但是还没收到Accepted消息之前就挂掉了，只有一个Acceptor接收到了Accept消息。那么整个Paxos协议就没法进行下去了，这时一个新的Leader（Proposer）会被选举出来，重新开始一轮新的共识。

Basic Paxos潜在的问题是：活锁（liveness）或eling

Basic Paxos很有可能出现这种情况：
1、议员A(proposer A)说我们来讨论提案1，大部分议员说：“好，我们来讨论提案1”；
2、但是此时议员A还没有说内容是什么，这时候又来了一个议员B，又来说：“我们来讨论提案2”；这时候大部分还没有接受提案1，提案2的编号是大于提案1的，这时候大部分还没有接受议案2；
3、这时候议员A以为网络断了，然后把编号改下，内容不变然后提出议案3；然后议案4、议案5....
这样就形成了活锁。
解决活锁的方法是用Random的timeout，当两个冲突的时候用一个随机的等待时间；当自己提议未生效时，再发起提议等待几秒。

Basic-Paxos是一个无限循环的2PC，1条日志的确认至少需要2个RTT + 2次落盘（1次是prepare的广播与回复，1次是accept的广播与回复）。

Basic Paxos when multiple Proposers conflict
最后再描述一个最复杂的情况，即有多个Proposers认为他们是Leaders，并不断的发送Prepare请求。为什么会有多个Leaders呢？ 有可能一个Proposer当了一段时间Leader之后挂掉了，新的Proposer被选为Leader继续新的一轮共识。后面挂掉的Proposer又恢复了，它认为自己还是Leader，所以继续发送Prepare请求。

Basic Paxos的问题
难实现（角色太多）、效率低（2轮RPC）、活锁问题

Multi Paxos:
新概念，Leader;唯一的propser，所有请求都需经过此Leader;

只有一个Proposer，没有第二个Proposer； 这个Proposer就是Leader,没人跟他抢;

再者分布式系统必须串行执行所有提议，否则就会出现前面说的顺序问题。

--------First Request(第一次执行)----------
Request
Prepare(N) //选Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

--------Following Request(第二次或者以后)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

第二次或者以后，就不用再选Leader了 直接执行Request 请求，由Leader 发出议案。
如果Leader 挂了 就选下一个总统Leader(N+1)

减少角色，进一步简化，在Basic-Paxos中我们区分了很多角色，有Clients、Proposers、Acceptors、 Learners，实际上Proposers、Acceptors 、Leanrners可以合并成一个，统称为Server，下面是合并之后的序列图。

Multi-Paxos when roles are collapsed and the leader is steady
同样的，当Leader很稳定的时候，我们可以在接下来的执行中忽略Phase 1. 如下图所示：

Raft
1、划分三个子问题
a、Leader Election
b、Log Replication
c、Safely
2、重定义角色
a、Leader
b、Follower
c、Candidate

原理动画解释： http://thesecretlivesofdata.com/raft
场景测试： https://raft.github.io

Raft 是比 Multi Paxos 还要简单的一个版本
一致性并不代表完全正确性！三个可能结果：成功，失败，unknown

详细内容参考：
https://www.jianshu.com/p/6cd41fe0b8f6

强一致性算法--ZAB
基本与raft相同。在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称为term。实现上也有些许不同：如raft保证日志连续性，心跳方向为leader至follower，ZAB则相反。