Java 7: HashMap против ConcurrentHashMap

Как вы, возможно, видели из моих прошлых статей, связанных с производительностью, и примеров из практики HashMap , проблемы безопасности потоков Java могут довольно легко разрушить ваше приложение Java EE и контейнер Java EE. Одной из наиболее распространенных проблем, с которыми я столкнулся при устранении проблем с производительностью Java EE, является бесконечный цикл, запускаемый из небезопасных операций HashMap get () и put (). Эта проблема известна уже несколько лет, но недавние производственные проблемы заставили меня вернуться к этой проблеме еще раз.

В этой статье мы вернемся к этой классической проблеме безопасности потоков и продемонстрируем, используя простую Java-программу, риск, связанный с неправильным использованием простой старой структуры данных java.util.HashMap, связанной с контекстом параллельных потоков.

Это доказательство концепции попытается достичь следующих 3 целей:

Пересмотрите и сравните уровень производительности Java-программ между реализациями, не ориентированными на многопоточные и поточнобезопасные, (HashMap, Hashtable, синхронизированный HashMap, ConcurrentHashMap).
Воспроизведите и продемонстрируйте проблему бесконечного цикла HashMap, используя простую Java-программу, которую каждый может скомпилировать, запустить и понять.
Просмотрите использование вышеупомянутых структур данных Map в реальной и современной реализации контейнера Java EE, такой как JBoss AS7

Для получения более подробной информации о стратегии реализации ConcurrentHashMap я настоятельно рекомендую отличную статью Брайана Гетца на эту тему.

Инструменты и спецификации сервера

В качестве отправной точки, найдите ниже различные инструменты и программное обеспечение, используемое для упражнения:

Sun / Oracle JDK & JRE 1.7 64-разрядная версия
Eclipse Java EE IDE
Проводник Windows (процессор на корреляцию потоков Java)
JVM Thread Dump (анализ застрявших потоков и соотношения ЦП на поток)

Следующий локальный компьютер использовался для процесса репликации проблемы и измерения производительности:

Процессор Intel (R) Core (TM) i5-2520M @ 2,50 ГГц (2 ядра процессора, 4 логических ядра)
8 ГБ ОЗУ
Windows 7 64-битная

* Результаты и производительность Java-программы могут отличаться в зависимости от вашей рабочей станции или спецификаций сервера.

Java программа

Чтобы помочь нам в достижении вышеуказанных целей, была создана простая Java-программа, как показано ниже:

Основной программой на Java является HashMapInfiniteLoopSimulator.java
Класс Worker Thread WorkerThread.java также был создан

Программа выполняет следующее:

Инициализируйте различные статические структуры данных Map с начальным размером 2
Назначить выбранную карту рабочим потокам (вы можете выбрать одну из 4 реализаций карты)
Создайте определенное количество рабочих потоков (согласно конфигурации заголовка). 3 рабочих потока были созданы для этого доказательства концепции NB_THREADS = 3;
Каждый из этих рабочих потоков выполняет одну и ту же задачу: поиск и вставка нового элемента в назначенную структуру данных Map с использованием случайного элемента Integer в диапазоне от 1 до 1 000 000.
Каждый рабочий поток выполняет эту задачу в общей сложности 500K итераций
Программа в целом выполняет 50 итераций, чтобы обеспечить достаточное время разгона для JSM HotSpot.
Контекст параллельных потоков достигается с помощью JDK ExecutorService

Как видите, программная задача на Java довольно проста, но достаточно сложна, чтобы сгенерировать следующие критические критерии:

Генерация параллелизма с общей / статической структурой данных Map
Используйте сочетание операций get () и put (), чтобы попытаться вызвать внутренние блокировки и / или внутреннее повреждение (для реализации без использования потоков)
Используйте маленький начальный размер карты 2, заставляя внутренний HashMap вызывать внутреннюю перефразировку / изменение размера

Наконец, следующие параметры могут быть изменены по вашему усмотрению:

## Количество рабочих потоков

private static final int NB_THREADS = 3;

## Количество итераций Java-программы

private static final int NB_TEST_ITERATIONS = 50;

## Назначение структуры данных карты. Вы можете выбрать между 4 структурами

// Plain old HashMap (since JDK 1.2)
threadSafeMap1 = new Hashtable<String, Integer>(2);
 
// Plain old Hashtable (since JDK 1.0)
threadSafeMap1 = new Hashtable<String, Integer>(2);
                    
// Fully synchronized HashMap
threadSafeMap2 = new HashMap<String, Integer>(2);
threadSafeMap2 = Collections.synchronizedMap(threadSafeMap2);
 
