Графовые базы данных для соц. сетей. Часть 1

Работа сис. админа
1 мин. на чтение

Если к вам в руки попала спецификация следующего Instagram, Facebook или хотя бы AirBnB, то вы можете сразу обратить внимание, что коренным отличием структуры хранения информации social-related проектах представляют собой связи. Нам уже мало знать, что существуют пользователи Виктория с какими-то параметрами и Михаил с другими параметрами, нас начинают интересовать взаимодействия пользователей, такие как дружба, взаимные друзья, общие интересы, «лайки» (классы, сердечки, супер – как ни назови, все равно речь про количественное выражение «симпатии»). Кроме того возникают еще сущности интересов, например есть список Книг, Фильмов, Хобби. На основании общих интересов (Михаилу и Виктории нравятся одинаковые книги) можно выдавать подсказки о том, что им неплохо бы подружиться.

Если рассматривать возможности реляционных баз данных, определенно придется строить непростые таблицы user_relationships, user_following, user_interaction, где будут храниться записи uuid одного пользователя,  uuid другого пользователя и как они провзаимодействовали.

Например, вполне возможен такой вариант:

itemOut relationship itemIn
Михаил дружит Елена
Виктор Гюго написал Отверженные
Билл Гейтс основал Фонд Билла и Мелинды Гейтс
Елена любит Мороженое

Когда таких пользователей перевалит через 1000 (что на самом деле очень мало), таблицы взаимодействий могут вырасти до гигантских размеров в несколько Гб. каждая. Обращение, выборки, JOIN постепенно будут деградировать по скорости, а внедрение новых фич в уже существующий проект будет делом нескольких недель, а то и месяцев.

Так же обратите внимание на очевидную ограниченность такой таблицы. Например это хорошо видно в научных работах. Предположим, у нас есть профессор и его ученики, которые написали совместную научную работу. Когда мы сделаем запрос к базе данных что-то вроде «дай-ка нам список авторов этой работы», то в ответ хотелось бы получить упорядоченных список авторов по их значимости (вкладу). Чтобы добиться такой возможности придется создавать все новые и новые поля в базе данных. Другой пример, связанный с нашей таблицей – как узнать в каком году Виктор Гюго [itg-tooltip href=»http://tooltip» tooltip-content=»<p>Первая публикация в <span style=&aquot;color: #222222; font-family: arial, sans-serif; font-size: small;&aquot;>1862 году :)</span></p>»]опубликовал[/itg-tooltip] своих «Отверженных»? Или с какого времени Михаил дружит с Еленой? А сколько им было тогда лет? Постепенно становится очевидно, что удовлетворить спрос на такие задачи реляционные базы данных не могут.

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

Сначала немного истории. Своим появлением графовые базы данным обязаны математическим графам, а те – Леонарду Эйлеру, который с их помощью доказал невозможность решения «Задачи о семи кёнигсбергских мостах» еще в далеком 1736 году.

Суть задачи проста: нужно пройти по всем 7 мостам, которые делят город Кенингсберг на 4 части, при этом не пройдя дважды по одному и тому же мосту.

Эйлер обратил внимание, что графическое отображение задачи можно максимально упростить с помощью точек и соединяющих их линий. Логично, что точками в нашей задаче выступают острова, а линиями – мосты. Эйлер так же заметил, что описание задачи нисколько не пострадает, если мы как-то передвинем точки относительно друг друга, при условии что количество и направление связей не исказится.

В дальнейшем при описании своей теории, Эйлер назвал «точки» – вершинами, соединяющих их «линии» – ребрами, а всю получающуюся конструкцию графом. От полноценного фундамента для наших графовых баз данных нас отделяет еще две вещи. Как вы помните из теории, обычно Автор пишет Книгу, т.е. ребра могут иметь направление. Когда у наших ребер есть направление, то такой граф называется ориентированным, соответственно граф без направления в ребрах называется неориентированным.

В существующих сегодня графовых БД существуют не только простые ориентации, но и сложные. Это понятно на примере с дружбой. Михаил не может дружить со Светланой в то самое время когда Светлана – нет. Поэтому существует так же связь вида (Светлана) -[Дружит с ]->(Михаил). Ну или просто их ребро имеет сразу двойное направление.

Последняя, но от этого не менее важная вещь – свойства ребер. Это уже не входит в базовые описания теории графов, а имеет уже отношение к графовым базам. Как мы уже говорили, тот факт что нам известно о том, что Виктор Гюго написал «Отверженные» еще не полная картина событий. Нас теоретически может заинтересовать: когда была написана эта книга, в каком городе  или стране, получил ли Гюго за публикацию гонорар и каков был его размер. Чтобы не создавать такие в какой-то мере бесполезные для общей структуры вершины, такие данные и хранятся в свойствах ребер.

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

Ihor Chyshkala

Пишу статьи про ИТ в свободное от работы время.

Оцените автора
Авторский блог Игоря Чишкалы
Добавить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.