Структурированный параллелизм (Structured Concurrency)

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

(Примечание: первые несколько разделов говорят об абстрактной концепции структурированного параллелизма и не специфичны для Rust или асинхронного программирования (ср., синхронное параллельное программирование с потоками). Я использую «задача» (task) для обозначения любого потока, асинхронной задачи или другого подобного примитива параллелизма).

Структурированный параллелизм — это философия проектирования параллельных программ. Для того чтобы программы полностью соответствовали принципам структурированного параллелизма, требуются определенные языковые features и библиотеки, но многие преимущества доступны при следовании философии и без таких features. Структурированный параллелизм не зависит от языка и примитивов параллелизма (потоки vs async и т.д.). Многие люди нашли идеи из структурированного параллелизма полезными при программировании на асинхронном Rust.

Основная идея структурированного параллелизма заключается в том, что задачи организованы в дерево. Дочерние задачи начинаются после своих родителей и всегда завершаются до них. Это позволяет результатам и ошибкам всегда передаваться обратно родительским задачам и требует, чтобы отмена родительских задач всегда распространялась на дочерние задачи. В первую очередь, временная область видимости (temporal scope) следует за лексической областью видимости (lexical scope), что означает, что задача не должна переживать функцию или блок, в котором она создана. Однако это не является требованием структурированного параллелизма, пока более долгоживущие задачи реифицированы в программе каким-либо образом (обычно с использованием объекта для представления временной области видимости дочерней задачи внутри ее родительской задачи).

TODO диаграмма

Структурированный параллелизм назван по аналогии со структурированным программированием — идеей о том, что поток управления должен быть структурирован с использованием функций, циклов и т.д., а не произвольных переходов (goto).

Прежде чем мы рассмотрим структурированный параллелизм, полезно поразмышлять о том, в каком смысле распространенные параллельные designs неструктурированы. Типичный шаблон заключается в том, что задача запускается с помощью какого-либо оператора порождения (spawning). Эта задача затем выполняется до завершения параллельно с другими задачами в системе (включая задачу, которая ее породила). Нет никаких ограничений на то, какая задача завершится первой. Программа, по сути, представляет собой просто мешок задач, которые живут независимо и могут завершиться в любой момент. Любое общение или синхронизация задач происходит ad hoc, и программист не может предполагать, что любая другая задача все еще будет работать.

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

Стоит отметить, что структурированный параллелизм — это дисциплина программирования, которая накладывает ограничения на вашу программу. Так же, как функции и циклы менее гибки, чем goto, структурированный параллелизм менее гибок, чем простое порождение задач. Однако, как и в случае со структурированным программированием, затраты структурированного параллелизма на гибкость перевешиваются выигрышем в предсказуемости.

Принципы структурированного параллелизма

Ключевая идея структурированного параллелизма заключается в том, что все задачи (или потоки, или что-то еще) организованы в виде дерева. Т.е., каждая задача (кроме главной задачи, которая является корнем) имеет одного родителя, и нет циклов родителей. Дочерняя задача запускается своим родителем2 и должна всегда завершить выполнение до своего родителя. Между родственными задачами (siblings) нет ограничений. Родитель задачи не может измениться.

При рассуждении о программах, реализующих структурированный параллелизм, ключевым новым фактом является то, что если задача активна, то все ее задачи-предки также должны быть активны. Это не гарантирует, что они находятся в хорошем состоянии — они могут находиться в процессе завершения работы или обработки ошибки, но они должны работать в какой-то форме. Это означает, что для любой задачи (кроме корневой задачи) всегда есть активная задача, которой можно отправить результаты или ошибки. Действительно, идеальный подход заключается в том, что обработка ошибок языка расширяется так, что ошибки всегда распространяются на родительскую задачу. В Rust это должно применяться как к возврату Result::Err, так и к панике.

Более того, время жизни дочерних задач может быть представлено в родительской задаче. В общем случае время жизни задачи (ее временная область видимости) привязана к лексической области видимости, в которой она запущена. Например, все задачи, запущенные внутри функции, должны завершиться до возврата из функции. Это чрезвычайно мощный инструмент для рассуждений. Конечно, это слишком ограничительно для всех случаев, поэтому временная область видимости задач может выходить за пределы лексической области видимости с использованием объекта в программе (часто называемого «областью видимости» (scope) или «питомником» (nursery)). Такой объект может передаваться или храниться и, таким образом, иметь произвольное время жизни. У нас все еще есть важный инструмент для рассуждений: задачи, привязанные к этому объекту, не могут пережить его (в Rust это свойство позволяет нам интегрировать задачи с системой времени жизни).

