👨‍💻 Шардируйте локи или ускорение in-memory кеша до 8 раз

Конкурентный in-memory кеш в Go часто пишут через один sync.Mutex. Пока нагрузка низкая, всё в порядке. Но под конкурентным доступом единственный лок превращается в узкое место, и добавление ядер не помогает, а иногда даже вредит.

Миша Стребков собрал один и тот же кеш string → string шестью способами на чистой стандартной библиотеке и прогнал бенчмарки под чтением, сбалансированной нагрузкой и записью на 1–8 ядрах. Порядок победителей меняется в зависимости от профиля, а одно «очевидное» решение с ростом числа ядер работает медленнее.

Шесть вариантов

1. naive это обычная map без блокировок, не потокобезопасна и падает на конкурентной записи.
2. mutex использует один sync.Mutex, прост и корректен, но не масштабируется.
3. rwmutex даёт параллельные чтения и эксклюзивную запись через sync.RWMutex.
4. syncmap это встроенная sync.Map.
5. sharded разбивает данные на 256 частей, у каждой свой мьютекс, ключ выбирает часть по хешу.
6. cow реализует copy-on-write через atomic.Pointer, чтения без блокировок, но каждая запись копирует всю мапу.

➡️Что показали замеры

sharded и cow наращивают пропускную способность с ростом ядер, а mutex остаётся плоским. Более того, у mutex на 8 ядрах пропускная способность падает до 0.66 от одноядерной. Чтения не идут параллельно, а кеш-линия с локом гоняется между ядрами. Вы добавили железо и потеряли производительность.

rwmutex упирается в потолок около 2× и перестаёт расти после 4 ядер. Счётчик читателей сам становится точкой конкуренции. На записи он оказывается хуже обычного мьютекса.

cow выигрывает на чистом чтении с огромным отрывом, 87 миллионов операций в секунду на 8 ядрах. Но как только появляется запись, он проваливается почти в ноль, потому что каждый Set копирует мапу на миллион записей.

sharded единственный дизайн, который держится у вершины во всех профилях сразу.

Победитель в пятнадцати строках

sharded это просто N независимых мап, каждая под своим локом. Хеш ключа выбирает часть, поэтому операции над разными ключами почти никогда не трогают один и тот же лок. Конкуренция падает примерно в N раз:

const shards = 256 // степень двойки, чтобы маскировать вместо modulo

type part struct {
  mu sync.Mutex
  m  map[string]string
}
type Sharded struct{ parts [shards]*part }

func (c *Sharded) at(key string) *part {
  h := uint64(14695981039346656037) // FNV-1a
  for i := 0; i < len(key); i++ {
    h = (h ^ uint64(key[i])) * 1099511628211
  }
  return c.parts[h&(shards-1)]
}

func (c *Sharded) Get(key string) (string, bool) {
  p := c.at(key)
  p.mu.Lock()
  v, ok := p.m[key]
  p.mu.Unlock()
  return v, ok
}

func (c *Sharded) Set(key, value string) {
  p := c.at(key)
  p.mu.Lock()
  p.m[key] = value
  p.mu.Unlock()
}

Одна деталь про явный Unlock. На Go 1.26 замер показал, что defer p.mu.Unlock() здесь стоит около +8% (примерно 1 нс) поверх явного анлока. На горячем пути это заметно, поэтому горячие методы разблокируют лок явно.

Почему 256 частей

Достаточно, чтобы убить конкуренцию, и не так много, чтобы жечь память. Свип количества частей на 8 ядрах и сбалансированной нагрузке растёт круто до 256, а дальше выходит на плато. Переход от одного лока к 256 даёт скачок в 9 раз (с 4.6 до 43 миллионов операций в секунду). После 256 отдача падает, 1024 добавляют +13%, 4096 всего +18% при кратно большем расходе памяти.

Цифры на 8 ядрах, ns/op, меньше лучше, равномерное распределение

mix          mutex  rwmutex  syncmap  sharded  cow
read-only    168    53       30       21       11.5
read-heavy   168    259      37       22       12000000
balanced     190    282      57       24       46500000
write-heavy  208    222      73       25       82500000

Восьмизначные значения cow в столбце записи реальные и указаны в наносекундах. 82 500 000 нс это 82 миллисекунды на один Set. Такова цена чтений без блокировок.

➡️ Что использовать

По умолчанию берите sharded. Он лучший или почти лучший везде, масштабируется с ядрами и пишется тривиально. Это ответ для большинства конкурентных мап.

cow подходит для данных, которые почти всегда только читают. Это снапшоты конфигов, таблицы маршрутизации, feature-флаги. Чтения непобедимы, но только если записи редкие и батчатся. Для записи он не годится.

sync.Map берите в её нише, ключи пишутся один раз и читаются вечно, либо горутины работают с непересекающимися наборами ключей. За пределами этого она посредственна и аллоцирует (40–72 B/op).

sync.RWMutex нужен редко. Он выигрывает только в узком углу с преобладанием чтений и малым числом ядер, а на записи хуже обычного мьютекса.

Обычный mutex нормален при низкой конкуренции или малом числе ядер. Не тяните за сложность, потребность в которой не можете измерить.

Рост числа ядер сделал кеш на одном мьютексе медленнее, и это чистая конкуренция за кеш-линию самого лока. RWMutex оказался полумерой, которая бьёт по записи. Перекос нагрузки (Zipf) это палка о двух концах, а не равномерный штраф, он ускоряет чтения за счёт кеш-локальности и одновременно концентрирует конкуренцию на записи.

Весь код, сырой вывод benchstat и однокомандный свип для воспроизведения лежат в репозитории.

➡️ Источник

Нашу новостную рассылку не нужно ускорять, она и так быстрая

📍 Навигация: Вакансии • Задачи • Собесы

🐸 Библиотека Go-разработчика

#GoDeep