Евгений Козлов пишет про IT

Результаты опроса меня впечатлили. Большинству интересны истории из работы. Поехали, начнем с истории из моего джунства. Разминка и затравка.

Джун SRE или как я чинил прод на Go с опытом работы меньше месяца и не зная Go

На дворе 2016й. Я впервые задумываюсь о поиске работы в своем родном городе Брянске. По итогу поисков я устроился в веб студию разрабатывающую фичи на заказ. Я устроился бэкэнд разработчиком поддерживать и писать проекты на Ruby on Rails.

Одним из проектов которым я занимался было приложение для пополнения карт Тройка в Москве. Он был разделен на 2 части:

- API для мобильного приложения (на RoR)
- API на Golang для работы непосредственно с эквайринговыми провайдерами.

В целом я быстро погрузился в первую часть системы. Во вторую погружение не требовалось. Она просто работала. До поры до времени.

Первые звоночки

Однажды я пришел на работу и обнаружил что сервис на Go упал ночью. В логах я не обнаружил ничего интересного кроме:

too many open files

Уже не помню было ли на сервере настроен systemd который перезапускал упавший процесс, но в любом случае выглядело это эпично.

Из обсуждения с тимлидом я сделал вывод, что на поверхности решения проблемы не видно и нужно разбираться. А у меня какое то время не было новых продуктовых задач на проектах. И уже не помню: он предложил мне или я вызвался - в общем задача разобраться с триггером, причиной и устранением дефекта досталась мне.

Сбор фактуры. Установление причины.

Первое с чего я начал - сбор всей доступной телеметрии. Я изучил причины почему вообще ошибка называется too many open files. Курс по линуксу в универе был свеж в моей голове и я быстро сориентировался. Дело врядли в файловой системе, а скорее всего в том что в линуксе "всё есть файл" и вот с какими то конкретными файлами у моего процесса проблемы. Так как сервис был развернут просто на голой виртуальной машине и у меня был доступ по ssh я имел полную свободу действий.

По итогу вот такая команда выдала мне то что я искал:

lsof -p <PID> | wc -l

Показатель монотонно растет, при достижении значения 1000 процесс падает с той самой ошибкой.

Погружение в код. Поиск триггера

Найдя причину мне стало немного легче. Но задача только набирала обороты. В моем распоряжении критичный по функциональности сервис на языке Go, языке с которым я не работал никогда. И надо в нем искать багулю (а мб бага вообще не в нем).

Изучив всю кодовую базу я обнаружил что единственная вещь которая может повлиять на найденную ранее метрику - работа http client. В Go это обычно выглядит так:

resp, err := http.Get("https://gobyexample.com")
if err != nil {
  return err
}
defer resp.Body.Close()
// бизнес логика

И собственно все стало на свои места. Погрузившись в доку гошки я черным по белому увидел что

resp.Body.Close()

влияет на метрику найденную на шаге №1.

Осталось дело за малым, найти кейс в коде когда resp.Body.Close() не выполняется. 30 минут вдумчивого и внимательного чтения и я вижу вот такой код:

// http запрос 
if resp.Status >= 400 || err != nil {
  return "что то там"
}
defer resp.Body.Close()
// бизнес логика

Я понял, вот оно. Мы не закрываем соединение если апи поставщика вернула статусы выше 400х. Почему так было сделано я не стал разбираться. Я понял что это явно неправильно поведение. Будучи на эмоциональном подъёме несу МР с фиксом тимлиду, получаю LGTM и мы вместе его катим. Фикс был примитивный:

// http запрос 
if err != nil {
  return err
}
defer resp.Body.Close()

if resp.Status >= 400 {
  return "что-то там"
}

Это был выстрел в яблочко, после наката новой версии значение найденной мной метрики держалось на одном уровне. Я до сих помню эти ощущения, чувство победы над вещью которая пару дней назад казалось нереальной.

Выводы

Чему меня научила эта история? Учеба в универе и некоторые предметы точно не лишние в работе😊

А если серьезно - не бояться залезать в сложные и неочевидные проблемы. Да у тебя может не быть на бумаге нужного опыта, да и вообще ты джун на испыталке, ну и что? Траблшутинг это вещь которой нельзя научиться в теории, ей учишься исключительно на практике. И с ростом практики начинаешь понимать почему методологии дебага и траблшутинга из умных книг и статей именно такие.

Вот такая история, делитесь в комментариях, помните ли вы свой первый баг, как его чинили?) Ну и делитесь фидбэком, как вам такой формат😊

Concurrency, Synchronization and Consistency. Non-blocking. Оглавление

