Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need to come up with a custom recursive object locking mechanism\pattern for a distributed system in C#. Essentially, I have a multi-node system. Each node has exclusive write permissions over n-number pieces of state. The same state is also available in read-only form on at least one other node. Some writes/updates must be atomic across all nodes, while other updates will eventually become consistent thru background replication processes, queues, etc...

For the atomic updates I'm looking for a pattern or samples that efficiently allow me to mark an object as locked for writes which I can then distribute, commit, rollback, etc... Since the system has high-levels of concurrency, I'm assuming I'll need to be able to stack-up locks which will either timeout or be unrolled once the locks are released.

The transaction or messaging pieces are not the focus of this question, but I've provided them for some extra context. With that said, feel free to articulate what messages you think would be needed if you like.

Here is a vague sample of what I was envisioning although I'm open to any new ideas aside from implementing whole new products

thing.AquireLock(LockLevel.Write);

//Do work

thing.ReleaseLock();

I was thinking of using extension methods, which might look something like this

public static void AquireLock(this IThing instance, TupleLockLevel lockLevel)
{ 
    //TODO: Add aquisition wait, retry, recursion count, timeout support, etc...  
    //TODO: Disallow read lock requests if the 'thing' is already write locked
    //TODO: Throw exception when aquisition fails
    instance.Lock = lockLevel;
}

public static void ReleaseLock(this IThing instance)
{
    instance.Lock = TupleLockLevel.None;
}

To clarify a couple details...

  • All communications are TCP/IP using a binary request/response protocol
  • There are no intermediary technologies such as queues or databases
  • There is no central master node. In this case, the locking arrangement is defined by the initiator of the lock and the partner which will honour the request with some form of timeout to govern its behaviour

Anyone have any suggestions?

share|improve this question
    
Locks are generally a standard feature in most systems. I guess it is there for C# as well. (A google search result: albahari.com/threading/part2.aspx ) Are you trying achieve something beyond basic Mutex or semaphores? –  Dipan Mehta Dec 26 '11 at 19:13
1  
@DipanMehta Sorry, I should've addressed this more clearly. The nodes I mentioned are machines on a network. My understanding of Mutex and Semaphores is that they're machine-wide locks (e.g. cross-process) and not locks that can extend between machines on a network. –  JoeGeeky Dec 26 '11 at 19:37
    
@JoeGeeky Your question is on-topic here and would be possibly too theoretical for Stack Overflow. If you want to re-ask it there you can, but you'll want a more code-focused phrasing. –  Anna Lear Dec 27 '11 at 17:18

2 Answers 2

up vote 4 down vote accepted

Thanks for the clarifications.

In that case, what I'd recommend is using a publish / subscribe model. Google's Chubby distributed locking protocol ( an implementation of Paxos)

I've never used Paxos (or Chubby), but there seems to be an open source implementation here.

If that doesn't work, you could implement your own version of Paxos using, for example, one of the usual suspects in terms of messaging libraries : the zero message queue library, RabbitMQ, or ActiveMQ.


Previous Answer:

Most of the suggestions on SO ([A], [B]) go for use of a message queue to achieve cross-machine locking.

Your AcquireLock method would push something identifying the lock object into the queue, checking for previous instances of locks before success. Your ReleaseLock method would remove the lock object from the queue.

SO user atlantis suggests, in this post, Jeff Key's post for some of the detail.

share|improve this answer
    
Thanks, but these solutions would not be suitable since I have not central master, database, or queue. I've updated the question with some additional details to clarify some of these details. –  JoeGeeky Dec 26 '11 at 20:55
    
I won't be able use these products directly since there is already a well-defined protocol that I must use for all communications between nodes, but the Chubby and Paxos may have well-defined patterns that I can learn from. I'll take a look. –  JoeGeeky Dec 27 '11 at 8:11
    
@JoeGeeky Yes, the Paxos link has sequence diagrams that might allow you to implement it using your preferred communications link. –  Peter K. Dec 27 '11 at 20:50
    
Although not a direct answer, reading through all the Chubby and Paxos stuff helped me define my own solution. I didn't use those tools, but was able to define a reasonable pattern based on some of their concepts. Thanks. –  JoeGeeky Jan 3 '12 at 8:43
    
@JoeGeeky: Good to hear it was some help, at least. Thanks for the tick. –  Peter K. Jan 3 '12 at 12:31

Seems to me like you have a couple of mixed technologies here:

  • communications (which you essentially rely on as being 100% reliable... which can be fatal)

  • locking / mutual exclusion

  • timeouts (for what purpose)?

