Teoria das Filas

Visão geral

A teoria das filas (queueing theory) estuda sistemas em que “jobs” (trabalhos: requisições, tarefas, pacotes, tokens) chegam de forma estocástica (stochastically), esperam em uma fila (queue) se os recursos estiverem ocupados e então recebem serviço (service) de um ou mais servidores. Ela fornece ferramentas matemáticas para prever:

Utilização (utilization) (quão ocupados os servidores estão)
Tempo médio de espera e tempo médio de resposta
Comprimento médio da fila
Probabilidade de esperar (ou de descartar)
Latência de cauda (tail latency) (por exemplo, tempos de resposta p95/p99)

Na infraestrutura moderna de IA—especialmente no serving de ML/LLM (ML/LLM serving)—essas previsões informam diretamente:

Planejamento de capacidade (capacity planning) (Quantas GPUs/réplicas precisamos para um SLO?)
Políticas de autoescalonamento (autoscaling) (Quando devemos adicionar/remover capacidade?)
Escalonamento (scheduling) e priorização (prioritization) (Como protegemos tráfego interativo contra jobs em lote?)
Decisões de agrupamento em lotes (batching) (Como o micro-agrupamento em lotes troca latência por vazão?)
Projeto do sistema em pipelines distribuídos (tokenização → modelo → pós-processamento → filtros de segurança)

A teoria das filas complementa a perspectiva de engenharia em Noções Básicas de Sistemas Distribuídos: ela dá intuição quantitativa, muitas vezes surpreendentemente precisa, sobre por que a latência “explode” perto da saturação e por que a variância importa tanto quanto a vazão média (throughput).

Conceitos centrais e métricas

Um sistema básico de filas tem:

Processo de chegada (arrival process): jobs chegam ao longo do tempo (aleatoriamente).
Processo de serviço (service process): cada job requer uma quantidade aleatória de tempo de serviço.
Servidores (servers): uma ou muitas unidades de serviço idênticas (ou heterogêneas).
Disciplina de fila (queue discipline): como os jobs em espera são selecionados (FCFS, prioridade etc.).
Capacidade (capacity): fila infinita, buffer finito ou sistema de “perda” (descartar/bloquear).

Taxas e variáveis-chave:

Taxa de chegada (arrival rate): (\lambda) jobs/segundo
Taxa de serviço (service rate) (por servidor): (\mu) jobs/segundo, então o tempo médio de serviço (E[S]=1/\mu)
Número de servidores: (k)
Utilização (intensidade de tráfego):
[ \rho = \frac{\lambda}{k\mu} = \frac{\lambda E[S]}{k} ] Intuitivamente, (\rho) é a fração do tempo em que os servidores estão ocupados.

Métricas comuns de desempenho:

Tempo de espera na fila: (W_q)
Tempo total de resposta (espera + serviço): (W = W_q + S)
Número no sistema (fila + em serviço): (L)
Número na fila: (L_q)

Lei de Little (Little’s Law) (a “ponte” universal)

Um dos resultados mais amplamente úteis é a Lei de Little (Little’s Law):

[ L = \lambda W,\quad L_q = \lambda W_q ]

Ela vale sob condições muito gerais (sistema estável, médias de longo prazo) e é frequentemente usada para validar (sanity-check) medições de sistemas em produção.

Implicação prática: se você mede concorrência média (L) e vazão (\lambda), você obtém a latência média (W) “de graça”.

Estabilidade e o “joelho” da latência

Um sistema é tipicamente estável apenas se:

[ \rho < 1 ]

À medida que (\rho \to 1), as filas crescem rapidamente e a latência explode. Por isso, sistemas de serving em produção frequentemente miram utilizações bem abaixo de 100% (por exemplo, 40–70%), especialmente para SLOs estritos de latência de cauda.

Notação de Kendall (Kendall’s notation): nomeando modelos de filas

Modelos de filas são frequentemente descritos pela notação de Kendall (Kendall’s notation):

