Эта статья написана с точки зрения безопасности многопотокового параллелизма и поможет вам понять, как использовать многопоточный параллельный доступ.HashMapВопросы, которые возникнут, углубленное изучениеConcurrentHashMap, поможет вам полностью освоить эти основные технологии.
Полный текст аннотации:
-
HashMapОсновные технологии -
ConcurrentHashMapОсновные технологии - Практическое применение блокировки сегментов
Адрес блога:sourl.cn/r3RVY8
HashMap
HashMapЭто класс коллекции, который мы часто используем.До JDK 1.7 нижний слой использовал структуру комбинации массива и связанного списка, как показано на следующем рисунке:
Недавно добавленный элемент позиционируется по модулюTableПозиция массива, а затем добавьте элемент в начало связанного списка, чтобы к нему можно было быстро получить доступ при следующем извлечении.
При обращении к данным позиция в массиве также находится по модулю, а затем выполняется обход связанного списка, и путем их поочередного сравнения получаются соответствующие элементы.
еслиHasMapКогда в нем слишком много элементов, связанный список в определенной позиции может быть очень длинным. оригинальныйO(1)Производительность поиска может снизиться доO(N), что серьезно снижает эффективность поиска.
Чтобы избежать этого, когдаHasMapКогда количество элементов соответствует следующим условиям, емкость будет автоматически расширена, а элементы будут переназначены.
// size:HashMap 中实际元素数量
//capacity：HashMap 容量，即 Table 数组长度，默认为：16
//loadFactor：负载因子，默认为：0.75
size>=capacity*loadFactor
HasMapУдвоит емкость, а затем перенесет исходные элементы массива в новый массив.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 以下代码导致死链的产生
e.next = newTable[i];
// 插入到链表头结点，
newTable[i] = e;
e = next;
}
}
}
Когда старые элементы массива переносятся в новый массив, "вставка головы', что приведет к сортировке новых элементов списка в обратном порядке.
В случае параллельного многопоточного расширения может формироваться связанный списокМертвая ссылка (кольцевой список). Как только происходит какое-либо действие по поиску элемента, поток застревает в бесконечном цикле, вызываяCPUИспользование взлетело.
Процессов детального разбора по формированию мертвых цепей в интернете много, поэтому я не буду их здесь подробно описывать, если вам интересно, вы можете прочитать следующие статьи от **@陈豪**.
Адрес статьи:классная оболочка.cai/articles/96…
План улучшения JDK1.8
JDK1.8 HashMapБазовая структура полностью реконструирована, и используется комбинированная структура массива плюс связанный список/красно-черное дерево.
Новые элементы по-прежнему получаются по модулюTableпозицию массива, а затем добавить элемент в связанный списокхвостик. Как только количество элементов связанного списка превышает 8, он автоматически преобразуется вкрасно-черное дерево, что еще больше повышает эффективность поиска.
Вопрос интервью: Почему здесь использовано красно-черное дерево? вместо других бинарных деревьев?
Поскольку связанный список JDK1.8 принимает "вставка хвоста”, чтобы избежать возможности образования мертвой цепи в связанном списке в случае параллельного расширения.
ТакHashMapБезопасен ли параллелизм в JDK1.8?
На самом деле не существует такой вещи, как многопоточный параллелизм.HashMapМожет привести к потере данных.
Ниже приведен тестовый код JDK1.8:
Вывод на моем компе такой, данные потеряны:
Начиная с исходного кода, причины потери данных в параллельном процессе следующие:
Переопределено во время параллельного назначения
В случае параллелизма назначение одного потока может быть перезаписано другим потоком, что приводит к потере объекта.
проблема расчета размера
После добавления каждого элементаsizeбудет увеличен на 1. используется здесь++iметод, который по своей сути небезопасен для параллелизма.
Причин проблемы потери объекта может быть много, но вот только две очевидные проблемы для сравнения.
Конечно, в JDK1.7 также существует проблема потери данных, и причина проблемы аналогична.
как только это произойдетмертвая цепьпроблема с машинойCPUПарящий, с помощью системы мониторинга, мы можем легко обнаружить.
Но проблему потери данных не так просто обнаружить. Поскольку канал потери данных часто бывает очень длинным, запуск системы часто занимает некоторое время, и в этом случае грязные данные не формируются. Только тогда, когда возникают какие-то странные ситуации, мы можем расследовать их, а устранять такие проблемы сложнее.
SynchronizedMap
Для одновременных случаев мы можем использовать предоставленный JDKSynchronizedMapобеспечить безопасность.
SynchronizedMapявляется внутренним классом, экземпляры могут быть созданы только следующими способами.
Map m = Collections.synchronizedMap(new HashMap(...));
SynchronizedMapИсходный код выглядит следующим образом:
будет использоваться в каждом методеsynchronizedБлокировка ключевых слов для обеспечения безопасности параллелизма.
Поскольку несколько потоков совместно используют одну и ту же блокировку, только одному потоку разрешено одновременно читать и записывать операции, а другие потоки должны ждать, что значительно снижает производительность.
И большинство бизнес-сценариев меньше читают и пишут, многопоточные операции чтения сами по себе не конфликтуют,SynchronizedMapСильно ограничивает производительность чтения.
Поэтому мы редко используем многопоточные параллельные сценарии.SynchronizedMap.
ConcurrentHashMap
Поскольку несколько потоков совместно используют блокировку, производительность падает. Затем представьте, сможем ли мы получить еще несколько блокировок, шунтировать потоки, уменьшить конфликты блокировок и улучшить параллелизм.
ConcurrentHashMapИменно этот метод не только обеспечивает сохранность данных параллельного процесса, но и обеспечивает определенную эффективность.
JDK1.7
JDK1.7 ConcurrentHashMapСтруктура данных выглядит так:
SegamentЯвляетсяConcurrentHashMapвнутренний класс, базовая структура сHashMapПоследовательный. Кроме тогоSegamentунаследовано отReentrantLock, диаграмма классов выглядит следующим образом:
при добавлении новых элементовConcurrentHashMap, сначала найдите соответствующий ключ по хеш-значению ключаSegament. затем непосредственноSegamentЗаблокировано, если приобретение прошло успешно, последующие шаги такие же, какHashMap.
Благодаря наличию замка,SegamentВсе внутренние операции защищены от параллелизма, в то время как из-за другихSegamentне занят и поэтому может поддерживатьconcurrencyLevelПоточно-ориентированное параллельное чтение и запись.
проблема со статистикой размера
Несмотря на то чтоConcurrentHashMapВведение блокировок сегментов решает проблему многопоточного параллелизма, но в то же время вносит новые сложности, приводящие к вычислительным затратам.ConcurrentHashMapКоличество элементов усложнится.
так какConcurrentHashMapЭлементы фактически распределены вSegament, чтобы подсчитать фактическое число, мы можем только пройтиSegamentСуммирование массива.
Для точности данных посредством этого процесса нам необходимо заблокировать всеSegament, а затем разблокировать их последовательно после завершения расчета. Однако это приведет к блокировке операции записи, которая в определенной степени уменьшится.ConcurrentHashMapпредставление.
Так прямо здесьConcurrentHashMap#sizeСтатистические методы в некоторой степени оптимизированы.
SegmentКаждый раз, когда он модифицируется (записывается, удаляется), онmodCount(количество обновлений) плюс 1. Пока два последовательных вычисления получают всеSegment modCountЕсли сумма одинакова, это означает, что в двух процессах расчета нет записи или удаления, и статистическая величина может быть возвращена напрямую.
Если трижды результаты не являются последовательными, это может быть не только для всехSegmentЗафиксируйте и пересчитайте результат.
Здесь следует отметить, чтоsizeКоличество не может быть точным на 100%. Это связано с тем, что последняя последовательностьSegmentПосле разблокировки другие потоки могут начать операцию записи. В результате возвращенное число не соответствует фактическому числу.
Тем не менее, это приемлемо, но никогда не останавливает запись во все элементы, чтобы подсчитать элементы.
проблемы с производительностью
Представьте себе экстремальную ситуацию, все записи попадают в одно и то жеSegment, что приводит кConcurrentHashMapвыродиться вSynchronizedMap, чтобы захватить замок вместе.
План улучшения JDK1.8
После JDK1.8,ConcurrentHashMapКонструкция сегментированных блокировок отменена, чтобы еще больше уменьшить возникновение конфликтов блокировок. Кроме того, для дальнейшего повышения эффективности поиска также введена структура красно-черного дерева.
Структура данных выглядит так:
Tableкаждый из массиваNodeМы все можем думать об этом как о замке, который позволяет избежатьSegamentпроблема деградации.
Также однаждыConcurrentHashMapрасширение,TableПо мере увеличения количества элементов массива будет увеличиваться и количество блокировок, а также будет увеличиваться степень параллелизма.
Написание исходного кода элемента более сложно, здесь вы можете обратиться к следующей блок-схеме.
Как правило, JDK1.8 использует метод CAS для добавленияsynchronizedспособ обеспечить безопасность параллелизма.
оптимизация метода размера
JDK1.8 ConcurrentHashMap#sizeСтатистический метод относительно прост:
Для этого метода нам нужно знать две важные переменные:
baseCountCounterCell[] counterCells
baseCountЧтобы записать количество элементов, каждый раз, когда элемент элемента изменяется, он будет использоватьсяCASспособ обновить значение.
Если несколько потоков добавляют новые элементы одновременно,baseCountКонфликт обновлений будет включенCounterCell,используяCASспособ обновить общее количество доcounterCellsПозиция, соответствующая массиву, снижает конкуренцию.
еслиCASвозобновитьcounterCellsМножественные сбои в расположении в массиве указывают на то, что это расположение используется несколькими потоками. В это время он будет расширен за счетcounterCellsобразом, опять же, чтобы уменьшить конфликт.
Благодаря вышеуказанным усилиям становится очень просто подсчитать общее количество элементов, просто рассчитайтеbaseCountиcounterCellsВ общем, весь процесс не нужно блокировать.
Хорошо подумай,counterCellsЭто также связано с идеей блокировок сегментов, чтобы уменьшить многопоточную конкуренцию.
Практическое применение блокировки сегментов
ConcurrentHashMapИспользуя метод проектирования сегментированных блокировок, снижается степень детализации блокировок и повышается степень параллелизма. Мы можем извлечь уроки из этого проекта и решить некоторыеДанные точки доступаОбновить вопрос.
Например, если у нас сейчас есть платежная система, каждый раз, когда пользователь совершает успешный платеж, баланс счета мерчанта будет соответственно увеличиваться.
Когда проводится большая акция, многие пользователи платят одновременно, и баланс одного и того же торгового счета будет обновляться одновременно.
Для обеспечения безопасности данных на уровне базы данных для каждого обновления используются блокировки строк. В случае одновременных обновлений только один поток может получить блокировку и обновить данные, а другие потоки могут только ждать снятия блокировки. Это может привести к тому, что операция обновления баланса других потоков займет слишком много времени или даже истечет время ожидания транзакции, а обновление баланса завершится ошибкой.
Это типичныйДанные точки доступаОбновить вопрос.
Фактическая причина этой проблемы заключается в многопоточном захвате параллелизма.блокировка строкиВ результате, если имеется несколько блокировок строк, можно ли уменьшить конфликт блокировок?
Да, здесь мы учимсяConcurrentHashMapДизайн сегментной блокировки, создание нескольких под аккаунтом мерчантатеневая учетная запись.
Затем каждый раз, когда баланс обновляется, случайныйтеневая учетная записьОбновите соответственно.
теоретическитеневая учетная записьИх может быть создано бесконечное количество, а это значит, что мы можем бесконечно улучшать возможности параллелизма.
Спасибо **@why** Боже за предложение концепции теневых аккаунтов. Если вам интересно, вы можете выполнить поиск и подписаться. Общедоступный номер: почему технологии
Внедрение новых решений в архитектуру проектирования означает введение новой сложности, мы должны учитывать эти вопросы четко и всесторонне сбалансировать проектирование.
Хотя введение теневых счетов решает проблему горячих данных, подсчет общего баланса мерчантов становится весьма проблематичным, приходится считать остатки всех субсчетов.
Кроме того, в реальном бизнес-сценарии баланс продавца не только увеличится, но и может быть соответственно вычтен. Возможно, что общий баланс мерчанта достаточен, но баланс выбранного теневого счета недостаточен.
Как это сделать? Об этом остается всем подумать. Я не знаю, сталкивался ли кто-нибудь из читателей с подобной проблемой, добро пожаловать, чтобы оставить сообщение для обсуждения.
Если вам интересно, мы можем подробно поговорить об этом в следующей статье.Горячий аккаунтрешение.
Суммировать
HashMapВ процессе многопоточного параллелизма есть вероятность мертвой цепи и потери данных, что не подходит для сценариев многопоточного параллельного использования, мы можем использовать это в локальных переменных метода.
SynchronizedMapХотя потокобезопасен, производительность слишком низкая из-за слишком большой детализации блокировок, поэтому он не подходит для многопоточного использования.
ConcurrentHashMapЗа счет использования множественных блокировок вероятность многопоточной параллельной конкуренции полностью снижается, а параллелизм улучшается, что очень подходит для использования в многопоточности.
Наконец, маленький черный брат упоминает еще один момент, не упоминайте многопоточную среду, просто используйте ее напрямую.ConcurrentHashMap. Если только использоватьMapПоскольку это глобальная переменная, после первоначальной загрузки переменной данные больше не будут меняться. Рекомендуется использовать неизменяемые классы коллекций.Collections#unmodifiableMap, или используйтеImmutableMap. Преимущество неизменяемых коллекций заключается в том, что они могут эффективно предотвращать их тайное изменение другими потоками, вызывая тем самым некоторые проблемы в бизнесе.
ConcurrentHashMapКлассическая идея блокировки сегмента, мы можем применить ее вГорячие обновлениясцена для повышения эффективности обновления.
Но нужно помнить, что когда мы вводим новые решения для решения проблем, мы должны вводить новую сложность, которая приводит к другим проблемам. В этом процессе вы должны сначала четко обдумать эти вопросы, а затем сделать определенные компромиссы посередине.
использованная литература
- Code Out the Efficient Java Development Manual
- Woohoo. Джейсон GJ.com/Java/concur…
Последнее слово (пожалуйста, обратите внимание)
Когда вы это увидите, пожалуйста, подпишитесь и поставьте лайк. Не делай этого в следующий раз, старший брат. Писать статьи очень сложно, и вам нужны положительные отзывы.
Если вам не хватает таланта и обучения, неизбежно будут ошибки.Если вы обнаружите какие-либо ошибки, пожалуйста, оставьте сообщение и укажите на это мне, и я его исправлю.
Спасибо за прочтение, настаиваю на оригинальности, очень приветствую и благодарю за внимание
Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: программа для общения, ежедневный толчок галантерейных товаров. Если вам интересен мой рекомендуемый контент, вы также можете подписаться на мой блог:studyidea.cn