Concurrency and Consistency. Non-blocking, lock-free and async. ABA ProblemСегодня поговорим о проблеме неразрывно связанной с lock-free алгоритмами. Она возникает в коде на атомиках и демонстрирует наглядно что имея атомики в коде, казалось бы безопасный примитив можно выстрелить себе в ногу.
Для воспроизведения проблемы нам нужны
- Cтруктура данных с указателями.
- Compare and Swap.
Представим себе что у нас стоит задача реализовать потокобезопасный стек. Классическая реализация неезопасна, с мьютексом достаточно медленная для наших условий, остается вариант с атомиками.
type Node[T any] struct {
val T
next atomic.Pointer[Node[T]]
}
type UnsafeStack[T any] struct {
dummy *Node[T]
top atomic.Pointer[Node[T]]
}
func NewUnsafeStack[T any]() *UnsafeStack[T] {
s := &UnsafeStack[T]{dummy: &Node[T]{}}
s.top.Store(s.dummy)
return s
}
func (s *UnsafeStack[T]) Push(n *Node[T]) {
for {
top := s.top.Load()
n.next.Store(top)
if s.top.CompareAndSwap(top, n) {
return
}
}
}
func (s *UnsafeStack[T]) Pop() *Node[T] {
for {
top := s.top.Load()
if top == s.dummy {
return nil
}
if s.top.CompareAndSwap(top, top.next.Load()) {
return top
}
}
}
func (s *UnsafeStack[T]) Values() []T {
var out []T
for n := s.top.Load(); n != s.dummy; n = n.next.Load() {
out = append(out, n.val)
}
return out
}
Основное отличие от версии которую бы мы написали с использованием мьютекса - бесконечные циклы в push, pop. Ведь если несколько потоков сделают вставку или извлечение то прочитанная в локальную память переменная top станет неактуальной и CAS операция будет неуспешной. Поэтому мы будем пытаться реализовать операцию до победного.
Демонстрация ABAДля того чтобы продемонстрировать проблему в этом коде я подготовил
Go Playground сниппет. Его суть:
- Есть 2 горутины, одна пытается извлечь данные из стека (не через использование функции pop, а напрямую, это нужны чтобы имитировать прерывание в нужном месте программы).
- Горутина №2 - это череда операций (pop, pop, push). В конце она пытается вставить узел который являлся изначальной вершиной стека.
- Когда управление возвращается горутине №1 она не видит абсолютно ничего криминального и делает успешный CAS, хотя внутреннее представление элемента поменялось и ссылка на следующий элемент в стеке изменилась.
На выходе получаем грязный стек c данными которых в нем быть не должно.
Как решается проблема ABA?Чтобы решить проблему ABA можно взять одно из решений:
- размечать узлы в стеке версиями. Этот подход подразумевает что адреса узлов сохраняются, но CAS все равно упадет из за несовпадения версий.
- оборачивать внутри стека узлы в указатели, тогда у нас не будет повторения адресов и успешных CAS.
Я для простоты покажу
работающий код решения №2.
ВыводыABA Problem это один из примеров того что может случиться когда мы пишем сложные программы в погоне за высоким перформансом. Посмотрите на получившийся код и вспомните как вы писали свой первый стек. И вот в голове маячат вопросы:
- Стоит ли так извращаться?
- Имеет ли оно смысл?
- Насколько разница существенная?
Это рассмотрим в следующем посте, а пока ставьте лайки и делитесь своим опытом работы с lock-free стеками и очередями.
