Теория и практика Java : Параллельные классы коллекций

ConcurrentHashMap и CopyOnWriteArrayList предлагают потокобезопасность и улучшенную масштабируемость

Помимо многих других полезных для построения параллелизма блоков, пакет Дага Ли (Doug Lea) util.concurrent содержит высокопроизводительные, потокобезопасные реализации для рабочих типов коллекций List и Map. В этом месяце Брайан Гетц покажет вам, насколько выиграют многие параллельные программы, если просто поменять Hashtable или synchronizedMap на ConcurrentHashMap.

Брайан Гетц, главный консультант, Quiotix

Брайан Гетц (Brian Goetz) - консультант по ПО и последние 15 лет работал профессиональными разработчиком ПО. Сейчас он является главным консультантом в фирме Quiotix, занимающейся разработкой ПО и консалтингом и находящейся в Лос-Альтос, Калифорния. Следите за публикациями Брайана в популярных промышленных изданиях. Вы можете связаться с Брайаном по адресу brian@quiotix.com



26.02.2007

Первым ассоциативным классом коллекций, который появился библиотеке классов Java, был Hashtable, который являлся частью JDK 1.0. Hashtable предоставлял легкую в использовании, потокобезопасную реализацию ассоциативной map-таблицы и, конечно, был удобен. Однако потокобезопасность обошлась дорого - все методы в Hashtable были синхронизированы. В то время за синхронизацию без конкуренции приходилось расплачиваться производительностью. Преемник Hashtable, HashMap, появившийся как часть Collections framework в JDK 1.2, решал проблему потокобезопасности, предоставляя несинхронизированный базовый класс и синхронизированное обрамление, Collections.synchronizedMap. Разделение базовой функциональности и потокобезопасности в Collections.synchronizedMap позволило получить синхронизацию пользователям, которым она была нужна, а тем, кому она не нужна, не приходилось платить за неё цену.

Упрощённый подход к синхронизации, использованный и в Hashtable и в synchronizedMap, - синхронизация каждого метода с Hashtable или с синхронизированным объектом обрамления Map - имеет два основных недостатка. Он является препятствием для масштабируемости, потому что к хеш-таблице может одновременно обращаться только один поток. Одновременно с этим, недостаточно обеспечить настоящую безопасность потоков, при этом множество распространённых составных операций всё ещё требует дополнительной синхронизации. Хотя простые операции вроде get() и put() могут выполняться безопасно без дополнительной синхронизации, существуют несколько распространённых последовательностей операций, таких как iterate или put-if-absent, которые всё же нуждаются во внешней синхронизации, чтобы избежать конкуренции за данные.

Условная потокобезопасность

Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потокобезопасными - все операции в отдельности потокобезопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные. Первый отрывок в Листинге 1 демонстрирует распросранённую идиому put-if-absent (запись-если-пусто) - если элемент ещё не существует в Map-таблице, добавить его. К сожалению, как уже говорилось, у другого потока существует возможность вставить значение с повторяющимся ключом между моментами возврата из метода containsKey() и вызова метода put(). Если вы хотите гарантировать, что вставка выполняется строго один раз, вам необходимо заключить пару выражений в синхронизированный блок, который синхронизируется с Map m.

Другие примеры в Листинге 1 связаны с повторением. В первом примере результаты List.size() могли стать недействительными во время выполнения цикла, потому что другой поток мог удалить элементы из списка. Если ситуация сложилась неудачно, и элемент был удален другим потоком сразу же после начала последнего повторения цикла, то List.get() возвратит null и doSomething() скорее всего выбросит NullPointerException. Что вам можно сделать, чтобы избежать этого? Если другой поток может обращаться к List, в то время, когда вы выполняете его перебор, вы должны заблокировать весь List на время перебора, заключив его в блок synchronized, синхронизирующийся с List l. Это решает проблемы с конкуренцией за данные, но в дальнейшем скажется на параллелизме, поскольку блокировка всего List во время перебора может надолго заблокировать доступ к списку другим потокам.

В Collections framework были введены итераторы для обхода списка или другой коллекции, которые оптимизируют процесс перебора элементов коллекции. Однако итераторы, реализованные в классах коллекций java.util, часто подвержены сбоям, что означает, что если один поток изменяет коллекцию в то время, когда другой пропускает её через Iterator, очередной вызов Iterator.hasNext() или Iterator.next() выбросит ConcurrentModificationException. Как и с предыдущим примером, если вы хотите предотвратить ConcurrentModificationException, вам надо целиком блокировать List в то время, когда вы выполняете повторения, заключив его внутрь блока synchronized, который синхронизируется с List l. (В качестве альтернативы, вы можете вызвать List.toArray() и делать перебор в массиве без синхронизации, но это может быть дорого, если список достаточно большой.)

