Решение проблемы с суперузлами

g = TitanFactory.open('/tmp/supernode')
// index configuration snippet goes here for Titan w/ vertex-centric indices
g.createKeyIndex('name',Vertex.class)
g.addVertex([name:'dan'])
  
r = new Random(100)
types = ['work','family','favorite']
(1..i).each{g.addEdge(g.V('name','dan').next(),g.addVertex(),'knows',[type:types.get(r.nextInt(3)),since:it]); stopTx(g,it)}
(1..(i*10)).each{g.addEdge(g.V('name','dan').next(),g.addVertex(),'likes',[rating:r.nextInt(5)]); stopTx(g,it)}
(1..(i*100)).each{g.addEdge(g.V('name','dan').next(),g.addVertex(),'tweets',[time:it]); stopTx(g,it)}

Для 5 экземпляров Titan / BerkeleyDB
с вершинно-ориентированными индексами был проанализирован следующий фрагмент кода. Этот код определяет индексы (см. Конфигурации типов Titan
).

type = g.makeType().name('type').simple().functional(false).dataType(String.class).makePropertyKey()
since = g.makeType().name('since').simple().functional(false).dataType(Integer.class).makePropertyKey()
rating = g.makeType().name('rating').simple().functional(false).dataType(Integer.class).makePropertyKey()
time = g.makeType().name('time').simple().functional(false).dataType(Integer.class).makePropertyKey()
g.makeType().name('knows').primaryKey(type,since).makeEdgeLabel()
g.makeType().name('likes').primaryKey(rating).makeEdgeLabel()
g.makeType().name('tweets').primaryKey(time).makeEdgeLabel()

Далее представлены три обхода, основанные на Дэне. Первый получает всех людей, которых Дэн знает о конкретном случайно выбранном типе (например, члены семьи). Второй возвращает все то, что Дэн высоко оценил (то есть 4 или 5 звезд). Третий возвращает 10 последних твитов Дэна. Наконец, обратите внимание, что Gremlin компилирует каждое выражение в соответствующий вершинный запрос (см. Оптимизацию обхода Gremlin
).

g.V('name','dan').outE('knows').has('type',types.get(r.nextInt(3)).inV
g.V('name','dan').outE('likes').interval('rating',4,6).inV
g.V('name','dan').outE('tweets').has('time',T.gt,(i*100)-10).inV

Приведенные выше обходы выполнялись по 25 раз, при этом база данных перезапускалась после каждого запроса, чтобы продемонстрировать время отклика с холодными
JVM- кэшами. Обратите внимание, что время отклика в оперативной памяти в оперативной памяти показывает схожую картину (хотя и относительно быстрее) Усредненные результаты представлены ниже, где ось Y находится в
логарифмическом масштабе . Зеленый, красный и синий цвета обозначают первый, второй и третий запросы соответственно. Более того, есть светлая и темная версия каждого цвета. Облегченная версия — Titan / BerkeleyDB
без вершинно-ориентированных индексов, а темная версия — Titan / BerkeleyDB
с вершинно-ориентированными индексами.

Возможно, самый впечатляющий результат — поиск 10 самых последних твитов Дэна (синий). С вершинно-ориентированными индексами (темно-синим), когда число твитов Дэна увеличивается до 1 миллиона, время, необходимое для получения первых 10, остается постоянным на уровне около 1,5 миллисекунд. Без индексов этот запрос растет пропорционально объему данных и, в конечном итоге, для его завершения требуется 13 секунд (светло-синий). Это разность времени отклика на 4 порядка для одного и того же набора результатов . Этот пример демонстрирует, насколько полезны вершинно-ориентированные индексы для систем типа потока операций.

На графике справа отображается количество вершин, возвращаемых каждым запросом, для каждого размера графика. Как и ожидалось, число tweetsостается постоянным на уровне 10, в то время как количество извлеченных вершин knowsи likesвершин увеличивается пропорционально растущим графам. Хотя примеры на одном и том же графике (с индексами и без них) возвращают одни и те же данные, доступ к этим данным быстрее с вершинно-ориентированными индексами.

Наконец, Titan также поддерживает составные ключевые индексы. Фрагмент графика строительства код предыдущие правопреемников первичный ключ как typeи sinceв knows-ребра. Таким образом, поиск 10 последних сотрудников Дэна более эффективен, чем получение в память всех сотрудников Дэна и последующая сортировка since. Заинтересованный читатель может исследовать время выполнения таких составных вершинно-ориентированных запросов, дополняя предоставленные фрагменты кода.

Вывод

Суперузел является проблемой, только когда игнорируется различающая информация между ребрами. Если все ребра обрабатываются одинаково, то O(n)требуется линейный поиск по множеству падающих ребер вершины. Однако , когда индексы и порядок сортировки используются, O(log(n))и O(1)поиски могут быть достигнуты. Представленные результаты демонстрируют в 2-5 раз более быстрый поиск для представленных knows/ likesзапросов и до 10 000 раз быстрее для tweetsзапроса при использовании вершинно-ориентированных индексов. Теперь рассмотрим, когда обход больше одного прыжка. Среды выполнения объединяются комбинаторным образом. Составление в 1 миллисекунду против 10 секунд приводит к астрономическим различиям в общем времени прохождения.

Графическая база данных Titan может масштабироваться для поддержки сотен миллиардов ребер (через Apache Cassandra и HBase ). В таких массивных графах часто встречаются вершины с миллионами + инцидентных ребер. В мире больших графических данных важно эффективно хранить и извлекать данные с диска и из памяти. При использовании Titan фильтрация краев опускается до уровня диска, поэтому только необходимые данные фактически извлекаются и заносятся в память. Вершинно-ориентированные запросы и индексы преодолевают проблему суперузлов, интеллектуально используя метку и информацию о свойствах ребер, падающих на вершину.

Связанные материалы

Родригес, М.А., Бройчелер, М., « Титан: рост больших графовых данных », публичная лекция в Jive Software, Пало-Альто, 2012.

Broecheler, M., LaRocque, D., Rodriguez, MA, « Титан предоставляет данные больших графиков в реальном времени », блог Aurelius, август 2012 г.

Авторы