A programação é NP-Hard. Precisamos de respostas em milissegundos.

O problema parece simples. Não é.

De fora, uma página de reserva mostra as horas em que alguém está livre. Por baixo, um mês de slots reserváveis é a interseção de cada restrição abaixo.

• Horários de disponibilidade definidos no próprio fuso horário do host, muitas vezes vários por host

• Substituições de datas que trocam o horário recorrente em dias específicos

• Períodos de fora do escritório e horários de viagem que mudam um fuso horário a meio do mês

• Horários ocupados puxados de cada calendário externo ligado

• Limites de reserva e duração por dia, semana, mês e ano

• Antecedência mínima, buffers, intervalos de slot e offsets que definem até que horas de início são elegíveis

Isso é um host. Cada link de agendamento de equipa aumenta a dificuldade de forma diferente.

• Eventos coletivos exigem que todos os hosts estejam disponíveis ao mesmo tempo, por isso o conjunto completo de restrições de cada host tem de ser intersectado com o de todos os outros

• Eventos round robin exigem escolher que host fica com a reserva, sujeito a pesos, justiça e prioridades

• Eventos geridos aplicam um único modelo a uma equipa inteira, por isso uma única alteração de configuração remodela o conjunto de restrições de cada membro ao mesmo tempo

• O routing reduz dinamicamente o grupo de hosts, por quem vai reservar, antes de qualquer disponibilidade ser calculada

Cada restrição, por si só, é fácil. A combinação não é. Encontrar a melhor hora para uma reunião de grupo sob restrições individuais de disponibilidade é um problema NP-hard bem estudado.

Sê preciso quanto ao local onde está a dificuldade. Enumerar os slots livres de um host é matemática intervalar polinomial. O que é NP-hard é o que nos pedem para otimizar em cima disso, como a melhor hora comum num grupo ou a atribuição mais justa de reservas ao longo de um horizonte de reservas futuras. A arquitetura mantém as duas coisas separadas. A enumeração continua linear, e a otimização nunca é autorizada a tornar-se numa pesquisa.

NP-hard significa que não se conhece nenhum algoritmo em tempo polinomial e, a menos que P seja igual a NP, nenhum existe. Não é “ainda não o otimizámos”. Não é “precisamos de hardware melhor”. A pesquisa exaustiva cresce exponencialmente. Parece instantânea para uma equipa de 5 pessoas e demora muitos segundos para uma organização com 3.000 membros. Os maiores clientes pagam primeiro por um algoritmo mau.

As restrições do SaaS em tempo real

O mundo em lote resolve esta mesma classe de problema com um orçamento adequado. O agendamento de tripulações de companhias aéreas recebe horas de tempo de solver em clusters dedicados, e nenhum voo embarca enquanto o otimizador corre. Uma página de reserva recebe algumas centenas de milissegundos, e o prazo vem da pessoa que está a olhar para um spinner, não da nossa infraestrutura.

A saída óbvia é pré-calcular a disponibilidade num job em background e servi-la a partir de uma tabela. Os inputs não ficam quietos para isso. Os horários ocupados mudam sempre que o calendário de alguém muda, cada nova reserva consome um slot e pode preencher um limite, e a questão é moldada por quem vai reservar através do seu fuso horário, da duração escolhida, da janela que está a ver e dos hosts que o routing escolheu para ele. Pré-calcular todas as combinações é a sua própria explosão combinatória, e qualquer resposta pré-calculada fica desatualizada no momento em que uma reunião cai no calendário de um host. Disponibilidade desatualizada é pior do que disponibilidade lenta, porque oferece horários que já estão ocupados. Por isso calculamos os slots no momento do pedido, e as caches à frente desse cálculo são de curta duração por design.

Corremos isto no Fluid Compute da Vercel porque torna fácil escalar a aplicação. A capacidade acompanha o tráfego sem precisarmos de provisionar nada, as instâncias são de longa duração e reutilizadas em vez de criadas por pedido, os cold starts desaparecem quase por completo (pre-warming, cache de bytecode), os pedidos partilham uma instância, e waitUntil empurra o trabalho não crítico para depois da resposta. O faturamento é dominado por CPU ativa. Esperar por uma API de calendário é quase grátis, e gastar CPU numa pesquisa combinatória é exatamente aquilo por que pagamos.

Greedy por design

Nunca fazemos uma pesquisa exaustiva do espaço. Em cada ponto de decisão fazemos a escolha localmente melhor com a informação que temos, comprometemo-nos e seguimos em frente. Sem olhar em frente. Sem backtracking.

