Java ConcurrentMap
 | Эта статья, возможно, содержит оригинальные исследования . ( декабрь 2017 г. ) |
языка программирования Java Java Collections Framework версии 1.5 и более поздних определяет и реализует исходные обычные однопоточные карты, а также
также новые потокобезопасные карты, реализующие java.util.concurrent.ConcurrentMap интерфейс среди других параллельных интерфейсов. [1]
В Java 1.6 java.util.NavigableMap был добавлен интерфейс, расширяющий java.util.SortedMap,
и java.util.concurrent.ConcurrentNavigableMap Интерфейс был добавлен как комбинация субинтерфейсов.
Интерфейсы карт Java [ править ]
Схема интерфейса карты версии 1.8 имеет вид, показанный ниже. Наборы можно рассматривать как подслучаи соответствующих карт, в которых значения всегда являются определенной константой, которую можно игнорировать, хотя API Set использует соответствующие методы, но с разными именами. Внизу находится java.util.concurrent.ConcurrentNavigableMap, что является множественным наследованием.
Реализации [ править ]
ConcurrentHashMap [ править ]
Для неупорядоченного доступа, как определено в java.util.Map интерфейс, java.util.concurrent.ConcurrentHashMap реализует java.util.concurrent.ConcurrentMap. [2] Механизм представляет собой хэш-доступ к хеш-таблице со списками записей, каждая запись содержит ключ, значение, хэш и следующую ссылку. До Java 8 существовало несколько блокировок, каждая из которых сериализовала доступ к «сегменту» таблицы. В Java 8 встроенная синхронизация используется в заголовках самих списков, и списки могут превращаться в небольшие деревья, когда они угрожают стать слишком большими из-за неудачных коллизий хешей. Кроме того, Java 8 оптимистично использует примитив сравнения и установки для размещения начальных головок в таблице, что очень быстро. Производительность равна O(n) , но иногда возникают задержки, когда требуется перефразирование. После расширения хеш-таблицы она никогда не сжимается, что может привести к «утечке» памяти после удаления записей.
ConcurrentSkipListMap [ править ]
Для упорядоченного доступа, как определено java.util.NavigableMap интерфейс, java.util.concurrent.ConcurrentSkipListMap был добавлен в Java 1.6, [1] и реализует java.util.concurrent.ConcurrentMap а также java.util.concurrent.ConcurrentNavigableMap. Это список пропуска , в котором для создания дерева используются методы блокировки. Производительность равна O(log(n)) .
Cтрие [ править ]
- Ctrie Дерево без блокировок на основе дерева.
Проблема одновременной модификации [ править ]
Одна проблема, решенная Java 1.5 java.util.concurrentпакет является пакетом параллельной модификации. Предоставляемые им классы коллекций могут надежно использоваться несколькими потоками.
Все непараллельные карты с общим потоком и другие коллекции должны использовать некоторую форму явной блокировки, такую как встроенная синхронизация, чтобы предотвратить одновременную модификацию, или же должен быть способ доказать с помощью логики программы, что одновременная модификация не может произойти. Параллельная модификация Map несколькими потоками иногда разрушает внутреннюю согласованность структур данных внутри Map, что приводит к ошибкам, которые проявляются редко или непредсказуемо и которые трудно обнаружить и исправить. Кроме того, одновременная модификация одним потоком с доступом для чтения другим потоком или потоками иногда дает непредсказуемые результаты для читателя, хотя внутренняя согласованность карты не будет нарушена. Использование внешней логики программы для предотвращения одновременной модификации увеличивает сложность кода и создает непредсказуемый риск ошибок в существующем и будущем коде, хотя и позволяет использовать непараллельные коллекции. Однако ни блокировки, ни программная логика не могут координировать внешние потоки, которые могут вступить в контакт с Collection.
Счетчики модификаций [ править ]
Чтобы помочь решить проблему одновременной модификации, непараллельный Map реализации и прочее Collections используют внутренние счетчики модификаций, к которым обращаются до и после чтения для отслеживания изменений: авторы увеличивают счетчики модификаций. Предполагается, что с помощью этого механизма будет обнаружена параллельная модификация, выдающая java.util.ConcurrentModificationException, [3] но это не гарантированно произойдет во всех случаях, и на него не следует полагаться. Счетное обслуживание также снижает производительность. По соображениям производительности счетчики не являются энергозависимыми, поэтому не гарантируется, что изменения в них будут распространяться между Threadс.
Collections.synchronizedMap() [ править ]
Одним из решений проблемы одновременной модификации является использование определенного класса-оболочки, предоставляемого фабрикой в java.util.Collections : public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) который оборачивает существующий непотокобезопасный Map с методами, которые синхронизируются с внутренним мьютексом. [4] Существуют также оболочки для других типов коллекций. Это частичное решение, поскольку все еще возможно, что лежащий в основе Map может быть случайно получен доступ Threads, которые сохраняют или получают развернутые ссылки. Кроме того, все коллекции реализуют java.lang.Iterable но карты с синхронизированной оболочкой и другие обернутые Collections не предоставляйте синхронизированные итераторы, поэтому синхронизация остается на усмотрение клиентского кода, который работает медленно и подвержен ошибкам, и невозможно ожидать дублирования другими потребителями синхронизированного кода. Map. Также необходимо защитить всю продолжительность итерации. Кроме того, Mapкоторый обернут дважды в разных местах, будет иметь разные внутренние объекты-мьютексы, с которыми работает синхронизация, что позволяет перекрываться. Делегирование снижает производительность, но современные JIT-компиляторы часто сильно встраиваются, что ограничивает снижение производительности. Вот как работает упаковка внутри оболочки: мьютекс — это всего лишь финал Object и m — финальная упаковка Map:
public V put ( K ключ , V значение ) {
синхронизировано ( мьютекс ) {
return m . поставить ( ключ , значение );
}
}
Синхронизацию итерации рекомендуется выполнять следующим образом: однако это синхронизируется с оболочкой, а не с внутренним мьютексом, что позволяет перекрываться: [5]
Map < String , String > обернутыйMap = Collections . синхронизированная карта ( карта );
...
Synchronized ( WrapMap ) {
for ( Final String s : WrappedMap . keySet ()) {
// возможно, какая-то длинная операция выполняется
// много раз, задерживая все остальные доступы
}
}
Встроенная синхронизация [ править ]
Любой Map может безопасно использоваться в многопоточной системе, гарантируя, что все обращения к ней обрабатываются механизмом синхронизации Java:
окончательная карта < String , String > карта = новый HashMap <> ();
...
// Поток A
// Используем саму карту в качестве блокировки. Вместо него можно использовать любой согласованный объект.
синхронизированный ( карта ) {
карта . put ( "ключ" , "значение" );
}
..
// Поток B
синхронизирован ( карта ) {
Строковый результат = карта . получить ( «ключ» );
...
}
...
// Поток C
синхронизирован ( карта ) {
for ( Final Entry < String , String > s : map . enterSet ()) {
/*
* Некоторые, возможно, медленные операции, задерживающие все другие предположительно быстрые операции.
* Синхронизация на отдельных итерациях невозможна.
*/
...
}
}
ReentrantReadWriteLock [ править ]
Код с использованием java.util.concurrent.ReentrantReadWriteLockаналогично встроенной синхронизации. Однако в целях безопасности блокировки следует использовать в блоке try/finally, чтобы обеспечить ранний выход, например java.lang.Exceptionбросок или перерыв/продолжение обязательно пройдет через разблокировку. Этот метод лучше, чем использование синхронизации [6] поскольку операции чтения могут перекрывать друг друга, возникает новая проблема при определении приоритета записи по отношению к чтению. Для простоты а java.util.concurrent.ReentrantLockвместо этого можно использовать, что не делает различия между чтением и записью. С блокировками возможно больше операций, чем при синхронизации, например tryLock() и tryLock(long timeout, TimeUnit unit).
окончательная ReentrantReadWriteLock блокировка = новый ReentrantReadWriteLock ();
окончательный ReadLock readLock = блокировка . читатьЛок ();
окончательный WriteLock writeLock = блокировка . записьБлокировка ();
..
// Поток A
try {
writeLock . замок ();
карта . put ( "ключ" , "значение" );
...
} наконец {
writeLock . разблокировать ();
}
...
// Поток B
try {
readLock . замок ();
конечная строка s = карта . получить ( «ключ» );
..
} наконец {
readLock . разблокировать ();
}
// Поток C
try {
readLock . замок ();
for ( Final Entry < String , String > s : map . enterSet ()) {
/*
* Некоторые, возможно, медленные операции, задерживающие все другие предположительно быстрые операции.
* Синхронизация на отдельных итерациях невозможна.
*/
...
}
} наконец {
readLock . разблокировать ();
}
Конвои [ править ]
Взаимное исключение имеет проблему сопровождения блокировок , при которой потоки могут накапливаться в блокировке, в результате чего JVM приходится поддерживать дорогостоящие очереди ожидающих и «припарковать» ожидание. Threadс. Парковать и распарковывать машину дорого. Threads, и может произойти медленное переключение контекста. Переключение контекста требует от микросекунд до миллисекунд, в то время как базовые операции карты обычно занимают наносекунды. Производительность может упасть до небольшой доли единичного Threadпропускная способность по мере увеличения конкуренции. Когда конкуренция за блокировку отсутствует или невелика, влияние на производительность незначительное; однако, за исключением проверки блокировки блокировки. Современные JVM встраивают большую часть кода блокировки, сокращая его до нескольких инструкций, обеспечивая очень быстрое отсутствие конфликтов. Реентерабельные методы, такие как встроенная синхронизация или java.util.concurrent.ReentrantReadWriteLockоднако имеют дополнительный багаж, снижающий производительность при поддержании глубины повторного входа, что также влияет на случай отсутствия конфликтов. Проблема Convoy вроде бы решается с помощью современных JVM, но ее можно скрыть за счет медленного переключения контекста: в этом случае задержка увеличится, но пропускная способность останется приемлемой. С сотнями Threads время переключения контекста 10 мс приводит к задержке в секундах.
Несколько ядер [ править ]
Решения на основе взаимного исключения не позволяют использовать всю вычислительную мощность многоядерной системы, поскольку только один Thread разрешено внутри Mapкод за раз. Реализации конкретных параллельных карт, предоставляемых Java Collections Framework и другими, иногда используют преимущества нескольких ядер с использованием без блокировок методов программирования . Методы без блокировок используют такие операции, как встроенный метод CompareAndSet(), доступный во многих классах Java, таких как AtomicReferenceатомарно выполнять условные обновления некоторых внутренних структур Map. Примитив CompareAndSet() дополнен в классах JCF собственным кодом, который может выполнять сравнениеAndSet для специальных внутренних частей некоторых объектов для некоторых алгоритмов (с использованием «небезопасного» доступа). Методы сложны и часто полагаются на правила межпоточного взаимодействия, обеспечиваемые изменчивыми переменными, отношением «происходит до», специальными типами «циклов повтора» без блокировок (которые не похожи на спин-блокировки, поскольку они всегда приводят к прогрессу). . Функция CompareAndSet() использует специальные инструкции, специфичные для процессора. Любой Java-код может использовать для других целей метод CompareAndSet() в различных параллельных классах для достижения параллельного выполнения без блокировки или даже без ожидания, что обеспечивает конечную задержку. Методы блокировки без блокировок просты во многих распространенных случаях и для некоторых простых коллекций, таких как стеки.
На схеме показано, как синхронизироваться с помощью Collections.synchronizedMap(java.util.Map)упаковка обычного HashMap (фиолетового цвета) может масштабироваться не так хорошо, как ConcurrentHashMap (красного цвета). Остальные — это упорядоченные ConcurrentNavigableMaps AirConcurrentMap (синий) и ConcurrentSkipListMap (зеленый CSLM). (Плоские пятна могут быть перефразированием, создающим таблицы, которые больше, чем Nursery, а ConcurrentHashMap занимает больше места. Обратите внимание, что на оси Y должно быть написано «ставит K». Система — 8-ядерный i7 2,5 ГГц с -Xms5000m для предотвращения GC). Расширение процессов GC и JVM значительно меняет кривые, а некоторые внутренние методы блокировки блокировок создают мусор при конкуренции.
Предсказуемая задержка [ править ]
Еще одна проблема с подходами взаимного исключения заключается в том, что предположение о полной атомарности, сделанное некоторым однопоточным кодом, создает спорадические неприемлемо длинные задержки между потоками в параллельной среде. В частности, итераторы и массовые операции, такие как putAll() и другие, могут занимать время, пропорциональное размеру карты, задерживая выполнение других операций. Threadкоторые ожидают предсказуемо низкой задержки для немассовых операций. Например, многопоточный веб-сервер не может допускать задержки некоторых ответов из-за длительных итераций других потоков, выполняющих другие запросы, которые ищут определенное значение. С этим связан тот факт, что Threadкоторые блокируют Map на самом деле нет никаких требований когда-либо снимать блокировку и бесконечный цикл у владельца Thread может распространять постоянную блокировку на другие Threadс. Медленный владелец Threads иногда может быть прервано. Карты на основе хеша также подвержены спонтанным задержкам во время перефразирования.
Слабая последовательность [ править ]
The java.util.concurrentРешение пакетов проблемы параллельной модификации, проблемы конвоя, проблемы предсказуемой задержки и проблемы многоядерности включает в себя архитектурный выбор, называемый слабой согласованностью. Этот выбор означает, что читается как get(java.lang.Object)не будет блокироваться, даже когда обновления выполняются, и допускается даже перекрытие обновлений друг с другом и с чтением. Слабая согласованность позволяет, например, содержимому ConcurrentMap измениться во время его итерации на один Thread. [7] Итераторы предназначены для использования одним Threadвовремя. Так, например, Map содержащие две взаимозависимые записи, могут быть восприняты читателем непоследовательно Thread во время модификации другим Thread. Обновление, которое должно атомарно изменить ключ записи ( k1,v ) на запись ( k2,v ), должно будет выполнить удаление ( k1 ), а затем put ( k2, v ), в то время как итерация может пропустить запись или увидеть ее в двух местах. При извлечении возвращается значение для данного ключа, которое отражает последнее завершенное обновление этого ключа. Таким образом, существует отношение «произошло до».
Нет никакого способа для ConcurrentMaps, чтобы заблокировать всю таблицу. Нет возможности ConcurrentModificationException как это происходит с непреднамеренной одновременной модификацией непараллельного Mapс. size() метод может занять много времени, в отличие от соответствующего непараллельного метода Maps и другие коллекции, которые обычно включают поле размера для быстрого доступа, поскольку им может потребоваться сканирование всей Mapкаким-то образом. Когда происходят одновременные изменения, результаты отражают состояние Map в какой-то момент, но не обязательно в одном непротиворечивом состоянии, следовательно size(), isEmpty() и containsValue(java.lang.Object) лучше всего использовать только для мониторинга.
Методы ConcurrentMap 1.5 [ править ]
Есть некоторые операции, предусмотренные ConcurrentMap которых нет в Map- который он расширяет - чтобы обеспечить атомарность модификаций. replace( K, v1, v2 ) проверит наличие v1 в записи, идентифицированной K , и только в случае обнаружения v1 заменяется на v2 атомарно. Новая замена( k,v ) выполнит put( k,v ) только в том случае, если k уже находится на карте. Кроме того, putIfAbsent( k,v ) выполнит put( k,v ) только в том случае, если k еще не находится в Mapи Remove(k, v) удалит запись для v, только если v присутствует. Эта атомарность может быть важна для некоторых случаев многопоточного использования, но не связана с ограничением слабой согласованности.
Для ConcurrentMaps, следующие атомарные.
m.putIfAbsent(k, v) является атомарным, но эквивалентным:
if ( k == null || v == null )
выдать новое исключение NullPointerException ();
если ( ! m . containsKey ( k )) {
return m . положить ( к , v );
} Еще {
вернуться м . получить ( к );
}
m.replace(k, v) является атомарным, но эквивалентным:
if ( k == null || v == null )
выдать новое исключение NullPointerException ();
если ( м . содержит ключ ( к )) {
вернуть м . положить ( к , v );
} Еще {
возвратить ноль ;
}
m.replace(k, v1, v2) является атомарным, но эквивалентным:
if ( k == null || v1 == null || v2 == null )
выдать новое исключение NullPointerException ();
if ( m . containsKey ( k ) && Objects . равно ( m . get ( k ), v1 )) {
m . положить ( к , v2 );
вернуть истину ;
} Еще
вернуть ложь ;
}
m.remove(k, v) является атомарным, но эквивалентным:
// если Map не поддерживает нулевые ключи или значения (по-видимому, независимо)
if ( k == null || v == null )
throw new NullPointerException ();
if ( m . containsKey ( k ) && Objects . равно ( m . get ( k ), v )) {
m . удалить ( к );
вернуть истину ;
} Еще
вернуть ложь ;
}
Методы ConcurrentMap 1.8 [ править ]
Потому что Map и ConcurrentMapявляются интерфейсами, к ним нельзя добавлять новые методы без нарушения реализации. Однако в Java 1.8 добавлена возможность реализации интерфейса по умолчанию, а также добавлена возможность Mapреализации интерфейса по умолчанию некоторых новых методов getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), ComputeIfAbsent(K, Function), ComputeIfPresent(K, BiFunction), Compute(K,BiFunction) и merge(K, V, Бифункция). Реализации по умолчанию в Map не гарантируют атомарность, но в ConcurrentMapпри переопределении значений по умолчанию они используют методы блокировки без блокировки для достижения атомарности, а существующие реализации ConcurrentMap автоматически будут атомарными. Методы блокировки могут быть медленнее, чем переопределения в конкретных классах, поэтому конкретные классы могут решить реализовать их атомарно или нет и документировать свойства параллелизма.
Безблокировочная атомарность [ править ]
С ConcurrentMaps можно использовать методы без блокировок, поскольку они включают методы с достаточно большим числом консенсуса, а именно с бесконечностью , что означает, что любое количество Threadы могут быть скоординированы. Этот пример можно реализовать с помощью функции merge() в Java 8, но он показывает общий шаблон блокировки, который является более общим. Этот пример относится не к внутреннему устройству ConcurrentMap, а к использованию ConcurrentMap в клиентском коде. Например, если мы хотим атомарно умножить значение в Map на константу C:
статический финал long C = 10 ;
voidatomicMultiply ConcurrentMap ( ( < Long , Long > map , Long key ) {
for ;;) {
Long oldValue = map . получить ( ключ );
// Предполагаем, что oldValue не равно нулю. Это операция «полезной нагрузки», и она не должна иметь побочных эффектов из-за возможного перерасчета в случае конфликта.
Long newValue = oldValue * C ;
если ( map . replace ( ключ , oldValue , newValue ))
перерыв ;
}
}
PutIfAbsent( k, v ) также полезен, когда запись для ключа может отсутствовать. Этот пример можно реализовать с помощью метода Compute() Java 8, но он показывает общий шаблон блокировки, который является более общим. Функция replace( k,v1,v2 ) не принимает нулевые параметры, поэтому иногда необходима их комбинация. Другими словами, если v1 putIfAbsent( k, v2 имеет значение null, то вызывается replace( k,v1,v2 ), в противном случае вызывается ).
voidatomicMultiplyNullable ConcurrentMap ( ( ;; < Long , Long > карта , длинный ключ ) {
for ) {
Long oldValue = map . получить ( ключ );
// Это операция «полезной нагрузки», и она не должна иметь побочных эффектов из-за возможного перерасчета в случае конфликта
Long newValue = oldValue == null ? INITIAL_VALUE : старое значение * C ;
if ( reneNullable ( map , key , oldValue , newValue ))
сломать ;
}
}
...
static boolean replaceNullable ( ConcurrentMap < Long , Long > map , Long key , Long v1 , Long v2 ) {
return v1 == null ? карта . putIfAbsent ( ключ , v2 ) == null : карта . заменить ( ключ , v1 , v2 );
}
История [ править ]
Платформа коллекций Java была спроектирована и разработана в первую очередь Джошуа Блохом и была представлена в JDK 1.2 . [8] Оригинальные классы параллелизма были созданы Дугом Ли . [9] пакет сбора.
См. также [ править ]
Цитаты [ править ]
- ^ Перейти обратно: а б Гетц и др. 2006 , стр. 84–85, §5.2 Параллельные коллекции.
- ^ Гетц и др. 2006 , стр. 85–86, §5.2.1 ConcurrentHashMap.
- ^ Гетц и др. 2006 , стр. 82–83, §5.1.2 Итераторы и исключение ConcurrentModificationException.
- ^ Гетц и др. 2006 , стр. 84–85, §5.2.1 ConcurrentHashMap.
- ^ "java.util.Collections.synchronizedMap" . Java/Java SE/11/API/java.base. Справочный центр Oracle . 19 сентября 2018 года . Проверено 17 июля 2020 г.
- ^ Гетц и др. 2006 , стр. 95–98, §13.5 Блокировки чтения и записи.
- ^ Гетц и др. 2006 , стр. 85–86, §5.21 ConcurrentHashMap.
- ^ Ванхельсуве, Лоуренс (1 января 1999 г.). «Битва контейнерных фреймворков: какую использовать?» . JavaWorld . Проверено 17 июля 2020 г.
- ^ Леа, Дуг . «Обзор пакета util.concurrent Release 1.3.4» . Проверено 1 января 2011 г.
Ссылки [ править ]
- Гетц, Брайан; Пайерлс, Тим; Блох, Джошуа; Боубир, Джозеф; Холмс, Дэвид; Леа, Дуг (2006). Параллелизм Java на практике . Эддисон Уэсли. ISBN 0-321-34960-1 . ОЛ 25208908М .
- Леа, Дуг (1999). Параллельное программирование на Java: принципы и шаблоны проектирования . Эддисон Уэсли. ISBN 0-201-31009-0 . ОЛ 55044М .
Внешние ссылки [ править ]
- Уроки коллекций
- Учебное пособие по коллекции Java 6 — Якоб Дженков, Кадафи Камфулуса
- Приручение тигра: структура коллекций
- «The Collections Framework» (документация Oracle Java SE 8)
- «Уроки Java — Коллекции», Джош Блох
- Какую коллекцию Java мне следует использовать? — Удобная блок-схема, упрощающая выбор коллекций.
- «Какую коллекцию Java использовать?» — Джанев Джордж