zookeeper是hadoop下面的一个子项目, 用来协调跟hadoop相关的一些分布式的框架, 如hadoop, hive, pig等, 其实他们都是动物, 所以叫zookeeper(本人歪歪).

zookeeper其实是集群中每个节点都维护着一棵相同的树, 树的结构跟linux的目录结构的概念差不多, 以/为跟节点, 下边可以扩展任意的节点和叶子节点, 每个节点都可以写入数据. 基于zookeeper的分布式锁的实现, 其实是得益于zookeeper同步文件的强大性, 我们相信每时每刻我们访问zookeeper的树时, 相同节点返回的数据都是一致的. 这要靠zookeeper内部的一些算法来实现. 特别是leader的选举算法, 这里就不说了, 感兴趣的话可以去搜索一下看看.

我们知道了zookeeper集群的每个节点的数据都是一致的, 那么我们可以通过这些节点来作为锁的标志.

首先给锁设置一下API, 至少要包含, lock(锁住), unlock(解锁), isLocked(是否锁住)三个方法

然后我们可以创建一个工厂(LockFactory), 用来专门生产锁.

锁的创建过程如下描述:

前提:每个锁都需要一个路径来指定(如:/jiacheo/lock)

1.根据指定的路径, 查找zookeeper集群下的这个节点是否存在.(说明已经有锁了)

2. 如果存在, 根据查询者的一些特征数据(如ip地址/hostname), 当前的锁是不是查询者的

3. 如果不是查询者的锁, 则返回null, 说明创建锁失败

4. 如果是查询者的锁, 则把这个锁返回给查询者

5. 如果这个节点不存在, 说明当前没有锁, 那么创建一个临时节点, 并将查询者的特征信息写入这个节点的数据中, 然后返回这个锁.

根据以上5部, 一个分布式的锁就可以创建了.

创建的锁有三种状态:

1. 创建失败(null), 说明该锁被其他查询者使用了.’

2. 创建成功, 但当前没有锁住(unlocked), 可以使用

3. 创建成功, 但当前已经锁住(locked)了, 不能继续加锁.

如图, 如果我们getLock(“/jiacheo/lock1″,”192.168.0.100″), 想要获取/jiacheo/lock1这个锁的话, 我们先判断这个节点是否存在, 存在的话获取他的数据(data), 然后通过解析data, 我们可以知道这个节点是不是我们查询者创建的(通过ip地址写入节点数据中), 然后就可以返回一个锁了.

正确实现一个分布式锁是一件非常棘手的事情,因为很难对所有类型的故障进行正确的处理,ZooKeeper带有一个Java语言编写的生产级别的锁实现,名为WriteLock,客户端可以方便的使用它。

(b)zookeeper分布式锁

    link:http://www.searchtb.com/2011/01/zookeeper-research.html

        拥有了zookeeper如此强大的分布式协作系统后,我们可以很容易的实现大量的分布式应用,包括了分布式锁,分布式队列,分布式Barrier,双阶段提交等等. 这些应用可以帮我们改进很多复杂系统的协作方式,将这些系统的实现变得更加优雅而高效.鉴于篇幅,本文仅介绍分布式锁的实现.
利用了前文提到的sequence nodes可以非常容易的实现分布式锁. 实现分布式锁的基本步骤如下(这些步骤需要在所有需要锁的客户端执行):

  1. client调用create()创建名为”_locknode_/lock-”的节点,注意需要设置sequence和ephemeral属性
  2. client调用getChildren(“_locknode_”),注意不能设置watch,这样才能避免羊群效应
  3. 如果步骤1中创建的节点序号最低,则该client获得锁,开始执行其它程序
  4. client对lock-xxx中序号仅次于自己创建节点的那个节点调用exists(),并设置watch
  5. 如果exist()返回false(节点不存在)则回到步骤2,否则等待步骤4中的watch被触发并返回步骤2

分布式锁在zookeeper的源代码中已经有实现,可以参考org.apache.zookeeper.recipes.lock



6、ZooKeeper一致性协议-Zab

link:http://blog.csdn.net/chen77716/article/details/7309915

Zookeeper的一致性协议:Zab

分类: 分布式算法 2657人阅读 评论(3) 收藏 举报
 

