Queueing theory for fun and practice (#1): square root staffing, Little's law

На 28-ом этаже центра разработки крупного инвестиционного банка есть 8 туалетных кабинок для людей, идентифицирующих себя с мужским гендером. Работающий в центре высокофункциональный аутист Иннокентий подсчитал, что когда он заходит в туалет, в среднем 5 из 8 кабинок уже заняты.

Сколько человеко-часов в день сотрудники офиса спускают в унитаз?

"Теория массового обслуживания для сантехников" (неизданное)

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

Материалы, которые мне попадались по теории массового обслуживания, распадаются на две категории: ТМО как раздел математики (теории вероятности), и ТМО как раздел бизнес-управления, менеджмента производства/обслуживания (operations research).

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

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

Примерный список тем, которые я хочу охватить (в нескольких постах):

1. Ключевая терминология (нагрузка, утилизация, нотация Кенделла)
2. Запас емкости и масштабирование (square root staffing)
3. Теорема Литтла
4. Время отклика vs утилизация (J-curve, Kingsman, Allen-Cunneen...)
5. Системы Эрланга
6. Дальше не придумали, импровизируй

Disclaimer: я не эксперт в области ТМО, поэтому не относитесь к этому конспекту слишком серьезно. Это то, что я сам успел узнать и понять, и что мне показалось достаточно простым, но интересным и полезным, чтобы это попытаться запомнить.

И конечно я не собираюсь покрыть всю ТМО: в основном я буду писать про сервера, очереди, и capacity planning. И я не планирую глубоко вдаваться в разбор каждого пункта – все это самая-самая база ТМО, и более глубокий разбор любой темы легко найти в интернете, если знать, что искать.

О чем вообще теория очередей?

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

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

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

Здесь и начинается интересное. Очевидный, и несколько неприятный вывод: без точного знания нагрузки наперед невозможно обеспечить одновременно а) высокий КПД использования ресурсов системы и б) высокое качество обслуживания. Чем ближе к 100% система загружена в среднем, тем более вероятно, что статистические флуктуации нагрузки в моменте превысят ее емкость – и тогда части клиентов придется отказать в обслуживании, либо оставить их ждать в очереди, пока ресурсы освободятся.

Это и есть центральная тема теории массового обслуживания – как связаны эффективность использования ресурсов и качество обслуживания для разных систем в разных условиях, и какие оптимальные режимы из этого можно получить для разных критериев оптимальности.

Утверждение, что для хорошего качества обслуживания как правило нужен КПД существенно менее 100% – может казаться очевидным, но это не всегда так. Например, по странному капризу интуиции часто не очевидно, что ~100% загруженный человек или команда – не смогут качественно работать так же, как и 100% загруженный сервер (см. раннего Дорофеева).

Терминология (нотация X/Y/k/s, нагрузка, утилизация…)

У теории очередей есть своя терминология – местами довольно странная и непривычная, ибо происходит из телефонии и телекома. Именно поэтому полезно знать хотя бы ее основы – иначе бывает сложно понять, о чем говорят иностранцы теоретики, даже если они говорят что-то достаточно простое.

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

Нотация Кендалла: в рамках теории очередей рассматривается много разных систем, и некоторые имеют свои имена (системы Эрланга, Поллачека-Хинчина, Энгсета…), но удобно иметь какую-то универсальную классификацию. Нотация Кенделла и есть такая классификация: основные параметры системы кодируются набором непонятных символов X/Y/k/s…:

• X: статистическое распределение интервалов между последовательными входящими задачами
• Y: статистическое распределение времен обработки задач
• k: количество серверов²
• s: максимальный размер очереди³ (если опущен, то очередь не ограничена)
• …(иногда в конец дописывают еще параметры, но их обычно оговаривают)

Статистические распределения в нотации Кендалла обозначаются буквами: чаще всего встречается пуассоновское распределение (M⁴), детерминированное (=постоянные интервалы, D) и распределение общего вида (G).

Например: M/D/2 это система с пуассоновским распределением интервалов между приходом задач, детерминированным временем обработки задач, двумя серверами, и бесконечной очередью на входе.

(Помимо простого удобства нотация Кенделла еще и подсказывает, как вообще выглядит пространство проблем в ТМО: т.е. 2 статистических распределения и 2 целых числа в первом приближении идентифицируют систему. Во втором приближении важна еще дисциплина очереди, если очередь есть – FIFO, LIFO, random, shortest first…)

