К вопросу о принципах работы асинхронных решений
Предлагаем вашему вниманию отличное новогоднее чтение для программистов :) Статью Александра Чистякова (alexclear), которую тот написал, вдохновившись тезисами доклада Mons Anderson (codesign) на HighLoad++ 2017.
Давайте поговорим о принципах работы асинхронных решений и рассмотрим предложенную Mons Anderson классификацию. Возможно, нам удастся предложить нашу собственную классификацию.
Для того, чтобы классифицировать существующие решения, придумаем сначала оси координат. С точки зрения инженера-разработчика »синхронная» и »асинхронная» парадигмы основаны на абстракциях, различающихся как сложностью применения, так и «эффективностью» (что такое «эффективность», нам еще предстоит определить).
Осторожно, под катом жёсткий хардкор!
Что касается сложности применения, считается, что синхронное программирование проще асинхронного. Во-первых, при использовании синхронной парадигмы не нарушается порядок следования инструкций в алгоритме. Во-вторых, проще контролируется область видимости переменных.
Асинхронная парадигма
Для того, чтобы понять, какие задачи решает асинхронная парадигма, рассмотрим работу программы на низком уровне.
Планировщик ОС
С точки зрения операционной системы алгоритм программы утилизирует ресурсы компьютера, основными из которых являются процессор (CPU) и память. Планировщик операционной системы отвечает за назначение процесса на одно из ядер процессора.
При смене процесса на ядре процессора необходимо выполнить переключение контекста, сохранив все текущие регистры процессора в память и восстановив из памяти регистры процессора, соответствующие процессу или потоку, предназначенному к исполнению. Эта операция занимает около 200 процессорных тактов для современных процессоров (что довольно дорого).
Операции ввода/вывода осуществляются с использованием механизма DMA, при этом CPU не участвует в процессе. Несмотря на то, что в Linux процессы, осуществляющие ввод-вывод, формально эккаунтятся как назначенные на CPU, фактически такие процессы не занимают процессор и попадают в состояние uninterruptible sleep (D-state). В момент осуществления ввода-вывода одним процессом планировщик назначает на процессор другой процесс.
С точки зрения планировщика ОС потоки ОС (по крайней мере, в Linux) являются просто процессами — каждый из них имеет собственный независимый контекст, блокирование на операциях ввода/вывода одного из потоков не отражается на работе других потоков.
Таким образом, снятие потока ОС с исполнения на процессоре может происходить в двух случаях:
- закончился квант времени, отведенный на исполнение;
- поток выполнил синхронную операцию ввода-вывода (такую, которая обязана дождаться своего завершения).
Java
Классическая (как в современной Java) модель синхронной параллельной обработки ориентируется на использование потоков операционной системы в качестве потоков рантайма (виртуальной машины) языка. Строго говоря, рантайм и виртуальная машина — разные понятия, но для нас это не важно.
Если наша программа обслуживает клиентские подключения, то каждый клиент потребует отдельный поток операционной системы для поддержания соединения. При этом количество переключений контекста между потоками операционной системы будет пропорционально количеству клиентских соединений (смотрите «эффективность» выше).
Допустим, нам необходимо обслужить 10000 клиентских соединений — нам придется породить 10000 потоков операционной системы, технически это возможно.
Perl
Такая модель многопоточности, как в Java, не работает в большинстве интерпретаторов современных языков (Python, Ruby (потоки в Ruby вообще не являются потоками операционной системы)) из-за GIL. Стандартная многопоточность в Perl реализована по тем же принципам, что и в Java — поток Perl является потоком ОС, но при этом каждый поток исполняется своим собственным интерпретатором (смотрите «эффективность» еще раз — это гораздо менее эффективно, чем потоки в Java).
Допустим, нам надо обслужить те же 10000 соединений — теперь нам придется породить 10000 отдельных копий интерпретатора Perl, что невозможно технически.
N:1
Чтобы оптимизировать переключения контекстов при массовом вводе-выводе для большого числа подключенных клиентов вместо потоков ОС используется эмуляция механизма кооперативной многозадачности прямо на уровне рантайма или интерпретатора языка программирования.
В этом случае «потоки» существуют только внутри процесса интерпретатора и планировщик ОС о них ничего не знает. Поэтому переключение между такими потоками должен делать сам интерпретатор, и делает он это в двух случаях: поток в явном виде выполняет команду yield или аналогичную, передающую управление в другой поток, либо поток выполняет операцию ввода-вывода. Такая модель многопоточности называется «N:1» — нескольким потокам уровня интерпретатора соответствует один поток уровня ядра ОС.
Тем не менее, если операция ввода-вывода синхронна, поток уровня ОС попадет в D-state и будет снят с исполнения на процессоре до момента окончания операции ввода-вывода. Это приведет к тому, что все N потоков, исполняющихся в данном потоке ОС, будут заблокированы до окончания операции ввода-вывода в одном из них (смотрите «эффективность»).
Коллбеки
К счастью, в ядре предусмотрен асинхронный (с некоторыми оговорками) механизм ввода-вывода, при использовании которого вызывающий поток уровня ОС не ожидает конца выполнения операции ввода-вывода, а продолжает исполнение. При этом в момент окончания операции I/O будет вызван зарегистрированный пользователем callback.
Для использования асинхронного ввода-вывода достаточно перевести сокет в асинхронный режим при помощи системного вызова fcntl (2).
Представим, что нам необходимо обслужить 10000 подключений — для этого нужно выполнить команду чтения на 10000 открытых сокетах.
В целях повышения эффективности был придуман механизм, позволяющий объединять открытые файловые дескрипторы в общую структуру данных в ядре и выполнять асинхронные операции ввода-вывода над группой сокетов. Изначально таким механизмом являлся системный вызов select (2). Проблема с вызовом select в том, что при наступлении события необходимо перебрать все зарегистрированные файловые дескрипторы, чтобы определить, а на каком именно из них случилось событие — алгоритмическая сложность такого перебора пропорциональна числу открытых файловых дескрипторов.
Для того, чтобы гарантировать константную алгоритмическую сложность поиска нужных сокетов, были реализованы механизмы kqueue (FreeBSD) и epoll (7) (Linux).
При использовании epoll поток исполнения уровня ОС занят регистрацией/удалением открытых файловых дескрипторов и подготовкой асинхронных вызовов I/O, а также обработкой сработавших коллбэков. Если ваша программа не использует yield, то становится критически важным не допускать CPU-интенсивных вычислений между операциями ввода-вывода, так как это нарушит справедливое распределение ресурса процессора между потоками уровня интерпретатора (или рантайма).
Golang и Node.JS
Мы только что описали механизм работы рантайма языка Golang. Отличие только в том, что механизм многопоточности в Golang не N:1, а N: M, где M — число ядер процессора. Рантайм Golang может автоматически переключать горутины не только в моменты ввода-вывода, но и в моменты вызова других функций (при этом бесконечный цикл утилизирует 100% процессорного времени в соответствующем потоке ОС и никогда не будет прекращен рантаймом).
Интерпретатор Node.JS также построен вокруг epoll (точнее говоря, вокруг кода из nginx), только он использует модель N:1 и далее одного ядра не масштабируется.
В некоторых случаях планировщик, подобный планировщику рантайма Golang имплементирован в виде библиотеки или транспайлера (например, Coro в Perl или async/await в JS при помощи Babel), что позволяет использовать корутины в языках, в которых отсутствует их поддержка на уровне интерпретатора.
Попытка классификации
Исходя из вышеизложенного, я бы предложил следующую классификацию многопоточных схем:
- Классическая имплементация потоков рантайма через потоки ОС;
- Имплементация корутин вида N:1 или N: M;
- Низкоуровневая работа с асинхронным вводом/выводом путем ручной регистрации коллбэков и написания соответствующей лапши (не забудьте завести где-то хэшмэп для контекстов).
Теперь к классификации Монса. Насколько я понимаю, она построена вокруг задачи обработки HTTP-запросов и использует классическую терминологию веб-сервера Apache.
Видимо, single process server — это просто синхронно работающий сервер, который может обрабатывать только один запрос в один момент времени.
Forking server — это сервер, который для каждого обрабатываемого запроса порождает отдельный процесс (смотрите «эффективность», в Linux fork (2) использует механизм CoW, а то было бы еще хуже).
Preforking server — это классика мира Apache, создание рабочих процессов заранее в заданном количестве, обработка все еще синхронна.
Про то, чем коллбэки хуже корутин, мы выше говорили, чтобы прочувствовать разницу на себе, напишите код сначала с коллбэками, а потом с корутинами, либо просто поизучайте исходный код nginx. Зачем люди хотят делать код на коллбэках более одного раза в своей жизни, я не знаю, лучше бы в секцию альпинизма или парашютного спорта записались.
Что такое async prefork — видимо, это имплементация механизма N: M, когда запущено M рабочих процессов.
Что такое async + worker мне неведомо, потому что worker от prefork в мире Apache отличается, насколько я помню, тем, что у worker схемы вместо рабочих процессов порождаются рабочие потоки (с точки зрения ОС никакой разницы нет, есть разница с точки зрения shared state, а mutable shared state — это причина, по которой вас сперва депремируют, а потом и уволят).
Что такое multithreaded async? По моей (она не моя, я сам, ленивый и грешный, ничего не изобретал) классификации это опять N: M, не знаю, зачем три названия для одного и того же.
Мы так и не определили, что такое «эффективность». Не понадобилось.
PS: Кстати, доклад тогда так и не прозвучал (доклад был не готов, хотя мы его очень хотели), но мы надеемся услышать его на HighLoad++ Junior этой весной. Где и продолжим нашу дискуссию :)
