Tarantool для визуализации графов: опыт применения в крупном проекте

Евгений Манаев, системный архитектор

Сегодня мы расскажем об опыте использования Tarantool в одном из проектов компании Форс. Мы столкнулись с интересной и сложной задачей: предоставить инструмент для визуализации связей между объектами в большом озере данных, собранном нашим заказчиком.




Описание задачи

Заказчик накопил большое количество данных о своих объектах анализа и их взаимодействиях. Требовалось предоставить ему инструмент, позволяющий изучать конкретные объекты и связи между ними. В соответствии с ТЗ пользователь должен получить возможность выбирать объект и отображать его связи с другими объектами, а также связи этих объектов с объектами следующего уровня и так далее. Задача также включала поиск всех цепочек связей между двумя заданными объектами на некоторую глубину.
Структура данных была крайне разнородной, что усложняло задачу. Но главная трудность заключалась в обеспечении требуемой эффективности работы алгоритмов поиска: в озере насчитывалось более 10 миллиардов связей между объектами, при этом построение графов связей должно осуществляться в режиме онлайн, и задержки более 3 секунд были крайне нежелательны, а более 10 секунд — неприемлемы.

Почему мы выбрали Tarantool

Мы рассматривали разные графовые движки, но отказались от них из-за отсутствия официальной поддержки в России. Поэтому мы решили использовать отечественную in-memory СУБД, которая могла бы эффективно работать с графами. В итоге наш выбор пал на Tarantool.

Несколько слов о Tarantool

Tarantool — это продукт VK Tech, российского вендора корпоративного ПО. Представляет собой высокопроизводительную базу данных, работающую в оперативной памяти (in-memory). Она поддерживает не только хранение и быстрый доступ к данным, но и выполнение сложной бизнес-логики непосредственно на сервере с помощью встроенного языка программирования Lua. Одной из ключевых особенностей Tarantool является то, что каждый экземпляр (инстанс) работает в одном потоке операционной системы. Это значит, что каждый инстанс обрабатывает запросы последовательно, что упрощает управление памятью и уменьшает накладные расходы на синхронизацию потоков. При этом для увеличения производительности требуется запускать много инстансов параллельно.
Горизонтальное масштабирование в Tarantool обеспечивается модулем vshard, c помощью которого осуществляется распределение данных и балансировка нагрузки. Vshard позволяет создавать инстансы с двумя основными ролями:

• Router (координатор): принимает запросы от клиентов, координирует выполнение запросов на инстансах с данными и возвращает результаты.
• Storage (хранилище): непосредственно хранит данные и выполняет локальные запросы.

Данные распределяются по инстансам с использованием механизма шардирования, при котором данные разбиваются на "бакеты" (buckets). Каждой записи присваивается номер bucket_id, который определяет, на каком storage инстансе она будет храниться. Обычно bucket_id вычисляется на основе хеш-функции, примененной к ключевым полям данных (sharding key).

Первые попытки реализации

Модуль crud

Наши первые попытки использования Tarantool для решения задачи начались с модуля crud. Этот модуль предоставляет базовые функции для работы с данными в распределенной среде. Он позволяет выполнять стандартные операции, такие как вставка, удаление и выборка данных в одном "спейсе" — аналоге таблицы в реляционной базе данных.
Основное преимущество использования модуля crud заключается в его простоте и возможности работать с распределенными данными через единый интерфейс. Однако у этого подхода есть серьезные ограничения. Например, crud не поддерживает операции JOIN, которые необходимы для объединения данных из нескольких спейсов на основе ключевых полей. Это означает, что если вам нужно объединить данные из разных спейсов, вам придется реализовать эту логику самостоятельно с использованием Lua.
Использование Lua для выполнения JOIN приводит к нескольким проблемам:

• Высокие накладные расходы на пересылку данных: поскольку операция JOIN осуществляется на стороне router, все данные, необходимые для объединения, должны быть загружены из всех storage инстансов, что создает значительную нагрузку на сеть.
• Проблемы с памятью: router может столкнуться с нехваткой памяти, так как он должен обрабатывать большие объемы данных, поступающих от storage инстансов.

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

