Читать «Распределенные системы. Паттерны проектирования» онлайн - страница 93

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

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

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

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

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

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

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

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

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

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

0: 15%

1: 25%

2: 50%

3: 10%

4: 5%

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