Введение
- Блокирующая и неблокирующая синхронизация
- Гарантии в неблокирующей синхронизации

Знакомимся с obstruction-free и lock-free. Пишем движок для финансовых транзакций
- Гарантия отсутствия препятствий (Obstruction-free). Наивная реализация TransferMoney.
- Введение в Lock-free

- Финал. Переписываем TransferMoney на lock-free код с MCAS.

Lock-Free структуры данных
- Структура данных Queue: от наивной реализации к lock-free
- Структура данных Stack и пример ABA problem
- Примеры lock-free кода в реальном мире

Гарантия отсутствия ожидания (Wait-free)
- Гарантия Wait-free. Введение
- Самая популярная Wait-free структура данных
- Примеры академического wait-free

Заключение
- Самые важные факты о Wait-free / Lock-free структурах данных
- Выводы и итоги

—————

Прошлые циклы постов:
- Concurrency and Consistency. Fundamentals & Locking Synchronization
- CPU, Memory Models, Concurrency, Multiprocess, Multithreading и Async

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №12. Заключение.

Когда я начинал цикл постов у меня было ожидание что lock-free это - ускорять программы ценой усложнения кода. При этом интуиция шептала, что в таком случае мьютексы автоматически становятся ненужными, а они живее всех живых. С этой точки я и решил погрузиться в вопрос в поисках истины.

По итогам цикла постов я могу с уверенностью сказать - выбор между locking и non-blocking синхронизацией это выбор проблем с которыми ты готов иметь дело + ограничения накладываемые предметной областью.

Блокирующая синхронизация это про
+ простоту
+ отличную среднюю производительность

- дедлоки
- голодание
- livelock
- инверсию приоритетов.
- thundering herd
- lock convoy

Страшные слова, но с ними вполне можно работать. Единственный момент - в совокупности с вытесняющей многозадачностью блокировки не способны дать предсказуемый latency для худшего случая. Наша программа может работать очень быстро 99% времени, но в 1% времени у нас могут случаться всплески latency (просто так совпало). Для некоторого набора софта это вполне нормально и не несет проблем.

Неблокирующая синхронизация в свою очередь это:
+ "почти никогда" не простаиваем
+ гарантии прогресса
+ гарантии предсказуемого количества попыток.

- пляски с аллокациями
- retry storm
- aba problem
- очень сложный код, по сравнению с кодом на мьютексах

При этом бенмарки шепчут - алгоритмы на атомиках в среднем будут работать хуже. Больше работы с памятью, CAS циклы, синхронизация кешей CPU. Еще и код очень сложный.

Зачем тогда это всё? Ответ - неблокирующая синхронизация способна дать больше гарантий для latency худшего случая.
В медицине, запуске ракет, роботах, авиаиндустрии, ну и само собой разработке ОС и СУБД можно найти примеры процессов для которых важен предсказуемый по времени ответ и для которых минусы блокирующего подхода неприемлемы. И вот тут рассмотренные алгоритмы и структуры выходят на сцену. А то что в среднем работает медленнее не проблема, а трейдофф на который нужно идти.

Вот такие выводы получились, дополняйте, если что-то упустил.
На этом цикл завершаю, спасибо, что читали, надеюсь вам было интересно и полезно, буду рад почитать о ваших впечатлениях от материала в комментариях)

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №11. Самые важные факты о Wait-free / Lock-free структурах данных

На основе прочитанных статей и материалов у меня в голове выстроились некоторые связи и закономерности, ими и хочу поделиться с вами:

- Фиксация количества потоков в Wait-Free. В отличии от lock-free и mutex реализаций wait-free структура должна заранее знать сколько конкурентных участников в системе (потоков). Нужно для того чтобы гарантировать фиксированное количество итераций (вместо бесконечных циклов).

- Потоки кооперируют а не конкурируют. Вместо блокировки и борьбы за ресурс участники подхватывают промежуточные состояние друг друга и доводят их до завершения. За счет этого достигается lock-free семантика. Реализуется через cхему "анонсирования изменений" во внутренностях алгоритма (термин - announce array в литературе)

- Для wait-free важна не только кооперация но и приоритеты. Сама по себе кооперация не дает гарантию wait-free но если ее приправить механикой приоритетов это то что гарантирует честность и очередность.

- Работа с памятью. SMR (Safe Memory Reclamation) это отдельная ось исследований. Ведь у нас структура данных над общей памятью и мы ничем не защищаем её. Если в языках с GC эту боль на себя забирает рантайм (ценой перформанса, и в худшем случае потерей статуса wait-free), то в C++ / Rust работа с памятью на плечах программиста. Благо существуют алгоритмы и подходы к этой задаче:

- Подсчет ссылок (std::shared_ptr и std::atomic<shared_ptr>)
- Hazard Pointers (std::hazard_pointer)
- Quiescent State-Based Reclamation. Реализован внутри языках Linux а также nogil версии Python (пруф)
- Epoch-based Reclamation. crossbeam-epoch в Rust.

Также стоит помнить про аллокаторы памяти. Это тоже алгоритм и он является частью нашей программы. И если у него под капотом есть блокировки то наши ухищрения потеряют смысл.

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №10. Продвинутые wait-free очереди

В прошлом посте я рассказал про один из самых популярных и полезных вариантов очередей с семантикой wait-free. Он такой не потому что использует какие то продвинутые алгоритмы, а именно из-за гарантий отсутствия нескольких читателей и писателей. Сегодня расскажу какие еще варианты существуют но уже со стороны академии и науки.

MPMC (Multiple Producers / Multiple Consumers) Queue by Kogan and Petrank

В 2011 уважаемые товарищи Alex Kogan, Erez Petrank написали статью "Wait-free queues with multiple enqueuers and dequeuers", в ней на основе очереди Майкла-Скотта реализовали свою собственную очередь с семантикой wait-free. Чтобы достичь той самой семантики они внедрили логику приоритетов в которой быстрые участники помогают медленным. Реализовали очередь на Java, с оговорками что алгоритм из статьи будет работать с листа только на языках с GC.

Достичь Wait-Freedom авторам статьи помог не раз упомянутый мной в постах Leslie Lamport и его алгоритм пекарни (A New Solution of Dijkstra's Concurrent Programming Problem)

По перформансу - однозначно победить очередь Майкла-Скотта не удалось, но есть сценарии в которых очередь действительно показывает себя лучше. Так появился первый в мире корректный алгоритм MPMC Queue, который может быть полезен в production.

MPMC Turn Queue by Ramalhete and Correia

В 2016м году другие товарищи сели писать свою очередь, как они сами пишут "по причине того что все остальное либо очень сложное, либо очень простое, привязано к языку или GC".

Так на свет появилась статья A Wait-Free Queue with Wait-Free Memory Reclamation. Ребята придумали свой протокол консенсуса, придумали подход для работы с памятью, чтобы очередь была пригодна не только для языков с GC. Как итог - самая популярная реализация очереди неограниченного размера в данный момент.

wCQ: A Fast Wait-Free Queue with Bounded Memory Usage

В 2022м Ruslan Nikolaev и Binoy Ravindran. публикуют статью в которой предлагают вариант очереди на основе кольцевого буфера фиксированного размера (как тот что мы рассматривали в прошлой заметке). Благодаря такому дизайну работы с памятью нет вообще + ребята спроектировали механику fast / slow path.

По итогу у них получилось приблизиться по перформансу к своему же детищу - lock-free SCQ (A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue). Что на самом деле большой успех для wait-free алгоритма.

Выводы
Этой заметкой мне хотелось показать, что Concurrency исследования это то что развивается прямо сейчас и все еще нет стандартов, чтобы можно было бы просто взять и поменять и станет резко хорошо. Все таки публикации очень свежие, а области в которых они могут полезны ограничены и очень сложны. Поэтому и в публичных источниках информацию найти сложно.

При этом попытки все таки есть:
- Parsec: Fast, Scalable, and Secure Design with Wait-Free Parallelism by Ruslan Nikolaev
- Scalable and Fault-Tolerant Storage and File System Services with Non-Blocking Synchronization for Private Clouds by Mincheol Sung, Ruslan Nikolaev, Binoy Ravindran

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №9. Wait-free структура данных в проде

Как и обещал, примеры кода с семантикой wait-free, сегодня поговорим про то что нашло применение в реальности.

🔵 SPSC (Single Producer - Single Consumer) Queue over Ring Buffer

Предложил алгоритм Leslie Lamport в статье Proving the Correctness of Multiprocess Programs.

Идея проста до безобразия - если свести проблему к состоянию когда у структуры данных 2 участника, по одному на чтение и запись то бесконечные циклы и CAS не нужны совсем. Только 2 атомика и битовая арифметика.

type SPSCQueue struct {
  buf  []int
  mask uint64

  // tail — индекс следующей записи, пишет только производитель.
  // head — индекс следующего чтения, пишет только потребитель.
  // Оба монотонно растут, реальный слот — индекс по модулю ёмкости.
  tail atomic.Uint64
  head atomic.Uint64
}

// NewSPSCQueue создаёт очередь ёмкостью capacity, которая должна быть
// степенью двойки (чтобы взятие по модулю свелось к побитовому &).
func NewSPSCQueue(capacity uint64) *SPSCQueue {
  if capacity == 0 || capacity&(capacity-1) != 0 {
    panic("capacity must be a power of two")
  }
  return &SPSCQueue{buf: make([]int, capacity), mask: capacity - 1}
}

// Push вызывается ТОЛЬКО производителем. Возвращает false, если очередь
// полна (ждать нельзя - это нарушило бы wait-free).
func (q *SPSCQueue) Push(val int) bool {
  tail := q.tail.Load()

  // Потребитель только увеличивает head, поэтому прочитанное значение
  // может лишь "устареть в нашу пользу": если места нет по этой оценке,
  // его точно не было и на момент проверки.
  if tail-q.head.Load() == uint64(len(q.buf)) {
    return false
  }

  q.buf[tail&q.mask] = val

  // Store публикует запись в слот: потребитель увидит новый tail только
  // после того, как значение уже лежит в буфере (release-семантика).
  q.tail.Store(tail + 1)
  return true
}

// Pop вызывается ТОЛЬКО потребителем. Возвращает false, если очередь пуста.
func (q *SPSCQueue) Pop() (int, bool) {
  head := q.head.Load()

  if head == q.tail.Load() {
    return 0, false
  }

  val := q.buf[head&q.mask]
  q.head.Store(head + 1)
  return val, true
}

Сниппет чтобы пощупать код

Где встречается SPSC
- Работа с аудио
- Сетевое программирование
- Трейдинг / финансы

Выводы
SPSC это алгоритм из категории просто и со вкусом. Всего 50 строк а применений нашлось большое множество. Практически на любом устройстве / программе хоть как то взаимодействующей с ОС или железом найдется место этому алгоритму. По причине того что взаимодействовать на стыке двух независимых систем (ядро-процесс, железо - драйвер) безопаснее всего без блокирующих примитивов (иначе привет дедлоки).

Пишите в комментариях встречали ли нечто подобное и какая задача была)

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №8. Гарантия отсутствия ожидания. Введение.

