Графовые

Записаться

Переходим к теме графовых баз данных. Это яркий представитель новых SQL баз. Но если мы раньше говорили, что большинство новых SQL баз это противопоставление требованиям ACID: атомарность, целостность, изолированность и надежность данных, то есть — требования к транзакционным системам, то графовые базы данных в общем случае могут удовлетворять, как мы дальше это увидим, данным требованиям.

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

Типичная схема данных RDF приложения это, в первую очередь, хранение и анализ сложных связанных данных в геоинформационных системах и в социальных сетях. Вот типичный пример графов, с которым вы, наверное, сталкивались, и очень часто, в своей жизни. Первый граф — это граф связи в социальных сетях, то, что иногда называют "friend to friend": друг друга друга или друзья друзей. Очень часто графы, задачи и методы решения задач на графах используются в геоинформационных системах, например, в задачах проложения маршрута. И тут часто, чтобы впечатлить возможностями данных подходов, приводится в пример сервис. Например, общеевропейские сервисы, которые прокладывают маршрут из одной страны в другую, из заданного города в заданный, и рассчитывают не только длину пути кратчайшего, но и скорость, с учетом текущего состояния всех этих дорог, трасс по маршруту.

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

Еще один пример, когда мы можем поискать с достаточно сложно связанных или сложно запутанных данных какие-либо называемые "инсайты". Это та информация, которая не достается исковыми запросами и, возможно, задается при непосредственном интерактивном взаимодействии с данными, в частности, с абстракциями сети. Каким образом позиционируются графовые базы данных относительно остальных? Таким образом, как только у нас сложность в виде взаимоувязанности объектов превышает миллионы и приближается к миллиардам, то это графовые базы данных. Это легко понять. В ближайшее время приблизится к миллиарду количество пользователей фейсбука и у каждого в среднем по 100 связей.

Как раз 109 связей есть самый яркий представитель графовых баз данных — это Neo4j. Это флагман,во-первых, потому что создатели в своей жизни засветились, во-вторых, потому что они предпринимают усилия по некоторой стандартизации различных реализаций графовых баз данных. Итак, Neo4j — это встраиваемое java приложение базы данных. Сама написана тоже на java, она полностью реализует требования ACID, начата была давно, в 2003 году. Кластеризация возможна, но дальше мы покажем ограничения. То есть, в первую очередь, данная база данных жертвует распределенностью, разделяемостью, если говорить в терминах теремы CAP.

Простейшая схема данных, у нас есть только узлы сети и только связи между ними. Связи могут быть типизированы, они индексируются, узлы могут иметь атрибуты самых разных типов графов: ориентированные графы, задавая ориентацию через атрибут связи; гиперграф — графы, у которых между двумя узлами несколько связей разного типа; многопродуктовый граф, и так далее. Интерфейсы, в основном, используем Embedded Java Api и вот эти попытки, которые игра смартизация, так называемой blue print, предпринимается. Я думаю, здесь еще все впереди и определенная часть поиска того, какие должны быть интерфейсы у графовых баз, какие они основные свойства должны реализовывать, еще будет развиваться и меняться.

Здесь приведен пример, как раз, Java интерфейса. Мы видим, что есть операции, но стандартные типы — это строковое значение, узел, relation, то есть связь между узлами, и все остальное описывается через атрибуты данных объектов. У нас есть такие абстракции, как стартовый узел, конечный узел, и здесь показана, как раз, типизация отношения "входящие-исходящие", и можно еще нагрузить другими атрибутами эту связь и индексировать, как атрибут свойства узлов, так и свойства связей.

Непосредственно в Neo4j используется механизм индексации "lucene" и пользователь сам явно указывает, какие индексы ему нужны, как их составлять, как с ними работать, как по ним искать. Вот чем отличается Neo4j от всего остального, с точки зрения инструментов, которые она дает пользователю. Это, в первую очередь, поиск узлов и связей по индексу или по разным индексам, и, самое важное, траверс графа. Это проход по графу, как в ширину, так и в глубину, перебор отношений и узлов, и, в том числе, алгоритмы поиска пути из узла в узел. То есть, если вы, например, на простой базе, я думаю, где-нибудь в базе IMDb, про фильмы, конечно же, лежат все связи фильмов с актерами, режиссеров с фильмами, и так далее. Все это, скорее всего, лежит, в лицензионной базе данных, но если вы пытались на такой базе данных построить с кем работал, какие актеры пересекались по режиссеру, то вам нужно будет построить цепочку джойнa от актера 1 до фильма — 1, от фильма до режиссера — 2, от режиссера снова до фильма — 3, и от фильма снова до актера — 4. Select будет с 4 джойнaми, и понимаете, сколько он будет исполняться.

Что предлагает Neo4j? Вам предлагает стандартную операцию найти путь или найти пути, параметром которого может быть один или много путей, и максимальная глубина. Эта операция делается, естественно, гораздо более оптимально, чем вы делали бы select с многочисленными джойнaми.

