Papers
Spanner: Google's Globally-Distributed Database
James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, Dale Woodford · OSDI (10th USENIX Symposium on Operating Systems Design and Implementation), 2012
O problema: escalar globalmente sem abrir mão de transações e consistência forte
Dentro do Google, muitas aplicações usavam o Bigtable, mas recebiam queixas constantes de times que precisavam de esquemas complexos e em evolução, ou de consistência forte mesmo com replicação em área ampla. O Bigtable só oferecia replicação eventualmente consistente entre datacenters e não tinha transações entre linhas. Outras equipes escolhiam o Megastore, que tinha um modelo semi-relacional e replicação síncrona, mas pagavam o preço de uma vazão de escrita relativamente baixa. O primeiro cliente do Spanner foi o F1, uma reescrita do backend de anúncios do Google, que precisava ao mesmo tempo de escala horizontal, de transações e de consistência forte entre réplicas. O paper descreve o Spanner como um banco escalável, multiversionado, distribuído globalmente e com replicação síncrona, que evoluiu de um armazém chave-valor versionado, parecido com o Bigtable, para um banco temporal multiversão: os dados ficam em tabelas semirrelacionais, cada versão recebe automaticamente o timestamp do seu commit, versões antigas passam por coleta de lixo configurável, e a aplicação pode ler dados em instantes passados. Os autores também defendem uma posição de engenharia: é melhor deixar os programadores lidarem com gargalos de desempenho causados pelo uso excessivo de transações do que obrigá-los a codificar sempre sem transações. Segundo eles, rodar commit em duas fases sobre Paxos atenua os problemas de disponibilidade tradicionalmente atribuídos ao 2PC.
Arquitetura: zonas, grupos Paxos e diretórios
Uma instalação do Spanner é chamada de universo e é organizada em zonas, que são a unidade de implantação administrativa e de isolamento físico, e também o conjunto de locais onde os dados podem ser replicados. Cada zona tem um zonemaster, que atribui dados aos spanservers, e entre uma centena e vários milhares de spanservers, que servem os dados aos clientes. Cada spanserver cuida de entre 100 e 1000 tablets, estruturas que mapeiam (chave, timestamp) para valores e guardam seu estado em arquivos e em um log de escrita antecipada no sistema de arquivos distribuído Colossus. Para replicar, cada tablet tem uma máquina de estados Paxos; o conjunto de réplicas de um tablet forma um grupo Paxos. O Paxos do Spanner usa líderes de longa duração, baseados em leases de tempo cuja duração padrão é de 10 segundos. Escritas precisam iniciar o protocolo Paxos no líder, enquanto leituras podem ser servidas por qualquer réplica suficientemente atualizada. O líder mantém uma tabela de locks para o controle de concorrência e um gerenciador de transações, usado quando uma transação envolve mais de um grupo Paxos. Sobre isso, o Spanner oferece o conceito de diretório: um conjunto de chaves contíguas com um prefixo comum, que é a unidade de posicionamento de dados. Todos os dados de um diretório compartilham a mesma configuração de replicação, e o sistema move diretórios entre grupos Paxos, inclusive enquanto clientes operam, para balancear carga ou aproximar dados de quem os acessa. Aplicações controlam onde cada dado fica, por exemplo guardando os dados de cada usuário em seu próprio diretório, com réplicas na região escolhida.
TrueTime: expor a incerteza do relógio em vez de escondê-la
A peça central do Spanner é a API TrueTime, que representa o tempo como um intervalo com incerteza limitada, em vez de um único instante. A chamada TT.now() devolve um TTinterval com os extremos earliest e latest, garantidos de conter o tempo absoluto em que a chamada ocorreu. TT.after(t) diz se t definitivamente já passou, e TT.before(t) diz se t definitivamente ainda não chegou. A implementação usa dois tipos de referência de tempo com modos de falha diferentes, GPS e relógios atômicos. Em cada datacenter há um conjunto de máquinas time master, a maioria com receptores GPS e as demais (chamadas Armageddon masters) com relógios atômicos, e cada máquina roda um daemon timeslave que consulta vários masters, descarta os que mentem e sincroniza o relógio local. Entre sincronizações, o daemon anuncia uma incerteza que cresce lentamente, derivada de uma taxa de deriva do relógio aplicada de forma conservadora, de 200 microssegundos por segundo, com consulta a cada 30 segundos. Em produção, essa incerteza (epsilon) varia em dente de serra de cerca de 1 a 7 ms a cada intervalo de consulta, o que dá uma média em torno de 4 ms na maior parte do tempo. A ideia-chave é que a correção das garantias do Spanner depende desses limites: se a incerteza cresce, o sistema fica mais lento porque precisa esperar, mas continua correto.
Consistência externa: commit timestamps, commit wait e 2PC entre grupos
O Spanner atribui timestamps globalmente significativos às transações, e a ordem desses timestamps respeita a ordem de serialização. Ele garante consistência externa, equivalente a linearizabilidade: se uma transação T1 faz commit antes de T2 começar, então o timestamp de commit de T1 é menor que o de T2. Isso vale mesmo que as transações sejam distribuídas. Duas regras do protocolo sustentam a garantia. A regra Start diz que o líder coordenador atribui a uma escrita um timestamp de commit não menor que TT.now().latest, calculado depois que o pedido de commit chega a ele. A regra Commit Wait diz que o coordenador não deixa clientes enxergarem os dados daquela transação até que TT.after(timestamp de commit) seja verdadeiro, ou seja, até que o timestamp esteja garantidamente no passado. A espera esperada é de pelo menos duas vezes a incerteza média, e em geral se sobrepõe à comunicação do Paxos. Transações de leitura e escrita usam locking em duas fases, com wound-wait para evitar deadlocks. Se a transação toca um único grupo Paxos, o líder basta; se toca vários, os líderes desses grupos executam commit em duas fases: cada participante registra via Paxos um registro de prepare com um timestamp, o líder de um dos grupos atua como coordenador, escolhe o timestamp final, espera o commit wait e registra o commit, e todos aplicam no mesmo timestamp antes de liberar os locks. Como o estado do gerenciador de transações fica dentro do grupo Paxos, ele é replicado.
Leituras sem lock, trade-offs e evidências de produção
Como cada versão tem um timestamp, o Spanner oferece leituras que não bloqueiam escritas. Uma transação somente leitura, declarada previamente como sem escritas, executa em um timestamp escolhido pelo sistema, sem locks, e pode ser servida por qualquer réplica suficientemente atualizada. Cada réplica mantém um safe time, o maior timestamp até o qual ela está atualizada, e só atende leituras em timestamps menores ou iguais a ele. Leituras de snapshot, em um timestamp ou limite de obsolescência dado pelo cliente, seguem a mesma lógica. O mesmo mecanismo permite mudanças atômicas de esquema: a transação de mudança recebe um timestamp explícito no futuro, registrado na fase de prepare, e leituras e escritas com timestamp anterior prosseguem, enquanto as posteriores esperam por ela. Nos benchmarks do paper, a latência de escrita fica em torno de 14 ms e a de leitura em torno de 1,3 ms, e a vazão de leituras de snapshot cresce quase linearmente com o número de réplicas. Em testes de disponibilidade, matar uma zona inteira sem aviso derrubou a taxa de leituras quase a zero, e a recuperação levou cerca de 10 segundos, ligada à duração dos leases dos líderes. O F1 usa cinco réplicas, duas na costa oeste e três na leste dos EUA, e os autores relatam que o failover automático foi quase invisível para eles. Como trabalho futuro, o paper cita itens como mais otimizações de desempenho e resharding automático por carga.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.