В прошлых постах мы разобрались, что из себя представляет термин lock-free. На очереди финальный босс - wait-free. Как всегда начинаем с определения:

Гарантия Wait-free - каждый поток завершает операцию за ограниченное число шагов, независимо от того, что делают другие потоки.

Вспоминаем написанные ранее lock-free stack и queue. Попадают ли они под определение? Конечно нет. В коде операций вставки и чтения присутствуют бесконечные циклы - о предсказуемости речи быть не может.

🔵 Атомарный счетчик как пример wait-free кода
Базовый пример кода соответствующего гарантии wait-free это связка Atomic Int и операция Add:

type Counter struct {
  value atomic.Int64
}

func (c *Counter) Add(delta int64) int64 {
  return c.value.Add(delta)
}

func (c *Counter) Load() int64 {
  return c.value.Load()
}

Почему это wait-free: под капотом одна аппаратная инструкция (LOCK XADD на x86) и как следствие никаких циклов.

Без аппаратной поддержки нам бы пришлось писать что-то вроде:

type Counter struct {
  value atomic.Int64
}

func (c *Counter) Add(delta int64) int64 {
  for {
    old := c.value.Load()
    newVal := old + delta
    if c.value.CompareAndSwap(old, newVal) {
      return newVal
    }
  }
}

func (c *Counter) Load() int64 {
  return c.value.Load()
}

Как мы видим - снова бесконечный цикл и никакой предсказуемости😁

🔵 Продвинутые примеры Wait-Free алгоритмов
На самом деле тут ситуация двоякая. Есть 2 лагеря:
- Исследователи, ищущие универсальные пути построения алгоритмов без ожидания.
- Практики, создающие реальный софт.

И вот как я понимаю - пересечений маловато. Потому что практики обычно достигают wait-freedom в своих программах за счет явного проектирования и подстраивания под железо. По сути пишут код именно так чтобы конкуренции не было в принципе. И поэтому их программы тоже получаются wait-free.

То что придумывают теоретики это очень общие алгоритмы, которые сложно встроить полностью "с листа" в программу. Только выборочно, какие то конкретные идеи в конкретное место. Я сколько не ресерчил не нашел примеров чистых wait-free структур данных в проде (как например с lock-free). Обычно это были гибриды (wait-free на чтение / lock-free или вообще mutex на запись)

