Анализ проблем многопоточного параллелизма HashMap

Java задняя часть сервер Безопасность

1 сопутствующие симптомы проблемы

1.1 Многопоточность может привести к бесконечному циклу

В прошлом наш Java-код почему-то использовал HashMap, но программа в то время была однопоточной, и все было нормально. Позже возникла проблема с производительностью нашей программы, поэтому нам нужно было стать многопоточной.Поэтому после того, как стала многопоточной, мы вышли в интернет и обнаружили, что программа часто загружала 100% ЦП.Проверить стек , и вы обнаружите, что программа зависает в HashMap. Метод .get() включен, и проблема исчезает после перезапуска программы. Но через какое-то время снова придет. Кроме того, эту проблему может быть трудно воспроизвести в тестовой среде.

Мы просто смотрим на наш собственный код, мы знаем, что HashMap управляется несколькими потоками. В документации Java говорится, что HashMap не является потокобезопасным, и следует использовать ConcurrentHashMap. Но здесь мы можем посмотреть, почему. Простой код выглядит следующим образом:

package com.king.hashmap;

import java.util.HashMap;

public class TestLock {

	private HashMap map = new HashMap();

	public TestLock() {
		Thread t1 = new Thread() {
			public void run() {
				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() {
				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() {
				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() {
				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() {
				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() {
				for (int i = 0; i < 50000; i++) {
					map.get(new Integer(i));
				}

				System.out.println("t6 over");
			}
		};

		Thread t7 = new Thread() {
			public void run() {
				for (int i = 0; i < 50000; i++) {
					map.get(new Integer(i));
				}

				System.out.println("t7 over");
			}
		};

		Thread t8 = new Thread() {
			public void run() {
				for (int i = 0; i < 50000; i++) {
					map.get(new Integer(i));
				}

				System.out.println("t8 over");
			}
		};

		Thread t9 = new Thread() {
			public void run() {
				for (int i = 0; i < 50000; i++) {
					map.get(new Integer(i));
				}

				System.out.println("t9 over");
			}
		};

		Thread t10 = new Thread() {
			public void run() {
				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) {
		new TestLock();
	}
}

То есть запустить 10 потоков и непрерывно помещать/получать содержимое в непоточно-безопасный HashMap.Содержимое put очень простое, а ключ и значение представляют собой целые числа, которые увеличиваются с 0 (содержимое этого put не очень хорошо сделано, в итоге это потом мешало мне думать об анализе проблемы). Выполняя параллельные операции записи в HashMap, я думал, что это будет генерировать только грязные данные, но многократно запуская эту программу,会出现线程t1、t2被hang住的情况，多数情况下是一个线程被hang住另一个成功结束，偶尔会10个线程都被hang住.

产生这个死循环的根源在于对一个未保护的共享变量 — 一个"HashMap"数据结构的操作. Когда я добавил "синхронизировал" в методы всех операций, все пришло в норму. Это ошибка JDK? Следует сказать, что нет, об этом явлении сообщалось давно.Sun的工程师并不认为这是bug，而是建议在这样的场景下应采用"ConcurrentHashMap".

CPU利用率过高一般是因为出现了出现了死循环，导致部分线程一直运行，占用cpu时间。问题原因就是HashMap是非线程安全的，多个线程put的时候造成了某个key值Entry key List的死循环，问题就这么产生了。

Когда другой поток получает ключ бесконечного цикла Entry List, get всегда будет выполняться. Конечным результатом является то, что все больше и больше потоков находятся в бесконечном цикле, что в конечном итоге приводит к зависанию сервера. Обычно мы думаем, что когда HashMap повторно вставляет значение, оно перезапишет предыдущее значение, и это правильно.但是对于多线程访问的时候，由于其内部实现机制(在多线程环境且未作同步的情况下，对同一个HashMap做put操作可能导致两个或以上线程同时做rehash动作，就可能导致循环键表出现，一旦出现线程将无法终止，持续占用CPU，导致CPU使用率居高不下)，就可能出现安全问题了.

Используйте инструмент jstack для создания дампа информации о стеке сервера с проблемой.死循环的话，首先查找RUNNABLE的线程, найдите код проблемы следующим образом:

java.lang.Thread.State:RUNNABLE в java.util.HashMap.get(HashMap.java:303) на com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183) Всего 23 раза. java.lang.Thread.State:RUNNABLE в java.util.HashMap.put(HashMap.java:374) на com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter.java:816) появился 3 раза.

Уведомление: Неразумное использование HashMap приводит к бесконечному циклу, а не к взаимоблокировке.

Более 1,2 потока, установленные время, может привести к потере элементов

Основная проблема заключается в методе Addentry New Entry (Hash, Key, Value, E), если два потока достигли E, то их следующие элементы равны E, а затем присваивают значение элементу Table. В проигрыше есть успех.

1.3 После помещения ненулевого элемента get становится нулевым

Код в методе передачи выглядит следующим образом:

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);
        }
    }
}

В этом методе присвоить старый массив src, пройтись по src, когда элемент src не нулевой, установить элемент в src равным null, то есть установить элемент в старом массиве равным null, то есть это предложение:

if (e != null) {
    src[j] = null;

В это время, если есть метод get для доступа к ключу, он по-прежнему получает старый массив и, конечно же, не может получить соответствующее ему значение.

Резюме: когда HashMap не синхронизирован, в параллельных программах будет много тонких проблем, и трудно найти причину на поверхности. Таким образом, использование HashMap противоречит здравому смыслу и может быть вызвано параллелизмом.

2 Структура данных HashMap

HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个<key, value>插到table[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表。

Мы знаем, что если таблица [] размера маленькая, скажем, только два, если вы хотите поставить 10 клавиш, то столкновение очень часто, поэтому A (1) алгоритм поиска, он становится связанным обходом в списке, изменение производительности O (n), который является дефектным хэш-таблицей.

Поэтому размер и емкость хеш-таблицы очень важны. Вообще говоря, когда в контейнере хеш-таблицы есть данные для вставки, он проверяет, превышает ли емкость установленный порог.Если он превышает, размер хэш-таблицы необходимо увеличить, но таким образом элементы во всем Хэш-таблица должна быть пересчитана. Это называется перефразировать, и стоимость довольно велика.

2.1 Перефразируйте исходный код HashMap

Далее давайте взглянем на исходный код Java HashMap. Поместите пару Key, Value в таблицу Hash:

public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //如果该key已被插入，则替换掉旧的value（链接操作）
    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++;
    //该key不存在，需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

Проверьте, не превышает ли емкость стандарт:

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);
    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

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

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

Перенесенный исходный код, обратите внимание на основные моменты:

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到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);
        }
    }
}

