Custom Sync Primitives: Building Your Own Concurrency Tools

Зачем знать на Middle 3: стандартная библиотека sync покрывает 90% случаев, но в high-performance системах (БД, кэши, networking) встречаются ситуации, где стандартные примитивы становятся узким местом или просто не подходят семантически. Middle 3 / Senior должен уметь: (1) реализовать spinlock, ticket lock, RWMutex с fairness, custom semaphore; (2) понимать как устроены runtime/sema и gopark; (3) знать memory ordering и atomic operations; (4) уметь профилировать contention и понимать когда custom primitive оправдан. Без этого вы не сможете дебажить production-инциденты в gRPC, fasthttp, BoltDB и других системах, где такие примитивы используются.

Содержание

1. Краткое введение
2. Глубокое погружение
   • 2.1 Building blocks: atomic, runtime/sema, gopark
   • 2.2 Spinlock
   • 2.3 Ticket lock (fairness)
   • 2.4 Custom RWMutex (reader/writer preference)
   • 2.5 Custom Cond с timeout
   • 2.6 Bounded buffer (channel-based)
   • 2.7 RWMutex с fairness
   • 2.8 RCU-like read-mostly
   • 2.9 Weighted / Priority semaphore
   • 2.10 Hierarchical lock для DAG
   • 2.11 Lock-free linked list
   • 2.12 Wait-free / sharded counters
   • 2.13 Backoff strategies
3. Gotchas
4. Real cases
5. Вопросы
6. Practice
7. Источники

---

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

Custom sync primitive — это собственная реализация механизма синхронизации, выходящая за рамки sync.{Mutex,RWMutex,Cond,WaitGroup,Once} и sync/atomic. Обычно строится поверх:

