Papers
Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber · USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2006, 2006
O problema: dados estruturados em escala de petabytes para cargas muito diferentes
Dentro do Google, produtos como indexação da web, Google Earth e Google Finance precisavam guardar dados estruturados em escala de petabytes, espalhados por milhares de servidores comuns. As demandas eram muito heterogêneas: o tamanho dos itens ia de URLs a imagens de satélite, e a latência exigida ia de processamento em lote, focado em vazão, até atendimento em tempo real a usuários finais. Os autores relatam que mais de sessenta produtos e projetos do Google já usavam o Bigtable. A decisão central de design foi não oferecer um modelo relacional completo. Em vez disso, o sistema expõe um modelo simples em que linhas e colunas são strings arbitrárias e os valores são bytes não interpretados; quem usa decide como serializar dados estruturados dentro dessas strings. Essa simplicidade dá ao cliente controle dinâmico sobre o formato dos dados e sobre a localidade, isto é, sobre quais dados ficam fisicamente próximos. Parâmetros de esquema também permitem escolher se um conjunto de dados é servido da memória ou do disco. O paper admite que o Bigtable se parece com um banco de dados em várias estratégias de implementação, mas propositalmente tem uma interface diferente, trocando expressividade por escala e desempenho.
O modelo de dados: um mapa ordenado, esparso e multidimensional
O Bigtable define uma tabela como um mapa ordenado, esparso, distribuído e persistente, indexado por chave de linha, chave de coluna e timestamp; cada valor é um array de bytes sem interpretação. As chaves de linha são strings arbitrárias e os dados são mantidos em ordem lexicográfica por essa chave. Toda leitura ou escrita sob uma única chave de linha é atômica, não importa quantas colunas envolva, o que facilita raciocinar sobre atualizações concorrentes na mesma linha. O intervalo de linhas da tabela é particionado dinamicamente em tablets, a unidade de distribuição e de balanceamento de carga. Como linhas vizinhas ficam juntas, o cliente escolhe chaves que deem boa localidade: no exemplo do paper, o nome do host da URL é invertido, de modo que páginas do mesmo domínio ficam contíguas e certas análises por host ou domínio ficam mais eficientes. As colunas são agrupadas em famílias, a unidade básica de controle de acesso e de contabilização de memória e disco; a família precisa ser criada antes do uso, e depois dela qualquer qualificador pode ser usado. Cada célula pode ter várias versões indexadas por timestamp de 64 bits, guardadas da mais recente para a mais antiga. Por família, o cliente pode pedir coleta automática de versões antigas, mantendo só as últimas n ou só as recentes o bastante.
Arquitetura: tablets, master, Chubby e a hierarquia de localização
O Bigtable se apoia em outras peças da infraestrutura do Google. O GFS guarda o log e os arquivos de dados; o formato SSTable armazena os dados como um mapa imutável e ordenado de chaves para valores; o Chubby, um serviço de locks distribuído e altamente disponível, garante no máximo um master ativo, guarda o ponto de partida para localizar os dados, ajuda a descobrir servidores de tablets vivos e guarda informações de esquema. A implementação tem uma biblioteca ligada a cada cliente, um master e muitos servidores de tablets. O master atribui tablets a servidores, detecta a entrada e a saída deles, balanceia a carga e trata mudanças de esquema. Cada servidor de tablets atende leituras e escritas dos tablets que carregou e divide os que crescem demais. Os dados dos clientes não passam pelo master, e a maioria dos clientes nem depende dele para saber onde os dados estão, então ele fica pouco carregado. Para localizar um tablet, o paper usa três níveis, análogos a uma árvore B+: um arquivo no Chubby aponta para o tablet raiz, que aponta para tablets de uma tabela especial chamada METADATA, que por sua vez localizam os tablets de usuário. O cliente mantém cache dessas localizações; com o cache vazio, a busca custa três idas e voltas de rede.
Escrita, leitura e compactações: memtable, log e SSTables imutáveis
O estado persistente de um tablet fica no GFS. Toda escrita válida é primeiro gravada em um log de commit, com registros de redo, e depois inserida na memtable, um buffer ordenado em memória; as atualizações mais antigas ficam em uma sequência de SSTables. Uma leitura é executada sobre a visão mesclada da memtable e das SSTables, algo eficiente porque tudo está ordenado. Para recuperar um tablet, o servidor lê seus metadados, carrega os índices das SSTables e reconstrói a memtable reaplicando as atualizações do log desde os pontos de redo. Quando a memtable atinge um limite, ela é congelada, uma nova é criada e a antiga é gravada como SSTable no GFS: a compactação menor (minor), que reduz o uso de memória e a quantidade de log a reler após falha. Como cada uma cria uma SSTable nova, compactações de mesclagem (merging) rodam em segundo plano para limitar esse número. A compactação maior (major) reescreve todas as SSTables em exatamente uma, sem entradas de exclusão nem dados apagados, o que libera recursos e garante que dados apagados de fato desapareçam, algo importante para serviços com dados sensíveis. Como as SSTables são imutáveis, a única estrutura mutável acessada por leituras e escritas é a memtable, o que simplifica o controle de concorrência.
Refinamentos e trade-offs: localidade, compressão, Bloom filters e escopo transacional
O paper descreve refinamentos que tornaram o sistema viável. Grupos de localidade permitem agrupar famílias de colunas normalmente lidas juntas; cada grupo gera uma SSTable própria por tablet, e um grupo pode ser declarado em memória. A compressão é escolhida pelo cliente por grupo e aplicada por bloco de SSTable, de modo que pequenas partes podem ser lidas sem descomprimir o arquivo inteiro, ao custo de algum espaço. Num experimento com páginas web, um esquema de duas passadas alcançou redução de 10 para 1, bem acima dos 3 para 1 ou 4 para 1 típicos do Gzip em HTML, porque páginas do mesmo host ficam adjacentes. Servidores de tablets usam dois níveis de cache (Scan Cache e Block Cache), e filtros de Bloom opcionais evitam acessos a disco para linhas e colunas que não existem. Cada servidor usa um único log de commit para todos os seus tablets, em vez de um por tablet, para evitar muitos arquivos simultâneos e preservar o group commit; o custo é uma recuperação mais complexa, resolvida ordenando o log por tablet. Em garantias, o Bigtable oferece transações atômicas de leitura-modificação-escrita dentro de uma única linha, mas não transações gerais entre linhas diferentes.
Escala medida, uso real e legado
Na avaliação, os autores variaram o número de servidores de tablets de 1 a 500 e mediram leituras e escritas de valores de 1000 bytes. A vazão agregada cresceu mais de cem vezes nesse intervalo, mas não linearmente: a vazão por servidor caiu bastante ao sair de 1 para 50 servidores, em parte por desbalanceamento de carga e porque o rebalanceamento é limitado para não mover tablets demais. O pior escalonamento foi o de leituras aleatórias, porque cada leitura de 1000 bytes traz pela rede um bloco de SSTable de 64 KB, saturando os links de 1 Gbit; por isso muitas aplicações reduzem o tamanho do bloco. Em agosto de 2006, o paper contava 388 clusters Bigtable fora de teste, com cerca de 24.500 servidores de tablets no total. Os exemplos de uso incluem o Google Analytics, com uma tabela de cliques brutos de cerca de 200 TB, e o Google Earth, com uma tabela de cerca de 70 TB de imagens servidas do disco. Como legado, o projeto Apache HBase se descreve como modelado a partir do Google Bigtable. O padrão de memtable, log, SSTables imutáveis e compactações aparece em outros sistemas de armazenamento, e a escolha da chave de linha continua sendo a decisão de modelagem que define localidade e distribuição de carga.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.