Обработка больших объемов графовых данных: путеводитель по современным технологиям

Узнайте об Apache Giraph, GraphLab и других Open Source-системах для обработки больших данных, структурированных в виде графов

На примере инфраструктур Apache Giraph и GraphLab в этой статье описываются и сравниваются Open Source-решения для обработки больших объемов графовых данных. Структурированные в виде графов данные широко используются в современных приложениях, таких как социальные сети и базы знаний, а для их обработки требуются масштабируемые платформы и параллельные вычислительные архитектуры, умеющие работать с большими объемами данных. Инфраструктура MapReduce, играющая важную роль при анализе больших данных, не является оптимальной моделью программирования для обработки графов. Причины этого вы узнаете из нашей статьи. Также в статье будут рассмотрены находящиеся в разработке системы, призванные помочь в решении задач обработки графов.

Шериф Сакр, старший научный сотрудник Австралийского национального института информационных и коммуникационных технологий, независимый специалист

Photo of Sherif SakrДоктор Шериф Сакр (Sherif Sakr) – старший научный сотрудник группы систем программного обеспечения в Австралийском национальном институте информационных и коммуникационных технологий (NICTA), г. Сидней. Также он совмещает должность старшего преподавателя школы компьютерных и технических наук в Университете Нового Южного Уэльса. В 2007 году Шериф получил докторскую степень в области компьютерных наук в Университете г. Констанца, Германия. Также имеет степени бакалавра и магистра компьютерных наук Каирского университета, Египет. В 2011 году занимал должность выездного научного работника группы Computing Group (XCG) подразделения Microsoft Research в Редмонде, штат Вашингтон. В 2012 году работал в штате исследователей корпорации Alcatel-Lucent Bell Labs.



06.09.2013

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

Глоссарий

Список смежных вершин (Adjacency list): набор неупорядоченных списков в структуре данных графа; для каждой вершины графа имеется один такой список, описывающий набор ее соседей.

Диаметр: максимальное количество вершин, которое необходимо пройти, чтобы добраться из одной вершины в другую (обратные перемещения, обходы и петли не учитываются).

Ребро (Edge): связь, соединяющая две вершины графа.

Натуральный граф: граф, состоящий из множества вершин с несколькими соединениями и нескольких вершин с множеством соединений.

Вершина (Node, или Vertex): один из множества объектов графа.

PageRank ("важность" страницы): алгоритм ссылочного ранжирования, используемый компанией Google в поисковых машинах. Алгоритм применяется к набору элементов Web-графа, связанных гиперссылками, и присваивает каждому элементу числовой "вес", оценивая таким образом относительную важность каждого элемента в общем наборе.

Алгоритм поиска кратчайшего пути: процесс нахождения пути (связи) между двумя вершинами графа, содержащего минимальное количество ребер.

Степень вершины (Vertex degree): количество ребер, которое имеет вершина.

Web-граф: граф, отображающий страницы Всемирной паутины и прямые ссылки между ними.

Web-граф является ярким примером крупномасштабного графа. По оценкам Google общее количество Web-страниц превышает 1 триллион, экспериментальные графы всемирной паутины содержат более 20 миллиардов вершин (страниц) и 160 миллиардов ребер (гиперссылок). Другой пример – графы социальных сетей. По сообщениям Facebook в 2012 году эта социальная сеть состояла более чем из миллиарда пользователей (вершины графа) и 140 миллиардов дружеских отношений (ребра графа). Сеть LinkedIn состоит почти из 8 миллионов вершин и 60 миллионов ребер. При этом графы социальных сетей быстро растут. Так, количество пользователей Facebook увеличилось с 1 миллиона пользователей в 2004 году до 1 миллиарда в 2012. Что касается семантического Web, то онтология DBpedia (проект на основе Wikipedia) в настоящий момент состоит из 3,7 миллиона объектов (вершин) и 400 миллионов фактов (ребер).

Некоторые системы графовых баз данных (особенно Neo4j) поддерживают обработку транзакций в реальном времени (см. раздел Ресурсы). Однако методы доступа к графам в Neo4j не учитывают локальность данных, и при обработке графов используется практически случайный доступ к данным. Для больших графов, которые невозможно хранить в памяти, случайный доступ к диску становится узким местом. Более того, Neo4j является централизованной системой и не обладает той вычислительной мощностью, которую может обеспечить распределенная параллельная система. Для реализации масштабируемой обработки большие графы необходимо разделять и обрабатывать на нескольких узлах.

