Ciclo de vida das leituras e escritas do Spanner

O Spanner é uma base de dados distribuída, escalável e fortemente consistente criada por engenheiros da Google para suportar algumas das aplicações mais críticas da Google. Baseia-se em ideias fundamentais das comunidades de bases de dados e sistemas distribuídos e expande-as de novas formas. O Spanner expõe este serviço interno do Spanner como um serviço disponível publicamente na Google Cloud Platform.

Uma vez que o Spanner tem de processar os exigentes requisitos de tempo de atividade e escala impostos pelas aplicações empresariais críticas da Google, criámos o Spanner desde o início para ser uma base de dados amplamente distribuída. O serviço pode abranger várias máquinas e vários centros de dados e regiões. Tiramos partido desta distribuição para processar conjuntos de dados e cargas de trabalho enormes, mantendo, ainda assim, uma disponibilidade muito elevada. Também pretendíamos que o Spanner oferecesse as mesmas garantias de consistência rigorosa oferecidas por outras bases de dados de nível empresarial, porque queríamos criar uma excelente experiência para os programadores. É muito mais fácil raciocinar e escrever software para uma base de dados que suporte uma consistência forte do que para uma base de dados que apenas suporte uma consistência ao nível da linha, uma consistência ao nível da entidade ou que não tenha garantias de consistência.

Neste documento, descrevemos detalhadamente como funcionam as escritas e as leituras no Spanner e como o Spanner garante uma consistência forte.

Pontos de partida

Existem alguns conjuntos de dados demasiado grandes para caberem numa única máquina. Também existem cenários em que o conjunto de dados é pequeno, mas a carga de trabalho é demasiado pesada para uma máquina processar. Isto significa que temos de encontrar uma forma de dividir os nossos dados em partes separadas que podem ser armazenadas em várias máquinas. A nossa abordagem consiste em particionar tabelas de base de dados em intervalos de chaves contíguos denominados divisões. Uma única máquina pode servir várias divisões e existe um serviço de pesquisa rápida para determinar as máquinas que servem um determinado intervalo de chaves. Os detalhes de como os dados são divididos e em que máquinas residem são transparentes para os utilizadores do Spanner. O resultado é um sistema que pode fornecer latências baixas para leituras e escritas, mesmo em cargas de trabalho pesadas, a uma escala muito grande.

Também queremos garantir que os dados estão acessíveis apesar das falhas. Para garantir isto, replicamos cada divisão em várias máquinas em domínios de falhas distintos. A replicação consistente nas diferentes cópias da divisão é gerida pelo algoritmo Paxos. No Paxos, desde que a maioria das réplicas de votação para a divisão esteja ativa, uma dessas réplicas pode ser eleita líder para processar escritas e permitir que outras réplicas sirvam leituras.

O Spanner oferece transações só de leitura e transações de leitura/escrita. As primeiras são o tipo de transação preferencial para operações (incluindo declarações SQL SELECT) que não alteram os seus dados. As transações de só de leitura continuam a oferecer uma forte consistência e funcionam, por predefinição, na cópia mais recente dos seus dados. No entanto, podem ser executados sem necessidade de qualquer forma de bloqueio interno, o que os torna mais rápidos e escaláveis. As transações de leitura/escrita são usadas para transações que inserem, atualizam ou eliminam dados. Isto inclui transações que executam leituras seguidas de uma escrita. Continuam a ser altamente escaláveis, mas as transações de leitura/escrita introduzem o bloqueio e têm de ser orquestradas pelos líderes do Paxos. Tenha em atenção que o bloqueio é transparente para os clientes do Spanner.

Muitos sistemas de bases de dados distribuídas anteriores optaram por não oferecer garantias de consistência fortes devido à comunicação entre máquinas dispendiosa que é normalmente necessária. O Spanner consegue fornecer instantâneos fortemente consistentes em toda a base de dados através de uma tecnologia desenvolvida pela Google denominada TrueTime. Tal como o condensador de fluxo numa máquina do tempo de 1985, o TrueTime é o que torna o Spanner possível. É uma API que permite que qualquer máquina nos centros de dados da Google saiba a hora global exata com um elevado grau de precisão (ou seja, dentro de alguns milissegundos). Isto permite que diferentes máquinas do Spanner raciocinem sobre a ordem das operações transacionais (e que essa ordem corresponda ao que o cliente observou), muitas vezes sem qualquer comunicação. A Google teve de equipar os respetivos centros de dados com hardware especial (relógios atómicos!) para fazer o TrueTime funcionar. A precisão e a exatidão de tempo resultantes são muito superiores às que podem ser alcançadas por outros protocolos (como o NTP). Em particular, o Spanner atribui uma data/hora a todas as leituras e escritas. Uma transação na data/hora T1 garante que reflete os resultados de todas as gravações que ocorreram antes de T1. Se uma máquina quiser satisfazer uma leitura em T2, tem de garantir que a respetiva vista dos dados está atualizada através, pelo menos, de T2. Devido ao TrueTime, esta determinação é normalmente muito barata. Os protocolos para garantir a consistência dos dados são complicados, mas são abordados mais detalhadamente no documento original do Spanner e neste documento sobre o Spanner e a consistência.

