Расподељена обрада података

Расподељени системи се често користе за прикупљање, приступ и манипулацију великим скуповима података. На пример, системи база података описани раније у поглављу могу да раде преко скупова података који се чувају на више рачунара. Ниједан рачунар понаособ не мора садржати податке потребне за одговор на упит, па је неопходна комуникација међу њима да би се одговорило на захтеве за услугом.

Овај одељак истражује уобичајен сценарио обраде велике количине података у којем је скуп података превелик да би га обрадио један рачунар, па се уместо тога посао расподељује између многих рачунара од којих сваки обрађује део скупа података. Резултат обраде се често мора агрегирати на више рачунара, тако да се резултати израчунавања са једног рачунара могу комбиновати са другима. Да би се координисала ова расподељена обрада података, биће разговора о програмском оквиру под називом MapReduce оквир.

Прављење расподељеног програма за обраду података са MapReduce комбинује многе идеје представљене у овом рукопису. Програм се изражава у виду чистих функција које се користе за пресликавање то јест мапирање (Map део) великог скупа података, а затим за свођење (Reduce део) мапираних секвенци вредности у коначни резултат.

Познати концепти из функционалног програмирања обилато се користе у MapReduce програмима. MapReduce захтева да функције које се користе за мапирање и свођење података буду чисте функције. Уопштено гледано, програми изражени само у виду чистих функција имају знатну флексибилност у начину извршења. Подизрази се могу израчунати произвољним редоследом и у паралели, без утицаја на коначни резултат. MapReduce програм многе чисте функције вреднује, односно извршава у паралели, преуређујући израчунавања која се ефикасно извршавају у расподељеном систему.

Главна предност MapReduce-а је што намеће раздвајање брига и проблема између два дела расподељеног програма за обраду података:

1. Функције за мапирање и свођење које обрађују податке и комбинују резултате.

2. Комуникација и координација међу рачунарима.

Механизам координације решава многа питања која се јављају у расподељеном израчунавању, као што су кварови на рачунарима, мрежни кварови и праћење напретка израчунавања. Иако управљање овим проблемима уноси одређене сложености у MapReduce програме, ниједна од тих сложености није директно изложена самом програмеру. Уместо тога, писање MapReduce програма захтева само навођење функција мапирања и свођења, као што је то написано у првој од горње две наведене тачке, док сви изазови расподељеног израчунавања остају сакривени апстракцијом.

MapReduce

MapReduce оквир као свој улаз претпоставља велики, неуређени ток улазних вредности произвољног типа. На пример, сваки унос може бити ред текста у неком огромном корпусу. Израчунавање се одвија у три корака.

1. На сваки улаз примењује се функција мапирања која даје нула или више међупарова кључ-вредност произвољног типа.

2. Сви међупарови парови кључ-вредност груписани су по кључу, тако да се парови са истим кључем могу свести заједно.

3. Функција свођења комбинује вредности за дати кључ \(k\) дајући нула или више вредности, које су све повезане са \(k\) у коначном излазу.

Да би извршио ово израчунавање, MapReduce оквир ствара задатке (могуће на различитим рачунарима) који извршавају различите улоге у израчунавању. Задатак мапирања примењује функцију мапирања на неки подскуп улазних података и избацује међупарове кључ-вредност. Задатак свођења сортира и групише парове кључ-вредност по кључу, а затим примењује функцију свођења на вредности за сваки кључ. Сва комуникација између задатака мапирања и свођења обрађује се у MapReduce оквиру, као и задатак груписања међупарова кључ-вредност по кључу.

Да би се користило више рачунара у MapReduce програму, више мапера ради паралелно у фази мапирања, а више редуктора, то јест свођача ради паралелно у фази свођења. Између ових фаза, фаза сортирања групише парове кључ-вредност једноставним сортирањем тако да су сви парови кључ-вредност са истим кључем суседни.

