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

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

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

Кажется, существует несколько вариантов.

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

Вопросы:

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

Спасибо

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

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


java concurrency guava multimap concurrenthashmap
person Joe Kearney    schedule 28.09.2010    source источник

Ответы (4)


arrow_upward
0
arrow_downward

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

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

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

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

person Jared Levy    schedule 01.10.2010
comment
Я решил, что такое поведение при просмотре в реальном времени multimap.get("foo") возвращает ForwardingSet делегирование реальному. Таким образом, каждая операция в этом наборе ищет нижележащий объект, который может меняться между любыми двумя вызовами. Я думаю, это косвенное обращение решает большинство проблем, но вызывает создание коллекции ложных значений при каждой операции с отсутствующим ключом. Спасибо за комментарии. - person Joe Kearney; 01.10.2010

arrow_upward
1
arrow_downward

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

Вопрос: High-performance Concurrent MultiMap Java / Scala

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

person Viktor Klang    schedule 03.10.2010

arrow_upward
0
arrow_downward

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

person Holger Hoffstätte    schedule 28.09.2010
comment
Это может сработать, но приведет к утечке значения заполнителя и закреплению ключа в памяти. Конечно, заполнитель, скорее всего, будет меньше, чем пустая коллекция, так что это улучшение. - person Joe Kearney; 30.09.2010

arrow_upward
0
arrow_downward

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

person Jed Wesley-Smith    schedule 29.09.2010
comment
Неизменяемые коллекции значений, безусловно, работают здесь с точки зрения безопасности, но да, любое копирование убьет это в полезном случае, когда есть много споров. - person Joe Kearney; 30.09.2010
comment
По моему опыту, должно быть много разногласий, прежде чем это станет проблемой, и для средних уровней разногласий это на самом деле явная победа - особенно там, где преобладают чтения. - person Jed Wesley-Smith; 08.10.2010