P99 0 ms* 240M 域名自动完成

我们将到达星号。我运行 Wirewiki.com，这是一个检查域名等互联网基础设施的网站。它可以帮助人们检查（历史）DNS 记录、DNS 委托、电子邮件送达配置等。有大量网站提供此服务（由于 vibe 编码，增长速度比以往任何时候都快），所以我需要一种方法来脱颖而出。我选择了工具质量/实用性和用户体验。自动完成是浏览 Wirewiki 的主要方式，因此它应该尽可能完整、准确和快速。我希望它是即时的。就像，下一帧瞬间。我基本上已经实现了这一点。自己尝试一下：方法如下。在 keyDown（用户开始按下某个键）时，我们预取针对键入的字符 + 任何下一个字符的建议。在 keyUp（用户释放按键）上，我们呈现建议。 GET /autocomplete?q=wi { "结果" : [ "wikipedia.org" , "windowsupdate.com" , "windows.net" , "windows.com" , "wixsite.com" , "wikimedia.org" , "wiley.com" , "wildberry.ru" ], "下一个" : { "-" : [ "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" ] } } 这为我们提供了 keyPress1Duration + 按键之间的间隙 + keyPress2Duration 的时间预算。如果 API 在第二次按键结束之前返回，我们将及时准备好结果。 （60 Hz 显示屏每 16.7 毫秒渲染一次。因此，从技术上讲，我们在 p50 处有 8.33 毫秒的额外时间预算，但在 p99 处接近 0 毫秒。） 释放按键 按下按键 w i k GET /autocomplete?q=wi “wik”的渲染完成 API 的时间预算 延迟 API 往返时间 q=wi 的请求在按下 i 时触发；如果其响应在 k 释放之前到达，则 wik 的补全将以零感知延迟呈现。因此，出于本文的目的，我们将延迟定义为 keyUp 到结果准备渲染的时间。 p99 0 ms 意味着 99% 的时间，结果将在用户释放按键之前准备就绪。我们需要两件事来实现这一点：客户端预取和缓存建议，以及足够快的 API。撇开带宽怎么样？这是我最初担心的问题。但事实证明这不是问题。有效域名只有 38 个字符： a-z 、 0-9 、 - 和 。 。这设置了响应中 (38 + 1) * 8 = 312 个域名的上限。实际上，每个请求最多可传输约 5 kB 的数据。压缩后，2.5 kB 通过线路传输。鉴于 50-100 kB 通常被认为是健康的图像大小，则相当于键入 20-40 个字符。由于带宽的使用，我从来没有考虑过在页面上包含图像，所以我认为我对此感到满意。预算有多大？我们现在知道我们可以花费两个按键持续时间和一个间隙持续时间，但是以毫秒为单位有多长？我在以相当快的速度输入 100 个域名时进行了测量，发现 p99 对我来说为 121 毫秒。这是我的结果。您可以开始输入以查看它适合您。我们可以多快地开发 API？好的，我们的延迟目标是 121 毫秒。但是我们能够以多快的速度开发 API？我使用此 API 的前 100 万个最流行域的 Tranco 列表。应首先建议这些域名，并辅之以当前使用的任何其他域名。 CZDS 提供大多数 gTLD（例如 .com、.net、.org）的所有域名列表。遗憾的是，ccTLD（例如 .uk、.de、.fr）不可用。但无论如何，那些具有任何有意义流量的域名都会出现在 Tranco 列表中。还有其他来源，例如我们可以使用证书透明度日志和 Archive.org，但我尚未集成它们。我将 API 设计为首先搜索 Tranco（头部），然后在必要时搜索 CZDS（尾部）。结果按排名顺序返回，因此前 8 名最受欢迎。 Head：内存中的字符特里。 trie（前缀树）存储为每个前缀预先计算的前 8 个建议。前缀查找是几个指针的遍历。最坏情况时间复杂度： O(您输入的内容的长度) 。 Tail：SSD 支持的内存映射块索引。 CZDS 域被排序并增量压缩为具有微小内存目录的固定大小的块。查找对目录 (27 MB) 进行二进制搜索，然后线性扫描一个块