Paxos、Raft、ZAB算法

Paxos、Raft、ZAB算法 强一致性

主从同步复制

1.Master接受写请求

2.Master复制日志至slave

3.Master等待，直到所有从库返回

问题：一个节点失败，Master阻塞，导致整个捷群不可用，保证了一致性，可用性缺大大降低

多数派

每次写保证写入大于N/2个节点，每次读保证从大于N/2个节点中读

问题：在并发环境下，无法保证系统正确性，顺序非常重要

Paxos 一、Paxos算法背景

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题

Basic PaxosMulti PaxosFast Paxos 角色

Client：系统外部角色，请求发起者。像民众Propser：接受Client请求，向集群提出提议（propose）。并在冲突发生时，起到冲突调节的作用。像议员，替民众提出议案Accpetor（Voter）：提议投票和接受者，只有在形成法定人数（Quorum，一般即为majority多数派）时，提议才会最终被接受。像国会Learner：提议接受者，backup，备份，对集群一致性没什么影响。像记录员 Basic Paxos

步骤、阶段（phases）

Phase la:Prepare

proposer提出一个提案，编号为N，此N大于这个proposer之前提出提案编号。请求acceptors的quorum接受

Phase 1b:Promise

如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝

Phase 2a:Accept

如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容

Phase 2b:Accepted

如果此acceptor在此期间没有收到任何大于编号大于N的提案，则接受此提案内容，否则忽略

基本流程

部分节点失败，但达到了Quoroms

Proposer失败

潜在问题，活锁（liveness）或dueling

问题：实现难、效率低（2轮RPC）、活锁

Multi Paxos

新概念，Leader：唯一的propser,所有请求都需经过此Leader

基本流程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-exCWgXQn-1642729366853)(C:Users67546AppDataRoamingTyporatypora-user-imagesimage-20220120180534722.png)]

第一次竞选lead，后续提案都通过lead来提

减少角色，进一步简化

Raft

简单版本的Multi Paxos

划分成三个子问题

Leader ElectionLog ReplicationSafety

重定义角色

LeaderFollowerCandidate

原动画解释
场景测试

ZAB

基本与raft相同

在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称之为term

实现上也有些许不同：如raft保证日志连续性，心跳放心为leader至follower。ZAB则相反