Skip to main content

Rethinking Multi-Threaded Design Priniciples

March 3, 2010



Introduction

For many years, we have been using Java Threads for developing numerous Client-Server based applications. While it's always desirable to have a highly responsive Client application,
handling a high volume of client requests has always been a prime goal of any Server application. However, designing a highly-scalable server requires lots of analysis. Without careful
design and adherence to a well thought out underlying policy, a thread based system can fail to produce the desired outcome.

In this article, we'll discuss certain design principles that should be followed when the objective is to build an efficient, thread-safe application.

Thread Safety lies in Domain

As a design principle of thread safety, the vital point to look into is "Domain First." After all, the whole structure of an application lies on the Domain itself. If you get your domain model right,
most of the problems are automatically taken care of. A model represents certain aspects of business logic
consisting of various constraints and invariants. Understanding the pre and post conditions of a model are much needed in order to make the realized application thread-safe.

Let's imagine an travel agency that arranges budgeted cars for their traveler guests. They need an interactive car rental application that allows
them to book multiple cars at different tourist locations on different dates within a specified price range. As they keep making multiple rental requests,
at the same time if the system fails to find a car at particular location within price range, they want to be notified with suggested locations on
the same screen.

We can think of this as a booking Requester taking the renal requests and putting them in a thread safe collection CarBookings that would be read
concurrently by an actual CarFinder process to provide suggested locations. If CarFinder succeeds, it forwards this via the booking engine to the booking rental location. If CarFinder does not succeed, it tries to find the cars based on the price range and nearest location. Once found, it adds the info to another thread safe collection
CarBookingAdvices.

There are many thread safe data structures available, but if you're sure about the Thread Safety policy that you want to adhere to, it's best to create a domain model on your own. For example:

[prettify]
//Defining first CarBookings
class CarBookings{
    private final Set bookings = new HashSet ();

    public synchronized void putCar(CarBooking booking){
        bookings.add(booking);
    }

    public synchronized Set getBookings(){
        return Collections.unmodifiableSet(new HashSet(bookings));
    }
}

Since the methods putCar() and getBookings() provide a secure way of accessing the non-thread-safe instance variable bookings, the CarBookings can be used safely by both the BookingRequester and CarFinder process running in different threads. This meets our simple thread safety requirement.

//Defining BookingAdvice
class BookingAdvice{
    private final String bookingId="";
    private final BigDecimal rate=new BigDecimal("");
    private final String location="";
//Getter and Setter ommited
}

class BookingAdvices{
    private final Set advices = new HashSet();

    public synchronized void putAdvice(BookingAdvice advice){
        advices.add(advice);
    }

    public synchronized Set getAdvices(){
        return Collections.unmodifiableSet(advices);
    }
}

//Defining Requester
class BookingRequester{
    private CarBookings bookings;
    private BookingAdvices advices;

    public void requestBooking(CarBooking booking){
        bookings.putCar(booking);                     //Line 1
        displayAdvice(advices.getAdvices());      //Line 2
    }

    private void displayAdvices(Set advices){
        //Displays the advices on the same screen
    }
}

//Defining Finder
class CarFinder{
    private BookingAdvices advices;
    private CarBookings bookings;

    public void processAdvice(){
        List adviceList = getGeneratedAdvices();
          for(BookingAdvice advice: adviceList)
            advices.putAdvice(advice);                //Line 3

        findAndProcessBookings(bookings.getBookings()); //Line 4
    }

    private List getGeneratedAdvices(){
        //Generate advice based on requests
    }

    private void findAndProcessBookings(Set bookings){
        //Finds advice for the booking if required
    }
}

[/prettify]

Hiding Model State

But, there is a caveat: if the CarBooking class is mutable, then there is a possibility of modifying each CarBooking instance in the set returned by getBookings(). Does it make our model brittle? Well, as long as we can make sure that it won't be modified later on, we'll be fine with that. But, sometimes it's easier get thread safety by hiding the model state and blocking the access to it thereafter. Here, we could do that by adding a copy constructor to the mutable CarBooking or making it immutable:

//Defining mutable CarBooking
class CarBooking{
    private String bookingId;
    private String location;
    private BigDecimal rate;

    //Copy constructor
    public CarBooking(CarBooking booking){
        this.bookingId= booking.getBookingId();
        this.location= booking.getLocation();
        this.rate= booking.getRate();
    }
    //public Getter methods below
}

class CarBookings{
    //Modified version
    public synchronized Set getBookings(){
        Set newBookings = new HashSet ();
        for(CarBooking b : bookings){
            CarBooking newBooking = new CarBooking(b);
            newBookings.add(newBooking);
        }
        return Collections.unmodifiableSet(newBookings);
    }
}

So, when getBookings() returns, it returns a copy of the CarBooking, thus not allowing modification of the original state--which makes it purely thread safe.

