1 Symptoms of concurrent problems
1.1 Multithreading PUT May Cause Get Loop
Our Java code used to use a HashMap thing for some reason, but back then the program was single-threaded and everything was fine. Later, we had performance problems with our program, so we needed to make it multithreaded, and when we went online, we found that the program was often using 100% of the CPU. When we looked at the stack, we found that the program was stuck on hashmap.get (), and when we restarted the program, the problem disappeared. But they’ll come back in a little while. Also, this problem may be difficult to reproduce in a test environment.
Taking a quick look at our own code, we know that a HashMap is being manipulated by multiple threads. The Java documentation says that HashMap is not thread-safe and ConcurrentHashMap should be used. But here’s why. The simple code is as follows:
package com.king.hashmap;
import java.util.HashMap;
public class TestLock {
private HashMap map = new HashMap();
public TestLock(a) {
Thread t1 = new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t1 over"); }}; Thread t2 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t2 over"); }}; Thread t3 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t3 over"); }}; Thread t4 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t4 over"); }}; Thread t5 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t5 over"); }}; Thread t6 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}
System.out.println("t6 over"); }}; Thread t7 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}
System.out.println("t7 over"); }}; Thread t8 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}
System.out.println("t8 over"); }}; Thread t9 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}
System.out.println("t9 over"); }}; Thread t10 =new Thread() {
public void run(a) {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}
System.out.println("t10 over"); }}; t1.start(); t2.start(); t3.start(); t4.start(); t5.start(); t6.start(); t7.start(); t8.start(); t9.start(); t10.start(); }public static void main(String[] args) {
newTestLock(); }}Copy the codeThis is to start 10 threads and continuously put/get content into a non-thread-safe HashMap. The content of the put is very simple, with keys and values incrementing from 0 (the put content is not very good, so it later interferes with my analysis). Running the program over and over again will result in threads T1 and T2 being hung. In most cases, one thread will be hung and the other thread will end successfully. Occasionally, all 10 threads will be hung.
The root cause of this endless loop is an operation on an unprotected shared variable, a “HashMap” data structure. When “synchronized” was added to all the methods, everything returned to normal. Is this a JDK bug? No, this phenomenon has been reported for a long time. The Sun engineers did not consider this a bug and suggested using a “ConcurrentHashMap” for such scenarios.
High CPU utilization is usually caused by an infinite loop, which causes some threads to run continuously and occupy CPU time. The reason for the problem is that the HashMap is not thread-safe, and multiple threads put an Entry key List in an infinite loop, which is where the problem occurs.
When another thread gets the Entry List key in an endless loop, the get is executed. The end result is more and more thread loops, which eventually lead to server slacks. We generally think that when a HashMap repeatedly inserts a value, it overwrites the previous value, and that’s true. However, for multi-threaded access, due to its internal implementation mechanism (in a multi-threaded environment without synchronization, the put operation on the same HashMap may lead to two or more threads doing the rehash action at the same time, which may lead to the emergence of the circular key table. Once the thread appears, it will not be terminated and continue to occupy CPU. Resulting in high CPU usage), security issues may arise.
Use the JStack tool to dump the stack information of the faulty server. For an infinite loop, first look for the RUNNABLE thread and find the following code:
java.lang.Thread.State:RUNNABLE at java.util.HashMap.get(HashMap.java:303) at Com. Sohu. Twap. Service. Logic. TransformTweeter. DoTransformTweetT5 (183) TransformTweeter. Java: a total of 23 times. java.lang.Thread.State:RUNNABLE at java.util.HashMap.put(HashMap.java:374) at Com. Sohu. Twap. Service. Logic. TransformTweeter. TransformT5 (TransformTweeter. Java: 816) has appeared three times.
Note: Improper use of HashMap results in an infinite loop rather than a deadlock.
1.2 Multithreading put may cause element loss
The main problem is the addEntry method’s new Entry<K,V>(hash, key, value, e). If both threads get e at the same time, then their next element will be E, and then when assigning to the table element, one will succeed and the other will lose.
1.3 Null is displayed after a non-null element is put
The code in the transfer method is as follows:
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if(e ! =null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while(e ! =null); }}}Copy the codeSRC = null; SRC = null; SRC = null; SRC = null; SRC = null;
if(e ! =null) {
src[j] = null;
Copy the codeIf a get method accesses the key, it still gets the old array, and of course it doesn’t get the value.
Summary: A HashMap that is not synchronized can cause many subtle problems in concurrent programs that are difficult to see on the surface. So the counterintuitive phenomenon of using HashMap is probably caused by concurrency.
2 HashMap data structure
A HashMap usually uses an array of Pointers (let's say table[]) to scatter all the keys. When a key is added, the Hash algorithm will calculate the index I of the array using the key, and then insert the <key, value> into the table[I]. If two different keys count in the same I, this is called a collision, and this will form a linked list on the table[I].
We know that if table[] is small in size, say 2 keys, and 10 keys are to be put in, then collisions are so frequent that an O(1) lookup algorithm becomes O(n) traversal, which is the drawback of Hash tables.
Therefore, the size and capacity of the Hash table are very important. In general, when the Hash table container has data to insert, the thredhold is checked to see if it exceeds the thredhold. If it does, the size of the Hash table is increased, but the entire Hash element needs to be recalculated. It’s called rehash, and it’s a pretty big cost.
2.1 Rehash source code for HashMap
Let’s take a look at the source code for Java’s HashMap. Put a Key and Value pair into the Hash table:
public V put(K key, V value)
{.../ / calculate the Hash value
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// If the key has already been inserted, replace the old value (link operation)
for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// The key does not exist and a node needs to be added
addEntry(hash, key, value, i);
return null;
}
Copy the codeCheck whether the capacity exceeds the standard:
void addEntry(int hash, K key, V value, int bucketIndex)
{
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// Check whether the current size exceeds the threshold we set. If so, resize is required
if (size++ >= threshold)
resize(2 * table.length);
}
Copy the codeCreate a larger hash table and migrate the data from the old hash table to the new hash table.
void resize(int newCapacity)
{
Entry[] oldTable = table;
intoldCapacity = oldTable.length; .// Create a new Hash Table
Entry[] newTable = new Entry[newCapacity];
// Migrate data from Old Hash Table to New Hash Table
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
Copy the codeMigrate source code, note the highlights:
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
// The following code means:
// Take an element from OldTable and place it in NewTable
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if(e ! =null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while(e ! =null); }}}Copy the codeOkay, so this code is kind of normal. And there was no problem.
2.2 Normal ReHash process
I drew a picture for a demonstration.
- Suppose our hash algorithm simply mod the table size (that is, the length of the array) with a key.
- The top hash table is the old hash table, where size=2, so key = 3, 7, 5, after mod 2 all conflict in table[1].
- The next three steps are to resize the Hash table to 4 and then rehash all
.
2.3 Concurrent Rehash procedure
(1) Suppose we have two threads. I’ve highlighted it in red and light blue. Let’s go back to this detail in our Transfer code:
do {
Entry<K,V> next = e.next; // <-- suppose the thread is scheduled to suspend as soon as it reaches this point
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while(e ! =null);
Copy the codeAnd our thread two execution is done. So we have something like this.
Note: Since e of Thread1 points to key(3) and next points to key(7), it points to the reassembled list of thread 2 after thread 2 rehash. We can see that the order of the linked list is reversed.
(2) Thread one is scheduled back to execute.
- NewTalbe [I] = e.
- Then e = next, resulting in e pointing to key(7).
- Next = e.next causes next to point to key(3).
(3) Everything is fine. The thread resumed work. Remove key(7) and place it first in newTable[I], then move e and next down.
(4) Ring links appear. E.ext = newTable[I] causes key(3). Next points to key(7). Note that key(7).next already points to key(3), and the circular list appears.
So, when our thread calls hashtable.get (11), the tragedy occurs — Infinite Loop.
3 Three solutions
3.1 Hashtable Replacing a HashMap
Hashtable is synchronous, but both iterators returned by iterators and listIterator methods of collections returned by “collection view methods” of all Hashtables fail quickly: If a Hashtable is modified structurally after the Iterator is created, it can be modified in any way, at any time, except through the Iterator’s own remove or add methods. The Iterator will throw ConcurrentModificationException. Thus, in the face of concurrent modifications, Iterator will quickly fail completely, without the risk of arbitrary uncertain behavior at some unspecified time in the future. Enumeration returned by the key and value methods of a Hashtable does not fail quickly.
Note that the fast failure behavior of iterators cannot be guaranteed because, in general, it is impossible to make any hard guarantees about the occurrence of unsynchronized concurrent changes. Fail fast iterator will do our best to throw ConcurrentModificationException. Therefore, it would be a mistake to write a program that relies on this exception to improve the correctness of such iterators: the fast failure behavior of iterators should only be used to detect program errors.
3.2 Collections. SynchronizedMap HashMap packing up
Returns a synchronous (thread-safe) mapping supported by the specified mapping. To ensure sequential access, all access to the underlying mapping must be done through the returned mapping. Forces the user to manually synchronize on the returned map when iterating over the returned map or any of its Collection views:
Map m = Collections.synchronizedMap(newHashMap()); . Set s = m.keySet();// Needn't be in synchronized block.synchronized(m) { // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
Copy the codeFailure to follow this advice will result in undetermined behavior. If you specify that the mapping is serializable, the returned mapping is also serializable.
3.3 ConcurrentHashMap Replacing the HashMap
Hash tables that support full concurrency for retrieval and expected adjustable concurrency for updates. This class follows the same functional specification as Hashtable and includes a method version corresponding to each method of Hashtable. However, while all operations are thread-safe, retrieval operations do not have to be locked, and there is no support for locking the entire table in a way that prevents all access. This class can programmatically fully interoperate with Hashtable, depending on its thread-safety and not its synchronization details.
Retrieval operations (including GET) are not normally blocked and, therefore, may overlap with update operations (including PUT and remove). Retrieval affects the results of recently completed update operations. For some aggregation operations, such as putAll and Clear, concurrent retrieval may only affect the insertion and removal of certain items. Similarly, Iterators and Enumerations return elements that affect the state of the hash table at a point in time at the creation of Iterators/Enumerations and thereafter. They don’t throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.