9 августа 2020 г.

Queueing theory for fun and practice #3: системы с потерями

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

Какова должна быть посадочная вместимость приемной, чтобы не более 1 просителя в день ушло не солоно хлебавши, если пропускная способность Апполинария Матвеевича не более дюжины челобитных в день, а входящий поток около 10 челобитных в день?

TL;DR: реальные системы обрабатывают не все задачи – часть задач теряется или отбрасывается за счет ограниченности буферов и/или таймаутов. Потери делают систему устойчивой к перегрузке, и улучшают качество обслуживания тех задач, что дожидаются обработки – теряются более вероятно именно те задачи, которым пришлось бы ждать дольше всех. Системы с потерями – добро, делайте его больше.

(часть 3, предыдущая часть: нагрузка и время отклика)

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

Почему? Конечно, может быть в оценку трафика затесалась ошибка, и система на самом деле имеет запас емкости. Другое возможное объяснение: в системе есть потери – она обрабатывает не всех клиентов. Часть клиентов не добирается до кассира, часть задач не добирается до сервера.

Два самых очевидных механизма потерь: либо очередь ограничена, и задачи теряются, когда она переполнена, либо задачи сами имеют какой-то внутренний TTL, и "уходят" из очереди, когда он превышен.

Если очередь состоит из людей, то обычно имеет место комбинация этих механизмов:

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

В теории массового обслуживания есть 2 классические модели, описывающие системы с потерями: сценарий с ограниченной очередью моделируется системой Эрланг-C1, а сценарий с нетерпеливыми клиентами моделируется системой Эрланг-А2

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

Однако у этих решений есть простые и понятные качественные свойства:

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

Конечно, очевидно, что размер очереди и время ожидания станут меньше, если часть задач не делать :) Не очевидно то, что значительное преимущество (в разы) остается даже если сделать поправку на потерянные задачи3 – если мы будем сравнивать системы при одинаковом количестве обрабатываемых задач, то система без потерь все равно значительно проигрывает системе с потерями, которая обрабатывает то же количество задач4.

На графике поведение систем M/M/1/10 и M/M/1/20 напротив M/M/1/Inf при одинаковой утилизации5: видно, что системы с ограниченной очередью остаются устойчивыми даже при загрузке приближающейся к 100%.

И средний размер очереди в них заметно ниже, даже при небольших потерях: при загрузке в 80% в системе M/M/1/10 только 2.8% входящих задач теряются6, но средняя длина очереди 2.4 против 3.2 в системе M/M/1/Inf, где не теряется ничего – т.е. на 25% меньше очередь при 2.8% потерь.

При загрузке 90% в M/M/1/10 теряются уже 8% задач – но средняя длина очереди 4 против 8 для M/M/1/Inf – очередь короче вдвое, ценой потери всего 8% задач.

Разница такая заметная потому, что задачи, потерянные из-за переполнения очереди исчерпания таймаута, это не случайные задачи, это самые "неудобные" задачи – те, которые пришли в моменты высокой занятости, и потому сами долго ждали бы обслуживания, да еще задерживали выполнение задач, пришедших после. Вероятность потери задачи оказывается скоррелирована с размером очереди – задачи чаще теряются тогда, когда очередь начинает расти 7.

Ограничивать буфера и всем запросам задавать таймауты – одна из стандартных рекомендаций в site reliability engineering. Рекомендация эта в SRE обычно обосновывается так, что система с потерями даже при за-критических нагрузках не уходит в штопор. Но оказывается, одновременно улучшается и качество обслуживания при нагрузках ниже критических

Вероятность потерь

Для системы с одним сервером и ограниченной очередью размера Q (M/M/1/Q) вероятность потерь равна $$\frac{(1-a)a^{Q+1}}{1-a^{Q+2}}$$, где а – входящая нагрузка в Эрлах8.

При малой нагрузке вероятность потерь очень мала даже при небольшом размере очереди: $$P_{loss}\overset{a \ll 1}\approx a^{Q+1}$$. В за-критической области a>>1 вероятность потерь слабо зависит от размера очереди – кривые для разных Q стягиваются к $$P_{loss}\approx 1-\frac{1}{a}$$. То есть размер очереди заметно влияет на потери только близко к критической области $$a\sim 1$$.

В частности, при входящей нагрузке в 1 Эрл (критическая нагрузка для системы с неограниченной очередью) в системе с очередью размером Q теряется $$\frac{1}{Q+2}$$ трафика – то есть система с буфером в 10 элементов будет терять всего ~8% входящего трафика9.

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

…В приемную Апполинарию Матвеевичу достаточно поставить 5 стульев.

