Напомню, кто проходил мои курсы по highload-системам:
"MapReduce -- модель программирования низкого уровня, предназначенная прежде всего для распределённых вычислений на кластерах машин. Языки запросов более высокого уровня, такие как SQL, можно реализовать в виде конвейера операций MapReduce.
Reduce также потенциально допускает параллельное вычисление -- например, список можно разбить на два, и редуцировать каждый из них независимо, и так далее рекурсивно."
Например, в Hadoop используется вариация MapReduce, которая сперва распределяет блоки данных по физическим узлам, которые далее обрабатываются map параллельно, и формируется временное хранилище ключ-значение. Затем происходит перераспределение: данные с одинаковыми ключами объединяются на конкретных узлах, и теперь они хорошо пригодны для дальнейшей обработки reduce в рамках каждого узла.
Однако сильное подозрение, что моноида будет недостаточно, потому что все типичные примеры вроде карт частотности ключей -- это на самом деле коммутативные моноиды при соответствующей операции reduce.
=
Вот кстати в тему отличные статьи "Абстрактная алгебра в действии" (примеры на прозаическом шарпике!), крайне рекомендую для ознакомления =>
https://habr.com/ru/articles/655059/
https://habr.com/ru/articles/656919/
Автор Степан (StepOne) классно пишет в тг "немного технической духоты на C#" :)
Его блог -- эталонный пример, кем вы должны становиться, если занимаетесь в моей Школе. Дико таких ребят уважаю.
Дорогие, ну пишите что-то подобное на Java например (или на F# :), и вас эйчары будут с руками рвать и на коленочках приползут умолять.
=
Так вот, моя гипотеза, что параллельный MapReduce будет давать корректные результаты, только если промежуточная структура данных, которую мы подготовили на фазе map, есть коммутативный моноид при операции reduce. Это более строгое условие для обеспечения действительной корректности крупных реализаций MapReduce, рассчитанных на BigData.
Ну если совсем для малышей: к reduce порядок элементов может случайно меняться из-за параллелизма, и если операции над ними не коммутативны, то итоговый результат может быть ошибочным. Темку недетерминизма мы разбирали, в частности, на курсе по декларативной вычислительной модели ("старайтесь никогда не использовать вместе параллелизм и состояния").
(добавил в курс "33 стиля программирования")