Нагрузка (load): интенсивность потока задач – объем задач (в единицах длительности их исполнения, т.е. в секундах), поступающих за секунду. Вообще величина безразмерная, но условная единица измерения – Эрланг (Эрл), равен потоку задач в одна секунду работы за секунду. Т.е. если в в систему за секунду в среднем влетает 10 задач со средним временем исполнения в 0.01 сек каждая, то это нагрузка в 0.1 Эрл. Общая формула так и выглядит: нагрузка = (количество задач/сек)*(среднее время обработки задачи, сек)⁵

Понятие нагрузки в ТМО отличается от привычного (поэтому я и вынес его в необходимый минимум): обычно мы говорим о нагрузке в "абсолютных" единицах – транзакциях/сек, или байтах/сек, или что-то вроде того. В ТМО же нагрузка измеряется в секундах работы, прилетающих за секунду. Но время работы зависит от конкретной системы, которая нагрузку будет обрабатывать – т.е. нагрузка в ТМО измеряется относительно возможностей системы.

Например: если сервер А обрабатывает одну транзакцию в среднем за 0.1 секунду, то 10 транзакций в секунду для этого сервера будут составлять 1 Эрл нагрузки. Но если тот же поток транзакций в направить в более быстрый сервер Б, который успевает обработать одну транзакцию (в среднем) за 0.01 секунды, то для этого сервера тот же самый поток транзакций будет представлять нагрузку в 0.1 Эрл.

Это может поначалу сбивать с толку, но в таких единицах измерения есть свое удобство: 1 сервер не может обработать больше 1 Эрла нагрузки (не может выполнить больше 1 секунды работы в секунду), т.е. нагрузка в 1 Эрл означает, что 1 сервер все время занят работой, никогда не простаивает. Если в системе 3 сервера – такая система может обработать не более 3 Эрлов нагрузки, и так далее. То есть пересчет нагрузки в Эрланги сразу позволяет соотнестись с количеством серверов и уровнем загруженности системы.

Утилизация (она же эффективность, она же КПД, она же $$\rho$$): доля ресурсов системы, фактически занятых обработкой задач. Тоже безразмерная величина, как и нагрузка, только учитывает еще и количество серверов в системе. Единиц измерения нет – утилизация измеряется просто в процентах. В случае одного сервера утилизация равна обрабатываемой нагрузке, в случае N одинаковых серверов она будет равна (load / N), в случае не одинаковых серверов… ну, придется посчитать.

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

При этом нагрузка и утилизация довольно похожи, и может возникнуть вопрос: не взаимозаменяемы ли они? Нельзя ли обойтись для описания загруженности системы чем-то одним из них?

Оказывается – нельзя, это не взаимозаменяемые вещи. Точнее: из 3 параметров (нагрузка, КПД, количество серверов) систему можно описать любыми двумя, но одним обойтись нельзя.

Простой пример: один быстрый сервер или 2 сервера вдвое медленнее. Утилизация/КПД у обоих систем будет одна и та же, а время отклика будет разным – при малой утилизации 1 быстрый сервер будет иметь время отклика вдвое меньше, чем 2 более медленных.

Время обработки / время ожидания / время в системе: время обработки это чистое время выполнения задачи сервером, без учета ожидания в очереди. Помимо этого есть время ожидания в очереди, и есть полное время в системе – в очереди и в обработке. Последнюю величину мы в IT часто называем "время отклика", или latency. В queueing theory время обработки обычно = service time, время ожидания = waiting time или queueing time, а полное время пребывания в системе = sojourn time или residence time. Я упоминаю о них не потому, что это сложные определения, а потому, что с их употреблением есть некий бардак: нет общепринятых обозначений, и даже названия авторы некоторых статей творчески тасуют, и/или дополняют своими – так что тут надо быть внимательным, разбираясь в какой формуле что есть что. (Похоже, что сосуществуют несколько традиций наименования, и разные авторы просто выросли в разных традициях)

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

Система Эрланг-B = M/M/n/0 – n серверов, нет входного буфера (клиенты отбрасываются, если нет свободных серверов) и оба распределения – пуассоновские. Эрланг-C = M/M/n/Inf — то же самое, только входной буфер есть, и неограничен.

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

Square root staffing rule

Вернемся к свободной емкости: если для поддержания хорошего качества обслуживания всегда нужен запас свободной емкости в системе, то как этот запас посчитать?

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

