ABA, False Sharing, sync.Mutex Internals: Низкоуровневые ловушки и устройство Mutex

Зачем знать на Middle 3: ABA и false sharing — это два главных источника subtle bugs и performance regressions в concurrent коде. Они проявляются под нагрузкой, race detector их не ловит, а debug может занять недели. Понимание устройства sync.Mutex (state machine, starvation mode, spin heuristic) — must-have для senior Go-разработчика: без этого вы не сможете правильно интерпретировать pprof.mutex, не поймёте contention patterns, не сможете отладить incident’ы в high-load системах. Также важно знать, как устроены runtime semaphores (база для Mutex, channels, WaitGroup), и как cache hierarchy / NUMA влияют на multi-core performance.

Содержание

Краткое введение
Глубокое погружение
- 2.1 ABA problem
- 2.2 False sharing
- 2.3 Cache lines, MESI, NUMA
- 2.4 sync.Mutex internals
- 2.5 sync.RWMutex internals
- 2.6 runtime semaphores
Gotchas
Real cases
Вопросы
Practice
Источники

1. Краткое введение

ABA problem

ABA — паттерн ошибки в lock-free алгоритмах: переменная имеет значение A, потом меняется на B, потом обратно на A. Между нашим Load и CAS другой поток сделал A → B → A. CAS пройдёт, но логически операция некорректна (потому что A “новый”, не тот, что был при Load).

False sharing — два разных поля, лежащих в одной cache line, обновляются разными CPU. Cache coherence протокол (MESI) перекидывает линию между ядрами при каждом write → 10-100x slowdown.

sync.Mutex internals

sync.Mutex в Go — не просто atomic flag. Это state machine с режимами Normal и Starvation, spin heuristic, runtime semaphore для парковки горутин. Понимание этого критично для интерпретации pprof.

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

2.1 ABA problem

2.1.1 Что это и почему опасно

Thread T1                Thread T2
---------                ---------
1. read X = A
2.                       3. CAS X: A → B
3.                       4. CAS X: B → A (same address reused?)
5. CAS X: A → B'         // succeeds, но это не тот же A!

2.1.2 Классический пример: lock-free stack pop с переиспользованием памяти

Initial state:
  head -> Node A -> Node B -> nil

T1 starts Pop():
  read head = A
  read A.next = B  ← T1 saves "next pointer is B"
  // (T1 stalled)

T2 does:
  Pop() — head = B, A's memory freed
  Pop() — head = nil, B's memory freed
  Push(new Node @ A's address) ← A's memory reused!
    A.next = nil
    head = A

T1 resumes:
  CAS(&head, A, B)  ← succeeds!
  Result: head = B, but B's memory was freed!
  Use-after-free bug.

2.1.3 ASCII схема

Time →
T1: [read X=A]----.....[CAS X=A→B' OK]  // CAS succeeded WRONGLY
T2:         [CAS A→B][CAS B→A]
                            ↑
                         X is "A" again, but it's NOT the
                         same A that T1 read (memory reused,
                         or just logically different)

2.1.4 Solutions

1) Tagged pointers (counter в high bits)

64-bit pointer:
  [ 16-bit counter | 48-bit address ]

Each modification increments counter.
A's first version: tag=0, addr=0x1234
A's second version: tag=2, addr=0x1234 (different tag!)

CAS detects the difference via tag.

В Go это сложно из-за unsafe.Pointer (только 64-bit). Workaround — struct {ptr; counter} + 128-bit CAS (требует CMPXCHG16B на x86). Go runtime использует похожую технику в runtime/lfqueue.go.

2) DCAS (Double Compare-And-Swap)

CAS на два слова одновременно: (ptr, ptr.counter). Не везде доступен hardware-wise.

3) Hazard Pointers (см. файл 09)

Поток объявляет “не освобождайте этот pointer”. Reclaimer проверяет hazard list.

4) Epoch-Based Reclamation (см. файл 09)

Защита через эпохи.

5) GC

