MapReduce no Windows Azure

Hoje vou descrever a vocês um pouco do que é o famoso MapReduce e como podemos simulá-lo no Azure.

Formalmente, o framework foi apresentado em um artigo de 2004 na OSDI por Jeff Dean e Sanjay Ghemawat, ambos da Google, e é hoje usado por vários sites (Facebook, Yahoo, e muitos outros).

O MapReduce é um framework para processamento em paralelo baseado em um meta-algoritmo. Meta-algoritmos são padrões de resolução de problemas, como os conhecidos divisão-e-conquista, backtracking e outros.

No caso do MapReduce a idéia foi a de implementar um padrão simples e bem conhecido que, por sua vez, já era realizado há muito no Lisp e no C++ (neste, com a API do MPI (Message Passing Interface) – usada em computação em grid, como no Windows HPC 2008).

A idéia é simples: se quisermos aumentar o paralelismo de uma operação, um processo Mestre deve dividir a tarefa em diversas partições, uma para cada processo Trabalhador. Chamamos este passo de Map.

Em seguida, cada processo retorna seu resultado parcial para o processo Mestre, que aglutina e retorna todas as respostas a quam requisitou o processamento. Chamamos este passo de Reduce.

Nada como um bom exemplo (neste caso, retirado do livro The Art of Concurrency): Imagine o processo de contar quantas letras ‘e’ existem numa frase. Ao passar para o computador mestre a frase “The quick brown fox jumps over the lazy dog.” ele deverá criar e enviar à cada Trabalhador um conjunto de pares com uma parte da frase e a letra a ser procurada (uma ordem para computação). Veja a figura abaixo.

 

Feito isto, cada Trabalhador faz sua procura em paralelo retornando seus resultados. Ao Mestre cabe juntar os resultados parciais e calcular o resultado final.

Pronto! Simples, elegante, podendo alcançar um altíssimo grau de paralelismo.

Realizar isto no Azure é simples também. Mostrei no TechEd um pouco do código exemplo que consegui com o Simon Guest e vale a pena falar dele aqui também.

O exemplo trata de achar todos os números primos dentro de uma série (range) de inteiros.

Para isto são utilizados vários processos: um processo com o papel Web e vários com o papel Worker.

Para a comunicação entre estes, são criadas duas filas e duas tabelas.

A primeira tabela guarda as ordens de serviço de acordo com o nó Trabalhador. Caberá a cada trabalhador fazer uma query para pegar a sua ordem e processá-la.

A segunda tabela é utilizada para que os nós Trabalhadores coloquem seus resultados. Caberá ao processo mestre fazer a query para consolidar os resultados processados pelos Workers.

Quanto às filas, elas são usadas para dar a cada nodo um número (node assignment), dar a ordem de início do processamento em paralelo aos Trabalhadores e, por fim, avisar ao Mestre que o processamento terminou.

Deixo aqui como exercício para vocês implementarem este processo. É simples e é um bom exercício.

Para facilitar, aqui vai uma função que indica se um número é primo ou não.

public bool IsPrime(int number)
{
    if (number == 0||number==1)
        return false;
    else
    {
        for (int i = 2; i * i <= number; i++)
        {
            if (number % i == 0)
            {
                return false;
            }
        }
        return true;
    }
}

Bom trabalho e abraços