Что если у нас есть уже функционирующая система, которая налажена и отрегулирована так, что она хорошо справляется с текущей входной нагрузкой – нас все устраивает. Но мы предвидим рост входной нагрузки в N раз, и хотим знать, как систему отмасштабировать, чтобы сохранить качество обслуживания?

(Качество обслуживания в разных источниках определяется как среднее время отклика, и/или как процент задач, отбрасываемых из-за переполнения, если входной буфер ограничен)

Первое, что приходит в голову: увеличивать емкость (количество серверов) прямо пропорционально росту нагрузки. Оказывается, это не очень оптимально: при малом коэффициенте пропорциональности будет ухудшаться качество обслуживания, а при большом качество обслуживания будет расти, но ценой потери в эффективности использования ресурсов (КПД, утилизации).

Square root staffing⁶ rule предлагает другой вариант: занятую емкость нужно масштабировать линейно с нагрузкой, а вот запас емкости нужно масштабировать примерно как корень из нагрузки ⁷.

Например: есть система из 10 серверов, которая обслуживает 1000 клиентов в час, с КПД (утилизацией) 70%, и качество обслуживания (~время отклика) системы нас в этих обстоятельствах полностью устраивает. Но в следующем месяце нагрузка вырастет в 10 раз – сколько примерно серверов нужно заказать, чтобы и в следующем месяце сохранить то же качество обслуживания (время отклика)?

При текущей нагрузке 10*70% = 7 серверов в среднем заняты, и эти 7 серверов точно нужно размножить в 10 раз – нужно 70 серверов чтобы переварить входящий трафик хоть как-то. И еще нужен запас сверху, чтобы переваривать этот трафик сохраняя качество обслуживания

SRSR говорит, что чтобы сохранить качество обслуживания, 3 "запасных" сервера нужно отмасштабировать в корень из нагрузки раз, получится 3*sqrt(10) ~ 10 серверов сверху.

В итоге, нужно примерно (70+10)=80 серверов, чтобы обслуживать 10 000 клиентов с тем же качеством, с которым мы обслуживали 1000 клиентов на 10 серверах с 70% утилизацией. При этом утилизация станет равной 70/80=87.5% – то есть отмасштабированная система имеет КПД на 17.5% больше исходной.

Правило квадратного корня выведено как асимптотика для простых систем типа Эрланг B/C, но в первом приближении выполняется для гораздо более широкого класса систем. И приближение довольно хорошее: например в⁸ авторы пишут, что разница между оценкой по SRSR и точным значением не превышает 1..3 сервера для широкого спектра значений параметров.

Откуда это правило возникает: интуитивно, мне кажется, из центральной предельной теореме.

Ведь запас емкости нужен, чтобы переваривать отклонения от среднего во входном потоке: в среднем прилетает 10 секунд работы в секунду, но в некоторые секунды прилетает сразу 15, и вот эти 5 сверху и должны принять на себя запасные сервера. Значит – запас емкости должен быть пропорционален объему отклонений от среднего в трафике.

Допустим, что трафик растет, потому что растет количество независимых источников трафика – тогда среднее моментальное значение трафика растет линейно с количеством этих источников, а вот отклонения от среднего (=стандартное отклонение) растут как корень из количества источников, это центральная предельная теорема. (Можно обойтись и без ЦПТ – достаточно аддитивности дисперсии независимых случайных величин)

Отсюда можно очертить и границы применимости square root staffing: оно применимо, когда входящий трафик создается N независимыми источниками, и растет трафик за счет роста количества этих источников. Если же весь трафик создают всего 1-2 клиента, которые сильно между собой скоррелированы, то от SRSR не стоит ожидать хорошего прогноза.

Закон (теорема, формула) Литтла

Формула Литтла – наверное, самая известная формула ТМО. Она же и самая простая: в установившемся режиме (если такой существует в системе) среднее по времени число задач N, обрабатываемых системой, равно среднему темпу прихода задач λ, умноженному на среднее время исполнения задачи S:

$$\bar{N}=\bar{\lambda} \bar{S}$$

А средний темп прихода задач умноженный на среднее время исполнения задачи – это и есть входящая нагрузка, в Эрлангах. То есть в терминах ТМО формула Литтла звучит еще проще: "среднее число задач в обработке равно средней нагрузке в Эрлах". Другими словами, формула Литтла предлагает наглядную интерпретацию для понятия нагрузки в ТМО: нагрузка в Эрлангах это просто среднее по времени число задач внутри системы.

