#parallel-processing #google-cloud-dataflow #apache-beam
#параллельная обработка #google-cloud-поток данных #apache-beam
Вопрос:
Когда вы применяете комбинированное преобразование, вы должны предоставить функцию, содержащую логику для объединения элементов или значений. Функция объединения должна быть коммутативной и ассоциативной ….
Ответ №1:
Значение ассоциативного и коммутативного в точности такое же, как в математике.
Оператор » » называется коммутативным, если a b = b a
Оператор » » называется ассоциативным, если (a b) c = a (b c)
Для «комбинированного преобразования», описанного в документации, вы пытаетесь реализовать накопление.
s =a b c d
где » » — любой оператор.
Ассоциативность — это абсолютное требование для возможности распараллеливания такой операции. Если » » не ассоциативный
-
a b c dне имеет никакого значения, поскольку((a b) c) d != (a (b c)) d. Чтобы придать непрозрачному выражению значение, результат не должен зависеть от группировки операций. -
Вы не можете изменить скобки, чтобы изменить порядок операций, чтобы выполнять их параллельно
(((a b) c) d)по своей сути является последовательным: вычислите a b, затем добавьте c, затем добавьте d
((a b) (c d))позволяет выполнять вычисления(a b)и(c d)параллельно.
Коммутативность реже требуется в качестве ограничения для распараллеливания, но она позволяет изменять порядок операндов.
Комментарии:
1. Можете ли вы привести какой-нибудь пример программирования с функциями, когда они ассоциативны, а не одинаковы для коммутативных?
2. Большинство полезных функций являются ассоциативными и коммутативными. Но если вы определяете оператор X как
a X b=a 2*b,X, очевидно, не является коммутативным. Он либо не является ассоциативным, поскольку (a X b) X c = a 2 * b 2 * c и a X (b X c) = a 2 * (b 2 * c) = a 2 * b 4 * c. Другие операции могут быть ассоциативными, но не коммутативными. Например, оператор leftof, которому заданы два аргумента (или два дочерних элемента узла дерева), возвращает левый. По моему опыту, я могу столкнуться с некоммутативными операторами, но я никогда не видел полезных операторов, которые не были бы ассоциативными.3. Ваш комментарий прекрасен, но в контексте математики, можете ли вы привести пример функций, которые являются / не являются коммутативными и ассоциативными с точки зрения программирования, что-то вроде «public void processElement (Элементы e) { //как сделать его коммутативным и ассоциативным}»?
Ответ №2:
В Apache Spark он распределяет данные по узлам, обрабатывает на нескольких машинах, а затем получает результаты из распределенных наборов данных. Распределенный набор данных называется RDD. Хорошо, давайте рассмотрим эти два свойства и их важность в параллельных системах.
val wordsRdd linesRdd.map(s => s.split(","))
Это просто разделение строк на слова. map — это локальная операция, то есть она будет выполнять функцию разделения на узлах, и между узлами не требуется координация и т.д.
val wordsRddWith1 = wordsRdd.map(w => (w, 1))
Это также локально. Это создаст, например, 5 кортежей, таких как
('cat', 1), ('bat', 1), ('cat', 1), ('rat', 1), ('rat', 1)
Теперь мы рассмотрим reduceByKey. Функция, которую он использует для работы с кортежами, должна быть ассоциативной и коммутативной.
val wordsCount = wordsRddWith1.reduce((tpl1, tpl2) => tpl1._2 tpl2._2)
Это приведет к:
cat, 2 | bat, 1 | rat, 2
Ассоциативный означает, что функция должна выполняться правильно, независимо от того, как 5 приведенных выше кортежей распределяются по узлам. Кортежи могут в конечном итоге обрабатываться на любом узле. Любой кортеж может ассоциироваться с любым другим кортежем на любом узле для суммирования количества локально в узле.
Коммутативный означает, что функция должна правильно выполняться, независимо от порядка, в котором применяется функция. Таким образом, группа кортежей может обрабатываться функцией до или после другой группы кортежей. Это не должно иметь значения.
Итак, ассоциативный — это распределение данных по узлам, а коммутативный — это обработка данных.