La pianificazione è NP-hard. Ci servono risposte in millisecondi.

Il problema sembra semplice. Non lo è.

Da fuori, una pagina di prenotazione mostra gli orari in cui qualcuno è libero. Sotto la superficie, un mese di slot prenotabili è l'intersezione di ogni vincolo qui sotto.

• Orari di disponibilità definiti nella timezone del host, spesso diversi per ogni host

• Sovrascritture di data che sostituiscono la pianificazione ricorrente in giorni specifici

• Periodi fuori ufficio e pianificazioni di viaggio che spostano una timezone a metà mese

• Orari occupati presi da ogni calendario esterno collegato

• Limiti di prenotazione e durata per giorno, settimana, mese e anno

• Preavviso minimo, buffer, intervalli degli slot e offset che determinano quali orari di inizio siano persino idonei

Questo è un solo host. Ogni scheduling link di team alza la posta in gioco in modo diverso.

• Gli eventi collettivi richiedono che tutti gli host siano disponibili contemporaneamente, quindi l'intero set di vincoli di ogni host va intersecato con quello di tutti gli altri

• Gli eventi round robin richiedono di scegliere quale host riceve la prenotazione, in base a pesi, equità e priorità

• Gli eventi gestiti applicano un singolo template a tutto il team, quindi una sola modifica di configurazione rimodella il set di vincoli per ogni membro in una volta sola

• Il routing restringe dinamicamente il pool di host, per chi prenota, prima che venga calcolata qualunque disponibilità

Ogni vincolo preso da solo è semplice. La combinazione no. Trovare un orario ottimale per un gruppo sotto vincoli di disponibilità individuali è un problema NP-hard ben studiato.

Sii preciso su dove si trova la difficoltà. Enumerare gli slot liberi di un host è matematica degli intervalli in tempo polinomiale. Ciò che è NP-hard è ciò che ci viene chiesto di ottimizzare sopra, come il miglior orario comune per un gruppo o l'assegnazione più equa delle prenotazioni su un orizzonte di prenotazioni future. L'architettura tiene separate le due cose. L'enumerazione resta lineare, e l'ottimizzazione non è mai autorizzata a diventare una ricerca.

NP-hard significa che non è noto alcun algoritmo in tempo polinomiale, e a meno che P non sia uguale a NP, non ne esiste nessuno. Non “non l'abbiamo ancora ottimizzato”. Non “ci serve hardware migliore”. La ricerca esaustiva cresce in modo esponenziale. Sembra istantanea per un team di 5 persone e richiede molti secondi per un'organizzazione da 3.000 membri. I clienti più grandi pagano prima per un algoritmo pessimo.

I vincoli del SaaS in tempo reale

Il mondo batch risolve questa stessa classe di problema con un budget adeguato. La pianificazione degli equipaggi delle compagnie aeree ottiene ore di tempo sui solver su cluster dedicati, e nessun volo parte mentre l'ottimizzatore gira. Una pagina di prenotazione ha a disposizione un paio di centinaia di millisecondi, e la scadenza arriva dal booker che guarda uno spinner, non dalla nostra infrastruttura.

L'evasione più ovvia è precomputare la disponibilità in un job in background e servirla da una tabella. Gli input però non stanno fermi. Gli orari occupati cambiano ogni volta che cambia il calendario di qualcuno, ogni nuova prenotazione consuma uno slot e può saturare un limite, e la domanda è modellata per chi prenota dalla sua timezone, dalla durata scelta, dalla finestra che sta consultando e dagli host selezionati dal routing. Precomputare ogni combinazione è un'esplosione combinatoria a sé stante, e qualsiasi risposta precomputata diventa vecchia nel momento in cui una riunione atterra sul calendario di un host. Una disponibilità vecchia è peggio di una lenta, perché offre orari già occupati. Quindi calcoliamo gli slot al momento della richiesta, e le cache davanti a questo calcolo sono volutamente di breve durata.

