Евгений Козлов пишет про 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 | 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)
- 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. Пост №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. Пост №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 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. Пост №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 без них потенциально позволяют увеличить пропускную способность системы, но все равно существует риск пауз связанных с активным ожиданием. Плюс такие программы все таки сложнее проектировать и реализовать. Подступаться к такому снаряду стоит после того как убедились что бутылочное горлышко в блокирующих примитивах.

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