Planowanie jest NP-trudne. Potrzebujemy odpowiedzi w milisekundach.

Problem wygląda prosto. Nie jest taki.

Z zewnątrz strona rezerwacji pokazuje godziny, kiedy ktoś jest wolny. Pod spodem jeden miesiąc dostępnych terminów to część wspólna wszystkich poniższych ograniczeń.

• Harmonogramy dostępności zdefiniowane we własnej strefie czasowej hosta, często kilka na jednego hosta

• Zastąpienia dat, które podmieniają cykliczny harmonogram w konkretnych dniach

• Okresy poza biurem i harmonogramy podróży, które przesuwają strefę czasową w połowie miesiąca

• Zajęte terminy pobierane z każdego podłączonego zewnętrznego kalendarza

• Limity rezerwacji i czasu trwania na dzień, tydzień, miesiąc i rok

• Minimalne wyprzedzenie, bufory, odstępy między slotami i przesunięcia, które decydują, które godziny rozpoczęcia w ogóle się kwalifikują

To tylko jeden host. Każdy link planowania zespołu podnosi stawkę inaczej.

• Wydarzenia zbiorowe wymagają, żeby wszyscy hostowie byli jednocześnie dostępni, więc cały zestaw ograniczeń każdego hosta trzeba przeciąć z każdym innym

• Wydarzenia round robin wymagają wybrania, który host dostaje rezerwację, z uwzględnieniem wag, sprawiedliwości i priorytetów

• Wydarzenia zarządzane nakładają jeden szablon na cały zespół, więc jedna zmiana konfiguracji od razu przekształca zestaw ograniczeń dla każdego członka

• Routing dynamicznie zawęża pulę hostów, dla każdego bookera, zanim w ogóle zostanie obliczona dostępność

Każde ograniczenie osobno jest proste. Razem już nie. Znalezienie optymalnego terminu spotkania dla grupy przy indywidualnych ograniczeniach dostępności to dobrze przebadany problem NP-trudny.

Trzeba precyzyjnie określić, gdzie leży trudność. Wyliczenie wolnych slotów jednego hosta to wielomianowa matematyka przedziałów. NP-trudne jest to, co mamy na tym wyżej optymalizować, na przykład najlepszy wspólny termin dla grupy albo najbardziej sprawiedliwy przydział rezerwacji w horyzoncie przyszłych rezerwacji. Architektura trzyma te dwa etapy osobno. Wyliczanie zostaje liniowe, a optymalizacja nigdy nie może stać się przeszukiwaniem.

NP-trudne oznacza, że nie jest znany algorytm wielomianowy w czasie, a jeśli P równa się NP, to żaden taki algorytm nie istnieje. Nie chodzi o „po prostu jeszcze tego nie zoptymalizowaliśmy”. Nie chodzi o „potrzebujemy lepszego sprzętu”. Pełne przeszukiwanie rośnie wykładniczo. Dla zespołu 5-osobowego wydaje się natychmiastowe, a dla organizacji z 3 000 członków trwa wiele sekund. Najwięksi klienci najpierw płacą za zły algorytm.

Ograniczenia SaaS czasu rzeczywistego

Świat wsadowy rozwiązuje ten sam rodzaj problemu z odpowiednim budżetem. Planowanie załóg linii lotniczych dostaje godziny czasu solvera na dedykowanych klastrach, a samoloty nie boardują się, gdy optymalizator działa. Strona rezerwacji dostaje kilkaset milisekund, a deadline bierze się z tego, że booker patrzy na spinner, a nie z naszej infrastruktury.

Najbardziej oczywiste wyjście to przeliczać dostępność z wyprzedzeniem w zadaniu w tle i serwować ją z tabeli. Tyle że dane nie stoją w miejscu. Zajęte terminy zmieniają się, kiedy zmienia się kalendarz kogokolwiek, każda nowa rezerwacja zużywa slot i może wypełnić limit, a pytanie jest kształtowane dla każdego bookera przez jego strefę czasową, wybraną długość spotkania, przeglądane okno i hostów wybranych przez routing. Przeliczenie wszystkich kombinacji to własna eksplozja kombinatoryczna, a każda wcześniej policzona odpowiedź robi się nieaktualna w momencie, gdy spotkanie ląduje w kalendarzu hosta. Nieaktualna dostępność jest gorsza niż wolna, bo pokazuje godziny, które już są zajęte. Dlatego liczymy sloty w momencie żądania, a cache przed tym obliczeniem z założenia żyją krótko.

