Свои исследования в данной области в интересах наших клиентов мы начали проводить примерно с 2015-2016 годов. Нашими целями были определение long-листа систем графового анализа, оценка их по широкому набору критериев и выделение short-листа для дальнейших испытаний в типовых задачах, решаемых системами такого класса.

В области нашего интереса были следующие решения:

• Neo4j
• Titan
• JanusGraph (Развитие Titan)
• Orient DB
• Arango DB
• Datastax
• Infinite Graph
• SAS SocialNetwork Analysis
• GraphLab
• GraphBase
• HypergraphDB
• SNAP
• Apache Spark GraphX
• Stardog
• IBM System G

Претенденты оценивались по следующим критериям:

• Тип графа
• Поддержка языков запроса
• Реализованные методы
• PageRank
• Clique Search
• Shortest Path
• Shortest Path на подграфе
• Получение смежных вершин
• API
• Интеграция со сторонними инструментами визуализации
• Максимальный размер графа (Вершин х Ребер)
• Поиск по внешнему идентификатору
• Масштабируемость
• Хранимые пользовательские функции
• Атрибутика вершин и ребер
• Возможность создания сессионного графа
• Возможность сохранения локального графа в разрезе пользователя/Sandbox
• Поддержка направлений связей графа
• Поддержка ролевой модели
• Высокая доступность (HA) “из коробки”
• Встроенные инструменты визуализации
• Интерфейс администрирования
• Интерфейс пользователя-аналитика
• Вариативность версий, отличия, стоимость, поддержка
• Наличие прямой поддержки поставщика ПО в случае необходимости
• Зрелость, развитие продукта и наличие внятного roadmap’а
• Наличие community версии и ее ограничения относительно enterprise
• Стоимость лицензий или подписки в случае покупки
• Наличие и развитость сообщества
• Наличие поддержки/Партнера в РФ
• Известные проблемы, особенности, и ограничения

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

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

Спустя некоторое время с 2018 года один из крупнейших финансовых системообразующих банков обратился к нам с предложением разработать и внедрить у себя систему графового анализа, но предварительно провести предпроект, чтобы выбрать движок и проработать архитектуру. Ничего не оставалось, кроме как взвесить опять весь "зоопарк" систем, определить основных претендентов на “престол”, провести нагрузочные испытания, разработать и защитить целевую архитектуру и наконец выполнить само внедрение системы.

Критерии оценки мы не пересматривали, а освежили веса по состоянию каждого продукта на тот момент времени и проверили, не появилось ли чего-то нового на горизонте.

Общие выводы получились следующие:

Ни одна система не обладает достойным функционалом пользовательского графического интерфейса “из коробки”. Эту задачу нужно решать самостоятельно.
В части GUI-интерфейса администрирования встречаются вполне интересные и зрелые решения, закрывающие большинство требований.

Некоторые популярные системы имеют сильно урезанный функционал в так называемой бесплатной community edition, который, как правило, востребован со стороны заказчика.

Важным критерием является чисто субъективная история “удобства пользования”. Некоторые системы имеют свои аналитические языки запросов, которые более понятны неподготовленным пользователям и в особенности пользователям, ранее работавшим только с SQL.

Двухлетний интервал между исследованиями показал, что некоторые системы успели умереть, другие непонятно куда и как плывут и не имеют четкого roadmap или он “управляется” сообществом со всеми вытекающими минусами такого подхода.

По результатам взвешивания в наш short list попали следующие претенденты:

• Orient DB;
• Arango DB;
• JanusGraph.

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

По совокупности тестов победителем вышла Arango. Для Arango мы намеренно не использовали in-memory-хранение как опцию, так как в предполагаемой боевой конфигурации его бы и не было. Позднее сам вендор отказался от этой опции, и сейчас используется в качестве persistent storage только rocksDB. На тот момент мы еще не знали, что родная утилита arangoimp может загружать данные в параллельном режиме, так что можно считать, что и в тесте на загрузку ArangoDB могла бы тоже одержать верх над остальными.

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

Use case Группа связанных компаний

