Реализация удаления на ConcurrentMultimap без гонок

Question

Я рассматривал проблему написания параллельной Multimap , и у меня есть реализация, поддерживаемая Google Guava AbstractSetMultimap и вычислительной картой MapMaker, которая создает по требованиюколлекции значений как представление набора над ConcurrentHashMap.С некоторой заботой о коллекциях представлений и различных обертках, я думаю, это довольно близко.

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

По-видимому, существует несколько вариантов.

• оставить там пустые коллекции.Это приведет к утечке некоторых CHM, но я считаю, что это по крайней мере правильно.
• Попытка оптимистично удалить коллекцию, когда она пуста, и компенсировать, если в ней что-то еще появится.Это полно рас и кажется, что по сути невозможно исправить.
• синхронизирует все в сборе значений, что, по крайней мере, позволило бы это удаление, но за счет любого параллелизма после первоначального поиска по ключу.
• для меньшего штрафа (возможно, в зависимости от моделей использования?), Возможно, синхронизации при создании и удалении сбора значений, необходимо проверить, охватывает ли это все.

Вопросы:

• Кто-нибудь знает о лучшей реализации, чем эта?Можем ли мы лучше составить биты из MapMaker, или для этого нужен специальный ConcurrentHashMultimap, написанный с нуля?
• Если это трудно улучшить, является ли эта утечка большой проблемой на практике?Известные коллекции, такие как java.util.HashMap, juc.ConcurrentHashMap и ArrayDeque, не изменяют размер резервного хранилища вниз, а ArrayList не делает этого автоматически.Пока мы очищаем объекты, мне интересно, будет ли это иметь слишком большое значение.

Спасибо

---

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

---

Редактировать 2: С тех пор я написал это.Пожалуйста, смотрите эту область кода Google для реализации.Я был бы очень признателен за любые отзывы от тех, кто пробует, там, а не здесь.

Answer 1

Я задавал тот же вопрос ранее и в итоге реализовал 4 разных реализации.

Вопрос: Высокопроизводительный параллельный MultiMap Java / Scala

Импл (я называю это индексом) http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314

Answer 2

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

Answer 3

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

Эта реализация последовала вашему первому предложению: оставить пустые коллекции в основекарта.Следующее поведение просмотра в реальном времени усложняет ваши другие предложения.

Multimap<String, Integer> multimap = HashMultimap.create();
Set<Integer> set = multimap.get("foo");
multimap.put("foo", 1);
int count = set.size();   // equals 1

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

Answer 4

Если вы действительно не хотите пропускать пустую коллекцию, вы можете попытаться атомарно заменить ее заполнителем для каждого ключа Future.Таким образом, одновременное добавление / удаление или добавление / добавление должно достигать согласованного состояния при повторном расширении.