Теория и практика на Java Паралелни класове за събиране
ConcurrentHashMap и CopyOnWriteArrayList предлагат безопасност на нишката и подобрена мащабируемост
Серия съдържание:
Това съдържание е част # от поредица # статии: Теория и практика на Java
Това съдържание е част от поредицата: Теория и практика на Java
Очаквайте нови статии от тази серия.
Първият клас за асоциативна колекция, който се появи в библиотеката с класове на Java, беше Hashtable, който беше част от JDK 1.0. Hashtable предостави лесна за използване, безопасна за нишки реализация на асоциативна карта и, разбира се, беше удобна. Безопасността на нишката обаче си струваше цената - всички методи в Hashtable бяха синхронизирани. По това време синхронизацията без конкуренция трябваше да се плаща с производителност. Наследникът на Hashtable, HashMap, който се появи като част от рамката на Collections в JDK 1.2, реши проблема с безопасността на нишките, като предостави несинхронизиран базов клас и синхронизирана обвивка, Collections.synchronizedMap. Разделянето на основната функционалност и безопасността на нишките в Collections.synchronizedMap направи възможно синхронизирането на потребителите, които се нуждаеха от нея, а тези, които не се нуждаеха от нея, не трябваше да плащат цената за това.
Опростеният подход за синхронизиране, използван както от Hashtable, така и от synchronizedMap - синхронизиране на всеки метод с Hashtable или синхронизиран обект за обвиване на Map - има два основни недостатъка. Това е пречка за скалируемостта, тъй като само една нишка може да има достъп до хеш-таблицата в даден момент. В същото време истинската безопасност на нишката не е достатъчна и много общи комбинирани операции все още изискват допълнителна синхронизация. Макар чепрости операции като get() и put() могат да се извършват безопасно без допълнителна синхронизация, има няколко общи последователности от операции като итерация или put-if-absent, които все още се нуждаят от външна синхронизация, за да се избегне конкуренция за данни.
Условна безопасност на резбата
Синхронизираните рамки за събиране synchronizedMap и synchronizedList понякога се наричат условно безопасни за нишки - всички операции поотделно са безопасни за нишки, но поредици от операции, при които контролният поток зависи от резултатите от предишни операции, могат да причинят конкуренция за данни. Първият пасаж в листинг 1 демонстрира общия идиом put-if-absent - ако елементът все още не съществува в таблицата Map, добавете го. За съжаление, както вече беше споменато, е възможно друга нишка да вмъкне стойност с дублиран ключ между момента, в който методът containsKey() се връща и методът put() се извиква. Ако искате да сте сигурни, че вмъкването се случва точно веднъж, трябва да оградите двойката изрази в синхронизиран блок, който е синхронизиран с Map m.
Други примери в листинг 1 включват повторение. В първия пример резултатите от List.size() може да са станали невалидни по време на цикъла, защото друга нишка може да е премахнала елементи от списъка. Ако ситуацията не е успешна и елементът е премахнат от друга нишка веднага след последната итерация на цикъла, тогава List.get() ще върне null и doSomething() най-вероятно ще хвърли NullPointerException. Какво можете да направите, за да избегнете това? Ако друга нишка може да има достъп до списъка, докато итерирате върху него, трябва да заключите целия списък за времетраенето на итерацията, като го затворите в блоксинхронизирано, синхронизиране със списък l. Това решава проблемите с конкуренцията за данни, но ще повлияе на паралелността по-късно, тъй като заключването на целия списък по време на повторение може да блокира достъпа на други нишки до списъка за дълго време.
Рамката на колекциите въвежда итератори за преминаване през списък или друга колекция, които рационализират процеса на итериране на елементите на колекция. Въпреки това, итераторите, внедрени в класовете на колекцията java.util, често са склонни към сривове, което означава, че ако една нишка модифицира колекция, докато друга я предава през Iterator, следващото извикване на Iterator.hasNext() или Iterator.next() ще хвърли ConcurrentModificationException. Както в предишния пример, ако искате да предотвратите ConcurrentModificationException, трябва да блокирате целия списък, докато итерирате, като го обвиете в синхронизиран блок, който се синхронизира със List l. (Алтернативно, можете да извикате List.toArray() и да обхождате масива без синхронизация, но това може да бъде скъпо, ако списъкът е достатъчно голям.)
Списък 1. Типичен случай на спор в синхронизирани карти
Фалшиво чувство на увереност
Безопасността на условната нишка, осигурена от synchronizedList и synchronizedMap, представлява скрита заплаха - разработчиците приемат, че тъй като тези колекции са синхронизирани, те са напълно безопасни за нишка и пренебрегват правилното синхронизиране на съставните операции. В резултат на това, въпреки че тези програми работят при леко натоварване, при голямо натоварване те могат да започнат да хвърлят NullPointerException или ConcurrentModificationException.
Проблеми с мащабируемостта
Мащабируемостта се отнася до начина, по който пропускателната способност на дадено приложение варираувеличаване на натоварването и наличните изчислителни ресурси. Една мащабируема програма може да се справи с пропорционално по-голямо натоварване с повече процесори, памет или I/O честотна лента. Заключването на споделен ресурс за ексклузивен достъп е проблем с мащабируемостта - то не позволява на други нишки да имат достъп до този ресурс, дори ако има неактивни процесори за планиране на тези нишки. За да постигнем мащабируемост, трябва да премахнем или намалим зависимостта си от ексклузивни блокировки на ресурси.
Още по-голям проблем със синхронизираното рамкиране на колекция и ранните класове Hashtable и Vector е, че те се синхронизират с едно заключване. Това означава, че само една нишка може да има достъп до колекцията в даден момент и ако една нишка е в процес на четене на таблицата Map, всички останали нишки, които искат да четат от нея или да пишат в нея, трябва да изчакат. Най-често срещаните операции с таблица Map, get() и put() , могат да бъдат по-интензивни от изчислителна гледна точка, отколкото си мислите - преминаването през хеш група в търсене на конкретна стойност на ключ get() може да изисква извикване на Object.equals() на голям брой кандидати. Ако функцията hashCode(), използвана от ключовия клас, не разпределя равномерно стойностите в хеш серията или има голям брой хеш сблъсъци, отделните кофички вериги може да са много по-дълги от другите, а преминаването през дълга хеш верига и извикването на equals() на определен процент от нейните елементи може да е твърде бавно. Проблемът с високата цена на get() и put() при тези условия е не само, че достъпът ще бъде бавен, но и че всички други нишки ще бъдат блокирани за достъпКартирайте таблицата, докато тази верига от хешове се обхожда.
Фактът, че изпълнението на get() може да отнеме значително време за изпълнение в някои случаи, се влошава от проблема с условната безопасност на нишките, обсъден по-горе. Условията на конкуренция, илюстрирани в листинг 1, често налагат едно заключване на събиране да бъде задържано много по-дълго, отколкото е необходимо за извършване на една операция. Ако ще задържите заключването на колекцията за времетраенето на итерацията, тогава други нишки може да блокират, чакайки заключването на колекцията за дълго време.
Пример: Обикновен кеш
Една от най-честите употреби на Map в сървърни приложения е като внедряване на кеш. Сървърните приложения могат да кешират файлово съдържание, генерирани страници, резултати от заявки към бази данни, DOM дървета, свързани с анализирани XML файлове, и много други типове данни. Основната цел на кеш паметта е да намали времето за поддръжка и да увеличи пропускателната способност чрез използване на резултатите от предишното изчисление. Типична характеристика на натоварването на кеша е, че попаденията са много по-чести от актуализациите, така че (в идеалния случай) кешът осигурява много добра производителност за get(). Кешът, който забавя производителността на приложението, е дори по-лошо от липсата на кеш.
Ако използвате synchronizedMap за внедряване на кеша, въвеждате потенциален проблем с мащабируемостта във вашето приложение. Само една нишка може да има достъп до карта в даден момент и това се отнася за всички нишки, които могат да извлекат стойност от таблица на карта, както и нишки, които желаят да вмъкнат нова двойка (ключ, стойност) в таблица на карта.
Намаляване на размерите на ключалката
Един подход за подобряване на паралелността на HashMap, като същевременно се поддържа безопасността на нишката, е да се заобиколи едно заключване на цялата таблица и да се използват брави за кофа с хешове (или, по-общо, група от брави, където всяко заключване защитава множество кофи). Това означава, че множество нишки имат достъп до различни части на картата едновременно, без конкуренция за едно заключване на цялата колекция. Този подход незабавно подобрява скалируемостта на операциите за вмъкване, извличане и изтриване. За съжаление, тази паралелност има цена - става по-трудно да се внедрят методи, които работят с цяла колекция, като size() или isEmpty(), защото това може да изисква получаване на много заключвания наведнъж или рискува връщането на неточен резултат. Въпреки това, за ситуации като внедряване на кеш, това представлява разумен компромис - операциите за извличане и вмъкване са чести, докато операциите size() и isEmpty() са много по-рядко срещани.
ConcurrentHashMap
Класът ConcurrentHashMap от util.concurrent (който също ще се появи в пакета java.util.concurrent в JDK 1.5) е безопасна за нишки имплементация на Map, която осигурява много по-висока степен на едновременност от synchronizedMap. Много четения наведнъж могат почти винаги да се изпълняват паралелно, едновременното четене и запис обикновено могат да се изпълняват паралелно, а множеството едновременни записи често могат да се изпълняват паралелно. (Съответният клас ConcurrentReaderHashMap предлага подобна едновременност за множество четения, но позволява само едно активно записване.) ConcurrentHashMap е проектиран да оптимизира операциите за извличане; всъщност успешни операцииget() обикновено успява без никакво блокиране. Постигането на безопасност на нишката без заключване е сложно и изисква задълбочено разбиране на детайлите на модела на паметта на Java. Внедряването на 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
| 1 | 1,00 | 1.03 |
| 2 | 2.59 | 32.40 |
| 4 | 5.58 | 78.23 |
| 8 | 13.21 | 163,48 |
| 16 | 27.58 | 341.21 |
| 32 | 57.27 | 778.41 |
CopyOnWriteArrayList
Класът CopyOnWriteArrayList е предназначен да замени ArrayList в едновременни приложения, където преминаванията далеч надхвърлят вмъкванията и изтриванията. Това е доста типично за случая, когато ArrayListизползвани за съхраняване на списък с абонати, както в AWT или Swing приложения, или в класовете на JavaBean като цяло. (Подобен CopyOnWriteArraySet използва CopyOnWriteArrayList за внедряване на интерфейса Set.)