Lock-Free структуры данных в Go

Зачем знать на Middle 2: lock-free — это инструмент для hot paths с экстремальной contention, для метрик/счётчиков, ring-buffer’ов, free-list’ов аллокаторов. Middle 2 должен знать atomic primitives Go (CAS, Load/Store, typed atomics), понимать модель памяти, видеть ABA-проблему, уметь объяснить cache lines и false sharing, реализовать SPSC/MPSC очередь и осознанно выбирать между mutex и lock-free. Без этого — невозможно объяснить, как устроены runtime queue, scheduler steal, sync.Pool internals и любые библиотечные ring-buffer’ы (prometheus, zap, lock-free metrics).

Содержание

1. Базовая концепция: lock-free, wait-free, obstruction-free
2. Глубокое погружение: atomics, memory model, ABA, false sharing
3. Gotchas (15)
4. Производительность: бенчмарки, real cases
5. Вопросы на собесе (28)
6. Practice (8)
7. Источники

---

1. Базовая концепция

1.1. Иерархия не-блокирующих алгоритмов

                Wait-free                ← strongest
                    ↑
                Lock-free                ← Go atomics
                    ↑
              Obstruction-free
                    ↑
            Lock-based (mutex)            ← weakest, but simple

• Lock-based — обычный sync.Mutex. Если поток держит lock и его swap’нут — все ждут.
• Obstruction-free — поток гарантированно завершит операцию, если выполняется в одиночку (без contention). Самое слабое.
• Lock-free — на каждом шаге хотя бы один поток в системе продвигается. Нет дедлоков, нет livelock’ов на уровне системы, но отдельный поток может «голодать» бесконечно (starvation).
• Wait-free — каждый поток завершает операцию за конечное число шагов независимо от других. Самая сильная гарантия, но почти никогда не реализуется на практике (сложно и медленно).

1.2. Где lock-free в Go встречается

• sync/atomic — базовые atomic операции (CAS, Load, Store, Add, Swap).
• sync.Pool — частично lock-free (per-P private slot — без локов).
• runtime — lock-free run queue, work-stealing (runqsteal).
• runtime.gopark/goready — synchronization без локов в hot path.
• Множество библиотек: zap, prometheus, fastcache, lockfree-queue (k-sone и др.).

1.3. Минимальный CAS-счётчик

package counter

import "sync/atomic"

type Counter struct {
    v int64
}

func (c *Counter) Add(delta int64) {
    atomic.AddInt64(&c.v, delta)
}

func (c *Counter) Load() int64 {
    return atomic.LoadInt64(&c.v)
}

// CAS-вариант (демонстрация)
func (c *Counter) AddCAS(delta int64) {
    for {
        old := atomic.LoadInt64(&c.v)
        if atomic.CompareAndSwapInt64(&c.v, old, old+delta) {
            return
        }
        // race lost — повторяем
    }
}

AddInt64 уже использует CAS внутри (на x86 — это LOCK XADD, на ARM — LDADD/LDXR/STXR). CAS-вариант — иллюстрация общего паттерна load → compute → CAS → retry.

1.4. Typed atomics (Go 1.19+)

package metrics

import "sync/atomic"

type Counters struct {
    Requests atomic.Int64
    Errors   atomic.Uint64
    Closed   atomic.Bool
    Latest   atomic.Pointer[Response]
}

type Response struct {
    Status int
    Body   []byte
}

func (c *Counters) Record(r *Response) {
    c.Requests.Add(1)
    c.Latest.Store(r)
}

Преимущества над «голым» atomic.AddInt64:

• Нет случайной не-atomic операции (c.v++ вместо atomic.AddInt64(&c.v, 1)).
• Гарантирован alignment на 32-bit платформах (см. §2.6).
• Generics: atomic.Pointer[T] — без unsafe.Pointer cast’ов.

1.5. Lock-free vs mutex — простое правило

Сценарий	Решение
Один счётчик, миллионы ops/sec	atomic.Int64.Add
Map, читается часто, пишется редко	sync.Map или atomic.Pointer[map] (COW)
Сложная критическая секция (≥3 операций)	sync.Mutex
SPSC очередь (один producer, один consumer)	lock-free ring buffer
MPMC очередь	обычно chan или mutex+slice; lock-free MPMC сложно

Главное: lock-free не означает быстрее при низкой contention. При contention > 50% lock-free выигрывает. При contention < 10% mutex часто быстрее (один CAS внутри, плюс scheduler park вместо busy-loop).

---

2. Глубокое погружение

2.1. CAS — главный примитив

atomic.CompareAndSwapInt64(addr *int64, old, new int64) bool

Семантика (атомарно):

