Google GFS e MapReduce

01 · CONTEXTO

Dois papers, uma mesma aposta em máquinas comuns

O GFS e o MapReduce nasceram no mesmo ambiente: clusters grandes de máquinas comuns, onde falhar é rotina. O paper do GFS parte justamente daí, ao tratar falhas de componente como a norma, não a exceção. O paper do MapReduce descreve clusters de centenas ou milhares de máquinas, nos quais falhas de máquina são comuns.

Os dois também compartilham a visão da carga. No GFS, os arquivos são enormes pelos padrões tradicionais e na maioria mudam por anexação de dados novos, sendo depois apenas lidos, muitas vezes de forma sequencial. O MapReduce esconde numa biblioteca a paralelização, a tolerância a falhas, a distribuição de dados e o balanceamento de carga.

O elo entre os dois está escrito no paper do MapReduce: os dados de entrada são gerenciados pelo GFS e ficam nos discos locais das máquinas do cluster. Este caso mostra como cada paper resolve uma camada e como as decisões de um se apoiam nas do outro. Segundo o mesmo paper, o armazenamento do cluster usa um sistema de arquivos distribuído desenvolvido internamente.

02 · GFS

Metadados no mestre, dados nos chunkservers

Um cluster GFS tem um único mestre e vários chunkservers, e é acessado por vários clientes. Os arquivos são divididos em chunks de tamanho fixo; cada chunk fica guardado como arquivo comum no disco local de um chunkserver e é replicado em vários deles, com três réplicas por padrão.

O mestre mantém todos os metadados, incluindo o mapeamento de arquivos para chunks e a localização atual dos chunks. Os dados em si nunca passam por ele: o cliente pergunta ao mestre onde está o chunk e depois conversa direto com os chunkservers.

1. O cliente converte o nome do arquivo e o deslocamento em um índice de chunk e envia ao mestre o nome do arquivo e esse índice.

2. O mestre responde com o identificador do chunk e a localização das réplicas.

3. O cliente guarda a resposta em cache e envia o pedido a uma das réplicas, provavelmente a mais próxima.

4. Os bytes do chunk fluem entre o chunkserver e o cliente; os dados do arquivo não passam pelo mestre.

5. Leituras seguintes do mesmo chunk não voltam ao mestre até a informação em cache expirar ou o arquivo ser reaberto.

O chunk grande é uma escolha deliberada. Leituras e escritas no mesmo chunk exigem só um pedido inicial ao mestre pela localização, e o chunk grande reduz o tamanho dos metadados, o que permite mantê-los em memória. O paper afirma que o mestre mantém menos de 64 bytes de metadados para cada chunk de 64 MB.

03 · O MESTRE ÚNICO

O que o mestre único compra e o que ele custa

Os autores justificam o mestre único pela simplicidade: ele simplifica o projeto e permite decisões sofisticadas de posicionamento de chunks, e essas decisões, de posicionamento e de replicação, usam conhecimento global. A contrapartida é que o envolvimento do mestre em leituras e escritas precisa ser mínimo para ele não virar gargalo. O paper afirma optar pela abordagem centralizada para simplificar o projeto, aumentar a confiabilidade e ganhar flexibilidade.

O mestre persiste o espaço de nomes e o mapeamento de arquivos para chunks por meio de um log de operações no disco local, replicado em máquinas remotas, e esse log é o único registro persistente dos metadados. Já a localização dos chunks ele não guarda de forma persistente: consulta os chunkservers na inicialização, e o paper explica que o chunkserver tem a palavra final sobre quais chunks existem em seus discos.

Para a disponibilidade, o log de operações e os checkpoints do mestre são replicados em várias máquinas. Se a máquina ou o disco do mestre falha, infraestrutura de monitoramento externa ao GFS inicia um novo processo mestre em outro lugar com o log replicado. Além disso, shadow masters dão acesso somente leitura ao sistema de arquivos mesmo com o mestre primário fora do ar.

1. Suponha que um chunkserver, o B, fique indisponível.

2. O mestre acompanha os chunkservers por mensagens periódicas de HeartBeat; quando o número de réplicas disponíveis cai abaixo da meta, ele re-replica o chunk.

3. O mestre instrui um chunkserver a copiar os dados diretamente de uma réplica válida existente; a cópia flui entre chunkservers.

Na re-replicação, o mestre instrui um chunkserver a copiar os dados diretamente de uma réplica válida existente.

