Для получения дополнительных галантерейных товаров, пожалуйста, обратите внимание на публичный аккаунт WeChat «AI Frontline» (ID: ai-front)
В настоящее время графические данные (далее именуемые «графические данные») используются повсеместно. Такие компании, как Facebook, Twitter и Pinterest, увидели и максимально использовали возможности этих взаимосвязанных данных. Это напрямую привело к повышенному вниманию к решениям для графических данных, и разнообразие решений растет день ото дня.
Внедрение системы загружаемых модулей Redis позволило нам осознать огромный потенциал внедрения графовых структур данных в набор инструментов Redis. Redis реализован на собственном языке C и ориентирован на предоставление высокопроизводительных функций. Теперь, разрабатывая Redis, мы добавили в него новую возможность графовой базы данных. RedisGraph доступен на GitHub как проект с открытым исходным кодом.
В этой статье будут представлены некоторые внутренние устройства и функции RedisGraph, а также продемонстрируются его текущие возможности.
RedisGraph — это графовая база данных, основанная на новом дизайне и реализации Redis. Он использует новый API модулей Redis, расширяя Redis и предоставляя некоторые новые команды и функции. Его основные функции включают в себя: простое и быстрое индексирование и запросы, хранение данных в памяти, использование настраиваемых структур данных с эффективным использованием памяти, сохранение данных на диске, наборы результатов в виде таблиц данных, простая и расширенная поддержка. Используемый язык запросов графа Cypher , а также фильтрация, агрегация и сортировка данных и т.д.
Чтобы представить некоторые ключевые функции RedisGraph, давайте приведем пример, основанный на инструменте redis-cli.
Сущности обычно представляются в виде узлов на графе. В этом примере создается мелкомасштабный график с актерами и фильмами в качестве сущностей с отношением «действующая роль», соединяющим актеров и фильмы, участвовавшие в фильме. Формат инструкции CREATE, выдаваемой с помощью команды GRAPH.QUERY, выглядит следующим образом и реализует добавление новых сущностей и связей в граф.
Следующая команда создает график:
RedisGraph реализует подмножество языка запросов графа openCypher. Хотя поддерживаются лишь некоторые возможности языка, их вполне достаточно для извлечения полезной информации из графа. Формат команды для выполнения запроса с помощью команды GRAPH.QUERY:
GRAPH.QUERY <graph_id> <query>Ниже мы выполняем серию запросов к созданным данным кинодиаграммы.
Среди них первая строка представляет собой информацию заголовка результирующего набора, а имя каждого столбца соответствует оператору RETURN. Вторая строка содержит результаты запроса.
Второй запрос — выяснить, в скольких фильмах снимался каждый актер.
Различные базы данных графов могут использовать разные структуры для представления графов. Некоторые используют список смежности, а некоторые используют матрицу смежности. Каждая структура представления имеет свои преимущества и недостатки. Ключевым моментом для RedisGraph является предоставление структуры данных, поддерживающей быстрый поиск по графу. Мы используем структуру под названием «Гексастор» для хранения всех взаимосвязей в графе.
Структура Hexastore состоит из ряда троек. Среди них каждая тройка состоит из следующих трех частей:
Субъект (Тема);
Предикат;
цель (объект).
Субъект представляет исходный узел, предикат представляет отношение, а цель представляет узел назначения. Для каждого отношения в графе Hexastore будет хранить все шесть возможных перестановок между исходными узлами, ребрами отношений и узлами назначения. В качестве примера возьмем следующие отношения:
(Aldis_Hodge)-[act]->(Straight_Outta_Compton)где Aldis_Hodge — исходный узел, act — отношение, а Straight_Outta_Compton — целевой узел.
Шесть возможных перестановок этого отношения следующие:
SPO:Aldis_Hodge:act:Straight_Outta_Compton
SOP:Aldis_Hodge:Straight_Outta_Compton:act
POS:act:Straight_Outta_Compton:Aldis_Hodge
PSO:act:Aldis_Hodge:Straight_Outta_Compton
OPS:Straight_Outta_Compton:act:Aldis_Hodge
OSP:Straight_Outta_Compton:Aldis_Hodge:actПосле создания Hexastore мы можем легко реализовать поиск по графу. Например, если вы хотите найти актеров в фильме «Прямиком из Комптона», вы можете сделать это, выполнив поиск в Hexastore всех строк, содержащих префикс OPS:Straight_Outta_Compton:act:*.
Если вы хотите найти все фильмы Aldis Hodge, вы можете реализовать строку, содержащую все префикс SPO: ALDIS_HODGE: ACT: *.
Хотя Hexastore может интенсивно использовать память, поскольку каждое отношение представлено в виде шести троек, такая тройная структура данных не только поддерживает быстрый поиск, но и эффективно использует память, поскольку она не генерирует повторно существующий строковый префикс.
Некоторые языки графовых запросов уже существуют, и мы не хотим изобретать велосипед и реализовывать собственный язык. Поэтому мы решили реализовать подмножество openCyper, наиболее широко используемого языка запросов к графам. Хотя методы создания парсера языка, предоставляемые проектом Open-Cypher, просты в использовании, мы решили создать свой собственный парсер. Анализатор использует Lex в качестве токенизатора и Lemon для создания целевого анализатора C.
Как упоминалось выше, в настоящее время мы поддерживаем только часть языка. Мы продолжим добавлять новые возможности и расширять язык.
Ниже мы представляем этапы работы модулей в RedisGraph при выполнении запросов. Возьмем, к примеру, следующий запрос, который находит всех актеров старше 30 лет, снимавшихся вместе с Элдисом Ходжем:
RedisGraph будет разбирать запрос, построить абстрактное синтаксическое дерево, построить план выполнения (состоящий из операций по сканированию тегов, операций фильтра, операций развертывания, расширить в операции и т. Д.), Выполните план и добавить соответствующие атрибуты объекта на набор результатов Отказ
Для данного допустимого запроса анализатор создаст абстрактное синтаксическое дерево. Следующие шесть типов операторов будут генерировать соответствующие основные узлы в абстрактном синтаксическом дереве:
MATCH
CREATE
DELETE
WHERE
RETURN
ORDER
Генерация абстрактных синтаксических деревьев — это общий способ описания и структурирования языков.
Запрос отфильтровывает сущности, создавая предикаты. Возьмем приведенный выше запрос в качестве примера, который должен отфильтровать актеров моложе 30 лет. В запросе вы можете использовать ключевые слова, такие как ИЛИ, И и т. д., чтобы комбинировать предикаты для создания детальных условий. Дерево фильтров строится из оператора WHERE во время выполнения. Каждый узел в дереве фильтров может представлять условие (например, A>B) или операцию (И или ИЛИ). Объекты-кандидаты будут оцениваться с помощью дерева фильтров.
Оператор MATCH описывает взаимосвязь между запрошенными объектами (то есть узлами). Узлы могут иметь псевдонимы для поддержки ссылок (инструкции WHERE, RETURN) позже в жизненном цикле выполнения запроса. В конечном итоге, однако, всем узлам также должен быть присвоен идентификатор. Процесс присвоения идентификатора узлу называется фазой поиска.
Фаза поиска запрашивает Hexastore на основе оператора MATCH, чтобы найти все идентификаторы. Взяв приведенный выше запрос в качестве примера, этап поиска начинается с поиска фильма, в котором участвует Элдис Ходж. Расширьте поиск для каждого найденного фильма, чтобы найти актеров в текущем фильме.
Такой процесс поиска можно рассматривать как итеративный процесс обхода графа. Этот итеративный процесс обнаруживает новый идентификатор на каждом этапе. После присвоения узлу идентификатора можно подтвердить, что текущий объект подходит для оператора фильтра. На этом этапе атрибуты запроса, указанные в операторе RETURN, могут быть извлечены, а новые записи добавлены в окончательный набор результатов.
Сложность вставки новой связи составляет O(1), а RedisGraph может создать 100 000 новых связей за 1 секунду. На другом базовом оборудовании результаты тестирования могут различаться.
Производительность извлечения данных полностью зависит от размера графа и типа выполняемого запроса. Для мелкомасштабного графа, скажем, ~1000 объектов, 2500 ребер, RedisGraph может выполнять ~65 000 запросов друзей друзей (FOAF) в секунду.
Следует отметить, что мы не индексируем объекты, кроме Hexastore. В будущем мы реализуем индексирование сущностей, что значительно сократит время выполнения запросов.
Redis-Graph выпускается под лицензией AGPL-3.0.
Проект RedisGraph, несмотря на его недавний запуск, уже доступен в качестве альтернативы графовым базам данных. RedisGraph поддерживает подмножество операций для анализа и изучения графических данных. В качестве модуля Redis все клиенты Redis могут использовать функциональные возможности модуля без каких-либо настроек. Мы рассматриваем возможность дальнейшего улучшения и дальнейшего расширения RedisGraph с помощью сообщества открытого исходного кода.
Посмотреть исходный английский текст:
http://redisgraph.io/design/
Для получения дополнительных галантерейных товаров, пожалуйста, обратите внимание на публичный аккаунт WeChat «AI Frontline» (ID: ai-front)