Для заданной начальной компании необходимо выполнить поиск связанных и аффилированных ЮЛ. При этом на основе внутренних источников данных и данных СПАРК определяются связи с другими компаниями и лицами через прямое владение, а также через поиск общих владельцев и руководителей.

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

Use case Определение и маркировка мошеннических связей

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

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

Use case Использование графового анализа в работе моделей

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

Архитектура

Графовые движки имеют несомненное преимущество над традиционными реляционными СУБД в решении типовых алгоритмов поиска связанности не только в том, что они эти задачи выполняют быстрее, но и в том, что они найдут связи, как правило, неочевидные либо требующие нетривиального написания кода в реляционном движке. Но, как ни парадоксально, все очевидные связи можно и нужно определять как раз в реляционном движке. На практике это означает, что в графовую БД данные желательно загружать подготовленными заранее, определив список вершин и список связей, каждый со своим атрибутивным составом. Конечно, если для этого есть соответствующая среда с требуемыми вычислительными мощностями.

В нашей реализации витрина состояла из 22 типов вершин общим количеством 350 миллионов записей и 750 миллионов связей 87 типов. Каждый тип имел свой атрибутный состав и историчность, если она требовалась. Подготовка витрины выполнялась в среде Hadoop (детально о системе можно прочитать тут). Все внутренние и внешние источники данных интегрированы заранее с Hadoop. Для преобразования данных использовался процессинговый движок Impala.

После подготовки витрины она преобразовывается в транспортный формат и с помощью родной утилиты Arangoimp в параллельном режиме загружается в back-движок Arango, который на самом деле реализован на документо-ориентированной rocksDB. Загрузка осуществляется инкрементально для каждого отдельного объекта и атомарно на уровне Arango. Данные автоматически индексируются.

Движок Arango развернут в кластерной конфигурации, состоящей из трех узлов, ведь изначально при выборе решения шардирование было одним из обязательных требований. В качестве сторонней СУБД, предназначенной для хранения всех метаданных решения, журналирования и метаданных фронт-части, используется Postres. Веб-часть реализована на базе открытых фреймворков. В качестве библиотеки визуализации графа используется D3.js. Это, к слову, не единственная библиотека в природе, реализующая эту функцию с необходимым уровнем визуализации и скорости работы, но выбор D3 скорее был связан с положительным предыдущим опытом команды заказчика.

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

Все взаимодействие Arango с веб-интерфейсом реализуется через REST API. Само приложение интегрировано с LDAP и имеет ролевую модель для ограничения доступа к чувствительным данных тех пользователей, кому он не положен по должностным обязанностям. В целом по реализации требований информационной безопасности можно писать как минимум отдельную статью.

Эксплуатация системы в данном архитектурном подходе выдержала испытание временем и решила поставленные задачи. Успех не проходит незаметным, и в конце 2019 года другая финансовая организация из списка системообразующих банков обратилась к ГлоуБайт за реализацией подобного решения со схожими бизнес-задачами. Вопрос выбора движка и проработки архитектуры уже не стоял. Были внесены минорные изменения в архитектуру, связанные скорее со спецификой существующих стандартов заказчика. Например, витрина в Hadoop регламентно собирается на Spark и имеет уже больший объем данных, чем в случае предыдущего внедрения системы. Витрина состоит из 80 типов связей общим количеством 1.2 миллиарда и 2.5 миллиарда связей. Arango также был развернут в кластерной конфигурации. Веб-интерфейс был разработан с нуля под специфику предполагаемого бизнес-процесса и интеграции с системами клиента.

Практические выводы

За 4 года нашего практического опыта работы с Arango система очень активно развивалась и продолжает развиваться по прозрачному и понятному roadmap’у. Появился компонент ArangoSearch на базе движка Lucene для полнотекстового индексирования и поиска с ранжированием с поддержкой русского языка как одного из основных наряду с английским, немецким и китайским. Данный компонент мы успешно использовали в проектах для реализации google-like поиска, что избавило нас от потребности внедрения сторонних компонент вроде Elastic.

Появилась возможность разворачивать систему в окружении Docker, что открыло новые возможности в инфраструктуре публичного или частного облака. Это дает возможность развернуть Arango как для quick win-решений, так как поднять cluster или single можно буквально за 5 мин. с минимальным конфигурированием, так и для зрелых промышленных процессов за счет расширенных возможностей гибкой настройки и самого движка и подсистемы хранения rocksDB.

