Графовые базы: особенности хранения данных

В этой статье хотел бы осветить основные аспекты быстрого доступа к графовым данным

Графовые данные можно технически хранить 3 известными мне способами:

1. В реалиционных базах:
* Данные хранятся в плоских таблицах
* Связи между сущностями осуществляются через индексированные внешие ключи

2. Документные базы:
* Связанные данные лежат прямо в колонках основной таблицы
К примеру, информация о друзьях аккаунта положена в json поле таблицы

3. Графовая база
Остановимся подробней на примере бд Neo4j:
* Отдельно хранятся данные о нодах, ребрах и значениях в ноде в разных файлах
* Нода (Node) имеет фиксированный размер, что позволяет переходить к ней в файле по смещению за константное время: ID * fixed size
[ 1 байт - активность | 4 байт - указатель на файл связи | 5 байт - указатель на файл свойств ]
* файл соединение (Relationship - ребра) состоит:
[ 5 байт - файл 1 ноды | 5 байт - файл 2 ноды | тип соединение | указатель на следующий relation | указатель на предыдущий relation ]
первый 10 байт - это обратные ссылки на ноды, что в сочетании с сылками в нодах дает двунаправленный список
* Связанный список свойств
повторяющиеся значения сжимаются в словарь, а в самом property хранится ссылка на словарь
если значение достаточно маленькое, то оно хранится прямо в property файл


Графически это можно представить следующим образом:


Какие же преимущества дает такой тип хранения данных:

Показатель	Графовая	Реалиционная	Документная
Простота выборки	Синтаксис проще и короче релиционной схемы: MATCH (john:Person { name:"John" })- [:friend *1..2]->(friend: Person) RETURN friend.name, friend.age	Достаточно сложный синтаксис: WITH RECURSIVE r AS ( SELECT id, parent_id, name, 1 AS level FROM geo WHERE id = 4 UNION ALL SELECT geo.id, geo.parent_id, geo.name, r.level + 1 AS level FROM geo JOIN r ON geo.parent_id = r.id ) SELECT * FROM r	Достаем готовые документ по ключу: val theget= new Get(Bytes.toBytes("rowkey1")) val result=table.get(theget) val value=result.value() println(Bytes.toString(value))
Скорость доступа к следующей записи графа	Константное время перехода к следуюещй записи в графе, т.к. смещения хранятся в самом relation	Для доступа к следующей записи нужно найти запись в индексе и перейти к таблице минимум 3-4 одноблочных чтения	Связанные записи хранятся в самом объекте
Досту к связям связей	Аналогичное константное время через relation	Еще 1 проход по внешнему ключу (+3-4 одноблочных чтения)	Дорогая операция, т.к. связанный объект нужно распарсить
Возможность обратного обхода (Наити людей, у кого ты в друзьях)	Константное время как вперед, так и назад	Чаще всего нет возможности пойти в обратную сторону, если это не предусмотрено в схеме дополнительными объектами	Такой возможности нет, т.к. нужно будет просмотреть и распарсить все документы
Связи многие ко многим	Аналогичное константное время через relation	Такая возможность есть через таблицы связки. Дополнительные минимум 3-4 одноблочных чтения к основным	Такой возможнсоти нет, связь всегда 1 к N
Ограничения на размер свойств	Свойства хранятся отдельно от связей, что уменьшает размер чтений при проходе по графу	Дополнительные поля таблицы хранятся в одном месте со связями, что увеличивает размер чтений при проходе по графу	Размер свойств не имеет значения

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

Еще чуть информации об внутреннем устройстве Neo4J:
* для данных используется LFU кэш (least freaq use) - аналогично Oracle
* есть возможность горизонтального масштабирования черзе шардирования по одному из ключей графа
* Параллелизация запроса возможна через парадигму map-reduce, если задача разбивается на подзадачи
 ** собирается массив параметров, по которому будем параллелить
 ** запускаем запрос в N потоков, передавая порцию данных
 ** собираем результат от потоков и выполняется доагрегация в reduce

Пример:

#параметры
with collect(distinct a) as addresses

# 1 параметр - код, для выполнения в потоке
# 2 - параметры параллелизации и шага
# 3 - параметры для передачи в поток
# 4 - спит параметров на число партиций
CALL apoc.cypher.mapParallel2("
   optional match (_)<-[:LOCKED_BY]-(o: Output)
   where not (o)-[:UNLOCKED_BY]->()
   return _.address as address,
   round(sum(o.bitcoinValue)*100000000)/100000000 as balance"
, {parallel:True, batchSize:1000, concurrency:20}, addresses,  20) yield value