if *addr == old {
    *addr = new
    return true
} else {
    return false
}

На уровне CPU:

• x86-64: LOCK CMPXCHG — одна инструкция, согласует кэш через MESI protocol.
• ARM64: пара LDAXR (load-acquire exclusive) + STLXR (store-release exclusive) с retry, либо LSE-инструкция CAS.

CAS — это basis для всего lock-free: AddInt, SwapInt, любая lock-free структура строится через CAS-loop.

2.2. Каноничный CAS-loop

func atomicUpdate(p *int64, update func(int64) int64) int64 {
    for {
        old := atomic.LoadInt64(p)
        new := update(old)
        if atomic.CompareAndSwapInt64(p, old, new) {
            return new
        }
        // другой поток обновил — повторяем
    }
}

Применение — atomic-monoid (max, min, append-list):

// atomic max
func atomicMax(p *int64, x int64) {
    for {
        cur := atomic.LoadInt64(p)
        if x <= cur {
            return
        }
        if atomic.CompareAndSwapInt64(p, cur, x) {
            return
        }
    }
}

2.3. Модель памяти Go (Go memory model)

Go использует sequentially consistent atomics по умолчанию — это сильнее, чем C++ memory_order_seq_cst для отдельных операций, но согласовано в обе стороны:

• Все atomic-операции синхронизируют память между goroutines (acquire-release семантика встроена).
• Между двумя atomic-операциями на одной переменной — happens-before гарантируется.
• Между atomic и non-atomic на разных переменных — только если atomic образует sync edge.

Ключевая формулировка из The Go Memory Model:

If the effect of an atomic operation A is observed by atomic operation B, then A is synchronized before B.

Пример (правильно):

var data int
var ready atomic.Bool

// goroutine 1
data = 42
ready.Store(true)   // release: данные перед store видны

// goroutine 2
for !ready.Load() { // acquire: после load видим data=42
    runtime.Gosched()
}
fmt.Println(data) // ВСЕГДА 42

Пример (неправильно):

var data int       // ← обычный int
var done bool      // ← обычный bool

// goroutine 1
data = 42
done = true        // ← БЕЗ atomic — компилятор может переставить!

// goroutine 2
for !done {        // ← без atomic — может никогда не увидеть true
}
fmt.Println(data) // UB: 0 или 42

⚠️ Go не даёт relaxed atomics. Если нужна «слабая» оптимизация — нужно использовать runtime/internal/atomic (приватный пакет), но это запрещено в user-коде.

2.4. ABA problem

Сценарий:

T1: load(p) = A
T1: <preempt>
T2: CAS(p, A → B)
T2: CAS(p, B → A)   // вернул то же значение, но семантически другой объект
T1: <resume>
T1: CAS(p, A → C)   // CAS PROXOR — но условие невалидно!

CAS видит «то же значение A», думает «ничего не изменилось», но на самом деле объект был дважды заменён. Если A — указатель на узел linked list, который был удалён, переиспользован и снова вставлен — мы можем починить «ссылку на мертвеца».

Защита от ABA:

1. Tag/version counter — пакуем указатель и счётчик в одно слово:

struct Tagged {
    ptr      *Node    // 48 бит на x86-64 (canonical address)
    counter  uint16   // 16 бит
}

В Go без unsafe.Pointer это сложно — обычно используют atomic.Uintptr + битовые сдвиги, или 128-bit CAS (CMPXCHG16B), которого в Go стандартно нет.

2. Double-word CAS (DCAS) — атомарный CAS пары (ptr, counter). Поддерживается через golang.org/x/sys с inline assembly или специальные обёртки.

3. Hazard pointers / SMR — отслеживание «активных» указателей, чтобы не переиспользовать узел, пока он может быть прочитан другим потоком.

4. Epoch-based reclamation — все потоки заходят в «эпоху»; узел можно реально удалить, только когда все потоки покинули эпоху, в которой он был «logically removed».

5. RCU (Read-Copy-Update) — Linux-стиль: writers создают новую копию, readers продолжают видеть старую, GC удаляет старую, когда все readers ушли. В Go RCU частично реализуется через atomic.Pointer[T] + GC.

2.5. Cache lines и false sharing

Современный x86 имеет cache line = 64 байта. ARM может иметь 64 или 128. Если два поля разных счётчиков лежат в одной cache line — каждое обновление вынудит invalidation, и оба потока будут гонять линию между ядрами.

Плохо (false sharing):

type BadStats struct {
    Reqs   atomic.Int64 // offset 0
    Errs   atomic.Int64 // offset 8 — ТА ЖЕ cache line
    Lat    atomic.Int64 // offset 16 — ТА ЖЕ cache line
}
// 3 ядра пишут — взаимная инвалидация

