Требования к продукту

  • Дайте список предложений запроса на основе ввода пользователя (в качестве префикса)
  • Предложения, упорядоченные по некоторому рейтинговому баллу

Требования, не относящиеся к продукту

  • Высокая производительность, ответ должен быть быстрее, чем скорость ввода пользователя, скажем
  • Точность результатов и доступность системы не требуются строго

Основная структура данных

Trie - это структура данных, которая хорошо подходит для поиска по префиксу.

Чтобы сэкономить место, вместо того, чтобы представлять каждый символ с одним узлом, мы представляем общую подстроку в узле. Например, «отдых», «ресторан», «туалет» и «ограничение» имеют общий префикс «отдых». В нашем дереве «rest» хранится в родительском узле с битом, установленным на True, что указывает на то, что сам узел является завершением («rest»), а его дочерние ветви - «restaurant», «restroom» и «ограничение».

Теперь, если есть пользовательский ввод длины L, и мы хотим вернуть K результатов из дерева, содержащего N слов, среднее время поиска будет: O (L) + O (Nlog (K))

O (L): найдите узел, на котором заканчивается префикс, в худшем случае нам нужно будет пройти L узлов, чтобы получить этот узел.

O (Nlog (K)): дойдя до конца префикса, мы должны пройти все подузлы, чтобы собрать все завершения с префиксом. В худшем случае мы должны пройти через все дерево. И, конечно же, если мы хотим вернуть первые K результатов, мы анализируем все завершения через минимальную кучу размера K, для этого требуется время Nlog (K).

Расширенная структура данных и архитектура более высокого уровня

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

  1. Сохранить отсортированный результат в узле

Чтобы предотвратить обход каждого поддерева для префикса, мы можем выполнить некоторые предварительные вычисления и сохранить результаты в этом узле конца префикса. В нашем случае это отсортированный список из K слов с этим префиксом.

С этой структурой данных мы жертвуем пространством, чтобы получить лучшую производительность. Поиск префикса займет O (L) времени, намного быстрее, чем раньше.

2. Ограничьте длину слова

Большинство пользовательских вводов останавливается перед 20 символами, если они точно не знают, что ищут, и в этом случае им наплевать на наши предложения.

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

3. Слой кеширования поверх Trie

В реальном мире на 20% наиболее частых запросов приходится 80% трафика. Если мы сможем выделить небольшое пространство для 20% запросов, мы значительно снизим нагрузку на нагрузку. В нашем случае:

{'re': ['ограничение': 6, 'ресторан': 5], 'a': ['яблоко': 11, 'животное': 5], 'ap': ['яблоко': 11, 'приложение ': 2]}

Обычно trie хранится в базе данных NoSQL, что обеспечивает его постоянство и удобство для масштабирования для больших попыток, подобных тому, что принадлежит Google. Что касается уровня кеширования, Redis - хороший выбор, потому что он поддерживает некоторые полезные операции с сортированным набором кешей, например, мы можем обновить рейтинг некоторых слов без необходимости читать весь список, прибегать и вставлять обратно.

4. Источник рейтинговых баллов

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

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

Затем MR job вычисляет рейтинг частотности всех выбранных поисковых запросов за определенный период времени и отправляет результат агрегатору (нет необходимости включать эти низкочастотные результаты, потому что мы знаем, что они не будут занимать первое место в рейтинге K в дереве).

Затем агрегатор вычисляет новый рейтинг слова с его старым рейтингом и оценкой частоты, заданной как MR + временной фактор (более новый результат получает больший вес).

5. Обновите Trie.

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

6. Репликация Trie

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

7. Снимок

Чтобы еще больше повысить стойкость, периодически создавайте три снимка. Эти снимки можно хранить в s3.

8. Разделение Trie

Разделение также является вариантом масштабирования системы для увеличения трафика и увеличения занимаемого пространства. Чтобы обеспечить сбалансированную нагрузку на сегменты, мы могли бы выполнить разделение на основе оценки того, сколько трафика получает каждый префикс. Например, если «a» - «ea», «eb» - «high», «hih» - «ke» имеют одинаковую нагрузку, они могут быть помещены в сегменты shard1, shard2 и shard3 соответственно.