目录(?)[+]

 

      Zookeeper使用了一种称为Zab(Zookeeper Atomic Broadcast)的协议作为其一致性复制的核心,据其作者说这是一种新发算法,其特点是充分考虑了Yahoo的具体情况:高吞吐量、低延迟、健壮、简单,但不过分要求其扩展性。下面将展示一些该协议的核心内容:

另,本文仅讨论Zookeeper使用的一致性协议而非讨论其源码实现

        Zookeeper的实现是有Client、Server构成,Server端提供了一个一致性复制、存储服务,Client端会提供一些具体的语义,比如分布式锁、选举算法、分布式互斥等。从存储内容来说,Server端更多的是存储一些数据的状态,而非数据内容本身,因此Zookeeper可以作为一个小文件系统使用。数据状态的存储量相对不大,完全可以全部加载到内存中,从而极大地消除了通信延迟。

        Server可以Crash后重启,考虑到容错性,Server必须“记住”之前的数据状态,因此数据需要持久化,但吞吐量很高时,磁盘的IO便成为系统瓶颈,其解决办法是使用缓存,把随机写变为连续写。

考虑到Zookeeper主要操作数据的状态,为了保证状态的一致性,Zookeeper提出了两个安全属性(Safety Property)

  • 全序(Total order):如果消息a在消息b之前发送,则所有Server应该看到相同的结果
  • 因果顺序(Causal order):如果消息a在消息b之前发生(a导致了b),并被一起发送,则a始终在b之前被执行。
为了保证上述两个安全属性,Zookeeper使用了TCP协议和Leader。通过使用TCP协议保证了消息的全序特性(先发先到),通过Leader解决了因果顺序问题:先到Leader的先执行。因为有了Leader,Zookeeper的架构就变为:Master-Slave模式,但在该模式中Master(Leader)会Crash,因此,Zookeeper引入了Leader选举算法,以保证系统的健壮性。归纳起来Zookeeper整个工作分两个阶段:
  • Atomic Broadcast
  • Leader选举

1. Atomic Broadcast

同一时刻存在一个Leader节点,其他节点称为“Follower”,如果是更新请求,如果客户端连接到Leader节点,则由Leader节点执行其请求;如果连接到Follower节点,则需转发请求到Leader节点执行。但对读请求,Client可以直接从Follower上读取数据,如果需要读到最新数据,则需要从Leader节点进行,Zookeeper设计的读写比例是2:1。
 
Leader通过一个简化版的二段提交模式向其他Follower发送请求,但与二段提交有两个明显的不同之处:
  • 因为只有一个Leader,Leader提交到Follower的请求一定会被接受(没有其他Leader干扰)
  • 不需要所有的Follower都响应成功,只要一个多数派即可
通俗地说,如果有2f+1个节点,允许f个节点失败。因为任何两个多数派必有一个交集,当Leader切换时,通过这些交集节点可以获得当前系统的最新状态。如果没有一个多数派存在(存活节点数小于f+1)则,算法过程结束。但有一个特例:
如果有A、B、C三个节点,A是Leader,如果B Crash,则A、C能正常工作,因为A是Leader,A、C还构成多数派;如果A Crash则无法继续工作,因为Leader选举的多数派无法构成。

2. Leader Election

Leader选举主要是依赖Paxos算法,具体算法过程请参考其他博文,这里仅考虑Leader选举带来的一些问题。Leader选举遇到的最大问题是,”新老交互“的问题,新Leader是否要继续老Leader的状态。这里要按老Leader Crash的时机点分几种情况:
  1. 老Leader在COMMIT前Crash(已经提交到本地)
  2. 老Leader在COMMIT后Crash,但有部分Follower接收到了Commit请求
第一种情况,这些数据只有老Leader自己知道,当老Leader重启后,需要与新Leader同步并把这些数据从本地删除,以维持状态一致。
第二种情况,新Leader应该能通过一个多数派获得老Leader提交的最新数据
老Leader重启后,可能还会认为自己是Leader,可能会继续发送未完成的请求,从而因为两个Leader同时存在导致算法过程失败,解决办法是把Leader信息加入每条消息的id中,Zookeeper中称为zxid,zxid为一64位数字,高32位为leader信息又称为epoch,每次leader转换时递增;低32位为消息编号,Leader转换时应该从0重新开始编号。通过zxid,Follower能很容易发现请求是否来自老Leader,从而拒绝老Leader的请求。
 
