Якія праблемы гэта MapReduce вырашыць?

Я чытаў пра MapReduce на некаторы час - але тое, што я не магу зразумець, як нехта прыме рашэнне выкарыстаць (ці не выкарыстоўваць) MapReduce.

Я маю на ўвазе, якія праблемныя мадэлі, якія сігналізуюць, што MapReduce можа быць выкарыстана.

61

12 адказы

Гэта ў асноўным праблемы, велізарныя, але не складана. каміваяжор у вырашальнай ступені залежыць ад адлегласці паміж любой парай гарадоў, таму ў той час як яна можа быць разбіта на мноства частак, частковыя вынікі не могуць быць рекомбинируют так, што аптымальнае рашэнне глабальна ўзнікае (ну, верагодна, не , калі вы ведаеце спосаб, калі ласка, падаць заяву на Філдса цяпер).

З іншага боку, лічачы частоты слоў у гіганцкім корпусе трывіяльным разбиваемы, <�ет> і трывіяльным recombinable (вы проста скласці вектары, вылічаныя для сегментаў корпуса), так што карта-скрутка з'яўляецца відавочным рашэнне.

На практыцы, больш праблем, як правіла, лёгка recombinable, чым няма, таму рашэнне аб тым, каб распараллелить задачу або не мае больш агульнага з тым, як велізарная задача, і менш з тым, як гэта цяжка.

47
дададзена
@dan_waterworth: Вы не можаце аб'яднаць гэтыя рашэнні. Аб'яднанне ў галіне «знайсці самы кароткі маршрут дзіцяці (, які не выкарыстоўвае якой-небудзь вузел з продкаў ) + шлях ад філіяла да дзіцяці.
дададзена аўтар Matthew Encinas, крыніца
Я не разумею, ваша тлумачэнне таго, чаму MapReduce ня падыходзіць для коміваяжора.
дададзена аўтар Adam Lassek, крыніца
У выпадку, калі ў вас ёсць рашэнне, памятаеце, што вы маеце права толькі для Філдса, калі вы маладзейшых за 40 гадоў.
дададзена аўтар Peter Schneider, крыніца
Калі вы шукаеце для прыблізнага адказу на задачы коміваяжора, вы можаце трывіяльны выбраць адказ з мінімальным адлегласцю да зліцця.
дададзена аўтар Alex, крыніца
@KilianFoth, вы маглі б зрабіць вычарпальны пошук шляхам падзелу прасторы рашэнняў у, пачынаючы з 1, пачынаючы з 2, ..., то для вырашэння задачы на ​​кожным з гэтых вузлоў шляхам разбіцця прасторы зноў такім жа чынам. Аб'яднанне ў корані проста знайсці самы кароткі шлях, зліваючыся на іншую галіны пошук найкарацейшага 'дзіця маршруту + маршрут ад галіны да дзіцяці.
дададзена аўтар Alex, крыніца
Вы маеце рацыю, вы <�я> можна </я> Выкарыстанне раздзелаў для вылічэнні аптымальнага рашэння, калі вы старанна гэта зрабіць - вы нават атрымаеце чаканую хуткасць уверх прыкладна на лік вузлоў. Гэта проста, што, паколькі зыходная задача экспанентна дорага, што, верагодна, не будзе рухацца праблему з «занадта дорага» да «магчыма», як гэта звычайна бывае з іншымі праблемамі. Такім чынам, тэхнічна гэта магчыма прымяненне, проста не тыповы адзін.
дададзена аўтар sigirisetti, крыніца
Ён падыходзіць для пошуку <�я> а </я> рашэнне, можа быць, нават вельмі добры адзін - проста разбіць мноства гарадоў на меншыя наборы, напрыклад, 1-10, 11-20, 21-30, знайсці аптымальныя маршруты паміж імі, і злучыць іх з хмелем 10-> 11, 20-> 21 і 30-> 1. Але сутнасць праблемы заключаецца ў тым, каб знайсці аптымальны маршрут, і няма ніякай гарантыі, што аптымальны маршрут падзелены такім чынам - гэта, магчыма, на самай справе пачаць з 1-> 25! Іншымі словамі, каб знайсці правільнае падзел, вы павінны ў асноўным ведаць рашэнне ўжо! Менавіта таму знаходжанне <�я> аптымальны маршрут не ўспрымальны да агароджвае-і-Зборку трук
дададзена аўтар sigirisetti, крыніца

<�Моцны> Можа праблема быць эфектыўна вырашана з дапамогай размеркаваных вылічэнняў? </Моцны>

