http://ayende.comAyende @ RahienCopyright (C) Ayende Rahien 2004 - 2021 (c) 202660Actually, now that I think about it, since you want a majority for quorum, it probably should be: return successfulLocks >= (topology.Count / 2) + 1 http://ayende.com/4175/break-the-algorithm-distributed-lock#comment14http://ayende.com/4175/break-the-algorithm-distributed-lock#comment14Tue, 08 Sep 2009 23:09:55 GMTHoward, I would like to deal with even number of servers, yes. But you are right, your code is simpler, much simpler. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment13http://ayende.com/4175/break-the-algorithm-distributed-lock#comment13Tue, 08 Sep 2009 14:04:37 GMTAyende: I'm confused by this line: return (successfulLocks/2) >= (topology.Count/2) Why is it not return successfulLocks >= (topology.Count/2) Are you somehow trying to deal with and even number of servers? http://ayende.com/4175/break-the-algorithm-distributed-lock#comment12http://ayende.com/4175/break-the-algorithm-distributed-lock#comment12Tue, 08 Sep 2009 12:51:31 GMT> The annoying thing is that we need to recover from situations in which some of the nodes holding the key are down or inaccessible. Ah, I see... That's the most complex problem. Check out the links ;) http://ayende.com/4175/break-the-algorithm-distributed-lock#comment11http://ayende.com/4175/break-the-algorithm-distributed-lock#comment11Sun, 06 Sep 2009 15:57:44 GMT> Don't at least n/2+1 servers need to return success in order for the lock to be considered as 'entered'? As far as I can judge from above, there is no code related to distributed consensus. So no any "global" state guarantees. Thus it's difficult to judge if this will work at all: no one can predict how such a system will work after failure, because state of recovered node initially can be completely unexpected. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment10http://ayende.com/4175/break-the-algorithm-distributed-lock#comment10Sun, 06 Sep 2009 15:54:45 GMTP.S. For me the worst issues here are: - Operations aren't atomic. Its completely unclear what guarantees are you going to provide after their completion. -There must be issues related to difference in time - Its completely unclear what will happen when new server wakes up after temporary failure (e.g. network outage). - It is unclear how they're classified as down / working. What invariants are guaranteed to be maintained? P.S. One more good article to read is Microsoft Boxwood project description. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment9http://ayende.com/4175/break-the-algorithm-distributed-lock#comment9Sun, 06 Sep 2009 15:49:28 GMTOren, I'd recommend you to read about Chubby & distributed consensus algorithms (Paxos, etc.). You'll see principal issues, rather than just technical. Btw, we evaluated DHT approach for distributed storage for DO databases. And finally decided this approach won't work for storages we typically need: index seek can't beimplemented there well, but this is essential in quite many cases. Note that e.g. BigTable is not DHT. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment8http://ayende.com/4175/break-the-algorithm-distributed-lock#comment8Sun, 06 Sep 2009 11:13:02 GMTUriel, I love Boo for its clean syntax. It is almost pseudo code http://ayende.com/4175/break-the-algorithm-distributed-lock#comment7http://ayende.com/4175/break-the-algorithm-distributed-lock#comment7Sat, 05 Sep 2009 21:59:43 GMTThat looks more like boo than psuedo code :-P http://ayende.com/4175/break-the-algorithm-distributed-lock#comment6http://ayende.com/4175/break-the-algorithm-distributed-lock#comment6Sat, 05 Sep 2009 18:09:39 GMTwhat interest me is that your pseudo is in Boo/Python(or really close to it) :) http://ayende.com/4175/break-the-algorithm-distributed-lock#comment5http://ayende.com/4175/break-the-algorithm-distributed-lock#comment5Sat, 05 Sep 2009 17:17:27 GMTAs I understand it, the Chubby service associates a number that is incremented for locking requests. It's a variant of the Paxos algorithm and the number is needed to form a consensus on who owns the lock. That may be overkill for this use, but I think the idea is if you need to change something in the DHT from one state to the next, this gives you some 'consensus' of the 'start state' before you begin. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment4http://ayende.com/4175/break-the-algorithm-distributed-lock#comment4Sat, 05 Sep 2009 15:52:39 GMTJason, You are probably right. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment3http://ayende.com/4175/break-the-algorithm-distributed-lock#comment3Sat, 05 Sep 2009 15:42:30 GMTWhat do you mean by automatically incrementing the lock revision? Can you explain? http://ayende.com/4175/break-the-algorithm-distributed-lock#comment2http://ayende.com/4175/break-the-algorithm-distributed-lock#comment2Sat, 05 Sep 2009 15:42:28 GMTDon't at least n/2+1 servers need to return success in order for the lock to be considered as 'entered'? Otherwise two nodes could enter the lock, each with half the nodes. This is sort of like the Google Chubby protocol. They use a lock revision # that is incremented 'atomically' across nodes to ensure that two nodes can't lock on the same key. http://ayende.com/4175/break-the-algorithm-distributed-lock#comment1http://ayende.com/4175/break-the-algorithm-distributed-lock#comment1Sat, 05 Sep 2009 14:23:30 GMT