因为在老Leader中存在着数据删除(情况1),因此Zookeeper的数据存储要支持补偿操作,这也就需要像数据库一样记录log。

3. Zab与Paxos

Zab的作者认为Zab与paxos并不相同,只所以没有采用Paxos是因为Paxos保证不了全序顺序:
Because multiple leaders can
propose a value for a given instance two problems arise.
First, proposals can conflict. Paxos uses ballots to detect and resolve conflicting proposals. 
Second, it is not enough to know that a given instance number has been committed, processes must also be able to figure out which value has been committed.
Paxos算法的确是不关系请求之间的逻辑顺序,而只考虑数据之间的全序,但很少有人直接使用paxos算法,都会经过一定的简化、优化。
一般Paxos都会有几种简化形式,其中之一便是,在存在Leader的情况下,可以简化为1个阶段(Phase2)。仅有一个阶段的场景需要有一个健壮的Leader,因此工作重点就变为Leader选举,在考虑到Learner的过程,还需要一个”学习“的阶段,通过这种方式,Paxos可简化为两个阶段:
  • 之前的Phase2
  • Learn
如果再考虑多数派要Learn成功,这其实就是Zab协议。Paxos算法着重是强调了选举过程的控制,对决议学习考虑的不多,Zab恰好对此进行了补充。
之前有人说,所有分布式算法都是Paxos的简化形式,虽然很绝对,但对很多情况的确如此,但不知Zab的作者是否认同这种说法?

4.结束

本文只是想从协议、算法的角度分析Zookeeper,而非分析其源码实现,因为Zookeeper版本的变化,文中描述的场景或许已找不到对应的实现。另,本文还试图揭露一个事实:Zab就是Paxos的一种简化形式。
【参考资料】
  • A simple totally ordered broadcast protocol
  • paxos


7、ZooKeeper选举和同步
 

zookeeper

 301人阅读 评论(0) 收藏 举报

http://stblog.baidu-tech.com/?p=1164

用于分布式下一致性相关问题的解决方案。可以理解为由集群组成的可靠的单master。可将传统方案中的master使用zookeeper代替,且不用担心单点问题。

应用场景:树状结构的命名服务、节点数据变更的消息通知、分布式共享锁、配置数据的集中存放、集群中节点机器的状态管理及状态变更通知

zookeeper实现分布式锁:通过zookeeper的节点状态进行条件判断,如果不满足,则在客户端本地加锁等待Object.wait()。利用zookeeper的实时通知机制,当zookeeper的节点满足条件状态时,客户端会同步获得通知,然后在本地解锁Object.notifyAll()。从而实现了分布式加锁、阻塞、解锁。

三类角色: leader(处理写请求,单点)、follower(处理客户端请求,参与投票)、observer(不投票,只处理客户端请求)

恢复模式:服务重启或者leader宕机后,通过paxos算法,从follower中重新选出leader,并以leader为准,进行数据同步。此时服务不可用。

paxos选举算法:

1、每次选举,都是针对某个txid(transaction id)进行。

2、每个follower首先广播询问,获取其它所有server的txid、提议value,txid必须相同,value存储到提议列表中

3、follower从提议列表中获取value,如果这个value被大于一半的follower支持,则直接使用此value,否则,继续发出广播询问。并且将此value作为回答其它follower轮训的提议。

4、循环执行3,直到收敛

paxos的精髓:解决了集群中,非全联通情况下的一致性问题。对于正常全联通情况,每台机器只需要广播获取其它各台机器的数据,然后比较获取最大值即可。这样各个节点得到的结论应该是一样的。问题在于,某些节点之间是不联通的。于是某个节点无法获知全局数据,只能通过paxos中循环投票,收敛至全局最优解。

同步流程:选举完成后,各个follower向leader发送同步请求,带上自己的最大zxid。leader通过zxid确定同步点,将这之后的commit log交给follower进行同步。所有节点都保存一份系统状态数据,非强一致(getData不保证最新数据,可以先sync一下保证数据的同步状态),有同步延时。

多节点可读可写,部分节点延时同步,最终一致性。follower和observer负责监听客户请求和处理读请求。对于所有写请求,都一律转发至leader进行选举和数据同步。observer不参与投票,只做数据同步,提高写请求的效率。