Re: synchronized HashMap vs. HashTable

From:

Daniel Pitts <newsgroup.spamfilter@virtualinfinity.net>

Newsgroups:

comp.lang.java.programmer

Date:

Fri, 23 May 2008 12:15:03 -0700

Message-ID:

<483717d5$0$11200$7836cce5@newsrazor.net>

Tom Anderson wrote:

On Fri, 23 May 2008, Daniel Pitts wrote:

Mikhail Teterin wrote:

Here is the explanation... My application has to send questions to an
external service, which replies asynchronously (some questions are
easier
to answer than others).

Upon submitting a question, the service's API returns a correlation ID,
which the response will also bear.

To match the received replies with the asked questions, I'm using a
Map<CorrelationID,MyObject>.

Once in a blue Moon, an answer would come back to the replies-processing
thread /before/ the questions-asking thread had the chance to finish
inserting the ID into the Map. The replies-processing thread then
treated
the reply as "unsolicited", etc.

You should look into Executors and Callable and Futures.

You can keep track of Future values, ones that you expect to have a
value for eventually.

I don't think there's any way to use a future, a callable, or an
executor to beat the race condition here. Those would be useful if the
problem was to do with an answer-demanding thread getting to the map
before an answer-supplying thread: you could use futures as a way of
giving the demanding thread a promise of an answer some time in the future.

But that isn't what the problem is. The problem is the other way round:
the answer-handling thread demands questions from the map, so it can
send answers to them, but it's possible for that thread to beat the
question-supplying thread there. This is despite the fact that the
question-supplying thread goes to the map as soon as it's sent the
question over the wire - it's a simple race condition.

AIUI, we're keying the map by correlation ID, and we don't have that
until we've sent the question over the wire, so there's no way to put
the question into the map before asking it, which would otherwise be a
simple solution.

Alternatively you need to serialize the act of putting into the map
*before* announcing that its available.

Announcing?

You might also consider using a ConcurrentMap for your problem.

Again, doesn't solve the problem. Although it is definitely a good idea.

I've thought of another solution: make the map sort of bidirectional
(and not typesafe). If the questioning thread gets there first, stash
the question; if the answering thread gets there first, stash the
answer. Both threads have to be prepared to deal with the job of
reuniting a question and an answer. You could use a normal map for this,
and lock on every get-test-put sequence, but a more scalable approach
would be to use a ConcurrentMap and its putIfAbsent method: the
questioner does:

Question q = ... ;
Answer a = (Answer)map.putIfAbsent(correlationId, q) ;
if (a != null) reunite(q, a) ;

And the answerer does:

Answer a = ... ;
Question q = (Question)map.putIfAbsent(correlationId, q) ;
if (q != null) reunite(q, a) ;

tom

I think I see the situation a little better now...

One thing to try, if possible: Make the question/answer synchronous
rather than asynchronous.

If you can't do this, then here's the next best thing:

Create a new class that keeps track of a Question and and Answer. Lets
call it Conversation.

Have one map ConcurrentMap<CorrelationId, Conversation>.
Have one method:
Conversation getConversation(CorrelationId id) {
     Conversation c = new Conversation();
     if (!map.putIfAbsent(id, c)) {
       return map.get(id);
     }
     return c;
}

in answer: getConversation(id).putAnswer(answer);
in question: getConversation(id).putQuestion(question);

Conversation.put* should both sync on the same lock (whether using Lock
or synchronize).

While they still have the lock, the should call checkCompleted();
checkCompleted will check if both Answer and Question are set, and will
invoke the appropriate behavior when they are.

Hope this helps.
Daniel.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>