1. 介绍

近几年来一些分布式算法越来越多的投入到生产环境中用于解决分布式场景下的一致性问题,这里也简单做一下介绍。

2. 协议介绍

2.1 totem协议

这个协议相比于其他协议来说现在不是那么流行,不过其思路还是值得学习。

基于该协议实现的软件有:

  1. corosync
  2. pacemaker

主要思想:所有节点形成一个令牌环,拿到token的节点才可以发送信息,这样等于避免了并发带来的一致性问题。该算法在网络通信中也有很多应用,参考Totem协议(SRP/RRP)讲解

2.2 paxos协议

比较流行的分布式一致性协议,论文1990年就出来了。当说议会(quorum)和拜占庭将军问题的时候,都是以故事形式说明该协议。

paxos也有一些发展,主要分为两类:

basic paxos

两阶段的基本实现,过程比multi paxos复杂些,效率也较低。
basic paxos的角色中,谨记一个原则:每个acceptor维护了自己知道的最大的协议号 vx,且每个acceptor不会同意任意一项小于等于vx的协议的prepare请求。

basic paxos是由client发起的同步过程,在两阶段返回前,client不能得到成功的返回。

  • 第一阶段a(发送prepare),proposer向acceptor提出一个协议,这里的协议可以理解为client发送过来期望多节点一起保存的一致性内容,举例:一句日志,某个配置等
  • 第一阶段b(计算协议vn),根据半数以上acceptor的返回,选择 max{va,vb,vc} = vn,这里的vx理解为这个acceptor已知的最大协议号,acceptor一旦返回了vx后,则表明: - acceptor在接下来的prepare请求中,会返回的vx自增1 - acceptor不会accept任何小于vx的协议请求,只会accept大于vx的协议请求
  • 第二阶段a(发送决议好的vn),把vn发送给acceptor
  • 第二阶段b,在半数acceptor返回了成功后,再返回client成功通过协议

下图演示client一次请求的决议过程(PS:每条竖线代表一个对象,这里acceptor有3个)。分布式场景下会有多个client并发的发送信息,来请求决议,这里我们就看一个。

在分布式场景下,client给多个proposer发送请求进行议会决议,最后得到多数派的结果。

缺点:有一些错误场景中,proposer会互相锁住对方的递交。所有proposer交替提交,导致一直没法决议得出多数派的结果。交替尝试投票选举的结果如下。

PS: 新来的决议的序号vn都比老的要新,acceptor会接受新的。

multi paxos:

multi-paxos 在basic paxos的二阶段上引入了一个机制,让自己看起来像一阶段一样,并且解决了交替提交无法得出多数派的问题。该机制主要就是引入了一个leader,选举Leader实际上就是之前的一阶段了。也就是说leader选举有可能由于和之前basic paxos一样的活锁导致一直没法选出leader。当然可以用一些方式来实现第一次的leader选举,比如发现冲突后,不同proposal随机休眠一段时间再提交。或者腾讯开源的Phxpaxos里面在冲突时拒接提交来达成leader选举。

multi paxos本质是将多次proposal利用leader来统一成一次,避免basic paxos的缺点,同时较少的通信业改进了效率。

资料参考:比较raft ,basic paxos以及multi-paxos

2.3 raft协议

raft和multi paxos选定leader后的行为是一样的,raft可以理解为特殊的multi paxos,就是选举leader方式的差别。multi paxos实际上要求任何一个节点都可以成为leader(也就是说具体看实现方式了,但是会有一些leader选举的约束)。raft选举leader就和Multi paxos差别为:

  1. raft仅允许日志最多的节点当选为leader,而multi-paxos则相反,任意节点都可以当选leader
  2. raft不允许日志的空洞,这也是为了比较方便和拉平两个节点的日志方便,而multi-paxos则允许日志出现空洞