IdBasedLocking

Java has excellent concurrency and locking support - perhaps the best that modern languages ​​offer. Besides the fact that the language itself has built-in support for synchronization, there are a number of useful utilities based on the AQS framework. These include CountDownLatches, Barriers, Semaphores and others. However, there is often a situation that is not directly supported: when it is necessary to block access not to a specific object , but to the idea of ​​this object .



Consider the following example: we have a service that is responsible for mailboxes (mailbox). It has a method for adding a new message and a method for reading the message. Of course, we run our service in a multi-threaded environment - after all, we have thousands of users who send a huge bunch of messages to each other. To protect the mailbox from data corruption, we should not allow the modification of one box by several threads at the same time:
')

public void sendMessage(UserId from, UserId to, Message message) { Mailbox sendersBox = getMailbox(from); Mailbox recipientsBox = getMailbox(to); min(sendersBox,recipientsBox).lock(); max(sendersBox, recipientsBox).lock(); sendersBox.addIncomingMessage(message); recipientsBox.addSentMessage(message); max(sendersBox, recipientsBox).lock(); min(sendersBox,recipientsBox).lock(); } 

The code assumes that for the mailbox we have the min / max function, which always gives an unambiguous result: for example, it compares the hash code, or the host id, or something else. This is necessary in order to always put the lock in the same order (smaller one first) and avoid deadlock when modifying two boxes. Taking this into account, the code looks relatively safe, doesn't it?

In fact, the security of this code depends on how, in fact, the getMailbox () method is implemented. If he can guarantee the return of the same object (and exactly “the same”, and not “the same”), then we are safe. Unfortunately, such a guarantee is practically impossible to implement. On the other hand, we could, of course, put synchronized on the entire sendMessage () method, but this would kill our performance on the root, since we could send only one message at a time, regardless of the number of threads and processors at our disposal.

Here is an example of how you can incorrectly implement getMailbox () :

  private Mailbox getMailbox(UserId id) { Mailbox mailbox = cache.get(id); if (mailbox == null) { mailbox = new Mailbox(); cache.put(id, mailbox); } return mailbox; } 

Obviously, this implementation is insecure: it allows the creation of the same mailbox as a matter of fact (that is, belonging to the same user) from different streams at the same time. This means that at some point two different boxes of the same user may appear in the system, and only Cthulhu will know which of them will survive. You can solve this problem by blocking the creation of a new mailbox globally, but this is again a rake with performance. You can start having fun with ConcurrentMap and all kinds of putIfAbsent . But imagine that we are not only creating new mailboxes, but also loading existing ones from the database. Then it will be much more difficult to synchronize correctly (and it would be nice to prevent unnecessary requests to the database).

Fortunately, IdBasedLocking solves this particular problem. Instead of blocking a specific mailbox object , we block the concept of the mailbox , based on the fact that we have one mailbox per user:

  IdBasedLockManager<UserId> manager = new SafeIdBasedLockManager<UserId>(); public void sendMessageSafe(UserId from, UserId to, Message message) { IdBasedLock<UserId> minLock = manager.obtainLock(min(from, to)); IdBasedLock<UserId> maxLock = manager.obtainLock(max(from, to)); minLock.lock(); maxLock.lock(); try { Mailbox sendersBox = getMailbox(from); Mailbox recipientsBox = getMailbox(to); sendersBox.addIncomingMessage(message); recipientsBox.addSentMessage(message); } finally { maxLock.unlock(); minLock.unlock(); } } 

An example may seem artificially complicated due to the simultaneous modification of two objects. IdBasedLocking works fine with a single object, as the following counter example demonstrates.

First - a broken version:

  public void increaseCounterUnsafe(String id) { Counter c = counterCache.get(id); if (c == null) { c = new Counter(); counterCache.put(id, c); } c.increase(); } 

And now the safe version:

  public void increaseCounterSafely(String id) { IdBasedLock<String> lock = lockManager.obtainLock(id); lock.lock(); try{ Counter c = counterCache.get(id); if (c == null) { c = new Counter(); counterCache.put(id, c); } c.increase(); } finally { lock.unlock(); } } 

IdBasedLocking project on githaba .

You can borrow it using maven, gradle or ivy, or simply from central . Or try it out on a githaba yourself.

Thanks for attention.