- ABA-проблема — CAS видит тот же адрес, но данные за ним уже другие. Аллокатор переиспользовал освобождённую память
- В Go не возникает: GC не освободит память пока есть ссылка. Актуально для C/C++ и кастомных аллокаторов
- Решения: hazard pointers, tagged pointers, GC
Суть проблемы
Горутина 1: загрузила head → указывает на элемент A (адрес 0x0A)
... засыпает ...
Горутина 2: Pop(A), Pop(B), Push(C)
→ аллокатор выделил C по тому же адресу 0x0A (переиспользование)
Горутина 1: просыпается
CAS(&head, 0x0A, ...) → УСПЕХ! адрес совпал
→ но там уже элемент C, не A. Стек сломан.
CAS сравнивает адреса, не содержимое. Адрес 0x0A = 0x0A, хотя за ним совершенно другие данные.
Почему в Go не возникает
GC не освободит объект, пока на него есть хоть одна ссылка. Горутина 1 держит указатель на A → A не будет собран → аллокатор не переиспользует этот адрес → CAS корректно обнаружит изменение.
Возникает если: пишете кастомный аллокатор на Go, или работаете в C/C++ где free() возвращает память немедленно.
Решения
Hazard Pointers — список "опасных" указателей. Если указатель в списке — нельзя освобождать память. Перед обращением — добавляешь в список, после — убираешь.
Tagged Pointers — в неиспользуемых битах адреса (например, верхние 16 из 64) хранится счётчик. При каждом обращении счётчик инкрементируется. CAS сравнивает адрес + счётчик → даже если адрес совпал, счётчик не совпадёт.
Адрес без тега: 0x000000000000_0A
Адрес с тегом: 0x0001_0000000000_0A (тег=1)
После операции: 0x0002_0000000000_0A (тег=2) → CAS не пройдёт
Используется в Boost (C++). Зависит от архитектуры (сколько бит доступно).
GC — встроенный (как в Go) или локальный для структуры данных. Некоторые реализации пишут мини-GC специально для одной структуры.
- Стек Трайбера — lock-free стек на связанном списке. Push и Pop = один CAS-луп на голове
- Высокий contention: все горутины оперируют одной точкой (головой) → не лучшая структура для конкурентного доступа
- Подвержен ABA-проблеме (в Go защищает GC)
Идея
Стек = связанный список, операции только с головой. CAS атомарно обновляет указатель на голову.
Push
func (s *Stack) Push(val int) {
node := &Item{value: val}
for {
head := atomic.LoadPointer(&s.head)
node.next = head // next → старая голова
if atomic.CompareAndSwapPointer(&s.head, head, unsafe.Pointer(node)) {
return // голова обновлена на новый элемент
}
// кто-то встроился → повторяем
}
}
Pop
func (s *Stack) Pop() int {
for {
head := atomic.LoadPointer(&s.head)
if head == nil {
return -1 // стек пуст
}
next := atomic.LoadPointer(&(*Item)(head).next)
if atomic.CompareAndSwapPointer(&s.head, head, next) {
return (*Item)(head).value // голова сдвинута на next
}
// кто-то встроился → повторяем
}
}
Почему CAS, а не просто присваивание
Между Load и обновлением головы другая горутина может изменить стек. CAS проверяет: "голова всё ещё та, что я загрузил?" Если да — обновляем. Если нет — повторяем.
Проблема: высокий contention
У стека одна точка входа и выхода — голова. Все горутины конкурируют за неё. Много CAS-неудач → много повторных итераций.
Очередь лучше: голова (pop) и хвост (push) разнесены → меньше contention.
- Очередь Майкла-Скотта — lock-free очередь на связанном списке. Базовая структура для многих lock-free алгоритмов
- Push = два CAS (tail.next + tail). Между ними другая горутина может помочь довернуть второй CAS
- Меньше contention чем стек: push работает с хвостом, pop — с головой
Ключевая идея: помоги другой горутине
В стеке один CAS. В очереди — два (обновить tail.next и tail). Между ними может встроиться другая горутина.
Решение: если горутина видит что кто-то начал push (tail.next ≠ nil), но не довернул tail — она сама довернёт чужой tail, а потом продолжит свой push.
Структура
type Item struct {
value int
next unsafe.Pointer // atomic
}
type Queue struct {
head unsafe.Pointer // dummy → first real element
tail unsafe.Pointer // last element
}
func NewQueue() *Queue {
dummy := &Item{}
q := &Queue{}
q.head = unsafe.Pointer(dummy)
q.tail = unsafe.Pointer(dummy)
return q
}
Dummy-элемент (пустышка) — чтобы не писать лишних if'ов. Head и tail начинают с dummy.
Push
func (q *Queue) Push(val int) {
node := &Item{value: val}
for {
tail := atomic.LoadPointer(&q.tail)
next := atomic.LoadPointer(&(*Item)(tail).next)
if tail != atomic.LoadPointer(&q.tail) {
continue // tail изменился, начинаем заново
}
if next == nil {
// Никто не добавляет → CAS 1: tail.next = node
if atomic.CompareAndSwapPointer(&(*Item)(tail).next, nil, unsafe.Pointer(node)) {
// CAS 2: tail = node (не проверяем успех!)
atomic.CompareAndSwapPointer(&q.tail, tail, unsafe.Pointer(node))
return
}
} else {
// Кто-то начал push, но не довернул tail → ПОМОГАЕМ
atomic.CompareAndSwapPointer(&q.tail, tail, next)
}
}
}
CAS 2 не проверяется: если не получилось — другая горутина поможет (ветка else).
Pop
func (q *Queue) Pop() int {
for {
head := atomic.LoadPointer(&q.head)
tail := atomic.LoadPointer(&q.tail)
next := atomic.LoadPointer(&(*Item)(head).next)
if head != atomic.LoadPointer(&q.head) { continue }
if head == tail {
if next == nil { return -1 } // пусто
// Один элемент + кто-то пушит → помогаем довернуть tail
atomic.CompareAndSwapPointer(&q.tail, tail, next)
} else {
val := (*Item)(next).value
if atomic.CompareAndSwapPointer(&q.head, head, next) {
return val
}
}
}
}
Pop тоже помогает push: если head == tail но next ≠ nil — элемент добавлен, но tail не обновлён. Pop доворачивает tail за чужую горутину.
Два CAS — общий паттерн
Когда операция требует >1 CAS, используй подход:
- Каждый CAS после первого — не проверяй успех
- Другие горутины должны помогать довернуть незавершённые CAS
Это основа для любых lock-free структур сложнее стека.
- Акторная модель — математическая модель параллельных вычислений (1973, Карл Хьюит). Акторы общаются сообщениями, не разделяют состояние
- Актор: inbox (буферизированный канал), внутреннее состояние (изолировано), уникальный адрес. 3 действия: создать актор, отправить сообщение, изменить своё состояние
- В Go: актор = горутина + канал. Круто для распределённых систем (YDB, Erlang), избыточно для продуктовой бизнес-логики
Структура актора
type Actor struct {
inbox chan Letter // почтовый ящик (буферизированный)
executor Executor // поведение (интерфейс)
}
type Letter struct {
To string
From string
Body interface{}
}
func NewActor(exec Executor) *Actor {
a := &Actor{inbox: make(chan Letter, 10), executor: exec}
go func() {
for letter := range a.inbox { // одна горутина обрабатывает
a.executor.Execute(letter) // последовательно (FIFO)
}
}()
return a
}
Свойства
Изоляция: актор не может изменить состояние другого актора. Только отправить сообщение.
Асинхронность: отправка = запись в буферизированный канал. Обработка — по одному, FIFO.
Параллелизм: нужно обработать N сообщений параллельно → создать N акторов одного типа.
Actor Manager: синглтон, хранит мапу адрес → актор. Маршрутизирует сообщения. Под мьютексом.
Где использовать
Да: распределённые системы. Актор сегодня локальный (канал), завтра — удалённый (gRPC). YDB (C++), мониторинг Яндекса (Java), Erlang/OTP.
Нет: обычная продуктовая бизнес-логика. Избыточная абстракция, усложняет код.
Минусы
- Как получать ошибки? Обратный канал? Две очереди (запрос/ответ)?
- Отладка сложнее: асинхронные цепочки вместо синхронных вызовов
- Overhead на сериализацию/десериализацию сообщений
- Закон Амдала: ускорение программы ограничено последовательной частью. S(N) = 1 / ((1-P) + P/N)
- P = доля параллелизуемого кода, N = количество ядер. Даже бесконечное N не поможет если (1-P) > 0
- Практическое применение: перед параллелизацией — оцени P, посчитай ожидаемое ускорение, сравни с бенчмарком
Формула
1
S(N) = -----------
(1-P) + P/N
P — доля кода, которую можно распараллелить (0..1) N — количество ядер (фактор параллельности) 1-P — доля кода, которая остаётся последовательной S(N) — итоговое ускорение
Пример
90% кода параллелится (P=0.9), 10 ядер (N=10):
S(10) = 1 / (0.1 + 0.9/10) = 1 / (0.1 + 0.09) = 1 / 0.19 = 5.26x
Ожидали 10x, получили 5.26x. 10% последовательного кода съели половину ускорения.
Предел при N -> бесконечности
S(inf) = 1 / (1-P)
P=0.5 -> максимум 2x (сколько бы ядер ни было)
P=0.9 -> максимум 10x
P=0.99 -> максимум 100x
Практика: бенчмарк подтверждает
func calculate(parallelFactor int) {
// 50% последовательный код
for i := 0; i < 1_000_000; i++ { /* work */ }
// 50% параллелизуемый код
var wg sync.WaitGroup
chunk := 1_000_000 / parallelFactor
for i := 0; i < parallelFactor; i++ {
wg.Add(1)
go func() {
defer wg.Done()
for j := 0; j < chunk; j++ { /* work */ }
}()
}
wg.Wait()
}
P=0.5:
N=1: базовое время T
N=2: S = 1/(0.5 + 0.25) = 1.33x -> T/1.33 (бенчмарк подтверждает)
N=4: S = 1/(0.5 + 0.125) = 1.6x -> T/1.6 (бенчмарк подтверждает)
Когда применять
Да: небольшая функция, можно глазами оценить P. Перед решением о параллелизации — посчитай.
Нет: огромная кодовая база, трудно оценить P.
Вывод: если последовательная часть большая — параллелизация не поможет. Сначала оптимизируй последовательную часть.
- Шардированная мапа — разрезать одну мапу с одним мьютексом на N мап с N мьютексами
- Роутинг по шардам: hash(key) % N. Горутины расходятся по разным шардам → меньше contention
- Тот же принцип что локальные очереди в планировщике Go
Проблема
type Cache struct {
mu sync.Mutex
data map[string]string
}
Один мьютекс → все горутины конкурируют за него → bottleneck.
Решение: шардирование
type Shard struct {
mu sync.RWMutex
data map[string]string
}
type ShardedMap struct {
shards []Shard
}
func NewShardedMap(n int) *ShardedMap {
sm := &ShardedMap{shards: make([]Shard, n)}
for i := range sm.shards {
sm.shards[i].data = make(map[string]string)
}
return sm
}
func (sm *ShardedMap) getShard(key string) *Shard {
h := fnv32(key)
return &sm.shards[h%uint32(len(sm.shards))]
}
func (sm *ShardedMap) Get(key string) (string, bool) {
shard := sm.getShard(key) // без синхронизации — слайс не меняется
shard.mu.RLock()
defer shard.mu.RUnlock()
v, ok := shard.data[key]
return v, ok
}
Почему работает
При N шардах и равномерном хэше: вероятность что 2 горутины попадут в один шард ≈ 1/N. Чем больше N — тем меньше contention.
1 шард: все горутины → 1 мьютекс (максимальный contention)
16 шардов: горутины → 16 мьютексов (contention / 16)
Выбор количества шардов
- Слишком мало → мало выигрыша
- Слишком много → overhead на память (N мьютексов + N мап)
- Типичное значение: количество ядер × 4..16
- Бенчмаркай под свою нагрузку
Продвинутый вариант: внешний роутинг
Можно вынести выбор шарда в интерфейс — вызывающий код явно роутит горутины к нужным шардам, чтобы определённые горутины никогда не пересекались.
Где используется
- sync.Map (внутри Go runtime)
- Локальные очереди планировщика Go (P-локальные)
- Concurrent hash maps в Java (ConcurrentHashMap)
- Шардирование в базах данных — та же идея
- RCU (Read-Copy-Update) — атомарная подмена указателя на целую структуру данных. Читатели работают с копией, писатель создаёт новую и подменяет указатель
- Работает когда операции — только чтение, а запись = полная замена (не модификация)
- Нет мьютексов, нет блокировок: только atomic.Store/Load на указателе
Идея
Есть кэш (мапа), который обновляется раз в минуту из внешнего хранилища. Между обновлениями — только чтение.
С мьютексом:
type Cache struct {
mu sync.Mutex
data map[string]string
}
func (c *Cache) Get(key string) string {
c.mu.Lock()
defer c.mu.Unlock()
return c.data[key]
}
С RCU (без мьютекса):
type Cache struct {
data unsafe.Pointer // *map[string]string
}
func (c *Cache) Get(key string) string {
m := (*map[string]string)(atomic.LoadPointer(&c.data))
return (*m)[key]
}
func (c *Cache) sync() {
newMap := loadFromStorage() // загрузка без блокировок
p := unsafe.Pointer(&newMap)
atomic.StorePointer(&c.data, p) // атомарная подмена
}
Как работает
Горутина A: Load → получила старую мапу → работает с ней
↓ (в это время)
Синхронизатор: Store → подменил указатель на новую мапу
↓
Горутина B: Load → получила НОВУЮ мапу → работает с ней
A и B работают с разными копиями одновременно. Это нормально — данные обновляются раз в минуту, секундное расхождение некритично.
Когда A закончит — следующий Load вернёт уже новую мапу.
Когда подходит
- Кэш с периодическим обновлением (read-heavy, write-rare)
- Конфигурация, загружаемая из внешнего источника
- Любая структура где запись = полная замена, не модификация отдельных полей
Не подходит: если нужно добавлять/удалять отдельные элементы конкурентно.
- 4 уровня: грубая → тонкая → оптимистичная → ленивая синхронизация. Каждый увеличивает пропускную способность и сложность кода
- Множество на отсортированном связанном списке как модельная структура. Метод find с двумя указателями (prev, curr)
- Аналогия с БД: блокировка таблицы → блокировка строк → оптимистичные транзакции
Модельная задача
Множество (set) на отсортированном связанном списке. Операции: contains, add, remove. Инвариант: элементы по возрастанию, без дубликатов.
head(0) → 10 → 20 → 30 → 40 → nil
find(val) бежит двумя указателями (prev, curr) пока curr.value < val.
1. Грубая синхронизация (59→72 строки)
type Set struct {
mu sync.Mutex
head *Node
}
Один мьютекс на всё. Lock перед каждой операцией. Просто, но все горутины конкурируют за один мьютекс.
2. Тонкая синхронизация (72→85 строк)
Мьютекс в каждом узле. Итерация = hand-over-hand locking:
Lock(prev) → Lock(curr) → Unlock(prev) → prev=curr
→ Lock(curr.next) → Unlock(prev) → ...
Две горутины могут одновременно двигаться по списку если они на расстоянии друг от друга.
Удаление: захватить prev + curr (2 мьютекса). Иначе аномалии: разрыв списка, потеря элементов.
Добавление: формально хватает 1 мьютекса, но на практике захватывают 2 (переиспользование find).
3. Оптимистичная синхронизация (85→145 строк)
Итерация без мьютексов (только атомики). Мьютексы захватываются только для модификации.
Но между "нашёл элемент" и "захватил мьютекс" кто-то мог удалить/добавить.
Решение — валидация: после захвата мьютексов пробежаться сначала списка → проверить что элементы ещё существуют и связь между ними цела.
func (s *Set) Add(val int) bool {
for {
prev, curr := s.find(val) // без мьютексов
prev.Lock(); curr.Lock() // захватили
if s.validate(prev, curr) { // повторный проход сначала
// элементы на месте → добавляем
break
}
prev.Unlock(); curr.Unlock() // не валидно → заново
}
}
4. Ленивая синхронизация (145→~130 строк)
Вместо повторного прохода — флаг deleted в каждом узле.
Валидация: !prev.dropped && !curr.dropped && prev.next == curr
func (s *Set) validate(prev, curr *Node) bool {
return !prev.dropped && !curr.dropped &&
prev.getNext() == curr
}
Важно: внутри мьютексов всё равно нужны атомики для указателей — горутины бегают по списку без мьютексов (через атомики), поэтому модификация указателей должна быть атомарной.
Удаление: сначала curr.dropped = true, потом prev.next = curr.next.
Сводка
Грубая Тонкая Оптимист. Ленивая
Строк кода 72 85 145 ~130
Мьютексов 1 N (в узлах) N N
Итерация под mx hand-over атомики атомики
Валидация — — повт.проход флаг
Contention макс меньше ещё меньше мин
Дальнейшие оптимизации
- Полностью lock-free (только атомики, без мьютексов)
- Шардирование (разрезать список на N частей)
- Комбинация: lock-free + шардирование
- Без правильной синхронизации: потеря элементов, разрыв списка, распад на два списка
- Удаление: захвати prev + curr. Иначе параллельное удаление/добавление соседних элементов ломает связи
- Принцип: для любой модификации связи A→B нужна блокировка обоих концов
Аномалия 1: потеря добавленного элемента
Начало: 10 → 20 → 30 → 40
Горутина 1: add(25) — нашла позицию между 20 и 30, засыпает
Горутина 2: add(27) — добавила между 20 и 30
10 → 20 → 27 → 30 → 40
Горутина 1: просыпается, ставит 25.next = 30 (старый next 20)
20.next = 25
Результат: 10 → 20 → 25 → 30 → 40
Элемент 27 потерян!
Проблема: горутина 1 использует устаревшую связь 20→30.
Аномалия 2: потеря элемента при удалении
Начало: 10 → 20 → 30 → 40
Горутина 1: remove(20) — засыпает перед обновлением связи
Горутина 2: remove(30) — удаляет: 20.next = 40
10 → 20 → 40
Горутина 1: просыпается, удаляет 20: 10.next = 30
Но 30 уже удалён!
10 → 30 → ??? (список сломан)
Аномалия 3: распад списка
Начало: 10 → 20 → 30 → 40
Горутина 1: remove(30) — засыпает
Горутина 2: remove(20) — удаляет: 10.next = 30
10 → 30 → 40
Горутина 1: просыпается, удаляет 30: 20.next = 40
Но 20 уже не в списке!
Список распался на два: 10 → 30 и 20 → 40
Решение: захват prev + curr
Для удаления элемента 30: Lock(20) + Lock(30).
Lock(20) Lock(30)
↓ ↓
→ [20] ----→ [30] → 40
Теперь никто не может:
- Удалить 20 (нужен Lock(20) — занят)
- Удалить 30 (нужен Lock(30) — занят)
- Удалить 40 (нужен Lock(30) как prev — занят)
- Добавить между 20 и 30 (нужен Lock(20) или Lock(30) — заняты)
Элемент 10 можно удалить — его блокировка свободна, и это не влияет на операцию с 30.
Deadlock prevention
Hand-over-hand: всегда захватываем в порядке prev → curr (слева направо). Все горутины двигаются в одном направлении → циклических зависимостей нет → deadlock невозможен.