Проектирование футур для Rust

Перевод | Автор оригинала: Aaron Turon

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

Напомним, цель - надежный и эргономичный асинхронный ввод-вывод без потери производительности:

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

• Эргономичность: библиотека должна делать написание асинхронного кода максимально безболезненным - в идеале, таким же простым, как написание синхронного кода, но с большей выразительностью. В то время как последнее потребует async / await для полного выполнения, библиотека futures предоставляет высокоуровневый способ выражения и комбинирования асинхронных вычислений, аналогичный успешному Rust Iterator API.

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

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

• Используйте особенности и закрытие Rust для эргономики и снижения затрат. Трэйты и замыкания в Rust не требуют выделения памяти в куче или динамической диспетчеризации - факты, которыми мы пользуемся. Мы также используем систему трэйтов, чтобы упаковать Futures API простым и удобным способом.

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

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

Давайте нырнем!

Предыстория: трейты в Rust

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

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

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

trait Hash {
    fn hash(&self) -> u64;
}

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

impl Hash for bool {
    fn hash(&self) -> u64 {
        if *self { 0 } else { 1 }
    }
}

impl Hash for i32 { ... } // etc

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

fn print_hash<T: Hash>(t: &T) {
    println!("The hash is {}", t.hash())
}

Функция print_hash является универсальной для неизвестного типа T, но требует, чтобы T реализовал свойство Hash. Это означает, что мы можем использовать его со значениями bool и i32:

print_hash(&true);   // instantiates T = bool
print_hash(&12);     // instantiates T = i32

Обобщения компилируются, что приводит к статической отправке. То есть, как и в случае с шаблонами C++, компилятор сгенерирует две копии метода print_hash для обработки вышеуказанного кода, по одной для каждого конкретного типа аргумента. Это, в свою очередь, означает, что внутренний вызов t.hash() - точка, где фактически используется абстракция - имеет нулевую стоимость: он будет скомпилирован в прямой статический вызов соответствующей реализации:

// The compiled code:
__print_hash_bool(&true);  // invoke specialized bool version directly
__print_hash_i32(&12);     // invoke specialized i32 version directly

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

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

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

Определение футур

А теперь обратимся к футурам. В более ранней публикации дано неформальное определение будущего:

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

Ясно, что мы хотим, чтобы футуры были своего рода трэйтом, поскольку будет много разных видов «значений, которые еще не готовы» (например, данные в сокете, возвращаемое значение из вызова RPC и т.д.). Но как нам представить «еще не готовую» часть?

Ложный старт: подход обратного вызова (также известный как завершение)

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

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

В терминах Rust модель обратного вызова приводит к следующему трэйту:

trait Future {
    // The type of value produced by the future
    type Item;

    // Tell the future to invoke the given callback on completion
    fn schedule<F>(self, f: F) where F: FnOnce(Self::Item);
}

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

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

Чтобы понять, почему, давайте рассмотрим простой способ объединения двух футур:

fn join<F, G>(f: F, g: G) -> impl Future<Item = (F::Item, G::Item)>
    where F: Future, G: Future

Эта функция принимает два футуры, f и g, и возвращает новое будущее, которое дает пару с результатами обоих. Объединенный футура завершается только тогда, когда оба базовых футуры завершаются, но до этого момента позволяет базовым футурам выполняться одновременно.

Как бы мы реализовали соединение, используя приведенное выше определение Future? Объединенному будущему будет предоставлен единственный обратный вызов both_done, который ожидает пару. Но каждому из базовых футур нужны свои собственные обратные вызовы f_done и g_done, принимающие только свои собственные результаты. Ясно, что здесь нам нужно какое-то совместное использование: нам нужно сконструировать f_done и g_done, чтобы каждый из них мог вызывать both_done, а также не забудьте включить соответствующую синхронизацию. Учитывая задействованные сигнатуры типов, просто невозможно сделать это без выделения (в Rust мы бы использовали здесь Arc).

Подобные проблемы повторялись во многих будущих комбинаторах.

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

TL;DR, мы не смогли сделать «стандартную» абстракцию будущего, обеспечивающую композицию футур с нулевой стоимостью, и мы не знаем ни одной «стандартной» реализации, которая бы это делала.

Что сработало: подход, ориентированный на спрос (также известный как готовность)

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

// A *simplified* version of the trait, without error-handling
trait Future {
    // The type of value produced on success
    type Item;

    // Polls the future, resolving to a value if possible
    fn poll(&mut self) -> Async<Self::Item>;
}

enum Async<T> {
    /// Represents that a value is immediately ready.
    Ready(T),

