Google Bigtable

01 · CONTEXTO

Um mapa ordenado para dados estruturados em escala

O Bigtable é um sistema de armazenamento distribuído para dados estruturados, projetado para escalar a petabytes de dados em milhares de servidores comuns. Muitos projetos do Google guardam dados nele, entre eles indexação da web, Google Earth e Google Finance, e o paper fala em mais de sessenta produtos e projetos.

Essas aplicações têm demandas muito diferentes: variam no tamanho dos dados, de URLs a páginas web e imagens de satélite, e na latência, do processamento em lote no backend ao serviço de dados em tempo real. Apesar disso, o paper apresenta o Bigtable como uma solução flexível e de alto desempenho para todos esses produtos.

O Bigtable não oferece um modelo de dados relacional completo. Um Bigtable é um mapa esparso, distribuído, persistente, multidimensional e ordenado, indexado por chave de linha, chave de coluna e timestamp, e cada valor é uma sequência de bytes sem interpretação.

Como os dados ficam ordenados pela chave de linha, o cliente pode escolher as chaves para obter boa localidade nos acessos. Na Webtable, o exemplo do paper, páginas do mesmo domínio ficam em linhas contíguas porque os componentes do nome do host das URLs são invertidos.

Cada célula pode guardar várias versões do mesmo dado, e o cliente pode pedir, por família de colunas, que se mantenham só as últimas n versões ou só as versões novas o bastante. O Bigtable suporta transações de uma única linha, mas não transações gerais entre chaves de linha.

02 · ARQUITETURA

Mestre, servidores de tablets, GFS e Chubby

A implementação tem três componentes principais: uma biblioteca ligada a cada cliente, um servidor mestre e muitos servidores de tablets. O mestre atribui tablets a servidores, detecta a entrada e a expiração de servidores, balanceia a carga e coleta arquivos no GFS. O servidor de tablets atende leituras e escritas dos tablets que carregou e divide os que cresceram demais.

Os dados dos clientes não passam pelo mestre: os clientes falam direto com os servidores de tablets para ler e escrever. Como os clientes não dependem do mestre para saber a localização de um tablet, a maioria nunca se comunica com ele.

Cada tabela começa com um único tablet e é dividida automaticamente em vários ao crescer, cada um com cerca de cem a duzentos megabytes por padrão. Cada servidor de tablets gerencia tipicamente entre dez e mil tablets, e cada tablet é atribuído a um servidor por vez.

O estado persistente de um tablet fica no GFS, que guarda os arquivos de log e de dados. Os dados são gravados no formato SSTable, um mapa persistente, ordenado e imutável de chaves para valores. O Chubby, serviço de travas distribuído, usa o algoritmo Paxos para manter suas réplicas consistentes, e o Bigtable o usa, entre outras tarefas, para garantir no máximo um mestre ativo e descobrir servidores de tablets.

1. O cliente lê e escreve direto no servidor de tablets que atende a faixa de linhas, sem passar pelo mestre.

2. O mestre atribui tablets aos servidores e acompanha quais servidores estão vivos e quais tablets estão sem atribuição.

3. Ao iniciar, o servidor de tablets cria e trava um arquivo no Chubby; o mestre monitora o diretório de servidores para descobri-los.

4. O estado persistente de cada tablet fica no GFS.

5. Se um servidor de tablets perde sua trava exclusiva, ele deixa de servir seus tablets; o mestre, ao obter a trava, apaga o arquivo do servidor e pode mover os tablets dele para o conjunto dos sem atribuição.

6. Se o Chubby fica indisponível por um período prolongado, o Bigtable fica indisponível.

O paper mediu esse efeito em 14 clusters do Bigtable ao longo de 11 instâncias do Chubby. A porcentagem média de horas de servidor em que algum dado não estava disponível por indisponibilidade do Chubby foi de 0,0047%, e no cluster mais afetado foi de 0,0326%.

03 · LOCALIZAÇÃO

Como o cliente acha o tablet certo