Например: упомянутый выше wait-free счетчик только по семантике wait-free, алгоритмически. А вот на практике с ростом количества ядер и потоков он будет работать все хуже и хуже (вспоминаем посты про синхронизацию кешей CPU). Отсюда и растут ноги у "шардируемых по количеству потоков счетчиков".

🔵 Wait-Free в реальном мире

Лучший пример из реальности который мне приходит в голову - обработка аудио в реальном времени. Если мы в программе работающем со звуком будем писать код без осознания дедлайнов то слушать музыку с комфортом будет невозможно😁

Если интересно почитать об этом подробнее - Real-time audio programming 101: time waits for nothing

Также wait-free механики встречаются в СУБД, Runtime, Linux. Но практически всегда это не академический wait-free a wait-free на осознанных трейдоффах.

На этом всё, в следующих постах попробую сообразить несколько примеров кода академического и практического. Так сказать увидим собственными глазами😊

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №7. Lock-free в реальном мире

Несколько постов подряд были сплошные харды, сложный кодан и отсылки к статьям. При этом я совсем не рассказывал о том где-же встречается всё то что мы рассматривали. Исправляюсь.

🔵 Рантайм языка Golang - очередь горутин
runq - это очередь готовых к выполнению горутин, привязанная к одному процессору (P). Её единственная задача: дать ответ на вопрос «что мне выполнять следующим?». И при этом:
- Отвечать как можно быстрее и дешевле
- С возможностью для простаивающих потоков подбирать чужую работу.

Эта очередь реализована через кольцевой буфер - структуру данных которая отлично работает в конкурентных сценариях и даже без мьютекса.

Ссылка на код в runtime2.go

🔵 Рантайм языка Golang - GC и Lock-free Stack
С помощью этого стека GC коллекционирует указатели на объекты для дальнейшего очищения. Интересный момент - элементом стека является не конкретная ссылка или указатель а буфер из 256 элементов. По сути вставка в стек идет батчами.

Код в golang/go

🔵 Рантайм языка Golang - Lock-Free Deque в sync.Pool
Популярный примитив для контроля аллокаций использует под капотом lock-free структуру данных

Код в golang/go

🔵 Apache Cassandra - Atomic Btree Partition
AtomicBTreePartition - структура, хранящая строки одного ключа партицирования в memtable. Само дерево неизменяемо, обновление строит новую версию с разделением пути (path copying), а затем подменяет ссылку через AtomicReferenceFieldUpdater.compareAndSet.

Код в apache/cassandra

🔵 Linux - lock-free linked list
Структура данных используется в планировщике, RCU, низкоуровневых функциях реализующих Symmetric MultiProcessing, упоминается в реализации сетевых примитивов.

Код в torvalds/linux

—————

На этом всё, надеюсь мне удалось продемонстрировать что lock-free это не просто теория, а очень даже практика😊

Дальше по плану разбор наивысшей гарантии неблокирующей синхронизации - Wait-Free

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №6. Структура данных Queue: от наивного алгоритма к lock-free реализации

В прошлом посте мы закончили разбирать нашу синтетическую задачу про денежки и я обмолвился что есть примеры алгоритмов и структур данных в которых также используется механизм взаимопомощи потоков. У нас уже была заметка про Lock-Free Stack Трайбера и в нем такой механики нет, за ненадобностью.

А что насчет очередей? Фундаментальная структура данных, встречается практически везде. Существует ли у нее lock-free реализация? Этому вопросу я посвятил сегодняшнюю заметку.

Залетайте читать, внутри полноценный экскурс в очереди - от классики до реализаций из научной статьи Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. С примерами на Golang.

Приятного чтения!

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №5. Пишем настоящий lock-free алгоритм с помощью научной статьи.

В прошлых заметках мы прошлись по синтетической задаче TransferMoney вдоль и поперек. Сошлись на том что код с Mutex - самая простая и понятная реализация. Но есть ли у нее альтернативы? Мы попробовали написать код на атомиках, он оказался сложнее и имел баги. В этой заметке я попробую написать код без найденных недостатков и чтобы он соответствовал тому самому определению lock-free.

Под катом:
- Собственный движок транзакций (с отсылкой к Distributed Systems и Software Transactional Memory).
- Как заставить потоки кооперировать, а не конкурировать.

Ни один мьютекс не пострадал (так как не был использован)😁

В рамках телеграма даже не стал пытаться упаковать такое количество контента, поэтому залетайте читать по ссылочке.

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. Спойлер: будет сурово, поэтому готовимся морально и физически😁

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №4. Obstruction-free или Гарантия отсутствия препятствий.

