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

Peter Kovacs peter.kovacs.1.0rc at gmail.com
Tue Jan 9 08:21:35 EST 2007


Does the "Batch" class in this example bear some well-known semantics?
(E.g. does it come from JCIP, which I haven't read.)

Thanks
Peter

On 1/9/07, Holger Hoffstätte <holger at wizards.de> wrote:
>
> 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
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>



More information about the Concurrency-interest mailing list