• atomic operations: CAS (Compare-And-Swap), LL/SC, fetch-and-add.
• runtime semaphores: runtime.semacquire / semrelease (через //go:linkname).
• gopark / goready: парковка горутины без OS-thread context switch.
• channels: для bounded-структур или sequencing.

Когда стоит писать свой примитив

Ситуация	Стандартный примитив	Custom
Простой shared state	sync.Mutex	—
Read-heavy, низкая contention	sync.RWMutex	—
Read-heavy, высокая contention, writer rare	RWMutex слишком тяжёл	RCU/atomic.Pointer copy-on-write
Counter	atomic.Int64	sharded counter (per-CPU)
Bounded queue с fairness	channel	ring buffer (LMAX-style)
Spinlock для очень короткой критической секции	sync.Mutex парк/разпарк дорог	spinlock + PAUSE
Priority-based locking	—	priority queue + sema

Главное правило

“Сначала измерь — потом оптимизируй”. sync.Mutex в Go 1.22 имеет sophisticated starvation mode, спин-эвристику и runtime integration. Custom primitive легко сделать медленнее при низкой contention.

---

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

2.1 Building blocks

2.1.1 Atomic operations

В Go 1.19+ — пакет sync/atomic с типизированными атомиками:

import "sync/atomic"

var x atomic.Int64
x.Add(1)
old := x.Load()
swapped := x.CompareAndSwap(old, old+1) // CAS

// До Go 1.19 — функции:
// atomic.AddInt64(&x, 1)
// atomic.LoadInt64(&x)
// atomic.CompareAndSwapInt64(&x, old, new)

Memory ordering (с Go 1.19 memory model доку обновили):

• Load — acquire semantics
• Store — release semantics
• Swap, Add, CAS — sequentially consistent (full barrier)

Это означает: после x.Load() все последующие операции “видят” то, что было записано перед соответствующим x.Store(). Аналог memory_order_acquire/release в C++.

2.1.2 runtime/sema (semaphores)

Внутренний механизм Go runtime. Доступ через //go:linkname:

package mypkg

import (
    _ "unsafe" // нужен для linkname
)

//go:linkname runtime_Semacquire sync.runtime_Semacquire
func runtime_Semacquire(s *uint32)

//go:linkname runtime_Semrelease sync.runtime_Semrelease
func runtime_Semrelease(s *uint32, handoff bool, skipframes int)

⚠️ Warning: //go:linkname — это unsupported API. Может сломаться в любом minor релизе. Использовать только если очень надо (как делают golang.org/x/sync/semaphore исторически).

2.1.3 gopark / goready

Используются runtime для парковки горутин без участия OS:

gopark(unlockf, lock, reason, traceEv, traceskip)
  → горутина переходит в _Gwaiting
  → P переключается на другую G
  → нет system call

goready(gp, traceskip)
  → горутина возвращается в _Grunnable
  → попадает в local или global run queue

В пользовательском коде напрямую не вызываются. Реализуются через channels и runtime/sema.

2.2 Spinlock — busy wait

Простейший lock. Используется когда критическая секция очень короткая (< 100 ns), и парковка горутины дороже спина.

package spinlock

import (
    "runtime"
    "sync/atomic"
)

type Spinlock struct {
    state atomic.Int32 // 0 = unlocked, 1 = locked
}

func (s *Spinlock) Lock() {
    for !s.state.CompareAndSwap(0, 1) {
        runtime.Gosched() // yield P (важно для cooperative scheduling)
    }
}

func (s *Spinlock) Unlock() {
    s.state.Store(0)
}

Проблемы наивного spinlock:

1. Cache line bouncing: CAS на одной cache line с N горутин → MESI протокол ping-pong’ит линию между cores → throughput падает.
2. Fairness отсутствует: горутина, которая активнее CAS’ит, выиграет.
3. CPU heat: busy wait жжёт ватты.

Улучшения:

// TTAS (Test-And-Test-And-Set) — сначала Load, потом CAS
func (s *Spinlock) Lock() {
    for {
        // Сначала просто Load (не вызывает invalidation линии)
        if s.state.Load() == 0 {
            if s.state.CompareAndSwap(0, 1) {
                return
            }
        }
        runtime.Gosched()
    }
}

С backoff:

func (s *Spinlock) Lock() {
    backoff := 1
    for !s.state.CompareAndSwap(0, 1) {
        for i := 0; i < backoff; i++ {
            // x86: PAUSE intrinsic; в Go — runtime.procyield(1)
            // нет прямого доступа, но runtime.Gosched() подходит
        }
        runtime.Gosched()
        if backoff < 1024 {
            backoff <<= 1
        }
    }
}

⚠️ В Go spinlock редко оправдан, потому что sync.Mutex уже спинит до парковки (до 4 итераций с активными спиннерами < GOMAXPROCS/2). Использовать только если измерено, что mutex медленнее.

2.3 Ticket lock — fairness

Каждый поток получает “билет” (номер очереди) и ждёт, пока serving достигнет его номера. FIFO порядок гарантирован.

package ticketlock

import (
    "runtime"
    "sync/atomic"
)

type TicketLock struct {
    next    atomic.Uint64 // следующий выдаваемый билет
    serving atomic.Uint64 // текущий обслуживаемый билет
}

func (t *TicketLock) Lock() {
    myTicket := t.next.Add(1) - 1 // atomic fetch-and-add
    for t.serving.Load() != myTicket {
        runtime.Gosched()
    }
}

func (t *TicketLock) Unlock() {
    t.serving.Add(1)
}

Плюсы:

• Strict FIFO (нет starvation).
• Простая семантика.

Минусы:

• Все потоки крутятся на serving, что вызывает cache line bouncing.
• Решается через MCS lock (queue of local nodes), но в Go его сложнее реализовать (нужен per-goroutine storage).

2.4 Custom RWMutex с writer preference

sync.RWMutex в Go — writer-preferring, но в edge cases (много reader’ов) writer может ждать долго. Сделаем свой с явным writer preference и timeout:

package rwmutex

import (
    "errors"
    "sync"
    "sync/atomic"
    "time"
)

var ErrTimeout = errors.New("rwmutex: timeout")

type RWMutex struct {
    mu             sync.Mutex
    readerCount    int32
    writerWaiting  int32
    readerCond     *sync.Cond
    writerCond     *sync.Cond
}

func New() *RWMutex {
    m := &RWMutex{}
    m.readerCond = sync.NewCond(&m.mu)
    m.writerCond = sync.NewCond(&m.mu)
    return m
}

func (m *RWMutex) RLock() {
    m.mu.Lock()
    for m.writerWaiting > 0 || m.readerCount == -1 {
        m.readerCond.Wait()
    }
    m.readerCount++
    m.mu.Unlock()
}

func (m *RWMutex) RUnlock() {
    m.mu.Lock()
    m.readerCount--
    if m.readerCount == 0 && m.writerWaiting > 0 {
        m.writerCond.Signal()
    }
    m.mu.Unlock()
}

func (m *RWMutex) Lock() {
    m.mu.Lock()
    atomic.AddInt32(&m.writerWaiting, 1)
    for m.readerCount != 0 {
        m.writerCond.Wait()
    }
    m.readerCount = -1 // -1 = writer holds lock
    atomic.AddInt32(&m.writerWaiting, -1)
    m.mu.Unlock()
}

func (m *RWMutex) Unlock() {
    m.mu.Lock()
    m.readerCount = 0
    if m.writerWaiting > 0 {
        m.writerCond.Signal()
    } else {
        m.readerCond.Broadcast()
    }
    m.mu.Unlock()
}

Сложность с timeout — sync.Cond.Wait() не поддерживает timeout. Нужен workaround через select на channel:

func (m *RWMutex) RLockTimeout(d time.Duration) error {
    done := make(chan struct{})
    go func() {
        m.RLock()
        close(done)
    }()
    select {
    case <-done:
        return nil
    case <-time.After(d):
        // ⚠️ горутина продолжит ждать!
        // в реальности надо more sophisticated design
        return ErrTimeout
    }
}

⚠️ Gotcha: горутина, которая стартанула RLock(), продолжит ждать даже после timeout. Решение — использовать channel-based mutex.

2.5 Channel-based Mutex с timeout

type ChannelMutex struct {
    c chan struct{}
}

func NewChannelMutex() *ChannelMutex {
    c := make(chan struct{}, 1)
    c <- struct{}{} // initial token
    return &ChannelMutex{c: c}
}

func (m *ChannelMutex) Lock() {
    <-m.c
}

func (m *ChannelMutex) TryLock() bool {
    select {
    case <-m.c:
        return true
    default:
        return false
    }
}

func (m *ChannelMutex) LockTimeout(d time.Duration) error {
    select {
    case <-m.c:
        return nil
    case <-time.After(d):
        return ErrTimeout
    }
}

func (m *ChannelMutex) LockContext(ctx context.Context) error {
    select {
    case <-m.c:
        return nil
    case <-ctx.Done():
        return ctx.Err()
    }
}

func (m *ChannelMutex) Unlock() {
    select {
    case m.c <- struct{}{}:
    default:
        panic("unlock of unlocked mutex")
    }
}

Плюсы:

• Поддерживает timeout, context, TryLock.
• Semantically clear.

Минусы:

• Медленнее sync.Mutex (channel overhead ~50-100 ns vs ~25 ns для Mutex).
• Каждый Lock() парковает горутину (нет spin).

2.6 Bounded buffer (channel-based vs ring buffer)

Простейший bounded buffer — buffered channel:

buf := make(chan Item, capacity)
buf <- item // blocks if full
item := <-buf // blocks if empty

Но для high-throughput (millions ops/sec) channel overhead заметен. Альтернатива — ring buffer:

package ringbuf

import (
    "runtime"
    "sync/atomic"
)

type RingBuffer struct {
    buf     []interface{}
    mask    uint64 // capacity - 1, capacity = 2^N

    // Padding для cache line separation
    _pad1   [56]byte
    head    atomic.Uint64
    _pad2   [56]byte
    tail    atomic.Uint64
    _pad3   [56]byte
}

func NewRingBuffer(capacityPow2 int) *RingBuffer {
    cap := 1 << capacityPow2
    return &RingBuffer{
        buf:  make([]interface{}, cap),
        mask: uint64(cap - 1),
    }
}

func (r *RingBuffer) Push(v interface{}) 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
    return true
}

