Есть ли в Go Lock-free структура данных?

Наличие Lock-free структур данных в Go

Да, в Go можно реализовывать lock-free (безалгоритмические) структуры данных, хотя язык не предоставляет встроенных высокоуровневых примитивов для этого в стандартной библиотеке. Go в основном полагается на каналы и мьютексы (sync.Mutex, sync.RWMutex) для синхронизации, но низкоуровневые атомарные операции из пакета sync/atomic позволяют создавать неблокирующие алгоритмы.

Ключевые механизмы для Lock-free программирования в Go

1. Атомарные операции (sync/atomic)

Пакет предоставляет атомарные операции над базовыми типами (int32, int64, uint32, uint64, uintptr, указатели через unsafe.Pointer):

package main

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

type Counter struct {
    value int64
}

func (c *Counter) Increment() {
    atomic.AddInt64(&c.value, 1)
}

func (c *Counter) Get() int64 {
    return atomic.LoadInt64(&c.value)
}

// CAS (Compare-And-Swap) операция
func (c *Counter) CompareAndSwap(old, new int64) bool {
    return atomic.CompareAndSwapInt64(&c.value, old, new)
}

2. Атомарные указатели (с Go 1.19)

Go 1.19 ввела обобщенные атомарные типы в sync/atomic, включая atomic.Pointer[T]:

import "sync/atomic"

type Node struct {
    value int
    next  atomic.Pointer[Node]
}

func (n *Node) SetNext(newNode *Node) {
    n.next.Store(newNode)
}

func (n *Node) GetNext() *Node {
    return n.next.Load()
}

Примеры Lock-free структур данных

Lock-free Stack (Treiber Stack)

package stack

import (
    "sync/atomic"
    "unsafe"
)

type node struct {
    value interface{}
    next  unsafe.Pointer
}

type Stack struct {
    top unsafe.Pointer
}

func NewStack() *Stack {
    return &Stack{}
}

func (s *Stack) Push(value interface{}) {
    n := &node{value: value}
    
    for {
        top := atomic.LoadPointer(&s.top)
        n.next = top
        
        if atomic.CompareAndSwapPointer(&s.top, top, unsafe.Pointer(n)) {
            return
        }
    }
}

func (s *Stack) Pop() interface{} {
    for {
        top := atomic.LoadPointer(&s.top)
        if top == nil {
            return nil
        }
        
        next := (*node)(top).next
        if atomic.CompareAndSwapPointer(&s.top, top, next) {
            return (*node)(top).value
        }
    }
}

Lock-free Counter с CAS

type LFMap struct {
    data atomic.Value // хранит map[string]int
}

func (m *LFMap) Update(key string, delta int) {
    for {
        oldMap := m.data.Load().(map[string]int)
        newMap := make(map[string]int, len(oldMap)+1)
        
        for k, v := range oldMap {
            newMap[k] = v
        }
        newMap[key] = oldMap[key] + delta
        
        if m.data.CompareAndSwap(oldMap, newMap) {
            return
        }
    }
}

Преимущества и недостатки Lock-free в Go

Преимущества:

• Отсутствие блокировок - потоки не блокируются мьютексами
• Устойчивость к задержкам - не страдают от проблем priority inversion
• Масштабируемость - хорошо работают на многоядерных системах
• Отсутствие deadlock'ов - алгоритмически предотвращают взаимные блокировки

Недостатки:

• Сложность реализации - легко допустить тонкие ошибки
• Проблема ABA - значение может измениться и вернуться к исходному
• Требуется GC безопасность - нужно предотвращать сборку мусора во время операций
• Сложность отладки - недетерминированное поведение сложнее анализировать

Практические рекомендации

1. Используйте стандартные примитивы, когда возможно - sync.Map, sync.Pool
2. Для счетчиков - sync/atomic обычно достаточно
3. Для сложных структур рассмотрите sync.Mutex - он часто быстрее при низкой конкуренции
4. Lock-free имеет смысл только при высокой конкуренции и измерениях производительности
5. В Go 1.19+ используйте atomic.Pointer[T] вместо unsafe.Pointer для типобезопасности

Альтернативы в Go

• sync.Map - оптимизирован для read-heavy workloads
• Каналы - CSP модель часто устраняет необходимость в lock-free
• sync/atomic.Value - для атомарной замены целых структур

Вывод: Хотя Go не предоставляет готовых lock-free коллекций как Java с java.util.concurrent.atomic, возможность создавать их есть через атомарные операции. Однако в большинстве случаев стандартные примитивы синхронизации Go более предпочтительны из-за простоты и читаемости. Lock-free подход стоит использовать только при доказанной необходимости после профилирования и измерения производительности.