[ A/S/k ]

(A): distribuição dos tempos entre chegadas (inter-arrival times)
(S): distribuição dos tempos de serviço
(k): número de servidores

Símbolos comuns:

M: “Markoviano (Markovian)” (sem memória), significando tempos entre chegadas ou de serviço exponenciais (exponential) (equivalentemente, chegadas de Poisson).
G: distribuição geral (arbitrária)
D: determinística (constante)

Exemplos:

M/M/1: chegadas de Poisson, serviço exponencial, 1 servidor
M/M/k: chegadas de Poisson, serviço exponencial, k servidores
M/G/1: chegadas de Poisson, tempo de serviço geral, 1 servidor
M/G/k: chegadas de Poisson, serviço geral, k servidores (importante, mais difícil)
G/G/1: totalmente geral (frequentemente aproximado)

Em serving de ML/LLM, as chegadas podem ocorrer em rajadas (bursty) (não perfeitamente Poisson) e os tempos de serviço frequentemente têm alta variância (high-variance) (comprimentos de prompt, comprimentos de geração, acertos/erros de cache), então o raciocínio com M/G/k e G/G/k frequentemente fica mais próximo do que o M/M/k puro.

A fila M/M/1 (servidor único, suposições exponenciais)

M/M/1 é o “hello world” da teoria das filas: simples, em forma fechada, e altamente instrutivo.

Suposições:

As chegadas são de Poisson com taxa (\lambda).
Os tempos de serviço são exponenciais com taxa (\mu).
Servidor único, FCFS (first-come-first-served), buffer infinito.

Resultados-chave (para (\rho=\lambda/\mu<1)):

Número médio no sistema: [ L = \frac{\rho}{1-\rho} ]
Tempo médio de resposta: [ W = \frac{1}{\mu-\lambda} ]
Tempo médio de espera na fila: [ W_q = W - \frac{1}{\mu} = \frac{\rho}{\mu-\lambda} ]

Intuição de latência de cauda a partir de M/M/1

Mesmo neste modelo “bonzinho”, os tempos de espera têm uma cauda pesada em relação à média. Uma lição crucial: pequenos aumentos na utilização perto de 1 podem causar grandes regressões na latência de cauda.

Exemplo prático: suponha que um worker único de GPU consiga completar (\mu = 20) requisições/s em média.

Em (\lambda=10): (W=1/(20-10)=0.1) s
Em (\lambda=18): (W=1/(20-18)=0.5) s
Em (\lambda=19): (W=1/(20-19)=1.0) s

Um aumento de 5% na carga perto da saturação pode dobrar a latência.

A fila M/M/k (k servidores) e Erlang C

Para k servidores idênticos em paralelo (por exemplo, k réplicas de modelo atrás de um balanceador de carga (load balancer)), M/M/k fornece uma ferramenta clássica de planejamento de capacidade.

Defina:

(a = \lambda/\mu) = carga oferecida (offered load) em “unidades de servidor”
(\rho = \lambda/(k\mu) = a/k)

Uma quantidade central é Erlang C, a probabilidade de um job que chega ter que esperar (todos os servidores ocupados). A fórmula é:

[ P(\text{wait}) = \frac{\frac{a^k}{k!}\frac{k}{k-a}}{\sum_{n=0}^{k-1}\frac{a^n}{n!} + \frac{a^k}{k!}\frac{k}{k-a}} \quad \text{(valid for } a<k\text{)} ]

Então:

[ W_q = \frac{P(\text{wait})}{k\mu - \lambda}, \quad W = W_q + \frac{1}{\mu} ]

Exemplo prático de planejamento de capacidade (réplicas para um SLO)

Suponha que um endpoint (endpoint) receba (\lambda=120) req/s. Cada réplica atende (\mu=15) req/s em média.

Carga oferecida (a=\lambda/\mu=8) “servidores de trabalho”.
Se (k=8), utilização (\rho=1): instável.
Se (k=10), (\rho=0.8): estável, mas a latência de cauda ainda pode ser alta sob variabilidade.
Se (k=12), (\rho\approx 0.67): frequentemente com caudas muito melhores.