func (r *RingBuffer) Pop() (interface{}, bool) {
    tail := r.tail.Load()
    head := r.head.Load()
    if tail >= head {
        return nil, false // empty
    }
    v := r.buf[tail&r.mask]
    r.tail.Store(tail + 1) // release
    return v, true
}

Это SPSC (Single Producer Single Consumer) — простейший вариант. Для MPMC нужны более сложные алгоритмы (см. файл 09).

2.7 RWMutex с fairness (no starvation)

Проблема sync.RWMutex: при постоянном потоке reader’ов writer может ждать вечно (зависит от реализации). Хотим strict alternation или token-based fairness.

Подход: явная очередь с epoch’ами:

type FairRWMutex struct {
    mu        sync.Mutex
    readers   int
    writeLock bool
    queue     []chan struct{} // FIFO queue waiters
}

func (m *FairRWMutex) RLock() {
    m.mu.Lock()
    if !m.writeLock && len(m.queue) == 0 {
        m.readers++
        m.mu.Unlock()
        return
    }
    ch := make(chan struct{})
    m.queue = append(m.queue, ch)
    m.mu.Unlock()
    <-ch
    m.mu.Lock()
    m.readers++
    m.mu.Unlock()
}

// ... аналогично Lock(), Unlock(), RUnlock()

