[Zookeeper-developer] [ zookeeper-Patches-1881204 ] New leader election algorithm with TCP.

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Patches item #1881204, was opened at 2008-01-28 15:28
Message generated for change (Comment added) made by mahadevkonar
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=1008546&aid=1881204&group_id=209147

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: server
Group: None
Status: Open
Resolution: None
Priority: 7
Private: No
Submitted By: fpj (fpj)
Assigned to: fpj (fpj)
Summary: New leader election algorithm with TCP.

Initial Comment:
This is a feature request for a new leader election algorithm with TCP.

----------------------------------------------------------------------

>Comment By: Mahadev Konar (mahadevkonar)
Date: 2008-02-25 19:35

Message:
Logged In: YES 
user_id=1926680
Originator: NO

only comment: the patch has tabs ... :) and also some of the lines are
really long (we could wrap them arnd).

----------------------------------------------------------------------

Comment By: Mahadev Konar (mahadevkonar)
Date: 2008-02-25 19:35

Message:
Logged In: YES 
user_id=1926680
Originator: NO

+1 make it happen

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-22 16:12

Message:
Logged In: YES 
user_id=1926444
Originator: YES

File Added: patch-le-tcp-v6b.txt

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-22 12:50

Message:
Logged In: YES 
user_id=1926444
Originator: YES

A few bugs fixed. These bugs were generating some race conditions, in
particular for the cross-colo cases.

Thanks,
-Flavio
File Added: patch-le-tcp-v6.txt

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-19 16:07

Message:
Logged In: YES 
user_id=1926444
Originator: YES

In version 5b, I simply removed some output messages, which I had forgot
to remove. Everything else should be the same as with version 5.

-Flavio
File Added: patch-le-tcp-v5b.txt

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-19 15:59

Message:
Logged In: YES 
user_id=1926444
Originator: YES

Version 5 has an input parameter (electionAlg) to select which
implementation of the algorithm to use. There are currently 4 flavors: the
original UDP-based ZK leader election algorithm (0),  UDP-based without
authentication (1), UDP-based with authentication (2), TCP-based (3). I
tested with three different clusters, and locally all four work fine.
However, when adding a remote machine the zookeeper servers go wild when
using any of the UDP-based versions. It seems that state gets corrupted,
and the servers stop beahving correctly. The TCP-based version presented no
problem when servers were in different clusters, though.

I can't explain why state gets corrupted, but it seems to happen when
there is at least one remote machine and I use a UDP-based implementation.

-Flavio 
File Added: patch-le-tcp-v5.txt

----------------------------------------------------------------------

Comment By: Benjamin Reed (breed)
Date: 2008-02-18 15:50

Message:
Logged In: YES 
user_id=154690
Originator: NO

+1 make it happen

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-14 14:30

Message:
Logged In: YES 
user_id=1926444
Originator: YES

I have tested the new implementation using machines across the Atlantic,
and I found a problem with the way we were opening a connection to the new
leader on Follower.java. On Follower.followLeader(), there was a for loop
that supposedly tried to connect to the new leader 3 times. The way it was
implemented before didn't work because in the second iteration the Socket
object was not valid anymore. This was causing the follower to try only
once as in the second iteration it was throwing an excpetion that was not
ConnectException, and it was leaving the for loop. I have modified the code
to create a socket inside the loop for every iteration. In this way the
Socket object is valid on every attempt.

Because the follower was trying only once, it was happening that the
follower would try to connect to the leader before the leader was ready to
accept connections. To avoid this problem, we had this hack in the leader
election implemention (the previous version was doing the same) to make the
follower wait for a fixed amount of time, which we had set to 100ms. When I
tried with high-latency connections, the value of 100ms was not sufficient,
and I was observing runs in which the system was never making progress
because the leader election would succeed, but the single follower of my
experiment was not being able to connect to the leader as the leader was
not ready yet and the bug in the code allowed the follower to try only
once. With this fix, the follower may still experience unsuccessful
attempts to connect to the leader, but given that it waits one second until
the next try, it often succeeds in the second attempt. Moreover, with this
fix, I've been able to get rid of the 100ms timer at the end of leader
election, so it now terminates even faster.

-Flavio
File Added: patch-le-tcp-v4.txt

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-02-05 14:09

Message:
Logged In: YES 
user_id=1926444
Originator: YES

I'm attaching a third version of the patch, in which I fixed a few bugs.
In response to Mahadev's comment, I could use the server id to initialize
the Random object, but since I'm not passing it to the constructor, I've
chosen to initialize the seed in a different way, using IP and time. The
idea of using IP is to have different different seeds for different
servers. As Mahadev pointed out before, we have to consider tha case in
which one computer runs multiple ZK servers. For this special case, I add
the current time to break ties with respect to challenge.

In my understanding, the way we generate the challenge value doesn't
really matter. I think it is more general in the way I've implemented as it
doesn't depend upon any particular scheme of identification for the
servers. It is important to note, though, that it is not always necessary
to break ties as there are times in which the attempt to initiate a
connection is one way. In these cases, if we try to break ties, we may end
up with no connection. The logic to overcome such corner cases is fairly
simple. if a server A doesn't have a connection to server B, and A has
received a connection request from B, then A must accept it. To make it
work despite the utilization of a tie-break mechanism, A changes its
challenge to the smallest possible value the challenge can have. In this
way, it makes sure that it loses the challenge.

If I use a mechanism that doesn't exchange challenge values (such as using
IP and port), then it is not possible to implement the trick I describe
above.
File Added: patch-le-tcp-v3.txt

----------------------------------------------------------------------

Comment By: Mahadev Konar (mahadevkonar)
Date: 2008-02-04 20:21

Message:
Logged In: YES 
user_id=1926680
Originator: NO

a few comments:

 new Random(System.currentTimeMillis()
+                + localIP.hashCode());

what is the idea behind adding ipaddress hashcode and currentimemillis?
why not just use the serverid or in that case why not just use the raw
server id for connection resolving? 
something like a server with higher server id is the server that the other
connects to... 

----------------------------------------------------------------------

Comment By: fpj (fpj)
Date: 2008-01-31 17:14

Message:
Logged In: YES 
user_id=1926444
Originator: YES

File Added: patch-le-tcp-v2.txt

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=1008546&aid=1881204&group_id=209147