title: Алекс Сюй, «System Design. Подготовка к сложному интервью» (Vol. 1, рус. изд.) — глава 13: Автозаполнение поисковых запросов source: materials/System Design. Подготовка к сложному интервью.pdf, стр. 222–243 конспект: TASK-45.38, извлечено pymupdf 2026-09-17; ниже полный «грязный» текст главы + выжимка статус: выжимка и перенос в knowledge-base.md / methodology.md / classic-designs.md — см. _map.md

Глава 13. Автозаполнение поисковых запросов

Выжимка

Автодополнение поиска: совпадение по началу запроса, топ-5 по популярности, <100 мс, 10 млн DAU. Оценки: 10M × 10 запросов × 20 символов ≈ 24k QPS (пик 48k); 0.4 ГБ/день новых запросов.

Наивно: частотная таблица + SQL ORDER BY frequency LIMIT 5 — БД становится узким местом.

Trie (префиксное дерево): узлы = символы, на «полных» запросах — частоты. Алгоритм: найти префикс O(p) → собрать поддерево O(c) → отсортировать O(c log c). Оптимизации до O(1): (1) ограничить максимальную длину префикса (пользователи не вводят сотни символов); (2) кэшировать топ-k запросов прямо в каждом узле (памяти больше, зато ответ мгновенный).

Сбор данных (off-line): логи анализа → агрегаторы (частоты за период; для Twitter — реальное время, для Google хватит еженедельно) → рабочие узлы строят trie → БД trie (документная MongoDB-снимок или KV: «префикс → список») → кэш trie в памяти. Запрос: LB → API → кэш trie → топ-5.

Масштабирование: шардирование trie по диапазонам префиксов (a–m / n–z...). Остальное: фильтрация нежелательных запросов, кэширование на клиенте, локализация.

Перенос: KB §14.8 (trie + топ-k в узлах + offline-пересборка).

Полный текст (грязная выгрузка)

13 ПРОЕКТИРОВАНИЕ СИСТЕМЫ АВТОЗАПОЛНЕНИЯ ПОИСКОВЫХ ЗАПРОСОВ При вводе запроса в поисковиках или интернет-магазинах пользователь часто видит один или несколько всплывающих вариантов слов или их сочетаний. Эту функцию называют автозаполнением, опережающим вводом, поиском по мере ввода или инкрементальным поиском. На рис. 13.1 показан пример того, как при вводе в поле поиска слова dinner Google выводит список вариантов автозаполнения. Эта полезная возможность доступна во многих продуктах, что подводит нас к следующей задаче: спроектируйте систему автозаполнения. На интервью также встречают­ ся ее разновидности: «Реализуйте алгоритм топ-k» или «Сформируйте список из k самых популярных поисковых запросов». Рис. 13.1

Проектирование системы автозаполнения поисковых запросов      223 ШАГ 1: ПОНЯТЬ ЗАДАЧУ И ОПРЕДЕЛИТЬ МАСШТАБ РЕШЕНИЯ Решение любой задачи на интервью по проектированию ИТ-систем на­ чинается с прояснения требований. Для этого нужно задать достаточное количество уточняющих вопросов. Вот пример диалога между кандида­ том и интервьюером: Кандидат: «Сопоставление поддерживается только в начале поис­ кового запроса или также в середине?» Интервьюер: «Только в начале поискового запроса». Кандидат: «Сколько вариантов автозаполнения должна возвращать система?» Интервьюер: «5». Кандидат: «Как система определяет, какие 5 вариантов нужно вер­ нуть?» Интервьюер: «В зависимости от популярности, основанной на стати­ стике частоты запросов». Кандидат: «Поддерживает ли система проверку орфографии?» Интервьюер: «Проверка орфографии и автозамена не поддержива­ ются». Кандидат: «Поисковые запросы выполняются на английском язы­ ке?» Интервьюер: «Да. Если в конце останется время, мы обсудим под­ держку разных языков». Кандидат: «Допускаются ли прописные буквы и специальные сим­ волы?» Интервьюер: «Нет, мы исходим из того, что все поисковые запросы состоят из алфавитных символов в нижнем регистре». Кандидат: «Сколько пользователей у этого продукта?» Интервьюер: «10 миллионов DAU».