Это упрощённая версия — production-grade требует careful state machine. Идея: новые reader’ы блокируются, если в очереди есть waiter’ы.

2.8 RCU-like read-mostly (через atomic.Pointer)

Read-Copy-Update — паттерн из Linux kernel. Readers вообще не блокируются. Writer копирует, изменяет копию, атомарно swap’ит указатель.

package rcu

import "sync/atomic"

type Map[K comparable, V any] struct {
    p atomic.Pointer[map[K]V]
    // writers serialized externally (e.g. sync.Mutex)
    mu sync.Mutex
}

func New[K comparable, V any]() *Map[K, V] {
    m := &Map[K, V]{}
    empty := make(map[K]V)
    m.p.Store(&empty)
    return m
}

func (m *Map[K, V]) Load(k K) (V, bool) {
    cur := m.p.Load()
    v, ok := (*cur)[k]
    return v, ok
}

func (m *Map[K, V]) Store(k K, v V) {
    m.mu.Lock()
    defer m.mu.Unlock()
    old := m.p.Load()
    newMap := make(map[K]V, len(*old)+1)
    for kk, vv := range *old {
        newMap[kk] = vv
    }
    newMap[k] = v
    m.p.Store(&newMap)
}

Когда подходит:

• Reads >> Writes (1000:1 и выше).
• Map небольшая (полная копия не дорога).
• Старые copies можно отдать GC (в Go это автоматически).

Минусы:

• Каждый Store — это O(n) копирование.
• Memory amplification под write-heavy load.

2.9 Weighted Semaphore

golang.org/x/sync/semaphore — стандарт. Семантика:

sem := semaphore.NewWeighted(10)
sem.Acquire(ctx, 3) // занять 3 из 10
defer sem.Release(3)

Внутри — FIFO очередь waiter’ов на channel.

Priority semaphore — расширение: waiters с более высоким priority идут раньше. Реализуется через container/heap:

package prioritysem

import (
    "container/heap"
    "context"
    "sync"
)

type waiter struct {
    n        int
    priority int
    ready    chan struct{}
}

type priorityHeap []*waiter

