Проектируем веб-страницу, отображающую миллион элементов

Может ли браузер справиться с миллионом элементов? Если вы когда-нибудь пробовали рендерить в браузере миллион элементов <div>, то знаете, что происходит — он вылетает, зависает и перестаёт реагировать.

Недавно мы выпустили фичу, привлёкшую большое внимание — загрузку и визуализацию до миллиона спанов на нашей странице детализации трассировок. Это вызвало любопытство у пользователей и разработчиков, поэтому многие начали задавать вопрос: как нам это удалось?

Наша мотивация ясна — пользователям нужна эта возможность. Она позволяет использовать новые процессы отладки, упрощая эффективный анализ огромных трассировок.

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

В этом блоге мы подробно расскажем о методиках, позволивших беспроблемно загружать и анализировать любое количество спанов.

Для начала мы вкратце расскажем о том, что же такое трассировки (trace).

Что такое трассировка? (И почему для неё важен миллион спанов)

Трассировка — это путь перемещения запроса по приложению, будь то монолит или микросервисы. Фундаментальный элемент трассировки — это спаны, составляющие трассировку. Спан (span) — это единица работы, выполняемой вашим приложением.

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

Трассировки также полезны в системах с фоновыми задачами, в которых в одной трассировке можно выполнять мониторинг состояния каждой фоновой задачи, запущенной инициатором.

Возьмём для примера трейдинговое приложение. Запланированное обновление стоимости ценных бумаг может привести к массовому обновлению всех доступных ценных бумаг на бирже. Любые задержки обновлений могут принести пользователям существенные потери. Именно здесь проявляются преимущества трассировок в выявлении сетевых задержек, торможения сторонних API и многого другого. Но если трассировки состоят из миллионов спанов, то как их эффективно загружать, анализировать и отлаживать?

Эту проблему мы и намеревались решить.

Задача: размер трассировки не должен ни на что влиять

Как загружать и отлаживать трассировки любого размера во вкладке браузера?

Мы намеренно отказались от ограничений трассировок по размерам. Наша цель была простой: какой бы большой ни стала трассировка, пользователи должны иметь возможность загружать и отлаживать её без вылетов, задержек и торможений.

Мы разбили задачу на две основные проблемы:

1. Загрузка большой трассировки – эффективное получение, обработка и рендеринг миллиона спанов.

2. Отладка большой трассировки – возможность практичного анализа огромных трассировок пользователями.

Загрузка большой трассировки: разбиваем проблему на части

Для загрузки большой трассировки в браузере нужно решить три задачи:

• Эффективное получение спанов из базы данных

• Обработка данных согласно контракту API

• Рендеринг спанов во фронтенде без узких мест производительности

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

Рендеринг миллиона спанов — ограничения браузера

Может ли вообще браузер обрабатывать миллион элементов? (Краткий ответ: нет)

Мы начали с тестирования абсолютных пределов того, что может обрабатывать браузер. Поначалу мы пользовались брутфорсом — рендерили миллион тэгов <div> на пустой странице странице со строками lorem ipsum в приложении на React.

Результат: вкладка браузера зависала. Полный провал.

Это стало нашим первым важным уроком: как бы мы ни старались, у нас не получится отобразить миллион спанов во фронтенде.

Значит, нужно ограничить количество элементов, которые рендерятся в DOM-дереве. В наших обсуждениях всплыла популярная концепция виртуализации.

Решение: рендерить только то, что видит пользователь (виртуализация)

Виртуализация — это техника оптимизации UI, при которой данные хранятся в виртуальной памяти, а рендерится только ограниченное их подмножество. Этот паттерн предназначен для минимизации количества элементов в DOM, уменьшения количества изменений и общего снижения необходимых ресурсов CPU и памяти.

Благодаря виртуализации:

• Мы можем рендерить только те спаны, которые находятся во вьюпорте пользователя.

• В процессе скроллинга новые спаны заменяют старые динамически.

• Работа UI остаётся плавной вне зависимости от размера трассировки.

Даже если нужно рендерить миллион или миллиард элементов, мы рендерим только фиксированное их подмножество и обновляем его динамически в зависимости от действий пользователя (в нашем случае — от скроллинга/нажатий мышью).

Мы снова попробовали отрендерить миллион div, на этот раз с виртуализацией.

Нам снова не удалось обеспечить плавную загрузку. Мы попробовали провести пару тестов с меньшим количеством элементов: 100 тысяч и 200 тысяч div. Нам удалось загрузить их в браузер, но мы не были довольны производительностью интерфейса.

Стало очевидно, что:

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

• Не подойдёт и любая «тяжёлая» обработка данных. То есть нам нужен такой контракт API, чтобы фронтенд мог просто рендерить интерфейс без какой-либо обработки.

• Любые обсуждения и исследования по размеру HTTP-вызовов становятся неважны, ведь мы будем нарезать данные.

Основываясь на вышеизложенном, мы закрыли эту тему с таким выводом:

• Нужно виртуализировать рендеринг данных во фронтенде.