Хорошо (cache line padding):

type CacheLine [64]byte // ровно 1 line

type GoodStats struct {
    Reqs atomic.Int64
    _    [56]byte // pad до 64
    Errs atomic.Int64
    _    [56]byte
    Lat  atomic.Int64
    _    [56]byte
}

Можно автоматизировать:

type Padded struct {
    Val atomic.Int64
    _   [64 - 8]byte
}

💡 В реальном Go runtime padding встречается в runtime.mheap, runtime.p (структура P в шедулере), sync.Pool.local.

2.6. Alignment на 32-bit платформах

На 32-bit (ARMv7, GOARCH=386) atomic.AddInt64 на не-выровненном адресе паникует или даёт неверный результат. Правило из документации:

On ARM, 386, and 32-bit MIPS, it is the caller’s responsibility to arrange for 64-bit alignment of 64-bit words accessed atomically. The first word in a variable or in an allocated struct, array, or slice can be relied upon to be 64-bit aligned.

// ПЛОХО на 32-bit:
type S struct {
    flag bool       // 1 байт, выровнен на 1
    cnt  int64      // 8 байт, но offset = 1 (или 4 после padding) — НЕ 8-aligned
}

// ХОРОШО:
type S struct {
    cnt  int64      // первое поле — гарантированно 8-aligned
    flag bool
}

Решение в Go 1.19+ — typed atomics:

type S struct {
    flag bool
    cnt  atomic.Int64 // ← компилятор сам обеспечивает alignment
}

atomic.Int64 имеет неявный align через noCopy + _ uint32. Это главная причина перехода на typed atomics.

2.7. SPSC ring buffer (один producer, один consumer)

Самый простой lock-free паттерн — два счётчика (head/tail), один пишет, другой читает.

package spsc

import (
    "runtime"
    "sync/atomic"
)

type Ring[T any] struct {
    buf  []T
    mask uint64
    head atomic.Uint64 // producer cursor
    _    [56]byte      // pad от false sharing
    tail atomic.Uint64 // consumer cursor
    _    [56]byte
}

func New[T any](size uint64) *Ring[T] {
    if size&(size-1) != 0 {
        panic("size must be power of two")
    }
    return &Ring[T]{
        buf:  make([]T, size),
        mask: size - 1,
    }
}

// Push — вызывается только из одного producer-goroutine
func (r *Ring[T]) Push(v T) bool {
    head := r.head.Load()
    tail := r.tail.Load()
    if head-tail >= uint64(len(r.buf)) {
        return false // full
    }
    r.buf[head&r.mask] = v
    r.head.Store(head + 1) // release: данные перед увеличением head
    return true
}

// Pop — вызывается только из одного consumer-goroutine
func (r *Ring[T]) Pop() (T, bool) {
    var zero T
    tail := r.tail.Load()
    head := r.head.Load()
    if head == tail {
        return zero, false // empty
    }
    v := r.buf[tail&r.mask]
    r.tail.Store(tail + 1)
    return v, true
}

// SpinPop — busy-wait вариант для real-time
func (r *Ring[T]) SpinPop() T {
    for {
        if v, ok := r.Pop(); ok {
            return v
        }
        runtime.Gosched()
    }
}

Корректность:

• Push пишет buf[head&mask] перед head.Store. Release-семантика гарантирует: после того как consumer увидит новый head, он увидит и записанные данные.
• Pop читает buf[tail&mask] после head.Load. Acquire-семантика.

Производительность: SPSC ring buffer на современном x86 — ~10ns/op без contention, ~100M ops/sec.

2.8. MPSC очередь (Vyukov)

Многопоточная вставка, один читатель. Алгоритм Дмитрия Вьюкова (1024cores.net), используемый в Linux kernel и многих lock-free библиотеках.

package mpsc

import (
    "sync/atomic"
)

type node[T any] struct {
    next atomic.Pointer[node[T]]
    val  T
}

type Queue[T any] struct {
    head atomic.Pointer[node[T]] // producer side
    _    [56]byte
    tail *node[T] // consumer side (single reader, no atomics needed for tail)
}

func New[T any]() *Queue[T] {
    stub := &node[T]{}
    q := &Queue[T]{tail: stub}
    q.head.Store(stub)
    return q
}

// Push — от любого producer
func (q *Queue[T]) Push(v T) {
    n := &node[T]{val: v}
    prev := q.head.Swap(n) // atomic swap — точка линеаризации
    prev.next.Store(n)     // release: prev.next.Load в consumer увидит данные
}

// Pop — только из одного consumer-goroutine
func (q *Queue[T]) Pop() (T, bool) {
    var zero T
    tail := q.tail
    next := tail.next.Load()
    if next == nil {
        return zero, false // empty
    }
    q.tail = next
    return next.val, true
}