Листинг 1. Типичный случай конкуренции в синхронизированных map-таблицах
    Map m = Collections.synchronizedMap(new HashMap());
    List l = Collections.synchronizedList(new ArrayList());

    // put-if-absent idiom - contains a race condition
    // may require external synchronization
    if (!map.containsKey(key))
      map.put(key, value);

    // ad-hoc iteration - contains race conditions
    // may require external synchronization
    for (int i=0; i<list.size(); i++) {
      doSomething(list.get(i));
    }

    // normal iteration - can throw ConcurrentModificationException
    // may require external synchronization
    for (Iterator i=list.iterator(); i.hasNext(); ) {
      doSomething(i.next());
    }

Ложное чувство уверенности

Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу - разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потокобезопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException.


Проблемы масштабируемости

Масштабируемость показывает, как меняется пропускная способность приложения при увеличении рабочей нагрузки и доступных вычислительных ресурсов. Масштабируемая программа может выдержать пропорционально большую нагрузку при большем количестве процессоров, памяти или пропускной способности ввода/вывода. Блокировка ресурса общего пользования ради монопольного доступа представляет собой проблему для масштабируемости - она не позволяет другим потокам получить доступ к этому ресурсу даже при наличии простаивающих процессоров для планирования этих потоков. Для достижения масштабируемости мы должны исключить или сократить нашу зависимость от монопольных блокировок ресурсов.

Ещё большая проблема с синхронизированным обрамлением коллекций и ранними классами Hashtable и Vector состоит в том, что они синхронизируются с единственной блокировкой. Это означает, что одновременно только один поток может иметь доступ к коллекции, и если один поток находится в процессе чтения Map-таблицы, все остальные потоки, которые хотят прочитать из неё или записать в неё, вынуждены ждать. Наиболее распространённые операции с Map-таблицей, get() и put(), могут требовать больших вычислений, чем это может показаться, - при обходе хеш-бакета в поисках специфического значения ключа get() может потребоваться вызов Object.equals() для большого количества кандидатов. Если функция hashCode(), используемая классом ключа, не распределяет значения равномерно по всему ряду хэшей или же имеет большое количество коллизий хэша, отдельные цепочки бакетов могут оказаться намного длиннее других, а прохождение длинной цепочки хэшей и вызов equals() на определённом проценте его элементов могут быть слишком медленными. Проблема высокой стоимости get() и put() при таких условиях выражается не только в том, что доступ будет медленным, но и в том, что всем другим потокам блокируется доступ кMap-таблице пока происходит обход этой цепочки хэшей.

Тот факт, что get() в некоторых случаях может требовать значительного времени на выполнение, ещё больше усугубляется проблемой условной безопасности потоков, обсуждавшейся выше. Условия конкуренции, иллюстрируемые в Листинге 1, часто делают необходимым, чтобы единичная блокировка коллекции удерживалась гораздо большее время, чем требуется на выполнение единичной операции. Если вы собираетесь удерживать блокировку коллекции в течение всего перебора, то другие потоки могут замереть в ожидании блокировки коллекции на длительное время.

Пример: Простая кэш-память

Одно из наиболее распространённых применений для Map в серверных приложениях - реализация кэш-памяти. Серверные приложения могут кэшировать содержимое файлов, сгенерированные страницы, результаты запросов к базам данных, деревья DOM, ассоциированные с анализируемыми XML-файлами и многие другие типы данных. Основное назначение кэш-памяти - сокращение времени обслуживания и увеличение пропускной способности за счёт использования результатов предыдущего вычисления. Типичная особенность рабочей нагрузки кэш-памяти состоит в том, что попадания встречаются гораздо чаще, чем обновления, поэтому (в идеале) кэш-память обеспечивает очень хорошую производительность для get(). Кэш-память, тормозящая производительность приложения, даже хуже, чем полное отсутствие кэш-памяти.

Если вы использовали synchronizedMap для реализации кэш-памяти, вы вносите в ваше приложение потенциальную проблему масштабируемости. Одновременно только один поток может иметь доступ к Map, и это распространяется на все потоки, которые могут извлекать значение из Map-таблицы, равно как и на потоки, которые желают вставить новую пару (key, value) в map-таблицу.

Сокращение размеров блокировок

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


ConcurrentHashMap

Класс ConcurrentHashMap из util.concurrent (который также появится в пакете java.util.concurrent в JDK 1.5) - это потокобезопасная реализация Map, предоставляющая намного большую степень параллелизма, чем synchronizedMap. Сразу много операций чтения могут почти всегда выполняться параллельно, одновременные чтения и записи могут обычно выполняться параллельно, а сразу несколько одновременных записей могут зачастую выполняться параллельно. (Соответственный класс ConcurrentReaderHashMap предлагает аналогичный параллелизм для множественных операций чтений, но допускает лишь одну активную операцию записи.) ConcurrentHashMap спроектирован для оптимизации операций извлечения; на деле, успешные операции get() обычно успешно выполняются безо всяких блокировок. Достижение потокобезопасности без блокировок является сложным и требует глубокого понимания деталей Модели Памяти Java (Java Memory Model). Реализация ConcurrentHashMap и остальная часть util.concurrent были в значительной степени проанализированы экспертами по параллелизму на предмет корректности и безопасности потоков. Мы рассмотрим детали реализации ConcurrentHashMap в статье в следующем месяце.