Инфраструктура MapReduce, разработанная компанией Google, позволяет создавать кластеры из обычных компьютеров и программировать их для обработки больших объемов данных за один проход. В отличие от Neo4j, инфраструктура MapReduce не предназначена для обработки запросов в реальном времени. MapReduce оптимизирована для анализа больших объемов данных, распределенных на сотнях компьютеров. Благодаря своей простоте и масштабируемости, в промышленной и научной областях широко популярна Open Source-инфраструктура Apache Hadoop, предназначенная для выполнения распределенных вычислений при работе с большими объемами данных и построенная на основе принципов MapReduce.

В то же времяHadoop и связанные с ней технологии (например, Pig и Hive) в целом не предназначены для масштабируемой обработки графовых данных. Чтобы приспособить инфраструктуру MapReduce (или Hadoop) под эти цели, было сделано несколько предложений, и эту статью мы начнем с рассмотрения двух из них. Наиболее надежные из всех доступных на сегодняшний день модели программирования, лежащие в основе технологий для крупномасштабной обработки графовых данных, отличаются от моделей на основе MapReduce. В оставшейся части статьи мы подробно рассмотрим и сравним следующие системы:

  • Giraph – распределенная отказоустойчивая система, основанная на модели параллельных вычислений (Bulk Synchronous Parallel) для обработки больших объемов графовых данных с применением алгоритмов параллелизации.
  • GraphLab – основанная на графах высокопроизводительная инфраструктура распределенных вычислений, написанная на C++.

В заключительной части этой статьи я также кратко расскажу о других Open Source-проектах для обработки графовых данных. Предполагается, что читатели знакомы с концепцией и терминологией графов. Для тех, кто не знаком с данной темой, в статье имеется краткий глоссарий.

MapReduce и обработка крупномасштабных графов

Surfer и GBASE

Surfer – это экспериментальный движок для работы с большими объемами графовых данных, предоставляющий в распоряжение программистов две базовых функции: MapReduce и propagation. Подход MapReduce обеспечивает параллельную обработку множества пар ключ/значение. Propagation представляет собой модель итерационных вычислений, в которой информация передается вдоль ребер графов от одной вершины к соседним с ней вершинам. MapReduce хорошо подходит для обработки плоских структур данных (например, задачи с вершинами), тогда как propagation оптимизирована на выполнение задач с ребрами в разделенных графах. Surfer решает проблему нехватки пропускной способности сети путем разделения графов в соответствии с характеристиками распределенной среды Hadoop. В Surfer реализован механизм, который учитывает пропускную способность сети и разделяет графы с учетом ее неоднородных характеристик.

Другим предложенным расширением MapReduce является GBASE, использующий метод хранения графов, называемый блочным сжатием (block compression) и позволяющий эффективно хранить однородные фрагменты графов. Сначала выполняется сжатие всех непустых блоков с помощью стандартного механизма, например, GZip, а затем сжатые блоки сохраняются вместе с определенными метаданными в графовой базе данных.

Ключевой особенностью GBASE является способность объединять запросы к ребрам и вершинам в векторы запросов, а также объединять различные типы операций с графами путем умножения матрицы-вектора на матрицы смежности и инцидентности. Это позволяет GBASE поддерживать различные типы графовых запросов. Запросы делятся на глобальные, требующие обработки всего графа, и целевые, для которых обычно требуется доступ к определенным частям графа. Прежде чем выполнять умножение матрицы-вектора, GBASE выбирает сетки, которые содержат блоки, относящиеся к входным запросам. Таким образом, в задания Hadoop под управлением GBASE попадают только те файлы, которые соответствуют выбранным сеткам.

В модели программирования MapReduce функция Map принимает пары ключ/значение и формирует из них набор промежуточных пар ключ/значение. Все промежуточные значения, связанные с одним и тем же промежуточным ключом, группируются и передаются на обработку функции Reduce. Функция Reduce получает промежуточные ключи с наборами соответствующих им значений и объединяет их.