No serving real de LLM, os tempos de serviço não são exponenciais, mas esse exercício frequentemente dá uma estimativa de primeira ordem para “quantas réplicas precisamos só para não derreter?”

Um pequeno snippet em Python para calcular a latência média de M/M/k

import math

def erlang_c(lam, mu, k):
    a = lam / mu
    if a >= k:
        return 1.0
    denom = sum((a**n) / math.factorial(n) for n in range(k))
    numer = (a**k) / math.factorial(k) * (k / (k - a))
    return numer / (denom + numer)

def mmk_mean_W(lam, mu, k):
    ec = erlang_c(lam, mu, k)
    Wq = ec / (k * mu - lam)
    W = Wq + 1/mu
    return W, Wq, ec

lam, mu = 120.0, 15.0
for k in [10, 12, 14]:
    W, Wq, ec = mmk_mean_W(lam, mu, k)
    print(k, "W=", W, "Wq=", Wq, "P(wait)=", ec)

Isso é útil para “cálculo de guardanapo (napkin math)”, mas você deve validar com traços (traces) reais e simulação (simulation) para cargas de trabalho de LLM.

M/G/1: por que a variância do tempo de serviço importa (Pollaczek–Khinchine)

No serving de LLM, os tempos de serviço raramente são sem memória (memoryless):

Comprimento do prompt (prompt) e comprimento da geração variam muito
Reuso de cache KV (KV-cache) cria tempos de serviço bimodais
Chamadas de ferramenta (tool calls) ou retrieval podem adicionar caudas longas
Kernels de GPU (GPU kernels) têm comportamento não linear com o tamanho do lote (batch size)

A fila M/G/1 mantém chegadas de Poisson, mas permite uma distribuição arbitrária de serviço.

Um resultado fundamental é a fórmula de Pollaczek–Khinchine (Pollaczek–Khinchine) (P–K):

[ W_q = \frac{\lambda E[S^2]}{2(1-\rho)} \quad \text{where } \rho=\lambda E[S] ]

Como (E[S^2] = \mathrm{Var}(S) + (E[S])^2), maior variância pode aumentar dramaticamente o tempo de espera—mesmo com o mesmo tempo médio de serviço.

Principal lição para sistemas de ML: otimizar apenas latência/vazão médias não é suficiente. Reduzir a variância (variance) (por exemplo, controlando tamanho de lote, separando requisições longas/curtas, cacheando, moldando cargas) pode ser tão impactante quanto.

Exemplo: mesma média de serviço, variância diferente

Dois serviços têm o mesmo tempo médio de serviço (E[S]=50) ms. Um é muito consistente; o outro é altamente variável.

Em (\lambda = 10) req/s, (\rho=\lambda E[S] = 0.5).

Se (E[S^2]) dobra por causa da variância, (W_q) aproximadamente dobra.
À medida que (\rho) se aproxima de 1, a explosão é ainda pior devido ao fator (1/(1-\rho)).

Este é um dos motivos pelos quais “prompts de cauda longa” podem desestabilizar um endpoint que, de outra forma, estaria saudável.

G/G/1 e a aproximação de Kingman (útil na prática)

Chegadas reais frequentemente não são de Poisson:

Picos de tráfego (lançamentos de produto, retries, efeito manada (thundering herd))
Rajadas correlacionadas (clientes “falantes” (chatty clients), agentes sincronizados)
Limites de taxa (rate limits) ou agrupamento em lotes a montante

Uma aproximação amplamente usada para G/G/1 é a fórmula de Kingman (Kingman’s formula):

[ W_q \approx \frac{\rho}{1-\rho}\cdot \frac{c_a^2 + c_s^2}{2}\cdot E[S] ]

Onde:

(c_a^2 = \frac{\mathrm{Var}(A)}{(E[A])^2}) é o coeficiente de variação ao quadrado (SCV (squared coefficient of variation)) dos tempos entre chegadas
(c_s^2 = \frac{\mathrm{Var}(S)}{(E[S])^2}) é o SCV dos tempos de serviço

Interpretação:

Chegadas mais em rajadas (maior (c_a^2)) aumentam a espera.
Serviço mais variável (maior (c_s^2)) aumenta a espera.
Alta utilização amplia ambos.

Essa aproximação é especialmente útil quando você tem dados de traços e pode estimar SCVs diretamente.

Disciplinas de escalonamento e por que elas importam para LLMs

Modelos de filas frequentemente assumem FCFS, mas sistemas reais usam políticas mais ricas:

FCFS (justo, simples, frequentemente ruim para caudas com tamanhos de job variáveis)

Se as requisições têm tempos de serviço muito variados, FCFS pode produzir latência de cauda ruim porque um job longo pode bloquear muitos curtos.

Filas de prioridade (proteger tráfego interativo)

Comum em plataformas de ML: requisições “online” recebem maior prioridade do que inferência em lote ou avaliações offline.

Melhora p95/p99 para a classe de alta prioridade
Pode causar starvation do trabalho de baixa prioridade, a menos que você adicione aging ou cotas

SRPT / menor-job-primeiro (shortest-job-first) (minimiza o tempo médio de resposta)

Se você consegue prever o tamanho do job (por exemplo, tokens esperados a gerar), Tempo Restante de Processamento Mais Curto (SRPT, Shortest Remaining Processing Time) pode reduzir dramaticamente a latência média.

No serving de LLM, você pode aproximar o “tamanho do job” por:

tokens do prompt + tokens esperados de saída
max_tokens (limite superior)
comportamento histórico por locatário (tenant)

Ressalva: SRPT pode ser injusto com requisições longas; muitos sistemas o combinam com restrições de fairness (justiça).

Alguns sistemas se comportam mais como compartilhamento do que como FCFS estrito (por exemplo, kernels de GPU concorrentes, tarefas de CPU multiplexadas). Modelos de filas como M/G/1-PS às vezes podem combinar melhor com o comportamento observado, mas a execução em GPU frequentemente é complexa e dependente do hardware.

Agrupamento em lotes como um problema de filas (e por que isso muda a matemática)

O agrupamento em lotes é central para a eficiência de GPU. Em inferência de LLM, agrupar em lotes aumenta a vazão ao amortizar overheads e melhorar a utilização do dispositivo—mas introduz espera para formar um lote.

Agora, dois atrasos importam:

Atraso de enfileiramento (queueing delay) esperando por um servidor
Atraso de formação de lote (batch formation delay) esperando por requisições compatíveis suficientes (mesmo modelo, shapes similares etc.)

Isso cria um ciclo de feedback:

Lotes maiores → mais tempo para formar um lote (mais espera)
Lotes maiores → serviço por requisição mais rápido (maior vazão)
Mas às vezes lotes maiores → serviço por requisição mais lento por pressão de memória ou overhead de padding

Exemplo de micro-agrupamento em lotes (micro-batching) (intuição)

Suponha:

Sem lotes: 1 requisição leva 40 ms na GPU
Com tamanho de lote 8: o lote leva 120 ms no total, ou 15 ms por requisição “em média”

Se o tráfego é baixo (digamos 20 req/s), esperar para coletar 8 requisições pode adicionar 100+ ms, eliminando os ganhos. Se o tráfego é alto (200 req/s), os lotes enchem rapidamente e a latência melhora.

Orientação prática: o agrupamento em lotes é mais efetivo quando as chegadas são altas o suficiente para que o tempo de formação do lote permaneça pequeno em relação à economia de computação. Muitos sistemas em produção usam agrupamento em lotes dinâmico (dynamic batching) com um timeout máximo de espera para formação do lote para limitar a latência de cauda.

Visão de teoria das filas sobre agrupamento em lotes

