通过预加载和即时渲染技术，实现了对2.4亿域名的自动补全功能，用户按键时提前获取建议，释放时立即显示结果，达到近乎零延迟的体验。

好的，这是根据您的要求，对原文进行的中文重述，保留了核心细节，并删减了与主题无关的评论性内容。

标题：为2.4亿个域名实现p99延迟为0毫秒*的自动补全

*关于这个星号，我们稍后会解释。

我运营着一个名为Wirewiki.com的网站，用于检查域名等互联网基础设施。为了在众多同类网站中脱颖而出，我专注于提升工具质量和用户体验。

自动补全是Wirewiki的主要导航方式，因此它必须尽可能完整、准确和快速。我的目标是让它实现“即时”响应，也就是在下一帧画面就显示出结果。我基本实现了这个目标。

实现方法如下：

当用户按下按键时，我们会预取当前输入字符以及下一个可能字符的搜索建议。当用户松开按键时，我们则渲染并显示这些建议。

API会返回当前查询的结果，以及一个包含所有可能后续字符（如“-”、“.”、“0”到“9”、“a”到“z”等）及其对应建议的“next”对象。

这为我们赢得了时间预算：即“第一次按键持续时间 + 两次按键间隔 + 第二次按键持续时间”。如果API在第二次按键结束前返回结果，那么用户就感觉不到延迟。

（一个60Hz的显示器每16.7毫秒刷新一次，所以理论上我们还有额外的预算，但p99的预算接近0毫秒。）

API往返时间

请求在按下“i”键的瞬间发出；如果响应在“k”键松开前到达，那么“wik”的补全结果就会以零感知延迟呈现。

因此，本文将延迟定义为“从松开按键到结果准备好渲染的时间”。p99为0毫秒意味着，99%的情况下，结果会在用户松开按键之前就已经准备就绪。

这需要两个条件： 1. 客户端预取和缓存建议。 2. 一个足够快的API。

时间预算有多大？

我通过快速输入100个域名进行了测量，发现对我来说，p99的时间预算为121毫秒。

API能有多快？

我的API使用Tranco列表（前100万个最流行域名）作为主要数据源，并辅以ICANN的CZDS（提供大多数通用顶级域名的列表）。API设计为先搜索Tranco列表（头部数据），如有必要再搜索CZDS（尾部数据），结果按流行度排序。

• 头部数据：内存中的字符Trie树。 这种前缀树为每个前缀预计算并存储了前8个建议。查找一个前缀只需遍历几个指针，最坏情况下的时间复杂度为O(输入长度)。
• 尾部数据：基于SSD的内存映射块索引。 CZDS域名经过排序和增量压缩，存储在固定大小的块中，并有一个很小的内存目录。查找时，先对27MB的目录进行二分搜索，然后线性扫描一个包含256个域名的块。2.4亿个域名占用约2.5GB磁盘空间，热数据由操作系统缓存在内存中。最坏情况下的时间复杂度为O(输入长度 * log(域名数量))。

由于查询长度和域名数量都有上限，这两种数据结构的最坏情况实际上都是O(1)，这有助于保持低延迟。

压力测试结果

我使用LLM对生产服务器进行了压力测试，模拟了6万个域名的72万次按键查询。

结果显示，大多数请求在2毫秒内得到API响应。即使在每秒1600个请求的速率下，通过Nginx和API的响应，p99延迟也仅为15毫秒。

我认为API的优化已经足够，因为网络延迟已成为主导因素。实际上，自动补全的延迟大约等于“浏览器到服务器的往返时间 + 10毫秒”。

挑战与结论

端到端延迟在我们的预算之内，即使1000人同时输入也是如此。但问题在于，我的服务器仅部署在欧洲。因此，来自更远地区（如美国）的流量会增加100-200毫秒的延迟，超出预算。

通过CDN缓存热门路径和利用尼尔森的0.1秒“瞬时”阈值可以缓解这个问题，但不足以完全达到目标。

我可以设置多台服务器并进行地理负载均衡，以实现p99为0毫秒*的延迟。但对我来说，这有点过了。如果我要把这个做成一个产品，我会这么做。不过，我认为这个功能过于小众，难以建立商业模式。但如果您愿意为使用此API付费，请发邮件给我，我可能会改变主意。

*注：星号指代的是，对于远离服务器的用户，延迟可能无法达到0毫秒。

根据评论内容，主要观点和论据如下：

1. 对延迟测量的质疑（评分：无） - 评论1：认为方法巧妙，但不符合延迟测量标准。 - 评论6：质疑实际延迟约为500毫秒，而非声称的即时响应。 - 评论7：澄清“即时”应理解为<1毫秒，而非字面意义。

2. 对用户体验的批评（评分：无） - 评论4：指出KeyDown事件在移动设备上效果不佳。 - 评论10：批评使用keyup而非keydown，认为这引入额外延迟，不符合用户预期。 - 评论11：建议在keyDown时触发请求，keyUp时显示结果，以减少延迟。

3. 对自动补全功能的质疑（评分：无） - 评论9：指出自动补全会建议不存在的域名，输入垃圾字符也会返回结果，降低防错功能。 - 评论12：同样质疑结果真实性，输入随机字符仍返回建议，难以区分合法与虚假结果。

4. 对技术实现的改进建议（评分：无） - 评论2：建议将问题框架化为优化问题，使用完整字母字典并添加基于流行度的残差预测，预存树结构以降低延迟。 - 评论8：提议将每个trie节点存储为文件，利用CDN查找实现遍历，减少网络延迟。

5. 对工具实用性的肯定（评分：无） - 评论3：认为自动补全功能之外，该工具本身很实用。 - 评论5：承认API速度令人印象深刻，但指出粘贴、IME或语音输入时的局限性。

关键引用（保留中英文）： - 评论1：“Clever but that’s not how we measure latency.”（巧妙，但这不是我们测量延迟的方式。） - 评论9：“This autocomplete suggests domains that don't exist... it will suggest something, but then if you go there, there are no records.”（自动补全会建议不存在的域名...会建议一些内容，但访问时没有记录。） - 评论10：“Using keyup makes no sense and is inconsistent with user expectations... It is in fact introducing latency by using keyup instead of keydown.”（使用keyup毫无意义，且不符合用户预期...实际上通过使用keyup而非keydown引入了延迟。） - 评论2：“I think you could get a lot closer by framing this as an optimization problem... weighted by popularity.”（我认为通过将其框架化为优化问题，可以更接近目标...按流行度加权。）