func (h priorityHeap) Len() int { return len(h) }
func (h priorityHeap) Less(i, j int) bool { return h[i].priority > h[j].priority }
func (h priorityHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *priorityHeap) Push(x any) { *h = append(*h, x.(*waiter)) }
func (h *priorityHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type PrioritySemaphore struct {
    mu      sync.Mutex
    size    int
    cur     int
    waiters priorityHeap
}

func New(size int) *PrioritySemaphore {
    return &PrioritySemaphore{size: size}
}

func (s *PrioritySemaphore) Acquire(ctx context.Context, n, priority int) error {
    s.mu.Lock()
    if s.cur+n <= s.size && s.waiters.Len() == 0 {
        s.cur += n
        s.mu.Unlock()
        return nil
    }
    w := &waiter{n: n, priority: priority, ready: make(chan struct{})}
    heap.Push(&s.waiters, w)
    s.mu.Unlock()

    select {
    case <-w.ready:
        return nil
    case <-ctx.Done():
        s.mu.Lock()
        select {
        case <-w.ready:
            // already granted, must release
            s.mu.Unlock()
            s.Release(n)
        default:
            // remove from heap
            for i, ww := range s.waiters {
                if ww == w {
                    heap.Remove(&s.waiters, i)
                    break
                }
            }
            s.mu.Unlock()
        }
        return ctx.Err()
    }
}

func (s *PrioritySemaphore) Release(n int) {
    s.mu.Lock()
    s.cur -= n
    // try to wake waiters
    for s.waiters.Len() > 0 {
        top := s.waiters[0]
        if s.cur+top.n > s.size {
            break
        }
        heap.Pop(&s.waiters)
        s.cur += top.n
        close(top.ready)
    }
    s.mu.Unlock()
}

⚠️ Starvation risk: low-priority waiters могут ждать вечно. В production добавьте aging — увеличивайте priority с течением времени.

2.10 Hierarchical lock для DAG

Иногда нужно lock’нуть несколько ресурсов в правильном порядке (предотвращение deadlock). Идея: каждому lock’у присвоить уровень; брать только в возрастающем порядке.

package hier

import (
    "fmt"
    "sync"
)

type HLock struct {
    level int
    mu    sync.Mutex
}

type Goroutine struct {
    held []int // levels of currently held locks
}

func (g *Goroutine) Lock(l *HLock) error {
    if len(g.held) > 0 && g.held[len(g.held)-1] >= l.level {
        return fmt.Errorf("hierarchy violation: holding level %d, want %d", g.held[len(g.held)-1], l.level)
    }
    l.mu.Lock()
    g.held = append(g.held, l.level)
    return nil
}

func (g *Goroutine) Unlock(l *HLock) {
    l.mu.Unlock()
    // remove from held (LIFO)
    g.held = g.held[:len(g.held)-1]
}

В Go нет per-goroutine TLS, поэтому Goroutine нужно передавать явно или хранить ID в runtime.Goid() (через unsafe).

В реальности: используется в DBMS (InnoDB lock manager), filesystem (Linux ext4) для предотвращения deadlock между inode locks.

2.11 Lock-free linked list

Stack push (lock-free):
    new_node.next = head.load()
    while !CAS(&head, new_node.next, new_node):
        new_node.next = head.load()

package lflist

import (
    "sync/atomic"
    "unsafe"
)

type node struct {
    value int
    next  unsafe.Pointer // *node
}

type Stack struct {
    head unsafe.Pointer // *node
}

func (s *Stack) Push(v int) {
    n := &node{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)
        if atomic.CompareAndSwapPointer(&s.head, head, next) {
            return (*node)(head).value, true
        }
    }
}

⚠️ ABA problem: между Load(&head) и CAS другие потоки могут pop’нуть head, переиспользовать память, и push’нуть тот же адрес обратно. CAS пройдёт, но next будет указывать в воздух. См. файл 10.

В Go это менее опасно, потому что нет ручного free — GC удержит node, пока есть ссылки. Но при использовании sync.Pool или unsafe ABA возможен.

2.12 Sharded counter (wait-free)

atomic.AddInt64 дорог при contention из-за cache line bouncing. Решение — раздать по shards (per-CPU):

package counter

import (
    "runtime"
    "sync/atomic"
)

const cacheLineSize = 64

type paddedInt64 struct {
    v   atomic.Int64
    _   [cacheLineSize - 8]byte
}

type ShardedCounter struct {
    shards []paddedInt64
}

func New() *ShardedCounter {
    n := runtime.GOMAXPROCS(0)
    return &ShardedCounter{shards: make([]paddedInt64, n)}
}

func (c *ShardedCounter) Add(delta int64) {
    // Распределяем по shard'ам — например, через goroutine ID или random
    // Простой подход: использовать GOMAXPROCS как hash basis
    // Для perfection — runtime.procPin (внутренний)
    idx := fastRand() % uint32(len(c.shards))
    c.shards[idx].v.Add(delta)
}

func (c *ShardedCounter) Value() int64 {
    var sum int64
    for i := range c.shards {
        sum += c.shards[i].v.Load()
    }
    return sum
}

// fastRand — простой PRNG для шардирования
func fastRand() uint32 {
    // ...
    return 0
}

Trade-off: Add ультра-быстр (~ns), но Read O(N) — суммирование по shards.

Используется в: Prometheus client (counter under contention), Caffeine cache statistics, golang.org/x/sync/syncmap (старая).

2.13 Backoff strategies

При CAS-loop важно не “перегревать” CPU. Используются:

1. Constant backoff — runtime.Gosched() каждую итерацию.
2. Exponential backoff — задержка удваивается.
3. Random/jitter backoff — экспонент с jitter (как в TCP).
4. PAUSE intrinsic — на x86 CPU подсказка для hyperthreading (нет прямого доступа в Go, но runtime.procyield доступен через linkname).

//go:linkname procyield runtime.procyield
func procyield(cycles uint32)

