Лента новостей

В этой главе нужно спроектировать систему новостной ленты. Что такое news feed? Согласно странице помощи Facebook, «News Feed is the constantly updating list of stories in the middle of your home page. News Feed includes status updates, photos, videos, links, app activity, and likes from people, pages, and groups that you follow on Facebook» [1]. Это популярный вопрос на интервью. Похожие формулировки: спроектировать ленту Facebook, ленту Instagram, таймлайн Twitter и т. д.

Рисунок 1

Шаг 1 — Понять задачу и определить рамки дизайна

Первый набор уточняющих вопросов нужен, чтобы понять, что именно имеет в виду интервьюер, когда просит спроектировать систему news feed. Как минимум нужно выяснить, какие функции мы должны поддержать. Ниже пример диалога кандидата и интервьюера:

Кандидат: Это мобильное приложение? Веб-приложение? Или и то и другое?
Интервьюер: И то и другое.

Кандидат: Какие функции самые важные?
Интервьюер: Пользователь может публиковать пост и видеть посты своих друзей на странице ленты.

Кандидат: Лента сортируется в обратном хронологическом порядке или по какому-то другому правилу, например по score?
Интервьюер: Для простоты предположим, что лента отсортирована в обратном хронологическом порядке.

Кандидат: Сколько друзей может быть у пользователя?
Интервьюер: 5000.

Кандидат: Какой объем трафика?
Интервьюер: 10 миллионов DAU.

Кандидат: Лента может содержать изображения и видео или только текст?
Интервьюер: Может содержать медиафайлы, включая и изображения, и видео.

Теперь, когда требования собраны, можно переходить к проектированию системы.

Шаг 2 — Предложить высокоуровневый дизайн и согласовать его

Дизайн делится на два потока: публикация постов и построение новостной ленты.

• Публикация поста: когда пользователь публикует запись, соответствующие данные записываются в кэш и в базу данных. Пост попадает в ленты его друзей.

• Построение ленты: для простоты будем считать, что лента формируется путем агрегации постов друзей в обратном хронологическом порядке.

API для news feed

API новостной ленты — основной способ общения клиентов с серверами. Это HTTP API, с помощью которых клиенты публикуют статус, получают ленту, добавляют друзей и т. д. Мы обсудим два самых важных API: публикацию поста и получение ленты.

API публикации поста

Чтобы опубликовать пост, клиент отправляет HTTP POST-запрос:

POST /v1/me/feed

Параметры:

• content: текст поста.

• auth_token: используется для аутентификации запросов к API.

API получения ленты

API для получения news feed выглядит так:

GET /v1/me/feed

Параметры:

• auth_token: используется для аутентификации запросов к API.

Публикация поста

На рисунке 2 показан высокоуровневый дизайн потока публикации.

Рисунок 2

• Пользователь может смотреть ленту в браузере или мобильном приложении. Он публикует пост с содержимым Hello через API:

  /v1/me/feed?content=Hello&auth_token={auth_token}

• Load balancer распределяет трафик по web-серверам.

• Web-серверы перенаправляют трафик во внутренние сервисы.

• Post service сохраняет пост в базе данных и в кэше.

• Fanout service доставляет новый контент в новостные ленты друзей. Данные news feed сохраняются в кэше для быстрого чтения.

• Notification service сообщает друзьям, что появился новый контент, и отправляет push-уведомления.

Построение новостной ленты

В этом разделе обсудим, как news feed формируется внутри системы. На рисунке 3 показан высокоуровневый дизайн.

Рисунок 3

• Пользователь отправляет запрос на получение ленты: /v1/me/feed.

• Load balancer перенаправляет трафик на web-серверы.

• Web-серверы маршрутизируют запрос в news feed service.

• News feed service получает ленту из кэша.

• News feed cache хранит ID, необходимые для отрисовки news feed.

Шаг 3 — Детальный разбор дизайна

На высоком уровне мы кратко рассмотрели два потока: публикацию поста и построение news feed. Теперь разберем эти темы глубже.

Детали публикации поста

На рисунке 4 показан подробный дизайн публикации. Большинство компонентов уже обсуждались на высоком уровне, поэтому здесь мы сосредоточимся на двух частях: web-серверах и fanout service.

Рисунок 4

Web-серверы

Помимо общения с клиентами, web-серверы обеспечивают аутентификацию и rate limiting. Только пользователи с валидным auth_token могут публиковать посты. Система ограничивает количество постов, которое пользователь может опубликовать за определенный период, что важно для защиты от спама и злоупотреблений.

Fanout service

Fanout — это процесс доставки поста всем друзьям. Существует две модели fanout: fanout on write (еще называют push model) и fanout on read (или pull model). У обеих моделей есть плюсы и минусы. Разберем их подробнее и выберем подходящую стратегию.

Fanout on write. В этой модели news feed вычисляется во время записи. Новый пост сразу после публикации доставляется в кэш друзей.

Плюсы:

• Лента формируется в реальном времени и может быть мгновенно доставлена друзьям.

