一致性算法（paxos、raft）

背景：分布式

 

一致性模型

1.弱一致性：（最终一致性）

    1.1 DNS

    1.1 Gossip

2.强一致性：

    2.1 同步

    2.1 paxos

    2.1 raft（multi-paxos）

    2.1 ZAB（multi-paxos）----与raft相似，心跳发起者相反（raft由master发起心跳，zab由slave发起）

注：强一致性的算法主要是保证：多数派、顺序性

    

 

概念区分：raft、paxos算法实际上是状态机复制的共识算法，raft/paxos/zab + client = 一致性算法

 

paxos算法：

作者论文中模型的概念：

1. Proposal提案，即分布式系统的修改请求，可以表示为[提案编号N，提案内容value]
2. Client用户，类似社会民众，负责提出建议
3. Propser议员，类似基层人大代表，负责帮Client上交提案
4. Acceptor投票者，类似全国人大代表，负责为提案投票，不同意比自己以前接收过的提案编号要小的提案，其他提案都同意，例如A以前给N号提案表决过，那么再收到小于等于N号的提案时就直接拒绝了
5. Learner提案接受者，类似记录被通过提案的记录员，负责记录提案

其他总结：

 

basic-Paxos：

逻辑流程图：

1.客户端发起写请求

2.proposer负责转发（专职人员---表示请求合法性）

3.发送给有投票权的Acceptor

4.Acceptor同意update或者insert，返回proposer，并通知learner记录下来

注：Acceptor才是真正的数据节点，主要保证的是Acceptor数据的一致性

 

multi Paxos：

设计理由：basic paxos的弊端

1.难以实现

2.效率较低（2轮RPC、一轮类似于选举leader、一轮写入请求）

3.活锁（存在多个proposer，就会出现同时提出多个法案，或者说请求，acceptor会选取版本号大的，认为版本号小的过时了，这样就可能出现各个请求由于重试，增大版本号，相互竞争，却都不能写入成功-----通常给定一个随机的等待时间解决，重试之前等待，但是依然不是很优雅）

 

基本流程：（角色未简化）

大致逻辑与basic paxos一致

主要优化：

只有一个proposer----只有一个可以合法发送请求者，这个proposer的高可用性可以通过集群实现，所以会有选举leader流程（确认身份）（启动、异常时），保证不需要每次都进行请求的版本检查，减少一次rpc、不会有请求冲突

 

简化角色：将proposer和acceptor整合成一个角色----分别是角色server的leader和follower

 

 

Raft算法：

设计理由：

1.paxos实现太复杂

2.raft为paxos的简化版

 

1.简化成三个子问题：

    1.1 Leader Election

    1.2 Log Replication

    1.3 Safety

2.重定义角色：

    1.1 Leader

    1.2 Follower

    1.3 Candidate（可以理解成一种中间状态，当Leader挂掉时候，follower想成为leader先要成为Candidate状态）

 

过半原则写入问题：

当机器节点被分为两个集群（网络不通）时，有过半原则；

例如：

3节点+2节点网络断开，3节点的集群可以通过master正常写入

2节点的集群可接收请求，但是写入会失败，因为没有过半，但是2节点的集群也是在运作的，并且也有一个leader，一个follower；由于这个小集群不能写入（不可用），所以还是认为这个完整的集群是只有一个leader的

当网络突然又好了，2节点的小集群发现leader的版本号落后了，所以会选择放弃自己没有commit的数据，同步3节点的集群的数据，达到一致性

 

 

以下两个动画是官方的，可以很好的理解raft原理，这里不再赘述

原理动画：http://thesecretlivesofdata.com/raft/

场景测试：https://raft.github.io/

 

 

注：会降低一点可用性，几百毫秒的不可用（请求timeout）