A localização dos tablets é guardada em uma hierarquia de três níveis, análoga a uma B+ tree. O primeiro nível é um arquivo no Chubby com a localização do root tablet; o root tablet contém a localização de todos os tablets da tabela especial METADATA; cada tablet da METADATA contém a localização de um conjunto de tablets de usuário.

O root tablet é apenas o primeiro tablet da METADATA, mas é tratado de forma especial para garantir que a hierarquia de localização não tenha mais de três níveis.

1. A biblioteca do cliente guarda em cache as localizações dos tablets.

2. Com o cache vazio, o cliente começa pelo arquivo no Chubby, que aponta o root tablet.

3. O root tablet contém a localização dos tablets da tabela METADATA.

4. O tablet da METADATA contém a localização do tablet de usuário, e o cliente chega ao servidor que o atende.

5. Com o cache desatualizado, o erro só é descoberto quando a consulta falha; então o cliente sobe a hierarquia, o que pode custar até seis idas e voltas pela rede.

6. Para reduzir esse custo no caso comum, a biblioteca faz prefetch: ao ler a METADATA, lê os metadados de mais de um tablet.

Com o cache vazio, o algoritmo de localização exige três idas e voltas pela rede, incluindo uma leitura no Chubby. Como as localizações ficam em memória, não são necessários acessos ao GFS.

04 · ARMAZENAMENTO

Log, memtable, SSTables e compactações

As atualizações de um tablet são confirmadas em um log de commit com registros de redo. As confirmadas mais recentes ficam em memória em um buffer ordenado chamado memtable, e as mais antigas ficam em uma sequência de SSTables.

1. Quando uma escrita chega, o servidor de tablets verifica se ela está bem formada e se o remetente está autorizado.

2. Uma mutação válida é gravada no log de commit; o group commit melhora a vazão de muitas mutações pequenas.

3. Depois de confirmada, a escrita é inserida na memtable.

4. Uma leitura válida é executada sobre uma visão mesclada da memtable e da sequência de SSTables, que pode ser formada com eficiência porque ambas são ordenadas.

5. Quando a memtable atinge um limite, ela é congelada, uma nova é criada e a congelada vira uma SSTable gravada no GFS.

6. Para recuperar um tablet, leem-se seus metadados e a memtable é reconstruída aplicando as atualizações confirmadas desde os pontos de redo no log.

Quando a memtable atinge um limite, uma compactação menor a converte em SSTable. O paper aponta dois objetivos: reduzir o uso de memória do servidor de tablets e reduzir o que precisa ser lido do log de commit na recuperação se o servidor morrer. Leituras e escritas continuam durante as compactações.

SSTables de compactações que não são maiores podem conter entradas de remoção que suprimem dados apagados em SSTables mais antigas ainda vivas; já a compactação maior produz uma SSTable sem informação de remoção nem dados apagados.

Como as SSTables geradas são imutáveis, não é preciso sincronizar acessos ao sistema de arquivos ao lê-las, e a única estrutura mutável acessada por leituras e escritas é a memtable. A imutabilidade também permite dividir tablets rapidamente: os tablets filhos compartilham as SSTables do tablet pai.

O paper compara esse desenho ao da Log-Structured Merge Tree: nos dois sistemas, dados ordenados são mantidos em buffer na memória antes de ir para o disco, e as leituras precisam mesclar dados da memória e do disco.

05 · REFINAMENTOS

Localidade, caches, log único e desempenho

Famílias de colunas podem ser agrupadas em grupos de localidade, e cada grupo gera uma SSTable separada em cada tablet. Separar famílias normalmente não acessadas juntas torna as leituras mais eficientes: na Webtable, metadados da página e conteúdo podem ficar em grupos diferentes. Um grupo também pode ser declarado em memória, o que o paper usa internamente para a família de localização da METADATA.

Os servidores de tablets usam dois níveis de cache: o Scan Cache, de nível mais alto, guarda os pares chave-valor devolvidos pela interface de SSTable; o Block Cache, de nível mais baixo, guarda blocos de SSTable lidos do GFS. Um filtro de Bloom permite perguntar se uma SSTable pode conter dados para um par linha/coluna, e com ele a maioria das consultas a linhas ou colunas inexistentes não precisa tocar o disco.

O servidor de tablets acrescenta as mutações de todos os seus tablets a um único log de commit. Isso traz ganhos significativos de desempenho na operação normal, mas complica a recuperação: quando um servidor morre, seus tablets vão para muitos outros servidores, e uma abordagem seria cada novo servidor ler o log inteiro e aplicar só as entradas de que precisa. O Bigtable evita essas leituras duplicadas ordenando primeiro as entradas do log por chave, de modo que as mutações de um tablet ficam contíguas.

Em um experimento com a Webtable, o esquema de compressão em duas passagens reduziu o espaço em 10 para 1, contra reduções típicas de 3 para 1 ou 4 para 1 do Gzip em HTML. O paper atribui a diferença ao layout das linhas, em que as páginas de um mesmo host ficam próximas.

Nos benchmarks, com valores de 1000 bytes, as leituras aleatórias são mais lentas que todas as outras operações por uma ordem de grandeza ou mais. Cada uma transfere um bloco de SSTable de 64 KB do GFS para o servidor de tablets, e só um valor de 1000 bytes é usado; a maioria das aplicações com esse padrão reduz o tamanho do bloco, tipicamente para 8 KB.

A vazão agregada cresce em mais de um fator de cem quando os servidores de tablets passam de 1 para 500, mas o desempenho não cresce de forma linear. O paper atribui a queda da vazão por servidor ao desequilíbrio de carga, muitas vezes por outros processos disputando CPU e rede.

06 · USO E LIÇÕES

O que a produção ensinou

Em agosto de 2006, o paper conta 388 clusters de Bigtable fora de teste, com cerca de 24.500 servidores de tablets no total. Muitos desses clusters são usados para desenvolvimento e ficam ociosos por períodos significativos.

Dois exemplos mostram o desenho da chave de linha. No Google Analytics, a tabela de cliques brutos mantém uma linha para cada sessão de usuário final, e o nome da linha é uma tupla com o nome do site e a hora de criação da sessão, o que mantém sessões do mesmo site contíguas e em ordem cronológica. No Personalized Search, cada usuário tem um userid único e recebe uma linha nomeada por ele, com uma família de colunas separada para cada tipo de ação.

Os dados do Personalized Search são replicados entre vários clusters de Bigtable para aumentar a disponibilidade e reduzir a latência causada pela distância dos clientes. O time construiu originalmente um mecanismo de replicação no lado do cliente que garantia consistência eventual entre as réplicas; o sistema atual usa um subsistema de replicação embutido nos servidores.

Entre as lições do paper está que sistemas distribuídos grandes são vulneráveis a muitos tipos de falha, não só às partições de rede e falhas fail-stop assumidas por muitos protocolos. Entre as causas observadas estão corrupção de memória e de rede, grande defasagem de relógio, máquinas travadas, partições de rede estendidas e assimétricas e bugs em outros sistemas usados, como o Chubby. Uma das respostas foi adicionar checksums ao mecanismo de RPC.

Outra lição foi sobre transações. O time planejava transações de uso geral na API, mas, sem uso imediato, não as implementou; depois descobriu que a maioria das aplicações precisa apenas de transações de uma única linha. Onde houve pedido de transações distribuídas, o uso mais importante era manter índices secundários, e o paper planeja um mecanismo especializado para isso.

O paper chama de lição mais importante o valor dos designs simples. O primeiro protocolo de pertinência dos servidores de tablets era simples: o mestre emitia leases periodicamente e os servidores se matavam se o lease expirasse; mas ele reduzia significativamente a disponibilidade na presença de problemas de rede. O protocolo resultante dos redesenhos era complexo demais, e o time o descartou por um mais simples, que depende apenas de recursos amplamente usados do Chubby.