Свойства:

• Push wait-free (один SWAP + один STORE).
• Pop wait-free для одного reader’а.
• Аллоцирует на каждый Push (GC давление). Можно решить через freelist.

2.9. MPMC — сложно

Множественные producer + consumer — здесь нужны более сложные алгоритмы:

• Michael–Scott queue — классика, два CAS на enqueue, обходит ABA через counter.
• Bounded MPMC Vyukov (mpmc-bounded) — массив со «слотом-секвенсом» (sequence number) на каждой ячейке, CAS на seq.
• LCRQ — современный (~2013), близок по производительности к hardware-FIFO.

В Go типично не пишут собственный MPMC — используют буферизованный chan, который внутри уже оптимизирован (mutex + park, но при contention он почти лучший выбор). Lock-free MPMC оправдан только в hot path с >10M ops/sec на ядро.

2.10. Lock-free stack (Treiber)

Стек проще очереди — push/pop с одной вершины.

package treiber

import "sync/atomic"

type node[T any] struct {
    next *node[T]
    val  T
}

type Stack[T any] struct {
    top atomic.Pointer[node[T]]
}

func (s *Stack[T]) Push(v T) {
    n := &node[T]{val: v}
    for {
        old := s.top.Load()
        n.next = old
        if s.top.CompareAndSwap(old, n) {
            return
        }
    }
}

func (s *Stack[T]) Pop() (T, bool) {
    var zero T
    for {
        old := s.top.Load()
        if old == nil {
            return zero, false
        }
        if s.top.CompareAndSwap(old, old.next) {
            return old.val, true
        }
    }
}

⚠️ Этот код подвержен ABA! Если другой поток сделает Pop+Push с тем же узлом, наш CAS не заметит. На практике в Go GC удерживает узлы — но если использовать freelist, проблема возникает.

2.11. Hazard Pointers (концепция)

Идея: каждый поток объявляет «hazard pointer» (HP) — указатель, который он сейчас собирается прочитать. Перед удалением узла мы проверяем все HP: если узел никем не отмечен — можно удалить, иначе отложить.

Thread A:
  load top → hp[A] = ptr
  read ptr.val

Thread B:
  CAS top from ptr to ptr.next
  → ptr "logically removed"
  → check all hp[*]: если ptr встречается — DEFER reclaim
  → если нет — free(ptr)

В Go HP редко нужны, потому что есть GC. GC сам реализует «epoch» для нас. Но если использовать sync.Pool или ручной аллокатор для узлов — HP/SMR становятся релевантны.

2.12. Epoch-based reclamation (EBR)

Все потоки заходят в «эпоху». При удалении узел помечается «retired в эпохе E». Реальное освобождение происходит, когда все потоки прошли через эпоху ≥ E+2. Используется в Crossbeam (Rust), концепт переносится в Go-библиотеки (например, lock_free_map).

Epoch:   1 → 2 → 3 → 4 ...
Threads: T1 in E2, T2 in E3, T3 in E3
Retired: node X (in E2)
Safe to free X when all threads moved past E2.

2.13. RCU (Read-Copy-Update) в Go стиле

RCU — Linux-стиль: writer создаёт новую копию данных, atomically swap’ает указатель, readers продолжают видеть старую копию.

type Config struct {
    URLs    []string
    Timeout time.Duration
}

var cfgPtr atomic.Pointer[Config]

func init() {
    cfgPtr.Store(&Config{Timeout: time.Second})
}

// Read — wait-free
func GetConfig() *Config {
    return cfgPtr.Load()
}

// Write — реже, тяжелее
func UpdateConfig(modify func(c Config) Config) {
    for {
        old := cfgPtr.Load()
        newCfg := modify(*old)
        if cfgPtr.CompareAndSwap(old, &newCfg) {
            return
        }
    }
}

💡 Это идиоматический Go pattern. Используется в Caddy, Vault, etcd для hot-reload конфигурации.

2.14. Lock-free в Go runtime

• runqsteal (runtime/proc.go) — work-stealing очередь, lock-free CAS на head/tail.
• mcache (per-P) — без локов, потому что доступ только из своего P.
• sched.runq — global run queue, обычный mutex (потому что contention редкая и сложность важнее).
• runtime.sysmon — atomic state machine.

Если читать runtime/runtime2.go, видно: где critical path — atomics, где сложно — mutex. Это и есть тот baseline, на который должен ориентироваться Go-разработчик.

---

3. Gotchas

⚠️ 3.1. Не смешивать atomic и non-atomic операции на одной переменной

