The version 1.8 Map interface diagram has the shape below. Sets can be considered sub-cases of corresponding Maps in which the values are always a particular constant which can be ignored, although the Set API uses corresponding but differently named methods. At the bottom is the java.util.concurrent.ConcurrentNavigableMap, which is a multiple-inheritance.
For unordered access as defined in the java.util.Map interface, the java.util.concurrent.ConcurrentHashMap implements java.util.concurrent.ConcurrentMap.[2] The mechanism is a hash access to a hash table with lists of entries, each entry holding a key, a value, the hash, and a next reference. Previous to Java 8, there were multiple locks each serializing access to a 'segment' of the table. In Java 8, native synchronization is used on the heads of the lists themselves, and the lists can mutate into small trees when they threaten to grow too large due to unfortunate hash collisions. Also, Java 8 uses the compare-and-set primitive optimistically to place the initial heads in the table, which is very fast. Performance is O(n), but there are delays occasionally when rehashing is necessary. After the hash table expands, it never shrinks, possibly leading to a memory 'leak' after entries are removed.
ConcurrentSkipListMap
For ordered access as defined by the java.util.NavigableMap interface, java.util.concurrent.ConcurrentSkipListMap was added in Java 1.6,[1] and implements java.util.concurrent.ConcurrentMap and also java.util.concurrent.ConcurrentNavigableMap. It is a Skip list which uses Lock-free techniques to make a tree. Performance is O(log(n)).
One problem solved by the Java 1.5 java.util.concurrent package is that of concurrent modification. The collection classes it provides may be reliably used by multiple Threads.
All Thread-shared non-concurrent Maps and other collections need to use some form of explicit locking such as native synchronization in order to prevent concurrent modification, or else there must be a way to prove from the program logic that concurrent modification cannot occur. Concurrent modification of a Map by multiple Threads will sometimes destroy the internal consistency of the data structures inside the Map, leading to bugs which manifest rarely or unpredictably, and which are difficult to detect and fix. Also, concurrent modification by one Thread with read access by another Thread or Threads will sometimes give unpredictable results to the reader, although the Map's internal consistency will not be destroyed. Using external program logic to prevent concurrent modification increases code complexity and creates an unpredictable risk of errors in existing and future code, although it enables non-concurrent Collections to be used. However, either locks or program logic cannot coordinate external threads which may come in contact with the Collection.
Modification counters
In order to help with the concurrent modification problem, the non-concurrent Map implementations and other Collections use internal modification counters which are consulted before and after a read to watch for changes: the writers increment the modification counters. A concurrent modification is supposed to be detected by this mechanism, throwing a java.util.ConcurrentModificationException,[3] but it is not guaranteed to occur in all cases and should not be relied on. The counter maintenance is also a performance reducer. For performance reasons, the counters are not volatile, so it is not guaranteed that changes to them will be propagated between Threads.
Collections.synchronizedMap()
One solution to the concurrent modification problem is using a particular wrapper class provided by a factory in java.util.Collections: public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) which wraps an existing non-thread-safe Map with methods that synchronize on an internal mutex.[4] There are also wrappers for the other kinds of Collections. This is a partial solution, because it is still possible that the underlying Map can be inadvertently accessed by Threads which keep or obtain unwrapped references. Also, all Collections implement the java.lang.Iterable but the synchronized-wrapped Maps and other wrapped Collections do not provide synchronized iterators, so the synchronization is left to the client code, which is slow and error prone and not possible to expect to be duplicated by other consumers of the synchronized Map. The entire duration of the iteration must be protected as well. Furthermore, a Map which is wrapped twice in different places will have different internal mutex Objects on which the synchronizations operate, allowing overlap. The delegation is a performance reducer, but modern Just-in-Time compilers often inline heavily, limiting the performance reduction. Here is how the wrapping works inside the wrapper - the mutex is just a final Object and m is the final wrapped Map:
The synchronization of the iteration is recommended as follows; however, this synchronizes on the wrapper rather than on the internal mutex, allowing overlap:[5]
Map<String,String>wrappedMap=Collections.synchronizedMap(map);...synchronized(wrappedMap){for(finalStrings:wrappedMap.keySet()){// some possibly long operation executed possibly // many times, delaying all other accesses}}
Native synchronization
Any Map can be used safely in a multi-threaded system by ensuring that all accesses to it are handled by the Java synchronization mechanism:
finalMap<String,String>map=newHashMap<>();...// Thread A// Use the map itself as the lock. Any agreed object can be used instead.synchronized(map){map.put("key","value");}..// Thread Bsynchronized(map){Stringresult=map.get("key");...}...// Thread Csynchronized(map){for(finalEntry<String,String>s:map.entrySet()){/* * Some possibly slow operation, delaying all other supposedly fast operations. * Synchronization on individual iterations is not possible. */...}}
ReentrantReadWriteLock
The code using a java.util.concurrent.ReentrantReadWriteLock is similar to that for native synchronization. However, for safety, the locks should be used in a try/finally block so that early exit such as java.lang.Exception throwing or break/continue will be sure to pass through the unlock. This technique is better than using synchronization[6] because reads can overlap each other, there is a new issue in deciding how to prioritize the writes with respect to the reads. For simplicity a java.util.concurrent.ReentrantLock can be used instead, which makes no read/write distinction. More operations on the locks are possible than with synchronization, such as tryLock() and tryLock(long timeout, TimeUnit unit).
finalReentrantReadWriteLocklock=newReentrantReadWriteLock();finalReadLockreadLock=lock.readLock();finalWriteLockwriteLock=lock.writeLock();..// Thread Atry{writeLock.lock();map.put("key","value");...}finally{writeLock.unlock();}...// Thread Btry{readLock.lock();finalStrings=map.get("key");..}finally{readLock.unlock();}// Thread Ctry{readLock.lock();for(finalEntry<String,String>s:map.entrySet()){/* * Some possibly slow operation, delaying all other supposedly fast operations. * Synchronization on individual iterations is not possible. */...}}finally{readLock.unlock();}
Convoys
Mutual exclusion has a lock convoy problem, in which threads may pile up on a lock, causing the JVM to need to maintain expensive queues of waiters and to 'park' the waiting Threads. It is expensive to park and unpark a Threads, and a slow context switch may occur. Context switches require from microseconds to milliseconds, while the Map's own basic operations normally take nanoseconds. Performance can drop to a small fraction of a single Thread's throughput as contention increases. When there is no or little contention for the lock, there is little performance impact; however, except for the lock's contention test. Modern JVMs will inline most of the lock code, reducing it to only a few instructions, keeping the no-contention case very fast. Reentrant techniques like native synchronization or java.util.concurrent.ReentrantReadWriteLock however have extra performance-reducing baggage in the maintenance of the reentrancy depth, affecting the no-contention case as well. The Convoy problem seems to be easing with modern JVMs, but it can be hidden by slow context switching: in this case, latency will increase, but throughput will continue to be acceptable. With hundreds of Threads , a context switch time of 10ms produces a latency in seconds.
Multiple cores
Mutual exclusion solutions fail to take advantage of all of the computing power of a multiple-core system, because only one Thread is allowed inside the Map code at a time. The implementations of the particular concurrent Maps provided by the Java Collections Framework and others sometimes take advantage of multiple cores using lock free programming techniques. Lock-free techniques use operations like the compareAndSet() intrinsic method available on many of the Java classes such as AtomicReference to do conditional updates of some Map-internal structures atomically. The compareAndSet() primitive is augmented in the JCF classes by native code that can do compareAndSet on special internal parts of some Objects for some algorithms (using 'unsafe' access). The techniques are complex, relying often on the rules of inter-thread communication provided by volatile variables, the happens-before relation, special kinds of lock-free 'retry loops' (which are not like spin locks in that they always produce progress). The compareAndSet() relies on special processor-specific instructions. It is possible for any Java code to use for other purposes the compareAndSet() method on various concurrent classes to achieve Lock-free or even Wait-free concurrency, which provides finite latency. Lock-free techniques are simple in many common cases and with some simple collections like stacks.
The diagram indicates how synchronizing using Collections.synchronizedMap(java.util.Map)wrapping a regular HashMap (purple) may not scale as well as ConcurrentHashMap (red). The others are the ordered ConcurrentNavigableMaps AirConcurrentMap (blue) and ConcurrentSkipListMap (CSLM green). (The flat spots may be rehashes producing tables that are bigger than the Nursery, and ConcurrentHashMap takes more space. Note y axis should say 'puts K'. System is 8-core i7 2.5GHz, with -Xms5000m to prevent GC). GC and JVM process expansion change the curves considerably, and some internal lock-Free techniques generate garbage on contention.
The hash tables are both fast
Predictable latency
Yet another problem with mutual exclusion approaches is that the assumption of complete atomicity made by some single-threaded code creates sporadic unacceptably long inter-Thread delays in a concurrent environment. In particular, Iterators and bulk operations like putAll() and others can take a length of time proportional to the Map size, delaying other Threads that expect predictably low latency for non-bulk operations. For example, a multi-threaded web server cannot allow some responses to be delayed by long-running iterations of other threads executing other requests that are searching for a particular value. Related to this is the fact that Threads that lock the Map do not actually have any requirement ever to relinquish the lock, and an infinite loop in the owner Thread may propagate permanent blocking to other Threads . Slow owner Threads can sometimes be Interrupted. Hash-based Maps also are subject to spontaneous delays during rehashing.
Weak consistency
The java.util.concurrent packages' solution to the concurrent modification problem, the convoy problem, the predictable latency problem, and the multi-core problem includes an architectural choice called weak consistency. This choice means that reads like get(java.lang.Object) will not block even when updates are in progress, and it is allowable even for updates to overlap with themselves and with reads. Weak consistency allows, for example, the contents of a ConcurrentMap to change during an iteration of it by a single Thread.[7] The Iterators are designed to be used by one Thread at a time. So, for example, a Map containing two entries that are inter-dependent may be seen in an inconsistent way by a reader Thread during modification by another Thread. An update that is supposed to change the key of an Entry (k1,v) to an Entry (k2,v) atomically would need to do a remove(k1) and then a put(k2, v), while an iteration might miss the entry or see it in two places. Retrievals return the value for a given key that reflects the latest previous completed update for that key. Thus there is a 'happens-before' relation.
There is no way for ConcurrentMaps to lock the entire table. There is no possibility of ConcurrentModificationException as there is with inadvertent concurrent modification of non-concurrent Maps. The size() method may take a long time, as opposed to the corresponding non-concurrent Maps and other collections which usually include a size field for fast access, because they may need to scan the entire Map in some way. When concurrent modifications are occurring, the results reflect the state of the Map at some time, but not necessarily a single consistent state, hence size(), isEmpty() and containsValue(java.lang.Object) may be best used only for monitoring.
ConcurrentMap 1.5 methods
There are some operations provided by ConcurrentMap that are not in Map - which it extends - to allow atomicity of modifications. The replace(K, v1, v2) will test for the existence of v1 in the Entry identified by K and only if found, then the v1 is replaced by v2 atomically. The new replace(k,v) will do a put(k,v) only if k is already in the Map. Also, putIfAbsent(k,v) will do a put(k,v) only if k is not already in the Map, and remove(k, v) will remove the Entry for v only if v is present. This atomicity can be important for some multi-threaded use cases, but is not related to the weak-consistency constraint.
// if Map does not support null keys or values (apparently independently)if(k==null||v==null)thrownewNullPointerException();if(m.containsKey(k)&&Objects.equals(m.get(k),v)){m.remove(k);returntrue;}elsereturnfalse;}
ConcurrentMap 1.8 methods
Because Map and ConcurrentMap are interfaces, new methods cannot be added to them without breaking implementations. However, Java 1.8 added the capability for default interface implementations and it added to the Map interface default implementations of some new methods getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), computeIfAbsent(K, Function), computeIfPresent(K, BiFunction), compute(K,BiFunction), and merge(K, V, BiFunction). The default implementations in Map do not guarantee atomicity, but in the ConcurrentMap overriding defaults these use Lock free techniques to achieve atomicity, and existing ConcurrentMap implementations will automatically be atomic. The lock-free techniques may be slower than overrides in the concrete classes, so concrete classes may choose to implement them atomically or not and document the concurrency properties.
Lock-free atomicity
It is possible to use lock-free techniques with ConcurrentMaps because they include methods of a sufficiently high consensus number, namely infinity, meaning that any number of Threads may be coordinated. This example could be implemented with the Java 8 merge() but it shows the overall lock-free pattern, which is more general. This example is not related to the internals of the ConcurrentMap but to the client code's use of the ConcurrentMap. For example, if we want to multiply a value in the Map by a constant C atomically:
staticfinallongC=10;voidatomicMultiply(ConcurrentMap<Long,Long>map,Longkey){for(;;){LongoldValue=map.get(key);// Assuming oldValue is not null. This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflictLongnewValue=oldValue*C;if(map.replace(key,oldValue,newValue))break;}}
The putIfAbsent(k, v) is also useful when the entry for the key is allowed to be absent. This example could be implemented with the Java 8 compute() but it shows the overall lock-free pattern, which is more general. The replace(k,v1,v2) does not accept null parameters, so sometimes a combination of them is necessary. In other words, if v1 is null, then putIfAbsent(k, v2) is invoked, otherwise replace(k,v1,v2) is invoked.
voidatomicMultiplyNullable(ConcurrentMap<Long,Long>map,Longkey){for(;;){LongoldValue=map.get(key);// This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflictLongnewValue=oldValue==null?INITIAL_VALUE:oldValue*C;if(replaceNullable(map,key,oldValue,newValue))break;}}...staticbooleanreplaceNullable(ConcurrentMap<Long,Long>map,Longkey,Longv1,Longv2){returnv1==null?map.putIfAbsent(key,v2)==null:map.replace(key,v1,v2);}
History
The Java collections framework was designed and developed primarily by Joshua Bloch, and was introduced in JDK 1.2.[8] The original concurrency classes came from Doug Lea's [9] collection package.
Java Platform, Standard Edition is a computing platform for development and deployment of portable code for desktop and server environments. Java SE was formerly known as Java 2 Platform, Standard Edition (J2SE).
Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without unintended interaction. There are various strategies for making thread-safe data structures.
In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.
Reentrancy is a programming concept where a function or subroutine can be interrupted and then resumed before it finishes executing. This means that the function can be called again before it completes its previous execution. Reentrant code is designed to be safe and predictable when multiple instances of the same function are called simultaneously or in quick succession. A computer program or subroutine is called reentrant if multiple invocations can safely run concurrently on multiple processors, or if on a single-processor system its execution can be interrupted and a new execution of it can be safely started. The interruption could be caused by an internal action such as a jump or call, or by an external action such as an interrupt or signal, unlike recursion, where new invocations can only be caused by internal call.
In software engineering, double-checked locking is a software design pattern used to reduce the overhead of acquiring a lock by testing the locking criterion before acquiring the lock. Locking occurs only if the locking criterion check indicates that locking is required.
In object-oriented (OO) and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created. In some cases, an object is considered immutable even if some internally used attributes change, but the object's state appears unchanging from an external point of view. For example, an object that uses memoization to cache the results of expensive computations could still be considered an immutable object.
In computer science, a lock or mutex is a synchronization primitive that prevents state from being modified or accessed by multiple threads of execution at once. Locks enforce mutual exclusion concurrency control policies, and with a variety of possible methods there exists multiple unique implementations for different applications.
In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures.
OpenMP is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran, on many platforms, instruction-set architectures and operating systems, including Solaris, AIX, FreeBSD, HP-UX, Linux, macOS, and Windows. It consists of a set of compiler directives, library routines, and environment variables that influence run-time behavior.
In computer programming, foreach loop is a control flow statement for traversing items in a collection. foreach is usually used in place of a standard for loop statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages, an iterator, even if implicit, is often used as the means of traversal.
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of that memory location to a new given value. This is done as a single atomic operation. The atomicity guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write would fail. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response, or by returning the value read from the memory location.
In computer programming, volatile means that a value is prone to change over time, outside the control of some code. Volatility has implications within function calling conventions, and also impacts how variables are stored, accessed and cached.
The object pool pattern is a software creational design pattern that uses a set of initialized objects kept ready to use – a "pool" – rather than allocating and destroying them on demand. A client of the pool will request an object from the pool and perform operations on the returned object. When the client has finished, it returns the object to the pool rather than destroying it; this can be done manually or automatically.
In computer science, a readers–writer is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, whereas write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers and readers will be blocked until the writer is finished writing. A common use might be to control access to a data structure in memory that cannot be updated atomically and is invalid until the update is complete.
The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures.
In computer science, synchronization is the task of coordinating multiple of processes to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action.
The Java programming language and the Java virtual machine (JVM) is designed to support concurrent programming. All execution takes place in the context of threads. Objects and resources can be accessed by many separate threads. Each thread has its own path of execution, but can potentially access any object in the program. The programmer must ensure read and write access to objects is properly coordinated between threads. Thread synchronization ensures that objects are modified by only one thread at a time and prevents threads from accessing partially updated objects during modification by another thread. The Java language has built-in constructs to support this coordination.
InfinityDB is an all-Java embedded database engine and client/server DBMS with an extended java.util.concurrent.ConcurrentNavigableMap interface that is deployed in handheld devices, on servers, on workstations, and in distributed settings. The design is based on a proprietary lockless, concurrent, B-tree architecture that enables client programmers to reach high levels of performance without risk of failures.
A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots.
A concurrent hash table or concurrent hash map is an implementation of hash tables allowing concurrent access by multiple threads using a hash function.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
