Пользователь
0,1
рейтинг
24 сентября 2012 в 14:03

Разработка → Графовая база данных Neo4j в PHP из песочницы

В последнее время я все чаще слышу о NoSQL и о графовых базах данных в частности. Но воспользовавшись хабропоиском с удивлением обнаружил, что статей на эту тему не так и много, а по запросу «Neo4j», так вообще 4 результата, где косвенно упоминается это название в тексте статей.

Что такое Neo4j?


image
Neo4j — это высокопроизводительная, NoSQL база данных основанная на принципе графов. В ней нет такого понятия как таблицы со строго заданными полями, она оперирует гибкой структурой в виде нод и связей между ними.

Как я докатился до этого?


Уже более года я не использовал в своих проектах SQL, с того времени, как попробовал документо-ориентированную СУБД "MongoDB". После MySQL моей радости не было предела, как все просто и удобно можно делать в MongoDB. За год, в нашей студии создания сайтов, переписали тройку CMS, использующих основные фишки Mongo c её документами, и с десяток сайтов работающих на их основе. Всё было хорошо, и я уже начал забывать, что такое писать запросы в полсотни строк на каждое действие с БД и все бы ничего пока на мою голову не свалился проект с кучей отношений, которые ну никак не укладывались в документы. Возвращаться к SQL очень не хотелось, и пару дней я потратил чисто на поиск NoSQL решения, позволяющего делать гибкие связи — на графовые СУБД. И по ряду причин мой выбор остановился на Neo4j, одна из главных причин — это то, что мой движок был написан на PHP, а для неё был написан хороший драйвер "Neo4jPHP", который охватывает почти 100% REST-интерфейса, предоставляющегося сервером Noe4j.

Ближе к делу


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

> SELECT actor_name, role_name FROM roles WHERE movie_title IN (SELECT DISTINCT movie_title FROM roles WHERE actor_name='Kevin Bacon')


Привел пример с под запросом, вы можете переписать его в голове с использованием «JOIN».

Но предположим, что мы хотим получить имена всех актеров, которые были в кино с кем-то, кто был в кино с Кевином Бэконом. И тут у нас появляется ещё один JOIN. А теперь попробуйте добавить третью степень: «Тот, кто был в кино с кем-то, кто был в кино с кем-то, кто был в фильме с Кевином Бэконом.» Страшно звучит, но задача реальная и с каждой новой связью мы должны добавлять JOIN, а запрос будет становится все более сложным, трудоёмким, все менее производительным.

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

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

image

Теперь становится очень легко найти путь от Кевина Бэкона до любого другого актера.

Немного кода


Во-первых, нам нужно установить соединение с базой данных. Так как Neo4jPHP работает с сервером БД через REST интерфейс, то нет постоянного соединения, и передача данных происходит, только тогда когда нам нужно считать или записать данные:

use Everyman\Neo4j\Client,
    Everyman\Neo4j\Transport,
    Everyman\Neo4j\Node,
    Everyman\Neo4j\Relationship;

$client = new Client(new Transport('localhost', 7474));


Теперь нам нужно создать узлы для каждого актёра и фильма. Это аналогично тому, как мы делаем INSERT в традиционных реляционных СУБД:

$keanu = new Node($client);
$keanu->setProperty('name', 'Keanu Reeves')->save();
$laurence = new Node($client);
$laurence->setProperty('name', 'Laurence Fishburne')->save();
$jennifer = new Node($client);
$jennifer->setProperty('name', 'Jennifer Connelly')->save();
$kevin = new Node($client);
$kevin->setProperty('name', 'Kevin Bacon')->save();

$matrix = new Node($client);
$matrix->setProperty('title', 'The Matrix')->save();
$higherLearning = new Node($client);
$higherLearning->setProperty('title', 'Higher Learning')->save();
$mysticRiver = new Node($client);
$mysticRiver->setProperty('title', 'Mystic River')->save();


Каждый узел имеет методы setProperty и getProperty, которые позволяют записывать произвольные данные в узел считывать их. Узел не имеет заданной структуры, это похоже на документы в документо-ориентированных СУБД, правда мы не можем делать вложенные данные и свойство может быть только одим из двух типов: строкой или числом.
На сервер данные отправляются только когда мы вызываем save() и это нужно сделать для каждого узла.

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

$keanu->relateTo($matrix, 'IN')->save();
$laurence->relateTo($matrix, 'IN')->save();

$laurence->relateTo($higherLearning, 'IN')->save();
$jennifer->relateTo($higherLearning, 'IN')->save();

$laurence->relateTo($mysticRiver, 'IN')->save();
$kevin->relateTo($mysticRiver, 'IN')->save(); 