Чтобы понять, откуда формула берется, достаточно рассмотреть "объем выполненной работы" (в человеко-часах или серверо-секундах): с одной стороны объем выполненной работы это сумма времени, потраченного на все задачи, с другой стороны это количество занятых работников, умноженное на время занятости.

Для наглядности проще нарисовать исполняемые задачи в осях (время, номер задачи). Каждая задача – прямоугольник, который тянется от момента, когда задача входит в систему, и до момента, когда задача систему покидает. Теперь суммарный "объем работы" – синюю площадь на графике – надо посчитать двумя разными способами: интегрированием по оси Х и суммированием по оси Y. С одной стороны синяя площадь равна сумме площадей всех прямоугольников – каждый высотой 1, и длиной равной времени обработки соответствующей задачи, $$S_i$$.

С другой стороны та же площадь равна интегралу по периоду наблюдения от N(t) – количества задач в системе в момент времени t:

$$\sum_{i=1}^MS_i = \int_0^TN(t)dt \ \ \ \rvert \cdot \frac{1}{T} \implies\ \ \frac{\sum_{i=1}^MS_i}{M}\frac{M}{T}=\frac{\int_0^TN(t)dt}{T}$$

Осталось заметить, что $$\frac{\sum_{i=1}^MS_i}{M} = \bar{S}$$, $$\frac{\int_0^TN(t)dt}{T}=\bar{N}$$, а $$\frac{M}{T}$$ – это количество задач, вошедших в систему за время T, то есть средний темп прихода задач, $$\bar{\lambda}$$:

$$\frac{\sum_{i=1}^MS_i}{M}\frac{M}{T}=\frac{\int_0^TN(t)dt}{T}\ \ \implies\ \ \bar{S}\bar{\lambda}=\bar{N}$$

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

Формула Литтла очень универсальна: она верна для почти любых систем, при любых статистических свойствах входного трафика и времен обработки, и верна не приближенно, а точно.

В частности, формулу можно применять к системе в целом, и к ее подсистемам по отдельности – да вообще к любому ящику, в который что-то входит и выходит. Ящик можно разрезать на части в произвольном месте – ФЛ будет применима к частям по-отдельности. Можно разделить входящий трафик на какие-нибудь "категории трафика" – закон Литтла будет выполняться для каждой категории в отдельности, и для любой их суммы. Нужно только правильно сформулировать, что такое в каждом случае "время в системе" и "число задач в системе".

• Если взять сервер с очередью, то "время в системе" это полное время, в очереди + в обработке, и "число задач в системе" это полное число задач, в очереди + в обработке.

• Если взять сервер отдельно от очереди – тогда "время в системе" это время обработки задачи сервером, без учета ожидания в очереди, а "число задач в системе" это количество задач "внутри" сервера – обрабатываемых сервером сейчас.

• Можно взять очередь отдельно от сервера – тогда "время в системе" это время от попадания в очередь до выхода из очереди на обработку (и оно может быть 0, если задача сразу попадает на обработку), а "число задач в системе" это число задач в очереди.

• Если система с потерями, т.е. часть задач отбрасывается, то эти задачи нужно учитывать как "обработанные за 0 секунд" в среднем времени обработки – либо просто вычесть их из входящего потока.

• Если нагрузка состоит из нескольких типов задач, то ТЛ выполняется для всех их вместе, для каждого типа по отдельности, и для любой комбинации типов. Но в каждом случае в формуле должны стоять соответствующие средние – среднее время в системе для конкретного типа или комбинации типов, и среднее число объектов конкретного типа или комбинации типов, и т.п.

Стационарность системы на самом деле тоже не обязательна – ФЛ будет верна и для нестационарной системы, если взять такой интервал времени, в конце которого система возвращается в то состояние, с которого начинала. Т.е. если сервис перезапускается каждые выходные, то ФЛ будет выполняться, если все средние брать за период от запуска до останова – и неважно, как там все колбасилось внутри недели. Опять же, это можно понять из графической интерпретации.

(Честно говоря, вместо того, чтобы запоминать, где и когда закон Литтла выполняется – проще разобрать доказательство, и обращаться к нему в случае сомнений. Обычно картинки достаточно.)

Минус в том, что оперирует ФЛ только средними величинами, а не 90/95/99%-илями, которые сейчас все больше в ходу для оценки качества обслуживания. Иметь такую же простую формулу для медиан и перцентилей было бы совсем уж сказочно, но увы.

