Reddit открыл в честь Первого апреля страничку для самовыражения пользователей, но созданный для шутки проект стал своеобразной стеной для коллективных граффити от участников со всего мира, показывающих, какой след они хотят оставить в истории.
Первого апреля Reddit запустил проект Place («Место») - страницу с пустым холстом, на котором каждый пользователь форума мог нарисовать любое изображение. У художников были ограничения: рисовать можно только один пиксель одного из 16 цветов раз в пять минут, размеры холста тоже ограничены. Поверх нарисованных пикселей можно рисовать другие (а затем первый автор может снова нарисовать свой пиксель поверх пикселя соперника), из-за чего авторы изображений априори конфликтуют. Как указывается в описании холста, проект рассчитан на совместное творчество - «Каждый из вас может создать нечто индивидуальное. Вместе вы можете создать нечто большее».
В момент старта проекта все желающие буквально накинулись на холст - каждый пиксель на нём был заполнен. Поначалу пользователи просто тыкали цветом в свободные пиксели, но потом начали образовываться команды, которые стали рисовать одну из простейших возможных идей, находящую единомышленников, - государственные флаги. Чем больше над холстом работали пользователи, тем более интересные и сложные идеи приходили им в голову. И «Место» превратилось из первоапрельского проекта в место, где пользователи всего мира объединяются в настоящие сообщества, чтобы показать что-то миру и поддерживать своё творение от групп рейдеров, которые на самом деле просто также хотят нарисовать какой-то собственный рисунок.
Place в первые часы работы
«Место» стало онлайн-доской для стикеров, но каждый из них создаётся с огромным трудом. К примеру, чтобы нарисовать и защитить от сквоттеров логотип Linux размером 48 х 68 пикселей, им должны одновременно заниматься 3 264 человека.
Пользователи объединяются для реализации идей поменьше и попроще, но всё же очень командных, как этот ряд сердечек с флагами разных стран (и не только): каждый отвечает за «своё» сердечко, но все вместе люди невольно образуют одну команду.
А другие пишут целые полотна текста, например, как эта группа фанатов «Звёздных войн», написавшая и поддерживающая известный монолог верховного канцлера Палпатина о ситхе Дарте Плэгасе из третьего эпизода космической саги.
Однако некоторые пользователи пожаловались на то, что участники проекта «посадили» вместо себя ботов, которые автоматически обновляют занятый автором пиксель каждые пять минут. Несмотря на то, что при рисовании каждого пикселя пользователю нужно повторить набор действий (к примеру, выбор определённого цвета), некоторые смогли обойти механизм защиты и создать ботов, рисующих за них картинки.
Однако есть и те, кто до сих пор создаёт специальные треды, пытаясь призвать единомышленников, которые помогут нарисовать и оставить для будущих поколений что-то вроде… блюющего Рика Санчеза из мультфильма «Рик и Морти». Серьёзно? Это точно не боты?
После 72 часов работы проект был закрыт. Администрация ресурса поблагодарила всех за участие и за то, что люди объединялись, «чтобы создавать нечто большее».
Reddit часто становится местом для проведения различных социальных активностей. К примеру, недавно грустные пользователи ресурса решили спросить , каково это - каждый день просыпаться с улыбкой. А до этого читатели Reddit делились друг с другом рассказами о от девушек. На популярном ресурсе сидят не только анонимы: недавно актёр и несколько часов отвечал на вопросы пользователей по поводу фильма «На игле».
Для начала было крайне важно определить требования к первоапрельскому проекту, потому что запустить его нужно было без «разгона», чтобы все пользователи Reddit сразу получили к нему доступ. Если бы он с самого начала не работал идеально, то вряд ли привлёк бы внимание большого количества людей.
«Доска» должна быть размером 1000х1000 тайлов, чтобы выглядеть очень большой.
Все клиенты должны быть синхронизированы и отображать единое состояние доски. Ведь если у разных пользователей будут разные версии, им будет трудно взаимодействовать.
Нужно поддерживать как минимум 100 000 пользователей одновременно.
Пользователи могут размещать по одному тайлу в пять минут. Поэтому необходимо поддерживать среднюю частоту обновления 100 000 тайлов в пять минут (333 обновления в секунду).
Проект не должен негативно влиять на работу остальных частей и функций сайта (даже при условии высокого трафика на r/Place).
- На случай возникновения непредвиденных узких мест или сбоев необходимо обеспечить гибкое конфигурирование. То есть нужно иметь возможность на лету настраивать размер доски и разрешённую частоту рисования, если объём данных окажется слишком велик или частота обновлений будет слишком высока.
Бэкенд
Решения по реализации
Главной трудностью при создании бэкенда было синхронизировать отображение состояния доски для всех клиентов. Было решено сделать так, чтобы клиенты в реальном времени прослушивали события размещения тайлов и немедленно запрашивали состояние всей доски. Иметь немного устаревшее полное состояние допустимо в случае подписки на обновления до того, как это полное состояние было сгенерировано. Когда клиент получает полное состояние, он отображает все тайлы, которые получил во время ожидания; все последующие тайлы должны отображаться на доске сразу же по мере получения.
Чтобы эта схема работала, запрос полного состояния доски должен выполняться как можно быстрее. Сначала мы хотели хранить всю доску в одной строке в Cassandra , и чтобы каждый запрос просто считывал эту строку. Формат каждой колонки в этой строке был таким:
(x, y): {‘timestamp’: epochms, ‘author’: user_name, ‘color’: color}
Но поскольку доска содержит миллион тайлов, нам нужно было считывать миллион колонок. На нашем рабочем кластере это занимало до 30 секунд, что было неприемлемо и могло привести к чрезмерной нагрузке на Cassandra.
Тогда мы решили хранить всю доску в Redis. Взяли битовое поле на миллион четырёхбитовых чисел, каждое из которых могло кодировать четырёхбитный цвет, а координаты х и y определялись смещением (offset = x + 1000y) в битовом поле. Для получения полного состояния доски нужно было считать всё битовое поле.
Обновлять тайлы можно было посредством обновления значений с конкретными смещениями (не нужно блокировать или проводить целую процедуру чтения/ обновления/ записи). Но все подробности всё равно нужно хранить в Cassandra, чтобы пользователи могли узнать, кто и когда разместил каждый из тайлов. Также мы планировали использовать Cassandra для восстановления доски при сбое Redis. Считывание из него всей доски занимало меньше 100 мс, что было достаточно быстро.
Здесь показано, как мы хранили цвета в Redis на примере доски 2х2:
Мы переживали, что можем упереться в пропускную способность чтения в Redis. Если много клиентов одновременно подключались или обновлялись, то все они одновременно отправляли запросы на получение полного состояния доски. Поскольку доска представляла собой общее глобальное состояние, то очевидным решением было воспользоваться кешированием. Решили кешировать на уровне CDN (Fastly), потому что это было проще в реализации, да и кеш получался ближе всего к клиентам, что уменьшало время получения ответа.
Запросы полного состояния доски кешировались Fastly с тайм-аутом в секунду. Чтобы предотвратить большое количество запросов при истечении тайм-аута, мы воспользовались заголовком stale-while-revalidate . Fastly поддерживает около 33 POP, которые независимо друг от друга осуществляют кеширование, поэтому мы ожидали получать до 33 запросов полного состояния доски в секунду.
Для публикации обновлений для всех клиентов мы воспользовались своим вебсокет-сервисом . До этого мы успешно использовали его для обеспечения работы Reddit.Live с более чем 100 000 одновременных пользователей для уведомлений о личных сообщениях в Live и прочих фич. Сервис также был краеугольным камнем наших прошлых первоапрельских проектов - The Button и Robin. В случае с r/Place клиенты поддерживали вебсокет-подключения для получения обновлений о размещениях тайлов в реальном времени.
API
Получение полного состояния доски
Сначала запросы попадали в Fastly. Если в нём была действующая копия доски, то он немедленно её возвращал без обращения к серверам приложений Reddit. Если же нет или копия была слишком старой, то приложение Reddit считывало полную доску из Redis и возвращало её в Fastly, чтобы тот закешировал и вернул клиенту.
Обратите внимание, что частота запросов никогда не достигала 33 в секунду, то есть кеширование с помощью Fastly было очень эффективным средством защиты приложения Reddit от большинства запросов.
А когда запросы всё же доходили до приложения, то Redis отвечал очень быстро.
Отрисовка тайла
Этапы отрисовки тайла:
- Из Cassandra считывается временная метка последнего размещения пользователем тайла. Если это было менее пяти минут назад, то мы ничего не делаем, а пользователю возвращается ошибка.
- Подробности о тайле записываются в Redis и Cassandra.
- Текущее время записывается в Cassandra в качестве последнего размещения тайла пользователем.
- Вебсокет-сервис отправляет всем подключённым клиентам сообщение о новом тайле.
Чтобы соблюсти строгую консистентность, все записи и чтение в Cassandra выполнялись с помощью QUORUM консистентного уровня .
На самом деле, здесь у нас возникла гонка, из-за чего пользователи могли размещать за раз несколько тайлов. На этапах 1–3 не было блокировки, поэтому одновременные попытки отрисовки тайлов могли пройти проверку на первом этапе и быть отрисованы – на втором. Похоже, некоторые пользователи обнаружили этот баг (либо они использовали ботов, которые пренебрегали ограничением на частоту отправки запросов) – и в результате с его помощью было размещено около 15 000 тайлов (~0,09% от общего количества).
Частота запросов и время ответов, измеренные приложением Reddit:
Пиковая частота размещения тайлов составила почти 200 в секунду. Это ниже нашего расчётного предела в 333 тайла/с (среднее значение при условии, что 100 000 пользователей размещают свои тайлы раз в пять минут).
Получение подробностей по конкретному тайлу
При запросе конкретных тайлов данные считывались напрямую из Cassandra.
Частота запросов и время ответов, измеренные приложением Reddit:
Этот запрос оказался очень популярным. Вдобавок к регулярным клиентским запросам люди написали скрипты для извлечения всей доски по одному тайлу за раз. Поскольку этот запрос не кешировался в CDN, то все запросы обслуживались приложением Reddit.
Время ответа на эти запросы было довольно небольшим и держалось на одном уровне в течение всего существования проекта.
Вебсокеты
У нас нет отдельных метрик, показывающих, как r/Place повлиял на работу вебсокет-сервиса. Но мы можем прикинуть значения, сравнив данные до запуска проекта и после его завершения.
Общее количество подключений к вебсокет-сервису:
Базовая нагрузка до запуска r/Place была около 20 000 подключений, пик - 100 000 подключений. Так что на пике мы, вероятно, имели около 80 000 одновременно подключённых к r/Place пользователей.
Пропускная способность вебсокет-сервиса:
На пике нагрузки на r/Place вебсокет-сервис передавал более 4 Гбит/с (150 Мбит/с на каждый инстанс, всего 24 инстанса).
Фронтенд: веб- и мобильные клиенты
В процессе создания фронтенда для Place нам пришлось решать много сложных задач, связанных с кроссплатформенной разработкой. Мы хотели, чтобы проект работал одинаково на всех основных платформах, включая настольные ПК и мобильные устройства на iOS и Android.
Пользовательский интерфейс должен был выполнять три важные функции:
- Отображать состояние доски в реальном времени.
- Позволять пользователям взаимодействовать с доской.
- Работать на всех платформах, включая мобильные приложения.
Главным объектом интерфейса был канвас, и для него идеально подошёл Canvas API . Мы использовали элемент
Отрисовка канваса
Канвас должен был отражать состояние доски в реальном времени. Нужно было нарисовать всю доску при загрузке страницы и дорисовывать обновления, приходящие через вебсокеты. Элемент canvas, использующий интерфейс CanvasRenderingContext2D , можно обновлять тремя способами:
- Рисовать существующее изображение в канвасе с помощью drawImage() .
- Рисовать формы с помощью разных методов отрисовки форм. Например, fillRect() заполняет прямоугольник каким-нибудь цветом.
- Конструировать объект ImageData и рисовать его в канвасе с помощью putImageData() .
Первый вариант нам не подошёл, потому что у нас не было доски в форме готового изображения. Оставались варианты 2 и 3. Проще всего было обновлять отдельные тайлы с помощью fillRect() : когда приходит обновление через вебсокет, просто рисуем прямоугольник размером 1х1 на позиции (x, y). В целом способ работал, но был не слишком удобен для отрисовки начального состояния доски. Метод putImageData() подходил гораздо лучше: мы могли определять цвет каждого пикселя в одном-единственном объекте ImageData и рисовать весь канвас за раз.
Отрисовка начального состояния доски
Использование putImageData() требует определения состояния доски в виде Uint8ClampedArray , где каждое значение - восьмибитное беззнаковое число в диапазоне от 0 до 255. Каждое значение представляет какой-то цветовой канал (красный, зелёный, синий, альфа), и для каждого пикселя нужно четыре элемента в массиве. Для канваса 2х2 необходим 16-байтный массив, в котором первые четыре байта представляют верхний левый пиксель канваса, а последние четыре - правый нижний.
Здесь показано, как пиксели канваса связаны со своими Uint8ClampedArray-представлениями:
Для канваса нашего проекта понадобился массив на четыре миллиона байтов - 4 Мб.
В бэкенде состояние доски хранится в виде четырёхбитного битового поля. Каждый цвет представлен числом от 0 до 15, что позволило нам упаковать два пикселя в каждый байт. Чтобы использовать это на клиентском устройстве, нужно сделать три вещи:
- Передать клиенту бинарные данные из нашего API.
- Распаковать данные.
- Преобразовать четырёхбитные цвета в 32-битные.
Для передачи бинарных данных мы использовали Fetch API в тех браузерах, которые его поддерживают. А в тех, которые не поддерживают, использовали XMLHttpRequest с responseType , имеющим значение “arraybuffer” .
Бинарные данные, полученные от API, в каждом байте содержат два пикселя. Самый маленький конструктор TypedArray , что у нас был, позволяет работать с бинарными данными в виде однобайтовых юнитов. Но они неудобны в использовании на клиентских устройствах, так что мы распаковывали данные, чтобы с ними было проще работать. Процесс простой: мы итерировали по упакованным данным, вытаскивали старшеразрядные и младшеразрядные биты, а затем копировали их в отдельные байты в другой массив.
Наконец, четырёхбитные цвета нужно было преобразовать в 32-битные.
Структура ImageData , которая нам понадобилась для использования putImageData() , требует, чтобы конечный результат был в виде Uint8ClampedArray с байтами, кодирующими цветовые каналы в очерёдности RGBA. Это означает, что нам нужно было осуществить ещё одну распаковку, разбивая каждый цвет на компонентные канальные байты и помещяя их в правильный индекс. Не слишком-то удобно выполнять четыре записи на каждый пиксель. Но к счастью, был ещё один вариант.
Объекты TypedArray по сути являются представлениями ArrayBuffer в виде массивов. Тут есть один нюанс: многочисленные инстансы TypedArray могут читать и писать в один и тот же инстанс ArrayBuffer . Вместо записи четырёх значений в восьмибитный массив мы можем записать одно значение в 32-битный! Используя Uint32Array для записи, мы смогли легко обновлять цвета тайлов, просто обновляя один индекс массива. Правда, пришлось сохранять нашу палитру цветов в обратном байтовом порядке (ABGR), чтобы байты автоматически попадали на правильные места при считывании с помощью Uint8ClampedArray .
Обработка обновлений, полученных через вебсокет
Метод drawRect() хорошо подходил для отрисовки обновлений по отдельным пикселям по мере их получения, но было одно слабое место: большие порции обновлений, приходящие одновременно, могли привести к торможению в браузерах. А мы понимали, что обновления состояния доски могут приходить очень часто, так что проблему нужно было как-то решать.
Вместо того чтобы немедленно перерисовывать канвас при каждом получении обновления через вебсокет, мы решили сделать так, чтобы вебсокет-обновления, приходящие одновременно, можно было объединять в пакеты и сразу скопом отрисовывать. Для этого были внесены два изменения:
- Прекращение использования drawRect() – мы нашли удобный способ обновлять много пикселей за раз с помощью putImageData() .
- Перенос отрисовки канваса в цикл requestAnimationFrame.
Благодаря переносу отрисовки в анимационный цикл мы смогли немедленно записывать вебсокет-обновления в ArrayBuffer , при этом откладывая фактическую отрисовку. Все вебсокет-обновления, приходящие между фреймами (около 16 мс), объединялись в пакеты и отрисовывались одновременно. Благодаря использованию requestAnimationFrame , если бы отрисовка заняла слишком много времени (дольше 16 мс), то это повлияло бы только на частоту обновления канваса (а не ухудшило бы производительность всего браузера).
Взаимодействие с канвасом
Важно отметить, что канвас был нужен для того, чтобы пользователям было удобнее взаимодействовать с системой. Основной сценарий взаимодействия - размещение тайлов на канвасе.
Но делать точную отрисовку каждого пикселя в масштабе 1:1 было бы крайне сложно, и мы не избежали бы ошибок. Так что нам был необходим зум (большой!). Кроме того, пользователям нужна была возможность легко перемещаться по канвасу, ведь он был слишком велик для большинства экранов (особенно при использовании зума).
Зум
Поскольку пользователи могли размещать тайлы раз в пять минут, то ошибки при размещении были бы особенно неприятны для них. Нужно было реализовать зум такой кратности, чтобы тайл получался достаточно большим, и его можно было легко поместить в нужное место. Это было особенно важно на устройствах с сенсорными экранами.
Мы реализовали 40-кратный зум, то есть каждый тайл имел размер 40х40. Мы обернули элемент