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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность потерь для ограниченной очереди

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

Откуда берется эта формула: в предыдущей статье я уже упоминал, что очередь на 1 элемент длиннее образуется в $$\rho$$ раз реже – т.е. вероятности очередей последовательных размеров соотносятся как $$\frac{P(L_q=N+1)}{P(L_q=N)}=\rho$$ (потому что очередь увеличивается в $$\rho$$ раз быстрее/медленнее, чем уменьшается). В общем случае это верно приближенно, для больших очередей, но для пуассоновских систем это верно точно, и для любых размеров очереди. Когда в системе один сервер, то $$\rho=a$$, то есть $$P(L_q=N)=P(L_q=0)a^N=P(empty)a^{N+1}$$. Вероятность $$P(empty)$$ обнаружить систему совсем пустой (без очереди, и не занятой) можно получить из нормировки общей вероятности на 1, и в итоге получится:

$$P_{loss}=P(L_q=Q)=\frac{a^{Q+1}}{1+a+a^2+...+a^{Q+1}}=\frac{1-a}{1-a^{Q+2}}a^{Q+1}$$

При малой нагрузке $$P_{loss}(a \ll 1)\approx a^{Q+1}$$ – т.е. вероятность потерь получается очень малой, даже для короткой очереди.

В за-критической области a>>1 вероятность потерь слабо зависит от размера очереди: кривые для разных Q стягиваются к $$P_{loss}(a\gg 1)\approx \frac{a-1}{a}$$ – т.е. система загружена почти на 100%, из a Эрлов входной нагрузки она обрабатывает свой максимум в 1 Эрл, а все остальное отбрасывается.

Получается, что размер очереди заметно влияет на потери только близко к критической области $$a\sim 1$$ – по графикам можно прикинуть, что примерно в интервале 50%..150%.

В частности, при входящей нагрузке в 1 Эрл (критическая нагрузка для системы с неограниченной очередью) в системе с очередью размером Q теряется $$\frac{1}{Q+2}$$ трафика. Мне кажется, это удобно использовать для оценок на салфетках: система с буфером в 10 элементов будет терять не более $$1/12\approx 8\%$$ на всем интервале входной нагрузки от 0 до 100% – и это оценка сильно сверху, на бОльшей части этого интервала она будет терять гораздо меньше⁹.

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

Модель с таймаутами

Классическая модель Эрланг-А/Palm для компьютерных систем не очень подходит: в ней предполагается, что таймауты разных задач распределены экспоненциально. Для клиентов-людей экспоненциальное распределение терпеливости похоже на правду, но TTL запросов в компьютерных системах обычно вообще фиксированный, либо представляет собой дискретное распределение поверх небольшого количества значений. При этом известно, что результаты довольно сильно зависят от конкретного вида распределения таймаутов¹⁰ – аналитические формулы, полученные для экспоненциального распределения таймаутов, дадут большую погрешность, если реальное распределение далеко от экспоненциального ¹¹.

Однако есть модель аналогичная Эрланг-А, но с фиксированными таймаутами – как раз то, что нужно ¹². Формула для вероятности потерь в этой модели выглядит так: $$P_{loss} = \frac{(1-a)a e^{-(1-a)\frac{D}{\overline{\tau}}}}{1-a^2e^{-(1-a)\frac{D}{\overline{\tau}}}}$$ где a это входящая нагрузка в Эрлах, D – таймаут, а $$\overline{\tau}$$ это среднее время обработки задач. Вероятность потерь зависит только от отношения $$D/\overline{\tau}$$, а не от абсолютной величины таймаута D – среднее время обработки выступает естественным масштабом. По структуре выражение похоже на формулу для ограниченной очереди, только множитель $$a^Q$$ заменен на $$e^{-(1-a)\frac{D}{\overline{\tau}}}$$ – поэтому и поведение логично ожидать похожее, и так оно и есть:

На графике серия кривых потерь в зависимости от нагрузки a для системы с детерминированными таймаутами. Для сравнения пунктиром изображены кривые потерь для системы Эрланг-С c ограниченной очередью.

Поведение системы с таймаутом $$D=n\overline{\tau}$$ сильно похоже на поведение системы с очередью размером n – разница есть, но не приглядываясь ее можно и не заметить. В частности, в критической точке a=1 система с таймаутам $$D=n\overline{\tau}$$ тоже будет терять $$\frac{1}{n+2}$$ часть входящего трафика, и при $$a\gg 1$$ кривые с таймаутами сходятся к той же самой асимптотике $$P_{loss}\approx \frac{a-1}{a}$$, что и система с очередью. Система с таймаутом теряет чуть большую долю задач до критической точки a=1, зато чуть меньшую долю задач теряет после нее – но разница невелика, при n=16 ее уже практически не разглядеть. Т.е. в первом приближении можно считать, что задать TTL в n раз больше среднего времени обработки это плюс-минус эквивалентно ограничению буфера размером n.

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

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 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)↩

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

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

12. "Call centers with impatient customers: exact analysis and many-server asymptotics of the M/M/n+G queue" (Sergey Zeltyn, Technion, 2004) – в диссертации построено решение для произвольного распределения таймаутов, но, кроме нескольких частных случаев, результат будет выражаться через неберущиеся интегралы.↩

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