Parallel Multi-Logging and Deletion

Question

This is a complex implementation of a multi-file list. A lower level implementation will be better, but harder.

Is ignoring O (n) deletion in a sublist a proper way to compose ConcurrentMap and CopyOnWriteArrayList into a functional ConcurrentMultimap? Are there irregular data feeds?

private final ConcurrentMap<K, Collection<V>> map = ...; // inconsequential public boolean put(K key, V value) { Collection<V> list = map.get(key); if(list != null) { list.add(value); return true; } // put if absent double check to avoid extra list creation list = new CopyOnWriteArrayList<V>(); list.add(value); Collection<V> old = map.putIfAbsent(key,value); if(old != null) old.add(value); return true; } public boolean remove(Object key, Object value) { Collection<V> list = map.get(key); if(list == null) return false; // O(n) remove is the least of my worries if( ! list.remove(value)) return false; if( ! list.isEmpty()) return true; // double-check remove if( ! map.remove(key,list)) return true; // already removed! (yikes) if(list.isEmpty()) return true; // another entry was added! Collection<V> old = map.putIfAbsent(key,list); if(old == null) return true; // new list added! old.addAll(list); return true; } 

Answer 1

I think you have a race. The problem I see is that the thread that is in "put" can NOT be sure that the inserted list has not been deleted and / or replaced with another list.

Note:

Thread 1 calls put () and retrieves (or creates) the list associated with the key. Meanwhile, Thread 2 removes this list from the card. Data loss.

I think you need to add a repeat loop to make sure that the right list is on the map after adding to it.