Teoria das filas: o que é e por que a latência dispara

A teoria das filas (em inglês, queueing theory) é a matemática da espera: a partir do ritmo em que o trabalho chega, de quanto cada tarefa demora e de quantos servidores existem, ela prevê quanto tempo as tarefas esperam e quanto a fila cresce. Para software, o resultado mais útil é que o tempo de resposta cresce devagar com carga moderada e depois de forma brusca quando um servidor se aproxima de 100% de ocupação. No modelo mais simples, um servidor ocupado 90% do tempo responde em média dez vezes mais devagar que um ocioso.

Os números abaixo são aritmética a partir de fórmulas padrão, conferidos com um script, sem nenhum teste por trás. As fontes foram conferidas em 1º de novembro de 2026.

São médias para a fila M/M/1: um servidor, chegadas de Poisson e tempos de atendimento exponenciais.

O que é teoria das filas?

É o ramo da probabilidade que modela trabalho que chega, espera e é atendido. Uma fila é descrita pelas chegadas, pelos tempos de atendimento, pelo número de servidores e pela disciplina de fila, ou seja, a ordem em que as tarefas em espera são atendidas.

O livro Urban Operations Research, de Larson e Odoni, um texto aberto do MIT, cita caixas de banco, caixas de supermercado e praças de pedágio como casos clássicos. Um servidor web cabe no mesmo esquema: as requisições chegam, threads ou núcleos as atendem e o resto espera numa fila.

De onde vem a teoria das filas?

Da central telefônica, onde A. K. Erlang chegou aos primeiros resultados para a Companhia Telefônica de Copenhague.

Segundo a biografia no MacTutor, o artigo de Erlang de 1909 mostrou que chamadas feitas ao acaso seguem a distribuição de Poisson, e sua fórmula de 1917 para perdas e tempo de espera logo passou a ser usada por companhias telefônicas de muitos países. O artigo de David Kendall de 1953, Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain, introduziu a notação usada até hoje, como registra o relato da obra dele escrito por Geoffrey Grimmett. A prova de L = λW de Little e os resultados de Kingman sobre tráfego intenso vieram em 1961.

O que significa a notação de Kendall, como M/M/1?

Ela nomeia uma fila em três partes, A/S/c: a distribuição dos intervalos entre chegadas, a dos tempos de atendimento e o número de servidores. M/M/1 significa chegadas aleatórias, tempos de atendimento exponenciais e um servidor.

M vem de memoryless, sem memória (chegadas de Poisson ou tempos exponenciais), D de determinístico e G de general, ou seja, qualquer distribuição: M/D/1 é um servidor com tempo de atendimento constante.

Como o tempo de resposta cresce com a utilização?

Numa fila M/M/1, o tempo médio no sistema é W = 1/(μ − λ), que é igual a S/(1 − ρ). Quando a utilização ρ se aproxima de 1, W cresce sem limite.

lambda = arrival rate        mu = service rate (1 / S)
rho    = lambda / mu         (utilization, must stay below 1)
W      = 1 / (mu - lambda)   = S / (1 - rho)

Larson e Odoni deduzem isso para uma central de atendimento com uma só telefonista e mostram que não há estado estacionário com ρ ≥ 1: a fila não para de crescer. A mesma fonte mostra que o tempo no sistema segue uma distribuição exponencial, então cada percentil cresce pelo mesmo fator 1/(1 − ρ), e o p95 fica em torno de três vezes a média: 600 ms na linha 0,9 acima.

Por que a latência faz um joelho antes de a CPU chegar a 100%?

Porque uma requisição espera sempre que encontra o servidor ocupado, e isso acontece com mais frequência à medida que a utilização sobe. Com as premissas do M/M/1, o tempo de resposta já dobrou a 50% de utilização.

O recurso que satura também pode ser um pool de conexões, um lock do banco de dados ou um event loop de uma só thread, e o mais carregado define a curva. Esse joelho precoce explica por que a utilização alvo fica bem abaixo de 100%. Faça a conta de trás para frente a partir do seu orçamento de latência: com S = 20 ms e uma média alvo de 100 ms, a tabela permite cerca de 80%, e um alvo de 60 ms cerca de 67%, antes que os picos levem a parte deles.

O painel Capacity da LoadFocus (página em inglês) agrupa um teste concluído pelo número de usuários virtuais ativos e informa o último nível que aguentou antes de a taxa de erros passar de 1% ou de o p95 passar do dobro do melhor nível, desde que nenhum nível mais alto tenha se recuperado. Ele precisa de um teste com um único gerador de carga que suba por pelo menos três degraus de carga, com o mais alto pelo menos o dobro do mais baixo. Pela conta acima, se o nível mais leve deixou o gargalo quase ocioso, a duplicação dispara logo acima de 50% de utilização; se o nível mais leve já o carregava a ρ0, ela dispara mais tarde, acima de (1 + ρ0)/2 no M/M/1.

