Конкурентные структуры, барьеры памяти, false sharing

Один мьютекс на всё и почему он тормозит

Самый прямой способ сделать структуру данных безопасной для нескольких потоков — обернуть её мьютексом. Такую структуру называют потокобезопасной (thread-safe): ей можно пользоваться из многих потоков одновременно, и данные не испортятся.

type SafeMap struct {
	mu sync.Mutex
	m  map[string]int
}
 
func (s *SafeMap) Inc(key string) {
	s.mu.Lock()
	s.m[key]++
	s.mu.Unlock()
}

Это корректно, и с этого почти всегда стоит начинать. Но представьте кэш сессий в сервисе на 32 ядрах процессора: каждый запрос делает Get или Set, и все они проходят через один s.mu. В каждый момент внутри может быть только одна горутина, остальные ждут. Ситуация, когда много потоков одновременно хотят один и тот же лок, называется contention (борьба за лок). При сильной борьбе параллельный код вырождается в последовательный: ядер 32, а работает фактически одно. Плюс каждое ожидание — это спин или парковка, которые мы разбирали в предыдущей главе.

Как увидеть contention в Go: профиль блокировок pprof с runtime.SetMutexProfileFraction показывает, на каких мьютексах горутины ждут дольше всего. Это первое, что стоит снять, прежде чем что-то оптимизировать.

Шардирование: много маленьких локов

Если ключи независимы, им не нужен общий замок. Разобьём map на N частей (шардов), у каждой свой мьютекс. Ключ попадает в шард по хешу.

   ключ "user:42"  ── hash % 16 = 5  ──►  shard[5]   (свой lock)
   ключ "order:7"  ── hash % 16 = 12 ──►  shard[12]  (свой lock)
 
   ┌────────┬────────┬────────┬─────┬─────────┐
   │ shard0 │ shard1 │ shard2 │ ... │ shard15 │   у каждого свой mutex
   └────────┴────────┴────────┴─────┴─────────┘

Две горутины с разными ключами почти всегда попадают в разные шарды и не мешают друг другу. Этот приём называют striped locks или sharding, а в общем виде говорят о гранулярности блокировок: крупная (один лок на всё) проще, мелкая (много локов на части) лучше масштабируется.

type ShardedMap struct {
	shards [16]struct {
		mu sync.Mutex
		m  map[string]int
	}
}
 
func (s *ShardedMap) shard(key string) int {
	h := fnv.New32a()
	h.Write([]byte(key))
	return int(h.Sum32() % 16)
}

У мелкой гранулярности есть цена. Операции «по всей структуре» (посчитать Len, обойти все элементы, сделать снимок) теперь должны пройти по всем шардам и взять все локи, и если брать их в разном порядке, можно получить взаимоблокировку. А если ключи распределены неравномерно (один горячий ключ), шардирование не поможет: все запросы всё равно упрутся в один шард.

В стандартной библиотеке Go есть sync.Map. С Go 1.24 внутри у неё конкурентное хеш-дерево (hash trie), где разные ключи живут в разных узлах, то есть по сути та же идея мелкой гранулярности. Документация по-прежнему советует её для двух сценариев: ключ записывается один раз и много раз читается, или разные горутины работают с непересекающимися наборами ключей. В остальных случаях обычная типизированная map с мьютексом проще и не хуже по скорости.

Lock-free: CAS вместо замка

Иногда без лока можно обойтись совсем. Нужна операция compare-and-swap (CAS) из прошлой главы: «запиши новое значение, если там всё ещё старое». На ней строится цикл повторов:

func incr(cnt *atomic.Int64) {
	for {
		old := cnt.Load()
		if cnt.CompareAndSwap(old, old+1) {
			return
		}
		// между Load и CAS кто-то успел изменить cnt — пробуем снова
	}
}

   A: Load → 5,  CAS(5→6) успех
   B: Load → 5,  CAS(5→6) неудача (там уже 6) → Load → 6, CAS(6→7) успех

