utilizzo multithread di `iteratori ConcurrentHashMap`

Question

Ho bisogno di scrivere un po 'specifica implementazione di una cache, che ha chiavi univoche ma può contenere valori duplicati, ad esempio:

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

La classe ha bisogno di offrire non bloccante legge/ricerche chiave, ma ha anche i tipici mutatori create/update/delete. Ad esempio, la rimozione di valore 2 dovrebbe portare

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

Legge per questa cache si superano le scritture di gran lunga in modo da scrivere le prestazioni non è un problema - fino a quando le scritture concorrenti non funzionano su uno sopra l'altro. Il numero complessivo di voci è molto probabile che sarà inferiore a 1000, quindi la ripetizione occasionale dei valori è ancora accessibile.

Così ho scritto qualcosa di simile (pseudo codice):

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

Dopo aver scritto quanto sopra, ho capito che ConcurrentHashMap offre anche non bloccante legge che renderebbe tutto il mio sforzo inutile, ma c'è una dichiarazione in la sua Javadoc che alza un sopracciglio:

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

Quindi, se sostituisco l'utilizzo di volatile ImmutableMap con final ConcurrentHashMap e rimuovere tutti i blocchi synchronized, è possibile che in competizione mutatori concorrenti saranno invalido l'un l'altro? Ad esempio, posso immaginare come due chiamate simultanee a remove comporterebbero una condizione di competizione, invalidando completamente i risultati del primo remove.

L'unico miglioramento che posso vedere è che utilizzando final ConcurrentHashMape lasciando synchronized come sono ho potuto almeno evitare di copiare inutile di dati.

Ha senso - o forse sto trascurando qualcosa qui? Qualcuno può suggerire altre alternative per questa soluzione?

Answer 1

Se è stata effettuata questa sostituzione, si avrà comunque una sola discussione utilizzando un determinato Iterator alla volta. L'avviso indica che due thread non devono utilizzare la stessa istanza di Iterator. Non che due thread non possano iterare contemporaneamente.

Il problema si avrebbe è che poiché l'operazione di rimozione non può essere realizzata in un'unica operazione atomica del ConcurrentMap, si potrebbe avere una filettatura concorrente vedere la mappa in uno stato intermedio: un valore è stato rimosso ma non l'altra.

Non sono sicuro che questo sarebbe più veloce, dal momento che tu dici che le prestazioni di scrittura non sono un problema, ma quello che potresti fare per evitare la copia della mappa ad ogni scrittura, è usare un ReadWriteLock che protegge un mutabile ConcurrentMap. Tutte le letture sarebbero comunque concomitanti, ma una scrittura sulla mappa impedirebbe a tutti gli altri thread di accedere alla mappa. E non dovresti creare una nuova copia ogni volta che viene modificata.

Answer 2

È possibile modificare lo ConcurrentHashMap tramite più iteratori/più thread contemporaneamente. È solo che non si suppone che si possa passare una singola istanza di iteratore a più thread e usarla contemporaneamente.

Quindi, se si utilizza ConcurrentHashMap non è necessario lasciare synchronized lì. Come nota JB Nizet, la differenza tra questa e l'attuale implementazione è la visibilità dello stato intermedio.Se non ti interessa, usare ConcurrentHashMap sarebbe la mia scelta preferita in quanto l'implementazione è molto semplice e non dovrai preoccuparti delle prestazioni di lettura o scrittura.