Модуль sbroad

В поисках решения мы обратились к модулю sbroad от российской компании Picodata. Этот модуль предназначен для выполнения распределенных запросов в кластере Tarantool и предоставляет более продвинутые возможности для работы с данными.
Sbroad позволяет выполнять запросы, которые распределяются между несколькими инстансами, что теоретически должно было бы улучшить производительность и снизить нагрузку на сеть. Однако, на практике мы столкнулись с рядом проблем:

• Ограниченная функциональность: на момент начала использования sbroad не поддерживал некоторые важные SQL-конструкции, такие как IN (VALUES(..)), что ограничивало его применение в сложных сценариях.
• Зависимость от шардирования: при неоптимальном шардировании данных скорость работы оставалась низкой из-за большого объема пересылки данных между инстансами, что нивелировало преимущества распределенной обработки.

Собственная обертка all_select

Осознав ограничения сторонних решений, мы решили разработать собственную обертку для выполнения распределенных запросов, названную all_select. Идея заключалась в том, чтобы запускать параллельные запросы на всех storage инстансах и собирать результаты в единый список на стороне router.
Этот подход обеспечивал большую гибкость и контроль над процессом выполнения запросов, но также имел свои недостатки:

• Необходимость корректного шардирования: для правильной работы JOIN все условия должны включать поля sharding key. В противном случае данные могут быть распределены по разным инстансам, что приведет к некорректным результатам.
• Управление сложностью: реализация сложной логики запросов на Lua требует значительных усилий по написанию и поддержанию кода, что увеличивает вероятность ошибок.

Vynil vs Memtx

При выборе между различными хранилищами данных в Tarantool мы изначально использовали Vynil для экономии памяти. Vynil — это хранилище, которое сохраняет данные на диске, не требуя большого количества оперативной памяти для работы с большими объемами данных. Оно использует стратегию "запись вперед" (write-ahead log) и оптимизировано для операций с дисковыми данными.
Однако, когда возникла необходимость в выполнении операций JOIN и обработке большого количества записей, стало очевидно, что производительность Vynil недостаточна. В таких сценариях in-memory движок Memtx показал себя гораздо лучше. Memtx хранит все данные в оперативной памяти, что обеспечивает очень быструю выборку и обработку данных, особенно в случаях, требующих частых операций чтения и записи. Поэтому мы решили перевести часто используемые витрины представления данных на Memtx.

Работающий подход для распределенных запросов

Шардирование для локальных JOIN

Одной из ключевых стратегий для обеспечения высокой производительности распределенных запросов является выполнение всех операций JOIN и фильтрации локально на storage инстансах, а на router — только сборка и возврат результатов. Это значительно сокращает объем данных, передаваемых по сети, и снижает нагрузку на router.
Для достижения этого необходимо, чтобы все поля, составляющие sharding key, участвовали в условиях JOIN. Это гарантирует, что данные, необходимые для выполнения запроса, будут находиться в одном бакете и, следовательно, на одном storage инстансе. Например, если у вас есть два спейса с ключевыми полями (fieldA1, fieldA2) и (fieldB1, fieldB2), то запрос вида:


будет корректным, так как все ключевые поля sharding key задействованы, и данные будут локализованы в одном бакете.

Копии спейсов с разным шардированием

В реальных сценариях разные запросы могут требовать выполнения JOIN по различным наборам полей. Оптимальным подходом в такой ситуации может быть создание нескольких копий каждого спейса с разными sharding key. Это позволяет гибко выбирать подходящую копию спейса для конкретного запроса, минимизируя пересылку данных между инстансами.
Например, если один запрос использует sharding key (fieldA1, fieldA2), а другой (fieldA2, fieldA3), то можно создать две копии спейса с соответствующими ключами. При этом важно обеспечить синхронизацию данных между копиями, чтобы они всегда содержали актуальную информацию. Это можно делать через распределенные транзакции или посредством принятия организационных мер, таких как триггеры или регулярные задачи на обновление.

Типовая функция выборки данных

 При правильном шардировании данных типовая функция выборки данных на Lua может выполняться следующим образом:

1.     Формирование SQL-запроса.
Создается SQL-запрос, который будет выполняться локально на всех storage инстансах. Запрос должен учитывать параметры поиска и поля шардирования, чтобы минимизировать объем данных, передаваемых на router.

 2.     Выполнение запроса на storage.
Запрос выполняется параллельно на всех соответствующих storage инстансах. Это обеспечивает быструю обработку и сбор данных.

 3.     Повторение при необходимости.
В случае сложных запросов, где необходимо учесть разные условия поиска, этапы 1 и 2 могут повторяться для других комбинаций параметров. Это связано с ограничениями Tarantool SQL на количество условий WHERE, которые могут включать составные условия и фильтрации.

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

Алгоритм обхода больших графов

Поиск цепочек

Одной из задач, которую мы решали с помощью Tarantool, была задача поиска путей в графе. Представьте себе граф как сеть, состоящую из узлов (вершин) и связей (ребер) между ними. В нашем случае узлы представляют собой объекты анализа, а связи — взаимодействия между ними. Мы разработали алгоритм, который позволяет находить все пути заданной глубины между заданными узлами.
Заказчику была важна возможность нахождения и просмотра именно всех вариантов путей. При поиске по большим данным это может порождать комбинаторный взрыв — экспоненциальный рост количества найденных путей по мере роста глубины. Это означает, что все найденные пути нельзя хранить — для хранения может просто не хватить вычислительных ресурсов.
При этом заказчику было достаточно постраничного просмотра списка найденных путей. Поэтому нами было принято решение хранить узлы, через которые проходят найденные пути. А пути восстанавливать на основе найденных узлов по мере необходимости — при отображении очередной страницы.
Глубина поиска в нашем ТЗ была фиксированной, поэтому для решения первой части задачи мы смогли использовать алгоритм на основе SQL, который работает достаточно эффективно на шардированных данных. Алгоритм включает в себя следующие шаги:

1.     Инициализация:

• Создаем временную таблицу, в которую добавляем начальную вершину. Эта таблица будет хранить узлы текущего уровня.

 2.     Итеративный SQL-запрос:

На каждой итерации, пока не достигнута максимальная глубина:

• Выполняем SQL-запрос, который выбирает все узлы, достижимые из текущих узлов, и добавляет их в таблицу следующего уровня. Данный запрос содержит JOIN, который при правильном шардировании временной таблицы и таблицы со связями графа выполняется локально на каждом сервере кластера.
• Обновляем таблицу, представляющую текущий уровень узлов.

 3.     Финальная проверка:

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

Задержка репликации

В процессе реализации алгоритма поиска узлов в цепочках мы столкнулись с явлением, известным как "задержка репликации". Это происходит, когда данные записываются на master реплики, но еще не успевают дойти до read-only реплик. В результате, когда следующий этап алгоритма пытается обратиться к данным на read-only репликах, он может получить устаревшую информацию.
Для решения этой проблемы мы решили использовать master реплики для операций выборки в рамках алгоритма поиска узлов. Это гарантирует, что все запросы работают с актуальными данными, и минимизирует риск получения некорректных результатов из-за задержек в репликации.

Заключение

Работа по решению задач проекта позволила нашей команде приобрести важный опыт применения Tarantool для обработки очень больших объемов данных. В процессе реализации этой задачи мы сделали следующие выводы:

• В экосистеме Tarantool есть разные инструменты для распределенной обработки данных, но все они имеют свои особенности, поэтому необходимо каждый раз выбирать инструмент, оптимальный для конкретной задачи.
• Ключевым аспектом быстрого доступа к данным является правильное шардирование.
• Важно учитывать объемы пересылки данных, объем данных на router и эффект задержки репликации.

Полученный опыт и навыки практического использования Tarantool в составе проектных решений позволят команде Форс в дальнейшем с еще большей уверенностью браться за решение задач, связанных с обработкой больших объёмов данных в условиях, максимально приближенных к реальному времени.

https://www.fors.ru/company/news/tarantool-dlya-vizualizatsii-grafov-opyt-primeneniya-v-krupnom-proekte/