Калі адказ на гэтае пытанне сцвярджальны, то ў вас ёсць праблемы кандыдата ў MapReduce. Гэта адбываецца таму, што карціна праблемы паддаецца расколваюцца на дробныя ізаляваныя праблемы.

<�Моцны> Ваша задача: Разабраць гэтую кнігу

Прыклад працуе добра ilustrate гэта. У вас ёсць вялікі дакумент ( Мобі Дзік Герман Мелвіл ) і ваша праца складаецца ў тым, каб правесці аналіз частоты усіх слоў, якія выкарыстоўваюцца ў ім.

Паслядоўны падыход

Вы можаце зрабіць гэта паслядоўна атрымліваць ваш хуткі машын (у вас ёсць шмат валяецца) і працуе над тэкстам ад пачатку да канца захоўваючы хэш-карту кожнага слова знайсці (ключ) і прырашчэнне частоты (значэнне) кожны раз, калі вы разабраць ні слова. Просты, просты і павольны.

<�Ет> The MapReduce падыход

Падышоўшы гэта з іншага пункту гледжання, вы заўважаеце, што ў вас ёсць усе гэтыя запасныя машыны, якія ляжаць вакол, і вы маглі б падзяліць гэтую задачу на кавалкі. Дайце кожнай машыне блок 1Mb тэксту для сінтаксічнага аналізу ў хэш-карту, а затым разбору ўсіх Хэш-карты з кожнага ў адзіны вынік. Гэта слаістай рашэнне MapReduce.

Працэс чытання радкі тэксту і збіраючы словы з'яўляецца фазай Map (стварыць простую карту, якія прадстаўляюць слова ў адпаведнасці з іх частатой 1,2,3 і г.д.), то паменшыць фазу, калі кожная машына супастаўляе сваю лінію карты ў адным абагульненай карце.

Агульнае рашэнне зыходзіць ад далейшага зніжэння фазы, дзе ўсе агрэгатныя карты абагульненай (зноў гэтае слова) у выніковую карту. Ледзь больш складаны, з масавым паралелізмам і хутка.

<�Моцны> Рэзюмэ

Такім чынам, каб падвесці вынік, калі ваша праблема паддаецца малююцца ключамі, значэнняў, агрэгатныя аперацыі на гэтых значэннях паасобку, то ў вас ёсць праблемы кандыдата ў MapReduce.

28
дададзена
мех; гэта спрашчэнне. MapReduce аб падзеле дадзеных, ужываючы функцыю на кавалкі паралельна <�я> без сувязі паміж аналізатарамі , а затым ўжываць іншую функцыю, каб аб'яднаць біты. Не ўсе размяркоўваюцца праблемы адпавядаюць гэтай мадэлі.
дададзена аўтар djn, крыніца
Кірмаш кропка - але яна служыць карысным увядзеннем і дазваляе камусьці «акно» іх праблемы.
дададзена аўтар Gary Rowe, крыніца

Шаблон MapReduce узяты са свету функцыянальнага праграмавання. Гэта працэс нанясення нешта, званае катаморфизм над структурай дадзеных паралельна. Функцыянальныя праграмісты выкарыстоўваюць катаморфизм для амаль кожнага простага пераўтварэння або рэферыраванне.

Калі выказаць здагадку, што вашыя дадзеныя дрэва, вырашальным фактарам з'яўляецца тое, ці можна вылічыць значэнне для вузла, выкарыстоўваючы толькі дадзеныя, якія змяшчаюцца ў гэтым вузле і вылічаныя значэння для сваіх дзяцей.

Напрыклад, вы можаце вылічыць памер дрэва, выкарыстоўваючы катаморфизм; вы б вылічыць суму вылічаных значэнняў для ўсіх дзяцей плюс адзін.

13
дададзена
Калі б толькі гэта называлі <�я> MapFold ; што было б нашмат лягчэй зразумець.
дададзена аўтар Matthew Encinas, крыніца
@scarfridge, я выказаў здагадку, што ОП не меў на ўвазе канкрэтныя рамкі Google. Я кансультаваўся ў артыкуле Вікіпедыі ў дачыненні да таго, ён выкарыстоўваецца толькі для спісаў або дрэў у цэлым перад публікацыяй. en.wikipedia.org/wiki/MapReduce#Overview
дададзена аўтар Alex, крыніца
Добры адказ, я не ўпэўнены, калі @good_computer меў на ўвазе канкрэтныя рамкі MapReduce, распрацаванай Google. І я не ведаю, калі MapReduce (ізноў жа рамкі Google) адносіцца да чаго-то іншаму, чым тыпы ізаморфныя спісаў.
дададзена аўтар scarfridge, крыніца

