System Design Interview Glossary [0] — Дизайним поиск твиттера

Twitter — одна из крупнейших социальных сетей, где пользователи могут обмениваться фотографиями, новостями и текстовыми сообщениями. В этой главе мы разработаем сервис, который может хранить и искать текстовые твиты пользователей. Если вы готовитесь к собеседованию по проектированию системы/улучшению аналога поиска, присаживайтесь поудобнее, вам будет интересно! Начнем по порядку

Пользователи Твиттера могут обновлять свой статус в любой момент, когда им захочется. Каждый статус (называемый твитом) состоит из обычного текста, и наша цель — разработать систему, позволяющую осуществлять поиск по всем твитам пользователя.

Возьмем как факт, что у Твиттера 1,5 миллиарда пользователей с 800 миллионами ежедневных активных пользователей. Предположим, что в среднем твиттер получает ~400 миллионов твитов каждый день. Средний размер твита составляет 300 байт. Также предположим, что каждый день будет производиться ~500 миллионов поисковых запросов. Поисковый запрос будет состоять из нескольких слов в сочетании с AND/OR. Нам необходимо разработать систему, которая сможет эффективно хранить твиты и выполнять запросы поиска.

Заполнение емкости хранилища:

Поскольку у нас есть 400 миллионов новых твитов каждый день, а каждый твит в среднем занимает 300 байт, общая емкость хранилища, которое нам необходимо, составит:

400M * 300 => 120GB/день

Заполнение емкости хранилища в секунду:

120GB / 24 часа / 3600 секунд ~= 1.38MB/секунду.

Мы можем использовать SOAP или REST API для раскрытия функциональности нашего сервиса, имея ввиду это замечание, следующее API может быть определением поиска:

search(api_dev_key, search_terms, maximum_results_to_return, sort, page_token)

Параметры:

1. api_dev_key (строка) : Ключ разработчика API зарегистрированного аккаунта. Он будет использоваться, в частности, для ограничения пользователей в зависимости от выделенной им квоты.

2. search_terms (строка) : Строка, содержащая условия поиска.

3. maximum_results_to_return (число) : Количество возвращаемых твитов.

4. sort (число) : Необязательный режим сортировки: Сначала последние (0 — по умолчанию) , Наилучшее совпадение (1), Больше всего понравилось (2).

5. page_token (string) : Этот токен указывает страницу в наборе результатов, которую следует вернуть.

Возвращает JSON, содержащий информацию о списке твитов, соответствующих поисковому запросу. Каждая запись результата может содержать идентификатор и имя пользователя, текст твита, идентификатор твита, время создания, количество лайков и т.д.

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

1. Хранилище: Нам необходимо хранить 120 ГБ новых данных каждый день. Учитывая такой огромный объем данных, нам необходимо придумать схему разделения данных, которая будет эффективно распределять данные по нескольким серверам. Если мы планируем на следующие пять лет, нам потребуется следующее хранилище:

120 ГБ * 365 дней * 5 лет ~= 200 ТБ.

Если мы не хотим, чтобы в любой момент времени хранилище было заполнено более чем на 80%, то нам потребуется примерно 250 ТБ общего объема хранилища. Предположим, что мы хотим хранить дополнительную копию всех твитов для обеспечения отказоустойчивости; тогда общая потребность в хранилище составит 500 ТБ. Если предположить, что современный сервер может хранить до 4 ТБ данных, то для хранения всех необходимых данных в течение следующих пяти лет нам потребуется 125 таких серверов.

Давайте начнем с упрощенного варианта, когда мы храним твиты в базе данных MySQL. Можно предположить, что мы храним твиты в таблице с двумя столбцами TweetID и TweetText. Предположим, что мы разделяем наши данные на основе TweetID. Если наши TweetID уникальны в масштабах всей системы, мы можем определить хэш-функцию, которая сопоставит TweetID с сервером хранения, где мы можем хранить объект твита.

Как мы можем создать уникальные TweetID в масштабах всей системы? Если мы получаем 400M новых твитов каждый день, то сколько объектов твитов мы можем ожидать через пять лет?

400M * 365 дней * 5 лет => 730 миллиардов.

Это означает, что нам понадобится пятибайтовое число для уникальной идентификации TweetID. Предположим, что у нас есть сервис, который может генерировать уникальный TweetID всякий раз, когда нам нужно сохранить объект. Мы можем передать TweetID нашей хэш-функции, чтобы найти сервер хранения и сохранить там наш объект твита.

2. Индекс: Как должен выглядеть наш индекс? Поскольку наши твиттер-запросы будут состоять из слов, давайте создадим индекс, который подскажет нам, какое слово встречается в каком твиттер-объекте. Давайте сначала оценим, насколько большим будет наш индекс. Если мы хотим построить индекс для всех английских слов и некоторых известных существительных, таких как имена людей, названия городов и т. д., и если мы предположим, что у нас есть около 300 тысяч английских слов и 200 тысяч существительных, то в нашем индексе будет 500 тысяч слов. Предположим, что средняя длина слова составляет пять символов. Если мы будем хранить наш индекс в памяти, то для хранения всех слов нам потребуется 2,5 МБ памяти:

500K * 5 => 2.5 MB

