提到分布式的算法,不得不说下,Paxos算法,在几十年里面,一直是分布式共识的代名词
常见的共识算法,狠毒哦都是基于此改进的,比如Fast Paxos算法 cheap Paxos算法 Raft算法
Paxos算法包含两个部分
一个是Basic Paxos算法,描述的是多节点之间如何根据某个值达成共识
二是Multi-Paxos算法,描述的是多个Basic Paxos实例,如何就一系列的值达成共识
现在,我们先了解Basic Paxos的算法是和如何实现的
假设,我们需要实现一个分布式集群,这个集群交给A B C 来组成,提供只读KV的服务,那么在创建这个只读的变量的时候,就必须对其进行复制,这个值后续也没法进行修改,那么就需要只读变量达成一致才行,所有节点再一起创建这个只读变量
假设有多个客户端进行访问这个系统,试图去创建同一个只读的变量,客户端1试图创建值为3的点,客户端2试图创建值为7的点,那么如何达成各节点的值的一致性呢?
在整体的Basic Paxos算法中,具有一些独特的概念,提案,准备,请求,接收,角色等,最重要的是就是一个角色的概念,因为角色是对Basic Paxos中核心的三个功能的抽象,由接受者对提议的值进行投票,并存储接受的值
Basic Paxos中,有提议者Proposer 接受者Acceptor 学习者Learner三种角色
提议者,提议一个值,用于投票表决,方便演示,一般情况下,这个的实现者是集群中的客户端请求的节点,而不是客户端,因为这样做,对业务代码没有入侵性,我们不需要在业务代码中实现算法逻辑,就好比数据库一样后端的数据
接受者,对每个提议进行投票,并存储接受的值,比如A B C ,往往所有节点都是扮演者,参与共识协商,并接受存储数据
学习者,被告知投票的结果,并直接进行存储,不参与直接投票的过程,学习者是数据备份节点,比如Master-Slave的Slave节点就是
而且在这个模型中,一般一个节点会身兼多个角色,一个三节点的集群,1个节点收到了请求,会作为提议者发起二阶段提交,然后这个节点和另外两个节点作为接受者进行协商共识
这三个角色,对应着是三种不同的功能,提议者代表着是接入和协调的功能,收到客户端请求,发起二阶段提交,进行共识协商
接受者,代表投票协商和存储,进行投票,然后保存’
学习者,不参与协商共识,而是只去接收达成共识的值
如何去达成呢?
假设我们需要进行对人民代表大会上进行一个提案
提交的提案中还得有一个提案的编号,才能起到唯一的标识的作用
整个的共识协商的过程是分为两个阶段进行的,如何进行呢?
假设客户端1的提案请求是1,客户端2的提案请求是5,节点A B收到来自客户端1的准备请求,节点C会先收到来自客户端2的准备请求
那么这时候,我们看第一个阶段的提交工作
准备阶段
首先第一个阶段,看客户端1 2 作为提议者,分别向所有接受者发送包含提案编号的准备请求
在准备请求阶段,是不需要提交提议的值的,只需要提交提案的编号,
然后当AB收到了编号1的提案,节点5收到了编号为5的准备请求
然后各自返回准备好了的响应,不过AB会返回表明自己不会再通过编号小于1的提案,
节点C会返回一个不会通过编号小于5的提案的表明
另外,当节点A B收到了提案编号为5的准备请求的时候,和节点C收到提案编号为1的请求的时候
会进行一些额外的处理
节点A B收到提案编号为5的准备请求的时候,因为提案的编号5大于了之前的1,而且还没有通过任何方案,于是会返回一个尚未提案的响应,并且承诺以后不会再响应提案编号小于等于5的准备请求
而节点C收到了编号1的提案,由于编号1小于之前的准备提案5,于是丢弃了这个请求,不做任何的响应
接受Accept阶段
第二个阶段接受阶段,在客户端1 2 收到大多数的节点的准备响应之后,会发送接受请求
客户端1收到了大多数的接受者的准备响应之后,根据响应中提案编号最大的提案的值,进行设置接受请求的值,而AB返回的是自己没有通过任何的提案,于是提交了请求[1,3]
客户端2收到了大多数接受者的准备响应之后,根据响应中最大的值来设置接受请求中的值,因为这个值来自节点A B C的准备响应都为空,于是将自己的提议值作为了提案的值,发送了请求[5,7]
然后三个客户端的请求处理流程如下
当节点A B C 收到了请求[1,3]的时候,由于提案的提案编号1小于三个节点承诺的能通过提案的最小编号5,于是提案[1,3]被拒绝
当三个节点收到了请求[5,7]的时候,由于提案的编号正好不小于三个节点承诺的能够通过的提案的最小编号5,于是通过了提案[5,7]
这个流程演示下来,就可以看出,最终各个节点就X的值达成了共识,而这个达成,不需要全部节点的参与
本章我们主要了解了一下Basic Paxos的原理
Basic Paxos是通过二阶段提交来保证共识问题
除了共识,Basic Paxos还是实现了容错能力,在少于一半的节点出现故障的时候,集群已经能够通过提案
本质上,提案的大小表示的优先级,根据天的代销,提交者能够保证三个承诺,因为,准备提交的编号小于等于接受者已经响应的准备请求的提案编号,那么承诺不响应这个准备请求,如果接受请求中的提案编号,小于等于接受者已经响应的准备请求的提案编号,承诺不通过这个提案,如果有通过提案,在准备请求的响应中,会包含已经通过的最大编号提案信息
课后思考
如果A B已经通过了提案[5,7],节点C没有通过任何提案,当提案者编号为9的时候,通过Basic Paxos执行SET X =6,会显示什么