Eseguiamo tutto su Fluid Compute di Vercel perché rende facile scalare l'app. La capacità segue il traffico senza che dobbiamo provisioning nulla, le istanze sono di lunga durata e riutilizzate invece di essere create a ogni richiesta, i cold start sono quasi spariti (pre-warming, caching del bytecode), le richieste condividono un'istanza, e waitUntil sposta il lavoro non critico oltre la risposta. La fatturazione è dominata dalla CPU attiva. Aspettare su una API del calendario costa quasi niente, e bruciare CPU su una ricerca combinatoria è esattamente ciò per cui paghiamo.

Greedy per design

Non cerchiamo mai in modo esaustivo lo spazio delle soluzioni. A ogni punto decisionale facciamo la scelta localmente migliore con le informazioni che abbiamo, ci impegniamo e andiamo avanti. Niente lookahead. Niente backtracking.

Nel mondo SaaS, greedy ha una connotazione negativa e può sembrare l'opzione ingenua. Ma per alcuni problemi greedy è dimostrabilmente il meglio che puoi fare. Per il set cover, un classico problema NP-hard della stessa famiglia della pianificazione di gruppo, greedy ottiene un rapporto di approssimazione logaritmico, e nessun algoritmo in tempo polinomiale può fare meglio a meno che P non sia uguale a NP.

L'assegnazione round robin degli host è l'esempio più chiaro. Assegnare “correttamente” vorrebbe dire ottimizzare su ogni possibile assegnazione futura, la ricerca esponenziale che rifiutiamo di eseguire. Invece, l'insieme fattibile è quello degli host disponibili all'orario richiesto, e la selezione è filtrata da tre ordinamenti:

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

L'equità confronta le prenotazioni effettive di ogni host nell'intervallo recente con una quota target ponderata e tiene gli host più indietro (il peso più alto rompe i pari merito). In pratica:

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

L'ordine dei filtri è una decisione di prodotto. L'equità gira prima della priorità e la priorità prima della recenza, e scambiare due filtri dà la stessa prenotazione a un host diverso. In ogni caso la decisione richiede pochi scan lineari, sia che il pool abbia 5 host sia che ne abbia 5.000.

Ecco cosa costa il nostro “rifiutiamo di eseguire quella ricerca”. Un evento round robin con 3.000 host passa da un routing. Chi prenota risponde alle domande di routing e il pool si riduce a 40 host qualificati. Un host già prenotato non viene mai rimosso dal pool, solo de-prioritizzato (se tutti gli altri sono fuori ufficio, l'host che ha appena ricevuto una prenotazione riceve anche la successiva), quindi ogni prenotazione ha indipendentemente 40 possibili assegnatari.

40 host, prossime 25 prenotazioni

40²⁵ ≈ 10⁴⁰ possibili assegnazioni. A un miliardo di controlli al secondo, questa ricerca richiede 3,6 × 10²³ anni, circa 26 trilioni di volte l'età dell'universo.

40 host, prossime 50 prenotazioni 40⁵⁰ ≈ 10⁸⁰ possibili assegnazioni. È più o meno il numero di atomi nell'universo osservabile.

La cascata greedy. Tre passaggi lineari su 40 host. Circa 100 confronti, in ben meno di un millisecondo.

Questo dopo che il routing ha già scartato 2.960 host. Stesse garanzie di equità, quasi quaranta ordini di grandezza di differenza nel costo.

Nessuna singola decisione deve essere perfetta, perché il sistema si corregge da solo. Se sovraccarichi un host oggi, il suo deficit si riduce, quindi l'equità lo de-prioritizza domani. Le correzioni usano lo stesso criterio. Un host che entra a metà intervallo riceve come credito la media delle prenotazioni per host fatte prima del suo ingresso, e un host che torna fuori ufficio riceve come credito la sua quota delle prenotazioni prese mentre era assente. La matematica del deficit vede un conteggio regolato. Nessuna cronologia ricalcolata, nessun passaggio di ribilanciamento.

La generazione degli slot è greedy nello stesso spirito. Normalizza ogni vincolo su un unico asse temporale assoluto, avanza una volta sola, emetti ogni orario di inizio che sopravvive e non tornare indietro mai. Persino l'impostazione di ottimizzazione degli slot dello scheduling link, che decide dove inizia la griglia dentro ogni finestra libera, è una riga di aritmetica durante la stessa scansione, non un confronto di layout.

Il compromesso è reale, e il caso limite è facile da costruire. Dai a un host una finestra di disponibilità stretta che si sovrappone a quella di tutti gli altri, lascia che il greedy gli assegni la prima prenotazione al suo interno, e hai bloccato l'unico slot che una prenotazione successiva, più vincolata, avrebbe potuto usare. La ricerca esaustiva l'avrebbe previsto. Greedy non guarda avanti. Sappiamo che questi casi esistono e dobbiamo stare bene a rilasciare così perché abbiamo millisecondi. La matematica del deficit bilancia le cose nel tempo.

Come appare davvero il lineare

“Processiamo i vincoli in modo lineare” è facile da dire. In concreto, la mossa è sempre la stessa. Converti tutto in intervalli su un unico asse temporale assoluto, ordina una volta, fai uno sweep.

I vincoli diventano intervalli prima che qualcosa li tocchi. Una regola settimanale non viene valutata per ogni slot candidato. Viene espansa una sola volta, in un unico loop sui giorni della finestra richiesta, in intervalli 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)