04 · MAPREDUCE

Duas funções do usuário e um master de tarefas

O usuário escreve duas funções. Map recebe um par de entrada e produz um conjunto de pares chave/valor intermediários; a biblioteca agrupa todos os valores intermediários da mesma chave e os passa à função Reduce, que os combina num conjunto possivelmente menor. No exemplo de contagem de palavras, o map emite cada palavra com a contagem de ocorrências e o reduce soma as contagens emitidas para cada palavra.

A biblioteca divide a entrada em pedaços e inicia várias cópias do programa no cluster. Uma delas é especial, o master; as demais são workers que recebem trabalho dele. O master escolhe workers ociosos e atribui a cada um uma tarefa de map ou de reduce.

1. O programa do usuário divide a entrada e inicia várias cópias de si no cluster; uma delas é o master.

2. O master escolhe workers ociosos e atribui a cada um uma tarefa de map ou de reduce.

3. Cada worker de map lê o conteúdo do seu split da entrada, que é gerenciada pelo GFS.

4. Os pares intermediários são gravados periodicamente no disco local do worker de map, particionados em regiões; o master recebe os locais e os encaminha aos workers de reduce.

5. O worker de reduce lê esses dados por chamada remota e os ordena por chave.

6. O worker de reduce anexa a saída da função Reduce a um arquivo de saída da sua partição, no sistema de arquivos global.

O master guarda, para cada tarefa de map e de reduce, o estado e a identidade da máquina worker, e é o canal pelo qual a localização dos dados intermediários chega aos workers de reduce.

05 · COMO SE COMPLEMENTAM

Localidade, falhas e saída: onde um paper encaixa no outro

A largura de banda de rede é um recurso relativamente escasso no ambiente do paper do MapReduce. O GFS guarda várias cópias de cada bloco em máquinas diferentes, e o master do MapReduce leva em conta a localização dos arquivos de entrada para escalar a tarefa de map numa máquina que contém uma réplica. Se não conseguir, tenta escalar perto de uma réplica, por exemplo num worker na mesma switch de rede.

1. O GFS guarda cópias de cada bloco em máquinas diferentes; aqui, a máquina A tem uma réplica do bloco de entrada.

2. O master do MapReduce considera a localização do arquivo de entrada e tenta escalar a tarefa de map numa máquina que tenha uma réplica.

3. Se não conseguir, tenta escalar a tarefa perto de uma réplica, por exemplo num worker na mesma switch de rede da máquina com os dados.

4. Quando isso vale para boa parte dos workers do cluster, a maior parte da entrada é lida localmente e não consome banda de rede.

A tolerância a falhas também se divide por camada. No GFS, cada chunk é replicado em vários chunkservers, e o mestre re-replica um chunk assim que o número de réplicas disponíveis cai abaixo da meta definida pelo usuário. No MapReduce, o modelo funcional permite usar a reexecução como mecanismo principal de tolerância a falhas: tarefas de map concluídas são reexecutadas após uma falha porque sua saída está no disco local da máquina que falhou, enquanto tarefas de reduce concluídas não precisam ser reexecutadas porque sua saída está num sistema de arquivos global.

Há ainda um ponto de contato na gravação. O MapReduce confia na operação atômica de renomeação do sistema de arquivos subjacente para garantir que o estado final contenha só os dados de uma execução da tarefa de reduce. No lado do GFS, as mutações do espaço de nomes, como a criação de arquivo, são atômicas e tratadas exclusivamente pelo mestre, e um padrão típico de escrita é gerar o arquivo do início ao fim e renomeá-lo atomicamente para o nome permanente.

O paper do MapReduce cita um uso que junta as duas camadas: no sistema de indexação de produção, os documentos rastreados ficam guardados como arquivos no GFS, e o processo roda como uma sequência de cinco a dez operações MapReduce.

06 · LIMITES E LIÇÕES

O que os dois pagam pelo coordenador único

No MapReduce, o master precisa tomar O(M + R) decisões de escalonamento. O paper cita uma execução típica com M igual a 200.000 e R igual a 5.000, usando 2.000 máquinas worker, o que mostra o tamanho do trabalho de coordenação.

Nos dois sistemas há um coordenador único, e os papers tratam a falha dele de modos diferentes, como mostra a tabela anterior: o GFS replica o estado do mestre e o MapReduce, na implementação descrita, aborta a computação.