Papers
The Google File System
Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung · SOSP 2003 (19th ACM Symposium on Operating Systems Principles), 2003
O problema: armazenamento para as cargas do próprio Google, não acesso a arquivos de uso geral
No início dos anos 2000, o Google precisava armazenar e processar quantidades enormes de dados — páginas da web coletadas, logs, shards de índice — em clusters construídos com máquinas commodity comuns e propensas a falhas, e não com hardware especializado e confiável. Os autores argumentaram que os sistemas de arquivos distribuídos existentes eram projetados em torno de premissas que não correspondiam a essa realidade. Eles partiram, em vez disso, do formato real das cargas do próprio Google: os arquivos eram rotineiramente objetos enormes, de vários gigabytes, em vez de documentos pequenos; a maioria dos arquivos era escrita uma vez, por anexação de novos dados, e depois apenas lida, muitas vezes de forma sequencial por muitas máquinas ao mesmo tempo (um job de análise em lote varrendo um conjunto de dados gigante, por exemplo); e, como o sistema rodaria em milhares de máquinas baratas, a falha de componentes — discos, máquinas, até enlaces de rede — tinha de ser tratada como um evento rotineiro e esperado, e não como uma exceção rara que exige heroísmo. Uma consequência adicional de a anexação ser o padrão de escrita dominante era que muitos clientes poderiam querer anexar ao mesmo arquivo de forma concorrente, e o sistema precisava tornar isso ao mesmo tempo rápido e correto, sem coordenação cara. Em vez de tentar satisfazer uma API de arquivos genérica no estilo POSIX, a equipe optou por co-projetar a API do sistema de arquivos com as aplicações que a usariam, aceitando uma interface fora do padrão em troca de um sistema que se ajustava muito melhor à sua carga real do que uma solução pronta poderia.
A ideia central: um master, muitos chunkservers, chunks grandes de tamanho fixo
O GFS organiza um cluster em um único processo master e muitos chunkservers, acessados por muitos clientes. Os arquivos são divididos em chunks de tamanho fixo — 64 megabytes cada, um tamanho incomumente grande comparado aos blocos típicos de sistemas de arquivos — e cada chunk é armazenado como um arquivo comum no disco local de um chunkserver, replicado (por padrão em três chunkservers) para que perder qualquer uma das máquinas não perca dados. O master é deliberadamente mantido fora do caminho dos dados: ele guarda apenas metadados — o namespace semelhante a um diretório, o mapeamento de cada arquivo para a sua lista ordenada de chunks e a localização atual das réplicas de cada chunk —, enquanto os bytes reais de um chunk fluem diretamente entre clientes e chunkservers. Um cliente que quer ler ou escrever fala primeiro com o master para saber quais chunkservers guardam o chunk relevante, guarda essa resposta em cache por um tempo e depois fala diretamente com os chunkservers, de modo que o master nunca se torna um gargalo para a transferência de dados em massa, embora toda operação de metadados passe por ele. Escolher um tamanho de chunk tão grande e fixo foi, em si, um trade-off deliberado: ele mantém os metadados por chunk do master pequenos o bastante para caberem em memória mesmo para arquivos muito grandes, e permite que um cliente execute muitas operações sequenciais no mesmo chunk com apenas uma requisição inicial ao master, o que se ajusta ao padrão de acesso sequencial e intensivo em anexações para o qual o sistema foi construído.
Um trade-off específico: consistência relaxada em troca de simplicidade e vazão
O GFS não dá às aplicações a visão forte e sempre consistente de um arquivo que um sistema de arquivos tradicional promete. Em vez disso, depois de uma sequência de mutações bem-sucedidas, uma região de um arquivo só tem a garantia de ser 'definida' (defined) — isto é, todos os clientes veem os mesmos dados, refletindo por inteiro uma mutação em particular — quando essa região foi escrita por uma única mutação que teve sucesso sem interferência de escritores concorrentes; escritas concorrentes na mesma região podem deixá-la apenas 'consistente' (todos os clientes veem os mesmos bytes), mas 'indefinida' (esses bytes podem ser uma mistura imprevisível dos dados dos escritores concorrentes), e uma mutação que falha pode deixar uma região inconsistente, com réplicas diferentes do chunk guardando dados diferentes. Para tornar isso viável na prática, o GFS destaca um padrão de escrita para uma garantia mais forte: o record append, uma operação em que o cliente não escolhe o offset de forma alguma — o GFS escolhe um offset e anexa o registro ali de forma atômica, pelo menos uma vez (at least once). Isso favorece produtores concorrentes (por exemplo, muitos processos de trabalho anexando resultados a um mesmo arquivo de saída compartilhado) ao custo de permitir registros duplicados ocasionais ou lacunas de preenchimento (padding), que as aplicações devem tolerar, por exemplo embutindo checksums ou identificadores únicos em cada registro para que um leitor consiga detectar e pular duplicatas ou padding por conta própria. Os autores aceitaram esse contrato mais fraco de forma deliberada, julgando que a maioria de suas aplicações — construídas junto com o sistema de arquivos — poderia ser escrita para lidar com ele, em troca de evitar o custo de coordenação que uma garantia mais forte imporia na escala deles.
Continuar no ar sob falha constante: leases, heartbeats e um master resiliente
Como a falha de componentes é rotina nessa escala, o GFS leva a tolerância a falhas para praticamente todos os mecanismos, em vez de tratá-la como um acessório. Nas escritas, o master concede a uma réplica de um chunk um lease temporário de 'primária' (primary) (60 segundos, renovável enquanto as mutações estão em andamento); a primária é responsável por escolher uma ordem serial para as mutações concorrentes e encaminhar essa ordem às outras réplicas, o que evita que o master precise coordenar cada escrita individual. O master troca mensagens de heartbeat continuamente com cada chunkserver; quando um chunkserver deixa de responder, o master percebe e começa a re-replicar, em outros pontos do cluster, quaisquer chunks que caíram abaixo da contagem-alvo de réplicas, de modo que o sistema se cura sozinho, sem um operador intervir, diante de perdas rotineiras de disco ou de máquina. Cada chunkserver mantém de forma independente checksums dos seus chunks e os verifica a cada leitura, de modo que a corrupção silenciosa de dados em um único disco é detectada localmente, em vez de ser servida a um cliente como se fosse válida. O próprio estado do master — o namespace e o mapeamento de arquivo para chunks — é tornado durável por um log de operações replicado em várias máquinas mais checkpoints periódicos, e um 'shadow master' pode servir leituras de metadados desatualizadas, porém úteis, se o master real estiver temporariamente lento ou inalcançável, de modo que um único master, apesar de ser um só processo, não se torna um ponto único de indisponibilidade total para o cluster inteiro.
Legado: o padrão master/worker com chunks grandes nos sistemas de armazenamento distribuído posteriores
O GFS era um sistema interno do Google, não um produto que outras empresas pudessem adotar diretamente, mas a arquitetura que ele descreveu — um master relativamente leve que guarda os metadados, emparelhado com muitos workers que guardam o armazenamento, blocos de dados grandes e de tamanho fixo e re-replicação em segundo plano guiada por heartbeats — tornou-se um modelo que reapareceu amplamente quando outras organizações precisaram de armazenamento em lote em larga escala semelhante. O exemplo mais direto é o Hadoop Distributed File System (HDFS), um sistema de código aberto construído no Yahoo! e depois amplamente adotado, cuja divisão NameNode/DataNode espelha a divisão master/chunkserver do GFS de perto o bastante para que a documentação do próprio HDFS e seus autores o descrevam como modelado diretamente sobre o projeto do GFS, até o ponto de guardar metadados de checksum junto de cada bloco de dados e replicar os blocos entre máquinas para durabilidade. O próprio Google depois foi além do projeto original de master único no seu sistema sucessor, o Colossus, para remover o teto de escalabilidade que vinha de ter um só master, mas a divisão básica entre serviço de metadados e armazenamento de dados em massa que o GFS popularizou persistiu. De modo mais amplo, a ideia de que as garantias de consistência e a API de um sistema de armazenamento devem ser escolhidas para casar com as aplicações realmente construídas sobre ele, em vez de buscar um padrão genérico, influenciou a forma como sistemas posteriores justificaram trade-offs igualmente não tradicionais em seus próprios projetos.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.