Дополнительно “из коробки” доступен ряд утилит, которые значительно упрощают администрирование и поддержку экземпляров ГБД. К таким можно отнести утилиту ArangoDB Starter, которая представляет из себя обертку для демона arangod и позволяет инициализировать новые экземпляры БД с минимальным конфигурированием, отвечает за мониторинг процессов, их автоматический перезапуск и расширенное журналирование. Таким образом, существует уже готовый механизм перезапуска сервисов в случае их падения. Также есть ряд инструментов, которые выполняют экспорт данных коллекций в различных форматах, что упрощает работы по интеграции со сторонними системами.

Документация Arango наполнена очень качественно, появилась система обучения и сертификации специалистов. Четыре первых в мире сертифицированных специалиста ArangoDB являются сотрудниками нашей команды ГлоуБайт.

Одним из приятных моментов работы с Arango для нас стал ее встроенный язык аналитических запросов AQL. Во многом он сформировал в чем-то субъективное мнение о системе и ее дружелюбности для простого непосвященного в нюансы графового анализа пользователя. Как показала практика, аналитик или разработчик, знакомый с обычным SQL, может буквально за несколько часов адаптироваться к среде AQL и начать эффективно работать в Arango. Это дает существенное снижение порога входа в технологию по сравнению с другими системами.

Из особенностей отметим следующие моменты.

Arango работает с AQL как «классическая» SQL СУБД:

• выполняет разбор (parsing) запроса;
• составляет execution план;
• исполняет запрос;
• дает вывод результата.

Для выполнения есть большой выбор:

• web-интерфейс собственной веб-консоли;
• Arangosh (shell-консоль);
• HTTP REST API. Этот метод стоит считать основным при обращении из стороннего приложения. В нашем случае фронт-интерфейс обращается через REST;
• достойный список API и поддерживаемых языков (Python, Java, JavaScript, Scala, PHP, Go, Ruby, .NET). В нашем случае специалисты Data Science обращаются к базе данных Arango из JupyterHub ноутбука на Python напрямую.

Примеры простых запросов:

Обход графа на заданную глубину 5 от вершины “v_natural/123”

FOR v,e,p IN 1..5 ANY “v_natural/123”

GRAPH NaturalGraph

RETURN p

Поиск кратчайшего пути между вершинами “v_natural/123” и “v_natural/999”

FOR v IN ANY SHORTEST_PATH

“v_natural/123” TO “v_natural/999”

GRAPH NaturalGraph

RETURN v

Одной из известных проблем при обходе высоко связных графов является наличие вершин-концентраторов, например, номер телефона работодателя. Попадание в такую вершину может негативно сказываться на производительности траверса и, ввиду того, что, зачастую, на сформированный подграф накладываются ограничения в виде количества итоговых путей, способно приводить к нерелевантным результатам. Данная проблема с легкостью решается формированием AQL-алгоритма, который прекращает траверс по путям, содержащим заявленное количество связей. Это возможно благодаря встроенному механизму параметризации запросов, где мы можем задать нужный threshold, и наличию опций для обхода графа (breadth-first/depth-first). В виду того, что обход графа довольно затратная операция, часто в графовых движках “под капотом” используется подход, при котором сперва выполняется траверс по всему графу, а далее идет фильтрация по заданным условиям - значениям атрибутов. Мы получаем ситуацию, при которой может возникнуть избыточная утилизация памяти с учетом того, что итоговый data set значительно меньше читаемого из источников. В кластерных конфигурациях это дополнительно приведет к просадке производительности на узле, в котором происходит финальная агрегация. В ArangoDB проблема нивелируется за счет наличия оператора PRUN, который позволяет фильтровать вершины и связи непосредственно в момент траверса, существенно снижая дата-трафик между узлами и утилизацию памяти.

Что дальше

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

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

Авторы:
Евгений Вилков, Технический Директор Практики, Ведущий Архитектор Данных
Алексей Фурсенко, Архитектор Данных