i3geek.com
闫庚哲的个人博客

大话Paxos——分布式一致性算法

Paxos是一种基于消息传递且具有高度容错性的一致性算法,在分布式当中应用的十分广泛。对于初学者来说理解paxos还是十分吃力的,因此本文主要是以通俗易懂的方式来介绍该算法,由浅及深来理解该算法。

背景

在分布式集群中,很难保障数据的一致性。在以往的单节点服务中,通常使用锁来实现,当发生并发冲突时 通过对锁的持有获得对象的操作权,从而保证数据在同一时刻只允许被一个请求操作。但是在集群中,若同样采用锁的机制,那么需要一台节点用来管理分配锁,当其他节点进行请求前,首先去获取锁从而获得执行权。但是这样会产生单节点问题,即若管理锁的节点down掉,那么整个集群将无法工作;同时,由于锁的机制会使整个集群变成串行化单节点的形式,失去了集群的意义。

所以,在集群中需要一种高容错的分布式一致性算法,因此提出了Paxos算法,一种使用少数服从多数思想的算法。下面用一个例子阐述下该算法的主要实现原理。

通俗理解

问题

假设某一班级中的30名同学在讨论假期旅游的目的地,每个人都有自己想去的城市或景点,为了得出统一的答案,最简单的办法就是投票,在班级QQ群中建立一个投票,按照少数服从多数的原则根据投票结果指定方案。当然这种方法类似于“共享内存”实现的一致性,可是存在很大一个弊端,由于网络是不稳定的,很可能负责投票的QQ服务器down掉了,甚至是部分同学“失联”了,这样整个投票的机制就无法进行下去了。所以,为了保证强容错性,要保证所有学生之间点对点通信(比如发送手机短信),这样不仅去除了投票服务器,即使少于半数的人手机关机了或者不参与投票,那么其他人也可以得出最终的结果。

设计

具体的设计方案如下:

首先进行角色划分,从这30名学生中,选择出5名学生(也可以是30名学生外的5人)做为组长,其余的25人做为组员。5名组长间是互相不可以通信的,只负责和25名队员做通信并交流旅游目的地(同一时刻一个组长只能与一个组员建立沟通);25名组员则负责分别向5名组长发送信息询问旅游目的地或告知自己倾向的旅游目的地。

组员的职责

第一步(申请阶段):分别向5个组长发送信息,申请进行沟通。每个组长任何时刻只能和一个组员进行沟通,组长会按照时间的顺序,与最后(最新)收到信息的队员进行沟通。组长是一个喜新厌旧的人,很有可能在沟通中出现了更新的短信,则会与短信更新的组员进行交流。

因此组员在发出申请短信后,会收到两种回复:可能是说你这短信太旧了,不与你沟通;可能是说你这短信是最新的,与你沟通。对于组员来说必须超过半数以上的组长(即超过3名以上)同意沟通了,才可以进入下一步骤。否则,会一直发送短信争取沟通权。

因为需要至少半数以上组长同意才可以进入第二步,且每名组长只能和一名组员对话,因此任何时候都不可能有两名组员同时进入第二步。(当然可以通过狂发短信来抢夺沟通权)

第二步(沟通阶段):对于这个获得沟通权的同学,组长(不一定是全部5个组长,但是超过半数)会把决定的旅游目的地(或还没有决定)发送给该同学。因此可以看出,组长直接是无需沟通的。当该同学收到结果后,可能有以下几种情况:

(1)与该同学沟通的组长都还没有决定旅游目的地。此时该同学把自己希望的旅游目的地发送给组长。

这时可能收到两种结果:1、半数以上组长都同意了,那么表示该同学的提议通过,整个过程结束。(其他同学早晚会收到这个消息的)2、同意组长没有超过半数,那么表示可能组长网络出问题,可能被其他组员抢走了沟通权,此时需要从第一步申请阶段重新开始。

(2)至少有一个组长决定了旅游目的地。这时可能收到两种结果:1、有的旅游目的地被半数以上的组长同意了(比如3个组长同意去A,1个组长同意去B,另1个组长没有回复)那么最终超过半数的提议(即旅游目的地是去A)通过,并结束整个过程。2、若没有超过半数以上的旅游目的地(比如2个组长同意去A,1个同意去B,1个同意去C,1个没有回应),此时Paxos采用后者认同前者的策略,以避免决定过程永无止境,该同学会给组长们发信息告知决定最新收到的旅游目的地。(比如2分钟前收到去B,1分钟前收到去A,则回复去A)

组长的职责

第一步(申请阶段):组长只会与最新收到申请短信的组员进行沟通

第二步(沟通阶段):组长会把自己确定好(或没有确定)的提议发送给各个组员,之后接收组员发回来的目的地,和已有的进行时间比较,保留最新的结果

真正的Paxos

Paxos中的Acceptor就相当于上面的组长,Proposer就相当于上面的组员(同学),epoch编号就相当于申请的发送时间。

但是从流程中可以发现,Paxos最耗时的地方就是需要半数以上同意沟通了才进入第二步,因此,在一开始所有人都疯狂的发申请信息,这样每个组长收到的最新信息都是不同的,很难达成一致,为了减少这个时间提出了Fast Paxos算法

赞(1)
未经允许不得转载:爱上极客 » 大话Paxos——分布式一致性算法
分享到: 更多 (0)

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    一言不发岂能证明我来过了?!

    中医秘方7个月前 (12-12)回复
  2. #2

    这样的博客让人禁不住一天来几次!

    促美优品7个月前 (12-18)回复