一致性算法（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)
image.png
DNS 就是一种最终一致性，比如 上图中 增加一条记录：www.hyb.small.com, 我们从其他DNS服务器一时会读取不到，但是过一会就会读取得到了。
分布式系统的问题
数据不能存在单点上。
分布式系统对fault tolerence的一般解决方案是state machine replication 。
准确的来说应该是 state machine replication 的共识（consensus）算法。
paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为
强一致性算法---主从同步
主从同步复制
1、Master 接受写请求
2、Master 复制日志到slave
3、Master 等待，直到所有从库返回
image.png
问题：
任何一个节点失败，哪怕是从节点（Slave）同步失败，都会导致整个集群不可用，虽然保证了一致性，但是可用性却大大降低
强一致性算法--多数派
基本想法：
a、多数派：
每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读。
比如5个节点，每次写大于3个节点才算成功；读也是大于3个节点才算成功。
b、多数派还不够！
在并发环境下，无法保证系统正确性，顺序非常重要。比如下图的 Inc 5; Set 0; 执行顺序乱了，结果就会引发错乱。
image.png
强一致性算法---Paxos
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的提案，则接受此提案内容，否则忽略。
流程图如下：
image.png
image.png
操作步骤如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;
1、Acceptor部分节点失败，但达到了Quoroms，此时仍然会成功。
image.png
如果有一个Acceptor因为各种原因挂掉了，3个Acceptors变成了2个Acceptors，还是满足>n/2 的要求，所以还是会成功。
image.png
2、Proposer失败，上一次记录不会被写入Proposer表，然后重新开启一个新的Proposer，来替代上次的Proposer来处理未完成请求，此时编号已经增加为2，也就是Prepare(2)
image.png
Basic Paxos when an Proposer fails
如果Proposer 在发送了一条Accept消息之后，但是还没收到Accepted消息之前就挂掉了，只有一个Acceptor接收到了Accept消息。那么整个Paxos协议就没法进行下去了，这时一个新的Leader（Proposer）会被选举出来，重新开始一轮新的共识。
image.png
Basic Paxos潜在的问题是：活锁（liveness）或dueling
Basic Paxos很有可能出现这种情况：
1、议员A(proposer A)说我们来讨论提案1，大部分议员说：“好，我们来讨论提案1”；
2、但是此时议员A还没有说内容是什么，这时候又来了一个议员B，又来说：“我们来讨论提案2”；这时候大部分还没有接受提案1，提案2的编号是大于提案1的，这时候大部分还没有接受议案2；
3、这时候议员A以为网络断了，然后把编号改下，内容不变然后提出议案3；然后议案4、议案5....
这样就形成了活锁。
解决活锁的方法是用Random的timeout，当两个冲突的时候用一个随机的等待时间；当自己提议未生效时，再发起提议等待几秒。
image.png
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请求。
image.png
image.png
强一致性算法 ---Multi Paxos
Basic Paxos的问题
难实现（角色太多）、效率低（2轮RPC）、活锁问题
Multi Paxos:
新概念，Leader;唯一的propser，所有请求都需经过此Leader;
image.png
image.png
只有一个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)
Multi-Paxos when roles are collapsed
减少角色，进一步简化，在Basic-Paxos中我们区分了很多角色，有Clients、Proposers、Acceptors、 Learners，实际上Proposers、Acceptors 、Leanrners可以合并成一个，统称为Server，下面是合并之后的序列图。
image.png
image.png
Multi-Paxos when roles are collapsed and the leader is steady
同样的，当Leader很稳定的时候，我们可以在接下来的执行中忽略Phase 1. 如下图所示：
image.png
强一致性算法---Raft
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则相反。
