YouTube

В этой главе нужно спроектировать YouTube. Решение этой задачи можно применять и к похожим вопросам, например к проектированию video sharing platform наподобие Netflix или Hulu. На рисунке 1 показана домашняя страница YouTube.

Рисунок 1

YouTube выглядит просто: создатели контента загружают видео, зрители нажимают play. Но на самом деле за этой простотой скрывается много сложных технологий. Вот несколько впечатляющих фактов и статистик о YouTube [1] [2]:

• Общее число monthly active users: 2 миллиарда.

• Количество просматриваемых видео в день: 5 миллиардов.

• 73% взрослых в США используют YouTube.

• На YouTube 50 миллионов creators.

• Ad revenue YouTube за 2019 год составила $15.1 млрд, что на 36% больше, чем в 2018.

• На YouTube приходится 37% всего мобильного интернет-трафика.

• YouTube доступен на 80 языках.

Из этих цифр видно, что YouTube — это огромный, глобальный и очень прибыльный продукт.

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

Как видно из рисунка 1, на YouTube можно не только смотреть видео. Пользователь может оставлять комментарии, делиться роликами, ставить лайки, сохранять видео в плейлисты, подписываться на каналы и так далее. Спроектировать все это за 45–60 минут интервью невозможно, поэтому важно сузить scope вопросами.

Кандидат: Какие функции для нас самые важные?
Интервьюер: Возможность загружать видео и смотреть видео.

Кандидат: Какие клиенты нужно поддержать?
Интервьюер: Mobile apps, web browsers и smart TV.

Кандидат: Сколько у нас daily active users?
Интервьюер: 5 миллионов.

Кандидат: Сколько времени в среднем пользователь проводит в продукте в день?
Интервьюер: 30 минут.

Кандидат: Нужна ли поддержка международных пользователей?
Интервьюер: Да, существенная часть аудитории — международная.

Кандидат: Какие video resolutions поддерживаются?
Интервьюер: Система принимает большинство разрешений и форматов.

Кандидат: Требуется ли encryption?
Интервьюер: Да.

Кандидат: Есть ли ограничения по размеру видеофайла?
Интервьюер: Мы фокусируемся на small и medium-sized videos. Максимальный размер — 1 ГБ.

Кандидат: Можем ли мы использовать существующую cloud infrastructure от Amazon, Google или Microsoft?
Интервьюер: Отличный вопрос. Строить все с нуля для большинства компаний нереалистично, так что использовать существующие cloud services — разумный вариант.

В этой главе мы сосредоточимся на проектировании video streaming service со следующими функциями:

• Быстрая загрузка видео

• Плавный video streaming

• Возможность менять качество видео

• Низкая стоимость инфраструктуры

• Высокая availability, scalability и reliability

• Поддерживаемые клиенты: mobile apps, web browser и smart TV

Оценка на салфетке

Следующие оценки основаны на множестве допущений, поэтому их стоит проговаривать с интервьюером:

• Предположим, у продукта 5 миллионов DAU.

• Пользователи смотрят по 5 видео в день.

• 10% пользователей загружают 1 видео в день.

• Предположим, средний размер видео — 300 МБ.

• Нужный объем хранения в день: 5 million * 10% * 300 MB = 150 TB

• Стоимость CDN.

• Когда cloud CDN отдает видео, вы платите за исходящий трафик.

• Возьмем для оценки Amazon CloudFront (рисунок 2) [3]. Предположим, что 100% трафика идет из США. Средняя стоимость — $0.02 за ГБ. Для простоты считаем только стоимость video streaming.

• 5 million * 5 videos * 0.3 GB * $0.02 = $150,000 в день.

Из этой грубой оценки видно, что доставка видео через CDN очень дорогая. Даже если cloud provider делает большие скидки крупным клиентам, стоимость все равно остается значительной. О способах ее снижения поговорим в deep dive.

Рисунок 2

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

Как уже обсуждалось, интервьюер предложил использовать существующие cloud services вместо того, чтобы строить все с нуля. В нашем дизайне мы будем использовать CDN и blob storage. Почему не строить все самостоятельно?

• System design interview не про то, чтобы реализовать все с нуля. За ограниченное время важнее выбрать подходящую технологию под задачу, чем подробно объяснять ее внутреннее устройство. Например, упоминания blob storage для source video достаточно; уходить в его детальную реализацию — уже перебор.

• Построить масштабируемое blob storage или CDN чрезвычайно сложно и дорого. Даже очень крупные компании не делают все самостоятельно. Netflix использует cloud services от Amazon [4], а Facebook пользуется CDN Akamai [5].

