为 2.4 亿域名实现 P99 0ms* 自动补全
先说那个星号的事，我们稍后再聊。
我运营着 Wirewiki.com，一个用来查看域名等互联网基础设施的网站。它能帮人们查询（历史）DNS 记录、DNS 委派、邮件投递配置等等。
提供这类服务的网站非常多（而且随着 vibe coding 越来越火，还在持续增长），所以我得想办法脱颖而出。我选择了工具质量和实用性、以及用户体验作为发力点。
自动补全是 Wirewiki 的主要导航方式，所以它必须尽可能地全面、准确、快速。我希望它是即时的——那种下一帧就能显示的即时。
我基本上做到了。不妨亲自试试：
Tab 切换标签页 Navigate Open实现思路如下。
在 keyDown 时（用户开始按下一个键），我们就为已输入字符加上任意可能的下一个字符预取建议。而在 keyUp 时（用户松开按键），再渲染这些建议。
这样一来，我们的时间预算就是 keyPress1Duration + gap between key presses + keyPress2Duration。只要 API 在第二次按键结束前返回，结果就能及时呈现。
（60 Hz 显示器每 16.7 ms 渲染一帧。所以在 p50 时我们实际上多了 8.33 ms 的时间余量，但在 p99 时几乎为 0 ms。）
i 的瞬间就会发出 q=wi 的请求；如果在松开 k 之前拿到响应，wik 的补全结果就能以零感知延迟呈现。因此本文中我们把延迟定义为「从松开键到结果可以渲染」。p99 0 毫秒意味着 99% 的情况下，结果会在用户松手之前就准备好了。
要做到这一点，需要两件事：
- 客户端对建议进行预取和缓存；
- API 本身要足够快。
预算有多少？
现在我们知道可以利用两次按键时长加一段间隔时间，但这换算成毫秒是多久？
我用较快速度输入 100 个域名做了测量，自己 p99 大约是 121 毫秒。
这是我的测试结果。你可以开始输入，看看你的数值是多少。
测量延迟预算
这里测量的是从一次按键到下一次松键的间隔。滑动条会告诉你：在某个 API 延迟下，有多少比例的按键能做到下一帧渲染。
121 毫秒 — 在 121 毫秒延迟下可做到下一帧渲染 不同延迟下「下一帧渲染」占比随延迟变化的关系。竖线对应滑动条位置。 每次按键的预算（毫秒）。线左边的小条表示在当前延迟下会「赶不上」的按键分布。 输入一些域名以填充数据。 重置API 能做到多快？
好，我们有了 121 毫秒这个延迟目标。但 API 能做到多快？
这个 API 我用的是 Tranco 列表里最热门的前 100 万域名。这些会优先推荐，再用其他正在使用的域名补足。
CZDS 提供了大多数 gTLD（如 .com、.net、.org）的全部域名列表。ccTLD（如 .uk、.de、.fr）则无法获取。不过这些里面只要流量有一定规模，基本都会出现在 Tranco 列表中。还有其他来源，比如证书透明度日志和 Archive.org 也可以用，但我暂时还没接入。
我的 API 设计是先搜 Tranco（头部），必要时再搜 CZDS（尾部）。结果按排名顺序返回，所以前 8 个就是最热门的。
首部：内存字符字典树。字典树（前缀树）为每个前缀预先存好前 8 条建议。前缀查找只需顺着几个指针走几步。
最坏情况时间复杂度：O(已输入长度)。
尾部：基于 SSD 的内存映射块索引。CZDS 域名排序后做差分压缩，按固定大小分块，配一个很小的内存目录。先在目录里二分查找（27 MB），再在一个块里线性扫描 256 个域名。2.4 亿个域名大约占 2.5 GB 磁盘空间。热点页由操作系统缓存在内存里。
最坏情况时间复杂度：O(已输入长度 × log(域名数量))。
域名数量和查询长度都是有界的。因此这两种数据结构的最坏情况实际上是 O(1)，应该能让 p99 延迟保持很低。来看看实际表现。
浏览器 → Cloudflare → nginx → API，响应原路返回。我让一个大模型对生产服务器做压力测试。它模拟 6 万次域名输入，生成了 72 万次按键查询，并以开环方式回放（按固定目标速率发出请求，不管响应多快回来）。分别测试了 API 单独运行、经 Nginx 以及端到端三种场景。
压测结果
不同请求速率下的延迟百分位数，两轴均为对数刻度。
仅 API 源站链路（nginx + API） 端到端（Cloudflare + nginx + API）| req/s | p50 | p90 | p99 | max | errors |
|---|
绝大多数请求在 API 这层 2 ms 内就返回了。即便达到 1.6k req/s，Nginx + API 也能在 15 ms 内响应 99% 的请求。
我相信还能再优化掉几毫秒，但目前这个结果我已经满意了。继续优化 API 意义不大，因为瓶颈在网络。
实际使用中，自动补全的延迟大约等于从浏览器经 Cloudflare 到服务器的往返时延再加 10 ms。
经 Cloudflare 走一圈会显著增加延迟，但同时也吸收了大量请求。
在我的测试里，即便 1000 个人同时在打字，端到端延迟也在预算范围内。
问题在于我只部署了一台欧洲服务器。所以来自更远地区的流量在 p99 上会超出预算。比如美国的流量会增加 100-200 毫秒。
对热门路径做 CDN 缓存，加上 Nielsen 提出的 0.1 秒"瞬时"阈值，能在很大程度上弥补这一点，但还不足以让我们达标。
我可以部署多台服务器并对流量做地理负载均衡，这样就能实现 p99 0 毫秒* 的延迟。但这对个人项目来说有点过头了。
如果要把这个做成产品，我会愿意去做。不过我觉得这个领域太细分了，没法撑起一门生意。但如果你愿意付费使用这个 API，欢迎给我发邮件，说不定我会改变主意。
对了，这是我在 Wirewiki 上为自己设定的用户体验标准，所以如果你发现有什么可以改进的地方，也请告诉我。