Saturday, March 8, 2008

Synchronization in a web application

UPDATED 03/08/2008 - source code completely rewritten.

While I was writing the code for the Project Guttenberg proxy, one of the problems I needed to solve was the concurrency in URL processing.

When a user requests a URL from the proxy, the proxy sends the request to the real Project Gutenberg web site, and writes the result into a file.

Then it processes the file - if it's an HTML document, it replaces the references to the original web site with links that point to the proxy. If it was a request for a LRF file, the text file that was fetched from the Project Gutenberg would be translated.

Then there's cache - the web pages that have already been fetched, but have not expired get fetched from that cache.

In other words, there's a lot of activity, that is by and large independent - unless the two requests come for the same page. Then of course we do not want to process them at the same time, because they are going to be modifying the same state, corrupting each other in the process.

The solution is not that hard, but I thought it would be instructive to put it here.


package com.solyanik.sync;

import java.util.HashSet;

/** The general object lock class.
* Ensures that any two objects
* that are equal to each other as
* in a.equals(b) cannot be locked
* simultaneously.
*
* This is a complement to the
* standard monitor functionality
* that protects objects that are
* equal in == sense (i. e. the
* same object).
*
* IMPORTANT NOTE: The same thread
* trying to lock the same object
* twice = INSTANT DEADLOCK!
*
* Usage:
* // in constructor
* ObjectLock lock = new ObjectLock();
* ...
* void handleRequest(final Object o) {
* try {
* lock.lock(o);
* ... // do processing
* } finally {
* lock.unlock(o);
* }
*
* @author sergey@solyanik.com (Sergey Solyanik)
*/
class ObjectLock {
/**
* Stores all currently locked objects
*/
private HashSet<Object> locked =
new HashSet<Object>();

public void lock(Object o)
throws InterruptedException {
synchronized(locked) {
for ( ; ; ) {
if (locked.contains(o)) {
// We are already locked.
locked.wait();
} else {
locked.add(o);
break;
}
}
}
}

public void unlock(Object o)
throws IllegalMonitorStateException {
synchronized(locked) {
if (!locked.remove(o))
throw new
IllegalMonitorStateException(
"The object is not locked.");
locked.notifyAll();
}
}
}


The code is tiny and by and large self explanatory. We keep a hash set, and whenever we are about to lock the object, we check if it is in the hash set already. If it is not, we put it there and continue on our merry way.

If it is, we're joining the queue of threads waiting on the hash set (it can actually be absolutely any object). When the object is unlocked, it will be removed from the hash, and the threads waiting will be notified.

To preempt obvious question - this assumes that the level of contention is not super high, so there are not a lot of threads pending at any given time. In the case of a high level of contention (10s of threads), we would want to wake up only the threads that are waiting for that specific object that has just been unlocked, not all of the threads.

How is this different from synchronized(o)? The ObjectLock will prevent collisions of code operating on objects that are equal in the sense that o1.equals(o2). The synchronized clause prevents operations on the objects that are the same (o1 == o2).

In the case of a string, by the way, an inefficient way of doing the same that the lock class above is trying to accomplish is this:

void handle_request(String url) {
String lock = url.toLowerCase().intern();
synchronized(lock) {
... do processing ...
}
}


Interned string have the property of s1 == s2 iff s1.equals(s2). The problem of course is that every url that has ever been processed will stay in your process's string heap forever, so it is not very efficient.

And the unit test:

package com.solyanik.sync;

import java.util.HashSet;