Гэта WPI - Ужыванне карты Паменшыць (РРТ) можа прадстаўляць цікавасць для вы. У ім разглядаюцца розныя прыкладання MR, і ў якасці аднаго з разгледжаных выпадкаў, гэта паказвае, як з дапамогай 100 асобнікаў EC2 і 24 гадзін, Нью-Ёрк Таймс быў у стане пераўтварыць 4 ТБ адсканаваных артыкулаў 1.5TB з PDF-дакументаў.

Іншы набор прыкладаў, калі MR дапамаглі ў паскарэнні прадукцыйнасці па адрасе: Aster - SQL Map Скарачэнне паказвае некаторыя тэматычныя даследаванні з SQL-Map Скарачэнне тэхналогіі, уключаючы выяўленне выпадкаў махлярства, Трансфармацыі і іншыя.

6
дададзена
Калі вы ў канчатковым выніку з аднаго дакумента на адным адсканаванага артыкуле, яны вас проста выкарыстоўваючы размеркаваную карту, а не MapReduce. У карце-скрутка прымяніць рэдукцыя да вынікаў карты для атрымання аднаго выніку.
дададзена аўтар Rob Hunter, крыніца
Справядліва, дзякуй за каментар.
дададзена аўтар Anders Lindahl, крыніца

Map/Reduce з'яўляецца спецыфічнай формай пэўнага выгляду алгарытму. Вы можаце выкарыстоўваць яго для пераўтварэння адзін велізарны набор дадзеных у іншы набор дадзеных. (У выніку набор дадзеных можа ці не можа быць велізарным.) Калі вы не хочаце, статычны выснову дадзеных усталяваны ў выніку статычнага ўводу дадзеных, то Map/Reduce не падыходзiць. Map/Reduce можа лёгка сказаць вам, колькі Джон Smiths у тэлефоннай кнізе Манхэтэна, але ён не вельмі добра падыходзіць для стварэння вэб-сервера.

Шлях Map/Reduce працы з'яўляецца:

  • Карта прымае пары ключоў (k1) і значэнняў (v1) і адлюстроўвае іх у новы набор ключоў (k2) і значэнняў (v2).
  • Зніжэнне прымае ўсе значэння v2 з тым жа ключом k2 і стварае новае значэнне (v3).

У выніку спіс (k1, v1) пара ператвараецца ў спіс (V3) с. (Вядома, значэнне «версія 3» можа быць састаўным, які ўключае ў сябе k2, які можа быць вызначаны, каб быць роўным k1.)

<�Моцны> Дык вы яго выкарыстоўваеце:

  1. <�моцны> Калі ў вас ёсць так шмат дадзеных, каб пачаць з гэтым запусціць яго ўсё паслядоўна праз адзін або два сервера зойме занадта шмат часу, і

  2. <�моцны> Вы можаце ўявіць сабе выходных дадзеных з'яўляецца спіс значэнняў або ключавых пар значэнняў (як правіла, не занадта складана, калі вы памятаеце, «ключ» азначае толькі «унікальная пазнака»), і </р>

  3. <�моцны> Які б ні былі адносіны, вы ўпэўненыя, што кожная частка ўваходных дадзеных ўплывае толькі на выхадную значэнне для аднаго выхаднога ключа.

Калі вашы дадзеныя могуць быць апрацаваны паслядоўна адным серверам, то так, што з'яўляецца дамінуючай парадыгмай вылічэнняў (сервера з іх пабудаваныя для і праграмістаў навучаны), выкарыстоўваць адзін сервер.

Прыступку карты павінна падзяліць усе ўваходныя дадзеныя ад выхаднога ключа. Ён не павінен вырабляць выходную значэнне, звязанае з ключом высновы (гэта зроблена на стадыі зніжэння), але ён павінен адназначна прызначаць кожны ўваходных пару ключоў значэння для садзейнічання значэння не больш за адзін выхаднога ключа. Калі дадзеныя занадта ўзаемазвязаны, то карта зніжэння можа быць не ў стане справіцца з гэтай праблемай. З іншага боку, гэта можа быць проста, што вам трэба выкарыстоўваць некалькі раўндаў карты/паменшыць.

Калі вы не можаце зразумець, як ператварыць пераўтварэнне дадзеных у карту/паменшыць, то, вядома, гэта не з'яўляецца рашэннем праблемы.

