Случайные процессы
Теория очередей
Цели урока
- Вывести стационарное распределение M/M/1 и основные показатели производительности
- Применить формулу Поллачека-Хинчина для M/G/1 с произвольным обслуживанием
- Использовать закон Литтла для анализа любой стабильной системы
- Анализировать сети очередей через теорему Джексона
Предварительные знания
- Пуассоновские процессы
- Теория возобновления
- Цепи Маркова
Нагрузка сервера 90% - это звучит нормально. Но M/M/1 говорит: при rho = 0.9 среднее число запросов в очереди - 8.1. При rho = 0.5 - 0.5. В 16 раз больше при росте нагрузки вдвое. Теория очередей - это математика неожиданных катастроф.
- AWS: оптимизация SLA серверных пулов через M/M/1 и закон Литтла
- LLM inference: M/G/1 с тяжёлыми хвостами объясняет P99 задержки
- Netflix CDN: анализ через сети Джексона
- Kubernetes: автоскейлинг на основе rho и закона Литтла
От телефонии к облакам
Агнер Эрланг в 1909 году решил задачу датской телефонной компании: сколько линий нужно для обслуживания N абонентов? Формула Эрланга-C до сих пор используется в call-центрах. Феликс Поллачек (1930) и Александр Хинчин (1932) независимо вывели P-K формулу для M/G/1. Джон Литтл доказал свой универсальный закон в 1961 году - элегантным вероятностным аргументом без сложных вычислений. Джексон открыл product-form для сетей в 1957 году.
Модель M/M/1 и формула Литтла
AWS управляет 1.5 миллиона серверов. Каждый запрос - это заявка в очереди. Нагрузка rho = 0.9 кажется безопасной: 90% утилизация. Но L = rho/(1-rho) = 9. Девять запросов ждут там, где при rho = 0.5 ждало бы одно. Нелинейность убивает.
Расчёт SLA для API-сервиса
Применение M/M/1 к инженерным задачам
API-сервис принимает 800 RPS (lambda = 800), обрабатывает со средним временем 1 мс (mu = 1000). Нагрузка rho = 0.8. Среднее время ответа W = 1/(1000 - 800) = 5 мс. Добавление 20% нагрузки (rho = 0.96) увеличивает W до 25 мс. В 5 раз - при росте нагрузки на 20%. Это нелинейность очереди в действии.
Закон Литтла применим к любой устойчивой системе - от M/M/1 до Kubernetes кластера. Если известны lambda и L, W = L/lambda вычисляется мгновенно без знания деталей распределений.
Что выражает закон Литтла L = lambda * W?
Закон Литтла L = lambda * W - фундаментальный результат теории очередей. Применим к любой устойчивой системе. Доказательство использует только закон больших чисел.
Модель M/G/1 и формула Поллачека-Хинчина
Реальные сервисы - не M/M/1. Время обработки запроса к LLM API распределено тяжелохвосто: большинство - быстро, редкие - очень медленно. Это M/G/1 с высоким коэффициентом вариации. И задержки взлетают - даже при той же средней нагрузке.
| Модель | C_S^2 | L_q (при rho=0.8) | W_q / E[S] |
|---|---|---|---|
| M/D/1 (детерминированное) | 0 | 1.60 | 2.0 |
| M/M/1 (экспоненциальное) | 1 | 3.20 | 4.0 |
| M/G/1 (логнорм. sigma=1) | ~1.7 | ~4.3 | ~5.4 |
| M/G/1 (Парето, alpha=2.5) | ~6.7 | ~11.7 | ~14.6 |
Тяжёлые хвосты в распределении времени обслуживания катастрофически увеличивают задержки. LLM inference с P99 = 30 сек при P50 = 0.5 сек имеет C_S^2 >> 1 - и длина очереди может быть в 10 раз больше M/M/1 при той же нагрузке.
В M/G/1 при том же rho = 0.8 и E[S] = 1, но C_S^2 = 4 (вместо 1 у M/M/1). Как изменится L_q?
P-K формула: L_q = rho^2 * (1 + C_S^2) / (2*(1-rho)). При C_S^2 = 4 и rho = 0.8: L_q = 0.64 * 5 / 0.4 = 8, против 3.2 у M/M/1. Рост в 2.5 раза.
Сети очередей и теорема Джексона
Микросервисная архитектура - это сеть очередей. Запрос проходит через auth -> api-gateway -> database -> cache. Каждый сервис - это очередь. Теорема Джексона 1957 года утверждает невероятное: при определённых условиях сеть распадается на независимые M/M/1 очереди.
Netflix использует теорему Джексона для анализа своей CDN-инфраструктуры: edge nodes, origin servers, encoding pipelines. Каждый уровень - узел сети Джексона. Стационарное распределение вычисляется аналитически - не симуляцией.
Теорема Джексона работает только при пуассоновских прибытиях и экспоненциальных временах обслуживания. Нарушение этих условий требует приближённых методов: decomposition, heavy-traffic approximations (диффузные приближения).
Теорема Джексона: стационарное распределение сети - произведение маргинальных. Что это означает для инженера?
Product-form теоремы Джексона означает факторизацию стационарного распределения. Инженерный смысл: каждый узел можно анализировать независимо как M/M/1 с эффективной нагрузкой lambda_j.
Связи с другими разделами
Теория очередей связывает вероятностный анализ, оптимизацию и проектирование систем
- Облачные системы — Связанная тема
- Теория возобновления — Связанная тема
- Пуассоновские процессы — Связанная тема
- Диффузные приближения — Связанная тема
Итоги
- M/M/1: L = rho/(1-rho) растёт нелинейно - при rho = 0.9 очередь в 9 раз длиннее, чем при rho = 0.5
- Закон Литтла L = lambda * W - универсален для любой стабильной системы
- M/G/1 P-K формула: высокий C_S^2 пропорционально увеличивает задержки
- Сети Джексона: product-form распределение позволяет анализировать сложные архитектуры
Вопросы для размышления
- Почему закон Литтла справедлив для любых распределений, а P-K формула зависит от E[S^2]?
- Как изменится анализ M/G/1, если заявки приходят пакетами (batch arrivals)?
- Почему теорема Джексона перестаёт работать при неэкспоненциальном обслуживании?