1. глосарій
2. MapReduce і обробка великомасштабних графів
3. Giraph
4. Як це працює
5. Малюнок 1. Модель програмування BSP
6. Малюнок 2. Голосування вершин
7. Малюнок 3. Приклад BSP - обчислення максимального значення вершини
8. Малюнок 4. Кроки обробки графа на головному вузлі і вузлах-обробниках
9. Giraph в дії
10. Лістинг 1. Алгоритм PageRank в Giraph
11. Лістинг 2. Алгоритм знаходження найкоротшого шляху в Giraph
12. GraphLab
13. Як це працює
14. GraphLab в дії
15. Лістинг 3. Алгоритм PageRank в GraphLab
16. Порівняння Giraph і GraphLab
17. Висновок
18. Ресурси для скачування

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

У математиці та комп'ютерних науках графами називають абстрактні структури даних, що описують структурні відносини між об'єктами. Сьогодні графи широко використовуються для моделювання даних в різних предметних областях, що вимагають з'ясування і визначення правил і схем відносин об'єктів, а також можливих відхилень. Такими предметними областями є 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 виконуваної програми всіх вершин присвоєно статус активних. На кожному супершаге всі активні вершини виконують призначену для користувача функцію compute ().

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

Малюнок 2. Голосування вершин

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

Малюнок 3. Приклад BSP - обчислення максимального значення вершини

На супершаге 1 малюнка 3 кожна вершина повідомляє своє значення своєму сусідові. На супершаге 2 кожна вершина порівнює своє значення з отриманим від сусіда. Якщо отримане значення вище, то вершина змінює своє значення на отримане і повідомляє це нове значення своєму сусідові. Якщо отримане значення нижче, ніж власне значення, то вершина зберігає своє поточне значення і надсилає запит до голосування на останов. Таким чином, на супершаге 2 тільки вершина 1 оновлює своє значення на більш високу (5) і передає його сусідові. Цей процес знову повторюється на супершаге 3 для вершини зі значенням 2, а на супершаге 4 всі вершини беруть участь в голосуванні на останов, і виконання програми завершується.

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

У Giraph реалізована архітектура головного вузла і вузлів-обробників, як показано на малюнку 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 підтримує типові завдання, такі як обчислення діаметра графа, обчислення радіуса кожного вузла і знаходження з'єднаних компонентів шляхом узагальнення множення матриці на вектор.

Ресурси для скачування

Схожі тими

Підпішіть мене на ПОВІДОМЛЕННЯ до коментарів