No mundo SaaS, greedy tem uma conotação negativa e pode soar como a opção ingénua. Mas para alguns problemas greedy é, de forma demonstrável, o melhor que podes fazer. Para set cover, um problema NP-hard clássico da mesma família do agendamento de grupo, greedy atinge uma taxa de aproximação logarítmica, e nenhum algoritmo em tempo polinomial pode fazer melhor, a menos que P seja igual a NP.

A atribuição round robin de hosts é o exemplo mais claro. Atribuir “corretamente” significaria otimizar sobre todas as atribuições futuras possíveis, a pesquisa exponencial que nos recusamos a executar. Em vez disso, o conjunto viável são os hosts disponíveis na hora pedida, e a seleção é feita por três filtros de ordenação:

pool = hostsAvailableAt(requestedTime)
if (weightedDistribution) pool = largestShortfall(pool) // fairness
pool = highestPriority(pool)
return leastRecentlyBooked(pool)                        // tie-break

A justiça compara as reservas reais de cada host no intervalo recente com uma quota-alvo ponderada e mantém os hosts mais atrasados (o peso mais alto desempata). Concretamente:

3 hosts, equal weights, 12 bookings this interval
target: 4 each
actual: A=6  B=4  C=2
shortfall: A=-2  B=0  C=+2  ->  C gets the booking

A ordem dos filtros é uma decisão de produto. A justiça corre antes da prioridade e a prioridade antes da recência, e trocar dois filtros dá a mesma reserva a um host diferente. Seja como for, a decisão são algumas passagens lineares, quer o grupo tenha 5 hosts ou 5.000.

Eis o que nos custa “recusamo-nos a executar essa pesquisa”. Um evento round robin com 3.000 hosts fica atrás de routing. Uma pessoa que vai reservar responde às perguntas de routing e o grupo reduz-se para 40 hosts qualificados. Um host reservado nunca é removido do grupo, apenas perde prioridade (se toda a gente estiver fora do escritório, o host que acabou de receber uma reserva recebe também a próxima), por isso cada reserva tem independentemente 40 possíveis atribuídos.

40 hosts, próximas 25 reservas

40²⁵ ≈ 10⁴⁰ possíveis atribuições. A mil milhões de verificações por segundo, essa pesquisa corre durante 3,6 × 10²³ anos, cerca de 26 biliões de vezes a idade do universo.

40 hosts, próximas 50 reservas 40⁵⁰ ≈ 10⁸⁰ possíveis atribuições. Isso é, aproximadamente, o número de átomos no universo observável.

A cascata greedy. Três passagens lineares por 40 hosts. Cerca de 100 comparações, em muito menos de um milissegundo.

E isto depois de o routing já ter descartado 2.960 hosts. As mesmas garantias de justiça, com quase quarenta ordens de grandeza de diferença no custo.

Nenhuma decisão isolada tem de ser perfeita, porque o sistema auto-corrige. Se sobrecarregares um host hoje, a sua falta diminui, por isso a justiça desprioriza-o amanhã. As correções seguem o mesmo critério. Um host que entra a meio do intervalo recebe crédito pela média de reservas por host antes de entrar, e um host que volta de fora do escritório recebe crédito pela sua parte das reservas feitas enquanto esteve ausente. A matemática da falta vê uma contagem ajustada. Sem histórico recalculado, sem passagem de reequilíbrio.

A geração de slots é greedy no mesmo espírito. Normaliza cada restrição num único eixo temporal absoluto, avança uma vez, emite cada hora de início que sobrevive e nunca volta atrás. Até a definição de otimização de slots do scheduling link, que decide onde a grelha começa dentro de cada janela livre, é uma linha de aritmética durante a mesma passagem, não uma comparação de layouts.

A troca é real, e o caso extremo é fácil de construir. Dá a um host uma janela de disponibilidade estreita que se sobrepõe à de toda a gente, deixa o greedy dar-lhe a primeira reserva dentro dela, e bloqueaste o único slot que uma reserva mais tarde, e mais restrita, podia usar. A pesquisa exaustiva teria visto isso a chegar. O greedy não olha em frente. Sabemos que estes casos existem e temos de estar bem com lançar isto porque temos milissegundos. A matemática da falta equilibra as coisas ao longo do tempo.

Como é que o linear realmente se parece

“Processamos restrições de forma linear” é fácil de dizer. Na prática, o movimento é sempre o mesmo. Converte tudo em intervalos num único eixo temporal absoluto, ordena uma vez, faz o sweep.

As restrições tornam-se intervalos antes de qualquer coisa lhes tocar. Uma regra semanal não é avaliada por cada slot candidato. É expandida uma vez, num único ciclo pelos dias da janela pedida, para intervalos UTC:

rule: Mon-Fri, 09:00-17:00, Europe/Berlin

Mon ██████ 07:00Z-15:00Z
Tue ██████ 07:00Z-15:00Z
Wed ██████ 07:00Z-15:00Z
Thu ██████ 07:00Z-15:00Z
Fri ██████ 07:00Z-15:00Z
Sat (none)
Sun (none)

É nesse ciclo que os horários de viagem mudam o fuso horário a meio do mês e a mudança para horário de verão altera um offset, por isso o trabalho independente do dia é retirado dele. A conversão de fuso horário domina o ciclo, e corre uma vez por dia por regra, não uma vez por slot.

Os eventos coletivos são um merge de dois ponteiros, não um produto cartesiano. Trinta hosts precisam das horas em que os trinta estão livres. Comparar cada intervalo com cada intervalo é quadrático duas vezes. Em vez disso, os intervalos de cada host são ordenados por hora de início e fundidos numa lista em execução de “disponibilidade comum”:

common: 09:00-13:00, 15:00-18:00
host B: 11:00-16:00
result: 11:00-13:00, 15:00-16:00

Um ponteiro percorre a lista comum, outro percorre a lista do próximo host, e avançamos sempre o intervalo que termina primeiro. O núcleo da implementação real é exatamente este pequeno bloco.

while (commonIndex < common.length && userIndex < userRanges.length) {
  const a = common[commonIndex];
  const b = userRanges[userIndex];
  const start = Math.max(a.startValue, b.startValue);
  const end = Math.min(a.endValue, b.endValue);
  if (start < end) intersected.push({ start, end });
  // advance whichever range ends first
  if (a.endValue <= b.endValue) commonIndex++;
  else userIndex++;
}

Cada host custa uma passagem linear, e no momento em que a lista comum fica vazia paramos. Se os hosts um a sete não partilharem tempo nenhum, os hosts oito a trinta não conseguem criar nenhum.

Os horários ocupados são subtraídos numa única passagem ordenada. Reservas, eventos de calendários externos e períodos de fora do escritório entram todos numa única lista de exclusão, ordenada uma vez por hora de início. Cada intervalo de disponibilidade percorre-a por ordem, mantendo os intervalos vazios:

available: 09:00-17:00
busy:      10:00-11:00, 13:00-14:30
result:    09:00-10:00, 11:00-13:00, 14:30-17:00

for (const busy of sortedBusyTimes) {
  if (busy.start >= sourceEnd) break;     // everything after is irrelevant
  if (busy.end <= currentStart) continue; // already behind us
  if (busy.start > currentStart) {
    result.push({ start: currentStart, end: busy.start }); // keep the gap
  }
  currentStart = busy.end; // jump past the busy block
}
if (currentStart < sourceEnd) {
  result.push({ start: currentStart, end: sourceEnd }); // keep the tail gap
}

Como as exclusões estão ordenadas, tudo o que fica atrás do break nunca é examinado.

Os limites de reserva tornam-se tempo ocupado sintético. “5 reservas por dia” podia ser verificado contra cada slot candidato, a um custo de slots × limites × reservas. Em vez disso, quando a contagem atinge o limite, o período inteiro torna-se um único intervalo ocupado e segue na mesma passagem de subtração:

limit: 5 per day
Sep 14 reaches 5 bookings
-> emit busy interval: Sep 14 00:00-24:00
-> subtracted like any calendar event

A verificação do limite corre uma vez por período, e o ciclo dos slots nunca fica a saber que existem limites.

Nenhum destes passos é, individualmente, brilhante. Um problema NP-hard dentro de um orçamento de milissegundos não se resolve com um algoritmo genial. Resolve-se recusando, em cada passo, deixar que qualquer cálculo dependa do produto de dois números grandes.

Tudo à volta do algoritmo também tem limites

Um algoritmo perfeito alimentado por uma query lenta continua a ser uma página de reserva lenta, e é a camada de dados que primeiro sofre à escala enterprise.

As leituras são agrupadas e depois indexadas em memória. A forma ingénua é um ciclo sobre hosts com três queries lá dentro. Trinta hosts significam 90 idas e voltas ao Postgres antes de sequer ser calculado um intervalo, invisível para uma equipa de 5 pessoas e um incidente de produção para 3.000. O pipeline de slots vai buscar tudo de antemão em vez disso:

per host (N+1)

┌─ host 1 ─▶ query bookings
├─ host 2 ─▶ query bookings
├─ host 3 ─▶ query bookings
│ ...
└─ host N ─▶ query bookings

