【文章标题】：P99 0 ms* 为2.4亿域名实现的自动补全
【文章正文】： p99 0 ms* autocomplete for 240 million domain names 为2.4亿域名实现的P99 0毫秒*自动补全
We’ll get to the asterisk. 星号标注我们稍后会解释
I run Wirewiki.com, a website to inspect internet infrastructure like domain names. It helps people check (historic) DNS records, DNS delegation, email deliverability config, etc. 我运营着Wirewiki.com，这是一个用于检查域名等互联网基础设施的网站。它帮助人们查看（历史）DNS记录、DNS委派、邮件可达性配置等。
There are a ton of sites that offer this (growing faster than ever thanks to vibe coding), so I need a way to stand out. I picked tool quality / usefulness and UX. 现在提供这类服务的网站非常多（由于vibe编程的流行，增长速度前所未有），所以我需要找到脱颖而出的方法。我选择了工具质量/实用性和用户体验作为突破口。
The autocomplete is the main way to navigate Wirewiki, so it should be as complete, accurate and fast as possible. I want it to be instant. Like, next frame instant. 自动补全是Wirewiki的主要导航方式，因此它应该尽可能完整、准确和快速。我希望它能即时响应。就像，下一帧就立即显示那种即时。
I’ve mostly achieved that. Try for yourself: 我已经基本实现了这个目标。你可以自己试试：
Here’s how. 实现原理如下：
On keyDown (the user starts pressing a key), we prefetch the suggestions for the typed character + any next character. And on keyUp (the user releases the key), we render the suggestions. 在keyDown事件（用户开始按键）时，我们会预获取已输入字符+任意下一个字符的建议。而在keyUp事件（用户释放按键）时，我们才渲染这些建议。
That gives us a time budget of keyPress1Duration + gap between key presses + keyPress2Duration. If the API returns before the end of the second key press, we’ll have the results ready in time. 这样我们就有了keyPress1Duration（第一次按键时长）+按键间隔+keyPress2Duration（第二次按键时长）的时间预算。如果API在第二次按键结束前返回结果，我们就能及时准备好建议。
(A 60 Hz display renders every 16.7 ms. So we technically have 8.33 ms extra time budget at p50, but near 0 ms at p99.) （60Hz的显示器每16.7毫秒渲染一帧。所以从技术上讲，在p50时我们还有8.33毫秒的额外时间预算，但在p99时这个预算接近0毫秒。）
So for the purpose of this article, we’ll define latency as keyUp to results ready for rendering. p99 0 ms means that 99% of the time, the results will be ready before the user even releases the key. 因此为了本文的目的，我们将延迟定义为从keyUp事件到结果准备好渲染的时间。p99 0毫秒意味着99%的情况下，结果会在用户松开按键前就准备就绪。
We need two things to make this happen: 要实现这一点，我们需要两样东西：
- Client side prefetching and caching of the suggestions, and
- 客户端预获取和缓存建议
- An API that’s fast enough.
- 足够快速的API
How big is the budget? 这个时间预算有多大？
We now know that we can spend two key press durations and a gap duration, but how long is that in milliseconds? 我们现在知道可以花费两次按键时长和一个间隔时长，但这具体是多少毫秒呢？
I’ve measured it while typing 100 domain names reasonably fast and found that p99 works out to 121 ms for me. 我在快速输入100个域名时进行了测量，发现对我来说p99是121毫秒。
Here are my results. You can start typing to see what it is for you. 这是我的测量结果。你可以开始输入看看你的数据是多少。
How fast can we make the API? 我们的API能有多快？
Okay, so we’ve got a latency target of 121 ms. But how fast can we make the API? 好，我们有了121毫秒的延迟目标。但API能有多快呢？
I’m using the Tranco list of the top 1 million most popular domains for this API. These should be suggested first, and supplemented by any other domain name currently in use. 我为这个API使用了Tranco的前100万个最受欢迎域名列表。这些应该优先建议，并补充当前正在使用的其他域名。
CZDS offers the list of all domains for most of the gTLDs (like .com, .net, .org). ccTLDs (like .uk, .de, .fr) are unfortunately not available. But domains for those with any meaningful traffic will be in the Tranco list anyway. There are other sources, like certificate transparency logs and Archive.org that we could use, but I’ve not integrated them yet. CZDS提供了大多数通用顶级域名（如.com、.net、.org）的所有域名列表。遗憾的是，国家代码顶级域名（如.uk、.de、.fr）不可用。但任何有实际流量的这些域名都会在Tranco列表中。还有其他来源，如证书透明度日志和Archive.org，我们可以使用，但我还没有集成它们。
I’ve designed the API to first search Tranco (the head), and then CZDS (the tail) if necessary. The results are returned in rank order, so the first 8 are the most popular. 我将API设计为先搜索Tranco（头部），必要时再搜索CZDS（尾部）。结果按排名顺序返回，所以前8个是最受欢迎的。
Head: in-memory character trie. A trie (prefix tree) stores the top 8 suggestions precomputed for every prefix. 头部：内存中的字符trie。一个trie（前缀树）存储了为每个前缀预先计算的前8个建议。 A prefix lookup is a walk of a few pointers. 前缀查找就是遍历几个指针。
Worst case time complexity: O(length of what you typed). 最坏情况时间复杂度：O(输入内容的长度)。
Tail: SSD backed memory-mapped block index. The CZDS domains are sorted and delta-compressed into fixed-size blocks with a 尾部：SSD支持的内存映射块索引。CZDS域名被排序并差分压缩成固定大小的块，并带有 tiny in-memory directory. A lookup binary-searches the directory (27 MB), then linearly scans one block of 256 names. The 240M domain names take about 2.5 GB of disk space. Hot pages are cached in memory by the OS. 小型内存目录。查找时对目录（27MB）进行二分搜索，然后线性扫描一个包含256个名称的块。2.4亿个域名约占2.5GB磁盘空间。热页面由操作系统缓存在内存中。
Worst case time complexity: O(length of what you typed * log(number of domains)). 最坏情况时间复杂度：O(输入内容的长度 * log(域名数量))。
Both the number of domains and the query length are bounded. That makes the worst case for both data structures effectively O(1), which should keep p99 latency low. Let’s see. 域名数量和查询长度都是有界的。这使得两种数据结构的最坏情况实际上都是O(1)，这应该能保持p99延迟较低。让我们看看。
I had an LLM stress test the production server. It generated 720k keystroke queries by simulating 60k typed domain names, and replayed them open-loop (firing at a fixed target rate regardless of how fast responses came back). It tested the API in isolation, through Nginx and end-to-end. 我用LLM对生产服务器进行了压力测试。它通过模拟输入6万个域名生成了72万次击键查询，并以开环方式重放（以固定目标速率发送，不管响应返回多快）。它分别测试了单独的API、通过Nginx的API以及端到端的性能。
Most requests are answered within 2 ms by the API. Even at 1.6k req/s, Nginx + the API responds in 15 ms 99% of the time. 大多数请求API在2毫秒内就能响应。即使在1.6k请求/秒的情况下，Nginx+API在99%的情况下都能在15毫秒内响应。
I’m sure we could shave off a couple of milliseconds, but I’m happy with this. Optimizing the API further doesn’t make sense, since the network dominates latency. 我相信我们还能再减少几毫秒，但我对这个结果已经很满意了。进一步优化API没有意义，因为网络延迟才是主要因素。
In practice, the autocomplete latency is about equal to the round trip time from the browser through Cloudflare to the server + 10 ms. 实际上，自动补全的延迟大约等于从浏览器经Cloudflare到服务器的往返时间加上10毫秒。
A round-trip through Cloudflare adds significant latency, but also absorbs frequent requests. 通过Cloudflare的往返会增加明显的延迟，但也能吸收频繁的请求。
In my tests, that end-to-end latency is within our budget. Even when 1000 people are typing at exactly the same time. 在我的测试中，这种端到端延迟在我们的预算范围内。即使1000人同时输入也是如此。
The problem is that I’m just running a single server in Europe. So traffic from further away will exceed the budget at p99. Traffic from the USA will add 100-200 ms, for example. 问题是我只在欧洲运行了一台服务器。所以来自更远地方的流量在p99时会超出预算。例如，来自美国的流量会增加100-200毫秒。
CDN caching of hot paths and Nielsen’s 0.1 s “instantaneous” threshold make up a lot for this, just not enough to make us hit our target. 热门路径的CDN缓存和Nielsen的0.1秒”瞬时”阈值在很大程度上弥补了这一点，只是还不足以让我们达到目标。
I could set up multiple servers and geo load balance traffic. That would give me the p99 0 ms* latency. But that’s a bit much. Even for me. 我可以设置多台服务器并进行地理负载均衡。这样就能实现p99 0毫秒*的延迟。但这有点过了。即使对我来说也是如此。
I would do it if I’d make this into a product. I think this is too niche to build a business on, though. But email me if you’d pay 如果我要把这个做成产品，我会这么做。不过我认为这个领域太细分了，不适合作为业务。但如果你愿意付费的话可以发邮件给我