// ConcurrentHashMap (since JDK 1.5)
threadSafeMap3 = new ConcurrentHashMap<String, Integer>(2);
 
/*** Assign map at your convenience ****/
assignedMapForTest = threadSafeMap3;

Теперь найдите ниже исходный код нашей программы примера.

#### HashMapInfiniteLoopSimulator.java
package org.ph.javaee.training4;
 
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.Hashtable;
 
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
/**
 * HashMapInfiniteLoopSimulator
 * @author Pierre-Hugues Charbonneau
 *
 */
public class HashMapInfiniteLoopSimulator {
 
       private static final int NB_THREADS = 3;
       private static final int NB_TEST_ITERATIONS = 50;
       
       private static Map<String, Integer> assignedMapForTest = null;
       private static Map<String, Integer> nonThreadSafeMap = null;
       private static Map<String, Integer> threadSafeMap1 = null;
       private static Map<String, Integer> threadSafeMap2 = null;
       private static Map<String, Integer> threadSafeMap3 = null;
       
       /**
        * Main program
        * @param args
        */
       public static void main(String[] args) {
             
             System.out.println("Infinite Looping HashMap Simulator");
             System.out.println("Author: Pierre-Hugues Charbonneau");
             System.out.println("http://javaeesupportpatterns.blogspot.com");
             
             for (int i=0; i<NB_TEST_ITERATIONS; i++) {
                    
                    // Plain old HashMap (since JDK 1.2)
                    nonThreadSafeMap = new HashMap<String, Integer>(2);
                    
                    // Plain old Hashtable (since JDK 1.0)
                    threadSafeMap1 = new Hashtable<String, Integer>(2);
                    
                    // Fully synchronized HashMap
                    threadSafeMap2 = new HashMap<String, Integer>(2);
                    threadSafeMap2 = Collections.synchronizedMap(threadSafeMap2);
                    
                    // ConcurrentHashMap (since JDK 1.5)
                    threadSafeMap3 = new ConcurrentHashMap<String, Integer>(2); // ConcurrentHashMap
                    
                    
                    /*** Assign map at your convenience ****/
                    assignedMapForTest = threadSafeMap3;
                    
                    
                    long timeBefore = System.currentTimeMillis();
                    long timeAfter = 0;
                    Float totalProcessingTime = null;
                    
                    ExecutorService executor = Executors.newFixedThreadPool(NB_THREADS);
                    
                    for (int j = 0; j < NB_THREADS; j++) {
                           
                           /** Assign the Map at your convenience **/
                           Runnable worker = new WorkerThread(assignedMapForTest);
                           executor.execute(worker);              
                    }
                    
                    // This will make the executor accept no new threads
                    // and finish all existing threads in the queue
                    executor.shutdown();
                    // Wait until all threads are finish
                    while (!executor.isTerminated()) {
       
                    }
                    
                    timeAfter = System.currentTimeMillis();
                    totalProcessingTime = new Float( (float) (timeAfter - timeBefore) / (float) 1000);
                    
                    System.out.println("All threads completed in "+totalProcessingTime+" seconds");
             }
       }
 
}

#### WorkerThread.java
package org.ph.javaee.training4;
 
import java.util.Map;
 
/**
 * WorkerThread
 *
 * @author Pierre-Hugues Charbonneau
 *
 */
public class WorkerThread implements Runnable {
       
       private Map<String, Integer> map = null;
 
       public WorkerThread(Map<String, Integer> assignedMap) {
             this.map = assignedMap;
             
       }
 
       @Override
       public void run() {
             
             for (int i=0; i<500000; i++) {
                    // Return 2 integers between 1-1000000 inclusive
                    Integer newInteger1 = (int) Math.ceil(Math.random() * 1000000);
                    Integer newInteger2 = (int) Math.ceil(Math.random() * 1000000);                    
                    
                    // 1. Attempt to retrieve a random Integer element
                    Integer retrievedInteger = map.get(String.valueOf(newInteger1));
                    
                    // 2. Attempt to insert a random Integer element
                    map.put(String.valueOf(newInteger2), newInteger2);                
             }
       }
 
}

Сравнение производительности между поточно-ориентированными реализациями Map

Первая цель — сравнить уровень производительности нашей программы при использовании различных реализаций Map с поддержкой многопоточных вычислений:

Обычный старый Hashtable (начиная с JDK 1.0)
Полностью синхронизированный HashMap (через Collections.synchronizedMap ())
ConcurrentHashMap (начиная с JDK 1.5)

