Конвейеризация: универсальный способ повышения пропускной способности

Что общего между стиральной машиной, CPU и микросервисами? Все они выигрывают от «конвейеризации» (англ. pipelining).

В этой статье мы соберем информацию из разных сфер, и увидим, насколько универсален принцип конвейеризации. Получим интуитивное понимание терминов «задержка» (англ. latency) и «пропускная способность» (англ. throughput). А также научимся увеличивать пропускную способность в своих бизнес-процессах, компьютерных системах, и просто в повседневной жизни.

В повседневной жизни: стирка

Это львиная доля статьи. Понимание процесса стирки будет ключом к пониманию работы конвейеризации в CPU, микросервисах, менеджменте, оптимизирующих компиляторах; к лучшему пониманию «конкурентной модели» (англ. concurrency model) Golang, и так далее (этот список можно дополнить в комментариях).

Вы когда-нибудь пользовались стиральной машиной? Если да, то вы уже сталкивались с понятиями задержки и пропускной способности. Возможно уже даже использовали принцип конвейеризации.

В разных странах популярны разные стиральные машины, но все их можно разделить на два вида:

• Совмещенные — один барабан, внутри которого происходит как стирка, так и сушка.

• Раздельные — два отдельных барабана для стирки и сушки. 

Какой из видов выбрать?

Пример

Разберем пример. Допустим, процесс стирки занимает 1 час, сушки — еще 1 час. Значит на сушку + стирку одной партии белья уходит 2 часа.

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

Итак, представьте что вам надо постирать одну партию белья.
Последовательность действий в случае совмещенной стиральной машины:

1. Закинуть белье в стиралку.

2. Достать постиранным и сухим через 2 часа.

В случае раздельной стиральной машины:

1. Закинуть белье в стиралку.

2. Достать постиранным через 1 час.

3. Закинуть белье в сушилку.

4. Достать постиранным и сухим еще через 1 час.

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

Задержка — это количество времени, необходимое на выполнение одной операции.

В нашем примере это количество часов, необходимое на стирку и сушку одной партии белья. В случае обоих видов стиральных машин задержка = 2 ч/партия.

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

Проще всего посмотреть на нее графически. Допустим, нам надо постирать 3 партии белья. Начнем с совмещенной стиралки:

Как видно, на обработку трех партий белья в совмещенной стиралке нам потребовалось 6 часов:
1 час — стирается Партия 1.
2 час — сушится Партия 1.
3 час — стирается Партия 2.
4 час — сушится Партия 2.
5 час — стирается Партия 3.
6 час — сушится Партия 3.

А сколько времени понадобится на обработку N партий белья в такой стиралке?

Не сложно вывести формулу: время обработки одной партии (2 часа) умножаем на количество партий белья.

Итак, формула такая: часов, где N — количество партий белья.

Теперь посмотрим как будет выглядеть стирка в раздельной машинке:

Ого! Мы закончили стирку за 4 часа вместо 6. Как так вышло? Давайте разберемся по шагам:
1 час — стирается Партия 1.
2 час — сушится Партия 1, и (внезапно) стирается Партия 2.
3 час — сушится Партия 2, и стирается Партия 3.
4 час — сушится Партия 3.

Сколько времени понадобится на обработку N партий белья в такой стиралке?

Этот вопрос уже не такой очевидный. Но его можно перефразировать: как часто мы можем доставать новую, постиранную и сухую партию белья из этого «конвейера»?
Интуитивно понятно — в конце каждого часа, кроме первого (ведь в первый час ничего еще не сушится).
Каждый час — значит N часов для N партий белья. Кроме первого — значит надо прибавить еще 1 час.

Итак, формула такая: часов, где N — количество партий белья.

Выбираем стиралку

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

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

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

• Совмещенная стиралка: = 0.5 партия/час. 

• Раздельная стиралка: ≈ 1 партия/час (чем больше N, тем ближе к 1).

Откуда взялась эта разница? Раздельная стиралка, в отличие от совмещенной, обрабатывает сразу две партии белья начиная со второго часа работы. Говорят что в таком состоянии система «полностью конвейеризированна» (англ. fully pipelined).

Нам удается держать конвейер заполненным потому, что партии белья не зависят друг от друга. Если бы мы не могли начать обработку второй партии, пока не закончим с первой, то заполнить конвейер бы не получилось. Случилась бы ситуация называемая «остановкой конвейера» (англ. pipeline stalling).

Также заметим, что, если бы мы могли сушить белье до стирки, то могли бы высушить третью партию белья в первый час. Сократив общее время с 4 часов до 3 (в общем случае с N + 1 до N). Но кто в здравом уме будет сушить еще не постиранное белье? Это пример «цепочки зависимости» (англ. dependency chain).

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

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

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

Вниз по абстракциям

Сразу скажу, что мы пропустим вступление на тему «что такое CPU». На Хабре уже есть статьи на эту тему, например эта. Тут мы сфокусируемся на общем понимании, каким образом CPU использует конвейеризацию.

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

Для примера рассмотрим один из самых простых конвейеров, используемый в процессорах с RISC архитектурой. Он имеет 5 стадий:

1. Получение (англ. fetch) инструкции — на этой стадии процессор читает инструкцию из памяти, адрес которой указывается в программном счетчике.

2. Декодирование (англ. decode) инструкции — процессор определяет инструкцию. При необходимости читает регистры (если инструкция предполагала работу с регистрами).

3. Выполнение (англ. execute) инструкции — вычисление с помощью арифметико-логического устройства.

4. Доступ к памяти (англ. memory access) — процессор читает данные из памяти, либо пишет результат в память, указанную в инструкции (если инструкция предполагала работу с памятью).

5. Запись в регистр (англ. register write back) — процессор пишет результат в регистр (если инструкция предполагала работу с регистрами).

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

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

Как видно, в варианте без конвейеризации, за 10 циклов процессор смог выполнить 2 инструкции.

За какое количество циклов будет выполнено N инструкций?

Тут опять не сложно вывести формулу: циклов, где S — количество стадий, а N — количество инструкций.
В данном случае 5 стадий * 2 инструкции = 10 циклов.

Применим конвейеризацию, и посмотрим, сколько инструкций процессор сможет выполнить за те же 10 циклов:

Целых 6 инструкций вместо 2! Разница даже больше, чем в нашем примере со стиральными машинами.

За какое количество циклов будет выполнено N инструкций?

Формула такая: циклов, где S — количество стадий, а N — количество инструкций.
В данном случае 5 стадий + 6 инструкций - 1 цикл = 10 циклов.

Заметим при этом, что задержка никак не поменялась. Одна инструкция как требовала 5 циклов для выполнения, так и требует. Поменялась только пропускная способность.

Но есть проблема — в реальных программах много «ветвления» (англ. branching). Другими словами, много «if»-ов. Эти «if»-ы превращаются в инструкции «условных прыжков» (англ. conditional jump), — команды, приказывающие процессору прыгнуть из одной области памяти с инструкциями в другую по какому-то условию. 
Мы не знаем, прыгать нам или нет, пока мы не вычислим условие. При этом конвейер наполняется инструкциями на каждом цикле. 
Если мы все-таки прыгнем, то все те инструкции, которые мы загрузили в конвейер до прыжка — это мусор, который нельзя выполнять.
Как решить эту проблему? Современные CPU решают ее с помощью «предсказания веток», или «предсказания переходов» (англ. branch prediction). Это выходит за рамки нашей темы, но про это уже есть другая статья.

Итак, время обработки для CPU с пятью стадиями рассчитывается как в случае конвейеризиранного, и в случае неконвейеризиранного CPU.
Рассчитаем пропускную способность:

• CPU без конвейеризации: = 0.2 инструкция/цикл.

• CPU с конвейеризацией: ≈ 1 инструкция/цикл (чем больше N, тем ближе к 1).

В общем все как со стиральными машинами.

Вверх по абстракциям

Теперь поднимемся на самый верхний уровень абстракции. Поговорим про микросервисную архитектуру. И снова тут не будет длинного введения. Для этого уже есть другая статья. 

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

Альтернатива микросервисам — «монолитная» архитектура, то есть единственная программа, решающая все те же задачи, что и куча отдельных микросервисов.

У каждой из этих архитектур есть свои плюсы и минусы. Тут мы не будем сравнивать их все, но сравним пропускную способность.

Допустим, мы делаем интернет магазин. Пользователь добавляет что-то в корзину и нажимает кнопку «быстрая покупка». Наша задача:

1. Рассчитать стоимость заказа.

2. Создать заказ.

3. Рассчитать стоимость доставки.

4. Создать доставку.

Для простоты представим, что каждый шаг занимает 100 миллисекунд.

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

Как это выглядит в монолите:

Как это выглядит в микросервисах:

Задержка примерно одинаковая: 400 мс/заказ = 0.4 сек/заказ.
Почему примерно? Потому, что в реальности есть дополнительные факторы. Такие же, как перекладывание белья из одной машинки в другую в примере со стиркой. Задержка может увеличиться за счет дополнительной коммуникации между микросервисам. А может и уменьшиться, если ваши маленькие микросервисы будут быстрее обрабатывать запрос за счет своего размера.

Пропускная способность:

• Монолит: = 0.25 заказ/100 мс = 2.5 заказ/сек.

• Микросервисы: ≈ 1 заказ/100 мс ≈ 10 заказ/сек (чем больше N, тем ближе к 10).

Как обычно, с применением конвейеризации возникают вопросы, которых раньше не было.
Например, вопрос распределенных транзакций между микросервисами. Что, если заказ был создан успешно, а расчет доставки завершился с ошибкой? Возможно, мы захотим удалить созданный заказ, и попросить пользователя заново нажать на «быструю покупку». Или захотим повторно попробовать создать доставку.
Сделать это в микросервисах становится значительно труднее, чем в монолите. На помощь приходит паттерн Saga, о котором тоже уже есть статья.

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

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

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

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

Если хотите ознакомиться с этим подробнее, Роб Пайк, — один из ключевых дизайнеров языка, давал об этом лекцию. Ее перевод уже есть на Хабре.

Совсем коротко про менеджмент

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

Заключение

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

Пойдем увеличивать пропускную способность!