Предположим, что мы хотим сохранить в памяти индекс для всех твитов только за последние два года. Поскольку за 5 лет мы получим 730B твитов, то за два года мы получим 292B твитов. Учитывая, что каждый TweetID будет иметь размер 5 байт, сколько памяти нам понадобится для хранения всех TweetID?

292B * 5 => 1460 GB

Таким образом, наш индекс будет похож на большую распределенную хэш-таблицу, где «ключом" будет слово, а "значением» — список TweetID всех твитов, содержащих это слово. Предположим, что в среднем у нас есть 40 слов в каждом твите, и поскольку мы не будем индексировать предлоги и другие маленькие слова, такие как «the", "an", "and» и т.д., давайте предположим, что у нас будет около 15 слов в каждом твите, которые нужно индексировать. Это означает, что каждый TweetID будет храниться в нашем индексе 15 раз. Итак, общий объем памяти, необходимый для хранения нашего индекса:

(1460 * 15) + 2,5 МБ ~= 21 ТБ.

Если предположить, что сервер высокого класса имеет 144 Гб памяти, то нам понадобится 152 таких сервера для хранения нашего индекса.

Мы можем разделить наши данные по двум критериям:

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

У нас есть несколько проблем с этим подходом:

Что, если слово станет «hot»? Тогда будет много запросов к серверу, содержащему это слово. Такая высокая нагрузка повлияет на производительность нашего сервиса. Со временем некоторые слова могут хранить много TweetID по сравнению с другими, поэтому поддерживать равномерное распределение слов в процессе роста твитов довольно сложно.

Разделение на основе объекта твита: При хранении мы передаем TweetID нашей хэш-функции для поиска сервера и индексации всех слов твита на этом сервере. При запросе конкретного слова мы должны запросить все серверы, и каждый сервер вернет набор TweetID. Централизованный сервер объединит эти результаты и вернет их пользователю.

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

Что если первичный и вторичный серверы умрут одновременно? Нам придется выделить новый сервер и восстановить на нем тот же индекс. Как мы можем это сделать? Мы не знаем, какие слова/твиты хранились на этом сервере. Если бы мы использовали шардирование, основанное но обьектах твитта, то решение методом грубой силы заключалось бы в том, чтобы просмотреть всю базу данных и отфильтровать TweetID, используя нашу хэш-функцию, чтобы выяснить все необходимые твиты, которые хранятся на этом сервере. Это было бы неэффективно, к тому же во время перестройки сервера мы не смогли бы выполнить ни один запрос с него, и таким образом пропустили бы некоторые твиты, которые должен был увидеть пользователь.

Как мы можем эффективно получить отображение между твитами и индексным сервером? Мы должны построить обратный индекс, который сопоставит все TweetID с их индексным сервером. Наш сервер Index-Builder может хранить эту информацию. Нам нужно будет создать Hashtable, где «ключ" будет номером индексного сервера, а "значение» — HashSet, содержащий все TweetID, хранящиеся на этом индексном сервере. Обратите внимание, что мы храним все TweetID в HashSet; это позволит нам быстро добавлять/удалять твиты из нашего индекса. Итак, теперь, когда индексный сервер должен перестроиться, он может просто запросить у сервера Index-Builder все твиты, которые ему нужно сохранить, а затем получить эти твиты для построения индекса. Такой подход, несомненно, будет быстрым. Мы также должны иметь копию сервера Index-Builder для обеспечения отказоустойчивости.

Чтобы справиться с горячими твитами, мы можем внедрить кэш перед нашей базой данных. Мы можем использовать Memcached, который может хранить все такие горячие твиты в памяти. Серверы приложений, прежде чем обратиться к базе данных бэкенда, могут быстро проверить, есть ли в кэше этот твит. Основываясь на моделях использования клиентов, мы можем регулировать количество необходимых нам серверов кэша. Для политики вытеснения кэша для нашей системы подходит метод наименьшего использования (LRU).

Мы можем добавить уровень балансировки нагрузки в двух местах нашей системы: 1) между клиентами и серверами приложений и 2) между серверами приложений и серверами бэкенда. Первоначально можно использовать простой подход Round Robin, который распределяет входящие запросы поровну между внутренними серверами. Этот LB прост в реализации и не влечет за собой никаких накладных расходов. Еще одним преимуществом этого подхода является то, что LB выводит «мертвые» серверы из ротации и прекращает отправку трафика на них. Проблема с Round Robin LB заключается в том, что он не учитывает нагрузку на сервер. Если сервер перегружен или работает медленно, LB не прекратит посылать новые запросы на этот сервер. Для решения этой проблемы можно использовать более интеллектуальное решение LB, которое периодически запрашивает внутренний сервер о его нагрузке и регулирует трафик в зависимости от этого.

Что, если мы захотим ранжировать результаты поиска по расстоянию между социальными графами, популярности и релевантности?

Предположим, мы хотим ранжировать твиты по популярности, например, по количеству лайков, комментариев и т. д. В таком случае наш алгоритм ранжирования может вычислить «число популярности» (основанное на количестве лайков и т. д.) и сохранить его в индексе. Каждый раздел может сортировать результаты на основе этого числа популярности, прежде чем вернуть результаты на сервер-агрегатор. Сервер-агрегатор объединяет все эти результаты, сортирует их на основе числа популярности и отправляет лучшие результаты пользователю.