You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@zookeeper.apache.org by "Patrick Hunt (JIRA)" <ji...@apache.org> on 2008/07/17 18:45:31 UTC
[jira] Created: (ZOOKEEPER-79) Document jacob's leader election on
the wiki recipes page
Document jacob's leader election on the wiki recipes page
---------------------------------------------------------
Key: ZOOKEEPER-79
URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
Project: Zookeeper
Issue Type: New Feature
Components: documentation
Reporter: Patrick Hunt
Assignee: Patrick Hunt
The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
---------------------from jacob ----------------
Avinash
The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
Flavio
Might it make sense to provide a standardized implementation of leader election in the library code in Java?
--Jacob
From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
Sent: Friday, July 11, 2008 1:02 AM
To: zookeeper-user@lists.sourceforge.net
Cc: zookeeper-user@hadoop.apache.org
Subject: Re: [Zookeeper-user] Leader election
Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
Hope it helps.
-Flavio
----- Original Message ----
From: Avinash Lakshman <av...@gmail.com>
To: zookeeper-user@lists.sourceforge.net
Sent: Friday, July 11, 2008 7:20:06 AM
Subject: [Zookeeper-user] Leader election
Hi
I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
public void electLeader()
{
ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
String path = "/Leader";
try
{
String createPath = path + "/L-";
LeaderElector.createLock_.lock();
while( true )
{
/* Get all znodes under the Leader znode */
List<String> values = zk.getChildren(path, false);
/*
* Get the first znode and if it is the
* pathCreated created above then the data
* in that znode is the leader's identity.
*/
if ( leader_ == null )
{
leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
}
else
{
leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
/* Disseminate the state as to who the leader is. */
onLeaderElection();
}
logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
Collections.sort(values);
/* We need only the last portion of this znode */
String[] peices = pathCreated_.split("/");
int index = Collections.binarySearch(values, peices[peices.length - 1]);
if ( index > 0 )
{
String pathToCheck = path + "/" + values.get(index - 1);
Stat stat = zk.exists(pathToCheck, true);
if ( stat != null )
{
logger_.debug("Awaiting my turn ...");
condition_.await();
logger_.debug("Checking to see if leader is around ...");
}
}
else
{
break;
}
}
}
catch ( InterruptedException ex )
{
logger_.warn(LogUtil.throwableToString(ex));
}
catch ( KeeperException ex )
{
logger_.warn(LogUtil.throwableToString(ex));
}
finally
{
LeaderElector.createLock_.unlock();
}
}
}
Thanks
Avinash
-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
Zookeeper-user mailing list
Zookeeper-user@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (ZOOKEEPER-79) Document jacob's leader election on
the wiki recipes page
Posted by "Flavio Paiva Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Flavio Paiva Junqueira resolved ZOOKEEPER-79.
---------------------------------------------
Resolution: Fixed
Added the description to the documentation: http://hadoop.apache.org/zookeeper/docs/current/recipes.html
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Flavio Paiva Junqueira
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614435#action_12614435 ]
Patrick Hunt commented on ZOOKEEPER-79:
---------------------------------------
I know, your submission (78) is what kicked me in the but to add this. :-) Should have done it a while ago.
I'm also initiating some discussion on the list (email) relative to 78. I also plan to create a Jira for user contrib recipe discussion/decision.. more on that soon.
How closely does your implementation match what Jacob has documented? Are you interested to take on this JIRA as well -- ie you document the election protocol outlined by Jacob on the wiki?
http://wiki.apache.org/hadoop/ZooKeeper/ZooKeeperRecipes
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Patrick Hunt
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (ZOOKEEPER-79) Document jacob's leader election on
the wiki recipes page
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Patrick Hunt reassigned ZOOKEEPER-79:
-------------------------------------
Assignee: Flavio Paiva Junqueira (was: Patrick Hunt)
Assigning to Flavio to document this recipe.
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Flavio Paiva Junqueira
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "Flavio Paiva Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614556#action_12614556 ]
Flavio Paiva Junqueira commented on ZOOKEEPER-79:
-------------------------------------------------
This idea of having clients watching on different nodes when waiting for application events is crucial to avoid the herd effect, and it has applications other than leader election. Ben and I, for example, used a similar idea to implement barriers. With a barrier, clients need to wait until all other clients are done with their part of a computation, and we can use the existence of a znode to express the fact that a particular client hasn't finished.
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Patrick Hunt
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "james strachan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614448#action_12614448 ]
james strachan commented on ZOOKEEPER-79:
-----------------------------------------
Ah cool :) Was just checking we were not about to do the same thing separate :).
I've basically followed the same algorithm from the wiki recipe - and the same one described in the ZooKeeper tutorial...
http://developer.yahoo.com/blogs/hadoop/2008/03/intro-to-zookeeper-video.html
So AFAIK yes its the same
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Patrick Hunt
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "Flavio Paiva Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614558#action_12614558 ]
Flavio Paiva Junqueira commented on ZOOKEEPER-79:
-------------------------------------------------
And, I like Jacob's suggestion. As recipes are an important of ZooKeeper, we might as well have a library of primitives that can serve at least as examples for application developers.
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Patrick Hunt
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "Flavio Paiva Junqueira (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12616257#action_12616257 ]
Flavio Paiva Junqueira commented on ZOOKEEPER-79:
-------------------------------------------------
I have added a description to the wiki. Comments are definitely welcome.
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Flavio Paiva Junqueira
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-79) Document jacob's leader election on
the wiki recipes page
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Patrick Hunt updated ZOOKEEPER-79:
----------------------------------
Fix Version/s: 3.0.0
Affects Version/s: 3.0.0
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Affects Versions: 3.0.0
> Reporter: Patrick Hunt
> Assignee: Flavio Paiva Junqueira
> Fix For: 3.0.0
>
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-79) Document jacob's leader election
on the wiki recipes page
Posted by "james strachan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614431#action_12614431 ]
james strachan commented on ZOOKEEPER-79:
-----------------------------------------
BTW https://issues.apache.org/jira/browse/ZOOKEEPER-78 contains a patch of just that :)
> Document jacob's leader election on the wiki recipes page
> ---------------------------------------------------------
>
> Key: ZOOKEEPER-79
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-79
> Project: Zookeeper
> Issue Type: New Feature
> Components: documentation
> Reporter: Patrick Hunt
> Assignee: Patrick Hunt
>
> The following discussion occurred on the zookeeper-user list. We need to formalize this recipe and document on the wiki recipes page:
> ---------------------from jacob ----------------
> Avinash
>
> The following protocol will help you fix the observed misbehavior. As Flavio points out, you cannot rely on the order of nodes in getChildren, you must use an intrinsic property of each node to determine who is the leader. The protocol devised by Runping Qi and described here will do that.
>
> First of all, when you create child nodes of the node that holds the leadership bids, you must create them with the EPHEMERAL and SEQUENCE flag. ZooKeeper guarantees to give you an ephemeral node named uniquely and with a sequence number larger by at least one than any previously created node in the sequence. You provide a prefix, like "L_" or your own choice, and ZooKeeper creates nodes named "L_23", "L_24", etc. The sequence number starts at 0 and increases monotonously.
>
> Once you've placed your leadership bid, you search backwards from the sequence number of *your* node to see if there are any preceding (in terms of the sequence number) nodes. When you find one, you place a watch on it and wait for it to disappear. When you get the watch notification, you search again, until you do not find a preceding node, then you know you're the leader. This protocol guarantees that there is at any time only one node that thinks it is the leader. But it does not disseminate information about who is the leader. If you want everyone to know who is the leader, you can have an additional Znode whose value is the name of the current leader (or some identifying information on how to contact the leader, etc.). Note that this cannot be done atomically, so by the time other nodes find out who the leader is, the leadership may already have passed on to a different node.
>
> Flavio
>
> Might it make sense to provide a standardized implementation of leader election in the library code in Java?
>
> --Jacob
>
> From: zookeeper-user-bounces@lists.sourceforge.net [mailto:zookeeper-user-bounces@lists.sourceforge.net] On Behalf Of Flavio Junqueira
> Sent: Friday, July 11, 2008 1:02 AM
> To: zookeeper-user@lists.sourceforge.net
> Cc: zookeeper-user@hadoop.apache.org
> Subject: Re: [Zookeeper-user] Leader election
>
> Hi Avinash, getChildren returns a list in lexicographic order, so if you are updating the children of the election node concurrently, then you may get a different first node with different clients. If you are using the sequence flag to create nodes, then you may consider stripping the prefix of the node name and using the sufix value to determine order.
> Hope it helps.
> -Flavio
>
> ----- Original Message ----
> From: Avinash Lakshman <av...@gmail.com>
> To: zookeeper-user@lists.sourceforge.net
> Sent: Friday, July 11, 2008 7:20:06 AM
> Subject: [Zookeeper-user] Leader election
> Hi
> I am trying to elect leader among 50 nodes. There is always one odd guy who seems to think that someone else distinct from what some other nodes see as leader. Could someone please tell me what is wrong with the following code for leader election:
> public void electLeader()
> {
> ZooKeeper zk = StorageService.instance().getZooKeeperHandle();
> String path = "/Leader";
> try
> {
> String createPath = path + "/L-";
> LeaderElector.createLock_.lock();
> while( true )
> {
> /* Get all znodes under the Leader znode */
> List<String> values = zk.getChildren(path, false);
> /*
> * Get the first znode and if it is the
> * pathCreated created above then the data
> * in that znode is the leader's identity.
> */
> if ( leader_ == null )
> {
> leader_ = new AtomicReference<EndPoint>( EndPoint.fromBytes( zk.getData(path + "/" + values.get(0), false, null) ) );
> }
> else
> {
> leader_.set( EndPoint.fromBytes( zk.getData(path + "/" + values .get(0), false, null) ) );
> /* Disseminate the state as to who the leader is. */
> onLeaderElection();
> }
> logger_.debug("Elected leader is " + leader_ + " @ znode " + ( path + "/" + values.get(0) ) );
> Collections.sort(values);
> /* We need only the last portion of this znode */
> String[] peices = pathCreated_.split("/");
> int index = Collections.binarySearch(values, peices[peices.length - 1]);
> if ( index > 0 )
> {
> String pathToCheck = path + "/" + values.get(index - 1);
> Stat stat = zk.exists(pathToCheck, true);
> if ( stat != null )
> {
> logger_.debug("Awaiting my turn ...");
> condition_.await();
> logger_.debug("Checking to see if leader is around ...");
> }
> }
> else
> {
> break;
> }
> }
> }
> catch ( InterruptedException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> catch ( KeeperException ex )
> {
> logger_.warn(LogUtil.throwableToString(ex));
> }
> finally
> {
> LeaderElector.createLock_.unlock();
> }
> }
> }
> Thanks
> Avinash
>
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________
> Zookeeper-user mailing list
> Zookeeper-user@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/zookeeper-user
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.