Многопоточное использование итераторов `ConcurrentHashMap`

Question

Мне нужно написать несколько конкретную реализацию кеша, который имеет уникальные ключи, но может содержать повторяющиеся значения, например:

 "/path/to/one" -> 1
 "/path/to/two" -> 2
 "/path/to/vienas" -> 1
 "/path/to/du" -> 2

Класс должен предлагать неблокирующие операции чтения / поиска ключей, но также имеетТипичные создания / обновления / удаления мутаторов.Например, удаление значения 2 должно привести к

"/path/to/one" -> 1
"/path/to/vienas" -> 1

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

Итак, я написал что-то вроде этого (псевдокод):

//
// tl;dr all writes are synchronized on a single lock and each
// resets the reference to the volatile immutable map after finishing
//
class CopyOnWriteCache {
   private volatile Map<K, V> readOnlyMap = ImmutableMap.of();

   private final Object writeLock = new Object();

   public void add(CacheEntry entry) {
      synchronized (writeLock) {
         readOnlyMap = new ImmutableMap.Builder<K, V>()
            .addAll(readOnlyMap)
            .add(entry.key, entry.value)
            .build();
      }
   }

   public void remove(CacheEntry entry) {
      synchronized (writeLock) {
         Map<K, V> filtered = Maps.filterValues(readOnlyMap, somePredicate(entry));
         readOnlyMap = ImmutableMap.copyOf(filtered);
      }
   }

   public void update(CacheEntry entry) {
      synchronized (writeLock) {
         Map<K, V> filtered = Maps.filterValues(readOnlyMap, somePredicate(entry));
         readOnlyMap = new ImmutableMap.Builder<K, V>()
             .addAll(filtered)
             .add(entry.key, entry.value)
             .build();
      }
   }

   public SomeValue lookup(K key) {
      return readOnlyMap.get(key);
   }
}

Посленаписав вышесказанное, я понял, что ConcurrentHashMap также предлагает неблокирующее чтение, которое сделало бы все мои усилия бессмысленными, но в его Javadoc есть утверждение, вызывающее удивление:

iterators are designed to be used by only one thread at a time

Так что, если я заменюиспользование volatile ImmutableMap с final ConcurrentHashMap и удаление всех блоков synchronized, возможно ли, что конкурирующие параллельные мутаторы лишат законной силы друг друга?Например, я могу себе представить, как два одновременных вызова на remove приведут к состоянию гонки, полностью аннулируя результаты первого remove.

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

Имеет ли это смысл - или, может быть, я что-то здесь упускаю?Кто-нибудь может предложить другие альтернативы для этого решения?

Answer 1

Если вы сделали эту замену, у вас все равно был бы только один поток, использующий данный итератор одновременно. Предупреждение означает, что два потока не должны использовать один и тот же экземпляр Iterator. Не то, чтобы два потока не могли выполнять итерацию одновременно.

Проблема, с которой вы столкнулись бы, заключается в том, что поскольку операция удаления не может быть выполнена за одну атомарную операцию ConcurrentMap, вы можете иметь параллельный поток, который видит карту в промежуточном состоянии: одно значение было удалено, но не другой.

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

Answer 2

Можно мутировать ConcurrentHashMap через несколько итераторов / нескольких потоков одновременно.Просто вы не должны передавать один экземпляр итератора нескольким потокам и использовать его одновременно.

Итак, если вы используете ConcurrentHashMap, вам не нужно оставлять synchronized там.Как отмечает JB Nizet, разница между этим и вашей текущей реализацией заключается в видимости промежуточного состояния.Если вас это не волнует, использование ConcurrentHashMap будет моим предпочтительным выбором, поскольку реализация наиболее проста, и вам не придется беспокоиться о производительности чтения или записи.