Такие структуры называют lock-free: ни один поток не держит замок, и если какой-то поток уснул на полпути, остальные всё равно продвигаются. Чем это отличается от мьютекса:

• при неудаче мьютекс со временем усыпит поток, а CAS-цикл сразу пробует снова, без похода в ядро ОС;
• при слабой борьбе это быстрее; при сильной потоки тратят CPU на повторы, которые всё равно проиграют.

Частое заблуждение: «atomic.AddInt64 внутри — такой же CAS-цикл». Нет. Для сложения у процессоров есть отдельная атомарная инструкция: на amd64 Go компилирует Add в LOCK XADD, на arm64 с расширением LSE — в LDADDAL. Цикл повторов появляется только там, где такой инструкции нет. CAS-цикл нужен, когда новое значение вычисляется сложнее, чем «плюс n»: например, «увеличить, но не больше лимита».

Ловушка lock-free структур на указателях — ABA-проблема. Поток прочитал указатель на узел A и собирается сделать CAS. Пока он медлил, другой поток снял A, снял B, освободил их и положил новый узел, который аллокатор разместил по тому же адресу, что был у A. CAS видит «там A, как и было» и проходит, хотя структура уже совсем другая. Лечат счётчиком версий рядом с указателем или отложенным освобождением памяти. В Go ABA встречается реже, потому что сборщик мусора не отдаст адрес узла, пока на него кто-то ссылается, но для индексов в массиве (вместо указателей) проблема остаётся.

Практическое правило: lock-free пишут для одной-двух горячих переменных (счётчики, флаги, указатель на текущий конфиг через atomic.Pointer). Lock-free очередь или map собственной разработки на ревью почти всегда хуже готового мьютекса.

Барьеры памяти: запись не обязана стать видна в том порядке

Теперь коварная часть. Один поток готовит данные и поднимает флаг, второй ждёт флаг и читает данные:

   Поток 1                  Поток 2
   data = 42                while ready == 0 { }
   ready = 1                print(data)

Кажется очевидным, что раз поток 2 увидел ready == 1, то data уже 42. Это не так. Переставлять операции имеют право двое.

Компилятор. Для потока 1 порядок двух независимых записей неважен, и оптимизатор может их поменять. Он же может прочитать ready в цикле потока 2 один раз и крутиться на значении из регистра вечно.

Процессор. Здесь всё зависит от архитектуры. На x86 действует довольно строгая модель (TSO): записи становятся видны другим ядрам в том порядке, в каком их сделал поток, и чтения тоже не обгоняют друг друга. Единственная разрешённая перестановка — более поздняя загрузка может выполниться раньше предыдущей записи (запись в это время ждёт в store buffer — очереди записей ядра, которые ещё не дошли до кэша). На ARM и POWER модель слабее: и записи, и чтения могут стать видны в другом порядке. Код, который «всегда работал» на ноутбуке с Intel, иногда ломается на сервере с ARM (Graviton, Ampere) или на Mac с Apple Silicon.

Запрещает перестановки барьер памяти (memory barrier, fence) — инструкция, через которую операции не переносятся: всё, что до барьера, станет видно раньше всего, что после. Барьер нужен с обеих сторон: у пишущего (не выпустить ready раньше data) и у читающего (не прочитать data раньше ready).

В Go барьеры руками не ставят. Их вставляют операции синхронизации: атомики, мьютексы, каналы. Модель памяти Go описывает это через отношение happens-before: если запись в канал случилась до чтения из канала, то всё, что горутина сделала до отправки, видно горутине после приёма. То же для Unlock → следующий Lock и для атомарной записи → атомарного чтения, которое её увидело. Подробно — в главе модель памяти Go.

Правильный вариант примера:

var (
	data  int
	ready atomic.Bool
)
 
