Разработчик сервиса Wirewiki.com — сайта для проверки интернет-инфраструктуры, DNS-записей, делегирования доменов и конфигурации email-доставки — поделился техническими деталями реализации автодополнения доменных имён. Задача звучала просто: сделать поиск максимально полным, точным и быстрым, чтобы результаты появлялись мгновенно — буквально в следующем кадре.

Автодополнение — основной способ навигации по Wirewiki, поэтому к его скорости предъявлялись повышенные требования. На фоне растущего числа похожих сервисов (отчасти благодаря буму «vibe coding») выделиться решили за счёт качества инструмента и удобства использования.

Как это работает

При нажатии клавиши (keyDown) браузер заранее запрашивает подсказки для введённого символа и для всех возможных следующих символов. А когда клавиша отпускается (keyUp), результаты уже готовы к отрисовке.

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"]
}
}

Таким образом получается временной бюджет: длительность первого нажатия + пауза между нажатиями + длительность второго нажатия. Если API успевает ответить до окончания второго нажатия — результаты будут готовы вовремя.

(Дисплей с частотой 60 Гц обновляет кадр каждые 16,7 мс. Формально это даёт дополнительные 8,33 мс запаса на уровне p50, но почти 0 мс на уровне p99.)

Запрос для q=wi отправляется в момент нажатия i; если ответ приходит до того, как отпущена k, подсказки для wik отрисовываются с нулевой ощутимой задержкой.

Для целей этой заметки задержка определяется как интервал от keyUp до готовности результатов к отрисовке. P99 0 мс означает, что в 99% случаев результаты будут готовы ещё до того, как пользователь отпустит клавишу.

Для этого нужны две вещи:

  1. Предзагрузка и кэширование подсказок на клиенте, и
  2. Достаточно быстрый API.

А как насчёт трафика?

Изначально это вызывало опасения. Но на практике проблемы не возникло. Всего существует 38 допустимых символов для доменных имён: a-z, 0-9, - и .. Это задаёт верхний предел в (38 + 1) * 8 = 312 доменных имён в ответе.

На практике это выливается максимум в около 5 кБ данных на запрос. После сжатия по сети передаётся около 2,5 кБ.

Если считать, что 50-100 кБ — это нормальный размер картинки, эквивалентом будет ввод 20-40 символов.

Никогда не задумываюсь дважды перед тем, как добавить картинку на страницу из-за трафика, так что таким расходом вполне доволен.

Насколько велик бюджет?

Теперь известно, что доступны две длительности нажатия клавиш и пауза между ними, но сколько это в миллисекундах?

Замер проводился при вводе 100 доменных имён в достаточно быстром темпе — p99 составил 121 мс.

Насколько быстрым можно сделать API?

Итак, целевая задержка — 121 мс. Но насколько быстрым реально можно сделать API?

Для этого API используется список Tranco — топ-1 миллион самых популярных доменов. Эти домены должны предлагаться первыми, дополняясь любыми другими используемыми доменными именами.

CZDS предоставляет список всех доменов для большинства gTLD (например, .com, .net, .org). ccTLD (например, .uk, .de, .fr), к сожалению, недоступны. Но домены из этих зон с хоть сколько-нибудь значимым трафиком всё равно попадут в список Tranco. Есть и другие источники — логи прозрачности сертификатов, Archive.org, — но пока они не интегрированы.

API устроен так: сначала поиск по Tranco (голова списка), затем при необходимости — по CZDS (хвост списка). Результаты возвращаются в порядке ранжирования, поэтому первые 8 — самые популярные.

Голова: character trie в памяти. Trie (префиксное дерево) хранит топ-8 подсказок, предвычисленных для каждого префикса. Поиск по префиксу — это проход по нескольким указателям.
Худшая временная сложность: O(длина введённого текста).

Хвост: блочный индекс на SSD с memory-mapped доступом. Домены CZDS отсортированы и дельта-сжаты в блоки фиксированного размера с небольшим каталогом в памяти. Поиск делает бинарный поиск по каталогу (27 МБ), затем линейно сканирует один блок из 256 имён. 240 миллионов доменных имён занимают около 2,5 ГБ на диске. Часто используемые страницы кэшируются в памяти операционной системой.
Худшая временная сложность: O(длина введённого текста * log(количество доменов)).

И количество доменов, и длина запроса ограничены. Это делает худший случай для обеих структур данных фактически O(1), что должно удерживать задержку p99 на низком уровне. Проверим это на практике.

Каждое нажатие клавиши проходит путь Браузер → Cloudflare → nginx → API, и ответ возвращается тем же путём.

Продакшн-сервер тестировался под нагрузкой с помощью LLM: сгенерировано 720 тысяч запросов на нажатия клавиш путём симуляции ввода 60 тысяч доменных имён, воспроизведённых в режиме открытого цикла (запросы отправлялись с фиксированной целевой частотой независимо от скорости ответов). API тестировался изолированно, через Nginx и end-to-end.

Большинство запросов API обрабатывает в пределах 2 мс. Даже при нагрузке 1,6 тысячи запросов в секунду связка Nginx + API отвечает за 15 мс в 99% случаев.

Наверняка ещё можно сэкономить пару миллисекунд, но этот результат вполне устраивает. Дальнейшая оптимизация API не имеет большого смысла, поскольку основной вклад в задержку вносит сеть.

На практике задержка автодополнения примерно равна времени round-trip от браузера через Cloudflare до сервера плюс 10 мс.

Round-trip через Cloudflare добавляет заметную задержку, но зато поглощает частые повторяющиеся запросы.

В тестах итоговая end-to-end задержка укладывается в бюджет — даже когда 1000 человек печатают одновременно.

Проблема в том, что сервер всего один и расположен в Европе. Поэтому трафик из более отдалённых регионов будет превышать бюджет на уровне p99. Трафик из США, например, добавит 100-200 мс.

Кэширование горячих путей на CDN и порог «мгновенности» в 0,1 секунды по Нильсену во многом компенсируют это, но недостаточно, чтобы уложиться в целевой показатель.

Можно было бы развернуть несколько серверов с гео-балансировкой трафика — это дало бы честные p99 0 мс*. Но это уже перебор. Даже для такого проекта.

Такой шаг имело бы смысл сделать, если превращать это в продукт. Но ниша выглядит слишком узкой для отдельного бизнеса. Тем не менее, желающие платить за доступ к этому API могут написать — возможно, это изменит ситуацию.

И да, именно такую планку по UX разработчик поставил себе для Wirewiki — если есть идеи, что можно улучшить, обратная связь приветствуется.