    /// Represents that a value is not ready yet, but may be so later.
    NotReady,
}

Сдвиг API здесь прост: вместо того, чтобы будущее активно вызывать обратный вызов по завершении, внешняя сторона должна опрашивать будущее, чтобы довести его до завершения. Будущее может сигнализировать о том, что он еще не готов и должен быть опрошен снова в какой-то момент, возвращая Async::NotReady (абстракция EWOULDBLOCK).

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

Устраняя все промежуточные обратные вызовы, мы решили некоторые ключевые проблемы предыдущей версии трейта. Но мы ввели новый: после возврата NotReady кто и когда опрашивает будущее?

Возьмем конкретный пример. Если future пытается прочитать байты из сокета, этот сокет может быть не готов к чтению, и в этом случае future может вернуть NotReady. Каким-то образом мы должны позаботиться о том, чтобы будущее позднее «просыпалось» (путем вызова опроса), как только сокет будет готов. Такого рода пробуждение - задача цикла обработки событий. Но теперь нам нужно каким-то образом связать сигнал в цикле событий с продолжением опроса будущего.

Решение составляет другой главный компонент дизайна: задачи.

Краеугольный камень: задачи

Задача - это будущее, которое выполняется. Это будущее почти всегда состоит из цепочки других футур, как в примере из исходного сообщения:

id_rpc(&my_server).and_then(|id| {
    get_row(id)
}).map(|row| {
    json::encode(row)
}).and_then(|encoded| {
    write_string(my_socket, encoded)
})

Ключевым моментом является то, что существует разница между такими функциями, как and_then, map и join, которые объединяют футуры в более крупные футуры, и функциями, которые выполняют футуры, например:

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

• Метод spawn в пуле потоков, который запускает future как независимую задачу в пуле.

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

Как бы ни начался опрос, если какой-либо из внутренних футур дал результат NotReady, он может привести к остановке всей задачи - задаче может потребоваться дождаться возникновения какого-либо события, прежде чем она сможет продолжить. При синхронном вводе-выводе именно здесь поток блокируется. Задачи представляют собой эквивалент этой модели: задача «блокируется», уступая место своему исполнителю после установки себя в качестве обратного вызова для событий, которых она ожидает.

Возвращаясь к примеру чтения из сокета, по результату NotReady задача может быть добавлена в таблицу диспетчеризации цикла событий, чтобы она была разбужена, когда сокет станет готовым, и в этот момент он повторно опросит свое будущее. Однако важно то, что экземпляр задачи остается фиксированным в течение всего времени существования будущего, которое он выполняет, поэтому для создания или установки этого обратного вызова не требуется выделения.

Завершая аналогию с потоками, задачи предоставляют API парковки / отмены для «блокировки» и пробуждения:

/// Returns a handle to the current task to call unpark at a later date.
fn park() -> Task;

impl Task {
    /// Indicate that the task should attempt to poll its future in a timely fashion.
    fn unpark(&self);
}

Блокировка будущего - это вопрос использования park для обработки его задачи, помещения результирующей задачи в некоторую очередь пробуждения для интересующего события и возврата NotReady. Когда происходит интересующее событие, дескриптор задачи может использоваться для пробуждения задачи, например перепланировав его для выполнения в пуле потоков. Точная механика парковки / снятия с парковки зависит от исполнителя задачи.

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

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

Пример: присоединитесь к модели, основанной на спросе

Чтобы реализовать функцию соединения, мы представим новый конкретный тип, Join, который отслеживает необходимое состояние:

fn join<F: Future, G: Future>(f: F, g: G) -> Join<F, G> {
    Join::BothRunning(f, g)
}

enum Join<F: Future, G: Future> {
    BothRunning(F, G),
    FirstDone(F::Item, G),
    SecondDone(F, G::Item),
    Done,
}

impl<F, G> Future for Join<F, G> where F: Future, G: Future {
    type Item = (F::Item, G::Item);

    fn poll(&mut self) -> Async<Self::Item> {
        // navigate the state machine
    }
}

Первое, на что следует обратить внимание, это то, что Join - это перечисление, варианты которого представляют состояния в «машине состояний соединения»:

• BothRunning: оба базовых футуры все еще исполняются.
• FirstDone: первое будущее принесло значение, но второе все еще выполняется.
• SecondDone: второе будущее принесло значение, но первое все еще выполняется.
• Готово: оба футуры завершены, и их значения возвращены.

Перечисления в Rust представлены без каких-либо указателей или выделения кучи; вместо этого размер перечисления равен размеру наибольшего варианта. Именно этого мы и хотим - этот размер представляет собой «высшую точку» этой маленькой государственной машины.