// поток 1
data = 42
ready.Store(true) // публикация: data станет видна вместе с флагом
 
// поток 2
for !ready.Load() {
	runtime.Gosched()
}
fmt.Println(data) // гарантированно 42

Обычный bool вместо atomic.Bool — это гонка данных, и go run -race её поймает. Синхронизация нужна не только чтобы «не толкаться» в критической секции, но и чтобы записи одного потока стали видны другому в правильном порядке.

Как ядра процессора договариваются о кэшах: MESI

В этом разделе и следующем «ядро» — всегда ядро процессора (core), а не ядро ОС.

Откуда вообще берётся проблема видимости? У каждого ядра свои кэши L1 и L2 — быстрые локальные копии кусков памяти. Обмениваются ядра не байтами, а кэш-линиями (cache line): на x86 линия 64 байта, на Apple M1/M2 и некоторых серверных ARM — 128.

Чтобы два ядра не держали разные значения одной ячейки, они соблюдают протокол когерентности. Классический вариант — MESI, по первым буквам четырёх состояний линии в кэше ядра:

   M (Modified)  — линия есть только у меня, я её изменил, в памяти старое
   E (Exclusive) — линия только у меня, совпадает с памятью
   S (Shared)    — копии у нескольких ядер, все только читают
   I (Invalid)   — моя копия устарела, пользоваться нельзя
 
   Ядро 0 хочет записать в линию, которая есть у ядра 1:
     ядро 0 рассылает invalidate → у ядра 1 линия становится I
     ядро 0 получает линию в M и пишет
     ядро 1 при следующем чтении заново запрашивает линию

Главное следствие: запись в линию, которую держат другие ядра, не бесплатна. Это обмен сообщениями между ядрами и ожидание ответов, десятки наносекунд вместо одной. Чем больше ядер пишут в одну линию, тем больше этого трафика. Поэтому один атомарный счётчик, который инкрементируют все ядра, масштабируется плохо, хотя никаких локов в нём нет.

False sharing

Теперь неочевидный случай. Два счётчика логически независимы: каждый инкрементирует своё ядро. Но если они лежат в памяти рядом и попали в одну кэш-линию, ядра всё равно гоняют линию друг другу:

   ┌──────────────── одна кэш-линия ────────────────┐
   │ counterA (8 Б) │ counterB (8 Б) │ ...           │
   └────────────────────────────────────────────────┘
        ▲ ядро 0 пишет        ▲ ядро 1 пишет
 
   ядро 0 пишет A → линия у ядра 1 становится I
   ядро 1 пишет B → линия у ядра 0 становится I
   ... линия скачет между кэшами, хотя A и B не связаны

Это false sharing (ложное разделение): данные не общие, а линия общая. Лечится padding (набивкой): между переменными вставляют пустые байты, чтобы каждая заняла свою линию.

Проверим на бенчмарке. Четыре горутины, каждая инкрементирует свой счётчик. В первом варианте счётчики лежат вплотную, во втором каждый добит до 128 байт.

package fs
 
import (
	"sync"
	"sync/atomic"
	"testing"
)
 
const workers = 4
 
type packed struct {
	n [workers]atomic.Int64 // 4 × 8 байт подряд, одна линия
}
 
type padded struct {
	n [workers]struct {
		v atomic.Int64
		_ [120]byte // 8 + 120 = 128 байт: своя линия и на x86, и на ARM
	}
}
 
func BenchmarkPacked(b *testing.B) {
	var c packed
	var wg sync.WaitGroup
	for w := 0; w < workers; w++ {
		wg.Add(1)
		go func(w int) {
			defer wg.Done()
			for i := 0; i < b.N; i++ {
				c.n[w].Add(1)
			}
		}(w)
	}
	wg.Wait()
}
 