• Получать ленту быстро, потому что она заранее предвычислена при записи.

Минусы:

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

• Для неактивных пользователей или тех, кто редко заходит, предварительное построение ленты впустую тратит вычислительные ресурсы.

Fanout on read. В этой модели лента формируется во время чтения. Это on-demand подход: свежие посты подтягиваются тогда, когда пользователь открывает домашнюю страницу.

Плюсы:

• Для неактивных пользователей или тех, кто редко заходит, fanout on read работает лучше, потому что не тратит ресурсы заранее.

• Данные не пушатся друзьям, поэтому не возникает hotkey problem.

Минусы:

• Получение ленты медленнее, потому что она не предвычислена.

Мы выберем гибридный подход, чтобы получить преимущества обоих вариантов и избежать их недостатков. Поскольку быстрое получение ленты критично, для большинства пользователей мы используем push model. Для знаменитостей или пользователей с очень большим числом друзей или подписчиков мы разрешаем подписчикам подтягивать контент по запросу, чтобы не перегружать систему. Консистентное хеширование здесь тоже полезно, потому что помогает равномернее распределять запросы и данные, смягчая hotkey problem.

Давайте внимательно посмотрим на fanout service на рисунке 5.

Рисунок 5

Fanout service работает так:

1. Получаем ID друзей из graph database. Графовые базы хорошо подходят для хранения связей дружбы и рекомендаций друзей. Подробнее см. [2].

2. Получаем информацию о друзьях из user cache. Затем система фильтрует друзей согласно настройкам пользователя. Например, если вы кого-то заглушили, его посты не будут появляться в вашей ленте, хотя вы все еще друзья. Аналогично пользователь может выборочно делиться контентом только с частью друзей или скрывать его от других.

3. Отправляем список друзей и ID нового поста в message queue.

4. Fanout workers считывают данные из message queue и записывают данные news feed в news feed cache. На news feed cache можно смотреть как на таблицу соответствия <post_id, user_id>. Каждый новый пост добавляется в эту таблицу, как показано на рисунке 6. Если хранить в кэше целые объекты пользователя и поста, потребление памяти будет слишком большим, поэтому в кэше хранятся только ID. Чтобы не раздувать память, мы задаем конфигурируемый лимит. Вероятность, что пользователь будет прокручивать тысячи постов, невелика. Большинству интересен только свежий контент, поэтому cache miss rate остается низким.

5. Сохраняем <post_id, user_id> в news feed cache. На рисунке 6 показан пример того, как это выглядит в кэше.

post_id	user_id
post_id	user_id
post_id	user_id
post_id	user_id
post_id	user_id
post_id	user_id
post_id	user_id
post_id	user_id

Рисунок 6

Детали получения новостной ленты

На рисунке 7 показан подробный дизайн получения news feed.

Рисунок 7

Как показано на рисунке 7, медиа-контент (изображения, видео и т. д.) хранится в CDN для быстрого получения. Посмотрим, как клиент получает ленту.

1. Пользователь отправляет запрос на получение ленты. Запрос выглядит так: /v1/me/feed

2. Load balancer перераспределяет запросы на web-серверы.

3. Web-серверы вызывают news feed service, чтобы получить ленту.

4. News feed service получает список ID постов из news feed cache.

5. Но news feed — это не просто список ID. Для рендеринга нужны имя пользователя, аватар, текст поста, изображение, и другие данные. Поэтому news feed service достает полные объекты пользователя и поста из кэшей (user cache и post cache) и на их основе собирает полностью hydrated news feed.

6. Полностью собранная news feed возвращается клиенту в формате JSON для отображения.

Архитектура кэша

Кэш чрезвычайно важен для системы новостной ленты. Мы делим кэш-слой на 5 уровней, как показано на рисунке 8.

Рисунок 8

• News Feed: хранит ID элементов ленты.

• Content: хранит данные постов. Популярный контент находится в hot cache.

• Social Graph: хранит данные о связях между пользователями.

• Action: хранит информацию о том, лайкнул ли пользователь пост, ответил ли на него и выполнял ли другие действия.

• Counters: хранит счетчики лайков, ответов, подписчиков, подписок и т. д.

Шаг 4 — Подведем итоги

В этой главе мы спроектировали систему новостной ленты. Наш дизайн состоит из двух потоков: публикация постов и получение ленты.

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

Масштабирование базы данных:

• Vertical scaling и horizontal scaling

• SQL vs NoSQL

• Master-slave replication

• Read replicas

• Consistency models

• Database sharding

Другие темы:

• Держать web-уровень stateless

• Максимально кэшировать данные

• Поддерживать несколько дата-центров

• Слабо связанные компоненты через message queues

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

Поздравляем, вы дошли до этого места! Можно похлопать себя по плечу. Отличная работа!

Справочные материалы

[1] How News Feed Works:
https://www.facebook.com/help/327131014036297/

[2] Friend of Friend recommendations Neo4j and SQL Sever:
http://geekswithblogs.net/brendonpage/archive/2015/10/26/friend-of-friend-recommendations-with-neo4j.aspx