Ниже приведены графические результаты выполнения Java-программы для каждой итерации вместе с образцом вывода программной консоли.

# Вывод при использовании ConcurrentHashMap

Infinite Looping HashMap Simulator
Author: Pierre-Hugues Charbonneau
http://javaeesupportpatterns.blogspot.com
All threads completed in 0.984 seconds
All threads completed in 0.908 seconds
All threads completed in 0.706 seconds
All threads completed in 1.068 seconds
All threads completed in 0.621 seconds
All threads completed in 0.594 seconds
All threads completed in 0.569 seconds
All threads completed in 0.599 seconds
………………

Как вы можете видеть, ConcurrentHashMap является явным победителем в этом случае, занимая в среднем всего полсекунды (после первоначального увеличения) для всех 3 рабочих потоков для одновременного чтения и вставки данных в циклическом выражении 500K для назначенной общей карты. Обратите внимание, что при выполнении программы проблем не обнаружено, например, нет ситуации зависания.

Повышение производительности определенно связано с улучшенной производительностью ConcurrentHashMap, такой как неблокирующая операция get ().

Уровень производительности двух других реализаций Map был довольно схожим с небольшим преимуществом для синхронизированного HashMap.

HashMap бесконечная петля проблема репликации

Следующая цель — воспроизвести проблему бесконечного зацикливания HashMap, которая часто наблюдается в производственных средах Java EE. Для этого вам просто нужно назначить не-поточно-безопасную реализацию HashMap согласно приведенному ниже фрагменту кода:

/*** Assign map at your convenience ****/
assignedMapForTest = nonThreadSafeMap;

Запуск программы с использованием не поточного безопасного HashMap должен привести к:

Нет вывода, кроме заголовка программы
Значительное увеличение ЦП наблюдается из системы
В какой-то момент программа Java зависнет, и вы будете вынуждены убить процесс Java

Что произошло? Чтобы разобраться в этой ситуации и подтвердить проблему, мы выполним анализ ЦП на поток из ОС Windows, используя Process Explorer и JVM Thread Dump.
1 — Запустите программу еще раз, затем быстро перехватите поток данных ЦП из Process Explorer, как показано ниже. Под explore.exe вам нужно будет щелкнуть правой кнопкой мыши javaw.exe и выбрать свойства. Вкладка темы будет отображаться. Мы можем видеть в общей сложности 4 потока, используя почти весь процессор нашей системы.

2 — Теперь вам нужно быстро захватить дамп потока JVM с помощью утилиты JDK 1.7 jstack. В нашем примере мы можем видеть наши 3 рабочих потока, которые кажутся занятыми / застрявшими, выполняя операции get () и put ().

..\jdk1.7.0\bin>jstack 272
2012-08-29 14:07:26
Full thread dump Java HotSpot(TM) 64-Bit Server VM (21.0-b17 mixed mode):
 
"pool-1-thread-3" prio=6 tid=0x0000000006a3c000 nid=0x18a0 runnable [0x0000000007ebe000]
   java.lang.Thread.State: RUNNABLE
        at java.util.HashMap.put(Unknown Source)
        at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:32)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
        at java.lang.Thread.run(Unknown Source)
 
"pool-1-thread-2" prio=6 tid=0x0000000006a3b800 nid=0x6d4 runnable [0x000000000805f000]
   java.lang.Thread.State: RUNNABLE
        at java.util.HashMap.get(Unknown Source)
        at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:29)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
        at java.lang.Thread.run(Unknown Source)
 
"pool-1-thread-1" prio=6 tid=0x0000000006a3a800 nid=0x2bc runnable [0x0000000007d9e000]
   java.lang.Thread.State: RUNNABLE
        at java.util.HashMap.put(Unknown Source)
        at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:32)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
        at java.lang.Thread.run(Unknown Source)
..............

Теперь пришло время преобразовать формат DECIMAL идентификатора потока Process Explorer в формат HEXA, как показано ниже. Значение HEXA позволяет нам отображать и идентифицировать каждый поток, как показано ниже:

## TID: 1748 (nid = 0X6D4)

Название темы: pool-1-thread-2
CPU @ 25,71%
Задача: Рабочий поток, выполняющий операцию HashMap.get ()

at java.util.HashMap.get(Unknown Source)
at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:29)
at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)

## TID: 700 (nid = 0X2BC)

Название темы: pool-1-thread-1
CPU @ 23,55%
Задача: Рабочий поток, выполняющий операцию HashMap.put ()

at java.util.HashMap.put(Unknown Source)
at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:32)
at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)

## TID: 6304 (nid = 0X18A0)

