Looking for a distributed locking pattern

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Your question can be easily implemented using a distributed cache like NCache. What you require is a Pessimistic Locking mechanism where you could Acquire a lock using an object. Then perform your tasks and operations and release the lock for other applications to consume later on.

Take a look at the following code;

Here you would acquire a lock on a specific Key and then perform tasks (ranging from one or more operations) then finally release the lock when you're done.

// Instance of the object used to lock and unlock cache items in NCache
LockHandle lockHandle = new LockHandle();

// Specify time span of 10 sec for which the item remains locked
// NCache will auto release the lock after 10 seconds.
TimeSpan lockSpan = new TimeSpan(0, 0, 10); 

try
{
    // If item fetch is successful, lockHandle object will be populated
    // The lockHandle object will be used to unlock the cache item
    // acquireLock should be true if you want to acquire to the lock.
    // If item does not exists, account will be null
    BankAccount account = cache.Get(key, lockSpan, 
    ref lockHandle, acquireLock) as BankAccount;
    // Lock acquired otherwise it will throw LockingException exception

    if(account != null && account.IsActive)
    {
        // Withdraw money or Deposit
        account.Balance += withdrawAmount;
        // account.Balance -= depositAmount;

        // Insert the data in the cache and release the lock simultaneously 
        // LockHandle initially used to lock the item must be provided
        // releaseLock should be true to release the lock, otherwise false
        cache.Insert("Key", account, lockHandle, releaseLock); 
        //For your case you should use cache.Unlock("Key", lockHandle);
    }
    else
    {
        // Either does not exist or unable to cast
        // Explicitly release the lock in case of errors
        cache.Unlock("Key", lockHandle);
    } 
}
catch(LockingException lockException)
{
    // Lock couldn't be acquired
    // Wait and try again
}

Taken from the link: http://blogs.alachisoft.com/ncache/distributed-locking/