针对2.4亿域名的p99 0ms*自动补全

# 99%的情况下，为2.4亿个域名提供零毫秒延迟的自动补全 来源：https://ruurtjan.com/articles/p99-0ms-autocomplete-for-240-million-domain-names 稍后会解释那个星号的含义\*。 我运营着[Wirewiki.com](https://www.wirewiki.com/)，一个用来检查互联网基础设施（如域名）的网站。它能帮助人们查看（历史）DNS记录、DNS委托、邮件送达性配置等信息。 提供这类服务的网站多如牛毛（得益于"氛围编码"，其增长速度前所未有），所以我需要脱颖而出。我选择的方向是工具质量/实用性以及用户体验。 自动补全是浏览Wirewiki的主要方式，因此它必须尽可能完整、准确和快速。我希望它是**即时的**——就像下一帧就出现结果那样即时。 我基本上已经实现了这个目标。你可以亲自试试看： Tab键切换标签页 导航 打开 下面说说实现方法。 在`keyDown`事件（用户开始按下一个键）时，我们预取当前输入字符加上下一个字符的建议结果。然后在`keyUp`事件（用户释放按键）时，渲染建议结果。 GET /autocomplete?q=wi ```json { "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"] } } ``` 这样我们就有了一个时间预算：`第一次按键持续时间 + 两次按键间隔 + 第二次按键持续时间`。如果API在第二次按键结束前返回结果，我们就能及时准备好建议。 （60Hz的显示器每16.7ms渲染一帧。所以从技术上来说，在p50（中位数）我们有额外的8.33ms时间预算，但在p99（99%分位）几乎为零。） 按键释放 → 按键按下 wik GET /autocomplete?q=wi 渲染‘wik’的建议 API的时间预算 API往返时间 当按下`i`的那一刻，就会发起`q=wi`的请求；如果它的响应在`k`释放之前到达，那么`wik`的建议就能以零感知延迟渲染出来。因此，在这篇文章中，我们将延迟定义为`从按键释放到结果准备就绪可以渲染`。p99零毫秒意味着，99%的情况下，结果会在用户甚至还没释放按键之前就准备好了。 要实现这一点，我们需要两样东西： 1. 客户端预取和缓存建议结果，以及 2. 一个足够快速的API。 ## 时间预算有多大？ 现在我们知道可以利用两次按键持续时间和一次间隔时间，但这具体是多少毫秒呢？ 我以较快的速度输入了100个域名并进行了测量，发现对我而言，p99大约是121毫秒。 以下是我测量的结果。你可以开始输入，看看你自己的情况。 ## API能有多快？ 好的，我们的延迟目标是121毫秒。但API本身能有多快呢？ 我使用[Tranco](https://tranco-list.eu/)列表中最受欢迎的100万个域名作为这个API的数据源。这些域名应该优先被建议，然后再补充其他正在使用的域名。 [CZDS](https://czds.icann.org/home)提供了大部分通用顶级域（gTLD，如.com、.net、.org）的所有域名列表。但国家顶级域（ccTLD，如.uk、.de、.fr）的数据不可用。不过，这些域中但凡有显著流量的，也都已经包含在Tranco列表中了。还有其他来源，比如证书透明度日志和Archive.org，但我们尚未集成。 我设计的API会先搜索Tranco（头部数据），如有必要再搜索CZDS（尾部数据）。结果按排名顺序返回，因此前8个是最受欢迎的。 **头部数据：内存中的字符Trie树。** Trie树（前缀树）存储了为每个前缀预计算好的前8个建议。前缀查找只是遍历几个指针。最坏情况时间复杂度：`O(输入长度)`。 **尾部数据：基于SSD的内存映射块索引。** CZDS的域名经过排序和增量压缩，存储为固定大小的块，并附带一个很小的内存目录。查找时，先二分查找目录（27MB），然后线性扫描一个包含256个域名的块。这2.4亿个域名大约占用2.5GB磁盘空间。热点页面由操作系统缓存在内存中。最坏情况时间复杂度：`O(输入长度 * log(域名数量))`。 由于域名数量和查询长度都有上限，这两种数据结构的 worst-case 实际上都是 O(1)，这应该能保证 p99 延迟很低。我们来看看。 浏览器 → wik | Cloudflare全局边缘缓存 → Wirewiki服务器 → nginx → TLS · 代理 → API → 自动补全 每次按键都经过 `浏览器 → Cloudflare → nginx → API` 的路径，响应也沿着相同路径返回。 我让一个LLM对生产服务器进行了压力测试。它模拟了6万个输入域名，生成了72万次按键查询，并以开环方式（无论响应返回多快，都按固定目标速率发送请求）重放。它分别测试了API本身、通过Nginx以及端到端的性能。 大多数请求在2毫秒内就能得到API的响应。即使在每秒1600个请求的负载下，Nginx+API在99%的情况下也在15毫秒内响应。 我相信我们还能再节省几毫秒，但对此已经满意了。进一步优化API没有意义，因为网络延迟才是主导因素。 实际上，自动补全的延迟大致等于从浏览器经过Cloudflare到服务器的往返时间加上10毫秒。 经过Cloudflare的往返会增加显著的延迟，但也能吸收频繁的请求。 在我的测试中，端到端延迟在我们的预算之内。即使有1000人同时在输入。 问题在于，我目前只运行了一台欧洲的服务器。因此，来自更远地区的流量在p99时会超出预算。例如，来自美国的流量会增加100-200毫秒。 对热点路径进行CDN缓存，以及[Nielsen提出的0.1秒“即时”阈值](https://www.nngroup.com/articles/response-times-3-important-limits/)，在很大程度上弥补了这一问题，但还不足以让我们达到目标。 我可以设置多台服务器并进行地理负载均衡。那样就能实现p99零毫秒\*的延迟。但这有点过了，即使对我来说也是。 如果我打算把这个做成产品，我会这么做的。不过我认为这个功能过于小众，很难建立商业模式。但如果你愿意为使用这个API付费，请[给我发邮件](mailto:[email protected])，我可能会改变主意。 哦，这是我为[Wirewiki](https://www.wirewiki.com/)的用户体验设定的标准，所以如果你发现任何可以改进的地方，也请告诉我。