Многозадачность и многопоточность — распространенные заблуждения и недопонимания

Когда я предложил перевести на русский мою последнюю статью Easy Concurrency with Python Shared Objects на английском, поступило предложение "написать в несколько раз короче и понятнее". Просьба более чем обоснована. Поскольку я уже порядка десяти лет пишу многопоточку и БД, то описываемые мной логические связи выглядели самоочевидно, и я ошибочно расчитывал на аудиторию из трех с половиной человек, которые сидят сейчас где-то в яндексе или гугле. Судя по всему, они там и сидят, но тема им не интересна, поскольку в питоне нет настоящих потоков, а значит для этих людей такого языка программирования не существует. Потому я немножко снижаю планку и делаю общий обзор проблематики параллельных вычислений для людей, которые в них разбираются, но не являются экспертами в области.

Из-за чего весь сыр-бор?

a := 1
b := a + 1
print(a)
print(b)

Цикл {
    a := a + 1
    b = b + 1
    a := a - 1
    b := b - 1
}

Два процесса выполняются параллельно и независимо. Если мы возьмем первую инструкцию процесса 1, то параллельно с ней может выполниться любая из четырех команд. Вторая команда процесса 1 аналогично не ограничивает выполнение в процессе 2, потому она может выполняться параллельно с любой из четырех команд. Для простоты допускаем, что одна команда атомарна. Всего число возможных сценариев выполнения первого процесса 4^4 = 256. Если в аналогичных первом и втором процессах по десять инструкций, то число различных вариантов выполнения равно 10¹⁰, то есть, 10 миллиардов. За пару минут мы можем написать 10 миллиардов программ! Вау, мы крутые! А если серьезно, то нам не хватит никакого времени, чтобы отладить все эти 10 миллиардов сценариев выполнения.

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

Что там сложного? Есть конкуренция за ресурс — повесь мьютекс. Я так всегда делаю.

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

А еще лучше вообще иметь только одну блокировку на все вилки, ложки, философов, и стол одновременно — создатели питона примерно так и подумали.

Если же вы решили использовать множественные блокировки, то неявные и допускающие вложенность блокировки (Rust std::sync::Mutex или Java synchronized) — путь в никуда, поскольку становится очень легко создать неочевидно дедлочащуюся программу. На самом деле, даже без дедлоков детальные блокировки не являются панацеей, поскольку простые блокировки, они же "семафоры Дейкстры", ограничены в своих способностях:

→ Задача о курильщиках

Хотя задачу курильщиков и возможно решить семафорами Дейкстры, такие "семафоры курильщика" дают сложный в понимании и поддержке алгоритм, при том, что задача, казалось бы, элементарна. Потому вторым по популярности механизмом блокировок стали условные переменные и более общий аспект оных — мониторы (в том числе уже упомянутое Java synchronized). Правда, проблемы дедлоков при множественных блокировках они не решают.

Что же делать? Мы все умрем? Да, но проблему дедлоков можно решить. Одно из остроумных решений для задачи обедающих философов предложил сам Дейкстра — брать детальные блокировки только в одном заранее заданном порядке. Следующий забавный прием — брать блокировки всем скопом одной командой либо отменять взятие блокировки. Такое можно реализовать на любой абстракции с примитивом try-lock (например, compare-and-swap), при помощи бесконечного цикла (например, std::lock из библиотеки C++).

Одна из самых последних и перспективных альтернатив блокировкам — это транзакционная память, по сути атомарный compare-and-swap на большом числе ячеек. Идею транзакционной памяти развил в конкретную программную реализацию, STM, мой любимый автор книг и статей по многопоточности — Нир Шавит. Главное преимущество STM — отсутствие дедлоков. В каком-то смысле транзакционная память достаточно стара, если вспомнить, что реляционные СУБД давно умели в транзакции. Программная транзакционная память, как правило, берет блокировки всем скопом, как в описанном выше алгоритме предварительной блокировки, но делает это не до выполнения операций изменения ячеек памяти, а после — таким образом нам не обязательно до начала работы алгоритма знать список нужных нам блокировок и длительность этих блокировок минимальна. Из популярных готовых решений на эту тему можно вспомнить Clojure и GHC.

У наивной реализации STM есть проблема — при интенсивных конфликтах меж потоками приложение большую часть времени крутит откаты транзакций вхолостую: подробнее.

Решение этой проблемы уже придумано за нас — это алгоритм раннего разрешения конфликтов, при котором реализация не ждет окончания транзакции для того, чтобы осознать невозможность применения ее результатов, а сразу прерывает одну из конфликтующих транзакций. По сути это способ организации детальных блокировок с разрешением дедлоков через откат изменений. Такой подход я и перенял при реализации Python Shared Object.

Коротко: взаимоисключающая блокировка не является основным средством организации доступа к разделяемой памяти и вообще разделяемым ресурсам, но именно этими блокировками чаще всего злоупотребляют.

Разделяемая память не нужна! Только акторная модель и сообщения (Erlang, Tcl)