Размотрити проблем пребројавања самогласника у корпусу текста. Овај проблем може се решити помоћу MapReduce оквира уз одговарајући избор функција мапирања и свођења. Функција мапирања узима као свој улаз ред текста и враћа парове кључ-вредност у којима је кључ самогласник, а вредност број самогласника у датом реду. Нулти бројеви самогласника су изостављени из излаза:

>>> def избројСамогласнике(ред):
...     """Функција мапирања која броји самогласнике у реду."""
...     for самогласник in 'аеиоу':
...         број = ред.count(самогласник)
...         if број > 0:
...             emit(самогласник, број)

Функција свођења је заправо уграђена sum функција збира у Пајтону, која као свој улаз прима итератор кроз вредности (све вредности за дати кључ) и враћа њихов збир.

Локална имплементација

Да би се одредила MapReduce апликацију, потребна је имплементација MapReduce оквира у који се могу уметнути функције мапирања и свођења. У следећем одељку биће искоришћена слободна Хадуп имплементација. У овом одељку биће развијена минимална имплементација користећи уграђене алате ГНУ/Линукс оперативног система.

Оперативни систем ГНУ/Линукс, као и други Јуниксолики оперативни системи, ствара апстракцијску баријеру између корисничких програма и основног хардвера рачунара. Такође пружа и механизам за међусобну комуникацију програма, посебно омогућавањем да један програм прима излаз другог. У свом првобитном тексту о Јуникс програмирању, Брајан Керниген и Роберт Пајк тврде да: „Снага система долази више из односа међу програмима него из самих програма.”

Датотека која садржи изворни код у Пајтону се претворити у ГНУ/Линукс програм додавањем коментара у први ред који указује на то да програм треба извршити помоћу Пајтон 3 интерпретатора. Улаз у ГНУ/Линукс програм је итерирајући објекат који се назива стандардни улаз и којем се приступа као sys.stdin. Итерирање над овим објектом производи редове текста у виду ниске као вредности. Излаз ГНУ/Линукс програма назива се стандардни излаз и њему се приступа као sys.stdout. Уграђена print функција исписује ред текста на стандардни излаз. Следећи ГНУ/Линукс програм исписује сваки ред свог улаза на свој излаз обрнуто:

#!/usr/bin/env python3

import sys

for ред in sys.stdin:
    print(ред.strip('\n')[::-1])

Ако се овај програм сачува у датотеци под именом обрнуто.py, може се извршити као ГНУ/Линукс програм. Прво, мора се рећи оперативном систему да је написан извршни програм:

$ chmod u+x обрнуто.py

Даље, може се проследити улаз у овај програм. Улаз у програм може доћи и из другог програма. Овај ефекат се постиже коришћењем | симбола (названим „цев”) који каналише излаз програма пре цеви у програм после цеви. Програм host исписује име хоста за унету ИП адресу (у овом случају за Српску академију наука и уметности):

$ host 147.91.101.20 | ./обрнуто.py
.sr.ca.unas.sinkanargo.www retniop eman niamod apra.rdda-ni.741.19.101.02
.sr.ca.unas.mbibew retniop eman niamod apra.rdda-ni.741.19.101.02
.sr.ca.unas.www retniop eman niamod apra.rdda-ni.741.19.101.02

Програм cat исписује садржај датотека. Тако се програм обрнуто.py може користити за изокретање садржаја датотеке обрнуто.py:

$ cat обрнуто.py | ./обрнуто.py
3nohtyp vne/nib/rsu/!#

sys tropmi

:nidts.sys ni дер rof
)]1-::[)'n\'(pirts.дер(tnirp

Ови алати су довољни за имплементацију основног MapReduce оквира. Ова верзија има само један задатак мапирања и један задатак свођења, а оба су ГНУ/Линукс програми имплементирани у Пајтону. Цела MapReduce апликација покреће се помоћу следеће наредбе:

$ cat input | ./mapper.py | sort | ./reducer.py

