В Java с незапямятных времён есть замечательный интерфейс Map и его имплементации, в частности, HashMap. А начиная с Java 5 есть ещё и ConcurrentHashMap. Рассмотрим эти две реализации, их эволюцию и то, к чему эта эволюция может привести невнимательных разработчиков.
Warning: в статье использованы цитаты исходного кода OpenJDK 8, распространяемого под лицензией GNU General Public License version 2.
Времена до Java 8
Те, кто застал времена долгого-долгого ожидания сначала Java 7, а потом и Java 8 (не то что сейчас, каждые полгода новая версия), помнят, какие операции с Map были самыми востребованными. Это:
Если нужно положить значение в коллекцию, используем первый метод, а для получения имеющегося значения — второй.
Но что делать, если требуется «ленивая» инициализация? Тогда появлялся код такого вида:
String getOrPut(String key) {
String result = map.get(key); //(1)
if (result == null) { //(2)
result = createValue(key); //(3)
map.put(key, result); //(4)
}
return result;
}
- получаем значение по ключу
- проверяем, найдено ли искомое значение
- если значения не обнаружено, то создаём его
- добавляем значение в коллекцию по ключу
Немного громоздко получается, не находите? Причём в случае, когда используется простой HashMap, то это просто код, который неудобно читать, т.к. он немногопоточен. Зато в случае с ConcurrentHashMap всплывает дополнительная особенность: метод createValue (2) может быть вызван несколько раз, если несколько потоков успеют проверить условие (1) до того, как один из них запишет значение в коллекцию (3). Такое поведение зачастую может привести к нежелательным последствиям.
До прихода Java 8 элегантных вариантов просто не было. Если требовалось увернуться от нескольких созданий значений, то приходилось использовать дополнительные блокировки.
С Java 8 всё стало проще. Казалось бы…
Java 8 к нам приходит…
Какая самая долгожданная фича пришла к нам с Java 8? Правильно, лямды. И не просто лямды, а их поддержка во всём разнообразии API стандартной библиотеки. Не обошли вниманием и структуры данных Map. В частности, там появились такие методы, как:
За счёт этих методов можно переписать приведённый ранее код гораздо проще:
String getOrPut(String key) {
return map.computeIfAbsent(key, this::createValue);
}
Понятно, что никто не откажется от возможности упростить свой код. Более того, в случае с ConcurrentHashMap метод computeIfAbsent ещё и выполняется атомарно. Т.е. createValue будет вызвано ровно один раз и только в том случае, если искомое значение будет отсутствовать.
IDE тоже не прошли мимо. Так IntelliJ IDEA предлагает автозамену старого варианта на новый:
Понятно, что и упрощение кода и подсказки от IDE стимулируют разработчиков использовать этот новый API. Как следствие тот же computeIfAbsent начал появляться в очень многих местах кода.
Пока…
Внезапно!
Пока не настала пора очередного нагрузочного тестирования. И тут обнаружилось страшное:
Приложение работало на следующей версии Java:
openjdk version "1.8.0_222" OpenJDK Runtime Environment (build 1.8.0_222-8u222-b10-1ubuntu1~18.04.1-b10) OpenJDK 64-Bit Server VM (build 25.222-b10, mixed mode)
Для тех, кто не знаком с таким замечательным инструментом, как YourKit.
На скриншоте горизонтальными широкими линиями отображается работа потоков приложения во времени. В зависимости от состояния потока в конкретный момент времени полоса раскрашивается в соответствующий цвет:
- жёлтый — поток бездействует, ожидая работы;
- зелёный — поток работает, выполняя програмный код;
- красный — данный поток заблокирован другим потоком.
То есть получается, что практически все потоки (а их на самом деле было гораздо больше, чем отображено на скриншоте) почти всё время находятся в заблокированном состоянии. И у всех блокировка находится в том самом computeIfAbsent у ConcurrentHashMap! И это при том, что в связи со спецификой данного конкретного нагрузочного теста в этой коллекции может храниться не более 6-8 значений. Т.е. практически все операции в данном месте — исключительно чтение уже имеющихся значений.
Но постойте, как так? Ведь даже в документации к методу про блокировки говорится только в приложении к обновлению:
«If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.»
На деле же получается всё не совсем так. Если заглянуть в исходный код этого метода, то получается, что он содержит два весьма толстых синхронизирующих блока:
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
if (key == null || mappingFunction == null)
throw new NullPointerException();
int h = spread(key.hashCode());
V val = null;
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
Node<K,V> r = new ReservationNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) {
binCount = 1;
Node<K,V> node = null;
try {
if ((val = mappingFunction.apply(key)) != null)
node = new Node<K,V>(h, key, val, null);
} finally {
setTabAt(tab, i, node);
}
}
}
if (binCount != 0)
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
boolean added = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek; V ev;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
val = e.val;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
if ((val = mappingFunction.apply(key)) != null) {
added = true;
pred.next = new Node<K,V>(h, key, val, null);
}
break;
}
}
}
else if (f instanceof TreeBin) {
binCount = 2;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(h, key, null)) != null)
val = p.val;
else if ((val = mappingFunction.apply(key)) != null) {
added = true;
t.putTreeVal(h, key, val);
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (!added)
return val;
break;
}
}
}
if (val != null)
addCount(1L, binCount);
return val;
}
Из приведённого примера видно, что результат может быть сформирован только в шести точках, и почти все эти места находятся внутри синхронизирующих блоков. Весьма неожиданно. Тем более, что простой get вообще не содержит синхронизации:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Так что же делать? По сути, есть только два варианта: или возвращаться к первоначальному коду, или использовать его же, но в чуть модифицированном варианте:
String getOrPut(String key) {
String result = map.get(key);
return (result != null) ? result : map.computeIfAbsent(key, this::createValue);
}
Заключение
Вообще такие фатальные последствия от, казалось бы, банального рефакторинга оказались весьма неожиданными. Ситуацию спасло только наличие нагрузочного теста, который удачно выявил деградацию.
К счастью в более новых версиях Java эту проблему поправили: JDK-8161372.
Так что будьте бдительны, не доверяйте заманчивым подсказкам и пишите тесты. Особенно нагрузочные.
Всем Java!
UPD1: как правильно заметили coldwind, проблема известна: JDK-8161372. И, вроде как, исправлялась для Java 9. Но при этом на момент публикации статьи и в Java 8, и в Java 11, и даже в Java 13 этот метод остался без изменений.
UPD2: vkovalchuk подловил меня на невнимательности. Действительно для Java 9 и более новых проблема исправлена добавлением ещё одного условия с возвращением результата без блокировки:
else if (fh == h // check first node without acquiring lock
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
Изначально я напаролся на ситуацию в следующей версии Java:
openjdk version "1.8.0_222" OpenJDK Runtime Environment (build 1.8.0_222-8u222-b10-1ubuntu1~18.04.1-b10) OpenJDK 64-Bit Server VM (build 25.222-b10, mixed mode)
А когда смотрел на исходники более поздних версий, то честно проморгал эти строки, что ввело меня в заблуждение.
Так что ради справедливости подправил основной текст статьи.
Комментарии (20)
coldwind
12.12.2019 16:37+2Поиск в гугле выдаёт информацию о данной проблеме JDK-8161372 и она должна была быть исправлена в Java 9. Какую версию вы использовали для тестирования?
vektory79 Автор
12.12.2019 16:42Как ни странно, исходники реализации брал из OpenJDK 11.
coldwind
12.12.2019 16:59А что там у вас, в файле
ConcurrentHashMap.javaна строке 1674? В исходниках там комментарий.
Ну и хотелось бы точную версию Java, например:
$ java -version openjdk version "11.0.4" 2019-07-16 OpenJDK Runtime Environment (build 11.0.4+11-post-Ubuntu-1ubuntu219.04) OpenJDK 64-Bit Server VM (build 11.0.4+11-post-Ubuntu-1ubuntu219.04, mixed mode, sharing)vektory79 Автор
12.12.2019 17:06and must not attempt to update any other mappings of this map.
Но другой маппинг и не модифицируется. Более того, после некоторого прогрева там начинается только чтение без модификаций. Но при этом картина в профиле не меняется к лучшему.
Более того чуть выше:
Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple
Т.е. контекст указанной вами строки относится именно к ситуации, когда требуется вычисление лямды с новым результатом, а не чтение. Блокировка на чтение контр интуитивна в данном случае.
coldwind
12.12.2019 17:13Я не на конкретное предложение в комментарии указываю, а на строку 1674 в файле ConcurrentHashMap.java. У вас на скриншоте именно на этой строке происходит блокировка, приведён код метода, но без нумерации строк. А в исходниках, которые есть в интернете, на этой строке нет исполняемой инструкции.
Я лишь указываю на то, что было бы не плохо предоставить чуть больше информации о причине блокировки. Например, указать, что блокировка осуществляется на конкретной строке.vektory79 Автор
12.12.2019 17:23Понял. Согласен. На скриншоте как раз профиль того момента, когда я обнаружил проблему. Т.е. на Java 8.
В дальнейшем начал копать и понял, что в Java 11 ситуация не изменилась, хотя строки и сдвинулись.
kdmitrii
12.12.2019 23:04Мне непонятно каким образом операция get не использует блокировок. Это выглядит очень странно. Может кто-нибудь привести пример как такое возможно реализовать в хеш таблице?
vektory79 Автор
13.12.2019 11:35+1Хороший вопрос, достойный отдельной статьи.
Всё строится на так называемых неблокирующих алгоритмах, основывающихся на том факте, что Java даёт определённые гарантии по работе с памятью. Особенно с общей памятью в многопоточной обработке.
Если приводить максимально простой пример, то, например, можно вместо честной блокировки завести флаг в виде AtomicBoolean и перед входом в критическую секцию делать магию:
private static AtomicBoolean guard = new AtomicBoolean(false); public void doSometing() { if (guard.compareAndSet(false, true)) { try { // It's safe now. We can change the state. } finally { guard.set(false); } } else { // Do something non-destructive. } }
Это намного дешевле, чем честная блокировка и во многих применения этого достаточно. Даже в штатной библиотеке JRE эти подходы используются очень широко.
kdmitrii
13.12.2019 15:12Спасибо, я понял. Мне показалось, что там нет синхронизацией вообще. Так-то понятно, что на касах можно при желании реализовать.
BugM
13.12.2019 01:19У вас что-то с кодом вашего приложения не то. Вы бы привели кусочек своего кода.
computeIfAbsent лочит только при создании ноды. И массовые локи могут быть в сценарии когда вы массово создаете ноды и удаляете по одним и тем же ключам (с точностью до коллизий хеша). Не надо так код писать. Хеш функцию поправьте или просто сценарий работы переосмыслите.
computeIfAbsent при получении значения не лочит ничего. Ей можно смело пользоваться и не городить велосипед.vektory79 Автор
13.12.2019 12:10Я тоже так думал.
Вот давайте ещё раз заглянем под спойлер с реализацией метода ConcurrentHashMap.computeIfAbsent. результат возвращается из переменной val. Где происходит присвоение в эту переменную? В 6-и местах. Я их там даже специально пометил. Хоть пометки и не очень заметными вышли, т.к. код очень разлапистый. Первое присвоение не под блокировкой. Но там просто присваивается null. А вот все остальные места — под блоками synchronized. Т.е. нет ни одного пути выполнения, который не попадал бы на блокировку. Ну кроме случая с пустой коллекцией.
Более того. Данные в нашем случае из этой коллекции вообще не удаляются. Никогда. И там используется сравнительно небольшое количество ключей. И именно это сыграло дурную шутку, т.к. в случае большого количества ключей блокировки бы размазывались по разным объектам нод и там неполучалось бы такого контеншена.
vkovalchuk
13.12.2019 14:32все остальные места — под блоками synchronized
Есть ещё «return fv;» в вашей версии кода вне синхронизации.
Но в сорцах 1.8.0_122 (у меня под рукой) такой строчки нет. Если пишете статью про реализацию, то будьте добры указать ТОЧНУЮ версию с ПРОИЗВОДИТЕЛЕМ. Просто «1.8.0_222» это что — Оракл, IBM J9, OpenJDK, GNU, азуль, алибаба? На чём меряли? откуда код? Почему разные?
BugM
13.12.2019 22:49java -version
openjdk version «11.0.1» 2018-10-16
OpenJDK Runtime Environment 18.9 (build 11.0.1+13)
OpenJDK 64-Bit Server VM 18.9 (build 11.0.1+13, mixed mode)
Открываем исходники
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { if (key == null || mappingFunction == null) throw new NullPointerException(); int h = spread(key.hashCode()); V val = null; int binCount = 0; for (Node<K,V>[] tab = table;;) { //1 Node<K,V> f; int n, i, fh; K fk; V fv; //2 if (tab == null || (n = tab.length) == 0) //3 tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { //4 Node<K,V> r = new ReservationNode<K,V>(); synchronized (r) { if (casTabAt(tab, i, null, r)) { binCount = 1; Node<K,V> node = null; try { if ((val = mappingFunction.apply(key)) != null) node = new Node<K,V>(h, key, val); } finally { setTabAt(tab, i, node); } } } if (binCount != 0) break; } else if ((fh = f.hash) == MOVED) //5 tab = helpTransfer(tab, f); else if (fh == h // check first node without acquiring lock //6 && ((fk = f.key) == key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; //7 else { boolean added = false; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { val = e.val; break; } Node<K,V> pred = e; if ((e = e.next) == null) { if ((val = mappingFunction.apply(key)) != null) { if (pred.next != null) throw new IllegalStateException("Recursive update"); added = true; pred.next = new Node<K,V>(h, key, val); } break; } } } else if (f instanceof TreeBin) { binCount = 2; TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> r, p; if ((r = t.root) != null && (p = r.findTreeNode(h, key, null)) != null) val = p.val; else if ((val = mappingFunction.apply(key)) != null) { added = true; t.putTreeVal(h, key, val); } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (!added) return val; break; } } } if (val != null) addCount(1L, binCount); return val; }
Запускаем простенький пример.
ConcurrentHashMap<Integer, Integer> f = new ConcurrentHashMap<>(); f.put(1,1); f.computeIfAbsent(1, p->10);
И видим что выполнение пойдет по строкам которые я прокомментировал 1-2-3-4-5-6-7.
Ни одного synchronized блока не затронуто. Как и ожидалось.
Жду вашего примера.vektory79 Автор
14.12.2019 00:15Да-да. Благодаря vkovalchuk уже разобрались. И даже UPD2 уже написан по этому поводу.
Так что актуальность статьи остаётся только для Java 8 и тех страдальцев, кто пока не может с неё спрыгнуть.
rolaman
Хорошая статья, есть ли либы по эффективной имплементации map?
vektory79 Автор
Так-то есть, но любая имплементация — компромисс. Да и ConcurrentHashMap в целом очень хороша. Сделать многопоточную реализацию лучше весьма проблематично. За вот таким вот исключением...