bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
какие бывают СУБД для графов?
06.02.2012 00:48
|
|
|
необходимо хранить граф, вершин около 15млн, ребер около 50млн граф только растет, ничего не удаляется ребра ориентированные хранить надо только ребра, вершины не надо (можно считать что вершины пронумерованы числами)
нужно быстро отвечать на вопросы "дай мне N ребер, выходящих из данной вершины" и "дай мне N ребер, выходящие из данной вершины или входящие в нее"
как уже пробовали хранить: 1) таблица (вершина1, вершина2) в postgresql на HDD с индексом - не хватает производительности 2) такая же таблица в postgresql на SSD - норм, но SSD недешев и перестает вмещать данные
из костылей приходит на ум: 3) партицирование (уже используется), 4) хранить данные дважды (в1-в2 и в2-в1) в разных таблицах, намекать базе данных что хорошо бы хранить таблицу отсортированными по первому столбцу (в случае postgresql это pg_reorg, в случае oracle - organization)
но мне кажется что в связи с развитием нынче тонны nosql-решений должна быть субд которая умеет только хранить граф и отвечать на поставленные вопросы, но делать это хорошо (т.е. не вызывая random scan по всему диску) как же она называется?
если бы я сам писал что-то такое, я бы наверное хранил данные примерно как в (4): для каждой вершины хранил бы массив ее соседей и направление ребра, если массив распухает и не лезет в отведенное ему место диска - освобождаю его для новых вершин с меньшим числом соседей и переношу его в свободное место. короче в любом случае данные о соседях каждой вершины лежат на диске рядом
|
|
Chamrajnagar
|
T_T
|
|
|
|
Рег.: 24.11.2005
|
Сообщений: 5095
|
Из: Северное кучкино
|
Рейтинг: 3360
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
06.02.2012 00:55
|
|
|
Покапитаню
|
Era of Lite beer, hand calculators and "user-friendly" software. |
|
Burjui
|
Pooh-Bah
|
|
|
|
Рег.: 26.11.2005
|
Сообщений: 2416
|
|
Рейтинг: 3784
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
06.02.2012 01:25
|
|
|
В ответ на:
2) такая же таблица в postgresql на SSD - норм, но SSD недешев и перестает вмещать данные
Как-то это странно: 50млн*2(кол-во вершин)*22байта(размер числа)*2(индексы + системная инфа) ~ 4Гб.
В ответ на:
нужно быстро отвечать на вопросы "дай мне N ребер, выходящих из данной вершины" и "дай мне N ребер, выходящие из данной вершины или входящие в нее"
Для таких простых вопросов не нужна специализированная СУБД. Я бы посмотрел в сторону key-value хранилищ, или же поднастроил реляционку.
|
|
CROTishka
|
Shai-Hulud
|
|
|
|
Рег.: 09.06.2004
|
Сообщений: 31439
|
Из: - под земли
|
Рейтинг: 3654
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
06.02.2012 10:38
|
|
|
В ответ на:
намекать базе данных что хорошо бы хранить таблицу отсортированными по первому столбцу (в случае postgresql это pg_reorg, в случае oracle - organization)
там параметр еще есть "размер запасного места для вставок", ну да ты наверно знаешь. +1 к классическим реляционкам - 15млн это фигня.
|
|
|
Driver
|
Pooh-Bah
|
|
|
|
Рег.: 12.11.2004
|
Сообщений: 2185
|
|
Рейтинг: 1677
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
06.02.2012 15:53
|
|
|
Quote:
одимо хранить граф, вершин около 15млн, ребер около 50млн
вообще все должно в оперативку влезь... уж 16 гигов для рабочей станции не предел, так что проблем быть не должно
|
|
Sevurrrra
|
Хранитель маяка
|
|
|
|
Рег.: 10.09.2007
|
Сообщений: 2051
|
|
Рейтинг: 2759
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
06.02.2012 18:35
|
|
|
Тыкал пару раз тип таблиц OQGRAPH в MariaDB. Работает хорошо, шустренько. Только, зараза, живет исключительно в памяти - при рестарте сервера надо создавать заново.
|
|
sadreamer
|
nuclear eclair
|
|
|
|
Рег.: 21.09.2009
|
Сообщений: 487
|
|
Рейтинг: 1464
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
08.02.2012 21:15
|
|
|
Посмотри Neo4j. Есть знакомые, ее использующие (по отзывам неплохая)
|
|
johnny_bee
|
bluesman
|
|
|
|
Рег.: 25.10.2002
|
Сообщений: 877
|
|
Рейтинг: 44
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
12.02.2012 01:52
|
|
|
при таких раскладах дешевле всего взять любую реляционку (чем легче, тем лучше) и воткнуть на тачку с достаточным количеством памятя (16Г вроде хватает, но лучше 32)
если данные дальше будут расти и наступит момент шардоваться, то это отдельный разговор
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
|
В ответ на:
если данные дальше будут расти
считаем что наступило в предыдущий раз я облажался и занизил оценку реально ребер порядка 400млн (или 800млн, если хранить оба направления), вершин порядка 40млн
|
|
DDD2
|
sir
|
|
|
|
Рег.: 23.11.2007
|
Сообщений: 1103
|
|
Рейтинг: 246
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
16.02.2012 17:02
|
|
|
В ответ на:
для каждой вершины хранил бы массив ее соседей и направление ребра
В постгресе есть массивы.
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 17:18
|
|
|
В ответ на:
В постгресе есть массивы.
я рассматривал такой вариант но при записи будет большой оверхед, боюсь: ведь MVCC хранит версии этого массива ![:(](/images/graemlins/frown.gif)
|
|
DDD2
|
sir
|
|
|
|
Рег.: 23.11.2007
|
Сообщений: 1103
|
|
Рейтинг: 246
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
16.02.2012 17:49
|
|
|
Как насчет файловой системы? Название файла - id ноды, содержимое файла - список соседей.
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 18:18
|
|
|
в постгресе напрягает что на каждую строку таблицы приходится 24-32б сраных заголовков ![:(](/images/graemlins/frown.gif)
насчет ФС подумаю. Мысль интересная!
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 19:30
|
|
|
В ответ на:
Как насчет файловой системы?
когда RAID-контроллер имеет батарейку, postgres делает sync достаточно редко, и это безопасно в случае с ФС, если мы добавляем 100 ребер, нам придется записать по 4 байта в _разные_ 101-200 файлов сможем ли мы в таком случае сделать sync один раз, а не сотню? не происходит ли fsync при каждом fclose?
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 19:32
|
|
|
man 2 close:
It is not common for a file system to flush the buffers when the stream is closed. If you need to be sure that the data is physically stored use fsync(2). (It will depend on the disk hardware at this point.)
fuck придется ботать конкретные ФС
|
|
DDD2
|
sir
|
|
|
|
Рег.: 23.11.2007
|
Сообщений: 1103
|
|
Рейтинг: 246
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
16.02.2012 23:00
|
|
|
Хотя нет, идиотская идея - ни бэкапа, ни репликации.
|
|
vissi
|
|
|
|
|
Рег.: 30.09.2007
|
Сообщений: 9275
|
|
Рейтинг: 8222
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 23:23
|
|
|
как раз для этого сделали DRBD/HAST.
|
|
|
bashtanov
|
спец по говядине
|
|
|
|
Рег.: 11.05.2007
|
Сообщений: 9569
|
Из: например
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: DDD2]
16.02.2012 23:29
|
|
|
В ответ на:
Хотя нет, идиотская идея - ни бэкапа, ни репликации.
в принципе и то и то можно устроить в некоторых ФС короче, буду ботать всякие необычные ФС
возможность снять снапшот считаю для этой задачи вредной - мне никакая внутренняя согласованность данных не нужна, а оверхеда от такой возможности не избежать
|
|
Mike
|
Ызарг
|
|
|
|
Рег.: 02.11.2002
|
Сообщений: 8098
|
|
Рейтинг: 2147
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
16.02.2012 23:40
|
|
|
Quote:
1) таблица (вершина1, вершина2) в postgresql на HDD с индексом - не хватает производительности
Не хватает производительности на чтение или на запись? Какое соотношение чтения и записи в системе?
На чем сделан проект?
Есть ли ограничения на количество ребер, входящих или выходящих из вершины?
|
|
Mike
|
Ызарг
|
|
|
|
Рег.: 02.11.2002
|
Сообщений: 8098
|
|
Рейтинг: 2147
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
16.02.2012 23:52
|
|
|
Quote:
хранить надо только ребра, вершины не надо (можно считать что вершины пронумерованы числами)
Вершины у вас действительно являются числами, хранятся именно как INT или BIGINT?
Есть ли необходимость идти по второму, третьему или произвольному уровню после изначальной вершины? То есть, выбрали исходящие ребра вершины, затем выбрали исходящие ребра всех вершин результата и так далее.
|
|