En dag är ett 288-bitars heltal

Tillgänglighet är den svåraste läsningen i en bokningsprodukt. En månadsvy för en klinik måste besvara en fråga — när kan den här patienten faktiskt boka? — mot öppettider, varje läkares egna tider, delade pass, befintliga bokningar, semestrar, stängningsdagar, dagliga tak per tjänst, buffertar mellan tjänster, tider som redan passerat och ett kundvänt rutnät som är grövre än det interna. Multiplicera det med trettio dagar och tio läkare, så är det den frågan som avgör om produkten känns snabb.

Vi byggde det som de flesta gör första gången: materialisera dagen som en lista av tider och filtrera sedan. Skapa 288 femminutersposter, gå igenom bokningarna och stryk poster, gå igenom semestrarna och stryk fler, och gå sedan för varje möjlig starttid framåt D poster för att se om tjänsten får plats. Det är läsbart, det är uppenbart korrekt, och varje ny regel kostar ytterligare ett helt varv genom listan.

Vändningen kom när vi slutade lagra tider och började lagra ett tal.

En dag är ett 288-bitars heltal — en bit per femminuterslucka.

288 bitar är 24 timmar med femminutersupplösning (SLOT_GRANULARITY_MINUTES = 5). Det måste vara ett BigInt snarare än ett vanligt number, eftersom JavaScript-tal bara har 53 bitars heltalsprecision — en dag får inte plats i en double. När en dag är ett enda heltal kollapsar varje schemabegrepp till en bitoperation:

Klockan nio är minut 540, vilket är bit 108; klockan fem är bit 204. Öppettider slutar vara ett par tidsstämplar att jämföra mot och blir en serie ettor som skiftats på plats. En läkare som arbetar förmiddagar och kvällar är två masker OR-ade ihop. En läkares bokningsbara tid är hens mask AND klinikens. Att avboka en tid är ingen radering och ombyggnad — det är en bit som blir en etta igen.

En disciplin gör det hela säkert: varje ~ och varje << följs av & DAY_MASK. BigInt är obegränsat, så ~x har oändligt många inledande ettor och << flyttar gladeligen bitar förbi midnatt. Utan masken får du spöktillgänglighet klockan två på natten en dag som inte finns. Det är den sortens invariant som måste skrivas ner en gång, överst i filen, och sedan aldrig brytas.

Hitta sammanhängande luckor utan att skanna

En ledig bit är inte en bokningsbar bit. En bokning på 60 minuter kräver tolv lediga luckor i rad, och den naiva kontrollen är att gå framåt från varje möjlig start.

let result = freeBits;
for (let i = 1; i < durationBits; i++) {
  result &= freeBits >> BigInt(i);
}

Det här är den klassiska shift-and-AND-detektorn, och den ersätter 288 × D jämförelser med D − 1 operationer. Varje operation är ordparallell: ett 288-bitarsvärde är ungefär fem maskinord, så en tjänst på 60 minuter är 11 AND — säg 55 ordoperationer för att hitta varje giltig starttid under en hel läkardag. Listversionen gör tusentals.

Kedjade bokningar, linjerade genom skiftning

Det vi är mest nöjda med är bokningar av flera tjänster. Om någon bokar tre tjänster i rad måste tjänst två starta vid T plus tjänst ettans längd plus en buffert, och tjänst tre efter det. Den uppenbara implementationen testar möjliga starttider och följer kedjan framåt från var och en.

const aligned = startsThisService >> BigInt(cumulativeOffsetBits);
chainStarts &= aligned;
cumulativeOffsetBits += durationBitsList[i] + bufferBits;

if (chainStarts === 0n) break;

I stället för att testa tider skiftas hela masken för varje tjänst bakåt med dess ackumulerade förskjutning, så att varje tjänst i kedjan uttrycks relativt samma utgångspunkt T. Sedan AND-as de bara ihop. En kedja med tre tjänster och buffertar är tre skift och tre AND, och i samma ögonblick som chainStarts blir noll är kedjan bevisat omöjlig och loopen avbryts. Det som återstår anpassas till kundens rutnät på 15 eller 30 minuter med applyGridMask, eftersom patienter inte ska erbjudas 09:35.

Vad det faktiskt kostar

Per dag är arbetet ett maskbygge, en operation per befintlig bokning, summan av (Dᵢ − 1) AND över tjänsterna och ett fast varv på ~58 iterationer för rutnätet. Trettio dagar för tio läkare är i storleksordningen några tusen BigInt-operationer på fem ord.

Hela månadens tillgänglighetsfråga är fyra SQL-anrop — klinikinfo, tjänster med behöriga läkare, bokningar och antal per tjänst mot taken — alla indexerade och alla laddade en gång, utanför dagsloopen. Databasen står för ungefär 99 % av tiden. Algoritmen är brus, och det är precis där du vill att din schemalogik ska ligga.

Den är också tillståndslös. Tillgänglighet beräknas per anrop och kastas sedan. Det finns ingen förberäknad tabell med tider, vilket betyder att det inte finns någon cache att invalidera när någon bokar — den enskilt svåraste buggklassen i bokningssystem existerar helt enkelt inte här, eftersom det som kunde bli inaktuellt aldrig lagrades.

Skyddsnätet

Snabb tillgänglighet är en optimering på lässidan, och en optimering på lässidan får aldrig vara det enda som står mellan dig och en dubbelbokning. Databasen upprätthåller det oberoende, med en exclusion constraint på överlappande tidsintervall:

EXCLUDE USING gist (
  doctor_id WITH =,
  tstzrange(starts_at, ends_at) WITH &&
)

Två anrop som tävlar om samma tid kan inte båda vinna, oavsett vad tillgänglighetsmotorn trodde ett ögonblick tidigare. Bitmasken gör den vanliga vägen snabb; Postgres gör den ovanliga vägen korrekt.

Vad vi tar med oss

• Rätt representation tar bort arbete i stället för att optimera det. Ingen av operationerna är smart i sig — de är bara möjliga för att dagen slutade vara en lista.
• Ordparallellism är gratis prestanda som de flesta applikationer aldrig tar vara på. En AND på 288 bitar kostar ungefär fem maskinord, oavsett hur många tider den avgör.
• Transformera problemet till en gemensam utgångspunkt i stället för att söka. Skift-och-linjera-tricket gjorde en nästlad sökning över starttider till ett enda snitt.
• Skriv invarianten där den upprätthålls. Varje ~ och << behöver & DAY_MASK, och det hör hemma i en kommentar överst i filen, inte i granskarens minne.
• Låt aldrig en snabb läsväg vara det enda skyddet för en skrivning. Det är exclusion constrainten som gör optimeringen säker att lita på.
• Att inte cacha är en funktion. Tillståndslös beräkning som är tillräckligt snabb har inga invalideringsbuggar, eftersom det inte finns något att invalidera.