`
michael8335
  • 浏览: 187016 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

paxos 实现

阅读更多
本文主要介绍zookeeper中zookeeper Server leader的选举,zookeeper在选举leader的时候采用了paxos算法(主要是fast paxos),这里主要介绍其中两种:LeaderElection 和FastLeaderElection.

我们先要清楚以下几点
•一个Server是如何知道其它的Server


在zookeeper中,一个zookeeper集群有多少个Server是固定,每个Server用于选举的IP和PORT都在配置文件中
•除了IP和PORT能标识一个Server外,还有没有别的方法

每一个Server都有一个数字编号,而且是唯一的,我们根据配置文件中的配置来对每一个Server进行编号,这一步在部署时需要人工去做,需要在存储数据文件的目录中创建一个文件叫myid的文件,并写入自己的编号,这个编号在处理我提交的value相同很有用
•成为Leader的必要条件

获得n/2 + 1个Server同意(这里意思是n/2 + 1个Server要同意拥有zxid是所有Server最大的哪个Server)
•zookeeper中选举采用UDP还是TCP

zookeeper中选举主要是采用UDP,也一种实现是采用TCP,在这里介绍的两种实现采用的是UDP
•zookeeper中有哪几种状态

LOOKING 初始化状态

LEADING  领导者状态

FOLLOWING  跟随者状态
•如果所有zxid都相同(例如: 刚初始化时),此时有可能不能形成n/2+1个Server,怎么办

zookeeper中每一个Server都有一个ID,这个ID是不重复的,而且按大小排序,如果遇到这样的情况时,zookeeper就推荐ID最大的哪个Server作为Leader
•zookeeper中Leader怎么知道Fllower还存活,Fllower怎么知道Leader还存活

Leader定时向Fllower发ping消息,Fllower定时向Leader发ping消息,当发现Leader无法ping通时,就改变自己的状态(LOOKING),发起新的一轮选举

名词解释

zookeeer Server: zookeeper中一个Server,以下简称Server

zxid(zookeeper transtion id): zookeeper 事务id,他是选举过程中能否成为leader的关键因素,它决定当前Server要将自己这一票投给谁(也就是我在选举过程中的value,这只是其中一个,还有id)

myid/id(zookeeper server id): zookeeper server id ,他也是能否成为leader的一个因素

epoch/logicalclock:他主要用于描述leader是否已经改变,每一个Server中启动都会有一个epoch,初始值为0,当 开始新的一次选举时epoch加1,选举完成时 epoch加1。

tag/sequencer:消息编号

xid:随机生成的一个数字,跟epoch功能相同

Fast Paxos消息流向图与Basic Paxos的对比

消息流向图
•basic paxos 消息流向图
Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)//向所有Server提议
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})//向提议人回复是否接受提议(如果不接受回到上一步)
   |         X--------->|->|->|       |  |  Accept!(N,Vn)//向所有人发送接受提议消息
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)//向提议人回复自己已经接受提议)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
•fast paxos消息流向图

没有冲突的选举过程
Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)//向所有Server提议,所有Server收到消息后,接受提议
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)//向提议人发送接受提议的消息
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

第一种实现: LeaderElection

LeaderElection是Fast paxos最简单的一种实现,每个Server启动以后都询问其它的Server它要投票给谁,收到所有Server回复以后,就计算出zxid最大的哪个Server,并将这个Server相关信息设置成下一次要投票的Server




每个Server都有一个response线程和选举线程,我们先看一下每个线程是做一些什么事情

response线程

它主要功能是被动的接受对方法的请求,并根据当前自己的状态作出相应的回复,每次回复都有自己的Id,以及xid,我们根据他的状态来看一看他都回复了哪些内容

LOOKING状态:

自己要推荐的Server相关信息(id,zxid)

LEADING状态

myid,上一次推荐的Server的id

FLLOWING状态:

当前Leader的id,以及上一次处理的事务ID(zxid)

选举线程

选举线程由当前Server发起选举的线程担任,他主要的功能对投票结果进行统计,并选出推荐的Server。选举线程首先向所有Server发起一次询问(包括自己),被询问方,根据自己当前的状态作相应的回复,选举线程收到回复后,验证是否是自己发起的询问(验证 xid是否一致),然后获取对方的id(myid),并存储到当前询问对象列表中,最后获取对方提议的leader相关信息(id,zxid),并将这些 信息存储到当次选举的投票记录表中,当向所有Server都询问完以后,对统计结果进行筛选并进行统计,计算出当次询问后获胜的是哪一个 Server,并将当前zxid最大的Server设置为当前Server要推荐的Server(有可能是自己,也有可以是其它的Server,根据投票 结果而定,但是每一个Server在第一次投票时都会投自己),如果此时获胜的Server获得n/2 + 1的Server票数, 设置当前推荐的leader为获胜的Server,将根据获胜的Server相关信息设置自己的状态。每一个Server都重复以上流程,直到选出 leader

了解每个线程的功能以后,我们来看一看选举过程
•选举过程中,Server的加入

当一个Server启动时它都会发起一次选举,此时由选举线程发起相关流程,那么每个Server都会获得当前zxid最大的哪个Server是谁,如果当次最大的Server没有获得n/2+1个票数,那么下一次投票时,他将向zxid最大的Server投票,重复以上流程,最后一定能选举出一个Leader
•选举过程中,Server的退出

只要保证n/2+1个Server存活就没有任何问题,如果少于n/2+1个Server存活就没办法选出Leader
•选举过程中,Leader死亡

当选举出Leader以后,此时每个Server应该是什么状态(FLLOWING)都已经确定,此时由于Leader已经死亡我们就不管它,其它的Fllower按正常的流程继续下去,当完成这个流程以后,所有的Fllower都会向Leader发送Ping消息,如果无法ping通,就改变自己的状态为(FLLOWING ==> LOOKING),发起新的一轮选举
•选举完成以后,Leader死亡

这个过程的处理跟选举过程中Leader死亡处理方式一样,这里就不再描述

第二种实现: FastLeaderElection

fastLeaderElection是标准的fast paxos的实现,它首先向所有Server提议自己要成为leader,当其它Server收到提议以后,解决epoch和zxid的冲突,并接受对方的提议,然后向对方发送接受提议完成的消息


数据结构


本地消息结构:

static public class Notification {
long leader;  //所推荐的Server id

long zxid;      //所推荐的Server的zxid(zookeeper transtion id)

long epoch;   //描述leader是否变化(每一个Server启动时都有一个logicalclock,初始值为0)

QuorumPeer.ServerState state;   //发送者当前的状态
InetSocketAddress addr;            //发送者的ip地址
}

网络消息结构:

static public class ToSend {

int type;        //消息类型
long leader;  //Server id
long zxid;     //Server的zxid
long epoch;  //Server的epoch
QuorumPeer.ServerState state; //Server的state
long tag;      //消息编号

InetSocketAddress addr;

}

Server具体的实现

每个Server都一个接收线程池(3个线程)和一个发送线程池 (3个线程),在没有发起选举时,这两个线程池处于阻塞状态,直到有消息到来时才解除阻塞并处理消息,同时每个Server都有一个选举线程(可以发起 选举的线程担任);我们先看一下每个线程所做的事情,如下:

被动接收消息端(接收线程池)的处理:

notification: 首先检测当前Server上所被推荐的zxid,epoch是否合法(currentServer.epoch <= currentMsg.epoch && (currentMsg.zxid > currentServer.zxid || (currentMsg.zxid == currentServer.zxid && currentMsg.id > currentServer.id))) 如果不合法就用消息中的zxid,epoch,id更新当前Server所被推荐的值,此时将收到的消息转换成Notification消息放入接收队列中,将向对方发送ack消息

ack:   将消息编号放入ack队列中,检测对方的状态是否是LOOKING状态,如果不是说明此时已经有Leader已经被选出来,将接收到的消息转发成Notification消息放入接收对队列

主动发送消息端(发送线程池)的处理:

notification: 将要发送的消息由Notification消息转换成ToSend消息,然后发送对方,并等待对方的回复,如果在等待结束没有收到对方法回复,重做三次,如果重做次还是没有收到对方的回复时检测当前的选举(epoch)是否已经改变,如果没有改变,将消息再次放入发送队列中,一直重复直到有Leader选出或者收到对方回复为止

ack: 主要将自己相关信息发送给对方

主动发起选举端(选举线程)的处理:

首先自己的epoch 加1,然后生成notification消息,并将消息放入发送队列中,系统中配置有几个Server就生成几条消息,保证每个Server都能收到此消息,如果当前Server的状态是LOOKING就一直循环检查接收队列是否有消息,如果有消息,根据消息中对方的状态进行相应的处理。

LOOKING状态:

首先检测消息中epoch是否合法,是否比当前Server的大,如果比较当前Server的epoch大时,更新epoch,检测是消息中的zxid,id是否比当前推荐的Server大,如果是更新相关值,并新生成notification消息放入发关队列,清空投票统计表; 如果消息小的epoch则什么也不做; 如果相同检测消息中zxid,id是否合法,如果消息中的zxid,id大,那么更新当前Server相关信息,并新生成notification消息放入发送队列,将收到的消息的IP和投票结果放入统计表中,并计算统计结果,根据结果设置自己相应的状态

LEADING状态:

将收到的消息的IP和投票结果放入统计表中(这里的统计表是独立的),并计算统计结果,根据结果设置自己相应的状态

FOLLOWING状态:

将收到的消息的IP和投票结果放入统计表中(这里的统计表是独立的),并计算统计结果,根据结果设置自己相应的状态

了解每个线程的功能以后,我们来看一看选举过程,选举过程跟第一程一样
•选举过程中,Server的加入

当一个Server启动时它都会发起一次选举,此时由选举线程发起相关流程,通过将自己的zxid和epoch告诉其它Server,最后每个Server都会得zxid值最大的哪个Server的相关信息,并且在下一次投票时就投zxid值最大的哪个Server,重复以上流程,最后一定能选举出一个Leader
•选举过程中,Server的退出

只要保证n/2+1个Server存活就没有任何问题,如果少于n/2+1个Server存活就没办法选出Leader
•选举过程中,Leader死亡

当选举出Leader以后,此时每个Server应该是什么状态 (FLLOWING)都已经确定,此时由于Leader已经死亡我们就不管它,其它的Fllower按正常的流程继续下去,当完成这个流程以后,所有的 Fllower都会向Leader发送Ping消息,如果无法ping通,就改变自己的状态为(FLLOWING ==> LOOKING),发起新的一轮选举
•选举完成以后,Leader死亡

这个过程的处理跟选举过 程中Leader死亡处理方式一样,这里就不再描述
【转自淘宝核心团队博客】:http://rdc.taobao.com/blog/cs/?p=162
分享到:
评论

相关推荐

    java初级笔试题-paxos:Python和Java中的简单Paxos实现

    java笔初级试题基本的Paxos 汤姆·科卡涅 &lt;&gt; v2.0,2013 年 1 月 介绍性说明 这个存储库包含我第一次尝试提供有用且具有教育意义的 Paxos 实现的结果。 存储库的状态非常好,仍然可以发挥其预期的作用,但设计...

    人工智能-项目实践-多线程-Paxos算法的多线程实现.zip

    4. **Chubby锁服务**:Google基于Paxos实现的分布式锁服务,它在Paxos基础上进行了许多工程上的优化。 5. **ZooKeeper的ZAB协议**:Apache ZooKeeper使用ZAB(Zookeeper Atomic Broadcast)协议,它是Paxos的一个...

    基于paxos的源码

    深入理解Paxos源码有助于我们掌握其实现细节,以及如何在实际项目中应用一致性算法。通过阅读和分析`libpaxos`,我们可以学习如何处理网络延迟、节点故障以及如何确保在分布式环境中的一致性。这对于我们设计和实现...

    云计算:C++实现的可直接运行paxos算法

    通过C++实现,开发者可以更深入地了解Paxos的工作原理,并将其应用于自己的分布式系统设计中,以实现强一致性、高可用性和容错性。 总的来说,这个C++实现的Paxos算法项目为学习和研究Paxos提供了一个实践平台,...

    paxos算法学习.docx

    然而,存在一些公开的Paxos实现,如SourceForge上的libpaxos项目,由意大利开发者Marco实现,是一个开源库,虽然目前尚未广泛应用于商业,但具有潜力。另一个实现是北京大学天网实验室的Debby项目,它使用ICE框架...

    paxos:Paxos的实现

    将Paxos实现于Akka中,可以利用其强大的并发处理能力和网络通信机制,创建可靠的分布式一致性服务。 **Paxos的基本概念** 1. **提案者(Proposer)**:提案者是提议新值的节点。它可以发起一个新的提案,并尝试获得...

    paxos:纯JavaScript中的Multi-Paxos实现

    在这个名为“paxos”的项目中,开发者用纯JavaScript实现了一个Multi-Paxos的版本,使得在JavaScript环境中也能应用Paxos算法。Multi-Paxos是Paxos的一种优化,它允许在一组副本节点上进行连续的、高效的决策,从而...

    使用GO实现Paxos共识算法的方法

    Paxos共识算法是一种分布式系统中解决一致性问题的算法,它允许系统...此外,对于从事分布式系统研发的工程师来说,阅读相关开源项目中的Paxos实现代码以及实际编写和调试Paxos代码都是加深理解和提高技能的重要手段。

    paxos 算法解释

    - **Multi-Paxos**:简化Paxos的实现,通过复用同一编号的提案,避免了每次决策都需要多轮通信的问题。 - **Fast Paxos**:在多数派节点已经就一个值达成一致的情况下,可以快速达成决策,减少了通信次数。 - **Raft...

    Paxos 共识算法的Rust实现

    Paxakos 是基于 Leslie Lamport 的Paxos的分布式共识算法的纯 Rust 实现。它使分布式系统能够一致地修改其网络中的共享状态,即使在出现故障的情况下也是如此 为了使用 Paxakos,需要实现特征 [ LogEntry]、[ State...

    Paxos算法中文翻译

    Paxos算法是一种在异步分布式系统中实现共识(Consensus)的算法,由Leslie Lamport提出。它能够确保系统中的多个节点即使在某些节点出现故障时,也能就某个值(例如一个操作请求)达成一致意见。Paxos算法的核心...

    cheap-paxos.pdf_Paxos算法_

    《廉价Paxos:一种高效的分布式一致性算法》 在分布式系统中,一致性是核心...无论是对分布式系统的初学者还是经验丰富的开发者,都能从中受益,学习如何在实际应用中有效地实现一致性保证,提升系统的稳定性和效率。

    Paxos implementation

    Paxos算法是一种分布式系统中用来实现一致性协议的经典算法。该算法由莱斯利·兰伯特(Leslie Lamport)于1990年提出,旨在解决分布式系统中不同节点间可能出现的故障和通信延迟问题,从而实现可靠的决策过程。Paxos...

    Multi-Paxos-UDP

    多Paxos实现##概述Multi-Paxos是Paxos的用例之一。 在实施多人Paxos之前,我以前已经在实现并发布了Single-Decree-Paxos。 对于用户来说,在尝试理解多用户之前,必须先了解Single-Decree-Paxos,这一点很重要。 该...

    Fast Paxos(pdf)

    它将达成共识所需的消息延迟从三次减少到了两次,通过改进经典Paxos算法的执行步骤,实现了更快的一致性决议。同时,TLA+的引入为算法的准确实现和验证提供了保障。为了实施该算法,需要考虑消息延迟、法定人数的...

    paxos的开源实现

    ### paxos的开源实现:Commodifying Replicated State Machines with OpenReplica #### 引言与背景 在分布式系统领域,确保数据的一致性和系统的可靠性是核心挑战之一。随着云计算成为主流的商业部署环境,对协调...

    zookeeper基于paxos算法的资料。

    在实际的Zookeeper实现中,有两类学习者:Follower和Leader。Follower是普通的服务器节点,它们接收提议并参与投票;Leader则是负责协调整个集群的节点,发起提案并处理客户端请求。 Paxos算法的执行流程包括提议...

    Paxos图解(xmid图解)

    3. **状态机复制**:通过在各个节点上实现状态机,Paxos可以保证状态机的复制状态一致性。 **Xmind图解** Xmind图解通常用于可视化Paxos算法的流程,包括各角色的交互、阶段划分以及决策过程。它可以帮助我们更好...

    paxos_simple:用 Go 编写的简单 Paxos 算法模拟

    通过这个简单的Paxos实现,开发者可以更深入地理解Paxos算法的工作原理,这对于构建分布式系统和理解一致性问题至关重要。此外,由于代码没有经过优化,这使得初学者更容易阅读和理解,有助于学习分布式一致性协议的...

    自动动手写zookeeper选举算法与心跳同步

    在Zookeeper的Fast Paxos实现中,每个节点都可以作为提议者或接受者。当一个节点想要提出新的状态更新时,它会发送一个提议到集群中的其他节点。如果大多数节点(超过半数)接受了这个提议,那么提议就会被确认,并...

Global site tag (gtag.js) - Google Analytics