Фундамент системы — это trie (префиксное дерево), где каждый узел представляет символ и хранит топ-N ранжированных подсказок для этого префикса. Это позволяет избежать полного обхода при каждом нажатии клавиши и обеспечивает экстремально быстрый поиск.
Чтобы стабильно укладываться в 100ms:
Подсказки ранжируются с помощью взвешенной модели оценки, которая объединяет:
Легковесный сервис профиля пользователя хранит недавние поиски и предпочтения. При ранжировании персональные сигналы смешиваются с глобальными оценками на лету, а основное trie остаётся stateless и общим для всех пользователей.
Trie шардируется по диапазону префиксов на несколько узлов (например, узел A обрабатывает a–m, узел B обрабатывает n–z). Каждый шард реплицируется для отказоустойчивости. Слой consistent hashing маршрутизирует каждый запрос на нужный шард.
Пайплайн потоковой обработки (например, Kafka + Flink) непрерывно принимает новые запросы и обновляет оценки подсказок. Вместо прямого изменения живого trie, обновления применяются к shadow trie и атомарно подменяются по расписанию — чтобы избежать конфликтов чтения/записи.
Ключевой trade-off — консистентность vs. задержка — слегка устаревшие подсказки вполне допустимы в обмен на практически мгновенные и масштабируемые ответы.
В trie-based системе автодополнения каждый узел хранит топ-N рейтинговых подсказок для данного префикса, чтобы избежать полного обхода при каждом нажатии клавиши, что является основным механизмом достижения задержки менее 100ms.
Новый — ещё не проверен сообществом
Вы