P99 0 ms* autocomplete for 240M domain names

We’ll get to the asterisk.

I tally Wirewiki.com, a website to inspect net infrastructure for illustration domain names. It helps group cheque (historic) DNS records, DNS delegation, email deliverability config, etc.

There are a ton of sites that connection this (growing faster than ever acknowledgment to vibe coding), truthful I need a measurement to guidelines out. I picked instrumentality value / usefulness and UX.

The autocomplete is the main measurement to navigate Wirewiki, truthful it should beryllium arsenic complete, meticulous and accelerated arsenic possible. I want it to beryllium instant. Like, adjacent framework instant.

I've mostly achieved that. Try for yourself:

Here's how.

On keyDown (the personification starts pressing a key), we prefetch the suggestions for the typed characteristic + immoderate adjacent character. And connected keyUp (the personification releases the key), we render the suggestions.

That gives america a clip fund of keyPress1Duration + spread betwixt cardinal presses + keyPress2Duration. If the API returns earlier the extremity of the 2nd cardinal press, we'll person the results fresh successful time.

(A 60 Hz show renders each 16.7 ms. So we technically person 8.33 ms other clip fund astatine p50, but adjacent 0 ms astatine p99.)

So for the intent of this article, we'll specify latency arsenic keyUp to results fresh for rendering. p99 0 ms intends that 99% of the time, the results will beryllium fresh earlier the personification moreover releases the key.

We request 2 things to make this happen:

1. Client broadside prefetching and caching of the suggestions, and
2. An API that's accelerated enough.

How large is the budget?

We now cognize that we tin walk 2 cardinal property durations and a spread duration, but really agelong is that successful milliseconds?

I've measured it while typing 100 domain names reasonably accelerated and recovered that p99 useful retired to 121 ms for me.

Here are my results. You tin commencement typing to spot what it is for you.

How accelerated tin we make the API?

Okay, truthful we've sewage a latency target of 121 ms. But really accelerated tin we make the API?

I'm utilizing the Tranco database of the apical 1 cardinal astir celebrated domains for this API. These should beryllium suggested first, and supplemented by immoderate different domain sanction presently successful use.

CZDS offers the database of each domains for astir of the gTLDs (like .com, .net, .org). ccTLDs (like .uk, .de, .fr) are unluckily not available. But domains for those pinch immoderate meaningful postulation will beryllium successful the Tranco database anyway. There are different sources, for illustration certificate transparency logs and Archive.org that we could use, but I've not integrated them yet.

I've designed the API to first hunt Tranco (the head), and past CZDS (the tail) if necessary. The results are returned successful rank order, truthful the first 8 are the astir popular.

Head: in-memory characteristic trie. A trie (prefix tree) stores the apical 8 suggestions precomputed for each prefix. A prefix lookup is simply a locomotion of a fewer pointers.
Worst lawsuit clip complexity: O(length of what you typed).

Tail: SSD backed memory-mapped artifact index. The CZDS domains are sorted and delta-compressed into fixed-size blocks pinch a mini in-memory directory. A lookup binary-searches the directory (27 MB), past linearly scans 1 artifact of 256 names. The 240M domain names return astir 2.5 GB of disk space. Hot pages are cached successful representation by the OS.
Worst lawsuit clip complexity: O(length of what you typed * log(number of domains)).

Both the number of domains and the query magnitude are bounded. That makes the worst lawsuit for some information structures efficaciously O(1), which should support p99 latency low. Let's see.

I had an LLM accent trial the accumulation server. It generated 720k keystroke queries by simulating 60k typed domain names, and replayed them open-loop (firing astatine a fixed target complaint sloppy of really accelerated responses came back). It tested the API successful isolation, done Nginx and end-to-end.

Most requests are answered wrong 2 ms by the API. Even astatine 1.6k req/s, Nginx + the API responds successful 15 ms 99% of the time.

I'm judge we could shave disconnected a mates of milliseconds, but I'm happy pinch this. Optimizing the API further doesn't make sense, since the web dominates latency.

In practice, the autocomplete latency is astir adjacent to the information travel clip from the browser done Cloudflare to the server + 10 ms.

A round-trip done Cloudflare adds important latency, but besides absorbs predominant requests.

In my tests, that end-to-end latency is wrong our budget. Even erstwhile 1000 group are typing astatine precisely the aforesaid time.

The problem is that I'm conscionable moving a azygous server successful Europe. So postulation from further distant will transcend the fund astatine p99. Traffic from the USA will adhd 100-200 ms, for example.

CDN caching of basking paths and Nielsen's 0.1 s "instantaneous" threshold dress up a batch for this, conscionable not capable to make america deed our target.

I could group up aggregate servers and geo load equilibrium traffic. That would springiness maine the p99 0 ms* latency. But that's a spot much. Even for me.

I would do it if I'd make this into a product. I deliberation this is excessively niche to build a business on, though. But email me if you'd salary for entree to this API, I mightiness alteration my mind.

Oh, and this is the barroom I group myself for UX connected Wirewiki, truthful if you spot thing that could beryllium improved, please fto maine cognize arsenic well.