Uruchamiamy to na Fluid Compute Vercel, bo dzięki temu łatwo skalować aplikację. Pojemność podąża za ruchem bez naszego ręcznego provisioningu, instancje są długowieczne i wielokrotnego użytku zamiast tworzyć się przy każdym żądaniu, cold starty są w dużej mierze wyeliminowane (pre-warming, cache bytecode), żądania współdzielą instancję, a waitUntil przesuwa niekrytyczną pracę poza odpowiedź. Rozliczenie jest zdominowane przez aktywne CPU. Czekanie na API kalendarza jest prawie darmowe, a palenie CPU na przeszukiwaniu kombinatorycznym to dokładnie to, za co płacimy.

Zachłanność z założenia

Nigdy nie przeszukujemy przestrzeni wyczerpująco. W każdym punkcie decyzji wybieramy lokalnie najlepszą opcję na podstawie danych, które mamy, zatwierdzamy ją i idziemy dalej. Bez patrzenia w przód. Bez cofania.

W świecie SaaS „zachłanny” ma negatywne skojarzenia i może brzmieć jak naiwna opcja. Ale dla niektórych problemów zachłanne podejście jest matematycznie najlepsze, jakie da się osiągnąć. Dla set cover, klasycznego problemu NP-trudnego z tej samej rodziny co planowanie grupowe, zachłanny algorytm osiąga logarytmiczny współczynnik aproksymacji, a żaden algorytm wielomianowy nie zrobi tego lepiej, chyba że P równa się NP.

Przydział hosta w round robin to najczytelniejszy przykład. Przydzielenie „poprawnie” oznaczałoby optymalizację po wszystkich możliwych przyszłych przydziałach, czyli wykładnicze przeszukiwanie, którego odmawiamy uruchamiania. Zamiast tego zbiorem dopuszczalnym są hostowie dostępni w żądanym czasie, a wybór przechodzi przez trzy filtry porządkujące:

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

Sprawiedliwość porównuje faktyczne rezerwacje każdego hosta w ostatnim okresie z ważonym celem i zostawia hostów najbardziej z tyłu (przy remisie wygrywa wyższa waga). Konkretnie:

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

Kolejność filtrów to decyzja produktowa. Sprawiedliwość działa przed priorytetem, a priorytet przed świeżością; zamiana dwóch filtrów daje tę samą rezerwację innemu hostowi. Tak czy inaczej decyzja to kilka liniowych przebiegów, niezależnie od tego, czy pula ma 5 hostów, czy 5 000.

Oto, ile kosztuje „odmawiamy uruchamiania tego przeszukiwania”. Wydarzenie round robin z 3 000 hostów stoi za routingiem. Booker odpowiada na pytania routingu, a pula zawęża się do 40 zakwalifikowanych hostów. Zarezerwowany host nigdy nie jest usuwany z puli, tylko dostaje niższy priorytet (jeśli wszyscy inni są poza biurem, host, który właśnie wziął rezerwację, dostaje też następną), więc każda rezerwacja osobno ma 40 możliwych przypisań.

40 hostów, następne 25 rezerwacji

40²⁵ ≈ 10⁴⁰ możliwych przypisań. Przy miliardzie sprawdzeń na sekundę takie przeszukiwanie trwa 3,6 × 10²³ lat, czyli około 26 bilionów razy dłużej niż wiek wszechświata.

40 hostów, następne 50 rezerwacji 40⁵⁰ ≈ 10⁸⁰ możliwych przypisań. To mniej więcej liczba atomów we wszechświecie obserwowalnym.

Zachłanny kaskadowy wybór. Trzy liniowe przebiegi po 40 hostach. Około 100 porównań, w znacznie mniej niż milisekundę.

To po tym, jak routing wcześniej odrzucił 2 960 hostów. Te same gwarancje sprawiedliwości, a koszt różni się o prawie czterdzieści rzędów wielkości.

Żadna pojedyncza decyzja nie musi być idealna, bo system sam się koryguje. Jeśli dziś przeciążysz hosta, jego deficyt się zmniejszy, więc jutro sprawiedliwość da mu niższy priorytet. Korekty jadą po tym samym kryterium. Host, który dołącza w połowie okresu, dostaje przypisanie średniej liczby rezerwacji na hosta sprzed dołączenia, a host wracający z out-of-office dostaje swój udział w rezerwacjach wziętych podczas nieobecności. Matematyka deficytu widzi skorygowaną liczbę. Bez przeliczania historii, bez etapu równoważenia.

Generowanie slotów jest zachłanne w tym samym duchu. Normalizujemy każde ograniczenie do jednej absolutnej osi czasu, przechodzimy po niej raz, emitujemy każdy ocalały czas rozpoczęcia i nigdy nie wracamy. Nawet ustawienie optymalizacji slotów w linku planowania, które decyduje, gdzie w każdym wolnym oknie zaczyna się siatka, to jedna linijka arytmetyki w tym samym przebiegu, a nie porównywanie układów.

