Planowanie terminów jest NP-trudne. Potrzebujemy odpowiedzi w milisekundach.

Problem wygląda prosto. Taki nie jest.

Z zewnątrz strona rezerwacji pokazuje godziny, w których ktoś ma wolne. Pod maską jeden miesiąc dostępnych slotów to część wspólna wszystkich poniższych ograniczeń.

• Harmonogramy dostępności zdefiniowane w 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 zmieniają strefę czasową w środku miesiąca

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

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

• Minimalne wyprzedzenie, bufory, interwały slotów i przesunięcia, które decydują, które godziny startu w ogóle się kwalifikują

To jeden host. Każdy typ wydarzenia zespołowego podnosi stawkę inaczej.

• Wydarzenia zbiorowe wymagają, żeby wszyscy hosty byli dostępni jednocześnie, więc pełny zestaw ograniczeń każdego hosta trzeba przeciąć z ograniczeniami wszystkich pozostałych

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

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

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

Każde ograniczenie z osobna jest łatwe. Połączenie już nie. Znalezienie optymalnego czasu spotkania dla grupy przy indywidualnych ograniczeniach dostępności to dobrze zbadany problem NP-trudny.

Bądź precyzyjny co do tego, gdzie leży trudność. Wyliczanie wolnych slotów jednego hosta to wielomianowa arytmetyka przedziałów. NP-trudne jest to, co mamy nad tym optymalizować, na przykład najlepszy wspólny termin dla grupy albo najbardziej sprawiedliwy przydział rezerwacji w horyzoncie przyszłych rezerwacji. Architektura trzyma te dwa poziomy osobno. Wyliczanie pozostaje liniowe, a optymalizacja nigdy nie może zamienić się w wyszukiwanie.

NP-trudne znaczy, że nie znamy algorytmu wielomianowego, a jeśli P = NP, to taki algorytm nie istnieje. Nie „jeszcze tego nie zoptymalizowaliśmy”. Nie „potrzebujemy lepszego sprzętu”. Wyczerpujące przeszukiwanie rośnie wykładniczo. Dla zespołu pięcioosobowego wydaje się natychmiastowe, a dla organizacji z 3 000 osób trwa wiele sekund. Najwięksi klienci najpierw płacą za zły algorytm.

Ograniczenia SaaS czasu rzeczywistego

Świat batch rozwiązuje ten sam rodzaj problemu z prawdziwym budżetem czasu. Planowanie załóg linii lotniczych dostaje wiele godzin pracy solvera na dedykowanych klastrach, a żaden lot nie odjeżdża, kiedy optymalizator liczy. Strona rezerwacji dostaje kilkaset milisekund, a deadline wynika z tego, że booker patrzy na spinner, a nie z naszej infrastruktury.

Najbardziej oczywiste wyjście to policzyć dostępność z wyprzedzeniem w zadaniu w tle i serwować ją z tabeli. Tylko że dane na to nie poczekają. Zajęte terminy zmieniają się, gdy tylko czyjś kalendarz się zmienia, każda nowa rezerwacja zajmuje slot i może wyczerpać limit, a pytanie jest kształtowane dla konkretnego bookera przez jego strefę czasową, wybrany czas trwania, oglądany zakres i routing hostów wybrany dla niego. Prekompilowanie każdej kombinacji samo w sobie jest kombinatoryczną eksplozją, a każda wcześniej policzona odpowiedź staje się nieaktualna w chwili, gdy spotkanie wpada do kalendarza hosta. Nieaktualna dostępność jest gorsza niż powolna dostępność, bo pokazuje godziny, które są już zajęte. Dlatego sloty liczymy w momencie żądania, a cache przed tym obliczeniem żyją z założenia krótko.

