O Zanzibar armazena permissões como tuplas de relação: um fato por linha, lido como “este usuário tem esta relação com este objeto”. Tudo o mais nesta página, as regras de reescrita, o Check e o Expand, é calculado a partir dessas linhas.
O exemplo recorrente: Anne, Beto e Chen (user:anne, user:beto, user:chen); o documento doc:readme em folder:A; o grupo group:eng. Anne é dona do readme, Beto está em eng, os membros de eng visualizam o readme e Chen visualiza a pasta A.
A gramática
O artigo (§2.1) apresenta a notação textual em quatro regras:
⟨tuple⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩ ‘@’ ⟨user⟩
⟨object⟩ ::= ⟨namespace⟩ ‘:’ ⟨object_id⟩
⟨user⟩ ::= ⟨user_id⟩ | ⟨userset⟩
⟨userset⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩
Uma tupla tem três partes. O objeto é um namespace mais um ID, como doc:readme. A relação é um nome que o namespace define, como owner ou viewer. O usuário é um único ID de usuário ou um userset. No artigo, um ID de usuário é um inteiro; este site escreve user:anne para que o exemplo continue legível.
O que diz uma única tupla?
Ela diz uma única coisa: Anne tem a relação owner com doc:readme. O artigo lista as chaves primárias que identificam uma tupla: namespace, ID do objeto, relação e usuário.
Usersets: uma tupla que aponta para um grupo
A quarta regra da gramática é a interessante. Um userset é, ele próprio, um objeto mais uma relação: group:eng#member significa “todo usuário que tem a relação member com group:eng”. Quando o usuário de uma tupla é um userset, uma linha concede algo a um conjunto inteiro de usuários, e esse conjunto é definido por outras linhas.
Como uma tupla dá a todos os membros de eng acesso ao readme?
Observe que nenhuma linha menciona Beto e o readme juntos. Beto é visualizador porque está no conjunto para o qual a segunda tupla aponta. Adicione um membro a eng e esse membro poderá visualizar o readme sem nenhuma alteração na ACL do readme.
O mesmo recurso se aninha. O membro de um grupo pode ser outro userset, por exemplo group:eng#member@group:sre#member (uma subequipe hipotética, que não faz parte do exemplo recorrente), e a associação então atravessa tantos níveis quantos as tuplas descreverem. O artigo diz isso em uma linha: “a ⟨userset⟩ allows ACLs to refer to groups and thus supports representing nested group membership” (um ⟨userset⟩ permite que ACLs se refiram a grupos e, assim, possibilita representar associações a grupos aninhados) (§2.1). Ele também explica o ganho: modelar com tuplas em vez de ACLs por objeto “allows us to unify the concepts of ACLs and groups” (permite-nos unificar os conceitos de ACLs e grupos) (§2.1). Um grupo é apenas um objeto cuja relação member é uma ACL.
A Tabela 1 como um único grafo
A Tabela 1 do artigo lista quatro tuplas de exemplo. Com os usuários 10 e 11 renomeados para Anne e Beto, e uma tupla acrescentada para Chen, elas são:
| Tupla | Leitura |
|---|---|
doc:readme#owner@user:anne |
Anne é dona do readme |
group:eng#member@user:beto |
Beto é membro de eng |
doc:readme#viewer@group:eng#member |
Os membros de eng são visualizadores do readme |
doc:readme#parent@folder:A#... |
O readme está na pasta A |
folder:A#viewer@user:chen |
Chen é visualizador da pasta A (não está na Tabela 1) |
O #... na quarta linha é a notação do artigo para “a relation that does not affect the semantics of the tuple” (uma relação que não afeta a semântica da tupla) (legenda da Tabela 1): a tupla aponta para a própria pasta, não para um conjunto de seus usuários.
Como ficam as cinco linhas juntas?
Observe que a aresta parent não diz nada sobre acesso. Nas palavras do artigo, algumas relações “only define abstract relations between objects. These abstract relations may indirectly affect access control given userset rewrite rules specified in namespace configs” (apenas definem relações abstratas entre objetos. Essas relações abstratas podem afetar indiretamente o controle de acesso, dadas as regras de reescrita de userset especificadas nas configurações de namespace) (§2.1). Se Chen pode ver o readme depende de uma regra desse tipo, que é o assunto da próxima seção.
Configuração de namespace
Antes de armazenar tuplas, um cliente configura um namespace, como doc ou folder (§2.3). A configuração lista as relações do namespace, cada uma com um nome e uma configuração de relação, além de parâmetros de armazenamento: configurações de sharding e uma codificação para IDs de objeto.
As tuplas, sozinhas, não definem a ACL efetiva. Muitos clientes querem que todo editor também seja visualizador. Armazenar uma tupla viewer extra para cada editor de cada objeto seria, nas palavras do artigo, “wasteful and make it hard to make modifications across all objects” (um desperdício e dificultaria fazer modificações em todos os objetos) (§2.3.1). Em vez disso, uma configuração de relação pode conter uma regra de reescrita de userset: uma função que recebe um ID de objeto e retorna uma árvore de expressão de userset.
Esta é a Figura 1 do artigo, literalmente:
name: "doc"
relation { name: "owner" }
relation {
name: "editor"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "owner" } }
} } }
relation {
name: "viewer"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "editor" } }
child { tuple_to_userset {
tupleset { relation: "parent" }
computed_userset {
object: $TUPLE_USERSET_OBJECT # parent folder
relation: "viewer"
} } }
} } }
Figure 1: Simple namespace configuration with concentric relations on documents. All owners are editors, and all editors are viewers. Further, viewers of the parent folder are also viewers of the document.
(Figura 1: Configuração de namespace simples com relações concêntricas sobre documentos. Todos os donos são editores, e todos os editores são visualizadores. Além disso, os visualizadores da pasta pai também são visualizadores do documento.)
As folhas de uma árvore de reescrita são de três tipos (§2.3.1):
| Folha | O que retorna | Na Figura 1 |
|---|---|---|
_this |
Os usuários das tuplas armazenadas para este objeto e esta relação, incluindo os usersets para os quais essas tuplas apontam. É o padrão quando uma relação não tem regra. | As tuplas viewer armazenadas em doc:readme |
computed_userset |
O userset de outra relação sobre o mesmo objeto. | editor no mesmo documento; para editor, owner |
tuple_to_userset |
Lê um conjunto de tuplas (tupleset) a partir do objeto e, em seguida, calcula um userset a partir de cada tupla encontrada. | Ler as tuplas parent do documento e, então, tomar viewer em cada pasta pai |
As folhas se combinam por união, interseção e exclusão (§2.3.1). A Figura 1 usa apenas união. Uma interseção exigiria que o usuário estivesse em todos os filhos, por exemplo “editores que também estão em eng”; uma exclusão removeria um conjunto, por exemplo “visualizadores, exceto uma lista de bloqueados”. Esses dois exemplos são ilustrações, não vêm do artigo.
Que árvore a regra viewer constrói para um documento?
Observe que owner fica dois níveis abaixo: donos são editores, editores são visualizadores. É isso que a legenda da Figura 1 quer dizer com “concentric relations” (relações concêntricas). O ramo da direita é o único que sai do documento: ele segue uma aresta parent armazenada até outro objeto.
Check como uma busca em grafo
Uma requisição Check nomeia um userset ⟨object#relation⟩ e um usuário, e pergunta se o usuário pertence a ele (§2.4.4). Sem regras de reescrita, o artigo escreve a avaliação como uma fórmula recursiva (§3.2.3): o usuário está em ⟨object#relation⟩ se existir uma tupla ⟨object#relation@U⟩, ou se existir uma tupla ⟨object#relation@U′⟩ em que U′ é um userset e o usuário está em U′. O artigo chama essa recursão de “pointer chasing”. As regras de reescrita “are also translated to boolean expressions as part of check evaluation” (também são traduzidas em expressões booleanas como parte da avaliação da verificação) (§3.2.3), de modo que a árvore de expressão acima se torna um OR de três ramos.
A pergunta para as quatro figuras seguintes: Chen pode visualizar doc:readme? Cada quadro usa o mesmo grafo e destaca as arestas que o ramo atual lê. A configuração do namespace folder não está no artigo; estes quadros supõem que folder#viewer não tem regra de reescrita, de modo que é apenas _this.
Passo 1: _this
Alguma tupla viewer armazenada no readme inclui Chen?
O único visualizador armazenado é um userset, então o Check desce recursivamente em group:eng#member. Seu único membro é Beto. Este ramo responde não.
Passo 2: computed_userset editor, depois owner
Chen é editor ou dono?
A reescrita passa de viewer para editor e para owner no mesmo objeto. Nenhuma tupla armazenada é necessária para os dois primeiros saltos: eles vêm da configuração. A única dona é Anne, então este ramo também responde não.
Passo 3: tuple_to_userset, encontrar a pasta pai
Em que pasta está o readme?
A tupla parent é a “relação abstrata” da Tabela 1. Sozinha, ela não concede nada; a regra de reescrita a transforma em uma nova pergunta sobre outro objeto.
Passo 4: folder:A#viewer
Chen é visualizador da pasta A?
O caminho user:chen → folder:A → doc:readme responde à pergunta. Observe que as arestas apontam no mesmo sentido em todos os quadros, mas a busca partiu do readme para fora: o Check começa em ⟨object#relation⟩ e procura o usuário.
Um pointer chasing como este “works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide” (funciona bem para a maioria dos tipos de ACLs e grupos, mas pode ser custoso quando ACLs indiretas ou grupos são profundos ou largos) (§3.2.3). Para esses namespaces, o Zanzibar usa o índice Leopard, descrito na página do Leopard.
Read e Expand
Duas chamadas da API olham para os mesmos dados de alturas diferentes.
O Read (§2.4.1) retorna apenas tuplas armazenadas. Uma requisição nomeia um ou mais conjuntos de tuplas (tuplesets): uma única chave de tupla, ou todas as tuplas de um ID de objeto ou de um userset em um namespace, opcionalmente restritas a uma relação. O artigo é explícito: “Read results only depend on contents of relation tuples and do not reflect userset rewrite rules” (os resultados de leitura dependem apenas do conteúdo das tuplas de relação e não refletem as regras de reescrita de userset) (§2.4.1). Ler doc:readme com a relação viewer no exemplo recorrente retorna uma linha:
doc:readme#viewer@group:eng#member
Anne não aparece, embora todo dono seja visualizador, e Chen não aparece, embora possa visualizar o readme.
O Expand (§2.4.5) “follows indirect references expressed through userset rewrite rules” (segue referências indiretas expressas por meio de regras de reescrita de userset). Ele retorna uma árvore de usersets: as folhas são IDs de usuário ou usersets que apontam para outros pares ⟨object#relation⟩, e os nós internos são união, interseção ou exclusão.
O que o Expand retorna para doc:readme#viewer?
Observe as duas folhas tracejadas. Segundo a §2.4.5, uma folha pode ser um userset que aponta para outro lugar, então um cliente que queira cada indivíduo (Beto, Chen) expande essas folhas por sua vez. O artigo não diz até que profundidade uma única chamada Expand desce recursivamente; esta figura para nos usersets alcançados pelas regras do próprio documento. O artigo nomeia o caso de uso: o Expand permite que os clientes “reason about the complete set of users and groups that have access to their objects, which allows them to build efficient search indices for access-controlled content” (raciocinem sobre o conjunto completo de usuários e grupos que têm acesso a seus objetos, o que lhes permite construir índices de busca eficientes para conteúdo com controle de acesso) (§2.4.5).
Fontes
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang