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。预算有多大？我们现在知道我们可以花费两个按键持续时间和一个间隙持续时间，但是以毫秒为单位有多长？我在以相当快的速度输入 100 个域名时对其进行了测量，发现 p99 对我来说为 121 毫秒。这是我的结果。您可以开始输入以查看它适合您。测量延迟预算 这测量从一次按键到下一次释放的时间。滑块告诉您在给定的 API 延迟下将渲染下一帧的击键百分比是多少。 121 毫秒 — 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) 进行二进制搜索，然后线性扫描 256 个名称的一个块。 240M的域名大约占用2.5GB的磁盘空间。热点页由操作系统缓存在内存中。最坏情况时间复杂度：O(您输入的内容的长度 * log(dom 的数量