какие бывают СУБД для графов?
2) такая же таблица в postgresql на SSD — норм, но SSD недёшев и перестаёт вмещать данныеКак-то это странно: 50млн*2(кол-во вершин)*22байта(размер числа)*2(индексы + системная инфа) ~ 4Гб.
нужно быстро отвечать на вопросы "дай мне N рёбер, выходящих из данной вершины" и "дай мне N рёбер, выходящие из данной вершины или входящие в неё"
Для таких простых вопросов не нужна специализированная СУБД. Я бы посмотрел в сторону key-value хранилищ, или же поднастроил реляционку.
намекать базе данных что хорошо бы хранить таблицу отсортированными по первому столбцу (в случае postgresql это pg_reorg, в случае oracle — organization)там параметр ещё есть "размер запасного места для вставок", ну да ты наверно знаешь.
+1 к классическим реляционкам - 15млн это фигня.
одимо хранить граф, вершин около 15млн, рёбер около 50млнвообще все должно в оперативку влезь... уж 16 гигов для рабочей станции не предел, так что проблем быть не должно
Тыкал пару раз тип таблиц OQGRAPH в MariaDB. Работает хорошо, шустренько. Только, зараза, живёт исключительно в памяти — при рестарте сервера надо создавать заново.
Посмотри Neo4j. Есть знакомые, ее использующие (по отзывам неплохая)
при таких раскладах дешевле всего взять любую реляционку (чем легче, тем лучше) и воткнуть на тачку с достаточным количеством памятя (16Г вроде хватает, но лучше 32)
если данные дальше будут расти и наступит момент шардоваться, то это отдельный разговор
если данные дальше будут расти и наступит момент шардоваться, то это отдельный разговор
если данные дальше будут растисчитаем что наступило
в предыдущий раз я облажался и занизил оценку
реально рёбер порядка 400млн (или 800млн, если хранить оба направления вершин порядка 40млн
для каждой вершины хранил бы массив её соседей и направление ребра
В постгресе есть массивы.
В постгресе есть массивы.я рассматривал такой вариант
но при записи будет большой оверхед, боюсь: ведь MVCC хранит версии этого массива
Как насчет файловой системы?
Название файла - id ноды, содержимое файла - список соседей.
Название файла - id ноды, содержимое файла - список соседей.
в постгресе напрягает что на каждую строку таблицы приходится 24-32б сраных заголовков
насчёт ФС подумаю. Мысль интересная!
насчёт ФС подумаю. Мысль интересная!
Как насчет файловой системы?когда RAID-контроллер имеет батарейку, postgres делает sync достаточно редко, и это безопасно
в случае с ФС, если мы добавляем 100 рёбер, нам придётся записать по 4 байта в _разные_ 101-200 файлов
сможем ли мы в таком случае сделать sync один раз, а не сотню? не происходит ли fsync при каждом fclose?
fuck
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.)
придётся ботать конкретные ФС
Хотя нет, идиотская идея - ни бэкапа, ни репликации.
как раз для этого сделали DRBD/HAST.
Хотя нет, идиотская идея - ни бэкапа, ни репликации.в принципе и то и то можно устроить в некоторых ФС
короче, буду ботать всякие необычные ФС
возможность снять снапшот считаю для этой задачи вредной — мне никакая внутренняя согласованность данных не нужна, а оверхеда от такой возможности не избежать
1) таблица (вершина1, вершина2) в postgresql на HDD с индексом — не хватает производительностиНе хватает производительности на чтение или на запись? Какое соотношение чтения и записи в системе?
На чём сделан проект?
Есть ли ограничения на количество ребёр, входящих или выходящих из вершины?
хранить надо только рёбра, вершины не надо (можно считать что вершины пронумерованы числами)Вершины у вас действительно являются числами, хранятся именно как INT или BIGINT?
Есть ли необходимость идти по второму, третьему или произвольному уровню после изначальной вершины? То есть, выбрали исходящие рёбра вершины, затем выбрали исходящие рёбра всех вершин результата и так далее.
короче, буду ботать всякие необычные ФСЯ бы поискал что-нибудь на основе DHT. Вот например серверная часть pohmelfs - это пул сторажей key-value, которые общаются друг с другом через dht. Соответственно файлы хранятся как записи в этой типоБД и через специальный гейт-посредник предоставляются клиенту
Не хватает производительности на чтение или на запись?думаю что на запись, но не уверен: на SSD перешли до меня, но репликацию вроде пробовали перед этим
Какое соотношение чтения и записи в системе?на одну запись строки в таблицу приходится чтение около 10 строк
На чём сделан проект?на пхп+постгрес
Есть ли ограничения на количество ребёр, входящих или выходящих из вершины?нет. Сейчас бывает до 100 тыщ.
Вершины у вас действительно являются числами, хранятся именно как INT или BIGINT?у вершин есть числовой ID, сейчас это bigint, но планируется для экономии перейти на int
Есть ли необходимость идти по второму, третьему или произвольному уровню после изначальной вершины? То есть, выбрали исходящие рёбра вершины, затем выбрали исходящие рёбра всех вершин результата и так далее.нет, такое не планируется
camlistore не пробовал? у него похожая идея, а цель — чтобы каждый мог хранить у себя данные.
на одну запись строки в таблицу приходится чтение около 10 строкПонятно, тогда репликация, скорее всего, не поможет. Думаю, что в вашем случае все проблемы можно решить с помощью шардинга, но здесь его не так просто применить. Я бы начал с шардов по идентификаторам вершин, основной проблемой в данном случае остаётся партиционирование во время записи, потому что добавление ребра может потребовать запись в две базы. Эту проблему можно решить, если пометить ребро специальным флагом, который постепенно сбрасывается фоновым процессом по факту проверки наличия обратного ребра в своём шарде. Вторая проблема тоже связана с партиционированием: если упал соотвествующий шард и у него нет реплики для чтения, то все рёбра, как входящие так и исходящие из вершин в шарде, будут недоступны. Проблема решается установкой 1-2 реплик для чтения.
Шарды можно устроить двумя способами: через хэширование идентификатора или через множества идентификаторов. Первый способ очень простой, но при его использовании очень тяжело добавлять новые шарды. Второй способ позволяет без проблем добавлять новые шарды, но усложняет добавление вершин.
Я рекомендую именно шардинг, потому что не очень люблю различные решения, которые массово не используются. Для альтернативы можно было бы посмотреть в сторону любого распределённого хранилища данных. Взять ту же Cassandra, весьма адская штуковина, но мне очень не нравится по итогам попыток её запуска в нескольких проектах, в которых я участвовал. Шардинг на MySQL и SQL Server мне показался проще как со стороны программирования, так и со стороны поддержки.
нужно быстро отвечать на вопросы "дай мне N рёбер, выходящих из данной вершины" и "дай мне N рёбер, выходящие из данной вершины или входящие в неё"Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?
Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?Автор как раз просит рекомендаций по поводу таких БД.
Автор как раз просит рекомендаций по поводу таких БД.Вроде нет, там в 4-х пунктах какие-то ужасы написаны про реляционные БД, а потом про ФС.
Вроде есть MongoDB (чего-то не видел ссылку на нее в треде) и какой-нть Redis.
Чотаянепонял, а что мешает завести две key-value БД, одну с ответами на первый вопрос, вторую с ответами на второй?думаешь не страшно что value для жирной вершины степени 100-1000 каждый раз придётся перезаписывать при добавлении ребра? если БД поддерживает снапшоты — это автоматом означает что мы будем хранить кучу версий этого value, всё это хозяйство распухнет на диске итд
Думаю, что в вашем случае все проблемы можно решить с помощью шардинга, но здесь его не так просто применитьшардинг уже применён (с реляционной БД по хешу от идентификатора. Шардим на 8 частей, пока держим 2 машины по 4 части на машине.
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое лёгкое решение
думаешь не страшно что value для жирной вершины степени 100-1000 каждый раз придётся перезаписывать при добавлении ребра?Не знаю. Из твоего описания задачи это неясно.
К тому же надо читать доки — в редиске можно к значению типа "список" приписывать вершинки слева или справа.
http://redis.io/topics/data-types
И с Монгой та же ситуация - http://www.mongodb.org/display/DOCS/Updating#Updating-%24pus...
если БД поддерживает снапшоты — это автоматом означает что мы будем хранить кучу версий этого value, всё это хозяйство распухнет на диске итд
Ичо? Пусть пухнет.
Ичо? Пусть пухнет.значит будет записи в несколько раз больше чем надо, и индексы чаще меняться будут
шардинг уже применён (с реляционной БД по хешу от идентификатора. Шардим на 8 частей, пока держим 2 машины по 4 части на машине.У вас есть точное понимание, что именно тормозит? Две машины на 800 млн простых записей должно по идее хватать. Вы индексируете по двум номерам вершин и какому-нибудь auto increment числу или просто по двум номерам вершин? Варианты поставить 4-8 машин не подходят?
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое лёгкое решениеТак в чём проблема: в этом ощущении или всё-таки в производительности?
К сожалению, я не работал с Postgress и не знаю, есть ли там аналог такой вещи, как CLUSTERED INDEX в SQL Server.У вас есть точное понимание, что именно тормозит? Две машины на 800 млн простых записей должно по идее хватать.там сейчас всё гораздо более запутано, куча лишних данных на рёбрах, но суть та же
обсуждается, как переделать эту систему, желательно уместив в одну машину
Так в чём проблема: в этом ощущении или всё-таки в производительности?проблема в том, что если не менять структуру — то точно будет тормозить, если подать бОльшую нагрузку
сейчас, когда планируется редизайн хранилища, хочется придумать оптимальную схему хранения
К сожалению, я не работал с Postgress и не знаю, есть ли там аналог такой вещи, как CLUSTERED INDEX в SQL Server.толком нету, к сожалению
есть 2 реализации, первая блокирует чтение при переупорядочении, вторая глючная
значит будет записи в несколько раз больше чем надо, и индексы чаще меняться будутТы с ВМК что ли?
Ты с ВМК что ли?нет, а ты?
предлагаю обойтись без срачей, если тебе кажется что я где-то ошибаюсь — сообщи своё мнение
но возникает ощущение, что мы тратим ресурсы на ненужные нам вещи: у нас хранится, читается и пишется как таблица, так и индекс, а нам фактически нужен только индекс, но РСУБД нам не может предложить такое лёгкое решениеЭто косяк не РСУБД, а конкретно постгреса: он лезет в таблицу чтобы проверить видимость строки. В твоем случае это совершенно лишний оверхед, так как строки не удаляются и всегда видимы. Тот же оракл не лезет в таблицу, если все нужные столбцы есть в индексе. Index cover это сейчас номер один feature request для постгреса.
В MySQL кстати вся таблица целиком лежит в индексе по первичному ключу.
предлагаю обойтись без срачей, если тебе кажется что я где-то ошибаюсь — сообщи своё мнениеПоясню: ты пропустил смысл сообщения, стал спрашивать про какие-то подробности про битики и байтики, которые не проверил нужны ли тебе вообще. Хотя бы прикинуть с цифрами.
"Пухнет" оно там по не совсем очевидным законам, проще проверить как именно, чем угадывать эти законы.
тогда при таких простых запросах есть резон посмотреть в сторону обычных бдбэшек — быстро, дешево, маштабируемо. полноценная реляционка типа постгри все-таки довольно большой оверхед дает — на небольших данных можно смириться, на таких наверно уже нет.
монго-редисы — хз, пару лет назад были совершенно неюзабельны.
могу еще сказать про графы друзей двух из трех крупнейших социалок рунета (там размеры десятки миллиардов записей): в одной бдбэшки, обвешанные кэшами, в другой полностью самописное хранилище.
в фейсбуке кстати тоже свое хранилище.
монго-редисы — хз, пару лет назад были совершенно неюзабельны.
могу еще сказать про графы друзей двух из трех крупнейших социалок рунета (там размеры десятки миллиардов записей): в одной бдбэшки, обвешанные кэшами, в другой полностью самописное хранилище.
в фейсбуке кстати тоже свое хранилище.
если говорить про социалки, то можно взять у твитера:
http://github.com/twitter/flockdb
http://github.com/twitter/gizzard
но разбираться надо самому, не слышал, чтобы их у нас использовали (правда, соцсетей тоже не писал
)
http://github.com/twitter/flockdb
http://github.com/twitter/gizzard
но разбираться надо самому, не слышал, чтобы их у нас использовали (правда, соцсетей тоже не писал
)В фейсбуке используется MySQL с обвесами для хранения ключ-значение + свой кэш. ссылка
Я может во всем этом дилетант, но пришла в голову такая идея:
1. Создать две таблицы (исходящие связи, входящие связи) (id1, id2)
2. Раздробить каждую таблицу на несколько по id1. Т.е. в каждой таблице хранить ограниченное количество записей с различными id1, например по 100 тыс. (Весь индекс балансироваться не будет)
Я может во всем этом дилетант, но пришла в голову такая идея:
1. Создать две таблицы (исходящие связи, входящие связи) (id1, id2)
2. Раздробить каждую таблицу на несколько по id1. Т.е. в каждой таблице хранить ограниченное количество записей с различными id1, например по 100 тыс. (Весь индекс балансироваться не будет)
Наверно не MySQL, а один из ее вариантов - http://citforum.ru/gazeta/170/
Оставить комментарий
hwh2010
необходимо хранить граф, вершин около 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): для каждой вершины хранил бы массив её соседей и направление ребра, если массив распухает и не лезет в отведённое ему место диска — освобождаю его для новых вершин с меньшим числом соседей и переношу его в свободное место. короче в любом случае данные о соседях каждой вершины лежат на диске рядом