p99 0ms* autocomplete voor 240 miljoen domeinnamen

We komen later terug op het sterretje.

Ik beheer Wirewiki.com, een website om internetinfrastructuur zoals domeinnamen te inspecteren. Het helpt mensen bij het controleren van (historische) DNS-records, DNS-delegatie, e-mailleverbaarheid-configuraties, enzovoort.

Er zijn talloze sites die dit aanbieden (een aantal dat sneller groeit dan ooit dankzij vibe coding), dus ik heb een manier nodig om op te vallen. Ik heb gekozen voor toolkwaliteit, bruikbaarheid en UX.

De autocomplete is de belangrijkste manier om door Wirewiki te navigeren, dus deze moet zo volledig, nauwkeurig en snel mogelijk zijn. Ik wil dat het direct is. Echt direct, binnen het volgende frame.

Dat is grotendeels gelukt. Zo werkt het:

De werking van de autocomplete

Bij keyDown (wanneer de gebruiker een toets indrukt), prefetcht de browser de suggesties voor het getypte teken plus elk mogelijk volgend teken. Bij keyUp (wanneer de gebruiker de toets loslaat), worden de suggesties gerenderd.

Voorbeeld van een API-aanroep: GET /autocomplete?q=wi

Respons:

{
  "results": ["wikipedia.org", "windowsupdate.com", "windows.net", "windows.com", "wixsite.com", "wikimedia.org", "wiley.com", "wildberries.ru"],
  "next": {
    "-": ["wi-fi.ru", "wi-fi.org", "wi-fi.click", "wi-tribe.ph", "wi-cat.ru", "wi-fi.link", "wi-power.com", "wi-fi.com"],
    ".": ["wi.gov", "wi.us", "wi.infomart.co.jp", "wi.net", "wi.likebtn.com", "wi.accountants", "wi.agency", "wi.amsterdam"],
    "0": ["wi0.buzz", "wi0.com", "wi0.mobi", "wi0.site", "wi0.tech", "wi0.top", "wi0.xyz", "wi00.com"],
    "9": ["wi9-h.com", "wi9.casino", "wi9.com", "wi9.lol", "wi9.mobi", "wi9.org", "wi9.top", "wi9.xyz"],
    "a": ["wiadomosci.wp.pl", "wiadomosci.onet.pl", "wiadomosci.gazeta.pl", "wialon.com", "wialon.host", "wiair.com", "wiara.pl", "wiadomosci.radiozet.pl"],
    "k": ["wikipedia.org", "wikimedia.org", "wiktionary.org", "wikihow.com", "wikia.com", "wikisource.org", "wikibooks.org", "wikidot.com"],
    "z": ["wizzair.com", "wizards.com", "wiz.world", "wiz.biz", "wiz.io", "wiz.cn", "wizardingworld.com", "wizaz.pl"]
  }
}

Dit geeft ons een tijdvenster bestaande uit: duur toetsaanslag 1 + pauze tussen toetsaanslagen + duur toetsaanslag 2. Als de API antwoordt voordat de tweede toetsaanslag is voltooid, zijn de resultaten op tijd klaar.

(Een 60 Hz-scherm rendert elke 16,7 ms. Technisch gezien hebben we dus 8,33 ms extra tijdbudget bij p50, maar bijna 0 ms bij p99.)

De aanvraag voor q=wi wordt verzonden op het moment dat de i wordt ingedrukt; als het antwoord binnenkomt voordat de k wordt losgelaten, worden de aanvullingen voor wik gerenderd met nul waarneembare latentie.

Voor dit artikel definiëren we latentie dus als de tijd van keyUp tot het moment dat de resultaten klaar zijn voor rendering. p99 0 ms betekent dat in 99% van de gevallen de resultaten klaar zijn voordat de gebruiker de toets heeft losgelaten.

Om dit te bereiken zijn twee zaken nodig:

  1. Client-side prefetching en caching van de suggesties.
  2. Een API die snel genoeg is.

Wat dacht je van de bandbreedte?

In eerste instantie maakte ik me hier zorgen over, maar dat bleek geen probleem. Er zijn slechts 38 geldige tekens voor domeinnamen: a-z, 0-9, - en .. Dat stelt de bovengrens van de respons vast op (38 + 1) * 8 = 312 domeinnamen.

In de praktijk komt dit neer op maximaal ongeveer 5 kB aan data per verzoek, wat na compressie resulteert in 2,5 kB over de lijn. Gegeven dat 50-100 kB over het algemeen wordt beschouwd als een gezonde afbeeldingsgrootte, staat dit gelijk aan ongeveer 20-40 getypte tekens. Aangezien ik nooit twee keer nadenk over het toevoegen van een afbeelding aan een pagina vanwege het bandbreedteverbruik, ben ik hier tevreden mee.

