o problema
Em 2006 o Google tinha dados que não cabiam em nenhuma categoria confortável: URLs, páginas web, imagens de satélite, sessões de usuário do Analytics, histórico de busca personalizada. Volumes de petabytes, milhares de máquinas commodity, e requisitos de latência que iam de processamento em lote noturno a servir dezenas de milhares de consultas por segundo por datacenter. Um banco paralelo relacional resolvia parte disso, mas com um contrato que ninguém precisava — modelo relacional completo, transações gerais — e um custo que todo mundo pagava.
O outro extremo, distributed hash table e par chave-valor puro, os autores descartam explicitamente: é limitado demais para servir de único bloco de construção. Faltava o meio-termo: algo mais rico que chave-valor, mais simples que SQL, e principalmente algo em que o cliente pudesse raciocinar sobre onde o byte vai parar no disco.
a ideia
Bigtable é um mapa ordenado, esparso, distribuído, persistente e multidimensional. A chave é a tripla (linha, coluna, timestamp) e o valor é um array de bytes que o sistema não interpreta. Linhas ficam em ordem lexicográfica; colunas são agrupadas em column families, que são a unidade de controle de acesso, de contabilidade e de compressão; cada célula guarda várias versões, com política de garbage collection por family (últimas n versões, ou versões dos últimos sete dias).
O truque está na ordem das linhas. Como o mapa é ordenado, o cliente escolhe a chave para produzir a localidade que quer. Na Webtable, maps.google.com/index.html vira com.google.maps/index.html: todas as páginas do domínio ficam vizinhas, uma varredura por domínio toca poucas máquinas, e o compressor de janela longa encontra o mesmo cabeçalho repetido mil vezes. O schema aqui não descreve o significado dos dados, descreve o layout físico.
como funciona
A tabela é fatiada por faixa de linhas em tablets de 100 a 200 MB, que são a unidade de distribuição e balanceamento. Há um master (atribui tablets, detecta servidores, coleta lixo no GFS) e muitos tablet servers, com dez a mil tablets cada. O cliente nunca passa pelo master para ler ou escrever: ele consulta uma hierarquia de localização de três níveis — um arquivo no Chubby aponta para o root tablet, que aponta para os tablets da tabela METADATA, que apontam para os tablets do usuário — e mantém cache dessas localizações, com prefetch.
Dentro de um tablet, escrita vai para um commit log de redo records no GFS e depois para uma memtable ordenada em memória. Leitura é feita sobre a visão mesclada da memtable com uma sequência de SSTables — arquivos imutáveis de mapa ordenado, com blocos de 64 KB e índice no fim. Quando a memtable estufa, ela é congelada e virada em SSTable (minor compaction); periodicamente uma merging compaction junta vários SSTables, e a major compaction reescreve tudo em um só, que é onde os registros de deleção finalmente somem e o dado apagado deixa o sistema.
A imutabilidade do SSTable é o que paga a simplicidade: não há sincronização para ler do disco, o único dado mutável é a memtable (copy-on-write por linha), e um split de tablet é barato porque os filhos compartilham os SSTables do pai. Há um único commit log por tablet server, não por tablet; na recuperação, o log é particionado em segmentos de 64 MB e ordenado em paralelo por chave (tabela, linha, sequência) para que cada servidor novo leia só o seu pedaço.
o que isso custou
Não há transação entre linhas. O paper admite isso e conta a decisão: eles planejavam transações gerais, não tinham uso imediato, adiaram — e depois, olhando as aplicações reais, viram que quase todas queriam só read-modify-write de uma linha. O caso legítimo que sobrou foi índice secundário, que ficou de fora com promessa de mecanismo especializado.
A dependência é total. Bigtable precisa de GFS para dados e log, de Chubby para master único, descoberta de servidores e schema, e de um gerenciador de cluster. Chubby indisponível por tempo suficiente é Bigtable indisponível: 0,0047% das horas-servidor em média nos 14 clusters medidos, 0,0326% no cluster mais afetado.
O escalonamento é sublinear. De 1 para 500 tablet servers, o throughput agregado sobe cerca de cem vezes, não quinhentas; a leitura aleatória é o pior caso, porque cada valor de 1.000 bytes custa um bloco de 64 KB vindo do GFS e satura os links de 1 Gbps. Os autores também registram que a interface confunde quem chega de banco relacional.
E os modos de falha que quebraram o sistema na prática não foram os do livro-texto: corrupção de memória e de rede, clock skew grande, máquinas travadas, partições assimétricas, bug em sistema de terceiros, estouro de quota do GFS.
onde isso aparece hoje
Bigtable é a peça de cima de uma pilha inteira do Google: assenta sobre The Google File System, coordena por The Chubby lock service for loosely-coupled distributed systems e serve de entrada e saída para jobs de MapReduce. A estrutura memtable mais SSTables mais compaction é reconhecida pelos próprios autores como parente do The Log-Structured Merge-Tree (LSM-Tree), e é o desenho que sustenta os engines de armazenamento modernos. O filtro que evita o disco em lookup de linha inexistente vem direto de Space/Time Trade-offs in Hash Coding with Allowable Errors, e a separação de column families em locality groups é comparada no paper ao armazenamento por coluna de C-Store: A Column-oriented DBMS.
Do lado do que veio depois: Cassandra: A Decentralized Structured Storage System declara o modelo de dados do Bigtable como origem do seu, e combina esse modelo com a replicação sem master de Dynamo: Amazon’s Highly Available Key-value Store. Dentro do Google, a lacuna que este paper deixa aberta — transação entre linhas — é exatamente o assunto dos trabalhos seguintes: Large-scale Incremental Processing Using Distributed Transactions and Notifications e Megastore: Providing Scalable, Highly Available Storage for Interactive Services constroem transação em cima do Bigtable, e Spanner: Google’s Globally-Distributed Database refaz a camada de baixo para entregá-la de fábrica.