На уровне реализации промежуточные пары ключ/значения буферизируются в памяти. Периодически буферизованные данные сбрасываются на локальный диск и разбиваются на области соответствующей функцией. Сведения о местоположении этих буферизованных пар на локальном диске передаются специальному главному экземпляру приложения, отвечающему за передачу этих сведений reduce-обработчикам. Когда reduce-обработчик получает данные о местоположении, он считывает буферизованные данные с локальных дисков map-обработчиков. После этого буферизованные данные сортируются по промежуточным ключам таким образом, чтобы все одинаковые ключи оказались сгруппированными. Reduce-обработчик передает ключ и соответствующий набор промежуточных значений на вход пользовательской функции Reduce, результат работы которой добавляется в итоговый результирующий файл для этого раздела reduce.

MapReduce позволяет разработчикам не заботиться об излишних подробностях работы распределенных приложений, например, о распределении и планировании данных или об обеспечении отказоустойчивости. Базовая модель MapReduce не подходит для задач обработки графов, поскольку большинство графовых алгоритмов являются итеративными и в них так или иначе используются переходы по графу. Таким образом, эффективность графовых вычислений сильно зависит от пропускной способности между узлами-обработчиками, поскольку структуры графов передаются по сети после каждой итерации. Например, базовая модель MapReduce не имеет прямой поддержки итеративных приложений для анализа данных. Для реализации такой поддержки от разработчика может потребоваться вручную запустить несколько заданий MapReduce и управлять ими с помощью программы-драйвера. На практике при ручном управлении итеративными приложениями в MapReduce возникают две ключевые проблемы:

  • Даже если большая часть данных не изменяется от итерации к итерации, все данные приходится повторно загружать и обрабатывать на каждой итерации, что приводит к затратам на выполнение операций ввода/вывода, а также к загрузке сети и ресурсов процессора.
  • Условие завершения может включать в себя проверку достижения контрольной точки. Это условие может предполагать выполнение дополнительной задачи MapReduce в каждой итерации, что опять же увеличивает загрузку ресурсов (выполнение дополнительных заданий, чтение дополнительных данных с диска и их передача по сети).

Surfer и GBASE являются примерами расширений для MapReduce, призванных обеспечить более эффективную обработку графов (их техническое описание вы найдете в боковой врезке Surfer и GBASE, а в разделе Ресурсы представлены ссылки на полные описания этих расширений). Однако эти два расширения позволяют лишь частично решить проблему:

  • По сравнению с пользовательскими функциями Hadoop реализация Surfer на основе propagation является более программируемой и эффективной в тех случаях, когда модель доступа целевого приложения совпадает с моделью propagation – в основном, в задачах с ребрами. Когда модель доступа задания не совпадает с моделью propagation (например, в задачах с вершинами), реализация целевого приложения с использованием propagation является довольно нетривиальной задачей.
  • GBASE вряд ли будет интуитивно понятен большинству разработчиков, поскольку им может быть сложно представить обработку графов в терминах матриц. Кроме того, каждая итерация планируется как отдельная задача Hadoop с увеличенной рабочей нагрузкой: когда структура графа считывается с диска, вывод операции map сбрасывается на диск и промежуточный результат записывается в распределенную файловую систему Hadoop (Hadoop Distributed File System, HDFS).

Таким образом, остается насущная потребность в распределенных системах, обеспечивающих эффективную поддержку масштабируемой обработки крупномасштабных графовых данных в кластерах, состоящих из горизонтально масштабируемых серийных компьютеров. Проекты Giraph и GraphLab призваны ответить на эту потребность.


Giraph

В 2010 году компания Google представила систему Pregel – масштабируемую платформу для реализации графовых алгоритмов (см. раздел Ресурсы). В основе Pregel лежит вершинный подход, а сама система основана на модели Bulk Synchronous Parallel (BSP) (см. раздел Ресурсы). В 2012 году был выпущен Apache Giraph – Open Source-проект, унаследовавший концепции Pregel. Giraph может выполняться в качестве обычной задачи Hadoop, использующей кластерную инфраструктуру Hadoop.

Как это работает

Программы обработки графов в Giraph представлены в виде последовательностей итераций, которые называются супершагами. При выполнении супершага для каждой вершины графа запускается определенная пользователем функция, и все функции выполняются параллельно. Пользовательская функция определяет поведение для отдельной вершины V и отдельного супершага S. Функция может считывать сообщения, отправляемые вершине V на супершаге S-1, посылать сообщения другим вершинам (они будут получены на супершаге S+1), а также изменять состояние вершины V и исходящих из нее ребер. Обычно сообщения посылаются вдоль исходящих ребер, но можно отправить сообщение любой вершине с известным идентификатором. Каждый супершаг представляет собой атомную единицу параллельных вычислений. На рисунке 1 изображен механизм выполнения модели программирования BSP.

