СУБД для социальных сетей

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

В графовой структуре используются объекты двух видов: именованные узлы и именованные дуги. В качестве иллюстрации рассмотрим СУБД, которые работают с данными, представленными в разработанной консорциумом W3C спецификации RDF [1], имеющей вид триплета: субъект-предикат-объект. Все данные в RDF можно изобразить в виде ориентированного графа, где объект и субъект — это узлы, а предикат — дуга от субъекта к объекту. Такой способ представления данных удобен для хранения данных социальных сетей и метаданных (вспомогательных данных). Например, если пользователь А следит за новостями пользователя Б, то из узла А идет дуга в узел Б с характеристикой «следить за новостями». Либо если от каждого пользователя какой-либо системы требуется указывать город своего проживания, то это можно отобразить следующим образом: «пользователь» (субъект) — «проживает в» (предикат) — «город» (объект). Наличие двунаправленной связи позволит найти людей, живущих в том же городе, что и определенный пользователь, или всех пользователей, проживающих в данном городе. Поиск соседей или поиск наличия связи между элементами намного проще выполнять именно на графах, поскольку по сравнению с реляционными базами здесь нет необходимости выполнять ресурсоемкие операции объединения таблиц.

Для работы с данными в модели RDF используется язык запросов SPARQL [1]. В ходе выполнения запроса система просматривает все подходящие под заданные условия триплеты и выводит данные из них или из зависящих от них. Пусть, например, pers — сокращенное имя для адреса www.example.org/person/ и пусть имеется база из триплетов (см. таблицу).

Пример фрагмента базы триплетов

Рассмотрим такой запрос

PREFIX pers: 
SELECT ?name
WHERE
 {
   ?name _:works ?city.
   pers:Josef_Svejk_:lives ?city
 }

Область SELECT объявляет, какие данные нас интересуют, а в самом запросе требуется вернуть значения переменной? name (все переменные начинаются со знака вопроса). Область WHERE указывает условие, в соответствии с которым ищется ответ:

name
pers:Senior_Lukas

В этом запросе ищутся все пары триплетов, у которых совпадают объекты (переменная ?city), предикат одного из триплетов называется _:lives, предикат другого _:works, причем субъект триплета с предикатом _:lives фиксирован и равен pers:Josef_Svejk. Здесь объявленная переменная ?name в области SELECT и WHERE имеет одно и то же значение, из чего следует, что результатом на запрос будут субъекты тех триплетов, которые удовлетворяют условиям, описанным в области WHERE. В этом конкретном случае подходит только одна пара триплетов:

pers:Senior_Lukas _:works «Prague».
pers:Josef_Svejk _:lives «Prague».

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

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

Одна из распространенных сегодня графовых СУБД — это Neo4j, она поддерживает механизм транзакций и позволяет работать с огромными объемами данных (до нескольких миллиардов узлов в графе). СУБД обеспечивает устойчивость данных путем их распределенного хранения. Приятным дополнением является возможность визуализации данных. В качестве языка запросов Neo4j использует собственный язык Cypher. СУБД Neo4j распространяется под лицензией GPLv3.

СУБД FlockDB изначально разрабатывалась для компании Twitter и примечательна тем, что оптимизирована для операций поиска соседних узлов, а не для операций обхода графа целиком. Сервис Twitter позволяет получать доступ к списку подписчиков конкретного пользователя и наоборот — к списку аккаунтов, на новости которых он подписан. Владея такой информацией, можно каждому пользователю показывать только сообщения тех авторов, на которых он подписан. Эта информация должна извлекаться достаточно быстро, для чего и была специально разработана FlockDB, весьма, кстати, устойчивая к сбоям. Для этой СУБД используется лицензия Apache.

СУБД Virtuoso — прогрессивная и производительная система, которая, помимо работы с данными в виде RDF, позволяет работать с SQL и XML. Эта СУБД обладает весьма гибкими конфигурациями сервера. Кроме того, имеется скрипт для выполнения массовой загрузки, заставляющий систему загружать данные порциями, ускоряя процесс загрузки целиком, а не по одному триплету. Благодаря тому, что Virtuoso написана на языке Cи/C++, имеется возможность полностью контролировать все выделенное пространство памяти, не позволяя операционной системе его изменять, причем можно создавать дополнительные индексы для ускорения обработки запросов. В коммерческом издании системы есть возможность одновременного запуска сервера на нескольких машинах для обеспечения безопасности или для ускорения обработки. Каждая машина производит вычисления над своей порцией данных, после чего возвращает результаты заранее определенной главной машине в сети, которая собирает полученные результаты и формирует из них финальный ответ. Открытая версия Virtuoso распространяется под лицензией GPLv2.

СУБД Sesame предназначена для хранения данных RDF, обработки SPARQL-запросов и операций с небольшими графами. Система не обладает обширным выбором настроек и использует все пространство памяти, которое было выделено JVM при запуске приложения, поэтому в тех случаях, когда приходится работать с большим графом, может понадобиться увеличение объема памяти JVM, если стандартного значения будет недостаточно. Интересной особенностью системы является возможность работы с двумя стратегиями представления графа внутри системы. Первая — Memory Store — предусматривает хранение целиком всего графа в оперативной памяти. Такой подход удобен при работе с небольшими графами, помещающимися в оперативной памяти. Вторая — Native Store —предлагает весь граф размещать на диске. При использовании этой стратегии можно создавать дополнительные индексы, что ускоряет работу. СУБД распространяется по лицензии BSD-3.