ConcurrentHashMap добивается более высокой степени параллелизма, слегка смягчая обещания, которые даются тем, кто её вызывает. Операция извлечения возвратит значение, вставленное самой последней завершившейся операцией вставки, а также может возвратить значение, добавленное операцией вставки, выполняемой в настоящее время (но она никогда не возвратит бессмыслицы). Итераторы, возвращаемые ConcurrentHashMap.iterator() возвратят каждый элемент не более одного раза и никогда не выкинут ConcurrentModificationException, но могут отображать или не отображать вставки или удаления, имевшие место со времени, когда итератор был сконструирован. Блокировки целой таблицы не требуются (да и невозможны) для обеспечения потокобезопасности при переборе коллекции. ConcurrentHashMap может использоваться для замены synchronizedMap или Hashtable в любом приложении, которое не основано на способности делать блокировку всей таблицы для предотвращения модификаций.

Данные компромиссы позволяют ConcurrentHashMap обеспечивать намного более высокую масштабируемость, чем Hashtable, не ставя под угрозу его эффективность для широкого множества распространённых случаев, таких как кэш-память с общим доступом.

Насколько лучше?

Таблица 1 приблизительно показывает отличия в масштабируемости между Hashtable и ConcurrentHashMap. При каждом запуске n потоков параллельно выполняли жёсткий цикл, в котором они извлекали произвольные значения ключа из Hashtable или из ConcurrentHashMap при 80 процентах неуспеха, выполняя операцию put(), и 1 проценте успешных извлечений при выполнении remove(). Тесты проводились на двухпроцессорной системе на базе Xeon под управлением системы Linux. Данные показывают время выполнения в миллисекундах для 10,000,000 итераций, приведённые к однопоточному случаю для ConcurrentHashMap. Вы можете видеть, что производительность ConcurrentHashMap остаётся масштабируемой до множества потоков, тогда как производительность Hashtable почти сразу падает при наличии конкуренции за блокировку.

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

Таблица 1. Масштабируемость Hashtable по сравнению с ConcurrentHashMap

toptoptoptoptoptoptop
ThreadsConcurrentHashMapHashtable
1 1.00 1.03
2 2.5932.40
4 5.5878.23
8 13.21163.48
16 27.58341.21
32 57.27778.41

CopyOnWriteArrayList

Класс CopyOnWriteArrayList предназначен на замену ArrayList в параллельных приложениях, где обходы значительно превосходят по количеству вставки и удаления. Это достаточно типично для случая, когда ArrayList используется для хранения списка подписчиков, как в приложениях AWT или Swing или вообще в классах JavaBean. (Похожие на них CopyOnWriteArraySet используют CopyOnWriteArrayList для реализации интерфейса Set.)

Если вы используете обычный ArrayList для хранения списка подписчиков, то до тех пор, пока список допускает изменения и к нему могут обращаться много потоков, вы должны либо блокировать целый список во время перебора либо клонировать его перед перебором, оба варианта обходятся значительной ценой. CopyOnWriteArrayList вместо этого создаёт новую копию списка каждый раз, когда выполняется модифицирующая операция, и гарантируется, что её итераторы возвращают состояние списка на момент, когда итератор был сконструирован и не выкинут ConcurrentModificationException. Нет необходимости клонировать список до перебора или блокировать его во время перебора, потому что копия списка, которую видит итератор, не будет изменяться. Другими словами, CopyOnWriteArrayList содержит изменяемую ссылку на неизменяемый массив, поэтому до тех пор, пока эта ссылка остаётся фиксированной, вы получаете все преимущества потокобезопасности от неизменности без необходимости блокировок.


Краткое изложение

Синхронизированные классы коллекций Hashtable и Vector и синхронизированные классы обрамления Collections.synchronizedMap и Collections.synchronizedList предоставляют базовую условно потокобезопасную реализацию Map и List. Однако несколько факторов делают их непригодными для использования в приложениях с высоким уровнем параллелизма - используемая в них единственная блокировка на всю коллекцию является препятствием для масштабируемости, а зачастую бывает необходимо блокировать коллекцию на значительное время в момент перебора для предотвращения исключений ConcurrentModificationException. Реализации ConcurrentHashMap и CopyOnWriteArrayList обеспечивают намного больший уровень параллелизма при сохранении безопасности потоков и при нескольких незначительных компромиссах в их обещаниях перед вызывающей стороной. ConcurrentHashMap и CopyOnWriteArrayList не обязательно полезны везде, где вы могли бы использовать HashMap или ArrayList, но они спроектированы для оптимизации в определённых распространённых ситуациях. Многие параллельные приложения будут в выигрыше от их использования.

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=197959
ArticleTitle=Теория и практика Java : Параллельные классы коллекций
publish-date=02262007