Предисловие
Будучи студентом третьего курса, я выбрал тему для курсовой роботы: «Графовые базы данных на примере Neo4j». Так как до того времени я изучал и использовал исключительно реляционные БД, мне было интересно, зачем вообще графовая БД и когда ее способности лучше применять? После просмотра множества сайтов в интернете я обнаружил только теорию и не больше. Так как теория не всегда убедительная и хотелось бы увидеть какую либо статистику, у меня разыгралось любопытство и я решил, что в своей курсовой я этим займусь, а в качестве противника Neo4j я выбрал MySQL.
Итак, кто же выиграет это противостояние?
Коротко о Neo4j и графовых БД
Neo4j — open-source графовая база данных, история которой началась по инвестициям компании «Neo Technology» в 2003 году. С 2007 года стала публично доступной. В Neo4j присутствуют все характеристики баз данных, включая соблюдение ACID, поддержание разбиение на кластеры и восстановления после сбоя в системе. Сегодня является лидером среди графов баз данных.
ACID (Atomicity, Consistency, Isolation, Durability) — набор свойств, которые гарантируют надежную работу транзакций.
Компоненты графовой базы данных — узлы и ребра. Они могут быть дополнены собственным набором полей. Модель такой БД схематично изображена на рисунке.
Сохранение данных в Neo4j
Файл nodestore.db содержит определенный размер записей, содержащих информацию о Ноды:
1. Метка, которая показывает, запись активна;
2. Указатель на первое отношение, которое содержит данная нода;
3. Указатель на первую свойство, которое содержит данная нода.
Нода не содержит собственного идентификатора. Так как каждая запись в nodestore.db занимает одинаковое количество места, можно рассчитать указатель на ноду.
Файл relationshipstore.db также содержит записи одинакового размера, которые описывают отношения, но они состоят из следующих элементов:
1. Метка, которая показывает, запись активна;
2. Указатель на ноду, которая содержит это отношение;
3. Указатель на ноду, к которой это отношение направлено;
4. Вид отношения;
5. Указатель на отношение, которое стоит впереди (в пределах данной ноды);
6. Указатель на отношение, которое стоит сзади (в пределах данной ноды);
7. Указатель на отношение, которое стоит впереди (в пределах Ноды, в которой это отношение направлено);
8. Указатель на отношение, которое стоит сзади (в пределах Ноды, в которой это отношение направлено);
9. Указатель на первое свойство данного отношения.
Наполнение данными
Для того, чтобы сравнить на эффективность, надо заполнить базы данных одинаковым контентом. Стоить заметить, что эти данные должны иметь большой объем. На маленьких объемах разницу мы не увидим. Поэтому я поставил себе за цель сгенерировать для реляционной модели не меньше, чем 300 мегабайт.
Мною была выбрана предметная область — социальная сеть. Я построил ER диаграмму, на основе которой создал реляционную и графовую модели.
После этого я заполнил MySQL данными, создав класс генерации этих данных и методы, которые вносили новые данные в БД.
Количество данных, которые были внесены в MySQL:
addUsers(100 000); — количество пользователей.
addGroups(200 000); — количество групп.
addPhotos(300 000); — количество фотографий.
addAudio(250 000); — количество аудиозаписей.
addFriendships(1 000 000); — количество друзей.
addMessages(4 000 000); — количество сообщений.
addUserAudio(350 000); — количество аудиозаписей.
addUserGroups(400 000); — количество групп пользователей.
addUserPhoto(400 000); — количество фотографий пользователей.
Потом я конвертировал эти данные в Neo4j. Стоит заметить, что заполнение БД у меня отняло очень много времени. Если вы решите провести что-то подобное самостоятельно, готовьтесь к тому, что либо потратите много времени, либо не используйте полей с текстом (думаю, это заняло много времени в моем случае). После этого я сравнил место, которое занимает информация в Neo4j и MySQL. Был небольшой шок, для реляционной БД надо было 351.5 МБ, а для графовой – 3.45 ГБ. Теперь приступим к экспериментам.
Эксперимент 1
Описание эксперимента: измерение времени поиска пользователя по его идентификатору.
В этом эксперименте я искал пользователей за их идентификатором определенное количество раз. Для этого я написал методы, код которых представлено ниже.
public static void main(String[] args){
// Database connection initialisation
init();
int [] counts = {10, 100, 1000, 5000, 10000, 30000, 60000, 90000, 120000};
for(int i = 0; i < counts.length; i++){
findUserByIDTest(counts[i]);
}
}
static void findUserByIDTest(int count){
System.out.println("__________________________________");
System.out.println("STATISTIC FOR COUNT: " + count);
{
Random r = new Random(count);
long time = - System.currentTimeMillis();
for (int i = 0; i < count; i++) {
int id = r.nextInt(100000);
User u = MySQLDAO.getUserByID(id);
}
time += System.currentTimeMillis();
System.out.println("Time for MySQL:" + time);
}
{
Random r = new Random(count);
long time = - System.currentTimeMillis();
for (int i = 0; i < count; i++) {
int id = r.nextInt(100000);
User u = Neo4jDAO.getUserByID(id);;
}
time += System.currentTimeMillis();
System.out.println("Time for Neo4j:" + time);
}
System.out.println("__________________________________");
}
После выполнения программного кода я составил таблицу и нарисовал построил диаграмму к ней. Результаты меня порадовали. Neo4j замечательно справилась.
| User count = 100000 |
||
| Number of queries |
Time for MySQL, ms |
Time for Neo4j, ms |
| 10 |
4 |
9 |
| 100 |
34 |
76 |
| 1000 |
286 |
510 |
| 5000 |
1034 |
1103 |
| 10000 |
1340 |
1187 |
| 30000 |
3390 |
1384 |
| 60000 |
6876 |
2102 |
| 90000 |
10537 |
3175 |
| 120000 |
14033 |
3858 |
Эксперимент 2
Описание эксперимента: измерение времени нахождения друзей пользователя с изменением величины интервала вхождения идентификаторов для поиска.
В этом эксперименте я выбирал диапазон допустимых значений идентификатора и искал друзей пользователя с этим идентификатором. Потом я менял этот диапазон и проводил эксперимент заново. После чего у меня вышла соответствующая таблица с данными, по которой я построил графики зависимости.
При любом раскладе, время графовой базы для поиска на больших данных было меньше, чем то, которое надо реляционной.
Эксперимент 3
Описание эксперимента: измерение времени нахождения общего количества фотографий у пользователей, которые администрируют хотя бы одну группу, в зависимости от диапазона значений идентификаторов пользователя.
Этот эксперимент очень похож на предыдущий, но является более сложным. Если значения времени в предыдущих экспериментах при повторениях отличались слабо, то в этом скачки куда сильнее. Поэтому я провел этот эксперимент три раза и составил соответствующую таблицу.
| User count = 100000, Photo count = 300000, User photo count = 400000 |
||||||
| experiment 1 |
experiment 2 |
experiment 3 |
||||
| id range < |
Time for MySQL, ms |
Time for Neo4j ,ms |
Time for MySQL, ms |
Time for Neo4j, ms |
Time for MySQL, ms |
Time for Neo4j, ms |
| 10 |
299 |
11339 |
164 |
92594 |
456 |
56575 |
| 100 |
10652 |
2748 |
674 |
2400 |
663 |
2826 |
| 1000 |
7243 |
4931 |
5433 |
2481 |
5649 |
1942 |
| 5000 |
22538 |
5521 |
23747 |
2408 |
23522 |
3514 |
| 10000 |
47755 |
5627 |
44917 |
2650 |
44992 |
1844 |
| 30000 |
137572 |
8161 |
33856 |
3108 |
136592 |
3707 |
| 60000 |
64002 |
13577 |
300814 |
5004 |
280672 |
6029 |
| 90000 |
482329 |
13475 |
438875 |
5102 |
429304 |
5631 |
После обсуждений на хабре, я попробовал изменил подход к условиям эксперимента: поправил запрос, на более простой, перед каждым экспериментом подымал заново MySQL и додерживался условия, что не должны работать MySQL и Neo4j одновременно. Вышло следующее: график MySQL стал более стабильным, а графовая бд начала очень сильно проигрывать реляционной на небольших объёмах данных.
| experiment 1 |
||
| id range < |
Time for MySQL, ms |
Time for Neo4j,ms |
| 10 |
120 |
10767 |
| 100 |
690 |
10706 |
| 1000 |
5879 |
10884 |
| 5000 |
24668 |
12245 |
| 10000 |
52462 |
12280 |
| 30000 |
154534 |
13352 |
| 60000 |
296369 |
14545 |
| 90000 |
489830 |
18058 |
Скромные выводы
Смело могу сказать, что графовая база данных нуждается в намного меньшем временем в поиске на больших объемах данных, однако места на жёстком диске она занимает куда больше. Поэтому для небольших систем лучше использовать реляционную БД или искать альтернативу среди других NoSQL баз данных.
Спасибо за внимание.
Комментарии (34)
tzlom
18.05.2015 12:05+2Это не данные а толпа артефактов, второй эксперимент наглядно показывает как вы сначала прогреваете кеш меньшим запросом а потом имеете вдвое большую производительность на удвоенном объёме данных.
Плюс никакого контроля как БД ведут себя под нагрузкой, для примера:
100мс на запрос при 1000 запросов в секунду это не 10мс на запрос при 100 запросах в секунду — на графиках скорости запроса выигрывает Б хотя по факту выигрывает А
Про настройки БД выше уже спросили, криво настроенный мускул это не прямо настроенный мускул, для Neo4j думаю то-же самое
Ну и на мякотку — вы сравнили производительность на разных запросах, вы генерируете два сета случайных чисел вместо одного, а значит одной БД достаётся работы больше другой.
Плюс всегда уместен контроль идентичности результатов, что и А и Б возвращают одинаковые данные.
alfss
18.05.2015 13:21+1Я бы дополнительно к выше сказанному попросил бы выложить схему БД в виде дампа.
Вообще лучше все скрипты и данные положить на github.
ADobrianskiy Автор
18.05.2015 16:16+1«вы сравнили производительность на разных запросах, вы генерируете два сета случайных чисел вместо одного» — я использовал псевдослучайные числа. «Random r = new Random(count); » — гарантирует то, что два множества буду равны
Slavenin999
18.05.2015 12:23Какой версии использовался mysql? Почему он, а не postgresql? Mysql, сейчас, далеко не показатель эффективной работы реляционной БД.
at0mic
18.05.2015 15:10В постгре, к слову, есть модуль pg_routing, который использует примерно те же алгоритмы для траверсинга графа.
vedenin1980
18.05.2015 14:46Очень странные результаты, присоединяюсь можно увидеть все коды и все скрипты настройки? Пока все выглядит так что или индексы не созданы/созданы неправильно, либо запросы созданы неверно, вроде того что не использовались join'ы и т.п. вещи в sql.
ADobrianskiy Автор
18.05.2015 16:34-4Запросы были куда уж легкие, индексы и так по PK, если так уж интересно, последний запрос выглядит следущим образом
String sql_query = «SELECT COUNT(DISTINCT social_network.photo.id) » +
«FROM (social_network.photo INNER JOIN social_network.user_photo » +
" ON social_network.photo.id = social_network.user_photo.photo_id) " +
«WHERE social_network.user_photo.user_id IN ( » +
" SELECT social_network.group.user_id\n" +
" FROM social_network.group " +
" WHERE social_network.group.user_id < ?);";vedenin1980
18.05.2015 16:56+11) Зачем все это? Чем запрос-то
SELECT COUNT(DISTINCT photo.id)
FROM photo, user_photo, group
WHERE photo.id = user_photo.photo_id and
user_photo.user_id = group.user_id and user_photo.user_id < ?;
не понравился? Зачем эти ужасные вложенные запросы по полю без индекса?
2) Я так понимаю что вы индексы на group.user_id и user_photo.photo_id не строили? Тогда о каком сравнении двух баз идет речь, если вы изначально перебили mysql ноги заставляя её заниматься прямым перебором, в то время Neo4j естественно построила индексы (откуда по вашему взялся этот размер)? Реляционная база вовсе не обязана обеспечивать быстрый поиск если вы не построили реляционных индексов по связующим полям.ADobrianskiy Автор
18.05.2015 20:16У вебадминке Neo4j нету ни одного индекса. Врядли, без указаний пользователя, база даных будет их создавать. Индексы и запрос поправлю, сделаю апдейт. P.S. Это не обьясняет результаты остальных експерементов.
vedenin1980
18.05.2015 22:38Сама по себе графическая база данных уже индекс, так как практически любой индекс это и есть граф (обычно красно-черные деревья), физически не может быть графической базы данных без индексов связей между сущностями.
ADobrianskiy Автор
18.05.2015 20:31Описание эксперимента: измерение времени нахождения общего количества фотографий у пользователей, которые «администрируют хотя бы одну группу», в зависимости от диапазона значений идентификаторов пользователя. — в вашем запросе оно подсчитывает фотографии любого пользователя
vedenin1980
18.05.2015 22:45А вы попробуйте выполнить и свой и мой и найти
десятьхоть какое-то отличие. Может быть вы и планировали более хитрую логику, но тогда у вас просто не верный запрос:
Смотрим на запрос
… user_photo.user_id IN (
SELECT user_id
FROM group
WHERE user_id < ?)
и понимаем что он выполняется только при user_photo.user_id = group.user_id and user_id <?.. Если не верите давайте представим что group содержит user_id = {1,2,3,5,7,8,9}, user_photo.user_id = {1,2,32,41}, ограничение? = 6, то когда запрос с in выполняется? Правильно при {1,2}, т.е. при user_photo.user_id = group.user_id and user_photo.user_id <?..
vedenin1980
18.05.2015 15:03+1Да, и я правильно понимаю что у вас обе базы работали одновременно на одной машине? Мне кажется это не лучшая идея для замера производительности, так как одна база легко может «слопать» себе всю доступную память и время работы винчестера оставив второй жалкие крохи, в результате выиграет самая прожорливая. Оптимальнее делать замеры по очереди на одной базе, остановив другую, в несколько заходов.
ADobrianskiy Автор
18.05.2015 16:36К сожелению да, это могло бы быть причной отклонений, но не таких уж больших.
vedenin1980
18.05.2015 17:20Ну попробуйте запустить последний Oracle и MySql вместе на простенькой персоналке. Oracle слопаем всю память и уйдет в файл подкачки даже толком не начав работу, забив все остальные приложения в системе ногами.
MikeGav
18.05.2015 15:05+1Сравните лучше с Neo4j движок графов MariaDB
mariadb.com/kb/en/mariadb/oqgraph-storage-engineat0mic
18.05.2015 15:15Оно не умеет делать k-shortest paths, например.
MikeGav
18.05.2015 15:19Еще как умеет.
mariadb.com/kb/en/mariadb/oqgraph-examples
Читайте документацию.at0mic
18.05.2015 15:25Ну я там и читал, и не нашел. Где?
MikeGav
18.05.2015 15:31Подзаголовок Shortest Path
SELECT * FROM oq_graph WHERE latch='breadth_first' AND origid=1 AND destid=6;
+----------+--------+--------+--------+------+--------+
| latch | origid | destid | weight | seq | linkid |
+----------+--------+--------+--------+------+--------+
| dijkstras| 1 | 6 | NULL | 0 | 1 |
| dijkstras| 1 | 6 | 1 | 1 | 2 |
| dijkstras| 1 | 6 | 1 | 2 | 6 |
+----------+--------+--------+--------+------+--------+
Note that nodes are uni-directional, so there is no path from node 6 to node 1:
SELECT * FROM oq_graph WHERE latch='dijkstras' AND origid=6 AND destid=1;
Empty set (0.00 sec)at0mic
18.05.2015 15:38Dijkstra в этом исполнении ищет только один самый дешевый путь, а я говорю про k-shortest paths, т.е. список самых дешевых путей отсортированных по весу. Pg_routing, например, умеет это делать. И Neo4j умеет через Java API.
A* тоже, кстати, не умеет.
remal
18.05.2015 15:40+4www.youtube.com/watch?v=Mw0Vimj39cI
Это доклад про java benchmarking. Крайне советую. Не потому, что это напрямую относится к теме статьи, а потому что, надеюсь, даст понимание, что для того, чтобы сделать замеры производительности, надо очень много знать и делать очень вдумчивые эксперименты.
На вашем бы месте я бы совсем не думал бы о бенчмарках, а сравнивал алгоритмы, подходы, основные задачи, простоту использования и т.п. Где хорошо использовать одно, а где другое без оглядки на производительность.ADobrianskiy Автор
18.05.2015 16:19Спасибо за совет, мне было интересноименно посмотреть как это дело происходит на практике. Этот процес затрагивает очень много другого, одними алгоритмами поиска здесь не обойтись, надо еще как минимум оптимизатора учитывать.
Jabher
18.05.2015 21:26+3Neo4j — то еще днище, если честно.
У меня сейчас аналогичная задача, только практическая — «отражение» части социального графа ВК на локальную базу, чтобы потом над ним манипулировать.
Оно отожрало все ресурсы системы (стандартный сервер за 20 баксов, ssd, 2 гига, 2 ядра) и медленно стагнирует, сейчас в базе около 0.3кк нод (с минимально нужным количеством данных, у большинства даже текстовых полей нет), они набились где-то за 3 дня. Мои теоретические расчеты говорили мне, что за 3 дня у меня будет все «отражение» в ~20кк нод, в жизни не думал, что уткнусь в производительность записи БД.
Запросы при этом уже оптимизированные, до оптимизаций за три дня было создано где-то 40к нод.
Сейчас либо переведу все на Titan, либо банальный postgres возьму, потому что так жить нельзя.
GearHead
18.05.2015 22:11+2Я на днях тестировал производительность neo4j на графе (200 000 вершин, 3 000 000+ дуг), который сейчас обслуживает PG. Причём не Embedded Java API, а на Cypher. Это было убогое днище, neo4j был буквально на порядок хуже. Я думаю, автор просто напорол чуши с настройкой мускула.
at0mic
18.05.2015 22:29+1Cypher сам по себе туповат, более того, у pg_routing более продвинутые алгоритмы поиска по графу. Cypher использует просто BFS сортируя результаты впоследствии.
Впрочем, pg_routing очень даже запросто загибается при поиске по большому ветвистому графу.
Rupper
Удивительные результаты!
В первых экспериментах на поиск время растет логарифмически, это я еще могу как-то понять. Но в последнем эксперименте такое поведение уже совсем не укладывается в голове.
Кстати, а как выглядела схема для MySQL? Были ли индексы, какие запросы выполнялись?
У Вас есть свое предположение о причинах такого роста времени у Neo4j?
at0mic
Как только у lucene заканчивается память, то начинаются тормоза.
В целом, ничего революционного в Neo4j по-моему нет. Главной проблемой для всех графовых баз данных является скорость доступа к самому графу, все алгоритмы траверсинга имеют примерно одинаковую производительность независимо от реализации.
В целом, Neo4j удобен Cypher'ом, но он позволяет реализовать только базовый поиск, а для использования более сложных алгоритмов прийдется использовать Java API.
ADobrianskiy Автор
Для реляционной бд дополнительных индексов не создавал. Разные росты времени напрямую зависят от алгоритмов поиска. Здесь нужен более глубокий анализ алгоритмов, чтобы понять причину такого огромного разрыва. Меня лично удивило то, что даже поиск по PK в MySQL на столько хуже.
vedenin1980
Вы бы показали что у вас в классах MySQLDAO и Neo4jDAO (это ведь ваши собственные классы?).
ADobrianskiy Автор
www.dropbox.com/sh/uuj6h2jxjgl1a16/AAAMStM-Gydqs7vSm-YjA5tCa?dl=0
vedenin1980
Ну, все просто же.
Вынесите
за цикл в идеале туда же где вы определяете Connection, недаром же в javadoc PreparedStatement пишут:
A SQL statement is precompiled and stored in a PreparedStatement object. This object can then be used to efficiently execute this statement multiple times.
И результаты экспериментов неожиданно станут совсем другими. У вас код большую часть времени тупо тратил на парсинг sql запросов и подготовку PreparedStatement на каждый чих.