Nota: sistemas de ficheiros distribuídos

Quando guarda um ficheiro no seu portátil, o ficheiro é normalmente escrito no disco rígido desse portátil. Mas o que acontece se esse disco rígido avariar? Perde o ficheiro? O seu portátil consegue guardar mais ficheiros (ou até ser usado para qualquer coisa) até que o disco rígido seja reparado? Estes são alguns dos problemas que os sistemas de ficheiros distribuídos tentam resolver. Há mais de uma década, a Google criou um sistema denominado Google File System (GFS) que resolve alguns destes problemas. Os ficheiros foram replicados em vários computadores. Se uma máquina falhasse, as outras máquinas continuariam a estar disponíveis para publicar leituras e escritas no ficheiro. Fizemos muitos avanços desde o GFS, mas o conceito fundamental permanece o mesmo: o armazenamento de ficheiros está separado das máquinas que os criam, leem, atualizam e eliminam. Isto permite a criação de sistemas mais robustos. Um único disco danificado não pode resultar na perda ou corrupção de dados. A combinação da replicação baseada em Paxos do Spanner e da robustez do sistema de ficheiros distribuído subjacente oferece uma fiabilidade de dados extremamente boa.

Para garantir a durabilidade das escritas, as transações do Spanner são confirmadas através da escrita de mutações em, pelo menos, a maioria das réplicas das divisões afetadas. As máquinas que alojam essas divisões escrevem estas mutações de forma duradoura num sistema de ficheiros distribuído. O Spanner é uma arquitetura "shared nothing" (que oferece uma elevada escalabilidade), mas, como qualquer servidor num cluster pode ler a partir deste sistema de ficheiros distribuído, podemos recuperar rapidamente de falhas de máquinas inteiras. Uma vez que a Google é proprietária de todo o conjunto de software e hardware do Spanner, podemos fazer otimizações adicionais para garantir o máximo desempenho e robustez. Por exemplo, todas as máquinas do Spanner usam RAM com bateria, para que as escritas possam ser sincronizadas com o disco, mesmo no caso (improvável) de perda de energia do centro de dados. Isto também permite que o sistema de ficheiros reconheça as escritas sem esperar pela latência da escrita no disco.

Exemplo prático

Vamos analisar alguns exemplos práticos para ver como tudo funciona:

CREATE TABLE ExampleTable (
 Id INT64 NOT NULL,
 Value STRING(MAX),
) PRIMARY KEY(Id);

Neste exemplo, temos uma tabela com uma chave principal de número inteiro simples.

Espargata	KeyRange
0	[-∞,3)
1	[3,224)
2	[224,712)
3	[712,717)
4	[717,1265)
5	[1265,1724)
6	[1724,1997)
7	[1997,2456)
8	[2456,∞)

Tendo em conta o esquema de ExampleTable acima, o espaço de chaves principal é particionado em divisões. Por exemplo: se existir uma linha em ExampleTable com um Id de 3700, esta vai estar na divisão 8. Conforme detalhado acima, a divisão 8 é replicada em vários computadores.

Neste exemplo de instância do Spanner, o cliente tem cinco nós e a instância é replicada em três zonas. As nove divisões estão numeradas de 0 a 8, sendo que os líderes do Paxos para cada divisão estão sombreados a escuro. As divisões também têm réplicas em cada zona (com ligeira sombra). A distribuição das divisões entre os nós pode ser diferente em cada zona, e os líderes do Paxos não residem todos na mesma zona. Esta flexibilidade ajuda o Spanner a ser mais robusto a determinados tipos de perfis de carga e modos de falha.

Escrita de divisão única

Suponhamos que o cliente quer inserir uma nova linha (7, "Seven") emExampleTable.

