|
ayvango
|
|
ушастый
|
|
|
|
|
|
|
Рег.: 10.01.2006
|
|
Сообщений: 27732
|
|
Из: Воронеж
|
|
Рейтинг: 11832
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 00:07
|
|
|
Quote:
короче, буду ботать всякие необычные ФС
Я бы поискал что-нибудь на основе DHT. Вот например серверная часть pohmelfs - это пул сторажей key-value, которые общаются друг с другом через dht. Соответственно файлы хранятся как записи в этой типоБД и через специальный гейт-посредник предоставляются клиенту
|
Сеть темна и полна ужасов |
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: Mike]
17.02.2012 00:37
|
|
|
В ответ на:
Не хватает производительности на чтение или на запись?
думаю что на запись, но не уверен: на SSD перешли до меня, но репликацию вроде пробовали перед этимВ ответ на:
Какое соотношение чтения и записи в системе?
на одну запись строки в таблицу приходится чтение около 10 строкВ ответ на:
На чем сделан проект?
на пхп+постгресВ ответ на:
Есть ли ограничения на количество ребер, входящих или выходящих из вершины?
нет. Сейчас бывает до 100 тыщ.В ответ на:
Вершины у вас действительно являются числами, хранятся именно как INT или BIGINT?
у вершин есть числовой ID, сейчас это bigint, но планируется для экономии перейти на intВ ответ на:
Есть ли необходимость идти по второму, третьему или произвольному уровню после изначальной вершины? То есть, выбрали исходящие ребра вершины, затем выбрали исходящие ребра всех вершин результата и так далее.
нет, такое не планируется
|
|
|
vissi
|
|
|
|
|
|
|
|
|
Рег.: 30.09.2007
|
|
Сообщений: 9275
|
|
|
|
Рейтинг: 8222
|
|
Re: какие бывают СУБД для графов?
[re: ayvango]
17.02.2012 00:51
|
|
|
camlistore не пробовал? у него похожая идея, а цель - чтобы каждый мог хранить у себя данные.
|
|
|
|
Mike
|
|
Ызарг
|
|
|
|
|
|
|
Рег.: 02.11.2002
|
|
Сообщений: 8098
|
|
|
|
Рейтинг: 2147
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 01:10
|
|
|
Quote:
на одну запись строки в таблицу приходится чтение около 10 строк
Понятно, тогда репликация, скорее всего, не поможет. Думаю, что в вашем случае все проблемы можно решить с помощью шардинга, но здесь его не так просто применить. Я бы начал с шардов по идентификаторам вершин, основной проблемой в данном случае остается партиционирование во время записи, потому что добавление ребра может потребовать запись в две базы. Эту проблему можно решить, если пометить ребро специальным флагом, который постепенно сбрасывается фоновым процессом по факту проверки наличия обратного ребра в своем шарде. Вторая проблема тоже связана с партиционированием: если упал соотвествующий шард и у него нет реплики для чтения, то все ребра, как входящие так и исходящие из вершин в шарде, будут недоступны. Проблема решается установкой 1-2 реплик для чтения.
Шарды можно устроить двумя способами: через хэширование идентификатора или через множества идентификаторов. Первый способ очень простой, но при его использовании очень тяжело добавлять новые шарды. Второй способ позволяет без проблем добавлять новые шарды, но усложняет добавление вершин.
Я рекомендую именно шардинг, потому что не очень люблю различные решения, которые массово не используются. Для альтернативы можно было бы посмотреть в сторону любого распределенного хранилища данных. Взять ту же Cassandra, весьма адская штуковина, но мне очень не нравится по итогам попыток ее запуска в нескольких проектах, в которых я участвовал. Шардинг на MySQL и SQL Server мне показался проще как со стороны программирования, так и со стороны поддержки.
|
|
|
__No__
|
|
|
|
|
|
|
|
|
Рег.: 17.01.2005
|
|
Сообщений: 21063
|
|
Из: Внутренняя Монголия
|
|
Рейтинг: 6309
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 01:20
|
|
|
В ответ на:
нужно быстро отвечать на вопросы "дай мне N ребер, выходящих из данной вершины" и "дай мне N ребер, выходящие из данной вершины или входящие в нее"
Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?
|
Dixi. |
|
|
Mike
|
|
Ызарг
|
|
|
|
|
|
|
Рег.: 02.11.2002
|
|
Сообщений: 8098
|
|
|
|
Рейтинг: 2147
|
|
Re: какие бывают СУБД для графов?
[re: __No__]
17.02.2012 01:22
|
|
|
Quote:
Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?
Автор как раз просит рекомендаций по поводу таких БД.
|
|
|
__No__
|
|
|
|
|
|
|
|
|
Рег.: 17.01.2005
|
|
Сообщений: 21063
|
|
Из: Внутренняя Монголия
|
|
Рейтинг: 6309
|
|
Re: какие бывают СУБД для графов?
[re: Mike]
17.02.2012 01:25
|
|
|
В ответ на:
Автор как раз просит рекомендаций по поводу таких БД.
Вроде нет, там в 4-х пунктах какие-то ужасы написаны про реляционные БД, а потом про ФС.
Вроде есть MongoDB (чего-то не видел ссылку на нее в треде) и какой-нть Redis.
|
Dixi. |
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: __No__]
17.02.2012 10:27
|
|
|
В ответ на:
Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?
думаешь не страшно что value для жирной вершины степени 100-1000 каждый раз придется перезаписывать при добавлении ребра? если БД поддерживает снапшоты - это автоматом означает что мы будем хранить кучу версий этого value, все это хозяйство распухнет на диске итд
|
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: Mike]
17.02.2012 10:33
|
|
|
В ответ на:
Думаю, что в вашем случае все проблемы можно решить с помощью шардинга, но здесь его не так просто применить
шардинг уже применен (с реляционной БД), по хешу от идентификатора. Шардим на 8 частей, пока держим 2 машины по 4 части на машине.
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое легкое решение
|
|
|
__No__
|
|
|
|
|
|
|
|
|
Рег.: 17.01.2005
|
|
Сообщений: 21063
|
|
Из: Внутренняя Монголия
|
|
Рейтинг: 6309
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 11:42
|
|
|
В ответ на:
думаешь не страшно что value для жирной вершины степени 100-1000 каждый раз придется перезаписывать при добавлении ребра?
Не знаю. Из твоего описания задачи это неясно.
К тому же надо читать доки - в редиске можно к значению типа "список" приписывать вершинки слева или справа.
http://redis.io/topics/data-types
И с Монгой та же ситуация - http://www.mongodb.org/display/DOCS/Updating#Updating-%24pus...
В ответ на:
если БД поддерживает снапшоты - это автоматом означает что мы будем хранить кучу версий этого value, все это хозяйство распухнет на диске итд
Ичо? Пусть пухнет.
Редактировал __No__ (17.02.2012 11:53)
|
Dixi. |
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: __No__]
17.02.2012 12:14
|
|
|
В ответ на:
Ичо? Пусть пухнет.
значит будет записи в несколько раз больше чем надо, и индексы чаще меняться будут
|
|
|
Mike
|
|
Ызарг
|
|
|
|
|
|
|
Рег.: 02.11.2002
|
|
Сообщений: 8098
|
|
|
|
Рейтинг: 2147
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 12:57
|
|
|
Quote:
шардинг уже применен (с реляционной БД), по хешу от идентификатора. Шардим на 8 частей, пока держим 2 машины по 4 части на машине.
У вас есть точное понимание, что именно тормозит? Две машины на 800 млн простых записей должно по идее хватать. Вы индексируете по двум номерам вершин и какому-нибудь auto increment числу или просто по двум номерам вершин? Варианты поставить 4-8 машин не подходят?
Quote:
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое легкое решение
Так в чем проблема: в этом ощущении или все-таки в производительности?  К сожалению, я не работал с Postgress и не знаю, есть ли там аналог такой вещи, как CLUSTERED INDEX в SQL Server.
|
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: Mike]
17.02.2012 13:12
|
|
|
В ответ на:
У вас есть точное понимание, что именно тормозит? Две машины на 800 млн простых записей должно по идее хватать.
там сейчас все гораздо более запутано, куча лишних данных на ребрах, но суть та же
обсуждается, как переделать эту систему, желательно уместив в одну машинуВ ответ на:
Так в чем проблема: в этом ощущении или все-таки в производительности?
проблема в том, что если не менять структуру - то точно будет тормозить, если подать бОльшую нагрузку
сейчас, когда планируется редизайн хранилища, хочется придумать оптимальную схему храненияВ ответ на:
К сожалению, я не работал с Postgress и не знаю, есть ли там аналог такой вещи, как CLUSTERED INDEX в SQL Server.
толком нету, к сожалению
есть 2 реализации, первая блокирует чтение при переупорядочении, вторая глючная
|
|
|
__No__
|
|
|
|
|
|
|
|
|
Рег.: 17.01.2005
|
|
Сообщений: 21063
|
|
Из: Внутренняя Монголия
|
|
Рейтинг: 6309
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 13:17
|
|
|
В ответ на:
значит будет записи в несколько раз больше чем надо, и индексы чаще меняться будут
Ты с ВМК что ли? 
|
Dixi. |
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: какие бывают СУБД для графов?
[re: __No__]
17.02.2012 14:34
|
|
|
В ответ на:
Ты с ВМК что ли?
нет, а ты?
предлагаю обойтись без срачей, если тебе кажется что я где-то ошибаюсь - сообщи свое мнение
|
|
|
DDD2
|
|
sir
|
|
|
|
|
|
|
Рег.: 23.11.2007
|
|
Сообщений: 1103
|
|
|
|
Рейтинг: 246
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 15:14
|
|
|
В ответ на:
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое легкое решение
Это косяк не РСУБД, а конкретно постгреса: он лезет в таблицу чтобы проверить видимость строки. В твоем случае это совершенно лишний оверхед, так как строки не удаляются и всегда видимы. Тот же оракл не лезет в таблицу, если все нужные столбцы есть в индексе. Index cover это сейчас номер один feature request для постгреса.
В MySQL кстати вся таблица целиком лежит в индексе по первичному ключу.
|
|
|
__No__
|
|
|
|
|
|
|
|
|
Рег.: 17.01.2005
|
|
Сообщений: 21063
|
|
Из: Внутренняя Монголия
|
|
Рейтинг: 6309
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
17.02.2012 15:47
|
|
|
В ответ на:
предлагаю обойтись без срачей, если тебе кажется что я где-то ошибаюсь - сообщи свое мнение
Поясню: ты пропустил смысл сообщения, стал спрашивать про какие-то подробности про битики и байтики, которые не проверил нужны ли тебе вообще. Хотя бы прикинуть с цифрами.
"Пухнет" оно там по не совсем очевидным законам, проще проверить как именно, чем угадывать эти законы.
|
Dixi. |
|
|
johnny_bee
|
|
bluesman
|
|
|
|
|
|
|
Рег.: 25.10.2002
|
|
Сообщений: 877
|
|
|
|
Рейтинг: 44
|
|
Re: какие бывают СУБД для графов?
[re: bashtanov]
18.02.2012 00:01
|
|
|
тогда при таких простых запросах есть резон посмотреть в сторону обычных бдбэшек - быстро, дешево, маштабируемо. полноценная реляционка типа постгри все-таки довольно большой оверхед дает - на небольших данных можно смириться, на таких наверно уже нет.
монго-редисы - хз, пару лет назад были совершенно неюзабельны.
могу еще сказать про графы друзей двух из трех крупнейших социалок рунета (там размеры десятки миллиардов записей): в одной бдбэшки, обвешанные кэшами, в другой полностью самописное хранилище.
в фейсбуке кстати тоже свое хранилище.
|
|
|
vissi
|
|
|
|
|
|
|
|
|
Рег.: 30.09.2007
|
|
Сообщений: 9275
|
|
|
|
Рейтинг: 8222
|
|
|
|
|
|
ramir
|
|
|
|
|
|
|
|
|
Рег.: 19.04.2008
|
|
Сообщений: 802
|
|
Из: ФДС
|
|
Рейтинг: 469
|
|
|
В фейсбуке используется MySQL с обвесами для хранения ключ-значение + свой кэш. ссылка
Я может во всем этом дилетант, но пришла в голову такая идея:
1. Создать две таблицы (исходящие связи, входящие связи) (id1, id2)
2. Раздробить каждую таблицу на несколько по id1. Т.е. в каждой таблице хранить ограниченное количество записей с различными id1, например по 100 тыс. (Весь индекс балансироваться не будет)
Редактировал ramir (11.03.2012 11:40)
|
|
Список
Плоский
Дерево
)