Вышесказанное приводит к еще одному преимуществу структурированного параллелизма: он позволяет нам рассуждать об управлении ресурсами across несколько задач. Код очистки вызывается, когда ресурс больше не будет использоваться (например, закрытие файлового дескриптора). В последовательном коде проблема того, когда вызывать код очистки, решается путем обеспечения вызова деструкторов, когда объект выходит из области видимости. Однако в параллельном коде объект все еще может использоваться другой задачей, поэтому неясно, когда следует очищать (подсчет ссылок или сборка мусора являются решениями во многих случаях, но затрудняют рассуждения о времени жизни объектов, что может привести к ошибкам, а также имеет накладные расходы во время выполнения).

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

Если задача завершается досрочно из-за ошибки (в Rust это может означать панику, а также досрочный возврат), то перед возвратом задача должна дождаться завершения всех своих дочерних задач. На практике досрочный возврат должен запускать отмену дочерних задач. Это аналогично панике в Rust: паника запускает деструкторы в текущей области видимости перед подъемом по стеку, вызывая деструкторы в каждой области видимости до завершения программы или перехвата паники. При структурном параллелизме досрочный возврат должен запускать отмену дочерних задач (и, следовательно, очистку объектов в этих задачах) и спускаться по дереву задач, отменяя все (транзитивные) дочерние задачи.

Некоторые designs очень естественно работают в условиях структурированного параллелизма (например, рабочие задачи с одной работой для выполнения), в то время как другие подходят не так хорошо. Обычно это шаблоны, в которых не быть привязанным к конкретной задаче является особенностью, например, пулы рабочих или фоновые потоки. Даже при использовании этих шаблонов задачи обычно не должны переживать всю программу, поэтому всегда есть одна задача, которая может быть родителем.

Реализация структурированного параллелизма

Примером реализации структурированного параллелизма является библиотека Python Trio. Trio — это библиотека общего назначения для асинхронного программирования и ввода-вывода, разработанная вокруг концепций структурированного параллелизма. Программы Trio используют конструкцию async with для определения лексической области видимости для порождения задач. Порожденные задачи связаны с объектом nursery (что несколько похоже на Scope в Rust). Время жизни задачи привязано к динамической временной области видимости ее питомника (nursery), и в общем случае — к лексической области видимости блока async with. Это обеспечивает отношение родитель/потомок между задачами и, следовательно, инвариант дерева структурированного параллелизма.

Обработка ошибок использует исключения Python, которые автоматически распространяются на родительские задачи.

Частично структурированный параллелизм

Как и многие методы программирования, полные преимущества структурированного параллелизма проявляются при его исключительном использовании. Если весь параллелизм структурирован, то это значительно облегчает рассуждения о поведении всей программы. Однако это предъявляет требования к языку, которые нелегко удовлетворить; достаточно легко делать неструктурированный параллелизм в Rust, например. Однако даже выборочное применение принципов структурированного параллелизма или мышление в терминах структурированного параллелизма может быть полезным.

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

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

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

Практический структурированный параллелизм с асинхронным Rust

Параллелизм в Rust (будь то async или использование потоков) по своей природе неструктурирован. Задачи могут порождаться произвольно, ошибки и паники в других задачах могут игнорироваться, и отмена обычно мгновенна и не распространяется на другие задачи (см. ниже, почему эти проблемы не могут быть легко решены). Однако есть несколько способов получить некоторые преимущества структурированного параллелизма в ваших программах:

  • Проектируйте свои программы на высоком уровне в соответствии со структурированным параллелизмом.
  • По возможности придерживайтесь идиом структурированного параллелизма (и избегайте неструктурированных идиом).
  • Используйте крейты, чтобы сделать структурированный параллелизм более эргономичным и надежным.

Одной из самых сложных проблем при использовании структурированного параллелизма с Rust является распространение отмены на дочерние фьючерсы/задачи. Если вы используете фьючерсы и компонуете их конкурентно, то это происходит естественным образом, хотя и резко (удаление фьючерса удаляет любые принадлежащие ему фьючерсы, отменяя их). Однако, когда задача удаляется, нет возможности отправить сигнал задачам, которые она породила (по крайней мере, не с Tokio3).

Следствием этого является то, что вы можете предполагать только более слабый инвариант, чем при «настоящем» структурированном параллелизме: вместо того, чтобы предполагать, что родительская задача всегда активна, вы можете предполагать, что родитель всегда активен, если он не был отменен или не запаниковал. Хотя это не оптимально, это все же может упростить программирование, потому что вам никогда не приходится обрабатывать случай отсутствия родителя для обработки какого-либо результата при нормальном выполнении.

