В рамках моей недавней работы над Open Credo я участвовал в проекте, который использовал базу данных Neo4J Graph для хранения приложений.
Neo4J — одна из первых графовых баз данных, появившихся на мировом рынке. Будучи открытым исходным кодом, он не только обладает мощью и простотой поддержки графической модели данных, но и является хорошим выбором для готовой графической базы данных.
Тем не менее, была одна область, в которой я изо всех сил пытался получить достаточно хорошую производительность от Neo4j — супер узлы.
Супер узлы представляют узлы с плотными отношениями (100 КБ и более), которые быстро становятся узкими местами в алгоритмах обхода графа при использовании Neo4J. Я пробовал много разных подходов, чтобы обойти эту проблему, но введение автоматической индексации в Neo4j 1.4 дало мне идею, с которой я добился успеха. Подход, который я выбрал, состоит в том, чтобы попытаться получить отношения суперузлов, используя индексы Lucene вместо стандартных API Neo. В этой записи я поделюсь тем, чего мне удалось достичь и как.
Для начала давайте сгенерируем примерный граф с суперузлами. Вот количество сгенерированных данных:
- 5 узлов, представляющих города / поселки (например, «Лондон», «Манчестер», «Эдинбург», «Кембридж» и «Оксфорд»)
- Каждый городской узел имеет отношение «IS_IN» к узлу страны UK (каждый город связан с узлом страны с отношением IS_IN, и у нас есть только один узел страны — Великобритания)
- У нас есть 100 000 пользователей, и каждый из них имеет отношение «HAS_VISITED» к каждому из пяти городов. Я знаю, что это маловероятный сценарий, но в большом наборе данных (скажем, среди всех пользователей Facebook) вы найдете более 5 городов, которые посетили более 100 000 пользователей.
- Это в общей сложности 100 006 узлов (100 000 пользователей + 5 городов + 1 узел страны в Великобритании) и 500 005 отношений (100 000 пользователей-HAS) _VISITED-5 городов + 5 городов IS_IN UK)
Это не большой объем данных, но достаточно большой для начала.
Допустим, мы хотим загрузить отношения «IS_IN» для данного узла города. Это довольно просто сделать с помощью Neo API:
Листинг 1: Итерация через связи узлов с использованием стандартного API Neo4j
Iterable relationships =
city.getRelationships(DynamicRelationshipType.withName("IS_IN"));
for (Relationship r : relationships) {
cnt++;
}
Сколько времени это займет для одного городского узла? Я запускал этот код 10 раз (для учета попаданий в кэш при последующих запусках), и вот результаты:
Таблица 1: Производительность выборки отношений с суперузла с отношениями 100K, используя стандартный API Neo4J
При первом извлечении отношения это занимает 1,6 секунды. Каждый последующий запрос занимает менее 1 мс! Мы можем поблагодарить механизм кэширования и отображения памяти Neo4j за это увеличение скорости (или разработчиков, которые реализовали его, если быть более точным).
Но я все еще беспокоился о производительности первого заезда. Для одной выбранной взаимосвязи (есть только одна взаимосвязь «IS_IN» для каждого городского узла), 1,6 секунды кажется много. Причина низкой производительности заключается в том, что городской узел имеет в общей сложности 100 001 связь, и только один из них имеет тип IS_IN. Чтобы выбрать правильный вариант, движок Neo4j должен будет просмотреть все отношения, затем сравнить их типы и вернуть только те, которые соответствуют запрошенному типу.
Хотя система будет работать хорошо, когда кеш прогревается, это может вызвать проблемы, если вы часто обращаетесь к «холодным» частям графика. Хотя Neo4j пытается хранить большую часть данных в кэш-памяти или отображенной памяти, это не всегда может быть достигнуто. Когда график слишком велик, чтобы полностью поместиться. Если супер-узлы не могут постоянно храниться в памяти (либо потому, что их слишком много, либо доступ к более частым данным занимает всю доступную кэш / отображенную память), тогда производительность будет отрицательно сказываться.
С точки зрения больших систем данных, 100 тыс. Связей на узел — это не так уж много. Что произойдет, если у вас есть супер узлы с отношениями 1M? Посмотрим сами!
Я собираюсь сохранить 5 городских узлов на графике, каждый из которых имеет одну связь IS_IN со страновым узлом Великобритании. Но я увеличу количество пользователей до 1 000 000. И предположим, что каждый пользователь посетил каждый из 5 городов. Таким образом, у нас будет 1 000 001 отношение на узел города. Я повторил код из листинга 1, чтобы получить отношения типа IS_IN (будет только один), и повторил его 10 раз, чтобы увидеть результаты, когда кэш включится. Таблица 2 показывает результаты.
Таблица 2: Производительность выборки отношений с супер-узла с отношениями 1M с использованием стандартного API Neo4J
Первый запуск теперь близок к 5 секундам, а последующие вызовы, которые попадают в кеш, по-прежнему занимают менее 1 мс!
Ухудшение производительности не является линейным (при увеличении входного сигнала в 10 раз время увеличилось только в 3 раза), и это хорошо. Когда это тепло, система работает хорошо с ответами sub-ms.
Но иногда наши требования не учитывают время прогрева. Если у вас есть обход, который должен пройти через 10 суперузлов, вы можете приблизиться к 1-минутному обходу. Если у вас есть пакетное задание, которое должно обработать 100 тыс. Таких обходов, а набор данных таков, что он не может храниться в памяти все время, это может занять 100 тыс. Минут или больше, чем месяц! Что мы можем сделать, чтобы улучшить это?
Одним из вариантов может быть развертывание кластера HA Neo4j и вычисление разбиения по всему кластеру. Я не пробовал это, и в зависимости от размера вашего набора данных и требований это может быть жизнеспособным решением.
Но мы собираемся сконцентрироваться на более простом решении: как мы можем получить только отношения требуемого типа, игнорируя огромное количество отношений других типов, которые нам не интересны. Мы собираемся использовать встроенный Neo4j. в поддержке индексации Lucene для получения необходимых отношений непосредственно из индекса. Чтобы сделать это, нам нужно будет добавлять тип отношения в индекс при каждом создании нового отношения.
Во-первых, мы собираемся настроить возможность автоматической индексации отношений Neo4J, добавив следующие свойства в
neo4j.properties
файл, как показано в листинге 2.
Листинг 2. Настройка автоматической индексации отношений в файле neo4j.properties
relationship_auto_indexing=true relationship_keys_indexable=type
Мы включаем автоматическое индексирование
отношений
с помощью Relationship_auto_indexing , свойство, и мы собираемся сказать Neo отслеживать и индексировать тип имени свойства каждого созданного отношения.
Мы должны внести небольшое изменение в наш генератор данных и установить
свойство type
для каждого отношения, которое мы создаем:
Листинг 3: Создание отношения с именем типа в качестве свойства, чтобы включить автоматическую индексацию отношений
DynamicRelationshipType relType = DynamicRelationshipType.withName("IS_IN");
Relationship isA = city.createRelationshipTo(ukCountry, relType);
isA.setProperty("type", relType.name());
DynamicRelationshipType hasVisited = DynamicRelationshipType.withName("HAS_VISITED");
Relationship rel = user.createRelationshipTo(city, hasVisited);
rel.setProperty("type", hasVisited.name());
Вставив данные для всех пользователей 1M, мы собираемся извлечь отношения IS_IN для одного узла города, используя автоматический индекс:
Листинг 4: Создание отношения с именем типа в качестве свойства, чтобы включить автоматическую индексацию отношений
Iterable relationships = autoIndex.query("type", "IS_IN", city, null);
for (Relationship r : relationships) {
cnt++;
}
Теперь давайте измерим, сколько времени занимает загрузка отношений из индекса — как и в предыдущих запусках, мы будем извлекать отношения 10 раз, чтобы позволить кэшу заполниться. Таблица 3 показывает результаты:
Таблица 3: Производительность выборки отношений из суперузла с отношениями 1M, используя автоматическую индексацию отношений
Благодаря индексу Lucene «холодная» выборка заняла всего 12 мс в этом пробеге. Последующие вызовы все еще очень быстрые, хотя и немного медленнее, чем раньше, как сейчас мы наблюдаем несколько раз в 1 мс среди большинства вызовов мс.
В предыдущем примере мы увидели, как мы можем обеспечить более эффективный поиск отношений определенного типа. В тех случаях, когда мы заинтересованы в операциях обхода, для обеспечения того, чтобы мы извлекали только те отношения, которые нам интересны, необходимо использовать пользовательский
RelationshipExpander
. Код в листинге 5 показывает реализацию расширителя отношений, который гарантирует, что мы используем индекс Lucene для получения отношений указанного типа.
Листинг 5: Реализация IndexedRelationshipExpander, которая использует индекс Lucene для извлечения отношений для узла
public class IndexedRelationshipExpander implements RelationshipExpander{
private final GraphDatabaseService graphDatabaseService;
private final RelationshipType relationshipType;
private final Direction direction;
private IndexedRelationshipExpander(GraphDatabaseService graphDatabaseService, RelationshipType relationshipType, Direction direction) {
this.relationshipType = relationshipType;
this.graphDatabaseService = graphDatabaseService;
this.direction = direction;
}
public static IndexedRelationshipExpander create(GraphDatabaseService graphDatabaseService, RelationshipType relationshipType, Direction direction){
return new IndexedRelationshipExpander(graphDatabaseService, relationshipType, direction); #1
}
@Override
public Iterable expand(Node node) {
Iterable hits = null;
ReadableRelationshipIndex autoIndex = this.graphDatabaseService.index().getRelationshipAutoIndexer().getAutoIndex();
switch (this.direction){
case OUTGOING:
hits = autoIndex.query("type", this.relationshipType.name(), node, null); #2
break;
case INCOMING:
hits = autoIndex.query("type", this.relationshipType.name(), null, node); #3
break;
case BOTH:
IndexHits out = autoIndex.query("type", this.relationshipType.name(), node, null);
IndexHits in = autoIndex.query("type", this.relationshipType.name(), null, node);
hits = Iterables.concat(out, in); #4
break;
}
return hits;
}
@Override
public RelationshipExpander reversed() {
return new IndexedRelationshipExpander(graphDatabaseService, relationshipType, direction.reverse());
}
}
Для доступа к индексу
IndexedRelationshipExpander
требуется ссылка на
GraphDatabaseService
. Кроме того, нам нужно
указать
интересующий нас тип и направление отношений для IndexedRelationshipExpander (# 1). Реализация метода expand () просто проверяет направление отношения и запрашивает авто-индекс отношения (# 2, # 3 — разница только в аргументах startNode / endNode). Там, где нам нужны отношения в обоих направлениях, мы должны выполнить два отдельных поиска, один для входящих и один для исходящих отношений. Затем нам нужно объединить два результата, в примере это делается с помощью библиотеки Google Guava (# 4)
И это все. Теперь мы можем пройти отношения указанного типа, используя новый расширитель отношений:
Листинг 6: Использование пользовательского IndexedRelationshipExpander в Neo4J Traversal API
RelationshipType relationshiptype = DynamicRelationshipType.withName("IS_IN");
Direction direction = Direction.OUTGOING;
TraversalDescription traversal = Traversal.description().
evaluator(Evaluators.atDepth(1)).expand(IndexedRelationhipExpande.create(this.embeddedGraphDatabase, relationshipType, direction));
traversal.traverse(city);
Обратите внимание, что у вас должно быть
свойство индексированного типа
для каждого отношения, которое содержит имя типа отношения, чтобы IndexedRelationshipExpander работал правильно.
Учитывая базовую реализацию
RelationshipExpander
, его легко адаптировать под ваши конкретные требования. Например, вы можете индексировать свойство creation_date для каждого отношения, а затем проходить только отношения, созданные после указанной даты. Вы можете включить любое индексированное свойство отношения при создании запроса Lucene и реализовать его в
методе RelationshipExpander.expand ()
.
Теперь мы увидели, как мы можем использовать индексирование Lucene для быстрой выборки и прохождения небольшого подмножества отношений на супер узле. Однако эффективность этого подхода зависит от того, заинтересованы ли вы только в небольшой части отношений. В следующей записи блога мы рассмотрим, как мы можем эффективно загружать большее количество отношений из суперузла.
nb Я использовал релиз Neo4j 1.4 для запуска примеров, описанных в этом блоге. Описанный расширитель индексированных отношений не будет работать с более ранней версией Neo4J, поскольку он зависит от возможностей автоматической индексации на Neo4j. Все тесты выполняются на MacBook Pro 2,76 ГГц с 8 ГБ оперативной памяти. Размер кучи Java был установлен на 2 ГБ, и использовались стандартные настройки отображения Neo4J.
nbb У некоторых ребят из Neo4J произошли некоторые улучшения в обходе супер-узлов, их можно найти здесь https://github.com/peterneubauer/graph-collections . Как только я опробую новые функции, я сообщу вам об этом в одной из следующих записей в блоге.
ПРИМЕЧАНИЕ. Вторая часть этой записи блога, в которой рассматривается выборка большого количества связей из суперузла, теперь доступна здесь.