Існуе рэальнае мастацтва высветліць, калі праблема можа быць раскладзеная на нешта Map/Reduce можа справіцца. Напрыклад, v1 і v2 можа быць не ў наборы ўваходных або выходных дадзеных на ўсіх. Калі вы проста хочаце, каб разлічваць унікальныя элементы ва ўваходных дадзеных, то k1 = k2 = элемент і v1 = v2 = 1 або 0, ці на самай справе нічога. Зніжэнне толькі вырабляе v3 як сума колькасці к2-х ён быў дадзены.

Так што цяжка сказаць напэўна, што пераўтварэнне дадзеных не можа быць зроблена з дапамогай Map/Reduce, але вышэй, дае вам некаторыя арыенціры.

6
дададзена

MapReduce працуе на любой праблеме, якая складаецца з роўна 2 функцый на пэўным узроўні абстракцыі. Першая функцыя прымяняецца да кожнага з элементаў у наборы ўводу, а другая функцыя агрэгуе вынікі.

Такім чынам, у любы час вы хочаце атрымаць (1) вынік (п) уваходаў, а ўсе ўваходы могуць быць разгледжаны і б/у (1) функцыі, вы можаце выкарыстоўваць MapReduce. Зноў жа, гэта ў нейкім пэўным узроўні абстракцыі. Функцыя (1) можа быць пэўная функцыя групоўкі, якая правярае увод і вырашае, якія з некалькіх іншых функцый для выкарыстання.

Гэта карысна, калі вы не ведаеце загадзя, колькі ўваходных вы будзеце мець, калі вам трэба дзяліць дыскрэтную «адзінку» працы, ці калі вы хочаце адзін вяртанне, каб прадставіць увесь вынік (IE працуе пяць тысяч модульных тэстаў , а калі менш, чым х% не атрымаецца, вярнуць поспех).

3
дададзена

Большасць адказаў тут, здаецца, некаторыя варыяцыі растлумачыць, што карта паменшыць робіць, што з'яўляецца сапраўдным. Але адказаць на пытанне, які быў, які шаблон будзе сігналізаваць, дзе вы маглі б выкарыстоўваць карту скараціць на самай справе не адрасаваны гэтым.

Калі наіўная, ня функцыянальная, рэалізацыя задачы вы глядзіце ўключае ў сябе цыкл над чымсьці, а затым абнавіць што-то па-за цыкла з некаторымі са стану ўнутры цыклу, хутчэй за ўсё, у вас ёсць нешта, што парты добра для адлюстравання паменшыць. Асабліва, калі вы можаце абагульняць абнаўленне цэнтральнага стану ў функцыі, якая працуе толькі з двума параметрамі і можа гарантаваць гэтая функцыя з'яўляецца коммутативной і асацыятыўнай.

Прычына вы можаце выкарыстоўваць карту паменшыць, калі гэта дакладна, то два разы: 1) ён можа быць трохі чысцей і прасцей для тэставання і адладкі, калі вы парушыце рэчаў у карце і паменшыць функцыі. 2) карты зніжэння функцыі з'яўляюцца асобамі без грамадзянства і могуць працаваць адначасова, што паскарае рэчы, калі ў вас ёсць некалькі працэсараў, даступных і нешта накшталт Hadoop або іскра, якая выкарыстоўвае, што для запуску рэчы ў кластары.

Гэта добра, калі вы зацыкленне на шмат рэчаў, але ваш прабег можа вар'іравацца ў залежнасці ад таго, наколькі складаная ваша карта/памяншае гэта. Гэта даволі часта, каб у канчатковым выніку з паслядоўнай ланцугу або дрэва скарачэнняў карты, дзе ў рэшце рэшт усё яшчэ ўпіраюцца на некаторай комплекснай стадыі аднаўлення ў канцы ланцужка. Напрыклад, многія алгарытмы графа цяжка маштабаваць эфектыўна толькі з карты паменшыць.

Найпросты прыклад, які добра працуе з картай паменшыць, разлічвае матэрыял, які з'яўляецца вельмі танным скарачэннем. Таму колькасць слоў з'яўляецца часта выкарыстоўваным прыкладам для карты паменшыць. Вы можаце ў значнай ступені чакаць лінейную маштабаванасць прадукцыйнасці з тым, што USECASE: кожны працэсар вы дадаеце робіць яго хутчэй.

3
дададзена

Калі вы робіце шмат функцыянальнага праграмавання вы пачаць працаваць у сітуацыі, якія патрабуюць агульнай карты і скарачэнне. Вы, напэўна, нават убачыць іх у імператыўным праграмаванні, але не прызнаюць іх за маскай завес і акумулятараў.