На 28-ом этаже центра разработки крупного инвестиционного банка есть 8 туалетных кабинок для людей, идентифицирующих себя с мужским гендером. Работающий в центре высокофункциональный аутист Иннокентий подсчитал, что когда он заходит в туалет, в среднем 5 из 8 кабинок уже заняты.

Сколько человеко-часов в день сотрудники офиса спускают в унитаз?

Сумма времени, потраченного в туалете, равна общему периоду наблюдения, умноженному на среднее количество занятых туалетов в течении периода. То есть если рабочий день 8 часов, то в день в унитаз смывается 8*5=40 человеко-часов, или 200 часов в неделю.

(Я предположил, что "наблюдаемое Иннокентием среднее" равно "среднему по времени" – довольно грубое предположение, потому что людям свойственно чаще заглядывать в туалет в определенные периоды, когда занятость будет выше, и количество наблюдений будет выше, поэтому высокая занятость будет иметь больший вес в наблюдаемом среднем)

Формула Литтла довольно странная штука: кому-то она кажется очевидной, кому-то совершенно неочевидной. Я несколько раз переходил из одного лагеря в другой, и поэтому попытался разобраться, как так получается. Моя версия: само по себе это соотношение не так уж очевидно, но выражение-то очень простое, а формулировки некоторых задач содержат подсказки для воображения, за которые мозг может уцепиться, и угадать. (Причем мозг может угадать правильную формулу неправильным способом – скажем, через метод размерностей, который вообще-то не диктует равенства). Если же формулировка задачи подсказок не содержит, то догадаться до такого соотношения не зная его – довольно нетривиально.

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

Интересная историческая деталь: формулой Литтла пользовались как "очевидным соотношением" еще до формального доказательства. Однако когда постдок Джон Литтл решил-таки ее аккуратно доказать – он потратил полгода, и столько сил, что отправив статью в печать зарекся работать в области ТМО (как я понял, полгода он возился с теми самыми "обрезками по краям"). С той статьи прошло полвека, и было опубликовано с полдюжины попыток упростить доказательство (ссылки на некоторые из них есть в википедии). Попытки успешные, как по мне, но сам факт, что на протяжении 50 лет эта тема все еще является темой для научных статей – говорит о том, что в очевидности формулы Литтла иногда сомневаются даже профессиональные математики.

Так что несмотря на внешнюю простоту формулу Литтла полезно разобрать и уложить в голову ее доказательство, и иметь некоторую практику ее применения – иначе можно не разглядеть ее применения, или наоборот, применить там и так, где и как она не применима.

Следствие из формулы Литтла: для любой очереди в установившемся режиме среднее время в очереди равно средней длине очереди, делённой на темп поступления задач в очередь:

$$\bar{T_q}=\frac{\bar{N_q}}{\bar{\lambda}}$$

Это верно независимо от статистических свойств процессов прихода и ухода из очереди, и даже независимо от того, в каком порядке задачи из очереди забираются на обработку.

Результат немного не интуитивный: интуитивно кажется, что время в очереди это средняя длина очереди на среднее время обработки, $$\bar{T_q}=\bar{N_q}\bar{\tau}$$. Почему вместо среднего времени обработки оказывается средний интервал между поступлениями задач, $$1/\bar{\lambda}$$?

Интуиция сбоит потому, что средняя по времени длина очереди должна учитывать и те периоды, когда очередь пуста. Интуитивно пустая очередь это отсутствие очереди, но для математиков пустая очередь – это очередь длины 0 :)

Если очередь никогда не пуста, то интуитивный ответ правильный – но это бывает только когда система загружена на 100%, а значит $$\bar{\tau}=1/\bar{\lambda}$$. Если же система загружена менее, чем на 100%, то какую-то часть времени очередь будет пустой – учет этого времени и приводит к тому, что вместо $$\tau$$ в формуле оказывается $$1/\bar{\lambda}}$$

Продолжение: нагрузка и время отклика

Примечания

1. Конечно же для случайности вовсе не обязательно иметь много клиентов – даже один клиент может создать случайностей по макушку. Так что "теория массового обслуживания" не всегда именно про массовое обслуживание.

   Но и теория очередей тоже не всегда про очереди: например, Эрланг-B – самая первая из систем, рассматриваемых в любом курсе – никакой очереди не содержит. Naming is hard, you know.↩