var counter int64
go func() { atomic.AddInt64(&counter, 1) }()
go func() { counter++ }() // DATA RACE

Race detector это поймает. Внутри Go memory model — UB.

⚠️ 3.2. atomic.LoadXxx не делает «memory barrier», как multi-store

var a, b atomic.Int64
// goroutine 1:
a.Store(1)
b.Store(1)

// goroutine 2:
x := b.Load() // 1
y := a.Load() // может ли быть 0?

В Go ответ: нет, не может. Sequentially consistent semantics. Но если использовать atomic на одних переменных и non-atomic на других — гарантий не будет.

⚠️ 3.3. atomic.Pointer[T] на nil

var p atomic.Pointer[int]
v := p.Load() // nil — это валидно
*v            // panic: nil deref

Всегда проверяйте if v == nil после Load.

⚠️ 3.4. Alignment на 32-bit

type S struct {
    flag bool
    cnt  int64 // на 32-bit может быть мисалайн → паника
}

Решение: atomic.Int64, либо переставить поля, либо использовать //go:linkname runtime.alignUp.

⚠️ 3.5. False sharing убивает scalability

Если 8 счётчиков в одной cache line — 8 ядер не масштабируются. Замерьте через perf stat -e cache-misses или Go pprof + benchmem.

⚠️ 3.6. CAS-loop может крутиться очень долго

Под высокой contention CAS-loop делает 100+ итераций. Это не deadlock, но 99-й percentile latency взлетит. Иногда лучше mutex (он паркует goroutine).

⚠️ 3.7. atomic не защищает invariants между несколькими переменными

var x, y atomic.Int64
// инвариант: x + y == 100
go func() { x.Add(1); y.Add(-1) }() // intermediate state x+y=101 виден

Атомарность ≠ транзакционность. Если нужно — mutex или DCAS.

⚠️ 3.8. ABA в Treiber stack с freelist

// Если узлы переиспользуются (например, через sync.Pool),
// Treiber stack ломается из-за ABA.

Не используйте Pool для узлов lock-free структур без HP/EBR.

⚠️ 3.9. atomic.Value требует один и тот же тип

var v atomic.Value
v.Store("hello")
v.Store(42) // PANIC: types must match

atomic.Value запоминает тип первого Store. Используйте atomic.Pointer[T] для type-safety.

⚠️ 3.10. atomic операции не работают на unaligned slice/struct fields

s := []int64{1, 2, 3}
atomic.AddInt64(&s[1], 1) // OK на 64-bit, но не делайте на 32-bit slice subslice

⚠️ 3.11. Lock-free может быть медленнее под низкой contention

Бенчмаркните обе версии. CAS — это LOCK-prefix на x86, тяжелее обычного MOV.

⚠️ 3.12. atomic.Int64.Add — не идемпотентный

for i := 0; i < 1000; i++ {
    cnt.Add(1)
}
// если retry — будет +1001

В отличие от Store, Add накапливается. Учитывайте при retry-логике.

⚠️ 3.13. atomic.Store не гарантирует видимость в for без atomic.Load

done := false
go func() { time.Sleep(time.Second); done = true }()
for !done {} // может крутиться вечно — нет sync edge

Используйте atomic.Bool или chan struct{}.

⚠️ 3.14. Помните про runtime.Gosched в spin-loops

Spin-loop без yield — съест ядро:

for !ready.Load() {
    runtime.Gosched() // или time.Sleep(time.Microsecond)
}

⚠️ 3.15. SPSC не выдерживает MPSC

Если случайно два producer’а пишут в SPSC — данные потеряются, причём race detector может не поймать (atomic операции корректны, но логика нет).

---

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

4.1. CAS vs Mutex — микробенчмарк

package bench

import (
    "sync"
    "sync/atomic"
    "testing"
)

func BenchmarkAtomicAdd(b *testing.B) {
    var c atomic.Int64
    b.RunParallel(func(pb *testing.PB) {
        for pb.Next() {
            c.Add(1)
        }
    })
}

func BenchmarkMutexAdd(b *testing.B) {
    var mu sync.Mutex
    var c int64
    b.RunParallel(func(pb *testing.PB) {
        for pb.Next() {
            mu.Lock()
            c++
            mu.Unlock()
        }
    })
}

Результаты (Apple M1, 8 ядер, Go 1.22):

BenchmarkAtomicAdd-8    34_000_000    35 ns/op
BenchmarkMutexAdd-8      9_000_000   135 ns/op

Atomic в ~4 раза быстрее под contention. Но если убрать RunParallel (single goroutine):

BenchmarkAtomicAdd-1   500_000_000    2 ns/op
BenchmarkMutexAdd-1    200_000_000    8 ns/op