Kompromis jest realny, a przypadek skrajny łatwo zbudować. Daj jednemu hostowi wąskie okno dostępności nachodzące na okna wszystkich innych, pozwól zachłannemu algorytmowi przydzielić mu w nim pierwszą rezerwację i zablokowałeś jedyny slot, którego mogłaby potrzebować późniejsza, bardziej ograniczona rezerwacja. Pełne przeszukiwanie by to przewidziało. Zachłanny algorytm nie patrzy w przód. Wiemy, że takie przypadki istnieją, i musimy umieć to wypuścić, bo mamy milisekundy. Matematyka deficytu wyrównuje to z czasem.

Jak naprawdę wygląda liniowość

„Przetwarzamy ograniczenia liniowo” łatwo powiedzieć. Konkretnie ruch zawsze jest ten sam. Zamień wszystko na przedziały na jednej absolutnej osi czasu, posortuj raz, przejdź po nich.

Ograniczenia stają się przedziałami, zanim cokolwiek ich dotknie. Tygodniowa reguła nie jest liczona dla każdego potencjalnego slotu. Jest rozwijana raz, w jednej pętli po dniach żądanego okna, do przedziałów 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)

To w tej pętli harmonogramy podróży zmieniają strefę czasową w połowie miesiąca, a czas letni przesuwa offset, więc praca niezależna od dnia jest z niej wyciągana. Konwersja strefy czasowej dominuje tę pętlę i uruchamia się raz na dzień na regułę, a nie raz na slot.

Wydarzenia zbiorowe to scalanie dwoma wskaźnikami, nie iloczyn kartezjański. Trzydziestu hostów potrzebuje terminów, w których wszyscy trzydziestu są wolni. Porównywanie każdego przedziału z każdym przedziałem jest kwadratowe podwójnie. Zamiast tego przedziały każdego hosta są sortowane po czasie startu i składane do bieżącej listy „wspólnej dostępności”:

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

Jeden wskaźnik idzie po wspólnej liście, drugi po liście następnego hosta, a my zawsze przesuwamy ten przedział, który kończy się pierwszy. Rdzeń prawdziwej implementacji jest dokładnie tak mały.

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

Każdy host kosztuje jeden liniowy przebieg, a gdy tylko wspólna lista się wyzeruje, przestajemy. Jeśli hostowie od pierwszego do siódmego nie mają żadnego wspólnego terminu, hostowie od ósmego do trzydziestego nie stworzą żadnego.

Zajęte terminy odejmujemy w jednym posortowanym przebiegu. Rezerwacje, zewnętrzne wydarzenia z kalendarza i okresy poza biurem trafiają do jednej listy wykluczeń, posortowanej raz po czasie startu. Każdy zakres dostępności przechodzi po niej po kolei, zachowując luki:

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
}

Ponieważ wykluczenia są posortowane, wszystko za break nigdy nie jest sprawdzane.

Limity rezerwacji zamieniają się w syntetyczny czas zajęty. „5 rezerwacji dziennie” dałoby się sprawdzać przeciwko każdemu kandydackiemu slotowi, za koszt sloty × limity × rezerwacje. Zamiast tego, gdy licznik dobije do limitu, cały okres staje się jednym przedziałem zajętości i jedzie tym samym przebiegiem odejmowania:

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

Sprawdzenie limitu uruchamia się raz na okres, a pętla po slotach nigdy nie dowiaduje się, że limity istnieją.

Żaden z tych kroków osobno nie jest genialny. Problem NP-trudny przy budżecie milisekundy nie jest rozwiązany jednym błyskotliwym algorytmem. Rozwiązuje się go, odmawiając na każdym kroku pozwolenia, żeby jakiekolwiek obliczenie zależało od iloczynu dwóch dużych liczb.

Wszystko wokół algorytmu też jest ograniczone

Idealny algorytm karmiony wolnym zapytaniem to nadal wolna strona rezerwacji, a warstwa danych pęka pierwsza przy skali enterprise.

Odczyty są grupowane, a potem indeksowane w pamięci. Naiwny kształt to pętla po hostach z trzema zapytaniami w środku. Trzydziestu hostów oznacza 90 round-tripów do Postgresa, zanim zostanie wyliczony choć jeden przedział, niezauważalne dla 5-osobowego zespołu i incydent produkcyjny przy 3 000. Pipeline slotów pobiera wszystko z góry zamiast tego:

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

