Собеседование по проектированию систем: спроектируйте Twitter
«Спроектируйте Twitter» — это каноническая задача генерации ленты. Она выглядит простой — опубликовать твит, прочитать ленту — но интересная часть заключается в генерации домашней ленты каждого пользователя в масштабе, где правильный ответ — гибридная стратегия fan-out. Интервьюер хочет увидеть, как вы обнаруживаете, что оба наивных подхода не работают, и рассуждаете до прихода к смеси.
Двигайтесь намеренно: уточните требования, оцените соотношение чтения/записи, спроектируйте хранение твитов, затем ленту — сравнивая fan-out-on-write с fan-out-on-read и приходя к гибриду, который решает проблему знаменитостей. Разбор ниже следует этому пути.
1. Уточнение требований
Ограничьтесь основной задачей ленты. Пользователи публикуют твиты, подписываются на других и читают домашнюю ленту, которая объединяет твиты всех, на кого они подписаны, от самых новых.
- Функциональные: опубликовать твит, подписаться/отписаться, домашняя лента (люди, на которых вы подписаны), лента пользователя (один автор); базовый поиск вне рамок, если не запрошен.
- Нефункциональные: очень интенсивное чтение, чтение ленты с низкой задержкой, высокая доступность; итоговая консистентность для ленты допустима.
- Нужно уточнить: медиа, ответы/треды и ранжирование — признайте их и ограничьте объём хронологической лентой для этого собеседования.
2. Оценка масштаба и соотношения чтения/записи
Это соотношение определяет весь дизайн. Чтений значительно больше, чем записей — пользователи листают свою ленту намного чаще, чем публикуют. При сотнях миллионов пользователей система должна сделать чтение ленты дешёвым, даже если это делает запись более дорогой. Это единственное наблюдение указывает на предварительное вычисление лент.
3. Хранение твитов
Сами твиты — это простые данные с преобладанием дозаписи. Храните их в горизонтально партиционированном хранилище, с ключом по ID твита (с временно-сортируемым ID, как Snowflake ID, чтобы порядок был встроен). Отдельное хранилище социального графа хранит отношения подписчиков/подписок.
- Твиты: распределённое хранилище, партиционированное по ID твита; временно-сортируемые ID дают дешёвый хронологический порядок.
- Социальный граф: кто-подписан-на-кого, оптимизирован для «получить всех подписчиков X» и «получить всех, на кого подписан X».
- Кэш (Redis) хранит горячие данные — последние твиты и предварительно вычисленные ленты.
4. Генерация ленты: fan-out при записи против чтения
Это суть задачи. Fan-out-on-write (push) вставляет каждый новый твит в предварительно вычисленный список ленты каждого подписчика в момент публикации — чтение ленты становится дешёвым обращением к кэшу, но публикация от кого-то с миллионами подписчиков вызывает миллионы записей. Fan-out-on-read (pull) строит ленту в момент чтения, объединяя последние твиты всех, на кого вы подписаны — дешёвые записи, но дорогие, медленные чтения для пользователей, подписанных на множество аккаунтов.
- Fan-out-on-write: быстрое чтение, дорогая запись; отлично для обычных пользователей.
- Fan-out-on-read: дешёвая запись, дорогое чтение; нужно для аккаунтов с огромным числом подписчиков.
5. Проблема знаменитостей и гибрид
Ни один чистый подход не выигрывает, поэтому комбинируйте их. Используйте fan-out-on-write для подавляющего большинства пользователей, но для аккаунтов-«знаменитостей» с очень большим числом подписчиков НЕ делайте fan-out их твитов при записи. Вместо этого, в момент чтения, объединяйте предварительно вычисленную ленту подписчика с живым запросом к немногим знаменитостям, на которых он подписан. Это ограничивает усиление записи, сохраняя быстрое чтение — ответ, который слушают интервьюеры.
6. Компромиссы, которые нужно озвучить
Завершите, назвав напряжённые моменты: усиление записи против задержки чтения (всё решение о fan-out), стоимость хранения предварительно вычисленных лент против их пересчёта, и консистентность — задержка в несколько секунд перед тем, как твит появится в лентах подписчиков, допустима, поэтому итоговая консистентность позволяет масштабироваться. Явное указание порога гибрида (как вы классифицируете «знаменитость») демонстрирует зрелое суждение.
Потренируйтесь в проектировании системы Twitter с помощью в реальном времени
Ассистент для собеседований по проектированию систем от Natively может помочь вам сохранять структуру во время живого собеседования — предлагая следующее измерение для рассмотрения и показывая компромиссы в реальном времени, всё на вашем собственном устройстве.