В прошлом посте мы дали все необходимые определения и провели параллели. Но все таки мы с вами теоретики, а не практики, поэтому без кода обойтись не могло.

Гарантию obstruction-free легче всего начать объяснять на примере кода, который мы все хотя бы раз в жизни писали - thread-safe структура данных закрытая мьютексом, например мой любимый счетчик:

std::mutex m;
int shared_value = 0;

void increment() {
    m.lock();          // (*)
    shared_value++;    // долгая критическая секция
    m.lock();
}

Потоков N, где N > 1. Соответствует ли код obstruction-free? Нет, не соответствует.

Вспоминаем как у нас работает ОС. У нас есть планировщик который может остановить выполнение программы в любой момент, чтобы дать ресурс кому то еще. И теперь ситуация:
- Поток №1 захватывает мьютекс и его сразу же усыпляет ОС чтобы разбудить поток №2
- Поток №2 проснулся, пытается тоже сделать increment, но терпит неудачу, так как сосед уже захватил мьютекс.
- Поток №2 после нескольких попыток засыпает потерпев неудачу.

Видим, что нет ни малейшего намека на выполнение требований из определения термина. В программе нет конкуренции, один поток работает, но достигнуть прогресса не может, так как ресурс захвачен соседом. Поэтому делаем вывод - код работающий в блокирующем режиме синхронизации не соответствует гарантии obstrcution-free.

———

Еще ситуация, "работаем в криптовалюте" переводим виртуальные денежки между счетами, естественно с гарантиями отсутствия потерь и дублирования:

struct Account { std::atomic<int> version; int balance; };

void transfer(Account& from, Account& to, int amount) {
    while (true) {
        int v1 = from.version.load();
        int v2 = to.version.load();

        int newFromBalance = from.balance - amount;
        int newToBalance    = to.balance + amount;

        if (from.version.compare_exchange_strong(v1, v1 + 1)) {
            if (to.version.compare_exchange_strong(v2, v2 + 1)) {
                from.balance = newFromBalance;
                to.balance   = newToBalance;
                return; // успех
            }
            from.version.store(v1);
        }
    }
}

Здесь ситуация отличается значительно. Если у нас несколько потоков, но работает только один - мы всегда будем достигать прогресса, так как у нас нет конкурентов за значения атомарных переменных. CAS операции всегда будут успешны и больше одной итерации в цикле нам не грозит. Такой код соответствует гарантии obstruction-free. Но обольщаться рано, не зря в быту обычно все упоминают lock-free а не obstruction-free ведь её недостаточно чтобы писать высокопроизводительные программы. В следующих постах разберемся с этим подробнее. Ваши идеи и соображения что не так с кодом выше буду ждать в комментариях😊

На этом все, спасибо что дочитали до конца, до встречи!

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №3. Что существует кроме Lock-Free? Гарантии в блокирующей и неблокирующей синхронизации.

В посте №1 я дал определение понятию lock-free. Дальше сразу пошёл разбирать ABA-проблему, и это было ошибкой. Всё-таки важный кусочек базы я упустил, поэтому делаю шаг назад.

Когда мы пишем код, мы так или иначе ожидаем от него определённой степени корректности. В случае с программами, в которых есть блокирующие примитивы синхронизации, нам важно, чтобы:

- Примитив обеспечивал эксклюзивный доступ к критической секции - это гарантия mutual exclusion и, по сути, гарантия безопасности нашего кода.
- В нашем коде отсутствовали взаимоблокировки - это гарантия deadlock freedom.
- Поток, намеревающийся попасть в критическую секцию, гарантированно попадал в неё за конечное время - это гарантия starvation freedom.

За дедлоки обычно отвечает программист, гарантии отсутствия голодания обычно падают на рантайм языка программирования (потому что в нём реализован примитив синхронизации) и рантайм ОС, потому что он планирует исполнение потоков.

А какие есть гарантии в неблокирующей синхронизации?

- Гарантия отсутствия препятствий (Obstruction-free): если поток активен и у него нет конкурентов, он должен исполнять полезные инструкции, демонстрировать прогресс.
- Гарантия отсутствия блокировок (Lock-free): наш код гарантирует, что в случае конкурентного исполнения кто-то обязательно достигнет прогресса.
- Гарантия отсутствия ожидания (Wait-free): каждый поток завершает операцию за ограниченное число шагов, независимо от того, что делают другие потоки.

Очень похожие определения, но немного другими словами, не находите? В следующих постах мы на примерах посмотрим, что скрывается за каждым красивым словом.