Свойства — мы сказали про ACID, мы теперь говорим про многопоточность, которая реализована внутри. Транзакция существует только на запись, что в общем-то, нам не мешает, и встроенным алгоритмом, про которого тоже сказали: обход шириной в глубину, поиск пути, в том числе пути Дейкстры, и поиск всех путей, реализованный просто, как внутренняя операция. Что он предлагает в качестве пользовательских интерфейсов? Это веб-консоль с достаточно привлекательным динамичным, интерактивным интерфейсом, когда мы просто кликами мышки можем показывать или сворачивать все связи данного узла, и, таким образом, продвигаясь от одного узла к другому, выявлять себе какие-то неожиданные сведения, находить, так называемые, инсайты. Это прямо стандартно, вам стоит только загрузить туда и преобразовать свои данные в тот вид, который требует Neo4j, и вы можете уже таким образом с ней работать. Из вкусного есть open-source инструмент анализа и визуализации, я бы сказал, в первую очередь, визуализации. Но и алгоритм анализа тоже активно очень пишется сообществом и встраивается в эту платформу Gephi. Они перестали быть инструментом, и этот инструмент может непосредственно обращаться к хранилищу Neo4j, то есть, к хранилищу, уже в виде абстракции узлов и связей.

Что у нас с распределенностью? Мы говорим, что, в первую очередь, это встроенная база, поэтому первое использование, это, конечно же, на одной машине. Почему распределенность не является свойством по умолчанию? Потому что именно для таких алгоритмов, именно для таких операций, нужен последовательный переход и практически в непредсказуемом порядке между различными узлами. Это значит, что в распределенной системе операцию MapReduce нам нужно будет делать либо очень большое количество тактов, очень много повторений, либо нам придется как-то передвигать данные, чтобы оптимизировать эти переходы, но тогда мы попадаем в узкое место в связи между нодами. Один из выходов из этой ситуации — это производить над сетью сначала операции кластеризации, выявлять где у нас наибольшая плотность, и такие кластеры размещать на конкретных нодах, а наименьшие сечения располагать, как раз, между физическими нодами, где хранятся данные.

Чтобы показать, что это не останавливает разработчиков, которые думают о графовых базах, приводим здесь все те инициативы, которые на данный момент существуют для графовых баз данных. Мы видим, что здесь есть и Google, и Apache, и Intel, и другие компании, и, кстати, показательно, что и Twitter использует, и Microsoft, и показательно, что все эти разработки еще находятся пока в research подразделениях больших компаний. То есть это говорит о том, что они точно понимают, что данные системы очень перспективны, и исследованием в данной области нужно заниматься. Но это говорит нам еще и о том, что данные системы незрелы, идет активный поиск и, в ближайшее время, я думаю, мы получим что-то более простое, понятно стандартизировано и эффективное для многих задач пользователя.

Итак, заключение. Мы разговаривали про все эти типы баз данных для того, чтобы научиться принимать решения, какие именно базы выбирать для своего приложения. Давайте, я повторюсь, у нас типичная дилемма из теоремы CAP — это выбор между разделяемостью, целостностью и доступностью. Если мы выбираем разделяемость — то у нас целостность и доступность гарантируют все реализационные базы данных, системы, которые поддерживают транзакции с требованиями ACID, и, в частности, некоторые графовые базы данных, которые тоже реализуют ACID. Там, где у нас небольшие данные, но очень критическая значимость о самих данных, нам данные терять нельзя. Как яркий пример, это биллинговые системы, система с деньгами в Steam платежах, и мы выбираем данное решение там, где мы можем пожертвовать доступностью, но нам нужна высокая согласованность данных. Мы используем большие объемы, у нас изменяющаяся структура, и нам нужна высокая скорость записи, то есть, информация прибывает быстрее, чем нам нужно ее читать, анализировать — то мы выбираем, например, колоночные типы данных, в частности, BigTable, HBase. Мы можем реализовать на них поисковые системы, аналитические какое-то кэширование возможно. И там, где мы можем пожертвовать целостностью, то есть, удовлетвориться слабой целостностью, нам нужно очень большое количество, как записи, так и чтения за единицу времени, то есть очень большие потоки. Мы выбираем разделяемость и доступность, и это такие системы, как системы ключ-значение. Некоторые из колоночных утверждают, что они ставят доступность более приоритетной, чем целостность. В частности, такие системы, которые говорят, что у них Memcached большую часть данных хранит в памяти, но из-за этого, естественно, риск потери при потере питания. Системы, которые могут быть реализованы, это кэширование, всевозможные лайки, всевозможные датчики, в большом количестве, всевозможные логи — выбирайте то, что вам необходимо.

Пользуйтесь, развивайтесь в данном направлении! Удачи!