Por que a variabilidade importa tanto quanto a utilização?

Filas nascem do acaso: chegadas em rajadas e tarefas lentas de vez em quando. Com tráfego intenso, o tempo de espera cresce com a variabilidade de ambas, multiplicada por um termo ρ/(1 − ρ).

O artigo de Kingman de 1961, The single server queue in heavy traffic, mostra que, quando a intensidade de tráfego de um servidor único se aproxima de 1, a fila fica longa e o tempo de espera é aproximadamente exponencial. Notas de aula da TU Eindhoven e do Technion dão uma aproximação para a média (o Technion a chama de aproximação de Allen-Cunneen; ela também é amplamente conhecida como fórmula de Kingman):

Wq ≈ rho / (1 - rho) × (ca² + cs²) / 2 × S
ca, cs = coefficient of variation (std dev / mean)
         of arrival gaps and of service times

Wq é a espera antes de o atendimento começar, e ca, cs são os coeficientes de variação. Tempos exponenciais têm c² = 1, o que devolve a espera do M/M/1 de 9S a 90% de utilização. Um tempo de atendimento constante corta a espera pela metade, para 4,5S; com cs² = 4, o que uma mistura de acertos de cache e chamadas lentas ao banco de dados pode produzir, ela sobe para 22,5S. Tráfego sintético regular varia menos que o de produção, então um teste costuma mostrar menos fila do que os picos reais.

Como mais servidores (M/M/c) ajudam?

Vários servidores que compartilham uma fila absorvem rajadas aleatórias muito melhor que os mesmos servidores com uma fila cada, então cada servidor pode trabalhar mais ocupado com a mesma espera.

Pelas fórmulas M/M/m de Larson e Odoni, com cada servidor 90% ocupado, W é 10S com um servidor, 5,3S com dois compartilhando a fila e 3,0S com quatro. Quatro instâncias atrás de um balanceador que escolhe uma livre se comportam como o último caso; quatro que recebem cada uma um quarto aleatório do tráfego, como filas M/M/1 separadas a 10S.

Onde entra a lei de Little?

A lei de Little, L = λW, liga o número médio de requisições num sistema à taxa de chegada e ao tempo que elas passam lá dentro, quaisquer que sejam as distribuições. A teoria das filas dá W, e a lei de Little o transforma em L.

Na linha 0,9, 45 requisições por segundo com W = 200 ms significam em média 9 requisições dentro do sistema. Nosso artigo sobre a lei de Little usa a mesma lei para dimensionar e conferir testes de carga.

Onde esses modelos deixam de valer em teste de carga?

Eles supõem um fluxo aberto de chegadas independentes e um estado estacionário. Um teste com número fixo de usuários virtuais é um sistema fechado, em que as chegadas desaceleram quando as respostas desaceleram.

• Testes fechados. Com N usuários virtuais há no máximo N requisições no sistema, então a taxa de requisições cai onde uma fila aberta cresceria, e o tempo de pensamento a reduz ainda mais. Nosso artigo sobre o modelo de carga aberto vs fechado explica por que isso esconde a saturação.
• A LoadFocus roda scripts k6, mas os cenários arrival-rate rodam lá com um número fixo de usuários, como avisa o validador de scripts dela. Leia esses testes como fechados: depois do joelho, espere uma taxa de requisições estável e tempos de resposta subindo.
• Estado estacionário. Aquecimento, caches e autoscaling mudam a taxa de atendimento durante o teste, então compare níveis mantidos por tempo suficiente para se estabilizar.

FAQ

Escreve-se queueing theory ou queuing theory? As duas grafias em inglês estão corretas e nomeiam o mesmo campo. O artigo de Kingman de 1961 escreve “queueing time”, enquanto a prova de Little do mesmo ano traz “Queuing Formula” no título.

A teoria das filas exige chegadas de Poisson? Só para os resultados exatos do M/M/1. Aproximações G/G/1 como a fórmula de Kingman usam a média e a variabilidade dos intervalos entre chegadas e dos tempos de atendimento, e a lei de Little não supõe nada sobre as distribuições.

Leituras relacionadas

• Lei de Little em teste de carga: dimensionar e conferir
• Modelo de carga aberto vs fechado: qual usar e quando
• Vazão vs latência: como se relacionam sob carga
• Latência de cauda: o que é e como medir
• Tempo de pensamento em teste de carga: como definir

As afirmações técnicas deste artigo não foram revisadas de forma independente.