Б Бёрнс - Распределенные системы. Паттерны проектирования

Как уже было сказано, шардирование может выступать при-мером реализации фазы Map в каноническом алгоритме Map/ Reduce . Следовательно, нам осталось лишь реализовать фазу Reduce . Reduce является примером паттерна координированной 208Часть III. Паттерны проектирования систем пакетных вычислений

Рис. 12.2. Паттерн пакетной обработки Join

пакетной обработки, поскольку может существовать независимо от того, как поделен входной поток, и использоваться аналогич-но паттерну Join, то есть для слияния параллельно вычисляемых результатов пакетной обработки элементов данных. Однако, в отличие от рассмотренного ранее паттерна Join, за-дача паттерна Reduce — выполнить оптимистичное слияние всех параллельно вычисленных элементов данных в единое исчерпывающее представление исходного множества. В паттерне Reduce каждый шаг вычислений приводит к свора-чиванию нескольких элементов выходных данных в один. Эта фаза называется сверткой , поскольку в ней уменьшается объем Глава 12. Координированная пакетная обработка 209выходных данных. Иными словами, исходный набор данных сво-рачивается до некоторого репрезентативного набора данных, по-зволяющего найти результат конкретных пакетных вычислений. Поскольку фаза свертки работает над некоторым участком вход-ных данных и порождает похожие на них выходные данные, ее можно повторять столько раз, сколько необходимо, до тех пор, пока на выходе не получится единственное значение, соответ-ствующее всему набору данных. Это выгодно отличает паттерн Reduce от паттерна Join, поскольку фаза свертки может запу-скаться параллельно фазе шардирования других участков дан-ных. Для получения конечного результата, конечно же, в итоге придется обработать все данные, но возможность начать обра-ботку раньше позволяет в целом быстрее завершить вычисления. Практикум. Подсчет

Чтобы понять, как работает паттерн Reduce, рассмотрим задачу подсчета количества вхождений определенного слова в книге. Сначала воспользуемся шардированием, чтобы разделить задачу подсчета на несколько очередей. Можно, например, создать де-сять разных шардированных очередей, за подсчет слов в каждой из которых отвечает один исполнитель. Книгу можно шарди-ровать между этими десятью очередями по номеру страницы. Страницы с номером, заканчивающимся на 1, уйдут в первую очередь, на 2 — во вторую и т. д.

Как только все исполнители закончат подсчет на своих стра-ницах, каждый из них запишет результат на листочке бумаги. Например:

a: 50

the: 17

cat: 2

airplane: 1

210Часть III. Паттерны проектирования систем пакетных вычислений Эти данные передаются на фазу свертки. Напомню, что паттерн Reduce выполняет свертку путем комбинации двух и более эле-ментов входных данных в один элемент выходных. Второй набор выходных данных:

a: 30

the: 25

dog: 4

airplane: 2

...

Далее в процессе свертки количество экземпляров слов в каж-дом из шардов суммируется:

a: 80

the: 42

dog: 4

cat: 2

airplane: 3

...

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