Google Zanzibar: autorização global

01 · CONTEXTO

Uma pergunta em quase toda requisição

Em muitas interações online, um serviço precisa confirmar que o usuário tem permissão para realizar uma operação sobre um objeto digital. O Zanzibar é o sistema do Google para armazenar permissões e fazer essas checagens, oferecendo um modelo de dados e uma linguagem de configuração comuns a centenas de serviços.

Segundo o paper, a autorização traz desafios próprios de consistência de dados e de escala. Entre os objetivos declarados estão a correção, porque as decisões devem respeitar a intenção dos usuários, e a baixa latência, porque a checagem costuma estar no caminho crítico da interação. A alta disponibilidade também é exigida: sem autorização explícita, os serviços clientes seriam forçados a negar acesso aos usuários.

Os dados de ACL não se prestam a particionamento geográfico, pois a checagem de qualquer objeto pode vir de qualquer lugar do mundo; por isso o Zanzibar replica todos os dados de ACL em dezenas de data centers e distribui a carga por milhares de servidores.

02 · MODELO DE DADOS

Tuplas de relação em vez de listas por objeto

No Zanzibar, as ACLs são relações representadas como tuplas de relação, e os grupos são simplesmente ACLs com semântica de participação. Segundo o paper, definir o modelo em torno de tuplas, em vez de ACLs por objeto, unifica os conceitos de ACL e de grupo e permite leituras eficientes e atualizações incrementais.

Um exemplo do paper é a tupla doc:readme#viewer@group:eng#member, que diz que os membros de group:eng são leitores de doc:readme. O lado do usuário pode ser um conjunto de usuários (userset), o que permite representar grupos aninhados.

Guardar uma tupla por objeto para cada relação derivada seria desperdício e dificultaria alterações em massa. Por isso o cliente define, nas configurações de relação, regras de reescrita de userset que descrevem relações independentes do objeto. Na configuração de exemplo do paper, todo dono é editor e todo editor é leitor, e os leitores da pasta pai também são leitores do documento; uma primitiva flexível da linguagem permite políticas como buscar a pasta pai do documento e herdar seus leitores.

03 · CONSISTÊNCIA

O new enemy problem e o zookie

A checagem respeita a ordem em que as mudanças de ACL foram confirmadas no armazenamento. Para o paper, evitar o new enemy problem exige entender e respeitar a ordem causal entre atualizações de ACL e de conteúdo, e por isso o sistema precisa de duas propriedades: consistência externa e leituras de snapshot com defasagem limitada.

No primeiro exemplo do paper, Alice remove Bob da ACL de uma pasta e depois pede a Charlie que mova novos documentos para essa pasta. Bob não deveria ver os novos documentos, mas poderia vê-los se a checagem ignorasse a ordem entre as duas mudanças de ACL.

1. Quando uma alteração de conteúdo está para ser salva, o cliente faz uma checagem de alteração de conteúdo para obter um zookie dessa versão.

2. Essa checagem não leva zookie e é avaliada no snapshot mais recente; se a alteração é autorizada, a resposta traz o zookie.

3. O cliente grava o zookie junto com a mudança de conteúdo, em uma escrita atômica no armazenamento do cliente.

4. Nas checagens seguintes sobre essa versão, o cliente envia o zookie guardado.

5. O Zanzibar avalia a checagem em um snapshot ao menos tão recente quanto o zookie, de modo que as mudanças de ACL anteriores ao conteúdo, pela ordem causal, sejam observadas.

Avaliar sempre no snapshot mais recente exigiria sincronização global, com viagens de alta latência e disponibilidade limitada. O protocolo do zookie evita isso: com a cooperação dos clientes, a maioria das checagens pode ser avaliada em dados já replicados.

As ACLs ficam no Spanner, que atribui a cada escrita um timestamp de resolução de microssegundos cuja ordem reflete a ordem causal das escritas, e cada checagem é avaliada em um único timestamp de snapshot ao longo de várias leituras. Sem zookie, o servidor usa uma defasagem padrão, escolhida para que a avaliação seja a mais recente possível sem prejudicar a latência; isso é só uma otimização de desempenho e não viola a consistência, porque os zookies fornecidos são sempre respeitados.