Рисунок 1. Модель программирования BSP
Рисунок 1. Модель программирования BSP

В этой модели программирования на супершаге 1 выполняемой программы всем вершинам присвоен статус активных. На каждом супершаге все активные вершины выполняют пользовательскую функцию compute().

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

Рисунок 2. Голосование вершин
Рисунок 2. Голосование вершин

На рисунке 3 изображен пример обмена сообщениями между набором вершин графа для определения максимального значения вершины.

Рисунок 3. Пример BSP – вычисление максимального значения вершины
Рисунок 3. Пример BSP – вычисление максимального значения вершины

На супершаге 1 рисунка 3 каждая вершина сообщает свое значение своему соседу. На супершаге 2 каждая вершина сравнивает свое значение с полученным от соседа. Если полученное значение выше, то вершина меняет свое значение на полученное и сообщает это новое значение своему соседу. Если полученное значение ниже, чем собственное значение, то вершина сохраняет свое текущее значение и посылает запрос в голосование на останов. Таким образом, на супершаге 2 только вершина 1 обновляет свое значение на более высокое (5) и передает его соседу. Этот процесс снова повторяется на супершаге 3 для вершины со значением 2, а на супершаге 4 все вершины участвуют в голосовании на останов, и выполнение программы завершается.

Так же, как и инфраструктура Hadoop, Giraph является эффективной, масштабируемой и отказоустойчивой реализацией, работающей в кластерах из тысяч рядовых компьютеров; при этом все специфические детали, относящиеся к продукту, спрятаны за абстракциями. На компьютере, выполняющем вычисления, все вершины и ребра хранятся в памяти, а сеть используется только для передачи сообщений. Эта модель хорошо подходит для распределенных реализаций благодаря тому, что она не использует каких-либо механизмов для определения порядка выполнения внутри супершага, и все взаимодействия выполняются только между супершагом S и супершагом S+1. Во время выполнения программы вершины графа разделяются на секции, которые назначаются отдельным обработчикам. По умолчанию используется механизм хеш-секционирования (hash-partitioning), но можно использовать и собственные алгоритмы секционирования.

В Giraph реализована архитектура главного узла и узлов-обработчиков, как показано на рисунке 4.

Рисунок 4. Шаги обработки графа на главном узле и узлах-обработчиках
Рисунок 4. Шаги обработки графа на главном узле и узлах-обработчиках

Главный узел распределяет секции по узлам-разработчикам, координирует синхронизацию, опрашивает контрольные точки и отслеживает статусы состояния. Как и в Hadoop, для синхронизации в Giraph используется Apache ZooKeeper. Обработчики отвечают за вершины. Узел-обработчик запускает функцию compute() для активных вершин, а также отправляет, получает и присваивает сообщения другим вершинам. Если во время выполнения обработчик получает входные данные, не предназначенные для его вершин, он передает их дальше.

Giraph в действии

Для реализации приложения Giraph следует разрабатывать алгоритм как Vertex. Каждый объект Vertex может являться экземпляром одного или нескольких существующих классов, например, BasicVertex, MutableVertex, EdgeListVertex, HashMapVertex и LongDoubleFloatDoubleVertex. Для чтения графа необходимо определить формат VertexInputFormat. Например, для чтения текстового файла со списками смежных вершин формат может выглядеть следующим образом: (vertex, neighbor1, neighbor2). Кроме того, необходимо определить формат VertexOutputFormat для записи результатов (например, vertex, pageRank).

В листинге 1 приведен код Java, являющийся примером использования функции compute() для реализации алгоритма PageRank.