Название темы: pool-1-thread-3
CPU @ 12,02%
Задача: Рабочий поток, выполняющий операцию HashMap.put ()

at java.util.HashMap.put(Unknown Source)
at org.ph.javaee.training4.WorkerThread.run(WorkerThread.java:32)
at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)

## TID: 5944 (nid = 0X1738)

Название темы: pool-1-thread-1
CPU @ 20,88%
Задача: выполнение основной программы Java

"main" prio=6 tid=0x0000000001e2b000 nid=0x1738 runnable [0x00000000029df000]
   java.lang.Thread.State: RUNNABLE
        at org.ph.javaee.training4.HashMapInfiniteLoopSimulator.main(HashMapInfiniteLoopSimulator.java:75)

Как видите, приведенная выше корреляция и анализ довольно показательны. Наша основная программа на Java находится в состоянии зависания, потому что наши 3 рабочих потока используют много ресурсов процессора и никуда не денутся. Они могут казаться «застрявшими», выполняя HashMap get () & put (), но на самом деле все они вовлечены в условие бесконечного цикла. Это именно то, что мы хотели повторить.

HashMap с бесконечным циклом глубокого погружения

Теперь давайте продвинем анализ на один шаг вперед, чтобы лучше понять это условие зацикливания. Для этого мы добавили код трассировки в сам Java-класс JDK 1.7 HashMap, чтобы понять, что происходит. Аналогичное ведение журнала было добавлено для операции put (), а также трассировка, указывающая, что сработала внутренняя и автоматическая перефразировка / изменение размера.
Трассировка, добавленная в операциях get () и put (), позволяет нам определить, имеет ли цикл for () работу с циклической зависимостью, которая объясняет условие бесконечного цикла.

#### HashMap.java get() operation
public V get(Object key) {
       
       if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        
/*** P-H add-on- iteration counter ***/
        int iterations = 1;
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
             
                    /*** Circular dependency check ***/
             Entry<K,V> currentEntry = e;
             Entry<K,V> nextEntry = e.next;
             Entry<K,V> nextNextEntry = e.next != null?e.next.next:null;
             
             K currentKey = currentEntry.key;              
             K nextNextKey = nextNextEntry != null?(nextNextEntry.key != null?nextNextEntry.key:null):null;
             
             System.out.println("HashMap.get() #Iterations : "+iterations++);
             
             if (currentKey != null && nextNextKey != null ) {       
                    if (currentKey == nextNextKey || currentKey.equals(nextNextKey))
                    System.out.println(" ** Circular Dependency detected! ["+currentEntry+"]["+nextEntry+"]"+"]["+nextNextEntry+"]");
             }
             /***** END ***/
             
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

HashMap.get() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.resize() in progress...
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 2
HashMap.resize() in progress...
HashMap.resize() in progress...
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 2
HashMap.put() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.put() #Iterations : 1
 ** Circular Dependency detected! [362565=362565][333326=333326]][362565=362565]
HashMap.put() #Iterations : 2
 ** Circular Dependency detected! [333326=333326][362565=362565]][333326=333326]
HashMap.put() #Iterations : 1
HashMap.put() #Iterations : 1
HashMap.get() #Iterations : 1
HashMap.put() #Iterations : 1
.............................
HashMap.put() #Iterations : 56823

Опять же, добавленная регистрация была довольно показательной. Мы можем видеть, что после нескольких внутренних HashMap.resize () внутренняя структура была затронута, создавая условия циклической зависимости и вызывая это условие бесконечного цикла (#iterations увеличивается и увеличивается …) без условия выхода.
Это также показывает, что операция resize () / rehash наиболее подвержена риску внутреннего повреждения, особенно при использовании размера HashMap по умолчанию, равного 16. Это означает, что начальный размер HashMap, по-видимому, является большим фактором риска проблема репликации.
Наконец, интересно отметить, что мы смогли успешно выполнить контрольный пример с помощью не поточного безопасного HashMap, назначив начальный размер настройки в 1000000, предотвращая любое изменение размера вообще. Найдите под объединенным графиком результаты:

HashMap был нашим лучшим исполнителем, но только в случае предотвращения внутреннего изменения размера. Опять же, это определенно не решение проблемы безопасности потока, а просто способ продемонстрировать, что операция изменения размера наиболее подвержена риску, учитывая все манипуляции с HashMap, выполненные в то время.
ConcurrentHashMap, безусловно, является нашим общим победителем, обеспечивая высокую производительность и безопасность потоков в этом тестовом примере.

JBoss AS7 Карта использования структур данных

Теперь мы завершим эту статью рассмотрением различных реализаций Map в современной реализации контейнера Java EE, такой как JBoss AS 7.1.2. Вы можете получить последний исходный код из главной ветки github .
Найти под отчетом:

Всего файлов Java JBoss AS7.1.2 (снимок 28 августа 2012 г.): 7302
Всего классов Java, использующих java.util.Hashtable: 72
Всего классов Java с использованием java.util.HashMap: 512
Всего классов Java с использованием синхронизированного HashMap: 18
Всего классов Java с использованием ConcurrentHashMap: 46

Ссылки на хеш-таблицы были обнаружены в основном в компонентах тестового набора, а также в реализациях, связанных с именами и JNDI. Это низкое использование здесь не является сюрпризом.

Ссылки на java.util.HashMap были найдены в 512 классах Java. Опять же, не удивительно, учитывая, насколько распространена эта реализация с последних нескольких лет. Тем не менее, важно отметить, что хорошее соотношение было найдено либо из локальных переменных (не общих для потоков), синхронизированного HashMap или защиты ручной синхронизации, так что «технически» поточно-ориентированно и не подвержено описанным выше условиям бесконечного цикла (ожидающие / скрытые ошибки). Это все еще реальность, учитывая сложность программирования параллелизма на Java … этот пример с использованием Oracle Service Bus 11g является прекрасным примером).