1. A camada da API procura a divisão proprietária do intervalo de chaves que contém 7. Está na divisão 1.
2. A camada API envia o pedido de gravação para o líder da divisão 1.
3. O líder inicia uma transação.
4. O líder tenta obter um bloqueio de escrita na linha Id=7. Esta é uma operação local. Se outra transação de leitura/escrita concorrente estiver atualmente a ler esta linha, a outra transação tem um bloqueio de leitura e a transação atual é bloqueada até poder adquirir o bloqueio de escrita.
   1. É possível que a transação A esteja à espera de um bloqueio detido pela transação B e que a transação B esteja à espera de um bloqueio detido pela transação A. Uma vez que nenhuma transação liberta bloqueios até adquirir todos os bloqueios, isto pode levar a um impasse. O Spanner usa um algoritmo de prevenção de deadlock "wound-wait" padrão para garantir que as transações progridem. Em particular, uma transação "mais recente" aguarda um bloqueio detido por uma transação "mais antiga", mas uma transação "mais antiga" "danifica" (interrompe) uma transação mais recente que detenha um bloqueio pedido pela transação mais antiga. Por conseguinte, nunca temos ciclos de impasse de esperas de bloqueio.
5. Assim que o bloqueio é adquirido, o líder atribui uma data/hora à transação com base no TrueTime.
   1. Esta data/hora é garantidamente superior à de qualquer transação confirmada anteriormente que tenha afetado os dados. Isto garante que a ordem das transações (conforme percebida pelo cliente) corresponde à ordem das alterações aos dados.
6. O líder informa as réplicas da divisão 1 acerca da transação e da respetiva indicação de tempo. Assim que a maioria dessas réplicas tiver armazenado a mutação da transação no armazenamento estável (no sistema de ficheiros distribuído), a transação é confirmada. Isto garante que a transação é recuperável, mesmo que ocorra uma falha numa minoria de máquinas. (As réplicas ainda não aplicam as mutações à respetiva cópia dos dados.)

7. O líder aguarda até ter a certeza de que a data/hora da transação passou em tempo real. Normalmente, isto requer alguns milissegundos para que possamos aguardar qualquer incerteza na data/hora do TrueTime. Isto garante uma forte consistência. Depois de um cliente ter aprendido o resultado de uma transação, é garantido que todos os outros leitores veem os efeitos da transação. Normalmente, esta "espera de confirmação" sobrepõe-se à comunicação da réplica no passo acima, pelo que o custo de latência real é mínimo. Pode encontrar mais detalhes neste documento.

8. O líder responde ao cliente indicando que a transação foi confirmada, comunicando opcionalmente a data/hora de confirmação da transação.

9. Em paralelo com a resposta ao cliente, as mutações de transações são aplicadas aos dados.

   1. O líder aplica as mutações à respetiva cópia dos dados e, em seguida, liberta os bloqueios de transações.
   2. O líder também informa as outras réplicas da divisão 1 para aplicarem a mutação às respetivas cópias dos dados.
   3. Qualquer transação de leitura/escrita ou só de leitura que deva ver os efeitos das mutações aguarda até que as mutações sejam aplicadas antes de tentar ler os dados. Para transações de leitura/escrita, isto é aplicado porque a transação tem de ter um bloqueio de leitura. Para transações só de leitura, isto é aplicado comparando a data/hora da leitura com a dos dados aplicados mais recentemente.

Normalmente, tudo isto acontece em alguns milissegundos. Esta escrita é o tipo de escrita mais barato feito pelo Spanner, uma vez que envolve uma única divisão.

Gravação com várias divisões

Se estiverem envolvidas várias divisões, é necessária uma camada adicional de coordenação (através do algoritmo de confirmação de duas fases padrão).

Suponhamos que a tabela contém quatro mil linhas:

1	"um"
2	"two"
…	…
4000	"quatro mil"

Suponhamos que o cliente quer ler o valor da linha 1000 e escrever um valor nas linhas 2000, 3000 e 4000 numa transação. Esta ação vai ser executada numa transação de leitura/escrita da seguinte forma:

1. O cliente inicia uma transação de leitura/escrita, t.
2. O cliente envia um pedido de leitura da linha 1000 para a camada API e marca-o como parte de t.
3. A camada da API procura a divisão que detém a chave 1000. Está alojado na divisão 4.

4. A camada API envia um pedido de leitura ao líder da divisão 4 e etiqueta-o como parte de t.

5. O líder da divisão 4 tenta obter um bloqueio de leitura na linha Id=1000. Esta é uma operação local. Se outra transação simultânea tiver um bloqueio de escrita nesta linha, a transação atual é bloqueada até poder adquirir o bloqueio. No entanto, este bloqueio de leitura não impede que outras transações obtenham bloqueios de leitura.

   1. Tal como no caso da divisão única, o impasse é evitado através da "wound-wait".