batched

┌─ ONE query: bookings, all hosts
├─ ONE query: OOO days, all hosts
├─ batched queries: limits, all hosts
└─ group into Map<userId, rows>
then a pure in-memory pass per host

As reservas e os dias fora do escritório carregam em paralelo sob um único Promise.all, e os limites seguem numa segunda ronda em lote. Os resultados são agrupados uma vez em lookups Map<userId, rows>, e a partir daí a matemática da disponibilidade não toca em nenhuma base de dados. A função por host é tipada para exigir os dados pré-carregados, para que ninguém possa reintroduzir discretamente uma query por utilizador sem que o compilador se queixe.

Os calendários externos têm uma cache com regras estritas. Uma única ida e volta ao provider ultrapassa de longe todo o cálculo de intervalos, por isso a cache é construída à volta de três regras:

miss:  fetch the full 90-day horizon in one provider call, cache it
many calendars miss at once: one batched provider call covers all
error: cache nothing

Um único miss paga todas as leituras subsequentes em qualquer ponto do horizonte. E uma chamada falhada ao provider nunca é posta em cache, porque guardar um erro como “livre para todo o horizonte” ofereceria silenciosamente slots em cima de reuniões reais. Uma indisponibilidade custa uma nova tentativa, nunca uma resposta errada.

O tratamento de datas é código de caminho crítico. A aritmética com fuso horário num ciclo por slot domina tudo o resto, por isso a conversão acontece uma vez na fronteira e os ciclos internos comparam valores simples de milissegundos UTC.

Os orçamentos de tempo são testados, não assumidos. Os testes unitários provam que cada algoritmo termina dentro da restrição de tempo que temos à escala enterprise, e não apenas que devolve a resposta certa, por isso uma regressão de complexidade falha no CI em vez de falhar em produção.

Onde somos honestos sobre ainda não lá estarmos

Tudo o que está acima é a disciplina, não um resultado acabado. Eis a diferença, medida no meu próprio evento de 15 minutos contra a API de produção enquanto escrevia este artigo:

slot computation: tens of ms
warm-cache response: 30-75 ms
cold request: ~600 ms (a 200-300 ms Google free/busy call plus lookups and compute)
20-person team page: ~3 s

O cálculo está dentro do orçamento. A página inteira só está dentro do orçamento quando a cache à frente das chamadas ao provider faz o seu trabalho. As equipas estão mais atrasadas, e por mais do que uma razão. Corremos as chamadas Google para todos os hosts em paralelo, por isso o custo externo mantém-se aproximadamente estável enquanto o lado computacional cresce com a equipa. A base de dados acrescenta o seu próprio arrasto. A disponibilidade da equipa puxa a configuração do link, as reservas, os limites e as linhas de fora do escritório para cada host de algumas tabelas com milhões de registos, e algumas dessas queries ainda são lentas.

Round robin é onde estamos a atacar primeiro a diferença da equipa, porque tem uma propriedade que o problema geral não tem. Um evento coletivo precisa de cada host livre, mas uma reserva round robin precisa exatamente de um. A página de reserva não precisa de saber quem está disponível em cada slot, apenas se alguém está. Por isso estamos a construir uma cache de nível superior que guarda, para um mês de slots, a contagem de hosts disponíveis calculada uma vez. Cada reserva decrementa as contagens que afeta, e o recálculo completo só corre quando a contagem de um slot fica suficientemente baixa para que possa realmente ficar sem hosts. A maioria dos slots nunca chega a isso. A pergunta cara, que host fica com a reserva, continua a ser respondida greedy no momento da reserva. A pergunta barata, se alguém está livre, torna-se uma leitura de contador.

Cada funcionalidade de reserva é uma decisão algorítmica

Cada funcionalidade de reserva que lançamos tem de responder a uma pergunta que a maioria dos produtos SaaS nunca faz. Isto explode a pesquisa? Uma funcionalidade que possa ser expressa como outro filtro de ordenação na cascata greedy é quase grátis em qualquer escala. Uma que nos obrigue a comparar combinações é redesenhada até deixar de o fazer.

Greedy às vezes escolhe uma opção pior do que uma pesquisa exaustiva escolheria, e isso será sempre verdade. Aceitamo-lo, limitamo-lo e corrigimo-lo ao longo do tempo, porque a resposta exaustiva só chega depois de quem vai reservar ter desistido de esperar. A troca já funciona para páginas de reserva individuais. Torná-la mais rápida para uma organização com 3.000 membros é o trabalho que estamos a fazer agora.