224      ГЛАВА 13 Требования Вот краткий список требований.

Короткое время ответа. Варианты автозаполнения должны отобра­ жаться достаточно быстро по мере того, как пользователь вводит поисковый запрос. В статье [1] говорится, что система автозаполне­ ния в Facebook должна возвращать результаты в течение 100 мил­ лисекунд. В противном случае возникают задержки.

Актуальность. Варианты автозаполнения должны иметь отношение к поисковому запросу.

Сортировка. Результаты, возвращаемые системой, должны быть упорядочены по популярности или с использованием других мо­ делей ранжирования.

Масштабирование. Система должна справляться с большим объ­ емом трафика.

Высокая доступность. Система должна оставаться доступной и от­ зывчивой, когда какая-то ее часть выходит из строя, показывает плохую производительность или испытывает неожиданные про­ блемы с сетью. Приблизительные оценки

Ожидается 10 миллионов активных пользователей в день (DAU).

В среднем пользователь выполняет 10 поисковых запросов в день.

Поисковая строка занимает 20 байтов: Š Š предполагается использование кодировки ASCII. Каждый сим­ вол занимает 1 байт; Š Š предполагается, что запрос состоит из 4 слов, в среднем по 5 символов в каждом; Š Š получается 4 × 5 = 20 байтов в каждом запросе.

При вводе в поле поиска каждого символа клиент обращается к серверу за вариантами автозаполнения. В среднем для каждой поисковой строки требуется 20 запросов. Например, при вводе слова dinner сервер получает следующие 6 запросов:

Проектирование системы автозаполнения поисковых запросов      225 search?q=d search?q=di search?q=din search?q=dinn search?q=dinne search?q=dinner

~24 000 запросов в секунду (QPS) = 10 000 000 пользователей * 10 запросов / день * 20 символов / 24 часа / 3600 секунд.

Пиковый показатель QPS = QPS * 2 = ~48 000.

Предполагается, что ежедневно 20 % запросов являются новыми. 10 миллионов * 10 запросов / день / 20 байт на запрос * 20 % = 0,4 Гб. Это означает, что каждый день в хранилище записывается 0,4 Гб новых данных. ШАГ 2: ПРЕДЛОЖИТЬ ОБЩЕЕ РЕШЕНИЕ И ПОЛУЧИТЬ СОГЛАСИЕ Общая архитектура системы состоит из двух сервисов.

Сервис сбора данных. Собирает пользовательские поисковые запросы и накапливает их в режиме реального времени. Для больших наборов данных обработка в реальном времени является нецелесообразной, но она послужит хорошей отправной точкой. Более реалистичное решение будет рассмотрено на следующем этапе.

Сервис запросов. Возвращает 5 самых популярных строк для за­ данного поискового запроса или его начальной части. Сервис сбора данных Чтобы увидеть, как работает сервис сбора данных, рассмотрим упро­ щенный пример. Допустим, у нас есть частотная таблица, содержащая строки и частоту, с которой их ищут, как показано на рис. 13.2. Изна­ чально эта таблица пустая. Затем пользователь вводит по очереди twitch, twitter, twitter и twillo. На рис. 13.2 видно, как обновляется частотная таблица.

226      ГЛАВА 13 Запрос: twitch Запрос: twitter Запрос: twitter Запрос: twillo Запрос Частота Запрос Частота twitch 1 Запрос Частота twitch 1 twitter 1 Запрос Частота twitch 1 twitter 2 Запрос Частота twitch 1 twitter 2 1 twillo Рис. 13.2 Сервис запросов Предположим, что у нас есть следующая частотная таблица (табл. 13.1). Она состоит из двух полей.

«Запрос» хранит строку запроса.

«Частота» показывает, сколько раз искали ту или иную строку. Таблица 13.1 Запрос Частота twitter 35 twitch 29 twilight 25 twin peak 21 twitch prime 18 twitter search 14 twillo 10 twin peak sf 8 Когда пользователь вводит tw в поле поиска, на экране появляется пять самых популярных поисковых запросов (рис. 13.3) при условии, что частотная таблица основана на табл. 13.1.

