o problema
Todo produto que compartilha coisas precisa responder a mesma pergunta milhões de vezes por segundo: este usuário pode ver este objeto. Quando cada aplicação responde do seu jeito, o “compartilhar” do Drive não significa o mesmo que o do Photos, um objeto de um app embutido em outro não sabe herdar permissão de ninguém, e não dá para construir nada em cima — em particular um índice de busca que atravesse aplicações e respeite ACL. Zanzibar existe porque o Google decidiu resolver isso uma vez para Calendar, Cloud, Drive, Maps, Photos e YouTube, em vez de resolver mal em cada um.
A parte difícil não é guardar as permissões, é a ordem. O paper batiza o modo de errar de “new enemy problem” e dá dois casos. Alice remove Bob da ACL de uma pasta e depois pede a Charlie que mova documentos novos para lá; se o check ignora a ordem entre as duas mudanças, Bob vê os documentos. Ou: Alice remove Bob da ACL de um documento e depois pede conteúdo novo nele; se o check roda contra uma ACL anterior à remoção, Bob lê o conteúdo novo. Nos dois casos, a causalidade passa por fora do sistema de autorização — por uma conversa entre pessoas — e mesmo assim precisa ser respeitada.
a ideia
Uma tupla só, e ela se refere a si mesma. doc:readme#owner@10 diz que o usuário 10 é dono do documento. doc:readme#viewer@group:eng#member diz que quem for membro do grupo eng é viewer do documento — no lugar do usuário está outro par objeto#relação. É esse aninhamento que dissolve a distinção entre ACL e grupo: grupo é só uma ACL cuja relação se chama member, e grupo dentro de grupo sai de graça.
A segunda metade da ideia é que nem toda relação precisa virar tupla gravada. “Todo editor também comenta” e “viewer da pasta pai é viewer do documento” são regras que valem para todos os objetos do namespace; gravá-las por objeto seria desperdício e tornaria impossível mudar a política sem reescrever bilhões de linhas. Elas viram configuração.
A terceira é o zookie: um token opaco de timestamp que o cliente grava junto com a versão do conteúdo e devolve no check seguinte. Em vez de “me responda com o estado mais atual”, o cliente diz “me responda com algo pelo menos tão novo quanto isto” — e o resto da folga fica para o Zanzibar gastar em latência.
como funciona
As tuplas ficam no Spanner, um banco por namespace, com chave primária (shard, object id, relation, user, commit timestamp). Versões antigas coexistem em linhas separadas, então qualquer check pode ser avaliado em qualquer snapshot dentro da janela de coleta de lixo. Toda escrita entra também num changelog, na mesma transação, e é o changelog que alimenta a API de Watch.
O namespace config define as relações e, para cada uma, uma regra de reescrita que recebe um object id e devolve uma árvore de expressão de usersets. As folhas são três: _this (as tuplas gravadas), computed_userset (aponta para outra relação do mesmo objeto — é a herança entre owner, editor e viewer) e tuple_to_userset (busca um tupleset, tipicamente parent, e computa um userset em cada tupla achada — é a herança hierárquica, com uma tupla por salto). Os nós internos são união, interseção e exclusão.
Um check vira expressão booleana. Todas as folhas são avaliadas concorrentemente e, quando o resultado de um nó já decide a subárvore, o resto é cancelado. Consistência de config também é escolhida por snapshot: um job de monitoramento agrega a faixa de timestamps de config disponível em todos os servidores do cluster e cada requisição escolhe um ponto dessa faixa, para que os servidores continuem servindo mesmo sem conseguir ler o armazenamento de config.
Grupos profundos ou muito largos quebram a travessia recursiva. Para esses namespaces entra o Leopard, um índice de conjuntos com dois tipos, GROUP2GROUP e MEMBER2GROUP, achatando alcançabilidade no grafo de grupos; a pergunta “U é membro de G” vira uma interseção de dois conjuntos. As listas são inteiros ordenados em skip list, os shards ficam em memória e um construtor offline os gera a partir de snapshots. Como snapshot offline não é fresco, cada servidor mantém uma camada incremental alimentada pela Watch API, com marcador de deleção, mesclada na hora da consulta. Uma única mudança de tupla no Zanzibar pode virar dezenas de milhares de eventos no Leopard.
O que sobra é hot spot. Os aclservers formam um cache distribuído por hash consistente, com a chave de encaminhamento derivada do object id para que check indireto e leitura de tupla do mesmo objeto caiam no mesmo servidor; caller e callee cacheiam, formando árvores de cache. Uma lock table impede que requisições concorrentes com a mesma chave estourem juntas antes do cache existir. E os timestamps de avaliação são arredondados para grãos de um ou dez segundos, respeitando o zookie, para que checks recentes compartilhem chave. Em produção: mais de 2 trilhões de tuplas, cerca de 100 TB, mais de 30 réplicas, mais de 10 mil servidores, 22 milhões de RPCs internas delegadas por segundo, p95 de Check Safe abaixo de 10 ms e disponibilidade acima de 99,999% por 3 anos.
o que isso custou
A escolha de manter tudo normalizado é o que dá consistência e é também a origem de quase todo o sofrimento operacional; o paper afirma que lidar com hot spots foi a fronteira mais crítica na busca por latência e disponibilidade. Cache distribuído, lock table, prefetch de todas as tuplas de um objeto quente, adiamento do cancelamento de checks indiretos quando há esperando na lock table — é uma pilha de remendos específicos, cada um adicionado depois que um cliente quebrou alguma coisa.
Escrita é cara: 127 ms na mediana, 401 ms no p99, porque sempre exige coordenação distribuída no Spanner. Frescor também: pedir dado com menos de 10 segundos custa 60 ms no p95 de Check contra 9,46 ms do caminho normal. O zookie não é grátis para o cliente — ele precisa emitir um check de mudança de conteúdo, guardar o token junto com o conteúdo numa escrita atômica no seu próprio armazenamento e devolvê-lo depois. Autorização correta obriga o cliente a mudar o schema dele.
O modelo também vaza. Read devolve tuplas cruas e não aplica reescrita, então quem quiser saber quem de fato tem acesso precisa chamar Expand e interpretar a árvore. Hedging, que resolve cauda contra Spanner e Leopard, não pode ser usado entre aclservers, porque os checks têm custos muito diferentes e duplicar os caros pioraria justamente a cauda. E como nenhuma dessas defesas basta contra um cliente que lançou uma feature popular demais, veio uma camada de contabilidade de custo em cpu-seconds, cotas e throttling por cliente, incluindo chaves de lock table separadas por cliente para que o throttle de um não respingue nos outros.
onde isso aparece hoje
O Cloud IAM do Google é, segundo o próprio paper, uma camada construída sobre o armazenamento e a avaliação de ACL do Zanzibar. Fora do Google, o paper virou especificação de fato: existe hoje uma família de sistemas de autorização abertos que se descrevem como inspirados no Zanzibar e reproduzem quase literalmente a tupla de relação, a linguagem de reescrita de userset e o token de consistência.
É também o fecho de uma linhagem. O Spanner prometeu consistência externa com TrueTime, e Zanzibar é o caso de uso que mostra o que se compra com ela: sem timestamps causalmente significativos, o zookie não existiria e a defesa contra o “new enemy problem” viraria sincronização global. O hedging vem direto de The Tail at Scale, aplicado com a ressalva de que ele exige requisições de custo semelhante. A distribuição de cache usa hash consistente. E a seção de trabalhos relacionados explica por que nada disso caberia no Chubby: falta volume de dados, leitura eficiente por faixa e snapshot com atraso limitado — a mesma constatação que separa um serviço de coordenação de um banco planetário.