func BenchmarkPadded(b *testing.B) {
	var c padded
	var wg sync.WaitGroup
	for w := 0; w < workers; w++ {
		wg.Add(1)
		go func(w int) {
			defer wg.Done()
			for i := 0; i < b.N; i++ {
				c.n[w].v.Add(1)
			}
		}(w)
	}
	wg.Wait()
}

На ноутбуке с Apple M2 Pro (go test -bench ., Go 1.25) получилось так:

BenchmarkPacked-10    10033843     115.4 ns/op
BenchmarkPadded-10   289468153       4.270 ns/op

Разница почти в 30 раз, а код отличается одним полем. Для сравнения: если все четыре горутины честно инкрементируют один общий счётчик, выходит те же ~115 нс. То есть с точки зрения железа «четыре независимых счётчика в одной линии» ничем не лучше одного общего. На вашей машине числа будут другими, но порядок разницы обычно сохраняется.

Где это встречается в Go: шардированные счётчики метрик, массивы per-worker-состояний, статистика по ядрам. Для набивки есть готовый тип cpu.CacheLinePad в пакете golang.org/x/sys/cpu (размер под текущую архитектуру). Рантайм Go внутри делает то же самое для своих структур на P. Частая ошибка — паддить «на 64 байта» вслепую: на ARM-серверах и Mac линия может быть 128 байт, и тогда набивка не помогает.

Что выбрать на практике

Порядок действий: начать с обычного мьютекса; если профиль показал contention — шардировать или уменьшить критическую секцию; атомики — для одиночных горячих переменных; padding — когда независимые данные пишутся с разных ядер.

Частые ошибки

• Оптимизировать без профиля: заменять мьютекс на lock-free структуру, не увидев contention в mutex-профиле.
• Использовать обычную переменную как флаг между горутинами «потому что на x86 работает». Это гонка данных; на ARM и после оптимизаций компилятора она проявится.
• Считать, что atomic.AddInt64 — это CAS-цикл и потому медленный под нагрузкой; медленным его делает борьба за кэш-линию.
• Паддить до 64 байт вслепую: на Apple Silicon и части ARM-серверов линия 128 байт.
• Ожидать, что шардирование поможет при одном горячем ключе.

Проверьте себя

1. Почему 32 горутины с одним общим мьютексом работают не быстрее одной?
2. Что может переставить процессор x86, а что — ARM, в примере с data и ready?
3. Почему четыре независимых atomic-счётчика, лежащих рядом, работают так же медленно, как один общий?
4. В бенчмарке из главы замените [120]byte на [56]byte. На x86 с 64-байтной линией результат почти не изменится, а на Apple Silicon вариант станет примерно вдвое медленнее варианта со [120]byte, хотя и намного быстрее packed. Сколько счётчиков теперь делят одну линию?

Что спрашивают на собесе

• Чем плох один мьютекс на всю структуру? При сильной борьбе горутины стоят в очереди, работа сериализуется. Лечится шардированием (striped locks) и сокращением критической секции.
• Как сделать lock-free счётчик на CAS и в чём ловушка? Цикл «Load → вычислить → CAS → при неудаче повторить». Ловушка структур на указателях — ABA. И уточнение: простой atomic.Add на amd64/arm64 — одна инструкция, а не цикл.
• Зачем барьеры памяти, если есть мьютекс? Мьютекс как раз и даёт барьеры. Синхронизация обеспечивает не только взаимное исключение, но и порядок видимости записей (happens-before).
• Что x86 может переупорядочить? Только запись с последующим чтением другого адреса (store buffer). ARM переупорядочивает больше, поэтому баги видимости чаще всплывают там.
• Что такое MESI? Протокол когерентности кэшей: Modified, Exclusive, Shared, Invalid. Запись требует инвалидировать чужие копии, отсюда цена записи в общую линию.
• Что такое false sharing и как лечить? Независимые переменные в одной кэш-линии, ядра гоняют линию друг другу. Лечится padding до размера линии (64 байта на x86, 128 на части ARM).