Метод опроса здесь будет пытаться продвинуться через конечный автомат, при необходимости опрашивая базовые футуры.

Напомним, что цель соединения состоит в том, чтобы позволить двум его футурам работать одновременно, стремясь к финишу. Например, каждый из двух футур может представлять подзадачи, выполняющиеся параллельно в пуле потоков. Когда эти подзадачи все еще выполняются, опрос их будущего вернет NotReady, эффективно «блокируя» будущее присоединения, в то же время сохраняя дескриптор внешней Задачи, чтобы разбудить ее, когда они закончатся. Затем две подзадачи могут соревноваться, чтобы разбудить задачу, но это нормально: метод unpark для пробуждения задачи является потокобезопасным и гарантирует, что задача будет опрашивать свое будущее хотя бы один раз после любого вызова unpark. Таким образом, синхронизация обрабатывается раз и навсегда на уровне задачи, не требуя комбинаторов, таких как соединение, для выделения или обработки самой синхронизации.

• Возможно, вы заметили, что опрос принимает &mut self, что означает, что данное будущее нельзя опрашивать одновременно - будущее имеет уникальный доступ к своему содержимому во время опроса. Это гарантирует автоматическая синхронизация.

И последнее. Комбинаторы, такие как join, воплощают в себе «маленькие» конечные автоматы, но поскольку некоторые из этих состояний включают дополнительные футуры, они позволяют вкладывать дополнительные конечные автоматы. Другими словами, опрос одного из базовых футур для соединения может включать в себя пошаговое выполнение его конечного автомата перед выполнением шагов в конечном конечном автомате соединения. Тот факт, что использование трейта Future не влечет за собой выделения кучи или динамической отправки, является ключом к тому, чтобы эта работа была эффективной.

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

Футуры в масштабе

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

Отмена

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

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

В модели, основанной на спросе, аннулирование в основном «выпадает». Все, что вам нужно сделать, это перестать опрашивать будущее, вместо этого «отбросить» его (термин Rust для уничтожения данных). И это обычно является естественным следствием вложенных конечных автоматов, таких как Join. Футуры, вычисление которых требует некоторых особых усилий для отмены (например, отмена вызова RPC), могут предоставлять эту логику как часть своей реализации Drop.

Обратное давление

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

Как и отмена, противодавление в значительной степени выпадает из нашей модели для футур и потоков. Это связано с тем, что задачи могут быть «заблокированы» на неопределенный срок будущим / потоком, возвращающим NotReady, и уведомлены о продолжении опроса в более позднее время. В примере с транзакциями базы данных, если постановка транзакции в очередь сама представлена как будущее, служба базы данных может вернуть NotReady для замедления запросов. Часто такие результаты NotReady передаются в обратном направлении по системе, например разрешая обратное давление течь от службы базы данных обратно к определенному клиентскому соединению, а затем обратно к общему диспетчеру соединений. Такие каскады - естественное следствие модели, ориентированной на спрос.

Сообщение о причине пробуждения

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

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

Чтобы справиться с этой проблемой, библиотека предлагает своего рода «epoll для всех»: возможность связывать «события отмены парковки» с заданным дескриптором Задачи. То есть могут быть разные дескрипторы одной и той же задачи, плавающие вокруг, все из которых могут использоваться для пробуждения задачи, но каждый из которых несет разные события отмены парковки. Проснувшись, будущее в задаче может изучить эти незапаркованные события, чтобы определить, что произошло. Подробнее см. В документации. Подведение итогов

Мы ознакомились с основными принципами проектирования, лежащими в основе библиотеки футур и потоков Rust. Подводя итог, можно сказать, что все сводится к нескольким ключевым идеям:

• Инкапсулируйте текущие футуры в задачи, которые служат единым постоянным «обратным вызовом» на будущее.

• Реализуйте футуры в стиле, ориентированном на спрос, а не на обратный вызов.

• Используйте систему трейтов Rust, чтобы позволить скомпонованным футурам превратиться в большие конечные машины.

Вместе эти идеи дают надежную, эргономичную библиотеку футур с нулевой стоимостью.

Как я упоминал в начале поста, мы очень активно работаем над уровнями над базовой библиотекой футур - слоями, которые включают определенные модели ввода-вывода (например, mio), а также предоставляют инструменты еще более высокого уровня для создания серверов. Эти слои являются частью проекта Tokio, и вы можете прочитать больше об общем видении в моей предыдущей публикации. По мере того, как эти API стабилизируются, ожидайте увидеть больше сообщений с их описанием!