Параллелизм Java с картой списков

Question

У меня есть класс Java, к которому одновременно обращается множество потоков, и хочу убедиться, что он безопасен для потоков. Класс имеет одно закрытое поле, которое представляет собой карту строк в списки строк. Я реализовал Map как ConcurrentHashMap, чтобы гарантировать, что операции получения и размещения являются потокобезопасными:

public class ListStore {

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

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

Итак, учитывая, что получение и установка на карту являются потокобезопасными, я беспокоюсь о списках, которые хранятся на карте. Например, рассмотрим следующий метод, который проверяет, существует ли данная запись в указанном списке в хранилище (я упустил проверку ошибок для краткости):

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;
}

Казалось бы, мне нужно синхронизировать все содержимое этого метода, потому что, если другой метод изменил содержимое списка в innerListStore.get (listName), пока этот метод итерирует по нему, возникнет исключение ConcurrentModificationException.

Это правильно, и если да, синхронизировать ли я на innerListStore или будет работать синхронизация на локальной переменной listToSearch?

ОБНОВЛЕНИЕ: Спасибо за ответы. Похоже, я могу синхронизировать в самом списке. Для получения дополнительной информации, вот метод add (), который может быть запущен в то же время, когда метод listEntryExists () выполняется в другом потоке:

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);
}

Если это единственный метод, который изменяет базовые списки, хранящиеся на карте, и никакие публичные методы не возвращают ссылки на карту или записи на карте, могу ли я синхронизировать итерацию в самих списках, и достаточно ли этой реализации add ()?

Answer 1

Вы можете синхронизировать в listToSearch («synchronized (listToSearch) {...}»).Убедитесь, что при создании списков нет условий гонки (для их создания используйте innerListStore.putIfAbsent).

Answer 2

Казалось бы, мне нужно синхронизировать все содержимое этого метода, потому что, если другой метод изменил содержимое списка в innerListStore.get (listName), пока этот метод выполняет итерации по нему, возникнет исключение ConcurrentModificationException.

Имеют ли другие потоки доступ к самому списку или только при операциях, предоставляемых ListStore?

Приведут ли операции, вызванные другими потоками, к изменению содержимого списка, сохраненного на карте? Или записи будут только добавляться / удаляться с карты?

Вам нужно будет синхронизировать доступ к списку, хранящемуся на карте, только если разные потоки могут привести к изменениям в одном и том же экземпляре списка. Если потокам разрешено только добавлять / удалять экземпляры List с карты (т. Е. Изменять структуру карты), синхронизация не требуется.

Answer 3

Вы можете синхронизироваться только с listToSearch, нет причин блокировать всю карту каждый раз, когда кто-либо использует только одну запись.

Только помните, что вам нужно синхронизировать список везде, где он изменен! Синхронизация итератора не блокирует автоматически других людей от выполнения add () или чего-то еще, если вы передали им ссылки на несинхронизированный список.

Было бы безопаснее просто сохранить синхронизированные списки на карте, а затем заблокировать их при выполнении итерации, а также задокументировать, когда вы возвращаете ссылку на список, которую пользователь должен синхронизировать с ней, если они повторяются. Синхронизация в современных виртуальных машинах JVM обходится довольно дешево, когда не происходит реальных конфликтов. Конечно, если вы никогда не позволите ссылке на один из списков покинуть ваш класс, вы можете обработать ее внутренне с помощью более тонкой расчески.

В качестве альтернативы вы можете использовать потокобезопасный список, такой как CopyOnWriteArrayList, который использует итераторы снимков. Какая согласованность во времени вам нужна, это дизайнерское решение, которое мы не можем принять за вас. javadoc также включает полезное обсуждение характеристик производительности.

Answer 4

Поскольку вы не предоставили ни одного клиента для отображения списков, кроме метода boolean listEntryExists(String listName, String listEntry), мне интересно, почему вы вообще храните списки?Эта структура кажется более естественной для Map<String, Set<String>>, и listEntryExists должен использовать метод contains (также доступен для List, но O (n) для размера списка):

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

Теперь вызов содержимого может инкапсулировать любой внутренний протокол параллелизма, который вам нужен.

Для add вы можете использовать синхронизированную оболочку (простую, но, возможно, медленную) или, если запись нечастапо сравнению с чтением используйте ConcurrentMap.replace для реализации своей собственной стратегии копирования при записи.Например, использование 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;
  }
}

Теперь это полностью поточно-безопасная безблокировочная структура, где параллельные читатели и писатели не будут блокировать друг друга (по модулюсвободная блокировка базовой реализации ConcurrentMap).Эта реализация имеет O (n) в записи, где исходная реализация была O9n) в чтении.Опять же, если вы читаете - в основном, а не пишете - в основном это может быть большой победой.

Answer 5

Вы можете использовать другую абстракцию из Гуава

Обратите внимание, что это будет синхронизироваться по всей карте, поэтому это может быть не очень полезно для вас.

Answer 6

, если списки, хранящиеся на карте, относятся к типу, который не генерирует CME (например, CopyOnWriteArrayList ), вы можете выполнять итерацию по желанию

это может привести к некоторым расам, хотя, если вы не будете осторожны

Answer 7

Если карта уже поточно-ориентированная, то я думаю, что синхронизация listToSearch должна работать. Я не 100%, но я думаю, что это должно работать

synchronized(listToSearch)
{

}