O agrupamento em lotes pode ser modelado como:

Filas de **serviço em lote (bulk service) ** (o servidor atende até B jobs de uma vez)
Sistemas com tempos de setup (setup times) (lançamento de kernel / compilação de grafo)
Tempos de serviço dependentes de estado (o serviço depende do tamanho do lote)

A análise exata pode ficar complexa rapidamente, então as equipes frequentemente combinam:

aproximações simples (tratar (\mu) efetivo como uma função do tamanho do lote)
simulação com curvas de serviço (service curves) medidas

Latência de cauda: percentis, não apenas médias

SLOs voltados ao usuário geralmente são baseados em percentis (p95/p99). A teoria das filas explica por que as caudas são sensíveis:

Perto da saturação, pequenas rajadas produzem filas longas.
Alta variância no tempo de serviço amplifica a espera.
Retries podem criar feedback positivo (mais carga → mais timeouts → mais retries → mais carga).

Alavancas práticas para reduzir a latência de cauda:

Manter a utilização abaixo de um alvo (frequentemente surpreendentemente baixo para p99 estrito).
Reduzir a variância do tempo de serviço (separar requisições longas/curtas; limitar max_tokens; cache).
Usar prioridades e isolamento (filas separadas para interativo vs lote).
Aplicar controle de admissão (admission control) (retornar “tente mais tarde” em vez de crescimento infinito de fila).
Usar requisições redundantes (hedged requests) / replicação com cuidado (pode ajudar nas caudas, mas também pode aumentar a carga).

A teoria das filas fornece o modelo mental: p99 é dominado por “eventos raros de congestionamento”, não pelo tempo de serviço típico.

De filas únicas a sistemas distribuídos: redes de filas

O serving real de ML frequentemente é um pipeline (pipeline):

API gateway / auth
Tokenização
Scheduler / agrupamento em lotes
Inferência em GPU (possivelmente multiestágio: prefill + decode)
Filtros de segurança / pós-processamento
Logging / métricas

Cada etapa pode ser aproximada como uma fila; a latência ponta a ponta é a soma dos atrasos entre as etapas. Em alguns casos, redes de filas têm soluções elegantes:

Redes de Jackson (Jackson networks) modelam redes abertas de nós do tipo M/M/k com distribuições estacionárias em forma de produto sob certas suposições.

Na prática, muitas suposições são violadas (serviço não exponencial, agrupamento em lotes, correlações), mas o princípio do gargalo (bottleneck principle) continua extremamente útil:

A etapa com a maior utilização efetiva tende a dominar a latência de cauda.
Melhorar não-gargalos gera pouco ganho ponta a ponta.

Esse tipo de raciocínio combina bem com instrumentação e tracing em Programação para ML.

Como a teoria das filas orienta decisões de serving de ML/LLM

Planejamento de capacidade e metas de utilização

Uma lição recorrente:

A vazão pode parecer boa em (\rho=0.9)
A latência de cauda frequentemente se torna inaceitável muito antes disso

Para endpoints interativos de LLM, equipes frequentemente planejam para uma utilização menor para absorver rajadas e prompts longos.

Fluxo de trabalho:

Estimar a distribuição da taxa de chegadas (média e pico).
Estimar a distribuição dos tempos de serviço (média, variância, dependência em tokens).
Usar aproximações M/M/k ou M/G/k para escolher a contagem de réplicas.
Validar com testes de carga (load tests) e simulação usando traços reais.

Escalonamento e isolamento por classes

Endpoints multi-tenant (multilocação) se beneficiam de:

Filas separadas por locatário (tenant) ou por classe (interativo vs lote)
Enfileiramento justo ponderado (weighted fair queuing) ou prioridades estritas com salvaguardas
Limites explícitos por locatário para evitar noisy neighbors (vizinhos ruidosos)

A teoria das filas ajuda você a raciocinar sobre como um locatário de alta variância pode inflar o tempo de espera de todos sob FCFS.

Políticas de agrupamento em lotes

