Алгоритм распределенной топологической сортировки

Question

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

Как я могу построить этот график зависимостей на нескольких машинах?

Answer 1

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

1. Разделите график зависимости работы между задействованными машинами. Каждая машина получает непересекающееся подмножество заданий и все зависимости, связанные с этими заданиями.

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

Общий сетевой трафик составляет порядка размера графа, а количество патронов ограничено по длине самого длинного пути, так что этот алгоритм должен быть достаточно эффективным для использования.