В Go ABA реже проявляется, потому что GC удерживает объект, пока есть ссылки. НО: если переиспользуете через sync.Pool или используете unsafe.Pointer — ABA реален.

2.1.5 Пример ABA в Go с sync.Pool

package abadanger

import (
    "sync"
    "sync/atomic"
    "unsafe"
)

type Node struct {
    value int
    next  unsafe.Pointer
}

var nodePool = sync.Pool{
    New: func() any { return new(Node) },
}

type Stack struct {
    head unsafe.Pointer
}

func (s *Stack) Push(v int) {
    n := nodePool.Get().(*Node)
    n.value = v
    for {
        head := atomic.LoadPointer(&s.head)
        n.next = head
        if atomic.CompareAndSwapPointer(&s.head, head, unsafe.Pointer(n)) {
            return
        }
    }
}

func (s *Stack) Pop() (int, bool) {
    for {
        head := atomic.LoadPointer(&s.head)
        if head == nil {
            return 0, false
        }
        next := atomic.LoadPointer(&(*Node)(head).next)
        // ⚠️ Здесь окно: между LoadPointer(head.next) и CAS
        // другой поток может Pop() head, Push() ещё что-то, вернуть head в pool, Push() head обратно.
        // CAS пройдёт, но head.next теперь указывает не туда!
        if atomic.CompareAndSwapPointer(&s.head, head, next) {
            v := (*Node)(head).value
            nodePool.Put((*Node)(head)) // ← ABA: возвращаем в pool
            return v, true
        }
    }
}

⚠️ Этот код опасен. Без sync.Pool GC удержал бы node, и ABA не случилось бы. С Pool — переиспользование reuse’ит память.

2.2.1 Что это

CPU кэширует данные cache line’ами (обычно 64 байта на x86_64). Если две переменные a и b лежат в одной cache line, и core 0 пишет в a, а core 1 пишет в b:

Core 0 writes a → cache line "M" (modified) on Core 0, "I" (invalid) on Core 1
Core 1 writes b → cache miss, fetch line from Core 0 (write-back), now "M" on Core 1
Core 0 writes a → cache miss, fetch line from Core 1, ...

→ Cache line ping-pongs between cores at high frequency.
→ Bandwidth wasted, 10-100x slowdown.

Cache line точно — 64 байта на x86_64 (можно проверить через getconf LEVEL1_DCACHE_LINESIZE). На Apple M1 — 128 байт. На некоторых ARM — 64 или 128.

2.2.2 ASCII схема

Without padding (BAD):
  Cache line (64 bytes):
  [ counterA | counterB | ... ]
       ^         ^
    Core 0    Core 1
    writes    writes

  Result: cache line bouncing, MESI thrashing.

With padding (GOOD):
  Cache line 0:
  [ counterA | padding (56 bytes) ]
  Cache line 1:
  [ counterB | padding (56 bytes) ]
       ^                ^
    Core 0           Core 1
    writes           writes

  Result: independent cache lines, no contention.

2.2.3 Пример bench

package falsesharing

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

// BAD: counters in same cache line
type CountersBad struct {
    a atomic.Int64
    b atomic.Int64
}

// GOOD: counters separated
type CountersGood struct {
    a   atomic.Int64
    _   [56]byte // pad to 64-byte alignment
    b   atomic.Int64
    _   [56]byte
}

func BenchmarkBad(b *testing.B) {
    var c CountersBad
    var wg sync.WaitGroup
    wg.Add(2)
    go func() {
        defer wg.Done()
        for i := 0; i < b.N; i++ {
            c.a.Add(1)
        }
    }()
    go func() {
        defer wg.Done()
        for i := 0; i < b.N; i++ {
            c.b.Add(1)
        }
    }()
    wg.Wait()
}

// Аналогично для CountersGood

Реальные цифры:

CountersBad: ~50 ns/op под 2 ядрами.
CountersGood: ~5 ns/op (10x speedup).

2.2.4 Detection

Linux: perf c2c (Cache-to-Cache events). Показывает HITM (Hit Modified) events — индикатор false sharing.

perf c2c record ./mybinary
perf c2c report

