графовая база данных что это
Введение в графовые базы данных SQL Server 2017
В преддверии старта курса «MS SQL Server Developer» подготовили для вас еще один полезный перевод.
Графовые базы данных — это важная технология для специалистов по базам данных. Я стараюсь следить за инновациями и новыми технологиями в этой области и, после работы с реляционными и NoSQL базами данных, я вижу, что роль графовых баз данных становится все больше. В работе со сложными иерархическими данными малоэффективны не только традиционные базы данных, но и NoSQL. Часто, с увеличением количества уровней связей и размера базы, наблюдается снижение производительности. А с усложнением взаимосвязей увеличивается и количество JOIN.
Конечно, в реляционной модели есть решения для работы с иерархиями (например, с помощью рекурсивных CTE), но это все равно остается обходными путями. При этом, функционал графовых баз данных SQL Server позволяет с легкостью обрабатывать несколько уровней иерархии. Упрощаются как модель данных, так и запросы, а следовательно, увеличивается их эффективность. Значительно сокращается объем кода.
Графовые базы данных — это выразительный язык для представления сложных систем. Эта технология уже довольно широко используется в ИТ-индустрии в таких областях, как социальные сети, антифрод-системы, анализ ИТ-сетей, социальные рекомендации, рекомендации по продуктам и контенту.
Функционал графовых баз данных в SQL Server подходит для сценариев, в которых данные сильно связаны между собой и имеют четко определенные связи.
Графовая модель данных
Граф — это множество вершин (узлов, node) и ребер (взаимосвязей, edge). Вершины представляют сущности, а ребра — связи, в атрибутах которых может содержаться информация.
Графовая база данных моделирует сущности в виде графа в том виде, как это определено в теории графов. Структуры данных — это вершины и ребра. Атрибуты — это свойства вершин и ребер. Связь — это соединение вершин.
В отличие от других моделей данных, в графовых базах данных в приоритете взаимосвязи между сущностями. Поэтому не требуется вычислять связи с помощью внешних ключей или какими-то другими способами. Можно создавать сложные модели данных, используя только абстракции вершин и ребер.
В современном мире моделирование взаимосвязей требует все более сложных методик. Для моделирования связей SQL Server 2017 предлагает возможности графовых баз данных. Вершины и ребра графа представляются в виде новых типов таблиц: NODE и EDGE. Для запросов к графу используется новая функция T-SQL под названием MATCH(). Так как этот функционал встроен в SQL Server 2017, то его можно использовать в ваших существующих базах данных без необходимости какой-либо их конвертации.
Польза графовой модели
В настоящее время бизнес и пользователи требуют приложений, которые работают все с большим и большим объемом данных, ожидая при этом высокой производительности и надежности. Представление данных в виде графа предлагает удобные средства для обработки сложных связей. Этот подход позволяет решить многие проблемы и помогает получить результаты в рамках заданного контекста.
Судя по всему, в будущем многие приложения смогут выиграть от использования графовых баз данных.
Моделирование данных: от реляционной модели к графовой
Давайте рассмотрим пример организационной структуры с иерархией сотрудников: сотрудник подчиняется менеджеру, менеджер — старшему менеджеру и так далее. В зависимости от конкретной компании в этой иерархии может быть любое количество уровней. Но с увеличением количества уровней вычисление связей в реляционной базе данных становится все сложнее и сложнее. В ней довольно сложно представить иерархию сотрудников, иерархию в маркетинге или связи в социальных сетях. Давайте посмотрим, как с помощью SQL Graph можно решить проблему с обработкой различных уровней иерархии.
Для этого примера сделаем простую модель данных. Создадим таблицу сотрудников EMP с идентификатором EMPNO и колонкой MGR, указывающей на идентификатор руководителя (менеджера) сотрудника. Вся информация об иерархии хранится в этой таблице и может быть запрошена с помощью колонок EMPNO и MGR.
На следующей диаграмме изображена так же самая модель оргструктуры с четырьмя уровнями вложенности в более привычном виде. Сотрудники — это вершины графа из таблицы EMP. Сущность «сотрудник» связана сама с собою связью «подчиняется» (ReportsTo). В терминах графа, связь — это ребро (EDGE), которое связывает узлы (NODE) сотрудников.
Давайте создадим обычную таблицу EMP и добавим туда значения в соответствии с вышеприведенной диаграммой.
На приведенном ниже рисунке показаны сотрудники:
Теперь давайте посмотрим на представление тех же данных в виде графа. Вершина EMPLOYEE имеет несколько атрибутов и связана сама с собой связью «подчиняется» (EmplReportsTo). EmplReportsTo — это название связи.
В таблице ребер (EDGE) также могут присутствовать атрибуты.
Создадим таблицу узлов EmpNode
Синтаксис создания узла довольно прост: к выражению CREATE TABLE в конец добавляется «AS NODE».
Теперь преобразуем данные из обычной таблицы в графовую. Следующий INSERT вставляет данные из реляционной таблицы EMP.
В таблице узлов в специальной колонке $node_id_* хранится идентификатор узла в виде JSON. В остальных столбцах этой таблицы находятся атрибуты узла.
Создаем ребра (EDGE)
Создание таблицы ребер очень похоже на создание таблицы узлов, за исключением того, что используется ключевое слово «AS EDGE».
Теперь определим связи между сотрудниками, используя столбцы EMPNO и MGR. По диаграмме оргструктуры хорошо видно как написать INSERT.
Таблица ребер по умолчанию состоит из трех столбцов. Первый, $edge_id — идентификатор ребра в виде JSON. Два других ( $from_id и $to_id ) представляют связь между узлами. Кроме того, ребра могут иметь дополнительные свойства. В нашем случае это Deptno.
Системные представления
В системном представлении sys.tables появилось две новые колонки:
Объекты, связанные с графами, располагаются в папке Graph Tables. Иконка таблицы узлов помечена точкой, а таблицы ребер — двумя связанными кругами (что немного похоже на очки).
Выражение MATCH
Выражение MATCH взято из CQL (Cypher Query Language). Это эффективный способ запроса к свойствам графа. CQL начинается с выражения MATCH.
Давайте посмотрим на несколько примеров.
Приведенный ниже запрос отображает сотрудников, которым подчиняется Smith и его менеджер.
Следующий запрос предназначен для поиска сотрудников и менеджеров второго уровня для Smith. Если убрать предложение WHERE, то в результате будут отображаться все сотрудники.
И, наконец, запрос для сотрудников и менеджеров третьего уровня.
Теперь давайте изменим направление, чтобы получить начальников Smith’а.
Заключение
SQL Server 2017 зарекомендовал себя как полноценное корпоративное решение для различных ИТ-задач бизнеса. Первая версия SQL Graph очень многообещающая. Даже несмотря на некоторые ограничения, уже сейчас есть достаточно функционала для изучения возможностей графов.
Функционал SQL Graph полностью интегрирован в SQL Engine. Однако, как уже было сказано, в SQL Server 2017 есть следующие ограничения:
Нет поддержки полиморфизма.
Графовая база данных Neo4j в PHP
В последнее время я все чаще слышу о NoSQL и о графовых базах данных в частности. Но воспользовавшись хабропоиском с удивлением обнаружил, что статей на эту тему не так и много, а по запросу «Neo4j», так вообще 4 результата, где косвенно упоминается это название в тексте статей.
Что такое Neo4j?
Neo4j — это высокопроизводительная, NoSQL база данных основанная на принципе графов. В ней нет такого понятия как таблицы со строго заданными полями, она оперирует гибкой структурой в виде нод и связей между ними.
Как я докатился до этого?
Уже более года я не использовал в своих проектах SQL, с того времени, как попробовал документо-ориентированную СУБД «MongoDB». После MySQL моей радости не было предела, как все просто и удобно можно делать в MongoDB. За год, в нашей студии создания сайтов, переписали тройку CMS, использующих основные фишки Mongo c её документами, и с десяток сайтов работающих на их основе. Всё было хорошо, и я уже начал забывать, что такое писать запросы в полсотни строк на каждое действие с БД и все бы ничего пока на мою голову не свалился проект с кучей отношений, которые ну никак не укладывались в документы. Возвращаться к SQL очень не хотелось, и пару дней я потратил чисто на поиск NoSQL решения, позволяющего делать гибкие связи — на графовые СУБД. И по ряду причин мой выбор остановился на Neo4j, одна из главных причин — это то, что мой движок был написан на PHP, а для неё был написан хороший драйвер «Neo4jPHP», который охватывает почти 100% REST-интерфейса, предоставляющегося сервером Noe4j.
Ближе к делу
Графовые базы данных, в первую очередь, предназначены для решения тех задач, где данные тесно связанные между собой в отношениях, которые могут углубляться в несколько уровней. Например, в реляционных базах данных нам не трудно выполнить запрос: «Дайте мне список всех актеров, которые были в фильме с Кевином Бэконом».
Привел пример с под запросом, вы можете переписать его в голове с использованием «JOIN».
Но предположим, что мы хотим получить имена всех актеров, которые были в кино с кем-то, кто был в кино с Кевином Бэконом. И тут у нас появляется ещё один JOIN. А теперь попробуйте добавить третью степень: «Тот, кто был в кино с кем-то, кто был в кино с кем-то, кто был в фильме с Кевином Бэконом.» Страшно звучит, но задача реальная и с каждой новой связью мы должны добавлять JOIN, а запрос будет становится все более сложным, трудоёмким, все менее производительным.
Глубокие связи особенно актуальны в различных социальных проектах, когда нам нужно получать друзей друзей, в задачах поиска маршрутов и т.п. Графовые базы данных призваны решить эти проблемы, когда наши данные могут быть удаленны друг от друга на два и более отношений. Они решаются очень элегантно, когда мы моделируем данные как «вершины графов», а связи как «ребра графа» между этими узлами. Мы можем делать обход графа с помощью давно известных и эффективных алгоритмов.
Приведенный выше пример может быть легко смоделирован следующим образом: каждый актер и фильм являются узлами, а роли — отношения, идущие от актера в кино, где они играли:
Теперь становится очень легко найти путь от Кевина Бэкона до любого другого актера.
Немного кода
Во-первых, нам нужно установить соединение с базой данных. Так как Neo4jPHP работает с сервером БД через REST интерфейс, то нет постоянного соединения, и передача данных происходит, только тогда когда нам нужно считать или записать данные:
Теперь нам нужно создать узлы для каждого актёра и фильма. Это аналогично тому, как мы делаем INSERT в традиционных реляционных СУБД:
Каждый узел имеет методы setProperty и getProperty, которые позволяют записывать произвольные данные в узел считывать их. Узел не имеет заданной структуры, это похоже на документы в документо-ориентированных СУБД, правда мы не можем делать вложенные данные и свойство может быть только одим из двух типов: строкой или числом.
На сервер данные отправляются только когда мы вызываем save() и это нужно сделать для каждого узла.
Теперь мы должны задать связи между актерами и фильмами, в которых они играли. В реляционных СУБД для этой цели мы бы создавали внешний ключ, тут мы создадим отношение, которое может быть произвольно названо хранить в себе любые параметры, как и узел и так же сохраняется в БД:
Как видите, все отношения называются «IN», но мы можем дать им и любое другое имя, например «ACTED IN». Так же мы можем задать обратное отношение от фильмов к актерам и сформулировать его как фильм «HAS» (имеет) актёра. Пути могут быть найдены не зависимо от того какое направление связи мы создадим, т.е. мы можем использовать любую семантику подходящую по смыслу для конкретной предметной области. В тоже время между узлами могут быть множественные отношения направленные в обе стороны.
Все отношения настроены, и теперь мы готовы найти связь между любым актером в нашей системе и Кевином Бэйконом до любой заданной глубины:
Так же мы можем выбирать не сами узлы, а связи между ними, например:
getRelationships — может вернуть все отношения для узла, необязательно ограничивать его только определенным типом отношения. Так же мы можем получить, только все входящие или исходящие из узла связи.
На этом пока закончу данный пост, и надеюсь он даст некий резонанс к написанию статей на тематику графовых баз данных и neo4j в частности.
В статье использовался пример с сайта разработчика Neo4jPHP с изменениями и комментариями основанными на моём личном опыте.
Начинаем работать с графовой базой данных Neo4j
В нашем проекте возникла следующая задача — есть база с большим количеством товаров, на уровне сотен тысяч. У каждого товара есть сотни динамически создаваемых характеристик. Необходимо обеспечить быструю фильтрацию по товарам по набору различных характеристик. Время формирования ответа должно быть не более 0.3 секунды, нужно поддерживать сложную логику в стиле.
У нас все реализовано в рамках MySQL + Symfony2/Doctrine, скорость неудовлетворительная — ответы формируются в течении 1-10 секунд. Мои попытки оптимизировать все это хозяйство — под катом.
Терминология задачи по фильтрации товаров (в упрощенном виде)
Для решения этой задачи я решил опробовать графовую базу данных Neo4j. Для поверхностного ознакомления рекомендую прочитать этот пост.
Терминология Neo4j и графовых баз данных в целом.
Схема решения задачи
Для каждого товара создать отдельную ноду, в свойствах ноды хранить id товара в базе MySQL. Для каждого критерия создать свою ноду, в свойствах хранить id критерия. Дальше, связать все ноды товаров с нодами критериев, которые подходят для товара. При изменении характеристик товара или свойств критериев обновлять связи между нодами.
Первый вариант решения — с Neo4j
Учитывая, что я с графовыми базами данных никогда не работал — я решил развернуть локально Neo4j, изучить на базовом уровне Cypher и попробовать реализовать требуемую логику. Если все получиться — провести тестирование скорости работы для базы из 1 миллиона товаров, у каждого 500 характеристик.
Разворачивание системы достаточно простое — скачиваем дистрибутив и устанавливаем его.
У Neo4j сервера есть RestAPI, для php есть библиотека neo4jphp. Также есть bundle для интеграции с Symfony2 — klaussilveira/neo4j-ogm-bundle.
В дистрибутив входит веб сервер и приложение для работы с ним, по умолчанию http://localhost:7474/
Есть еще старая версия клиента, с другим функционалом.
В качестве документации удобно использовать краткую документацию. Примеры кода есть в graphgist. По идее, они должны там выполнятся онлайн, но сейчас это не работает. Чтобы посмотреть код нужно перейти по ссылке из graphgist (например, сюда) и там нажать кнопку Page Source.
Для экспериментов с Neo4j очень удобно использовать встроенный веб клиент Там можно выполнять запросы Cypher и просматривать ответ на запросы вместе со связями и характеристиками нод.
Простые Cypher команды
Создание ноды с меткой
Создать 2 связанные ноды
Связать 2 существующие ноды
Удалить все связанные ноды
Удалить все несвязанные ноды — если попробовать запустить эту команду в базе, где есть связанные ноды — она не пройдет. Нужно удалить вначале связанные ноды.
Выбрать товары, которым подходит критерий 3
Сразу несколько Cypher команд веб клиент выполнять не умеет. Тут говорят, что старый клиент это умеет, но я не нашел такой возможности. Поэтому, нужно копировать по 1 строке.
Можно выполнить создание множества нод со связями одной командой, нужно давать разные имена нодам, связям можно не давать имя
Получится такая структура. Если у вас выглядит менее понятно — можно переставить мышкой ноды.
Промежуточные тесты скорости Neo4j
Пришло время протестировать скорость заполнения базы и простых выборок из большой базой.
Для этого клонируем neo4jphp
Базовое описание этой библиотеки есть в этом посте, поэтому я сразу выложу код для заполнения тестовой базы еxamples/test_fill_1.php
Скрипт заполнения базы я оставил на ночь. Примерно спустя 4 часа скрипт перестал добавлять данные и сервис Neo4j начал грузить сервер на 100%. Утром по итогу работы было вставлено 78300 товаров из 8 категорий товаров.
Результаты тестового заполнения базы — примерно 20 товаров в секунду с 200-400 связями. Не очень высокий результат — Mysql и Cassandra выдавали около 10-20 тысяч вставок в секунду (10 полей, 1 primary index, 1 индекс). Но скорость вставки для нас не критична — мы можем обновлять граф данных в фоновом режиме после редактирования товара. А вот скорость выборки данных — критична.
Размер тестовой базы данных на диске — 1781 мегабайт. В ней хранится 78300 товаров, 4000 критериев, 15660000-31320000 связей. Общее количество объектов (нодов и связей) менее 32 миллионов — в среднем по 55 байт на сущность. Многовато, как по мне, но главное требование все же скорость выборок, а не размер базы.
Первая попытка протестировать скорость выборки провалилась — сервер Neo4j опять «ушел» в режим 100% загрузки процессора и за несколько минут так и не выдал ответ на запрос.
Чтобы двигаться дальше нужно разобраться, как оптимизировать запрос в Neo4j. Вначале я хотел ограничить стартовый набор нод в выборке с помощью инструкции START
Для этого нужно, чтобы в базе были индексы. В Neo4j я не нашел команду для просмотра перечня текущих индексов, но в веб приложении Neo4j можно набрать команду
Добавить индексы можно командой
Уникальный индекс можно создать командой
Индексы, добавленные командами выше, нельзя использовать в START директиве. Тут утверждают, что их можно использовать только в where
The indexes created via Cypher are called Schema indexes, and are not to be used in the START clause. The START clause index lookups are reserved for the legacy indexes that you create via autoindexing or through the non-Cypher APIs.
In order to use the :user index you’ve created, you can do this:
match n:user
where n.name=«aapo»
return n;
START is optional. If you do not specify explicit starting points, Cypher will try and infer starting points from your query. This is done based on node labels and predicates contained in your query. See Chapter 14, Schema for more information. In general, the START clause is only really needed when using legacy indexes.
Так родился первый рабочий запрос
В нашей тестовой базе индексов не обнаружено, поэтому мы создадим еще одну базу для теста другим способом. Возможности создать независимые наборы данных (аналог базы данных в MySQL) в Neo4j я не нашел. Поэтому для тестирования я просто менял путь к хранилищу данных в настройках Neo4j Community (Database location)
Внимательные читатели возможно обнаружили пару комментариев в коде test_fill_1.php, а именно
В batch режиме в Neo4jphp у меня не получилось добавить метки к нодам, а индексы почему то не сохранились. Учитывая, что Cypher перестал для меня быть китайской грамотой, я решил заполнять базу хардкорно — на чистом Cypher. Так получился test_fill_2.php
Это привело к катастрофическому падению скорости работы, модифицированный скрипт работал примерно около часа. Я решил протестировать скорость выборки по нескольким критериям и вернуться к вопросу быстрой вставки данных позже.
Скрипт выше отработал за 0.02 секунды. В целом — это вполне приемлемо, но проблема как быстро сохранять большое количество связей между нодами при апдейте свойств товара — осталась.
Альтернативное решение
Я решил «для очистки совести» опробовать MySQL в качестве хранилища. Связи между нодами будут храниться в отдельной таблице без дополнительной информации.
Тестовый скрипт для заполнения базы ниже
Заполнение базы заняло 12 секунд. Размер таблицы — 37 мегабайт. Поиск по 2 критериям занимает 0.0007 секунд
Еще один вариант
Под mysql есть полноценное графовое хранилище данных — но я его не тестировал. Судя по документации, он гораздо примитивнее Neo4j.
Выводы
Neo4j — очень крутая штука. Запрос наподобие «Выбрать контакты пользователей, которые лайкнули киноактёров, которые снялись в фильмах, в которых звучали саунтдтреки, которые были написаны музыкантами, которым я поставил лайк» в Neo4j решается тривиально. Примерно так
Для SQL это гораздо более хлопотное занятие.
Сравнивать полноценную графовую базу с голой таблицей индексов в MySQL — некорректно, но в рамках решения моей задачи — использование Neo4j никаких плюсов не дало.
UPDATE. Изменил url’ы картинок, по идее должны у всех загрузаться.
UPDATE 2. Предложили еще несколько вариантов — MongoDB, elasticsearch, solr, sphinx, OrientDB. Планирую протестировать MongoDB, результаты тестов выложу тут же.
Знакомство с графовой базой данных Neo4j
Mar 15, 2019 · 6 min read
Содержание
История происхождения графов
Среди жителей Кёнигсберга (нынешний Калиниград) была распространена такая загадка: как пройти по всем городским мостам через реку, не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
Решил задачку Леонард Эйлер, сформулировав ряд правил и доказав, что пройти по мостам, не повторяясь, невозможно.
Так и зародилась теория графов.
Что такое граф?
Граф — абстрактный математический объект, представляющий собой множество вершин (точек) и набор рёбер (линий ), то есть соединений между парами вершин.
Ориентированный граф
Ориентиров а нный граф — это граф, ребро которого имеет заданное направление между вершинами.
Петля
Если вершина графа соединена ребром сама с собой, то такое ребро называется петлей.
Классификация графов
Связанный граф
Если из любой вершины есть путь до любой другой — такой граф называется связанным.
В данном примере есть путь от вершины А до вершины D, хоть он и пролегает через другие вершины.
Сильно связанный граф
Граф называется сильно связанным, если любая его вершина соединена с любой другой ребром. Если связи ориентированные — то граф называется ориентированно связанным.
Взвешенный граф
Если к каждому ребру в соответствие поставлено некоторое число (вес ребра) — такой граф называется взвешенным.
Мультиграф
Граф, в котором разрешается присутствие параллельных ребер, то есть ребер, имеющих те же самые конечные вершины. Параллельные ребра выделены красным.
Где используются графы
Графы используются в геоинформационных системах (ГИС), логистике, социальных сетях, магазинах и других сферах жизни.
Схема метро — взвешенный граф, на ребрах которого указано время перехода между станциями, или прогона состава.
По весам ребер можно посчитать время в пути, так же и выбрать оптимальный путь с помощью какого-либо алгоритма. Алгоритмов поиска кратчайшего пути в графе много, самый известный — алгоритм Дейкстры, вы наверняка о нем слышали.
Карту города тоже можно представить в виде графа.
Данный граф применим в системах навигации для поиска оптимального маршрута. Перекрестки — вершины графа, а дороги — ребра.
Молекулярный граф — связный неориентированный граф, соответсвует формуле химического соединения таким образом, что вершины графа — атомы молекулы, а ребра — химические связи между этими атомами.
Наиболее частный пример графов в разработке — граф социальной сети, в котором отображены дружеские отношения между людьми, их вкусовые предпочтения и прочее.
Даже 3D-объект можно представить в виде графа:
Каждая вершина хранит координаты x, y, z.
Граф — довольно абстрактная вещь, поэтому ее можно применить практически во всех сферах жизни.
Графовые базы
Первая графовая СУБД Neo4j создана в 2007 году, сейчас их уже десятки, наиболее популярные:
Neo4j
Графовая СУБД с открытым исходным кодом, реализована на Java компанией Neo Technology.
Не уступает по производительности реляционным базам данных благодаря собственному формату хранения данных.
Приложение может взаимодействовать с БД по одному из протоколов:
Продолжим знакомство с Neo4j на примере стандартной БД “Movie”
Пользователь может просматривать БД с помощью Neo4j Browser
Вершины графа в Neo4j имеют свой тип, в БД Movie у нас 2 типа вершин:
* Person (name — имя актера, born — год рождения)
* Movie (title — наименование фильма, released — год выхода)
Если проводить аналогию с реляционными базами, то Person и Movie — это таблицы.
Для работы с БД используется язык запросов Cypher.
Cypher
Cypher — декларативный язык запросов в виде графа, позволяющий получить выразительный и эффективный запрос данных. Язык представлен интуитивно понятным и простым в освоении.
Для начала найдем актера с именем Том Хэнкс
MATCH — аналог WHERE, в круглых скобках мы описываем свойства вершины (условие поиска), а RETURN — аналог SELECT, в нем мы описываем, что вернуть.
Теперь поищем фильмы, в которых снимался Том Хэнкс.
Запрос усложнился, в MATCH мы описали вершины обоих типов, и отношение между ними (ребро) в квадратных скобках.
Теперь посмотрим, кто снимался с Томом на одной площадке, и в каком фильме:
Текст запроса приближен к текстовому отображению графа:
Где и когда использовать графовые СУБД
Графовые базы уже нашли применение в:
Если в вашем приложении планируется много сущностей и связей многие-ко-многим, то это один из признаков, что предпочтительней выбрать графовую СУБД (утверждение Martin Kleppmann’а в книге “Designing Data Intensive Applications”).
А если у вас уже есть приложение с множеством связей, и обход этих связей занимает много времени и ресурсов — стоит присмотреться в сторону графов, т.к. обход связей в них практически ничего не стоит.
Выводы
Графовые базы не является таблеткой от всех проблем, их следует использовать для решения задач, которые решаются только графами.
Например, площадка medium использует Neo4j для хранения отношений между различными сущностями (Стек, который позволил Medium обеспечить чтение на 2.6 тысячелетия), а данные хранит в NoSQL БД dynamoDB.
Если вас заинтересовали графовые базы, то на официальном сайте Neo4j можно скачать БЕСПЛАТНО книгу с осьминогом, в ней больше информации про внутреннее устройство Neo4j и Cypher.