Hoe groot is het budget?

We weten nu dat we twee toetsaanslagduuren en een pauze kunnen gebruiken, maar hoeveel milliseconden is dat precies?

Ik heb dit gemeten terwijl ik 100 domeinnamen redelijk snel typte en ontdekte dat p99 voor mij uitkomt op 121 ms.

Hoe snel kunnen we de API maken?

Het latentiedoel is dus 121 ms. Maar hoe snel kan de API worden gemaakt?

Ik gebruik de Tranco-lijst van de 1 miljoen meest populaire domeinen voor deze API. Deze moeten als eerste worden gesuggereerd, aangevuld met elk ander domein dat momenteel in gebruik is.

CZDS biedt de lijst van alle domeinen voor de meeste gTLD's (zoals .com, .net, .org). ccTLD's (zoals .uk, .de, .fr) zijn helaas niet beschikbaar, maar domeinen met aanzienlijk verkeer staan sowieso in de Tranco-lijst. Er zijn andere bronnen, zoals certificate transparency logs en Archive.org, maar die heb ik nog niet geïntegreerd.

Ik heb de API zo ontworpen dat hij eerst zoekt in Tranco (de head) en daarna, indien nodig, in CZDS (de tail). De resultaten worden geretourneerd op basis van rangorde, zodat de eerste acht de populairste zijn.

De Head: in-memory character trie

Een trie (prefixboom) slaat de top 8 vooraf berekende suggesties op voor elk prefix. Een prefix-zoekopdracht is een wandeling van enkele pointers.

  • Worst-case tijdcomplexiteit: $O(\text{lengte van de invoer})$.

De Tail: SSD-backed memory-mapped block index

De CZDS-domeinen zijn gesorteerd en delta-gecomprimeerd in blokken van vaste grootte, met een kleine directory in het geheugen. Een zoekopdracht voert een binaire zoekopdracht uit in de directory (27 MB) en scant vervolgens lineair één blok van 256 namen. De 240 miljoen domeinnamen nemen ongeveer 2,5 GB aan schijfruimte in beslag. 'Hot pages' worden door het OS in het geheugen gecachet.

  • Worst-case tijdcomplexiteit: $O(\text{lengte van de invoer} \times \log(\text{aantal domeinen}))$.

Omdat zowel het aantal domeinen als de querylengte begrensd zijn, is de worst-case voor beide datastructuren effectief $O(1)$, wat de p99-latentie laag zou moeten houden.

Netwerkpad en resultaten

Elke toetsaanslag reist via: Browser → Cloudflare (global edge cache) → Wirewiki server (nginx TLS proxy) → API (Autocomplete). De respons volgt hetzelfde pad terug.

Ik heb een LLM gebruikt om de productieserver te stress-testen. Er werden 720.000 keystroke-queries gegenereerd door 60.000 getypte domeinnamen te simuleren, die open-loop werden afgespeeld (met een vaste doelsnelheid, ongeacht hoe snel de responsen terugkwamen). Er is getest op de API in isolatie, via Nginx en end-to-end.

Resultaten van de loadtest: De meeste verzoeken worden binnen 2 ms beantwoord door de API. Zelfs bij 1,6k req/s reageert de combinatie van Nginx en de API in 99% van de gevallen binnen 15 ms.

Verdere optimalisatie van de API heeft weinig zin, aangezien het netwerk de latentie domineert. In de praktijk is de autocomplete-latentie ongeveer gelijk aan de round-trip time (RTT) van de browser via Cloudflare naar de server + 10 ms.

Hoewel een round-trip via Cloudflare aanzienlijke latentie toevoegt, absorbeert het ook frequente verzoeken. In mijn tests valt deze end-to-end latentie binnen ons budget, zelfs wanneer 1000 mensen tegelijkertijd typen.

Beperkingen en conclusie

Het probleem is dat ik momenteel slechts één server in Europa draai. Verkeer van verder weg zal het budget bij p99 overschrijden. Verkeer uit de VS voegt bijvoorbeeld 100-200 ms toe.

CDN-caching van populaire paden en de drempelwaarde van 0,1 s van Nielsen voor "instantane" reacties compenseren dit grotendeels, maar niet genoeg om ons doel overal te halen.

Ik zou meerdere servers kunnen opzetten en het verkeer via geo load balancing kunnen verdelen. Dat zou me de p99 0 ms* latentie geven. Maar dat is wat overdreven, zelfs voor mij. Ik zou het doen als ik hier een product van zou maken, maar ik denk dat dit te niche is om een bedrijf op te bouwen. (Mocht je echter bereid zijn te betalen voor toegang tot deze API, stuur me dan een e-mail).

Dit is de lat die ik voor de UX van Wirewiki heb gelegd. Als je dingen ziet die verbeterd kunnen worden, laat het me dan weten.