Check répond à une seule question : cet utilisateur peut-il faire ceci sur cet objet. Une page de liste en pose une autre : quels objets cet utilisateur peut-il voir, filtrés, triés et page par page. Cette page explique pourquoi la seconde question est plus difficile, ce que l’article fournit pour y répondre, et les trois approches que documentent les produits inspirés de Zanzibar.
Une autre question que Check
Check part d’un objet et parcourt les tuples jusqu’à trouver l’utilisateur ou épuiser les chemins (§2.4.4, §3.2.3). Le travail est borné par ce qui est rattaché à cet objet. « Tous les documents qu’Anne peut voir » n’a pas d’objet de départ. Y répondre avec Check signifie un Check par document du système, la plupart recevant la réponse « non ».
La liste a aussi besoin de données que le service d’autorisation ne détient pas. Le guide d’OpenFGA le formule ainsi : le service « does not store object metadata (names of files, creation dates, time of last update, etc) » (ne stocke pas les métadonnées des objets (noms de fichiers, dates de création, date de dernière mise à jour, etc.)), si bien que la recherche « will require data from your database » (nécessitera des données de votre base de données) (OpenFGA, Search With Permissions). Le filtrage et le tri se font dans votre base de données ; l’autorisation se fait dans l’autre service ; la réponse est l’intersection des deux.
L’article connaît bien ce cas d’usage. Parmi les avantages qu’il avance pour un système unifié figure « a search index that respects access control and works across applications » (un index de recherche qui respecte le contrôle d’accès et fonctionne d’une application à l’autre) (§1), et son objectif de latence cite expressément le fait de « serving search results, which often require tens to hundreds of checks » (servir des résultats de recherche, qui nécessitent souvent des dizaines à des centaines de vérifications) (§1).
Ce que l’article propose, et ce qu’il ne propose pas
L’API de l’article comporte cinq appels : Read, Write, Watch, Check et Expand (§2.4). Aucun ne renvoie « tous les objets que l’utilisateur U peut voir ».
- Read renvoie uniquement des tuples stockés. Avec un ensemble de tuples indexé par utilisateur, les clients peuvent « look up all groups with a given user as a direct member » (rechercher tous les groupes dont un utilisateur donné est membre direct) (§2.4.1). Direct : Read n’applique pas les règles de réécriture ; il ne suit donc ni
editorversviewer, ni un dossier vers ses documents. - Expand suit les règles de réécriture, mais dans l’autre sens : il prend une paire ⟨object#relation⟩ et renvoie son « effective userset » (userset effectif) sous la forme d’un arbre de userset dont les feuilles « are user IDs or usersets pointing to other ⟨object#relation⟩ pairs » (sont des identifiants d’utilisateurs ou des usersets pointant vers d’autres paires ⟨object#relation⟩) (§2.4.5). L’article en nomme le but : il permet aux clients de « build efficient search indices for access-controlled content » (construire des index de recherche efficaces pour du contenu soumis au contrôle d’accès) (§2.4.5). Construire l’index est le travail du client.
- Watch diffuse les modifications de tuples afin que les « clients maintain secondary indices of relation tuples » (clients maintiennent des index secondaires des tuples de relation) (§2.4.3).
- Leopard (§3.2.4) aplatit les groupes imbriqués : il répond à la question de savoir si un utilisateur appartient à un groupe par une seule intersection d’ensembles. Il est utilisé à l’intérieur de Zanzibar pour accélérer Check sur « selected namespaces » (certains espaces de noms) ; l’article ne le décrit pas comme une API de listage. Voir Leopard, l’index des groupes.
Que renvoie Expand pour les lecteurs du readme, comparé à la liste plate que veut réellement un client ?
Remarquez que l’arbre répond à « qui peut voir ce document », et non à « que peut voir Anne ». Pour lister les documents d’Anne avec Expand seul, un client devrait développer chaque document ou, comme le suggère le §2.4.5, développer à l’avance et conserver le résultat dans son propre index. La documentation de SpiceDB décrit la même lacune : Expand « responds with a tree structure that can be awkward for applications to consume » (répond par une structure arborescente qui peut être malcommode à exploiter pour les applications) ; SpiceDB a donc ajouté LookupResources et LookupSubjects, qui « return a flattened list of results » (renvoient une liste aplatie de résultats) (SpiceDB, Google Zanzibar).
Approche 1 : une API de recherche, puis un filtrage dans la base de données
Le service d’autorisation calcule directement la question inverse : LookupResources de SpiceDB et ListObjects d’OpenFGA renvoient les identifiants de tous les objets d’un type sur lesquels l’utilisateur dispose d’une permission. L’application passe ensuite ces identifiants à sa requête de base de données (WHERE id = ANY(…)), qui filtre, trie et pagine comme d’habitude. SpiceDB qualifie cela de « the simplest approach from a bookkeeping perspective and is a good place to start » (l’approche la plus simple du point de vue de la gestion, et un bon point de départ) (SpiceDB, Protecting a List Endpoint).
Le coût est que l’ensemble complet des identifiants revient avant que la première ligne soit affichée, et que son calcul parcourt le graphe à rebours depuis l’utilisateur.
- SpiceDB : « it’s a heavy request that can cause performance problems when more than 10k results are involved » (c’est une requête lourde qui peut causer des problèmes de performances lorsque plus de 10k résultats sont en jeu) (SpiceDB, Querying Data) ; elle « can get slow quickly: with a sufficiently large relation dataset, a sufficiently complex schema, or a sufficiently large set of accessible results » (peut vite devenir lente : avec un jeu de relations suffisamment grand, un schéma suffisamment complexe ou un ensemble de résultats accessibles suffisamment grand) (Protecting a List Endpoint). La requête diffuse ses résultats en flux et prend en charge les curseurs.
- 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) » (renverra les résultats trouvés dans le temps imparti (listObjectsDeadline, par défaut :3s), jusqu’au nombre maximal de résultats configuré (listObjectsMaxResults, par défaut :1000)), et est présenté comme destiné au « access-aware filtering on small object collections » (filtrage tenant compte des accès sur de petites collections d’objets) (OpenFGA, Relationship Queries). Ses performances varient « drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate » (considérablement selon la complexité du modèle, le nombre de tuples et les relations à évaluer), et les relations comportantandoubut not« are more expensive to evaluate than relations withor» (sont plus coûteuses à évaluer que les relations avecor) (Search With Permissions).
Une liste partielle ne suffit pas pour trier : OpenFGA note que « you won’t be able to sort using it » (vous ne pourrez pas trier à partir d’elle) tant que la liste complète n’est pas disponible (Search With Permissions).
Approche 2 : interroger la base de données, puis vérifier en lot
L’autre sens : laisser la base de données produire une page de candidats (filtrés et triés selon la requête de l’utilisateur), vérifier la page en un seul appel groupé (CheckBulkPermissions de SpiceDB, /batch-check d’OpenFGA), écarter les lignes refusées, et recommencer jusqu’à ce que la page soit pleine. C’est Check utilisé comme le §1 le décrit pour les résultats de recherche, par dizaines ou centaines à la fois.
Le guide de SpiceDB donne la boucle et ses contraintes : « 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 » (comme nous ne savons pas à l’avance combien de résultats seront accessibles, nous devons itérer jusqu’à obtenir une page complète de résultats accessibles) ; les performances « will depend in part on choosing the size of the page of candidate results » (dépendront en partie du choix de la taille de la page de résultats candidats) ; et cela « 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 » (fonctionne mieux avec une API reposant sur une pagination par curseur qu’avec une pagination limit-offset, puisque la base de données ne connaît pas le décalage associé au dernier résultat accessible) (Protecting a List Endpoint). Il recommande aussi d’exécuter tous les appels groupés « at the same revision » (à la même révision) : prendre le ZedToken (le zookie de SpiceDB) du premier appel et l’envoyer avec les suivants, afin qu’une même page ne soit pas assemblée à partir de deux instantanés.
Comment les deux approches ordonnent-elles leurs appels lorsqu’Anne ouvre sa liste de documents ?
Remarquez où se déplace le coût. Le pré-filtrage paie une fois, proportionnellement à tout ce qu’Anne peut voir. Le post-filtrage paie à chaque tour, proportionnellement au nombre de candidats qu’elle ne peut pas voir. Le guide d’OpenFGA en tire une règle : rechercher puis vérifier convient lorsque la requête de base de données renvoie peu de lignes ou que l’utilisateur peut en voir une forte proportion ; cela convient mal lorsque l’utilisateur voit de nombreux objets qui ne représentent pourtant qu’une faible part du total, son cas « Google Drive », car « you will be retrieving and checking against a lot of items and discarding most of them » (vous récupérerez et vérifierez beaucoup d’éléments pour en écarter la plupart) (Search With Permissions).
Approche 3 : un index dénormalisé alimenté par Watch
La troisième approche est celle que décrivent le §2.4.3 et le §2.4.5 : maintenir votre propre index de qui peut voir quoi, à côté des données qu’il protège, et le tenir à jour à partir du flux de modifications. Une requête de liste devient alors une jointure dans votre propre base de données.
Où se trouve chaque élément, et qu’est-ce qui maintient l’index à jour ?
Remarquez la boîte de l’indexeur : elle fait le travail que Leopard accomplit à l’intérieur de Zanzibar. Un tuple peut modifier de nombreuses lignes. Ajouter group:eng#member@user:beto ajoute une ligne pour chaque document que group:eng peut consulter ; ajouter un lecteur à folder:A ajoute une ligne pour chaque document du dossier. L’article rapporte la même démultiplication pour Leopard : « a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events » (un seul ajout ou une seule suppression de tuple Zanzibar peut produire potentiellement des dizaines de milliers d’événements distincts sur des tuples Leopard) (§3.2.4).
Les produits documentent deux façons de construire cet index :
- Le construire soi-même à partir du flux de modifications. L’option 2 d’OpenFGA consomme
GET /changes, aplatit les modifications pour la version du modèle utilisée (son exemple : «user:anne, writer, doc:planningbecomes two tuples » (user:anne, writer, doc:planningdevient deux tuples)), puis appelle/checksur les résultats finaux « to filter out any resource with permissions revoked but whose authorization data has not made it into your index yet » (pour écarter toute ressource dont les permissions ont été révoquées mais dont les données d’autorisation ne sont pas encore parvenues dans votre index) (Search With Permissions). Avec SpiceDB, le flux estWatch; Garder les tuples synchronisés avec vos données explique pourquoi ce flux n’est pas une file d’attente durable. - Le faire calculer par l’éditeur. AuthZed Materialize « takes inspiration from the Leopard index » (s’inspire de l’index Leopard), précalcule les permissions configurées, et sa fonctionnalité Event Streams vous permet de « 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 » (conserver votre propre copie, soit à côté des données qu’elle protège dans la base de données de votre application, soit dans un index secondaire tel qu’un moteur de recherche) (AuthZed, What is Materialize?). C’est une fonctionnalité commerciale : Event Streams est « currently in early access for AuthZed Dedicated users » (actuellement en accès anticipé pour les utilisateurs d’AuthZed Dedicated) (Protecting a List Endpoint), et ses limitations documentées incluent le fait que « your application must be able to tolerate some lag » (votre application doit pouvoir tolérer un certain retard) (limitations de Materialize).
Les trois approches comparées
Les limites d’échelle sont citées d’après la documentation de chaque produit. La latence et l’effort sont relatifs, non mesurés.
| API de recherche, puis requête | Requête, puis vérification en lot | Index alimenté par Watch | |
|---|---|---|---|
| Latence | Croît avec le nombre d’objets accessibles et la profondeur du schéma ; ensemble complet avant la première ligne | Croît avec le nombre de tours, c’est-à-dire avec la part de candidats refusés | Une jointure en base de données ; indépendante de la profondeur du graphe |
| Fraîcheur | Mêmes options de cohérence que Check (ZedToken dans SpiceDB ; MINIMIZE_LATENCY / HIGHER_CONSISTENCY dans OpenFGA) |
Comme Check ; utiliser un seul jeton pour tous les tours d’une page | En retard sur le flux ; revérifier la page pour écarter les lignes révoquées |
| Limites d’échelle documentées | SpiceDB : « performance problems when more than 10k results are involved ». OpenFGA : valeurs par défaut 3s et 1000 résultats, « small object collections » |
SpiceDB : dépend de « the size of the page of candidate results ». OpenFGA : médiocre lorsque l’utilisateur voit une faible part de nombreux objets | SpiceDB : « the greatest scalability of the three options » (via Materialize) |
| Effort | Un appel et une clause IN |
Une boucle, une pagination par curseur, un choix de taille de page | Un indexeur, une logique d’aplatissement, une position de flux stockée, des reconstructions ; ou un service commercial |
Le guide d’OpenFGA ajoute deux moyens de rendre le post-filtrage viable lorsqu’un utilisateur voit peu d’objets parmi beaucoup : filtrer par locataire dans la requête de base de données (« Duplicating logic from the authorization model is not ideal, but it can be a reasonable trade-off » (Dupliquer la logique du modèle d’autorisation n’est pas idéal, mais cela peut être un compromis raisonnable)), ou lister d’abord une ressource plus grossière, par exemple les dossiers qu’un utilisateur peut voir, puis filtrer les documents par dossier (Search With Permissions). Dans l’exemple suivi, l’accès de Chen provient de folder:A ; « les documents des dossiers que Chen peut consulter » le couvre donc avec une liste d’un seul dossier.
Une liste vide exige aussi une décision. Le guide de SpiceDB suggère que, dans les systèmes à granularité fine, il « 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 » (est souvent judicieux de traiter “il n’y a pas de données” et “il n’y a rien que vous soyez autorisé à voir” de la même façon, en renvoyant une réponse réussie avec un ensemble de résultats vide) plutôt qu’une erreur 403 (Protecting a List Endpoint).
Sources
- 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 (éditeur), Protecting a List Endpoint, documentation de SpiceDB.
- AuthZed (éditeur), Querying Data, documentation de SpiceDB.
- AuthZed (éditeur), Google Zanzibar, documentation de SpiceDB, section « Reverse Indices ».
- AuthZed (éditeur), What is Materialize? et Limitations.
- AuthZed, Proposal: Lookup Watch API and Tiger Cache for fast ACL-aware filtering, ticket spicedb #207, ouvert le 2021-10-22.
- OpenFGA, Search With Permissions.
- OpenFGA, Relationship Queries: Check, Read, Expand, ListObjects and ListUsers.
- OpenFGA, Query Consistency Modes.