Эвакуация данных в мапах Golang

Эвакуация данных (evacuation) в мапах Go — это процесс перераспределения элементов мапы при её расширении (rehashing). Этот механизм позволяет мапе динамически увеличивать количество бакетов и поддерживать высокую производительность операций (вставка, поиск, удаление).

---

1. Зачем нужна эвакуация данных?

• Когда мапа заполняется, количество коллизий (элементов, попадающих в один бакет) увеличивается, что ухудшает производительность.
• Чтобы избежать этого, Go увеличивает количество бакетов и эвакуирует (перемещает) элементы из старых бакетов в новые.

---

2. Как происходит эвакуация данных?

a) Инициализация расширения:

• Когда коэффициент заполнения мапы (отношение количества элементов к количеству бакетов) превышает пороговое значение, Go инициирует расширение.
• Количество бакетов увеличивается в 2 раза (например, с 8 до 16).

b) Создание новых бакетов:

• Go выделяет память для новых бакетов.
• Старые бакеты помечаются как «подлежащие эвакуации».

c) Перераспределение элементов:

• Go начинает процесс эвакуации:
  1. Каждый элемент из старых бакетов перехэшируется.
  2. На основе нового хэша элемент перемещается в один из новых бакетов.
• Этот процесс выполняется постепенно, чтобы минимизировать задержки.

d) Завершение эвакуации:

• Когда все элементы перемещены, старые бакеты освобождаются.
• Мапа начинает использовать новые бакеты.

---

3. Пример процесса эвакуации

Предположим, у нас есть мапа с 8 бакетами, и каждый бакет может хранить до 8 элементов.

1. Начальное состояние:
   • Количество бакетов: 8.
   • Элементы равномерно распределены по бакетам.
2. Добавление элементов:
   • По мере добавления элементов бакеты начинают заполняться.
   • Если в одном бакете оказывается слишком много элементов (например, из-за коллизий), производительность ухудшается.
3. Расширение:
   • Когда коэффициент заполнения превышает порог, Go увеличивает количество бакетов до 16.
   • Начинается процесс эвакуации.
4. Эвакуация:
   • Элементы из старых бакетов перехэшируются и перемещаются в новые бакеты.
   • Этот процесс выполняется постепенно, чтобы минимизировать задержки.
5. После эвакуации:
   • Количество бакетов: 16.
   • Элементы снова равномерно распределены, и производительность восстанавливается.

---

4. Особенности эвакуации в Go

a) Постепенная эвакуация:

• Go не перемещает все элементы сразу. Вместо этого эвакуация выполняется постепенно, по мере обращения к мапе.
• Это позволяет минимизировать задержки и равномерно распределить нагрузку.

b) Инкрементальный rehashing:

• Эвакуация выполняется инкрементально, то есть элементы перемещаются по мере выполнения операций с мапой.
• Например, при вставке нового элемента Go может переместить несколько элементов из старых бакетов.

c) Параллельная эвакуация:

• В многопоточных сценариях Go может выполнять эвакуацию параллельно, чтобы ускорить процесс.

 

Итог

• Эвакуация данных — это процесс перераспределения элементов мапы при её расширении.
• Go увеличивает количество бакетов и постепенно перемещает элементы из старых бакетов в новые.
• Это обеспечивает высокую производительность операций с мапой (вставка, поиск, удаление) даже при большом количестве элементов.