Програми mapper.py и reducer.py морају имплементирати функцију мапирања и функцију свођења, заједно са неким једноставним улазним и излазним понашањем. На пример, да би се имплементирала горе описана апликација за бројање самогласника, написао би се следећи избројСамогласникеМапер.py програм:

#!/usr/bin/env python3

import sys
from mr import emit

def избројСамогласнике(ред):
    """Функција мапирања која броји самогласнике у реду."""
    for самогласник in 'аеиоу':
        број = ред.count(самогласник)
        if број > 0:
            emit(самогласник, број)

for ред in sys.stdin:
    избројСамогласнике(ред)

Поред тога, требало би написати и следећи збирноСвођење.py програм:

#!/usr/bin/env python3

import sys
from mr import values_by_key, emit

for кључ, вредностИтератор in values_by_key(sys.stdin):
    emit(кључ, sum(вредностИтератор))

Модул mr је пратећи модул овом тексту који садржи функције emit за емитовање пара кључ-вредност и values_by_key за груписање вредности које имају исти кључ. Пример имплементације функције за емитовање прилично је једноставан:

>>> def emit(кључ, вредност, reprПровера=False):
...     """Емитуј пар кључ-вредност као ред текста. Да би се овај пар кључ-вредност
...        касније успешно очитао, и кључ и вредност морају бити исправне repr ниске."""
...     if reprПровера:
...         assert eval(repr(кључ)) == кључ, 'Неисправна представа кључа'
...         assert eval(repr(вредност)) == вредност, 'Неисправна представа вредности'
...     print(repr(кључ) + '\t' + repr(вредност))

Поменути mr модул такође укључује сучеље ка Хадуп расподељеној имплементацији за MapReduce оквир.

Коначно, уз претпоставку да је у следећу улазну датотеку под називом химна.txt записано:

Боже правде, ти што спасе од пропасти досад нас,
чуј и одсад наше гласе и од сад нам буди спас.

Моћном руком води, брани будућности српске брод,
Боже спаси, Боже храни,
српске земље, српски род!

Боже спаси, Боже брани
моли ти се српски род!

Локално извршење које користи ГНУ/Линукс цеви и цевоводе даје тачан број сваког самогласника у химни:

$ cat химна.txt | ./избројСамогласникеМапер.py | sort | ./збирноСвођење.py
'а'     16
'е'     14
'и'     16
'о'     20
'у'     5

Расподељена имплементација

Хадуп је назив слободне имплементације MapReduce програмског оквира који извршава MapReduce апликације на кластеру рачунара, расподељујући улазне податке и прорачуне за ефикасну паралелну обраду. Његово сучеље омогућава произвољним ГНУ/Линукс програмима да дефинишу функције мапирања и свођења. У ствари, горе написани програми избројСамогласникеМапер.py и збирноСвођење.py могу се користити директно са Хадуп инсталацијом за израчунавање броја самогласника на великим текстуалним корпусима.

Хадуп нуди неколико предности у односу на горњу поједностављену локалну MapReduce имплементацију. Прва је брзина: функције мапирања и свођења примењују се у паралели користећи различите задатке на различитим рачунарима који раде истовремено. Друга је толеранција на грешке и отказе: када неки задатак из било ког разлога закаже, његов резултат може бити прерачунат другим задатком како би се довршило укупно израчунавање. Треће је надгледање: програмски оквир пружа корисничко сучеље за праћење напретка MapReduce апликације.

Да би се покренуо програм за бројање самогласника помоћу приложеног mr.py модула, треба инсталирати Апачи Хадуп, променити наредбу доделе HADOOP променљивама тако да показују ка путањама локалне инсталације, затим ископирати колекцију текстуалних датотека у Хадупов расподељени датотечни систем и на крају покренути:

$ python3 mr.py избројСамогласникеМапер.py збирноСвођење.py [улаз] [излаз]

где су [улаз] и [излаз] директоријуми у Хадуп датотечном систему.

Више информација о Хадуп сучељу и уопште о употреби самог система може се пронаћи у званичној Хадуп документацији.