func spinWithPause(s *atomic.Int32) {
    backoff := uint32(1)
    for !s.CompareAndSwap(0, 1) {
        procyield(backoff)
        if backoff < 256 {
            backoff <<= 1
        }
    }
}

⚠️ runtime.procyield — internal, может убрать. На ARM64 — другой инструкция (YIELD).

---

3. Gotchas

1. ⚠️ runtime.Gosched() в hot loop. Кажется безобидным, но дёргает scheduler. Под высокой нагрузкой замедляет throughput. Лучше PAUSE + ограниченное число spin’ов.

2. ⚠️ CAS в loop без backoff. Cache line bouncing → 100x slowdown. ВСЕГДА добавляйте backoff (хотя бы TTAS).

3. ⚠️ sync.Cond.Wait() без проверки в loop. Spurious wakeups возможны (особенно при Broadcast). Всегда: for !cond { c.Wait() }.

4. ⚠️ sync.Cond нельзя копировать после первого использования. go vet это ловит, но в reflection или generics может проскочить.

5. ⚠️ Channel-based mutex не имеет re-entrancy. Дважды Lock() из одной горутины = deadlock. Так же и у sync.Mutex. Re-entrant нужно реализовывать вручную через goroutine ID.

6. ⚠️ goroutine ID нестабилен между запусками. runtime.Goid() (unexported, через unsafe) можно использовать как owner marker, но не для bookkeeping между restarts.

7. ⚠️ go:linkname ломается при обновлении Go. В Go 1.23 уже добавлены проверки для unauthorized linkname. Используйте только если очень надо.

8. ⚠️ Padding в struct может быть оптимизирован компилятором. Используйте [N]byte явно или golang.org/x/sys/cpu.CacheLinePad.

9. ⚠️ atomic.Int64 на 32-bit платформах. До Go 1.19 требовалось 8-byte alignment вручную. Сейчас компилятор выравнивает автоматически, но при embedded в struct учитывайте порядок полей.

10. ⚠️ CAS на pointer ≠ memory ordering на содержимое. CAS гарантирует только ordering pointer’a, не данных, на которые он указывает. Нужны acquire/release semantics, а они в sync/atomic есть только через типизированные методы.

11. ⚠️ TryLock на sync.Mutex (Go 1.18+) — не fairness. Может “украсть” lock у waiter’а. Документировано.

12. ⚠️ Spinlock + GOMAXPROCS=1 — катастрофа. Горутина будет крутиться, не отдавая P, ровно forever. Если нет CAS успеха — deadlock. ВСЕГДА в spinlock’е делайте runtime.Gosched() периодически.

13. ⚠️ sync.Pool не для long-lived state. Pool очищается между GC, объекты могут пропасть. Только для temporary buffers.

14. ⚠️ Lock-free стэк страдает от ABA даже в Go. Если переиспользуете node’ы через sync.Pool или unsafe — bug возможен.

15. ⚠️ runtime.LockOSThread + sync primitive = странные взаимодействия. OS thread не может быть стэлен, поэтому если горутина blocked на mutex, поток “застрял”. Использовать с осторожностью.

---

4. Real cases

4.1 gRPC connection pool (внутри google.golang.org/grpc)

В grpc-go ClientConn поддерживает pool subconnections. Внутри — read-write protected list через sync.Mutex + atomic.Pointer на snapshot. Reads (которые наиболее частые — выбор subconn для RPC) идут через atomic load, writes (добавление/удаление subconn) — через mutex + copy-on-write. Это паттерн RCU.

4.2 fasthttp’s worker pool

В valyala/fasthttp workers pool использует custom mutex-protected list с очень короткой критической секцией. Используется TTAS-spinlock-подобный паттерн перед уходом в sync.Mutex. Цель — минимизировать park/unpark overhead при низкой contention.

4.3 Go runtime’s M-P-G scheduler

Внутри Go runtime используется MCS lock (вариант ticket lock с per-thread node) для защиты глобальных структур (sched.lock, allp). Critical sections супер-короткие, и MCS избегает cache line bouncing, в отличие от ticket lock’а.

4.4 BoltDB / bbolt

bbolt (форк BoltDB) — embedded KV DB. Использует single global RWMutex для readers/writer. Это даёт MVCC-подобную семантику (multiple readers, one writer), но при write-heavy workload — bottleneck.

4.5 etcd’s MVCC store