Подход, известный также как "у меня болит палец — отрежу себе руку!".

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

• состояние с последовательными переходами, синхронными и заранее предсказуемыми, потенциально в виде большого вектора, как то SIMD, GPGPU, компьютерные и даже живые нейронные сети. Да, живые организмы чутко воспринимают задержки входных сигналов, потому могут ощущать время и движение;
• асинхронное взаимодействие, как то сообщение в очереди или состояние-флаг, запись которого и чтение условно не зависят от задержек.

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

Асинхронная передача сообщений сама по себе не способна обеспечить строгую согласованность состояния/данных на разрозненных узлах. Если быть точным, то в асинхронной системе с отказами узла (или непредсказуемыми задержками ответа) невозможно детерминированное достижение консенсуса (достижение единого согласованного решения между всеми узлами) в соответствии с FLP-недостижимостью, а также производной теоремой CAP. В случае, если мы имеем некую гарантию времени ответа от узла и отсутствие отказов, мы можем достигнуть некоего условного консенсуса за время порядка нескольких круговых задержек передачи сообщения (то есть, периода выполнения запроса и обратного ответа).

Недетерминированность достижения консенсуса в асинхронной системе с отказами значит, что прийти к единому решению в такой системе — это рулетка, полнейшая случайность, хотя шанс "выиграть" в ней и повышается с течением времени, но он никогда не может быть меньше двух круговых задержек сети. По этой причине в реальности передача сообщений не так уж прозрачна и не так бесплатна при увеличении дистанции, например, при переходе от передачи сообщений между потоками одного процесса ОС к передаче сообщений между удаленными датацентрами. В случае большой круговой задержки протоколы организации распределенных БД, как то Raft, Zab, MultiPaxos, минимизируют проблемы координации, ограничивая ее выборами лидера, и применяют случайную задержку при выборах лидера. Аналогично Ethernet использует случайную задержку при конфликте использования канала.

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

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

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

YandexDB, она же Calvin, использует Zookeeper для организации глобально согласованной истории изменений. Сам Zookeeper использует асинхронные сообщения только для выбора лидера — работа с данными происходит синхронно на выбранном эталонном узле (лидере). Создатели экспериментальной СУБД Tango заявляют, что реализовывает ZooKeeper в 300 строчек кода. Однако, сам оригинальный Tango использует нереплицируемый счетчик в качестве опорного средства координации, потому не обеспечивает гарантий отказоустойчивости ZooKeeper. И по итогу для организации сравнимых гарантий в этой "реализации ZooKeeper" на Tango вам нужно реализовать координацию Tango на… ZooKeeper. Это похоже на игру "горячий пирожок".

Почему в этот горячий пирожок играют? Потому что идеальное решение невозможно чисто теоретически (FLP-недостижимость) — все практически реализации являются тем или иным компромиссом. Но есть желающие "идеальное решение" купить, потому используется популярный маркетинговый прием: недостатки существующих решений уже хорошо известны, а недостатки нашей новой системы еще не известны… значит можно сказать, что их нет. Так и развиваются многие Big Data проекты.

Когда же у вас есть хотя бы общий атомарный счетчик, а еще лучше — общий атомарный список транзакций, дальше вы можете наращивать объем "нагрузочных данных" как угодно, реплицировать их в eventual consistency хранилищах, придавать им произвольную форму (как это сделало в том же Tango, давшем пользователю свободу выбора формы данных) — это всё имеет второстепенное значение и легко меняется, хотя многие люди по прежнему обращают внимание на обёртку, а не на суть. То есть, ходовые качества машины определяются двигателем, трансмиссией, рулевой системой, но большинство видит лишь красивый кузов и отделку салона, к сожалению. Я хочу здесь подчеркнуть, что ZooKeeper в случае Tango, YandexDB, Calvin, ClickHouse и прочих аналогичных проектов — это не "просто вспомогательная штука", как его рисуют, а ключевой компонент и большая часть сложности реализации всей СУБД, и этот компонент, к тому же, полностью определяет число транзакций в секунду, которые сможет обработать весь кластер.

Проблем неопределенности в том числе избегает реализация синхронной передачи сообщений, иначе известная как "взаимодействующие последовательные процессы" (Communicating sequential processes, CSP), которые являются давно известным подходом. В частности, этот подход выбрал в качестве своего фундамента популярный язык Go и сильно менее популярные предшественники оного, языки Limbo и Newsqueak. Атомарная операция отправки сообщения через канал гарантирует, что либо сообщение отправлено и отправка одновременно подтверждена, либо оно не отправлено — для обеспечения этой синхронизации используется разделяемое состояние канала скрытое от программиста на Go.

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

Золотая середина

Асинхронные алгоритмы и синхронные алгоритмы, передача сообщений и разделяемое состояние дополняют друг друга. Проблемы возникают только когда одним из подходов злоупотребляют, а второй — игнорируют. Невозможность организации простого эффективного разделяемого состояния на питоне привела к появлению массы многочисленных "костылей" — это и простые РСУБД, как то PostgreSQL и MySQL, и NoSQL вроде Redis/MemCached, и очереди сообщений (RabbitMQ). Примерно на этой волне я и решил написать Python Shared Objects. В упомянутом Erlang уже давно есть специальный модуль для организации разделяемой памяти: подробнее.

