mufassall

Шпаргалка · Целые системы

Проектируем поисковые подсказки (autocomplete)

13 мин · Средний · mufassall.dtwin.uz/ru/l/design-search-autocomplete/

← Открыть урок

Проблема

Каждое нажатие в строке поиска просит десять подсказок, и ответ должен прийти раньше следующей клавиши. Строим систему по шагам: бюджет, почему `LIKE 'pre%'` не справляется, trie с заранее посчитанным top-k, шарды по префиксу, debounce и CDN, офлайн-пайплайн с атомарной подменой индекса, слой реального времени для трендов, фильтрация и цена персонализации.

Чему вы научитесь

  • Как превратить нажатия клавиш в поток запросов и бюджет задержки
  • Почему префиксное дерево с top-k в каждом узле обгоняет запрос к базе
  • Как debounce, кэш на клиенте и CDN снимают большую часть запросов до бэкенда
  • Как офлайн-пайплайн, атомарная подмена индекса и маленький слой реального времени держат подсказки свежими и чистыми
Итоговая сцена
35%40%50%20%30%50%50%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в 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_trend

Mermaid: последовательность запросов

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 OK

D2

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_trend

PlantUML: последовательность запросов

@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
@enduml

PlantUML: компоненты

@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/день

Шаги

  1. Кейс Десять подсказок на нажатие, до следующей клавиши

    Пусть 25 миллионов поисков в день, в среднем 12 нажатий на каждый: 300 миллионов вызовов suggest в день, 3 500/s в среднем и вчетверо больше в вечерний пик.

  2. Проблема LIKE 'ip%' читает миллионы строк, чтобы вернуть десять

    B-tree индекс на query умеет найти, где начинается диапазон ip.

  3. Решение Trie, где ответ уже лежит в каждом узле

    В trie (префиксном дереве) на каждый префикс свой узел: i, затем ip, затем iph.

  4. Решение Шардируем индекс по диапазону префиксов

    Полному trie нужно около 60 GB — многовато для одного процесса и одного CPU в вечерний пик.

  5. Проблема Каждое нажатие — запрос

    В вечерний пик API получает 14 000 запросов/s.

  6. Решение Большинство запросов не доходит до бэкенда

    Три слоя, от самого дешёвого.

  7. Решение Логи запросов становятся следующим индексом

    Каждый поиск, который пользователь действительно отправил, уходит в поток лога запросов, без ожидания ответа.

  8. Решение Грузим новый trie рядом со старым и меняем один указатель

    Каждый шард скачивает свой новый снапшот в свободную память, продолжая обслуживать старый.

  9. Решение Маленький слой реального времени для того, что горячо сейчас

    Второй потребитель читает тот же лог запросов и держит в памяти счётчики за последние пять минут.

  10. Решение Фильтруем до того, как что-то покажем

    Подсказки — это слова, которые мы сами ставим перед пользователем, и обращаться с ними надо как с любым контентом.

  11. Кейс Персонализация бьёт по кэшу

    Продукт хочет видеть сверху прошлые поиски самого пользователя.

  12. Итоги Итог

    Autocomplete — гонка со следующим нажатием: около 100 ms от начала до конца, 20 ms на сервере.

Термины

Trie (префиксное дерево)
Дерево с узлом на каждый префикс; цена поиска зависит от длины префикса, а не от объёма данных.
Top-k
Заранее посчитанный список k лучших результатов, чтобы не сортировать во время запроса.
Debounce
Отправлять запрос только после короткой паузы с последнего события, так серия быстрых нажатий даёт один запрос.