//Defining immutable CarBooking
class CarBooking{
    private final String bookingId;
    private final String location;
    private final BigDecimal rate;

    public CarBooking(String bookingId, String location, BigDecimal rate){
        this.bookingId= bookingId;
        this.location= location;
        this.rate= rate;
    }
    //Getter ommited
}

In case we make CarBooking immutable, we can just return the bookings set from getBookings() as shown in our first CarBookings example.

Do Thread Delegation if you can

Sometimes you might find yourself being overburdened with handling the thread safety in your domain model; in that case you can simply delegate it to a range
of Java built-in data structures that are already proven and tested to be thread safe. Like in our example, if we had to use bookings as HashMap, where String could represent bookingId, we could have easily replaced that with ConcurrentHashMap--which is a thread safe HashMap. Likewise there are many other data structures available (under the java.util.concurrent package) like CopyOnWriteArrayList and ConcurrentLinkedQueue, to name a few.

Figuring Single Thread Confinement

To coordinate multiple threads in a lock-based application, the OS and JVM have to burn fair amount of CPU cycles for context switching and thread
scheduling--making the system less responsive sometimes.

This can be avoided by allowing only one thread to gain access to work on a unit model (either CarBooking or BookingAdvice) at a time, and also making sure that same unit model should not be re-worked by the same thread. To make this happen, we can employ bounded BlockingQueues (BookingQ and AdviceQ) that would act
as a mediator between Requester and CarFinder.
So, for a rental request, the Requester would just create a CarBooking and put it in the BookingQ queue, and on the other hand, CarFinder would take that
off of the queue. The same thing will be done by the CarFinder to return a BookingAdvice in the AdviceQ queue. This way, multiple Requesters and CarFinders can work
asynchronously, making the system highly responsive.

Use synchronized lock wisely

While synchronized lock provides an easy way to work with multiple threads, improper usage of the lock may cause unpredictable results. This becomes obvious when multiple locks are acquired to perform an atomic operation where the first lock is held until last lock operation is performed. Let's consider our BookingRequester and CarFinder that are using simple java Sets instead of CarBookings and BookingAdvices. Here two operations: putting request and getting
advices for Requester (vice versa for CarFinder, lines 5,6,7 and 8) become implicitly atomic under the same lock:

class BookingRequester{
    private final Set bookings = new HashSet();
    private final CarFinder finder;

    public BookingRequester(CarFinder cf){
        finder = cf;
    }
    public synchronized void requestBooking(CarBooking booking){
          bookings.add(booking);                    //Line 5

        displayAdvice(finder.getAdvices());    //Line 6
    }

    public synchronized Set getBookings(){
        return bookings;
    }
}
class CarFinder{
    private final Set advices = new HashSet();
    private BookingRequester bookings;

    public CarFinder(BookingRequester br){
        bookings = br;
    }
    public synchronized void processAdvice(){
        List adviceList = getGeneratedAdvices();
          for(Advice advice: adviceList
              advices.add(advice);            //Line 7

        findAndProcessBookings(bookings.getBookings());    //Line 8
    }

    public synchronized Set getAdvices(){
        return advices;
    }

}

Now, a problem starts to creep in when two threads T1 and T2 try to call Requester requestBooking() and CarFinder processAdvice() respectively at the
same time. During requestBooking, before T1 calls getAdvices() on CarFinder (Line 6), it has to wait for T2 to complete processAdvice. But to complete processAdvice, T2 needs to call getBookings() on Requester (Line 8), which won't happen until T1 completes requestBooking()--leading to a deadlock situation.

In our previous implementation of BookingRequester and CarFinder, we have already delegated the two operations to be handled independently under different locks (one for CarBookings and another for BookingAdvices, lines 1, 2, 3 and 4) to avoid any deadlock.

But, here we can simply resolve it by moving synchronized from the entire method to only the time required to put the booking (Line 5) and advice (line 7).

Another important point regarding deadlocks would be the order in which the resources are accessed in an atomic operation. If two threads work on an operation with two resource locks being held in a different order, it can lead to a deadlock situation too. So, make sure all threads calling an atomic operation get all resource locks in the same order.

Conclusion

Designing and improvising a thread based application is a challenge. But by following certain design principles and guidance, this can be easily overcome. At the same time, clear understanding of thread safety policy is also essential as it helps you simplify the design. There are many other techniques available that we couldn't cover here. However, the principles presented here will always assist you in overcoming some of the thread safety related hurdles you might be facing as you develop thread-safe applications intended for operation on modern multicore and multiprocessor computers.


width="1" height="1" border="0" alt=" " />
Dibyendu Roy has more than ten years of design and development experience in various domains including Banking and Financial Systems, Business Intelligence tools and ERP products.
Related Topics >> Java Tech   |   Performance   |   Programming   |   Featured Article   |   

Comments

The fact that the code

The fact that the code sections are not formatted properly makes this article hard to read. Please try cleaning then up. Thanks, Gili

Hi, I agree with you that

Hi,

I agree with you that writing concurrent code is very complex, and if you follow guidelines you can get far.

But in a lot of cases you don't want this in your code, especially if you are writing more business-like code where you want the business logic to remain simple instead of it being sprinkled with synchronized, volatile etc. And if the number of classes and interaction between objects increases, concurrency control complexity tends to get very messy/complex leading to all kinds of problems (especially since most developers don't understand concurrency control very good).

