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

Мотивация

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

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

Что, если бы один кассир по-прежнему обслуживал клиентов одного за другим, а теперь у нас было пять кассиров? Конечно, время обслуживания тоже увеличилось бы. В этом случае мы говорим, что наши кассиры работают параллельно. Можно также сказать, что с точки зрения клиентов кассиры работают одновременно: одновременно обслуживается более одного клиента.

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

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

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

Это работает ™.

Но со временем мы начали замечать проблемы с производительностью. У нас была одна служба, которая занимала всю оперативную память своего хоста, потому что в приложении Java было запущено в общей сложности 10 тысяч потоков. С размером стека потоков JVM по умолчанию для 64-битных виртуальных машин, который составлял 1024 байта, это означало, что мы выделили около 10 ГБ памяти только для стека потоков, даже когда большая часть ее, возможно, не использовалась. Загрузка ЦП также была значительно высокой из-за всех переключений контекста.

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

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

Теперь поговорим о расписании.

Совместное и упреждающее планирование

Планирование - это механизм назначения задач работникам. Того, кто назначает задачи, часто называют планировщиком. В операционной системе (ОС) обычно задачи переводятся в потоки, а worker переводятся в ядра ЦП.

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

Существует два стиля планирования: совместный и упреждающий.

1. Кооператив

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

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

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

Раньше Windows 3.1x и MacOS 9 использовали кооперативный планировщик для параллелизма. Допустим, разработчик плохо пишет программу и забыл передать управление, вся ОС может перестать работать.

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

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

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

2. Превентивный

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

Задача удаляется из воркера, когда она завершается (т.е. выполняется или блокируется для ввода-вывода) или когда она израсходовала свой временной интервал.

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

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

Большинство современных многоцелевых операционных систем прямо сейчас имеют планировщик с вытеснением для планирования программных потоков.

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

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

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

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

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

Далее мы поговорим о потоковых моделях.

Модель потоков (на уровне ядра и на уровне пользователя)

С точки зрения ОС существует два типа потоков.

Потоки уровня ядра - это потоки, которыми управляет сама ОС. ОС выполняет создание, планирование и учет потоков.

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

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

1. Распределение потоков на уровне ядра (модель 1: 1)

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

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

2. Распределение потоков на уровне пользователя (модель N: 1)

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

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

3. Гибридная резьба (модель M: N)

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

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

Перед этим мне нужно заняться еще одним важным аспектом параллелизма: моделью памяти.

Модель памяти

Беззастенчивое копирование из Википедии:

модель памяти описывает взаимодействие потоков через память и их совместное использование данных.

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

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

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

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

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

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

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

Параллельный подход на практике

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

1. Программы с потоковой моделью на уровне ядра, с вытесняющим планировщиком

Пример: Java (JVM), C, Rust

Это семейство программ напрямую использует возможность многопоточности ОС (1: 1). Таким образом, планировщик, используемый для этих программ, является вытесняющим; вот почему это нормально (в смысле планирования) для вас писать или использовать код блокировки, потому что планировщик гарантирует, что он не будет загружать процессор.

Java (благодаря возможности потоковой передачи JVM) и C (с pthreads) имеют примитивы синхронизации для обеспечения согласованной модели памяти.

Rust - интересный игрок в этой области: благодаря своей концепции владения ценностями, которая гарантирует безопасность памяти без сборки мусора, им не приходится сталкиваться со многими типичными проблемами, связанными с неограниченным одновременным доступом к памяти. Любая потенциальная проблема параллелизма может быть обнаружена во время компиляции. Они назвали эту функцию Бесстрашным параллелизмом (что, на мой взгляд, довольно круто!).

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

2. Программы с потоковой моделью на уровне ядра, но с GIL

Пример: Python, Ruby, OCaml

Эти программы могут использовать потоки на уровне ядра в течение своего жизненного цикла. Однако эти потоки ограничены GIL. GIL означает глобальная блокировка интерпретатора. В GIL в процессе может одновременно выполняться только один поток. Это происходит с такими языками, как Python, Ruby и OCaml.

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

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

С помощью таких программ мы обычно можем добиться параллелизма за счет запуска нескольких процессов. Однако процессы тяжелые, а обмен данными между процессами (IPC) дороже, чем потоки, разделяющие память, поэтому люди обычно полагаются на библиотеки пользовательского уровня для улучшения параллелизма (о чем мы расскажем в следующем разделе).

Примечание: Ruby имеет неясные планы по удалению GIL, Python фактически решил проблему GIL, если вы использовали Jython вместо CPython (а у PyPy есть планы на это), в то время как OCaml продолжает многоядерный проект стремительно прогрессирует. Интересно, какими будут эти языки в будущем.

3. Программы с потоковой моделью на уровне пользователя, совместное планирование.

Пример: Node.js, Twisted, EventMachine, Lwt

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

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

Node.js - один из крупнейших игроков в этой области. Остальные три, которые я упомянул в приведенном выше примере, на самом деле являются библиотеками пользовательского уровня для языков на базе GIL, например Twisted для Python, EventMachine для Ruby и Lwt для OCaml.

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