Uruchamiamy to na Fluid Compute od Vercel, bo dzięki temu łatwo skalować aplikację. Pojemność podąża za ruchem bez żadnego provisioning, instancje są długowieczne i używane ponownie zamiast uruchamianych per żądanie, cold starty w dużej mierze zniknęły (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 spalanie CPU na przeszukiwaniu kombinatorycznym jest dokładnie tym, za co płacimy.

Zachłannie z założenia

Nigdy nie przeszukujemy przestrzeni wyczerpująco. W każdym punkcie decyzyjnym wybieramy lokalnie najlepszą opcję na podstawie dostępnych informacji, zatwierdzamy ją i idziemy dalej. Bez podglądania w przyszłość. Bez cofania.

W świecie SaaS zachłanność ma negatywne skojarzenia i może brzmieć jak naiwna opcja. Ale dla niektórych problemów zachłanny wybór jest formalnie najlepszy, jaki da się zrobić. Dla problemu pokrycia zbioru, klasycznego problemu NP-trudnego z tej samej rodziny co planowanie grupowe, zachłanność daje logarytmiczny współczynnik aproksymacji, a żaden algorytm wielomianowy nie zrobi lepiej, jeśli tylko P ≠ NP.

Przydział hostów round robin jest najczytelniejszym przykładem. „Poprawny” przydział oznaczałby optymalizację po wszystkich możliwych przyszłych przydziałach, czyli wykładnicze przeszukiwanie, którego odmawiamy uruchamiać. Zamiast tego zbiorem dopuszczalnym są hosty dostępni w żądanym czasie, a wybór przechodzi przez trzy filtry sortowania:

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

Sprawiedliwość porównuje rzeczywistą liczbę rezerwacji każdego hosta w ostatnim przedziale z ważonym udziałem docelowym i utrzymuje 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ą, a 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 nasze „odmawiamy uruchamiania tego przeszukiwania”. Wydarzenie round robin z 3 000 hostów siedzi za routingiem. Booker odpowiada na pytania routingu, a pula kurczy się do 40 zakwalifikowanych hostów. Zarezerwowany host nigdy nie jest usuwany z puli, tylko degradowany (jeśli wszyscy inni są poza biurem, host, który właśnie dostał rezerwację, dostaje też następną), więc każda rezerwacja ma niezależnie 40 możliwych przydziałów.

40 hostów, następne 25 rezerwacji

40²⁵ ≈ 10⁴⁰ możliwych przydziałów. 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 przydziałów. To mniej więcej liczba atomów w obserwowalnym wszechświecie.

Zachłanna kaskada. Trzy liniowe przebiegi po 40 hostach. Około 100 porównań, w dużo mniej niż milisekundę.

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

Żadna pojedyncza decyzja nie musi być idealna, bo system sam się koryguje. Przeciąż hosta dzisiaj, a jego niedobór się zmniejszy, więc sprawiedliwość obniży jego priorytet jutro. Korekty jadą na tym samym kryterium. Host, który dołącza w środku przedziału, dostaje przypisaną średnią liczbę rezerwacji na hosta z okresu przed dołączeniem, a host wracający z poza biura dostaje swój udział rezerwacji zabranych podczas nieobecności. Matematyka niedoboru widzi skorygowaną liczbę. Bez przeliczania historii, bez osobnego etapu równoważenia.

Generowanie slotów jest zachłanne w tym samym duchu. Normalizujesz każde ograniczenie do jednej absolutnej osi czasu, przechodzisz do przodu tylko raz, emitujesz każdy ocalały czas startu i nigdy nie wracasz. Nawet ustawienie optymalizacji slotów w typie wydarzenia, które decyduje, gdzie siatka zaczyna się w każdym wolnym oknie, to jedna linijka arytmetyki podczas tego samego przebiegu, a nie porównywanie układów.

Koszt jest realny, a przypadek skrajny łatwo skonstruować. Daj jednemu hostowi wąskie okno dostępności nachodzące na okna wszystkich pozostałych, pozwól zachłonnemu algorytmowi dać mu pierwszą rezerwację w tym oknie i zablokujesz jedyny slot, z którego mógł skorzystać późniejszy, bardziej ograniczony booking. Wyczerpujące przeszukiwanie by to przewidziało. Zachłanny algorytm nie patrzy w przyszłość. Wiemy, że takie przypadki istnieją, i musimy pogodzić się z tym, że to wysyłamy, bo mamy milisekundy. Matematyka niedoboru wyrównuje to z czasem.

Jak naprawdę wygląda liniowość

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

Ograniczenia stają się przedziałami, zanim cokolwiek ich dotknie. Reguła tygodniowa 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)

Ta pętla to miejsce, gdzie harmonogramy podróży zmieniają strefę czasową w środku miesiąca, a zmiana czasu koryguje przesunięcie, więc praca niezależna od dnia jest z niej wynoszona. Konwersja stref czasowych dominuje w pętli i działa 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 czasów, w których wszyscy trzydziestu są wolni. Porównywanie każdego przedziału z każdym przedziałem jest kwadratowe dwa razy. Zamiast tego przedziały każdego hosta są sortowane po czasie rozpoczęcia i składane w bieżącą listę „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 przechodzi po wspólnej liście, drugi po liście następnego hosta, a my zawsze przesuwamy ten wskaźnik, którego przedział kończy się wcześniej. 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 w chwili, gdy wspólna lista robi się pusta, przerywamy. Jeśli hosty od pierwszego do siódmego nie mają wspólnego czasu, hosty od ósmego do trzydziestego nie mogą go stworzyć.

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 rozpoczęcia. 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, nic za break nie jest już sprawdzane.