One of the new directions of concurrency control is STM and the BookingRequester problem could be solved using STM like this:

@TransactionalObject
class BookingRequester{
...private final TransactionalSet bookings = new TransactionalHashSet();
...private final CarFinder finder;

...public BookingRequester(CarFinder cf){
......finder = cf;
...}

...public void requestBooking(CarBooking booking){
......bookings.add(booking);
......displayAdvice(finder.getAdvices());
... }

...public Set getBookings(){
......return Collections.unmodfiableList(bookings);
...}
}
In this example all access to BookingRequester has become transactional.

The cool thing is that you can also compose new transactional operations using other transactional operations:

@TransactionalMethod
static void requestBookings(BookingRequester requester, CarBooking... bookings){
...for(CarBooking bookig: bookings){
......requester.requestBooking(booking)
...}
}

This is very hard to realize with normal lock based concurrency control without exposing the internal lock of the object; so exposing your implementation details.

You could even make it possible that a thread waits for a certain booking to retrieve (is added to the BookingRequester):

CarBooking findBookingWithValueBiggerThan(float atleast){
...for(Booking booking: bookings){
......if(booking.rate>atLast){
.........return booking;
......}

......retry(); // static import that does the blocking
......return null;//is never called..
...}
}


And if you want you can combine this using an orelse so that you can wait on multiple BookingRequester:
atomic{
...{
...... return bookingRequester1.findBookingWithValueBiggerThan(10);
...}orelse{
......return bookingRequester2.findBookingWithValueBiggerThan(10);
...}
}

This Very hard to realize with traditional concurrency control.

This is pseudo code btw because the template I need to use in Java are very very messy... will be fixed when closures are added to java).

PS I'm the founder of the STM Project: Multiverse http://multiverse.codehaus.org

The title is 'Rethinking

The title is 'Rethinking Multi-Threaded Design Priniciples'. But I think the article is more like 'My First Threading Excercise'.

I'm not convinced that

I'm not convinced that CarBookings can be used safely across multiple threads by just simply synchronizing both of its methods.

CarFinder is storing a reference to the (albeit unmodifiable) Set returned by CarBookings.getBookings(). This is wrapping the underlying bookings Set - the unmodifiable set is still delegating directly to bookings for read operations such as iteration.

Imagine CarFinder starts to iterate through the set. There does not appear to be anything stopping BookingRequester adding to the underlying set via CarBookings.putCar() while CarFinder is iterating, and so there is the potential here for a ConcurrentModificationException to occur while CarFinder is iterating.

Apologies - I know it's not the core of the article, but I am worried that this is potentially a bad example. Maybe there is something I can't see to protect against this case?

Follow the the section Hiding

