Google Spanner e TrueTime

01 · CONTEXTO

Por que o Spanner existiu

Antes do Spanner, os times do Google que precisavam de um banco com alcance global esbarravam em dois sistemas imperfeitos. O Bigtable tinha muitos usuários, mas gerava queixas de quem tinha esquemas complexos e em evolução ou queria consistência forte com replicação em área ampla; além disso, só oferecia replicação eventualmente consistente entre datacenters. O Megastore tinha modelo semirrelacional e replicação síncrona, mas com vazão de escrita relativamente baixa.

O primeiro cliente foi o F1, uma reescrita do backend de anúncios do Google, que vinha de um MySQL fatiado manualmente. O último reshard desse banco levou mais de dois anos de esforço intenso, e o F1 precisava de semântica transacional forte, o que tornava impraticáveis os outros sistemas NoSQL.

O Spanner responde fatiando os dados em vários conjuntos de máquinas de estado Paxos espalhados pelo mundo, com replicação síncrona, e oferecendo transações distribuídas com consistência externa. Segundo o paper, é o primeiro sistema a fazer isso em escala global.

02 · ARQUITETURA

Zonas, grupos Paxos e diretórios

Uma instalação do Spanner é organizada em zonas. A zona é a unidade de implantação administrativa e o conjunto de zonas é também o conjunto de locais para onde os dados podem ser replicados. Cada zona tem um zonemaster, que atribui dados aos spanservers, e entre cem e alguns milhares de spanservers, que servem os dados aos clientes.

Cada spanserver implementa uma máquina de estado Paxos sobre cada tablet, e o conjunto de réplicas é um grupo Paxos. Escritas começam no líder; leituras acessam o estado direto da tablet em qualquer réplica suficientemente atualizada. No líder fica ainda a tabela de travas usada no controle de concorrência.

1. A aplicação pergunta ao proxy de localização qual spanserver atende os dados que ela quer.

2. O proxy aponta para a réplica líder do grupo Paxos responsável pelos dados.

3. Uma escrita vai ao líder, que trava as chaves envolvidas.

4. O líder replica a escrita para as seguidoras em outras zonas; com a maioria dos votos, ela é confirmada.

5. Uma leitura pode ser atendida por qualquer réplica suficientemente atualizada, sem passar pelo líder.

6. Em segundo plano, o placement driver move diretórios entre grupos quando é preciso equilibrar carga ou cumprir restrições de replicação.

Para controlar localidade, o Spanner agrupa chaves contíguas de mesmo prefixo em diretórios. O diretório é a unidade de colocação: todos os seus dados têm a mesma configuração de replicação, e é diretório por diretório que os dados se movem entre grupos Paxos, mesmo com operações de clientes em andamento. A aplicação pode, por exemplo, guardar os dados de cada usuário em um diretório próprio, de modo que um usuário tenha réplicas na Europa e outro na América do Norte.

03 · TEMPO

TrueTime: relógio com incerteza declarada

Para ordenar transações no mundo todo, o Spanner atribui timestamps de commit com significado global. A garantia pretendida é a consistência externa, equivalente à linearizabilidade: se uma transação termina antes de outra começar, o timestamp da primeira é menor que o da segunda. Relógios comuns não dizem quão errados estão; o TrueTime é a API que expõe essa incerteza.

TT.now() devolve um intervalo, com os extremos earliest e latest, que garantidamente contém o instante absoluto da chamada. TT.after(t) só é verdadeiro quando t definitivamente já passou. É essa honestidade sobre o erro que permite raciocinar sobre ordem sem supor relógios perfeitos.

1. O spanserver pede o tempo ao daemon local e recebe um intervalo, não um instante único.

2. O daemon consulta vários masters, tanto de GPS quanto de relógio atômico, e descarta os que divergem dos demais.

3. Os dois tipos de referência existem porque falham de modos diferentes: uma falha de GPS não derruba, por si só, os relógios atômicos.

4. Entre duas consultas, o daemon anuncia uma incerteza que cresce devagar, e o spanserver passa a trabalhar com um intervalo cada vez mais largo.