Проектирование системы автозаполнения поисковых запросов      227 Рис. 13.3 Чтобы получить 5 строк, которые ищут чаще всего, нужно выполнить следующий SQL-запрос: Рис. 13.4 Это приемлемое решение для небольших наборов данных. Если же данных много, обращение к БД становится узким местом. В следующем разделе мы исследуем потенциальные пути оптимизации. ШАГ 3: ПОДРОБНОЕ ПРОЕКТИРОВАНИЕ При описании общей архитектуры мы обсудили сервис сбора данных и сервис запросов. Этот подход не оптимален, но его можно взять за ос­ нову. В этом разделе мы подробно поговорим о нескольких компонентах и способах оптимизации:

228      ГЛАВА 13

префиксное дерево;

сервис сбора данных;

сервис запросов;

масштабирование хранилища;

операции с префиксным деревом. Префиксное дерево В общей архитектуре в качестве хранилища используется реляционная база данных. Но для извлечения пяти самых популярных поисковых запросов она будет малоэффективной. Чтобы решить эту проблему, вос­ пользуемся структурой данных, известной как префиксное дерево. По­ скольку этот компонент крайне важен для работы системы, мы уделим его проектированию особое внимание. Следует отметить, что некоторые представленные здесь идеи позаимствованы из статей [2] и [3]. Для решения этой задачи обязательно нужно понимать, как работает про­ стое префиксное дерево, хотя этот аспект больше относится к структурам данных, чем к проектированию ИТ-систем. К тому же в интернете есть множество материалов на эту тему. В этой главе приведен лишь краткий обзор префиксных деревьев, а основное внимание уделяется тому, как их оптимизировать, чтобы сократить время ответа. Префиксное дерево — это иерархическая структура данных, которая подходит для компактного хранения строк. Ее английское название, trie, происходит от слова retrieval («извлечение, поиск»); это говорит о том, что она предназначена для операций извлечения строк. Основные свойства префиксного дерева:

префиксное дерево является иерархической структурой данных;

корень представляет пустую строку;

каждый узел хранит символы и имеет 26 дочерних узлов, по одному для каждой буквы английского алфавита. Для экономии места мы не показываем пустые ветви;

каждый узел дерева представляет отдельное слово или префиксную строку.

Проектирование системы автозаполнения поисковых запросов      229 На рис. 13.5 показано префиксное дерево с поисковыми запросами tree, try, true, toy, wish и win. Полные поисковые запросы имеют утолщенные края. t w tr tre tree try tru true to toy wi wis wish win корень Рис. 13.5 Простое префиксное дерево хранит в своих узлах символы. Для поддерж­ ки сортировки узлы должны содержать информацию о частоте. Допустим, у нас есть следующая частотная таблица. Таблица 13.2 Запрос Частота tree 10 try 29 true 35 toy 14 wish 25 win 50

230      ГЛАВА 13 После добавления в узлы информации о частоте префиксное дерево будет выглядеть, как на рис. 13.6. t w tr tre tree: 10 try: 29 tru true: 35 to toy: 14 wi wis wish: 25 win: 50 корень Рис. 13.6 Как работает автозаполнение при использовании префиксного дерева? Прежде чем углубляться в алгоритм, определимся с обозначениями:

p — длина префикса;

n — общее количество узлов в префиксном дереве;

c — количество потомков у заданного узла. Ниже перечислены этапы получения k самых популярных поисковых запросов. 1. Найти префикс. Временная сложность: O(p). 2. Пройтись по дереву, начиная с префиксного узла, чтобы полу­ чить все подходящие узлы-потомки. Потомок подходит, если он может сформировать нужную строку запроса. Временная слож­ ность: O(c). 3. Отсортировать узлы-потомки и получить первые k. Временная сложность: O(clogc).

Проектирование системы автозаполнения поисковых запросов      231 Давайте рассмотрим этот алгоритм на примере рис. 13.7. Допустим, k равно 2, а пользователь вводит в поле поиска tr. Алгоритм работает следующим образом:

Шаг 1. Найти префиксный узел tr.

Шаг 2. Пройтись по поддереву, чтобы получить все подходящие дочерние узлы. В данном случае подходят узлы [tree: 10], [true: 35], [try: 29].