На high-level система состоит из трех компонентов, показанных на рисунке 3.

Рисунок 3

Client: YouTube можно смотреть на компьютере, мобильном телефоне и smart TV.

CDN: Видео хранятся в CDN. Когда пользователь нажимает play, видео стримится именно оттуда.

API servers: Все остальное, кроме video streaming, проходит через API servers. Это включает feed recommendation, генерацию video upload URL, обновление metadata database и cache, signup пользователя и т. д.

Во время беседы интервьюер особенно интересовался двумя flow:

• Video uploading flow

• Video streaming flow

Рассмотрим high-level design для каждого из них.

Flow загрузки видео

На рисунке 4 показан high-level design video uploading flow.

Рисунок 4

В этой схеме есть такие компоненты:

• User: пользователь смотрит YouTube на компьютере, телефоне или smart TV.

• Load balancer: равномерно распределяет запросы между API servers.

• API servers: все пользовательские запросы, кроме video streaming, проходят через них.

• Metadata DB: здесь хранится video metadata. База шардируется и реплицируется для производительности и высокой доступности.

• Metadata cache: video metadata и пользовательские объекты кэшируются для ускорения.

• Original storage: blob storage для хранения исходных видео. В Wikipedia blob storage описывается как коллекция бинарных данных, хранящаяся как единая сущность [6].

• Transcoding servers: video transcoding, или video encoding, — это процесс преобразования видео в другие форматы и представления (MPEG, HLS и т. д.), чтобы обеспечить наилучший playback на разных устройствах и при разной пропускной способности сети.

• Transcoded storage: blob storage для уже перекодированных видео.

• CDN: видео кэшируются в CDN. При нажатии play поток идет оттуда.

• Completion queue: message queue, в которой лежат события завершения transcoding.

• Completion handler: набор workers, которые читают события из completion queue и обновляют metadata cache и database.

Теперь разберем, как работает video uploading flow. Он делится на два процесса, которые идут параллельно:

1. Загрузка самого видеофайла.

2. Обновление video metadata. Metadata включает video URL, размер, разрешение, формат, информацию о пользователе и т. д.

Flow A: загрузка видеофайла

Рисунок 5

Объяснение потока:

1. Видео загружается в original storage.

2. Transcoding servers забирают видео из original storage и запускают transcoding.

3. После завершения transcoding параллельно выполняются два шага:

• 3a. Перекодированные видео отправляются в transcoded storage.

• 3b. В completion queue помещается событие завершения transcoding.

  3a.1. Transcoded videos распространяются в CDN.

  3b.1. Completion handler состоит из workers, которые непрерывно читают события из queue.

  3b.1.a и 3b.1.b. Completion handler обновляет metadata database и cache после завершения transcoding.

4. API servers сообщают клиенту, что видео успешно загружено и готово к streaming.

Flow B: обновление metadata

Пока файл загружается в original storage, клиент параллельно отправляет запрос на обновление video metadata, как показано на рисунке 6. Запрос содержит metadata: file name, size, format и т. д. API servers обновляют metadata cache и database.

Рисунок 6

Flow streaming видео

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

Перед разбором video streaming flow стоит упомянуть важное понятие: streaming protocol. Это стандартизированный способ контролировать передачу данных при streaming. Популярные streaming protocols:

• MPEG-DASH

• Apple HLS

• Microsoft Smooth Streaming

• Adobe HTTP Dynamic Streaming (HDS)

Необязательно полностью понимать или запоминать эти названия — это низкоуровневые детали. Важно другое: разные streaming protocols поддерживают разные video encodings и playback players. При проектировании video streaming service нужно выбрать протокол, подходящий под наши use cases.

Видео отдаются прямо из CDN. Edge server, расположенный ближе всего к пользователю, доставляет поток, поэтому задержка очень мала. На рисунке 7 показан high-level design video streaming flow.

Рисунок 7

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

В high-level design вся система была разделена на две части: video uploading flow и video streaming flow. Теперь уточним их важными оптимизациями и обсудим механизмы error handling.

Video transcoding

Когда вы записываете видео, устройство (обычно телефон или камера) сохраняет его в некотором формате. Чтобы видео плавно воспроизводилось на других устройствах, его нужно перекодировать в совместимые bitrates и formats. Bitrate — это скорость обработки битов во времени. Чем выше bitrate, тем обычно выше качество видео, но тем больше требуется processing power и bandwidth.