В 4 раза разница сохраняется, но в абсолюте — 2ns vs 8ns, обе быстрые.

4.2. False sharing — замер

type Counters struct {
    A atomic.Int64
    B atomic.Int64 // в той же cache line
}

type Padded struct {
    A atomic.Int64
    _ [56]byte
    B atomic.Int64
    _ [56]byte
}

При параллельных Add в A и B:

Counters (false sharing):  120 ns/op
Padded:                     38 ns/op   ← 3× быстрее

4.3. SPSC throughput

SPSC ring buffer 1024 элементов, два goroutine:

items: 100M
producer: 110M ops/sec
consumer: 110M ops/sec
latency p50: 9ns
latency p99: 18ns

chan int для сравнения (size=1024):

items: 100M
producer/consumer: 25M ops/sec
latency p50: 40ns
latency p99: 200ns

SPSC ring ~4× быстрее. Но требует point-to-point coupling и не работает с select.

4.4. atomic.Pointer COW vs sync.RWMutex+map

Config update раз в минуту, чтение 1M/sec:

RWMutex.RLock + map read:  35 ns/op
atomic.Pointer.Load:        2 ns/op    ← 17× быстрее

Чтение через atomic.Pointer (RCU-style) — почти бесплатно, потому что в кэше.

4.5. Real case 1: Prometheus counters

Prometheus client library использует atomic.Uint64 для счётчиков. Один counter может бить 10M/sec под нагрузкой. Без atomics это было бы узким горлышком.

type counter struct {
    bits atomic.Uint64
}

func (c *counter) Inc() {
    c.bits.Add(1)
}

func (c *counter) Add(v float64) {
    for {
        old := c.bits.Load()
        new := math.Float64bits(math.Float64frombits(old) + v)
        if c.bits.CompareAndSwap(old, new) {
            return
        }
    }
}

4.6. Real case 2: zap logger ring buffer

go.uber.org/zap использует MPSC очередь для асинхронной записи логов. Producer’ы (goroutines, пишущие в логгер) не блокируются на consumer’е (writer-goroutine).

4.7. Real case 3: free list в аллокаторе

sync.Pool сам по себе использует lock-free слоты для per-P storage. Под нагрузкой это даёт 10× ускорение по сравнению с глобальным mutex’ным freelist.

4.8. Когда mutex выигрывает у lock-free

• Сложная критическая секция: 10 операций, mutex дешевле, чем 10 CAS.
• Низкая contention: < 1% probability of conflict → mutex почти как atomic, но проще.
• Sleep/wait логика: с mutex + cond можно park’ить goroutines, lock-free всегда busy-loop.

4.9. Когда lock-free строго лучше

• Hot path с миллионами ops/sec.
• Real-time требования (нет park/unpark задержки).
• Метрики/счётчики (атомарный read-modify-write, не нужна транзакционность).
• SPSC/MPSC очереди в pipeline architecture.

4.10. Профилирование lock-free кода

go test -run=^$ -bench=. -cpuprofile=cpu.prof
go tool pprof cpu.prof
(pprof) top

В hot функциях ищите runtime.casgstatus, runtime.cas64, runtime/internal/atomic. Если они > 20% CPU — у вас contention на атомиках. Проверьте false sharing.

perf stat -e cache-misses,cache-references ./your_binary

Если cache-miss ratio > 5% — есть проблема с layout.

---

5. Вопросы на собесе

5.1. Что такое lock-free алгоритм?

Алгоритм, в котором на каждом шаге хотя бы один поток в системе продвигается. Нет блокировок, нет дедлоков, но возможна starvation отдельного потока. Реализуется через atomic-операции (CAS, FAA).

5.2. Чем lock-free отличается от wait-free?

В wait-free каждый поток завершает операцию за конечное число шагов независимо от других. Lock-free допускает starvation отдельного потока. Wait-free сильнее, но почти всегда медленнее и сложнее.

5.3. Что такое CAS и как он работает?

CompareAndSwap(addr, old, new) — атомарно проверяет, что *addr == old, и если да, записывает new. На x86 — LOCK CMPXCHG. Возвращает true/false. Основа всех lock-free алгоритмов.

5.4. Опишите ABA-проблему.

Поток T1 читает значение A, прерывается. T2 меняет A→B→A. T1 продолжает с CAS(A→C) — он успешен, но семантика нарушена (объект между чтением и CAS изменился). Особенно опасно с указателями и переиспользованием памяти.

5.5. Как защититься от ABA?

Tag/version counter (ptr+counter в одном слове), double-word CAS, hazard pointers, epoch-based reclamation, RCU. В Go GC частично решает проблему: пока узел жив в Go-куче, его не переиспользуют.

