Latest posts
Евгений Козлов пишет про IT
21 Sept, 16:57edited
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 структура данныхЕвгений Козлов пишет про IT
21 Sept, 06:30edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №12. Заключение.Когда я начинал цикл постов у меня было ожидание что lock-free это - ускорять программы ценой усложнения кода. При этом интуиция шептала, что в таком случае мьютексы автоматически становятся ненужными, а они живее всех живых. С этой точки я и решил погрузиться в вопрос в поисках истины.По итогам цикла постов я могу с уверенностью сказать - выбор между locking и non-blocking синхронизацией это выбор проблем с которыми ты готов иметь дело + ограничения накладываемые предметной областью.Блокирующая синхронизация это про + простоту + отличную среднюю производительность- дедлоки - голодание - livelock - инверсию приоритетов. - thundering herd - lock convoyСтрашные слова, но с ними вполне можно работать. Единственный момент - в совокупности с вытесняющей многозадачностью блокировки не способны датьЕвгений Козлов пишет про IT
20 Sept, 06:55edited
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 важна неЕвгений Козлов пишет про IT
19 Sept, 07:17edited
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, с оговорками чтоACM ConferencesWait-free queues with multiple enqueuers and dequeuers | Proceedings of the 16th ACM symposium on Principles and practice of parallel…Евгений Козлов пишет про IT
17 Sept, 11:32edited
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 }Евгений Козлов пишет про IT
16 Sept, 07:06edited
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.Евгений Козлов пишет про IT
15 Sept, 07:04edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №7. Lock-free в реальном миреНесколько постов подряд были сплошные харды, сложный кодан и отсылки к статьям. При этом я совсем не рассказывал о том где-же встречается всё то что мы рассматривали. Исправляюсь.🔵 Рантайм языка Golang - очередь горутин runq - это очередь готовых к выполнению горутин, привязанная к одному процессору (P). Её единственная задача: дать ответ на вопрос «что мне выполнять следующим?». И при этом: - Отвечать как можно быстрее и дешевле - С возможностью для простаивающих потоков подбирать чужую работу.Эта очередь реализована через кольцевой буфер - структуру данных которая отлично работает в конкурентных сценариях и даже без мьютекса.Ссылка на код в runtime2.go🔵 Рантайм языка Golang - GC и Lock-free Stack С помощью этого стека GC коллекционирует указатели на объекты для дальнейшегоЕвгений Козлов пишет про IT
12 Sept, 07:27
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.Приятного чтения!TeletypeСтруктура данных Queue: от наивного алгоритма к lock-free реализацииВ прошлом посте мы разобрались что такое lock-free алгоритм на примере задачи TransferMoney. В заметке я обмолвился что идеи...Евгений Козлов пишет про IT
3 Sept, 16:43edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №5. Пишем настоящий lock-free алгоритм с помощью научной статьи.В прошлых заметках мы прошлись по синтетической задаче TransferMoney вдоль и поперек. Сошлись на том что код с Mutex - самая простая и понятная реализация. Но есть ли у нее альтернативы? Мы попробовали написать код на атомиках, он оказался сложнее и имел баги. В этой заметке я попробую написать код без найденных недостатков и чтобы он соответствовал тому самому определению lock-free.Под катом: - Собственный движок транзакций (с отсылкой к Distributed Systems и Software Transactional Memory). - Как заставить потоки кооперировать, а не конкурировать.Ни один мьютекс не пострадал (так как не был использован)😁В рамках телеграма даже не стал пытаться упаковать такое количество контента, поэтому залетайте читать по ссылочке.TeletypeПишем ThreadSafe код без Mutex или что такое этот ваш Lock-free?тоВ прошлых заметках мы прошлись по синтетической задаче TransferMoney вдоль и поперек. Сошлись на том что код с Mutex самая простая...Евгений Козлов пишет про IT
21 Aug, 06:40edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №4. Гарантия отсутствия блокировок.В прошлом посте рассмотрели классический пример - конкурентная работа со счетами пользователей. Код довольно простой и наглядный, и даже соответствует гарантии которую разбирали.Но с ним есть проблема - он неправильный. - Мы буквально можем потерять операцию и как следствие деньги. - У нас возможен дедлок, если в один и тот же момент два пользователя переведут друг другу денежку.Как чинить эти проблемы? Шаг №1 - Заменить атомики на мьютексы. Шаг №2 - Добавить упорядочивание в захват мьютексов. package mainimport ( "sync" "unsafe" )type SafeAccount struct { mu sync.MutexTelegramЕвгений Козлов пишет про ITConcurrency and Consistency. Non-blocking, lock-free and async. ABA Problem Сегодня поговорим о проблеме неразрывно связанной с lock-free алгоритмами. Она возникает в коде на атомиках и демонстрирует наглядно что имея атомики в коде, казалось бы безопасный…Евгений Козлов пишет про IT
10 Aug, 06:58edited
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 захватывает мьютекс иЕвгений Козлов пишет про IT
8 Aug, 10:25edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №3. Что существует кроме Lock-Free? Гарантии в блокирующей и неблокирующей синхронизации.В посте №1 я дал определение понятию lock-free. Дальше сразу пошёл разбирать ABA-проблему, и это было ошибкой. Всё-таки важный кусочек базы я упустил, поэтому делаю шаг назад.Когда мы пишем код, мы так или иначе ожидаем от него определённой степени корректности. В случае с программами, в которых есть блокирующие примитивы синхронизации, нам важно, чтобы:- Примитив обеспечивал эксклюзивный доступ к критической секции - это гарантия mutual exclusion и, по сути, гарантия безопасности нашего кода. - В нашем коде отсутствовали взаимоблокировки - это гарантия deadlock freedom. - Поток, намеревающийся попасть в критическую секцию, гарантированно попадал в неё за конечное время - это гарантия starvation freedom.За дедлоки обычноЕвгений Козлов пишет про IT
23 May, 09:23edited
Несколько лет назад я написал целый цикл постов на тему виртуализации. Мотивация - расставить все точки над и, разобраться что есть что. Провести параллели и границы между контейнерами, виртуалками, а также объяснить понянтным языком что же такое Docker. Получилось 4 поста: - Введение в виртуализацию. Какая бывает, какие проблемы решает - Аппаратная виртуализация - Виртуализация на уровне ОС (Контейнеризация) - Истинно ли утверждение что Контейнеры это Docker?Почему я вспомнил об этих постах? Мой товарищ Никита у себя в канале взялся еще глубже препарировать тему и уже опубликовал пост о продвинутых технологиях на стыке виртуалок и контейнеров. Он посвящен OCI и тому что современные контейнеры стремятся быть абстракцией поверх VM, а не чем-то сбоку. И дальше идет разбор софта подтверждающего этот тезис.🔖Контейнер ≠ Docker [1/3] by DevOps BrainБуду читать сам, поэтому могу смелоЕвгений Козлов пишет про IT
18 May, 15:26edited
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]] }go.devGo Playground - The Go Programming LanguageЕвгений Козлов пишет про IT
24 Apr, 08:05edited
Concurrency MindmapНаписав пост про Lock-Free я осознал что за 2 года, с момента публикации самого первого поста у меня из головы некоторые моменты выпали напрочь (оно и понятно, не каждый день на работе сталкиваюсь с тем о чем рассказываю).Также пришел к выводу, что убер большие посты саммари по 20+ ссылок тяжело воспринимать тем кто подписался на канал недавно и только погружается в вопрос. А мне очень уж хочется по максимуму вас вовлекать, хоть материал не самый простой.На мой взгляд воспринимать большой скоуп информации помогают визуализации, поэтому я заморочился и оформил Mindmap по всем материалам. Мне он помог 100%, рассчитываю что он станет отправной точкой в тему Concurrency и позволит выбрать траекторию погружения и увидеть картину вширь.💎 Исходник доступен по ссылке----- 🔹 Concurrency, Threads & Processes 🔹 Concurrency & Consistency
Евгений Козлов пишет про IT
21 Apr, 08:11edited
Concurrency and Consistency. Non-blocking, lock-free and async. Пост №1. В чем разница между Blocking, Non-blocking, lock-free?После написания десятков постов о традиционном способе синхронизации конкуррентных программ - блокирующей синхронизации, я задумался, а возможен ли другой путь? Я что-то слышал про lock-free алгоритмы, а также слышал что в распределенных системах существуют conflict-free структуры данных. Вдогонку к этому - флешбэки из десятых когда был максимальный хайп вокруг функционального программирования и отовсюда звучал тезис - "только на ФП языках получается трушный concurrency код". Что же там такого под капотом у этих языков чего нет у остальных я разобраться не успел, но у меня закрались сомнения от таких сильных заявлений, ведь какой бы не был язык все что мы пишем превращается в - syscalls для ядра ОС написанного на С. - инструкции для процессора.Поэтому вЕвгений Козлов пишет про IT
8 Apr, 12:27edited
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 }Problem pioneer“Double-checked locking is a matter of style, not performance”Double-checked locking is 100 times faster than synchronized locking, but there’s a caveatЕвгений Козлов пишет про IT
23 Mar, 09:01edited
Мой коллега Матвей на прошлой неделе дебютировал на Хабре с классным лонгридом о своем опыте добавления в язык Golang "условного выражения". Все по полочкам, как мы любим - небольшое теоретическое введение, и очень много кода. Если вы интересуетесь компиляторами и дизайном языков - вам точно будет что обсудить с Матвеем в комментариях.Лайки и репосты горячо приветствуются😊https://habr.com/ru/articles/1012900/Евгений Козлов пишет про IT
22 Mar, 07:13edited
Метрики? Метрики! Метрики...А есть ли жизнь за пределами Prometheus?Обычно инженеры подразумевают одно и тоже когда говорят про метрики и Prometheus. Мы работаем с PromQL синтаксисом, устанавливаем экспортеры расположенные в Github организации Prometheus. Выглядит так что это одно и тоже. Но что если нет?Краткая историческая справка Prometheus был создан на SoundCloud в 2012 году и с тех пор стал стандартом для мониторинга систем. Если упростить система мониторинга состоит из:- Приложения экспортирующего метрики. Это может быть ваше приложение с метриками оформленными вами. Для их экспорта вам требуется специальный SDK. Альтернатива - взять готовый экспортер для сбора стандартных метрик (кафки, постгреса, или просто вирт. машины). - Prometheus server. Отвечает за сбор метрик с целей. Экспорт метрик осуществляется за счет публикации HTTP ручки с набором метрик. И пром опрашиваетOnidelOnidel CloudWhen running Prometheus at scale, the built-in local storage quickly becomes a bottleneck. For organizations processing millions of metrics across distributed sЕвгений Козлов пишет про IT
17 Mar, 09:56edited
Метрики? Метрики! Метрики...Пишем и настраиваем алертыПрошлый пост очень тепло был принят вами, судя по реакцим и продвинутой статистике, поэтому я пошел дальше рыскать по закромам и генерить идеи чем бы еще интересным и полезным с вами поделиться. Сегодня хочется поговорить о развитии системы мониторинга за счет внедрения механизмов алертирования.Шаг №1 - Перестать глазами мониторить дашборды и графики😑 Проблема - за дашбордами не уследить, слишком много визуализаций, можно что-то пропустить, да и много времени уходит.✅ Решение - настроить уведомления для метрик которые достигли порогового значения. Называют их алерты.🛠 Тулинг - https://github.com/prometheus/alertmanager. Позволяет настроить декларативно правила рассылки алертов по метрикам. Поддерживается множество получателей, в том числе Telegram.Шаг №2 - На какие события мне нужны алерты?Современные инструменты уже
Related Channels
Other channels in the same section of the catalogue.