Шаг 3. Отсортировать дочерние узлы и получить два верхних. Двумя самыми популярными запросами с префиксом tr являются [true: 35] и [try: 29]. b w be bee: 20 beer: 10 bet: 29 bes best: 35 bu buy: 14 wi wis wish: 25 win: 50 корень 2 самых популярных узла: [best: 35, bet: 29] 1 1 2 3 Рис. 13.7 Временная сложность этого алгоритма равна общему времени, потрачен­ ному на каждый этап, описанный выше: O (p) + O (c) + O (clogc). Этот алгоритм довольно простой, но при этом слишком медленный, так как в худшем случае для получения k верхних результатов при­ дется пройти по всему префиксному дереву. Есть два варианта опти­ мизации:

232      ГЛАВА 13 1) ограничить максимальную длину префикса; 2) кэшировать самые популярные поисковые запросы в каждом узле. Давайте рассмотрим их по порядку. Ограничение максимальной длины префикса Пользователи редко вводят длинные поисковые запросы. Поэтому можно легко предположить, что p — это небольшое целое число (скажем, 50). Если ограничить длину префикса, временную сложность его поиска можно сократить с O (p) до O (небольшая константа), например O (1). Кэширование самых популярных поисковых запросов в каждом узле Чтобы не выполнять обход всего дерева, мы сохраняем k наиболее часто используемых запросов в каждом узле. Пользователю будет достаточно 5–10 вариантов автозаполнения, поэтому k будет относительно не­ большим числом. В нашем конкретном случае кэшируются только пять верхних поисковых запросов. Кэшируя популярные запросы в каждом узле, мы существенно снижаем временную сложность извлечения вариантов автозаполнения. Но этот подход требует много места для хранения популярных запросов в каж­ дом узле. Короткое время ответа крайне важно и вполне оправдывает выделение дополнительного места. На рис. 13.8 показано обновленное префиксное дерево. В каждом узле хранится пять верхних запросов. Например, узел с префиксом be хранит следующее: [best: 35, bet: 29, bee: 20, be: 15, beer: 10]. Давайте проанализируем временную сложность алгоритма после при­ менения этих двух оптимизаций: 1. Поиск префиксного узла. Временная сложность: O(1). 2. Возвращение k верхних результатов. Поскольку популярные за­ просы кэшируются, временная сложность этого этапа составляет O(1). Временная сложность каждого шага сведена к O(1), поэтому получение k самых популярных запросов с помощью этого алгоритма занимает всего O(1).

