Um Check faz uma única pergunta: este usuário está neste userset neste snapshot? Respondê-la pode exigir dezenas de leituras espalhadas por vários servidores. Esta página acompanha um Check por dentro: a expressão booleana em que ele se transforma, a ordem em que suas partes são executadas, quando ele pode encerrar cedo, o que ele deixa no cache e onde ele desiste.
Duas outras páginas cobrem o terreno vizinho. Tuplas de relação e usersets percorre a mesma pergunta um ramo de cada vez, como uma busca em grafo. Arquitetura acompanha a requisição entre servidores: consistent hashing, árvores de cache, a tabela de locks (lock table), o agrupamento de leituras e o hedging. Esta página permanece dentro da avaliação.
Um Check é uma expressão booleana
O artigo parte do caso sem regras de reescrita: “Zanzibar evaluates ACL checks by converting check requests to boolean expressions” (“O Zanzibar avalia verificações de ACL convertendo requisições de verificação em expressões booleanas”, §3.2.3). Para um usuário U e um userset ⟨object#relation⟩, a fórmula do artigo é:
CHECK(U, ⟨object#relation⟩) = ∃ tuple ⟨object#relation@U⟩
∨ ∃ tuple ⟨object#relation@U′⟩, where
U′ = ⟨object′#relation′⟩ s.t. CHECK(U, U′)
A primeira linha é um acerto direto: uma tupla armazenada nomeia o usuário. A segunda linha é a recursão: uma tupla armazenada nomeia outro userset, e o usuário está nesse outro. O artigo chama o ato de seguir essas referências de “pointer chasing” e observa que ele “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). As regras de reescrita entram na mesma expressão: “Userset rewrite rules are also translated to boolean expressions as part of check evaluation.” (“As regras de reescrita de userset também são traduzidas em expressões booleanas como parte da avaliação da verificação.”)
Tome a configuração da Figura 1 do artigo para doc (§2.3.1). viewer é a união de suas próprias tuplas, de editor e dos visualizadores da pasta pai; editor é a união de suas próprias tuplas e de owner. Escrita por extenso para Chen e o readme, supondo, como fazem as outras páginas, que folder#viewer não tem regra de reescrita:
viewer(readme, chen) = this(readme#viewer, chen)
∨ editor(readme, chen)
∨ ∃ parent tuple readme#parent@folder:X : viewer(folder:X, chen)
editor(readme, chen) = this(readme#editor, chen)
∨ this(readme#owner, chen)
Cada this(…) é uma consulta de tupla, e cada ∨ é um nó de uma árvore. Em quais subproblemas se divide a pergunta “Chen pode visualizar doc:readme?”?
Observe que os números nomeiam subproblemas, não uma sequência. As folhas ②, ④a, ④b e ⑥ precisam apenas das tuplas do próprio readme, e é por isso que o artigo usa o objeto como chave do encaminhamento (§3.2.5): todas elas podem ser respondidas pelo servidor responsável por doc:readme. O passo ⑦ é um novo Check sobre outro objeto, então é encaminhado ao servidor de folder:A, e é, ele próprio, uma árvore, aqui uma única consulta _this.
Todas as folhas de uma vez, e cancelamento
Em que ordem as folhas são executadas? O artigo não percorre a árvore: “To minimize check latency, we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (“Para minimizar a latência da verificação, avaliamos todos os nós folha da árvore de expressão booleana simultaneamente. Quando o resultado de um nó determina o resultado de uma subárvore, a avaliação dos demais nós da subárvore é cancelada.”, §3.2.3)
Como isso se desenrola no tempo para a verificação de Chen?
Observe que a latência é determinada pelo caminho mais rápido até uma resposta decisiva, e não pela folha mais lenta. Se o ramo da pasta pai tivesse sido lento e Chen não fosse visualizador, a raiz teria de esperar que todos os filhos respondessem falso.
O cancelamento economiza trabalho, mas deixa uma lacuna. Uma subverificação cancelada nunca grava seu resultado no cache, e outras requisições podem estar aguardando esse resultado na tabela de locks. O artigo se deparou exatamente com isso: “indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated.” (“verificações de ACL indiretas são frequentemente canceladas quando o resultado da verificação de ACL pai já está determinado. Isso deixa a chave de cache sem preenchimento.”) A correção: “we delay eager cancellation when there are waiters on the corresponding lock table entry” (“adiamos o cancelamento antecipado quando há requisições aguardando na entrada correspondente da tabela de locks”, §3.2.5).
Quando cada operador pode encerrar cedo
O artigo lista três maneiras de combinar subexpressões, “union, intersection, and exclusion” (“união, interseção e exclusão”, §2.3.1), e enuncia uma única regra de cancelamento para todas elas. Quando uma subárvore está “determinada” depende do operador. Qual resposta isolada basta para cada um?
Observe a assimetria. Cada operador tem uma resposta que pode chegar cedo e outra que exige todos os filhos. Para a união, a resposta antecipada é sim; para a interseção e a exclusão, é não. Assim, uma permissão escrita como união responde “permitido” tão rápido quanto seu caminho mais rápido, enquanto uma permissão com interseção ou exclusão responde “permitido” apenas tão rápido quanto sua parte obrigatória mais lenta. A tabela detalha:
| Operador | Decidido cedo por | Exige que todos os filhos digam |
|---|---|---|
União A ∪ B |
qualquer filho verdadeiro → verdadeiro | falso, para responder falso |
Interseção A ∩ B |
qualquer filho falso → falso | verdadeiro, para responder verdadeiro |
Exclusão A − B |
base falsa, ou excluído verdadeiro → falso | base verdadeira e excluído falso, para responder verdadeiro |
Os produtos seguem a mesma lógica. No check.go do OpenFGA (v1.22.1), o redutor de união retorna no primeiro resultado permitido (“Short-circuit success”), o redutor de interseção no primeiro resultado não permitido (“Short-circuit failure”), e o redutor de exclusão executa a base e o lado subtraído simultaneamente e retorna não permitido quando “base is false” (“a base é falsa”) ou quando “subtract is true” (“o lado subtraído é verdadeiro”). O post da AuthZed sobre interseções e exclusões (2022-03-03) diz que, para esses operadores, “SpiceDB can only partially short-circuit the subproblems” (“o SpiceDB só consegue fazer curto-circuito parcial dos subproblemas”), e, em seu exemplo, “SpiceDB was able to cancel the other check immediately” (“o SpiceDB conseguiu cancelar o outro check imediatamente”) assim que um ramo de uma interseção disse não. Para uniões, o post anterior (2021-03-17) diz de forma simples: “any path found suffices to grant permission!” (“qualquer caminho encontrado basta para conceder a permissão!”)
Armazenar sub-resultados em cache por snapshot
Cada nó da árvore é uma pergunta com uma resposta, e o artigo armazena todas em cache: os servidores “form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing” (“formam um cache distribuído tanto para leituras quanto para avaliações de verificação, incluindo resultados intermediários de verificação avaliados durante o pointer chasing”, §3.2.5). O passo ⑦ acima, “Chen está em folder:A#viewer?”, é um desses resultados intermediários. Qualquer verificação posterior que chegue à mesma pergunta pode reutilizá-lo.
O que torna a reutilização segura? Um resultado só é verdadeiro em um snapshot. O artigo coloca o snapshot na chave: “We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys.” (“Evitamos reutilizar resultados avaliados em um snapshot diferente codificando os timestamps de snapshot nas chaves de cache.”) Em seguida, arredonda os timestamps de avaliação para cima, “to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies” (“para uma granularidade grossa, como um ou dez segundos, respeitando as restrições de defasagem dos zookies das requisições”), de modo que a maioria das verificações caia nos mesmos poucos timestamps (§3.2.5; o arredondamento é desenhado na página de consistência).
Quando um sub-resultado em cache ajuda, e quando é um miss?
Observe que não há etapa de invalidação. Uma entrada com o snapshot na chave nunca pode se tornar errada, porque os dados em 13 s nunca mudam; ela apenas deixa de ser consultada quando a avaliação passa para timestamps posteriores. O post da AuthZed sobre a versão do SpiceDB desse mecanismo (2023-05-10) expressa a mesma ideia: “For any given problem or sub-problem, at a specified time, the result to the check is immutable” (“Para qualquer problema ou subproblema, em um instante especificado, o resultado da verificação é imutável”), e “if we were to change the evaluation timestamp, the cache keys would change as well” (“se mudássemos o timestamp de avaliação, as chaves de cache também mudariam”).
Mais dois mecanismos da §3.2.5 cercam esse cache, e ambos são desenhados na página de arquitetura: as árvores de cache formadas ao armazenar em cache “at both the caller and the callee of internal RPCs” (“tanto no chamador quanto no chamado das RPCs internas”), e a tabela de locks, em que “Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (“Entre as requisições que compartilham a mesma chave de cache, apenas uma começará a ser processada; as demais ficam bloqueadas até que o cache seja preenchido.”)
Nos produtos:
- O SpiceDB arredonda revisões em janelas definidas por
--datastore-revision-quantization-interval, padrão5s(dsconfig/config.go, v1.57.1), e envolve seu dispatcher em uma camadasingleflightque conta “dispatch requests that were single flighted” (“requisições de dispatch que passaram pelo single flight”), o que cumpre o papel da tabela de locks. - O cache de verificação do OpenFGA vem desativado por padrão (
checkQueryCache.enabledéfalse, TTL de10squando ativado) (configuração). Suas entradas expiram após um TTL em vez de pertencerem a um snapshot, e é por isso que o OpenFGA precisa de um modoHIGHER_CONSISTENCYpara ignorá-lo (consistência; veja Ordenação sem TrueTime).
As leituras são agrupadas por verificação
As folhas ②, ④a, ④b e ⑥ leem, todas, linhas de doc:readme. Em vez de enviar cada leitura isoladamente, “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner” (“Aplicamos um mecanismo de agrupamento para reunir as leituras de uma mesma verificação de ACL e minimizar o número de RPCs de leitura ao Spanner”, §3.2.3). O artigo não descreve o mecanismo além dessa frase. A página de arquitetura desenha as quatro leituras chegando a um mesmo servidor; o layout de armazenamento, ordenado por objeto e relação (§3.1.1), é o que permite que elas se tornem leituras de intervalo sobre linhas adjacentes.
Até que profundidade um Check pode ir
A recursão em CHECK(U, U′) não tem limite embutido: um grupo pode conter um grupo que contém um grupo, e nada no modelo de dados proíbe um ciclo. O que uma verificação faz quando encontra um?
O artigo não fixa nenhum número. Ele trata o aninhamento profundo e largo com o Leopard para “selected namespaces that exhibit such structure” (“namespaces selecionados que apresentam tal estrutura”, §3.2.4; veja a página do Leopard), e a §5 afirma “safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups)” (“pointer chasing seguro apesar de recursão potencialmente profunda (por exemplo, verificações de associação em grupos hierárquicos)”) sem dizer o que o torna seguro além disso. Os limites por cliente da §3.2.6 restringem CPU e RPCs pendentes, não a profundidade. Os produtos escolhem limites explícitos:
| Sistema | Limite | Padrão | Ao ser atingido | Fonte |
|---|---|---|---|---|
| Artigo | nenhum declarado | nenhum | não descrito | §3.2.4, §5 |
| SpiceDB | --dispatch-max-depth |
50 | erro: “the check request has exceeded the allowable maximum depth of 50” | Cyclical relationships and traversal limits, serve.go |
| OpenFGA | resolveNodeLimit |
25 | erro; ciclos são detectados antes e respondem não permitido | configuração, check.go |
| OpenFGA | resolveNodeBreadthLimit |
10 | limita “how many nodes on a given level can be evaluated concurrently” (quantos nós de um mesmo nível podem ser avaliados simultaneamente) | configuração |
| Ory Keto | limit.max_read_depth |
5 | o máximo global; uma requisição só pode reduzi-lo | config.schema.json |
A documentação do SpiceDB diz que ele não tem um detector de ciclos separado: um ciclo é executado até atingir o limite de profundidade e retorna o mesmo erro de uma hierarquia muito profunda, e a documentação explica que o rastreamento de objetos visitados foi evitado por razões de semântica e desempenho (recursion and max depth). O LocalChecker do OpenFGA mantém um conjunto de chaves de tupla visitadas por requisição e retorna não permitido com CycleDetected quando uma se repete (check.go, hasCycle). Ambos os limites contam saltos ao longo de um caminho, que é a profundidade da árvore da primeira figura; resolveNodeBreadthLimit é o único deles que restringe o “evaluate all leaf nodes … concurrently” (“avaliar todos os nós folha … simultaneamente”) do artigo.
Fontes
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.3.1, §3.1.1, §3.2.3, §3.2.4, §3.2.5, §3.2.6, §5.
- AuthZed, Check it out: How permissions are answered in SpiceDB and Authzed, 2021-03-17 (blog do fornecedor).
- AuthZed, Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed, 2022-03-03 (blog do fornecedor).
- AuthZed, Hotspot Caching in Google Zanzibar and SpiceDB, 2023-05-10 (blog do fornecedor).
- AuthZed, Cyclical Relationships and Traversal Limits, documentação do SpiceDB.
- Código-fonte do SpiceDB v1.57.1:
pkg/cmd/serve.go,pkg/cmd/datastore/dsconfig/config.go,internal/dispatch/singleflight/singleflight.go. - OpenFGA, Configuring OpenFGA e Query Consistency Modes.
- Código-fonte do OpenFGA v1.22.1:
internal/graph/check.go. - Ory Keto,
.schema/config.schema.json(limit.max_read_depth).