Intel VTune: more sophisticated, показывает на уровне cache lines.

Go: нет встроенного инструмента, но можно через perf (Linux), dtrace (macOS), Intel VTune (cross-platform).

Бенчмарк-based detection: запустите на 1, 2, 4, 8 cores. Если scaling нелинейный — подозревайте false sharing.

2.2.5 Avoidance

1) Manual padding:

type Counter struct {
    v   atomic.Int64
    _   [56]byte // pad to 64 bytes
}

⚠️ Компилятор может оптимизировать unused fields. Безопаснее — использовать [N]byte array, который имеет address.

2) golang.org/x/sys/cpu.CacheLinePad:

import "golang.org/x/sys/cpu"

type Counter struct {
    _ cpu.CacheLinePad // 64 or 128 bytes depending on arch
    v atomic.Int64
}

Преимущество: автоматически правильный размер для платформы (на Apple M1 — 128 байт).

3) Struct field reordering:

Если два поля редко обновляются вместе, и одно read-mostly, второе write-mostly — расположите их в разных cache lines.

4) atomic.Int64 alignment (Go 1.19+):

С Go 1.19 типы atomic.Int64, atomic.Uint64, atomic.Pointer авто-выравниваются на 8 байт. До 1.19 на 32-bit ARM это было проблемой.

5) Per-CPU sharded structures:

type ShardedCounter struct {
    shards []paddedCounter
}

type paddedCounter struct {
    v atomic.Int64
    _ [56]byte
}

Каждый shard в своей cache line.

2.2.6 Anti-pattern: padding в map values

// BAD: map values are not cache-line aligned regardless of padding
type Stats struct {
    v atomic.Int64
    _ [56]byte
}

m := make(map[string]*Stats)

Объекты в heap, padding в struct работает только если объект сам выровнен. В Go все аллокации выровнены на 8 байт, но не на 64. Для гарантии нужны custom allocator или runtime.MemStats (не доступно user-side).

2.3 Cache lines & NUMA

2.3.1 Cache hierarchy

+--------+   +--------+   +--------+   +--------+
| Core 0 |   | Core 1 |   | Core 2 |   | Core 3 |
|  L1d   |   |  L1d   |   |  L1d   |   |  L1d   |
|  32KB  |   |  32KB  |   |  32KB  |   |  32KB  |
+--------+   +--------+   +--------+   +--------+
     |            |            |            |
+--------+   +--------+   +--------+   +--------+
|   L2   |   |   L2   |   |   L2   |   |   L2   |
|  256KB |   |  256KB |   |  256KB |   |  256KB |
+--------+   +--------+   +--------+   +--------+
     |            |            |            |
+-------------------------------------------------+
|                   L3 (shared)                    |
|                     16-32MB                      |
+-------------------------------------------------+
     |
+-------------------------------------------------+
|                    DRAM (100s GB)                |
+-------------------------------------------------+

Access latencies (approx):
  L1d:  ~1 ns
  L2:   ~3-5 ns
  L3:   ~12-20 ns
  DRAM: ~80-100 ns
  NUMA remote: ~150-200 ns

2.3.2 MESI protocol

Cache coherence на multi-core:

States:
  M = Modified  (dirty, only this core has it)
  E = Exclusive (clean, only this core has it)
  S = Shared    (clean, multiple cores have it)
  I = Invalid   (not in this cache)

Transitions (simplified):
  M → S: another core reads
  M → I: another core writes
  S → M: this core writes (other copies become I)
  E → M: this core writes
  ...

False sharing вызывает M↔I ping-pong → катастрофическое падение performance.

MOESI — расширенная версия с состоянием Owned (одна копия в Modified, другие в Shared, owner отвечает за write-back).

MESIF — добавляет Forward (определяет, кто отвечает на read request, чтобы не было multiple snoop hits).

2.3.3 NUMA (Non-Uniform Memory Access)

На multi-socket системах:

+----------------+      +----------------+
| Node 0         |      | Node 1         |
|   CPU 0-7      | <--> |   CPU 8-15     |
|   DRAM (local) |      |   DRAM (local) |
+----------------+      +----------------+

