I'm trying to find one or more concurrent collections to use that I can implement the following behavior (the names are contrived for analogy purposes):
/**
* Acts as a broker for a concurrent hash map that stores its keys in order
* of submission. At shipping time, the concurrent map is "sealed"
* (picture a truck with its cargo door being closed)
* and its contents presented as an immutable map, and is replaced
* by a new concurrent map ready to accept values.
*
* Consumers of this class that submit information to it, are expected to
* know that this contains a concurrent collection, and should use the
* compareAndSet paradigm, e.g. the following:
*
* LoadingDock loadingDock = ...
* boolean done = false;
* while (!done)
* {
* V oldValue = loadingDock.get();
* V newValue = computeNewValue(oldValue, otherInformation);
* if (oldValue == null)
* done = loadingDock.putIfAbsent(newValue) == null;
* else
* done = loadingDock.replace(oldValue, newValue) == oldValue;
* }
*
*
* Keys and values must be non-null. Keys are not ordered.
*/
class LoadingDock<K,V>
{
/**
* analogous to ConcurrentMap's replace, putIfAbsent, and get methods
*/
public boolean replace(K key, V oldValue, V newValue);
public V putIfAbsent(K key, V value);
public V get(K key)
/* see above */
public Map<K,V> ship();
}
I'm having two issues with this.
One is that neither Java nor Guava contain a ConcurrentLinkedHashMap. This makes me wonder why not -- maybe I'm missing the subtleties of such a beast. It looks like I could just make one myself by decorating a ConcurrentHashMap with a class that adds a key to a list if putIfAbsent() is ever called and returns null -- I don't need any of the other methods in ConcurrentHashMap beyond the ones above, so there's no way to add a new key to the map except through a call to putIfAbsent() .
The other, more insidious issue, is that I can't seem to think of how to implement ship() without blocking synchronization -- when ship() is called, the LoadingDock needs to direct all new calls to the new map, and can't return the old map until it is certain all of the concurrent writes are done. (Otherwise I would just use AtomicReference to hold the concurrent map.)
Is there a way to do this w/o having to synchronize?
You could use a ConcurrentSkipListMap and provide your own comparator that sorts the entries based on a timestamp. One imagines there's no ConcurrentLinkedMap because there isn't any particularly good way to implement it that's much better than synchronizing a regular one.
ReplyDeleteFor the ship() method just use a ReadWriteLock that has fair mode turned on. Threads that want to add to the map, acquire the Read lock (weird semantics I know, but it's how it works, think of it as read mode for the actual reference to the map, which is then used normally) so that as many as want can be adding at the same time. In the ship method you acquire the Write lock and it will block anyone else from changing the map while you export and create a new one. Fair-mode makes it so that you "cut off" would be adders as close as possible to when ship() is called and just let the existing ones finish.