Distributed Systems-leader based分布式一致性协议

  1. 云栖社区>
  2. 博客>
  3. 正文

Distributed Systems-leader based分布式一致性协议

feilengcui008 2016-03-10 09:41:02 浏览868
展开阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/50843779

上一篇文章推导了基本Paxos算法,并引出了在实际使用中其存在的问题,然后说明了leader-based分布式一致算法的优势。这篇文章分析一下选主的本质,选出一个主对整个算法的影响,以及采用选主会存在的问题以及基本Paxos协议是怎么样保证这些问题不会影响一致性的。

1.为什么选主

至于为什么选主?个人认为有如下原因:

  • 避免并发决议导致的livelock和新丢失的问题

  • 可以采用一定方法在选主时(raft),选主中或者选主后保证leader上有最新的达成多数派(达成多数派应该用多数派已经将值写入持久化日志来判定),这样可以优化针对同一个项的读请求,不然每次客户端读请求也需要走一遍基本Paxos

  • 选出leader可以保证在一个leader的统治期间内只有这一个leader可以接收客户端请求,发起决议(至于脑裂的问题,后面会分析),

2.不同的选主算法,其本质是什么?

前面说了在一个leader统治期间内,不可能存在多个leader同时对一个项达成多数派(如果一个leader也没有自然满足,包括脑裂后面会分析到也是满足的),但是对于选主本身来说,实际上其本质上就是一个分布式一致性问题,并且可能有多个proposer并发提出选主决议,所以可以使用基本Paxos来解决,这就回到了基本的Paxos算法了!所以我们需要为每次选主决议编号,比如raft算法的term,这个实际上就对应基本Paxos算法的proposal id。

3.选主后对整个算法造成什么影响?

前面提到了”选出leader可以保证在一个leader的统治期间内只有这一个leader可以接收客户端请求,发起决议”。这样实际上基本Paxos的第一阶段prepare就没有必要了,因为对于下一个项来说,在这个leader统治期内,在达成多数派之前,不可能有其他人提出决议并达成多数派,所以可以直接使用客户端的值进入第二阶段accept。

4.选主可能会导致的问题?

最大的问题应该是脑裂了,也就是说可能存在多个分区多个leader接收客户端响应,但是由于多数派的限制,只能最多有一个分区能达成多数派。我们假设最简单的情况,A/B/C/D/E五台机器,两个分区P1有三台A/B/C和P2有两台D/E,那么可能的情况是:

(1).P1有leader;P2没有leader

(2).P1有leader;P2也有leader

显然由于多数派的限制,只有P1可能达成决议

5.新的leader选出来后的操作

一般来说,新的leader选出来后,我们需要对leader进行日志恢复,以便leader决定下一次客户端请求的时候该用哪个日志槽位或者说哪个项吧,这里也是不同的算法差异较大的地方,比如raft,viewstamped replication,zab以及lamport 《Paxos Made Simple》里面第三节描述的方法。在lamport论文的描述中,还是采用基本的Paxos,对未明确知道达成多数派的项重新走一遍基本Paxos算法,具体可以参照原论文,细节还是挺多。对于raft来说,由于其保证日志是连续的,且保证在选主的时候只选择具有最新的日志的机器,所以选主之后,新的leader上的日志本身就是最新的。

下一篇会着重分析在新的leader选举后,新leader怎么恢复日志记录以及怎么确定已提交的日志,这一点还是通过对比lamport在《Paxos Made Simple》第三节提到的方法以及raft中的实现来说明。

网友评论

登录后评论
0/500
评论
feilengcui008
+ 关注