Video transcoding важно по нескольким причинам:

• Raw video занимает очень много места. Часовое HD-видео при 60 FPS может занимать сотни гигабайт.

• Многие устройства и браузеры поддерживают только некоторые форматы, поэтому видео нужно кодировать в несколько вариантов ради совместимости.

• Чтобы пользователь мог смотреть качественное видео без рывков, полезно отдавать высокое разрешение тем, у кого хорошая сеть, и более низкое — тем, у кого сеть слабее.

• Network conditions, особенно на мобильных устройствах, постоянно меняются. Для непрерывного playback необходимо уметь автоматически или вручную переключать качество видео.

Существует множество encoding formats, но у большинства есть две основные части:

• Container: это как корзина, содержащая сам video file, audio и metadata. Формат контейнера можно понять по file extension, например .avi, .mov, .mp4.

• Codecs: алгоритмы сжатия и распаковки, уменьшающие размер видео при сохранении приемлемого качества. Наиболее популярные video codecs — H.264, VP9 и HEVC.

Модель directed acyclic graph (DAG)

Transcoding видео вычислительно дорого и занимает время. Кроме того, у разных content creators могут быть разные требования к обработке: кому-то нужен watermark, кто-то сам загружает thumbnails, кто-то работает с HD-видео, а кто-то нет.

Чтобы поддержать разные processing pipeline и сохранить высокий уровень parallelism, важно ввести уровень абстракции и позволить разработчикам описывать, какие именно задачи запускать. Например, Facebook использует directed acyclic graph (DAG) programming model, где задачи определяются стадиями и могут выполняться последовательно или параллельно [8]. В нашем дизайне мы используем похожую DAG-модель ради гибкости и parallelism. На рисунке 8 показан пример DAG для video transcoding.

Рисунок 8

В DAG из рисунка 8 исходное видео делится на video, audio и metadata. Вот некоторые задачи, которые можно выполнять над video file:

• Inspection: проверить, что видео хорошего качества и не malformed.

• Video encodings: преобразование в разные resolutions, codecs и bitrates. На рисунке 9 показан пример encoded video files.

• Thumbnail: превью может быть либо загружено пользователем, либо автоматически сгенерировано системой.

• Watermark: наложение изображения с identifying information поверх видео.

Рисунок 9

Архитектура video transcoding

Предлагаемая architecture для transcoding, использующая cloud services, показана на рисунке 10.

Рисунок 10

В архитектуре шесть основных компонентов: preprocessor, DAG scheduler, resource manager, task workers, temporary storage и encoded video как выходной результат. Рассмотрим каждый подробнее.

Preprocessor

Рисунок 11

У preprocessor четыре обязанности:

1. Video splitting. Video stream разбивается или доразбивается на небольшие GOP-aligned chunks. GOP (Group of Pictures) — это группа кадров в определенном порядке. Каждый chunk можно воспроизвести независимо, обычно это несколько секунд видео.

2. Некоторые старые mobile devices или browsers не поддерживают video splitting. Для таких клиентов preprocessor выполняет разделение по GOP alignment.

3. DAG generation. Processor генерирует DAG на основе configuration files, которые пишут client programmers. На рисунке 12 показана упрощенная DAG с двумя nodes и одним edge.

Рисунок 12

Эта DAG строится на основе двух configuration files ниже, показанных на рисунке 13.

Рисунок 13 (источник: [9])

4. Кэширование данных. Preprocessor работает как кэш для сегментированных видео. Для надежности он сохраняет GOP и metadata во temporary storage. Если encoding завершится ошибкой, система сможет использовать сохраненные данные для retry.

DAG scheduler

Рисунок 14

DAG scheduler разбивает DAG на stages и кладет задачи в task queue внутри resource manager. На рисунке 15 показан пример этой логики.

Рисунок 15

Как видно на рисунке 15, original video разбивается на три сущности: video, audio и metadata. Далее video порождает две задачи stage 2: video encoding и thumbnails. Audio, в свою очередь, проходит audio encoding.

Resource manager

Рисунок 16

Resource manager отвечает за эффективное распределение ресурсов. В его составе три очереди и task scheduler, как показано на рисунке 17.

• Task queue: priority queue с задачами, которые нужно выполнить.

• Worker queue: priority queue с информацией о загрузке workers.

• Running queue: хранит сведения о выполняющихся задачах и workers, которые их исполняют.

• Task scheduler: выбирает оптимальную пару task/worker и командует выбранному task worker запустить задачу.

Рисунок 17

Resource manager работает так:

• Task scheduler берет задачу с наивысшим приоритетом из task queue.

• Затем выбирает оптимального task worker из worker queue.

• Дает выбранному worker команду выполнить задачу.

• Связывает task/worker info и кладет ее в running queue.

• После завершения задачи удаляет запись из running queue.

Task workers

Рисунок 18

Task workers исполняют задачи, заданные в DAG. Разные workers могут запускать разные типы задач, как показано на рисунке 19.

Рисунок 19

Temporary storage

Рисунок 20

Здесь используются разные storage systems. Выбор зависит от типа данных, размера, частоты доступа, срока жизни и т. д. Например, metadata часто читаются workers и обычно невелики по размеру, поэтому их разумно кэшировать в памяти. Video и audio данные лучше держать в blob storage. Данные во temporary storage освобождаются после завершения соответствующей обработки видео.

Encoded video

Рисунок 21

Encoded video — это финальный результат encoding pipeline. Пример выходного файла: funny_720p.mp4.

Оптимизации системы

Теперь, когда video uploading flow, video streaming flow и transcoding уже понятны, доработаем систему оптимизациями по скорости, безопасности и стоимости.

Оптимизация скорости: параллельная загрузка видео

Загружать видео целиком как одну большую единицу неэффективно. Вместо этого можно делить его на небольшие chunks по GOP alignment, как показано на рисунке 22.

Рисунок 22

Это делает загрузку resumable: если предыдущая попытка сорвалась, можно продолжить с нужного chunk. Работу по splitting by GOP alignment можно выполнять на стороне клиента, чтобы ускорить upload, как на рисунке 23.

Рисунок 23

Оптимизация скорости: размещать upload centers ближе к пользователям

Еще один способ ускорить upload — развернуть несколько upload centers по миру, как на рисунке 24. Пользователи из США смогут загружать видео в North America upload center, а пользователи из Китая — в Asian upload center. Для этого можно использовать CDN как upload centers.

Рисунок 24

Оптимизация скорости: максимальный parallelism

Чтобы добиться низкой latency, нужен высокий parallelism и слабо связанная архитектура.

Текущий дизайн нужно немного изменить, чтобы получить высокую степень parallelism. Если посмотреть на путь передачи видео от original storage к CDN, как показано на рисунке 25, видно, что результат каждого этапа зависит от результата предыдущего, а это затрудняет параллельное выполнение.

Рисунок 25

Чтобы сделать систему более loosely coupled, вводятся message queues, как на рисунке 26. Пример:

• До появления message queue encoding module должен был ждать завершения download module.

• После добавления message queue encoding module больше не обязан ждать напрямую: если в queue уже есть события, он может выполнять jobs параллельно.

Рисунок 26

Оптимизация безопасности: pre-signed upload URL

Безопасность — один из самых важных аспектов продукта. Чтобы только авторизованные пользователи могли загружать видео в правильное место, вводим pre-signed URLs, как на рисунке 27.

Рисунок 27

Обновленный upload flow:

1. Клиент делает HTTP-запрос к API servers, чтобы получить pre-signed URL, который дает право загружать объект по указанному URL. Термин pre-signed URL используется, например, в Amazon S3. У других cloud providers название может отличаться, например у Azure это Shared Access Signature [10].

2. API servers возвращают pre-signed URL.

3. Получив URL, клиент загружает видео напрямую по нему.

Оптимизация безопасности: защита видео

Многие content creators опасаются публиковать видео из-за риска кражи оригиналов. Чтобы защитить copyrighted videos, можно использовать один из трех вариантов:

• Digital rights management (DRM): например Apple FairPlay, Google Widevine и Microsoft PlayReady.

• AES encryption: видео шифруется, а при воспроизведении расшифровывается только для авторизованных пользователей.

• Visual watermarking: поверх видео накладывается изображение с identifying information, например логотип или название компании.

Оптимизация стоимости

CDN — критически важный компонент системы, обеспечивающий быструю доставку видео по всему миру. Но из rough estimation мы уже знаем, что CDN дорогой, особенно при больших объемах данных. Как уменьшить расходы?

Исследования показывают, что просмотры YouTube следуют long-tail distribution [11] [12]. Это значит, что небольшая часть видео очень популярна, а у большинства мало или вообще нет зрителей. Исходя из этого можно сделать несколько оптимизаций:

1. Отдавать из CDN только самые популярные видео, а менее популярные — с собственных high-capacity video servers, как на рисунке 28.

Рисунок 28