Access latency:
  Local DRAM:  ~80 ns
  Remote DRAM: ~150-200 ns (across QPI/UPI link)

Go и NUMA: Go не делает NUMA-aware scheduling. Все горутины могут мигрировать между nodes произвольно. Это упрощает runtime, но на NUMA boxes снижает performance.

Workarounds:

taskset (Linux) — pin процесс к node.
numactl --membind — bind memory к node.
Несколько Go процессов, по одному на NUMA node.
В крайних случаях — runtime.LockOSThread() + manual pinning через cgo + pthread_setaffinity (HACK).

Бенчмарк impact: на серверах с 2+ NUMA nodes Go программы могут показывать 30-50% degradation vs C/C++ с явным NUMA pinning. Это известная проблема.

2.4 sync.Mutex internals

2.4.1 State field

sync.Mutex в Go:

type Mutex struct {
    state int32  // битовое поле
    sema  uint32 // адрес для runtime semaphore
}

state — битовое поле:

Bit 0:    locked       (mutex is held)
Bit 1:    woken        (a goroutine is woken up to acquire)
Bit 2:    starving     (mutex is in starvation mode)
Bits 3-31: waiterShift (count of waiters)

+----------+----------+----------+-------------------+
| starving |  woken   | locked   | waiters (29 bits) |
|  1 bit   |  1 bit   | 1 bit    |                   |
+----------+----------+----------+-------------------+
   bit 2     bit 1      bit 0       bits 3..31

2.4.2 Normal mode

При Lock():

Fast path: CAS(state, 0, locked). Если успех — done.
Slow path:
- Спин (до 4 итераций) если: multi-CPU, active spinners < GOMAXPROCS/2, P has no other G.
- Если не получил — увеличить waiter count, parkировать через runtime.semacquire.
- При парковке запомнить время начала ожидания.
При unpark проверить, как долго ждал.
Если waited > 1ms — switch to starvation mode.

2.4.3 Starvation mode (Go 1.9+)

Введён, потому что в Normal mode новые arriving goroutines могут “украсть” lock у waiter’ов через spin/CAS, вызывая waiter starvation.

В Starvation mode:

При unlock’е mutex передаётся напрямую первому waiter’у в очереди (no spin, no CAS by newcomers).
Newcomers сразу парк, не спинят.
Lock остаётся в starvation mode, пока:
- Waiter получил lock < 1ms (значит contention снизилась).
- Очередь пустая.

Normal mode:               Starvation mode:
[Lock arrives] → spin       [Lock arrives] → park immediately
[Lock available] → CAS      [Lock available] → handoff to head of queue
                                                (no contention)

⚠️ Starvation mode снижает throughput (нет batching, нет spin), но гарантирует fairness. Trade-off in favor of tail latency.

2.4.4 Spin heuristic

sync_runtime_canSpin (в runtime/proc.go):

return spinCount < 4 &&
       ncpu > 1 &&
       active_spinning < GOMAXPROCS/2 &&
       p.runnext == 0 && p.local_queue_empty()

Условия:

spinCount < 4: не более 4 итераций.
ncpu > 1: на single-CPU спин бессмыслен.
active_spinning < GOMAXPROCS/2: ограничить число одновременно спинящих горутин.
p has no other G: если у P есть другая G, лучше переключиться на неё, чем спинить.

2.4.5 Unlock fast path

func (m *Mutex) Unlock() {
    new := atomic.AddInt32(&m.state, -mutexLocked)
    if new != 0 {
        // slow path
        m.unlockSlow(new)
    }
}

Fast path: один atomic. Slow path вызывается, если:

Есть waiter’ы (waiter count > 0).
Или mutex в starvation mode (нужен handoff).

2.4.6 ASCII схема state transitions

state = 0 (free)
    │
    │ CAS(0 → locked) — Lock() fast path
    ↓
state = locked
    │
    │ Lock() arrives → spin or park
    ↓