A word of warning: Timeouts in distributed systems can be fraught with danger and difficulty. If used, they must be set and used very carefully because the indiscriminate use of timeouts does not fix a problem, it just defers the catastrophe. (If you want to see how timeouts should be used, read and understand the HDLC communication protocol documentation. This is a good example of suitable and clever use, in combination with a clever bit-coding system to allow detection of things like IDLE line).

For a time I worked in multi-processor distributed systems connected up using communication links (not TCP, something else). One of the things I learned was that as a rough generalisation, there are some dangerous multi-programming places to go:

  • reliance on queues usually ends in tears (if the queue fills, you are in trouble. UNLESS you can calculate a queue size that will never fill, in which case you probably could use a no-queue solution)

  • reliance on locking is painful, try and think if there is another way (if you must use locking, look at the literature, multi-processor distributed locking has been the subject of many acedemic papers of the last 2-3 decades)

I you have to proceed using locking, then:

I will ASSUME that you will use timeouts only as a means of recovery of last resort - ie for detection of a failure of the underlying communications system. I will further assume that your TCP/IP communication system is high bandwidth and can be thought of as low latency (ideally zero, but this never happens).

What I would suggest is that every node has a connectivity list of other nodes it can connect to. (Nodes would not care where a connection comes from.) Population of the tables of which nodes a node can connect to is left as a separate thing to sort out, you have not said if that would be statically set or otherwise. Also conveniently ignored is things like the allocation of the IP port numbers where connections would come into a node - there can be good reasons for accepting requests on only a single port, or on multiple ports. This needs to be carefully considered. Factors will include implicit queuing, ordering, resource use, operating system type and capabilities.

Once nodes know who they connect to, they can send to that node a lock request, and must receive back from a lock reply from that remote node. You can pack those two operations into a wrapper to make it look atomic. The effect of this is that nodes wishing to acquire a lock will make a call something like:

if (get_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

/* Lock is now acquired - do work here */

if (release_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

the calls get_lock and release_lock should be something like (in principle):

send_to_remote_node(lock_request)
get_from_remote_node_or_timeout(lock_reply, time)
if (result was timeout) then
  return timeout
else
  return ok

You will have to take great care with a distributed locking system that the units of work performed while a lock is held are small and fast because you will have many remote nodes potentially held up waiting to get a lock. This is effectively a stop-and-wait multiprocessor / communication system which is robust but does not have the highest possible performance.

A suggestion is to take a completely different approach. Can you use a remote procedure call where each RPC call carries a package of information which can be handled by the recipient, and which removes the needs for locks?


On re-reading the question, it looks like you don't really want to be concerned with the communication side of things, you just want to solve your locking issue.

My answer might therefore seem a bit off-topic, however, I believe you can't solve your locking issue without getting the parts underneath it right as well. Analogy: Building a house on bad foundations causes it to fall down... Eventually.

share|improve this answer
1  
The timeout semantics are largely there to deal with nodes that disappear from the network, or to deal with large backlogs in locking stacks... This will limit the time spent blocked while waiting to acquire a lock and will provide those requesting the lock an opportunity to kick off other processes in the midst of unexpected delays, failures, etc... Additionally, this would prevent something from being locked forever in case something fails. I appreciate your concerns although at this point, I don't see any alternatives given that eventually something will fail –  JoeGeeky Dec 27 '11 at 7:43
    
To speak to some of your other comments, I'm not using queues per se (in the async communication sense), although I'd expect that locks are stacked and released based using a FIFO pattern. I've not quite reconciled how this will work in terms of the required request/response pattern other than this will need to block in some way and be part of a larger handshake. At the moment, I’m working through the stacked locking mechanism within a single node and then how it will work through the distributed scenario. I'll do a bit more reading as you suggested. Thanks –  JoeGeeky Dec 27 '11 at 8:08
    
@JoeGeeky - a FIFO is a queue. Beware of queues. Think that side through very carefully. It sounds a lot like you are not going to just get something "off the shelf" but will have to think through your problem and solution carefully. –  quickly_now Dec 27 '11 at 11:20
    
I understand... I was trying to clarify the difference btwn a FIFO queue used in async processes (e.g. one process enqueues and then another dequeues). In this case, things will need to be managed in order, but the process entering the queue would not leave until (a) they get the lock, (b) are denied a lock, or (c) they timeout and leave the line. More like standing in line at the ATM. This behaves like a FIFO pattern in the success case, but processes could leave out of order prior to reaching the front of the line. As for off-the-shelf? No, but this is not a new problem –  JoeGeeky Dec 27 '11 at 13:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.