我们会提到星号。我经营着Wirewiki.com，这是一个用来检查互联网基础设施（例如域名）的网站。它帮助人们检查（历史）DNS记录、DNS委派、电子邮件投递配置等。许多网站提供这种服务（由于潮流编码的影响，这一趋势增长得比以往更快），所以我需要一种方式来脱颖而出。我选择了工具的质量/实用性和用户体验。自动完成是导航Wirewiki的主要方式，因此它应该尽可能完整、准确和快速。我希望它是即时的。就像下一个帧那样的即时。我大多数情况下已经达到了这一点。你可以试试自己：Tab 循环选项卡 导航 打开 方法如下。在键按下时（用户开始按下一个键），我们预取输入字符及任何下一个字符的建议。在键释放时（用户松开键），我们会渲染建议。GET /autocomplete?q=wi { "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" ] } } 这给我们留出键按下1持续时间 + 键按下之间的间隔 + 键按下2持续时间的时间预算。如果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'的完成就能以零感知延迟进行渲染。因此，出于本文的目的，我们将延迟定义为从键释放到结果准备好进行渲染的时间。 p99 0毫秒意味着在99%的时间里，结果会在用户释放键之前准备好。为了实现这一点，我们需要两件事：客户端的预取和建议的缓存，以及一个足够快速的API。 预算有多大？我们现在知道我们可以消耗两个按键持续时间和一个间隔持续时间，但这在毫秒中有多长？我在合理快速地输入100个域名的同时测量了它，发现对于我来说p99的持续时间是121毫秒。以下是我的结果。你可以开始输入，以看看你自己的数值。 我们能把API做得多快？好的，所以我们的延迟目标是121毫秒。但是我们能把API做得多快呢？我使用Tranco前100万最受欢迎域名的列表作为这个API。这些应该首先建议，并补充任何当前正在使用的其他域名。 CZDS提供大多数gTLD（像.com，.net，.org）的所有域名的列表。ccTLD（例如.uk，.de，.fr）不幸的是不可用。但对那些有任何有意义的流量的域名来说，无论如何将在Tranco列表中。还有其他来源，比如证书透明度日志和Archive.org，我们可以使用，但我还没有整合它们。 我设计API首先搜索Tranco（头部），然后在必要时搜索CZDS（尾部）。结果按排名顺序返回，因此前8个是最流行的。头部：内存中字符前缀树。前缀树存储每个前缀预计算的前8个建议。一个前缀查找是几个指针的行走。最坏情况时间复杂度为：O（你输入的内容的长度）。尾部：SSD支持的内存映射块索引。CZDS域名被排序并以固定大小块进行增量压缩，并带有一个小的内存目录。查找通过二分搜索目录（27 MB），然后线性扫描一个256个名称的块。240M域名大约占用2.5 GB的磁盘空间。热点页面由操作系统缓存于内存。最坏情况时间复杂度为：O（你输入的内容的长度 * log（域名数量））。这两个数据结构中域名数量和查询长度都是有限制的。这使得这两个数据结构的最坏情况实际上为O(1)，这应该保持p99延迟低。我们来看看。 浏览器wik| Cloudflare全球边缘缓存 Wirewiki服务器 nginx TLS · 代理API 自动完成每个键击都经过 浏览器 → Cloudflare → nginx → API，响应沿同一路径返回。我曾有一个L