È in quel loop che gli orari di viaggio spostano la timezone a metà mese e il passaggio all'ora legale modifica un offset, quindi il lavoro indipendente dal giorno viene spostato fuori da lì. La conversione di timezone domina il loop, e gira una volta al giorno per regola, non una volta per slot.

Gli eventi collettivi sono una merge a due puntatori, non un prodotto cartesiano. Trenta host devono avere gli orari in cui tutti e trenta sono liberi. Confrontare ogni intervallo con ogni intervallo è quadratico due volte. Invece, gli intervalli di ogni host sono ordinati per orario di inizio e fusi in una lista di “disponibilità comune” in aggiornamento:

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

Un puntatore percorre la lista comune, uno la lista del prossimo host, e avanziamo sempre l'intervallo che finisce per primo. Il cuore dell'implementazione reale è esattamente così piccolo.

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++;
}

Ogni host costa un passaggio lineare, e nel momento in cui la lista comune diventa vuota ci fermiamo. Se gli host da uno a sette non condividono alcun orario, gli host da otto a trenta non possono crearne nessuno.

Gli orari occupati vengono sottratti in un unico sweep ordinato. Prenotazioni, eventi di calendari esterni e periodi fuori ufficio finiscono tutti in una sola lista di esclusione, ordinata una volta per orario di inizio. Ogni intervallo di disponibilità la percorre in ordine, tenendo i gap:

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
}

Poiché le esclusioni sono ordinate, tutto ciò che sta dietro il break non viene mai esaminato.

I limiti di prenotazione diventano tempo occupato sintetico. “5 prenotazioni al giorno” potrebbe essere controllato contro ogni slot candidato, a un costo di slot × limiti × prenotazioni. Invece, quando il conteggio raggiunge il tetto, l'intero periodo diventa un unico intervallo occupato e segue lo stesso sweep di sottrazione:

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

Il controllo del limite gira una volta per periodo, e il loop degli slot non arriva mai a sapere che i limiti esistono.

Nessuno di questi passaggi è geniale preso singolarmente. Un problema NP-hard dentro un budget di un millisecondo non si risolve con un algoritmo brillante. Si risolve rifiutandosi, a ogni passaggio, di permettere che qualunque calcolo dipenda dal prodotto di due numeri grandi.

Anche tutto ciò che sta attorno all'algoritmo è limitato

Un algoritmo perfetto alimentato da una query lenta è comunque una pagina di prenotazione lenta, e il livello dati è il primo punto in cui la scala enterprise mostra i denti.

Le letture sono batchate, poi indicizzate in memoria. La forma ingenua è un loop sugli host con tre query dentro. Trenta host significano 90 round trip a Postgres prima che venga calcolato anche un solo intervallo, invisibile per un team di 5 persone e un incidente di produzione per 3.000. La pipeline degli slot recupera tutto in anticipo invece:

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

