Когда HashMap начинает убивать продакшн: инженерная история ConcurrentHashMap

Представьте обычный продакшн-сервис.

• 32 CPU
• сотни потоков
• кэш конфигурации / сессий / rate limits
• десятки тысяч операций в секунду

И где-то внутри — обычный Map.

Сначала всё выглядит безобидно.

Map<String, Session> sessions = new HashMap<>();

Потом появляется пара потоков.

Потом десятки.

Потом начинается продакшн-нагрузка.

И внезапно:

• latency скачет
• CPU уходит в 100%
• появляются странные зависания
• иногда — бесконечные циклы в HashMap

Это не гипотеза. Это реальные production-инциденты, которые происходили в крупных Java системах до появления правильных concurrent-структур.

Именно из таких историй и родился ConcurrentHashMap.

Но чтобы понять почему он устроен именно так, нужно пройти весь путь эволюции:

HashMap
   ↓
synchronized Map
   ↓
Segmented ConcurrentHashMap (JDK7)
   ↓
CAS + bin locking (JDK8)
   ↓
tree bins + lock striping + resize migration

И это одна из самых красивых инженерных эволюций в JVM.

Tree bins — это механизм в HashMap и ConcurrentHashMap (начиная с Java 8), при котором bucket с большим количеством коллизий автоматически преобразуется из связного списка (linked list) в сбалансированное красно-чёрное дерево (Red-Black Tree). Это предотвращает деградацию производительности при большом числе элементов с одинаковым hash: вместо линейной сложности O(n) операции поиска, вставки и удаления выполняются за O(log n). Такое преобразование происходит, когда число элементов в одном bucket превышает заданный порог (обычно 8), и служит защитой как от плохих hashCode, так и от потенциальных hash collision атак.

---

Первая наивная идея: просто synchronized

Самая очевидная защита HashMap:

Map<K, V> map = Collections.synchronizedMap(new HashMap<>());

Или:

public synchronized V get(K key)
public synchronized V put(K key, V value)

Это работает.

Но ровно до того момента, пока появляется настоящий concurrency.

Что происходит под нагрузкой

32 threads
200k ops/sec

Каждый вызов:

lock(map)
   → read/write
unlock(map)

Получаем глобальный lock.

Схема

Thread1 ─┐
Thread2 ─┤
Thread3 ─┤
Thread4 ─┤ → LOCK(map) → операция → unlock
Thread5 ─┤
Thread6 ─┘

Все потоки выстраиваются в очередь.

Даже get() блокирует все остальные get().

Это фундаментальная проблема.

---

Вторая попытка: lock striping

Инженеры Java решили:

"А что если разделить map на несколько независимых частей?"

Так появился ConcurrentHashMap JDK7.

Сегменты

ConcurrentHashMap
 ├─ Segment 0
 ├─ Segment 1
 ├─ Segment 2
 └─ Segment 3

Каждый сегмент — отдельная mini HashMap со своим lock.

segment = hash(key) % segments

Теперь:

Thread1 → Segment1 → lock
Thread2 → Segment2 → lock
Thread3 → Segment3 → lock

И они не мешают друг другу.

Код операции

Segment<K,V> s = segments[(hash >>> segmentShift) & segmentMask];
s.lock();

try {
    s.put(key, value);
} finally {
    s.unlock();
}

Улучшение производительности

Но появились новые проблемы.

---

Проблема №1 — фиксированная параллельность

Количество сегментов фиксировано.

16 segments

Но сервер:

64 threads

В итоге снова:

Thread1 → Segment3
Thread2 → Segment3
Thread3 → Segment3

Контеншн возвращается.

---

Проблема №2 — resize

Resize — самая сложная часть любой hash map.

capacity = capacity * 2

В segmented модели:

resize → lock entire segment

Это дорого.

---

Проблема №3 — memory overhead

Каждый Segment содержит:

ReentrantLock
table
metadata

На больших картах это превращается в memory waste.

Инженеры JVM решили:

Нам нужна структура без сегментов.

Так родился ConcurrentHashMap JDK8.

---

Архитектура ConcurrentHashMap (JDK8)

Node<K,V>[] table

Каждый bucket управляется отдельно.

table
 ├─ bin0
 ├─ bin1
 ├─ bin2
 ├─ bin3

Главная идея

---

End-to-End операция put

map.put("user42", session);

Шаг 1 — hash

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

Это защищает от плохих hashCode.

Шаг 2 — index

index = (n - 1) & hash

Bit mask быстрее modulo.

Шаг 3 — CAS insertion

if (casTabAt(tab, i, null,
      new Node<>(hash, key, value)))
      break;

CAS = Compare And Swap.

if (table[i] == null)
    table[i] = node

Но атомарно на уровне CPU.

CAS выполняется через Unsafe.compareAndSwapObject и мапится на CPU instruction cmpxchg.

Почему это важно

CAS избегает lock.

Thread1 → CAS success
Thread2 → CAS fail → retry

Нет kernel switch.

---

Когда CAS не помогает

Если bucket не пустой:

bin0 → node → node → node

Используется локальный lock:

synchronized (f) {
    // modify chain
}

Lock только для одного bucket.

---

Когда bucket превращается в дерево

Если:

bucket size > 8

List превращается в Red-Black Tree.

O(log n)

Схема

before

bucket
  ↓
  N → N → N → N → N


after

        N
      /   \
     N     N
    / \   / \

---

Resize — самая сложная часть

ConcurrentHashMap делает resize без глобальной остановки.

Кооперативная миграция

old table
 ├─ bin0
 ├─ bin1
 ├─ bin2
 └─ bin3

Thread1 → bin0
Thread2 → bin1
Thread3 → bin2
Thread4 → bin3

Потоки помогают переносить buckets.

ForwardingNode

ForwardingNode

Это сигнал:

"этот bucket уже переехал"

---

Java Memory Model

volatile Node<K,V>[] table;

Это обеспечивает visibility между потоками.

put → happens-before → get

---

CPU Cache Effects

CAS вызывает:

invalidate cache line

Если много потоков бьют в один bucket:

cache ping-pong

Производительность падает.

---

Влияние на GC

Node
 key
 value
 next

Миллионы Node → нагрузка на GC scanning.

---

Реальный production кейс

Map<IP, Counter>

нагрузка:

150k req/sec

Замена:

synchronized HashMap
↓
ConcurrentHashMap

---

Главные trade-offs

---

Самая важная инженерная идея

ConcurrentHashMap — это комбинация трёх стратегий:

optimistic (CAS)
pessimistic (locks)
structural (tree bins)

Каждая используется только когда нужна.

---

Инженерная интуиция

Если:

high concurrency
frequent reads
rare writes

ConcurrentHashMap идеален.

Но если:

writes dominate

CAS может превратиться в retry storm.

---