O agrupamento em lotes dinâmico tem “knobs” ajustáveis:

tamanho máximo de lote
tempo máximo de espera para formar o lote
restrições de compatibilidade (baldes por comprimento de sequência)

Trade-off de filas:

Aumentar o tamanho do lote → aumenta a vazão, mas também aumenta a espera e, às vezes, a variância.
Apertar o timeout de espera → protege a latência de cauda, mas reduz a vazão.

Um bom padrão operacional é tratar o agrupamento em lotes como um problema de controle (control problem): ajustar parâmetros para manter um percentil-alvo de latência.

Autoescalonamento e laços de controle

O autoescalonamento é “consciente de filas” mesmo que não diga isso:

Se o tamanho da fila cresce, você adiciona réplicas.
Mas o atraso do laço de controle (control loops) pode causar oscilações.

Modelos de filas ajudam você a:

definir limiares seguros de utilização
interpretar o tamanho da fila como “demanda oculta (hidden demand)”
entender por que escalar baseado apenas em utilização de CPU/GPU pode não capturar sobrecarga (overload) (filas podem crescer mesmo quando a utilização está limitada)

Armadilhas comuns ao aplicar teoria das filas

Assumir chegadas de Poisson quando o tráfego é em rajadas ou correlacionado (comum para agentes de LLM e retries).
Ignorar a variância do tempo de serviço (frequentemente o principal motor das caudas).
Não estacionariedade (non-stationarity): (\lambda) muda ao longo do tempo; o sistema pode nunca atingir regime estacionário (steady state).
Serviço dependente de estado: o agrupamento em lotes faz a taxa de serviço depender do tamanho da fila.
Ignorar contrapressão a montante (upstream backpressure): filas interagem; aplicar backpressure pode deslocar o congestionamento em vez de eliminá-lo.
Confundir médias com garantias: a latência média pode parecer boa enquanto o p99 é terrível.

A melhor prática é usar a teoria das filas como uma lente de modelagem, e então validar com medição e simulação.

Abordagem prática: combinando teoria, medição e simulação

Instrumentar (instrument):
- timestamps de chegada
- timestamps de início/fim de serviço
- características da requisição (tokens in/out, locatário, modelo)
Estimar (estimate):
- (\lambda) em diferentes janelas (média/pico, grau de rajadas)
- média e variância do tempo de serviço, SCVs (c_a^2, c_s^2)
Modelar (model):
- começar com M/M/k para dimensionamento grosseiro
- usar M/G/1 ou aproximações no estilo de Kingman para considerar variância
Simular (simulate) com workloads orientados por traços ou sintéticos (especialmente para agrupamento em lotes/escalonamento)
Iterar (iterate) usando métricas guiadas por SLO (p95/p99), não apenas médias

A simulação frequentemente é a forma mais rápida de avaliar políticas complexas (agrupamento em lotes dinâmico, escalonamento por prioridades) onde não há formas fechadas.

Resumo

A teoria das filas fornece uma estrutura fundamentada para raciocinar sobre sistemas com chegadas e tempos de serviço aleatórios—exatamente as condições enfrentadas por stacks de serving de ML e LLM em produção. As ideias centrais:

Utilização (\rho) controla se as filas permanecem limitadas, e a latência cresce rapidamente conforme (\rho \to 1).
Lei de Little conecta vazão, concorrência e latência.
Variância importa: modelos como M/G/1 mostram como a variabilidade do tempo de serviço impulsiona espera e latência de cauda.
Efeitos de múltiplos servidores (M/M/k, Erlang C) orientam o dimensionamento de réplicas e a probabilidade de esperar.
Escalonamento e agrupamento em lotes remodelam trade-offs de latência/vazão; a teoria das filas ajuda a prever e controlar esses efeitos.

Usada com cuidado—em conjunto com medição e validação—a teoria das filas é uma das ferramentas matemáticas mais práticas para construir sistemas de IA confiáveis e custo-efetivos.