Что ж, этот код относительно нормальный. И нет проблем.

2.2 Обычный процесс ReHash

Нарисуйте картинку для демонстрации.

  1. Предположим, что наш алгоритм хеширования состоит в том, чтобы просто использовать модификатор ключа для просмотра размера таблицы (то есть длины массива).
  2. Верхний — старая хэш-таблица Размер хеш-таблицы равен 2, поэтому ключи = 3, 7 и 5. После мода 2 все они конфликтуют с таблицей[1].
  3. Следующие три шага — это процесс изменения размера хэш-таблицы до 4, а затем повторный хеширование всех .

2.3 ОСОБЕННОЕ ПРОЦЕСС

(1) Предположим, у нас есть два потока. Я отметил его красным и голубым цветом. Давайте вернемся и посмотрим на эту деталь в нашем коде передачи:

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);

И наше выполнение второго потока завершено. Итак, у нас есть что-то вроде этого ниже.

Примечание. Поскольку e для Thread1 указывает на ключ (3), а next указывает на ключ (7), после повторного хеширования потока 2 он указывает на связанный список после повторного хеширования потока 2. Мы видим, что порядок связанного списка обратный.

(2) После запланированного возвращения потока для выполнения.

  1. Сначала выполните newTalbe[i] = e.
  2. Тогда E = Далее, в результате чего указательный ключ E (7).
  3. И next = e.next в следующем цикле приводит к тому, что next указывает на ключ (3).

(3) Все хорошо.Нити работают одна за другой. Снимите ключ (7), поместите его в первый из newTable[i], а затем переместите e и следующий вниз.

(4) Появится кольцевая ссылка. e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了.

Итак, когда наш поток вызывает HashTable.get(11), происходит трагедия — бесконечный цикл.

3 три решения

3.1 Hashtable заменяет HashMap

Hashtable синхронизируется, но итератор возвращается итератором и возвращается всеми "методами представления коллекции" Hashtable.Collection 的 listIterator 方法都是快速失败的: после создания Iterator, если Hashtable структурно изменена,除非通过 Iterator 自身的移除或添加方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException. Таким образом, перед лицом одновременных модификаций итератор быстро полностью выйдет из строя, не рискуя произвольным недетерминированным поведением в какой-то неопределенное время в будущем. Перечисления, возвращаемые методами ключа и значения Hashtable, не являются отказоустойчивыми.

Уведомление,迭代器的快速失败行为无法得到保证, потому что, как правило, невозможно дать какие-либо жесткие гарантии того, будут ли происходить несинхронизированные одновременные модификации.快速失败迭代器会尽最大努力抛出 ConcurrentModificationException. Поэтому было бы ошибкой написать программу, которая опирается на это исключение, чтобы улучшить правильность таких итераторов: Fail-быстрое поведение итераторы следует использовать только для обнаружения программных ошибок.

3.2 Collections.synchronizedMap обертывает HashMap

返回由指定映射支持的同步（线程安全的）映射. Чтобы гарантировать доступ по порядку, все обращения к базовой карте должны выполняться через возвращенную карту.在返回的映射或其任意 collection 视图上进行迭代时，强制用户手工在返回的映射上进行同步:

Map m = Collections.synchronizedMap(new HashMap());
...
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());
}

Несоблюдение этой рекомендации приведет к неопределенному поведению. Если указанная карта является сериализуемой, возвращаемая карта также будет сериализуемой.

3.3 ConcurrentHashMap заменяет HashMap

Поддержка получения полной параллельной и обновленной хеш-таблицы. Такое соответствие той же функциональной спецификации, что и у HashTable, и включает версию каждого метода, соответствующую HashTable. но,尽管所有操作都是线程安全的，但检索操作不必锁定，并且不支持以某种防止所有访问的方式锁定整个表. Такая программа может быть полностью совместима с Hashtable, в зависимости от ее потокобезопасности, и синхронизирована с посторонними деталями.

Восстановление операций (включая GET), как правило, не блокируют и, следовательно, могут перекрываться с операциями обновления (включая поставку и удалить).检索会影响最近完成的更新操作的结果. Для некоторых агрегатных операций, таких как putAll и clear, параллельное извлечение может влиять только на вставку и удаление определенных записей. Точно так же итераторы и перечисления возвращают элементы, влияющие на состояние хеш-таблицы в момент времени, когда итератор/перечисление создан, или позже. Они не вызывают ConcurrentModificationException. Однако итераторы предназначены для одновременного использования только одним потоком.

Категории