6. O líder procura o valor de Id 1000 ("Mil") e devolve o resultado de leitura ao cliente.

   
   Mais tarde…
   

7. O cliente emite um pedido de confirmação para a transação t. Este pedido de confirmação contém 3 mutações: ([2000, "Dos Mil"],[3000, "Tres Mil"] e [4000, "Quatro Mil"]).

   1. Todas as divisões envolvidas numa transação tornam-se participantes na transação. Neste caso, a divisão 4 (que publicou a leitura da chave 1000), a divisão 7 (que vai processar a mutação da chave 2000) e a divisão 8 (que vai processar as mutações da chave 3000 e da chave 4000) são participantes.

8. Um participante torna-se o coordenador. Neste caso, talvez o líder do grupo Split 7 se torne o coordenador. A tarefa do coordenador é garantir que a transação é confirmada ou anulada atomicamente em todos os participantes. Ou seja, não vai ser confirmada num participante e anulada noutro.

   1. O trabalho realizado pelos participantes e coordenadores é, na verdade, realizado pelas máquinas líderes dessas divisões.

9. Os participantes adquirem cadeados. (Esta é a primeira fase da confirmação de duas fases.)

   1. A divisão 7 adquire um bloqueio de escrita na chave 2000.
   2. A divisão 8 adquire um bloqueio de escrita na chave 3000 e na chave 4000.
   3. O Split 4 verifica se ainda tem um bloqueio de leitura na chave 1000 (por outras palavras, se o bloqueio não foi perdido devido a uma falha de sistema ou ao algoritmo de espera de ferimentos).
   4. Cada registo dividido de participante regista o respetivo conjunto de bloqueios replicando-os para (pelo menos) a maioria das réplicas divididas. Isto garante que os bloqueios podem permanecer mantidos mesmo em caso de falhas do servidor.
   5. Se todos os participantes notificarem com êxito o coordenador de que os respetivos bloqueios estão mantidos, a transação geral pode ser confirmada. Isto garante que existe um ponto no tempo em que todos os bloqueios necessários para a transação são mantidos, e este ponto no tempo torna-se o ponto de confirmação da transação, garantindo que podemos ordenar corretamente os efeitos desta transação em relação a outras transações que ocorreram antes ou depois.
   6. É possível que não seja possível adquirir bloqueios (por exemplo, se soubermos que pode haver um impasse através do algoritmo de espera ferida). Se algum participante indicar que não consegue confirmar a transação, toda a transação é anulada.

10. Se todos os participantes e o coordenador adquirirem bloqueios com êxito, o coordenador (divisão 7) decide confirmar a transação. Atribui uma data/hora à transação com base no TrueTime.

    1. Esta decisão de confirmação, bem como as mutações da chave 2000, são replicadas para os membros da divisão 7. Assim que a maioria das réplicas divididas em 7 registar a decisão de confirmação no armazenamento estável, a transação é confirmada.

11. O coordenador comunica o resultado da transação a todos os participantes. (Esta é a segunda fase da confirmação de duas fases.)

    1. Cada líder participante replica a decisão de confirmação nas réplicas da divisão de participantes.

12. Se a transação for confirmada, o coordenador e todos os participantes aplicam as mutações aos dados.

    1. Tal como no caso da divisão única, os leitores subsequentes de dados no coordenador ou nos participantes têm de aguardar até que os dados sejam aplicados.

13. O líder do coordenador responde ao cliente a indicar que a transação foi confirmada, devolvendo opcionalmente a data/hora de confirmação da transação

    1. Tal como no caso da divisão única, o resultado é comunicado ao cliente após uma espera de confirmação, para garantir uma forte consistência.

Normalmente, tudo isto acontece em alguns milissegundos, embora, normalmente, demore um pouco mais do que no caso de divisão única devido à coordenação entre divisões adicional.

Leitura forte (divisão múltipla)

Suponhamos que o cliente quer ler todas as linhas onde Id >= 0 e Id < 700 como parte de uma transação só de leitura.

1. A camada da API procura as divisões que detêm chaves no intervalo [0, 700). Estas linhas são propriedade de Split 0, Split 1 e Split 2.
2. Uma vez que se trata de uma leitura forte em vários computadores, a camada da API escolhe a data/hora de leitura através do TrueTime atual. Isto garante que ambas as leituras devolvem dados do mesmo resumo da base de dados.
   1. Outros tipos de leituras, como leituras desatualizadas, também escolhem uma data/hora para ler (mas a data/hora pode ser no passado).
3. A camada de API envia o pedido de leitura para algumas réplicas da divisão 0, algumas réplicas da divisão 1 e algumas réplicas da divisão 2. Também inclui a data/hora de leitura que selecionou no passo acima.