Также, сама реализация Erlang/OTP неявно использует разделяемую память. Даже если из питона получится жалкое подобие Erlang — это все равно намного лучше, чем тот безнадежно однозадачный (не путать с зелеными потоками/concurrent IO) интерпретатор питона, который мы имеем сейчас.

Состояние/ячейки данных, используемое для координации, должно быть разделяемым и изменяться строго последовательно. Независимые состояния должны оставаться независимыми, асинхронно выполняющиеся задачи должны выполняться асинхронно. Если лишь часть задач требуют координации, то они и должны разделять некоторую часть состояния для своей координации. Если возможно выполнить одинаковый набор инструкций для большого числа в ячеек в векторе — выполните его при помощи SIMD/CUDA/OpenCL, а не созданием асинхронно выполняющихся потоков, которые потом придется обратно синхронизировать.

Например, оригинальная STM от Нир Шавита использует глобальный атомарный счетчик для координации всех задача, но в остальном "общими" ячейки данных становятся только когда они по-настоящему общие для нескольких задач. Аналогичный подход с общим атомарным счетчиком номера/приоритета транзакции и детальными блокировками также применяет моя реализация STM в виде Python Shared Objects.

Тесты, еще тесты, нужно больше тестов

Как же тестировать и отлаживать многозадачные и распределенные системы? Основная проблема многопоточных, многозадачных, распределенных систем — это недетерминированность их поведения. То есть, ваша система может работать пять лет, а потом резко начать падать из-за какого-то незначительного изменения алгоритма.

В общем случае ответ на вопрос "как тестировать?" — "никак", вы подходите к проблемы с неправильной стороны. Но не расстраивайтесь — это нормально, так делает много кто. По этой причине, например, большинство распределенных СУБД, заявлявших про строгую согласованность данных и отказоустойчивость, в жестких тестах на Jepsen показывают, что на самом деле никогда не обеспечивали как минимум одну из этих гарантий: подробнее.

Тестирование — это способ обнаружить наличие проблемы, но тестированием невозможно доказать отсутствие проблем. Если в качестве отказоустойчивого хранилища согласованных данных вы используете не ZooKeeper и не Etcd, то с большой вероятностью ваша система потеряет/испортит данные или вовсе упадет при потере лидера. Если вы уделите пару часов чтению серии статей по ссылке, то вы узнаете, что какой-нибудь Galera Cluster способен нарушать согласованность даже на полностью исправном кластере, а MongoDB не дает даже "eventual consistency" гарантий при отказах (то есть, в MongoDB ваши данные из подтвержденных транзакций может быть сохранятся, а может быть не сохранятся). Однако, даже если вы построили систему на базе условно надежных ZooKeeper или Etcd, вы не знаете, сколько еще проблем возникло из-за некорректного использования оных в самописном коде.

Единственный более-менее гарантированный способ построить работающую систему — это прежде всего грамотно подойти к ее проектированию и реализации, доказать корректность алгоритма, а не полагаться на популярный нынче метод тестирования и "авось". Вторая линия обороны — это тестирование, но не простое. Разработчики должны понимать, что если ошибка есть, то ее необходимо обнаружить, а не замести под ковер и подпереть костылем. То есть, без участия и сотрудничества самих разработчиков невозможно эффективно произвести тестирование. Необходимо тестировать систему в самых неудобных и опасных режимах, предусмотреть в исходном коде отладочные опции для более частого срабатывания редких фрагментов кода — в том числе такой подход я задействовал для своего проекта Python Shared Objects. В случае отказоустойчивых кластеров обязательно необходимо периодически симулировать отказы, как это делает, например, Яндекс.

Поскольку очень часто проблема происходит только один раз и больше никогда не повторяется, то большую ценность имеет логирование, создание снимков состояния системы во время проблемы. Для последнего, например, есть замечательная утилита rr от Mozilla, которая была разработана специально для отладки многопоточного кода в Firefox. Эта утилита позволяет выполнить код в обратном направлении, точно восстанавливая последовательность выполнения асинхронных потоков, приведшую к ошибке. И хотя облака нынче стали популярным хайпом, выбор инструментов для отладки многозадачного кода и распределенных систем на удивление скудный. Для распределенных систем есть упомянутый Jepsen, для многопоточных есть, например, ThreadSanitizer.

К сожалению, для тестирования моего Python Shared Objects мне так и не удалось найти готового решения для неинтрузивного логирования. Неинтрузивного — поскольку для многопоточного кода имеет место так "эффект наблюдателя" — когда при логировании программа ведет себя совсем не так, как без него. Когда-то давно для закрытой разработки я сам реализовывал неинтрузивное логирование на Delphi, но это было давно и неправда, а на сишные программы этот код довольно плохо налазит.

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