P.S. Канал переходит в режим Wait-Free, теперь посты гарантированно будут публиковаться за конечное количество дней😁 Я вернулся.

Несколько лет назад я написал целый цикл постов на тему виртуализации. Мотивация - расставить все точки над и, разобраться что есть что. Провести параллели и границы между контейнерами, виртуалками, а также объяснить понянтным языком что же такое Docker. Получилось 4 поста:
- Введение в виртуализацию. Какая бывает, какие проблемы решает
- Аппаратная виртуализация
- Виртуализация на уровне ОС (Контейнеризация)
- Истинно ли утверждение что Контейнеры это Docker?

Почему я вспомнил об этих постах? Мой товарищ Никита у себя в канале взялся еще глубже препарировать тему и уже опубликовал пост о продвинутых технологиях на стыке виртуалок и контейнеров. Он посвящен OCI и тому что современные контейнеры стремятся быть абстракцией поверх VM, а не чем-то сбоку. И дальше идет разбор софта подтверждающего этот тезис.

🔖Контейнер ≠ Docker [1/3] by DevOps Brain

Буду читать сам, поэтому могу смело советовать😊 Если вам такие посты заходят поддержите Никитоса лайком и подпиской❤️

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 стеками и очередями.

Concurrency Mindmap

Написав пост про Lock-Free я осознал что за 2 года, с момента публикации самого первого поста у меня из головы некоторые моменты выпали напрочь (оно и понятно, не каждый день на работе сталкиваюсь с тем о чем рассказываю).

Также пришел к выводу, что убер большие посты саммари по 20+ ссылок тяжело воспринимать тем кто подписался на канал недавно и только погружается в вопрос. А мне очень уж хочется по максимуму вас вовлекать, хоть материал не самый простой.

На мой взгляд воспринимать большой скоуп информации помогают визуализации, поэтому я заморочился и оформил Mindmap по всем материалам. Мне он помог 100%, рассчитываю что он станет отправной точкой в тему Concurrency и позволит выбрать траекторию погружения и увидеть картину вширь.

💎 Исходник доступен по ссылке

-----
🔹 Concurrency, Threads & Processes
🔹 Concurrency & Consistency

Concurrency and Consistency. Non-blocking, lock-free and async. Пост №1. В чем разница между Blocking, Non-blocking, lock-free?

После написания десятков постов о традиционном способе синхронизации конкуррентных программ - блокирующей синхронизации, я задумался, а возможен ли другой путь? Я что-то слышал про lock-free алгоритмы, а также слышал что в распределенных системах существуют conflict-free структуры данных. Вдогонку к этому - флешбэки из десятых когда был максимальный хайп вокруг функционального программирования и отовсюда звучал тезис - "только на ФП языках получается трушный concurrency код". Что же там такого под капотом у этих языков чего нет у остальных я разобраться не успел, но у меня закрались сомнения от таких сильных заявлений, ведь какой бы не был язык все что мы пишем превращается в
- syscalls для ядра ОС написанного на С.
- инструкции для процессора.

Поэтому в новом цикле постов будем развеивать туман. Начнем с разбора основных баззвордов.

Блокирующий (blocking) вызов

Понятие блокирующих функций мы подробно разбирали в прошлых постах. Во время работы один из потоков нашей программы может заблокироваться если наткнулся на блокирующий примитив синхронизации захваченный или например ему понадобилось вызвать системную функцию.

В такие моменты исполнение инструкций потоком останавливается, поток засыпает. Разблокировка потока происходит по сигналу ОС или рантайма ЯП.

Примеры блокирующих функций:
- функции работы с сокетами (send, recv, accept)
- функции работы с файлами (fsync, fdatasync)
- синхронизация (pthread_mutex_lock, pthread_cond_wait, pthread_barrier_wait)
- sleep 😊


Неблокирующий (non-blocking) вызов

Тут все намного проще. Неблокирующая функция - та в которой нет вызовов блокирующих функций. И как следствие остановить выполнение такой функции может только ОС или рантайм языка программирования через вытесняющую многозадачность.

Как обеспечивать синхронизацию в случае когда мы не можем себе позволить засыпать и передавать контроль ОС? Ответ - Spinlocks. Потому что это примитив с активным ожиданием, то есть он заставляет потоки постоянно крутится в ожидании освобождения ресурса.


Lock-free

Понятие lock-free обычно упоминают в контексте структур данных или алгоритмов. В общем случае это код в котором
- Отсутствуют мьютексы. Как следствие невозможно уснуть и передать контроль ОС. Отсутствует блокирующая синхронизация
- Отсутствуют спинлоки. Несмотря на неблокирующую логику спинлоков у нас в программе создается ситуация эксклюзивного владения и при захвате примитива одним потоком у остальных нет возможности продвигаться и делать полезную работу.