4. Para leituras fortes, a réplica de publicação normalmente faz um RPC ao líder para pedir a data/hora da última transação que tem de aplicar, e a leitura pode prosseguir assim que essa transação for aplicada. Se a réplica for o líder ou determinar que está suficientemente atualizada para responder ao pedido a partir do respetivo estado interno e TrueTime, responde diretamente à leitura.

5. Os resultados das réplicas são combinados e devolvidos ao cliente (através da camada da API).

Tenha em atenção que as leituras não adquirem bloqueios em transações só de leitura. Além disso, as leituras podem ser potencialmente fornecidas por qualquer réplica atualizada de uma determinada divisão, pelo que o débito de leitura do sistema é potencialmente muito elevado. Se o cliente conseguir tolerar leituras com, pelo menos, dez segundos de atraso, o débito de leitura pode ser ainda maior. Uma vez que o líder atualiza normalmente as réplicas com a data/hora segura mais recente a cada dez segundos, as leituras numa data/hora desatualizada podem evitar um RPC adicional ao líder.

Nota: bloqueio no Spanner

Normalmente, as exclusões de escrita em bases de dados são exclusivas: apenas um escritor de cada vez pode atualizar os dados. Isto evita a corrupção de dados, impedindo condições de concorrência nos mesmos dados. No entanto, limita a taxa de transferência, uma vez que apenas uma transação de cada vez pode progredir. No Spanner, podemos tirar partido das datas/horas atribuídas às transações para permitir que os bloqueios de escrita sejam partilhados em muitos casos. Em particular, para escritas cegas (escrever dados sem os ler previamente na mesma transação) numa única transação dividida, podemos permitir que várias transações que escrevam os mesmos dados prossigam em paralelo. Uma vez que as datas/horas atribuídas do TrueTime a cada gravação têm a garantia de ser diferentes, evitamos condições de concorrência. Os dados com datas/horas diferentes são aplicados separadamente e por ordem de data/hora, evitando a corrupção de dados. Consideramos que isto representa um ganho significativo de débito para as gravações cegas feitas no Spanner pelos sistemas internos da Google.

Aparte: qual é a desvantagem? Os primitivos de base de dados poderosos não têm um custo de desempenho?

Um dos princípios que tentamos seguir é "não paga (em termos de desempenho) por aquilo que não usa". Um exemplo disto são as garantias de concorrência do Spanner: embora o Spanner use vários mecanismos para garantir uma forte consistência, uma aplicação não paga pelos mecanismos que não usa. Implementamos a confirmação em duas fases (2PC) para transações que abrangem divisões, mas uma transação para uma única divisão ignora a 2PC e usa um protocolo mais simples e rápido. As leituras "fortes" dos dados mais recentes podem gastar alguma latência a verificar se uma réplica está suficientemente atualizada, mas uma leitura que possa ser satisfeita com dados desatualizados não paga esta latência. Outro exemplo é a nossa disposição dos dados, em que usamos a divisão em partições por intervalo. As aplicações que fazem análises de alcance podem usar este esquema para obter um elevado desempenho. No entanto, algumas aplicações não precisam de análises de intervalos e, se essas aplicações não quiserem preocupar-se com o custo de desempenho de potenciais pontos críticos de intervalos de linhas, podem colocar um valor hash na respetiva chave primária, o que faz com que o Spanner use efetivamente a divisão em fragmentos hash. Em geral, o Spanner foi concebido para oferecer ferramentas poderosas aos criadores de aplicações, mas para lhes dar um elevado grau de controlo sobre quaisquer compromissos entre a funcionalidade e o desempenho poderosos.

Conclusão

Tradicionalmente, os criadores de sistemas de bases de dados distribuídas descobriram que as garantias transacionais fortes são caras devido a toda a comunicação entre máquinas necessária. Com o Spanner, focámo-nos na redução do custo das transações para as tornar viáveis em grande escala e apesar da distribuição. Um dos principais motivos pelos quais isto funciona é o TrueTime, que reduz a comunicação entre máquinas para muitos tipos de coordenação. Além disso, a engenharia cuidadosa e o ajuste do desempenho resultaram num sistema com um desempenho elevado, mesmo quando oferece fortes garantias. Na Google, verificámos que isto facilitou significativamente o desenvolvimento de aplicações no Spanner em comparação com outros sistemas de bases de dados com garantias mais fracas. Quando os programadores de aplicações não têm de se preocupar com condições de concorrência ou inconsistências nos respetivos dados, podem concentrar-se no que realmente importa: criar e enviar uma excelente aplicação.