Limity rezerwacji stają się syntetycznym zajętym czasem. „5 rezerwacji dziennie” można sprawdzać względem każdego potencjalnego slotu, za koszt slots × limits × bookings. Zamiast tego, gdy licznik dojdzie 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 działa raz na okres, a pętla slotów nigdy nie dowiaduje się, że limity istnieją.

Żaden z tych kroków sam w sobie nie jest genialny. Problem NP-trudny w budżecie jednej milisekundy nie jest rozwiązywany przez jeden błyskotliwy algorytm. Rozwiązuje się go przez to, że na każdym kroku odmawiamy dopuszczenia, by jakiekolwiek obliczenie zależało od iloczynu dwóch dużych liczb.

Wszystko wokół algorytmu też ma ograniczenia

Idealny algorytm karmiony wolnym zapytaniem nadal daje wolną stronę rezerwacji, a warstwa danych jako pierwsza zaczyna boleć przy skali enterprise.

Odczyty są batchowane, a potem indeksowane w pamięci. Naiwny układ to pętla po hostach z trzema zapytaniami w środku. Trzydzieści hostów oznacza 90 round tripów do Postgresa, zanim policzy się choćby jeden przedział, co jest niewidoczne dla zespołu 5-osobowego, a dla 3 000 osób staje się incydentem produkcyjnym. 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ą potem w drugim batchu. Wyniki są raz grupowane w lookupy Map<userId, rows>, a od tego momentu matematyka dostępności nie dotyka bazy danych. Funkcja per host jest typowana tak, żeby wymagała wcześniej pobranych danych, więc nikt nie może po cichu wprowadzić z powrotem zapytania per użytkownik bez krzyku kompilatora.

Zewnętrzne kalendarze dostają cache z twardymi zasadami. Jedna podróż do dostawcy kosztuje więcej niż całe obliczenie 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 trafienie do cache płaci za każdy kolejny odczyt w całym horyzoncie. A nieudane wywołanie dostawcy nigdy nie jest cachowane, bo zapisanie błędu jako „wolne przez cały horyzont” cicho proponowałoby sloty nakładające się na prawdziwe spotkania. Awaria kosztuje ponowną próbę, nigdy złą odpowiedź.

Obsługa dat to kod hot path. Arytmetyka uwzględniająca strefy czasowe 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.

Budżety czasu są testowane, a nie zakładane. Zestawy unitowe dowodzą, że każdy algorytm kończy się w limicie czasu, który 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 przyznajemy, że jeszcze nas tam nie ma

Wszystko powyżej to dyscyplina, a nie gotowy wynik. Oto luka, zmierzona na moim własnym 15-minutowym wydarzeniu przeciwko produkcyjnemu 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

Obliczenie mieści się w budżecie. Cała strona mieści się w budżecie tylko wtedy, gdy cache przed wywołaniami dostawcy robi swoją robotę. Teams jest dalej w tyle i to z więcej niż jednego powodu. Uruchamiamy wywołania Google dla wszystkich hostów równolegle, więc koszt zewnętrzny pozostaje mniej więcej stały, podczas gdy strona obliczeniowa rośnie wraz z zespołem. Baza danych dokłada własny opór. Dostępność zespołu pobiera konfigurację linków, rezerwacje, limity i wiersze poza biurem dla każdego hosta z tabel trzymających miliony rekordów, a część z tych zapytań nadal jest wolna.

Round robin to obszar, w którym najpierw atakujemy lukę zespołową, bo ma własność, której nie ma problem ogólny. Wydarzenie zbiorowe wymaga, żeby każdy host był wolny, ale rezerwacja round robin potrzebuje dokładnie jednego. Strona rezerwacji nie musi wiedzieć, kto jest dostępny w każdym slocie, tylko czy ktoś jest. Budujemy więc wyższej warstwy cache, który przechowuje dla miesiąca slotów liczbę dostępnych hostów policzoną raz. Każda rezerwacja zmniejsza liczby, których dotyczy, a pełne przeliczenie uruchamia się dopiero wtedy, gdy liczba w slocie spadnie na tyle nisko, że może faktycznie zabraknąć hostów. Większość slotów nigdy tam nie dochodzi. Droższe pytanie, który host dostaje rezerwację, nadal odpowiadamy 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ą wysyłamy, musi odpowiedzieć na pytanie, którego większość produktów SaaS nigdy nie zadaje. Czy to eksploduje przeszukiwanie? Funkcja, którą da się wyrazić jako kolejny filtr porządkowania w zachłannej kaskadzie, jest prawie darmowa w każdej skali. Tę, która zmusza nas do porównywania kombinacji, przebudowujemy, aż już tego nie robi.

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