Шпаргалка · Целые системы
Проектируем поисковые подсказки (autocomplete)
Проблема
Каждое нажатие в строке поиска просит десять подсказок, и ответ должен прийти раньше следующей клавиши. Строим систему по шагам: бюджет, почему `LIKE 'pre%'` не справляется, trie с заранее посчитанным top-k, шарды по префиксу, debounce и CDN, офлайн-пайплайн с атомарной подменой индекса, слой реального времени для трендов, фильтрация и цена персонализации.
Чему вы научитесь
- Как превратить нажатия клавиш в поток запросов и бюджет задержки
- Почему префиксное дерево с top-k в каждом узле обгоняет запрос к базе
- Как debounce, кэш на клиенте и CDN снимают большую часть запросов до бэкенда
- Как офлайн-пайплайн, атомарная подмена индекса и маленький слой реального времени держат подсказки свежими и чистыми
Диаграмма как код
Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).
Mermaid: схема
flowchart LR
n_user(["Строка поиска"])
n_api["Suggest API"]
n_index{{"Шард индекса 1"}}
n_index2{{"Шард индекса 2"}}
n_cdn[/"CDN edge"\]
n_queue[["Лог запросов"]]
n_agg("Агрегация")
n_storage[("Снапшоты")]
n_trend{{"Тренды 5 мин"}}
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn -.-> n_user
n_cdn --> n_api
n_api -->|"асинхронно"| n_queue
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trendMermaid: последовательность запросов
sequenceDiagram
participant n_user as Строка поиска
participant n_api as Suggest API
participant n_db as База запросов
participant n_index as Шард индекса 1
participant n_cdn as CDN edge
participant n_agg as Агрегация
participant n_storage as Снапшоты
participant n_trend as Тренды 5 мин
participant n_queue as Лог запросов
Note over n_user,n_api: Десять подсказок на нажатие, до следующей клавиши
n_user->>n_api: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_api-->>n_user: HTTP/1.1 200 OK
Note over n_api,n_db: LIKE 'ip%' читает миллионы строк, чтобы вернуть десять
n_api->>n_db: EXPLAIN ANALYZE
n_db-->>n_api: Limit (actual time=611.4..611.5 rows=10)
Note over n_api,n_index: Trie, где ответ уже лежит в каждом узле
n_api->>n_index: lookup prefix=#34;ip#34;
n_index-->>n_api: walk root -#62; i -#62; p (2 hops)
Note over n_api,n_index: Шардируем индекс по диапазону префиксов
n_api->>n_index: shard map v7 (split by traffic, not alphabet)
n_index-->>n_api: [a, iq) -#62; idx-1 heap 29 GB 49% of traffic
Note over n_user,n_api: Каждое нажатие — запрос
n_user->>n_api: 18:14:02.110 GET /suggest?q=i
Note over n_user,n_cdn: Большинство запросов не доходит до бэкенда
n_user->>n_cdn: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OK
Note over n_agg,n_storage: Логи запросов становятся следующим индексом
n_agg->>n_storage: agg output window=2026-11-17T08:00Z/1h
Note over n_storage,n_index: Грузим новый trie рядом со старым и меняем один указатель
n_storage->>n_index: 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
Note over n_api,n_trend: Маленький слой реального времени для того, что горячо сейчас
n_api->>n_trend: trend.match prefix=#34;st#34; window=5m
n_trend-->>n_api: storm warning 1 812 / 5m x46 vs usual
Note over n_queue,n_trend: Фильтруем до того, как что-то покажем
n_queue->>n_trend: filter drop #34;cheap pills now#34; from trend:en
n_trend-->>n_queue: rule blocklist match (spam)
Note over n_user,n_cdn: Персонализация бьёт по кэшу
n_user->>n_cdn: GET /suggest?q=iph#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OKD2
direction: right
n_user: "Строка поиска" {
shape: rectangle
}
n_api: "Suggest API" {
shape: rectangle
}
n_index: "Шард индекса 1" {
shape: hexagon
}
n_index2: "Шард индекса 2" {
shape: hexagon
}
n_cdn: "CDN edge" {
shape: oval
}
n_queue: "Лог запросов" {
shape: queue
}
n_agg: "Агрегация" {
shape: rectangle
style.multiple: true
}
n_storage: "Снапшоты" {
shape: stored_data
}
n_trend: "Тренды 5 мин" {
shape: hexagon
}
n_api -> n_index
n_api -> n_index2
n_user -> n_cdn
n_cdn -> n_user {
style.stroke-dash: 3
}
n_cdn -> n_api
n_api -> n_queue: "асинхронно"
n_queue -> n_agg
n_agg -> n_storage
n_storage -> n_index
n_storage -> n_index2
n_queue -> n_trend
n_api -> n_trendPlantUML: последовательность запросов
@startuml
participant "Строка поиска" as n_user
participant "Suggest API" as n_api
database "База запросов" as n_db
collections "Шард индекса 1" as n_index
participant "CDN edge" as n_cdn
participant "Агрегация" as n_agg
database "Снапшоты" as n_storage
collections "Тренды 5 мин" as n_trend
queue "Лог запросов" as n_queue
note over n_user, n_api : Десять подсказок на нажатие, до следующей клавиши
n_user -> n_api : GET /suggest?q=ip&lang=en HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
note over n_api, n_db : LIKE 'ip%' читает миллионы строк, чтобы вернуть десять
n_api -> n_db : EXPLAIN ANALYZE
n_db --> n_api : Limit (actual time=611.4..611.5 rows=10)
note over n_api, n_index : Trie, где ответ уже лежит в каждом узле
n_api -> n_index : lookup prefix="ip"
n_index --> n_api : walk root -> i -> p (2 hops)
note over n_api, n_index : Шардируем индекс по диапазону префиксов
n_api -> n_index : shard map v7 (split by traffic, not alphabet)
n_index --> n_api : [a, iq) -> idx-1 heap 29 GB 49% of traffic
note over n_user, n_api : Каждое нажатие — запрос
n_user -> n_api : 18:14:02.110 GET /suggest?q=i
note over n_user, n_cdn : Большинство запросов не доходит до бэкенда
n_user -> n_cdn : GET /suggest?q=ip&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
note over n_agg, n_storage : Логи запросов становятся следующим индексом
n_agg -> n_storage : agg output window=2026-11-17T08:00Z/1h
note over n_storage, n_index : Грузим новый trie рядом со старым и меняем один указатель
n_storage -> n_index : 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
note over n_api, n_trend : Маленький слой реального времени для того, что горячо сейчас
n_api -> n_trend : trend.match prefix="st" window=5m
n_trend --> n_api : storm warning 1 812 / 5m x46 vs usual
note over n_queue, n_trend : Фильтруем до того, как что-то покажем
n_queue -> n_trend : filter drop "cheap pills now" from trend:en
n_trend --> n_queue : rule blocklist match (spam)
note over n_user, n_cdn : Персонализация бьёт по кэшу
n_user -> n_cdn : GET /suggest?q=iph&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
@endumlPlantUML: компоненты
@startuml
left to right direction
agent "Строка поиска" as n_user
component "Suggest API" as n_api
stack "Шард индекса 1" as n_index
stack "Шард индекса 2" as n_index2
frame "CDN edge" as n_cdn
queue "Лог запросов" as n_queue
collections "Агрегация" as n_agg
storage "Снапшоты" as n_storage
stack "Тренды 5 мин" as n_trend
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn ..> n_user
n_cdn --> n_api
n_api --> n_queue : асинхронно
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trend
@endumlИтог
Autocomplete — гонка со следующим нажатием: около 100 ms от начала до конца, 20 ms на сервере.
1) Считайте нажатия, а не поиски: 3 500/s в среднем, 14 000/s в пик. 2) LIKE 'pre%' читает все совпадения, чтобы их ранжировать; trie с top-k в каждом узле отвечает за микросекунды. 3) Шардируйте по диапазонам префиксов, нарезанным по трафику, с репликами. 4) Debounce, кэш на клиенте и CDN для коротких префиксов снимают большую часть нагрузки. 5) Офлайн-пайплайн превращает логи запросов в снапшоты, которые подменяются атомарно; маленький слой реального времени добавляет тренды. 6) Фильтруйте через blocklist и порог уникальных пользователей; персонализируйте только там, где кэш всё равно не помогает.
Показатели: в начале и в конце
| Показатель | В начале | В конце |
|---|---|---|
| p95 подсказок | 60 мс | 35 мс |
| Запросы на бэкенд | 3 500/с | 3 600/с |
| Отставание свежести | 86 400 с | 60 с |
| Плохие подсказки | 140/день | 3/день |
Шаги
- Кейс Десять подсказок на нажатие, до следующей клавиши
Пусть 25 миллионов поисков в день, в среднем 12 нажатий на каждый: 300 миллионов вызовов suggest в день, 3 500/s в среднем и вчетверо больше в вечерний пик.
- Проблема
LIKE 'ip%'читает миллионы строк, чтобы вернуть десятьB-tree индекс на
queryумеет найти, где начинается диапазонip. - Решение Trie, где ответ уже лежит в каждом узле
В trie (префиксном дереве) на каждый префикс свой узел:
i, затемip, затемiph. - Решение Шардируем индекс по диапазону префиксов
Полному trie нужно около 60 GB — многовато для одного процесса и одного CPU в вечерний пик.
- Проблема Каждое нажатие — запрос
В вечерний пик API получает 14 000 запросов/s.
- Решение Большинство запросов не доходит до бэкенда
Три слоя, от самого дешёвого.
- Решение Логи запросов становятся следующим индексом
Каждый поиск, который пользователь действительно отправил, уходит в поток лога запросов, без ожидания ответа.
- Решение Грузим новый trie рядом со старым и меняем один указатель
Каждый шард скачивает свой новый снапшот в свободную память, продолжая обслуживать старый.
- Решение Маленький слой реального времени для того, что горячо сейчас
Второй потребитель читает тот же лог запросов и держит в памяти счётчики за последние пять минут.
- Решение Фильтруем до того, как что-то покажем
Подсказки — это слова, которые мы сами ставим перед пользователем, и обращаться с ними надо как с любым контентом.
- Кейс Персонализация бьёт по кэшу
Продукт хочет видеть сверху прошлые поиски самого пользователя.
- Итоги Итог
Autocomplete — гонка со следующим нажатием: около 100 ms от начала до конца, 20 ms на сервере.
Термины
- Trie (префиксное дерево)
- Дерево с узлом на каждый префикс; цена поиска зависит от длины префикса, а не от объёма данных.
- Top-k
- Заранее посчитанный список k лучших результатов, чтобы не сортировать во время запроса.
- Debounce
- Отправлять запрос только после короткой паузы с последнего события, так серия быстрых нажатий даёт один запрос.