Building a synchronous map, blocking on individual keys

Question

I want to build a repository class, as follows:

public class ResultRepository {

  private Map<String, Result> sqlRepository = Collections.synchronizedMap(new HashMap<>());

  public synchronized Result getResult(String key) {
    Result result = map.get(key);
    if (result == null) {
      result = doAnExpensiveOperation(key));
      map.put(key, result);
    }
    return result;
  }

  ...

}

This will work, currently, but will be slow if multiple calls are made to the getResult method if the expensive operation is required.

What I want, however, is this:

Retrieving the result for different keys is non-blocking
If the result for a specific key has already been created, it is returned immediately
If the result for a specific key has not already been created, it is generated (via the expensive operation)
If the result for a specific key has not already been created, but is being generated in a separate thread, the thread waits until the results are created and then returns this.

Is there a pattern I can apply to get this behaviour? I could theoretically have a Set of the pending result keys but this seems a bit janky. Maybe the repository could hold Future<Result> objects?

why don't you put result = doAnExpensiveOperation(key)); map.put(key, result); in synchroized block — Optional, Nov 26 '19 at 15:35
You might want to have a look at [ConcurrentHashMap#computeIfAbsent](https://stackoverflow.com/q/26481796/1225328). — sp00m, Nov 26 '19 at 15:36
@Optional won't this block method calls to other keys that aren't in the map? — Ekos IV, Nov 26 '19 at 15:38
no. it won't. You are not acquiring lock on any key. So that shall be fine. But if you are on jdk8 plus, computeIfAbsent makes more sense — Optional, Nov 26 '19 at 15:43
As others suggested just use `ConcurrentHashMap#computeIfAbsent`. This implementation of map has better concurrency level - meaning you can fetch keyA in threaA and `computeIfAbsent` in threadB - in paralel - at the same time. This implementation does not use a single lock for all access to the hash table -. — Oleksandr Papchenko, Nov 26 '19 at 15:49
Synchronized HashMap has a drawback that at a time only one thread can read it. Use ConcerrentHashMap, That uses RentrrantReadWrtiteLock which has the capability to read multiple threads at a same time. — Navneet Rabadiya, Nov 26 '19 at 16:01
PS. Given the context what you really should be doing here is using a _cache_ not roll-your-own. Look into https://github.com/ben-manes/caffeine/ — drekbour, Nov 26 '19 at 17:22

score 3 · Accepted Answer · answered Nov 26 '19 at 15:39

3

I think all of this comes with ConcurrentHashMap

    private Map<String, Result> sqlRepository = new ConcurrentHashMap<>();

    public Result getResult(String key) {
        return sqlRepository.computeIfAbsent(key, this::doAnExpensiveOperation);
    }

answered Nov 26 '19 at 15:39

drekbour

2,895
18
28

A small improvement, that works for _some_ applications, is to do the expensive stuff in a _speculative_ fashion: (1) check the map, and if no result is found then, (2) do the expensive stuff to create a new result _without locking any lock_, then (3) do an atomic `putIfAbsent(key, newResult)`. Finally (4), If it turns out that some other thread duplicated the effort and won the race, then throw away the `newResult`, and use the one that the other guy created. Performance gained by not locking a "expensive" operation can more than offset the performance lost by occasional duplicated effort. – Solomon Slow Nov 26 '19 at 15:51

Building a synchronous map, blocking on individual keys

1 Answers1