2. Для менее популярного контента необязательно хранить много encoded versions. Короткие видео можно кодировать по требованию.

3. Некоторые видео популярны только в отдельных регионах, поэтому нет смысла распространять их в другие регионы.

4. Можно строить собственный CDN, как Netflix, и партнериться с ISP. Это огромный проект, но для больших streaming companies он может быть оправдан. ISP — это Comcast, AT&T, Verizon и другие интернет-провайдеры, которые находятся близко к пользователям. Такое партнерство может улучшить viewing experience и снизить bandwidth charges.

Все эти оптимизации основаны на popularitу контента, user access patterns, размере видео и других факторах. Перед их внедрением важно проанализировать исторические просмотры.

Обработка ошибок

Для large-scale system ошибки неизбежны. Чтобы система была fault-tolerant, нужно уметь корректно обрабатывать ошибки и быстро восстанавливаться. Есть два типа ошибок:

• Recoverable error. Например, не удалось перекодировать один video segment. Общая идея — retry несколько раз. Если задача продолжает падать и система считает ошибку нерешаемой, клиенту возвращается корректный error code.

• Non-recoverable error. Например, malformed video format. В этом случае система останавливает связанные задачи и сразу возвращает клиенту корректный error code.

Вот playbook типичных ошибок по компонентам:

• Upload error: retry несколько раз.

• Split video error: если старые клиенты не умеют делить видео по GOP alignment, весь файл отправляется на сервер, и splitting выполняется уже там.

• Transcoding error: retry.

• Preprocessor error: сгенерировать DAG заново.

• DAG scheduler error: заново запланировать задачу.

• Resource manager queue down: использовать replica.

• Task worker down: запустить task повторно на новом worker.

• API server down: API servers stateless, поэтому запросы уйдут на другой API server.

• Metadata cache server down: данные реплицируются несколько раз, поэтому если один узел недоступен, можно читать с других и поднять новый cache server взамен.

• Metadata DB server down:

• Master down: повысить одного из slaves до нового master.

• Slave down: читать с другого slave и поднять новый database server на замену.

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

В этой главе мы представили архитектуру video streaming service наподобие YouTube. Если в конце интервью останется время, можно обсудить еще несколько тем:

• Масштабирование API tier: поскольку API servers stateless, этот слой легко масштабировать горизонтально.

• Масштабирование database: replication и sharding.

• Live streaming: это сценарий, где видео записывается и транслируется в реальном времени. Хотя наша система не проектировалась специально под live streaming, у live и non-live streaming много общего: upload, encoding и streaming. Но есть и отличия:

• Для live streaming требования к latency выше, поэтому может понадобиться другой streaming protocol.

• Для live streaming требования к parallelism ниже, потому что маленькие chunks уже и так обрабатываются в реальном времени.

• Для live streaming нужны другие механизмы error handling. Любая обработка ошибок, которая занимает слишком много времени, становится неприемлемой.

• Video takedowns: ролики, нарушающие copyright, содержащие pornographic content или иные illegal acts, должны удаляться. Часть из них можно выявлять на этапе upload, часть — после user flagging.

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

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

[1] YouTube by the numbers:
https://www.omnicoreagency.com/youtube-statistics/

[2] 2019 YouTube Demographics:
https://blog.hubspot.com/marketing/youtube-demographics

[3] Cloudfront Pricing:
https://aws.amazon.com/cloudfront/pricing/

[4] Netflix on AWS:
https://aws.amazon.com/solutions/case-studies/netflix/

[5] Akamai homepage: https://www.akamai.com/

[6] Binary large object:
https://en.wikipedia.org/wiki/Binary_large_object

[7] Here’s What You Need to Know About Streaming Protocols:
https://www.dacast.com/blog/streaming-protocols/

[8] SVE: Distributed Video Processing at Facebook Scale:
https://www.cs.princeton.edu/~wlloyd/papers/sve-sosp17.pdf

[9] Weibo video processing architecture (in Chinese):
https://www.upyun.com/opentalk/399.html

[10] Delegate access with a shared access signature:
https://docs.microsoft.com/en-us/rest/api/storageservices/delegate-access-with-shared-access-signature

[11] YouTube scalability talk by early YouTube employee:
https://www.youtube.com/watch?v=w5WVu624fY8

[12] Understanding the characteristics of internet short video sharing: A youtube-based measurement study.
https://arxiv.org/pdf/0707.3670.pdf

[13] Content Popularity for Open Connect:
https://netflixtechblog.com/content-popularity-for-open-connect-b86d56f613b