state = locked + woken + waiters++
    │
    │ Unlock() — atomic.Add(-locked) + signal sema
    ↓
state = waiters>0
    │
    │ Wake up waiter → CAS to lock
    ↓
state = locked (woken cleared) ...

Если waiter ждал > 1ms — set starving bit:
state = locked + starving
    │
    │ Unlock() in starvation mode → direct handoff
    │ (no CAS race with newcomers)
    ↓
state = locked (passed to next waiter)

2.4.7 Profile: `-mutexprofile`

go test -mutexprofile=mutex.out -mutexprofilefraction=1
go tool pprof -text mutex.out

mutexprofilefraction — sample ratio (1 = sample every contention event). Дорого, не использовать в production без думалки.

Включить в runtime:

import "runtime"
runtime.SetMutexProfileFraction(100) // sample 1 in 100

Что показывает pprof.mutex:

Сколько времени другие горутины ждали на mutex.
Не время удержания, а время ожидания.

2.5 sync.RWMutex internals

type RWMutex struct {
    w           Mutex        // held if there are pending writers
    writerSem   uint32       // semaphore for writers to wait for completing readers
    readerSem   uint32       // semaphore for readers to wait for completing writers
    readerCount atomic.Int32 // number of pending readers
    readerWait  atomic.Int32 // number of departing readers
}

2.5.1 RLock

readerCount++
if readerCount < 0:
    // writer is pending, wait
    park on readerSem

readerCount может стать negative — это сигнал “writer pending”:

Lock() делает readerCount.Add(-rwmutexMaxReaders).
Это превращает readerCount в большое отрицательное.
Новые reader’ы видят negative → парк.

2.5.2 Lock (writer)

1. Acquire w.Lock() (only one writer at a time)
2. r = readerCount.Add(-rwmutexMaxReaders) + rwmutexMaxReaders
   // r = number of active readers before this Lock
3. if r != 0 and readerWait.Add(r) != 0:
   // wait for all current readers to RUnlock
   park on writerSem

2.5.3 RUnlock

r = readerCount.Add(-1)
if r < 0:
    // writer is waiting, decrement readerWait
    if readerWait.Add(-1) == 0:
        // last departing reader, wake writer
        runtime.Semrelease(&writerSem)

2.5.4 Unlock (writer)

r = readerCount.Add(rwmutexMaxReaders)
// wake all pending readers
for i := 0; i < r; i++ {
    runtime.Semrelease(&readerSem)
}
w.Unlock()

2.5.5 Writer-preferring

Если writer ждёт, новые reader’ы блокируются (видят negative readerCount). Это предотвращает writer starvation, но может вызвать reader starvation при постоянных writers.

⚠️ Gotcha: RWMutex дороже Mutex при низкой contention. Если у вас редкие writes — RWMutex выгоден. Если 50/50 — Mutex быстрее.

2.6 runtime semaphores

Внутренний механизм Go runtime. Основа для sync.Mutex, sync.Cond, channel send/recv block.

2.6.1 Структура

// в runtime/sema.go
type semaRoot struct {
    lock  mutex          // protect treap
    treap *sudog         // root of balanced BST (sudog = sleeping goroutine)
    nwait atomic.Uint32  // number of waiters
}

