sexta-feira, 5 de março de 2010

MapReduce é o que há!




DESCRIÇÂO

MapReduce é um framework patenteado, introduzido pelo Google para computação distribuída em grandes conjuntos de dados e em clusters(grids) de computadores.







Inspirado pelas funções map() e reduce() comumente usadas na programação funcional [embora os seus efeitos no âmbito do framework MapReduce não é o mesmo nas suas formas originais Bibliotecas MapReduce tem sido escritas em diversas linguagens de programação como C + +, C #, Erlang, Java, Python, Ruby, F #, Haskell,Clojure.

MapReduce é uma estrutura para processamento de grandes conjuntos de dados sobre determinados tipos de problemas distribuiveis utilizando um grande número de computadores (nós), referidos coletivamente como um cluster. Processamento computacional pode ocorrer tanto em dados armazenados em um sistema de arquivos (não estruturadas) ou dentro de um banco de dados (estruturados).


  1. "Map" : O nó mestre(master) recebe os dados de entrada, divide esses dados em pequenos sub-problemas, e os distribui para nós trabalhadores(workers). Um nó trabalhador pode fazer isso de novo, por sua vez, levando a uma estrutura multi-level da árvore de tarefas.A tecnica usada é a Divisão/Conquista amplamente usada em soluções de problemas top-down, utilizando recursão.Os nós trabalhadores processam as pequenas partes do problema, e passa a resposta de volta ao seu nó mestre.
  2. "Reduce": O nó mestre toma então as respostas para todas as sub-problemas e os combina de modo a obter os dados de saída - a resposta para o problema que originalmente o algoritmo tentava resolver. A vantagem de MapReduce é que ele permite o processamento distribuído da função map e das operações reduce. Já que cada operação de mapeamento é independente da outra, todos os map's podem ser executadas em paralelo - embora na prática seja limitado pela fonte de dados e / ou o número de CPUs para esses dados.


Da mesma forma, um conjunto de "reduces" podem executar a fase de redução - tudo o que é necessário é que todas as saídas da operação de map que compartilhem a mesma chave sejam apresentadas ao mesmo redutor, ao mesmo tempo. Embora este processo muitas vezes possa parecer ineficiente em relação aos algoritmos que são mais seqüenciais, MapReduce pode ser aplicada a conjuntos de dados significativamente maior do que aqueles algoritmos usados no mercado de servidores - um grande "farm" de servidores pode usar MapReduce para classificar um petabyte de dados em apenas alguns horas.

A partes cruciais do algoritmos MapReduce podem ser resumidas em:

  • an input reader(Leitor de Dados de Entrada)
  • a Map function(Função de Mapeamento)
  • a partition function(Função de Particionamento de Dados)
  • a compare function(Função de Comparação de Dados)
  • a Reduce function(Função de Redução para achar Resultado Final)
  • an output writer(Escritor de Dados)


O paralelismo também oferece possibilidade de recuperação de falha parcial de servidores e armazenamento durante a operação: se um mapeador ou redutor der falha, o trabalho pode ser remarcado - considerando que os dados de entrada ainda estejam disponíveis.

MapReduce é útil em uma ampla gama de aplicações e arquiteturas , incluindo: "grep distribuido, ordenação distribuida, reversão link web-grafo, vetor de termos por host, estatísticas web de log de acesso, construção de índice invertido, o agrupamento de documentos, aprendizado de máquina ,mineração de dados, tradução de maquina estatística ... "Mais significativamente, quando MapReduce estava terminado, ele foi usado para regenerar completamente índices do Google da World Wide Web, e substituiu o antigos programas que atualizavam o índice e funcionavam com várias análises .

Os inputs e outputs estaveis do algoritmo MapReduce são normalmente armazenados em um sistema de arquivos distribuídos. Os dados intermediarios são normalmente armazenados em um disco local e são pegos remotamente pelo redutor.









Marcadores:

0 Comentários:

Postar um comentário

Assinar Postar comentários [Atom]

<< Página inicial