public class UnitTest {
static class Executor extends Thread {
private static HashSet<String> inuse
= new HashSet<String> ();

private String url;
private int id;
private ObjectLock lock;

public Executor(String url, int id,
ObjectLock lock) {
this.url = url;
this.id = id;
this.lock = lock;
}

public void run() {
try {
System.out.println("[" + id +
"] Started to process " + url);
System.out.println("[" + id +
"] Locking " + url);
lock.lock(url);
System.out.println("[" + id +
"] Lock acquired " + url);
// Yes, I know this is unnecessary.
// But just to be absolutely sure,
// this is a test after
// all...
String internedUrl = url.intern();

if (inuse.contains(internedUrl)) {
System.out.println("[" + id +
"] ERROR: COLLISION " + url);
throw new AssertionError(
"Bad lock implementation!");
}

inuse.add(internedUrl);
Thread.sleep(5000);
inuse.remove(internedUrl);

System.out.println("[" + id +
"] Releasing " + url);
lock.unlock(url);
System.out.println("[" + id +
"] Lock released " + url);
System.out.println("[" + id +
"] Thread finished ");
} catch (InterruptedException ex) {
System.out.println("[" + id +
"] Interrupted: " + ex);
}
}
}

/**
* @param args Not used.
*/
public static void main(String[] args) {
String [] urls = {
new String("http://www.google.com"),
new String("http://www.google.com"),
new String("http://www.google.com"),
new String("http://www.google.com"),
new String("http://www.google.com"),
new String("http://www.live.com"),
new String("http://www.live.com"),
new String("http://www.live.com"),
new String("http://www.yahoo.com"),
new String("http://www.yahoo.com")
};
ObjectLock lock = new ObjectLock();
for (int i = 0; i < 128; ++i) {
(new Executor(urls[i % urls.length],
i, lock)).start();
}
}
}

5 comments:

dimrub said...

How, er, complicated. Why not append the resource being processed with a random string of sorts (uuid or something) and then atomically remove it at the end of processing, taking a small penalty for possible (but unlikely) duplicate processing, but greatly simplifying and boosting the code in the general case?

Sergey Solyanik said...

Dimrub,

In my case what you suggest would have been more complicated - because I have (but not always) several intermediate files, and several resultant files. This allows me to forget about synchronization in most of my code, and only care about it at the very top handler. But of course every situation is different and I can easily see cases where your would be better.

Anonymous said...

Read it twice... but still scratch my head. If duplicated requests results have to be collapsed to first ... to optimize some thing it does not look like synchronization issue to me even if one request handled in several steps. So simple serialization of cash element control blocks may do the trick. Duplicated request queued in some kind of "completion" list, that should also be guarded by simple lock. So, there is no complex dependences meaning no dead locks and only very few structures actuality guarded and locked for a very short time - : data that defines status of request. may be I missed some thing about problem or design, but I do not understand why two duplicated requests have to "fight" for some thing and do synchronization between each other, instead you just wait if you are not the first one for that URL. That is also handled on the "very top level" :

First come - "map" to cash and do all the work.
Duplicate - register for final result and sleep till done.

The way to find duplicate : check if maped.

if work was already done : adding ti completion queue will auto - dequeue .

Serban said...

I may be wrong here, but I am not confident this approach scales too well.

Namely, I think that if you have threads that take a long time to process their requests, you may end up in a situation where a thread T2 acquires the lock on the urlLocks map, then attempts to lock() the urlLock only to find that another thread T1 has already acquired it and is crunching on the work.

Now, T2 gets blocked waiting for T1 to release the urlLock, all this while holding the urlLocks map lock.

Other threads that complete their works will attempt to get the urlLocks map lock but won't be able to, since T2 holds it. That will serialize a lot of threads around the slow-goers.

I also did not get the part about locking out of order - in your example the lock() method first acquires the urlLocks map lock, then acquires the lockedUrls map lock. However, the unlock() method first attempts to acquire the lockedUrls map lock, then the urlLocks map lock.

Considering my example above, if you have thread T2 waiting for T1 to complete, T1 may never be able to enter the synchronized (urlLocks) block in the unlock() method because T2 holds the lock on the map.

Or maybe it's just too late for me to focus on concurrency stuff right now... better go read how people spend to little on education...

Regards,
Serban

Sergey Solyanik said...

Serban, you are absolutely correct. Not only this did not work aby better than a global lock, but it was way, way, way more complicated than necessary.

Thank you for pointing this out!

The post has been substantially rewritted. Wonders of the peer review!