СУБД Parliament поддерживает индексы и позволяет обращаться к своей функциональности через Sesame. Эта СУБД существенно уступает по производительности уже перечисленным системам, однако в ней имеется возможность использования временных индексов (temporal indexing), структурирующих информацию по времени изменения данных. Кроме того, в системе реализована поддержка стандарта GeoSPARQL, который применяется для работы с географическими данными. Распространяется под лицензией BSD.

Распределенная графовая СУБД Titan поддерживает различные хранилища, используемые сегодня для обработки Больших Данных (Apache Cassandra, Apache HBase, Oracle BerkeleyDB и Akiban Persistit), поддерживает механизм транзакций и полнотекстовый поиск, а также способна справляться с ростом объемов данных. Система с помощью механизма репликаций обеспечивает устойчивость данных при сбоях, а также может работать с семейством API Blueprints (Java API для работы с графами), которое позволяет взаимодействовать с разными хранилищами и имеет различные реализации алгоритмов работы c графами, механизмов передачи данных и др. Для некоммерческого использования Titan распространяется под лицензией Apache 2.

СУБД OrientDB совмещает в себе преимущества документо-ориентированных и графовых СУБД. Все данные хранятся в иерархической структуре, но при этом операции над этой структурой выполняются как в графовой СУБД, а система поддерживает язык запросов SQL. Важно отметить, что для поддержки индексов используется собственная структура MVRB-Tree — смесь красно-черных деревьев (самобалансирующиеся двоичные деревья) и деревьев B+ (сбалансированные деревья поиска со значениями в листьях). Поддерживается механизм ACID транзакций и работа с API Blueprints. Лицензия СУБД OrientDB — Apache 2.

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

Для сравнения производительности графовых СУБД используется тестовый набор SP2B [1], база данных которого представлена в формате N3 [2] (компактный формат представления RDF-данных). Структура данных теста напоминает структуру DBLP (электронная библиотека научных трудов), имитирующую социальные связи. Тест проверяет 11 типов запросов SELECT, среди которых: простые запросы — время поиска не должно зависеть от размера базы данных; запросы с ветвистым обходом графа — размер результата растет с размером базы данных; проверка упорядочивания результатов; выполнение разной степени фильтраций; объединение результатов; проверка одиночных и двойных отрицаний; запросы, требующие нестандартных способов обхода графа, и др.

Для всех рассмотренных графовых СУБД использовалось Java-приложение Apache Jena, отправляющее тестовые запросы в систему и ожидающее ответа — набора подходящих под условие строк.

Системы тестировались на двух базах данных: размером 50 тыс. и 90 млн триплетов — и выполнялись на виртуальной машине с 4 Гбайт оперативной памяти. На рис. 1 и 2 даны графики времени выполнения запросов на разных системах. Чем больше значение на графике, тем дольше выполнялся запрос. Если какой-то из запросов отсутствует на графике, значит, одна из систем не прошла этот тест.

Рис.1. Результаты тестирования на маленьком графе

Рис. 2. Результаты тестирования на большом графе

В ходе сравнения СУБД Titan не прошла шесть тестов по несоответствию результатов, поэтому она не оценивалась целиком на всех тестах, однако эта СУБД достаточно перспективна, хотя пока и непригодна для использования со SPARQL.

СУБД Parliament не выполнила два теста и показала значительно худшие результаты на некоторых тестах. В целом Virtuoso и Sesame Memory показали довольно неплохие результаты и являются лучшими для работы с небольшими графами.

СУБД Sesame Native Store не справилась с шестью тестами, а Virtuoso не прошла тест query 4. Несмотря на выигрыш Sesame на некоторых тестах, Virtuoso лучше справляется с поставленной задачей на больших графах. Можно отметить, что единственным невыполненным Virtuoso тестом по времени являлся тест, требующий хранения большого количества данных, тогда как Sesame не прошла более простые тесты. Кроме того, Virtuoso загрузила базу данных быстрее, чем Sesame, лишний раз подтверждая превосходство при работе именно с базами, объем которых превышает доступную оперативную память.

Таким образом, тестирование показало, что для работы с большими графами лучше всех приспособлена СУБД Virtuoso, для работы с небольшими графами, кроме нее, можно применять и Sesame.

Удобной особенностью графовой структуры является возможность представления графа в виде нескольких подграфов меньшего размера, получаемых, например, путем разбиения по ребрам или по вершинам. Такое представление позволяет ускорить обработку запросов на разных узлах — в частности, такой возможностью обладает коммерческая версия Virtuoso. Кроме такого подхода распределения данных, используется также метод репликаций, когда данные дублируются на несколько машин, — это обеспечивает надежное хранение информации, так как при утере данных с одной машины их можно восстановить, пользуясь репликациями, хранимыми на других машинах. Например, система Neo4j использует распределенное хранение данных только для репликации, но не для ускорения обработки запросов. Однако распределенная версия не всегда обрабатывает запросы быстрее, чем при работе только на одном узле, — возможны ситуации для маленьких графов, когда возникают дополнительные накладные расходы на компоновку финального ответа из результатов, полученных с нескольких узлов.

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

***

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

Литература

1. Владислав Головков, Андрей Портнов, Виктор Чернов. RDF — инструмент для неструктурированных данных // Открытые системы.СУБД. — 2012. — № 09. — С. 46–49. URL: http://www.osp.ru/os/2012/09/13032513 (дата обращения: 11.03.2014).
2. Notation3 (N3): A readable RDF syntax. URL: http://www.w3.org/TeamSubmission/n3 (дата обращения: 11.03.2014).

Александр Алексиянц (aleksiyantsa@ispras.ru) — лаборант, Антон Коршунов (korshunov@ispras.ru) — м.н.с., Сергей Кузнецов (kuz@ispras.ru) — главный научный сотрудник ИСП РАН (Москва).