Java concurrency with a Map of Lists

Question

I have a java class that is accessed by a lot of threads at once and want to make sure it is thread safe. The class has one private field, which is a Map of Strings to Lists of Strings. I've implemented the Map as a ConcurrentHashMap to ensure gets and puts are thread safe:

public class ListStore {

  private Map<String, List<String>> innerListStore;

  public ListStore() {
    innerListStore = new ConcurrentHashMap<String, List<String>>();
  }
  ...
}

So given that gets and puts to the Map are thread safe, my concern is with the lists that are stored in the Map. For instance, consider the following method that checks if a given entry exists in a given list in the store (I've omitted error checking for brevity):

public boolean listEntryExists(String listName, String listEntry) {

  List<String> listToSearch = innerListStore.get(listName);

  for (String entryName : listToSearch) {
    if(entryName.equals(listEntry)) {
      return true;
    }
  }

  return false;
}

It would seem that I need to synchronize the entire contents of this method because if another method changed the contents of the list at innerListStore.get(listName) while this method is iterating over it, a ConcurrentModificationException would be thrown.

Is that correct and if so, do I synchronize on innerListStore or would synchronizing on the local listToSearch variable work?

UPDATE: Thanks for the responses. It sounds like I can synchronize on the list itself. For more information, here is the add() method, which can be running at the same time the listEntryExists() method is running in another thread:

public void add(String listName, String entryName) {

  List<String> addTo = innerListStore.get(listName);
  if (addTo == null) {
    addTo = Collections.synchronizedList(new ArrayList<String>());
    List<String> added = innerListStore.putIfAbsent(listName, addTo);
    if (added != null) {
      addTo = added;
    }
  }

  addTo.add(entryName);
}

If this is the only method that modifies the underlying lists stored in the map and no public methods return references to the map or entries in the map, can I synchronize iteration on the lists themselves and is this implementation of add() sufficient?

your add() implementation is broken. you need to handle the results of putIfAbsent() correctly (otherwise you may add to the wrong list). — jtahlborn
– jtahlborn, Commented May 31, 2011 at 18:55
@jtahlborn Are you saying I need to call add() on the the List that putIfAbsent() returns? If so, I disagree. putIfAbsent() returns whatever was previously associated with that key, which would be the wrong list. Right? — Cameron
– Cameron, Commented May 31, 2011 at 19:00
please re-read the documentation on the putIfAbsent() method (note the name of the method for that matter). — jtahlborn
– jtahlborn, Commented May 31, 2011 at 19:12
I think I see what you mean now and have edited the add(). Is that the correct way to handle it? — Cameron
– Cameron, Commented May 31, 2011 at 19:41

Spike Gronim · Accepted Answer · 2011-05-31 17:49:39Z

2

You can synchronize on listToSearch ("synchronized(listToSearch) {...}"). Make sure that there is no race condition creating the lists (use innerListStore.putIfAbsent to create them).

answered May 31, 2011 at 17:49

Spike Gronim

6,20225 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Affe · Accepted Answer · 2011-05-31 17:58:18Z

1

You could synchronize on just listToSearch, there's no reason to lock the entire map any time anyone is using just one entry.

Just remember though, that you need to synchronize on the list everywhere it is modified! Synchronizing the iterator doesn't automagically block other people from doing an add() or whatnot if you passed out to them references to the unsynchronized list.

It would be safest to just store synchronized lists in the Map and then lock on them when you iterate, and also document when you return a reference to the list that the user must sycnhronize on it if they iterate. Synchronization is pretty cheap in modern JVMs when no actual contention is happening. Of course if you never let a reference to one of the lists escape your class, you can handle it internally with a finer comb.

Alternately you can use a threadsafe list such as CopyOnWriteArrayList that uses snapshot iterators. What kind of point in time consistency you need is a design decision we can't make for you. The javadoc also includes a helpful discussion of performance characteristics.

edited May 31, 2011 at 17:58

answered May 31, 2011 at 17:52

Affe

48.1k12 gold badges85 silver badges86 bronze badges

3 Comments

CPerkins Over a year ago

+1 for the reminder that synchronizing the iterator in listEntryExists doesn't block modifications in other methods.

Jed Wesley-Smith Over a year ago

Sorry Affe, that was me, on a general war against synchronization. Having re-read the answer today it is perfectly sensible and doesn't deserve a down-vote. You are right that uncontended synchronization is cheap, but contended synchronization is not. The problem the locked solution has is that as the lists get larger the critical section gets larger and there is more likelihood of contention. You though step around that with the suggestion of the copy-on-write structure. Apologies, but SE won't let me remove the down-vote now.

Affe Over a year ago

No harm, I just like to ask since if I did say something that's wrong I want to learn about it :)

matt b · Accepted Answer · 2011-05-31 18:18:29Z

It would seem that I need to synchronize the entire contents of this method because if another method changed the contents of the list at innerListStore.get(listName) while this method is iterating over it, a ConcurrentModificationException would be thrown.

Are other threads accessing the List itself, or only though operations exposed by ListStore?

Will operations invoked by other threads result in the contents of the a List stored in the Map being changed? Or will entries only be added/removed from the Map?

You would only need to synchronize access to the List stored within the Map if different threads can result in changes to the same List instances. If the threads are only allowed to add/remove List instances from the Map (i.e. change the structure of the Map), then synchronization is not necessary.

ratchet freak · Accepted Answer · 2011-05-31 17:52:19Z

0

if the lists stored in the map are of the type that don't throw CME (CopyOnWriteArrayList for example) you can iterate at will

this can introduce some races though if you're not careful

answered May 31, 2011 at 17:52

ratchet freak

48.4k5 gold badges76 silver badges114 bronze badges

Comments

RMT · Accepted Answer · 2011-05-31 17:52:29Z

0

If the Map is already thread safe, then I think syncronizing the listToSearch should work. Im not 100% but I think it should work

synchronized(listToSearch)
{

}

edited May 31, 2011 at 17:52

answered May 31, 2011 at 17:46

RMT

7,0904 gold badges28 silver badges39 bronze badges

Comments

whiskeysierra · Accepted Answer · 2011-05-31 18:41:13Z

0

You could use another abstraction from Guava

Note that this will synchronize on the whole map, so it might be not that useful for you.

answered May 31, 2011 at 18:41

whiskeysierra

5,1201 gold badge32 silver badges41 bronze badges

Comments

Jed Wesley-Smith · Accepted Answer · 2011-05-31 23:10:57Z

As you haven't provided any client for the map of lists apart from the boolean listEntryExists(String listName, String listEntry) method, I wonder why you are storing lists at all? This structure seems to be more naturally a Map<String, Set<String>> and the listEntryExists should use the contains method (available on List as well, but O(n) to the size of the list):

public boolean listEntryExists(String name, String entry) {
  SetString> set = map.get(name);
  return (set == null) ? false : set.contains(entry;
}

Now, the contains call can encapsulate whatever internal concurrency protocol you want it to.

For the add you can either use a synchronized wrapper (simple, but maybe slow) or if writes are infrequent compared to reads, utilise ConcurrentMap.replace to implement your own copy-on-write strategy. For instance, using Guava ImmutableSet:

public boolean add(String name, String entry) {
  while(true) {
    SetString> set = map.get(name);
    if (set == null) {
      if (map.putIfAbsent(name, ImmutableSet.of(entry))
        return true
      continue;
    }
    if (set.contains(entry)
      return false; // no need to change, already exists
    Set<String> newSet = ImmutableSet.copyOf(Iterables.concat(set, ImmutableSet.of(entry))        
    if (map.replace(name, set, newSet)
      return true;
  }
}

This is now an entirely thread-safe lock-free structure, where concurrent readers and writers will not block each other (modulo the lock-freeness of the underlying ConcurrentMap implementation). This implementation does have an O(n) in its write, where your original implementation was O9n) in the read. Again if you are read-mostly rather than write-mostly this could be a big win.

wromma · Accepted Answer · 2023-04-27 06:31:24Z

0

It can be done with less coding. Here is an example, it is part of the concurrency stress test Jcstress enter link description here

void add(String key, String val) {
     List<String> list = map.computeIfAbsent(key,
                    k -> Collections.synchronizedList(new ArrayList<>()));
     list.add(val);
}

answered Apr 27, 2023 at 6:31

wromma

491 silver badge5 bronze badges

Collectives™ on Stack Overflow

Java concurrency with a Map of Lists

8 Answers 8

Comments

3 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

Comments

3 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related