Как видите, все отношения называются «IN», но мы можем дать им и любое другое имя, например «ACTED IN». Так же мы можем задать обратное отношение от фильмов к актерам и сформулировать его как фильм «HAS» (имеет) актёра. Пути могут быть найдены не зависимо от того какое направление связи мы создадим, т.е. мы можем использовать любую семантику подходящую по смыслу для конкретной предметной области. В тоже время между узлами могут быть множественные отношения направленные в обе стороны.

Все отношения настроены, и теперь мы готовы найти связь между любым актером в нашей системе и Кевином Бэйконом до любой заданной глубины:

$path = $keanu->findPathsTo($kevin)
    ->setMaxDepth(12)
    ->getSinglePath();

foreach ($path as $i => $node) {
    if ($i % 2 == 0) {
        echo $node->getProperty('name');
        if ($i+1 != count($path)) {
            echo " was in\n";
        }
    } else {
        echo "\t" . $node->getProperty('title') . " with\n";
    }
}


Так же мы можем выбирать не сами узлы, а связи между ними, например:

echo $laurence->getProperty('name') . " was in:\n";
$relationships = $laurence->getRelationships('IN');
foreach ($relationships as $relationship) {
    $movie = $relationship->getEndNode();
    echo "\t" . $movie->getProperty('title') . "\n";
}


getRelationships — может вернуть все отношения для узла, необязательно ограничивать его только определенным типом отношения. Так же мы можем получить, только все входящие или исходящие из узла связи.

На этом пока закончу данный пост, и надеюсь он даст некий резонанс к написанию статей на тематику графовых баз данных и neo4j в частности.

