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

В этом посте мы изучим очереди в контексте HTTP-запросов. Начнём мы с простого, и постепенно будем вводить более сложные структуры очередей.

Зачем нужны очереди?

Самый простой случай: один клиент и один сервер.

[Все анимации в оригинале статьи интерактивны.]

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

Отбрасываемые запросы — это проблема. Если это HTTP-запросы, то их потеря приведёт к отображению страницы с ошибкой. Из-за этого пользователь может уйти с вашего сайта, а вы потенциально потеряете новую регистрацию или продажу. Нам следует по возможности избегать потерянных запросов.

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


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

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

FIFO

В предыдущем примере мы использовали очередь под названием «первым пришёл — первым ушёл», или FIFO (first-in first-out). Как понятно из названия, запросы обрабатываются в порядке их добавления.

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

Возможно, вы подумаете: «Почему бы не сделать очередь длиннее? Если очередь длиннее, в ней может храниться больше запросов и снижается риск их потери».

Давайте попробуем! В следующем примере размер очереди был увеличен с 3 до 5. Проблема в том, что если пользователю приходится ждать больше 5 секунд, он откажется от запроса. Это можно показать, сделав запрос полым. Когда такое происходит, мы говорим, что произошёл таймаут запроса.


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

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

«Постойте, а почему нам просто не отбрасывать запросы, у которых произошёл таймаут? Зачем вообще их обрабатывать?»

Отличный вопрос! Ничто не мешает нам придумать систему, проверяющую валидность запросов перед их обработкой, но по умолчанию HTTP-серверы редко так делают.

LIFO

Для предотвращения ситуаций, когда обрабатываются только запросы с таймаутом, можно применять очередь «последним пришёл — первым ушёл», или LIFO (last-in first-out). Иногда она называется «стеком». В очереди LIFO первым обрабатывается самый последний добавленный запрос. Это противоположно FIFO, где первым обрабатывается самый старый запрос.


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

Для веб-запросов такой режим отказа часто предпочтителен. Неважно, застрял ли запрос на 20 секунд или на 20 минут — пользователь уже ушёл. Можно продолжить обрабатывать новые запросы в приоритетном порядке, а от старых избавляться, когда нагрузка упадёт.

Очередь с приоритетами

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

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

В примере ниже мы добавили концепцию запросов с приоритетами. Они визуально отличаются от запросов по цвету и штриховке. Запросы с приоритетами проскакивают очередь и размещаются в её начало.


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

Активное управление очередью

Нам бы хотелось иметь возможность выталкивать из очереди запросы с низким приоритетом, чтобы освобождать место, когда придёт запрос с приоритетом. Здесь нам на помощь приходит активное управление очередью (active queue management, AQM).

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

Чтобы снизить вероятность этого, мы будем отбрасывать запросы с низким приоритетом до заполнения очереди. Это будет происходить пропорционально заполненности очереди. Если очередь пуста, мы никогда не отбрасываем запросы. Если очередь заполнена на 50%, есть вероятность 50% отбрасывания запроса. Если очередь заполнена на 90%, то вероятность отбрасывания равна 90%.

Стоит помнить, что это правило применимо только к запросам с низким приоритетом. Запросы с приоритетом никогда не отбрасываются, если очередь не заполнена.


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

Это называется «случайным ранним распознаванием» (random early detection, RED): мы обмениваем отбрасывание большего количества низкоприоритетных запросов на отбрасывание меньшего количества высокоприоритетных. Самое лучшее заключается в том, что такая система дешева и проста в реализации. Из-за этого RED — это самый часто используемый алгоритм AQM в реальной жизни. Строго говоря, поскольку мы используем для низкого и высокого приоритетов разные вероятности, то применяемый здесь принцип называется взвешенным случайным ранним распознаванием (weighted random early detection, WRED).

Сравнение очередей

Мы рассмотрели различные типы очередей, теперь давайте сравним их друг с другом.

Сравнивать мы будем четыре изученные нами в этом посте очереди: FIFO, LIFO, с приоритетами (PQ) и с приоритетами+RED.

▍ Время ожидания

Начнём с, вероятно, самой важной метрики: времени нахождения запросов внутри каждой очереди. Ниже показаны графики перцентилей задержек для каждой очереди, разделённые на запросы и запросы с приоритетом. Замечаете что-то необычное с увеличением перцентилей?

Напомню, что 50-й перцентиль — это время, соответствующее или превышающее время для 50% запросов. То есть если 50-й перцентиль равен 1 с, то 50% запросов обрабатываются за 1 с или меньше.






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

▍ Отбрасываемые запросы

Ниже показаны графики количества отбрасываемых запросов в каждой очереди, разделённые на запросы с приоритетом и запросы.


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

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

▍ Обработанные таймауты

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


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

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

Заключение

Давайте вкратце повторим, что мы знали:

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

Для HTTP-запросов на практике часто используют очереди FIFO. Я утверждаю, и данные из этого поста подтверждают это, что для большинства нагрузок более предпочтительным выбором оказывается LIFO. Если вам нужно разбить запросы по приоритетам, то хороший выбор — это очередь с приоритетами и AQM, но на практике её используют нечасто.

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

• Two Weird Things
• Observing and Understanding Accept Queues in Linux
• Things We (Finally) Know About Network Queues
• SYN Packet Handling in the Wild
• TCP global synchronisation

Telegram-канал со скидками, розыгрышами призов и новостями IT ?