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

Автодополнение — это задача про задержку, а не про полноту: подсказка, пришедшая за 200 мс, бесполезна, потому что пользователь уже набрал следующую букву. Отсюда решение: не искать по индексу на каждое нажатие, а заранее посчитать топ-N подсказок для каждого префикса и хранить их в памяти как готовый список. Источник популярности — журнал поисковых запросов, агрегированный окнами; словарь обновляется офлайн-задачей раз в несколько минут, а не в реальном времени. Главный компромисс — свежесть против стоимости: предрасчёт даёт единицы миллисекунд на ответ, но подсказки отстают от реальности на длину окна. Узкое место — короткие префиксы: на них приходится основная доля запросов, и их держат в локальном кэше процесса.