etcd использует custom lock manager поверх BoltDB. Внутри — range-based locks (lock’и не на ключи, а на key ranges). Реализовано через interval tree + RWMutex per node. Custom, потому что стандартный sync.Map не поддерживает range queries.

---

5. Вопросы

1. Чем spinlock отличается от mutex?
   Spinlock крутится в CPU loop, не парковая горутину. Mutex после короткого спина парк через runtime/sema. Spinlock дешевле при короткой критической секции (< 1µs), но greвает CPU и без backoff’а вызывает cache line bouncing.

2. Что такое TTAS и зачем он?
   Test-And-Test-And-Set: сначала простой Load (не вызывает MESI invalidation), и только если “похоже что lock свободен” — CAS. Снижает cache line traffic.

3. Как реализовать TryLock без sync.Mutex.TryLock (до Go 1.18)?
   Через atomic.Int32 + CAS на 0→1. Простейший пример — spinlock c одной итерацией.

4. Какие memory ordering гарантии даёт atomic.Load в Go?
   Acquire semantics: все последующие операции в горутине видят то, что было до соответствующего Store (с release semantics). Эквивалентно memory_order_acquire в C++.

5. Что такое ticket lock и в чём fairness?
   Каждый поток получает порядковый номер через atomic increment. Ждёт, пока serving == myTicket. FIFO порядок гарантирован. Минус — все потоки крутятся на одной переменной (cache line bouncing).

6. В чём проблема ticket lock vs MCS lock?
   Ticket lock крутится на одной shared переменной → cache line bouncing. MCS lock даёт каждому потоку локальный node, на котором он крутится — нет contention.

7. Можно ли реализовать sync.Cond с timeout в Go?
   Стандартный — нет. Workaround: channel + select на time.After. Но goroutine, которая делает Wait, может остаться парковой. Лучше — channel-based mutex/cond с самого начала.

8. Зачем нужен sharded counter?
   При высокой contention atomic.Add на одной переменной — bottleneck (cache line bouncing). Sharded counter распределяет по N переменных (по числу CPU), каждая в своей cache line. Read = sum всех shard’ов.

9. Чем bounded buffer на channel отличается от lock-free ring buffer?
   Channel: goroutine парк/распарк, runtime overhead ~50-100 ns. Ring buffer: lock-free atomic ops, ~10-20 ns, но требует careful memory ordering.

10. Что такое RCU и где применяется?
    Read-Copy-Update: readers без синхронизации, writer копирует, меняет копию, атомарно swap’ит pointer. Старые copies удаляются после grace period (когда все pre-swap readers завершились). В Linux kernel — для read-mostly структур. В Go — через atomic.Pointer.

11. Чем отличается lock-free от wait-free?
    Lock-free: хотя бы один поток гарантированно прогрессирует. Wait-free: каждый поток прогрессирует за bounded шагов независимо от других.

12. Почему sync.RWMutex в Go writer-preferring?
    Чтобы избежать writer starvation. Если новый reader приходит, когда writer уже ждёт, reader блокируется и пропускает writer’a вперёд.

13. Что такое priority inversion и как с ней бороться?
    Low-priority поток держит lock, high-priority ждёт его, middle-priority блокирует low. Решения: priority inheritance (low temporary boost’ит priority до high’a), priority ceiling (lock имеет фикс. priority).

14. Зачем нужны hierarchical locks?
    Для предотвращения deadlock при acquire’е нескольких locks. Каждому lock’у присваивается уровень; брать только в возрастающем порядке. Используется в DBMS, filesystem.

15. Почему atomic.Pointer появился только в Go 1.19?
    Generics! До Go 1.18 был atomic.Value (untyped), но он не давал compile-time safety. С generics стало возможным atomic.Pointer[T].

16. Что значит “wait-free counter”?
    Counter, где каждый Add завершается за bounded шагов (без retry loop’а). atomic.AddInt64 — wait-free на x86 (lock add instruction). На ARM64 — CAS-loop, может быть lock-free но не wait-free.

17. Можно ли реализовать lock-free очередь без CAS?
    Нет. CAS (или его эквивалент LL/SC) — necessary primitive. Без него wait-free алгоритмы вообще невозможны (теорема Herlihy).

18. Чем sync/atomic.Value отличается от atomic.Pointer?
    Value хранит interface{}, требует не менять тип после первого Store. Pointer — типизированный, безопаснее. Pointer быстрее, потому что нет interface boxing.