Follow the the section Hiding Model State: class CarBookings{ //Modified version public synchronized Set getBookings(){ Set newBookings = new HashSet(); for(CarBooking b : bookings){ CarBooking newBooking = new CarBooking(b); newBookings.add(newBooking); } return Collections.unmodifiableSet(newBookings); } } Here, the getBookings would return a brand new copy of the Set without compromising the thread safety.

Confused by thread safety of

Confused by thread safety of initial attempt.

Thanks - I was confused by the statement against the first attempt at CarBookings. The article states:
Since the methods putCar() and getBookings() provide a secure way of accessing the non-thread-safe instance variable bookings, the CarBookings can be used safely by both the BookingRequester and CarFinder process running in different threads. This meets our simple thread safety requirement.

I am suggesting that the first implementation of CarBookings does not meet thread safety requirements, for the reason I gave earlier. I can see that the second go at CarBookings does not have this problem.

Yes, first implementation

Yes, first implementation would also meet the thread safety as long as you dont attempt to modify the returned set. See: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#unmod... Query operations on the returned set "read through" to the specified set, and attempts to modify the returned set, whether direct or via its iterator, result in an UnsupportedOperationException.

Exactly, but... Imagine on

Exactly, but...
Imagine on thread 1, I obtain a reference to the unmodifiable set. I then use an iterator on the set to iterate through the list. I am not attempting to change it so UnsupportedOperationException is not an issue.

While I am half way through iterating the Set on thread 1, another thread 2 makes a further booking and thus modifes the underlying set.

This means that on Thread 1, a ConcurrentModificationException will occur, since the underlying set has been changed during iteration.

To me, this indicates that the class is not Thread-safe.

You are right on your point.

You are right on your point. But the main focus of that part is centered around not allowing to modify the underlying state of the set bookings. I know you could get ConcurrentModificationException, but you don't get a chance to add/delete item to/from it - That's the whole point being made. It just that simple without getting more complicated. And your point can be easily addressed by making: public synchronized Set getBookings(){ return Collections.unmodifiableSet(new HashSet(bookings)); } But thats not the point. Again, we know that it has some pitfall as you can update the mutable item of the Set, so the following section shows the way to handle it. Hope this clarifies what I intended.

Perfect - thanks for

Perfect - thanks for clarifying.

Personally I think you have

Personally I think you have really taken the time to show us all the ins and outs of this. Great examples and explanations and very well-written as well.
  1. Casino Online Gratis
  2. I think this online casino has casino online games for every gambling budget and they also offer generous bonuses on deposits.

Thank you.

Thank you.

I see you already answered

I see you already answered another commenter regarding this, but I am sorry - that just won't cut it. If the article is about thread safety the example code should be thread safe. If soem example code is not thread safe, this should be *clearly* pointed out. Your statement "This meets our simple thread safety requirement." is clearly false - since you are returning a view of the set. Not even querying this view is thread safe, let alone iterating over it.

It is true that your modified version solves this problem - but you don't even mention that in the article! The focus is *only* on making CarBooking immutable. Additionally, copying each CarBooking is completely unnecessary given that CarBooking is immutable. The new implementation would be better written as:

public synchronized Set<CarBooking> getBookings(){
return new HashSet<CarBooking> (bookings);
}
Having a copy constructor for an immutable class seems rather useless. There may be rare cases when it is desirable, but normally copying something that is immutable will just waste cpu cycles and consume memory.

By the way, if CarBooking were mutable, it would mean trouble even disregarding thread safety: Using instances of mutable classes as keys in a HashSet (or HashSet) is a bad idea, at least if mutable fields are involved in the computations of equals and hashcode. Consider this code:

Set points = new HashSet<Point2D> ();
Point2D p = new Point2D.Double (1.0, 1.0);
points.add (p);
p.setLocation (0.0, 1.0);
System.out.println (points.contains(p));

What would it print?

I also don't understand why generics and the final-modifier are used so inconsistently in the example code (perhaps the generics is due to unescaped <>?). And comments like the one below are completely unhelpful:

//Defining BookingAdvice
class BookingAdvice{
...
}

What additional information does the comment convey? Is it intended for a reader completely unfamiliar with Java?

I am sorry to sound so harsh. I think it is a good thing to share your knowledge with other people. But, if you do, you have to go the extra mile to be clear and correct. There is an enormous amount of information about Java on the internet. There is a lof of good information, but most of it is noise that just makes it harder to find the good stuff. Sadly, this article is in the latter category in its current state. I suggest reworking or retracting it.

Thanks for your comment. We

Thanks for your comment. We know every approach has some pros and cons and it’s hard to address everything at first place. Here we started with a trivial example and tried to improve it in the following section. As we have stressed upon adherence to a well thought out underlying policy, our policy here is not allowing the client code to modify bookings set obtained from getBookings() as part of thread safety. The same policy may not be same for everyone.

You are right, I could return new HashSet (bookings);, but how do you set expectation of client code that once it gets bookings set from getBookings(), it can’t modify it. That’s why we have returned the Collections.unmodifiableSet, without which client is unaware of underlying policy. The immutable CarBooking is used for the same purpose.

Again, it may not be the exact solution for everyone.

On BookingAdvice, I hope it's pretty obvious that it's just the model object with BookingId, rate and location properties set by CarFinder.

//Defining BookingAdvice
class BookingAdvice{
private final String bookingId="";
private final BigDecimal rate=new BigDecimal("");
private final String location="";
//Getter and Setter ommited
}

Since it was similar to CarBooking, it was made self explanatory to make the article concise.
Hope this has helped to remove some of the noises a bit.

First of all, I appreciate

First of all, I appreciate the tone of your response. I was arguably too "aggressive" in my comment, and I am glad you kept your response to the point.

However, I still want to point out that:
  • You need to copy the set for thread safety.
  • You don't need to copy the immutable CarBooking instances for thread safety.

    I don't think the article makes this sufficiently clear.

    Regarding returning an Collections.unmodifiableSet, I think that is a valid design decision to avoid confusing callers whether they are updating the "real" set or not. But it is neither necessary nor sufficient for thread safety: In that case you still need to do
    return Collections.unmodifiableSet(new HashSet<CarBooking>(bookings));