Низкое использование синхронизированного HashMap было обнаружено только с 18 классами Java из таких пакетов, как JMS, EJB3, RMI и кластеризация.

Наконец, найдите ниже разбивку использования ConcurrentHashMap, которая была нашим основным интересом здесь. Как вы увидите ниже, эта реализация Map используется критическими слоями компонентов JBoss, такими как Web-контейнер, реализация EJB3 и т. Д.

## JBoss Single Sign On
Используется для управления внутренними идентификаторами единого входа с одновременным доступом к потокам.
Всего: 1

## JBoss Java EE & Web-контейнер
Неудивительно, что для управления объектами http-сессий используется много внутренних структур данных Map,
Реестр развертывания, кластеризация и репликация, статистика и т. д. с интенсивным параллельным доступом к потокам.
Всего: 11

## JBoss JNDI & Уровень безопасности
Используется параллельными структурами, такими как внутреннее управление безопасностью JNDI.
Всего: 4

## Управление доменом и управляемым сервером JBoss, планы развертывания…
Всего: 7

## JBoss EJB3
Используется такими структурами данных, как постоянное хранилище файлового таймера, исключение приложения, кэш Entity Bean, сериализация, пассивация …
Всего: 8

## Ядро JBoss, Пулы потоков и управление протоколами
Используется высокопараллельными потоками. Отображает структуры данных, участвующих в обработке и отправке / обработке входящих запросов, таких как HTTP.
Всего: 3

## Разъемы JBoss, такие как JDBC / XA DataSources…
Всего: 2

## Weld (эталонная реализация JSR-299: контексты и внедрение зависимостей для платформы JavaTM EE) Используется в контексте ClassLoader и параллельных статических структур данных Map, включающих одновременный доступ к потокам.
Всего: 3

## JBoss Test Suite Используется в некоторых тестах интеграции, таких как внутреннее хранилище данных, тестирование ClassLoader и т. Д.
Всего: 3

Заключительные слова

Я надеюсь, что эта статья помогла вам вернуться к этой классической проблеме и понять одну из распространенных проблем и рисков, связанных с неправильным использованием не поточной безопасной реализации HashMap. Моя главная рекомендация — быть осторожным при использовании HashMap в контексте параллельных потоков. Если вы не являетесь экспертом по параллелизму Java, я рекомендую вместо этого использовать ConcurrentHashMap, который предлагает очень хороший баланс между производительностью и безопасностью потоков.

Как обычно, всегда рекомендуется дополнительная юридическая экспертиза, например, выполнение циклов тестирования нагрузки и производительности. Это позволит вам обнаружить проблемы с безопасностью потоков и / или производительностью до того, как вы начнете продвигать решение в своей производственной среде клиента.

Ссылка: Java 7: HashMap против ConcurrentHashMap от нашего партнера по JCG Пьера-Хьюга Шарбонно из блога по шаблонам поддержки Java EE и учебному пособию по Java .

Java 7: HashMap против ConcurrentHashMap

Категории

Последние статьи

Рефакторинг Hudson God Class

Альтернативы синтаксиса Java лямбда

Morphia и MongoDB: развивающиеся структуры документов

OpenShift Express: развертывание приложения Java EE (с поддержкой AS7)

Интеграция jqGrid, REST, AJAX и Spring MVC