🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №4. Гарантия отсутствия блокировок.
В прошлом посте рассмотрели классический пример - конкурентная работа со счетами пользователей. Код довольно простой и наглядный, и даже соответствует гарантии которую разбирали.
Но с ним есть проблема - он неправильный.
- Мы буквально можем потерять операцию и как следствие деньги.
- У нас возможен дедлок, если в один и тот же момент два пользователя переведут друг другу денежку.
Как чинить эти проблемы?
Шаг №1 - Заменить атомики на мьютексы.
Шаг №2 - Добавить упорядочивание в захват мьютексов.
package main
import (
"sync"
"unsafe"
)
type SafeAccount struct {
mu sync.Mutex
balance int64
}
func transferSafe(from, to *SafeAccount, amount int64) {
first, second := from, to
if uintptr(unsafe.Pointer(from)) > uintptr(unsafe.Pointer(to)) {
first, second = to, from
}
first.mu.Lock()
second.mu.Lock()
from.balance -= amount
to.balance += amount
second.mu.Unlock()
first.mu.Unlock()
}
Возвращая мьютексы мы теряем любые намеки на неблокирющую синхронизацию, зато код корректный и предсказуемый. Опять трейдоффы, что ж с ними поделаешь.
Но раз перед нами стоит цель - научиться писать программы в неблокирующем стиле нужно продолжать погружение. Для начала определение:
Гарантия отсутствия блокировок (Lock-free) - наш код гарантирует что в случае конкурентного исполнения кто-то обязательно достигнет прогресса.
Вспомним наш "неправильный" пример про операцию transfer. Несмотря на неправильность, тем не менее он отлично демонстрирует гарантию obstruction-free. А что насчет lock-free? Гарантируется ли что при конкурентном запуске кто-то из участников обязательно достигнет прогресса?
Такая гарантия отсутствует. Код допускает ситуацию livelock - потоки что-то делают, но постоянно откатываются назад, потому что конкурент успевает изменить общее состояние и нужно перечитывать заново, чтобы ничего не потерять.
Получается что и не lock-free + критичные баги.
Причина у двух следствий одна - в нашем алгоритме больше одного атомика. И вдобавок между ними есть связь, они части одного целого. Разделяя наше состояние на 2 части у нас не остается механизма для того чтобы работать с этими частями атомарно вместе, только по отдельности.
Классические структуры данных, например стеки или очереди если нужна lock-free гарантия всегда реализуются через один атомик или несколько, при этом абсолютно независимых между собой. При таком дизайне гарантируется что какой бы ни была конкуренция - один участник точно достигнет успеха.
Что такое Lock-free стек можно посмотреть здесь вместе с сопутствующей ABA Problem.
Фух, многовато текста получилось, поэтому уже в следующем посте мы вернемся к функции transfer и сделаем её lock-free. Спойлер: будет сурово, поэтому готовимся морально и физически😁
