Nested synchronized blocks on interned Strings

Question

The title sounds like there is a lot of problems ahead. Here's my specific case:

This is a travel tickets sales system. Each route has a limited quantity of tickets, and so purchasing the last ticket for a given route shouldn't be accessible to two people (a standard scenario). However, there is the "return ticket" option.. So, I'm using the unique route ID (database-provided) to do the following:

synchronized(bothRoutesUniqueString.intern()) {
    synchronized (routeId.intern()) {
        if (returnRouteId != null) {
            synchronized (returnRouteId.intern()) {
                return doPurchase(selectedRoute, selectedReturnRoute);
            }
        }
        return doPurchase(selectedRoute, selectedReturnRoute);
    }
}

The two inner synchronized blocks are in order to make threads stop there only if a ticket for this particular route is being purchased by two people at the same time, not if tickets for two distinct routes are purchased at the same time. The second synchronization is if course due to the fact, that someone may be attempting to purchase the retuern route as a outbound route at the same time.

The outer-most synchronized block is to account for the scenario, when two people purchase the same combination of tickets, reversed. For example one orders London-Manchester, and the other orders Manchester-London. If there isn't an outer synchronized block, this situation could lead to a deadlock.

(The doPurchase() method either returns a Ticket object, or throws an exception, if there are no more tickets available)

Now, I'm perfectly aware this is a very awkward solution, but, if it works as it is expected to, it gives:

• 10 lines to handle the whole complex scenario (and with proper comments, it won't be that hard to understand)
• no unnecessary locking - everything blocks only if it has to block.
• database agnosticism

I'm also aware that such scenarios are handled by either pessimistic or optimistic database locks, and since I'm using Hibernate, these won't be hard to implement either.

I think horizontal scaling can be achieved with the above code using VM clustering. According to Teracotta documentation, it allows turning a single-node multithreaded app to a multi-node, and:

Terracotta tracks String.intern() calls and guarantees reference equality for these explicitly interned strings. Since all references to an interned String object point to the canonical value, reference equality checks will work as expected even for distributed applications.

So, now onto the questions themselves:

• do you spot any drawbacks to the above code (apart from its awkwardness)?
• is there an applicable class from the java.util.concurrent API to help in this scenario?
• why would a database locking be preferable to this?

Update: Since most of the answers are concerned with OutOfMemoryError, I crated a benchmark for intern(), and the memory hasn't been eaten up. Perhaps the strings table is being cleared, but this wouldn't matter in my case, since I need the objects to be equal in race conditions, and clearing of the most recent Strings should not happen at the point:

System.out.println(Runtime.getRuntime().freeMemory());
for (int i = 0; i < 10000000; i ++) {
    String.valueOf(i).intern();
}
System.out.println(Runtime.getRuntime().freeMemory());

P.S. The environment is JRE 1.6

Answer 1

why would a database locking be preferable to this?

Your in-code solution will only work if you have only one front-end to the database, which means you can only scale vertically (with more processing power on a single front-end box). As soon as you start getting into a web farm or similar (horizontal scaling), your solution doesn't work anymore.

Answer 2

I would say the main drawback is your interning of the synchronization objects.

I think the intern map is limited in size, so at some point the unique strings will start to be pushed out of it, so you will not be locking on the same objects if your program runs for a long enough time.

On the other hand if in some implementations intern map is not bounded by size, there is a possibility that you may run out of memory.

I would have not rely on the internal logic of intern and have created my own object to hold stings and locks.

Other than that, there is nothing wrong to use nested locks. Just don't try to lock in reverse order somewhere else in your code.

Answer 3

Interning is a moderately expensive operation, and there's a small chance that it will chew up more CPU time than possible alternatives. But certainly, I can't see it taking longer in wall time than a query to a database. The only scenario where I could imagine a DB-based implementation to win is if you have so many threads doing this in parallel that you'd be happy to let the DB do some of the work, so your CPU will be waiting but not grinding in the meantime.

For the admittedly limited scope of your intended application, your solution looks brilliant to me.

Answer 4

The way to go might better be a singleton, RouteProvider, which gives a Route only once, blocking or returning null if the route is already used. I'm thinking of a commons GenericObjectPool like construct with only one take per Route.

A Route would have a Origin place and a Destination, and have an appropriate equals and HashCode.

You'd need to take() and release() a route so the RouteProvider knows it's available again. Don't forget to take exceptions into account and release() in a finally clause :)

Anyway, I'd never go for something implementation dependend as an intern string.

Answer 5

I can offer two pieces of advice.

1) The standard way to avoid deadlocks is to sort your lock acquisition so they are acquired in a well known order. This would avoid some of the awkwardness of using three locks when only two are needed.

2) Are you asking this question explicitly and only in the presence of Terracotta? If so then it's not necessary to intern your Strings. It's maybe non-obvious, but when converting a synchronized (String) into a Terracotta lock, Terracotta locks on the VALUE of the String, not on the identity. Obviously if you rely on this behavior then you should comment it since interning as you have done is required in any case other than in the presence of Terracotta, so any standard Java programmer having a look at your code would justifiably be terrified :)

Answer 6

Another thought I have on the way you have implemented this is that you are using a pessimistic locking scheme.

It depends on the overall probability of collisions which scheme would be better - optimistic or pessimistic.

But given the problem domain, I suspect that in a given time window it's highly improbable that you would have a collision, so using a pessimistic locking scheme will be very slow compared to an optimistic locking scheme.

An optimistic locking scheme is what is used by default in a typical database scenario, for example using Hibernate.

What it means is you simply try to make the purchase without worrying about locking, and only when the purchase attempts to commit, do you check to make sure no one else made that purchase.

This type of behavior is easily expressed in Hibernate - and will scale significantly better than your proposal. Also, since you can do it very easily and in a very standard way using Hibernate, you will find your code easier to debug and maintain and scale because complex non-standard solutions to problems like this are more likely to be bug-prone in difficult to identify ways, are more difficult to maintain, and usually are much more difficult to scale.

Read this page (especially section 11.3) for more details on Hibernate's concurrency and locking support.