Случайные процессы
Теория массового обслуживания
Почему Uber, Netflix и Amazon планируют мощности серверов на уровне 70%, а не 95%? Почему снижение вариабельности запросов важнее увеличения производительности? Ответ - теория массового обслуживания: математика, которая стоит за проектированием каждой масштабируемой системы.
- **Site Reliability Engineering** - расчёт мощностей, планирование хранения, анализ latency через L=λW
- **Kubernetes/Auto-scaling** - когда добавлять поды? Модели очередей дают аналитические ответы
- **Логистика и здравоохранение** - скорая помощь, операционные, супермаркеты используют те же модели M/M/c и M/G/1
Предварительные знания
Очередь M/M/1
Стандартная задача: запросы поступают случайно, один сервер их обрабатывает. Как долго будет ждать клиент? Сколько запросов скопится в очереди? Модель M/M/1 - самая простая и фундаментальная: пуассоновский поток заявок (M - Markovian arrivals), экспоненциальное обслуживание (M - Markovian service), один сервер (1).
**M/M/1 очередь:** λ - интенсивность прихода, μ - интенсивность обслуживания, ρ = λ/μ < 1 (условие стабильности). **Стационарное распределение:** π_n = (1-ρ)·ρⁿ (геометрическое) **Ключевые формулы:** - L = ρ/(1-ρ) - среднее число в системе - Lq = ρ²/(1-ρ) - среднее в очереди - W = 1/(μ-λ) - среднее время в системе - Wq = λ/(μ(μ-λ)) - среднее время ожидания
**«Закон квадратичной загрузки»:** L = ρ/(1-ρ). При ρ = 0.5 → L = 1. При ρ = 0.9 → L = 9. При ρ = 0.99 → L = 99. Очередь нелинейно взрывается при приближении к 100% загрузке. Это объясняет, почему хорошо спроектированные системы работают при 70-80% загрузке, а не при 99%.
| Загрузка ρ | L (в системе) | Lq (в очереди) | W (сек, μ=10) |
|---|---|---|---|
| 0.5 | 1 | 0.5 | 0.2 |
| 0.7 | 2.33 | 1.63 | 0.33 |
| 0.8 | 4 | 3.2 | 0.5 |
| 0.9 | 9 | 8.1 | 1.0 |
| 0.95 | 19 | 18.05 | 2.0 |
Если сервер не перегружен (ρ < 1), очередь не образуется
Даже при низкой загрузке (ρ = 0.5) средняя длина очереди Lq = ρ²/(1-ρ) = 0.5 > 0. Случайность потока неизбежно создаёт очереди
Даже если в среднем λ < μ, возможны «пачки» запросов (bursts), которые временно перегружают систему. Очередь - плата за случайность. Только при ρ → 0 очередь практически исчезает
API сервер обрабатывает в среднем 100 req/s (μ=100), нагрузка 80 req/s (λ=80). Каково среднее время ответа?
Очередь M/G/1
В реальных системах время обработки не обязательно экспоненциально: HTTP-запросы имеют тяжёлый хвост, запросы к базе данных - разное время в зависимости от типа. Очередь **M/G/1** - пуассоновский приток, произвольное (General) распределение обслуживания, один сервер. Формула Поллачека-Хинчина показывает, что важны только первые два момента распределения обслуживания.
**Формула Поллачека-Хинчина (P-K formula):** Lq = ρ²/(1-ρ) + λ²·E[S²] / (2(1-ρ)) = ρ²/(1-ρ) · (1 + CV²_S) / 2 где ρ = λ·E[S], E[S] = 1/μ - среднее время обслуживания, CV_S = σ_S/E[S] - коэффициент вариации. При CV_S = 1 (экспоненциальное): Lq = ρ²/(1-ρ) - совпадает с M/M/1. При CV_S = 0 (детерминированное): Lq = ρ²/(2(1-ρ)) - в два раза меньше!
**Практический вывод:** Уменьшение вариабельности времени обслуживания (CV) снижает очередь, даже при той же нагрузке. Это обоснование для **batching** (группировки похожих запросов), **resource pooling** (объединение серверов), и равномерного распределения нагрузки. Тяжёлые хвосты обслуживания (редкие, но очень долгие запросы) катастрофически увеличивают очередь.
| Распределение S | CV_S | Lq / Lq^{M/M/1} | Пример |
|---|---|---|---|
| Детерминированное | 0 | 1/2 | Фиксированный timeout |
| Эрланга-2 | 1/√2 ≈ 0.71 | ~0.75 | Обработка в 2 фазы |
| Экспоненциальное | 1 | 1 | M/M/1 базовый случай |
| Гиперэкспоненциальное | >1 | >1 | Смесь быстрых и медленных |
| Pareto/тяжёлый хвост | >>1 | >>1 | HTTP с большими файлами |
Для очереди M/G/1 нужно знать полное распределение времени обслуживания
Формула Поллачека-Хинчина требует только E[S] и E[S²] (первые два момента). Полное распределение не нужно для вычисления L, Lq, W, Wq
Это удивительная «нечувствительность» очередей: детали распределения кроме первых двух моментов не влияют на среднее число в системе. Только CV (коэффициент вариации) имеет значение
Два сервера M/G/1 с ρ=0.7. У первого CV_S=1 (экспоненциальное), у второго CV_S=2 (тяжёлый хвост). Как соотносятся их средние времена ожидания?
Закон Литтла
Закон Литтла - самый мощный и универсальный результат теории массового обслуживания: **L = λ·W**. Среднее число клиентов в системе = интенсивность прихода × среднее время в системе. Никаких предположений о типе очереди, распределениях, числе серверов - только «входной поток» и «время в системе».
**Закон Литтла:** В стационарной системе: L = λ·W где: - L = среднее число клиентов в системе - λ = средняя интенсивность прихода - W = среднее время клиента в системе **Применяется к любой стабильной системе:** очереди, базы данных, HTTP-серверы, производственные линии, больницы. Не требует предположений о распределениях - только стационарность!
**Применение в SRE:** По метрикам дашборда - concurrency (число активных запросов = L) и throughput (λ) - можно вычислить среднее время ответа W = L/λ без явного измерения W. Если L = 50 запросов, λ = 100 req/s, то W = 0.5 с = 500 мс. Это работает для любой системы без знания её внутреннего устройства.
Джон Дитрих Литтл
Джон Дитрих Литтл доказал свой закон в 1961 году в статье «A Proof for the Queuing Formula L = λW». До Литтла этот результат использовался эмпирически, но строгого доказательства не было. Доказательство Литтла элегантно и минималистично - оно требует лишь стационарности и применимо к любой системе. Закон Литтла считается одним из наиболее практически полезных результатов операционных исследований.
Закон Литтла применим только к M/M/1 очереди
Закон Литтла L = λW - универсальный результат для ЛЮБОЙ стабильной системы с потоком: M/M/1, M/G/1, G/G/n, даже без марковской структуры
Доказательство Литтла использует только временные средние, а не предположения о распределениях. Закон применяется к больницам, заводам, серверам, магазинам - любой системе с приходами и временем обслуживания
В Kubernetes поде наблюдается 30 активных HTTP-запросов (L=30), пропускная способность 600 req/min. Каково среднее время ответа?
Сети Джексона
Реальные системы - это не одна очередь, а **сети** из множества узлов. Запрос к API попадает сначала в load balancer, затем к серверу приложений, затем к базе данных. **Теорема Джексона (1957)** - замечательный результат: в сети с пуассоновскими потоками и экспоненциальным обслуживанием каждый узел ведёт себя как независимая M/M/1 очередь!
**Теорема Джексона:** В открытой сети с J узлами, где: - Внешние прибытия: Poisson(γ_j) к узлу j - Обслуживание: Exp(μ_j) в узле j - Маршрутизация: с вероятностью p_{jk} из j в k Стационарное распределение: π(n₁,...,n_J) = ∏_j π_j^{(M/M/1)}(n_j) Где λ_j = γ_j + ∑_k λ_k·p_{kj} - «трафик уравнение».
**«Сюрприз» теоремы Джексона:** Несмотря на то что потоки между узлами НЕ являются пуассоновскими (после обслуживания в M/M/1 выходной поток пуассоновский, но это содержательный результат - теорема Берка), стационарное распределение сети совпадает с произведением независимых M/M/1 распределений. Это называется **продуктовая форма** (product form) и упрощает анализ сложных систем.
| Метрика | Формула | Использование |
|---|---|---|
| Трафик узла j | λ_j = γ_j + ∑_k λ_k p_{kj} | Уравнения трафика |
| Загрузка узла j | ρ_j = λ_j / μ_j | Узкое место (bottleneck) |
| Среднее в узле j | L_j = ρ_j/(1-ρ_j) | M/M/1 для каждого узла |
| Время в узле j | W_j = 1/(μ_j - λ_j) | Цепочка W_total = ∑W_j |
Теорема Джексона работает только для пуассоновского потока на каждом узле
Теорема Джексона утверждает, что система ведёт себя КАК БУДТО каждый узел имеет пуассоновский поток. Но входные потоки в узлы могут не быть пуассоновскими - это следствие (product form), а не предположение
Это и есть «сюрприз» Джексона: несмотря на то что потоки между узлами не пуассоновские (деление потока меняет его характер), стационарное распределение сохраняет продуктовую форму. Это глубокий результат, обусловленный симметрией задачи
В теореме Джексона стационарное распределение сети - это произведение M/M/1 распределений узлов. Что это означает практически?
Ключевые идеи
- **M/M/1** - базовая модель: ρ=λ/μ < 1, L = ρ/(1-ρ), W = 1/(μ-λ); нелинейный рост при ρ → 1
- **M/G/1 (Поллачек-Хинчин)** - зависит только от E[S] и E[S²]; уменьшение CV снижает очередь
- **Закон Литтла** - L = λW: универсальный, без предположений о распределениях; основа SRE метрик
- **Сети Джексона** - продуктовая форма: каждый узел - независимая M/M/1; основа проектирования микросервисов
Связанные темы
Теория очередей - прикладное приложение CTMC и пуассоновских процессов:
- Цепи Маркова с непрерывным временем — M/M/1 - это birth-death CTMC; Q-матрица, стационарное распределение, детальный баланс
- Пуассоновский процесс — M в M/M/1 означает пуассоновский поток заявок; свойство суперпозиции и истончения
- Stochastic в ML и Systems — Очереди в распределённых системах, GPU job scheduling, inference batching
Вопросы для размышления
- Система M/M/1 с ρ=0.8 vs M/D/1 (детерминированное обслуживание) с тем же ρ. Какую выбрать и почему?
- Закон Литтла: если снизить среднее время ответа W вдвое при том же λ, как изменится L? Как это влияет на ресурсы?
- Теорема Джексона требует экспоненциального обслуживания. Как проектировать системы с нормальным или тяжёлым хвостом?