5.6. Что такое memory model Go?

Спецификация happens-before между goroutines. Atomic операции в Go — sequentially consistent: образуют sync edge, гарантирующий видимость записей до/после атома. Без atomic нет гарантий о видимости и порядке.

5.7. atomic.Int64 vs atomic.AddInt64(&x, …) — что лучше?

atomic.Int64 (Go 1.19+) лучше: type-safe, alignment гарантирован, нет случайных не-atomic операций. Старый API нужен для legacy кода и интероперабельности с C.

5.8. Что такое false sharing?

Два независимых счётчика лежат в одной cache line. Любое обновление одного инвалидирует кэш у владельца второго → постоянное «переливание» линии между ядрами, performance падает в 5-10 раз. Лечится padding до 64 байт.

5.9. Почему на 32-bit платформах atomic.Int64 нужно выравнивать?

Hardware на 32-bit не поддерживает atomic 64-bit на неподогнанных адресах. Go runtime требует 8-байтовое выравнивание; первое поле структуры/слайса гарантированно выровнено, остальные — на усмотрение программиста. atomic.Int64 сам выравнивает через noCopy+padding.

5.10. Что такое SPSC/MPSC/MPMC?

• SPSC — single producer, single consumer (простейший ring buffer).
• MPSC — multi producer, single consumer (Vyukov MPSC).
• MPMC — multi producer, multi consumer (Michael-Scott, LCRQ, bounded Vyukov).

Сложность нарастает; в Go MPMC обычно реализуют через chan.

5.11. Опишите SPSC ring buffer.

Кольцевой массив + head (producer) + tail (consumer). Producer пишет в buf[head%size], увеличивает head (release). Consumer читает buf[tail%size], увеличивает tail. Состояния: empty head==tail, full head-tail==size. Lock-free, ~10ns/op.

5.12. Опишите алгоритм Vyukov MPSC.

Linked list со stub-узлом. Push: создать node, atomic Swap head → prev, prev.next = node. Pop: tail.next, если nil — пусто, иначе advance. Push — wait-free. Pop — для одного reader’а.

5.13. Когда оправдан lock-free?

Hot paths с миллионами ops/sec, real-time, metrics/counters, pipeline architectures. Не оправдан при сложных критических секциях, низкой contention, ограниченной поддерживаемости команды.

5.14. Почему mutex иногда быстрее lock-free?

При низкой contention CAS внутри mutex отрабатывает сразу, мьютекс не паркует goroutine, и накладные расходы — те же. При сложных секциях один Lock дешевле 5 CAS. И mutex проще читать/отлаживать.

5.15. Что такое hazard pointers?

SMR (Safe Memory Reclamation) техника: каждый поток объявляет «hazard» — указатель, который он сейчас читает. Удаление узла откладывается, пока он встречается в чьих-то HP. Альтернатива GC в lock-free структурах.

5.16. Epoch-based reclamation — как работает?

Все потоки заходят в «эпоху». Удалённые узлы помечаются текущей эпохой. Реальное освобождение — когда все потоки прошли эпоху ≥ E+2. Используется в Crossbeam (Rust), в Go-библиотеках реже из-за GC.

5.17. Что такое RCU?

Read-Copy-Update — Linux паттерн. Writer создаёт новую копию данных, atomically swap’ает указатель. Readers продолжают видеть старую копию без блокировок. В Go — atomic.Pointer[T].CompareAndSwap. Идеально для read-heavy конфигов.

5.18. Где Go runtime использует lock-free?

Per-P run queue (runqsteal, runqget, runqput — CAS на head/tail), per-P mcache (без локов внутри P), sysmon state machine, sync.Pool.local per-P slot.

5.19. Как тестировать lock-free код?

• -race flag (race detector).
• Stress tests с миллионами итераций и тысячами goroutine.
• go test -count=100 для воспроизводимости.
• Formal verification (Spin/TLA+) для сложных алгоритмов.
• Сравнение с reference mutex-реализацией под нагрузкой.

5.20. atomic.Value vs atomic.Pointer[T] — разница?

atomic.Value — interface{} хранилище, требует один и тот же тип после первого Store (иначе panic). atomic.Pointer[T] — type-safe (generic), без boxing, эффективнее. С Go 1.19+ предпочитайте Pointer.

5.21. Объясните барьер acquire/release в Go.

В Go нет явных acquire/release, есть только sequentially consistent atomics. Любое atomic.Store имеет release-семантику (все non-atomic записи до — видны после atomic.Load). Любое atomic.Load имеет acquire-семантику.

5.22. Что произойдёт при atomic операции на nil pointer?

