Во храме Божьей Матери Поклонской батюшка Иннокентий принимает исповедь у раба божьего обыкновенно минут за 10, а утешения жаждут около 5-и рабов божьих в час. Много ли стульев надобно поставить во храме, дабы исповеди ожидающие не толпились в праздности пред святым алтарем?
"Массовое окормление паствы: пособие для начинающих" (редакция 3-я, неизданная)
(Часть 2, начало: ТМО, square root staffing, Little)
Как зависит время отклика от нагрузки на систему (утилизации)? Для многих систем измерения дадут что-то вроде такой картинки:
Такую кривую зависимости среднего времени отклика от нагрузки за характерную форму часто называют J-curve. Конечно, не обязательно кривая в конкретной системе будет выглядеть точно так – например, могут присутствовать ступеньки, соответствующие разным механизмам, которые ответственны за время отклика – но в среднем такая кривая свойственна многим системам, и приводит к ней как раз наличие внутренних очередей/буферов.
Было бы удобно иметь явный вид зависимости $$W(\rho)$$. К сожалению, с явным аналитическим выражением для этой зависимости все непросто. Детальная форма кривой зависит от многих факторов, таких как:
- точный вид статистических распределений времен прихода задач и длительности их обработки (есть теорема, что, в общем случае, недостаточно только средних значений и дисперсий этих распределений)
- способ распределения задач по серверам, если серверов больше одного
- дисциплина очереди – порядок выборки задач из очереди (FIFO, LIFO, random, shortest first…)
- … и чего-то там еще
Решения в явном виде для общего случая не известно (скорее всего, его и не существует1) – но есть несколько точных решений для частных случаев, и изрядное количество приближенных решений и асимптотических оценок для более общих случаев.
Вот несколько из них 2:
| # | Тип системы | Формула | Примечание |
|---|---|---|---|
| 1 | M/M/1 |
$$\frac{\bar{W_q}}{\bar{\tau}}=\frac{\rho}{1-\rho}$$ | Эрланг-C(1) |
| 2 | M/G/1 |
$$\frac{\bar{W_q}}{\bar{\tau}}=\frac{\rho}{1-\rho}\frac{1+c_{p}^2}{2}$$ | Поллачек-Хинчин |
| 3 | G/G/1 |
$$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{\rho}{1-\rho}\frac{c_{in}^2+c_{p}^2}{2}$$ | Kingsman |
| 4 | M/M/s |
$$\frac{\bar{W_q}}{\bar{\tau}}=\frac{E_{2,s}(\rho)}{s(1-\rho)}$$ | Эрланг-C(s) 3 |
| 5 | G/G/s |
$$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{\rho^\sqrt{2(s+1)}}{s(1-\rho)}\frac{\sigma_{in}^2+\sigma_{p}^2}{2}$$ | Sakasegawa4 |
| 6 | G/G/s |
$$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{\rho}{s(1-\rho)}\frac{c_{in}^2+c_{p}^2}{2}$$ | Simple heavy traffic approximation |
| 7 | G/G/s |
$$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{E_{2,s}(\rho)}{s(1-\rho)}\frac{c_{in}^2+c_{p}^2}{2}$$ | Allen-Cunneen |
(Для краткости я привел время ожидания в очереди, $$\bar{W_q}$$, обезразмеренное за счет деления на среднее время обработки $$\bar{\tau}$$ – оно иногда называется congestion index. s – число серверов, $$\rho$$ – утилизация, $$c_{in},\ c_p$$ – коэффициенты вариации входящего трафика и времени обработки соответственно, а $$E_{2,s}(\rho)$$ – значение формулы Эрланга 2-го рода5)6
Формулы довольно похожи, и видны общие закономерности7:
- Среднее время в очереди зависит от утилизации примерно как $$\sim\frac{\rho}{1-\rho}$$, в более точных приближениях как $$\sim\frac{\rho^s}{1-\rho}$$.
- При низкой утилизации время в очереди растет примерно линейно с $$\rho$$ (а в более точных приближениях примерно как $$\rho^s$$), при высокой утилизации оно растет обратно пропорционально оставшейся свободной емкости, $$1/(1-\rho)$$.
- Чем больше количество серверов
s, тем позже происходит переход между $$\sim\rho^s$$ и $$\sim 1/(1-\rho)$$. - Т.к. утилизация прямо пропорциональна входной нагрузке, то все вышеописанное прямо переносится на зависимость от входной нагрузки.
- Утилизация так же прямо пропорциональна среднему времени обработки $$\bar{\tau}}$$, но среднее время обработки еще участвует в обезразмеривании congestion index $$W_q/\bar{\tau}}$$, поэтому размерное время ожидания $$W_q\sim\bar{\tau}^{s+1}$$. В частности, для одного сервера время в очереди получается пропорциональным квадрату времени обработки задачи – т.е. чтобы уменьшить время ожидания гораздо эффективнее оптимизировать среднее время обработки, чем уменьшать нагрузку.
- Время в очереди пропорционально квадрату вариабельности.
Формул слишком много, как же быть?
Для практического использования вряд ли имеет смысл запоминать все приближения (тем более, что это далеко не все они) – проще всего запомнить какую-то из последних двух формул:
G/G/sSimple heavy traffic8: $$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{\rho}{s(1-\rho)}\frac{c_{in}^2+c_{p}^2}{2}$$G/G/sAllen-Cunneen: $$\frac{\bar{W_q}}{\bar{\tau}}\approx\frac{E_{2,s}(\rho)}{s(1-\rho)}\frac{c_{in}^2+c_{p}^2}{2}$$
Они отличаются одним множителем $$\rho \leftrightarrow E_{2,s}(\rho)$$
(Если известно среднее время ожидания, то средний размер очереди всегда можно получить по формуле Литтла: $$\overline{L}_q=\lambda\overline{W}_q$$)
Приближение Allen-Cunneen удобно тем, что вырождается в точные формулы для систем Эрланга, Поллачека-Хинчина, и в приближение Кингсмана. Иначе говоря, Allen-Cunneen накрывает 5 из 7-и формул, перечисленных в таблице в первой части – вырождается в 4 точных и одно приближенное решение.
Однако для практических целей, особенно для прикидок в уме, или "на салфетках" Allen-Cunneen слишком сложен (формула Эрланга $$E_{2,s}(\rho)$$, которая в него входит – очень громоздкая). Для этих целей simple heavy traffic подходит лучше.
Обе формулы приближенные, у них есть границы применимости:
- Не слишком большое количество серверов
s(не больше десятков для A-C). То есть 16-ядерный сервер еще нормально, а вот ферма на 100 серверов уже скорее всего нет. - Не слишком большие коэффициенты вариации $$c_{in},\ c_p$$ – точность падает когда они больше 5, а выше 10-15 уже становится совсем плохой. Если входной поток и/или время обработки слишком иррегулярны, то формулы не дадут хорошего результата.
Обе формулы лучше работают при высокой нагрузке, когда очередь почти всегда есть9, и в этой области разница в точности между ними невелика, потому что $$E_{2,s}(\rho) \overset{\rho\rightarrow 1}\approx 1 \approx \rho$$. В этих границах обещается погрешность <10-15%
В области средних нагрузок simple heavy traffic обычно переоценивает время ожидания, особенно для s>1 ($$E_{2,s=1}(\rho)=\rho,\ E_{2,s>1}(\rho) \leq \rho$$), и проигрывает в точности Allen-Cunneen – Allen-Cunneen и был создан как раз чтобы подтянуть точность в области средних нагрузок10
При малых нагрузках обе формулы дают большую относительную погрешность, но это обычно не важно, потому что при малых нагрузках время ожидания в очереди это лишь малая часть от общего времени отклика, и большая относительная погрешность времени ожидания превращается в пренебрежимо малую абсолютную погрешность общего времени отклика – если среднее время ожидания в очереди составляет 5% от времени обработки, то 300% погрешности во времени ожидания превратятся в 10% погрешности общего времени в системе.
Откуда возникает такая зависимость?
Ниже я пытаюсь несколькими способами более-менее на пальцах объяснить, как образуется зависимость вида $$W_q \sim \frac{\overline{\tau}}{s}\frac{\rho^s}{1-\rho}\frac{c_{in}^2+c_{p}^2}{2}$$. Честно говоря, ни один из способов мое собственное чувство прекрасного полностью не удовлетворяет: они сложнее, и менее наглядны, чем хотелось бы. Так что не исключено, что кому-то будет проще и понятнее разобраться с честным анализом системы Эрланга-С. Я предупредил :)
Начнем с малой утилизации: при малой утилизации очередь возникает редко – бОльшую часть времени ждать вообще не приходится, а если уже пришлось, то почти наверняка только одну задачу, которая прямо сейчас в работе. Поэтому среднее время ожидания в первом приближении это вероятность обнаружить сервер занятым, умноженная на остаточное время обработки той задачи, которой он занят: $$P_{occupied}W_{remaining}$$. Если сервер один, то вероятность обнаружить его занятым это и есть утилизация, поэтому в первом приближении $$\overline{W}_q \sim \bar{\tau}\rho$$. Если вспомнить историю про остаточное время из парадокса времени ожидания, то выражение получится чуть точнее: $$\overline{W}_q \sim \bar{\tau}\rho\frac{1+c_p^2}{2}$$ – уже видно, откуда появляется коэффициент вариации.
Аналогичное рассуждение для s серверов дает первое приближение $$\overline{W}_q \sim \overline{\tau}\rho^s$$ – как вычислить точнее среднее остаточное время в случае s серверов я не знаю, поэтому придется на этом остановиться.
Если утилизация не маленькая, и очередь возникает часто – то насколько она большая? Я приведу два способа оценить средний размер очереди: один простой, второй труднее, но (мне кажется) понятнее.
Первый способ опирается на теорему Литтла, примененную к очереди (в предыдущей статье серии я о ней упоминал): $$\overline{L}_q=\lambda\overline{W}_q$$. Но среднее время ожидания в очереди можно оценить как время исчерпания очереди плюс остаточное время обработки той задачи (задач) которая сейчас в работе11:
$$\overline{W}_q\approx\overline{L}_q\overline{\tau}/s+\overline{W}_{remaining}$$
Объединяя эти выражения получаем:
$$\overline{L}_q \approx \lambda\left(\overline{L}_q\frac{\overline{\tau}}{s} + \overline{W}_{remaining}\right)\ \ \implies\ \overline{L}_q \approx \frac{\lambda\overline{W}_{remaining}}{1-\frac{\lambda\overline{\tau}}{s}} = \frac{\lambda\overline{W}_{remaining}}{1-\rho}$$
$$\overline{W}_q \approx \frac{\overline{W}_{remaining}}{1-\rho}$$
Для 1 сервера мы уже выяснили, как выглядит среднее остаточное время: $$\overline{W}_{remaining}=\overline{\tau}\rho\frac{1+c_{p}^2}{2}$$, и подставив его получаем:
$$\overline{W}_q \approx \overline{\tau}\frac{\rho}{1-\rho}\frac{1+c_{p}^2}{2}$$
что совпадает с точной формулой Поллачека-Хинчина для M/G/112.
Для s серверов точного выражения для среднего остаточного времени я не знаю, но даже с оценкой $$\overline{W}_{remaining}\sim\overline{\tau}\rho^s$$ получается практически то, что нужно:
$$\overline{W}_q \sim \overline{\tau}\frac{\rho^s}{1-\rho}$$
Альтернативный способ получить примерно тот же результат: заметить, что отношение вероятностей появления очереди размером N+1 и N равно утилизации: $$\frac{P[L_q=N+1]}{P[L_q=N]}\approx\rho$$ – то есть эти вероятности образуют геометрическую прогрессию $$P[L_q=N] \sim \rho^N$$.
Почему? Потому что вероятность увеличения очереди на единицу в какой-то малый период времени в $$\rho$$ раз меньше, чем вероятность ее уменьшения на единицу в тот же период – ведь пока очередь есть, все сервера загружены на 100%, то есть убывают задачи из очереди с условной скоростью 1, а прибывают в очередь новые задачи со скоростью только $$\rho$$. А это значит, что чтобы вероятности $$P[L_q=N]$$ не менялись во времени, нужно чтобы они убывали как $$\rho^N$$ 13
Отсюда, пропуская пол-страницы суммирования геометрических рядов, можно получить для времени ожидания в очереди оценку
$$\overline{W}_q \sim \frac{\overline{\tau}}{s}\frac{1-P[L_q=0]}{\rho}\frac{1}{1-\rho}$$
Этот способ сложнее, но (мне кажется) более нагляден, потому что понятно, откуда берется $$1/(1-\rho)$$ – и в качестве бонуса проявляется интересное свойство очереди14.
Я думаю, теперь уже видно, как устроены формулы из таблицы в первой части:
$$\overline{W}_q \approx \underbrace{\frac{\overline{\tau}}{s}}_\textrm{1/скорость утекания очереди} \overbrace{\frac{f(\rho)}{(1-\rho)}}^\textrm{средняя длина очереди}\underbrace{\frac{c_{in}^2+c_{p}^2}{2}}_\textrm{поправка на остаточное время}$$
где в качестве $$f(\rho)$$ в разных вариантах выступают $$\rho,\ \rho^{\sqrt{2(s+1)}},\ E_{2,s}(\rho)$$
Как насчет перцентилей?
Ок, со средним временем ожидания разобрались – а как получить перцентили?
Проще всего получить перцентили для общего времени в системе (RTT) для системы с пуассоновскими потоками (читай: M/M/s): общее время в системе распределено экспоненциально. Так как у экспоненциального распределения только один параметр – среднее значение – то любые перцентили находятся в фиксированном отношении со средним значением $$W(P\%)=c(P)\overline{W}_{RTT}$$, где $$c(P)=-ln(1-P)$$ – т.е. решение уравнения $$1-e^{-c}=P$$
Для быстрых оценок в уме можно вычислить эти коэффициенты для нескольких перцентилей (50%, 80%, 90%…) и округлить до ближайших красивых дробей, которые легко запомнить – например, вот так15:
- $$W_{50\%} \approx \frac{2}{3}\ \overline{W}$$
- $$W_{80\%} \approx \frac{5}{3}\ \overline{W}$$
- $$W_{90\%} \approx \frac{7}{3}\ \overline{W}$$
- $$W_{95\%} \approx \frac{9}{3}\ \overline{W}$$
Для систем общего вида G/G/s в пределе большой нагрузки и большой очереди (aka heavy traffic) время ожидания распределено по закону $$P(W>X) \approx \alpha e^{-\beta X}$$. Здесь уже 2 параметра, и связать их со свойствами системы не так-то просто: есть оценки вида $$\beta\approx\frac{2s(1-\rho)}{c^2_{in}+c^2_{p}},\ \alpha\approx\beta\overline{W}}$$, но в итоге все равно получается крокодил, который на салфетке не посчитаешь.
Остается либо применять формулы для пуассоновских систем, надеясь, что ошибка окажется не слишком велика, либо писать честную симуляцию.
…продолжение, вероятно, следует…
Примечания и литература
Например: "…not likely that computationally tractable methods can be developed to compute the exact numerical values of the steady-state probability in the M/G/k queue" (wiki)↩
"Approximations for the GI/G/m queue" (Ward Witt, 1993). Ward Witt один из ведущих экспертов в теме, и его статья начинается с хорошего обзора известных приближений – большинство приближений из этой статьи затронуты в его обзоре. Еще один источник информации, но хуже структурированный – слайды к курсу Техниона "Service Engineering (096324)" (к теме поста относится лекция 11)↩
Формулы для систем Эрланга-C, Поллачека-Хинчина, и приближение Кингсмана можно найти в википедии – правда, без особых подробностей.↩
"An approximation formula $$L_q\approx\alpha\rho^\beta/(1-\rho)$$", Hirotaka Sakasegawa, 1976.↩
Формула Эрланга 2-го рода, она же формула Эрланг-C, дает вероятность того, что в системе
M/M/sс утилизацией $$\rho$$ все сервера заняты – т.е. вероятность того, что новая задача, пришедшая в произвольный момент времени, встанет в очередь.Сама формула – тот еще крокодил:
$$E_{2,s}(\rho)=\frac{\frac{(s\rho)^s}{s!}\frac{1}{1-\rho}}{\sum_{i=0}^{s-1}\frac{(s\rho)^i}{i!} + \frac{(s\rho)^s}{s!}\frac{1}{1-\rho}}=\frac{1}{1+(1-\rho)\left(\frac{s!}{(s\rho)^s}\right)\sum_{i=0}^{s-1}\frac{(s\rho)^i}{i!}}$$
Мало того, что в уме ее не посчитаешь, так и на компьютере вычислять по этой формуле не рекомендуется – благодаря факториалам уже для сравнительно небольших
sбудут накапливаться большие погрешности, и для вычислений лучше использовать рекуррентные соотношения. Если нужно посчитать значение формулы Эрланга, то лучше найти готовую реализацию в каком-нибудь пакете численных методов – или, например,wolframalpha.comпо запросу "erlang-C formula" предоставит потребное (в интернете полно онлайн-калькуляторов, но кто их знает, насколько хорошая там реализация).Несколько свойств формулы Эрланга-С: $$E_{2,s}(\rho=0)=0,\ E_{2,s}(\rho=1)=1$$ $$E_{2,s=1}(\rho)=\rho,\ E_{2,s>1}(\rho) \leq \rho$$↩
Подразумевается что дисциплина очереди = FIFO, и алгоритм распределения по серверам = "первый свободный". И распределения хоть и общего вида, но подразумеваются взаимно-независимыми – например, вероятность прихода задачи длительностью T не зависит от времени, прошедшего с предыдущей задачи.↩
Это не исчерпывающий список: есть и другие точные решения, и другие аппроксимации – но лучше запомнить одну формулу, чем не запомнить 5.↩
Simple heavy traffic approximation не очень удобное название, потому что есть много heavy traffic approximations – через раз так называют формулу Кингсмана, да и Allen-Cunneen попадает в эту категорию. Но ничего лучшего, чем simple heavy traffic approximation для этого приближения я в литературе не нашел.↩
Название heavy traffic approximation означает не просто что нагрузка большая, а что нагрузка такая большая, что почти всегда есть очередь (sic!). Высокая утилизация, $$\rho \rightarrow 1$$, сама по себе этого не гарантирует – в разделе про square root staffing я уже упоминал, что чем больше серверов, тем ближе можно подойти к 100% утилизации без ухудшения качества обслуживания ("экономия от масштаба"). Например, для
M/M/n95% утилизация при 10 серверах означает 80% вероятности образования очереди, а при 1000 серверах – всего лишь 7%. То есть 1000 серверов с загрузкой в 95% еще не находятся в области heavy traffic.↩Имейте в виду, что за simple heavy traffic стоит теоретическая модель, а вот Allen-Cunneen это подгонка – из нескольких точных и приближенных формул сшили что-то, что хорошо приближает известные точные решения и результаты симуляций.↩
$$\overline{L}_q \overline{\tau}/s$$ это примерное время исчерпания очереди
sсерверами, когда в задач в очереди больше, чем серверов, и можно пренебречь дискретностью задач – рассматривать их как непрерывную "жидкость" вытекающую со скоростьюs. Если очередь маленькая, $$L_q < s$$, то исчерпываться она будет медленнее, потому что дискретностью уже нельзя будет пренебречь, ведь 9 женщин не могут выносить ребенка за 1 месяц. То есть полученная формула будет тем точнее, чем больше средний размер очереди – так называемое heavy traffic approximation.(При некоторых комбинациях параметров задачи – свойств статистических распределений и/или числа серверов – формула оказывается точна независимо от размера очереди)↩
Нестрогий, но зато доступный вывод формулы Поллачека-Хинчина можно посмотреть вот здесь на русском, и вот здесь на английском. Оба вывода используют примерно ту же идею, что и здесь, но заходят в нее немного с разных сторон, непонятны в разных местах, и потому хорошо дополняют друг друга.↩
Это рассуждение верно либо для трафика с удачными статистическими свойствами (читай: для пуассоновского), либо для большой очереди, когда дискретностью задач можно пренебречь. То есть и в этом случае мы имеем дело с heavy traffic approximation.↩
Оба варианта вывода не претендуют на точность – я срезал очень много углов. Но их можно сделать более-менее точными: первый вариант действительно используется для вывода формулы Поллачека-Хинчина (см. выше), а второй вариант в более аккуратном, развернутом виде используется для вывода формул Эрланга.↩
Идея взята из "The Essential Guide to Queueing Theory", она же изложена в блоге одного из авторов Percentile Rules of Thumb (не знаю, сами ли они ее придумали, или тоже откуда-то взяли).
Сравните точные значения обратной функции распределения, со значением соответствующих дробей:
P 50% 80% 90% 95% 99% -ln(1-P) 0.693 1.609 2.302 2.995 4.605 Fraction 2/3 5/3 7/3 9/3 14/3 = 0.666 1.666 2.333 3.000 4.666 погрешность не превышает 5%. Как видно, для 99% тоже можно подобрать дробь вида x/3, но красивой последовательности числителей уже не получится. Да и вряд ли вообще имеет смысл оценивать 99% – ведь экспоненциальное распределение времени ожидания это лишь приближение.↩
Комментариев нет:
Отправить комментарий