Faunus — это лицензированный механизм анализа распределенных графов Apache 2 , оптимизированный для пакетной обработки графиков, представленных в кластере с несколькими машинами. Faunus делает глобальное сканирование графов эффективным, поскольку он использует последовательные операции чтения / записи на диске в сочетании с различными методами сжатия на диске. Более того, для нечислительных вычислений Фаунус способен линейно масштабироваться перед лицом комбинаторных взрывов . Чтобы обосновать эти вышеупомянутые утверждения, эта статья представляет серию анализов с использованием графического представления Википедии (как это предусмотрено в DBpedia версии 3.7). График знаний DBpedia хранится в 7 m1.xlarge Titan / HBase Amazon EC2 кластер, а затем пакетная обработка с использованием Faunus / Hadoop . В рамках кластера Aurelius Graph Faunus предоставляет аналитику данных Big Graph.
Поглощение DBpedia в Титан
База знаний DBpedia в настоящее время описывает 3,77 миллиона вещей, из которых 2,35 миллиона классифицированы в последовательной онтологии, включая 764 000 человек, 573 000 мест (в том числе 387 000 населенных пунктов), 333 000 творческих работ (в том числе 112 000 музыкальных альбомов, 72 000 фильмов и 18 000 видеоигр). ), 192 000 организаций (в том числе 45 000 компаний и 42 000 учебных заведений), 202 000 видов и 5500 заболеваний. (через DBpedia.org )
DBpedia — это связанная с данными работа, направленная на обеспечение машинно-потребляемого представления Википедии. Н-тройной формат распространен DBpedia может быть легко преобразуются в модель свойства графа поддерживается многими граф вычислительных систем , включая Фаунус. Данные вводятся в кластер Titan / HBase 7 m1.xlarge на Amazon EC2 с помощью оболочки BatchGraph API-интерфейса графа Blueprints .
Фаунус Интеграция с Титаном
На каждом сервере области в кластере Titan / HBase существует Hadoop DataNode и задачи трекера . Faunus использует Hadoop для выполнения первичных представлений запросов / обходов Gremlin , компилируя их в цепочку заданий MapReduce . Далее, SequenceFile формат Hadoop служит промежуточным форматом данных HDFS между заданиями (т.е. этапами обхода). В рамках SequenceFileFaunus используются методы сжатия, такие как кодирование с переменной шириной и схемы сжатия префиксов. чтобы обеспечить небольшой след HDFS. Глобальный анализ графа может выполняться быстрее, чем это возможно из базы данных графа, такой как Titan, поскольку SequenceFile формат не поддерживает структуры данных, необходимые для произвольного доступа для чтения / записи, и, благодаря своей неизменяемости, может быть легче выстроен последовательно на диске.
ubuntu@ip-10-140-13-228:~/faunus$ bin/gremlin.sh
\,,,/
(o o)
-----oOOo-(_)-oOOo-----
gremlin> g = FaunusFactory.open('bin/titan-hbase.properties')
==>faunusgraph[titanhbaseinputformat]
gremlin> g.getProperties()
==>faunus.graph.input.format=com.thinkaurelius.faunus.formats.titan.hbase.TitanHBaseInputFormat
==>faunus.graph.output.format=org.apache.hadoop.mapreduce.lib.output.SequenceFileOutputFormat
==>faunus.sideeffect.output.format=org.apache.hadoop.mapreduce.lib.output.TextOutputFormat
==>faunus.output.location=dbpedia
==>faunus.output.location.overwrite=true
gremlin> g._()
12/11/09 15:17:45 INFO mapreduce.FaunusCompiler: Compiled to 1 MapReduce job(s)
12/11/09 15:17:45 INFO mapreduce.FaunusCompiler: Executing job 1 out of 1: MapSequence[com.thinkaurelius.faunus.mapreduce.transform.IdentityMap.Map]
12/11/09 15:17:50 INFO mapred.JobClient: Running job: job_201211081058_0003
...
gremlin> hdfs.ls()
==>rwxr-xr-x ubuntu supergroup 0 (D) dbpedia
gremlin>
Первым шагом к любому повторному анализу графа с использованием Faunus является получение необходимых данных из исходного местоположения. Для примеров в этом посте источником графа является Titan / HBase. В приведенном выше фрагменте кода оценивается функция идентификации, которая просто отображает представление DBpedia в Titan / HBase в HDFS SequenceFile ( g._()). Этот процесс занимает около 16 минут. На приведенной ниже диаграмме представлено среднее число байтов в минуту, записываемых на диски кластера и с них в течение двух отдельных этапов обработки.
- Слева ввод исходных данных DBpedia в Titan через
BatchGraph. Многочисленные записи в малом объеме происходят в течение длительного периода времени. - Справа — отображение Фаунуса графа Titan DBpedia
SequenceFileв HDFS. Меньшее количество операций чтения / записи большого объема происходит за более короткий период времени.
Сюжет повторяет известный результат, что последовательное чтение с диска почти в 1,5 раза быстрее, чем случайное чтение из памяти, и на 4-5 порядков быстрее, чем случайное чтение с диска (см. «Патологии больших данных» ). Фаунус использует эти особенности иерархии памяти, чтобы обеспечить быстрое полное сканирование графиков.
Потоки данных Фаунуса в HDFS: график и побочный эффект
Фаун имеет два параллельных потока данных: график и побочный эффект . Каждое задание MapReduce считывает график, каким-то образом изменяет его, а затем записывает обратно в HDFS как graph* (или в его окончательное местоположение приемника). Наиболее распространенной мутацией graph* является распространение траверсеров (то есть состояние вычислений). Граф SequenceFile кодирует не только графические данные, но и вычислительные метаданные, например, какие траверсеры и у каких элементов (вершины / ребра). Другие мутации носят более структурный характер, например, обновления свойств и / или создание ребер (например, перезапись графа ). Второй поток данных представляет собой специфическую для шага статистику о графике, который хранится в sideeffect*. Побочные эффекты включают, например:
- агрегаты : счетчики, группы, множества и т. д.
- данные графика : идентификаторы элементов, свойства, метки и т. д.
- Обход данных : перечисление путей.
- деривации : функциональные преобразования графовых данных.
gremlin> g.getProperties()
==>faunus.graph.input.format=org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat
==>faunus.input.location=dbpedia/job-0
==>faunus.graph.output.format=com.thinkaurelius.faunus.formats.noop.NoOpOutputFormat
==>faunus.sideeffect.output.format=org.apache.hadoop.mapreduce.lib.output.TextOutputFormat
==>faunus.output.location=output
==>faunus.output.location.overwrite=true
gremlin> hdfs.ls('dbpedia/job-0')
==>rw-r--r-- ubuntu supergroup 426590846 graph-m-00000
==>rw-r--r-- ubuntu supergroup 160159134 graph-m-00001
...
gremlin> g.E.label.groupCount()
...
gremlin> hdfs.ls('output/job-0')
==>rw-r--r-- ubuntu supergroup 37 sideeffect-r-00000
==>rw-r--r-- ubuntu supergroup 18 sideeffect-r-00001
...
gremlin> hdfs.head('output/job-0')
==>deathplace 144374
==>hasBroader 1463237
==>birthplace 561837
==>page 8824974
==>primarytopic 8824974
==>subject 13610094
==>wikipageredirects 5074113
==>wikiPageExternalLink 6319697
==>wikipagedisambiguates 1004742
==>hasRelated 28748
==>wikipagewikilink 145877010
Механика обхода Фаунуса
Важно понимать, как Фаун хранит вычисления в SequenceFile. Когда шаг g.V оценивается, на каждую вершину графа помещается один обходчик (длинное значение 1). Когда count() вычисляется, число траверсеров в графе суммируется и возвращается. Аналогичный процесс происходит для g.E сохранения того, что к каждому ребру на графике добавляется отдельный обходчик.
gremlin> g.V.count() ==>30962172 gremlin> g.E.count() ==>191733800
Если требуется количество траверсеров в конкретном элементе (т. Е. Количество — выше) в отличие от самих конкретных экземпляров траверсера (и их соответствующих историй пути — ниже), то время, необходимое для вычисления комбинаторных вычислений, может линейно масштабироваться с количество итераций MapReduce. Приводимые ниже обходы Фаунуса / Гремлина подсчитывают (не перечисляют) количество 0-, 1-, 2-, 3-, 4- и 5-ступенчатых путей в графе DBpedia. Обратите внимание, что время выполнения масштабируется линейно приблизительно за 15 минут на шаг обхода, даже если результаты составляются экспоненциально, так что в последнем примере определено, что в графе DBpedia имеется 251 квадриллион длиной 5 путей.
gremlin> g.V.count() // 2.5 minutes ==>30962172 gremlin> g.V.out.count() // 17 minutes ==>191733800 gremlin> g.V.out.out.count() // 35 minutes ==>27327666320 gremlin> g.V.out.out.out.count() // 50 minutes ==>5429258407462 gremlin> g.V.out.out.out.out.count() // 70 minutes ==>1148261617434916 gremlin> g.V.out.out.out.out.out.count() // 85 minutes ==>251818304970074185
Хотя этот результат может показаться странным, существует возможность аналитической оценки эмпирически рассчитанного количества путей. Средняя степень вершин в графе равна 6, но общее количество 5-шаговых путей намного более чувствительно к связности вершин высокой степени. При анализе только самых верхних 25% наиболее соединенных вершин — 200k вершин, показанных красным цветом под синей линией, — средняя степень составляет 260. Это дает приблизительное число путей:
Это число соответствует фактическому количеству 5 путей, рассчитанному Фаунусом. Как вычисленные, так и аналитические результаты демонстрируют особенность естественных графов, о которых должны знать все аналитики графов — комбинаторные взрывы имеются в большом количестве (см. Loopy Lattices ).
gremlin> g.V.sideEffect('{it.outDegree = it.outE.count()}').outDegree.groupCount()
12/11/11 18:36:16 INFO mapreduce.FaunusCompiler: Compiled to 1 MapReduce job(s)
...
==>1001 6
==>101 4547
==>1016 10
==>1022 5
==>1037 9
gremlin>
Вывод
Faunus — это свободно распространяемый, распространяемый по Apache 2 лицензированный механизм анализа графов. В настоящее время он находится в стадии 0.1-альфа с выпуском 0.1, запланированным на зиму 2012/2013. Фаунус является одним из компонентов OLAP в кластере графов Аурелия .
В мире графических вычислений ни одно решение не сможет удовлетворить все вычислительные потребности. Titan поддерживает сценарии использования, в которых тысячи одновременно работающих пользователей выполняют короткие эгоцентрические обходы на одном крупномасштабном графике. Faunus, с другой стороны, поддерживает глобальные обходы графа в таких случаях использования, как автономная обработка данных и / или ориентированная на производство пакетная обработка. Наконец, Fulgora будет служить графическим процессором в памяти для алгоритмов многопоточного итеративного графа и машинного обучения . Вместе Aurelius Graph Cluster предоставляет комплексное решение для решения различных задач графического вычисления.
Связанные материалы
Джейкобс А., « Патологии больших данных », сообщения ACM, 7 (6), июль 2009 г.
Нортон Б., Родригес М.А., « Петлевые решетки », блог Аврелия, апрель 2012 г.
Хо, Р., « Обработка графиков в Map Reduce », блог Pragmatic Programming Techniques, июль 2010 г.
Лин, Дж., Schatz, М., « Шаблоны проектирования для эффективных алгоритмов графов в MapReduce », Mining and Learning with Graphs Proceedings, 2010.