19. Что такое linkname и почему опасно?
    //go:linkname localname importpath.remotename позволяет вызвать unexported функцию из другого пакета. Опасно: internal API может измениться/исчезнуть. С Go 1.23 ужесточены проверки.

20. Можно ли получить goroutine ID в Go?
    Не через стандартный API. Через unsafe + parsing stack frame — да, но HIGHLY discouraged. Только для отладки.

21. Что такое starvation mode в sync.Mutex (Go 1.9+)?
    Если waiter ждал > 1ms, lock переходит в starvation mode: direct handoff (lock передаётся следующему waiter’у без spin), новые ariving goroutines парк сразу. Восстанавливается, когда waiter получает lock < 1ms.

22. Зачем нужен runtime.semacquire?
    Это внутренний semaphore Go runtime. Используется sync.Mutex, channel send/recv (когда block), sync.WaitGroup.Wait(). По адресу *uint32 — wait queue.

23. Как PAUSE intrinsic помогает в spinlock’е?
    На x86 PAUSE подсказывает CPU, что в hot loop’е, и снижает memory order violation overhead на hyperthreading. Без PAUSE другой hyperthread на том же core страдает. В Go — через runtime.procyield (внутренний).

24. Что такое “false wakeup” (spurious wakeup)?
    sync.Cond.Wait() может проснуться без Signal/Broadcast (например, при resize wait queue). Поэтому всегда for !condition { c.Wait() }.

25. Когда custom primitive оправдан?
    После профилирования. Если sync.Mutex в pprof.mutex — top contention, и contention real (не bug в коде), и стандарт не подходит семантически (нет timeout, нет priority, etc) — тогда custom. ВСЕГДА бенчмарк до и после.

---

6. Practice

6.1 Реализовать ticket lock и сравнить с sync.Mutex

Напишите ticket lock, замерьте throughput при 1/4/16/64 goroutines, contention low/high.

6.2 Custom semaphore с WaitContext

Расширьте golang.org/x/sync/semaphore — добавьте метод TryAcquireUntil(deadline time.Time).

6.3 RCU-like cache

Реализуйте read-mostly cache: map[string]Value, где Get атомарен, Set копирует map. Бенчмарк под 99% reads / 1% writes.

6.4 Sharded counter с per-P sharding

Реализуйте sharded counter, использующий runtime.procPin (через linkname) для P-affinity вместо random hash. Сравните с random sharding.

6.5 Custom RWMutex с writer timeout

Реализуйте RWMutex, где writer может указать deadline. Если до deadline lock не получен — отменяет операцию, освобождая ресурс.

6.6 Reentrant mutex

Реализуйте reentrant mutex (горутина может Lock несколько раз, должна столько же раз Unlock’нуть). Используйте goroutine ID через runtime.Stack.

6.7 Bounded buffer SPSC

Реализуйте SPSC ring buffer на atomic ops с правильной cache line separation. Бенчмарк против chan T с capacity 1024.

6.8 Hierarchical lock для DAG

Реализуйте hierarchical lock с runtime check: если поток нарушает порядок — panic с сообщением, в каком уровне нарушение.

---

7. Источники

1. Russ Cox, Go Memory Model — официальная документация memory ordering в Go.
2. Dmitry Vyukov, 1024cores.net — энциклопедия lock-free алгоритмов и atomics.
3. Maurice Herlihy, Nir Shavit, “The Art of Multiprocessor Programming” — фундаментальная книга, главы про spinlocks, MCS, ticket lock.
4. Paul McKenney, Is Parallel Programming Hard? — RCU, memory ordering, в Linux kernel context.
5. golang/sync source code — semaphore, errgroup, singleflight.
6. Go runtime source — src/runtime/sema.go, src/runtime/lock_*.go, src/sync/mutex.go.
7. Folly SpinLock.h — C++ реализации backoff, MCS.
8. Linux kernel docs/RCU — RCU объяснён с практической стороны.
9. Bryan Cantrill, “Cantrill on Concurrency” talks — DTrace и lock contention в production.
10. Sutter, Lock-Free Queues — classic article по lock-free queues.
11. John Mellor-Crummey, Michael Scott, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors” (1991) — MCS lock paper.
12. golang.org/x/sys/cpu — CacheLinePad, CacheLineSize константы.