Поскольку создавать потоки дешево, в приложении нередко находятся сотни тысяч потоков. Если вы попытаетесь использовать сотни тысяч потоков уровня ядра, вам понадобятся «хорошие» характеристики для вашей машины (и это будет стоить ОЧЕНЬ ДЕНЕГ).

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

4. Лучшее из обоих миров: гибридная потоковая модель, упреждающее + совместное планирование.

Пример: RxJava, корутины Kotlin, Akka, uThreads, Go (горутины)

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

Часто использование потоков уровня ядра невидимо для пользователя, поскольку среда выполнения на уровне пользователя, которая управляет легковесными потоками, также управляет назначением их потокам ОС под капотом.

RxJava, Kotlin coroutines и Akka - это библиотеки пользовательского уровня поверх JVM, поэтому они могут назначать эти потоки потокам JVM. Библиотека uThreads является одним из примеров реализации кооперативного потока пользовательского уровня для C и C ++.

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

В Go достаточно вызвать любую обычную функцию с ключевым словом go.

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

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

(Существует также текущее проектное предложение по превращению планировщика в вытесняющий, а не кооперативный.)

В общем, этот подход по-прежнему имеет недостатки, связанные с конкуренцией данных и синхронизацией из-за использования потоков ОС. С Kotlin, Akka и Go мы можем избежать этого, используя акторов или каналов для связи между потоками с передачей сообщений вместо совместного использования памяти, однако все же возможно случайно написать небезопасный код.

Блокирующий код также будет блокировать базовый поток ОС, которому был назначен облегченный поток.

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

5. Бонус: гибридная модель потоков, вытесняющая + вытесняющая

Пример: Erlang, Elixir, Haskell

Сначала я подумал, что невозможно (или, по крайней мере, осуществимо) реализовать упреждающий планировщик для потоковой передачи на уровне пользователя, но оказалось, что такая вещь действительно существует!

Из своего исследования я узнал, что Haskell, Erlang и Elixir (которые используют среду выполнения Erlang) используют именно этот подход для параллелизма.

Ранее я сказал, что реализовать упреждающий планировщик сложно, потому что нам нужно учитывать переключение контекста и примитивы синхронизации, так как же Haskell и Erlang могут это сделать?

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

Из документации Haskell (фактически, GHC, его самая популярная реализация компилятора) утверждает, что он использует вытесняющий планировщик. Я бы сказал, что на самом деле это кооперативный планировщик, который срабатывает каждый раз, когда происходит выделение памяти. Цитата из документов:

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

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

Erlang / Elixir
подход Erlang, с другой стороны, возможно, более превосходен. Потоки Erlang называются процессами, поскольку они имитируют процесс ОС, в котором несколько процессов не совместно используют память. Как и Akka (на самом деле, Erlang является источником вдохновения для Akka), процессы Erlang обмениваются данными, передавая между ними сообщения. Все это встроено в языковую среду выполнения.

Это также верно для Elixir, относительно нового языка, который работает поверх Erlang VM (вспомните Scala или Kotlin на JVM).

Поскольку процессы являются строительными блоками Erlang, у процессов просто нет возможности совместно использовать память, и, следовательно, нет необходимости в сложной модели памяти. Затем Erlang может легко использовать механизм упреждающего планирования для планирования процессов. Запуская один планировщик на каждое ядро ​​ЦП, виртуальная машина Erlang может поддерживать параллелизм.

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

Итак, похоже, что Haskell и Erlang / Elixir являются воплощением лучшего подхода к параллелизму, не так ли? Почему я ставлю это в качестве бонуса?

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

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

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

Так что же дальше?

Какую пользу это исследование принесло моей команде?

Поскольку моя команда активно работает с Java, в настоящее время мы внедряем Kotlin и сопрограммы в наш код. Причина, по которой мы выбрали Kotlin, заключалась в том, что, рассмотрев плюсы и минусы, мы подумали, что сопрограммы Kotlin обеспечат наилучшее соотношение усилий, потому что у них есть гибридный подход с упреждающим и кооперативным параллелизмом при 100% взаимодействии с нашей кодовой базой Java и собственными силами. библиотеки.

Тем не менее, лично я хотел бы попробовать PoC Go, Haskell или Erlang в одном из наших сервисов, чтобы увидеть, как они соотносятся с нашим текущим решением.

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

Если вы дочитали до этого места, поздравляем! У вас есть любопытство и желание учиться чему-то, чего ожидают от инженеров Traveloka.

Все эти знания я приобрел, когда вместе с моей командой решаю реальные инженерные проблемы, работая в Traveloka, одной из крупнейших онлайн-туристических компаний в Юго-Восточной Азии. Если вы инженер-программист, заинтересованный в решении реальных проблем масштабируемости и надежности в больших распределенных системах, которые позволяют пользователям создавать моменты со своими близкими, ознакомьтесь с возможностями на странице карьеры Traveloka!

Мы приветствуем предложения и исправления в этой статье.