У якасці прыкладу аднаго, які прыдумаў для мяне ў апошні час, я працаваў на сінтаксічны аналізатар ў Haskell. Для таго, каб праверыць мой парсер, я напампаваць спіс радковых фрагментаў праз аналізатар, а затым я хачу, каб атрымаць адзін радок, я магу выводзіць з маіх вынікаў, каб убачыць, калі ён разабраны правільна. Так што выглядае наступным чынам:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Of course, this is just pedagogical. My actual code looks a bit different, and uses more internal functions (like fold concat isn't needed since Haskell already includes unlines that does [String]->String). My main point was that I didn't anticipate using a map/reduce when I started, it just aligned to my needs. I wanted to do some stuff with lists, then turn my list into a single element of output. The use of map/reduce emerged naturally.

Апрацоўка радкоў (напрыклад, пры разборы) адзін вельмі відавочнае выкарыстанне рэдукцыі карты, адлюстраванне з'яўляецца ужываннем розных пераўтварэнняў на ўваходным тэксце, і паменшыць яго ўвод тэксту выніку зноў разам у якасці выхаднога сігналу. Аналагічна, кампілятар можа быць падобны, выкарыстоўваючы зморшчыны, каб ператварыць паток элементаў абстрактнага сінтаксічнага дрэва ў лепшы форму (аптымізацыя).

2
дададзена

Ці з'яўляецца гэта параллелизуемы?

Любая параллелизуемы праблема, па сутнасці, карту і згін; наадварот, крок карта з'яўляецца па сваёй сутнасці параллелизуемы (і зморшчына крок можа быць, у залежнасці ад структуры, над якой ён складаны), так што гэта ўласцівасць двунаправленным.

1
дададзена
Ёсць шмат ашаламляльна паралельных праблем, не ўсе з якіх трэба паменшыць часткі.
дададзена аўтар djn, крыніца
дзякуй за спасылку, я не ведаў пра embarassingly paralell перспектыве. не ўсе карты зніжаюць адрозныя праблемы embarassingly paralell?
дададзена аўтар Paul Sanwald, крыніца
Гэта толькі ў выпадку праблем Смущающе паралельна . Ёсць шмат праблем, якія з'яўляюцца вельмі параллелизуемы, але якія ўтрымліваюць дастатковую ўзаемадзеянне паміж элементамі, што просты MapReduce не будзе эфектыўным.
дададзена аўтар Mark Booth, крыніца

у сутнасці, гэта радавое «падзяляй і ўладар» мадэль, так што рашэнні для размеркавання вылічэнняў можна запісаць у агульным выглядзе.

просты прыклад, як вялікі дакумент. праблема ў тым, вы хочаце, каб падлічыць колькасць літар у гэтым дакуменце. замест таго, каб працаваць на адной машыне, вы можаце разбіць яго на масіў ўсіх слоў у дакуменце. то вы можаце апрацаваць кожнае слова ў асобнасці, і вынікі разам.

карціна карысна, таму што, як толькі вы атрымаеце агульную карту/паменшыць выкананне працы вам можа вырашыць любую праблему, выкарыстоўваючы той жа пласт праграмнага забеспячэння, вам проста трэба, каб выказаць вашу праблему ў тэрмінах.

1
дададзена

Вось асноўныя пытанні, якія я выкарыстоўваю, каб даследаваць рашэнне выкарыстаць (ці не выкарыстоўваць) MapReduce.

  • Is achieving reasonable parallel execution performance with minimal programmer effort important for a given problem?
  • Do I have a large number (hundreds) of parallel execution elements available?
  • Is there excellent communication bandwidth/throughput among the parallel execution elements?
  • Do I need to process a huge amount (TB) of data?
  • Does the problem I am trying to solve decompose into Map and Reduce operation?

    • Map: Execute the same operation on all data.
    • Reduce: Execute the same operation on each group of data produced by Map.
1
дададзена

Дапусцім, вы шукаеце кластар сервераў і адзін не можа адказаць на гэты момант. Што MapReduce будзе рабіць гэта, бо ён не можа атрымаць доступ да гэтага вузла дрэва на карту большага памеру ён будзе перанесці яго на потым і выконваць альбо карту або паменшыць то. Па сутнасці, ён спрабуе гарантаваць ўся інфармацыя даступная з непрадказальнасцю праграмнага і апаратнага забеспячэння ў асяроддзі.

1
дададзена