Очередь и хвост: почему рост нагрузки на 19 % даёт рост задержки вчетверо

Что здесь на самом деле спрашивают

Лестница обычно такая:

1. «Что такое p99?» — разминка.
2. «Почему нельзя смотреть на среднее?» — здесь начинается содержание.
3. «Нагрузка выросла на пятую часть, а задержка вчетверо. Почему?» — главный вопрос темы.
4. «До какой загрузки можно нагружать сервис?» — вопрос про запас.
5. «Почему хвост длиннее середины?» — вопрос, на который обычно отвечают «потому что нагрузка», и это неверный ответ.
6. «Что делать с хвостом?» — вопрос про то, на что реально можно влиять.

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

База: очередь появляется тогда, когда приходят чаще, чем успевают

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

Пусть сервер успевает обрабатывать десять запросов в секунду. Больше он не может — это его предел.

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

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

Вторая вещь, которую надо назвать до всего остального, — из чего складывается задержка, которую видит пользователь:

время обслуживания + время ожидания = задержка

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

И вот главный вопрос: какое из двух слагаемых растёт, когда «стало медленнее»? Работа ведь не изменилась: тот же код, то же железо, тот же запрос.

Ответ: растёт ожидание. Обслуживание остаётся тем же самым, а времени в очереди становится всё больше — потому что пауз, в которые она рассасывается, всё меньше.

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

Механизм 1: очередь дорожает быстрее, чем растёт нагрузка

TIME IN THE SYSTEM AGAINST UTILISATION
--------------------------------------
    load       mean        p50        p95        p99
    0.50      20.3       14.0       61.2       94.0 
    0.70      34.1       23.6      103.2      158.1 
    0.80      51.3       35.8      155.7      227.2 
    0.90     109.2       74.1      331.9      503.2 
    0.95     212.9      152.9      634.0      932.5 

Столбец «load» — это та самая доля из «Базы»: восемь запросов на десять посильных — загрузка 0,8, девять с половиной — 0,95. Формально загрузка ρ в модели есть доля времени, в течение которой единственный обработчик занят.

И сразу граница, без которой это число уводит в сторону: ρ в модели — это не загрузка процессора на дашборде. Процессор показывает, сколько работает железо; ρ говорит, насколько плотно занято то место, где стоит очередь. Совпадать они не обязаны: узким местом может быть диск, соединение с базой, пул обработчиков или блокировка, и тогда очередь растёт по всем законам этой таблицы при спокойных процентах на графике процессора. Читая таблицу, держите в голове ρ того ресурса, который на самом деле ограничивает, а не самого заметного.

Прочитайте таблицу по столбцу «mean»: 20 → 34 → 51 → 109 → 213. Нагрузка растёт равными шагами, время — ускоряясь.

Причина не в том, что сервис устал. Обслуживание всё это время занимает те же 10 мс; растёт только ожидание. Механизм такой: пока обработчик занят, новые запросы копятся; чем выше загрузка, тем реже случаются паузы, в которые очередь успевает рассосаться. У загрузки 0,5 пауз много, у 0,95 — почти нет, и каждая случайная порция запросов рассасывается всё дольше.

Отсюда правило, которым стоит отвечать: последние проценты загрузки самые дорогие. В столбце «mean» шаг с 0,5 на 0,8 — это 20,3 → 51,3, а следующий шаг, с 0,8 на 0,95, — 51,3 → 212,9, вчетверо.

Механизм 2: считаем непропорциональность

WHAT GROWS FASTER THAN WHAT
---------------------------
  load 0.80 -> 0.95 is a rise of              1.19x
  mean time rises by                          4.15x
  p99 rises by                                4.10x
  p99 over mean at load 0.80                  4.43x
  p99 over mean at load 0.95                  4.38x

Первые две строки — ответ на главный вопрос темы: нагрузка выросла на 19 %, задержка — вчетверо. Это и есть непропорциональность, из-за которой планы вида «у нас есть ещё пятнадцать процентов запаса» оказываются неверными: пятнадцать процентов загрузки — это не пятнадцать процентов задержки.

А вот третья и четвёртая строки — то, ради чего стоит читать модель внимательно. Отношение p99 к среднему не изменилось: 4,43 против 4,38. То есть в M/M/1 — той модели, из которой взята вся эта таблица, — p99 и среднее масштабируются одинаково: хвост растёт ровно с той же скоростью, что и середина, а не быстрее.

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