• Ограничивать размер данных для рендеринга даже при виртуализации.

• Не накапливать данные между множественными запросами во фронтенде.

Получение миллиона спанов — оптимизация бэкенда

Для получения больших трассировок требуется эффективная работа с запросами. Для хранения и извлечения данных телеметрии мы используем столбчатую базу данных.

Благодаря нагрузочному тестированию и индексированию мы достигли времени отклика меньше секунды для трассировок с миллионом спанов. Подробности этой оптимизации заслуживают отдельной статьи.

Нарезание миллиона спанов — основа пагинации в иерархических данных

Сложность: трассировки — это не плоские данные

Вернёмся к нарезанию данных для рендеренга во фронтенде. Самое популярное решение для нарезания данных — это пагинация. Однако мы занимались реализацией пагинацией только плоских структур данных, но никогда не слышали о пагинации древовидных структур данных, а трассировки по природе своей принадлежат к семейству графов.

После пары неудачных поисков по StackOverflow (ответами почти всегда были «не делайте этого» и ни одного ответа о том, как это сделать), мы решили подойти к задаче по-другому. Что, если мы не будем рассматривать трассировку как граф?

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

Граф трассировки начинается с корня трассировки, за которыми следуют дочерние поддеревья корневого узла. Тот же паттерн рекурсивно применяется и ко всем подддеревьям дочерних узлов. Это напомнило нам о знаменитом прямом типе обхода (pre-order traversal) графов!

Что такое «прямой тип обхода»?

Прямой обход — это тип обхода вершин дерева, который следует политике Root-Left-Right (в случае двоичного дерева), где:

• Корневой узел поддерева посещается первым.

• Затем выполняется обход левого поддерева.

• Наконец, обходится правое поддерево.

Превращение графа в плоский с сохранением иерархии

Прямой обход трассировки создаёт плоский список спанов, имеющий следующий порядок:

ROOT_NODE, CHILD-1 , CHILD-1-SUBTREE , CHILD-2 , CHILD-2-SUBTREE……

Делая трассировки плоскими при помощи прямого обхода, мы создаём структуру, которая:

• Сохраняет естественный порядок трассировки.

• Позволяет использовать пагинацию, как плоский список.

• Не меняет соотношения родительских и дочерних узлов.

Синхронизация бэкенда и фронтенда — умное использование окон для плавного UX

Динамическая настройка данных на основании фокуса пользователя

Одной пагинации недостаточно. Пользователям необходимо удобство отладки, то есть UI всегда должен загружать спаны в окрестностях интересующей их точки.

Перед тем, как мы могли бы начать генерацию прямого обхода данных трассировки, нам нужно было узнать, какие спаны были свёрнуты/развёрнуты.

После генерации плоского списка нам нужно определиться со смещениями и диапазоном отправляемых во фронтенд данных. Смещение и диапазон в основном будут обновляться при помощи пары взаимодействий пользователя с интерфейсом.

• Свёртывание/разворачивание спана

• Скроллинг по списку спанов.

Каждое из этих действий подразумевало необходимость ещё одной сущности в полезной нагрузке запроса, используемой в качестве якоря смещения. Мы назвали эту сущность interestedSpanID.

Мы реализовали прямой обход и interestedSpanID для взаимодействия пользователя с интерфейсом. Так как нам требовалось избежать накопления избыточных данных во фронтенде, обеспечив при этом плавный процесс, пришлось определить оптимальный объём отправляемых во фронтенд данных.

В качестве центра окна со смещением мы выбрали interestedSpanId и отдали 40% окна под просмотр предыдущих данных, а 60% окна — под новые спаны.

Мы определили сфокусированное окно для динамического получения спанов:

Нижняя граница  → i - 0.4 * SPAN_LIMIT_ON_FRONTEND   Верхняя граница  → i + 0.6 * SPAN_LIMIT_ON_FRONTEND  Результат -> PREORDER_TRAVERSAL[LOWER_LIMIT, UPPER_LIMIT]

Где:

• i = индекс interestedSpanID.

• SPAN_LIMIT_ON_FRONTEND = количество видимых на экране спанов.

• 40% спанов — исторические, 60% — новые.

Благодаря этому пользователи всегда получают релевантные спаны без задержек во фронтенде.

Отладка миллиона трассировок

Загрузка миллионов спанов окажется бесполезной, если пользователи не смогут найти то, что им нужно. Мы добавили:

• Поиск по спанам: фильтрацию спанов по атрибуту (например, service.name = «payment-service»).

• Навигацию вперёд/назад: беспроблемное перемещение между связанными спанами.

Ещё один ключевой аспект упрощения отладки большой трассировки — наш синхронизированный режим отображения waterfall и flamegraph. Он сильно упрощает выявление местоположения конкретного спана в транзакции.

Теперь даже если пользователи проскроллят до 490-тысячного спана, они сразу увидят, где он находится в общей картине.

Трассировки без ограничений

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

Краткое список наших решений:

• Ограничения браузера — использовали виртуализацию.

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

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