Pregel¶

Pregel — это вычислительная модель, предназначенная для обработки крупномасштабных графов, основанная на парадигме «вершинных программ» (vertex-centric programming) и реализующая подход Bulk Synchronous Parallel (BSP). Модель была разработана в компании Google и впервые описана в одноимённой научной статье, опубликованной в 2010 году. Pregel позволяет эффективно выполнять итеративные алгоритмы на графах с миллиардами вершин и рёбер, распределяя вычисления на кластере из тысяч машин. Название модели происходит от реки Прегель (ныне Преголя), протекающей через Калининград (бывший Кёнигсберг), что отсылает к знаменитой задаче о Кёнигсбергских мостах, решённой Леонардом Эйлером и положившей начало теории графов.

¶Основные принципы

¶Модель «вершинных программ» (Vertex-Centric)

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

• читать и изменять состояние вершины;
• отправлять сообщения другим вершинам (по идентификаторам);
• получать сообщения, отправленные на предыдущей итерации;
• изменять топологию графа (добавлять или удалять вершины и рёбра).

Такой подход упрощает реализацию многих графовых алгоритмов, таких как поиск кратчайшего пути, PageRank, кластеризация и анализ связности.

¶Парадигма BSP (Bulk Synchronous Parallel)

Вычисления в Pregel организованы в виде последовательности итераций, называемых супершагами (supersteps). Каждый супершаг состоит из трёх фаз:

1. Вычисления: Каждая вершина выполняет свою функцию. В этой фазе вершина обрабатывает сообщения, полученные на предыдущем супершаге, обновляет своё состояние и генерирует новые сообщения.
2. Коммуникация: Все сообщения, отправленные вершинами, доставляются адресатам. Эта фаза является синхронной — ни одна вершина не может начать следующий супершаг, пока не будут доставлены все сообщения текущего.
3. Синхронизация: Система ожидает завершения всех вычислений и коммуникаций текущего супершага. После этого начинается следующий супершаг.

Синхронная модель BSP упрощает разработку и отладку, так как гарантирует детерминированность выполнения при одинаковых входных данных и порядке обработки сообщений. Вершина может «голосовать за остановку» (vote to halt), переставая участвовать в дальнейших супершагах, пока не получит новое сообщение.

¶Архитектура и реализация

¶Распределённое выполнение

Pregel спроектирован для работы на кластерах, состоящих из множества машин (узлов). Граф разбивается на разделы (partitions), которые распределяются между узлами. Каждый узел отвечает за выполнение программы на вершинах своего раздела. Для обеспечения отказоустойчивости система периодически сохраняет состояние графа (чекпоинты) на распределённую файловую систему (например, Google File System). В случае сбоя узла вычисления могут быть восстановлены с последнего чекпоинта.

¶Агрегаторы (Aggregators)

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

¶Комбинаторы (Combiners)

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

¶Применение

Модель Pregel и её реализации (как открытые, так и коммерческие) широко применяются для решения задач, связанных с анализом больших графов:

• Поисковые системы: Вычисление PageRank и других метрик ранжирования веб-страниц.
• Социальные сети: Анализ социальных связей, поиск сообществ, рекомендация друзей и контента.
• Логистика и транспорт: Поиск кратчайших путей в дорожных сетях, оптимизация маршрутов.
• Биоинформатика: Анализ белковых взаимодействий и метаболических путей.
• Финансовый сектор: Выявление мошеннических схем и анализ транзакционных графов.

¶Реализации и влияние

Хотя внутренняя реализация Pregel в Google является проприетарной, её идеи оказали огромное влияние на развитие систем обработки графов. Было создано несколько открытых и коммерческих реализаций, основанных на той же модели:

• Apache Giraph: Открытая реализация Pregel, работающая поверх Apache Hadoop. Используется в Facebook (организация признана экстремистской и запрещена в РФ) для анализа социального графа.
• Apache Hama: Ещё одна открытая реализация BSP-модели, поддерживающая не только графовые, но и матричные вычисления.
• GraphX: Компонент Apache Spark, предоставляющий API для обработки графов, вдохновлённый Pregel, но интегрированный с общей моделью данных Spark RDD.
• Pregel+: Улучшенная версия модели, разработанная в Китайском университете Гонконга, с поддержкой динамических графов и более эффективной обработкой.
• Pregelix: Реализация, ориентированная на гибридные вычисления (графовые и реляционные).

Модель Pregel также повлияла на развитие стандартов и языков для обработки графов, таких как Gremlin и Cypher.

¶Критика и ограничения

Несмотря на свою популярность, модель Pregel имеет ряд ограничений:

• Синхронность: Синхронная модель BSP может быть неэффективной для алгоритмов с сильно различающимся временем выполнения на разных вершинах, так как все вершины вынуждены ждать самую медленную.
• Сложность реализации некоторых алгоритмов: Алгоритмы, требующие глобального состояния или сложной координации между вершинами, могут быть труднореализуемы в рамках простой модели «отправки сообщений».
• Затраты на коммуникацию: Для графов с высокой степенью вершин (например, в социальных сетях) объём передаваемых сообщений может быть очень большим, что приводит к узким местам в сети.
• Память: Каждая вершина должна хранить своё состояние и очередь входящих сообщений, что может быть проблематично для графов с миллиардами вершин.

В ответ на эти ограничения были разработаны более гибкие модели, такие как GraphLab (асинхронная модель) и PowerGraph (GAS — Gather-Apply-Scatter), которые решают часть проблем, связанных с обработкой графов с неравномерным распределением степеней вершин.

¶Источники

• Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. "Pregel: a system for large-scale graph processing." Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.
• Apache Giraph Documentation.
• Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. "Spark: Cluster Computing with Working Sets." HotCloud'10.