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();
    }
  }
}