Проектирование системы автозаполнения поисковых запросов      233 b w be: 15 bee: 20 beer: 10 bet: 29 bes best: 35 bu buy: 14 wi win: 11 корень [best: 35, bet: 29, bee: 20, be: 15, beer: 10 [bee: 20, beer, 10] [best: 35] [best: 35, bet: 29, bee: 20, be: 15, buy: 14] [buy: 14] [win: 11] [win: 11] Рис. 13.8 Сервис сбора данных В предыдущем варианте архитектуры данные обновлялись в реальном времени по мере ввода поискового запроса. Этот подход непрактичен по двум причинам.

Пользователи могут вводить миллиарды запросов в день. Обнов­ ление дерева при каждом вводе существенно замедляет сервис запросов.

После того как префиксное дерево сформировано, изменение самых популярных вариантов автозаполнения может быть незначитель­ ным. Следовательно, префиксное дерево не нужно часто обновлять. Чтобы спроектировать масштабируемый сервис сбора данных, нужно по­ нять, откуда эти данные поступают и как они используются. Приложения вроде Twitter, работающие в реальном времени, нуждаются в актуальных вариантах автозаполнения. Но, к примеру, в Google варианты автозапол­ нения для многих ключевых слов могут практически не меняться изо дня в день. Несмотря на разные сценарии использования, основной принцип работы сервиса сбора данных остается неизменным, поскольку информация, с помощью которой формируется префиксное дерево, обычно берется из сервисов анализа или логирования.

234      ГЛАВА 13 На рис. 13.9 показан переработанный сервис сбора данных. Проанализи­ руем по очереди каждый его компонент. Агрегаторы Агрегирован- ные данные Рабочие узлы Еженедельное обновление БД префикс- ного дерева Кэш префикс- ного дерева Логи анализа КЭШ КЭШ КЭШ Еженедельные снимки образов БД Рис. 13.9 Логи анализа. Необработанная информация о поисковых запросах. Со­ держимое логов не индексируется и может только дополняться. Пример лог-файла показан в табл. 13.3. Таблица 13.3 Запрос Время tree 2019-10-01 22:01:01 try 2019-10-01 22:01:05 tree 2019-10-01 22:01:30 toy 2019-10-01 22:02:22 tree 2019-10-02 22:02:42 try 2019-10-03 22:03:03 Агрегаторы. Логи анализа обычно очень большие, и их содержимое не соответствует нужному формату. Чтобы наша система могла легко об­ рабатывать эти данные, их необходимо агрегировать. Способ агрегации данных зависит от ситуации. Для таких приложений, как Twitter, работающих в реальном времени, требуются актуальные

Проектирование системы автозаполнения поисковых запросов      235 результаты, поэтому информация агрегируется за короткие промежут­ ки времени. С другой стороны, менее частая агрегация (скажем, раз в неделю) может подойти для других задач. Во время интервью поинте­ ресуйтесь, важны ли актуальные результаты. Мы исходим из того, что префиксное дерево формируется заново каждую неделю. Агрегированные данные В табл. 13.4 показан пример данных, агрегируемых еженедельно. Поле «время» обозначает начало недели. Поле «частота» показывает, сколько раз за неделю вводился тот или иной запрос. Таблица 13.4 Запрос Время Частота tree 2019-10-01 12 000 tree 2019-10-08 15 000 tree 2019-10-15 9000 toy 2019-10-01 8500 toy 2019-10-08 6256 toy 2019-10-15 8866 Рабочие узлы. Это группа серверов, которые выполняют асинхронные задания с регулярной периодичностью. Они формируют префиксное дерево и сохраняют его в соответствующую БД. Кэш префиксного дерева. Это распределенная система кэширования, которая хранит префиксное дерево в памяти для быстрого чтения. Она делает снимок БД на еженедельной основе. БД префиксного дерева. Это постоянное хранилище одного из двух типов: 1. Документное хранилище. Поскольку новое префиксное дере­ во генерируется еженедельно, мы можем периодически сохра­ нять его снимок в сериализованном виде. Для сериализованных данных хорошо подходят такие документные хранилища, как MongoDB [4].

236      ГЛАВА 13 2. Хранилище типа «ключ–значение». Префиксное дерево можно представить в виде хеш-таблицы [4], если руководствоваться сле­ дующей логикой: Š Š каждый префикс в дереве соответствует ключу в хеш-таблице; Š Š данные в каждом узле дерева соответствуют значению в хеш- таблице. На рис. 13.10 показано, как префиксное дерево соотносится с хеш- таблицей. b be: 15 bee: 20 beer: 10 bes best: 35 [be: 15, bee: 20, beer: 10, best: 35 [bee: 20, beer, 10] [best: 35] [be: 15, bee: 20, beer: 10, best: 35 корень [be: 15, bee: 20, beer: 10, best: 35] Ключ b be bee bes beer best Значение [be: 15, bee: 20, beer: 10, best: 35] [bee: 20, beer: 10] [best: 35] [beer: 10] [best: 35] Рис. 13.10 На рис. 13.10 каждый узел префиксного дерева (слева) привязан к паре <ключ, значение> (справа). Если вам не до конца понятно, как работают хранилища типа «ключ–значение», вернитесь к главе 6 «Проектирование хранилища типа “ключ–значение”». Сервис запросов В нашей общей архитектуре сервис запросов извлекает пять самых по­ пулярных результатов непосредственно из базы данных. Такой подход неэффективен. На рис. 13.11 показана улучшенная архитектура.

Проектирование системы автозаполнения поисковых запросов      237 Балансировщик нагрузки Серверы API БД префиксного дерева Кэш префиксного дерева 2 4 1 3 Пользователь Веб-браузер Мобильное приложение КЭШ КЭШ КЭШ Рис. 13.11 1. Поисковый запрос передается балансировщику нагрузки. 2. Балансировщик нагрузки перенаправляет запрос серверам API. 3. Серверы API достают содержимое префиксного дерева из кэша и генерируют варианты автозаполнения для клиента. 4. Если данных нет в кэше, мы их дополнительно кэшируем. Таким образом, все последующие запросы для того же префикса будут возвращаться из кэша. Сбой кэша происходит, когда кэширующий сервер недоступен или у него заканчивается память. Сервис запросов должен работать молниеносно. Мы предлагаем следу­ ющие оптимизации:

238      ГЛАВА 13

AJAX-запросы. В веб-приложениях для извлечения результатов автозаполнения обычно используются AJAX-запросы. Их основ­ ное преимущество в том, что для отправки/получения запроса/ ответа браузеру не нужно обновлять всю веб-страницу целиком.

Кэширование на уровне браузера. Во многих приложениях вари­ анты автозаполнения меняются не очень часто. В связи с этим их можно хранить в кэше браузера и впоследствии доставать оттуда напрямую. Такой механизм кэширования использует Google. На рис. 13.12 показан заголовок ответа, который приходит при вводе в Google запроса system design interview. Как видите, результаты кэшируются в браузере на протяжении 1 часа. Слово private в за­ головке cache-control означает, что результаты предназначены для отдельного пользователя и не должны попасть в общий кэш. max- age=3600 означает, что кэш действителен на протяжении 3600 секунд (то есть одного часа). Рис. 13.12

Выборка данных. В крупномасштабных системах логирование каждого поискового запроса требует много вычислительных ре­ сурсов и места. Поэтому важно выбрать те данные, которые будут сохранены. Например, наша система может записывать в лог лишь 1 из N запросов.

Проектирование системы автозаполнения поисковых запросов      239 Операции с префиксным деревом Префиксное дерево — ключевой компонент системы автозаполнения. Давайте рассмотрим операции, которые оно поддерживает (создание, обновление и удаление). Создание Префиксное дерево создается рабочими узлами на основе агрегирован­ ных данных. Источником данных выступает лог или БД с результатами анализа. Обновление Префиксное дерево можно обновлять двумя способами.

Способ 1: обновлять дерево еженедельно. Дерево, созданное заново, заменяет собой старое.

Способ 2: обновлять узлы дерева напрямую. Мы стараемся избе­ гать этой операции ввиду ее низкой скорости. Но если префиксное дерево небольшое, это приемлемое решение. При обновлении узла необходимо обновить всех его предков вплоть до корня, так как они хранят его популярные запросы. На рис. 13.13 показан пример того, b be: 15 bee: 20 beer: 10 bes best: 35 [best: 35, bee: 20, be: 15, beer: 10] [bee: 20, beer, 10] [best: 35] [best: 35, bee: 20, be: 15, beer: 10] корень b be: 15 bee: 20 beer: 30 bes best: 35 [best: 35, beer: 30, bee: 20, be: 15] [beer, 30, bee: 20] [best: 35] [best: 35, beer: 30, bee: 20, be: 15] корень Рис. 13.13

240      ГЛАВА 13 как работает операция обновления. В левой части поисковый запрос beer имеет начальное значение 10. В правой части он обновляется до 30. Как видите, узел и его предки теперь содержат обновленное значение beer, равное 30. Удаление Мы обязаны удалять варианты автозаполнения, которые разжигают нена­ висть, пропагандируют насилие, носят откровенно сексуальный характер или представляют опасность. Мы добавили слой фильтрации (рис. 13.14) перед кэшем префиксного дерева, чтобы отсеивать нежелательные ре­ зультаты. Это позволяет фильтровать запросы на основе разных гибких правил. Данные удаляются непосредственно из БД асинхронным образом, чтобы во время следующего цикла обновления для генерации префикс­ ного дерева использовалась походящая информация. Кэш префиксного дерева Серверы API Слой фильтрации КЭШ КЭШ КЭШ Рис. 13.14 Масштабирование хранилища Итак, мы разработали системы для автозаполнения пользовательских поисковых запросов. Пришло время решить проблему с масштабирова­ нием, которая возникает, когда префиксное дерево становится слишком большим и уже не помещается на одном сервере. Поскольку наша система поддерживает только английский язык, для сегментирования проще всего использовать первые символы. Вот не­ сколько примеров.

Если для хранения данных требуется два сервера, запросы, первая буква которых находится в диапазоне от a до m, можно записывать на первый, а все остальные (от n до z) — на второй.

Проектирование системы автозаполнения поисковых запросов      241

Если требуется три сервера, запросы можно разделить на диапазоны от a до i, от j до r и от s до z. Если следовать этой логике, запросы можно распределить по 26 серверам, так как английский алфавит состоит из 26 букв. Пусть это будет первый уровень сегментирования. Если 26 серверов будет недостаточно, мы можем перейти на второй или даже третий уровень. Например, запросы, начинающиеся с a, можно распределить по четырем серверам: aa-ag, ah- an, ao-au и av-az. На первый взгляд этот подход кажется разумным, если не брать во внимание тот факт, что намного больше слов начинается с буквы c, чем с буквы x. Это приводит к неравномерному распределению. Чтобы минимизировать несбалансированность данных, нужно проанали­ зировать, как они обычно распределяются, и применить более элегантную логику шардинга, показанную на рис. 13.15. Диспетчер карты сегментов содержит базу данных для определения того, где должны храниться те или иные строки. Например, если результаты анализа показывают, что совокупное количество запросов для u, v, w, x, y и z сравнимо с количе­ ством запросов для s, мы можем предусмотреть два сегмента: один для s, а другой для диапазона от u до z. Веб-серверы Базы данных ШАРД 1 Диспетчер карты сегментов Извлекаем данные из сегмента 2 Какой это сегмент? 1 ШАРД 2 ШАРД ... Рис. 13.15

242      ГЛАВА 13 ШАГ 4: ПОДВЕДЕНИЕ ИТОГОВ Когда вы закончите подробное проектирование, интервьюер может задать вам несколько дополнительных вопросов. Интервьюер: «Как бы вы расширили свою архитектуру для под­ держки других языков?» Для поддержки запросов на языках, отличных от английского, мы за­ писываем в узлы префиксного дерева символы Unicode. Если вы не знакомы с Unicode, вот определение: «Стандарт кодирования, охваты­ вающий все символы для всех систем письма в мире, как современных, так и древних» [5]. Интервьюер: «Что, если список самых популярных запросов за­ висит от страны?» В этом случае мы можем генерировать разные префиксные деревья для разных стран. Чтобы сократить время ответа, их можно хранить в CDN. Интервьюер: «Как реализовать обновление популярных поисковых запросов в реальном времени?» Предположим, в результате какого-то важного события становится по­ пулярным определенный поисковый запрос. Наша исходная архитектура не подойдет, так как:

рабочие узлы обновляют префиксное дерево по расписанию (раз в неделю) и в остальное время бездействуют;

даже если обновление префиксного дерева запланировано, оно за­ нимает слишком много времени. Разработка системы автозаполнения поисковых запросов реального вре­ мени — сложная задачеа, которая выходит за рамки этой книги, поэтому мы дадим лишь несколько советов:

уменьшите рабочий набор данных с помощью шардинга;

измените модель ранжирования так, чтобы недавним поисковым запросам назначался больший вес;

данные могут поступать в виде потоков, поэтому они могут не быть доступны целиком и сразу. Потоковые данные генерируются непре­ рывно. Для обработки потоков нужен другой набор систем: Apache

Проектирование системы автозаполнения поисковых запросов      243 Hadoop MapReduce [6], Apache Spark Streaming [7], Apache Storm [8], Apache Kafka [9] и т. д. Поскольку все эти продукты требуют знаний в определенных предметных областях, мы не станем рас­ сматривать их подробно. Поздравляем, вы проделали длинный путь и можете гордиться собой. Отличная работа! СПРАВОЧНЫЕ МАТЕРИАЛЫ [1]  The Life of a Typeahead Query: https://www.facebook.com/notes/facebook- engineering/the-life-of-a-typeahead-query/389105248919/ [2]  How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete: https://medium.com/@prefixyteam/how-we-built-prefixy-a-scalable- prefix-search-service-for-powering-autocomplete-c20f98e2eff1 [3]  Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables: https://people.eecs.berkeley.edu/~sylvia/papers/pht.pdf [4]  Страница MongoDB на Википедии: https://ru.wikipedia.org/wiki/MongoDB [5]  Часто задаваемые вопросы о Unicode: https://www.unicode.org/faq/basic_q. html [6]  Apache Hadoop: https://hadoop.apache.org/ [7]  Spark Streaming: https://spark.apache.org/streaming/ [8]  Apache Storm: https://storm.apache.org/ [9]  Apache Kafka: https://kafka.apache.org/documentation/