atomic.LoadPointer(nil) — segfault (panic в Go). Всегда проверяйте, что адрес валиден. atomic.Pointer[T].Load() возвращающее nil — не паника, это легальное значение.

5.23. Можно ли использовать atomic для синхронизации канала?

Нет. Каналы уже синхронизованы. Использование atomic вокруг канала избыточно и опасно (можно сломать happens-before гарантии Go runtime).

5.24. Что такое thundering herd и как lock-free помогает?

Thundering herd — много потоков просыпаются на один сигнал, все бьются за один ресурс. Lock-free counter (одно atomic.Inc) лучше mutex+wait, потому что нет park/unpark цикла, нет contention за wait queue.

5.25. atomic.Bool vs chan struct{} для cancel-сигнала?

• atomic.Bool — лёгкий, но не блокирующий (нужно polling).
• chan struct{} — блокирующий через <-, интегрируется в select.

Используйте chan, если нужна интеграция с select; atomic.Bool — если только одноразовый флаг без блокировки.

5.26. Опишите Treiber stack и его проблемы.

Lock-free стек: один указатель top, Push — CAS(top, old, new), Pop — CAS(top, old, old.next). Простой, но подвержен ABA (если узлы переиспользуются). В Go GC обычно защищает.

5.27. atomic.Int64.Add возвращает что?

Новое значение (после прибавления). В отличие от хардвейр-инструкций (которые часто возвращают старое), Go нормализует API.

5.28. Что такое sequentially consistent memory order?

Гипотетическое существование одного глобального линейного порядка всех atomic-операций. Любая программа видит этот порядок одинаково. Сильнейшая модель памяти, но дорогая (требует full memory fence на каждой операции).

---

6. Practice

6.1. Atomic счётчик с padding

Реализовать PaddedCounter с защитой от false sharing. Бенчмарк сравнить с обычным atomic.Int64 под параллельной нагрузкой.

6.2. SPSC ring buffer

Реализовать generic SPSCRing[T] (Push, Pop). Написать stress-test с одним producer и одним consumer на 10M элементов. Замерить latency p50, p99, p999.

6.3. MPSC очередь Vyukov

Реализовать MPSCQueue[T] с двумя методами Push (от N goroutine) и Pop (от одного). Сравнить throughput с буферизованным chan T.

6.4. RCU конфигурация

Реализовать Config с Get (wait-free read) и Update(modify func(Config) Config) (CAS-loop). Перезагружать конфиг в фоне раз в секунду.

6.5. Treiber stack + ABA reproduction

Реализовать Treiber stack. Намеренно создать ABA через sync.Pool для узлов. Воспроизвести bug. Починить через counter в указателе.

6.6. Lock-free hash counter

Map[string]*atomic.Int64. При Inc — если ключа нет, создать атомарно (через sync.Map.LoadOrStore). Сравнить с обычным mutex+map[string]int64.

6.7. atomic.Pointer COW slice

Реализовать AtomicSlice[T] с Append, Snapshot. Append копирует slice, делает CAS на указатель. Snapshot — wait-free read.

6.8. Profile false sharing

Создать 8 счётчиков в одной cache line и 8 в разных. Запустить bench, измерить cache-misses через perf stat. Документировать разницу.

---

7. Источники

1. The Go Memory Model — https://go.dev/ref/mem (официальная спецификация sync semantics).
2. sync/atomic package — https://pkg.go.dev/sync/atomic (документация, Go 1.19+ typed atomics).
3. Dmitry Vyukov, 1024cores.net — lock-free MPSC/MPMC очереди, ставшие де-факто стандартом.
4. Michael & Scott (1996) — “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms” — оригинальная MS-queue.
5. The Art of Multiprocessor Programming (Herlihy, Shavit) — каноническая книга по lock-free алгоритмам.
6. Maurice Herlihy, “Wait-Free Synchronization” (1991) — теоретическая иерархия non-blocking.
7. Linux RCU documentation — https://docs.kernel.org/RCU/ — концептуальная база для RCU-стиля в Go.
8. Go runtime source — src/runtime/proc.go (runqsteal), src/sync/pool.go (per-P storage).
9. Crossbeam (Rust) — https://github.com/crossbeam-rs/crossbeam — EBR-реализация, полезная как образец дизайна.
10. Hazard Pointers (Maged Michael) — “Safe Memory Reclamation for Dynamic Lock-Free Objects” (2004).

---

Итог Middle 2: lock-free — это не «модно», а инструмент с узкой нишей. Знайте atomics, Go memory model, ABA, false sharing. Используйте atomic.Pointer[T] для COW конфигов, SPSC ring buffer для pipeline, mutex для всего остального. Не пишите свой MPMC — берите chan или библиотеку.