Check responde a una pregunta: ¿puede este usuario hacer esto con este objeto? Una página de listado plantea otra: ¿qué objetos puede ver este usuario, filtrados, ordenados y de página en página? Esta página explica por qué la segunda pregunta es más difícil, qué ofrece el artículo para responderla y los tres enfoques que documentan los productos de estilo Zanzibar.
Una pregunta distinta de Check
Check parte de un objeto y recorre las tuplas hasta encontrar al usuario o quedarse sin caminos (§2.4.4, §3.2.3). El trabajo está acotado por lo que cuelga de ese objeto. “Todos los documentos que Anne puede ver” no tiene objeto de partida. Responderla con Check supone una comprobación por cada documento del sistema, la mayoría con respuesta “no”.
El listado necesita además datos que el servicio de autorización no tiene. La guía de OpenFGA lo expresa así: el servicio “does not store object metadata (names of files, creation dates, time of last update, etc)” (no almacena metadatos de los objetos: nombres de archivo, fechas de creación, hora de la última actualización, etc.), así que la búsqueda “will require data from your database” (requerirá datos de su base de datos) (OpenFGA, Search With Permissions). El filtrado y la ordenación ocurren en la base de datos propia; la autorización, en el otro servicio; la respuesta es la intersección de ambos.
El artículo conoce bien este caso de uso. Entre las ventajas que da para un sistema unificado está “a search index that respects access control and works across applications” (un índice de búsqueda que respete el control de acceso y funcione entre aplicaciones) (§1), y su objetivo de latencia destaca el “serving search results, which often require tens to hundreds of checks” (servir resultados de búsqueda, que con frecuencia requieren de decenas a cientos de comprobaciones) (§1).
Qué ofrece el artículo y qué no
La API del artículo tiene cinco llamadas: Read, Write, Watch, Check y Expand (§2.4). Ninguna devuelve “todos los objetos que el usuario U puede ver”.
- Read devuelve solo tuplas almacenadas. Con un conjunto de tuplas cuya clave es un usuario, los clientes pueden “look up all groups with a given user as a direct member” (buscar todos los grupos que tienen a un usuario dado como miembro directo) (§2.4.1). Directo: Read no aplica las reglas de reescritura, así que no sigue de
editoraviewerni de una carpeta a sus documentos. - Expand sigue las reglas de reescritura, pero en la otra dirección: toma un par ⟨object#relation⟩ y devuelve su “effective userset” (userset efectivo) como un árbol de usersets cuyas hojas “are user IDs or usersets pointing to other ⟨object#relation⟩ pairs” (son ID de usuario o usersets que apuntan a otros pares ⟨object#relation⟩) (§2.4.5). El artículo nombra el propósito: permite a los clientes “build efficient search indices for access-controlled content” (construir índices de búsqueda eficientes para contenido con control de acceso) (§2.4.5). Construir el índice es tarea del cliente.
- Watch transmite los cambios de tuplas para que “clients maintain secondary indices of relation tuples” (los clientes mantengan índices secundarios de las tuplas de relación) (§2.4.3).
- Leopard (§3.2.4) aplana los grupos anidados: responde si un usuario está en un grupo con una sola intersección de conjuntos. Se usa dentro de Zanzibar para acelerar Check en “selected namespaces” (determinados espacios de nombres); el artículo no lo describe como una API de listado. Véase Leopard, el índice de grupos.
¿Qué devuelve Expand para los lectores del readme, comparado con la lista plana que un cliente quiere en realidad?
Obsérvese que el árbol responde a “quién puede ver este documento”, no a “qué puede ver Anne”. Para listar los documentos de Anne solo con Expand, un cliente tendría que expandir todos los documentos o, como sugiere §2.4.5, expandir de antemano y guardar el resultado en su propio índice. La documentación de SpiceDB describe el mismo hueco: Expand “responds with a tree structure that can be awkward for applications to consume” (responde con una estructura de árbol que puede resultar incómoda de consumir para las aplicaciones), así que SpiceDB añadió LookupResources y LookupSubjects, que “return a flattened list of results” (devuelven una lista aplanada de resultados) (SpiceDB, Google Zanzibar).
Enfoque 1: una API de búsqueda y después filtrar en la base de datos
El servicio de autorización calcula directamente la pregunta inversa: LookupResources de SpiceDB y ListObjects de OpenFGA devuelven los ID de todos los objetos de un tipo sobre los que el usuario tiene un permiso. La aplicación pasa después esos ID a su consulta de base de datos (WHERE id = ANY(…)), que filtra, ordena y pagina como de costumbre. SpiceDB lo llama “the simplest approach from a bookkeeping perspective and is a good place to start” (el enfoque más sencillo desde el punto de vista de la gestión, y un buen punto de partida) (SpiceDB, Protecting a List Endpoint).
El coste es que el conjunto completo de ID vuelve antes de que se muestre la primera fila, y calcularlo recorre el grafo hacia atrás desde el usuario.
- SpiceDB: “it’s a heavy request that can cause performance problems when more than 10k results are involved” (es una solicitud pesada que puede causar problemas de rendimiento cuando hay más de 10k resultados) (SpiceDB, Querying Data); “can get slow quickly: with a sufficiently large relation dataset, a sufficiently complex schema, or a sufficiently large set of accessible results” (puede volverse lenta rápidamente: con un conjunto de relaciones lo bastante grande, un esquema lo bastante complejo o un conjunto de resultados accesibles lo bastante grande) (Protecting a List Endpoint). La solicitud transmite sus resultados en flujo y admite cursores.
- OpenFGA:
ListObjects“will return the results found within the time allotted (listObjectsDeadline, default:3s) up to the maximum number of results configured (listObjectsMaxResults, default:1000)” (devolverá los resultados encontrados dentro del tiempo asignado,listObjectsDeadline, por defecto3s, hasta el número máximo de resultados configurado,listObjectsMaxResults, por defecto1000), y se presenta para el “access-aware filtering on small object collections” (filtrado con control de acceso sobre colecciones pequeñas de objetos) (OpenFGA, Relationship Queries). Su rendimiento varía “drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate” (drásticamente según la complejidad del modelo, el número de tuplas y las relaciones que necesita evaluar), y las relaciones conandobut not“are more expensive to evaluate than relations withor” (son más costosas de evaluar que las relaciones conor) (Search With Permissions).
Una lista parcial no basta para ordenar: OpenFGA señala que “you won’t be able to sort using it” (no podrá ordenar con ella) hasta tener la lista completa (Search With Permissions).
Enfoque 2: consultar la base de datos y después comprobar en bloque
La otra dirección: dejar que la base de datos produzca una página de candidatos (filtrados y ordenados según la consulta del usuario), comprobar la página con una sola llamada en bloque (CheckBulkPermissions de SpiceDB, /batch-check de OpenFGA), descartar las filas denegadas y repetir hasta completar la página. Es Check usado tal como lo describe §1 para los resultados de búsqueda, de decenas a cientos a la vez.
La guía de SpiceDB da el bucle y sus restricciones: “because we don’t know how many results are going to be accessible beforehand, we need to iterate until we have a full page of accessible results” (como no sabemos de antemano cuántos resultados van a ser accesibles, necesitamos iterar hasta tener una página completa de resultados accesibles); el rendimiento “will depend in part on choosing the size of the page of candidate results” (dependerá en parte de la elección del tamaño de la página de resultados candidatos); y “works better with an API backed by cursor-based pagination than limit-offset pagination, since the database doesn’t know the offset associated with the last accessible result” (funciona mejor con una API respaldada por paginación basada en cursores que con paginación por límite y desplazamiento, ya que la base de datos no conoce el desplazamiento asociado al último resultado accesible) (Protecting a List Endpoint). También recomienda ejecutar todas las llamadas en bloque “at the same revision” (en la misma revisión): tomar el ZedToken (el zookie de SpiceDB) de la primera llamada y enviarlo con las demás, para que una página no se componga a partir de dos instantáneas.
¿En qué orden hacen sus llamadas los dos enfoques cuando Anne abre su lista de documentos?
Obsérvese hacia dónde se desplaza el coste. El prefiltrado paga una vez, en proporción a todo lo que Anne puede ver. El posfiltrado paga por ronda, en proporción a cuántos candidatos no puede ver. La guía de OpenFGA convierte esto en una regla: buscar y luego comprobar encaja cuando la consulta a la base de datos devuelve pocas filas o el usuario puede ver una proporción alta de ellas; encaja mal cuando el usuario ve muchos objetos que siguen siendo una proporción pequeña del total, su caso “Google Drive”, porque “you will be retrieving and checking against a lot of items and discarding most of them” (recuperará y comprobará muchos elementos y descartará la mayoría) (Search With Permissions).
Enfoque 3: un índice desnormalizado alimentado por Watch
El tercer enfoque es el que describen §2.4.3 y §2.4.5: mantener un índice propio de quién puede ver qué, junto a los datos que protege, y mantenerlo al día a partir del flujo de cambios. Una consulta de listado se convierte entonces en un join en la base de datos propia.
¿Dónde reside cada pieza y qué mantiene al día el índice?
Obsérvese la caja del indexador: hace el trabajo que Leopard hace dentro de Zanzibar. Una tupla puede cambiar muchas filas. Añadir group:eng#member@user:beto añade una fila por cada documento que group:eng puede ver; añadir un lector a folder:A añade una fila por cada documento de la carpeta. El artículo informa de la misma multiplicación (fan-out) en Leopard: “a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events” (una sola adición o eliminación de una tupla de Zanzibar puede dar lugar potencialmente a decenas de miles de eventos discretos de tuplas de Leopard) (§3.2.4).
Los productos documentan dos formas de construirlo:
- Construirlo uno mismo a partir del flujo de cambios. La opción 2 de OpenFGA consume
GET /changes, aplana los cambios para la versión del modelo en uso (su ejemplo: “user:anne, writer, doc:planningbecomes two tuples”, se convierte en dos tuplas) y después llama a/checksobre los resultados finales “to filter out any resource with permissions revoked but whose authorization data has not made it into your index yet” (para descartar cualquier recurso con permisos revocados cuyos datos de autorización aún no hayan llegado al índice) (Search With Permissions). Con SpiceDB, el flujo esWatch; Mantener las tuplas al día con los datos explica por qué ese flujo no es una cola duradera. - Dejar que lo calcule el proveedor. AuthZed Materialize “takes inspiration from the Leopard index” (se inspira en el índice Leopard), precalcula los permisos configurados, y su función Event Streams permite “keep your own copy of it — either colocated alongside the data it protects in your application database, or in a secondary index like a search engine” (mantener una copia propia, ya sea junto a los datos que protege en la base de datos de la aplicación o en un índice secundario como un motor de búsqueda) (AuthZed, What is Materialize?). Es una función comercial: Event Streams está “currently in early access for AuthZed Dedicated users” (actualmente en acceso anticipado para los usuarios de AuthZed Dedicated) (Protecting a List Endpoint), y entre sus limitaciones documentadas figura que “your application must be able to tolerate some lag” (la aplicación debe poder tolerar cierto retraso) (Materialize limitations).
Los tres, uno al lado del otro
Los límites de escala se citan de la documentación de cada producto. La latencia y el esfuerzo son relativos, no medidos.
| API de búsqueda y después consulta | Consulta y después comprobación en bloque | Índice alimentado por Watch | |
|---|---|---|---|
| Latencia | Crece con el número de objetos accesibles y la profundidad del esquema; conjunto completo antes de la primera fila | Crece con el número de rondas, es decir, con la proporción de candidatos denegados | Un join en la base de datos; independiente de la profundidad del grafo |
| Frescura | Las mismas opciones de consistencia que Check (ZedToken en SpiceDB; MINIMIZE_LATENCY / HIGHER_CONSISTENCY en OpenFGA) |
Igual que Check; usar un mismo token para todas las rondas de una página | Va por detrás del flujo; volver a comprobar la página para descartar filas revocadas |
| Límites de escala en la documentación | SpiceDB: “performance problems when more than 10k results are involved” (problemas de rendimiento cuando hay más de 10k resultados). OpenFGA: valores predeterminados 3s y 1000 resultados, “small object collections” (colecciones pequeñas de objetos) |
SpiceDB: depende de “the size of the page of candidate results” (el tamaño de la página de resultados candidatos). OpenFGA: malo cuando el usuario ve una proporción pequeña de muchos objetos | SpiceDB: “the greatest scalability of the three options” (la mayor escalabilidad de las tres opciones) (mediante Materialize) |
| Esfuerzo | Una llamada y una cláusula IN |
Un bucle, paginación por cursor, elegir el tamaño de página | Un indexador, lógica de aplanamiento, una posición del flujo almacenada, reconstrucciones; o un servicio comercial |
La guía de OpenFGA añade dos formas de hacer viable el posfiltrado cuando un usuario ve pocos objetos de entre muchos: filtrar por inquilino en la consulta a la base de datos (“Duplicating logic from the authorization model is not ideal, but it can be a reasonable trade-off”, duplicar lógica del modelo de autorización no es lo ideal, pero puede ser un compromiso razonable), o listar primero un recurso más grueso, por ejemplo las carpetas que puede ver un usuario, y filtrar los documentos por carpeta (Search With Permissions). En el ejemplo de referencia, el acceso de Chen procede de folder:A, así que “documentos en carpetas que Chen puede ver” lo cubre con una lista de una sola carpeta.
Una lista vacía también requiere una decisión. La guía de SpiceDB sugiere que, en sistemas de grano fino, “often makes sense to treat ‘there is no data’ and ‘there is nothing you’re authorized to see’ as the same, by returning a successful response with an empty result set” (a menudo tiene sentido tratar “no hay datos” y “no hay nada que esté autorizado a ver” como lo mismo, devolviendo una respuesta satisfactoria con un conjunto de resultados vacío) en lugar de un 403 (Protecting a List Endpoint).
Fuentes
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §1, §2.4.1, §2.4.3, §2.4.5, §3.2.4.
- AuthZed (proveedor), Protecting a List Endpoint, documentación de SpiceDB.
- AuthZed (proveedor), Querying Data, documentación de SpiceDB.
- AuthZed (proveedor), Google Zanzibar, documentación de SpiceDB, sección “Reverse Indices”.
- AuthZed (proveedor), What is Materialize? y Limitations.
- AuthZed, Proposal: Lookup Watch API and Tiger Cache for fast ACL-aware filtering, issue #207 de spicedb, abierto el 2021-10-22.
- OpenFGA, Search With Permissions.
- OpenFGA, Relationship Queries: Check, Read, Expand, ListObjects and ListUsers.
- OpenFGA, Query Consistency Modes.