Для модели с таймаутами (Эрланг-А) существуют явные формулы вероятности потерь10 разной степени громоздкости. Но у них есть большой недостаток: в модели с таймаутами результаты сильно зависят от конкретного вида распределения таймаутов11 – т.е. аналитические формулы, полученные для экспоненциального распределения таймаутов, дадут большую погрешность, если реальное распределение далеко от экспоненциального. А для компьютерных систем оно, скорее всего, будет сильно не-экспоненциальным – это для клиентов-людей экспоненциальное распределение терпеливости похоже на правду, а TTL запросов в компьютерных системах часто вообще фиксированный, либо представляет собой дискретное распределение поверх небольшого количества значений. Поэтому для компьютерных систем численные оценки по модели Эрланг-А не надежны12.

Примечания и литература

  1. Систему Эрланг-C чаще рассматривают с бесконечной очередью, но анализ системы с конечной очередью ничем не отличается, только формулы получаются еще чуть более крокодиловыми – суммы конечных геометрических рядов более громоздки, чем суммы бесконечных. Частный случай системы вовсе без очереди исторически был проанализирован первым, и поэтому имеет собственное название Эрланг-B.

  2. Система Эрланг-А ("А" = abadonment) еще называется Эрланг-А/Palm: ее проанализировал Конрад Палм почти через 30 лет после Эрланга.

  3. Здесь как раз появляется разница между входящей нагрузкой (offered load) и обрабатываемой нагрузкой (carried load): система с бесконечной очередью уступает по качеству обслуживания системе с конечной очередью/таймаутами при равной обрабатываемой нагрузке – но чтобы создать одинаковую обрабатываемую нагрузку, входящая нагрузка у этих систем должна отличаться как раз на величину потерь.

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

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

  6. Чтобы загрузить систему M/M/1/10 на 80%, нужно подать ей на вход ~0.828 Эрла нагрузки – из которых ~0.028 Эрла будут потеряны, а оставшиеся 0.8 Эрла обработаны, и создадут утилизацию 80%.

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

  8. Для системы с s серверами, M/M/s/Q тоже существует явная формула вероятности потерь, но она более громоздкая, так ее "явность" мало что дает. Чтобы было понятно, что я имею в виду, когда говорю про громоздкость: $$P_{loss}(s)=\frac{\frac{a^s}{s!}\left(\frac{a}{s}\right)^Q}{\sum_{i=0}^{s-1}\frac{a^i}{i!}\ +\ \frac{a^s}{s!}\frac{1-(\frac{a}{s})^{Q+1}}{1-\frac{a}{s}}}$$

  9. Чтобы убавить желание порезать все буфера до 10 ячеек напомню, что результаты получены для модели, где время обработки и интервалы между задачами распределены экспоненциально. В реальности они часто не распределены экспоненциально. Но даже если распределения близки к экспоненциальному, наверняка случаются локальные всплески нагрузки (запуск, остановка, реконфигурация, swapping, и т.п.) – для них желательно иметь буфер все-таки с запасом относительно рассчитанного по модели Эрланга.

  10. "The Palm/Erlang-A Queue, with Applications to Call Centers" (Avishai Mandelbaum and Sergey Zeltyn, 2005)

  11. …The fluid model accurately shows that steady-state performance depends strongly upon the time-to-abandon distribution beyond its mean, but not upon the service-time distribution beyond its mean ("Fluid Models for Multiserver Queues with Abandonments", Witt 2006)

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

    Конечно, можно реализовать аккуратную обработку таймаутов – например, передавать TTL вместе с запросом, чтобы сервер сам мог сбрасывать протухшие – но это нужно делать, и часто этого не делают. То есть по всем статьям модель Эрланг-А заметно хуже отображается на реальные системы с таймаутами, чем Эрланг-С на реальные системы с ограниченной очередью.

27 июля 2020 г.

Queueing theory for fun and practice (#2): нагрузка и время отклика

Во храме Божьей Матери Поклонской батюшка Иннокентий принимает исповедь у раба божьего обыкновенно минут за 10, а утешения жаждут около 5-и рабов божьих в час. Много ли стульев надобно поставить во храме, дабы исповеди ожидающие не толпились в праздности пред святым алтарем?

"Массовое окормление паствы: пособие для начинающих" (редакция 3-я, неизданная)

(Часть 2, начало: ТМО, square root staffing, Little)

Как зависит время отклика от нагрузки на систему (утилизации)? Для многих систем измерения дадут что-то вроде такой картинки:

Такую кривую зависимости среднего времени отклика от нагрузки за характерную форму часто называют J-curve. Конечно, не обязательно кривая в конкретной системе будет выглядеть точно так – например, могут присутствовать ступеньки, соответствующие разным механизмам, которые ответственны за время отклика – но в среднем такая кривая свойственна многим системам, и приводит к ней как раз наличие внутренних очередей/буферов.