var semtable [semTabSize]struct {
    root semaRoot
    pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

semtable — глобальный массив semaRoot’ов (типичный размер 251). Адрес семафора *uint32 хэшируется в index в semtable. Это для шардирования lock contention.

2.6.2 semacquire / semrelease

func runtime.Semacquire(s *uint32) {
    // 1. Fast path: try to decrement *s if > 0
    if *s > 0 && atomic.CompareAndSwap(s, *s, *s - 1) {
        return
    }
    // 2. Slow path: park
    root := semroot(s)
    root.lock()
    *s -= 1
    if *s >= 0:
        // someone released between fast path and lock
        root.unlock()
        return
    // park goroutine
    gp := acquireSudog()
    gp.elem = unsafe.Pointer(s)
    root.queue(s, gp)
    goparkunlock(&root.lock, "semacquire", traceEvBlock, 4)
}

func runtime.Semrelease(s *uint32, handoff bool) {
    *s += 1
    root := semroot(s)
    root.lock()
    if root.nwait == 0:
        // no waiters
        root.unlock()
        return
    // dequeue and wake
    gp := root.dequeue(s)
    if handoff:
        gp.elem = nil // direct handoff
    root.unlock()
    goready(gp.g, 4)
}

2.6.3 Treap

semaRoot.treap — это treap (balanced binary search tree by key=address and priority=random). Каждая нода — sudog (sleeping goroutine descriptor). Ноды по тому же адресу образуют list внутри treap node.

При Semrelease:

Найти treap node по s (адресу).
Взять первого sudog из его list.
Wake его горутину.

Это даёт O(log N) acquire/release где N — число различных адресов с waiter’ами.

2.6.4 Trace

go test -trace=trace.out записывает события goWaitSemacquire, goWaitSemrelease, можно анализировать в go tool trace.

3. Gotchas

⚠️ ABA в Go с sync.Pool. Pool переиспользует объекты — типичный ABA scenario для lock-free стэков/очередей. Если используете Pool + unsafe.Pointer — внимательно.
⚠️ False sharing в struct fields. Поля рядом в struct = одна cache line. Между atomic.Int64 поля нужно [56]byte padding или cpu.CacheLinePad.
⚠️ Compiler может выкинуть padding. Используйте [N]byte (array), не неиспользуемые типы. Array всегда занимает место.
⚠️ atomic.Int64 НЕ автоматически выровнен на cache line. Он выровнен на 8 байт. Cache line — 64 байта. False sharing возможен между соседними atomic.Int64.
⚠️ Apple M1 cache line = 128 байт. Если хардкодите [56]byte (для 64-byte line), на M1 будете иметь false sharing. Используйте cpu.CacheLinePad.
⚠️ sync.RWMutex имеет негативный readerCount как маркер. Если случайно увеличите счётчик через unsafe — нарушите invariant.
⚠️ Starvation mode в Mutex активируется при 1ms ожидания. Если у вас короткие критические секции, но плотная contention — никогда не достигнете 1ms, и starvation mode не сработает. Иногда это причина reader starvation в production.
⚠️ runtime.SetMutexProfileFraction(1) в production = огромный overhead. Используйте 100 или 1000 (sample 1 in N events).
⚠️ NUMA effects невидимы локально. На laptop’е (1 socket) NUMA не проявляется. На production server’е (2+ sockets) — внезапный 50% slowdown без видимых причин.
⚠️ sync.Mutex нельзя копировать после первого использования. go vet ловит copy by value, но не все случаи (например, через reflection или interface boxing).
⚠️ Mutex’s spin path не для long critical sections. Если в hot path mutex держится > 1µs, spin не помогает — горутины парк сразу. Уменьшайте critical section.
⚠️ Cond с RWMutex — bug. sync.NewCond требует sync.Locker. RWMutex реализует Locker (через Lock/Unlock, не RLock/RUnlock), поэтому Cond с RWMutex технически работает, но semantics confusing. Используйте Mutex.
⚠️ runtime.semacquire через linkname в внешнем пакете. С Go 1.23 ужесточены проверки. Может перестать работать в minor релизе.
⚠️ Treap в semtable означает все семафоры — глобальный shared state. Под массивной contention (миллионы waiters) — bottleneck. Это редкий сценарий, но возможен.
⚠️ atomic.Pointer[T] Zero value = nil pointer. Load() вернёт nil. Dereference = panic. Всегда инициализируйте или проверяйте.

4. Real cases

В ранних версиях prometheus/client_golang counter / gauge структуры имели atomic.Uint64 подряд. Под высокой нагрузкой (миллион increment/sec) — false sharing → 5-10x slowdown. Fix: добавили padding между metric fields.

4.2 ABA в Aerospike client (Go)

aerolab/aerospike-client-go имел subtle ABA bug в connection pool. Connection из pool возвращался, реюзался, и в lock-free pool stack происходил use-after-recycle. Fix: switched to mutex-protected pool.

4.3 Starvation mode разрулил production incident в Uber

Pre-Go 1.9 (без starvation mode) Uber имел production случай: 1 writer + 1000 readers. Reader continuously arriving → writer ждал минутами → cascading failure. Go 1.9’s starvation mode для Mutex и аналогично для RWMutex резко улучшил tail latency.

4.4 NUMA effects в etcd

etcd в крупных production deployments (3-5 нод, каждая на multi-socket server) показывал unexpected latency. Причина — Go scheduler мигрирует горутины между NUMA nodes. Workaround: запуск etcd с taskset к одному node.

4.5 sync.Mutex contention в Docker daemon

Docker daemon имел один глобальный mutex для container state. Под нагрузкой (создание 1000 containers/sec) — mutex был bottleneck. Решение: sharded locks per-container (одна mutex per container).

4.6 cache line padding в Go runtime’s mcache

runtime/mcache.go использует cache line padding для per-P структур, чтобы избежать false sharing при concurrent allocation. Каждый P имеет свой mcache, выровненный на cache line.

5. Вопросы

Что такое ABA problem и почему опасна?
Значение A → B → A между Load и CAS другого потока. CAS пройдёт, но логически операция некорректна. Опасна в lock-free алгоритмах с manual memory management.
Как защититься от ABA?
Tagged pointers (counter в high bits), DCAS, Hazard Pointers, EBR, или GC (в Go обычно достаточно).
Безопасны ли lock-free структуры в Go от ABA?
Обычно да, благодаря GC. Но НЕ если переиспользуете объекты через sync.Pool или используете unsafe.Pointer арифметику.
Что такое false sharing?
Два разных поля в одной cache line обновляются разными CPU → MESI ping-pong → 10-100x slowdown.
Как обнаружить false sharing?
perf c2c (Linux), Intel VTune, бенчмарк с разным числом cores (нелинейный scaling — индикатор).
Как избежать false sharing?
Padding ([56]byte), cpu.CacheLinePad, struct field reordering, per-CPU sharding.
Какой размер cache line на x86_64? На Apple M1?
x86_64: 64 байта. Apple M1: 128 байт. ARM64: обычно 64, но может быть 128.
Что делает MESI протокол?
Cache coherence: гарантирует, что multiple cores имеют consistent view of memory. Состояния Modified/Exclusive/Shared/Invalid.
Что такое NUMA?
Non-Uniform Memory Access: на multi-socket системах память каждого socket’а ближе к “своим” CPU. Remote access в 2-3 раза медленнее.
Делает ли Go NUMA-aware scheduling?
Нет. Горутины могут мигрировать между NUMA nodes произвольно. На multi-socket box’ах это снижает performance.
Что такое state field в sync.Mutex?
Битовое поле: bit 0 = locked, bit 1 = woken, bit 2 = starving, bits 3-31 = waiter count.
Что такое starvation mode в Mutex?
Активируется, если waiter ждал > 1ms. В этом режиме unlock делает direct handoff к первому waiter’у (нет spin, нет CAS race с newcomers). Гарантирует fairness в ущерб throughput.
Когда Go’s Mutex спинит?
Условия: multi-CPU, active spinners < GOMAXPROCS/2, P has no other G, not more than 4 iterations. Спин помогает при коротких critical sections.
Что такое mutexprofilefraction?
Sample ratio для mutex contention profiling. 1 = sample every event (дорого). 100 = sample 1 in 100. Использовать с осторожностью в production.
Что показывает pprof.mutex?
Время, которое другие горутины ждали на mutex’е. НЕ время удержания.
Чем sync.RWMutex дороже sync.Mutex?
Больше atomic операций (readerCount, readerWait), больше state polnoct. При низкой contention или mostly writes — sync.Mutex быстрее.
Как RWMutex понимает, что writer ждёт?
readerCount уходит в negative (через Add(-rwmutexMaxReaders)). Новые reader’ы видят negative → парк.
Что такое runtime.semacquire?
Внутренний семафор Go runtime. По адресу *uint32. Используется sync.Mutex (через slow path), channel block, WaitGroup, sync.Cond.
Что такое semtable?
Глобальный массив semaRoot’ов (251 элемент). Адрес семафора хэшируется в index. Шардирует lock contention.
Что такое treap в semaRoot?
Balanced BST (по адресу), randomized priorities. Хранит waiting goroutines (sudog). O(log N) acquire/release.
Можно ли использовать runtime.semacquire напрямую?
Через //go:linkname — да, но это unsupported API. Может сломаться при обновлении Go.
Что такое handoff в Mutex?
Direct transfer ownership к следующему waiter’у без spin/CAS race. Используется в starvation mode.
Почему sync.Mutex нельзя копировать после Lock?
Внутренние pointer’ы и state становятся inconsistent. go vet ловит большинство случаев.
Чем atomic.Int64.Add отличается от atomic.AddInt64?
Семантически идентичны. Int64.Add — метод на типизированном atomic.Int64 (с Go 1.19). atomic.AddInt64 — функция на *int64. Используйте typed (новый).
Что такое cache line bouncing?
Multiple cores конкурируют за одну cache line через MESI. Линия пересылается между cores при каждом write → высокий traffic → slow.

6. Practice

6.1 Демонстрация ABA через sync.Pool

Напишите lock-free stack, использующий sync.Pool для нод. Создайте сценарий ABA: один поток Pop’ит, другой Push’ит ту же node. Проверьте, что CAS даёт incorrect result.

Создайте два counter struct: с padding и без. Бенчмарк под 2/4/8 ядер. Должны увидеть 5-10x разницу.

6.3 sync.Mutex state inspection

Через reflect или unsafe извлеките state field из sync.Mutex. Напишите функцию, которая декодирует биты и печатает: “locked, X waiters, starving=true/false”.

6.4 RWMutex contention под reader-heavy

Бенчмарк: 1 writer + 1, 4, 16, 64 readers. Покажите, как scaling меняется. Используйте sync.Map для сравнения.

6.5 Implement custom Mutex с metrics

Создайте Mutex, который записывает время удержания и contention в histogram (например, prometheus.Histogram). Полезно для debug.

6.6 NUMA-aware sharded counter

На multi-socket Linux box’е: попробуйте через cgo + sched_setaffinity сделать NUMA-aware sharding. Сравните с регулярным sharding.

6.7 ABA с tagged pointers

Реализуйте 128-bit CAS (через CGo или assembly). Используйте для lock-free стэка с tagged pointers. Сравните overhead с обычным CAS.

6.8 Mutex profile analysis

Возьмите свой проект, запустите -mutexprofile=mutex.out -mutexprofilefraction=10. Проанализируйте go tool pprof. Найдите top 3 contention point’а.

7. Источники

Go source code: src/sync/mutex.go, src/sync/rwmutex.go, src/runtime/sema.go.
Dmitry Vyukov, “Go scheduler: Implementing language” — talks на dotGo / GopherCon.
Russ Cox, Go Memory Model — официальная документация.
Maurice Herlihy, Nir Shavit, “The Art of Multiprocessor Programming” — главы 7 (spinning), 8 (queues), 10 (linearizability), 11 (lock-free).
Intel, 64-IA-32 Architectures Optimization Reference Manual — cache hierarchy, MESI.
Paul McKenney, “Is Parallel Programming Hard?” — memory ordering, NUMA, RCU.
Folly — production C++ библиотека с padding, hazptr, EBR.
Linux kernel Documentation/memory-barriers.txt — memory ordering basics.
golang.org/x/sys/cpu — CacheLinePad, CacheLineSize.
Bryan Cantrill, talks про DTrace, NUMA, false sharing.
John Hennessy, David Patterson, “Computer Architecture: A Quantitative Approach” — главы про cache coherence.
perf c2c tutorial — detection false sharing.
Go issue tracker: #16589 (mutex starvation mode), #37753 (atomic.Int64 alignment Go 1.19).
GitHub: Aerospike Go client incident — реальный ABA case study.