As 5 réplicas votantes ficam no leste e no centro dos EUA, em 3 áreas metropolitanas diferentes para isolar falhas, mas a até 25 milissegundos umas das outras para que as transações Paxos confirmem rápido.

04 · ARQUITETURA

Servir checagens com baixa latência

Os aclservers são o principal tipo de servidor e se organizam em clusters. O pedido chega a qualquer servidor do cluster, que reparte o trabalho com os demais conforme necessário.

1. O pedido chega a qualquer aclserver do cluster, que reparte o trabalho com os outros servidores conforme necessário.

2. As tuplas e seus metadados ficam em bancos Spanner, que os aclservers leem e escrevem ao responder.

3. Os watchservers acompanham o changelog e servem aos clientes um fluxo de mudanças de namespace quase em tempo real.

4. O Leopard otimiza conjuntos grandes e muito aninhados e recebe o fluxo completo de mudanças de tuplas pela API Watch.

5. Um pipeline periódico executa funções offline sobre todos os dados no Spanner, e o Leopard lê snapshots periódicos dos dados de ACL.

Uma checagem é convertida em uma expressão booleana, e os nós-folha são avaliados concorrentemente. Seguir ponteiros de grupo em grupo funciona bem para a maioria das ACLs, mas pode ser caro quando grupos são profundos ou largos.

Para esses casos o Leopard trata a participação em grupos como um problema de alcançabilidade em um grafo, em que nós são grupos e usuários e arestas são participações diretas. Como o índice offline sozinho não oferece um snapshot fresco e consistente, o Leopard mescla durante a consulta as atualizações com timestamp menor ou igual ao da consulta sobre o índice offline.

Para favorecer a consistência, o Zanzibar evita desnormalizar o armazenamento e usa dados normalizados. O preço é que hot spots em ACLs comuns, como grupos populares, podem sobrecarregar os bancos. Os autores consideram o tratamento de hot spots a fronteira mais crítica na busca por baixa latência e alta disponibilidade.

1. O servidor que recebeu o pedido o encaminha a outro servidor usando uma chave de encaminhamento que, na maioria dos namespaces, vem do ID do objeto.

2. Os resultados são cacheados tanto no chamador quanto no chamado das RPCs internas, o que forma árvores de cache.

3. Entre requisições com a mesma chave de cache, só uma começa a processar; as demais esperam o cache ser preenchido.

4. O timestamp de avaliação é arredondado para cima, em granularidade grosseira e respeitando os zookies, para que muitas checagens compartilhem os mesmos resultados em cache.

5. Nas chamadas ao Spanner, envia-se primeiro um pedido e adia-se o pedido redundante até que o inicial se mostre lento.

O cache distribuído usa hashing consistente entre os servidores. O hedging vale para chamadas ao Spanner e ao Leopard, mas não entre servidores do Zanzibar, porque duplicaria justamente as checagens mais caras e pioraria a latência.

05 · NA PRÁTICA

Números de produção e lições

Segundo o paper, o Zanzibar gerencia mais de 1.500 namespaces definidos por centenas de aplicações, com mais de 2 trilhões de tuplas que ocupam perto de 100 terabytes. Atende mais de 10 milhões de consultas por segundo, distribuídas por mais de 10.000 servidores organizados em algumas dezenas de clusters.

Na amostra de sete dias, a checagem Safe teve picos de cerca de 3, 11, 20 e 93 ms nos percentis 50, 95, 99 e 99,9. A disponibilidade ficou acima de 99,999% em três anos de operação e, por trimestre, o paper reporta menos de 2 minutos de indisponibilidade global.

As leituras são duas ordens de magnitude mais frequentes que as escritas. As escritas são as mais lentas porque sempre exigem coordenação distribuída entre servidores Spanner.

O paper compara o Zanzibar ao TAO: o TAO oferece consistência global eventual com replicação assíncrona, enquanto o Zanzibar fornece consistência externa e leituras de snapshot com defasagem limitada, de modo que respeita a ordem causal entre atualizações de ACL e de conteúdo.