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

пакетной обработки, поскольку может существовать независимо от того, как поделен входной поток, и использоваться аналогич-но паттерну 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

...

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

Суммирование

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

К примеру, вы хотите посчитать численность населения Со-единенных Штатов. Предположим, для этого вы сначала опре-Глава 12. Координированная пакетная обработка 211делите численность населения в каждом городе, а затем про-суммируете полученные результаты.

Первый шаг — разделить задачу на очереди по городам с шар-дированием по штатам. Это хороший первый шаг, но очевидно, что даже при параллельном распределении задачи одному чело-веку будет трудно подсчитать численность населения в каждом городе. Следовательно, необходимо углубить шардирование, на этот раз по округам.

На данный момент мы распараллелили задачу по штатам, затем по округам. Очереди задач в каждом округе на выходе выдают поток пар вида (город , население) .

Как только на выходе появляются значения, начинает работу паттерн Reduce.

В данном случае ему даже не обязательно знать о двухуров-невом шардировании. Ему достаточно взять два выходных элемента, например (Сиэтл, 4000000) и (Нортгемптон , 25000) и просуммировать их. В результате получится новый выход-

ной элемент (Сиэтл-Нортгемптон, 4025000) . Очевидно, что, как и в случае с подсчетом, такая свертка может выполняться неограниченное количество раз, в результате чего получится единственное выходное значение, содержащее общую числен-ность населения США. Опять-таки важно то, что почти все не-обходимые вычисления происходят параллельно. Гистограмма

В качестве последнего примера применения паттерна Reduce рассмотрим задачу, в которой одновременно с определением численности населения США путем шардирования и свертки нужно построить модель среднестатистической американской семьи. Для этого желательно получить гистограмму размера 212Часть III. Паттерны проектирования систем пакетных вычислений семьи, то есть модель, оценивающую общее количество семей с количеством детей от 0 до 10. Многоуровневое шардирование организуется так же, как и прежде (вероятно, даже с использо-ванием тех же исполнителей).

Выходным значением фазы сбора данных в этом случае будет гистограмма по городу:

0: 15%

1: 25%

2: 50%

3: 10%

4: 5%

Из предыдущих примеров видно, что можно объединить все эти гистограммы в одну, получив тем самым общую картину по США. Сперва может быть довольно трудно понять, как выполнить слияние гистограмм. Взяв данные гистограммы и данные о населении из предыдущего примера, видим, что если умножить данные гистограмм на соответствующую чис-ленность жителей, то можем получить количество населения для каждого элемента данных объединенной гистограммы. По-делив эти значения на сумму численностей населения, соответ-ствующих объединяемым гистограммам, получим данные для объединенной гистограммы. Таким образом, можно применять паттерн Reduce столько раз, сколько нужно, пока не получится единственная гистограмма.

Практикум. Конвейерная разметка и обработка изображений

Чтобы понять, как координированная пакетная обработка мо-жет быть использована для выполнения сложных пакетных задач, рассмотрим задачу разметки и обработки наборов изо-бражений. Предположим, есть большой набор фотографий Глава 12. Координированная пакетная обработка 213шоссе в час пик. Нужно посчитать количество автомобилей, грузовиков и мотоциклов, а также статистическое распределе-ние цветов машин. Допустим также, что в целях анонимизации предварительно выполняется размытие изображений номерных знаков.

Фотографии предоставляются в виде последовательности URL-адресов HTTPS, каждый из которых указывает на необработан-ное изображение. Первый этап конвейера — нахождение и раз-мытие номерных знаков. Чтобы упростить задания в очередях, введем двух исполнителей. Один будет обнаруживать номерной знак, а другой — размывать соответствующую область изо-бражения. Объединим эти два контейнера-исполнителя в одну группу, как показано в главе 10 при рассмотрении паттерна Multi-Worker. Такое распределение обязанностей на первый взгляд может показаться избыточным. Его польза в том, что контейнер-исполнитель для размытия фрагментов изображений можно использовать повторно, например для размытия лиц на фотографиях.