MapReduce

Gil Abrantesgil@webreakstuff.com

MapReduce?Google = vários TB/diaFramework de processamento distribuido

MapReduce?

Fluxo dos dados

Distribuição do codigo das tarefas

Monitorização

Optimizações

Tolerancia a falhas

MapReduce!Problemas resolvidos uma unica vezBase de codigo maduraFacil e rapido escrever jobs!

IngredientesIngredientes

Master

Centro de monitorização

Divide os dados em chunks

Recebe o resultado

Envia tarefas aos slaves

Slaves

Devolvem o resultado

Recebem tarefas respectivas a chunks especi"cos

Procuram os respectivos chunks de dados

Executam as tarefas

Master conhece o estado dos slavesDetecção de chunks rebeldes

Detecção de falhas

OptimizaçõesOptimização espacial das tarefasReplicação de tarefas

(out_key, intermediate_value) list

IN:

OUT:

map(int_key, in_value)

map

reduce(out_key, intermediate_value list)

reduce

IN:

OUT: out_value list

demo!

O Timoteo é pequeno O urso Timoteo é um urso de peluche do IkeaO Fuzy gosta de tremoços

input

map(1,“O Timoteo é pequeno”)

map(2, “O urso Timoteo é um urso de peluche”)

map(3, “O Fuzy gosta de tremoços”)

map!

IN: “O Timoteo é pequeno”

OUT: “O”, 1 “Timoteo”, 1 “é”, 1 “pequeno”, 1

IN:“O urso Timoteo é um urso de peluche”

OUT: “O”, 1 “urso”,1 “Timoteo”, 1 “é”, 1 “um”, 1

“urso”,1 “de”, 1 “peluche”, 1

IN:“O Fuzy gosta de tremoços”

OUT:“O”, 1“Fuzy”, 1“gosta”, 1“de”, 1“tremoços”,1

map 1 map 2 map 3

reduce!

reduce(“pequeno”, [1])

reduce(“O”, [1, 1, 1])

reduce(“urso”, [1,1])

reduce(“Timoteo”,[1, 1])

reduce(“de”,[1, 1])

reduce(“Fuzy”, [1])(...)

reduce 1 reduce 2 reduce 3

IN: “pequeno”, [1]

OUT: “pequeno”, 1

IN: “O”, [1, 1, 1]

OUT: “O”, 3

IN: “urso”, [1,1]

OUT: “urso”, 2

output

“O”, 3“Timoteo”, 2“é”, 2“pequeno”, 1“urso”, 2“um”, 1“de”, 2“peluche”, 1“Fuzy”, 1“gosta”, 1“tremoços”, 1

!(MapReduce)

Fn= Fn-1 + Fn-2 , F0= 0 e F1= 1

!(MapReduce)

Implementações

Disco - open source, jobs Python, NokiaSkynet - open source, Ruby, Adam Pisoni

Hadoop - open source, Java, Apache Foundation

Yahoo! Facebook IBM

Last.fm New York Times

Recordista no Terabyte Sort BenchmarkInclui HDFS, uma implementação do GFS

Hadoop

aws.amazon.com/publicdatasets+

Hadoop+

EC2 =

<3

gil@webreakstuff.com

twitter.com/slitz

http://www.#ickr.com/photos/mhaithaca/157392437/http://www.#ickr.com/photos/udronotto/1517472773/

http://www.#ickr.com/photos/12005027@N07/1342053253/http://www.#ickr.com/photos/hpebley3/2237114065/

http://www.#ickr.com/photos/monkeywobble/2124397478/http://www.#ickr.com/photos/jakobesben/2431770977/