Как сделать автодополнение, которое работает быстрее мысли

Замечали, как поисковая строка угадывает ваши мысли раньше, чем вы допечатали слово? Это не магия — это инженерия. И задача становится по-настоящему интересной, когда у вас 240 миллионов доменов в базе.

Почему скорость — это всё

Когда вы печатаете, то ожидаете мгновенный отклик. Исследователи из Nielsen Norman Group установили порог в 0,1 секунды — после этого интерфейс начинает казаться «тупым». Пользователь выпадает из потока, раздражается и уходит.

Для инструмента проверки доменов автодополнение — это главные ворота. Каждая миллисекунда на счету. Юзер должен чувствовать, что инструмент читает его мысли, а не ждёт ответа от сервера.

Фокус с предварительной загрузкой

Суть не в том, чтобы ускорить API (хотя это тоже полезно). Главное — украсть время у самого процесса печати.

Когда пользователь нажимает клавишу (keyDown), система уже подгружает подсказки для текущего ввода и предполагаемого следующего символа. При отпускании (keyUp) отображается то, что успело загрузиться. Итог: ваш бюджет времени — это не латентность API, а длительность двух нажатий плюс пауза между ними.

На экране 60Hz у вас 16,7 мс на кадр. Для быстрых печатующих на p99 бюджет составляет примерно 121 мс. Вот это ваше окно. Успели подготовить данные до конца второго нажатия — юзер видит «мгновенный» отклик.

Архитектура для скорости на масштабе

240 миллионов доменов — серьёзная цифра. Хитрость в том, чтобы обрабатывать популярные домены иначе, чем остальные:

Горячая часть: Топовые домены лежат в trie-структуре прямо в оперативной памяти. Поиск по префиксу — просто обход указателей. Топ-8 подсказок для любого префикса уже предпосчитаны. Худший случай? O(длина ввода). То есть копейки.

Холодная часть: Всё остальное живёт на SSD с memory-mapped индексом. Домены отсортированы, дельта-сжаты и упакованы в блоки фиксированного размера. Небольшая служебная таблица в RAM позволяет делать бинарный поиск. Все 240M доменов занимают около 2,5 ГБ, а операционная система сама кеширует горячие блоки.

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

Цифры

Нагрузочное тестирование показало интересную картину. Сам API отвечает быстрее 2 мс. Даже под нагрузкой в 1600 запросов в секунду связка Nginx плюс API укладывается в 15 мс на p99. Неплохо.

Но тут в дело вступает реальность: сеть. Итоговая задержка складывается из round-trip time от браузера через Cloudflare до сервера плюс примерно 10 мс накладных расходов. Для пользователей в том же регионе — всё в бюджете. Для остальных? Вот где появляется звёздочка.

Звёздочка

p99 0 мс* означает, что 99% запросов возвращают результат до того, как юзер отпустит клавишу — при условии, что он рядом с сервером. Добавьте 100-200 мс трансатлантической задержки, и бюджет улетает.

Решение — геораспределённые серверы с балансировкой нагрузки. Но для побочного проекта это тонны инфраструктуры, которую нужно поддерживать. Иногда «достаточно хорошо» — это и есть достаточно хорошо, особенно если ваша целевая аудитория — европейские разработчики, проверяющие домены.

Что это значит для вашего проекта

Урок, который выходит далеко за пределы поиска доменов: предзагружайте умно. Если вы знаете, что пользователь может запросить следом — загружайте до того, как он попросит. Пусть интерфейс реагирует на готовые данные, а не ждёт стопроцентной уверенности.

Второй урок — выбор структур данных. Trie для горячих данных, хорошо проиндексированная сортировка для остальных. Не нужно держать 240 миллионов записей в оперативке, если вы спроектируете доступ вокруг реальных паттернов запросов.

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

Результат ощущается как магия. Но начинается он с понимания того, сколько времени у вас реально есть.