5. Se os masters ficam indisponíveis, a incerteza sobe e o spanserver tem de esperar mais; a correção é preservada, mas a latência piora.

O TrueTime usa dois tipos de referência de tempo, GPS e relógios atômicos, porque eles falham de modos diferentes. Os masters restantes, chamados de Armageddon masters, têm relógios atômicos. Em cada máquina, um daemon consulta vários masters e rejeita os que mentem. Na produção da época, a incerteza instantânea variava de cerca de um a sete milissegundos a cada intervalo de consulta, e a incerteza média ficava em quatro milissegundos na maior parte do tempo; a implementação a mantém geralmente abaixo de dez milissegundos.

04 · TRANSAÇÕES

Commit wait: trocar latência por ordem

Transações de leitura e escrita usam travamento em duas fases. Quando a transação toca um único grupo Paxos, como a maioria, ela dispensa o gerente de transações. Com mais de um grupo, os líderes coordenam um commit em duas fases sobre Paxos, o que mitiga os problemas de disponibilidade desse protocolo. Os autores defendem tratar os gargalos do uso excessivo de transações quando aparecerem, em vez de obrigar todos a programar sem transações.

1. O cliente, que mantém as escritas em buffer, conduz o commit: envia o pedido aos líderes dos dois grupos e indica qual é o coordenador.

2. O líder participante trava os dados, escolhe um prepare timestamp maior que os que já atribuiu e registra o prepare via Paxos.

3. O participante avisa o coordenador do seu prepare timestamp.

4. O coordenador escolhe o timestamp de commit: não menor que os prepare timestamps e maior que TT.now().latest do momento em que recebeu o pedido.

5. O coordenador registra o commit via Paxos, mas, antes de permitir que suas réplicas apliquem o registro, espera até TT.after do timestamp ser verdadeiro.

6. Passada a espera, as réplicas do coordenador aplicam o registro; o coordenador envia o timestamp ao cliente e ao participante, e todos aplicam no mesmo timestamp e liberam as travas.

A consistência externa vem de duas regras. Na regra Start, o coordenador escolhe um timestamp de commit maior que o TT.now().latest do momento em que recebeu o pedido e não menor que os prepare timestamps dos participantes. Na regra Commit Wait, ele impede que clientes vejam o que foi commitado até que o timestamp esteja no passado. A espera esperada é de pelo menos duas vezes a incerteza média.

Nem toda leitura precisa de travas. Uma transação somente leitura executa as leituras em um timestamp escolhido pelo sistema, sem travar, e não bloqueia as escritas que chegam; o snapshot read é uma leitura no passado, também sem travas. Cada réplica acompanha seu safe time, o maior timestamp em que está atualizada, e só atende leituras até ele.

05 · CUSTOS E LIMITES

O que a escala global cobra

No teste de disponibilidade do paper, matar uma zona sem líderes não afetou a vazão de leitura. Os líderes têm leases de duração padrão de dez segundos. Matar a zona dos líderes sem aviso teve efeito severo na taxa de conclusão, e só cerca de dez segundos depois, quando os leases venceram e novos líderes foram eleitos, tudo voltou. Leases mais curtos reduziriam o efeito, ao custo de mais tráfego de renovação.

A coordenação também tem preço. Em um micro-benchmark com uma réplica, o commit wait ficou em cerca de cinco milissegundos e a latência do Paxos em cerca de nove. O commit em duas fases escalou de forma razoável até dezenas de participantes, e a latência começou a subir de modo notável com cem. Os valores são os do paper, da época.

Para o F1, o ganho foi não precisar mais de reshard manual e ter failover automático, enquanto no MySQL com replicação mestre-escravo o failover era difícil e arriscava perda de dados e indisponibilidade. O F1 usa cinco réplicas espalhadas pelos Estados Unidos.

O paper também lista limitações da época, como a falta de suporte a mudanças de configuração dentro do próprio Paxos e de índices secundários automáticos.