Rezerwacje i dni poza biurem ładują się równolegle w jednym Promise.all, a limity idą w drugiej zbiorczej rundzie. Wyniki są raz grupowane do lookupów Map<userId, rows>, i od tego momentu matematyka dostępności nie dotyka bazy danych. Funkcja per host jest typowana tak, żeby wymagać wcześniej pobranych danych, więc nikt nie może po cichu wprowadzić zapytania per użytkownik bez protestu kompilatora.

Zewnętrzne kalendarze dostają cache ze ścisłymi regułami. Jedna podróż do dostawcy dominuje cały koszt obliczania przedziałów, więc cache opiera się na trzech zasadach:

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

Jedno nietrafienie płaci za każdy kolejny odczyt gdziekolwiek w horyzoncie. A nieudane wywołanie dostawcy nigdy nie trafia do cache, bo zcache'owanie błędu jako „wolne przez cały horyzont” cicho oferowałoby sloty na istniejące spotkania. Awaria kosztuje ponowną próbę, nigdy złą odpowiedź.

Obsługa dat to gorąca ścieżka kodu. Arytmetyka zależna od strefy czasowej w pętli per slot dominuje wszystko inne, więc konwersja dzieje się raz na granicy, a wewnętrzne pętle porównują zwykłe wartości milisekund UTC.

Limity czasu testujemy, nie zakładamy. Zestawy unitów dowodzą, że każdy algorytm kończy się w limicie czasu, jaki mamy przy skali enterprise, a nie tylko że zwraca poprawną odpowiedź, więc regresja złożoności wywala się w CI, a nie na produkcji.

Gdzie uczciwie mówimy, że jeszcze tam nie jesteśmy

Wszystko powyżej to dyscyplina, a nie gotowy wynik. Oto luka, zmierzona na moim własnym 15-minutowym evencie względem produkcyjnego API podczas pisania tego wpisu:

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

Obliczenia mieszczą się w budżecie. Cała strona mieści się w budżecie tylko wtedy, gdy cache przed wywołaniami dostawcy robi swoją robotę. Zespoły są dalej w tyle i z więcej niż jednego powodu. Uruchamiamy wywołania do Google dla wszystkich hostów równolegle, więc koszt zewnętrzny pozostaje mniej więcej stały, podczas gdy część obliczeniowa rośnie wraz z zespołem. Baza danych dokłada własny ciężar. Dostępność zespołu pobiera konfigurację linku, rezerwacje, limity i wiersze out-of-office dla każdego hosta z tabel trzymających miliony rekordów, a niektóre z tych zapytań wciąż są wolne.

Round robin to obszar, w którym najpierw atakujemy lukę zespołów, bo ma własność, której nie ma problem ogólny. Wydarzenie zbiorowe wymaga, żeby wszyscy hostowie byli wolni, ale rezerwacja round robin potrzebuje dokładnie jednego. Strona rezerwacji nie musi wiedzieć, kto jest dostępny w każdym slocie, tylko czy ktoś w ogóle jest. Dlatego budujemy cache wyższego poziomu, który przechowuje, dla miesiąca slotów, policzoną raz liczbę dostępnych hostów. Każda rezerwacja zmniejsza liczby, których dotyczy, a pełne przeliczenie uruchamia się dopiero wtedy, gdy liczba slotu spadnie na tyle nisko, że naprawdę może zabraknąć hostów. Większość slotów nigdy tam nie dociera. Droższe pytanie, który host bierze rezerwację, nadal jest odpowiadane zachłannie w momencie rezerwacji. Tanie pytanie, czy ktoś jest wolny, staje się odczytem licznika.

Każda funkcja rezerwacji to decyzja algorytmiczna

Każda funkcja rezerwacji, którą wdrażamy, musi odpowiedzieć na pytanie, którego większość produktów SaaS nigdy nie zadaje. Czy to eksploduje przestrzeń przeszukiwania? Funkcja, którą da się wyrazić jako kolejny filtr porządkowania w zachłannym kaskadzie, jest prawie darmowa w dowolnej skali. Taka, która zmusza nas do porównywania kombinacji, jest przeprojektowywana, aż przestaje to robić.

Zachłanny algorytm czasem wybierze gorszą opcję, niż wybrałoby pełne przeszukanie, i to zawsze będzie prawdą. Akceptujemy to, ograniczamy i korygujemy z czasem, bo pełna odpowiedź przychodzi dopiero wtedy, gdy booker przestał czekać. Taki kompromis już działa dla pojedynczych stron rezerwacji. Przyspieszenie go dla organizacji z 3 000 członków to praca, którą właśnie wykonujemy.