В статье использовался пример с сайта разработчика Neo4jPHP с изменениями и комментариями основанными на моём личном опыте.
Евгений @rework
карма
12,0
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (45)

  • 0
    А он может искать пути только по определенным связям?
    Например используя только «IN», но избегая «MARRIED»?
    • +1
      да
      • –3
        плохо.
        • +1
          Что же плохого? Вы можете делать множество связей разных типов и искать для конкретных задач, только по заданным.
          • 0
            В какой-нибудь конкретной задаче может понадобиться поиск по нескольким связям.
            Пример с потолка: родственные связи (родитель, ребёнок, брат) и поиск всех родственников до Nого колена.
            • +3
              и? это можно сделать
              • –2
                Ну вот в статье этого не оражено, и в документации сходу не находится.
                Какие параметры поиска путей есть?
  • 0
    А с какими объемами данных приходилось работать используя эту субд?
    • 0
      Лично мне приходилось пока работать с данными порядка тысяч узлов/связей. Но по уверениям разработчиков база может работать с несколькими миллиардами узлов, связей, параметров на одной машине, а так же может быть масштабирована на множество машин.
      • 0
        А физический объем данных каков?
    • +3
      Порядка 27 млн связей и нод, но ноды и связи без свойств, только идентификаторы. По идентификаторам нод и связей создавался индекс Lucene. Размер идентификатора порядка 30-40 байт в виде NODE_TYPE.Размер на диске (база+индексы) ~16 гигабайт. Импорт выполняется из JSON с использованием BatchInserter примерно за 40 минут, но с проверкой существования в базе идентификатора, т.е. импорт без такой логики будет быстрей.
      • 0
        >> Размер идентификатора порядка 30-40 байт в виде NODE_TYPE.{SHA1 in hex}
      • 0
        Неплохо, попробуем )
  • 0
    приятная новость,
    когда я изучал рынок NoSQL, neo4j не имела драйвера РНР и я ее отбросил на потом…
    видно это потом уже настало :()
  • +1
    Графовые БД — это очень и очень круто, просто руки чешутся попробовать, но:

    1. Как там насчет пакетного сохранения данных, транзакций?
    2. Бенчмарки есть?
    3. Что с масштабированием?
    4. Как ведет себя с большими объемами данных?
    • +2
      1. Транзакции есть. Может быть в следующих статьях получится написать об этом.
      2. Тут многое зависит от задачи, но очевидно, что она очень быстра по сравнению с SQL, в тех случаях когда данные легко описываются графом и имеют много связей. Конкретных цифр у меня нет. Кому интересна тема, есть презентация www.slideshare.net/thobe/nosqleu-graph-databases-and-neo4j там есть некоторые цифры.
      3, 4. Как выше я отмечал в комментарии, производители заверяют о хорошем механизме масштабирования на множество машин и быструю работу с большими объёмами.
      • +2
        > Как выше я отмечал в комментарии, производители заверяют о хорошем механизме масштабирования на множество машин и быструю работу с большими объёмами

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

        Если траверсинг не нужен и нужен только поиск на глубину одной связи, то масштабироваться горизонтально просто. Пример — FlockDB.

        Neo4J умеет лишь реплицироваться, и то только в версии с коммерческой лицензией. Master-Master там или Active-Passive я не помню, подозреваю последнее.
        • +1
          Спасибо за полезный комментарий. Я лишь сказал, что разработчики написали на своём сайте neo4j.org/learn/
          У меня нет опыта в масштабировании Neo4J, поэтому если вы знаете об этом на личном опыте, было бы интересно послушать в развернутом виде.
  • +4
    Вот видео с прошлогодней конференции в Киеве
    Выступает разработчик этой БД

    jeeconf.com/archive/jeeconf-2011/materials/graph-db/
  • 0
    """
    свойство может быть только одим из двух типов: строкой или числом.
    """
    что, даже дат нету?
    • 0
      в PHP драйвере нет, даты можно хранить в timestamp, если же говорить о использовании neo4j в Java, а именно на нём он написан, то там можно хранить данные любых типов, доступных в Java.
      • +2
        А… таки строки и числа — это ограничения пхп!
        Чтоли бы как-нить акцентиоовали на этом в тексте, а то натурально, на всю базу тень бросет.
        • 0
          Я даже думаю, что это ограничение не PHP, а REST интерфейса.
          • 0
            ну это как-то сомнительно, либо крайне неадекватно.
    • 0
      таки нету.
      поддерживаются только примитивы жавы: boolean, 8/16/32/64 int, 32/64 float, ucs16 char, ucs16 string
  • 0
    Интересно, а к ГИС применять это пробовали?
    • 0
      OSM вроде бы использует.
      • +1
        ага.
        вот тут ужасного качества видео презентация:
        www.youtube.com/watch?v=I0bTa5Kp7Wg

        вот тут слайды:
        www.oscon.com/oscon2011/public/schedule/detail/19822

      • 0
        OSM не использует.
        Просто есть модуль Neo4j Spatial, к которому дописали код, позволяющий быстро импортировать OSM данные.
    • 0
      Пробовали, API удобное, но получалось достаточно медленно (тестировали 1-2 года назад, может быть что-то поменялось уже)
      • 0
        медленные сами запросы, или графовые алгоритмы?
        • 0
          Запросы, естественно. Алгоритмы можно переписать — это не проблема. Сравнивали обычную Дейкстру на двух разных БД. Более того общались напрямую с Peter Neubauer и, к сожалению, даже после их рекомендаций скорость оставалась неприемлимой.
          • 0
            Так графовые алгоритмы же там «встроенные».
            Тоесть, по построению, используют специально оптимизированную под это внутреннюю сруктуру данных.
            Или вы и переписывали прямо в реализации базы?
            • 0
              Вы посмотрите код. Что там специального для Дейкстры? Только получение следующих нод из текущей, связанных отношением (отношение – «дорога» в данном случае). Естественно для этого пользовались функциями Neo4J.
  • +1
    Возможно ли автоматическое удаление связанных записей и ограничение количества связей для одной записи?
    • 0
      полагаю если возможно получить все связи одного нода, то на уровне кода можно сделать удаление связанных записей.
      • 0
        Меня интересует именно встроенная поддержка.
  • +2
    я просто оставлю это тут http://en.wikipedia.org/wiki/Graph_database
  • 0
    А вот если бы вы в примере с фильмами и актёрами использовали связи типа «out», то есть не «актёр снимался в таком-то фильме», а наоборот «в фильме снимались такие-то актёры» — в этом случае время поиска по графу изменилось бы?

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

    Почему спрашиваю? Потому что зацепило вот это предложение: «В тоже время между узлами могут быть множественные отношения направленные в обе стороны.»
    Когда нужны двунаправленные связи? В каких ситуациях это даёт выигрыш?
    • 0
      По сути куда бы не была направлена связь, алгоритм обхода графа от этого не меняется соответственно и по скорости разница не заметна. Это нам даёт простор в написании самих запросов, как нам удобнее написать запрос: «актёр снимался в таком-то фильме», или «в фильме снимались такие-то актёры» так и делаем связь.
      • 0
        Ясно, спасибо.
  • 0
    А что там у неё унутре?
    Как хранятся данные?
    • 0
      Опять же, 1-2 года назад были несколько файликов, которые хранили отдельно ноды, атрибутику, связи + Lucene, который индексировал всё что скажете и делал полнотекстный поиск. Легче всего взять примерчик и запустить это дело у себя — он создаст штук 10 файликов — там по названиям всё в общем-то понятно было.
      • 0
        А торжество изобретательской мысли по оптимизации хранения графов там увидеть можно?
        • 0
          Вот этого не помню честно говоря. Я тогда игрался с большим количеством графовых БД – не всё запомнил точно.

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