Очередь и хвост: почему рост нагрузки на 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, о котором шла речь выше: как только у времени обслуживания появился тяжёлый хвост, хвост задержки стал расти быстрее середины. Обратите внимание на формулировку: не «хвост растёт быстрее среднего, потому что очередь», а «хвост растёт быстрее среднего, когда меняется разброс; одной загрузки для этого мало».

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

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

Механизм 4: ускорение узкого места при том же потоке запросов

Из первой таблицы легко сделать неверный вывод. При загрузке 0,95 запрос проводит в системе в среднем 212,9 мс, из них обслуживание — 10 мс, около пяти процентов; значит, ускорять обслуживание бессмысленно? Нет: в этом рассуждении ожидание принято постоянным, а оно само зависит от скорости обслуживания. Если поток запросов прежний, более быстрый обработчик реже занят — загрузка падает вместе с временем обслуживания, и очередь сжимается.

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

SAME ARRIVALS, MORE CAPACITY: 95 REQUESTS PER SECOND IN EVERY ROW
-----------------------------------------------------------------
  arrivals: 95 requests per second in every row, seed 20260905

                                       util     mean      p50      p99   theory
           baseline: 1 server, 10 ms  0.950    212.9    152.9    932.5    200.0
        service -20%: 1 server, 8 ms  0.760     34.1     23.8    153.1     33.3
    capacity x1.2: 1 server, 8.33 ms  0.792     41.0     28.6    181.6     40.0
            second server: 2 x 10 ms  0.475     13.0      9.5     55.4     12.9
      one server twice as fast: 5 ms  0.475      9.6      6.7     44.7      9.5

  baseline row equals block 1 at load 0.95   True

                against the baseline  mean falls  p99 falls
        service -20%: 1 server, 8 ms       6.24x      6.09x
    capacity x1.2: 1 server, 8.33 ms       5.19x      5.13x
            second server: 2 x 10 ms      16.34x     16.83x
      one server twice as fast: 5 ms      22.08x     20.85x

Обслуживание на 20 % короче (10 → 8 мс) снижает загрузку с 0,95 до 0,76, и среднее падает с 212,9 до 34,1 мс — в 6,2 раза, p99 — в 6,1. Если «на 20 % быстрее» понимать как производительность ×1,2 (8,33 мс), выигрыш — в 5,2 раза. Формула M/M/1 для среднего, E[T] = 1/(μ − λ), даёт то же направление и тот же порядок: 200 → 33,3 мс; у самого предела конечная симуляция отходит от формулы на несколько процентов.

Второй обработчик — тоже прибавка производительности, только вдвое, и выигрыш у него соответственно больше: в 16 раз по среднему. Сравнивать его с ускорением на 20 % — значит сравнивать разные прибавки. При равной прибавке один вдвое более быстрый обработчик здесь даёт среднее даже ниже, 9,6 мс против 13,0: у двух обработчиков каждый запрос по-прежнему обслуживается 10 мс. И второй обработчик помогает, только если работа действительно делится: общая блокировка или общая база оставят узкое место там, где оно было.

Обратная крайность — «ускорение кода выгоднее всего» — тоже неверна. Выигрыш от одного и того же ускорения зависит от того, насколько близко узкое место к насыщению:

THE SAME 20% SHORTER SERVICE AT DIFFERENT ARRIVAL RATES
-------------------------------------------------------
  1 server; service 10 ms -> 8 ms; arrivals fixed within each row

  arrivals/s         util  mean, 10 ms  mean, 8 ms    falls
          50   0.50->0.40         20.3        13.4    1.51x
          80   0.80->0.64         51.3        22.7    2.26x
          95   0.95->0.76        212.9        34.1    6.24x

Вдали от предела (50 запросов в секунду) те же 20 % дают полтора раза, у предела — шесть. И ускорять имеет смысл именно узкое место: ускорение шага, у которого очереди нет, не снижает загрузку того ресурса, где очередь стоит.

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

Модель этого урока — 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 втрое, а медиану — вдвое с небольшим. Третья — вы делаете из этого практический вывод при фиксированном потоке запросов: если хвост оторвался от середины, ищут медленный класс запросов; если растёт всё распределение, нужна производительность узкого места — и у предела даже её прибавка на 20 % сокращает время в разы (в модели при 95 запросах в секунду — с 212,9 до 34,1 мс), а вдали от предела — заметно меньше.

И две вещи, в которых легко перегнуть палку. Первая: «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

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