2. Я говорю о "серверах", потому что мне, как программисту, так привычнее. В терминологии ТМО они называются "устройствами обслуживания", или "каналами обслуживания" – наследие времен телефона-телеграфа, ср. "одноканальная система"/"многоканальная система". При этом "устройство обслуживания" это нечто, что способно обрабатывать один запрос в один момент времени – т.е. физический сервер с 24 ядрами может представлять собой, в зависимости от степени параллелизации софта, до 24 устройств обслуживания.↩

3. Иногда на 4-й позиции в X/Y/m/k вместо размера буфера пишут размер буфера + количество серверов – т.е. общее количество задач, которое система может вместить, прежде чем приходящие задачи начнут отбрасываться.↩

4. Вот за то, пуассоновское распределение обозначается буквой M (от markovian или memoryless) – за это хочется кого-нибудь пнуть! Терминология ТМО вообще нередко вызывает мысли о физическом насилии.↩

5. Выделяют еще offered load – нагрузку, падающую на систему, и carried load – нагрузку, реально обрабатываемую системой. (Вроде бы на языке родных осин offered load это "интенсивность нагрузки", а carried load это "фактическая нагрузка", но я видел эти термины всего в одном источнике, поэтому в сомнениях.) Разница возникает если система допускает потери, т.е. часть входящего трафика может отбрасываться без обработки. Если система переваривает всю нагрузку, ничего не отбрасывая, то carried load = offered load↩

6. По названию понятно, что придумали это правило еще в то дикое и неполиткорректное время, когда и server, и computer чаще обозначали живого человека, чем машину. О конкретных датах мнения расходятся: иногда отсылают к самому Эрлангу (1913), но чаще к Halfin-Whitt (1981).↩

7. Если масштабировать количество серверов линейно с ростом нагрузки $$n \approx \alpha \lambda$$, то при $$0 < \alpha \leq 1$$ то система не сможет переваривать весь трафик (т.к. утилизация $$\frac{\lambda}{\alpha\lambda} \geq 1$$) – значит часть задач будет отбрасываться. Зато оставшиеся задачи будут загружать систему на 100% – поэтому этот режим масштабирования в литературе называется Efficiency-Driven (ED).

   При $$\alpha > 1$$ утилизация $$\frac{\lambda}{\alpha\lambda} < 1$$, т.е. система сможет переваривать весь трафик. Более того: качество обслуживания будет тем лучше, чем трафика больше, и поэтому в литературе этот режим называется Quality-Driven (QD). Цена за это – ресурсы системы будут систематически недоиспользоваться (КПД < 100%).

   Square root staffing находится ровно между двумя этими режимами, и убивает двух зайцев сразу: по мере масштабирования утилизация будет стремиться к 100%, но качество обслуживания не будет падать. Поэтому этот режим масштабирования называется Quality-Efficiency-Driven (QED)↩

8. Refining square root staffing by expanding Erlang C↩

9. На русском доказательство с цветной иллюстрацией есть в статье от яндекса (статья большая, надо искать "Как пользоваться теоремой Литтла"). Статья с более строгим доказательством: A Last Word on L = λW (насчет last – не верьте). Разбор от самого Литтла, вместе с историческими анекдотами, есть в главе 5 "Building intuition:…" (см литературу)↩

Литература

1. "The Essential Guide to Queueing Theory": поверхностное, но зато очень короткое (34 страницы) и простое введение в тему, с фокусом на практике. Guerrilla Capacity Planning Exercises: упражнения к курсу, который ведут авторы книги

2. "Building intuition: insights from basic operations management models and principles": книга довольно короткая (~200 страниц) и читается легко. Авторы пишут с позиции менеджмента/исследования операций, а не математики, и фокусируются на формировании интуиции – довольно редкая и ценная позиция. Математической строгости от книги ждать не стоит, но если что-то можно вывести достаточно наглядно – авторы это делают. К queueing theory относятся главы 1, 4 и 5, хотя остальные тоже заслуживают внимания

   (На амазоне ebook стоит 100$, но у книги есть doi.org/10.1007/978-0-387-73699-0, и вы поразитесь, когда узнаете, какая это полезная штука!)

3. MAP6264 - Queueing Theory: лекции профессора Купера – для более яростных. Я считаю его лекции очень хорошими по темпу и фокусу на понимании. Но это все-таки лекции по теории, и для людей, понимающих математику хотя бы на уровне 1-2 курса. То есть интегралы, бесконечные ряды, производящие функции – будут присутствовать, хоть и не чрезмерно. (Отдохнуть душой можно во время разбора симуляций на бейсике)

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