Le prenotazioni e i giorni fuori ufficio vengono caricate in parallelo sotto un unico Promise.all, e i limiti seguono in un secondo round batchato. I risultati vengono raggruppati una volta in lookup Map<userId, rows>, e da lì in poi la matematica della disponibilità non tocca più il database. La funzione per host è tipizzata per richiedere i dati prelevati prima, così nessuno può reintrodurre di nascosto una query per utente senza che il compilatore protesti.

I calendari esterni ottengono una cache con regole rigide. Un singolo round trip al provider supera di gran lunga l'intero calcolo degli intervalli, quindi la cache è costruita attorno a tre regole:

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

Un singolo miss paga per ogni lettura successiva in qualunque punto dell'orizzonte. E una chiamata fallita al provider non viene mai messa in cache, perché mettere in cache un errore come “libero per l'intero orizzonte” offrirebbe silenziosamente slot sopra riunioni reali. Un outage costa un retry, mai una risposta sbagliata.

La gestione delle date è codice hot path. L'aritmetica consapevole della timezone in un loop per slot domina tutto il resto, quindi la conversione avviene una volta al confine e i loop interni confrontano semplici valori UTC in millisecondi.

I budget di tempo si testano, non si presumono. Le suite di unit test dimostrano che ogni algoritmo finisce entro il vincolo di tempo che abbiamo su scala enterprise, non solo che restituisca la risposta giusta, così una regressione di complessità fallisce in CI invece che in produzione.

Dove siamo onesti sul fatto che non ci siamo ancora

Tutto quanto sopra è disciplina, non un risultato finito. Ecco il divario, misurato sul mio evento di 15 minuti contro la production API mentre scrivevo questo post:

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

Il calcolo rientra nel budget. L'intera pagina rientra nel budget solo quando la cache davanti alle chiamate al provider fa il suo lavoro. I team sono più indietro, e per più di un motivo. Eseguiamo le chiamate a Google per tutti gli host in parallelo, quindi il costo esterno resta più o meno piatto mentre il lato computazionale cresce con il team. Il database aggiunge il suo attrito. La disponibilità di team recupera la configurazione del link, le prenotazioni, i limiti e le righe fuori ufficio per ogni host da alcune tabelle che contengono milioni di record, e alcune di quelle query sono ancora lente.

Il round robin è il punto da cui stiamo attaccando per primo il divario di team, perché ha una proprietà che il problema generale non ha. Un evento collettivo ha bisogno che ogni host sia libero, ma una prenotazione round robin ha bisogno di esattamente uno. La pagina di prenotazione non deve sapere chi è disponibile a ogni slot, solo se qualcuno lo è. Quindi stiamo costruendo una cache di livello superiore che memorizza, per un mese di slot, il conteggio degli host disponibili calcolato una sola volta. Ogni prenotazione decrementa i conteggi che tocca, e il ricalcolo completo parte solo quando il conteggio di uno slot scende abbastanza da poter davvero restare senza host. La maggior parte degli slot non arriva mai lì. La domanda costosa, quale host prende la prenotazione, viene ancora risposta in modo greedy al momento della prenotazione. La domanda economica, se qualcuno è libero, diventa una lettura di contatore.

Ogni funzionalità di prenotazione è una decisione algoritmica

Ogni funzionalità di prenotazione che rilasciamo deve rispondere a una domanda che la maggior parte dei prodotti SaaS non si pone mai. Fa esplodere la ricerca? Una funzionalità che può essere espressa come un altro filtro di ordinamento nella cascata greedy è quasi gratuita a qualunque scala. Una che ci costringe a confrontare combinazioni viene ridisegnata finché non succede più.

Greedy a volte sceglie un'opzione peggiore di quella che avrebbe scelto una ricerca esaustiva, e sarà sempre così. Lo accettiamo, lo delimitiamo e lo correggiamo nel tempo, perché la risposta esaustiva arriva solo dopo che chi prenota ha smesso di aspettare. Il compromesso funziona già per le singole pagine di prenotazione. Renderlo più veloce per un'organizzazione da 3.000 membri è il lavoro che stiamo facendo adesso.