ConcurrentHashMap Conditional Replace

Question

I'd like to be able to conditionally replace a value in a ConcurrentHashMap. That is, given:

public class PriceTick {
   final String instrumentId;
   ...
   final long timestamp;
   ...

And a class (let's call it TickHolder) which owns a ConcurrentHashMap (let's just call it map).

I wish to be able to implement a conditional put method, so that if there's no entry for the key, the new one is inserted, but if there is an existing entry, the new one is inserted only if the timestamp value in the new PriceTick is greater than the existing one.

For an old-school HashMap solution, TickHolder would have a put method:

public void add(PriceTick tick) {
   synchronized(map) {
      if ((map.get(tick.instrumentId) == null)
         || (tick.getTimestamp() > map.get(tick.instrumentId).getTimestamp()) )
         map.put(tick.instrumentId, tick);
      }
}

With a ConcurrentHashMap, one would want to drop the synchronization and use some atomic method like replace, but that's unconditional. So clearly the "conditional replace" method must be written.

However, since the test-and-replace operation is non-atomic, in order to be thread safe, it would have to be synchronized - but my initial reading of the ConcurrentHashMap source leads me to think that external synchronization and their internal locks will not work very well, so at a very minimum, every Map method which performs structural changes and the containing class performs would have to be synchronized by the containing class... and even then, I'm going to be fairly uneasy.

I thought about subclassing ConcurrentHashMap, but that seems to be impossible. It makes use of an inner final class HashEntry with default access, so although ConcurrentHashMap is not final, it's not extensible.

Which seems to mean that I have to fall back to implementing TickHolder as containing an old-school HashMap in order to write my conditional replace method.

So, the questions: am I right about the above? Have I (hopefully) missed something, whether obvious or subtle, which would lead to a different conclusion? I'd really like to be able to make use of that lovely striped locking mechanism here.

Answer 1

The non-deterministic solution is to loop replace():

do {
  PriceTick oldTick = map.get(newTick.getInstrumentId());
} while ((oldTick == null || oldTick.before(newTick)) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);

Odd though it may seem, that is a commonly suggested pattern for this kind of thing.

Answer 2

@cletus solution formed the base for my solution to an almost identical problem. I think a couple of changes are needed though as if oldTick is null then replace throws a NullPointerException as stated by @hotzen

PriceTick oldTick;
do {
  oldTick = map.putIfAbsent(newTick.getInstrumentId());
} while (oldTick != null && oldTick.before(newTick) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);

Answer 3

The correct answer should be

PriceTick oldTick;
do {
  oldTick = map.putIfAbsent(newTick.getInstrumentId(), newTick);
  if (oldTick == null) {
    break;
  }
} while (oldTick.before(newTick) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);

Answer 4

As an alternative, could you create a TickHolder class, and use that as the value in your map? It makes the map slightly more cumbersome to use (getting a value is now map.getValue(key).getTick()), but it lets you keep the ConcurrentHashMap's behavior.

public class TickHolder {
  public PriceTick getTick() { /* returns current value */
  public synchronized PriceTick replaceIfNewer (PriceTick pCandidate) { /* does your check */ }
}

And your put method becomes something like:

public void updateTick (PriceTick pTick) {
  TickHolder value = map.getValue(pTick.getInstrumentId());
  if (value != null) {
    TickHolder newTick = new TickHolder(pTick);
    value = map.putIfAbsent(pTick.getInstrumentId(), newTick);
    if (value == null) {
      value = newTick;
    }
  }
  value.replaceIfNewer(pTick);
}