[concurrency-interest] Attempt at yet another mostly-concurrent result cache

Holger Hoffstätte holger at wizards.de
Mon Jan 8 22:02:44 EST 2007


I'd like to ask for some ideas about how to make a previously completely
locked method as concurrent as possible. I've made great headway but a
final bit has thrown me off. I've read JCIP and the chapter on the
Memoizer but it didn't seem to apply here; if some variation of using
FutureTask can help here too I'd love to hear about it.

The single method basically receives an incoming message, looks up a
corrsponding result batch and when the batch is ready, a result is
returned. There are many batches and evaluation/result creation might take
a while, in which I don't want to lock out other threads happily doing
their thing.

Here is what I did so far:

// used to be a synchronizedMap()
private final ConcurrentMap cache = new ConcurrentHashMap();

// now unsynchronized
BatchResult process(Message msg)
{
    String batchKey = msg.getBatchId();

    // get-or-create with the (very rare) unnecessary new object
    Batch batch = cache.get(batchKey);
    if (batch == null)
    {
        batch = new Batch();
        Batch prev = cache.putIfAbsent(batchKey, batch);
        if (prev != null) batch = prev; // flip refs
    }

    // regardlesss of thread we now have a valid batch;
    // add a message and evaluate it

    // PROBLEM: we only want one thread to update the batch at a time;
    // Batches are threadsafe but we want atomic update/evaluation,
    // sync on the batch, so threads for other batches are not blocked
    synchronized (batch)
    {
        batch.add(msg);
        if (batch.isReady())
        {
            // BUG1
            cache.remove(batchKey);
            return batch.toResult();
        }
    }

    // no result yet
    return null;
}


So far so good, though the astute reader will immediately spot the obvious
bug: BUG1 marks a lost update when two threads synchronize on the same
batch, one wins and removes the batch, the second thread adds to a removed
batch which disappears in GC land.

So we try harder:

    // SYNC1
    synchronized (batch)
    {
        // check whether the batch reference is still valid,
        // update if necessary (same as above)
        batch = cache.get(batchKey);
        if (batch == null)
        {
            batch = new Batch();
            Batch prev = cache.putIfAbsent(batchKey, batch);
            if (prev != null) batch = prev; // flip refs
        }

        // BUG2
        batch.add(msg);
        if (batch.isReady())
        {
            cache.remove(batchKey);
            return batch.toResult();
        }
    }

Now a thread that was blocked at SYNC1 does the get-or-create thing and
even plays nice with another thread coming in from above. but wait..if the
thread entering the method at the top synchronizes on the batch created
inside SYNC1 (which it got hold of via the cache), it will not block at
SYNC1, possibly overtaking us and we no longer have per-batch atomic
update/evaluation at BUG2. right?

So, we try even harder..

    // SYNC1
    synchronized (batch)
    {
        // check whether thee batch reference is still valid,
        // update if necessary (same as above)
        batch = cache.get(batchKey);
        if (batch == null)
        {
            batch = new Batch();
            Batch prev = cache.putIfAbsent(batchKey, batch);
            if (prev != null) batch = prev; // flip refs
        }

        // acquire either the already held batch lock again or
        // a new one created either by the toplevel get-or-create
        // or the one we just did
        synchronized (batch)
        {
            batch.add(msg);
            if (batch.isReady())
            {
                cache.remove(batchKey);
                return batch.toResult();
            }
        }
    }

In case you made it until here, here's my question: is this sort of
"double-checked get-or-create" really enough or did I miss something?
My gut feeling teels me that the second synchronize block is somehow just
a nested repetition of the first (requiring a third one ad.inf.) and that
I need to unravel this in some entirely different way. It seems to me that
the batch itself is the only available object available to synchronize on.

I did several multi-threaded state transition diagrams and all conditions
I've played through so far seem to resolve, so I would really like someone
else to think this through. Of course all other funky tricks using
AtomicReference/CAS loops or RWLocks are welcome too. :)

thanks!
Holger


More information about the Concurrency-interest mailing list