Как обрабатывать огромные графы: BFS в Python и PySpark GraphFrames

Почему BFS на словарях Python тормозит на больших графах и как ускорить обход с PySpark и GraphFrames. Плюсы распределённых DataFrame и пример.

Обработка графов с миллионами вершин в Python обычно упирается сразу в две стены: давление на память из‑за встроенных структур и медленный однопоточный обход. Поиск в ширину или в глубину по спискам смежности, хранящимся в файлах, превращается в проблему координации, как только вы пытаетесь безопасно распараллелить обновления состояния. Когда BFS на словарях наконец запускается, он часто «застревает» из‑за случайных обращений к памяти и промахов кэша. Выход — переложить обход на движок, рассчитанный на распределённые данные, сохранив при этом удобство разработки.

Базовый вариант: однопроцессный BFS, который не масштабируется

Вот каноничный BFS в памяти: выглядит просто, но на очень больших графах быстро упирается в ограничения по памяти и пропускной способности:

from collections import deque

def walk_bfs(adj_index, origin):
    seen = set()
    frontier = deque([origin])
    while frontier:
        cur = frontier.popleft()
        if cur not in seen:
            seen.add(cur)
            frontier.extend(adj_index.get(cur, []))
    return seen

Логика корректна, но сочетание Python‑структур dict, set и deque влечёт за собой «погоню за указателями» и хаотичный доступ к памяти. По мере роста графа это выводит на критический путь задержки DRAM и ухудшает масштабирование по ядрам. Попытка разбить работу на несколько процессов добавляет борьбу за общие ресурсы и накладные расходы на координацию общего состояния — выгоды часто нивелируются.

Почему на масштабе всё замедляется

Обходы больших графов упираются в нерегулярные обращения к памяти. В словарях и множествах Python операции поиска и вставки прыгают по адресному пространству. Такой профиль кладёт пропускную способность и латентность DRAM в основу производительности и ограничивает ускорение от дополнительных ядер. Расширение фронтира BFS между процессами усложняет синхронизацию и обмен данными, особенно когда нужны потокобезопасные обновления и устранение повторных посещений. Сам BFS особенно плохо масштабируется; DFS, как правило, проще распараллелить. Переход на более низкоуровневое нативное представление и более векторизованный код мог бы сократить объём памяти и помочь с производительностью, но реализовать это непросто.

Практичный путь вперёд: pyspark + graphframes

Чтобы обходить очень большие графы без загрузки всего в память одного Python‑процесса, перенесите работу в распределённый движок данных. Связка pyspark и graphframes позволяет описать BFS на высоком уровне и поручить движку оркестрацию параллельного выполнения и управление данными. Обход остаётся декларативным, и вам не нужно самостоятельно строить синхронизацию общего состояния. Ниже — минимальный пример: он создаёт небольшой граф и запускает сквозной BFS с использованием graphframes.

from pyspark.sql import SparkSession
from graphframes import GraphFrame

# Инициализируем сессию Spark
spark_sess = SparkSession.builder \
    .appName("BFS") \
    .config("spark.jars.packages", "graphframes:graphframes:0.8.2-spark3.0-s_2.12") \
    .getOrCreate()

# Создаём DataFrame с вершинами и рёбрами
v_df = spark_sess.createDataFrame([
    ("a", "Alice"),
    ("b", "Bob"),
    ("c", "Charlie"),
    ("d", "David"),
    ("e", "Esther")
], ["id", "name"])

e_df = spark_sess.createDataFrame([
    ("a", "b"),
    ("b", "c"),
    ("c", "d"),
    ("d", "e")
], ["src", "dst"])

# Собираем GraphFrame
gf = GraphFrame(v_df, e_df)

# Выполняем запрос BFS
bfs_out = gf.bfs(fromExpr="id = 'a'", toExpr="id = 'e'")
bfs_out.show(truncate=False)

Этот подход бьёт по ключевым проблемам, описанным выше. Данные представлены в виде DataFrame, сам обход выполняет graphframes, и нет необходимости грузить огромный словарь смежности в один процесс или проектировать собственные механизмы межпроцессного взаимодействия. Если позже захотите посмотреть в сторону графовых баз, можно рассмотреть и Neo4j.

Почему это важно знать

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

Вывод

Если BFS на словарях Python упирается в память и работает медленно, перенесите вычисления в pyspark с graphframes и описывайте обход на уровне DataFrame. Это избавляет от самодельной конкуррентности, не требует держать весь граф в одном процессе и согласует задачу с инфраструктурой, для которой она создана. Помните, что BFS по природе тяжело масштабируется из‑за случайного доступа к памяти; если позже понадобится другое средство, графовая база вроде Neo4j — разумное направление для дальнейшего изучения.