Теперь аккуратно про то, что отсюда следует. Из этого результата не следует, что хвост никогда не растёт быстрее среднего. Из него следует ровно одно: тезис «хвост всегда растёт быстрее среднего просто из-за очереди» не является общим законом — есть очередь, в которой это не так, и это самая разобранная очередь на свете. Формулировать надо от границы: в M/M/1 хвост и среднее масштабируются одинаково; за её пределами — как получится.

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

Механизм 3: хвост делает разброс, а не загрузка

Гипотеза: хвост отрывается от середины не от загрузки, а от разброса времени обслуживания. Проверяем так — загрузка та же, среднее то же, меняется только разброс: вместо «в среднем 10 мс» — «95 % запросов по 5 мс и 5 % по 105 мс». Среднее у такого обслуживания ровно то же самое: 0,95 × 5 + 0,05 × 105 = 10.

SAME MEAN SERVICE TIME, DIFFERENT SPREAD
----------------------------------------
  both runs: load 0.80, average service time 10 ms
  A: service time exponential, average 10 ms
  B: service time is 5 ms in 95% of cases and 105 ms in 5%

                           mean        p50        p99
      A, exponential      51.3       35.8      227.2
            B, mixed     139.1       92.2      713.8
  p99 of B over p99 of A                      3.14x
  p50 of B over p50 of A                      2.58x

Всё выросло — и медиана, и хвост, — но хвост дальше: 3,1 против 2,6. Причём загрузка не менялась ни на процент, и средняя работа на запрос осталась прежней.

Это и есть тот выход за границу M/M/1, о котором шла речь выше: как только у времени обслуживания появился тяжёлый хвост, хвост задержки поехал быстрее середины. Заметьте порядок утверждений — не «хвост растёт быстрее среднего, потому что очередь», а «хвост растёт быстрее среднего, когда меняется разброс; одной загрузки для этого мало».

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

И практический вывод: чтобы улучшить p99, надо искать медленный класс запросов, а не увеличивать мощность вообще. Увеличение мощности снижает загрузку и двигает всё распределение целиком; сокращение разброса двигает именно хвост.

Глубже: чего в модели нет

Модель этого урока — M/M/1, и её имя стоит держать при себе вместе с числами: почти все выводы верны в её границах, а не вообще. Четыре вещи, о которых стоит сказать самому.

Обработчик один. Настоящий сервис обслуживает несколько запросов параллельно, и это меняет числа сильно: очередь у нескольких обработчиков рассасывается быстрее, и та же загрузка стоит дешевле. Направление зависимости при этом сохраняется, а вот конкретные кратности — нет. Здесь же ломается и равенство «p99 и среднее растут одинаково»: оно доказано только для M/M/1.

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

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

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

Как отвечать на собеседовании

Короткий ответ: время в системе — это обслуживание плюс ожидание, и с ростом загрузки растёт ожидание, а не обслуживание. Поэтому зависимость непропорциональна: в модели рост загрузки с 0,80 до 0,95 — это плюс 19 %, а время выросло в 4,1 раза при неизменных 10 мс работы на запрос.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

Хороший ответ отличают три вещи. Первая — вы не выдаёте «хвост растёт быстрее среднего» за общий закон очередей: в модели M/M/1 отношение p99 к среднему постоянно (4,43 против 4,38), то есть от одной только загрузки растягивается всё распределение целиком. Вторая — вы называете настоящую причину длинного хвоста: разброс времени обслуживания; в той же модели при той же загрузке и том же среднем смена ровного обслуживания на «95 % по 5 мс и 5 % по 105 мс» подняла p99 втрое, а медиану — вдвое с небольшим. Третья — вы делаете из этого практический вывод: p99 чинят поиском медленного класса запросов, а не добавлением мощности вообще.

И две вещи, на которых легко переусердствовать. Первая: «p99 и среднее растут одинаково» — свойство M/M/1, а не закон очередей. При тяжёлом хвосте времени обслуживания, нескольких обслуживающих устройствах, пакетировании и приоритетах хвост вполне отрывается от середины — измеренный в уроке разброс как раз такой случай. Вторая: загрузка ρ в модели — не загрузка процессора на дашборде; прежде чем прикладывать таблицу к своей системе, надо понять, у какого ресурса стоит очередь.

Дальше спросят

Частые заблуждения

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ взят из прогона модели, а не назначен.

low = simulate(0.80)
high = simulate(0.95)
mixed = simulate(0.80, service_mixed)
print(f"{high['mean'] / low['mean']:.1f}")
print(f"{high['p99'] / low['p99']:.1f}")
print(f"{mixed['p99'] / low['p99']:.1f}")

4.1
4.1
3.1

1.2
4.1
3.1

4.1
8.5
1.0

1.2
1.2
3.1

Проверка знаний