С чем мы в итоге остаемся?

Для того чтобы строить lock-free алгоритмы и логику у нас остается только один путь - самостоятельно писать код на атомарных операциях (CAS, TAS, FAA).

Без этого с большой вероятностью наша программа будет работать некорректно, так как все равно даже без примитивов синхронизации потоки программы в любое время могут быть остановлены ОС и запущены спустя время. И если поток был остановлен где то посередине важной операции и такой сценарий не учтен в коде нас будут ждать сюрпризы😁


Нужно ли стремиться к lock-free коду?

Когда мы пишем код, используем структуры данных, алгоритмы мы всегда взвешиваем все за и против. В Concurrency тоже самое.

Алгоритм / структура данных построенный на Blocking примитивах работает предсказуемо и понятно, не самый сложный код. Поддержка в любом ЯП и ОС из коробки. Для низконагруженных приложений - обязательно к использованию. Под высокой нагрузкой может стать бутылочным горлышком.

Алгоритмы и СД со спинлоками или трушные lock-free без них потенциально позволяют увеличить пропускную способность системы, но все равно существует риск пауз связанных с активным ожиданием. Плюс такие программы все таки сложнее проектировать и реализовывать. Подступаться к снаряду стоит после того как убедились что бутылочное горлышко именно в блокирующих примитивах.

На этом первый пост всё, спасибо что читали, оставляйте комментарии и реакции, чтобы я видел что вы ждали посты❤️

Concurrency, Synchronization and Consistency. Double checked locking problem

Пока готовил материал для новых постов, понял что не рассказал о задачке с которой иногда приходится иметь дело в работе.

Представьте что у нас конкурентное приложение. И в нем есть объект обязанный существовать в единственном экземпляре. С ним и будут работать наши потоки. Инициализация объекта тяжелая, занимает какое то время.

Варианты:
- Инициализация ресурса на старте.
- Инициализация в момент запроса ресурса (lazy init).

Вы с командой подумали и решили - на старте слишком долго, давайте делать лениво. Посидели, подумали и получилось вот так:

type Cache struct {
 data map[string]string
}

type Service struct {
 cache *Cache
 mu    sync.Mutex
}

func (s *Service) GetCache() *Cache {
 s.mu.Lock()
 defer s.mu.Unlock()

 if s.cache == nil {
  s.cache = &Cache{
   data: make(map[string]string),
  }
 }
 return s.cache
}

Всё четко работает, но после релиза видите по метрикам и профилировщику что горутины начали конкурировать в этом кусочке кода (он вызывается часто). Надо что-то менять, и вы приходите к выводу - мьютекс нужен только когда объект не существует, иначе нужно просто вернуть ресурс.

package main

// код выше не изменился

func (s *Service) GetCache() *Cache {
 if s.cache == nil {
  s.mu.Lock()
  defer s.mu.Unlock()

  if s.cache == nil {
   s.cache = &Cache{
    data: make(map[string]string),
   }
  }
 }
 return s.cache
}

Все работает четко, но код слегка попахивает. Можно ли красивее?

// код выше не изменился

type Service struct {
 cache *Cache
 once  sync.Once
}

func (s *Service) GetCache() *Cache {
 s.once.Do(func() {
  s.cache = &Cache{
   data: make(map[string]string),
  }
 })
 return s.cache
}

Это и есть Double Checked Locking (DCL). На первый взгляд может показаться что проблема высосана из пальца, но на самом деле Go просто обошелся малой кровью - спасибо за простую модель памяти. В Java раньше был целый челлендж с тем чтобы правильно написать подобный код - почитать об этом можно здесь и здесь. Вторая ссылка так вообще монументальная, под ней подписался в том числе Joshua Bloch - автор Effective Java. В его книге как раз есть глава посвященная этой проблеме. Если на моем канале есть джависты, ставьте 🐳 и рассказывайте как вы писали свой первый синглтон😁

Приходилось ли вам писать подобный код и к чему это привело?

Мой коллега Матвей на прошлой неделе дебютировал на Хабре с классным лонгридом о своем опыте добавления в язык Golang "условного выражения". Все по полочкам, как мы любим - небольшое теоретическое введение, и очень много кода. Если вы интересуетесь компиляторами и дизайном языков - вам точно будет что обсудить с Матвеем в комментариях.

Лайки и репосты горячо приветствуются😊

https://habr.com/ru/articles/1012900/