ConcurrentHashMap: remove on condition

Question

I have a ConcurrentHashMap which used as an in-memory storage (or a cache, you might say)

What I'd like to achieve is: Concurrently check if an item "is ready", and if so, remove it from the map (+ return it to the caller). There's no direct method that enables me to do that.

The only solution I came up with is having an ItemContainer which will contain both the item and meta-data (isReady field). On every access, I'll have to apply merge or compute operations. Essentially replacing the container of the object on every access/check.

Questions:

1. Is my solution seem reasonable?
2. Are there any good libraries that achieves something similar?

I added a "boilerplate" code as requested:

public class Main {

    public static void main(String[] args) {
        Storage storage = new Storage();
        storage.put("1", new Record("s", 100));
        storage.put("2", new Record("s", 4));
        storage.removeIf("1", Main::isReady);
    }

    public static boolean isReady(Record record) {
        return record.i > 42;
    }

    public static class Record {

        public Record(String s, Integer i) {
            this.s = s;
            this.i = i;
        }

        String s;
        Integer i;
    }

    public static class Storage {
        ConcurrentHashMap<String, Record> storage = new ConcurrentHashMap<>();

        public void put(String key, Record record) {
            storage.put(key, record);
        }

        public Record removeIf(String key, Function<Record, Boolean> condition) {
            return null; // TODO: implement
        }
    }
}

Other solutions (with tradeoffs):

1. Always remove() on check and then merge() it back to the map.
2. Use a cache with some reasonable policy of items evacuation (i.e. LRU) and check only evacuated items.

Based on @ernest_k solution:

public Record removeIf(String key, Predicate<Record> condition) {
    AtomicReference<Record> existing = new AtomicReference<>();

    this.storage.computeIfPresent(key, (k, v) -> {
        boolean conditionSatisfied = condition.test(v);

        if (conditionSatisfied) {
            existing.set(v);
            return null;
        } else {
            existing.set(null);
            return v;
        }
    });

    return existing.get();
}

Answer 1

ConcurrentHashMap already gives you the guarantee of atomicity with computeIfPresent.

If the value for the specified key is present, attempts to compute a new mapping given the key and its current mapped value. The entire method invocation is performed atomically. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

So you can just use that:

public Record removeIf(String key, Predicate<Record> condition) {

    AtomicReference<Record> existing = new AtomicReference<>();

    this.storage.computeIfPresent(key, (k, v) -> {
        existing.set(v);
        return condition.test(v) ? null : v;
    });

    return existing.get();
}

Note that I used Predicate<Record> as it should be preferred to Function<Record, Boolean>.

The reason for storing the current value in an AtomicReference here is to make sure that the returned value is the same one that the predicate was testedd against (otherwise there might be a race condition).

Answer 2

The answer which uses an AtomicReference is in essence an attempt of a workaround on the "why variables used in lambdas need to be effectively final" problem. It is an ok'ish workaround to this problem, but an AtomicReference will have a little bit of overhead. Another option is to use an array reference although I understand that is frowned upon (however, I can't see why it would have unexpected side-effects in this case?)

Alas, here's another one. I think a by-the-book solution would be this:

public class MyMapClass<K,V> {        
    private final ConcurrentMap<K,V> storage = new ConcurrentHashMap<>();
    
    public V removeIf(K key, final Predicate<V> condition) {
        BiFunctionForConditionalRemove bf = new BiFunctionForConditionalRemove(condition);
        storage.computeIfPresent(key, bf);
        return bf.existingValue;
    }
        
    private class BiFunctionForConditionalRemove implements BiFunction<K, V, V> {
        private V existingValue;
        private final Predicate<V> condition;

        public BiFunctionForConditionalRemove(Predicate<V> condition) {
            this.condition = condition;
        }

        @Override
        public V apply(K existingKey, V existingValue) {
            this.existingValue = existingValue;
            return condition.test(existingValue) ? null : existingValue;
        }
    }
}

This for sure is a lot more verbose, but I would argue it is a bit faster than using a temporary AtomicReference for each invocation. (just a wild claim, I haven't measured it). The assumption is that using a throw-away instance of BiFunction for each invocation is faster than using a throw-away AtomicReference for each invocation. In fact I don't think it adds overhead to use a specialized version of BiFunction compared to using a Lambda. Same work for the JVM.

Side note: One thing I don't like with the using-computeIfPresent-trick for doing a conditional remove is that I can't find evidence in the source code for ConcurrentHashMap that JDK developers have anticipated this situation, although it will work. If the majority of your use-cases do not hit the condition (meaning no delete) then ConcurrentHashMap will still do an (unnecessary) replace operation in the map. It doesn't seem to check if newVal == oldVal but blindly proceeds with the operation regardless. This means you'll have locking contention on the map even where it is not needed. I hope I'm wrong on this. If not, there's for sure room for improvement in the JDK8 I've looked into.