TODO

  • владение/время жизни, естественно ведущие к sc
  • рассуждения о ресурсах

Применение структурированного параллелизма к проектированию асинхронных программ

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

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

Если вы пишете библиотеку и хотите использовать структурированный параллелизм (или хотите, чтобы библиотека могла использоваться в программе со структурированным параллелизмом), то важно, чтобы инкапсуляция компонента библиотеки включала временную инкапсуляцию. Т.е., она не должна запускать задачи, которые продолжают работать после возврата из API-функций.

Поскольку Rust не может обеспечить соблюдение правил структурированного параллелизма, важно осознавать и документировать, каким образом программа (или компонент) структурирована и где она нарушает дисциплину структурированного параллелизма.

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

TODO почему это полезно?

TODO было бы здорово иметь здесь case study.

Структурированные и неструктурированные идиомы

Этот подраздел охватывает набор идиом, которые хорошо работают со структурированным подходом к параллелизму, и несколько тех, которые затрудняют структурирование параллелизма.

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

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

Для обработки завершения работы программы (или компонента) используйте явный метод завершения работы вместо удаления компонента, чтобы функция завершения работы могла дождаться завершения дочерних задач или отменить их (поскольку drop не может быть async).

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

  • Порождение задач без ожидания их завершения через дескриптор соединения или удаление этих дескрипторов.
  • Макросы/функции select или race. Они не являются inherently структурированными, но поскольку они резко отменяют фьючерсы, это common источник неструктурированной отмены.
  • Рабочие задачи или пулы. Для асинхронных задач накладные расходы на запуск/завершение задач настолько низки, что использование пула задач, вероятно, будет иметь очень мало преимуществ по сравнению с пулом «данных», например, пулом соединений.
  • Данные без четкой структуры владения — это не обязательно противоречит структурированному параллелизму, но часто приводит к проблемам проектирования.

Крейты для структурированного параллелизма

TODO

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

Области видимости для потоков (Scoped threads)

Структурированный параллелизм с потоками Rust работает довольно хорошо. Хотя вы не можете предотвратить порождение потоков с неограниченным временем жизни, этого легко избежать. Вместо этого ограничьтесь использованием потоков с областью видимости, см. документацию по функции scope. Использование потоков с областью видимости ограничивает время жизни дочерних потоков и автоматически распространяет паники обратно на родительский поток. Родительский поток должен проверять результаты дочерних потоков для обработки ошибок. Вы даже можете передавать объект Scope как питомник (nursery) в Trio. Отмена обычно не является проблемой для потоков Rust, но если вы используете отмену потоков, вам придется интегрировать это с потоками с областью видимости вручную.

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

Асинхронный Drop и задачи с областью видимости

В Rust деструкторы (drop) используются для обеспечения очистки ресурсов, когда время жизни объекта заканчивается. Поскольку фьючерсы — это просто объекты, их деструктор был бы очевидным местом для обеспечения отмены дочерних фьючерсов. Однако в асинхронной программе очень часто желательно, чтобы действия по очистке были асинхронными (если этого не делать, это может блокировать другие задачи). К сожалению, Rust в настоящее время не поддерживает асинхронные деструкторы (async drop). Ведутся работы по их поддержке, но это сложно по ряду причин, включая то, что объект с асинхронным деструктором может быть удален из неасинхронного контекста, и поскольку вызов drop является неявным, нет места, где можно было бы написать явный await.

Учитывая, насколько полезны потоки с областью видимости (как в общем, так и для структурированного параллелизма), возникает другой хороший вопрос: почему нет аналогичной конструкции для асинхронного программирования («задачи с областью видимости»)? TODO ответить на это

Ссылки

Если вам интересно, вот несколько хороших постов в блогах для дальнейшего чтения:

  1. Использование дескрипторов соединения (join handles) несколько смягчает эти недостатки, но это ad hoc механизм без надежных гарантий. Чтобы получить полные преимущества структурированного параллелизма, вы должны быть дотошны в их постоянном использовании, а также в правильной обработке отмены и ошибок. Это сложно без поддержки языка или библиотеки; мы обсудим это немного подробнее ниже. ↩

  2. На самом деле это не является жестким требованием для структурированного параллелизма. Если временная область видимости задачи может быть представлена в программе и передаваться между задачами, то дочерняя задача может быть запущена одной задачей, но иметь другую в качестве родителя. ↩

  3. Семантика JoinHandle в Tokio такова, что если дескриптор удален, то базовая задача «освобождается» (ср., удаляется), т.е. результат дочерней задачи не обрабатывается никакой другой задачей. ↩