Данным материалом я начинаю серию статей в которых постараюсь на понятном примере описать различия между монолитной и микросервисной архитектурами, а также привести практические примеры создания каждой из них с использованием различных языков программирования (Python, Go) и фреймворков (fastapi, asyncio).
Итак, начнем с постановки задачи. Требуется реализовать систему авто заполнения поисковых запросов, описанную в главе 13 книги System Design. Подготовка к сложному интервью . Авто заполнение можно встретить в поисковых системах или интернет-магазинах. Пользователь
вводит несколько букв или слов и получает всплывающее окно с вариантами слов или их сочетаний.
В минимальный список требований, предъявляемых к таким системам, можно включить следующие:
1. Короткое время отклика. Варианты должны выдаваться достаточно быстро по мере ввода поискового запроса. В упомянутой выше книге говорится о возврате результатов в течение 100 миллисекунд;
2. Варианты, выдаваемые системой, должны иметь отношение к поисковому запросу;
3. Результаты должны быть упорядочены по убыванию популярности; 4.Система должна оставаться доступной даже при выходе из строя какой-то ее части.
При вводе каждого символа в поле поиска программа посылает запрос к серверу за вариантами авто заполнения. Например, при вводе слова python сервер получает следующие 6 запросов:
- search?q=p
- search?q=py
- search?q=pyt
- search?q=pyth
- search?q=pytho
- search?q=python
Для решения поставленной задачи cистема должна состоять как минимум из двух подсистем: сбора данных и запросов. Первая собирает пользовательские поисковые запросы и накапливает их. Вторая возвращает N самых популярных авто заполнений для заданного поискового запроса или его начальной части.
Для того чтобы понять, какие алгоритмы заложены в основу этих подсистем, рассмотрим описание, приведенное в статье, на которую ссылается автор книги по system design. Для начала определимся с терминологией.
- префикс (prefix) — строка, которую пользователь уже ввел в окне поискового запроса;
- завершения (completions) — все возможные способы завершения данного префикса для образования слова или фразы допустимой в текущем языке пользователя;
- предложения (suggestions) — самые высоко оцененные варианты завершения, которые начинаются с префикса и будут представлены пользователю;
- счет (score) — целое число, представляющее популярность данного завершения;
- выбор (selection) — предложение, которое выбирает пользователь, или новое завершение, которое отсутствует в списке предложений.
Приведенные понятия можно проиллюстрировать следующим образом:
Наиболее важными параметрами разрабатываемой системы являются:
- скорость получения ответа на введенный префикс (в идеале не более 100 миллисекунд);
- динамическая ранжируемость предложений во времени. То есть те варианты завершения, который пользователи набирают чаще всего, должны обладать максимальным значением счета (score) и иметь в предложении позиции выше чем менее часто выбираемые завершения.
Для того чтобы удовлетворить указанные требования необходимо тщательно подойти к отбору алгоритмов и структур данных, которые лягут в основу разрабатываемой системы.
Перед рассмотрением алгоритмов введем следующие обозначения:
- N — количество префиксов в нашем наборе данных;
- K — количество завершений, сохраненных для данного префикса;
- L — длина префикса, который мы ищем.
Первое, что приходит на ум — это использовать хеш-таблицу, в которой будут хранится все завершения в качестве ключей, а их счета — в качестве значений как показано на следующем рисунке:
Рассмотрим временную сложность алгоритма (в терминах "О большое") выборки предложений и их ранжирования для префикса "ca".
- Проверка всех ключей (Completions) на соответствие префиксу имеет сложность порядка O(N);
- Проверка одного ключа на соответствие префиксу - O(L), где L - длина префикса, как описано выше;
- Сортировка К завершений в соответствии со значением счета (Score) - O(KlogK).
Таким образом, суммарная сложность будет равна O(NL) + O(K log K).
Главным узким местом этого подхода является проверка всех ключей за O(N). По мере того, как количество данных будет расти, этот алгоритм будет все менее подходящим для удовлетворения наших требований.
Далее рассмотрим структуру данных, называемую префиксным деревом (trie). Префиксное дерево естественным образом подходит для нашей системы, поскольку позволяет выполнять поиск префикса за O(L) (L — длина префикса). Такое дерево занимает меньше места чем хэш-таблица поскольку все потомки текущего узла разделяют этот узел. Хранение префиксного дерева проиллюстрировано на следующем рисунке:
Пусть корень дерева - вершина, хранящая букву "с". В префиксном дереве вершины можно разделить на промежуточные (хранящая букву "с" в нашем примере) и терминальные, которые хранят последнюю букву некоторого слова. Терминальные вершины на рисунке кроме буквы содержат символ ":" за которым следует число, отображающее значение счета (score) для данного варианта завершения. Промежуточные и терминальные вершины могут иметь дочерние вершины. В них входят стрелки, исходящие из родительских вершин. Проходя по пути от корневой вершины к терминальной, можно получить все варианты предложений для заданного префикса. Пусть пользователь ввел префикс "ca" . Начинаем с корневой вершины "c" и в списке ее дочерних находим следующую букву префикса - "а". У "а" - две дочерних вершины "r" и "t". Каждая из них соответствует слову. Выбирая первую ("r"), получаем вариант завершения "car". У "r" одна дочерняя вершина - "t". Переходя в нее получаем следующий вариант завершения - "cart". У вершины "t" нет дочерних, поэтому мы возвращаемся к "r". У нее также нет дочерних. Поэтому поднимаемся к вершине "a". "a" имеет еще одну дочернюю вершину - "t". Переходя к ней, получаем последний вариант завершения - "cat". Таким образом для получения вариантов завершения применяется алгоритм обхода префиксного дерева в глубину.
Поиск префикса в таком дереве будет занимать - O(L), где L - длина префикса, как описано выше. Поиск всех завершений - O(N). Сортировка всех завершений - O(KlogK). Т.е. суммарная сложность - O(L) + O(N) + O(K log K). Опять получаем временную сложность порядка O(N). Такая сложность получается из-за того, что после нахождения префиксного узла все равно придется пройти вниз ко всем его дочерним узлам, чтобы найти все завершения.
Для того чтобы уменьшить временную сложность необходимо хранить все завершения для заданного префикса в его узле. Тогда больше не нужно выполнять обход префиксного дерева чтобы найти все завершения, тем самым эффективно устраняя поиск за O(N).
Таким образом мы выигрываем во временной сложности O(L) + O(K log K), увеличивая пространственную сложность (потребление памяти) алгоритма. Внешний вид дерева показан на следующем рисунке. Здесь, для простоты, в вершинах показаны префиксы вместо отдельных букв. При этом для каждой вершины хранится множество префиксов, показанных в пунктирном прямоугольнике.
Теперь для получения завершений для префикса требуется найти его и отсортировать завершения по полю счета. Временная сложность теперь значительно лучше, так как она больше не является узким местом из-за N, но это имеет свою цену. Мы потребляем больше места, дублируя дополнения для каждого префикса. Также необходимо ограничить максимальную длину префиксов, которые мы храним. Например храним префикс не более 20 символов.
Также необходимо помнить что пользователь автозаполнения увидит только небольшое подмножество всех дополнений для данного префикса. Автозаполнение обычно отображает только около 5-10 самых популярных предложений для префикса.
Также наличие ограничения на количество заполнений, которые мы сохраняем для префикса, экономит место. Но что еще важнее, время сортировки O(K log K) фактически становится постоянным временем O(1). Это справедливо, потому что K никогда не станет больше небольшого предварительно заданного числа N.
Таким образом, сохраняя L и K постоянными, можно улучшить временную сложность алгоритма с O(L) + O(K log K) до O(1) + O(1). Это снижает сложность поиска до O(1)!
Есть еще одна оптимизация, которую можно сделать. Для этого сопоставим префиксы trie с завершениями, хранящимися в каждом узле, с хешем в структуре данных, которая называется префиксным хеш-деревом. Пример такого дерева показан ниже.
По сути каждый узел trie сопоставляется с ключом в хэше. Мы также сопоставляем завершения, хранящиеся в этом узле, со значением этого ключа. Дерево префиксного хэша дает несколько преимуществ по сравнению с trie. Мы можем получить доступ к любому префиксу за один шаг O(1). Но что еще важнее для наших нужд, структура ключ/значение легко реализуется в хранилище данных NoSQL.
Хэш занимает больше места, чем trie. Это происходит потому, что теряется ключевая способность trie разделять общие символы префиксов. Однако можно пожертвовать дополнительными затратами памяти ради упомянутых ранее преимуществ, так как для нас приоритетом является скорость получения завершений.
В следующей статье рассмотрим организацию хранилища префиксов при помощи NoSQL СУБД Redis.