Листинг 1. Алгоритм PageRank в Giraph
public class SimplePageRankVertex extends Vertex<LongWritable, DoubleWritable, 
                            FloatWritable, DoubleWritable> {
    public void compute(Iterator<DoubleWritable> msgIterator) {
        if (getSuperstep() >= 1) {
            double sum = 0;
            while (msgIterator.hasNext()) {
                sum += msgIterator.next().get();
            }
            setVertexValue(new DoubleWritable((0.15f / getNumVertices()) + 0.85f * sum);
        }
        if (getSuperstep() < 30) {

            long edges = getOutEdgeIterator().size();
            sentMsgToAllEdges(new DoubleWritable(getVertexValue().get() / edges));
        } else {
            voteToHalt();
        }
    }

В листинге 2 приведен пример использования функции compute() для реализации алгоритма нахождения кратчайшего пути.

Листинг 2. Алгоритм нахождения кратчайшего пути в Giraph
public static class ShortestPathVertex extends Vertex<Text, IntWritable, IntWritable> {
     public void compute(Iterator<IntWritable> messages) throws IOException {
      int minDist = isStartVertex() ? 0 : Integer.MAX_VALUE;
      while (messages.hasNext()) {
         IntWritable msg = messages.next();
         if (msg.get() < minDist) {
            minDist = msg.get();
         }
      }
      if (minDist < this.getValue().get()) {
         this.setValue(new IntWritable(minDist));
         for (Edge<Text, IntWritable> e : this.getEdges()) {
            sendMessage(e, new IntWritable(minDist + e.getValue().get()));
         }
      } else {
         voteToHalt();
      }
   }
}

GraphLab

GraphLab – это инфраструктура распределенных вычислений для работы с графами, написанная на C++. Проект начал разрабатываться в 2009 году в Университете Карнеги-Меллона. В GraphLab заложена абстракция параллельного программирования, предназначенная для реализации алгоритмов разреженных итеративных графов с помощью высокоуровневого программируемого интерфейса. Каждый процесс в GraphLab является многопотоковым и полностью задействует все многопроцессорные ресурсы, доступные на узлах современных кластеров. GraphLab поддерживает чтение и запись в файловых системах Posix и HDFS.

Как это работает

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

Абстракция GraphLab состоит из трех основных компонентов: граф данных, функция обновления и операция синхронизации. Граф данных представляет собой изменяемое пользователем программное состояние, которое сохраняет изменяющиеся пользовательские данные и скрывает за собой зависимости разреженных вычислений. Функция обновления выполняет пользовательские вычисления и работает с графом данных, преобразуя данные в небольшие совмещенные контексты, называющиеся областями.

Модель выполнения GraphLab обеспечивает эффективную распределенную работу, снижая требования к разделяемой памяти и позволяя механизму времени выполнения определять наилучший порядок обработки вершин. Например, функция может возвращать вершины в последовательности, минимизирующей количество сетевых взаимодействий или время отклика. Абстракция GraphLab предъявляет лишь единственное требование: в конечном счете должны запускаться все вершины. Исключая потребность в сообщениях, GraphLab изолирует пользовательский алгоритм от перемещения данных, позволяя системе выбирать, когда и каким образом должно изменяться состояние программы. GraphLab позволяет назначать постоянно изменяющиеся данные вершинам и ребрам, благодаря чему разработчик алгоритма может более точно различать данные, общие для всех соседей (данные вершин), и данные, общие только с определенным соседом (данные ребер). Абстракция GraphLab также неявно определяет порядок взаимодействия на этапах gather и scatter (см. раздел GraphLab в действии далее в этой статье), гарантируя, что изменения вершин или данных ребер автоматически становятся видны смежным вершинам. Также важно заметить, что GraphLab не различает направления ребер.

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

GraphLab в действии

Программу GraphLab можно рассматривать как небольшую программу, запускающуюся на вершине графа и имеющую три этапа выполнения:

  1. Этап gather (сбор): на каждом ребре, смежном с ребрами вершины, запускается функция класса вершины gather(), которая возвращает полученные значения.
  2. Этап apply (обработка): значения, собранные на предыдущем этапе, суммируются и передаются функции класса вершины apply().
  3. Этап scatter (распространение): снова на каждом ребре, смежном с ребрами вершины, запускается функция класса вершины scatter().

В листинге 3 приведен пример кода на C++, реализующего алгоритм PageRank в GraphLab.

Листинг 3. Алгоритм PageRank в GraphLab
class pagerank_program :
            public graphlab::ivertex_program<graph_type, double>,
            public graphlab::IS_POD_TYPE {
public:
  // будем выполнять сбор по всем внутренним ребрам
  edge_dir_type gather_edges(icontext_type& context,
                             const vertex_type& vertex) const {
    return graphlab::IN_EDGES;
  }
  // для каждого внутреннего ребра соберем взвешенную сумму ребра
  double gather(icontext_type& context, const vertex_type& vertex,
               edge_type& edge) const {
    return edge.source().data().pagerank / edge.source().num_out_edges();
  }
  
  // Используем общий ранг смежных страниц для обновления текущей страницы 
  void apply(icontext_type& context, vertex_type& vertex,
             const gather_type& total) {
    double newval = total * 0.85 + 0.15;
    vertex.data().pagerank = newval;
  }
  
  // Разделения не требуется. Возвращаем NO_EDGES  
  edge_dir_type scatter_edges(icontext_type& context,
                              const vertex_type& vertex) const {
    return graphlab::NO_EDGES;
  }
};

Сравнение Giraph и GraphLab

Как в Pregel, так и в GraphLab используется модель GAS – gather, apply, scatter (сбор, обработка, распространение), характеризующая три концептуальных этапа программы для работы с вершинами. Однако эти две абстракции отличаются способом сбора и распространения данных. В частности, в Pregel и GraphLab по-разному реализуются программы GAS.В абстракции Pregel этап сбора данных (gather) реализован с помощью объединителей сообщений, а этапы apply и scatter описываются в классе вершины. С другой стороны, в GraphLab ориентированная на работу с вершинами программа полностью видит всю картину соседства, а пользователи могут определять собственные программы на этапах gather и apply. В абстракции GraphLab неявно определяются аспекты взаимодействий на этапах gather и scatter – это гарантирует, что изменения, произошедшие в вершине или данных ребра, автоматически станут видны смежным вершинам.

Другое различие между Pregel и GraphLab заключается в способе реализации динамических вычислений. В GraphLab планирование будущих вычислений отделено от перемещения данных. Так, например, функции обновления в GraphLab должны получить доступ к данным смежных вершин даже если в этих смежных вершинах не было запланировано текущее обновление. Функции обновления в Pregel, наоборот, инициируются сообщениями и могут получить только доступ к данным сообщения; таким образом, представляемая информация ограничена.

И Pregel, и GraphLab используют разделение графов для минимизации взаимодействий и равномерного распределения работы. Тем не менее в случае с натуральными графами обеим абстракциям приходится прибегать к случайному хеш-секционированию, которое может иметь плохую локальность. Хотя Pregel и GraphLab и рассматриваются в числе предвестников новой волны крупномасштабных систем для работы с графами, остается еще много возможностей для улучшения производительности. Серьезные попытки оценить и сравнить сильные и слабые стороны этих систем в различных предметных областях с большими наборами графовых данных еще не предпринимались.


Заключение

В Giraph и GraphLab реализованы новые модели анализа больших графовых данных. Вероятнее всего, эти системы будут продолжать вызывать достаточно серьезный интерес в области обработки больших данных. Тем временем идеи Pregel уже были позаимствованы и реализованы в нескольких других Open Source-проектах, которые могут заинтересовать вас (см. раздел Ресурсы).

  • Apache Hama – как и Giraph, предназначен для работы в инфраструктуре Hadoop. Основная задача этого проекта – общие BSP-вычисления, поэтому он может использоваться не только для работы с графами (например, в него включены алгоритмы преобразования матриц и линейной алгебры). Версия Hama 0.6.1 была выпущена в апреле 2013 г.
  • GoldenOrb – молодой проект (на момент написания этой статьи вышла версия 0.1.1), в котором реализован API-интерфейс Pregel. Требует расширения существующей инфраструктуры Hadoop с помощью дополнительного программного обеспечения.
  • Signal/Collect – использует модель программирования, похожую на модель Pregel, но не зависит от инфраструктуры Hadoop.

Из проектов, не основанных на Pregel, можно выделить PEGASUS – библиотеку для работы с большими графовыми данными, реализованную на базе Hadoop. PEGASUS поддерживает типовые задачи, такие как вычисление диаметра графа, вычисление радиуса каждого узла и нахождение соединенных компонентов путем обобщения умножения матрицы на вектор.

Ресурсы

Научиться

Получить продукты и технологии

  • Загрузите Giraph (EN) с Web-сайта Apache.
  • Загрузите GraphLab (EN).

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Open source
ArticleID=943677
ArticleTitle=Обработка больших объемов графовых данных: путеводитель по современным технологиям
publish-date=09062013